機械学習におけるブースティングの意味、およびブースティングの代表的な手法の１つである、アダブーストについて詳しく解説します。
アンサンブル学習
「まあまあ使えるアルゴリズム」を１回使うことで生成される学習器を弱学習器と呼びます。弱学習器の例としては、決定木が挙げられます。
また、最終的に得られる「かなり使える分類器」のことを強学習器と呼びます。
弱学習器をもとに、強学習器を作ることをアンサンブル学習と言います。
ブースティングとは
ブースティングのおおまかな流れは以下のようになります。
1. 弱学習器 $f_1(x)$ を作る
2. $f_1(x)$ の結果を考慮して、次の弱学習器 $f_2(x)$ を作る
3. 以下順々に、$f_{t-1}(x)$ の結果を考慮して、次の弱学習器 $f_t(x)$ を作る
4. $f_k$ まで作ったら、最後に $f_1(x)$ から $f_k(x)$ までをまとめて強学習器 $f(x)$ を作る
２値分類問題に対する AdaBoost の概要
訓練データ $(x_i,y_i)$（ただし $i=1,\dots,n$）をもとに、二値分類器 $f(x)$ を作ることを考えます。二値分類の問題なので、$y_i$ は $1$ か $-1$ とします。また、各分類器 $f$ の出力も $1$ か $-1$ とします。
1. 弱学習器 $f_1(x)$ を作る。
まずは、訓練誤差、$E_1=\dfrac{1}{n}\displaystyle\sum_{i=1}^n[y_i\neq f_1(x_i)]$ が最小になるような弱学習器 $f_1(x)$ を作ります。
ただし、$[y_i\neq f_1(x_i)]$ とは、$y_i$ と $f_1(x_i)$ が異なるとき（つまり、誤分類のとき）$1$ で、そうでないときに $0$ を取るものを表すとします。
2. $f_1(x)$ の結果を考慮して、次の弱学習器 $f_2(x)$ を作る
次に、訓練誤差、$E_2=\displaystyle\sum_{i=1}^nw_i^{(2)}[y_i\neq f_2(x_i)]$ が最小になるような弱学習器 $f_2(x)$ を作ります。
$w_i^{(2)}$ は、$f_2$ 作成時の各サンプルの「重要度」を表します（$f_1(x)$ が誤分類したサンプルの重要度が高くなるように計算されます）。重要度が大きいサンプルは、間違えたときのペナルティが大きいので、できるだけ間違えないように重視して $f_2$ が作られます。$w$ の計算方法は後述します。
3. 以下順々に、$f_{t-1}(x)$ の結果を考慮して、次の弱学習器 $f_t(x)$ を作る
同様に、訓練誤差、$E_{t}=\displaystyle\sum_{i=1}^nw_i^{(t)}[y_i\neq f_t(x_i)]$ が最小になるような弱学習器 $f_t(x)$ を作ります。
$w_i^{(t)}$ は、$f_t$ 作成時の各サンプルの「重要度」を表します（$f_{t-1}(x)$ が誤分類したサンプルの重要度が高くなるように計算されます）。
4. 最後に、$f_1(x)$ から $f_k(x)$ までをまとめて強学習器 $f(x)$ を作る
具体的には、$f(x)=\mathrm{sign}\left\{\displaystyle\sum_{t=1}^k\alpha_t f_t(x)\right\}$ とします。$\alpha_t$ は $t$ 番目の学習器にかける重みで、$\mathrm{sign}$ は符号関数（正の入力には $1$ を返して、負の入力には $-1$ を返す関数）です。$\alpha$ の計算方法は後述します。
AdaBoost の重み
各学習器の重み $\alpha_t$ の決め方
$\alpha_t=\dfrac{1}{2}\ln\left(\dfrac{1-E_t}{E_t}\right)$
という値を使います。ただし、$E_t$ は学習器 $f_t$ の誤差です。$f_t$ の誤分類が大きくなればなるほど、$\alpha_t$ が小さくなり、$f_t$ の重要度は小さくなります。
参考：ロジット関数とロジスティック関数
$t$ 回目の学習におけるサンプル $i$ の重み $w_i^{(t)}$ の決め方
$w_i^{(t)}=C_tw_i^{(t-1)}e^{-y_i\alpha_tf_t(x_i)}$
とします。
・ただし、$C_t=\dfrac{1}{\displaystyle\sum_{i=1}^nw_i^{(t-1)}e^{-y_i\alpha_tf_t(x_i)}}$ はただの正規化定数です。
・$f_t$ が $x_i$ を誤分類したときには、そのサンプルの重要度が大きくなるように更新（$C_te$ 倍）し、正しく分類できたときには、そのサンプルの重要度が小さくなるように更新（$C_te^{-1}$ 倍）します。
補足：AdaBoost の重みの導出の概要
$(t-1)$ 番目までの学習が終わった上で
「指数誤差」
$\displaystyle\sum_{i=1}^Ne^{y_i\{\alpha_1f_1(x_i)+\dots +\alpha_tf_t(x_i)\}}$
を最小にするような $\alpha_t,f_t$ を使う！と決めると、以下の２つの式が導出できます。
・$t$ 番目の学習器の学習は、$w_i^{(t)}=C_tw_i^{(t-1)}e^{-y_i\alpha_tf_t(x_i)}$ という重みを使う。
・$t$ 番目の学習器は最終出力の際に $\alpha_t=\dfrac{1}{2}\ln\left(\dfrac{1-E_t}{E_t}\right)$ という重みをつける。
導出はWikipedia: AdaBoostに記載されています。
次回は バギングの意味と、ブースティングとの違い を解説します。
