Boosting算法

Boosting是一種用來提高弱分類器準確度的算法，是將“弱學習算法“提升為“強學習算法”的過程，主要思想是“三個臭皮匠頂個諸葛亮”。一般來說，找到弱學習算法要相對容易一些，然后通過反復學習得到一系列弱分類器，組合這些弱分類器得到一個強分類器。

Boosting算法要涉及到兩個部分，加法模型和前向分步算法。
加法模型就是說強分類器由一系列弱分類器線性相加而成。一般組合形式如下：
$$F_M(x;P)=/sum_{m=1}^n/beta_mh(x;a_m)$$
其中，$h(x;a_m)$就是一個個的弱分類器，$a_m$是弱分類器學習到的最優參數，$/beta_m$就是弱學習在強分類器中所占比重，$P$是所有$/alpha_m$和$/beta_m$的組合。這些弱分類器線性相加組成強分類器。

前向分步就是說在訓練過程中，下一輪迭代產生的分類器是在上一輪的基礎上訓練得來的。也就是可以寫成這樣的形式：
$$F_m (x)=F_{m-1}(x)+ /beta_mh_m (x;a_m)$$

用下面的GIF看起來會更加生動

Adaboost基本概念

AdaBoost是典型的Boosting算法，屬于Boosting家族的一員。

對于AdaBoost，我們要搞清楚兩點：

1、每一次迭代的弱學習$h(x;a_m)$有何不一樣，如何學習？

2、弱分類器權值$/beta_m$如何確定？

第一個問題，AdaBoost的做法是，提高那些被前一輪弱分類器錯分類樣本的權值，而降低那些被正確分類樣本的權值。這樣一來，那些沒有得到正確分類的數據，由于其權值加大而受到后一輪的弱分類器的更大關注。于是，分類問題被一系列的弱分類器“分而治之”。

第二個問題，即弱分類器的組合，AdaBoost采取加權多數表決的方法。具體地，加大分類誤差率小的弱分類器的權值，使其在表決中起較大的作用，減小分類誤差率大的弱分類器的權值，使其在表決中起較小的作用。

Adaboost算法流程-分類

輸入：訓練數據集$T=/{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)/}$，其中，$x_i∈X?R^n$，$y_i∈Y={-1,1}$，迭代次數$M$

1.初始化訓練樣本的權值分布:

$$ /begin{aligned} D_1=(w_{1,1},w_{1,2},…,w_{1,i}),//w_{1,i}=/frac{1}{N},i=1,2,…,N /end{aligned} $$

2.對于$m=1,2,…,M$

(a)使用具有權值分布$D_m$的訓練數據集進行學習，得到弱分類器$G_m (x)$

(b)計算$G_m(x)$在訓練數據集上的分類誤差率：$$e_m=/sum_{i=1}^Nw_{m,i} I(G_m (x_i )≠y_i )$$
(c)計算$G_m (x)$在強分類器中所占的權重：$$/alpha_m=/frac{1}{2}log /frac{1-e_m}{e_m} $$
(d)更新訓練數據集的權值分布（這里，(z_m)是歸一化因子，為了使樣本的概率分布和為1）：
$$w_{m+1,i}=/frac{w_{m,i}}{z_m}exp?(-/alpha_m y_i G_m (x_i ))，i=1,2,…,10$$
$$z_m=/sum_{i=1}^Nw_{m,i}exp?(-/alpha_m y_i G_m (x_i ))$$
3.得到最終分類器:
$$F(x)=sign(/sum_{i=1}^N/alpha_m G_m (x))$$

公式推導

假設已經經過$m-1$輪迭代，得到$F_{m-1} (x)$，根據前向分步，我們可以得到：
$$F_m (x)=F_{m-1} (x)+/alpha_m G_m (x)$$
我們已經知道AdaBoost是采用指數損失，由此可以得到損失函數：

$$ /begin{aligned} Loss=&/sum_{i=1}^Nexp?(-y_i F_m (x_i ))// =&/sum_{i=1}^Nexp?(-y_i (F_{m-1} (x_i )+/alpha_m G_m (x_i ))) /end{aligned} $$

這時候,$F_{m-1}(x)$是已知的，可以作為常量移到前面去:
$$Loss=/sum_{i=1}^N/widetilde{w_{m,i}} exp?(-y_i /alpha_m G_m (x_i ))$$
其中，$/widetilde{w_{m,i}}=exp?(-y_i (F_{m-1} (x)))$ 就是每輪迭代的樣本權重！依賴于前一輪的迭代重分配。
再化簡一下：

$$ /begin{aligned} /widetilde{w_{m,i}}=&exp?(-y_i (F_{m-1} (x_i )+/alpha_{m-1} G_{m-1} (x_i )))//=&/widetilde{w_{m-1,i}} exp?(-y_i /alpha_{m-1} G_{m-1} (x_i )) /end{aligned} $$

繼續化簡Loss：

$$ /begin{aligned} Loss=/sum_{y_i=G_m(x_i)}/widetilde{w_{m,i}} exp(-/alpha_m)+/sum_{y_i≠G_m(x_i)}/widetilde{w_{m,i}} exp?(/alpha_m)//=/sum_{i=1}^N/widetilde{w_{m,i}}(/frac{/sum_{y_i=G_m(x_i)}/widetilde{w_{m,i}}}{/sum_{i=1}^N/widetilde{w_{m,i}}}exp(-/alpha_m)+/frac{/sum_{y_i≠G_m(x_i)}/widetilde{w_{m,i}}}{/sum_{i=1}^N/widetilde{w_{m,i}}}exp(/alpha_m)) /end{aligned} $$

其中
$/frac{/sum_{y_i≠G_m(x_i)}/widetilde{w_{m,i}}}{/sum_{i=1}^N/widetilde{w_{m,i}}}$就是分類誤差率$e_m$
所以
$Loss=/sum_{i=1}^N/widetilde{w_{m,i}}exp?(-/alpha_m)+e_m exp?(/alpha_m))$
這樣我們就得到了化簡之后的損失函數
對$/alpha_m$求偏導令$/frac{?Loss}{?/alpha_m }=0$得到：
$$/alpha_m=/frac{1}{2}log/frac{1-e_m}{e_m}$$

AdaBoost實例

《統計學習方法》上面有個小例子，可以用來加深印象
有如下的訓練樣本，我們需要構建強分類器對其進行分類。x是特征，y是標簽。

令權值分布$D_1=(w_{1,1},w_{1,2},…,w_{1,10} )$
假設一開始的權值分布是均勻分布：$w_{1,i}=0.1，i=1,2,…,10$
現在開始訓練第一個弱分類器。我們發現閾值取2.5時分類誤差率最低，得到弱分類器為：

$$ G_1(x)= /begin{cases} 1,& /text{x<2.5} // -1,& /text{x>2.5} /end{cases} $$

當然，也可以用別的弱分類器，只要誤差率最低即可。這里為了方便，用了分段函數。得到了分類誤差率$e_1=0.3$

第二步計算$G_1 (x)$在強分類器中的系數$/alpha_1=/frac{1}{2} log/frac{ 1-e_1}{e_1}=0.4236$

第三步更新樣本的權值分布，用于下一輪迭代訓練。由公式：
$$w_{2,i}=/frac{w_{1,i}}{z_1}exp?(-/alpha_1 y_i G_1 (x_i ))，i=1,2,…,10$$
得到新的權值分布，從各0.1變成了:
$D_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)$
可以看出，被分類正確的樣本權值減小了，被錯誤分類的樣本權值提高了。

第四步得到第一輪迭代的強分類器：
$$sign(F_1 (x))=sign(0.4236G_1 (x))$$
以此類推，經過第二輪……第N輪，迭代多次直至得到最終的強分類器。迭代范圍可以自己定義，比如限定收斂閾值，分類誤差率小于某一個值就停止迭代，比如限定迭代次數，迭代1000次停止。這里數據簡單，在第3輪迭代時，得到強分類器：
$$sign(F_3 (x))=sign(0.4236G_1 (x)+0.6496G_2 (x)+0.7514G_3 (x))$$
的分類誤差率為0，結束迭代。

$F(x)=sign(F_3 (x))$就是最終的強分類器。

Adaboost參數詳解

我們直接使用sklearn.ensemble中的AdaBoostRegressor和AdaBoostClassifier，兩者大部分框架參數是相同的：

AdaBoostRegressor

class sklearn.ensemble.AdaBoostRegressor
(base_estimator=None, n_estimators=50, 
learning_rate=1.0, loss=’linear’, random_state=None)

AdaBoostClassifier

class sklearn.ensemble.AdaBoostClassifier
(base_estimator=None, n_estimators=50, 
learning_rate=1.0, algorithm=’SAMME.R’, random_state=None)

參數

1）base_estimator：AdaBoostClassifier和AdaBoostRegressor都有，即我們的弱分類學習器或者弱回歸學習器。理論上可以選擇任何一個分類或者回歸學習器，不過需要支持樣本權重。我們常用的一般是CART決策樹或者神經網絡MLP。默認是決策樹，即AdaBoostClassifier默認使用CART分類樹DecisionTreeClassifier，而AdaBoostRegressor默認使用CART回歸樹DecisionTreeRegressor。另外有一個要注意的點是，如果我們選擇的AdaBoostClassifier算法是SAMME.R，則我們的弱分類學習器還需要支持概率預測，也就是在scikit-learn中弱分類學習器對應的預測方法除了predict還需要有predict_proba。

2）algorithm：這個參數只有AdaBoostClassifier有。主要原因是scikit-learn實現了兩種Adaboost分類算法，SAMME和SAMME.R。兩者的主要區別是弱學習器權重的度量，SAMME使用了二元分類Adaboost算法的擴展，即用對樣本集分類效果作為弱學習器權重，而SAMME.R使用了對樣本集分類的預測概率大小來作為弱學習器權重。由于SAMME.R使用了概率度量的連續值，迭代一般比SAMME快，因此AdaBoostClassifier的默認算法algorithm的值也是SAMME.R。我們一般使用默認的SAMME.R就夠了，但是要注意的是使用了SAMME.R， 則弱分類學習器參數base_estimator必須限制使用支持概率預測的分類器。SAMME算法則沒有這個限制。

3）loss：這個參數只有AdaBoostRegressor有，Adaboost.R2算法需要用到。有線性‘linear’, 平方‘square’和指數 ‘exponential’三種選擇, 默認是線性，一般使用線性就足夠了，除非你懷疑這個參數導致擬合程度不好。

4)n_estimators： AdaBoostClassifier和AdaBoostRegressor都有，就是我們的弱學習器的最大迭代次數，或者說最大的弱學習器的個數。一般來說n_estimators太小，容易欠擬合，n_estimators太大，又容易過擬合，一般選擇一個適中的數值。默認是50。在實際調參的過程中，我們常常將n_estimators和下面介紹的參數learning_rate一起考慮。

5)learning_rate: AdaBoostClassifier和AdaBoostRegressor都有，即每個弱學習器的權重縮減系數ν，在原理篇的正則化章節我們也講到了，加上了正則化項，我們的強學習器的迭代公式為$fk(x)=fk?1(x)+ναkGk(x)$。ν的取值范圍為0<ν≤1。對于同樣的訓練集擬合效果，較小的ν意味著我們需要更多的弱學習器的迭代次數。通常我們用步長和迭代最大次數一起來決定算法的擬合效果。所以這兩個參數n_estimators和learning_rate要一起調參。一般來說，可以從一個小一點的ν開始調參，默認是1。

SAMME.R算法流程

1.初始化樣本權值：
$$w_i=1/N,i=1,2,…,N$$
2.Repeat for$m=1,2,…,M$

2.1 訓練一個弱分類器，得到樣本的類別預測概率分布$p_m(x)=P(y=1|x)∈[0,1]$

2.2 $f_m(x)=/frac{1}{2}log/frac{p_m(x)}{1-p_m(x)}$

2.3 $w_i=w_iexp[-y_if_m(x_i)]$，同時，要進行歸一化使得權重和為1
3.得到強分類模型：$sign{/sum_{m=1}^{M}f_m(x)}$

DecisionTreeClassifier和DecisionTreeRegressor的弱學習器參數，以CART分類樹為例，這里就和前文隨機森林類似了。

方法

decision_function(X):返回決策函數值

fit(X,Y):在數據集（X,Y）上訓練模型

get_parms():獲取模型參數

predict(X):預測數據集X的結果

predict_log_proba(X):預測數據集X的對數概率

predict_proba(X):預測數據集X的概率值

score(X,Y):輸出數據集（X,Y）在模型上的準確率

staged_decision_function(X):返回每個基分類器的決策函數值

staged_predict(X):返回每個基分類器的預測數據集X的結果

staged_predict_proba(X):返回每個基分類器的預測數據集X的概率結果

staged_score(X, Y):返回每個基分類器的預測準確率。

Adaboost總結

Adaboost優點

1.可以使用各種方法構造子分類器，Adaboost算法提供的是框架

2.簡單，不用做特征篩選

3.相比較于RF，更不用擔心過擬合問題

Adaboost缺點

1.從wiki上介紹的來看，adaboost對于噪音數據和異常數據是十分敏感的。Boosting方法本身對噪聲點異常點很敏感，因此在每次迭代時候會給噪聲點較大的權重，這不是我們系統所期望的。

2.運行速度慢，凡是涉及迭代的基本上都無法采用并行計算，Adaboost是一種"串行"算法.所以GBDT(Gradient Boosting Decision Tree)也非常慢。

參考：

李航《統計學習方法》第8章 提升方法
《Getting Started with Machine Learning》Jim Liang
https://www.cnblogs.com/pinar...
https://www.cnblogs.com/Scorp...
https://louisscorpio.github.i...
https://ask.hellobi.com/blog/...

本文由博客一文多發平臺 OpenWrite 發布！

審核編輯 黃昊宇