28
$\begingroup$

I have read various (seemingly) contradicting statements whether or not AdaBoost (or other boosting techniques) are less or more prone to overfitting compared to other learning methods.

Are there good reasons to believe one or the other? If it depends, what does it depend on? What are the reasons that AdaBoost is less/more prone to overfitting?

$\endgroup$
1
  • 1
    $\begingroup$ My intuition is that it is more prone to overfitting than a random forest. However, the algorithm is designed to avoid overfitting, and it usually doesn't seem to be a problem. I have no references to back this up, but you can use the caret package to cross-validate adaboost, and I've found that it usually generalizes well. $\endgroup$
    – Zach
    Jan 5, 2012 at 13:04

2 Answers 2

25
$\begingroup$

As you say a lot has been discussed about this matter, and there's some quite heavy theory that has gone along with it that I have to admit I never fully understood. In my practical experience AdaBoost is quite robust to overfitting, and LPBoost (Linear Programming Boosting) even more so (because the objective function requires a sparse combination of weak learners, which is a form of capacity control). The main factors that influence it are:

  • The "strength" of the "weak" learners: If you use very simple weak learners, such as decision stumps (1-level decision trees), then the algorithms are much less prone to overfitting. Whenever I've tried using more complicated weak learners (such as decision trees or even hyperplanes) I've found that overfitting occurs much more rapidly

  • The noise level in the data: AdaBoost is particularly prone to overfitting on noisy datasets. In this setting the regularised forms (RegBoost, AdaBoostReg, LPBoost, QPBoost) are preferable

  • The dimensionality of the data: We know that in general, we experience overfitting more in high dimensional spaces ("the curse of dimensionality"), and AdaBoost can also suffer in that respect, as it is simply a linear combination of classifiers which themselves suffer from the problem. Whether it is as prone as other classifiers is hard to determine.

Of course you can use heuristic methods such as validation sets or $k$-fold cross-validation to set the stopping parameter (or other parameters in the different variants) as you would for any other classifier.

$\endgroup$
14
$\begingroup$

I agree with most of the points mentioned in tdc comment. however, I have to add and correct few things.

  • As shown in L2Boost by Peter Bühlmann, as the number of weak learners (rounds of boosting) increases, the bias converges exponentially fast while the variance increases by geometrically diminishing magnitudes which means: It overfits much slower than most of the other methods.
  • It was wrongly mentioned in Zach comment that it is better than random forest in terms of overfit. It is completely wrong. In fact, according to theory (look at original random forest paper by Breiman), Random Forest is absolutely immune against overfitting as long as its weak classifiers don't overfit to data.
  • Unlike what mentioned in tdc comment, most of boosting methods are highly sensitive to the labeling noise and may easily overfit in the presence of labeling noise.
  • In datasets where Bayes error rates are far from 0 (i.e., features are not discriminative enough) boosting methods can easily overfit , as well. Because they try to reduce the training error to zero while in reality even the optimal classifier, i.e., Bayes classifier can reach to a lets say 40% error rate.
  • finally, and this has not been published any where (to the best of my knowledge) there is a kind of overfitting in which the generalization error does not increase as the boosting rounds increases but it does not decreases either. It means the algorithm has stuck in a local optima. In this situation, the training error constantly decreases while the test error remains almost constant. So far, we never considered this phenomenon as an indication of overfitting but I believe it is a sign of overfitting and by using more complex weak learners, (strange!) we may in fact go against it (This last point should be considered with caution :D)
$\endgroup$
4
  • 1
    $\begingroup$ It's worth adding to this answer that I might have experienced the latter kind of overfitting today, with both AdaBoost and Random Forest. In cross-validation, the out-of-fold error converged to a constant with only 20 base estimators, and then bounced around that constant with a high variance. My suspicion was exactly the same: the greedy algorithms got stuck in some kind of local optimum. This isn't confirmation of what happened but it's nice to know someone else had the same thought. $\endgroup$ Jun 28, 2015 at 15:13
  • $\begingroup$ @ssdecontrol Can you share what you did ? I want to reproduce the results to have a better understanding $\endgroup$ Feb 24, 2016 at 11:57
  • $\begingroup$ @saurabhagarwal I think I was working on the Kaggle Titanic project $\endgroup$ Feb 24, 2016 at 18:56
  • 1
    $\begingroup$ @TNM it is a late question, but sometimes with boosting one can experiment learning in stages, training error goes down but test error goes in steps. I imagined this behavior caused by how the signal is stratified in data. Due to weak learners at first it discovers general structure in data, and after that other particular structure in data with localized behavior, but it takes time (iteration) until the subsequent structures goes as a priority to weak learners. That is not overfit but an artifact of boosting $\endgroup$
    – rapaio
    Jun 30, 2021 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.