AdaBoost
AdaBoost為英文"Adaptive Boosting"(自適應增強)的縮寫,是一種機器學習方法,由約阿夫·弗羅因德和羅伯特·沙皮爾提出。[1]AdaBoost方法的自適應在於:前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對於噪聲數據和異常數據很敏感。但在一些問題中,AdaBoost方法相對於大多數其它學習算法而言,不會很容易出現過擬合現象。AdaBoost方法中使用的分類器可能很弱(比如出現很大錯誤率),但只要它的分類效果比隨機好一點(比如兩類問題分類錯誤率略小於0.5),就能夠改善最終得到的模型。而錯誤率高於隨機分類器的弱分類器也是有用的,因為在最終得到的多個分類器的線性組合中,可以給它們賦予負係數,同樣也能提升分類效果。
AdaBoost方法是一種迭代算法,在每一輪中加入一個新的弱分類器,直到達到某個預定的足夠小的錯誤率。每一個訓練樣本都被賦予一個權重,表明它被某個分類器選入訓練集的概率。如果某個樣本點已經被準確地分類,那麼在構造下一個訓練集中,它被選中的概率就被降低;相反,如果某個樣本點沒有被準確地分類,那麼它的權重就得到提高。通過這樣的方式,AdaBoost方法能「聚焦於」那些較難分(更富信息)的樣本上。在具體實現上,最初令每個樣本的權重都相等,對於第k次迭代操作,我們就根據這些權重來選取樣本點,進而訓練分類器Ck。然後就根據這個分類器,來提高被它分錯的樣本的權重,並降低被正確分類的樣本權重。然後,權重更新過的樣本集被用於訓練下一個分類器Ck[2]。整個訓練過程如此迭代地進行下去。
AdaBoost算法
編輯用xi和yi表示原始樣本集D的樣本點和它們的類標。用Wk(i)表示第k次迭代時全體樣本的權重分佈。這樣就有如下所示的AdaBoost算法:
- 初始化:輸入參數為訓練集D={x1,y1,...,xn,yn},最大循環次數kmax,採樣權重Wk(i)=1/n,i=1,...,n;
- 迭代計數器k賦值為0;
- 計數器k自增1;
- 使用Wk(i)採樣權重對弱學習器Ck進行訓練;
- 對弱學習器Ck的訓練結果進行評估並記錄進誤差矩陣Ek中;
- 當k=kmax時停止訓練
- 返回結果 Ck和αk,k=1,...,kmax(帶權值分類器的總體)
- 結束
注意第5行中,當前權重分佈必須考慮到分類器Ck的誤差率。在第7行中,Zk只是一個歸一化係數,使得Wk(i)能夠代表一個真正的分佈,而hk(xi)是分量分類器Ck給出的對任一樣本點xi的標記(+1或-1),hk(xi) = yi時,樣本被正確分類。第8行中的迭代停止條件可以被換為判斷當前誤差率是否小於一個閾值。
最後的總體分類的判決可以使用各個分量分類器加權平均來得到:
這樣,最後對分類結果的判定規則是:
軟件實現
編輯- AdaBoost and the Super Bowl of Classifiers - A Tutorial on AdaBoost.(頁面存檔備份,存於互聯網檔案館)
- Adaboost in C++(頁面存檔備份,存於互聯網檔案館), an implementation of Adaboost in C++ and boost by Antonio Gulli
- icsiboost(頁面存檔備份,存於互聯網檔案館), an open source implementation of Boostexter
- JBoost(頁面存檔備份,存於互聯網檔案館), a site offering a classification and visualization package, implementing AdaBoost among other boosting algorithms.
- MATLAB AdaBoost toolbox. Includes Real AdaBoost, Gentle AdaBoost and Modest AdaBoost implementations.
- A Matlab Implementation of AdaBoost(頁面存檔備份,存於互聯網檔案館)
- Multi-threaded MATLAB-compatible implementation of Boosted Trees(頁面存檔備份,存於互聯網檔案館)
- milk(頁面存檔備份,存於互聯網檔案館) for Python implements AdaBoost.
- MPBoost++(頁面存檔備份,存於互聯網檔案館), a C++ implementation of the original AdaBoost.MH algorithm and of an improved variant, the MPBoost algorithm.
- multiboost, a fast C++ implementation of multi-class/multi-label/multi-task boosting algorithms. It is based on AdaBoost.MH but also implements popular cascade classifiers and FilterBoost along with a batch of common multi-class base learners(stumps, trees, products, Haar filters)。
- NPatternRecognizer (頁面存檔備份,存於互聯網檔案館), a fast machine learning algorithm library written in C#. It contains support vector machine, neural networks, bayes, boost, k-nearest neighbor, decision tree, ..., etc.
- OpenCV implementation of several boosting variants
- Into contains open source implementations of many AdaBoost and FloatBoost variants in C++.
- Mallet(頁面存檔備份,存於互聯網檔案館) Java implementation.
- adabag adabag: An R package for binary and multiclass Boosting and Bagging.
- Scikit-learn Python implementation.
參考書目
編輯- ^ 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 .
- ^ O. Duda, Peter E. Hart, David G. Stork, Pattern Classification, 2nd Edition, Wiley, 2000, ISBN 978-0-471-05669-0