AdaBoost

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

AdaBoost は、それぞれの標本ひょうほんに対たいし、弱じゃく分類ぶんるい器き $t$ を、$t=1$ から $t=T$ まで順じゅんに適用てきようし、それぞれの分類ぶんるい器きが正解せいかいしたか否ひかを判断はんだんする。間違まちがって分類ぶんるいされた標本ひょうほんに対応たいおうする重おもみ $D_{t}$ は、より重おもくされる（あるいは、正まさしく分類ぶんるいされた標本ひょうほんの場合ばあいは、重おもみを減へらす）。これらの標本ひょうほんに対たいする重おもみから、次つぎの t のループでは正ただしい分類ぶんるい器きを早はやく探さがす事ことが出来できる。

二に分類ぶんるいのアルゴリズム

Given: $(x_{1},y_{1}),\ldots ,(x_{m},y_{m})$ where $x_{i}\in X,\,y_{i}\in Y=\{-1,+1\}$

Initialize $D_{1}(i)={\frac {1}{m}},i=1,\ldots ,m.$

For $t=1,\ldots ,T$:

• Find the classifier $h_{t}:X\to \{-1,+1\}$ that minimizes the error with respect to the distribution $D_{t}$:

$h_{t}={\underset {h_{j}\in {\mathcal {H}}}{\operatorname {argmin} }}\;\epsilon _{j}$, where $\epsilon _{j}=\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h_{j}(x_{i})]$

• if $\epsilon _{t}>0.5$ then stop.
• Choose $\alpha _{t}\in \mathbf {R}$, typically $\alpha _{t}={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{t}}{\epsilon _{t}}}$ where $\epsilon _{t}$ is the weighted error rate of classifier $h_{t}$.
• Update:

$D_{t+1}(i)={\frac {D_{t}(i)\exp(-\alpha _{t}y_{i}h_{t}(x_{i}))}{Z_{t}}}$

where $Z_{t}$ is a normalization factor (chosen so that $D_{t+1}$ will be a probability distribution, i.e. sum one over all x).

Output the final classifier:

$H(x)={\textrm {sign}}\left(\sum _{t=1}^{T}\alpha _{t}h_{t}(x)\right)$

The equation to update the distribution $D_{t}$ is constructed so that:

$-\alpha _{t}y_{i}h_{t}(x_{i}){\begin{cases}<0,&y(i)=h_{t}(x_{i})\\>0,&y(i)\neq h_{t}(x_{i})\end{cases}}$

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

ブースティングの統計とうけい的てき理解りかい

ブースティングは凸とつ集合しゅうごうの関数かんすう上じょうに関かんする凸とつ損失そんしつ関数かんすうの最小さいしょう化かとみなすことができる。特とくに、損失そんしつ関数かんすうを最小さいしょう化かするために指数しすう関数かんすうの損失そんしつ関数かんすう:

$\sum _{i}e^{-y_{i}f(x_{i})}$

および関数かんすうに対たいして探索たんさくを行おこなう:

$f=\sum _{t}\alpha _{t}h_{t}$

を用もちいる。

関連かんれん項目こうもく

• バギング
• 線形せんけい計画けいかくブースティング
• 勾配こうばいブースティング
• 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