AdaBoost

AdaBoost（Adaptive Boosting、エイダブースト、アダブースト）は、Yoav Freund と Robert Schapire によって考案された機械学習アルゴリズムである。メタアルゴリズムであり、他の多くの学習アルゴリズムと組み合わせて利用することで、そのパフォーマンスを改善することができる。AdaBoost は前の分類機の間違いに応じて調整された次の分類機を作るという意味で適応的 (Adaptive) である。AdaBoost はノイズの多いデータや異常値に影響を受ける。しかし、いくつかの場面では、多くの学習アルゴリズムより過剰適合の影響を受けにくい。

AdaBoost は、それぞれの標本に対し、  を、 から  まで順に適用し、それぞれの分類器が正解したか否かを判断する。間違って分類された標本に対応する重み  は、より重くされる（あるいは、正しく分類された標本の場合は、重みを減らす）。これらの標本に対する重みから、次の t のループでは正しい分類器を早く探す事が出来る。

 二分類のアルゴリズム 
Given:  where 

Initialize 

For :

 Find the classifier  that minimizes the error with respect to the distribution :
 , where 
 if  then stop.
 Choose , typically  where  is the weighted error rate of classifier .
 Update:

where  is a normalization factor (chosen so that  will be a probability distribution, i.e. sum one over all x).

Output the final classifier:



The equation to update the distribution  is constructed so that:



Thus, after selecting an optimal classifier  for the distribution , the examples  that the classifier  identified correctly are weighted less and those that it identified incorrectly are weighted more.  Therefore, when the algorithm is testing the classifiers on the distribution , it will select a classifier that better identifies those examples that the previous classifer missed.

ブースティングの統計的理解
ブースティングは凸集合の関数上に関する凸損失関数の最小化とみなすことができるT. Zhang, "Convex Risk Minimization", Annals of Statistics, 2004.。特に、損失関数を最小化するために指数関数の損失関数: 

および関数に対して探索を行う: 

を用いる。

関連項目
 バギング

 勾配ブースティング
 LightGBM

脚注

外部リンク
icsiboost, an open source implementation of Boostexter
NPatternRecognizer , a fast machine learning algorithm library written in C#. It contains support vector machine, neural networks, bayes, boost, k-nearest neighbor, decision tree, ..., etc.

Adaboost in C++, an implementation of Adaboost in C++ and boost by Antonio Gulli
 Easy readable Matlab Implementation of Classic AdaBoost
Boosting.org, a site on boosting and related ensemble learning methods
JBoost, a site offering a classification and visualization package, implementing AdaBoost among other boosting algorithms. 
AdaBoost Presentation summarizing Adaboost (see page 4 for an illustrated example of performance)
A Short Introduction to Boosting Introduction to Adaboost by Freund and Schapire from 1999
A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997  (Original paper of Yoav Freund and Robert E.Schapire where Adaboost is first introduced.)
An applet demonstrating AdaBoost
Ensemble Based Systems in Decision Making, R. Polikar, IEEE Circuits and Systems Magazine, vol.6, no.3, pp. 21-45, 2006. A tutorial article on ensemble systems including pseudocode, block diagrams and implementation issues for AdaBoost and other ensemble learning algorithms.
A Matlab Implementation of AdaBoost

Additive logistic regression: a statistical view of boosting by Jerome Friedman, Trevor Hastie, Robert Tibshirani. Paper introducing probabilistic theory for AdaBoost, and introducing GentleBoost
OpenCV implementation of several boosting variants 
MATLAB AdaBoost toolbox. Includes Real AdaBoost, Gentle AdaBoost and Modest AdaBoost implementations. 
AdaBoost and the Super Bowl of Classifiers - A Tutorial on AdaBoost. 
Rapid Object Detection using a Boosted Cascade of Simple Features
Category:分類アルゴリズム