AdaBoost - The Algorithm For The Binary Classification Task

The Algorithm For The Binary Classification Task

Given:

• training set: where
• number of iterations

Initialize

For :

• From the family of weak classifiers ℋ, find the classifier that maximizes the absolute value of the difference of the corresponding weighted error rate and 0.5 with respect to the distribution :

where .

I is the indicator function.

• If, where is a previously chosen threshold, then stop.
• Choose, typically .
• Update:

where is the normalization factor:

which ensures that will be a probability distribution (i.e., the sum over all x equals one)

Output the final classifier:

Note that 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 classifier missed.