AdaBoost

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

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

AdaBoost算法

用xⁱ和y_i表示原始樣本集D的樣本點和它們的類標。用W_k(i)表示第k次迭代時全體樣本的權重分佈。這樣就有如下所示的AdaBoost算法：

1. 初始化：輸入參數為訓練集D={x¹，y₁，...，xⁿ，y_n}，最大循環次數k_max，採樣權重W_k(i)=1/n，i=1，...，n；
2. 迭代計數器k賦值為0；
3. 計數器k自增1；
4. 使用W_k(i)採樣權重對弱學習器C_k進行訓練；
5. 對弱學習器C_k的訓練結果進行評估並記錄進誤差矩陣E_k中；
6. ${\displaystyle \alpha _{k}\gets {\tfrac {1}{2}}\ln {\frac {1-E_{k}}{E_{k}}}}$
7. ${\displaystyle W_{k+1}(i)\gets {\dfrac {W_{k}(i)}{Z_{k}}}\times {\begin{cases}e^{-\alpha _{k}},&{\mbox{if }}h_{k}(x^{i})=y_{i}\\e^{\alpha _{k}},&{\mbox{if }}h_{k}(x^{i})\neq y_{i}\end{cases}}}$
8. 當k=k_max時停止訓練
9. 返回結果 C_k和α_k，k=1，...，k_max（帶權值分類器的總體）
10. 結束

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

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

${\displaystyle g(x)=[\sum _{k=1}^{k_{max}}\alpha _{k}h_{k}(x)]}$

這樣，最後對分類結果的判定規則是：

${\displaystyle H(x)={\textrm {sign}}\left(g(x)\right)}$

軟件實現

• 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.

參考書目

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