AdaBoost

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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.