Adaboost 算法介紹

1. 集成學(xué)習(xí)

集成學(xué)習(xí)（ensemble learning）通過構(gòu)建并結(jié)合多個學(xué)習(xí)器（learner）來完成學(xué)習(xí)任務(wù)，通?？色@得比單一學(xué)習(xí)器更良好的泛化性能（特別是在集成弱學(xué)習(xí)器（weak learner）時）。

目前集成學(xué)習(xí)主要分為2大類：

一類是以bagging、Random Forest等算法為代表的，各個學(xué)習(xí)器之間相互獨立、可同時生成的并行化方法；

一類是以boosting、Adaboost等算法為代表的，個體學(xué)習(xí)器是串行序列化生成的、具有依賴關(guān)系，它試圖不斷增強單個學(xué)習(xí)器的學(xué)習(xí)能力。

2. Adaboost 算法詳解

2.1 Adaboost 步驟概覽

1. 初始化訓(xùn)練樣本的權(quán)值分布，每個訓(xùn)練樣本的權(quán)值應(yīng)該相等（如果一共有$N$個樣本，則每個樣本的權(quán)值為$\frac{1}{N}$)

2. 依次構(gòu)造訓(xùn)練集并訓(xùn)練弱分類器。如果一個樣本被準確分類，那么它的權(quán)值在下一個訓(xùn)練集中就會降低；相反，如果它被分類錯誤，那么它在下個訓(xùn)練集中的權(quán)值就會提高。權(quán)值更新過后的訓(xùn)練集會用于訓(xùn)練下一個分類器。

3. 將訓(xùn)練好的弱分類器集成為一個強分類器，誤差率小的弱分類器會在最終的強分類器里占據(jù)更大的權(quán)重，否則較小。

2.2 Adaboost 算法流程

給定一個樣本數(shù)量為$m$的數(shù)據(jù)集
T = { ( x 1 , y 1 ) , … , ( x m , y m ) } T= \left \{\left(x_{1}, y_{1}\right), \ldots,\left(x_{m}, y_{m}\right) \right \} T={(x1?,y1?),…,(xm?,ym?)}
$y_i$ 屬于標記集合 { ? 1 , + 1 } \{-1,+1\} {?1,+1}。

訓(xùn)練集的在第$k$個弱學(xué)習(xí)器的輸出權(quán)重為
$$D(k)=\left(w_{k1},w_{k2},\dots w_{km}\right);w_{1i}=\frac{1}{m};i=1,2\dots m$$

• 初始化訓(xùn)練樣本的權(quán)值分布，每個訓(xùn)練樣本的權(quán)值相同：

$$D(1)=\left(w_{11},w_{12},\dots w_{1m}\right);w_{1i}=\frac{1}{m};i=1,2\dots m$$

• 進行多輪迭代，產(chǎn)生$T$個弱分類器。
  • 使用權(quán)值分布 $D(t) $的訓(xùn)練集進行訓(xùn)練，得到一個弱分類器

G t ( x ) : χ → { ? 1 , + 1 } G_{t}(x) : \quad \chi \rightarrow\{-1,+1\} Gt?(x):χ→{?1,+1}

• 計算 $G_t(x)$ 在訓(xùn)練數(shù)據(jù)集上的分類誤差率（其實就是被 $G_t(x) $誤分類樣本的權(quán)值之和）:

$$e_t=P\left(G_t\left(x_i\right)\ne y_i\right)=\sum _{i=1}^m{w}_{ti}I\left(G_t\left(x_i\right)\ne y_i\right)$$

• 計算弱分類器 Gt(x) 在最終分類器中的系數(shù)(即所占權(quán)重)
  $${\alpha }_t=\frac{1}{2}\ln \frac{1?e_t}{e_t}$$
• 更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布，用于下一輪（t+1）迭代
  $$D(t+1)=\left(w_{t+1,1},w_{t+1,2},?w_{t+1,i}?,w_{t+1,m}\right)$$

$$w_{t+1,i}=\frac{w_{t,i}}{Z_t}\times \{\begin{array}{ll}{e}^{?{\alpha }_t}& \text{（}if{G}_t\left(x_i\right)=y_i）\\ e^{{\alpha }_t}& \text{（}if{G}_t\left(x_i\right)\ne y_i）\end{array}=\frac{w_{t,i}}{Z_t}\exp \left(?{\alpha }_t{y}_i{G}_t\left(x_i\right)\right)$$

? 其中 $Z_t$是規(guī)范化因子，使得$D(t+1)$成為一個概率分布（和為1）：
$$Z_t=\sum _{j=1}^m{w}_{t,i}\exp \left(?{\alpha }_t{y}_i{G}_t\left(x_i\right)\right)$$

• 集成$T$個弱分類器為1個最終的強分類器：
  $$G(x)=\mathrm{sign}\left(\sum _{t=1}^T{\alpha }_t{G}_t(x)\right)$$

3. 算法面試題

3.1 Adaboost分類模型的學(xué)習(xí)器的權(quán)重系數(shù)$\alpha$怎么計算的？

Adaboost是前向分步加法算法的特例，分類問題的時候認為損失函數(shù)指數(shù)函數(shù)。

1. 當(dāng)基函數(shù)是分類器時，Adaboost的最終分類器是：
   $$f(x)=\sum _{m?1}^M{\alpha }_m{G}_m(x)=f_{m?1}(x)+{\alpha }_m{G}_m(x)$$

2. 目標是使前向分步算法得到的$\alpha$和$G_m(x)$使$f_m(x)$在訓(xùn)練數(shù)據(jù)集T上的指數(shù)損失函數(shù)最小，即
   $$(\alpha ,G_m(x))=argmi{n}_{\alpha ,G}\sum _{i=1}^{N}exp[?y_i(f_{m?1}(x_i)+\alpha G(x_i))]$$
   其中，${\hat{w}}_{mi}=exp[?y_i{f}_{m?1}(x_i)].$為了求上式的最小化，首先計算$G_m^{?}(x)$,對于任意的$\alpha >0$,可以轉(zhuǎn)化為下式：
   $$G_m^{?}=argmi{n}_G\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))$$
   之后求${\alpha }_m^{?}$,將上述式子化簡，得到

$$\sum _{i=1}^N{\hat{w}}_{mi}exp[?y_i\alpha G(x_i)]=\sum _{y_i=G_m(x_i)}{\hat{w}}_{mi}{e}^{?\alpha }+\sum _{y_i\ne G_m(x_i)}{\hat{w}}_{mi}{e}^{\alpha }=(e^{\alpha }?e^{?\alpha })\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G(x_i))+e^{?\alpha }\sum _{i=1}^N{\hat{w}}_{mi}$$

將已經(jīng)求得的$G_m^{?}(x)$帶入上式面，對$\alpha$求導(dǎo)并等于0，得到最優(yōu)的$\alpha$.
$$a_m^{?}=\frac{1}{2}log\frac{1?e_m}{e_m}$$
其中$e_m$是分類誤差率:
$$e_m=\frac{{\sum }_{i=1}^N{\hat{w}}_{mi}I(y_i\ne G_m(x_i))}{{\sum }_{i=1}^N{\hat{w}}_{mi}}=\sum _{i=1}^N{\hat{w}}_{mi}I(y_i\ne G_m(x_i))$$

3.2 Adaboost能否做回歸問題？

Adaboost也能夠應(yīng)用到回歸問題，相應(yīng)的算法如下:
輸入: $T=(x_i,y_1),(x_i,y_1),...,(x_N,y_N)$, 弱學(xué)習(xí)器迭代次數(shù)$M$。
輸出：強分類器$f(x)$.

1. 初始化權(quán)重，
   $$D(1)=w_{11},w_{12},...,w_{1N};w_{1i}=\frac{1}{N};i=1,2,..,N$$

2. 根據(jù)$m=1,2,...,M$;

   • 學(xué)習(xí)得到$G_m(x)$

   • 計算訓(xùn)練集上最大誤差
     $$E_m=max|y_i?G_m(x_i)|,i=1,2,..,N$$

   • 計算樣本的相對平方誤差:
     $$e_{mi}=\frac{(y_i?G_m(x_i){)}^2}{E_m^2}$$

   • 計算回歸誤差率:
     $$e_m=\sum _{i=1}^N{w}_{mi}{e}_{mi}$$

   • 計算學(xué)習(xí)器系數(shù):
     $${\alpha }_m=\frac{e_m}{1?e_m}$$

   • 更新樣本權(quán)重：
     $$w_{m+1,i}=\frac{w_{mi}}{Z_m}{\alpha }_m^{1?e^{m,i}}$$
     其中$Z_m$是規(guī)范化因子，
     $$Z_m=\sum _{i=1}^m{w}_{mi}{\alpha }_m^{1?e^{m,i}}$$

3. 得到強學(xué)習(xí)器：
   $$f(x)=\sum _{m=1}M{G}_m^{?}(x)$$

注: 不管是分類問題還是回歸問題，根據(jù)誤差改變權(quán)重就是Adaboost的本質(zhì)，可以基于這個構(gòu)建相應(yīng)的強學(xué)習(xí)器。

3.3 boosting和bagging之間的區(qū)別,從偏差-方差的角度解釋Adaboost？

集成學(xué)習(xí)提高學(xué)習(xí)精度，降低模型誤差，模型的誤差來自于方差和偏差，其中bagging方式是降低模型方差，一般選擇多個相差較大的模型進行bagging。boosting是主要是通過降低模型的偏差來降低模型的誤差。其中Adaboost每一輪通過誤差來改變數(shù)據(jù)的分布，使偏差減小。

3.4 為什么Adaboost方式能夠提高整體模型的學(xué)習(xí)精度？

根據(jù)前向分布加法模型，Adaboost算法每一次都會降低整體的誤差，雖然單個模型誤差會有波動，但是整體的誤差卻在降低，整體模型復(fù)雜度在提高。

3.5 Adaboost算法如何加入正則項?

$$f_m(x)=f_{m?1}(x)+\eta {\alpha }_m{G}_m(x)$$

3.6 Adaboost使用m個基學(xué)習(xí)器和加權(quán)平均使用m個學(xué)習(xí)器之間有什么不同？

Adaboost的m個基學(xué)習(xí)器是有順序關(guān)系的，第k個基學(xué)習(xí)器根據(jù)前k-1個學(xué)習(xí)器得到的誤差更新數(shù)據(jù)分布，再進行學(xué)習(xí)，每一次的數(shù)據(jù)分布都不同，是使用同一個學(xué)習(xí)器在不同的數(shù)據(jù)分布上進行學(xué)習(xí)。加權(quán)平均的m個學(xué)習(xí)器是可以并行處理的，在同一個數(shù)據(jù)分布上，學(xué)習(xí)得到m個不同的學(xué)習(xí)器進行加權(quán)。

3.7 Adaboost和GBDT之間的區(qū)別？

相同點：

? Adaboost和GBDT都是通過減低偏差提高模型精度，都是前項分布加法模型的一種，

不同點:

? Adaboost每一個根據(jù)前m-1個模型的誤差更新當(dāng)前數(shù)據(jù)集的權(quán)重，學(xué)習(xí)第m個學(xué)習(xí)器；

? GBDT是根據(jù)前m-1個的學(xué)習(xí)剩下的label的偏差，修改當(dāng)前數(shù)據(jù)的label進行學(xué)習(xí)第m個學(xué)習(xí)器，一般使用梯度的負方向替代偏差進行計算。

3.8 Adaboost的迭代次數(shù)(基學(xué)習(xí)器的個數(shù))如何控制？

一般使用earlystopping進行控制迭代次數(shù)。

3.9 Adaboost算法中基學(xué)習(xí)器是否很重要，應(yīng)該怎么選擇基學(xué)習(xí)器？

sklearn中的adaboost接口給出的是使用決策樹作為基分類器，一般認為決策樹表現(xiàn)良好，其實可以根據(jù)數(shù)據(jù)的分布選擇對應(yīng)的分類器，比如選擇簡單的邏輯回歸，或者對于回歸問題選擇線性回歸。

3.10 MultiBoosting算法將Adaboost作為Bagging的基學(xué)習(xí)器，Iterative Bagging將Bagging作為Adaboost的基學(xué)習(xí)器。比較兩者的優(yōu)缺點？

兩個模型都是降低方差和偏差。主要的不同的是順序不同。MultiBosoting先減低模型的偏差再減低模型的方差，這樣的方式
MultiBoosting由于集合了Bagging，Wagging，AdaBoost，可以有效的降低誤差和方差，特別是誤差。但是訓(xùn)練成本和預(yù)測成本都會顯著增加。
Iterative Bagging相比Bagging會降低誤差，但是方差上升。由于Bagging本身就是一種降低方差的算法，所以Iterative Bagging相當(dāng)于Bagging與單分類器的折中。

3.11 訓(xùn)練過程中，每輪訓(xùn)練一直存在分類錯誤的問題，整個Adaboost卻能快速收斂，為何？

每輪訓(xùn)練結(jié)束后，AdaBoost 會對樣本的權(quán)重進行調(diào)整，調(diào)整的結(jié)果是越到后面被錯誤分類的樣本權(quán)重會越高。而后面的分類器為了達到較低的帶權(quán)分類誤差，會把樣本權(quán)重高的樣本分類正確。這樣造成的結(jié)果是，雖然每個弱分類器可能都有分錯的樣本，然而整個 AdaBoost 卻能保證對每個樣本進行正確分類，從而實現(xiàn)快速收斂。

3.12 Adaboost 的優(yōu)缺點？

? 優(yōu)點：能夠基于泛化性能相當(dāng)弱的的學(xué)習(xí)器構(gòu)建出很強的集成，不容易發(fā)生過擬合。

? 缺點：對異常樣本比較敏感，異常樣本在迭代過程中會獲得較高的權(quán)值，影響最終學(xué)習(xí)器的性能表現(xiàn)。