ブースティング (boosting) / AdaBoost

バギングとならぶ代表的なアンサンブル学習の手法で,クラス分類問題を扱う. 弱学習器は,各事例を重み付けして学習できるものでなくてはならない.


アルゴリズム AdaBoost

  • \(D_t(\mathbf{x}_i)\) を均一に初期化.
  • 以下の手続きを \(t=1,2,\ldots,T\) について反復
  1. 現在の誤分類率分布 \(D_t(\mathbf{x}_i)\) の重み付けを用いて,弱学習器に分類器 \(C_t(x)\) を生成させる.
  2. 誤分類率分布 \(D_t(\mathbf{x}_i)\) で重み付けした,データ集合 \(\{\mathbf{x}_i\}\) に対する誤分類率を \(\epsilon_t\) とする. \(\beta_t=\epsilon_t/(1-\epsilon_t)\)
  3. 誤分類分布を更新:事例 \(\mathbf{x}_i\in\{\mathbf{x}_i\}\) を\(C_t\)が誤分類したならば,\(D_{t+1}(\mathbf{x}_i)=\beta_t D_t(\mathbf{x}_i)\),そうでなければ,\(D_{t+1}(\mathbf{x}_i)=D_t(\mathbf{x}_i)\). 最後に \(D_{t+1}(\mathbf{x}_i)\) を正規化.
  • 最終分類器は \(C_1,\ldots,C_T\) がそれぞれ,\(\log\frac{1}{\beta_t}\)で重み付けした投票で行う.

  • 誤分類率に応じて(adaptive)重みを変えるブースティングなので,AdaBoostという.
  • 上記のものは厳密には AdaBoost.M1 で,他にも幾つかのバリエーションがある.
  • \(\gamma_t=\frac{1}{2}-\epsilon_t\) とすると,最終分類器の誤分類率の上界は \[\prod_t^T \sqrt{1-4\gamma_t^2}\le\exp[-2\sum_t^T\gamma_t^2]\] このように上界は指数関数型なので,ブースティングは指数損失関数を最小化している手法とみなせる.
  • 他のアンサンブル学習と同様に,弱学習器Fisher判別分析などの安定的な高バイアスなものでは性能は向上しない.
  • 回帰問題へ適用する拡張もある.

-- しましま

関連項目

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:26 (2488d)