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二元分類問題演算法流程總結
輸入：訓練資料集$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，則上式和我們的二元分類演算法中的弱分類器的系數一致，
到這里Adaboost分類問題差不多結束了，前面有一個沒有提到，就是弱學習器的型別，理論上任何學習器都可以用于Adaboost，但一般來說，使用最廣泛的Adaboost弱學習器是決策樹和神經網路，對于決策樹，文章開頭有提到Adaboost既可以用作分類，也可以用作回歸，Adaboost分類用了CART分類樹，而Adaboost回歸用了CART回歸樹，
6. Adaboost回歸演算法原理
由于Adaboost的回歸問題有很多變種，這里我們以Adaboost R2演算法為準，
假設一個回歸訓練集樣本是：$$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個弱學習器，計算他在訓練集上的最大誤差：$$E_k= max|y_i - G_k(x_i)|\;i=1,2...m$$
然后計算每個樣本的相對誤差：$$e_{ki}= \frac{|y_i - G_k(x_i)|}{E_k}$$
這里是誤差損失為線性時的情況，如果我們用平方誤差，則$e_{ki}= \frac{(y_i - G_k(x_i))^2}{E_k^2}$,如果我們用的是指數誤差，則$e_{ki}= 1 - exp（\frac{-y_i + G_k(x_i))}{E_k}）$
最終得到第k個弱學習器的誤差率：$$e_k = \sum\limits_{i=1}^{m}w_{ki}e_{ki}$$
弱學習器權重系數α
接下來計算弱學習器權重系數$\alpha$：$$\alpha_k =\frac{e_k}{1-e_k}$$
計算更新樣本權重D，第k+1個弱學習器的樣本集權重系數為：$$w_{k+1,i} = \frac{w_{ki}}{Z_k}\alpha_k^{1-e_{ki}}$$
這里$Z_k$是規范化因子：$$Z_k = \sum\limits_{i=1}^{m}w_{ki}\alpha_k^{1-e_{ki}}$$
最后是結合策略，和分類問題稍有不同，采用的是對加權的弱學習器取權重中位數對應的弱學習器作為強學習器的方法，最終的強回歸器為：$$f(x) =G_{k^*}(x)$$
其中，$G_{k^*}(x)$是所有$ln\frac{1}{\alpha_k}, k=1,2,....K$的中位數值對應序號$k^*$對應的弱學習器，
7. Adaboost回歸問題演算法流程總結
這里再對AdaBoost回歸問題演算法流程做一個總結，AdaBoost回歸演算法變種很多，下面的演算法為Adaboost R2回歸演算法程序，
輸入為樣本集：$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$，弱學習器演算法, 弱學習器迭代次數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)$
b) 計算訓練集上的最大誤差：$$E_k= max|y_i - G_k(x_i)|\;i=1,2...m$$
c) 計算每個樣本的相對誤差：
- 如果是線性誤差，則$e_{ki}= \frac{|y_i - G_k(x_i)|}{E_k}$；
- 如果是平方誤差，則$e_{ki}= \frac{(y_i - G_k(x_i))^2}{E_k^2}$；
- 如果是指數誤差，則$e_{ki}= 1 - exp（\frac{-|y_i -G_k(x_i)|}{E_k}$，
d) 計算回歸誤差率：$$e_k = \sum\limits_{i=1}^{m}w_{ki}e_{ki}$$
e) 計算弱學習器的系數：$$\alpha_k =\frac{e_k}{1-e_k}$$
f) 更新樣本集的權重分布為：$$w_{k+1,i} = \frac{w_{ki}}{Z_k}\alpha_k^{1-e_{ki}}$$
這里$Z_k$是規范化因子：$$Z_k = \sum\limits_{i=1}^{m}w_{ki}\alpha_k^{1-e_{ki}}$$
3) 構建最終強學習器為：$$f(x) =G_{k^*}(x)$$
其中，$G_{k^*}(x)$是所有$ln\frac{1}{\alpha_k}, k=1,2,....K$的中位數值對應序號$k^*$對應的弱學習器，
8. 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，對于同樣的訓練集學習效果，較小的ν意味著我們需要更多的弱學習器的迭代次數，通常我們用步長和迭代最大次數一起來決定演算法的擬合效果，
9. Adaboost演算法優缺點
Adaboost的優點：
1）Adaboost作為分類器時，分類精度很高；
2）在Adaboost的框架下，可以使用各種回歸分類模型來構建弱學習器，非常靈活；
3）作為簡單的二元分類器時，構造簡單，容易實施，結果可理解；
4）不容易發生過擬合，
Adaboost的缺點：
1）對例外樣本敏感，例外樣本在迭代中可能會獲得較高的權重，影響最終的強學習器的預測準確性；
2）訓練時間過長，每次一個分類器都要用全部樣本學習，對于弱分類器學習來講，時間及速度上影響不大，強分類器的學習時間會就會比較大，
參考文章：
https://zhuanlan.zhihu.com/p/59121403
https://www.cnblogs.com/pinard/p/6133937.html
https://www.cnblogs.com/ScorpioLu/p/8295990.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/160781.html
標籤：Python