出差結(jié)束，繼續(xù)好好學(xué)習(xí)機(jī)器學(xué)習(xí)基礎(chǔ)算法，今天了解提升方法(Boosting)，主要側(cè)重于AdaBoost算法，同樣理論知識(shí)來(lái)自Peter Harrington的《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》和李航的《統(tǒng)計(jì)學(xué)習(xí)方法》，非常感謝這些優(yōu)秀人物和優(yōu)秀書(shū)籍，正文開(kāi)始啦
提升算法(Boosting)
考慮前幾篇提到的分類(lèi)算法，各有利弊，如果可以有效地將這些分類(lèi)器結(jié)合起來(lái)，各取所長(zhǎng)，應(yīng)該也是不錯(cuò)的選擇。提升算法正是基于這樣的思想，但是它不是簡(jiǎn)單、均等的將不同分類(lèi)器的結(jié)果相加，而是基于全部分類(lèi)器的加權(quán)求和結(jié)果，而這個(gè)權(quán)重代表的是該分類(lèi)器在上一輪迭代中的成功度。歷史上，Kearns和Valiant首先提出了'強(qiáng)可學(xué)習(xí)(strongly learnable)'和'弱可學(xué)習(xí)(weakly learnable)'的概念。指出：在概率近似正確(probably approximately correct, PAC)學(xué)習(xí)的框架中，一個(gè)概念(一個(gè)類(lèi))，如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法能夠?qū)W習(xí)它，并且正確率很高，那么就稱(chēng)這個(gè)概念是強(qiáng)可學(xué)習(xí)的；一個(gè)概念，如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法能夠?qū)W習(xí)它，學(xué)習(xí)的正確率僅比隨機(jī)猜測(cè)略好，那么就稱(chēng)這個(gè)概念是弱可學(xué)習(xí)的。非常有趣的是Schapire后來(lái)證明強(qiáng)可學(xué)習(xí)與弱可學(xué)習(xí)是等價(jià)的，也就是說(shuō)，在PAC學(xué)習(xí)的框架下，一個(gè)概念是強(qiáng)可學(xué)習(xí)的充分必要條件是這個(gè)概念是弱可學(xué)習(xí)的。這樣一來(lái)，問(wèn)題便成為，在學(xué)習(xí)中，如果已經(jīng)發(fā)現(xiàn)了'弱學(xué)習(xí)算法'，那么能否將它提升（boost）為'強(qiáng)學(xué)習(xí)算法'。大家知道，發(fā)現(xiàn)弱學(xué)習(xí)算法通常要比發(fā)現(xiàn)強(qiáng)學(xué)習(xí)算法容易得多。那么如何具體實(shí)施提升，便成為開(kāi)發(fā)提升方法時(shí)所要解決的問(wèn)題。關(guān)于提升方法的研究很多，有很多算法被提出。最具代表性的是AdaBoost算法(AdaBoost algorithm，adaptive boosting algorithm)。
AdaBoost算法工作原理：開(kāi)始時(shí)，賦予訓(xùn)練數(shù)據(jù)中的每個(gè)樣本一個(gè)相等的初始權(quán)重值，這些權(quán)重構(gòu)成了向量D。首先在訓(xùn)練數(shù)據(jù)上訓(xùn)練出一個(gè)弱分類(lèi)器并計(jì)算該分類(lèi)的錯(cuò)誤率，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類(lèi)器。在分類(lèi)器的第二次訓(xùn)練中，將第一次分對(duì)的樣本的權(quán)重降低，將第一次分錯(cuò)的樣本的權(quán)重提高。這樣一來(lái)，那些沒(méi)有得到正確分類(lèi)的數(shù)據(jù)，由于其權(quán)值的加大而受到后一輪的弱分類(lèi)器的更大關(guān)注。反復(fù)學(xué)習(xí)，不斷調(diào)整樣本權(quán)重，最終得到一個(gè)強(qiáng)分類(lèi)器。
最終，AdaBoost算法的分類(lèi)器是：
舉栗子-AdaBoost算法模型：
1）準(zhǔn)備數(shù)據(jù)
2）準(zhǔn)備一些后續(xù)用到的工具函數(shù)
在此，要先介紹下“單層決策樹(shù)”。單層決策樹(shù)(decision stump，也稱(chēng)決策樹(shù)樁)是一種簡(jiǎn)單的決策樹(shù)，它僅基于單個(gè)特征來(lái)做決策，由于這棵樹(shù)只有一次分裂過(guò)程，因此實(shí)際就是一個(gè)樹(shù)樁。而圖4中的stumpClassify函數(shù)就是基于這一思想，在分類(lèi)時(shí)，根據(jù)某種比較規(guī)則，如less than (lt) 或者 great than (gt)等，判斷屬性值與閾值的關(guān)系。buildStump函數(shù)是構(gòu)建單層決策樹(shù)，包括三層嵌套循環(huán)。
3）基于單層決策樹(shù)的AdaBoost算法
此算法主要流程為：在限定最大運(yùn)算次數(shù)的限制下，分別計(jì)算alpha、weights、和errorRate，當(dāng)errorRate=0時(shí)跳出循環(huán)，此過(guò)程中的計(jì)算主要是依據(jù)圖1中的計(jì)算式。實(shí)際分類(lèi)器不是僅限于單層決策樹(shù)，任何一種分類(lèi)算法都可以作為基分類(lèi)器。
4）AdaBoost分類(lèi)函數(shù)
好噠，關(guān)于提升方法的基礎(chǔ)學(xué)習(xí)先到這里，等在下一階段的深入學(xué)習(xí)中再往深挖掘，希望對(duì)大家有幫助，歡迎大神隨時(shí)指點(diǎn)。謝謝
