AdaBoost
二分類のアルゴリズム
Given:
where 
Initialize 
For
:
- Find the classifier
that minimizes the error with respect to the distribution
:
, where ![{\displaystyle \epsilon _{j}=\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h_{j}(x_{i})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9a4c26f52b4cbd6d53f1c8171c05145fbc975b3)
- 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.
ブースティングの統計的理解
ブースティングは凸集合の関数上に関する凸損失関数の最小化とみなすことができる。特に、損失関数を最小化するために指数関数の損失関数:

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

を用いる。