Adaboost 演算法介紹（附常見面試題）

1. Adaboost簡介

1.1 集成學習（ensemble learning）背景介紹

集成學習（ensemble learning）通過構建並結合多個學習器（learner）來完成學習任務，通常可獲得比單一學習器更良好的泛化性能（特別是在集成弱學習器（weak learner）時）。

目前集成學習主要分為2大類：

一類是以bagging、Random Forest等演算法為代表的，各個學習器之間相互獨立、可同時生成的並行化方法；

一類是以boosting、Adaboost等演算法為代表的，個體學習器是串列序列化生成的、具有依賴關係，它試圖不斷增強單個學習器的學習能力。

1.2 Adaboost背景介紹

Adaboost是Yoav Freund和Robert Schapire在1997年提出的一種集成學習（ensemble learning）演算法。

此前也Schapire也曾提出了一種boosting演算法（Schapire』s Boosting ），但實際應用效果並不好，主要原因是因為Schapire』s Boosting 對於訓練集樣本的選取條件十分精確而又苛刻，以至於很難找出符合條件的訓練集。而Adaboost在選取樣本的時候採用了基於概率分佈（也可解釋為基於權值）來選取樣本的方法，相比Schapire』s Boosting 放寬了對於訓練樣本選取的要求。

2. Adaboost 演算法詳解

2.1 Adaboost 步驟概覽

? ① 初始化訓練樣本的權值分佈，每個訓練樣本的權值應該相等（如果一共有N個樣本，則每個樣本的權值為1/N)

? ② 依次構造訓練集並訓練弱分類器。如果一個樣本被準確分類，那麼它的權值在下一個訓練集中就會降低；相反，如果它被分類錯誤，那麼它在下個訓練集中的權值就會提高。權值更新過後的訓練集會用於訓練下一個分類器。

? ③ 將訓練好的弱分類器集成為一個強分類器，誤差率小的弱分類器會在最終的強分類器裏佔據更大的權重，否則較小。

2.2 Adaboost 演算法流程

給定一個樣本數量為m的數據集T= ${left(x_{1}, y_{1} ight), ldots,left(x_{m}, y_{m} ight) }$ ，yi 屬於標記集合{-1,+1}。

訓練集的在第k個弱學習器的輸出權重為 $D(k)=left(w_{k 1}, w_{k 2}, ldots w_{k m} ight) ; quad w_{1 i}=frac{1}{m} ; i=1,2 ldots m$

① 初始化訓練樣本的權值分佈，每個訓練樣本的權值相同： $D(1)=left(w_{1 1}, w_{1 2}, ldots w_{1 m} ight) ; quad w_{1 i}=frac{1}{m} ; i=1,2 ldots m$

② 進行多輪迭代，產生T個弱分類器。

? for t = 1, ... , T :

? a. 使用權值分佈 D(t) 的訓練集進行訓練，得到一個弱分類器 $G_{t}(x) : quad chi ightarrow{-1,+1}$ ? b. 計算 Gt(x) 在訓練數據集上的分類誤差率（其實就是被 Gt(x) 誤分類樣本的權值之和）: $e_{t}=Pleft(G_{t}left(x_{i} ight) eq y_{i} ight)=sum_{i=1}^{m} w_{t i} Ileft(G_{t}left(x_{i} ight) eq y_{i} ight)$

c. 計算弱分類器 Gt(x) 在最終分類器中的係數(即所佔權重) $alpha_{t}=frac{1}{2} ln frac{1-e_{t}}{e_{t}}$

? d. 更新訓練數據集的權值分佈，用於下一輪（t+1）迭代 $D(t+1)=left(w_{t+1,1} ,w_{t+1,2} ,cdots w_{t+1, i} cdots, w_{t+1, m} ight)$ ?

for i = 1, ... , m： $w_{t+1,i}=frac{w_{t,i}}{Z_{t}} imes left{egin{array}{ll}{e^{-alpha_{t}}} & { ext （{ if } G_{t}left(x_{i} ight)=y_{i}}） \ {e^{alpha_{t}}} & { ext （{ if } G_{t}left(x_{i} ight) eq y_{i}}）end{array} ight. = frac{w_{t,i}}{Z_{t}} exp left(-alpha_{t} y_{i} G_{t}left(x_{i} ight) ight)$