ブースティング

機械学習およびデータマイニング

問題分類クラスタリング回帰異常検知相関ルール（英語版）強化学習構造化予測（英語版）特徴量設計（英語版）表現学習（英語版）オンライン学習（英語版）半教師あり学習（英語版）教師なし学習ランキング学習（英語版）文法獲得（英語版）
教師あり学習（分類 • 回帰）決定木（英語版）アンサンブル（バギング、ブースティング、ランダムフォレスト） k-NN 線形回帰単純ベイズニューラルネットワークロジスティック回帰パーセプトロン関連ベクトルマシン (RVM)（英語版）サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版）階層的（英語版） k平均法期待値最大化法 (EM) DBSCAN OPTICS（英語版）平均値シフト（英語版）
次元削減因子分析 CCA ICA LDA（英語版） NMF（英語版） PCA t-SNE
構造化予測（英語版）グラフィカルモデルベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワークオートエンコーダディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN U-Net
強化学習 TD学習 Q学習 SARSA
理論偏りと分散のトレードオフ計算論的学習理論（英語版）経験損失最小化（英語版）オッカム学習（英語版） PAC学習統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表話編歴

ブースティング（英: Boosting）とは、教師あり学習を実行するための機械学習メタアルゴリズムの一種。ブースティングは、Michael Kearns の提示した「一連の弱い学習器をまとめることで強い学習器を生成できるか？」という疑問に基づいている^[1]。弱い学習器は、真の分類と若干の相関のある分類器と定義される。対照的に、強い学習器とは真の分類とよく相関する分類器である。

Michael Kearns の疑問への肯定的解答は、機械学習や統計学に多大な影響を及ぼしている。

アルゴリズム

ブースティングはアルゴリズム的に制限されてはおらず、多くの場合、分布に従って弱い分類器に繰り返し学習させ、それを最終的な強い分類器の一部とするものである。弱い分類器を追加する際、何らかの方法で重み付けをするのが一般的で、重み付けは弱い学習器の正確さに関連しているのが一般的である。弱い学習器が追加されると、データの重み付けが見直される。すなわち、誤分類される例は重みを増し、正しく分類される例は重みを減らす（boost by majority や BrownBoost などの一部のブースティングアルゴリズムは、繰り返し誤分類される例の重みを減らす）。従って、新たに追加される弱い学習器は、それまでの弱い学習器が誤分類していた例に注目することになる。

ブースティング・アルゴリズムには様々なものがある。初期のブースティング・アルゴリズムとして Robert Schapire の recursive majority gate formulation ^[2]、Yoav Freund の boost by majority ^[3] がある。これらは適応的ではなく、弱い学習器の利点を完全に生かしているとは言えない。

PAC学習（probably approximately correct learning）理論に従うブースティング・アルゴリズムだけが真のブースティング・アルゴリズムである。他の類似のアルゴリズムも誤ってブースティング・アルゴリズムと呼ばれることがあるが、それらを区別する用語として "leveraging algorithm" がある^[4]。

例

各種ブースティング・アルゴリズムの主な違いは、データ点と仮説の重み付けの方法である。有名なブースティング・アルゴリズムとして AdaBoost があり、これはおそらく初めて弱い学習器の適応を実現したものである。それ以外にも最近では LPBoost、BrownBoost、LogitBoost などのアルゴリズムがある。ブースティング・アルゴリズムの多くは、凸コスト関数を使った関数空間における最急降下法を実行できる AnyBoost フレームワークに適合する^[5]。

脚注

^ Michael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript. 1988
^ Rob Schapire. Strength of Weak Learnability. Journal of Machine Learning Vol. 5, pages 197-227. 1990
^ Yoav Freund. Boosting a weak learning algorithm by majority. Proceedings of the Third Annual Workshop on Computational Learning Theory. 1990
^ Nir Krause and Yoram Singer. Leveraging the margin more carefully. In Proceedings of the International Conference on Machine Learning (ICML), 2004.
^ Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In S.A. Solla, T.K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pages 512--518. MIT Press, 2000

参考文献

Yoav Freund and Robert E. Schapire A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119--139, 1997.
Robert E. Schapire and Yoram Singer. Improved Boosting Algorithms Using Confidence-Rated Predictions. Machine Learning, 37(3):297--336, 1998.