ブースティングとアダブースト(AdaBoost)について詳しく解説

機械学習におけるブースティングの意味、およびブースティングの代表的な手法の1つである、アダブーストについて詳しく解説します。

アンサンブル学習

機械学習における分類や回帰の問題に対して「まあまあ使えるアルゴリズム」があるときに、それを繰り返し使うことで「かなり使える学習器」を作ることができる場合があります。

「まあまあ使えるアルゴリズム」を1回使うことで生成される学習器を弱学習器と呼びます。弱学習器の例としては、決定木が挙げられます。

また、最終的に得られる「かなり使える分類器」のことを強学習器と呼びます。

弱学習器をもとに、強学習器を作ることをアンサンブル学習と言います。

ブースティングとは

アンサンブル学習の1つの方法としてブースティングが挙げられます。

ブースティングのおおまかな流れは以下のようになります。

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)$ を作る

2値分類問題に対する AdaBoost の概要

ブースティングの基本的な例として、2値分類問題に対する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$ を使う!
と決めると、以下の2つの式が導出できます。

・$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に記載されています。

次回は 名義尺度、順序尺度、間隔尺度、比率尺度 を解説します。

スポンサーリンク

スポンサーリンク

学校では教えてくれない点数アップ5つの作戦
具体例で学ぶ数学の作成者が、数学の勉強法について徹底的にまとめました。

誤植がございましたら @mathwordsnet までご連絡をお願いいたします。
ページ上部へ戻る