# AdaBoost
:::warning
:notebook_with_decorative_cover: **摘要**
[toc]
:::
# 簡介
給定擁有 $N$ 個樣本的一組資料集：

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

其中

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

AdaBoost 的核心概念是依序建立 $T$ 個弱學習器 (weak learner) $h_t(x)$，每個模型會更關注在前個模型分類錯誤的那些樣本上。不僅如此，每個模型都將會被賦予一個模型權重 $\alpha_t$ ，該權重必須反映兩件事：
- 模型權重越高，代表該模型效果較好。
- 模型權重越低，代表該模型效果較差。

如此一來，最終模型 $H(x)$ 就是蒐集這 $T$ 個弱學習器 (weak learner)的觀點，做出最終分類。也就是說，我們可以表示如下：

:::success
**重點**

$$
\large
H(x)=\text{sign}\Big(\sum_{t=1}^T \alpha_t h_t(x)\Big)
$$
:::spoiler 其中

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

值得注意的是，我們有提到這 $T$ 個模型是「依序」建立的，而且會更關注在前個模型「分類錯誤」的樣本上。換句話說，當前模型 $h_t(x)$ 的建立其實是依賴於前一個模型 $h_{t-1}(x)$，依此類推。

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

首先，我們可以維護一組樣本權重，用來代表第 $t$ 個模型關注每個樣本的程度：

:::success
**重點**

$$
\large
W_{t}=\big[ w_{t1},~w_{t2},~\dots,~w_{tN} \big]^T
$$
:::spoiler 其中
$$
\large
0<w_{tn}<1~~\forall~~n=1,~\dots,~N \\
~ \\
\sum_{w~\in~W_t}w = 1
$$
:::

接著，根據當前模型 $h_t(x)$ 的分類結果，更新當前樣本權重 $W_t$ 至 $W_{t+1}$。更新樣本權重的準則有兩個：
- 「分類正確」的樣本必須給予更低的樣本權重。
- 「分類錯誤」的樣本必須給予更高的樣本權重。

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

# 如何計算模型權重？
目前我們已經知道每個模型 $h_t(x)$ 會有一個模型權重 $\alpha_t$，用來表示當前模型的重要程度。但是我們並不知道怎麼求得？實際上，我們可以透過以下步驟求得。

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

:::success
**重點**

$$
\large
\varepsilon_t = \sum_{n=1}^{N}w_{tn}\cdot I\big[h_t(x_n) \ne y_n\big]
$$
:::spoiler 其中
$$
\large
I\big[h_t(x_n) \ne y_n\big]=
\begin{cases}
1 &\text{if}~~h_t(x_n) \ne y_n \\
0 &\text{if}~~h_t(x_n) = y_n
\end{cases} \\
~\\
\large
\varepsilon_t \le 0.5
$$
:::

為什麼 $\varepsilon_t \le 0.5$ 呢？一個很直觀的理解是，若當前模型 $h_t$ 的 $\varepsilon_t \ge 0.5$，只要將當前模型的分類準則顛倒過來（過去分類為 $-1$ 的樣本就改為分類至 $1$，反之亦然），那麼新的 $\varepsilon_t$ 就會小於等於 $0.5$ 了。因此，以最小化加權分類錯誤率為目標的訓練方式，是不可能建立出 $\varepsilon_t \le 0.5$ 的模型的。

而模型權重 $\alpha_t$ 其實就只是將 $\varepsilon_t$ 經過某個函數轉換而已，定義如下：

:::success
**重點**

$$
\large
\alpha_t=\frac{1}{2}\log\Big(\frac{1-\varepsilon_t}{\varepsilon_t}\Big)
$$
:::

為什麼要這樣定義呢？請觀察以下這張圖，其中橫軸是 $\varepsilon_t$，縱軸則是 $\alpha_t$：


我們可以觀察到以下兩點：
- 當模型分類能力就跟丟銅板沒兩樣（$\varepsilon_t\approx0.5$）時，模型權重 $\alpha_t=0$，代表模型非常不值得參考，給予極低的模型權重。
- 當模型每猜必中（$\varepsilon_t \approx 0$）時，模型權重 $\alpha_t\approx\infty$，代表模型非常值得參考，給予極高的模型權重。

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

**結論**
- $\alpha_t$ 越高，代表該模型效果越好。
- $\alpha_t$ 越低，代表該模型效果越差。

# 如何更新樣本權重？
回憶一下，更新樣本權重的準則如下：
- 「分類正確」的樣本必須給予更低的樣本權重。
- 「分類錯誤」的樣本必須給予更高的樣本權重。

實際上，給定第 $n$ 個樣本 $(x_n,~y_n)$，第 $t$ 個模型 $h_t$ 和第 $t$ 組樣本權重 $W_t$，更新公式可定義如下：
:::success
**重點**

$$
\large
w_{(t+1)n} := \frac{w_{tn} \cdot \exp \big(-\alpha_t y_n h_t(x_n)\big)}{\sum_{n=1}^N w_{(t+1)n}}\\
$$
:::

分母就只是個 normalize 的計算，將 $W_{t+1}$ 的所有元素壓縮在 $0$ 到 $1$ ，並且總和為 $1$（全機率總和為 $1$）。重要的是分子的涵義。

針對 $\exp \big(-\alpha_t y_n h_t(x_n)\big)$ ，我們從兩個角度了解。

### 分類正確
給定第 $n$ 個樣本 $(x_n,~y_n)$，第 $t$ 個模型 $h_t$，當模型分類正確時，$\exp \big(-\alpha_t y_n h_t(x_n)\big)$ 會等於 $\exp (-\alpha_t)$。將 $\varepsilon_t$ 畫在橫軸上，$\exp(-\alpha_t)$ 畫在縱軸上，圖形會長得像這樣。


我們可從圖中觀察到兩件事：
- 當模型分類能力就跟丟銅板沒兩樣（$\varepsilon_t\approx0.5$）時，$\exp(-\alpha_t) \approx 1$。因為模型分類能力非常不值得參考，就算當前樣本分類正確，更新時也不降低其樣本權重。
- 當模型每猜必中（$\varepsilon_t \approx 0$）時，$\exp(-\alpha_t) \approx 0$。因為模型分類能力非常值得參考，只要當前樣本分類正確，更新時就大幅降低其樣本權重。

### 分類錯誤
給定第 $n$ 個樣本 $(x_n,~y_n)$，第 $t$ 個模型 $h_t$，當模型分類錯誤時，$\exp \big(-\alpha_t y_n h_t(x_n)\big)$ 會等於 $\exp (\alpha_t)$。將 $\varepsilon_t$ 畫在橫軸上，$\exp(\alpha_t)$ 畫在縱軸上，圖形會長得像這樣。


我們可從圖中觀察到兩件事：
- 當模型分類能力就跟丟銅板沒兩樣（$\varepsilon_t\approx0.5$）時，$\exp(\alpha_t) \approx 1$。因為模型分類能力非常不值得參考，就算當前樣本分類錯誤，更新時也不降低其樣本權重。
- 當模型每猜必中（$\varepsilon_t \approx 0$）時，$\exp(\alpha_t) \approx \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](https://www.youtube.com/watch?v=LsK-xG1cLYA)
- [Introduction to Adaptive Boosting, Hsuan-Tien Lin](https://www.csie.ntu.edu.tw/~htlin/course/ml08fall/doc/adaboost.pdf)
- [機器學習: Ensemble learning之Bagging、Boosting和AdaBoost, Tommy Huang](https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-ensemble-learning%E4%B9%8Bbagging-boosting%E5%92%8Cadaboost-af031229ebc3)

###### tags: `ML`