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

AdaBoost は、それぞれの標本に対し、弱い分類器([weak classifier])を、からまで順に適用し、それぞれの分類器が正解したか否かを判断する。間違って分類された標本に対応する重みは、より重くされる(あるいは、正しく分類された標本の場合は、重みを減らす)。これらの標本に対する重みから、次の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.

ブースティングの統計的理解編集

Boosting can be seen as minimization of a convex loss function over a convex set of functions. [2] Specifically, the loss being minimized is the exponential loss

 

and we are seeking a function

 

関連項目編集

脚注編集

  1. ^ Yoav Freund, Robert E. Schapire. "A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting", 1995
  2. ^ T. Zhang, "Convex Risk Minimization", Annals of Statistics, 2004.

外部リンク編集

  • 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.