能否使用弱分類器和多個實例來構建一個強分類器？這是一個非常有趣的理論問題。這裡的「弱」意味著分類器的性能比隨機猜測要略好，但是也不會好太多。這就是說，在二分類情況下弱分類器的錯誤率會高於50%，而「強」分類器的錯誤率將會低很多。AdaBoost算法即脫胎於上述理論問題。
AdaBoost是adaptive boosting（自適應boosting）的縮寫，其運行過程如下：訓練數據中的每個樣本，並賦予其一個權重，這些權重構成了向量D。一開始，這些權重都初始化成相等值。首先在訓練數據上訓練出一個弱分類器並計算該分類器的錯誤率，然後在同一數據集上再次訓練弱分類器。在分類器的第二次訓練當中，將會重新調整每個樣本的權重，其中第一次分對的樣本的權重將會降低，而第一次分錯的樣本的權重將會提高。為了從所有弱分類器中得到最終的分類結果，AdaBoost為每個分類器都分配了一個權重值alpha，這些alpha值是基於每個弱分類器的錯誤率進行計算的。其中，錯誤率ε的定義為：
而alpha的計算公式如下：
AdaBoost算法的流程如圖7-1所示。
圖7-1 AdaBoost算法的示意圖。左邊是數據集，其中直方圖的不同寬度表示每個樣例上的不同權重。在經過一個分類器之後，加權的預測結果會通過三角形中的alpha值進行加權。每個三角形中輸出的加權結果在圓形中求和，從而得到最終的輸出結果
計算出alpha值之後，可以對權重向量D進行更新，以使得那些正確分類的樣本的權重降低而錯分樣本的權重升高。D的計算方法如下。
如果某個樣本被正確分類，那麼該樣本的權重更改為：
而如果某個樣本被錯分，那麼該樣本的權重更改為：
在計算出D之後，AdaBoost又開始進入下一輪迭代。AdaBoost算法會不斷地重複訓練和調整權重的過程，直到訓練錯誤率為0或者弱分類器的數目達到用戶的指定值為止。
接下來，我們將建立完整的AdaBoost算法。在這之前，我們首先必須通過一些代碼來建立弱分類器及保存數據集的權重。