[ML] 機器學習技法：第八講 Adaptive Boosting

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第八講 Adaptive Boosting

Adaptive Boosting (AdaBoost) Algorithm

• ${\mathbf{u}}^{(1)}=[\frac{1}{N},\frac{1}{N},\cdots ,\frac{1}{N}]$
• for $t=1,2,\cdots ,T$，$T$ 自行決定
1. 從 $A(D,{\mathbf{u}}^{(t)})$ 得到 $g_t$ 利用 $A$ 最小化 ${\mathbf{u}}^{(t)}$-weighted 0/1 error
   $$g_t\leftarrow \underset{h\in H}{argmin}(\sum _{n=1}^N{u}_n^{(t)}[y_n\ne h({\mathbf{x}}_n)])$$
2. 更新 ${\mathbf{u}}^{(t)}$ 為 ${\mathbf{u}}^{(t+1)}$，藉由
   $$\begin{array}{rl}(incorrectexamples)[y_n\ne g_t({\mathbf{x}}_n)]& :u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot {⧫}_t\\ (correctexamples)[y_n=g_t({\mathbf{x}}_n)]& :u_n^{(t+1)}\leftarrow u_n^{(t)}/{⧫}_t\\ {⧫}_t=\sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}and{ϵ}_t& =\frac{\sum _{n=1}^N{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]}{\sum _{n=1}^N{u}_n^{(t)}}\end{array}$$ 
3. 計算 ${\alpha }_t=\ln ({⧫}_t)$
• 回傳 $G(\mathbf{x})=sign(\sum _{t=1}^T{\alpha }_t{g}_t(\mathbf{x}))$

首先，先考慮四個 data 的情況
$$D=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),({\mathbf{x}}_3,y_3),({\mathbf{x}}_4,y_4)\}$$ 利用 bootsrap 重新取樣
$$\tilde{D}=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),({\mathbf{x}}_4,y_4)\}$$ 如下圖，$E_{in}$ 可以有兩種表示方法
右邊是常見的，左邊則是加上 weighted，表示次數，$(t)$ 表示第幾輪
所以可將 bagging，視為在每一輪最小化 bootsrap-weighted error 並得到 $g_t$

重新寫下更廣義的 $E_{in}$，且 $u_n$ 可為小數，依其權重給於 1, 0.5, 2 等
$$E_{in}^{\mathbf{u}}(h)=\frac{1}{N}\sum _{n=1}^N{u}_n\cdot err(y_n,h({\mathbf{x}}_n))$$ 將此用在之前學過的演算法，SVM 的上限會改變如左圖，${\xi }_n$ 即是 ${\widehat{err}}_{SVM}$
可參考 [ML] 機器學習技法：第四講 soft-margin SVM
logistic regression 若使用 SGD 取樣機率會被改變如右圖，記得 $u_n$ 其實跟資料個數有關
所以當 $u_n$ 變大，不就等同被抽到的機率增加
可參考 [ML] 機器學習基石：第十一講 Linear Models for Classification

當得到的 $g_t$ 越不一樣時，那麼結合在一起時越好
那麼如何讓更新後的 $g_{t+1}$ 與 $g_t$ 不一樣呢？ $$\begin{array}{rl}{g}_t& \leftarrow \underset{h\in H}{argmin}(\sum _{n=1}^N{u}_n^{(t)}[y_n\ne h({\mathbf{x}}_n)])\\ g_{t+1}& \leftarrow \underset{h\in H}{argmin}(\sum _{n=1}^N{u}_n^{(t+1)}[y_n\ne h({\mathbf{x}}_n)])\end{array}$$ 換句話說，當 $g_t$ 在 $u_n^{(t+1)}$ 表現不好時，不就表示 $g_{t+1}$ 與 $g_t$ 不一樣
也就是說，當錯誤的比例跟隨機挑選沒啥兩樣時，等同 $g_t$ 在這些資料上根本就無任何作用
因是二分法，所以隨機機率為 $\frac{1}{2}$
為何不選擇最大錯誤率呢？也就是 1，因為在二分法中全錯不就是等於全對嗎？加個負號就好
如下算式，何時可為 $\frac{1}{2}$？當 ${◼}_{t+1}={◯}_{t+1}$
$$\begin{array}{rl}\frac{\sum _{n=1}^N{u}_n^{(t+1)}[y_n\ne g_t({\mathbf{x}}_n)]}{\sum _{n=1}^N{u}_n^{(t+1)}}& =\frac{{◼}_{t+1}}{{◼}_{t+1}+{◯}_{t+1}}=\frac{1}{2}\\ \\ {◼}_{t+1}& =\sum _{n=1}^N{u}_n^{(t+1)}[y_n\ne g_t({\mathbf{x}}_n)]\\ {◯}_{t+1}& =\sum _{n=1}^N{u}_n^{(t+1)}[y_n=g_t({\mathbf{x}}_n)]\end{array}$$ 那麼如何讓 ${◼}_{t+1}={◯}_{t+1}$？
$$\begin{array}{rl}{◼}_{t+1}& ={◯}_{t+1}\\ \sum _{n=1}^N{u}_n^{(t+1)}[y_n\ne g_t({\mathbf{x}}_n)]& =\sum _{n=1}^N{u}_n^{(t+1)}[y_n=g_t({\mathbf{x}}_n)]\\ \sum _{n=1}^N\alpha \cdot u_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]& =\sum _{n=1}^N\beta \cdot u_n^{(t)}[y_n=g_t({\mathbf{x}}_n)]\\ \alpha \sum _{n=1}^N{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]& =\beta \sum _{n=1}^N{u}_n^{(t)}[y_n=g_t({\mathbf{x}}_n)]\\ \alpha \cdot {◼}_t& =\beta \cdot {◯}_t\end{array}$$ 若讓 $\beta ={◼}_t$ & $\alpha ={◯}_t$，可達成兩者相同的要求
當然也可以是對錯比例 $\beta =\frac{{◼}_t}{{◼}_t+{◯}_t}$ & $\alpha =\frac{{◯}_t}{{◼}_t+{◯}_t}$
於是
$$\begin{array}{rl}{ϵ}_t& =\beta \\ & =\frac{{◼}_t}{{◼}_t+{◯}_t}\\ & =\frac{\sum _{n=1}^N{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]}{\sum _{n=1}^N{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]+\sum _{n=1}^N{u}_n^{(t)}[y_n=g_t({\mathbf{x}}_n)]}\\ & =\frac{\sum _{n=1}^N{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]}{\sum _{n=1}^N{u}_n^{(t)}}\\ \alpha & =1-\beta =1-{ϵ}_t\\ \\ \alpha \cdot {◼}_t& =\beta \cdot {◯}_t\\ (1-{ϵ}_t)\cdot {◼}_t& ={ϵ}_t\cdot {◯}_t\\ \frac{1-{ϵ}_t}{\sqrt{{ϵ}_t(1-{ϵ}_t)}}\cdot {◼}_t& =\frac{{ϵ}_t}{\sqrt{{ϵ}_t(1-{ϵ}_t)}}\cdot {◯}_t\\ \frac{\sqrt{1-{ϵ}_t}}{\sqrt{{ϵ}_t}}\cdot {◼}_t& =\frac{\sqrt{{ϵ}_t}}{\sqrt{1-{ϵ}_t}}\cdot {◯}_t\\ \sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}\cdot {◼}_t& =\sqrt{\frac{{ϵ}_t}{1-{ϵ}_t}}\cdot {◯}_t\\ \\ {⧫}_t& =\sqrt{\frac{1-{ϵ}_t}{{ϵ}_t}}\\ {⧫}_t\cdot {◼}_t& =\frac{1}{{⧫}_t}\cdot {◯}_t\\ {⧫}_t\sum _{n=1}^N{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]& =\frac{1}{{⧫}_t}\sum _{n=1}^N{u}_n^{(t)}[y_n=g_t({\mathbf{x}}_n)]\\ \sum _{n=1}^N{⧫}_t{u}_n^{(t)}[y_n\ne g_t({\mathbf{x}}_n)]& =\sum _{n=1}^N\frac{1}{{⧫}_t}{u}_n^{(t)}[y_n=g_t({\mathbf{x}}_n)]\\ \sum _{n=1}^N{u}_n^{(t+1)}[y_n\ne g_t({\mathbf{x}}_n)]& =\sum _{n=1}^N{u}_n^{(t+1)}[y_n=g_t({\mathbf{x}}_n)]\\ {◼}_{t+1}& ={◯}_{t+1}\end{array}$$ 故
$$\begin{array}{rl}(incorrectexamples◼)[y_n\ne g_t({\mathbf{x}}_n)]& :u_n^{(t+1)}\leftarrow u_n^{(t)}\cdot {⧫}_t\\ (correctexamples◯)[y_n=g_t({\mathbf{x}}_n)]& :u_n^{(t+1)}\leftarrow u_n^{(t)}/{⧫}_t\end{array}$$ 當 ${ϵ}_t\le \frac{1}{2}$ 時，則 ${⧫}_t\ge 1$ 時
所以理論上 ${⧫}_t$ 應該都會 $\ge 1$，因這才表示比亂猜的好

但該如何決定 ${\mathbf{u}}^1$ 呢？
因為希望原來的無權重的 $E_{in}$ 也要很好，所以令所有 ${\mathbf{u}}_n^1$ 都一樣
但如果令 ${\mathbf{u}}_n^1=1$，因 ${⧫}_t\ge 1$，更新時可能越來越大
故使 ${\mathbf{u}}_n^1=\frac{1}{N}$

得到這些 $g_t$，該如何組成 $G(\mathbf{x})$ 呢？
uniform 不是個好選擇，由於演算法的刻意多樣性，所以 $g_2$ 對原先的 $E_{in}$ 表現會很差
linear or non-linear，兩者皆可
但若可以邊跑邊決定，也許是個更好的方法
${⧫}_t$ 越大的，表示 $g_t$ 表現越好
所以從 ${⧫}_t$ 下手，套入一個 monotonic function
$$\begin{gathered} {\alpha }_t=\ln ({⧫}_t) \\ G(\mathbf{x})=\sum _{t=1}^T=sign(\sum _{t=1}^T{\alpha }_t{g}_t(\mathbf{x})) \end{gathered}$$ 選擇 $\ln ({⧫}_t)$ 的原因

• 在 $g_t$ 很差的情況下，${ϵ}_t=\frac{1}{2}\Rightarrow {⧫}_t=1\Rightarrow {\alpha }_t=0$
• 在 $g_t$ 很好的情況下，${ϵ}_t=0\Rightarrow {⧫}_t=\mathrm{\infty }\Rightarrow {\alpha }_t=\mathrm{\infty }$
• 在 $g_t$ 還行的情況下，${ϵ}_t<\frac{1}{2}\Rightarrow {⧫}_t>1\Rightarrow {\alpha }_t>0$

現實意義

Adaptive Boosting = 弱弱的 base learning algorithm $A$ (學生)
                              + 最佳化 re-weighting factor ${⧫}_t$ (老師)
                              + magic linear aggregation ${\alpha }_t$ (整個班級的結論)

當老師在教小學生如何辨認圖片有無蘋果時，於是收集了十張蘋果照和十張其他水果照
並詢問各位學生的意見

有學生說，蘋果是圓的，但可以看到有些錯誤

所以將做對的縮小，錯誤的放大一點進而強調

此時，有學生說，蘋果也是紅的，但仍有些錯誤

同樣的，所以將做對的縮小，錯誤的放大一點

此時，有學生說，蘋果有的是綠色的，但仍有些錯誤

同樣的，所以將做對的縮小，錯誤的放大一點

最後，有學生說，蘋果有梗，於是得到了蘋果的所有特徵

Theoretical Guarantee of AdaBoost

$$E_{out}(G)\le E_{in}(G)+O\left(\sqrt{\underset{d_{VC}ofallpossibleG}{\underbrace{O(d_{VC}(H)\cdot T\log T)}}\cdot \frac{\log N}{N}}\right)$$ 第一項，當 $T=O(\log N)$ 且 ${ϵ}_t\le ϵ<\frac{1}{2}$，則可以令 $E_{in}=0$
第二項，因 $T=O(\log N)$ 有限，資料量 N 若夠多也可保證做得很小

最佳化原理可參考 [ML] 機器學習技法：第十一講 Gradient Boosted Decision Tree

未整理
Computer Science 511 Theoretical Machine Learning
$E_{i}n$ COS 511: Theoretical Machine Learning
$E_{o}ut$ COS 511: Theoretical Machine Learning
A Short Introduction to Boosting
Adaboost通論上課版
$$\begin{array}{rl}{E}_{in}(G)& =\frac{1}{N}\sum _{n=1}^N[G({\mathbf{x}}_i)\ne y_i]\\ & =\frac{1}{N}\sum _{n=1}^N[sign(\sum _{t=1}^T{\alpha }_t{g}_t({\mathbf{x}}_i))\ne y_i]\\ [f({\mathbf{x}}_i)=\sum _{t=1}^T{\alpha }_t{g}_t({\mathbf{x}}_i)]& =\frac{1}{N}\sum _{n=1}^N[sign(f({\mathbf{x}}_i))\ne y_i]\\ [\because y_{i}f({\mathbf{x}}_i)\le 0\Rightarrow e^{-y_{i}f({\mathbf{x}}_i)}\ge 1]& \le \frac{1}{N}\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{e}^{-y_{i}f({\mathbf{x}}_i)}\\ & =\frac{1}{N}\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{e}^{-y_i\sum _{t=1}^T{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =\frac{1}{N}\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{e}^{\sum _{t=1}^T-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =\frac{1}{N}\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}\prod _{t=1}^T{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}\frac{1}{N}\prod _{t=1}^T{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}\frac{1}{N}{e}^{-y_i{\alpha }_1{g}_1({\mathbf{x}}_i)}\prod _{t=2}^T{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ [\because \frac{1}{N}=u_i^{(1)}and{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}=\{\begin{array}{cc}{⧫}_t& g_t({\mathbf{x}}_i)\ne y_i\\ \frac{1}{{⧫}_t}& g_t({\mathbf{x}}_i)=y_i\end{array}]& =\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{u}_i^{(2)}\prod _{t=2}^T{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{u}_i^{(2)}{e}^{-y_i{\alpha }_2{g}_2({\mathbf{x}}_i)}\prod _{t=3}^T{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{u}_i^{(3)}\prod _{t=3}^T{e}^{-y_i{\alpha }_t{g}_t({\mathbf{x}}_i)}\\ & =⋮\\ & =\sum _{{\mathbf{x}}_i\in [G(\mathbf{x})\ne y_i]}{u}_i^{(T+1)}\\ [\because {⧫}_t\ge 0]& \le \sum _{n=1}^N{u}_i^{(T+1)}\\ [iff{u}_i^{(t)}normalized]& =1\end{array}$$ VC dimension 可參考此篇[ML] 機器學習基石：第七講 The VC Dimension

AdaBoost-Stump

利用 decision stump，共有三個參數 (feature i, threshold $\theta$, direction $s$)

$$h_{s,i,\theta }(\mathbf{x})=s\cdot sign(x_i-\theta )$$

物理上的意義，即是切水平或垂直一刀
計算時間也不長，$O(d\cdot N\log N)$，即是搜尋所有組合，並找到其最佳解
大概做法，對 feature 做排序 ($N$)，再利用二分法 ($\log N$)，每個 feature 都做 ($d$)
而且可用來挑選合適的 feature，畢竟每個 decision stump，其實就只有單個 feature，那麼得到的 $g_t$ 自然是最佳 feature

這也是世界上第一個即時人臉辨識的程式所運用的演算法

程式碼

import numpy as np
import matplotlib.pyplot as plt
 
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles
 
 
# 建立資料，為高斯分佈
X1, y1 = make_gaussian_quantiles(cov=2.,
                                 n_samples=200, n_features=2,
                                 n_classes=2, random_state=1)
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,
                                 n_samples=300, n_features=2,
                                 n_classes=2, random_state=1)
X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))
 
plot_colors = "br"
plot_step = 0.02
class_names = "AB"
 
# 畫分界圖資料
xx1_min, xx1_max = X[:, 0].min() - 1, X[:, 0].max() + 1
xx2_min, xx2_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx1, xx2 = np.meshgrid(np.arange(xx1_min, xx1_max, plot_step),
                     np.arange(xx2_min, xx2_max, plot_step))
 
N = 4
f, axarr = plt.subplots(N//2, 2)
for n in range(N):
    if n==0:
        T = 1
    else:
        T = (n+1) * 10
    # AdaBoosted decision stump
    bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1, min_samples_leaf=1), n_estimators=T)
    # 訓練資料
    bdt.fit(X, y)
    
    # 畫分界圖
    Y = bdt.predict(np.c_[xx1.ravel(), xx2.ravel()])
    Y = Y.reshape(xx1.shape)
    axarr[n//2, n%2].contourf(xx1, xx2, Y, cmap=plt.cm.Paired)
 
    # 畫出訓練資料
    for i, l, c in zip(range(2), class_names, plot_colors):
        idx = np.where(y == i)
        axarr[n//2, n%2].scatter(X[idx, 0], X[idx, 1],
                    c=c, cmap=plt.cm.Paired,
                    label="Class %s" % l)
    # 設定座標軸上下限
    axarr[n//2, n%2].set_xlim(xx1_min, xx1_max)
    axarr[n//2, n%2].set_ylim(xx2_min, xx2_max)
    
    if n==0:
        # 畫出 legend
        axarr[n//2, n%2].legend(loc='upper left')
    # 設定 title
    axarr[n//2, n%2].set_title('T={}'.format(T))
 
# 設定最上面的 title
f.suptitle('AdaBoost-Stump')
# 調整之間的空白高度
plt.subplots_adjust(hspace=0.3)
plt.show()

參考

sklearn.ensemble.AdaBoostClassifier
sklearn.ensemble.AdaBoostRegressor