Boosting algorithms and overfitting

Question

In the book of Witten and Frank on Data Mining algorithms, I read:

"If boosting succeeds in reducing the error on fresh test data, it often does so in a spectacular way. One very surprising finding is that performing more boosting iterations can reduce the error on new data long after the error of the combined classifier on the training data has dropped to zero. Researchers were puzzled by this result because it seems to contradict Occam’s razor, which declares that of two hypotheses that explain the empirical evidence equally well the simpler one is to be preferred. Performing more boosting iterations without reducing training error does not explain the training data any better, and it certainly adds complexity to the combined classifier. Fortunately, the contradiction can be resolved by considering the classifier’s confidence in its predictions."

If I understand correctly, boosting can reduce the test error after the training error has dropped to zero. Does it mean that the classifier does overfit? Can you clear me this point?

Answer 1

A boosted classifier can still overfit. With boosting as you add more base learners to the classifier you can (potentially) keep decreasing the training set error rate. Eventually this training set error rate will bottom out at a minimum value (possibly 0, possibly higher). The point being made is that even after the training set error has reached its minimum, adding more base learners to the classifier can cause the error of the classifier on an unseen test set to decrease (even though the error on the training set is stable).

Having said all that, it is possible that the improvement you see on the training/test set is due to the classifier overfitting. For example, you may have a dataset that is poorly representative of the potential range of all data points. In this case your boosted classifier could reach 0% error rate, but still be overfit as it has poor generalisation capabilities. Alternatively, if the base learners you use are inappropriate for the problem you may end up with all the base learners being overfit, and consequently the boosted classifier will possibly be overfit.