1. 回顧Boosting提升演算法 AdaBoost是典型的Boosting演算法，屬於Boosting家族的一員。在說AdaBoost之前，先說說Boosting提升演算法。Boosting演算法是將“弱學習演算法“提升為“強學習演算法”的過程，主要思想是“三個臭皮匠頂個諸葛亮”。一般來說，找到弱學習演算法要 ...
1. 回顧Boosting提升演算法
AdaBoost是典型的Boosting演算法，屬於Boosting家族的一員。在說AdaBoost之前，先說說Boosting提升演算法。Boosting演算法是將“弱學習演算法“提升為“強學習演算法”的過程，主要思想是“三個臭皮匠頂個諸葛亮”。一般來說，找到弱學習演算法要相對容易一些，然後通過反覆學習得到一系列弱分類器，組合這些弱分類器得到一個強分類器。Boosting演算法要涉及到兩個部分，加法模型和前向分步演算法。
模型為加法模型就是我們最終的強分類器是若幹個弱分類器加權平均而得到的（弱分類器線性相加而成）。
前向分步就是我們在訓練的過程中，下一輪迭代產生的分類器是在上一輪的基礎上訓練得來的。我們的演算法是通過一輪輪的弱學習器學習，利用前一個強學習器的結果和當前弱學習器來更新當前的強學習器的模型。也就是說
第k-1輪的強學習器為：$f_{k-1}(x) = \sum\limits_{i=1}^{k-1}\alpha_iG_{i}(x)$
而第k輪的強學習器為：$f_{k}(x) = \sum\limits_{i=1}^{k}\alpha_iG_{i}(x)$
上兩式一比較可以得到：$f_{k}(x) = f_{k-1}(x) + \alpha_kG_k(x)$
可見強學習器的確是通過前向分步學習演算法一步步而得到的。
2. 集成學習之AdaBoost演算法
Adaboost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。這裡的集合起來的策略是通過提高前一輪分類器分類錯誤的樣本的權值，降低分類分類正確的樣本權值，對於那些沒有本分類正確的樣本會得到後面分類器更多的關註。然後可以產生很多的弱分類器，通過多數加權投票組合這些弱分類器，加大誤差率小的分類器，減少誤差率大的分類器，使其在表決中起到較少的作用。
只要是boosting演算法，都要解決以下這4個問題：（結合Adaboost演算法原理理解怎麼解決）
1）如何計算學習誤差率e?
2）如何得到弱學習器權重繫數αα?
3）如何更新樣本權重D?
4) 使用何種結合策略？
3. Adaboost演算法原理
假設一個二分類訓練樣本集：
$$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$$
訓練集的在第k個弱學習器的輸出權重為：
$$D(k) = (w_{k1}, w_{k2}, ...w_{km}) ;\;\; w_{1i}=\frac{1}{m};\;\; i =1,2...m$$
第k個弱分類器$G_k(x)$在訓練集上的加權誤差率為：
$$e_k = P(G_k(x_i) \neq y_i) = \sum\limits_{i=1}^{m}w_{ki}I(G_k(x_i) \neq y_i)$$
第k個弱分類器$G_k(x)$的權重繫數為：
$$\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k}$$
為什麼這樣計算弱學習器權重繫數？從上式可以看出，如果分類誤差率$e_k$越大，則對應的弱分類器權重繫數$\alpha_k$越小。也就是說，誤差率小的弱分類器權重繫數越大。具體為什麼採用這個權重繫數公式，我們在講Adaboost的損失函數優化時再講。
更新樣本權重D。假設第k個弱分類器的樣本集權重繫數為$D(k) = (w_{k1}, w_{k2}, ...w_{km})$，則對應的第k+1個弱分類器的樣本集權重繫數為：
$$w_{k+1,i} = \frac{w_{ki}}{Z_K}exp(-\alpha_ky_iG_k(x_i))$$
這裡$Z_k$是規範化因數：
$$Z_k = \sum\limits_{i=1}^{m}w_{ki}exp(-\alpha_ky_iG_k(x_i))$$
從$w_{k+1,i}$ 計算公式可以看出，如果第i個樣本分類錯誤，則$yiGk(xi)<0$，導致樣本的權重在第k+1個弱分類器中增大，如果分類正確，則權重在第k+1個弱分類器中減少.具體為什麼採用樣本權重更新公式，我們在講Adaboost的損失函數優化時再講。
最後是集合策略。Adaboost分類採用的是加權表決法，構建基本分類器的線性組合：
$$f(x) = \sum\limits_{k=1}^{K}\alpha_kG_k(x)$$
最終的強分類器為：
$$G(x) = sign(f(x)) = sign(\sum\limits_{k=1}^{K}\alpha_kG_k(x))$$
4. AdaBoost分類問題的損失函數優化
分類問題的Adaboost的弱學習器權重繫數公式和樣本權重更新公式，可以從Adaboost的損失函數推導出來。Adaboost是模型為加法模型，學習演算法為前向分步學習演算法，損失函數為指數函數的分類問題。
首先AdaBoost演算法的最終模型表達式為：
$$f(x) = \sum\limits_{m=1}^{M}\alpha_kG_k(x)$$
可以看到這是一個“加性模型(additive model)”。我們希望這個模型在訓練集上的經驗誤差最小，即：
$$min\sum_{i=1}^{N}L(y_i,f(x)) < = > min\sum_{i=1}^{N}L(y_i,\sum\limits_{i=1}^{M}\alpha_mG_m(x))$$
通常這是一個複雜的優化問題。前向分步演算法求解這一優化問題的思想就是: 因為最終模型是一個加性模型，如果能從前往後，每一步只學習一個基學習器$G_m(x)$及其權重$\alpha_m$, 不斷迭代得到最終的模型，那麼就可以簡化問題複雜度。具體的，當我們經過$m-1$輪迭代得到了最優模型$f_{m-1}(x)$時，由前向分步演算法可知：
$$f_m(x) = f_{m-1}(x) + \alpha_mG_m(x)$$
所以此輪優化目標就為：
$$min\sum_{i=1}^{N}L(y_i,f_{m-1}(x) + \alpha_mG_m(x))$$
求解上式即可得到第$m$個基分類器$G_m(x)$及其權重$\alpha_m$。
這樣，前向分步演算法就通過不斷迭代求得了從$m=1$到$m=M$的所有基分類器及其權重，問題得到瞭解決。
上面主要介紹了前向分步演算法逐一學習基學習器，這一過程也即AdaBoost演算法逐一學習基學習器的過程。下麵將證明前向分步演算法的損失函數是指數損失函數(exponential loss function)時，AdaBoost學習的具體步驟。
首先指數損失函數即$L(y,f(x)) = exp(-yf(x))$，指數損失函數是分類任務原本0/1損失函數的一致(consistent)替代損失函數，由於指數損失函數有更好的數學性質，例如處處可微，所以我們用它替代0/1損失作為優化目標。
AdaBoost是採用指數損失，由此可以得到損失函數：
$$Loss=\sum_{i=1}^{N}exp(-y_if_m (x_i ))=\sum_{i=1}^{N}(-y_i(f_{m-1}(x_i )+\alpha_mG_m(x)))$$
因為$y_if_{m-1}(x)$與優化變數$\alpha$和$G$無關，所以令$w_{m,i}=exp(-y_if_m(x))$，這裡$y_if_{m-1}(x)$是已知的，相當於可以作為常量移到前面去：
$$Loss=\sum_{i=1}^{N}w_{m,i} exp(-y_i\alpha_mG_m(x)))$$接下來就是求解上式的優化問題的最優解$\hat{\alpha}_m$和$\hat{G}_m(x)$。
首先我們求$\hat{G}_m(x)$，可以得到：
$$G_m(x) = \underset{G}{arg\;min\;}\sum\limits_{i=1}^{m}w_{mi}I(y_i \neq G_m(x_i))$$
上式將指數函數換成指示函數是因為前面說的指數損失函數和0/1損失函數是一致等價的。式子中所示的優化問題其實就是AdaBoost演算法的基學習器的學習過程，即計算數據集的分類誤差率，得到的$\hat{G}_m(x)$是使第$m$輪加權訓練數據分類誤差最小的基分類器。
然後求$\hat{\alpha}_m$，將$G_m(x)$帶入損失函數，並對$\alpha$求導，使其等於0，即可得到：$$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$
其中，$e_m$即為我們前面的分類誤差率：$$e_m = \frac{\sum\limits_{i=1}^{m}w_{mi}I(y_i \neq G(x_i))}{\sum\limits_{i=1}^{m}w_{mi}} = \sum\limits_{i=1}^{m}w_{mi}I(y_i \neq G(x_i))$$
最後看樣本權重的更新：利用$f_{m}(x) = f_{m-1}(x) + \alpha_mG_m(x) $和$w_{mi} = exp(-y_if_{m-1}(x))$，即可得：$$w_{m+1,i} = w_{mi}exp[-y_i\alpha_mG_m(x)]$$
到此AdaBoost二分類演算法推導結束。
5. Adaboost演算法的正則化
為了防止Adaboost過擬合，我們通常也會加入正則化項，這個正則化項我們通常稱為步長(learning rate)。定義為ν,對於前面的弱學習器的迭代：
$$f_{k}(x) = f_{k-1}(x) + \alpha_kG_k(x) $$
如果我們加上了正則化項，則有：
$$f_{k}(x) = f_{k-1}(x) + \nu\alpha_kG_k(x) $$
ν 的取值範圍為0<ν≤1。對於同樣的訓練集學習效果，較小的ν意味著我們需要更多的弱學習器的迭代次數。通常我們用步長和迭代最大次數一起來決定演算法的擬合效果。
6. AdaBoost二元分類問題演算法流程總結
輸入：訓練數據集$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$，輸出為{-1, +1}，弱分類器演算法, 弱分類器迭代次數K；
輸出：為最終的強分類器$f(x)$。
1) 初始化樣本集權重為：
$$D(1) = (w_{11}, w_{12}, ...w_{1m}) ;\;\; w_{1i}=\frac{1}{m};\;\; i =1,2...m$$
2) 對於k=1,2，...K：
a) 使用具有權重$D_k$的樣本集來訓練數據，得到弱分類器$G_k(x):\chi\to\{{-1,+1}\}$
b)計算$G_k(x)$的分類誤差率：$$e_k = P(G_k(x_i) \neq y_i) = \sum\limits_{i=1}^{m}w_{ki}I(G_k(x_i) \neq y_i)$$
c) 計算弱分類器的繫數：$$\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k}$$
d) 更新樣本集的權重分佈：$$w_{k+1,i} = \frac{w_{ki}}{Z_K}exp(-\alpha_ky_iG_k(x_i)) \;\; i =1,2,...m$$
這裡$Z_k$是規範化因數：$$Z_k = \sum\limits_{i=1}^{m}w_{ki}exp(-\alpha_ky_iG_k(x_i))$$
3) 構建最終分類器為：$$f(x) = sign(\sum\limits_{k=1}^{K}\alpha_kG_k(x))$$
對於Adaboost多元分類演算法，其實原理和二元分類類似，最主要區別在弱分類器的繫數上。比如Adaboost SAMME演算法，它的弱分類器的繫數：$$\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k} + log(R-1)$$
其中R為類別數。從上式可以看出，如果是二元分類，R=2，則上式和我們的二元分類演算法中的弱分類器的繫數一致。
7. 總結
到這裡Adaboost分類問題差不多結束了，前面有一個沒有提到，就是弱學習器的類型。理論上任何學習器都可以用於Adaboost，但一般來說，使用最廣泛的Adaboost弱學習器是決策樹和神經網路。對於決策樹，Adaboost分類用了CART分類樹，而Adaboost回歸用了CART回歸樹。
Adaboost的優點有：
1）Adaboost作為分類器時，分類精度很高；
2）在Adaboost的框架下，可以使用各種回歸分類模型來構建弱學習器，非常靈活；
3）作為簡單的二元分類器時，構造簡單，容易實施，結果可理解；
4）不容易發生過擬合。
Adaboost的缺點有：
1）對異常樣本敏感，異常樣本在迭代中可能會獲得較高的權重，影響最終的強學習器的預測準確性。
【補充】：文章開頭有提到Adaboost既可以用作分類，也可以用作回歸，本文主要針對Adaboost二分類問題做了詳細介紹，關於Adaboost回歸問題，可以參考https://www.cnblogs.com/pinard/p/6133937.html這篇博客，解釋的很詳細。
參考文章：
https://zhuanlan.zhihu.com/p/59121403
https://www.cnblogs.com/pinard/p/6133937.html
https://www.cnblogs.com/ScorpioLu/p/8295990.html
