【機械学習】Boostingアルゴリズムをつくろう(2)
目次
前回は「概要」と「生成されるモデルの構造」までやりました。
今回は「学習アルゴリズム」です。
学習アルゴリズム
ここからは、前回紹介したモデルを生成する方法を紹介します。
まず、すごく荒い粒度で全体の流れをフローチャートにします。
このうち、「弱仮説を大量に生成する」ステップはどんな弱仮説を使うかによって変化します。
今回はHaar-Likeを使用しますが、Haar-Likeの説明の時に合わせて説明します。
したがって、ここでは以下の3つの処理の詳細を説明します。
最も優秀な弱仮説を選択する
最も優秀な弱仮説とは何かを考えるために、
個々の学習データに新たに出現確率というパラメータを付け加えます。
説明のため、以下の言葉を導入します。
ここでは、出現確率はデータの重要度と思ってください。
SVD : 学習データの集合
D(s) : ∀s∈SVDに対する出現確率(確率分布)
L(s) : ∀s∈SVDに対する正解ラベル
この時、最も優秀な弱仮説Wは以下の通りです。
最も優秀な弱仮説W : argmax(W)( Σ|W(s)==L(s)| D(s) )
つまり、「正解する学習データの出現確率の総和」が最も大きい弱仮説
(以下、「正解する学習データの出現確率の総和」を「正解率」と記載)
よって、生成した全ての弱仮説に対し「正解率」を計算し、
これが最も大きい弱仮説を選択すればよいわけです。
ただしモデルがカスケード型の場合、弱仮説の再現率に閾値を設定します。
カスケード型は階層が深くなるほど再現率が低くなるためです。
(逆に適合率は上がっていく)
例えば、再現率0.8の弱仮説をカスケード型に3段結合した場合、
モデルの再現率は0.83 = 0.512になります。
顔画像を顔でないと判断する確率が50%近くあるモデルになってしまいます。
(とにかく適合率を上げろというモデルであれば、再現率0.512でもOKですが)
選択した弱仮説をモデルに付け加える
モデルに選択した弱仮説を追加します。
ただし、線形結合に追加する場合選択した弱仮説の重み付き平均をとるため、
弱仮説毎の「重み」が必要です。
これは「正解率」-0.5の値を使用します。
学習データを更新
この処理では、学習データの確率分布を更新します。
現在のステップで選択した弱仮説Wに対して、以下のような処理を行います。
- Wが誤った結論を出す学習データの出現確率を上げる
- Wが正しい結論を出す学習データの出現確率を下げる
これによって、次のステップの最も優秀な弱仮説を選択する処理で
今まで選択してきた弱仮説が弱い学習データに対して強い弱仮説を選択するようになります。
出現確率の更新方法は様々あり、有名なものはAda-BoostとかMada-Boostとか名前がついています。
今回は基本のAda-Boostの更新方法を見ていきます。
superior = 「正解率」- 0.5
coef = sqrt( (1 - 2 * superior) / (1 + 2 * superior) )
[Wが誤った結論を出す学習データの場合]
D(s) = D(s) / coef
[Wが正しい結論を出す学習データの場合]
D(s) = D(s) * coef
ただし、Ada-Boostは学習データに存在する外れ値に敏感に反応しすぎる欠点があることに注意してください。
