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

Boosting，也稱為增強(qiáng)學(xué)習(xí)或提升法，是一種重要的集成學(xué)習(xí)技術(shù)，能夠?qū)㈩A(yù)測(cè)精度僅比隨機(jī)猜度略高的弱學(xué)習(xí)器增強(qiáng)為預(yù)測(cè)精度高的強(qiáng)學(xué)習(xí)器，這在直接構(gòu)造強(qiáng)學(xué)習(xí)器非常困難的情況下，為學(xué)習(xí)算法的設(shè)計(jì)提供了一種有效的新思路和新方法。作為一種元算法框架，Boosting幾乎可以應(yīng)用于所有目前流行的機(jī)器學(xué)習(xí)算法以進(jìn)一步加強(qiáng)原算法的預(yù)測(cè)精度，應(yīng)用十分廣泛，產(chǎn)生了極大的影響。而AdaBoost正是其中最成功的代表，被評(píng)為數(shù)據(jù)挖掘十大算法之一。在AdaBoost提出至今的十幾年間，機(jī)器學(xué)習(xí)領(lǐng)域的諸多知名學(xué)者不斷投入到算法相關(guān)理論的研究中去，扎實(shí)的理論為AdaBoost算法的成功應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)。AdaBoost的成功不僅僅在于它是一種有效的學(xué)習(xí)算法，還在于：

1）它讓Boosting從最初的猜想變成一種真正具有實(shí)用價(jià)值的算法；

2）算法采用的一些技巧，如：打破原有樣本分布，也為其他統(tǒng)計(jì)學(xué)習(xí)算法的設(shè)計(jì)帶來(lái)了重要的啟示；

3）相關(guān)理論研究成果極大地促進(jìn)了集成學(xué)習(xí)的發(fā)展。

對(duì)adaBoost算法的研究以及應(yīng)用大多集中于分類問(wèn)題，同時(shí)也出現(xiàn)了一些在回歸問(wèn)題上的應(yīng)用。就其應(yīng)用adaBoost系列主要解決了： 兩類問(wèn)題、多類單標(biāo)簽問(wèn)題、多類多標(biāo)簽問(wèn)題、大類單標(biāo)簽問(wèn)題、回歸問(wèn)題。它用全部的訓(xùn)練樣本進(jìn)行學(xué)習(xí)。

最初的Boosting算法由Schapire于1990年提出，即一種多項(xiàng)式的算法，并進(jìn)行了實(shí)驗(yàn)和理論性的證明。在此之后，F(xiàn)reund研究出一種更高效的Boosting算法。但這兩種算法都有共同的不足即需要提前確定弱學(xué)習(xí)算法識(shí)別準(zhǔn)確率的下限。Boosting算法可以提升任意給定學(xué)習(xí)算法的準(zhǔn)確度，主要思想是通過(guò)一些簡(jiǎn)單的規(guī)則整合得到一個(gè)整體，使得該整體具有的性能比任何一個(gè)部分都高。其思想受啟發(fā)于Valiant提出的PAC學(xué)習(xí)模型。

Valiant認(rèn)為“學(xué)習(xí)”是一種不管模式明顯清晰或是否存在模式時(shí)都能夠獲得知識(shí)的過(guò)程，并從計(jì)算的角度定義了學(xué)習(xí)的方法，其包含學(xué)習(xí)的協(xié)議、合理信息采集機(jī)制的選擇以及可以在適當(dāng)過(guò)程內(nèi)實(shí)現(xiàn)學(xué)習(xí)概念的分類。PAC學(xué)習(xí)模型的原理是指在訓(xùn)練樣本的基礎(chǔ)上，算法的輸出能夠以概率靠近未知的目標(biāo)進(jìn)行學(xué)習(xí)分類，基本框架涉及樣本復(fù)雜度和計(jì)算復(fù)雜度。簡(jiǎn)而言之，在PAC學(xué)習(xí)模型中，能夠在多項(xiàng)式個(gè)時(shí)間內(nèi)和樣本獲得特定要求的正確率即就是一個(gè)好的學(xué)習(xí)過(guò)程。該模型由統(tǒng)計(jì)模式識(shí)別、決策理論得到的一些簡(jiǎn)單理論并結(jié)合計(jì)算復(fù)雜理論的方法而得出的學(xué)習(xí)模型。其中提出了弱學(xué)習(xí)和強(qiáng)學(xué)習(xí)的概念。

Adaboost算法已被證明是一種有效而實(shí)用的Boosting算法。該算法是Freund和Schapire于1995年對(duì)Boosting算法的改進(jìn)得到的，其算法原理是通過(guò)調(diào)整樣本權(quán)重和弱分類器權(quán)值，從訓(xùn)練出的弱分類器中篩選出權(quán)值系數(shù)最小的弱分類器組合成一個(gè)最終強(qiáng)分類器。基于訓(xùn)練集訓(xùn)練弱分類器，每次下一個(gè)弱分類器都是在樣本的不同權(quán)值集上訓(xùn)練獲得的。每個(gè)樣本被分類的難易度決定權(quán)重，而分類的難易度是經(jīng)過(guò)前面步驟中的分類器的輸出估計(jì)得到的。

Adaboost算法在樣本訓(xùn)練集使用過(guò)程中，對(duì)其中的關(guān)鍵分類特征集進(jìn)行多次挑選，逐步訓(xùn)練分量弱分類器，用適當(dāng)?shù)拈撝颠x擇最佳弱分類器，最后將每次迭代訓(xùn)練選出的最佳弱分類器構(gòu)建為強(qiáng)分類器。其中，級(jí)聯(lián)分類器的設(shè)計(jì)模式為在盡量保證感興趣圖像輸出率的同時(shí)，減少非感興趣圖像的輸出率，隨著迭代次數(shù)不斷增加，所有的非感興趣圖像樣本都不能通過(guò)，而感興趣樣本始終保持盡可能通過(guò)為止。

算法流程

該算法其實(shí)是一個(gè)簡(jiǎn)單的弱分類算法提升過(guò)程，這個(gè)過(guò)程通過(guò)不斷的訓(xùn)練，可以提高對(duì)數(shù)據(jù)的分類能力。整個(gè)過(guò)程如下所示：

1． 先通過(guò)對(duì)N個(gè)訓(xùn)練樣本的學(xué)習(xí)得到第一個(gè)弱分類器；

2． 將分錯(cuò)的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個(gè)新的N個(gè)的訓(xùn)練樣本，通過(guò)對(duì)這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器 ；

3． 將1和2都分錯(cuò)了的樣本加上其他的新樣本構(gòu)成另一個(gè)新的N個(gè)的訓(xùn)練樣本，通過(guò)對(duì)這個(gè)樣本的學(xué)習(xí)得到第三個(gè)弱分類器；

4． 最終經(jīng)過(guò)提升的強(qiáng)分類器。即某個(gè)數(shù)據(jù)被分為哪一類要由各分類器權(quán)值決定。

由Adaboost算法的描述過(guò)程可知，該算法在實(shí)現(xiàn)過(guò)程中根據(jù)訓(xùn)練集的大小初始化樣本權(quán)值，使其滿足均勻分布，在后續(xù)操作中通過(guò)公式來(lái)改變和規(guī)范化算法迭代后樣本的權(quán)值。樣本被錯(cuò)誤分類導(dǎo)致權(quán)值增大，反之權(quán)值相應(yīng)減小，這表示被錯(cuò)分的訓(xùn)練樣本集包括一個(gè)更高的權(quán)重。這就會(huì)使在下輪時(shí)訓(xùn)練樣本集更注重于難以識(shí)別的樣本，針對(duì)被錯(cuò)分樣本的進(jìn)一步學(xué)習(xí)來(lái)得到下一個(gè)弱分類器，直到樣本被正確分類。在達(dá)到規(guī)定的迭代次數(shù)或者預(yù)期的誤差率時(shí)，則強(qiáng)分類器構(gòu)建完成。 

算法特點(diǎn)

Aadboost 算法系統(tǒng)具有較高的檢測(cè)速率，且不易出現(xiàn)過(guò)適應(yīng)現(xiàn)象。但是該算法在實(shí)現(xiàn)過(guò)程中為取得更高的檢測(cè)精度則需要較大的訓(xùn)練樣本集，在每次迭代過(guò)程中，訓(xùn)練一個(gè)弱分類器則對(duì)應(yīng)該樣本集中的每一個(gè)樣本，每個(gè)樣本具有很多特征，因此從龐大的特征中訓(xùn)練得到最優(yōu)弱分類器的計(jì)算量增大。典型的 Adaboost 算法采用的搜索機(jī)制是回溯法，雖然在訓(xùn)練弱分類器時(shí)每一次都是由貪心算法來(lái)獲得局部最佳弱分類器，但是卻不能確保選擇出來(lái)加權(quán)后的是整體最佳。在選擇具有最小誤差的弱分類器之后，對(duì)每個(gè)樣本的權(quán)值進(jìn)行更新，增大錯(cuò)誤分類的樣本對(duì)應(yīng)的權(quán)值，相對(duì)地減小被正確分類的樣本權(quán)重。且執(zhí)行效果依賴于弱分類器的選擇，搜索時(shí)間隨之增加，故訓(xùn)練過(guò)程使得整個(gè)系統(tǒng)的所用時(shí)間非常大，也因此限制了該算法的廣泛應(yīng)用。另一方面，在算法實(shí)現(xiàn)過(guò)程中，從檢測(cè)率和對(duì)正樣本的誤識(shí)率兩個(gè)方面向預(yù)期值逐漸逼近來(lái)構(gòu)造級(jí)聯(lián)分類器，迭代訓(xùn)練生成大量的弱分類器后才能實(shí)現(xiàn)這一構(gòu)造過(guò)程。由此推出循環(huán)逼近的訓(xùn)練分類器需要消耗更多的時(shí)間。