AdaBoostのソースを表示

'''AdaBoost'''（Adaptive [[ブースティング|Boosting]]、エイダブースト、アダブースト）は、[[Yoav Freund]] と [[Robert Schapire]] によって考案された<ref>{{Cite Web|author=Yoav Freund, Robert E. Schapire |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.9855 |title=A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting |year=1995 |access-date=July 9 2010 }}</ref>機械学習アルゴリズムである。メタアルゴリズムであり、他の多くの学習アルゴリズムと組み合わせて利用することで、そのパフォーマンスを改善することができる。AdaBoost は前の分類機の間違いに応じて調整された次の分類機を作るという意味で適応的 (Adaptive) である。AdaBoost はノイズの多いデータや異常値に影響を受ける。しかし、いくつかの場面では、多くの学習アルゴリズムより[[過剰適合]]の影響を受けにくい。

AdaBoost は、それぞれの標本に対し、{{仮リンク|弱識別機|en|weak classifier|label=弱分類器}} <math>t</math> を、<math> t = 1</math> から <math>t = T</math> まで順に適用し、それぞれの分類器が正解したか否かを判断する。間違って分類された標本に対応する重み <math>D_{t}</math> は、より重くされる（あるいは、正しく分類された標本の場合は、重みを減らす）。これらの標本に対する重みから、次の t のループでは正しい分類器を早く探す事が出来る。

== 二分類のアルゴリズム ==
Given: <math>(x_{1},y_{1}),\ldots,(x_{m},y_{m})</math> where <math>x_{i} \in X,\, y_{i} \in Y = \{-1, +1\}</math>

Initialize <math>D_{1}(i) = \frac{1}{m}, i=1,\ldots,m.</math>

For <math>t = 1,\ldots,T</math>:

* Find the classifier <math>h_{t} : X \to \{-1,+1\}</math> that minimizes the error with respect to the distribution <math>D_{t}</math>:
: <math>h_{t} = \underset{h_{j} \in \mathcal{H}}{\operatorname{argmin}} \; \epsilon_{j}</math>, where <math> \epsilon_{j} = \sum_{i=1}^{m} D_{t}(i)[y_i \ne h_{j}(x_{i})]</math>
* if <math>\epsilon_{t} > 0.5</math> then stop.
* Choose <math>\alpha_{t} \in \mathbf{R}</math>, typically <math>\alpha_{t}=\frac{1}{2}\textrm{ln}\frac{1-\epsilon_{t}}{\epsilon_{t}}</math> where <math>\epsilon_{t}</math> is the weighted error rate of classifier <math>h_{t}</math>.
* Update:
: <math>D_{t+1}(i) = \frac{ D_t(i) \exp(-\alpha_t y_i h_t(x_i)) }{ Z_t }</math><br>
where <math>Z_{t}</math> is a normalization factor (chosen so that <math>D_{t+1}</math> will be a [[probability distribution]], i.e. sum one over all x).

Output the final classifier:

: <math>H(x) = \textrm{sign}\left( \sum_{t=1}^{T} \alpha_{t}h_{t}(x)\right)</math>

The equation to update the distribution <math>D_{t}</math> is constructed so that:

: <math>- \alpha_{t} y_{i} h_{t}(x_{i}) \begin{cases} <0, & y(i)=h_{t}(x_{i}) \\ >0, & y(i) \ne h_{t}(x_{i}) \end{cases}</math>

Thus, after selecting an optimal classifier <math>h_{t} \,</math> for the distribution <math>D_{t} \,</math>, the examples <math>x_{i} \,</math> that the classifier <math>h_{t} \,</math> 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 <math>D_{t+1} \,</math>, it will select a classifier that better identifies those examples that the previous classifer missed.

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

:<math>\sum_i e^{-y_i f(x_i)}</math>

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

:<math>f = \sum_t \alpha_t h_t</math>

を用いる。

==関連項目==
* [[バギング]]
* {{仮リンク|線形計画ブースティング|en|LPBoost}}
* [[勾配ブースティング]]
* LightGBM

==脚注==
{{reflist}}

==外部リンク==
*[https://code.google.com/archive/p/icsiboost icsiboost], an open source implementation of Boostexter
*[http://npatternrecognizer.codeplex.com/ 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.

*[https://codingplayground.blogspot.com/2009/03/adaboost-improve-your-performance.html Adaboost in C++], an implementation of Adaboost in C++ and boost by Antonio Gulli
*[http://www.mathworks.com/matlabcentral/fileexchange/27813  Easy readable Matlab Implementation of Classic AdaBoost]
*[http://www.boosting.org Boosting.org], a site on boosting and related ensemble learning methods
*[http://jboost.sourceforge.net JBoost], a site offering a classification and visualization package, implementing AdaBoost among other boosting algorithms. 
*[http://cmp.felk.cvut.cz/~sochmj1/adaboost_talk.pdf AdaBoost] Presentation summarizing Adaboost (see page 4 for an illustrated example of performance)
*[http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf A Short Introduction to Boosting] Introduction to Adaboost by Freund and Schapire from 1999
*[http://citeseer.ist.psu.edu/cache/papers/cs/2215/http:zSzzSzwww.first.gmd.dezSzpersonszSzMueller.Klaus-RobertzSzseminarzSzFreundSc95.pdf/freund95decisiontheoretic.pdf 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.)
*[http://www.cs.ucsd.edu/~yfreund/adaboost/index.html An applet demonstrating AdaBoost]
*[http://engineering.rowan.edu/~polikar/RESEARCH/PUBLICATIONS/csm06.pdf 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.
*[http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=21317&objectType=file A Matlab Implementation of AdaBoost]

*[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9525 Additive logistic regression: a statistical view of boosting] by Jerome Friedman, Trevor Hastie, Robert Tibshirani. Paper introducing probabilistic theory for AdaBoost, and introducing GentleBoost
*[http://opencv.willowgarage.com/documentation/boosting.html OpenCV implementation of several boosting variants] 
*[http://graphics.cs.msu.ru/en/science/research/machinelearning/adaboosttoolbox MATLAB AdaBoost toolbox. Includes Real AdaBoost, Gentle AdaBoost and Modest AdaBoost implementations.] 
*[http://www.inf.fu-berlin.de/inst/ag-ki/adaboost4.pdf AdaBoost and the Super Bowl of Classifiers - A Tutorial on AdaBoost.] 
*[http://research.microsoft.com/en-us/um/people/viola/Pubs/Detect/violaJones_CVPR2001.pdf Rapid Object Detection using a Boosted Cascade of Simple Features]
[[Category:分類アルゴリズム]]