読者です 読者をやめる 読者になる 読者になる

プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

Real AdaBoostについて

 画像処理の話でAdaBoostについて解説も真ん中ぐらいでしようと思っていたけどReal AdaBoost*1をやったので、忘れないうちにメモ。AdaBoostは知っている前提。順序?HP作ったときに綺麗にまとめるから良いんだょ!(たぶん



AdaBoostとの違い

 AdaBoostの弱識別器の出力はTrue or Falseの2つ。(一般に{+1,-1})

 それに対して、Real AdaBoostのRealが示すように、実数値の出力を行う。 なお、詳しく知らなかったときの私が、Real=on timeかと思っていたなんて事は地球の自転が反転してもあり得ません。ええ、ありませんとも。私は嘘は決して断じて何があってもつきません。



弱識別器の出力

 一般的なAdaBoostの弱識別器は、入力xを受け取ったら、xに何らかの処理を施して、{+1,-1}を出力します。(閾値より大か小かというのが最も単純)

 一方、Real AdaBoostの弱識別器の出力は2段階の工程を経ています。まず、1段階目は入力xを1〜Kの連続した整数の番号の内、一定のルールに従いどれかに割り振ります。最も単純な例では、入力xの値(ベクトルならxのどれかの要素)をK段階に量子化するという事があげられるでしょう。なお、Kの値は弱識別器の内部定数なので、弱識別器ごとに異なっていても問題ないと思います。

 次に、入力xが割り振られた番号jを用いて
h(x)=\frac{1}{2}\ln\frac{W^j_+ +\epsilon}{W^j_- +\epsilon}
という関数を計算し、値を出力します。εは0除算を避ける為の定数です。W^j_+,W^j_-は学習によって得られるjに関する弱識別器の内部状態で、詳しくは次の「弱識別器の内部状態と選択」で解説します。W^j_+は学習サンプルの中で番号がjになるポジティブサンプルの重み付き出現確率W^j_-は学習サンプルの中で番号がjになるネガティブサンプルの重み付き出現確率となります。


 この式は、入力xが正解だとものすごく信じることが出来るときは大きな正数を出力し、不正解だとものすごく信じることが出来るときは小さな負数(※絶対値が大きな負数)を出力します。一方、あんまり自信ないとき0近辺の値を出力し、全く分からん時0を出力します。


弱識別器の内部状態と選択

 学習段階では弱識別器の選択だけではなく、弱識別器の内部状態W^j_+,W^j_-を学習サンプルに対し適切な値にする必要があります。


 学習サンプル群Xが与えられたとき、通常のAdaBoostと同じように各サンプルx_i\in Xには正解ラベルy_i=\{+1,-1\}と重みD_t(i)が与えられます。(tは弱識別器選択が何回目かを表す。また、重みの和は1である。初回は全ての重みは同じに設定される。)

 まず、内部状態W^j_+,W^j_-の値を全て0に設定します。次に、各学習サンプルx_iについて、サンプルが番号jに割り振られた時、y_iが+1であればW^j_+に、-1であればW^j_-D_t(i)を加えます。この処理を行うことで、W_+,W_-のグラフが得られます。適切なKの選択や学習サンプルの数を用いなければ、W_+,W_-がスパース(ほとんど値が0)になってしまうので注意が必要です。


 次に、弱識別器の中からどれを選択すると良いかについてです。弱識別器が出力する式hが最も良く結果を出せるときは、W_+,W_-のグラフを重ねたときに下図の様に完全に分離されているときです。

 これを数値化して表す指標として
1-\sum_j\sqrt{W_+^jW_-^j}
という値を利用します。この値が最も大きい弱識別器が最も分離性能が良い識別器です。



 弱識別器の選択が終わったら、AdaBoostと同様にサンプルの重みを更新し、次の弱識別器の選択を行います。
D_{t+1}(i) = D_t(i)\exp\{-y_ih(x_i)\}
 ※和が1になるように、正規化処理もします。


強識別器

 強識別器は非常に単純で、弱識別器を全部足すだけです。
H(x) = \text{sign}\{\sum_t h_t(x) - \lambda\}
 λは閾値で、考えるのが面倒くさいときは0で。



 なお、Wの値が0の所為で、あまりに大きな間違った結果を出力する弱識別器が存在すると、それに引っ張られてしまう。そこで、弱識別器の出力を一定の範囲内に納めるように改善したReal AdaBoostなどもあるらしい。(論文読んでない)