深入理解機器學習——集成學習（二）：提升法Boosting與Adaboost演算法

Boosting是一族可將弱學習器提升為強學習器的演算法，這族演算法的作業機制類似：先從初始訓練集訓練出一個基學習器，再根據基學習器的表現對訓練樣本分布進行調整，使得先前基學習器做錯的訓練樣本在后續受到更多關注，然后基于調整后的樣本分布來訓練下一個基學習器；如此重復進行，直至基學習器數目達到事先指定的值 T T T，最終將這 T T T個基學習器進行加權結合，

Boosting族演算法最著名的代表是AdaBoost：

Adaboost演算法
輸入：
\qquad 訓練集： D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ? ? , ( x N , y N ) D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)} D=(x1?,y1?),(x2?,y2?),?,(xN?,yN?)
\qquad 基學習演算法： L L L
\qquad 訓練輪數： T T T
輸出：
H ( x ) = sign ( ∑ i = 1 T α i h i ( x ) ) \qquad H(x)=\text{sign}(\sum_{i=1}^T\alpha_ih_i(x)) H(x)=sign(∑i=1T?αi?hi?(x))
演算法：.
（ 1 ） D 1 ( x ) = 1 m D_1(x)=\frac{1}{m} D1?(x)=m1?
（ 2 ） for i = 1 , 2 , ? ? , T i = 1, 2, \cdots, T i=1,2,?,T do
（ 3 ） h i = L ( D , D i ) \quad h_i=L(D, D_i) hi?=L(D,Di?)
（ 4 ） ? i = P x ～ D i ( h i ( x ) ≠ f ( x ) ) \quad \epsilon_i=P_{x\sim D_i}(h_i(x)\neq f(x)) ?i?=Px～Di??(hi?(x)?=f(x))
（ 5 ） \quad if ? i > 0.5 \epsilon_i>0.5 ?i?>0.5 then
（ 6 ） \qquad break
（ 7 ） α i = 1 2 ln ? 1 ? ? i ? i \quad \alpha_i=\frac{1}{2}\ln\frac{1-\epsilon_i}{\epsilon_i} αi?=21?ln?i?1??i??
（ 8 ） D i + 1 ( x ) = D i ( x ) exp ? ( ? α i f ( x ) h i ( x ) ) Z i \quad D_{i+1}(x)=\frac{D_i(x)\exp{(-\alpha_if(x)h_i(x))}}{Z_i} Di+1?(x)=Zi?Di?(x)exp(?αi?f(x)hi?(x))?
（ 9 ） end for

其中， y i ∈ { + 1 , ? 1 } y_i\in\{+1,-1\} yi?∈{+1,?1}， f f f是真實函式， D i D_i Di?是第 i i i輪訓練資料的權重，

Adaboost演算法有多種推導方式，比較容易理解的是基于“加性模型”，即基學習器的線性組合：
H ( x ) = sign ( ∑ i = 1 T α i h i ( x ) ) H(x)=\text{sign}(\sum_{i=1}^T\alpha_ih_i(x)) H(x)=sign(i=1∑T?αi?hi?(x))

來最小化指數損失函式：
l ( H ∣ D ) = E x ～ D [ e ? f ( x ) H ( x ) ] l(H|D)=E_{x\sim D}[e^{-f(x)H(x)}] l(H∣D)=Ex～D?[e?f(x)H(x)]

指數損失函式最小化，則分類錯誤率也將最小化，這說明指數損失函式是分類任務原本0/1損失函式的一致的替代損失函式，由于這個替代函式有更好的數學性質，例如它是連續可微函式，因此我們用它替代0/1損失函式作為優化目標，

在Adaboost演算法中，第一個基分類器 h 1 h_1 h1?是通過直接將基學習演算法用于初始資料分布而得；此后迭代地生成 h i h_i hi?和 α i \alpha_i αi?，當基分類器 h i h_i hi?基于分布 D i D_i Di?產生后，該基分類器的權重 α i \alpha_i αi?應使得 α i h i \alpha_ih_i αi?hi?最小化指數損失函式：
l ( α i h i ∣ D ) = E x ～ D i [ e ? f ( x ) α i h i ( x ) ] = e ? α i ( 1 ? ? i ) + e α i ? i l(\alpha_ih_i|D)=E_{x\sim D_i}[e^{-f(x)\alpha_ih_i(x)}]=e^{-\alpha_i}(1-\epsilon_i)+e^{\alpha_i}\epsilon_i l(αi?hi?∣D)=Ex～Di??[e?f(x)αi?hi?(x)]=e?αi?(1??i?)+eαi??i?

考慮指數損失函式的導數：
? l ( α i h i ∣ D i ) ? α i = ? e ? α i ( 1 ? ? i ) + e α i ? i = 0 \frac{\partial l(\alpha_ih_i|D_i)}{\partial\alpha_i}=-e^{-\alpha_i}(1-\epsilon_i)+e^{\alpha_i}\epsilon_i=0 ?αi??l(αi?hi?∣Di?)?=?e?αi?(1??i?)+eαi??i?=0

可解得：
α i = 1 2 ln ? 1 ? ? i ? i \alpha_i=\frac{1}{2}\ln\frac{1-\epsilon_i}{\epsilon_i} αi?=21?ln?i?1??i??

AdaBoost演算法在獲得 H i ? 1 H_{i-1} Hi?1?之后樣本分布將進行調整，使下一輪的基學習器 h i h_i hi?能糾正 H i ? 1 H_{i-1} Hi?1?的一些錯誤，理想的 h i h_i hi?能糾正 H i ? 1 H_{i-1} Hi?1?的全部錯誤，即最小化：
l ( H i ? 1 + h i ∣ D ) = E x ～ D [ e ? f ( x ) ( H i ? 1 + h i ) ] l(H_{i-1}+h_i|D)=E_{x\sim D}[e^{-f(x)(H_{i-1}+h_i)}] l(Hi?1?+hi?∣D)=Ex～D?[e?f(x)(Hi?1?+hi?)]

Boosting演算法要求基學習器能對特定的資料分布進行學習，這可通過“重賦權法”（實施，即在訓練程序的每一輪中，根據樣本分布為每個訓練樣本重新賦予一個權重，對無法接受帶權樣本的基學習演算法，則可通過“重樣法”來處理，即在每一輪學習中，根據樣本分布對訓練集重新進行樣，再用重樣而得的樣本集對基學習器進行訓練，

一般而言，這兩種做法沒有顯著的優劣差別需注意的是， Boosting演算法在訓練的每一輪都要檢查當前生成的基學習器是否滿足基本條件，例如檢查當前基分類器是否是比隨機猜測好，一旦條件不滿足，則當前基學習器即被拋棄，且學習程序停止，在此種情形下，初始設定的學習輪數 T T T也許還遠未達到，可能導致最終集成中只包含很少的基學習器而性能不佳，若采用“重采樣法”，則可獲得“重啟動”機會以避免訓練程序過早停止，即在拋棄不滿足條件的當前基學習器之后，可根據當前分布重新對訓練樣本進行采樣，再基于新的采樣結果重新訓練出基學習器，從而使得學習程序可以持續到預設的 T T T輪完成，

從偏差方差分解的角度看， Boosting主要關注降低偏差，因此 Boosting能基于泛化性能相當弱的學習器構建出很強的集成，