100天搞定機(jī)器學(xué)習(xí)：Day57 Adaboost知識(shí)手冊(cè)(理論篇)

Boosting算法

Boosting是一種用來(lái)提高弱分類器準(zhǔn)確度的算法，是將“弱學(xué)習(xí)算法“提升為“強(qiáng)學(xué)習(xí)算法”的過(guò)程，主要思想是“三個(gè)臭皮匠頂個(gè)諸葛亮”。一般來(lái)說(shuō)，找到弱學(xué)習(xí)算法要相對(duì)容易一些，然后通過(guò)反復(fù)學(xué)習(xí)得到一系列弱分類器，組合這些弱分類器得到一個(gè)強(qiáng)分類器。

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

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

用下面的GIF看起來(lái)會(huì)更加生動(dòng)

Adaboost基本概念

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

對(duì)于AdaBoost，我們要搞清楚兩點(diǎn)：

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

2、弱分類器權(quán)值$/beta_m$如何確定？

第一個(gè)問(wèn)題，AdaBoost的做法是，提高那些被前一輪弱分類器錯(cuò)分類樣本的權(quán)值，而降低那些被正確分類樣本的權(quán)值。這樣一來(lái)，那些沒(méi)有得到正確分類的數(shù)據(jù)，由于其權(quán)值加大而受到后一輪的弱分類器的更大關(guān)注。于是，分類問(wèn)題被一系列的弱分類器“分而治之”。

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

Adaboost算法流程-分類

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

1.初始化訓(xùn)練樣本的權(quán)值分布:

$$ /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.對(duì)于$m=1,2,…,M$

(a)使用具有權(quán)值分布$D_m$的訓(xùn)練數(shù)據(jù)集進(jìn)行學(xué)習(xí)，得到弱分類器$G_m (x)$

(b)計(jì)算$G_m(x)$在訓(xùn)練數(shù)據(jù)集上的分類誤差率：$$e_m=/sum_{i=1}^Nw_{m,i} I(G_m (x_i )≠y_i )$$
(c)計(jì)算$G_m (x)$在強(qiáng)分類器中所占的權(quán)重：$$/alpha_m=/frac{1}{2}log /frac{1-e_m}{e_m} $$
(d)更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布（這里，(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))$$

公式推導(dǎo)

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

$$ /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} $$

這時(shí)候,$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)))$ 就是每輪迭代的樣本權(quán)重！依賴于前一輪的迭代重分配。
再化簡(jiǎn)一下：

$$ /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} $$

繼續(xù)化簡(jiǎn)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))$
這樣我們就得到了化簡(jiǎn)之后的損失函數(shù)
對(duì)$/alpha_m$求偏導(dǎo)令$/frac{?Loss}{?/alpha_m }=0$得到：
$$/alpha_m=/frac{1}{2}log/frac{1-e_m}{e_m}$$

AdaBoost實(shí)例

《統(tǒng)計(jì)學(xué)習(xí)方法》上面有個(gè)小例子，可以用來(lái)加深印象
有如下的訓(xùn)練樣本，我們需要構(gòu)建強(qiáng)分類器對(duì)其進(jìn)行分類。x是特征，y是標(biāo)簽。

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

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

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

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

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

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

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

Adaboost參數(shù)詳解

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

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)

參數(shù)

1）base_estimator：AdaBoostClassifier和AdaBoostRegressor都有，即我們的弱分類學(xué)習(xí)器或者弱回歸學(xué)習(xí)器。理論上可以選擇任何一個(gè)分類或者回歸學(xué)習(xí)器，不過(guò)需要支持樣本權(quán)重。我們常用的一般是CART決策樹(shù)或者神經(jīng)網(wǎng)絡(luò)MLP。默認(rèn)是決策樹(shù)，即AdaBoostClassifier默認(rèn)使用CART分類樹(shù)DecisionTreeClassifier，而AdaBoostRegressor默認(rèn)使用CART回歸樹(shù)DecisionTreeRegressor。另外有一個(gè)要注意的點(diǎn)是，如果我們選擇的AdaBoostClassifier算法是SAMME.R，則我們的弱分類學(xué)習(xí)器還需要支持概率預(yù)測(cè)，也就是在scikit-learn中弱分類學(xué)習(xí)器對(duì)應(yīng)的預(yù)測(cè)方法除了predict還需要有predict_proba。

2）algorithm：這個(gè)參數(shù)只有AdaBoostClassifier有。主要原因是scikit-learn實(shí)現(xiàn)了兩種Adaboost分類算法，SAMME和SAMME.R。兩者的主要區(qū)別是弱學(xué)習(xí)器權(quán)重的度量，SAMME使用了二元分類Adaboost算法的擴(kuò)展，即用對(duì)樣本集分類效果作為弱學(xué)習(xí)器權(quán)重，而SAMME.R使用了對(duì)樣本集分類的預(yù)測(cè)概率大小來(lái)作為弱學(xué)習(xí)器權(quán)重。由于SAMME.R使用了概率度量的連續(xù)值，迭代一般比SAMME快，因此AdaBoostClassifier的默認(rèn)算法algorithm的值也是SAMME.R。我們一般使用默認(rèn)的SAMME.R就夠了，但是要注意的是使用了SAMME.R， 則弱分類學(xué)習(xí)器參數(shù)base_estimator必須限制使用支持概率預(yù)測(cè)的分類器。SAMME算法則沒(méi)有這個(gè)限制。

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

4)n_estimators： AdaBoostClassifier和AdaBoostRegressor都有，就是我們的弱學(xué)習(xí)器的最大迭代次數(shù)，或者說(shuō)最大的弱學(xué)習(xí)器的個(gè)數(shù)。一般來(lái)說(shuō)n_estimators太小，容易欠擬合，n_estimators太大，又容易過(guò)擬合，一般選擇一個(gè)適中的數(shù)值。默認(rèn)是50。在實(shí)際調(diào)參的過(guò)程中，我們常常將n_estimators和下面介紹的參數(shù)learning_rate一起考慮。

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

SAMME.R算法流程

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

2.1 訓(xùn)練一個(gè)弱分類器，得到樣本的類別預(yù)測(cè)概率分布$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)]$，同時(shí)，要進(jìn)行歸一化使得權(quán)重和為1
3.得到強(qiáng)分類模型：$sign{/sum_{m=1}^{M}f_m(x)}$

DecisionTreeClassifier和DecisionTreeRegressor的弱學(xué)習(xí)器參數(shù)，以CART分類樹(shù)為例，這里就和前文隨機(jī)森林類似了。

方法

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

fit(X,Y):在數(shù)據(jù)集（X,Y）上訓(xùn)練模型

get_parms():獲取模型參數(shù)

predict(X):預(yù)測(cè)數(shù)據(jù)集X的結(jié)果

predict_log_proba(X):預(yù)測(cè)數(shù)據(jù)集X的對(duì)數(shù)概率

predict_proba(X):預(yù)測(cè)數(shù)據(jù)集X的概率值

score(X,Y):輸出數(shù)據(jù)集（X,Y）在模型上的準(zhǔn)確率

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

staged_predict(X):返回每個(gè)基分類器的預(yù)測(cè)數(shù)據(jù)集X的結(jié)果

staged_predict_proba(X):返回每個(gè)基分類器的預(yù)測(cè)數(shù)據(jù)集X的概率結(jié)果

staged_score(X, Y):返回每個(gè)基分類器的預(yù)測(cè)準(zhǔn)確率。

Adaboost總結(jié)

Adaboost優(yōu)點(diǎn)

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

2.簡(jiǎn)單，不用做特征篩選

3.相比較于RF，更不用擔(dān)心過(guò)擬合問(wèn)題

Adaboost缺點(diǎn)

1.從wiki上介紹的來(lái)看，adaboost對(duì)于噪音數(shù)據(jù)和異常數(shù)據(jù)是十分敏感的。Boosting方法本身對(duì)噪聲點(diǎn)異常點(diǎn)很敏感，因此在每次迭代時(shí)候會(huì)給噪聲點(diǎn)較大的權(quán)重，這不是我們系統(tǒng)所期望的。

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

參考：

李航《統(tǒng)計(jì)學(xué)習(xí)方法》第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/...

本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！

審核編輯 黃昊宇