I am trying to read up about AdaBoost from Tibshirani (page 337 onwards), and would appreciate some help in understanding it better.

The book says that "For each successive iteration m = 2, 3, . . . , M the observation weights are individually modiﬁed and the classiﬁcation algorithm is reapplied to the weighted observations. At step m, those observations that were misclassiﬁed by the classiﬁer Gm−1 (x) induced at the previous step have their weights increased, whereas the weights are decreased for those that were classiﬁed correctly. Thus as iterations proceed, observations that are diﬃcult to classify correctly receive ever-increasing inﬂuence. Each successive classiﬁer is thereby forced to concentrate on those training observations that are missed by previous ones in the sequence."

I am not able to understand what it means to "reapply the algorithm to the weighted observations". Say for example if I am doing 2-class text classification, what am I doing to my observations (document vectors)? How does this "force" the classifier to concentrate on some samples vs others?

• Any thoughts on this? Or if anyone could explain AdaBoost in simple English, that will be helpful also. Thanks.
– Andy
Mar 3, 2011 at 18:18

mpq has already explained boosting in plain english.

A picture may substitute a thousand words ... (stolen from R. Meir and G. Rätsch. An introduction to boosting and leveraging)

Image remark: In the 1st Iteration the classifier based on all datapoints classifies all points correctly except those in x<0.2/y>0.8 and the point around 0.4/0.55 (see the circles in the second picture). In the second iteration exactly those points gain a higher weight so that the classifier based on that weighted sample classifies them correctly (2nd Iteration, added dashed line). The combined classifiers (i.e. "the combination of the dashed lines") result in the classifier represent by the green line. Now the second classifier produces another missclassifications (x in [0.5,0.6] / y in [0.3,0.4]), which gain more focus in the third iteration and so on and so on. In every step, the combined classifier gets closer and closer to the best shape (although not continuously). The final classifier (i.e. the combination of all single classifiers) in the 100th Iteration classifies all points correctly.

Now it should be more clear how boosting works. Two questions remain about the algorithmic details.

1. How to estimate missclassifications ?

In every iteration, only a sample of the training data available in this iteration is used for training the classifier, the rest is used for estimating the error / the missclassifications.

2. How to apply the weights ?

You can do this in the following ways:

• You sample the data using an appropriate sample algorithm which can handle weights (e.g. weighted random sampling or rejection sampling) and build classification model on that sample. The resulting sample contains missclassified examples with a higher probability than correctly classified ones, hence the model learned on that sample is forced to concentrate on the missclassified part of the data space.
• You use a classification model which is capable of handling such weights implicitly like e.g. Decision Trees. DT simply count. So instead of using 1 as counter/increment if an example with a certain predictor and class values is presented, it uses the specified weight w. If w = 0, the example is practically ignored. As a result, the missclassified examples have more influence on the class probability estimated by the model.

Imagine a certain word separates the classes perfectly, but it only appears in a certain part of the data space (i.e. near the decision boundary). Then the word has no power to separate all documents (hence it's expressiveness for the whole dataset is low), but only those near the boundary (where the expressiveness is high). Hence the documents containing this word will be misclassified in the first iteration(s), and hence gain more focus in later applications. Restricting the dataspace to the boundary (by document weighting), your classifier will/should detect the expressiveness of the word and classify the examples in that subspace correctly.

(God help me, I can't think of a more precise example. If the muse later decides to spend some time with me, I will edit my answer).

Note that boosting assumes weak classifiers. E.g. Boosting applied together with NaiveBayes will have no significant effect (at least regarding my experience).

edit: Added some details on the algorithm and explanation for the picture.

• Thanks for your response. Well I am afraid I don't get it still. How are the boundaries changing in the figure? What is it about the misclassified examples that causes the classifier to become smart, and do better next time? I mean let's say that there's an example that I don't know the correct class of - how would seeing that example again in later iterations help me put it in the right class? I can sense that there is something obvious here that I am not seeing - love that feeling :-)
– Andy
Mar 7, 2011 at 20:48
• @Andy: Updated my answer accordingly. Of course you have to know the correct class to estimate the missclassified points. In every iteration, you use only a sample of the training data for actual training and the rest to estimate the quality/missclassifications. Mar 8, 2011 at 7:47
• Thanks for explaining. The fact that not all data is used in every iteration for training was not obvious to me before. Let me chew on this for a bit, and I will get back.
– Andy
Mar 8, 2011 at 17:46
• Anyone still respond to this? I have a question - are the weights based on the missclassification of the most recent model, or the aggregate of all prior models? Elements of Statistical Learning says Gm-1(X), which seems to imply the previous model only. Feb 10, 2020 at 15:50

The weights should be applied in calculating of the cost function when training the classifier.

For example, assume our cost function is sum-of-square, weighted sample means when we calculate cost function, each item of sum-of-square will multiply its sample weight(former misclassified samples will have a large weight, so training process of this classifier concentrate more on those samples).