アンサンブル学習、AdaBoost(アダブースト)の数式を分解してみた

機械学習と統計学は切っても切り離せない関係です。が、統計学って数学の一種なので簡単な事象に対しても小難しい式を使いがちですよね。。

私自身物理学科出身なので学生の時にシュレディンガー方程式やらマックスウェル方程式やらを扱っていましたが、数学を仕事も含めてずっと扱ってきた人に比べると理解力は圧倒的に低いと思います。(そもそも数式は得意な方ではないです。)

上記を感じたのは最近アンサンブル学習の中身をそろそろ知らんとあかんなと思い、AdaBoostについて勉強していたことがきっかけです。

愛読書の機械学習参考書で該当説明を見ていましたが、一読で飲み込めなかったので何度か読み込みネットでも調べてやっと理解できたかな、という感じでした。得意な人から「は、そんなん簡単やろ」って感じなんでしょうが、そんな人ごく一部で私みたいな一般人はなかなか理解にたどり着くのに時間がかかると思います。

この世の中に蔓延る「統計学ブラックボックス現象」をなんとかわかりやすい解説により解消したいなとつくづく思います。

前置きはこれくらいにして、本題のAdaBoostの説明(備忘)をしたいと思います。

アンサンブル学習にはバギングとブースティングがあります。

バギングは下図のようにデータの一部を取ってきて各学習器に突っ込み答えを多数決で決めるといった具合です。この時、データをダブりありで取ってくるのがバギングでダブりなしで取ってくるのがペースティングです。(認識が間違ってたらご指摘ください。)

f:id:doreikaiho:20190210121128p:plain:w400

ランダムフォレストは一般的にこのバギングを用いて決定木を各学習器として使用しています。

それに対して、ブースティングは下図のイメージ。一回一回学習器で学習させるのですが、一個前の学習器で予測した結果を踏まえて、学習データの重みを更新します。更新された学習データを元に誤差が小さくなるように計算されるため、簡単に言うと前回の反省を生かして同じミスをしないようにする学習方法です。さらに、最後の多数決で正解率の高い学習器の発言力を強くし(学習器の重みを大きくする)、最終回答案の正答率を上げます。 f:id:doreikaiho:20190210132926p:plain:w400

例えば図の中で $X_2$ のベクトルから予測される $f(X_2)$ が答えの $y_2$ と違っていた場合次の学習の際に、前回間違ってたからここ気をつけろよって感じで重みを大きくします。そうすることで、誤差関数の最小化をしている学習器は重みが大きくなったX2の予測をケアするので結果的に誤認識しなくなります。 f:id:doreikaiho:20190210135149p:plain

そして、指定回数学習を行い学習器を作成したら多数決をとります。イメージは下図のような感じで正答率の高い人の重みを大きくして発言力強くさせます。 f:id:doreikaiho:20190210143347p:plain

それでは実際何をしているのかなるべくわかりやすく数式で書いていきます。ちなみに、一個の学習器を弱学習器と言い、多数決を取ったチームを強学習器と言います。

学習データを $X_1$ ... $X_n$ と $y_1$ ... $y_n$ とします。 yは1か-1のクラス分け問題で、学習器を $f_j(x)$ と書きます。(学習はm回行いj回目の学習器と表記)

・1回目の弱学習器の学習

1回目は全データへの重みを $1/n$ とします。学習は誤差関数

$E_1=1/n\sum_{i=1}^{n}\bigl[y_i\not=f_1(x_i)\bigr]$

が最小になるように学習させます。

$\bigl[y_i\not=f_1(x_1)\bigr]$ は正解したデータは0が返され、不正解のデータに対しては1が返されると言う意味です。

つまり単純に不正解の数が最小になるようにすると言うことです。(nで割っているのはMAXを1にするため。)

この学習結果を踏まえてデータの重み(過去の間違いを生かす)と弱学習器の重み(正答率高い人の発言力を強める)の更新を行なっていきます。

まずは後者から。以下の式で弱学習器の信頼度を計算します。ここでηは学習率です。早く学習させたい場合ηを大きくします。

$α_1 = η\ln{(1-E_1)/E_1}$

単純に正答率が高ければ1番目の弱学習器の信頼度αは大きくなり正答率が低ければ小さくなると言うことを表しています。

次に2番目の学習器で使うデータの重み付けです。以下の式で重みをつけます。(ここで $w_i ← C_1$ は正則化のための定数ですが、ちょっとLaTeXがうまく書けず。重みの合計が1になるような定数を掛けていると思ってください。 )

$w_i ← C_1w_i\exp(-y_1α_1f_1(x_i))$

識別が間違ってたデータに対しては先ほど定義した $α_1$ のエクスポーネンシャル分重みをつけてやります。識別が合ってたものに対しては逆に軽くしてやります。そうすることで次回の学習で重みをが増したデータの誤識別が誤差関数に与える影響が大きくなってしまうため、注意して識別するようになると言うことです。

・2回目の弱学習器の学習

あとは同様に学習→重みアップデートを繰り返していきます。まずは誤差関数を最小にするように学習器を作成。今度はnで割らずにそれぞれのデータの重みをつけた誤差関数の最小化を図ります。(1回目は全データの重みが $1/n$ だった)

$E_2=\sum_{i=1}^{n}w_i\bigl[y_i\not=f_2(x_i)\bigr]$

そして学習器の重み付とデータの重み付です。

$α_2 = η\ln{(1-E_2)/E_2}$

$w_i ← C_2w_i\exp(-y_2α_2f_2(x_i))$

以上をm回繰り返すと1...m番目の学習器の重みが出そろいます。あとは多数決！

以下の式で計算します。もともとyは1か-1だったので符号関数のsignを使います。(本当は $α_i$ と書きたいのですがまたもやLaTeXがうまくいかずorz)

$F(x) = sign(\sum_{i=1}^{m} αf_i(x))$

前述の通り、重みの大きい弱学習器は $α_i$ の値が大きくなっているため、上式を見れば発言力が大きくなっていることが分かると思います。この式は、重み付きの弱学習器の答えを合計した時に0より大きければ $y_i = 1$ 、0より小さければ $y_i = -1$ となります。この $F(x)$ が強学習器です。