機器學習筆記：集成學習一種，AdaBoost 演算法

建議閱讀前文：

機器學習筆記：基本術語?

zhuanlan.zhihu.com

集成學習是如下過程：建構一組個體學習器，用某種策略將它們結合，來完成學習任務。

同質集成中的個體學習器都為同種類型，稱為基學習器；包含不同類型的，是異質集成，其中的個體學習器稱為組件學習器。

我們期待，通過集成學習，獲得較單一學習器顯著優越的泛化性能。

集成學習（多分類器系統、委員會學習）： ensemble learning / multi-classifier system / committee-based learning 個體學習器：individual learner 同質：homogeneous 基學習器：base learning algorithm 異質：heterogenous 組件學習器：component learner

要獲得好的集成，個體學習器應同時具有準確性和多樣性，好而不同。

Boosting 是一族可將弱學習器提升為強學習器的演算法，其工作機制類似：

先從初始訓練集訓練出一個基學習器，再根據基學習器的表現對訓練樣本分佈進行調整，然後基於調整後的的樣本分佈來訓練下一個基學習器；如此重複直到學習器數目達到事先指定值，最終將這個基學習器進行加權結合。

Boosting 族演算法最著名的代表是 AdaBoost，我們這樣在此演算法下描述一個二分類任務：

輸入：

訓練集 $D = left{ left( oldsymbol { x } _ { 1 } , y _ { 1 } ight) , left( oldsymbol { x } _ { 2 } , y _ { 2 } ight) , cdots , left( oldsymbol { x } _ { m } , y _ { m } ight) ight}, y_iin{ -1,+ 1}$
基學習演算法
訓練輪數

過程：

將樣本分佈初始化，設定為 $mathcal { D } _ { 1 } ( oldsymbol { x } ) = {1 over m}$ ，輪數初始化
更新輪數，
基於分佈 $mathcal { D_t }$ 從數據集中訓練分類器，即 $h_t=mathcal { L }(D,mathcal { D_t })$
測量的誤差，即 $epsilon _ { t } = P _ { oldsymbol { x } sim mathcal { D } _ { t } } left( h _ { t } ( oldsymbol { x } ) eq f ( oldsymbol { x } ) ight)$ ，其中是真實函數，，且通常應有
確定分類器的權重 $alpha _ { t }$ ，即 $alpha _ { t } = frac { 1 } { 2 } ln left( frac { 1 - epsilon _ { t } } { epsilon _ { t } } ight)$
更新樣本分佈，其中是規範化因子，用以確保 $mathcal { D } _ { t+1 }$ 是一個分佈，即 $mathcal { D } _ { t + 1 } ( oldsymbol { x } ) = frac { mathcal { D } _ { t } ( oldsymbol { x } ) } { Z _ { t } } imes left{ egin{array} { l l } { exp left( - alpha _ { t } ight) , } & { ext { if } h _ { t } ( oldsymbol { x } ) = f ( oldsymbol { x } ) } \ { exp left( alpha _ { t } ight) , } & { ext { if } h _ { t } ( oldsymbol { x } ) eq f ( oldsymbol { x } ) } end{array} ight.$ 亦即 $mathcal { D } _ { t + 1 } ( oldsymbol { x } ) =frac { mathcal { D } _ { t } ( oldsymbol { x } ) exp left( - alpha _ { t } f ( oldsymbol { x } ) h _ { t } ( oldsymbol { x } ) ight) } { Z _ { t } }$
當時，返回第二步；否則結束。

輸出：

$H ( oldsymbol { x } ) = sum _ { t = 1 } ^ { T } alpha _ { t } h _ { t } ( oldsymbol { x } )$

此時給出了判斷。

AdaBoost（自適應增強）：Adaptive Boosting

如下是指數損失函數

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

當令指數損失函數最小化時，有一階條件

$egin{aligned} frac { partial ell _ { exp } ( H | mathcal { D } ) } { partial H ( oldsymbol { x } ) } &= - e ^ { - H ( oldsymbol { x } ) } P ( f ( oldsymbol { x } ) = 1 | oldsymbol { x } ) + e ^ { H ( oldsymbol { x } ) } P ( f ( oldsymbol { x } ) = - 1 | oldsymbol { x } )\ &=0 end{aligned}$

解得此時

$H ( oldsymbol { x } ) = frac { 1 } { 2 } ln frac { P ( f ( oldsymbol { x } ) = 1 | oldsymbol { x } ) } { P ( f ( oldsymbol { x } ) = - 1 | oldsymbol { x } ) }$

故有

$egin{aligned} operatorname { sign } ( H ( oldsymbol { x } ) ) &= operatorname { sign } left( frac { 1 } { 2 } ln frac { P ( f (oldsymbol { x } ) = 1 | oldsymbol { x } ) } { P ( f ( oldsymbol { x } ) = - 1 | oldsymbol { x } ) } ight)\ &= left{ egin{array} { l l } { 1 , } & { P ( f ( oldsymbol { x } ) = 1 | oldsymbol { x } ) > P ( f ( oldsymbol { x } ) = - 1 | oldsymbol { x } ) } \ { - 1 , } & { P ( f ( oldsymbol { x } ) = 1 | oldsymbol { x } ) < P ( f ( oldsymbol { x } ) = - 1 | oldsymbol { x } ) } end{array} ight. end{aligned}$

這實際上就是

以上說明達到了貝葉斯最優錯誤率，當指數損失函數最小時，分類錯誤率也將最小。顯然，指數損失函數是分類任務原本損失函數的一致的替代損失函數。指數損失函數有更好的數學性質，所以我們用它作為優化目標。

指數損失函數：exp-loss function 一致的替代損失函數：consistent surrogate loss function

下面推導過程中 5 步的權重確定公式：

我們想要，基於 $mathcal { D } _ { t }$ 產生的基分類器及其權重 $a _ { t }$ 使指數損失函數最小。即最小化如下函數：

$egin{aligned} 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 } end{aligned}$

其中 $epsilon _ { t } = P _ { oldsymbol { x } sim mathcal { D } _ { t } } left( h _ { t } ( oldsymbol { x } ) eq f ( oldsymbol { x } ) ight)$ ，最小化的一階條件：

$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 }=0$

解得此時

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

這就是 5 步的權重確定公式。

下面推導過程中 6 步的分佈更新公式：

我們想要改善 $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}$

利用 $e ^ { - f ( x ) h _ { t } ( x ) }$ 的泰勒展開，化為

$egin{array} { r l } { 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 - 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] } end{array}$

於是對理想的基學習器有

$egin{aligned} 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] end{aligned}$

考慮到 $mathbb { E } _ { oldsymbol { x } sim mathcal { D } } left[ e ^ { - f ( oldsymbol { x } ) H _ { t - 1 } ( oldsymbol { x } ) } ight]$ 是常數，可化為

$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]$

顯然，當表示一個分佈時

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

一定可以表示一個分佈 $mathcal { D }_t$ 。

利用這一關係，得到

$egin{aligned} 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 } ) ] end{aligned}$

鑒於，顯然有

$egin{aligned} h _ { t } ( oldsymbol { x } ) & = underset { h } { arg max } mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } [ f ( oldsymbol { x } ) h ( oldsymbol { x } ) ]\ &=underset { h } { arg max } mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } [ 1 - 2 mathbb { I } ( f ( oldsymbol { x } ) eq h ( oldsymbol { x } ) )]\ &= underset { h } { arg min } mathbb { E } _ { oldsymbol { x } sim mathcal { D } _ { t } } [ mathbb { I } ( f ( oldsymbol { x } ) eq h ( oldsymbol { x } ) ) ] end{aligned}$

此式便說明瞭這樣的會在分佈 $mathcal { D } _ { t }$ 下最小化分類誤差，注意到上面已有

這使得下面成立：

$egin{aligned} 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] } end{aligned}$

令

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

就得到了

$mathcal { D } _ { t + 1 } ( oldsymbol { x } ) =frac { mathcal { D } _ { t } ( oldsymbol { x } ) exp left( - alpha _ { t } f ( oldsymbol { x } ) h _ { t } ( oldsymbol { x } ) ight) } { Z _ { t } }$

這就是 6 步的分佈更新公式。

在如上過程中，AdaBoost 演算法的有效性得到證明。

2018.12