AdaBoost

摘要

• AdaBoost
• 簡介
• 關注在「分類錯誤」的樣本上
• 如何計算模型權重？
• 如何更新樣本權重？
  • 分類正確
  • 分類錯誤
  • 小結
• 總結
• 參考資料

簡介

給定擁有

$N$ 個樣本的一組資料集：

$$D=\{(x_n,y_n)\mathrm{\forall }n=1,\dots ,N\}$$

其中

$$y_n\in \{-1,1\}\mathrm{\forall }n=1,\dots ,N$$

AdaBoost 的核心概念是依序建立

$T$ 個弱學習器 (weak learner)

$h_t(x)$，每個模型會更關注在前個模型分類錯誤的那些樣本上。不僅如此，每個模型都將會被賦予一個模型權重

${\alpha }_t$ ，該權重必須反映兩件事：

• 模型權重越高，代表該模型效果較好。
• 模型權重越低，代表該模型效果較差。

如此一來，最終模型

$H(x)$ 就是蒐集這

$T$ 個弱學習器 (weak learner)的觀點，做出最終分類。也就是說，我們可以表示如下：

重點

$$H(x)=\text{sign}(\sum _{t=1}^T{\alpha }_t{h}_t(x))$$

其中

$$h_t(x)\in \{-1,1\}\mathrm{\forall }t=1,\dots ,T$$

值得注意的是，我們有提到這

$T$ 個模型是「依序」建立的，而且會更關注在前個模型「分類錯誤」的樣本上。換句話說，當前模型

$h_t(x)$ 的建立其實是依賴於前一個模型

$h_{t-1}(x)$，依此類推。

關注在「分類錯誤」的樣本上

至於該怎麼「更關注」在前個模型「分類錯誤」的樣本呢？概念其實很簡單：

首先，我們可以維護一組樣本權重，用來代表第

$t$ 個模型關注每個樣本的程度：

重點

$$W_t=[w_{t1},w_{t2},\dots ,w_{tN}{]}^T$$

其中

$$\begin{gathered} 0<w_{tn}<1\mathrm{\forall }n=1,\dots ,N \\ \sum _{w\in W_t}w=1 \end{gathered}$$

接著，根據當前模型

$h_t(x)$ 的分類結果，更新當前樣本權重

$W_t$ 至

$W_{t+1}$。更新樣本權重的準則有兩個：

• 「分類正確」的樣本必須給予更低的樣本權重。
• 「分類錯誤」的樣本必須給予更高的樣本權重。

如此一來，下個模型

$h_{t+1}(x)$ 就會更關注在那些前個模型分類錯誤的那些樣本上了。

如何計算模型權重？

目前我們已經知道每個模型

$h_t(x)$ 會有一個模型權重

${\alpha }_t$，用來表示當前模型的重要程度。但是我們並不知道怎麼求得？實際上，我們可以透過以下步驟求得。

首先，我們定義一個用來衡量模型分類效果的指標（可理解為加權過後的分類錯誤率）：

重點

$${\epsilon }_t=\sum _{n=1}^N{w}_{tn}\cdot I[h_t(x_n)\ne y_n]$$

其中

$$\begin{gathered} I[h_t(x_n)\ne y_n]=\{\begin{array}{ll}1& \text{if}{h}_t(x_n)\ne y_n\\ 0& \text{if}{h}_t(x_n)=y_n\end{array} \\ {\epsilon }_t\le 0.5 \end{gathered}$$

為什麼

${\epsilon }_t\le 0.5$ 呢？一個很直觀的理解是，若當前模型

$h_t$ 的

${\epsilon }_t\ge 0.5$，只要將當前模型的分類準則顛倒過來（過去分類為

$-1$ 的樣本就改為分類至

$1$，反之亦然），那麼新的

${\epsilon }_t$ 就會小於等於

$0.5$ 了。因此，以最小化加權分類錯誤率為目標的訓練方式，是不可能建立出

${\epsilon }_t\le 0.5$ 的模型的。

而模型權重

${\alpha }_t$ 其實就只是將

${\epsilon }_t$ 經過某個函數轉換而已，定義如下：

重點

$${\alpha }_t=\frac{1}{2}\log (\frac{1-{\epsilon }_t}{{\epsilon }_t})$$

為什麼要這樣定義呢？請觀察以下這張圖，其中橫軸是

${\epsilon }_t$，縱軸則是

${\alpha }_t$：

我們可以觀察到以下兩點：

• 當模型分類能力就跟丟銅板沒兩樣（
  ${\epsilon }_t\approx 0.5$）時，模型權重
  ${\alpha }_t=0$，代表模型非常不值得參考，給予極低的模型權重。
• 當模型每猜必中（
  ${\epsilon }_t\approx 0$）時，模型權重
  ${\alpha }_t\approx \mathrm{\infty }$，代表模型非常值得參考，給予極高的模型權重。

如此一來，我們就得到符合我們預期的模型權重了。

結論

• ${\alpha }_t$ 越高，代表該模型效果越好。
• ${\alpha }_t$ 越低，代表該模型效果越差。

如何更新樣本權重？

回憶一下，更新樣本權重的準則如下：

• 「分類正確」的樣本必須給予更低的樣本權重。
• 「分類錯誤」的樣本必須給予更高的樣本權重。

實際上，給定第

$n$ 個樣本

$(x_n,y_n)$，第

$t$ 個模型

$h_t$ 和第

$t$ 組樣本權重

$W_t$，更新公式可定義如下：

重點

$$w_{(t+1)n}:=\frac{w_{tn}\cdot \exp (-{\alpha }_t{y}_n{h}_t(x_n))}{\sum _{n=1}^N{w}_{(t+1)n}}$$

分母就只是個 normalize 的計算，將

$W_{t+1}$ 的所有元素壓縮在

$0$ 到

$1$ ，並且總和為

$1$（全機率總和為

$1$）。重要的是分子的涵義。

針對

$\exp (-{\alpha }_t{y}_n{h}_t(x_n))$ ，我們從兩個角度了解。

分類正確

給定第

$n$ 個樣本

$(x_n,y_n)$，第

$t$ 個模型

$h_t$，當模型分類正確時，

$\exp (-{\alpha }_t{y}_n{h}_t(x_n))$ 會等於

$\exp (-{\alpha }_t)$。將

${\epsilon }_t$ 畫在橫軸上，

$\exp (-{\alpha }_t)$ 畫在縱軸上，圖形會長得像這樣。

我們可從圖中觀察到兩件事：

• 當模型分類能力就跟丟銅板沒兩樣（
  ${\epsilon }_t\approx 0.5$）時，
  $\exp (-{\alpha }_t)\approx 1$。因為模型分類能力非常不值得參考，就算當前樣本分類正確，更新時也不降低其樣本權重。
• 當模型每猜必中（
  ${\epsilon }_t\approx 0$）時，
  $\exp (-{\alpha }_t)\approx 0$。因為模型分類能力非常值得參考，只要當前樣本分類正確，更新時就大幅降低其樣本權重。

分類錯誤

給定第

$n$ 個樣本

$(x_n,y_n)$，第

$t$ 個模型

$h_t$，當模型分類錯誤時，

$\exp (-{\alpha }_t{y}_n{h}_t(x_n))$ 會等於

$\exp ({\alpha }_t)$。將

${\epsilon }_t$ 畫在橫軸上，

$\exp ({\alpha }_t)$ 畫在縱軸上，圖形會長得像這樣。

我們可從圖中觀察到兩件事：

• 當模型分類能力就跟丟銅板沒兩樣（
  ${\epsilon }_t\approx 0.5$）時，
  $\exp ({\alpha }_t)\approx 1$。因為模型分類能力非常不值得參考，就算當前樣本分類錯誤，更新時也不降低其樣本權重。
• 當模型每猜必中（
  ${\epsilon }_t\approx 0$）時，
  $\exp ({\alpha }_t)\approx \mathrm{\infty }$。因為模型分類能力非常值得參考，只要當前樣本分類錯誤，更新時就大幅提高其樣本權重。

小結

以下是在不同情況下，怎麼更新樣本權重的準則：

模型＼分類	正確	錯誤
不值得參考	小幅度降低	小幅度提高
值得參考	大幅度降低	大幅度提高

總結

以上就是我們 AdaBoost 的所有核心概念。接下來透過 pseudocode 從頭到尾再瞭解 AdaBoost 一遍吧。

N # 樣本個數
T # 分類器個數

# STEP 1: 初始化一組樣本權重
W = [1/N for _ in range(T)]
# STEP 2: 建立 T 個分類器
for t in range(1, T+1):
    # STEP 2-1: 根據最佳化目標（最小化加權分類錯誤率 epsilon_t），訓練第 t 個分類器。
    
    # STEP 2-2: 根據加權分類錯誤率 epsilon_t，計算模型權重 alpha_t。
    
    # STEP 2-3: 根據模型權重 alpha_t 和分類結果，更新每個樣本權重 w_{tn}。
    
# STEP 3: 根據 T 個分類器和模型權重，給出最終分類結果。

參考資料

• AdaBoost, Clearly Explained, StatQuest with Josh Starmer
• Introduction to Adaptive Boosting, Hsuan-Tien Lin
• 機器學習: Ensemble learning之Bagging、Boosting和AdaBoost, Tommy Huang

tags: ML