作者簡介：

Treant

人工智慧愛好者社群專欄作者

部落格專欄：

https：//www。

cnblogs。com/en-heng

1.整合學習

整合學習（ensemble learning）透過組合多個基分類器（base classifier）來完成學習任務，頗有點“三個臭皮匠頂個諸葛亮”的意味。基分類器一般採用的是弱可學習（weakly learnable）分類器，透過整合學習，組合成一個強可學習（strongly learnable）分類器。所謂弱可學習，是指學習的正確率僅略優於隨機猜測的多項式學習演算法；強可學習指正確率較高的多項式學習演算法。整合學習的泛化能力一般比單一的基分類器要好，這是因為大部分基分類器都分類錯誤的機率遠低於單一基分類器的。

偏差與方差

“偏差-方差分解”（bias variance decomposition）是用來解釋機器學習演算法的泛化能力的一種重要工具。對於同一個演算法，在不同訓練集上學得結果可能不同。對於訓練集

，由於噪音，樣本

的真實類別為

（在訓練集中的類別為

），則噪聲為

學習演算法的期望預測為

使用樣本數相同的不同訓練集所產生的方法

期望輸入與真實類別的差別稱為bias，則

為便於討論，假定噪聲的期望為0，即

，透過多項式展開，可對演算法的期望泛化誤差進行分解（詳細的推導參看［2］）：

也就是說，誤差可以分解為3個部分：bias、variance、noise。bias度量了演算法本身的擬合能力，刻畫模型的準確性；variance度量了資料擾動所造成的影響，刻畫模型的穩定性。為了取得較好的泛化能力，則需要充分擬合數據（bias小），並受資料擾動的影響小（variance小）。但是，bias與variance往往是不可兼得的：

當訓練不足時，擬合能力不夠強，資料擾動不足以產生較大的影響，此時bias主導了泛化錯誤率；

隨著訓練加深時，擬合能力隨之加強，資料擾動漸漸被學習到，variance主導了泛化錯誤率。

Bagging與Boosting

整合學習需要解決兩個問題：

如何調整輸入訓練資料的機率分佈及權值；

如何訓練與組合基分類器。

從上述問題的角度出發，整合學習分為兩類流派：Bagging與Boosting。Bagging（Bootstrap Aggregating）對訓練資料擦用自助取樣（boostrap sampling），即有放回地取樣資料；每一次的取樣資料集訓練出一個基分類器，經過MM次取樣得到MM個基分類器，然後根據最大表決（majority vote）原則組合基分類器的分類結果。

Boosting的思路則是採用重賦權（re-weighting）法迭代地訓練基分類器，即對每一輪的訓練資料樣本賦予一個權重，並且每一輪樣本的權值分佈依賴上一輪的分類結果；基分類器之間採用序列式的線性加權方式進行組合。

從“偏差-方差分解”的角度看，Bagging關注於降低variance，而Boosting則是降低bias；Boosting的基分類器是強相關的，並不能顯著降低variance。Bagging與Boosting有分屬於自己流派的兩大殺器：Random Forests（RF）和Gradient Boosting Decision Tree（GBDT）。本文所要講的AdaBoost屬於Boosting流派。

2.AdaBoost演算法

AdaBoost是由Freund與Schapire ［1］ 提出來解決二分類問題

根據加型模型（additive model），第m輪的分類函式

其中，

為基分類器

的組合係數。AdaBoost採用前向分佈（forward stagewise）這種貪心演算法最小化損失函式（1），求解子模型的

其中，

為

的分類誤差率。第m+1輪的訓練資料集權值分佈

其中，

為規範化因子

則得到最終分類器

是

的單調遞減函式，特別地，當

時，

；當

時，即基分類器不滿足弱可學習的條件（比隨機猜測好），則應該停止迭代。具體演算法流程如下：

在演算法第4步，學習過程有可能停止，導致學習不充分而泛化能力較差。因此，可採用“重取樣”（re-sampling）避免訓練過程過早停止；即拋棄當前不滿足條件的基分類器，基於重新取樣的資料訓練分類器，從而獲得學習“重啟動”機會。

AdaBoost能夠自適應（addaptive）地調整樣本的權值分佈，將分錯的樣本的權重設高、分對的樣本的權重設低；所以被稱為“Adaptive Boosting”。sklearn的AdaBoostClassifier實現了AdaBoost，預設的基分類器是能

fit()

帶權值樣本的DecisionTreeClassifier。

老師木在微博上提出了關於AdaBoost的三個問題：

1，adaboost不易過擬合的神話。

2，adaboost人臉檢測器好用的本質原因，

3，真的要求每個弱分類器準確率不低於50%。

3.參考資料

［1］ Freund， Yoav， and Robert E。 Schapire。 “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting。” Journal of Computer and System Sciences 55。1 （1997）： 119-139。

［2］ 李航，《統計學習方法》。

［3］ 周志華，《機器學習》。

［4］ Pang-Ning Tan， Michael Steinbach， Vipin Kumar， Introduction to Data Mining。

［5］ Ji Zhu， Classification。

［6］ @龍星鏢局，機器學習刀光劍影之 屠龍刀。

［7］ 過擬合， 為什麼說bagging是減少variance，而boosting是減少bias？

往期回顧：

【十大經典資料探勘演算法】C4。5

【十大經典資料探勘演算法】k-means

【十大經典資料探勘演算法】SVM

【十大經典資料探勘演算法】Apriori

【十大經典資料探勘演算法】EM

【十大經典資料探勘演算法】PageRank

【從傳統方法到深度學習】影象分類