AdaBoost

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

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

## 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. $\alpha _{k}\gets {\tfrac {1}{2}}\ln {\frac {1-E_{k}}{E_{k}}}$
7. $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=kmax 時停止訓練
9. 返回結果 Ck 和 αk，k=1，...，kmax（帶權值分類器的總體）
10. **結束**

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

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

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

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

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

## 參考書目