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

  1. AdaBoost

Boosting族演算法最著名的代表是AdaBoost，其演算法描述如下圖，其中 y_i in {-1, +1 } ， f 是真實函數.

AdaBoost演算法有多種推導方式，比較容易理解的是基於「加性模型」(additive model)，即基學習器的線性組合

H(x) = sum_{t=1}^{T}alpha_th_t(x) ag{1}

來最小化指數損失函數(exponential loss function)，

ell _ { mathrm { exp } } ( H | mathcal { D } ) = mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H ( oldsymbol { x } ) } ight] ag{2}

AdaBoost演算法偽代碼

演算法第1步首先初始化樣本的權值分佈，後面循環迭代 T 次，第3步基於分佈 mathcal{D_t} 從數據 D 中訓練出分類器，第4步估計分類器 h_t 的誤差 varepsilon_t ，第6步計算分類器 h_t 的權重 alpha_t ，第7步更新樣本分佈，其中 Z_t 是規範化因子，以確保 mathcal{D_{t+1}} 是一個分佈。

2. AdaBoost推導過程

我們基於加性模型迭代式優化指數損失函數的角度來推導AdaBoost。

2.1 為什麼選擇指數損失函數？

欲找到一個 H(x) 使得指數損失函數 ell _ { mathrm { exp } } ( H | mathcal { D } ) 最小化，考慮指數損失函數對 H(x) 的導數：

frac { partial ell _ { exp } ( H | mathcal { D } ) } { partial H ( oldsymbol { x } ) } = mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H ( oldsymbol { x } ) }(- f ( oldsymbol { x } )) ight] \ = - e ^ { - H ( oldsymbol { x } ) } P ( f ( oldsymbol { x } ) = 1 | oldsymbol { x } ) + e ^ { H ( oldsymbol { x } ) } P ( f ( oldsymbol { x } ) = - 1 | oldsymbol { x } ) ag{3}

令式(3)等於0，得到

H ( x ) = frac { 1 } { 2 } ln frac { P ( f ( x ) = 1 | x ) } { P ( f ( x ) = - 1 | x ) } ag{4}

因此有

operatorname { sign } ( H ( x ) ) = operatorname { sign } left( frac { 1 } { 2 } ln frac { P ( f ( x ) = 1 | x ) } { P ( f ( x ) = - 1 | x ) } ight) \ = left{ egin{array} { l l } { 1 , } & { P ( f ( x ) = 1 | x ) > P ( f ( x ) = - 1 | x ) } \ { - 1 , } & { P ( f ( x ) = 1 | x ) < P ( f ( x ) = - 1 | x ) } end{array} ight. \ = underset { y in { - 1,1 } } { arg max } P ( f ( x ) = y | oldsymbol { x } ) ag{5}

這意味著 operatorname { sign } ( H ( x ) ) 達到了貝葉斯最優錯誤率；換言之，若指數損失函數最小化，則分類錯誤率也將最小化。而且它是連續可微的，所以我們選擇指數損失函數作為優化目標。

2.2 基分類器的權重 alpha_t 是怎麼更新的？

在AdaBoost演算法中，第一個基分類器 h_1 是通過直接將基學習演算法用於初始數據分佈而得；此後迭代地生成 h_t 和 alpha_t ，當基分類器 h_t 基於分佈 mathcal{D_t} 產生後，該基分類器的權重 alpha_t 應使得 alpha_th_t 最小化指數損失函數。

ell _ { exp } left( alpha _ { t } h _ { t } | mathcal { D } _ { t } ight) = mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } left[ e ^ { - f ( oldsymbol { x } ) alpha _ { t } h _ { t } ( oldsymbol { x } ) } ight] \ = mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } left[ e ^ { - alpha _ { t } } mathbb { I } left( f ( oldsymbol { x } ) = h _ { t } ( oldsymbol { x } ) ight) + e ^ { alpha _ { t } } mathbb { I } left( f ( oldsymbol { x } ) eq h _ { t } ( oldsymbol { x } ) ight) ight] \ = e ^ { - alpha _ { t } } P _ { oldsymbol { x } sim mathcal { D } _ { t } } left( f ( oldsymbol { x } ) = h _ { t } ( oldsymbol { x } ) ight) + e ^ { alpha _ { t } } P _ { oldsymbol { x } sim mathcal { D } _ { t } } left( f ( oldsymbol { x } ) eq h _ { t } ( oldsymbol { x } ) ight) \ = e ^ { - alpha _ { t } } left( 1 - epsilon _ { t } ight) + e ^ { alpha _ { t } } epsilon _ { t } ag{6}

其中 epsilon _ { t } = P _ { oldsymbol { x } sim mathcal { D } _ { t } } left( h _ { t } ( oldsymbol { x } ) eq f ( oldsymbol { x } ) ight) .

考慮指數損失函數對 alpha_t 的導數，

frac { partial ell _ { exp } left( alpha _ { t } h _ { t } | mathcal { D } _ { t } ight) } { partial alpha _ { t } } = - e ^ { - alpha _ { t } } left( 1 - epsilon _ { t } ight) + e ^ { alpha _ { t } } epsilon _ { t } ag{7}

令式(7)為0，得到

alpha _ { t } = frac { 1 } { 2 } ln left( frac { 1 - epsilon _ { t } } { epsilon _ { t } } ight) ag{8}

這就是AdaBoost演算法中第6行的分類器權重更新公式。

2.3 每一輪的樣本分佈怎麼調整？

AdaBoost演算法在獲得 H_{t-1} 之後樣本分佈將進行調整，使下一輪的基學習器 h_t 能糾正 H_{t-1} 的一些錯誤。理想的 h_t 能糾正 H_{t-1} 的全部錯誤，即最小化

egin{aligned} ell _ { exp } left( H _ { t - 1 } + h _ { t } | mathcal { D } ight) & = mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) left( H _ { t - 1 } ( oldsymbol { x } ) + h _ { t } ( oldsymbol { x } ) ight) } ight] \ & = mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } e ^ { - f ( oldsymbol { x } ) h _ { t } ( oldsymbol { x } ) } ight] end{aligned} ag{9}

注意到 f ^ { 2 } ( oldsymbol { x } ) = h _ { t } ^ { 2 } ( oldsymbol { x } ) = 1 ，式(9)可使用 e ^ { - f ( oldsymbol { x } ) h _ { t } ( oldsymbol { x } ) } 的泰勒展式近似為

ell _ { exp } left( H _ { t - 1 } + h _ { t } | mathcal { D } ight) simeq mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - mathbf { 1 } } ( oldsymbol { x } ) } left( 1 - f ( oldsymbol { x } ) h _ { t } ( oldsymbol { x } ) + frac { f ^ { 2 } ( oldsymbol { x } ) h _ { t } ^ { 2 } ( oldsymbol { x } ) } { 2 } ight) ight] \ = mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } left( 1 - f ( oldsymbol { x } ) h _ { t } ( oldsymbol { x } ) + frac { 1 } { 2 } ight) ight] ag{10}

於是，理想的基學習器

h _ { t } ( oldsymbol { x } ) = underset { h } { arg min } ell _ { exp } left( H _ { t - 1 } + h | mathcal { D } ight) \ = underset { h } { arg min } mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } left( 1 - f ( oldsymbol { x } ) h ( oldsymbol { x } ) + frac { 1 } { 2 } ight) ight] \ = underset { h } { arg max } mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } f ( oldsymbol { x } ) h ( oldsymbol { x } ) ight] \ = underset { h } { arg max } mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ frac { e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } } { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } ight] } f ( oldsymbol { x } ) h ( oldsymbol { x } ) ight] ag{11}

其中 mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } ight] 是一個常數。

令 mathcal{D_t} 表示一個分佈，

mathcal { D } _ { t } ( oldsymbol { x } ) = frac { mathcal { D } ( oldsymbol { x } ) e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } } { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } ight] } ag{12}

則根據數學期望的定義，這等價於令

h _ { t } ( oldsymbol { x } ) = underset { h } { arg max } mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ frac { e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } } { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } ight] } f ( oldsymbol { x } ) h ( oldsymbol { x } ) ight] \ = underset { h } { arg max } mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } [ f ( oldsymbol { x } ) h ( oldsymbol { x } ) ] ag{13}

由 f ( oldsymbol { x } ) , h ( oldsymbol { x } ) in { - 1 , + 1 } ，有

f ( oldsymbol { x } ) h ( oldsymbol { x } ) = 1 - 2 mathbb { I } ( f ( oldsymbol { x } ) eq h ( oldsymbol { x } ) ) ag{14}

則理想的基學習器

h _ { t } ( oldsymbol { x } ) = underset { h } { arg min } mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } [ mathbb { I } ( f ( oldsymbol { x } ) eq h ( oldsymbol { x } ) ) ] ag{15}

由此可見，理想的 h_t 將在分佈 mathcal{D_t} 下最小化分類誤差。因此，弱分類器將基於分佈 mathcal{D_t} 來訓練，且針對 mathcal{D_t} 的分類誤差應小於0.5。這在一定程度上類似「殘差逼近」的思想。

考慮到 mathcal{D} 和 mathcal{D_{t+1}} 的關係，有

mathcal { D } _ { t + 1 } ( oldsymbol { x } ) = frac { mathcal { D } ( oldsymbol { x } ) e ^ { - f ( oldsymbol { x } ) H _ { t } ( oldsymbol { x } ) } } { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t } ( oldsymbol { x } ) } ight] } \ = frac { mathcal { D } ( oldsymbol { x } ) e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } e ^ { - f ( oldsymbol { x } ) alpha _ { t } h _ { t } ( oldsymbol { x } ) } } { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t } ( oldsymbol { x } ) } ight] } \ = mathcal { D } _ { t } ( oldsymbol { x } ) cdot e ^ { - f ( oldsymbol { x } ) alpha _ { t } h _ { t } ( oldsymbol { x } ) } frac { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } ight] } { mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t } ( oldsymbol { x } ) } ight] } ag{16}

這正是AdaBoost演算法偽代碼第7步的樣本分佈更新公式。

3. Boosting演算法特點

Boosting演算法要求基學習器能對特定的數據分佈進行學習，這可通過「重賦權法」(re-weighting)實施，即在訓練過程的每一輪中，根據樣本分佈為每個訓練樣本重新賦予一個權重。對無法接受帶權樣本的基學習演算法，則可通過「重採樣法」(re-sampling)來處理，即在每一輪學習中，根據樣本分佈對訓練集重新進行採樣，再用重採樣而得的樣本集對基學習器進行訓練。一般而言，這兩種做法沒有顯著的優劣差別。

需注意的是，Boosting演算法在訓練的每一輪都要檢查當前生成的學習器是否滿足基本條件(如AdaBoost中第5行檢查當前基分類器是否要比隨機猜測好)，一旦條件不滿足，則當前基學習器即被拋棄，且學習過程停止。在此種情形下，初始設置的學習輪數 T 也許還遠未達到，可能導致最終集成中只包含很少的基學習器而性能不佳。若採用「重採樣法」，則可獲得「重啟動」機會以避免訓練過程過早停止，即在拋棄不滿足條件的當前基學習器之後，可根據當前分佈重新對訓練樣本進行採樣，再基於新的採樣結果重新訓練出基學習器，從而使得學習過程可以持續到預設的 T 輪完成。

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

下圖是一個Boosting的例子，以決策樹樁(單層決策樹)為基學習器，在西瓜數據集上運行AdaBoost演算法，不同規模的集成及其基學習器所對應的分類邊界如下圖所示。

AdaBoost集成例子，集成(紅色)與基分類器(黑色)的分類邊界

參考：

【1】周志華《機器學習》

【2】

杜博亞：Adaboost、GBDT與XGBoost的區別?

zhuanlan.zhihu.com圖標
推薦閱讀：
相關文章