Week 47: From Decision Trees to Ensemble Methods, Random Forests and Boosting Methods

Basic Steps of AdaBoost

With the above definitions we are now ready to set up the algorithm for AdaBoost. The basic idea is to set up weights which will be used to scale the correctly classified and the misclassified cases.

We start by initializing all weights to $ w_i = 1/n $, with $ i=0,1,2,\dots n-1 $. It is easy to see that we must have $ \sum_{i=0}^{n-1}w_i = 1 $.
We rewrite the misclassification error as

$$ \mathrm{\overline{err}}_m=\frac{\sum_{i=0}^{n-1}w_i^m I(y_i\ne G(x_i))}{\sum_{i=0}^{n-1}w_i}, $$

Then we start looping over all attempts at classifying, namely we start an iterative process for $ m=1:M $, where $ M $ is the final number of classifications. Our given classifier could for example be a plain decision tree.
1. Fit then a given classifier to the training set using the weights $ w_i $.
2. Compute then $ \mathrm{err} $ and figure out which events are classified properly and which are classified wrongly.
3. Define a quantity $ \alpha_{m} = \log{(1-\mathrm{\overline{err}}_m)/\mathrm{\overline{err}}_m} $
4. Set the new weights to $ w_i = w_i\times \exp{(\alpha_m I(y_i\ne G(x_i)} $.
Compute the new classifier $ G(x)= \sum_{i=0}^{n-1}\alpha_m I(y_i\ne G(x_i) $.

For the iterations with $ m \le 2 $ the weights are modified individually at each steps. The observations which were misclassified at iteration $ m-1 $ have a weight which is larger than those which were classified properly. As this proceeds, the observations which were difficult to classifiy correctly are given a larger influence. Each new classification step $ m $ is then forced to concentrate on those observations that are missed in the previous iterations.