Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器（強(qiáng)分類器）。

一 Boosting 算法的起源

boost 算法系列的起源來(lái)自于PAC Learnability(PAC 可學(xué)習(xí)性)。這套理論主要研究的是什么時(shí)候一個(gè)問題是可被學(xué)習(xí)的，當(dāng)然也會(huì)探討針對(duì)可學(xué)習(xí)的問題的具體的學(xué)習(xí)算法。這套理論是由Valiant提出來(lái)的，也因此（還有其他貢獻(xiàn)哈）他獲得了2010年的圖靈獎(jiǎng)。

PAC 定義了學(xué)習(xí)算法的強(qiáng)弱

弱學(xué)習(xí)算法---識(shí)別錯(cuò)誤率小于1/2(即準(zhǔn)確率僅比隨機(jī)猜測(cè)略高的學(xué)習(xí)算法)

強(qiáng)學(xué)習(xí)算法---識(shí)別準(zhǔn)確率很高并能在多項(xiàng)式時(shí)間內(nèi)完成的學(xué)習(xí)算法

同時(shí) ,Valiant和 Kearns首次提出了 PAC學(xué)習(xí)模型中弱學(xué)習(xí)算法和強(qiáng)學(xué)習(xí)算法的等價(jià)性問題,即任意給定僅比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法 ,是否可以將其提升為強(qiáng)學(xué)習(xí)算法 ? 如果二者等價(jià) ,那么只需找到一個(gè)比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法就可以將其提升為強(qiáng)學(xué)習(xí)算法 ,而不必尋找很難獲得的強(qiáng)學(xué)習(xí)算法。 也就是這種猜測(cè)，讓無(wú)數(shù)牛人去設(shè)計(jì)算法來(lái)驗(yàn)證PAC理論的正確性。

不過很長(zhǎng)一段時(shí)間都沒有一個(gè)切實(shí)可行的辦法來(lái)實(shí)現(xiàn)這個(gè)理想。細(xì)節(jié)決定成敗，再好的理論也需要有效的算法來(lái)執(zhí)行。終于功夫不負(fù)有心人， Schapire在1996年提出一個(gè)有效的算法真正實(shí)現(xiàn)了這個(gè)夙愿，它的名字叫AdaBoost。AdaBoost把多個(gè)不同的決策樹用一種非隨機(jī)的方式組合起來(lái)，表現(xiàn)出驚人的性能！

第一，把決策樹的準(zhǔn)確率大大提高，可以與SVM媲美。

第二，速度快，且基本不用調(diào)參數(shù)。

第三，幾乎不Overfitting。我估計(jì)當(dāng)時(shí)Breiman和Friedman肯定高興壞了，因?yàn)檠劭粗麄兲岢龅腃ART正在被SVM比下去的時(shí)候，AdaBoost讓決策樹起死回生！Breiman情不自禁地在他的論文里贊揚(yáng)AdaBoost是最好的現(xiàn)貨方法（off-the-shelf，即“拿下了就可以用”的意思）。(這段話摘自統(tǒng)計(jì)學(xué)習(xí)那些事)

二 Boosting算法的發(fā)展歷史

Boosting算法是一種把若干個(gè)分類器整合為一個(gè)分類器的方法，在boosting算法產(chǎn)生之前，還出現(xiàn)過兩種比較重要的將多個(gè)分類器整合 為一個(gè)分類器的方法，即boostrapping方法和bagging方法。我們先簡(jiǎn)要介紹一下bootstrapping方法和bagging方法。

1）bootstrapping方法的主要過程

主要步驟：

i)重復(fù)地從一個(gè)樣本集合D中采樣n個(gè)樣本

ii)針對(duì)每次采樣的子樣本集，進(jìn)行統(tǒng)計(jì)學(xué)習(xí)，獲得假設(shè)Hi

iii)將若干個(gè)假設(shè)進(jìn)行組合，形成最終的假設(shè)Hfinal

iv)將最終的假設(shè)用于具體的分類任務(wù)

2）bagging方法的主要過程 -----bagging可以有多種抽取方法

主要思路：

i)訓(xùn)練分類器

從整體樣本集合中，抽樣n* < N個(gè)樣本 針對(duì)抽樣的集合訓(xùn)練分類器Ci

ii)分類器進(jìn)行投票，最終的結(jié)果是分類器投票的優(yōu)勝結(jié)果

但是，上述這兩種方法，都只是將分類器進(jìn)行簡(jiǎn)單的組合，實(shí)際上，并沒有發(fā)揮出分類器組合的威力來(lái)。直到1989年，Yoav Freund與 Robert Schapire提出了一種可行的將弱分類器組合為強(qiáng)分類器的方法。并由此而獲得了2003年的哥德爾獎(jiǎng)（Godel price）。

Schapire還提出了一種早期的boosting算法，其主要過程如下：

i)從樣本整體集合D中，不放回的隨機(jī)抽樣n1 < n個(gè)樣本，得到集合 D1

訓(xùn)練弱分類器C1

ii)從樣本整體集合D中，抽取 n2 < n個(gè)樣本，其中合并進(jìn)一半被C1 分類錯(cuò)誤的樣本。得到樣本集合D2

訓(xùn)練弱分類器C2

iii)抽取D樣本集合中，C1 和 C2 分類不一致樣本，組成D3

訓(xùn)練弱分類器C3

iv)用三個(gè)分類器做投票，得到最后分類結(jié)果

到了1995年，F(xiàn)reund and schapire提出了現(xiàn)在的adaboost算法，其主要框架可以描述為：

i)循環(huán)迭代多次

更新樣本分布

尋找當(dāng)前分布下的最優(yōu)弱分類器

計(jì)算弱分類器誤差率

ii)聚合多次訓(xùn)練的弱分類器

三 Adaboost 算法

AdaBoost 是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器，即弱分類器，然后把這些弱分類器集合起來(lái)，構(gòu)造一個(gè)更強(qiáng)的最終分類器。(很多博客里說(shuō)的三個(gè)臭皮匠賽過諸葛亮)

算法本身是改變數(shù)據(jù)分布實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中的每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來(lái)確定每個(gè)樣本的權(quán)值。將修改權(quán)值的新數(shù)據(jù)送給下層分類器進(jìn)行訓(xùn)練，然后將每次訓(xùn)練得到的分類器融合起來(lái)，作為最后的決策分類器。

完整的adaboost算法如下

簡(jiǎn)單來(lái)說(shuō)，Adaboost有很多優(yōu)點(diǎn):

1)adaboost是一種有很高精度的分類器

2)可以使用各種方法構(gòu)建子分類器，adaboost算法提供的是框架

3)當(dāng)使用簡(jiǎn)單分類器時(shí)，計(jì)算出的結(jié)果是可以理解的。而且弱分類器構(gòu)造極其簡(jiǎn)單

4)簡(jiǎn)單，不用做特征篩選

5)不用擔(dān)心overfitting！

四 Adaboost 舉例

也許你看了上面的介紹或許還是對(duì)adaboost算法云里霧里的，沒關(guān)系，百度大牛舉了一個(gè)很簡(jiǎn)單的例子，你看了就會(huì)對(duì)這個(gè)算法整體上很清晰了。

下面我們舉一個(gè)簡(jiǎn)單的例子來(lái)看看adaboost的實(shí)現(xiàn)過程：

圖中，“+”和“-”分別表示兩種類別，在這個(gè)過程中，我們使用水平或者垂直的直線作為分類器，來(lái)進(jìn)行分類。

第一步：

根據(jù)分類的正確率，得到一個(gè)新的樣本分布D2-，一個(gè)子分類器h1

其中劃圈的樣本表示被分錯(cuò)的。在右邊的途中，比較大的“+”表示對(duì)該樣本做了加權(quán)。

也許你對(duì)上面的?1，ɑ1怎么算的也不是很理解。下面我們算一下，不要嫌我啰嗦，我最開始就是這樣思考的，只有自己把算法演算一遍，你才會(huì)真正的懂這個(gè)算法的核心，后面我會(huì)再次提到這個(gè)。

算法最開始給了一個(gè)均勻分布 D 。所以h1 里的每個(gè)點(diǎn)的值是0.1。ok，當(dāng)劃分后，有三個(gè)點(diǎn)劃分錯(cuò)了，根據(jù)算法誤差表達(dá)式

得到 誤差為分錯(cuò)了的三個(gè)點(diǎn)的值之和，所以?1=(0.1+0.1+0.1)=0.3，而ɑ1 根據(jù)表達(dá)式的可以算出來(lái)為0.42. 然后就根據(jù)算法 把分錯(cuò)的點(diǎn)權(quán)值變大。如此迭代，最終完成adaboost算法。

第二步：

根據(jù)分類的正確率，得到一個(gè)新的樣本分布D3，一個(gè)子分類器h2

第三步：

得到一個(gè)子分類器h3

整合所有子分類器：

因此可以得到整合的結(jié)果，從結(jié)果中看，及時(shí)簡(jiǎn)單的分類器，組合起來(lái)也能獲得很好的分類效果，在例子中所有的。

五 Adaboost 疑惑和思考

到這里，也許你已經(jīng)對(duì)adaboost算法有了大致的理解。但是也許你會(huì)有個(gè)問題，為什么每次迭代都要把分錯(cuò)的點(diǎn)的權(quán)值變大呢？這樣有什么好處呢？不這樣不行嗎? 這就是我當(dāng)時(shí)的想法，為什么呢？我看了好幾篇介紹adaboost 的博客，都沒有解答我的疑惑，也許大牛認(rèn)為太簡(jiǎn)單了，不值一提，或者他們并沒有意識(shí)到這個(gè)問題而一筆帶過了。然后我仔細(xì)一想，也許提高錯(cuò)誤點(diǎn)可以讓后面的分類器權(quán)值更高。然后看了adaboost算法，和我最初的想法很接近，但不全是。 注意到算法最后的表達(dá)式為

，這里面的a 表示的權(quán)值，是由

得到的。而a是關(guān)于誤差的表達(dá)式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯(cuò)誤點(diǎn)的權(quán)值，當(dāng)下一次分類器再次分錯(cuò)了這些點(diǎn)之后，會(huì)提高整體的錯(cuò)誤率，這樣就導(dǎo)致 a 變的很小，最終導(dǎo)致這個(gè)分類器在整個(gè)混合分類器的權(quán)值變低。也就是說(shuō)，這個(gè)算法讓優(yōu)秀的分類器占整體的權(quán)值更高，而挫的分類器權(quán)值更低。這個(gè)就很符合常理了。到此，我認(rèn)為對(duì)adaboost已經(jīng)有了一個(gè)透徹的理解了。

六 總結(jié)

最后，我們可以總結(jié)下adaboost算法的一些實(shí)際可以使用的場(chǎng)景：

1）用于二分類或多分類的應(yīng)用場(chǎng)景

2）用于做分類任務(wù)的baseline

無(wú)腦化，簡(jiǎn)單，不會(huì)overfitting，不用調(diào)分類器

3）用于特征選擇（feature selection)

4）Boosting框架用于對(duì)badcase的修正

只需要增加新的分類器，不需要變動(dòng)原有分類器

由于adaboost算法是一種實(shí)現(xiàn)簡(jiǎn)單，應(yīng)用也很簡(jiǎn)單的算法。Adaboost算法通過組合弱分類器而得到強(qiáng)分類器，同時(shí)具有分類錯(cuò)誤率上界隨著訓(xùn)練增加而穩(wěn)定下降，不會(huì)過擬合等的性質(zhì)，應(yīng)該說(shuō)是一種很適合于在各種分類場(chǎng)景下應(yīng)用的算法。