St_Hakky’s blog

Data Science / Human Resources / Web Applicationについて書きます

AdaBoostについて調べたのでまとめる

こんにちは。

今日はAdaBoostについて書きます。Boostingってそもそも何っていうのとか他のBoostingの手法については以下の記事をどうぞ。

st-hakky.hatenablog.com

AdaBoostとは

AdaBoostは"Adaptive Boosting"の略でBoostingのアルゴリズムとしては最初に出てきたものです(1996年に出た)。これは、弱い分類器をより強いものにしていくBoostingのアルゴリズムの1種です。

アルゴリズム

アルゴリズムはこの資料のFig. 1に書かれている通りです。

f:id:St_Hakky:20170728174743j:plain


このアルゴリズムが書かれている資料ではないのですが、こちらの資料がめちゃめちゃ完結でわかりやすかったです。

一つ一つ自分へのメモがてらアルゴリズムの詳細を解説していこうかと思います。


まず最終的なアウトプットとしては以下の式になります。

$$
H(x) = sign (\sum_{t=1}^T \alpha_t h_t (x))
$$


$h_t (x)$ が弱学習器で、$\alpha$ が各弱学習機の重みになります。この重み $\alpha_t$ が良い役割を果たすのですが、それについては後述します。

さて、この式が最終のアウトプットになり、新しいデータセットが来た時に-1か1の値を返すのですが、その過程について見ていきます。

■与えられるデータ

まず初期値として与えられるデータです。

  • $(x_i, y_i)$ : 訓練データ集合。 $y_i$ は-1か1。
  • $D_1(i)$ : 各データ点の重み。重要度。最初は全部均一な重み。

基本的には、この $D_t(i)$ の値を更新して、次にどのサンプルを重要視して学習するかを定め、そのサンプルを学習するようにします。

■ループ( $t=1, ..., T$ )

初期値を与えたら、次にループの中に入ります。

ループの中では、主に次の4つを行います。

  1. 弱学習機の学習を重み $D_t$ に従って行う
  2. もっとも分類結果の重み付きエラーが低いものを選んで、それで $\epsilon_t$ (重み付きの誤差の期待値)を計算
  3. $\alpha_t$ を計算
  4. 重み $D_t$ を各訓練データ一つ一つに対して行う

上の学習をぐるぐる回していき、最終的な予測器を得ます。

AdaBoostがうまくいくポイント

このアルゴリズムより、以下の3点がわかります。

  • より間違いが少ない場合は、 $\alpha_t$ の値が大きくなり、より間違いが多い場合は小さくなる。
  • 間違った学習データに対してより重要度を上げて次の時刻 $t$ で弱学習器を学習をしている
  • 最終的にはより正解度が高いものにより重要度を高くして、正か負かを平均化して計算している

これにより、間違えたものを正解に近づくように学習しており、且つ間違いの度合いによって各弱学習器の重み付けをして最終的にアンサンブルしていることから、なんとなくだけどより精度がよくなりそうな気がする。

ぶっちゃけこの $\alpha_t$の値とエラー率の関係ってみなさん直感的にオッケー!っとなるのかしら、、、私はならなかったので、可視化してみることにしました。

import numpy as np
import matplotlib.pyplot as plt

error_rate = np.linspace(0, 1, 100)
alpha = 1/2 *np.log((1 - error_rate)/ error_rate)

plt.plot(error_rate, alpha)
plt.xlabel("error_rate")
plt.ylabel("alpha")
plt.show()

実装ってことでもないんですが、とりま可視化させました。可視化させた図が以下。

f:id:St_Hakky:20170728192839p:plain

この図からは以下のようなことが読み取れるかなと。

  • エラー率が0付近のところでは、指数的に重みが上昇していることから、エラー率が少ないものは重要視するようにしていることがわかる
  • エラー率が0.5のところで、$\alpha$ の値が0になっていること
  • エラー率が0.5より大きいと、$\alpha$ の値がマイナスになっていること

このことから、 $\alpha$ の値によって、次に学習されるサンプルの重みが以下のようになるため、どうなるかがわかる。

  • $\alpha$ の値が正で大きい:間違えたサンプルがあると、そのサンプルがすごく強調されるので、次はそのサンプルを間違えないように学習する
  • $\alpha$ の値が負で大きい:正解のサンプルに対して、そのサンプルが強調されるので、次はそのサンプルを間違えないように学習する

ここでは理解を優先するため極端な例だけをあげました。

こう考えると、うまくいきそうなのがマジで雰囲気だけだけどわかる(笑)。AdaBoostについてはこんな感じで終わり。