機器學習筆記:集成學習一種,AdaBoost 演算法
建議閱讀前文:
機器學習筆記:基本術語集成學習是如下過程:建構一組個體學習器,用某種策略將它們結合,來完成學習任務。
同質集成中的個體學習器都為同種類型,稱為基學習器;包含不同類型的,是異質集成,其中的個體學習器稱為組件學習器。
我們期待,通過集成學習,獲得較單一學習器顯著優越的泛化性能。
集成學習(多分類器系統、委員會學習):
ensemble learning / multi-classifier system / committee-based learning
個體學習器:individual learner
同質:homogeneous
基學習器:base learning algorithm
異質:heterogenous
組件學習器:component learner
要獲得好的集成,個體學習器應同時具有準確性和多樣性,好而不同。
Boosting 是一族可將弱學習器提升為強學習器的演算法,其工作機制類似:
先從初始訓練集訓練出一個基學習器,再根據基學習器的表現對訓練樣本分布進行調整,然後基於調整後的的樣本分布來訓練下一個基學習器;如此重複直到學習器數目達到事先指定值 ,最終將這 個基學習器進行加權結合。
Boosting 族演算法最著名的代表是 AdaBoost,我們這樣在此演算法下描述一個二分類任務:
輸入:
- 訓練集
- 基學習演算法
- 訓練輪數
過程:
- 將樣本分布初始化,設定為 ,輪數初始化
- 更新輪數,
- 基於分布 從數據集 中訓練分類器 ,即
- 測量 的誤差 ,即 ,其中 是真實函數, ,且通常應有
- 確定分類器 的權重 ,即
- 更新樣本分布,其中 是規範化因子,用以確保 是一個分布,即 亦即
- 當 時,返回第二步;否則結束。
輸出:
此時 給出了判斷。
AdaBoost(自適應增強):Adaptive Boosting
如下是指數損失函數
當 令指數損失函數最小化時,有一階條件
解得此時
故有
這實際上就是
以上說明 達到了貝葉斯最優錯誤率,當指數損失函數最小時,分類錯誤率也將最小。顯然,指數損失函數是分類任務原本 損失函數的一致的替代損失函數。指數損失函數有更好的數學性質,所以我們用它作為優化目標。
指數損失函數:exp-loss function
一致的替代損失函數:consistent surrogate loss function
下面推導過程中 5 步的權重確定公式:
我們想要,基於 產生的基分類器 及其權重 使指數損失函數最小。即最小化如下函數:
其中 ,最小化的一階條件:
解得此時
這就是 5 步的權重確定公式。
下面推導過程中 6 步的分布更新公式:
我們想要 改善 。即最小化如下函數:
利用 的泰勒展開,化為
於是對理想的基學習器 有
考慮到 是常數,可化為
顯然,當 表示一個分布時
一定可以表示一個分布 。
利用這一關係,得到
鑒於 ,顯然有
此式便說明了這樣的 會在分布 下最小化分類誤差,注意到上面已有
這使得下面成立:
令
就得到了
這就是 6 步的分布更新公式。
在如上過程中,AdaBoost 演算法的有效性得到證明。
2018.12
推薦閱讀: