AdaBoost

AdaBoost，是「adaptive boosting」（自適應增強）的縮寫，是一種機器學習方法，由Yoav Freund和Robert Schapire提出。AdaBoost方法的自適應在於：後面的分類器會在那些被之前分類器分錯的樣本上訓練。AdaBoost方法對於噪聲數據和異常數據很敏感。但在一些問題中，相比於大多數學習算法，AdaBoost方法對於過擬合問題不夠敏感。AdaBoost方法中使用的分類器可能很弱（比如出現很大錯誤率），但其分類效果只要比隨機好一點（比如它的二分類錯誤率略小於0.5），就能夠改善最終模型。即使是那些錯誤率高於隨機分類器的弱分類器也是有用的，因為在最終的多個分類器的線性組合中，可以給它們賦予負係數，反過來也能提升分類效果。
AdaBoost方法是一種迭代算法，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率。每一個訓練樣本都被賦予一個權重，表明它被某個分類器選入訓練集的概率。如果某個樣本點已經被準確地分類，那麼在構造下一個訓練集中，它被選中的概率就被降低；相反，如果某個樣本點沒有被準確地分類，那麼它的權重就得到提高。通過這樣的方式，AdaBoost方法能「聚焦於」那些較困難（更富信息）的樣本上。在具體實現上，最初令每個樣本的權重都相等，對於第k次迭代操作，我們就根據這些權重來選取樣本點，勁兒訓練分類器C_k。然後就根據這個分類器，來提高被它分錯的的樣本的權重，並降低被正確分類的樣本權重。然後，權重更新過的樣本集被用於訓練下一個分類器C_k。整個訓練過程如此迭代地進行下去。

AdaBoost算法

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

1. begin initial D={x¹，y₁，...，xⁿ，y_n}，k_max，W_k(1)=1/n，i=1，...，n
2. k ← 0
3. do k ← k+1
4. 訓練使用按照 W_k(i) 採樣的 D 的若學習器 C_k
5. E_k ← 對使用 W_k(i) 的 D 測量的 C_k 的訓練誤差
6. $\alpha _{k}\gets {\tfrac {1}{2}}\ln {\frac {1-E_{k}}{E_{k}}}$
7. $W_{k}(i+1)\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. until k=k_max
9. return C_k和α_k，k=1，...，k_max（帶權值分類器的總體）
10. end

注意第5行中，當前權重分布必須考慮到分類器 C_k 的誤差率。在第7行中， Z_k只是一個歸一化係數，使得 W_k(i) 能夠代表一個真正的分布，而 h_k(xⁱ) 是分量分類器 C_k 給出的對任一樣本點xⁱ的標記（+1或-1）， h_k(xⁱ) = y_i 時，樣本被正確分類。第8行中的迭代停止條件可以被換為判斷當前誤差率是否小於一個閾值。
最後的總體分類的判決可以使用各個分量分類器加權平均來得到：
$g(x)=[\sum _{k=1}^{k_{max}}\alpha _{k}h_{k}(x)]$
這樣，最後的判定規則簡單的就是 Sgn[g(x)] 。