AdaBoost為英文"Adaptive Boosting"(自適應增強)的縮寫,是一種機器學習方法,由約阿夫·弗羅因德羅伯特·沙皮爾提出。[1]AdaBoost方法的自適應在於:前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對於噪聲數據和異常數據很敏感。但在一些問題中,AdaBoost方法相對於大多數其它學習算法而言,不會很容易出現過擬合現象。AdaBoost方法中使用的分類器可能很弱(比如出現很大錯誤率),但只要它的分類效果比隨機好一點(比如兩類問題分類錯誤率略小於0.5),就能夠改善最終得到的模型。而錯誤率高於隨機分類器的弱分類器也是有用的,因為在最終得到的多個分類器的線性組合中,可以給它們賦予負係數,同樣也能提升分類效果。

AdaBoost方法是一種迭代算法,在每一輪中加入一個新的弱分類器,直到達到某個預定的足夠小的錯誤率。每一個訓練樣本都被賦予一個權重,表明它被某個分類器選入訓練集的概率。如果某個樣本點已經被準確地分類,那麼在構造下一個訓練集中,它被選中的概率就被降低;相反,如果某個樣本點沒有被準確地分類,那麼它的權重就得到提高。通過這樣的方式,AdaBoost方法能「聚焦於」那些較難分(更富信息)的樣本上。在具體實現上,最初令每個樣本的權重都相等,對於第k次迭代操作,我們就根據這些權重來選取樣本點,進而訓練分類器Ck。然後就根據這個分類器,來提高被它分錯的樣本的權重,並降低被正確分類的樣本權重。然後,權重更新過的樣本集被用於訓練下一個分類器Ck[2]。整個訓練過程如此迭代地進行下去。

AdaBoost算法

用xi和yi表示原始樣本集D的樣本點和它們的類標。用Wk(i)表示第k次迭代時全體樣本的權重分布。這樣就有如下所示的AdaBoost算法:

  1. 初始化:輸入參數為訓練集D={x1,y1,...,xn,yn},最大循環次數kmax,採樣權重Wk(i)=1/n,i=1,...,n;
  2. 迭代計數器k賦值為0;
  3. 計數器k自增1;
  4. 使用Wk(i)採樣權重對弱學習器Ck進行訓練;
  5. 對弱學習器Ck的訓練結果進行評估並記錄進誤差矩陣Ek中;
  6.  
  7.  
  8. 當k=kmax時停止訓練
  9. 返回結果 Ck和αk,k=1,...,kmax(帶權值分類器的總體)
  10. 結束

注意第5行中,當前權重分布必須考慮到分類器Ck的誤差率。在第7行中,Zk只是一個歸一化係數,使得Wk(i)能夠代表一個真正的分布,而hk(xi)是分量分類器Ck給出的對任一樣本點xi的標記(+1或-1),hk(xi) = yi時,樣本被正確分類。第8行中的迭代停止條件可以被換為判斷當前誤差率是否小於一個閾值。

最後的總體分類的判決可以使用各個分量分類器加權平均來得到:

 

這樣,最後對分類結果的判定規則是:

 

軟件實現

參考書目

  1. ^ Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855 . 
  2. ^ O. Duda, Peter E. Hart, David G. Stork, Pattern Classification, 2nd Edition, Wiley, 2000, ISBN 978-0-471-05669-0