超全總結(jié)！一文囊括李航《統(tǒng)計學(xué)習(xí)方法》幾乎所有的知識點！（李航統(tǒng)計方法的課后答案）

如果大家對機(jī)器學(xué)習(xí)算法有所涉獵的話，想必你一定看過《統(tǒng)計學(xué)習(xí)方法》這本書，里面介紹了統(tǒng)計學(xué)中的一些基本算法和知識點，本文進(jìn)行了詳細(xì)的總結(jié)。

轉(zhuǎn)載來源

閱讀本文大概需要 19 分鐘。

閱讀目錄：

1. 知識點

2. 感知機(jī)

3. k 近鄰法

4. 樸素貝葉斯

5. 決策樹

6. logistic 回歸和最大熵模型

7. 支持向量機(jī)

8. 提升方法

9. EM 算法

10. 隱馬爾可夫模型 ( HMM )

11. 統(tǒng)計學(xué)習(xí)方法總結(jié)

12. 神經(jīng)網(wǎng)絡(luò)

13. K-Means

14. Bagging

15. Apriori

16. 降維方法

17. 引用

因為要準(zhǔn)備面試，本文以李航的《統(tǒng)計學(xué)習(xí)方法》為主，結(jié)合西瓜書等其他資料對機(jī)器學(xué)習(xí)知識做一個整理。

一、知識點

進(jìn)程和線程：進(jìn)程和線程都是一個時間段的描述，是 CPU 工作時間段的描述，不過是顆粒大小不同。進(jìn)程就是包換上下文切換的程序執(zhí)行時間總和 = CPU 加載上下文 + CPU 執(zhí)行 + CPU 保存上下文。線程是共享了進(jìn)程的上下文環(huán)境的更為細(xì)小的 CPU 時間段。

判別式模型和生成式模型：

判別式模型直接學(xué)習(xí)決策函數(shù) f(X) 或條件概率分布 P(Y|X) 作為預(yù)測的模型。往往準(zhǔn)確率更高，并且可以簡化學(xué)習(xí)問題。如 k 近鄰法/感知機(jī)/決策樹/最大熵模型/ Logistic 回歸/線性判別分析 ( LDA ) /支持向量機(jī) ( SVM ) / Boosting /條件隨機(jī)場算法 ( CRF ) /線性回歸/神經(jīng)網(wǎng)絡(luò)

生成式模型由數(shù)據(jù)學(xué)習(xí)聯(lián)合概率分布 P(X，Y)，然后由 P(Y|X)=P(X，Y)/P(X) 求出條件概率分布作為預(yù)測的模型,即生成模型。當(dāng)存在隱變量時只能用生成方法學(xué)習(xí)。如混合高斯模型和其他混合模型/隱馬爾可夫模型 ( HMM ) /樸素貝葉斯/依賴貝葉斯 ( AODE ) / LDA 文檔主題生成模型。

概率質(zhì)量函數(shù)，概率密度函數(shù)，累積分布函數(shù)：

概率質(zhì)量函數(shù) ( probability mass function，PMF ) 是離散隨機(jī)變量在各特定取值上的概率。

概率密度函數(shù) ( probability density function，PDF ) 是對?連續(xù)隨機(jī)變量?定義的，本身不是概率，只有對連續(xù)隨機(jī)變量的取值進(jìn)行積分后才是概率。

累積分布函數(shù) ( cumulative distribution function，CDF ) 能完整描述一個實數(shù)隨機(jī)變量 X 的概率分布，是概率密度函數(shù)的積分。對於所有實數(shù) x，與 pdf 相對。

極大似然估計：已知某個參數(shù)能使這個樣本出現(xiàn)的概率最大，我們當(dāng)然不會再去選擇其他小概率的樣本，所以干脆就把這個參數(shù)作為估計的真實值。

最小二乘法：二乘的英文是 least?square，找一個 ( 組 ) 估計值，使得實際值與估計值之差的平方加總之后的最小。求解方式是對參數(shù)求偏導(dǎo)，令偏導(dǎo)為0即可。樣本量小時速度快。

梯度下降法：負(fù)梯度方向是函數(shù)值下降最快的方向，每次更新值都等于原值加學(xué)習(xí)率 ( 步長 ) 乘損失函數(shù)的梯度。每次都試一個步長看會不會下降一定的程度，如果沒有的話就按比例減小步長。不斷應(yīng)用該公式直到收斂，可以得到局部最小值。初始值的不同組合可以得到不同局部最小值，在最優(yōu)點時會有震蕩。

批量梯度下降 ( BGD )：每次都使用所有的 m 個樣本來更新，容易找到全局最優(yōu)解，但是 m 較大時速度較慢。

隨機(jī)梯度下降 ( SGD )：每次只使用一個樣本來更新，訓(xùn)練速度快，但是噪音較多，不容易找到全局最優(yōu)解，以損失很小的一部分精確度和增加一定數(shù)量的迭代次數(shù)為代價，換取了總體的優(yōu)化效率的提升。注意控制步長縮小，減少震蕩。

小批量梯度下降 ( MBGD )：每次使用一部分樣本來更新。

牛頓法：牛頓法是二次收斂，因此收斂速度快。從幾何上看是每次用一個二次曲面來擬合當(dāng)前所處位置的局部曲面，而梯度下降法是用一個平面來擬合。

紅色的是牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。牛頓法起始點不能離極小點太遠(yuǎn)，否則很可能不會擬合。

黑塞矩陣是由目標(biāo)函數(shù) f(x) 在點 X 處的二階偏導(dǎo)數(shù)組成的 n*n 階對稱矩陣。

牛頓法：將 f(x) 在 x(k) 附近進(jìn)行二階泰勒展開：

其中，gk 是 f(x) 的梯度向量在 x(k) 的值，H(x(k)) 是 f(x) 的黑塞矩陣在點 x(k) 的值。牛頓法利用極小點的必要條件 f(x) 處的梯度為0，每次迭代中從點 x(k) 開始，假設(shè)，對二階泰勒展開求偏導(dǎo)有，代入得到，即，以此為迭代公式就是牛頓法。

擬牛頓法：用一個 n 階正定矩陣 Gk=G(x(k)) 來近似代替黑塞矩陣的逆矩陣就是擬牛頓法的基本思想。在牛頓法中黑塞矩陣滿足的條件如下：，令，則有，稱為擬牛頓條件。根據(jù)選擇 Gk 方法的不同有多種具體實現(xiàn)方法。

DFP 算法：假設(shè)每一步，為使 Gk+1 滿足擬牛頓條件，可使 Pk 和 Qk 滿足，，例如取，，就得到迭代公式

BFGS 算法：最流行的擬牛頓算法。考慮用 Bk 逼近黑塞矩陣，此時相應(yīng)的擬牛頓條件是，假設(shè)每一步，則 Pk 和 Qk 滿足，，類似得到迭代公式

先驗概率和后驗概率：

先驗概率就是事情發(fā)生前的預(yù)測概率。

后驗概率是一種條件概率，它限定了事件為隱變量取值，而條件為觀測結(jié)果。一般的條件概率，條件和事件可以是任意的。

貝葉斯公式 P(y|x) = ( P(x|y) * P(y) ) / P(x) 中，P(y|x) 是后驗概率，P(x|y) 是條件概率，P(y) 是先驗概率。

偏差，方差，噪聲：

偏差：度量了學(xué)習(xí)算法的期望預(yù)測和真實結(jié)果偏離程度。

方差：度量了同樣大小的訓(xùn)練集的變動所導(dǎo)致的學(xué)習(xí)性能的變化，即刻畫了數(shù)據(jù)擾動所造成的影響。

噪聲：可以認(rèn)為是數(shù)據(jù)自身的波動性，表達(dá)了目前任何學(xué)習(xí)算法所能達(dá)到泛化誤差的下限。

泛化誤差可以分解為偏差、方差與噪聲之和。

對偶原理：一個優(yōu)化問題可以從主問題和對偶問題兩個方面考慮。在推導(dǎo)對偶問題時，通過將拉格朗日函數(shù)對 x 求導(dǎo)并使導(dǎo)數(shù)為0來獲得對偶函數(shù)。對偶函數(shù)給出了主問題最優(yōu)解的下界，因此對偶問題一般是凸問題，那么只需求解對偶函數(shù)的最優(yōu)解就可以了。

KKT 條件：通常我們要求解的最優(yōu)化條件有如下三種：

無約束優(yōu)化問題：通常使用求導(dǎo)，使導(dǎo)數(shù)為零，求解候選最優(yōu)值。

有等式約束的優(yōu)化問題：通常使用拉格朗日乘子法，即把等式約束用拉格朗日乘子和優(yōu)化問題合并為一個式子，通過對各個變量求導(dǎo)使其為零，求解候選最優(yōu)值。拉格朗日乘數(shù)法其實是 KKT 條件在等式約束優(yōu)化問題的簡化版。

有不等式約束的優(yōu)化問題：通常使用 KKT 條件。即把不等式約束，等式約束和優(yōu)化問題合并為一個式子。假設(shè)有多個等式約束 h(x) 和不等式約束 g(x)

則不等式約束引入的KKT條件如下：

實質(zhì)是最優(yōu)解在 g(x)<0 區(qū)域內(nèi)時，約束條件不起作用，等價于對 μ 置零然后對原函數(shù)的偏導(dǎo)數(shù)置零；當(dāng) g(x)=0 時與情況2相近。結(jié)合兩種情況，那么只需要使 L 對 x 求導(dǎo)為零，使 h(x) 為零，使 μg(x) 為零三式即可求解候選最優(yōu)值。

性能度量：

準(zhǔn)確度，最常用，但在數(shù)據(jù)集不平衡的情況下不好。

Precision ( 精確度/查準(zhǔn)率 )：P=TP/(TP+FP)

Recall ( 召回率/查全率 )：R=TP/(TP+FN)

Fβ 度量：，當(dāng) β=1 時退化為 F1 度量，是精確率和召回率的調(diào)和均值。

TPR ( 真正例率 )：TPR=TP/(TP+FN)

FPR ( 假正例率 )：FPR=FP/(TN+FP)

PR 曲線：縱軸為 Precision，橫軸為 Recall，一般使用平衡點 ( BEP，即 Precsion=Recall 的點 ) 作為衡量標(biāo)準(zhǔn)。

ROC ( 接受者操作特征 ) 曲線：縱軸為 TRP，橫軸為 FPR，在繪圖時將分類閾值依次設(shè)為每個樣例的預(yù)測值,再連接各點。ROC 曲線圍住的面積稱為 AOC，AOC 越大則學(xué)習(xí)器性能越好。

損失函數(shù)和風(fēng)險函數(shù)：

損失函數(shù)度量模型一次預(yù)測的好壞。常用的損失函數(shù)有：0-1損失函數(shù)，平方損失函數(shù)，絕對損失函數(shù)，對數(shù)似然損失函數(shù)。

損失函數(shù)的期望是理論上模型關(guān)于聯(lián)合分布 P(X，Y) 的平均意義下的損失，稱為風(fēng)險函數(shù)，也叫期望風(fēng)險。但是聯(lián)合分布是未知的，期望風(fēng)險不能直接計算。

當(dāng)樣本容量 N 趨于無窮時經(jīng)驗風(fēng)險趨于期望風(fēng)險，但現(xiàn)實中訓(xùn)練樣本數(shù)目有限。

經(jīng)驗風(fēng)險最小化和結(jié)構(gòu)風(fēng)險最小化：

模型關(guān)于訓(xùn)練數(shù)據(jù)集的平均損失稱為經(jīng)驗風(fēng)險。經(jīng)驗風(fēng)險最小化的策略就是最小化經(jīng)驗風(fēng)險。當(dāng)樣本數(shù)量足夠大時學(xué)習(xí)效果較好。比如當(dāng)模型是條件概率分布，損失函數(shù)是對數(shù)損失函數(shù)時，經(jīng)驗風(fēng)險最小化就等價于極大似然估計。但是當(dāng)樣本容量很小時會出現(xiàn)過擬合。

結(jié)構(gòu)風(fēng)險最小化等于正則化。結(jié)構(gòu)風(fēng)險在經(jīng)驗風(fēng)險上加上表示模型復(fù)雜度的正則化項。比如當(dāng)模型是條件概率分布，損失函數(shù)是對數(shù)損失函數(shù)，模型復(fù)雜度由模型的先驗概率表示時，結(jié)構(gòu)風(fēng)險最小化就等價于最大后驗概率估計。

過擬合是指學(xué)習(xí)時選擇的模型所包含的參數(shù)過多，以致于對已知數(shù)據(jù)預(yù)測得很好，但對未知數(shù)據(jù)預(yù)測很差的現(xiàn)象。模型選擇旨在避免過擬合并提高模型的預(yù)測能力。

正則化是模型選擇的典型方法。正則化項一般是模型復(fù)雜度的單調(diào)遞增函數(shù)，比如模型參數(shù)向量的范數(shù)。

交叉驗證是另一常用的模型選擇方法，可分為簡單交叉驗證，K 折交叉驗證，留一交叉驗證等。

二、感知機(jī)

感知機(jī)是二類分類的線性模型，屬于判別模型。感知機(jī)學(xué)習(xí)旨在求出將訓(xùn)練數(shù)據(jù)進(jìn)行線性劃分的分離超平面。是神經(jīng)網(wǎng)絡(luò)和支持向量機(jī)的基礎(chǔ)。

模型：，w 叫作權(quán)值向量，b 叫做偏置，sign 是符號函數(shù)。

感知機(jī)的幾何解釋：wx+b 對應(yīng)于特征空間中的一個分離超平面 S，其中 w 是 S 的法向量，b 是 S 的截距。S 將特征空間劃分為兩個部分，位于兩個部分的點分別被分為正負(fù)兩類。

策略：假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的，感知機(jī)的損失函數(shù)是誤分類點到超平面 S 的總距離。因為誤分類點到超平面S的距離是，且對于誤分類的數(shù)據(jù)來說，總有成立，因此不考慮 1/||w||，就得到感知機(jī)的損失函數(shù)：，其中 M 是誤分類點的集合。感知機(jī)學(xué)習(xí)的策略就是選取使損失函數(shù)最小的模型參數(shù)。

算法：感知機(jī)的最優(yōu)化方法采用隨機(jī)梯度下降法。首先任意選取一個超平面 w0，b0，然后不斷地極小化目標(biāo)函數(shù)。在極小化過程中一次隨機(jī)選取一個誤分類點更新 w，b，直到損失函數(shù)為0。

其中 η 表示步長。該算法的直觀解釋是：當(dāng)一個點被誤分類，就調(diào)整 w，b 使分離超平面向該誤分類點接近。感知機(jī)的解可以不同。

對偶形式：假設(shè)原始形式中的 w0 和 b0 均為0，設(shè)逐步修改 w 和 b 共 n 次，令 a=nη，最后學(xué)習(xí)到的 w，b 可以表示為

那么對偶算法就變?yōu)樵O(shè)初始 a 和 b 均為0，每次選取數(shù)據(jù)更新 a 和 b 直至沒有誤分類點為止。對偶形式的意義在于可以將訓(xùn)練集中實例間的內(nèi)積計算出來，存在 Gram 矩陣中，可以大大加快訓(xùn)練速度。

三、k 近鄰法

k 近鄰法根據(jù)其 k 個最近鄰的訓(xùn)練實例的類別，通過多數(shù)表決等方式進(jìn)行預(yù)測。k 值的選擇，距離度量及分類決策規(guī)則是 k 近鄰法的三個基本要素。當(dāng) k=1 時稱為最近鄰算法。

模型：當(dāng)訓(xùn)練集，距離度量，k 值以及分類決策規(guī)則確定后，特征空間已經(jīng)根據(jù)這些要素被劃分為一些子空間，且子空間里每個點所屬的類也已被確定。

策略：

距離：特征空間中兩個實例點的距離是相似程度的反映，k 近鄰算法一般使用歐氏距離，也可以使用更一般的 Lp 距離或 Minkowski 距離。

k 值：k 值較小時，整體模型變得復(fù)雜，容易發(fā)生過擬合。k 值較大時，整體模型變得簡單。在應(yīng)用中 k 一般取較小的值，通過交叉驗證法選取最優(yōu)的 k 。

分類決策規(guī)則：k 近鄰中的分類決策規(guī)則往往是多數(shù)表決，多數(shù)表決規(guī)則等價于經(jīng)驗風(fēng)險最小化。

算法：根據(jù)給定的距離度量，在訓(xùn)練集中找出與 x 最鄰近的 k 個點，根據(jù)分類規(guī)則決定 x 的類別 y 。

kd 樹：

kd 樹就是一種對 k 維空間中的實例點進(jìn)行存儲以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。kd 樹更適用于訓(xùn)練實例數(shù)遠(yuǎn)大于空間維數(shù)時的 k 近鄰搜索。

構(gòu)造，可以通過如下遞歸實現(xiàn)：在超矩形區(qū)域上選擇一個坐標(biāo)軸和此坐標(biāo)軸上的一個切分點，確定一個超平面，該超平面將當(dāng)前超矩形區(qū)域切分為兩個子區(qū)域。在子區(qū)域上重復(fù)切分直到子區(qū)域內(nèi)沒有實例時終止。通常依次選擇坐標(biāo)軸和選定坐標(biāo)軸上的中位數(shù)點為切分點，這樣可以得到平衡 kd 樹。

搜索：從根節(jié)點出發(fā)，若目標(biāo)點 x 當(dāng)前維的坐標(biāo)小于切分點的坐標(biāo)則移動到左子結(jié)點，否則移動到右子結(jié)點，直到子結(jié)點為葉結(jié)點為止。以此葉結(jié)點為 " 當(dāng)前最近點 "，遞歸地向上回退，在每個結(jié)點：(a) 如果該結(jié)點比當(dāng)前最近點距離目標(biāo)點更近，則以該結(jié)點為 " 當(dāng)前最近點 " ( b ) " 當(dāng)前最近點 " 一定存在于該結(jié)點一個子結(jié)點對應(yīng)的區(qū)域,檢查該結(jié)點的另一子結(jié)點對應(yīng)的區(qū)域是否與以目標(biāo)點為球心，以目標(biāo)點與 " 當(dāng)前最近點 " 間的距離為半徑的超球體相交。如果相交，移動到另一個子結(jié)點，如果不相交，向上回退。持續(xù)這個過程直到回退到根結(jié)點，最后的 " 當(dāng)前最近點 " 即為最近鄰點。

四、樸素貝葉斯

樸素貝葉斯是基于貝葉斯定理和特征條件獨(dú)立假設(shè)的分類方法。首先學(xué)習(xí)輸入/輸出的聯(lián)合概率分布，然后基于此模型，對給定的輸入 x，利用貝葉斯定理求出后驗概率最大的輸出 y。屬于生成模型。

模型：首先學(xué)習(xí)先驗概率分布，然后學(xué)習(xí)條件概率分布

如果估計實際，需要指數(shù)級的計算，所以樸素貝葉斯法對條件概率分布作了條件獨(dú)立性的假設(shè)，上式變成在分類時，通過學(xué)習(xí)到的模型計算后驗概率分布，由貝葉斯定理得到：

將條件獨(dú)立性假設(shè)得到的等式代入，并且注意到分母都是相同的，所以得到樸素貝葉斯分類器：

樸素貝葉斯將實例分到后驗概率最大的類中，這等價于期望風(fēng)險最小化。

算法：使用極大似然估計法估計相應(yīng)的先驗概率和條件概率，計算條件獨(dú)立性假設(shè)下的實例各個取值的可能性，選取其中的最大值作為輸出。

用極大似然估計可能會出現(xiàn)所要估計的概率值為0的情況，在累乘后會影響后驗概率的計算結(jié)果，使分類產(chǎn)生偏差。可以采用貝葉斯估計，在隨機(jī)變量各個取值的頻數(shù)上賦予一個正數(shù)。

Sj 為 j 屬性可能取值數(shù)量，當(dāng) λ=0 時就是極大似然估計。常取 λ=1，稱為拉普拉斯平滑。

如果是連續(xù)值的情況，可以假設(shè)連續(xù)變量服從高斯分布，然后用訓(xùn)練數(shù)據(jù)估計參數(shù)。

五、決策樹

決策樹是一種基本的分類與回歸方法。它可以認(rèn)為是 if-then 規(guī)則的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布。主要優(yōu)點是模型具有可讀性,分類速度快。

模型：分類決策樹由結(jié)點和有向邊組成.結(jié)點分為內(nèi)部結(jié)點(表示一個特征或?qū)傩?和葉結(jié)點(表示一個類)。決策樹的路徑具有互斥且完備的性質(zhì)。

策略：決策樹學(xué)習(xí)本質(zhì)上是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則。我們需要的是一個與訓(xùn)練數(shù)據(jù)矛盾較小，同時具有很好的泛化能力的決策樹。從所有可能的決策樹中選取最優(yōu)決策樹是 NP 完全問題，所以現(xiàn)實中常采用啟發(fā)式方法近似求解。

算法：決策樹學(xué)習(xí)算法包含特征選擇，決策樹的生成與決策樹的剪枝過程。生成只考慮局部最優(yōu)，剪枝則考慮全局最優(yōu)。

特征選擇：如果利用一個特征進(jìn)行分類的結(jié)果與隨機(jī)分類的結(jié)果沒有很大差別，則稱這個特征是沒有分類能力的。扔掉這樣的特征對決策樹學(xué)習(xí)的精度影響不大。

信息熵：熵是衡量隨機(jī)變量不確定性的度量。熵越大，隨機(jī)變量的不確定性就越大。信息熵是信息量的期望。條件熵表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。

信息增益：表示得知特征 X 的信息而使得類 Y 的信息的不確定性減少的程度。定義為集合 D 的經(jīng)驗熵與特征 A 在給定條件下 D 的經(jīng)驗條件熵之差，也就是訓(xùn)練數(shù)據(jù)集中類與特征的互信息。

信息增益算法：計算數(shù)據(jù)集 D 的經(jīng)驗熵，計算特征 A 對數(shù)據(jù)集 D 的經(jīng)驗條件熵，計算信息增益,選取信息增益最大的特征。

信息增益比：信息增益值的大小是相對于訓(xùn)練數(shù)據(jù)集而言的,并無絕對意義。使用信息增益比可以對這一問題進(jìn)行校正。

決策樹的生成：

ID3 算法：核心是在決策樹各個結(jié)點上應(yīng)用信息增益準(zhǔn)則選擇信息增益最大且大于閾值的特征,遞歸地構(gòu)建決策樹。ID3 相當(dāng)于用極大似然法進(jìn)行概率模型的選擇。由于算法只有樹的生成，所以容易產(chǎn)生過擬合。

C4.5 算法：C4.5 算法與 ID3 算法相似，改用信息增益比來選擇特征。

決策樹的剪枝：

在學(xué)習(xí)時過多考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過于復(fù)雜的決策樹，產(chǎn)生過擬合現(xiàn)象。解決方法是對已生成的決策樹進(jìn)行簡化，稱為剪枝。

設(shè)樹的葉結(jié)點個數(shù)為 |T|，每個葉結(jié)點有 Nt 個樣本點，其中 k 類樣本點有 Ntk 個，剪枝往往通過極小化決策樹整體的損失函數(shù)來實現(xiàn)，其中經(jīng)驗熵。剪枝通過加入 a|T| 項來考慮模型復(fù)雜度，實際上就是用正則化的極大似然估計進(jìn)行模型選擇。

剪枝算法：剪去某一子結(jié)點，如果生成的新的整體樹的損失函數(shù)值小于原樹，則進(jìn)行剪枝，直到不能繼續(xù)為止。具體可以由動態(tài)規(guī)劃實現(xiàn)。

CART 算法：

CART 既可以用于分類也可以用于回歸。它假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點特征的取值為 " 是 " 和 " 否 " 。遞歸地構(gòu)建二叉樹，對回歸樹用平方誤差最小化準(zhǔn)則，對分類數(shù)用基尼指數(shù)最小化準(zhǔn)則。

回歸樹的生成：在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸地將每個區(qū)域劃分為兩個子區(qū)域。選擇第 j 個變量和它取的值 s 作為切分變量和切分點，并定義兩個區(qū)域，遍歷變量 j，對固定的 j 掃描切分點 s，求解。用選定的對 ( j，s ) 劃分區(qū)域并決定相應(yīng)的輸出值直到滿足停止條件。

基尼指數(shù)：假設(shè)有 K 個類，樣本屬于第 k 類的概率為 pk，則概率分布的基尼指數(shù)為，表示不確定性。在特征 A 的條件下集合 D 的基尼指數(shù)定義為，表示分割后集合 D 的不確定性。基尼指數(shù)越大，樣本集合的不確定性也就越大。

分類樹的生成：從根結(jié)點開始，遞歸進(jìn)行以下操作：設(shè)結(jié)點的訓(xùn)練數(shù)據(jù)集為 D，對每個特征 A 和其可能取的每個值 a，計算 A=a 時的基尼指數(shù)，選擇基尼指數(shù)最小的特征及其對應(yīng)的切分點作為最優(yōu)特征與最優(yōu)切分點，生成兩個子結(jié)點，直至滿足停止條件。停止條件一般是結(jié)點中的樣本個數(shù)小于閾值，或樣本集的基尼指數(shù)小于閾值，或沒有更多特征。

CART 剪枝:

Tt 表示以 t 為根結(jié)點的子樹，|Tt| 是 Tt 的葉結(jié)點個數(shù)。可以證明當(dāng)時，Tt 與 t 有相同的損失函數(shù)值，且t的結(jié)點少，因此 t 比 Tt 更可取，對 Tt 進(jìn)行剪枝。自下而上地對各內(nèi)部結(jié)點 t 計算，并令 a=min(g(t))，自上而下地訪問內(nèi)部節(jié)點 t，如果有 g(t)=a，進(jìn)行剪枝，并對 t 以多數(shù)表決法決定其類，得到子樹 T，如此循環(huán)地生成一串子樹序列，直到新生成的 T 是由根結(jié)點單獨(dú)構(gòu)成的樹為止。利用交叉驗證法在子樹序列中選取最優(yōu)子樹。

如果是連續(xù)值的情況,一般用二分法作為結(jié)點來劃分。

六、logistic 回歸和最大熵模型

邏輯斯諦分布:

分布函數(shù)f(x)以點(μ,1/2)為中心對稱,γ的值越小,曲線在中心附近增長得越快.

邏輯斯諦回歸模型：對于給定的輸入 x，根據(jù)和計算出兩個條件概率值的大小，將 x 分到概率值較大的那一類。將偏置 b 加入到權(quán)值向量 w 中，并在 x 的最后添加常數(shù)項1，得到和如果某事件發(fā)生的概率是 p，則該事件發(fā)生的幾率 ( 此處幾率指該事件發(fā)生概率與不發(fā)生概率之比 ) 是 p/1-p，對數(shù)幾率是 log(p/1-p)，那么，也就是說在邏輯斯諦回歸模型中，輸出 Y=1 的對數(shù)幾率是輸入 x 的線性函數(shù)，線性函數(shù)值越接近正無窮，概率值就越接近1，反之則越接近0。

似然估計：給定 x 的情況下參數(shù) θ 是真實參數(shù)的可能性。

模型參數(shù)估計：對于給定的二分類訓(xùn)練數(shù)據(jù)集，對數(shù)似然函數(shù)為

也就是損失函數(shù)。其中 P(Y=1|x)=π(x)，對 L(w) 求極大值，就可以得到 w 的估計值。問題變成了以對數(shù)似然函數(shù)為目標(biāo)函數(shù)的最優(yōu)化問題。

多項邏輯斯諦回歸：當(dāng)問題是多分類問題時，可以作如下推廣：設(shè) Y 有 K 類可能取值，，，實際上就是 one-vs-all 的思想，將其他所有類當(dāng)作一個類，問題轉(zhuǎn)換為二分類問題。

最大熵原理：學(xué)習(xí)概率模型時，在所有可能的概率模型中，熵最大的模型是最好的模型。直觀地，最大熵原理認(rèn)為模型首先要滿足已有的事實，即約束條件。在沒有更多信息的情況下，那些不確定的部分都是 " 等可能的 " 。

最大熵模型：給定訓(xùn)練數(shù)據(jù)集，可以確定聯(lián)合分布 P(X，Y) 的經(jīng)驗分布和邊緣分布 P(X) 的經(jīng)驗分布，其中 v 表示頻數(shù)，N 表示樣本容量。用特征函數(shù) f(x，y)=1 描述 x 與 y 滿足某一事實，可以得到特征函數(shù)關(guān)于 P(X，Y) 的經(jīng)驗分布的期望值和關(guān)于模型 P(Y|X) 與 P(X) 的經(jīng)驗分布的期望值，假設(shè)兩者相等，就得到了約束條件

定義在條件概率分布 P(Y|X) 上的條件熵為，則條件熵最大的模型稱為最大熵模型。

最大熵模型的學(xué)習(xí)就是求解最大熵模型的過程。等價于約束最優(yōu)化問題

將求最大值問題改為等價的求最小值問題

引入拉格朗日乘子

將原始問題轉(zhuǎn)換為無約束最優(yōu)化的對偶問題首先求解內(nèi)部的極小化問題,即求 L(P，W) 對 P(y|x) 的偏導(dǎo)數(shù)

并令偏導(dǎo)數(shù)等于0，解得

可以證明對偶函數(shù)等價于對數(shù)似然函數(shù)，那么對偶函數(shù)極大化等價于最大熵模型的極大似然估計

之后可以用最優(yōu)化算法求解得到 w 。

最大熵模型與邏輯斯諦回歸模型有類似的形式，它們又稱為對數(shù)線性模型。模型學(xué)習(xí)就是在給定的訓(xùn)練數(shù)據(jù)條件下對模型進(jìn)行極大似然估計或正則化的極大似然估計。

算法：似然函數(shù)是光滑的凸函數(shù)，因此多種最優(yōu)化方法都適用。

改進(jìn)的迭代尺度法 ( IIS )：假設(shè)當(dāng)前的參數(shù)向量是 w，如果能找到一種方法 w->w+δ 使對數(shù)似然函數(shù)值變大，就可以重復(fù)使用這一方法，直到找到最大值。

邏輯斯諦回歸常應(yīng)用梯度下降法，牛頓法或擬牛頓法。

七、支持向量機(jī)

模型：支持向量機(jī) ( SVM ) 是一種二類分類模型。它的基本模型是定義在特征空間上的間隔最大的線性分類器。支持向量機(jī)還包括核技巧，使它成為實質(zhì)上的非線性分類器。分離超平面，分類決策函數(shù)

策略：間隔最大化,可形式化為一個求解凸二次規(guī)劃的問題，也等價于正則化的合頁損失函數(shù)的最小化問題。

當(dāng)訓(xùn)練數(shù)據(jù)線性可分時，通過硬間隔最大化，學(xué)習(xí)出線性可分支持向量機(jī)。當(dāng)訓(xùn)練數(shù)據(jù)近似線性可分時，通過軟間隔最大化，學(xué)習(xí)出線性支持向量機(jī)。當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時，通過使用核技巧及軟間隔最大化，學(xué)習(xí)非線性支持向量機(jī)。

核技巧：當(dāng)輸入空間為歐式空間或離散集合，特征空間為希爾伯特空間時，核函數(shù)表示將輸入從輸入空間映射到特征空間得到的特征向量之間的內(nèi)積。通過核函數(shù)學(xué)習(xí)非線性支持向量機(jī)等價于在高維的特征空間中學(xué)習(xí)線性支持向量機(jī)。這樣的方法稱為核技巧。

考慮一個二類分類問題，假設(shè)輸入空間與特征空間為兩個不同的空間，輸入空間為歐氏空間或離散集合，特征空間為歐氏空間或希爾伯特空間。支持向量機(jī)都將輸入映射為特征向量，所以支持向量機(jī)的學(xué)習(xí)是在特征空間進(jìn)行的。

支持向量機(jī)的最優(yōu)化問題一般通過對偶問題化為凸二次規(guī)劃問題求解，具體步驟是將等式約束條件代入優(yōu)化目標(biāo),通過求偏導(dǎo)求得優(yōu)化目標(biāo)在不等式約束條件下的極值。

線性可分支持向量機(jī)：

當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時，存在無窮個分離超平面可將兩類數(shù)據(jù)正確分開。利用間隔最大化得到唯一最優(yōu)分離超平面和相應(yīng)的分類決策函數(shù)稱為線性可分支持向量機(jī)。

函數(shù)間隔：一般來說，一個點距離分離超平面的遠(yuǎn)近可以表示分類預(yù)測的確信程度。在超平面確定的情況下，|wx+b| 能夠相對地表示點x距離超平面的遠(yuǎn)近，而 wx+b 與 y 的符號是否一致能夠表示分類是否正確。所以可用來表示分類的正確性及確信度，這就是函數(shù)間隔。注意到即使超平面不變，函數(shù)間隔仍會受 w 和 b 的絕對大小影響。

幾何間隔：一般地，當(dāng)樣本點被超平面正確分類時，點 x 與超平面的距離是，其中 ||w|| 是 w 的 l2 范數(shù)。這就是幾何間隔的定義。定義超平面關(guān)于訓(xùn)練數(shù)據(jù)集 T 的幾何間隔為超平面關(guān)于 T 中所有樣本點的幾何間隔之最小值。可知，當(dāng) ||w||=1 時幾何間隔和函數(shù)間隔相等。

硬間隔最大化：對線性可分的訓(xùn)練集而言，這里的間隔最大化又稱為硬間隔最大化。直觀解釋是對訓(xùn)練集找到幾何間隔最大的超平面意味著以充分大的確信度對訓(xùn)練數(shù)據(jù)進(jìn)行分類。求最大間隔分離超平面即約束最優(yōu)化問題：

將幾何間隔用函數(shù)間隔表示

并且注意到函數(shù)間隔的取值并不影響最優(yōu)化問題的解，不妨令函數(shù)間隔=1，并讓最大化 1/||w|| 等價為最小化 ||w||^2/2，問題變?yōu)橥苟我?guī)劃問題

支持向量和間隔邊界：與分離超平面距離最近的樣本點的實例稱為支持向量。支持向量是使最優(yōu)化問題中的約束條件等號成立的點。因此對 y=+1 的正例點和 y=-1 的負(fù)例點，支持向量分別在超平面 H1：wx+b=+1 和 H2：wx+b=-1 。H1 和 H2 平行，兩者之間形成一條長帶，長帶的寬度??稱為間隔，H1 和 H2 稱為間隔邊界。在決定分離超平面時只有支持向量起作用，所以支持向量機(jī)是由很少的"重要的"訓(xùn)練樣本確定的。由對偶問題同樣可以得到支持向量一定在間隔邊界上。

對偶算法：引進(jìn)拉格朗日乘子，定義拉格朗日函數(shù)

根據(jù)拉格朗日對偶性,原始問題的對偶問題是極大極小問題：

先求對 w，b 的極小值。將 L(w，b，a) 分別對 w，b 求偏導(dǎo)數(shù)并令其等于0，得

代入拉格朗日函數(shù)得

這就是極小值。

接下來對極小值求對 a 的極大，即是對偶問題

將求極大轉(zhuǎn)換為求極小

由KKT條件成立得到

其中 j 為使 aj*>0 的下標(biāo)之一。所以問題就變?yōu)榍髮ε紗栴}的解 a*，再求得原始問題的解 w*，b*，從而得分離超平面及分類決策函數(shù)可以看出 w* 和 b* 都只依賴訓(xùn)練數(shù)據(jù)中 ai*>0 的樣本點 (xi，yi)，這些實例點 xi 被稱為支持向量。

線性支持向量機(jī)：

如果訓(xùn)練數(shù)據(jù)是線性不可分的，那么上述方法中的不等式約束并不能都成立，需要修改硬間隔最大化，使其成為軟間隔最大化。

線性不可分意味著某些特異點不能滿足函數(shù)間隔大于等于1的約束條件，可以對每個樣本點引進(jìn)一個松弛變量，使函數(shù)間隔加上松弛變量大于等于1，約束條件變?yōu)椋瑫r對每個松弛變量，支付一個代價，目標(biāo)函數(shù)變?yōu)椋渲?C>0 稱為懲罰參數(shù)，C 值越大對誤分類的懲罰也越大。新目標(biāo)函數(shù)包含了兩層含義：使間隔盡量大，同時使誤分類點的個數(shù)盡量小。

軟間隔最大化，學(xué)習(xí)問題變成如下凸二次規(guī)劃問題：

可以證明 w 的解是唯一的，但 b 的解存在一個區(qū)間。線性支持向量機(jī)包含線性可分支持向量機(jī)，因此適用性更廣。

對偶算法：原始問題的對偶問題是,構(gòu)造拉格朗日函數(shù)

先求對 w，b，ξ 的極小值，分別求偏導(dǎo)并令導(dǎo)數(shù)為0，得

代入原函數(shù)，再對極小值求 a 的極大值，得到

利用后三條約束消去 μ，再將求極大轉(zhuǎn)換為求極小，得到對偶問題

由 KKT 條件成立可以得到

j 是滿足 00，求得對偶問題 ( 凸二次規(guī)劃問題 ) 的最優(yōu)解 a*，代入計算 w* 和 b*，求得分離超平面和分類決策函數(shù)。因為 b 的解并不唯一，所以實際計算 b* 時可以取所有樣本點上的平均值。

支持向量：在線性不可分的情況下，將對應(yīng)與 ai*>0 的樣本點 (xi，yi) 的實例點xi稱為支持向量。軟間隔的支持向量或者在間隔邊界上，或者在間隔邊界與分類超平面之間，或者再分離超平面誤分一側(cè)。

合頁損失函數(shù)：可以認(rèn)為是0-1損失函數(shù)的上界，而線性支持向量機(jī)可以認(rèn)為是優(yōu)化合頁損失函數(shù)構(gòu)成的目標(biāo)函數(shù)。

非線性支持向量機(jī)：

如果分類問題是非線性的，就要使用非線性支持向量機(jī)。主要特點是使用核技巧。

非線性分類問題，用線性分類方法求解非線性分類問題分為兩步：首先使用一個變換將原空間的數(shù)據(jù)映射到新空間，然后在新空間里用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型。

核函數(shù)：設(shè) X 是輸入空間(歐式空間的子集或離散集合)，H 為特征空間(希爾伯特空間)，一般是高維甚至無窮維的。如果存在一個從 X 到 H 的映射使得對所有 x，z 屬于 X，函數(shù) K(x,z) 滿足條件，點乘代表內(nèi)積，則稱 K(x，z) 為核函數(shù)。

核技巧：基本思想是通過一個非線性變換將輸入空間對應(yīng)于一個特征空間，使得在輸入空間中的超曲面模型對應(yīng)于特征空間中的超平面模型 ( 支持向量機(jī) ) 。在學(xué)習(xí)和預(yù)測中只定義核函數(shù) K(x，z)，而不顯式地定義映射函數(shù)。對于給定的核 K(x，z)，特征空間和映射函數(shù)的取法并不唯一。注意到在線性支持向量機(jī)的對偶問題中，目標(biāo)函數(shù)和決策函數(shù)都只涉及輸入實例與實例之間的內(nèi)積，xi`xj 可以用核函數(shù) K(xi，xj)=Ф(xi)`Ф(xj) 來代替。當(dāng)映射函數(shù)是非線性函數(shù)時，學(xué)習(xí)到的含有核函數(shù)的支持向量機(jī)是非線性分類模型。在實際應(yīng)用中，往往依賴領(lǐng)域知識直接選擇核函數(shù)。

正定核：通常所說的核函數(shù)是指正定核函數(shù)。只要滿足正定核的充要條件，那么給定的函數(shù) K(x，z) 就是正定核函數(shù)。設(shè)K是定義在 X*X 上的對稱函數(shù)，如果任意 xi 屬于 X，K(x，z) 對應(yīng)的 Gram 矩陣是半正定矩陣，則稱 K(x，z) 是正定核。這一定義在構(gòu)造核函數(shù)時很有用，但要驗證一個具體函數(shù)是否為正定核函數(shù)并不容易，所以在實際問題中往往應(yīng)用已有的核函數(shù)。

算法：選取適當(dāng)?shù)暮撕瘮?shù) K(x，z) 和適當(dāng)?shù)膮?shù) C，將線性支持向量機(jī)對偶形式中的內(nèi)積換成核函數(shù)，構(gòu)造并求解最優(yōu)化問題

選擇最優(yōu)解 a* 的一個正分量 0

常用核函數(shù)：

多項式核函數(shù) ( polynomial?kernel?function )：

，對應(yīng)的支持向量機(jī)是一個 p 次多項式分類器，分類決策函數(shù)為

高斯核函數(shù) ( Gaussian?krenel?function )：

對應(yīng)的支持向量機(jī)是高斯徑向基函數(shù) ( RBF ) 分類器。分類決策函數(shù)為

字符串核函數(shù) ( string kernel function )：

核函數(shù)不僅可以定義在歐氏空間上，還可以定義在離散數(shù)據(jù)的集合上。字符串核函數(shù)給出了字符串中長度等于 n 的所有子串組成的特征向量的余弦相似度。

序列最小最優(yōu)化 ( SMO ) 算法：

SMO 是一種快速求解凸二次規(guī)劃問題

的算法。

基本思路是：如果所有變量都滿足此優(yōu)化問題的 KKT 條件，那么解就得到了。否則，選擇兩個變量，固定其他變量，針對這兩個變量構(gòu)建一個二次規(guī)劃問題。不斷地將原問題分解為子問題并對子問題求解，就可以求解原問題。注意子問題兩個變量中只有一個是自由變量，另一個由等式約束確定。

兩個變量二次規(guī)劃的求解方法：假設(shè)選擇的兩個變量是 a1，a2，其他變量是固定的，于是得到子問題

ε 是常數(shù)，目標(biāo)函數(shù)式省略了不含 a1，a2 的常數(shù)項。考慮不等式約束和等式約束，要求的是目標(biāo)函數(shù)在一條平行于對角線的線段上的最優(yōu)值

問題變?yōu)閱巫兞康淖顑?yōu)化問題。假設(shè)初始可行解為 aold，最優(yōu)解為 anew，考慮沿著約束方向未經(jīng)剪輯的最優(yōu)解 anew，unc ( 即未考慮不等式約束 ) 。對該問題求偏導(dǎo)數(shù)，并令導(dǎo)數(shù)為0，代入原式，令

得到，經(jīng)剪輯后 a2 的解是

L 與 H 是 a2new 所在的對角線段端點的界。并解得

變量的選擇方法：在每個子問題中選擇兩個變量優(yōu)化，其中至少一個變量是違反 KKT 條件的。第一個變量的選取標(biāo)準(zhǔn)是違反 KKT 條件最嚴(yán)重的樣本點，第二個變量的選取標(biāo)準(zhǔn)是希望能使該變量有足夠大的變化，一般可以選取使對應(yīng)的 |E1-E2| 最大的點。在每次選取完點后，更新閾值 b 和差值 Ei 。

八、提升方法

提升 ( boosting ) 是一種常用的統(tǒng)計學(xué)習(xí)方法，是集成學(xué)習(xí)的一種。它通過改變訓(xùn)練樣本的權(quán)重 ( 概率分布 )，學(xué)習(xí)多個弱分類器 ( 基本分類器 )，并將這些分類器線性組合來構(gòu)成一個強(qiáng)分類器提高分類的性能。

AdaBoost：

AdaBoost 提高那些被前一輪弱分類器錯誤分類樣本的權(quán)值，而降低那些被正確分類樣本的權(quán)值。然后采取加權(quán)多數(shù)表決的方法組合弱分類器。

算法：首先假設(shè)訓(xùn)練數(shù)據(jù)集具有均勻的權(quán)值分布 D1，使用具有權(quán)值分布 Dm 的訓(xùn)練數(shù)據(jù)集學(xué)習(xí)得到基本分類器 Gm(x)，計算分類誤差率和 Gm(x) 的系數(shù)，更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布其中

Zm 是使 Dm+1 成為概率分布的規(guī)范化因子

重復(fù)上述操作 M 次后得到 M 個弱分類器，構(gòu)建線性組合得到最終分類器

AdaBoost 算法也可以理解成模型為加法模型，損失函數(shù)為指數(shù)函數(shù)，學(xué)習(xí)算法為前向分步算法的二類分類學(xué)習(xí)方法。

前向分步算法：考慮加法模型其中 b(x，γm) 為基函數(shù)，γm 為基函數(shù)的參數(shù)，βm 為基函數(shù)的系數(shù)。在給定損失函數(shù) L(y，f(x)) 的條件下，學(xué)習(xí)加法模型就是求解損失函數(shù)極小化問題

前向分步算法求解的想法是：從前往后，每一步只學(xué)習(xí)一個基函數(shù)及其系數(shù)，優(yōu)化

得到參數(shù) βm 和 γm，更新，逐步逼近優(yōu)化目標(biāo)。最終得到加法模型。

提升樹：

提升樹是模型為加法模型，算法為前向分布算法，基函數(shù)為決策樹的提升方法。第 m 步的模型是，通過經(jīng)驗風(fēng)險極小化確定下一棵決策樹的參數(shù)。不同問題的提升樹學(xué)習(xí)算法主要區(qū)別在于使用的損失函數(shù)不同。

二類分類問題：只需將 AdaBoost 算法中的基本分類器限制為二類分類數(shù)即可。

回歸問題：如果將輸入空間劃分為J個互不相交的區(qū)域，并且在每個區(qū)域上確定輸出的常量 Cj，那么樹可表示為，

其中

提升樹采用前向分步算法：

當(dāng)采用平方誤差損失函數(shù)時，損失變?yōu)?/p>

其中r是當(dāng)前模型擬合數(shù)據(jù)的殘差。每一步都只需擬合殘差學(xué)習(xí)一個回歸樹即可。

梯度提升樹 ( GBDT )：利用最速下降法的近似方法來實現(xiàn)每一步的優(yōu)化，關(guān)鍵在于用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值作為回歸問題中提升樹算法中的殘差的近似值,每一步以此來估計回歸樹葉結(jié)點區(qū)域以擬合殘差的近似值，并利用線性搜索估計葉結(jié)點區(qū)域的值使損失函數(shù)最小化，然后更新回歸樹即可。

AdaBoost 產(chǎn)生的基礎(chǔ)學(xué)習(xí)器有好有壞，因此加入權(quán)重。提升樹產(chǎn)生的基礎(chǔ)學(xué)習(xí)器是一個不斷減少殘差的過程，并不是一個單獨(dú)的分類器，因此一般不加權(quán)重。

XGBoost，相比傳統(tǒng) GBDT 有以下優(yōu)點：

在優(yōu)化時用到了二階導(dǎo)數(shù)信息。

在代價函數(shù)里加入了正則項。

每次迭代后都將葉子結(jié)點的權(quán)重乘上一個系數(shù)，削弱每棵樹的影響。

列抽樣。

在訓(xùn)練前對數(shù)據(jù)進(jìn)行排序，保存為 block 結(jié)構(gòu)，并行地對各個特征進(jìn)行增益計算。

九、EM 算法

EM 算法是一種迭代算法，用于含有隱變量的概率模型參數(shù)的極大似然估計。每次迭代由兩步組成：E 步，求期望 ( expectation )，M 步，求極大值 ( maximization )，直至收斂為止。

隱變量：不能被直接觀察到，但是對系統(tǒng)的狀態(tài)和能觀察到的輸出存在影響的一種東西。

算法：

選擇參數(shù)的初始值 θ(0)，開始迭代。注意 EM 算法對初值是敏感的。

E 步：θ(i) 為第 i 次迭代參數(shù)θ的估計值，在第 i+1 次迭代的E步，計算

P(Z|Y，θ(i)) 是在給定觀測數(shù)據(jù) Y 和當(dāng)前參數(shù)估計 θ(i) 下隱變量數(shù)據(jù)Z的條件概率分布。

M 步：求使 Q(θ，θ(i)) 極大化的 θ，確定第 i+1 次迭代的參數(shù)的估計值

重復(fù)2和3直到收斂，一般是對較小的正數(shù) ε1 和 ε2 滿足

則停止迭代。

EM 算法是通過不斷求解下界的極大化逼近求解對數(shù)似然函數(shù)極大化的算法。可以用于生成模型的非監(jiān)督學(xué)習(xí)。生成模型由聯(lián)合概率分布 P(X，Y) 表示。X 為觀測數(shù)據(jù)，Y 為未觀測數(shù)據(jù)。

高斯混合模型 ( GMM )：高斯混合模型是指具有如下形式的概率分布模型：，其中

稱為第 k 個分模型。

高斯混合模型參數(shù)估計的 EM 算法：

取參數(shù)的初始值開始迭代

E 步：計算分模型k對觀測數(shù)據(jù) yj 的響應(yīng)度

M 步：計算新一輪迭代的模型參數(shù)

重復(fù)2和3直到對數(shù)似然函數(shù)

收斂。

十、隱馬爾可夫模型 ( HMM )

隱馬爾可夫模型是關(guān)于時序的概率模型，描述由一個隱藏的馬爾可夫鏈隨機(jī)生成不可觀測的狀態(tài)序列，再由各個狀態(tài)生成一個觀測而產(chǎn)生觀測隨機(jī)序列的過程。

設(shè) Q 是所有可能的狀態(tài)的集合，V 是所有可能的觀測的集合，I 是長度為T的狀態(tài)序列，O 是對應(yīng)的觀測序列，A 是狀態(tài)轉(zhuǎn)移概率矩陣，aij 表示在時刻t處于狀態(tài) qi 的條件下在時刻 t+1 轉(zhuǎn)移到狀態(tài) qj 的概率。B 是觀測概率矩陣，bij 是在時刻 t 處于狀態(tài) qj 的條件下生成觀測 vk 的概率。π 是初始狀態(tài)概率向量，πi 表示時刻 t=1 處于狀態(tài) qi 的概率。隱馬爾可夫模型由初始狀態(tài)概率向量 π，狀態(tài)轉(zhuǎn)移概率矩陣 A 以及觀測概率矩陣 B 確定。π 和 A 決定即隱藏的馬爾可夫鏈，生成不可觀測的狀態(tài)序列。B 決定如何從狀態(tài)生成觀測，與狀態(tài)序列綜合確定了觀測序列。因此，隱馬爾可夫模型可以用三元符號表示。

隱馬爾可夫模型作了兩個基本假設(shè)：

齊次馬爾可夫性假設(shè)：假設(shè)隱藏的馬爾可夫鏈在任意時刻 t 的狀態(tài)只依賴于其前一時刻的狀態(tài)。

觀測獨(dú)立性假設(shè)：假設(shè)任意時刻的觀測只依賴于該時刻的馬爾可夫鏈的狀態(tài)。

隱馬爾可夫模型有三個基本問題，即概率計算問題，學(xué)習(xí)問題，預(yù)測問題。

概率計算問題：給定模型和觀測序列，計算在模型λ下觀測序列 O 出現(xiàn)的概率 P(O|λ) 。

直接計算法：最直接的方法是列舉所有可能長度為 T 的狀態(tài)序列，求各個狀態(tài)序列I與觀測序列 O 的聯(lián)合概率，但計算量太大，實際操作不可行。

前向算法：定義到時刻 t 部分觀測序列為 o1~ot 且狀態(tài)為 qi 的概率為前向概率，記作初始化前向概率，遞推，對 t=1~T-1，得到減少計算量的原因在于每一次計算直接引用前一個時刻的計算結(jié)果，避免重復(fù)計算。

后向算法：定義在時刻 t 狀態(tài)為qi的條件下，從 t+1 到 T 的部分觀測序列為 oi+1~oT 的概率為后向概率，記作初始化后向概率，遞推，對 t=T-1~1，，得到

學(xué)習(xí)算法：已知觀測，估計模型的參數(shù)，使得在該模型下觀測序列概率 P(O|λ) 最大。根據(jù)訓(xùn)練數(shù)據(jù)是否包括觀察序列對應(yīng)的狀態(tài)序列分別由監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)實現(xiàn)。

監(jiān)督學(xué)習(xí)：估計轉(zhuǎn)移概率

和觀測概率

初始狀態(tài)概率 πi 的估計為 S 個樣本中初始狀態(tài)為 qi 的頻率。

非監(jiān)督學(xué)習(xí) ( Baum-Welch 算法 )：將觀測序列數(shù)據(jù)看作觀測數(shù)據(jù) O，狀態(tài)序列數(shù)據(jù)看作不可觀測的隱數(shù)據(jù) I。首先確定完全數(shù)據(jù)的對數(shù)似然函數(shù)求 Q 函數(shù)

用拉格朗日乘子法極大化Q函數(shù)求模型參數(shù)

預(yù)測問題：也稱為解碼問題。已知模型和觀測序列，求對給定觀測序列條件概率 P(I|O) 最大的狀態(tài)序列

近似算法：在每個時刻t選擇在該時刻最有可能出現(xiàn)的狀態(tài) it*，從而得到一個狀態(tài)序列作為預(yù)測的結(jié)果。優(yōu)點是計算簡單，缺點是不能保證狀態(tài)序列整體是最有可能的狀態(tài)序列。

維特比算法：用動態(tài)規(guī)劃求概率最大路徑，這一條路徑對應(yīng)著一個狀態(tài)序列。從 t=1 開始，遞推地計算在時刻t狀態(tài)為i的各條部分路徑的最大概率，直至得到時刻 t=T 狀態(tài)為i的各條路徑的最大概率。時刻 t=T 的最大概率即為最優(yōu)路徑的概率 P*，最優(yōu)路徑的終結(jié)點it*也同時得到，之后從終結(jié)點開始由后向前逐步求得結(jié)點，得到最優(yōu)路徑。

十一、統(tǒng)計學(xué)習(xí)方法總結(jié)

---?以下內(nèi)容并非出自《統(tǒng)計學(xué)習(xí)方法》---

十二、神經(jīng)網(wǎng)絡(luò)

神經(jīng)元 ( 感知器 ) 接收到來自 n 個其他神經(jīng)元傳遞過來的輸入信號，這些輸入信號通過帶權(quán)重的連接進(jìn)行傳遞，神經(jīng)元將接收到的總輸入值與神經(jīng)元的閾值進(jìn)行比較,然后通過激活函數(shù)處理以產(chǎn)生神經(jīng)元的輸出。把許多個這樣的神經(jīng)元按一定的層次結(jié)構(gòu)連接起來就得到了神經(jīng)網(wǎng)絡(luò)。一般使用反向傳播 ( BP ) 算法來進(jìn)行訓(xùn)練。

反向傳播 ( BP ) 算法：

前向傳播：將訓(xùn)練集數(shù)據(jù)輸入，經(jīng)過隱藏層，到達(dá)輸出層并輸出結(jié)果。

計算估計值與實際值之間的誤差，并將該誤差從輸出層向輸入層反向傳播。

在反向傳播的過程中，根據(jù)誤差使用梯度下降與鏈?zhǔn)椒▌t調(diào)整各種參數(shù)的值。

不斷迭代直至收斂。

深度神經(jīng)網(wǎng)絡(luò) ( DNN )：可以理解為有很多隱藏層的神經(jīng)網(wǎng)絡(luò)。DNN 內(nèi)部分為輸入層 ( 第一層 )，隱藏層，輸出層(最后一層)。層與層之間是全連接的。

卷積神經(jīng)網(wǎng)絡(luò) ( CNN )：一般用于圖像識別。通過卷積核和感受野的乘積形成卷積后的輸出。在每一個卷積層之后，通常會使用一個 ReLU ( 修正線性單元 ) 函數(shù)來把所有的負(fù)激活都變?yōu)榱恪Ｔ趲讉€卷積層之后也許會用一個池化層 ( 采樣層 ) 來輸出過濾器卷積計算的每個子區(qū)域中的最大數(shù)字或平均值。

循環(huán)神經(jīng)網(wǎng)絡(luò) ( RNN )：如果訓(xùn)練樣本輸入是連續(xù)序列，則 DNN 和 CNN 不好解決。RNN 假設(shè)樣本是基于序列的，對應(yīng)的輸入是樣本序列中的 x(t)，而模型在序列索引號 t 位置的隱藏狀態(tài) h(t) 由 x(t) 和 h(t-1) 共同決定。在任意序列索引號t有對應(yīng)的模型預(yù)測輸出 o(t) 。也就是說，RNN 是包含循環(huán)的網(wǎng)絡(luò)，允許信息的持久化。

長短期記憶網(wǎng)絡(luò) ( LSTM )：一種特殊的 RNN，可以學(xué)習(xí)長期依賴信息。

十三、K-Means

K-Means 是無監(jiān)督的聚類算法。思想是對于給定的樣本集，按照樣本之間的距離大小將樣本集劃分為 K 個簇，讓簇內(nèi)的點盡量緊密地連在一起，而讓簇間的距離盡量的大。

傳統(tǒng)算法：

用先驗知識或交叉驗證選擇一個合適的 k 值。

隨機(jī)選擇 k 個樣本作為初始的質(zhì)心。注意初始化質(zhì)心的選擇對最后的聚類結(jié)果和運(yùn)行時間都有很大的影響。

計算每個樣本點和各個質(zhì)心的距離，將樣本點標(biāo)記為距離最小的質(zhì)心所對應(yīng)的簇。

重新計算每個簇的質(zhì)心，取該簇中每個點位置的平均值。

重復(fù)2，3，4步直到 k 個質(zhì)心都沒有發(fā)生變化為止。

K-Means++：用于優(yōu)化隨機(jī)初始化質(zhì)心的方法

從輸入樣本點中隨機(jī)選擇一個點作為第一個質(zhì)心。

計算每一個樣本點到已選擇的質(zhì)心中最近質(zhì)心的距離 D(x)。

選擇一個新的樣本點作為新的質(zhì)心，選擇原則是 D(x) 越大的點被選中的概率越大。

重復(fù)2和3直到選出 k 個質(zhì)心。

Elkan K-Means：利用兩邊之和大于第三邊以及兩邊之差小于第三邊來減少距離的計算。不適用于特征稀疏的情況。

Mini?Batch?K-Means：樣本量很大時，只用其中的一部分來做傳統(tǒng)的 K-Means 。一般多用幾次該算法，從不同的隨即采樣中選擇最優(yōu)的聚類簇。

十四、Bagging

Bagging 的弱學(xué)習(xí)器之間沒有 boosting 那樣的聯(lián)系，它的特點在于 " 隨機(jī)采樣 "，也就是有放回采樣。因此泛化能力很強(qiáng)。一般會隨機(jī)采集和訓(xùn)練集樣本數(shù)一樣個數(shù)的樣本。假設(shè)有 m 個樣本，且采集 m 次，當(dāng) m 趨向無窮大時不被采集到的數(shù)據(jù)占 1/e，也就是36.8%，稱為袋外數(shù)據(jù)，可以用來檢測模型的泛化能力。Bagging 對于弱學(xué)習(xí)器沒有限制，一般采用決策樹和神經(jīng)網(wǎng)絡(luò)。

算法：

對于 t=1~T，對訓(xùn)練數(shù)據(jù)進(jìn)行第 t 次隨機(jī)采樣，共采集 m 次，得到包含 m 個樣本的采樣集 Dm 。

用采樣集 Dm 訓(xùn)練第 m 個弱學(xué)習(xí)器 Gm(x) 。

如果是分類，則用簡單投票法。如果是回歸，則取 T 個弱學(xué)習(xí)器結(jié)果的平均值。

隨機(jī)森林：使用 CART 決策樹作為弱學(xué)習(xí)器，然后每次不從 n 個樣本特征中選擇最優(yōu)特征，而是從隨機(jī)選擇的 nsub 個樣本特征中來選擇。一般用交叉驗證來獲取合適的 nsub 值。

十五、Apriori

Apriori 是常用的挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，用于找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合。一般使用支持度或者支持度與置信度的組合作為評估標(biāo)準(zhǔn)。

支持度：幾個關(guān)聯(lián)的數(shù)據(jù)在數(shù)據(jù)集中出現(xiàn)的次數(shù)占總數(shù)據(jù)集的比重

置信度：一個數(shù)據(jù)出現(xiàn)后。另一個數(shù)據(jù)出現(xiàn)的概率

Apriori 算法的目標(biāo)是找到最大的 K 項頻繁集。假設(shè)使用支持度來作為評估標(biāo)準(zhǔn)，首先搜索出候選1項集及對應(yīng)的支持度，剪枝去掉低于支持度的1項集，得到頻繁1項集。然后對剩下的頻繁1項集進(jìn)行連接，得到候選的頻繁2項集......以此類推，不斷迭代，直到無法找到頻繁 k+1 項集為止，對應(yīng)的頻繁 k 項集的集合即為輸出結(jié)果。

十六、降維方法

主成分分析 ( PCA )：降維，不斷選擇與已有坐標(biāo)軸正交且方差最大的坐標(biāo)軸。

奇異值分解 ( SVD )：矩陣分解，降維，推薦系統(tǒng)。

線性判別分析 ( LDA )

十七、引用

如何理解神經(jīng)網(wǎng)絡(luò)里面的反向傳播算法？ - 陳唯源的回答 - 知乎

https://www.zhihu.com/question/24827633/answer/91489990

劉建平Pinard-博客園

https://www.cnblogs.com/pinard/category/894694.html

十八、原文地址

https://www.cnblogs.com/limitlessun/p/8611103.html

深度學(xué)習(xí) 機(jī)器學(xué)習(xí)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。