AdaBoost
AdaBoostの概要
AdaBoostは、弱学習器を直列につなげ、前の分類器で誤分類されたデータの重みを大きくして次の分類器を作ることで、最終的に高性能な強学習器を生成するアンサンブル学習のアルゴリズムです。
Adaは英語のAdaptive「適応的」を意味します。
AdaBoostの学習アルゴリズムは次の通りです。
アルゴリズム（AdaBoost）
次のような2値分類のデータセットを考える。
\[
\{(\boldsymbol{x}_i,y_i) \mid \boldsymbol{x}_i\in\mathbb{R}^d,~y_i\in\{1,-1\}\}_{i=1}^N
\]
各データ \(\boldsymbol{x}_i\) の重みを初期化する。
\[
w_i^{(1)}=\frac{1}{N} \quad (i=1,\cdots,N)
\]
以下の操作を \(m=1,2\cdots,M\) で繰り返す。
-
弱学習器 \(f_m(\boldsymbol{x})\) を学習する。
\[
f_m(\boldsymbol{x})=\operatorname*{arg min\;}_{f(\boldsymbol{x})}\sum_{i=1}^Nw_i^{(m)}1(y_i\neq f(\boldsymbol{x}_i))
\]
-
弱学習器 \(f_m(\boldsymbol{x})\) の誤判定率を計算する。
\[
\varepsilon_m=\sum_{i:y_i\neq f_m(\boldsymbol{x}_i)}w_i^{(m)}
\]
-
弱学習器 \(f_m(\boldsymbol{x})\) の信頼度を計算する。
\[
\alpha_m=\frac{1}{2}\log\left(\frac{1-\varepsilon_m}{\varepsilon_m}\right)
\]
-
データの重み係数を更新する。
\[
w_i^{(m+1)}=w_i^{(m)}e^{-\alpha_my_if_m(\boldsymbol{x}_i)} \quad (i=1,\cdots,N)
\]
-
データの重みを正規化する。
\[
w_i^{(m+1)}\gets\frac{w_i^{(m+1)}}{\displaystyle\sum_{j=1}^Nw_j^{(m+1)}} \quad (i=1,\cdots,N)
\]
最終的に次の強学習器を得る。
\[
F(\boldsymbol{x})=\sum_{m=1}^M\alpha_mf_m(\boldsymbol{x})
\]
分類の予測は次のようになる。
\[
\hat{y}_i=\operatorname{sgn}F(\boldsymbol{x}_i) \quad (i=1,\cdots,N)
\]
AdaBoostの理論
AdaBoostの導出を説明します。
\[
F_M(\boldsymbol{x})=\sum_{m=1}^M\alpha_mf_m(\boldsymbol{x}_i)
\]
\[
F_m(\boldsymbol{x})=F_{m-1}(\boldsymbol{x}_i)+\alpha_mf_m(\boldsymbol{x}_i)
\]
指数損失により、次の平均損失を損失関数とする。
\[
\begin{align}
L
&=\frac{1}{N}\sum_{i=1}^Ne^{-y_iF_m(\boldsymbol{x}_i)} \\
&=\frac{1}{N}\sum_{i=1}^Ne^{-y_i\{F_{m-1}+\alpha_mf_m(\boldsymbol{x}_i)\}} \\
&=\frac{1}{N}\sum_{i=1}^Ne^{-y_iF_{m-1}}e^{-y_i\alpha_mf_m(\boldsymbol{x}_i)}
\end{align}
\]
ここで
\[
w_i^{(1)}=\frac{1}{N}, \quad w_i^{(m)}=\frac{1}{N}e^{-y_iF_{m-1}(\boldsymbol{x}_i)}
\]
とすると
\[
L=\sum_{i=1}^Nw_i^{(m)}e^{-y_i\alpha_mf_m(\boldsymbol{x}_i)}
\]
正しく分類できたとき、すなわち \(y_i=f_m(\boldsymbol{x}_i)\) であるとき
\[
y_if_m(\boldsymbol{x}_i)=1
\]
誤って分類されたとき、すなわち \(y_i \neq f_m(\boldsymbol{x}_i)\) であるとき
\[
y_if_m(\boldsymbol{x}_i)=-1
\]
となるので、これらで和を分けると
\[
\begin{align}
L&=\sum_{i=1}^Nw_i^{(m)}e^{-y_i\alpha_mf_m(\boldsymbol{x}_i)} \\
&=\sum_{\substack{1\le i\le N \\ y_i=f_m(\boldsymbol{x}_i)}}w_i^{(m)}e^{-\alpha_m} + \sum_{\substack{1\le i\le N \\ y_i\neq f_m(\boldsymbol{x}_i)}}w_i^{(m)}e^{\alpha_m} \\
&=(1-\varepsilon)e^{-\alpha_m} + \varepsilon e^{\alpha_m} \\
\end{align}
\]
このとき
\[
\begin{align}
&\frac{\partial L}{\partial\alpha_m}=0 \\
\\
&\Longleftrightarrow -(1-\varepsilon)e^{-\alpha_m} + \varepsilon e^{\alpha_m} = 0 \\
\\
&\Longleftrightarrow e^{2\alpha_m} = \frac{1-\varepsilon}{\varepsilon} \\
\\
&\Longleftrightarrow 2\alpha_m = \log\left(\frac{1-\varepsilon}{\varepsilon}\right) \\
\\
&\Longleftrightarrow \alpha_m = \frac{1}{2}\log\left(\frac{1-\varepsilon}{\varepsilon}\right) \\
\end{align}
\]
また、\(w_i^{(m)}=\dfrac{1}{N}e^{-y_iF_{m-1}(\boldsymbol{x}_i)}\) より
\[
\begin{align}
w_i^{(m+1)}
&=\frac{1}{N}e^{-y_iF_{m}(\boldsymbol{x}_i)} \\
&=\frac{1}{N}e^{-y_i\{F_{m-1}(\boldsymbol{x}_i)+\alpha_mf_m(\boldsymbol{x}_i)\}} \\
&=\frac{1}{N}e^{-y_iF_{m-1}(\boldsymbol{x}_i)}e^{-y_i\alpha_mf_m(\boldsymbol{x}_i)} \\
&=w_i^{(m)}e^{-y_i\alpha_mf_m(\boldsymbol{x}_i)}
\end{align}
\]