AdaBoost算法詳解與python實現

2020 年 11 月 3 日
筆記

1. 概述

1.1 集成學習

目前存在各種各樣的機器學習算法，例如SVM、決策樹、感知機等等。但是實際應用中，或者說在打比賽時，成績較好的隊伍幾乎都用了集成學習(ensemble learning)的方法。集成學習的思想，簡單來講，就是「三個臭皮匠頂個諸葛亮」。集成學習通過結合多個學習器(例如同種算法但是參數不同，或者不同算法)，一般會獲得比任意單個學習器都要好的性能，尤其是在這些學習器都是”弱學習器”的時候提升效果會很明顯。

弱學習器指的是性能不太好的學習器，比如一個準確率略微超過50%的二分類器。

下面看看西瓜書對此做的一個簡單理論分析。
考慮一個二分類問題 $y \in \{-1, +1\}$ 、真實函數 $f$ 以及 $M$ 個相互獨立且犯錯概率均為 $\epsilon$ 的個體學習器(或者稱基學習器) $h_i$ 。我們用簡單的投票進行集成學習，即分類結果取半數以上的基學習器的結果:

$H(x) = sign(\sum_{i=1}^M h_i(x)) \tag{1.1.1}$

由Hoeffding不等式知，集成學習後的犯錯(即過半數基學習器犯錯)概率滿足

$P(H(x) \neq f(x)) \leq exp(- \frac 1 2 M (1-2\epsilon)^2) \tag{1.1.2}$

式 $（1.1.2）$ 指出，當犯錯概率獨立的基學習器個數 $M$ 很大時，集成後的犯錯概率接近0，這也很符合直觀想法: 大多數人同時犯錯的概率是比較低的。

就如上面加粗字體強調的，以上推論全部建立在基學習器犯錯相互獨立的情況下，但實際中這些學習器不可能相互獨立，而如何讓基學習器變得「相對獨立一些」，也即增加這些基學習器的多樣性，正是集成學習需要考慮的主要問題。

按照每個基學習器之間是否存在依賴關係可以將集成學習分為兩類：

基學習器之間存在強依賴關係，一系列基學習器需要串行生成，代表算法是Boosting；
基學習器之間不存在強依賴關係，一系列基學習器可並行生成，代表算法是Bagging和隨機森林。

Boosting系列算法里最著名算法主要有AdaBoost和提升樹(Boosting tree)系列算法，本文只介紹最具代表性的AdaBoost。提升樹、Bagging以及隨機森林不在本文介紹範圍內，有時間了再另外介紹。

1.2 Boosting

Boosting指的是一類集成方法，其主要思想就是將弱的基學習器提升(boost)為強學習器。具體步驟如下:

先用每個樣本權重相等的訓練集訓練一個初始的基學習器；
根據上輪得到的學習器對訓練集的預測表現情況調整訓練集中的樣本權重(例如提高被錯分類的樣本的權重使之在下輪訓練中得到更多的關注), 然後據此訓練一個新的基學習器；
重複2直到得到 $M$ 個基學習器，最終的集成結果是 $M$ 個基學習器的組合。

由此看出，Boosting算法是一個串行的過程。

Boosting算法簇中最著名的就是AdaBoost，下文將會詳細介紹。

2. AdaBoost原理

2.1 基本思想

對於1.2節所述的Boosting算法步驟，需要回答兩個問題:

如何調整每一輪的訓練集中的樣本權重？
如何將得到的 $M$ 個學習器組合成最終的學習器？

AdaBoost(Adaptive Boosting, 自適應增強)算法採取的方法是:

提高上一輪被錯誤分類的樣本的權值，降低被正確分類的樣本的權值；
線性加權求和。誤差率小的基學習器擁有較大的權值，誤差率大的基學習器擁有較小的權值。

下面先給出AdaBoost算法具體實現步驟，至於算法解釋（為什麼要這樣做）將在下一大節闡述。

2.2 算法步驟

考慮如下形式的二分類（標準AdaBoost算法只適用於二分類任務）訓練數據集: $\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 其中 $x_i$ 是一個含有 $d$ 個元素的列向量, 即 $x_i\in \mathcal{X} \subseteq \mathbf{R}^d$ ; $y_i$ 是標量, $y\in\{+1,-1\}$ 。

Adaboost算法具體步驟如下:

初始化樣本的權重

$D_1=(w_{11}, w_{12},...w_{1N}), w_{1i}=\frac 1 N, i = 1,2...N \tag{2.2.1}$

對 $m = 1,2,...M$ ,重複以下操作得到 $M$ 個基學習器:
(1) 按照樣本權重分佈 $D_m$ 訓練數據得到第 $m$ 個基學習器: $G_m(x): \mathcal{X} \to \{-1, +1\}$

(2) 計算 $G_m(x)$ 在加權訓練數據集上的分類誤差率:

$e_m = \sum_{i=1}^NP(G_m(x_i) \neq y_i)=\sum_{i=1}^N w_{mi} I(G_m(x_i) \neq y_i) \tag{2.2.2}$

上式中 $I(\cdot)$ 是指示函數，考慮更加周全的AdaBoost算法在這一步還應該判斷是否滿足基本條件(例如生成的基學習器是否比隨機猜測好), 如果不滿足，則當前基學習器被拋棄，學習過程提前終止。

(3) 計算 $G_m(x)$ 的係數(即最終集成使用的的基學習器的權重):

$\alpha_m = \frac 1 2 log \frac {1-e_m} {e_m} \tag{2.2.3}$

(4) 更新訓練樣本的權重，其中 $Z_m$ 是規範化因子，目的是為了使 $D_{m+1}$ 的所有元素和為1。

$D_{m+1}=(w_{m+1,1}, w_{m+1,2},...w_{m+1,N}) \tag{2.2.4}$ $w_{m+1, i} = \frac{w_{mi}} {Z_m} exp(-\alpha_my_iG_m(x_i)) ,i=1,2,...N \tag{2.2.5}$

$Z_m=\sum_{i=1}^N w_{mi} exp(-\alpha_my_iG_m(x_i)) \tag{2.2.6}$

構建最終的分類器線性組合

$f(x) = \sum_{i=1}^M \alpha_m G_m(x) \tag{2.2.7}$ 　　　得到最終的分類器為

$G(x) = sign(f(x))=sign(\sum_{i=1}^M \alpha_m G_m(x)) \tag{2.2.8}$

由式 $(2.2.3)$ 知，當基學習器 $G_m(x)$ 的誤差率 $e_m \le 0.5$ 時， $\alpha_m \ge 0$ ，並且 $\alpha_m$ 隨着 $e_m$ 的減小而增大，即分類誤差率越小的基學習器在最終集成時佔比也越大。即AdaBoost能夠適應各個弱分類器的訓練誤差率，這也是它的名稱中”適應性(Adaptive)”的由來。

由式 $(2.2.5)$ 知，被基學習器 $G_m(x)$ 誤分類的樣本權值得以擴大，而被正確分類的樣本的權值被得以縮小。

需要注意的是式 $(2.2.7)$ 中所有的 $\alpha_m$ 的和並不為1(因為沒有做一個softmax操作)， $f(x)$ 的符號決定了所預測的類，其絕對值代表了分類的確信度。

3. AdaBoost算法解釋

有沒有想過為什麼AdaBoost算法長上面這個樣子，例如為什麼 $\alpha_m$ 要用式 $(2.2.3)$ 那樣計算？本節將探討這個問題。

3.1 前向分步算法

在解釋AdaBoost算法之前，先來看看前向分步算法。就以AdaBoost算法的最終模型表達式為例:

$f(x) = \sum_{i=1}^M \alpha_m G_m(x) \tag{3.1.1}$

可以看到這是一個「加性模型(additive model)」。我們希望這個模型在訓練集上的經驗誤差最小，即

$min \sum_{i=1}^N L(y_i, f(x)) \iff min \sum_{i=1}^N L(y_i, \sum_{i=1}^M \alpha_m G_m(x)) \tag{3.1.2}$

通常這是一個複雜的優化問題。前向分步算法求解這一優化問題的思想就是: 因為最終模型是一個加性模型，如果能從前往後，每一步只學習一個基學習器 $G_m(x)$ 及其權重 $\alpha_m$ , 不斷迭代得到最終的模型，那麼就可以簡化問題複雜度。具體的，當我們經過 $m-1$ 輪迭代得到了最優模型 $f_{m-1}(x)$ 時，因為

$f_m(x)= f_{m-1}(x) + \alpha_mG_m(x) \tag{3.1.3}$ 所以此輪優化目標就為 $min \sum_{i=1}^N L(y_i, f_{m-1}(x) + \alpha_mG_m(x)) \tag{3.1.4}$ 求解上式即可得到第 $m$ 個基分類器 $G_m(x)$ 及其權重 $\alpha_m$ 。
這樣，前向分步算法就通過不斷迭代求得了從 $m=1$ 到 $m=M$ 的所有基分類器及其權重，問題得到了解決。

3.2 AdaBoost算法證明

上一小結介紹的前向分步算法逐一學習基學習器，這一過程也即AdaBoost算法逐一學習基學習器的過程。本節就證明前向分步算法的損失函數是指數損失函數(exponential loss function)時，AdaBoost學習的具體步驟就如2.2節所示。

指數損失函數即 $L(y, f(x)) = exp(-yf(x))$ ，指數損失函數是分類任務原本0/1損失函數的一致(consistent)替代損失函數（損失函數的上界，優化指數損失函數，等價於優化AdaBoost的損失函數）。由於指數損失函數有更好的數學性質，例如處處可微，所以我們用它替代0/1損失作為優化目標。

將指數損失函數代入式 $(3.1.4)$ ，優化目標就為 $\underset{\alpha_m,G_m}{argmin} \sum_{i=1}^N exp[-y_i(f_{m-1}(x) + \alpha_mG_m(x))] \tag{3.2.1}$ 因為 $y_if_{m-1}(x)$ 與優化變量 $\alpha$ 和 $G$ 無關，如果令 $w_{m,i} = exp[-y_i f_{m-1}(x)] \tag{3.2.2}$

這個 $w_{m,i}$ 其實就是2.2節中歸一化之前的權重 $w_{m,i}$

那麼式 $(3.2.1)$ 等價於 $\underset{\alpha_m,G_m}{argmin} \sum_{i=1}^N w_{m,i}exp(-y_i\alpha_mG_m(x)) \tag{3.2.3}$

我們分兩步來求解式 $(3.2.3)$ 所示的優化問題的最優解 $\hat{\alpha}_m$ 和 $\hat{G}_m(x)$ :

對任意的 $\alpha_m > 0$ , 求 $\hat{G}_m(x)$ ： $\hat{G}_m (x) = \underset{G_m}{argmin} \sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)) \tag{3.2.4}$ 上式將指數函數換成指示函數是因為前面說的指數損失函數和0/1損失函數是一致等價的。

式子 $(3.2.4)$ 所示的優化問題其實就是AdaBoost算法的基學習器的學習過程，即2.2節的步驟2(1)，得到的 $\hat{G}_m(x)$ 是使第 $m$ 輪加權訓練數據分類誤差最小的基分類器。

求解 $\hat{\alpha}_m$ ：

將式子 $(3.2.3)$ 中的目標函數展開 $\begin{aligned} \sum_{i=1}^N w_{m,i}exp(-y_i\alpha_mG_m(x)) &= \sum_{y_i=G_m(x_i)} w_{m,i}e^{- \alpha} + \sum_{y_i \neq G_m(x_i)}w_{m,i}e^{\alpha} \\\\ & = (e^{\alpha} - e^{-\alpha}) \sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)) + e^{-\alpha} \sum_{i=1}^N w_{m,i} \end{aligned} \tag{3.2.5}$ 註：為了簡潔，上式子中的 $\hat{G}_m(x)$ 被略去了 $\hat{\cdot}$ ， $\alpha_m$ 被略去了下標 $m$ ，下同
將上式對 $\alpha$ 求導並令導數為0，即 $(e^{\alpha} + e^{-\alpha}) \sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)) - e^{-\alpha} \sum_{i=1}^N w_{m,i} = 0 \tag{3.2.6}$ 解得 $\hat{\alpha}_m = \frac 1 2 log \frac {1-e_m} {e_m} \tag{3.2.7}$ 其中, $e_m$ 是分類誤差率： $e_m = \frac {\sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)} {\sum_{i=1}^N w_{mi}} \tag{3.2.8}$ 如果式子 $(3.2.8)$ 中的 $w_{mi}$ 歸一化成和為1的話那麼式 $(3.2.8)$ 也就和2.2節式 $(2.2.2)$ 一模一樣了，進一步地也有上面的 $\hat{\alpha}_m$ 也就是2.2節的 $\alpha_m$ 。
最後來看看每一輪樣本權值的更新，由 $(3.1.3)$ 和 $(3.2.2)$ 可得 $w_{m+1,i} = w_{m,i} exp[-y_i \alpha_m G_{m}(x)] \tag{3.2.9}$ 如果將上式進行歸一化成和為1的話就和與2.2節中 $(2.2.5)$ 完全相同了。

由此可見，2.2節所述的AdaBoost算法步驟是可以經過嚴密推導得來的。總結一下，本節推導有如下關鍵點:

AdaBoost算法是一個加性模型，將其簡化成前向分步算法求解；
將0/1損失函數用數學性質更好的指數損失函數替代。

代碼如下

對任意的 $\alpha_m > 0$ , 求 $\hat{G}_m(x)$ ： $\hat{G}_m (x) = \underset{G_m}{argmin} \sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)) \tag{3.2.4}$ 上式將指數函數換成指示函數是因為前面說的指數損失函數和0/1損失函數是一致等價的。
式子 $(3.2.4)$ 所示的優化問題其實就是AdaBoost算法的基學習器的學習過程，即2.2節的步驟2(1)，得到的 $\hat{G}_m(x)$ 是使第 $m$ 輪加權訓練數據分類誤差最小的基分類器。