* ブースティング (boosting) / AdaBoost[#k79c57e0]

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

----
''アルゴリズム AdaBoost''
- \(D_t(\mathbf{x}_i)\) を均一に初期化.
- 以下の手続きを \(t=1,2,\ldots,T\) について反復
+ 現在の誤分類率分布 \(D_t(\mathbf{x}_i)\) の重み付けを用いて,弱学習器に分類器 \(C_t(x)\) を生成させる.
+ 誤分類率分布 \(D_t(\mathbf{x}_i)\) で重み付けした,データ集合 \(\{\mathbf{x}_i\}\) に対する誤分類率を \(\epsilon_t\) とする.
\(\beta_t=\epsilon_t/(1-\epsilon_t)\)
+誤分類分布を更新:事例 \(\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判別分析などの安定的な高バイアスなものでは性能は向上しない.
- 回帰問題へ適用する拡張もある.

> -- しましま

**関連項目 [#ldfdb6dd]

-[[boosting]]
#br
-[[AdaBoost]]
#br
-[[アンサンブル学習]]
-[[バギング]]
-[[arcing]]
-[[TrAdaBoost]]
-[[識別]]
-[[情報幾何]]
#br
-[[検索:ブースティング boosting]]

** リンク集 [#tccd188d]

-[[Boosting>http://www.cs.princeton.edu/~schapire/boost.html]]:Shapireによるチュートリアル
-[[boosting.org>http://www.boosting.org/]]:チュートリアル,論文集,ソフトウェア
#br
-[[Wikipedia:Boosting]]
-[[Wikipedia.jp:ブースティング]]

*** Freeware [#m9a6f503]

-[[mloss:Adaboost]], [[mloss:Boosting]]
-[[BoosTexter>http://www.cs.princeton.edu/~schapire/boostexter.html]]:Shapire自身による実装
-[[gboost>http://www.kyb.mpg.de/bs/people/nowozin/gboost/]]:Graph Boosting Toolbox (matlab)
-[[mboost>http://CRAN.R-project.org/package=mboost]]:model-based boosting (R)
-[[RAdaBoost>http://www.ism.ac.jp/~kawakita/R_jp.html]]:[[R]]でのAdaBoostの実装
-[[JBoost>http://jboost.sourceforge.net/]]:AdaBoostなどをjavaで実装

** 関連文献 [#r27fae9b]

-基本文献~
Y.Freund and R.E.Schapire, "Experiments with a New Boosting Algorithm",Proc. of The 13th Int'l Conf. on Machine Learning, pp.148-156 (1996)~
[[GoogleScholarAll:Experiments with a New Boosting Algorithm]]
-boostingの日本語解説
フロインド Y., シャピリ R., 阿部 直樹, "ブースティング入門", 人工知能学会誌, vol.14, no.5, pp.771-780 (1999)~
[[GoogleScholarAll:ブースティング入門]]
-ブースティングの基本から始まるが,後半は濃くなってゆく~
金森 敬文, 畑埜 晃平, 渡辺 治, 小川 英光 "ブースティング - 学習アルゴリズムの設計技法" 森北出版 (2006)~
Amazon.co.jpへのリンク:&amazon(4627813317);
-[[Book/Data Mining - Practical Machine Learning Tools and Techniques]] Boosting
-[[Book/Pattern Recognition and Machine Learning]] 14.3章
-[[Book/Data Mining - Concepts and Techniques]] 6.14.2節
-[[Book/Pattern Classification]] 9.5.2節
-[[Book/The Elements of Statistical Learning]] 10章
-[[Book/データマイニングの基礎]] 3.1.3節
-[[Book/パターン認識と学習の統計学(統計科学のフロンティア6)]] III部 5節
-[[Book/パターン認識(Rで学ぶデータサイエンス5)]] 14.5章

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS