本文總結(jié)了《統(tǒng)計學(xué)習方法》(李航)中的一些機器學(xué)習方法熙卡,組織目錄如下:
【第1章】 統(tǒng)計學(xué)習方法概論
【第2章】 感知機
【第3章】 k 近鄰法
【第4章】 樸素貝葉斯法
【第5章】 決策樹
【第6章】 邏輯斯諦回歸與最大熵模型
【第7章】 支持向量機
【第8章】 提升方法
【第9章】 EM算法及其推廣
【第10章】 隱馬爾科夫模型
【第11章】 條件隨機場
【第12章】 統(tǒng)計學(xué)習方法總結(jié)
【第1章】 統(tǒng)計學(xué)習方法概論
- 統(tǒng)計學(xué)習方法包括監(jiān)督學(xué)習纯赎、無監(jiān)督學(xué)習、半監(jiān)督學(xué)習和強化學(xué)習。
- 統(tǒng)計學(xué)習方法三要素:模型算行、策略、方法羡鸥。
- 模型:所要學(xué)習的條件概率分布或決策函數(shù)蜈块。所有可能的條件概率分布或決策函數(shù)組成模型的假設(shè)空間百揭。
- 策略:
4.1 損失函數(shù):能夠度量模型一次預(yù)測的好壞课锌,值越谐浮(接近0)越好。包括0-1損失函數(shù)、平方損失函數(shù)唆缴、絕對損失函數(shù)、對數(shù)損失函數(shù)。
4.2 風險函數(shù):能夠度量平均意義下模型預(yù)測的好壞霎匈,包括期望風險函數(shù)和經(jīng)驗風險函數(shù)袭厂。
4.2.1 期望風險函數(shù):損失函數(shù)的期望帖烘。P(X,Y)
是未知的讥珍,因此監(jiān)督學(xué)習就是一個病態(tài)問題。
4.2.2 經(jīng)驗風險函數(shù):模型關(guān)于訓(xùn)練樣本集的平均損失锄列。Rexp(f) = Remp(f)
。
4.3 經(jīng)驗風險最小化與結(jié)構(gòu)風險最小化:
J(f)
為模型復(fù)雜度较木。結(jié)構(gòu)風險最小化需要經(jīng)驗風險和模型復(fù)雜度同時猩睬啊(λ
趨于無窮時校坑,后一項的系數(shù)收縮作用就增大了膏斤,很多系數(shù)趨于0,模型復(fù)雜度將變信陶ァ型酥;λ
為0,則后一項沒有起到收縮作用)。 - 算法:求解最優(yōu)模型的方法蔑舞,找到全局最優(yōu)解州弟。
- 使測試誤差達到最小的兩種方法:正則化和交叉驗證啃奴。
- 監(jiān)督學(xué)習分為生成方法和判別方法。同時黎炉,監(jiān)督學(xué)習也可以分為分類問題(k近鄰法洪添、感知機、樸素貝葉斯、決策樹、決策列表滤钱、logistic回歸他炊、SVM、Boosting幔嫂、貝葉斯網(wǎng)絡(luò)呢蔫、神經(jīng)網(wǎng)絡(luò)全谤、Winnow算法等)盈匾、標注問題(隱馬爾科夫模型、條件隨機場)狭姨、回歸問題(數(shù)值型數(shù)據(jù)回歸漓柑、樹回歸(CART,既可以分類叨吮,又可以回歸))辆布。
7.1 生成方法: - 分類問題的評價指標:精確率(P)、召回率(R)茶鉴、F1(P和R的調(diào)和均值:
2/F = 1/P + 1/R
)锋玲。
8.1 P是指被判別器預(yù)測為正類的樣本(將正類預(yù)測為正類TP+將負類預(yù)測為正類FP)中正類正確分類(正類預(yù)測為正類TP)的個數(shù),如判別器預(yù)測有100個正類樣本涵叮,但只有90個是真正預(yù)測正確(正類預(yù)測為正類)惭蹂,則 P=0.9伞插。
8.2 R是指所有正類樣本(正類預(yù)測為正類TP+正類預(yù)測為負類FN)中,正類正確分類(正類預(yù)測為正類TP)的個數(shù)盾碗,如樣本中有100個正類媚污,但只有80個正類正確分類,則 R=0.8廷雅。
8.3 準確率/正確率(A)是指所有樣本(正類預(yù)測為正類TP+正類預(yù)測為負類FN+負類預(yù)測為正類FP+負類預(yù)測為負類TN)中耗美,判別器正確預(yù)測的樣本數(shù)(正類預(yù)測為正類TP+負類預(yù)測為負類TN)。
8.4 希望P榜轿、R幽歼、F1、A的值越接近1越好谬盐。
【第2章】 感知機
- 感知機是二分類的線性分類模型
f(x) = sign(w · x + b)
甸私,對應(yīng)于輸入空間(特征空間)中的分離超平面w · x + b = 0
。 - 感知機學(xué)習策略是極小化損失函數(shù):
- 感知機的學(xué)習算法是基于隨機梯度下降法的對損失函數(shù)的優(yōu)化算法皇型,有原始形式和對偶形式。原始形式中砸烦,首先任意選取一個超平面弃鸦,然后用梯度下降法不斷極小化目標函數(shù)。在這個過程中一次隨機選取一個誤分類點使其梯度下降(這也是隨機梯度下降與梯度下降(選取所有點)的區(qū)別)幢痘。
- 當訓(xùn)練數(shù)據(jù)集線性可分時唬格,感知機學(xué)習算法存在無窮多個解,其解由于不同的初值或迭代順序而可能有所不同颜说。
【第3章】 k 近鄰法
- k 近鄰點用于分類和回歸购岗,基本做法是:給定訓(xùn)練實例點和輸入實例點,首先確定輸入實例點 k 個最近鄰訓(xùn)練實例點门粪,然后利用這 k 個訓(xùn)練實例點的類的多數(shù)來預(yù)測輸入實例點的類喊积。
- k 近鄰法三要素:距離度量、k 值的選擇和分類決策規(guī)則玄妈。k 值小時乾吻,k 近鄰模型更復(fù)雜,反之亦然拟蜻。k 值常采用交叉驗證的方法確定绎签,而分類決策函數(shù)常采用多數(shù)表決。
- kd 樹是一種便于對 k 維空間中的數(shù)據(jù)進行快速檢索的數(shù)據(jù)結(jié)構(gòu)酝锅。kd 樹是二叉樹辜御,表示對 k 維空間的一個劃分,其每個節(jié)點對應(yīng)于 k 維空間劃分中的一個超矩形區(qū)域屈张。利用 kd 樹可以省去對大部分數(shù)據(jù)點的搜索擒权,從而減少搜索的計算量。
【第4章】 樸素貝葉斯法
- 樸素貝葉斯法通過訓(xùn)練數(shù)據(jù)集學(xué)習聯(lián)合概率分布
P(X,Y)
阁谆,具體做法是學(xué)習先驗概率分布P(Y)
與條件概率分布P(X|Y)
(二者相乘就是聯(lián)合概率分布)碳抄,所以它屬于生成模型。
- 在上述條件概率分布中场绿,假設(shè)特征彼此相互獨立剖效,即滿足條件獨立性假設(shè):
- 樸素貝葉斯用于分類時,就是通過學(xué)習到的模型計算后驗概率分布
P(Y|X)
焰盗,將后驗概率最大的類最為x的類輸出:
ck
都是相同的璧尸,因此可以轉(zhuǎn)化為以下求解問題: -
P(Y)
和P(X|Y)
都可以使用極大似然估計法估計相應(yīng)的概率,但是這種方法會出現(xiàn)所要估計的概率值為0的情況熬拒,這回影響到后驗概率的計算結(jié)果爷光,使分類產(chǎn)生偏差。因此澎粟,采取貝葉斯估計法可以解決這一問題蛀序。 -
補充知識: 什么是極大似然估計法?
(個人理解:極大似然估計法就是根據(jù)樣本(已知的結(jié)果)定好模型(但參數(shù)未知)活烙,反推最有可能(最大概率)的模型參數(shù)徐裸,就可以確定參數(shù)已知的該模型,即根據(jù)結(jié)果推斷參數(shù)的過程啸盏。)
【第5章】 決策樹
- 決策樹可以轉(zhuǎn)化為一個if-then規(guī)則的集合重贺,也可以看做是定義在特征空間劃分上的類的條件概率分布。
- 從可能的決策樹中直接選取最優(yōu)決策樹是一個NP問題回懦,現(xiàn)實中采用啟發(fā)式方法學(xué)習次優(yōu)決策樹气笙。
- 決策樹的生成對應(yīng)于模型的局部選擇,決策樹的剪枝(自下而上合并過于細分的葉結(jié)點粉怕,防止過擬合)對應(yīng)于模型的全局選擇健民。
- 決策樹的學(xué)習包括三部分:特征選擇、樹的生成和樹的剪枝贫贝。常用的算法有ID3秉犹、C4.5和CART。
- 特征選擇的目的在于選取對訓(xùn)練數(shù)據(jù)能夠分類的特征稚晚。常用的準則有信息增益(ID3)崇堵、信息增益比(C4.5)、基尼指數(shù)(CART)客燕。
- 信息增益:
- 決策樹的生成通常使用信息增益最大赏廓、信息增益比最大或基尼指數(shù)最小作為特征選擇的準則涵紊。決策樹的生成往往通過計算信息增益或其他指標,從根結(jié)點開始幔摸,遞歸地產(chǎn)生決策樹摸柄。這相當于用信息增益或其他準則不斷地選取局部最優(yōu)的特征,或?qū)⒂?xùn)練集分割為能夠基本正確分類的子集既忆。
-
決策樹的剪枝解決決策樹的過擬合問題驱负,做法是從已生成的樹上減掉一些葉結(jié)點或葉結(jié)點以上的子樹,并將其父結(jié)點或根節(jié)點作為新的葉節(jié)點患雇,從而簡化生成的決策樹跃脊。
- CART算法就是遞歸地構(gòu)建二叉決策樹的過程,既可以用于分類問題(采取基尼指數(shù)最小化準則)苛吱,又可以用于回歸問題(采取平方誤差最小化準則)酪术。剪枝過程同樣采用損失函數(shù)最小化的標準。
【第6章】 邏輯斯諦回歸與最大熵模型
- 邏輯斯諦回歸模型源自邏輯斯諦分布又谋,其分布函數(shù)F(x)是S形函數(shù)拼缝。它是由輸入的線性函數(shù)表示的輸出的對數(shù)幾率模型。
- 最大熵模型可以由最大熵原理推導(dǎo)得出彰亥。最大熵原理認為咧七,在所有可能的概率模型(分布)的集合中,熵最大的模型是最好的模型(均勻分布的熵最大)任斋。
- 邏輯斯蒂模型與最大熵模型的共同點:(1)兩者都可以表示為求解條件概率分布的分類模型继阻;(2)兩者都屬于對數(shù)線性模型;(3)兩者學(xué)習一般都采用極大似然估計或正則化的極大似然估計废酷;(4)兩者可以學(xué)習形式化的無約束優(yōu)化問題(最大熵模型原本是有約束問題瘟檩,但可以引入拉格朗日乘子轉(zhuǎn)化為無約束條件的對偶問題來求解);(5)兩者求解最優(yōu)化問題的算法有梯度下降法澈蟆、隨機梯度下降法墨辛、改進的迭代尺度法、牛頓法或擬牛頓法等等趴俘;(6)兩者都可以用于二分類或多分類問題昧港。
【第7章】 支持向量機
- 支持向量機分類:
類別 | 別名 | 構(gòu)建條件 |
---|---|---|
線性可分支持向量機 | 硬間隔支持向量機 | 訓(xùn)練數(shù)據(jù)線性可分 |
線性支持向量機 | 軟間隔支持向量機 | 訓(xùn)練數(shù)據(jù)近似線性可分 |
非線性支持向量機 | NULL | 訓(xùn)練數(shù)據(jù)線性不可分 |
- 線性可分支持向量機:
2.1 學(xué)習策略是最大間隔法通贞,可表示為以下凸二次規(guī)劃問題:w* · x + b* = 0
,分類決策函數(shù)為f(x) = sign(w* · x + b*)
疲憋。
2.2 最大間隔法中凿渊,函數(shù)間隔和幾何間隔是重要的概念。
2.3 線性可分支持向量機的最優(yōu)解存在且唯一。位于間隔邊界的上的實例支持點為支持向量埃脏。最優(yōu)分離超平面由支持向量完全決定搪锣。
2.4 二次規(guī)劃問題的對偶問題:
- 線性支持向量機:
3.1 最基本的支持向量機监嗜,通過引入孫馳變量 ξi谐檀,使其“可分”,得到線性支持向量機學(xué)習的凸二次規(guī)劃問題:
w* · x + b* = 0
,分類決策函數(shù)為f(x) = sign(w* · x + b*)
刽肠。
其中溃肪,C > 0 稱為懲罰系數(shù)。C值大時對誤分類的懲罰增大音五,模型變復(fù)雜惫撰,趨于過擬合,支持向量的樣本點變少躺涝;C值小對誤分類的懲罰減小厨钻。
3.2 線性支持向量機的解 w* 唯一,但 b* 不一定唯一坚嗜。支持向量可在間隔邊界上夯膀,也可以在間隔邊界與分離超平面之間,或者在分離超平面誤分一側(cè)苍蔬。最優(yōu)分離超平面由支持向量完全決定诱建。
3.3 二次規(guī)劃問題的對偶問題:
3.4 線性支持向量機學(xué)習等價于最小化二階范數(shù)正則化的合頁函數(shù):
- 非線性支持向量機:
4.1 對于輸入空間的非線性分類問題,可以通過非線性變換將它轉(zhuǎn)化為某個高維特征空間中的線性分類問題抓狭,在高維特征空間中學(xué)習線性支持向量機伯病。
4.2 核函數(shù):通過一個非線性變換后的兩個實例間的內(nèi)積。在實際應(yīng)用中往往應(yīng)用已有的核函數(shù)。常見的核函數(shù)有多項式核函數(shù)(pkf)午笛,高斯核函數(shù)(rbf惭蟋,其中參數(shù)gamma:隨著gamma參數(shù)增大,支持向量先減少后增多药磺,模型更復(fù)雜告组,趨于過擬合),字符串核函數(shù)(skf)等癌佩。
4.3 非線性支持向量機求解的決策函數(shù):
- SMO(序列最小最優(yōu)化)算法:支持向量機學(xué)習的一種快速算法木缝,其特點是不斷地將原二次規(guī)劃問題分解為只有兩個變量的二次規(guī)劃子問題,并對子問題進行解析求解围辙,直到所有變量滿足KKT條件為止我碟。這是一種啟發(fā)式的方法,得到的解是近似解姚建,但總體上是高效的矫俺。
【第8章】 提升方法
- 提升方法是將弱學(xué)習算法提升為強學(xué)習算法的統(tǒng)計學(xué)習方法。在分類學(xué)習中掸冤,提升方法通過反復(fù)修改訓(xùn)練數(shù)據(jù)集的權(quán)值分布厘托,構(gòu)建一系列基本分類器(弱分類器),并將這些基本分類器線性組合稿湿,構(gòu)成一個強分類器铅匹。代表性的提升方法是 AdaBoost 算法。
-
AdaBoost 算法是弱分類器的線性組合:
- AdaBoost 算法的特點是通過迭代每次學(xué)習一個基本分類器缎罢。每次迭代中伊群,提高那些被前一輪分類器錯誤分類數(shù)據(jù)的權(quán)值,而降低那些被正確分類的線性數(shù)據(jù)的權(quán)值策精。最后舰始,AdaBoost 將基本分類器的線性組合作為強分類器,其中給分類誤差率小的基本分類器以大的權(quán)值咽袜,給分類誤差大的基本分類器以小的權(quán)值丸卷。
- AdaBoost 算法的一個解釋是該算法實際是前向分步算法的一個實現(xiàn)。在這個方法里询刹,模型是加法模型谜嫉,函數(shù)損失是指數(shù)損失,算法是前向分步算法凹联。每一步通過極小化損失函數(shù):
- 提升樹是以分類樹或回歸樹為基本分類器的提升方法蔽挠。提升樹被認為是統(tǒng)計學(xué)習方法中最有效的方法之一住闯。
- 補充知識: RF(隨機森林)、GBDT、XGBoost:RF比原、GBDT插佛、XGBoost 區(qū)別
【第9章】 EM算法及其推廣
- EM (期望極大)算法是含有隱變量的概率模型極大似然估計或極大后驗概率估計的迭代算法。含有隱變量的概率模型的數(shù)據(jù)表示為 P(Y, Z | θ)量窘。這里雇寇,Y 是觀測變量的數(shù)據(jù),Z 是隱變量的數(shù)據(jù)(不可觀測到的變量數(shù)據(jù))蚌铜,θ 是模型參數(shù)锨侯。EM 算法通過迭代求解觀測數(shù)據(jù)的對數(shù)似然函數(shù) L(θ) = log P(Y | θ) 的極大化,實現(xiàn)極大似然估計厘线, 每次迭代包括兩步:E步识腿,求期望。即求 log P(Y, Z | θ) 關(guān)于 P(Y | Y, θi) 的期望:
- EM 算法在每次迭代后均能提高觀測數(shù)據(jù)的似然函數(shù)值混驰,即
- EM 算法主要應(yīng)用于含有隱變量的概率模型的學(xué)習栖榨。高斯混合模型的參數(shù)估計是 EM 算法的一個重要應(yīng)用昆汹,下一章將要介紹的隱馬爾科夫模型的無監(jiān)督學(xué)習也是 EM 算法的一個重要應(yīng)用。
- EM 算法還可以解釋為 F 函數(shù)的極大-極大算法(一次迭代中婴栽,兩次極大化 F 函數(shù)值)满粗。EM 算法有很多變形,如 GEM 算法愚争。GEM 算法的特點是每次迭代增加 F 函數(shù)值(并不一定是極大化 F 函數(shù)映皆,因為是兩次極大),從而增加似然函數(shù)的 L(θ) 的值轰枝。
【第10章】 隱馬爾科夫模型
- 隱馬爾科夫模型是關(guān)于時序的概率模型捅彻,描述由一個隱藏的馬爾科夫鏈隨機生成不可觀測的狀態(tài)序列,再由各個狀態(tài)隨機生成一個觀測而產(chǎn)生觀測序列的過程鞍陨。