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

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

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

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

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

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

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

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

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

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

算法流程

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

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

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

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

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

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

算法特點

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