28
$\begingroup$

See also a similar question on stats.SE.

In boosting algorithms such as AdaBoost and LPBoost it is known that the "weak" learners to be combined only have to perform better than chance to be useful, from Wikipedia:

The classifiers it uses can be weak (i.e., display a substantial error rate), but as long as their performance is not random (resulting in an error rate of 0.5 for binary classification), they will improve the final model. Even classifiers with an error rate higher than would be expected from a random classifier will be useful, since they will have negative coefficients in the final linear combination of classifiers and hence behave like their inverses.

  • What are the benefits of using weak as opposed to strong learners? (e.g. why not boost with "strong" learning methods - are we more prone to overfitting?)

  • Is there some sort of "optimal" strength for the weak learners? And is this related to the number of learners in the ensemble?

Is there any theory to back up the answers to these questions?

$\endgroup$
  • $\begingroup$ Weak learners also avoid over-fitting to training data $\endgroup$ – Aman Deep Gautam Nov 25 '15 at 8:54
15
$\begingroup$

So, boosting is a learning algorithm, which can generate high-accuracy predictions using as a subroutine another algorithm, which in turn can efficiently generate hypotheses just slightly better (by an inverse polynomial) than random guessing.

It's main advantage is speed.

When Schapire presented it in 1990 it was a breakthrough in that it showed that a polynomial time learner generating hypotheses with errors just slightly smaller than 1/2 can be transformed into a polynomial time learner generating hypotheses with an arbitrarily small error.

So, the theory to back up your question is in "The strength of weak learnability" (pdf) where he basically showed that the "strong" and "weak" learning are equivalent.

And perhaps the answer the the original question is, "there's no point constructing strong learners when you can construct weak ones more cheaply".


From the relatively recent papers, there's "On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithms" (pdf) which I don't understand but which seems related and may be of interest to more educated people :)

$\endgroup$
  • 1
    $\begingroup$ +1 nice references. So perhaps the answer is: "there's no point constructing strong learners when you can construct weak ones more cheaply"? $\endgroup$ – tdc Feb 17 '12 at 11:20
  • $\begingroup$ yeah, sounds like it - I updated the answer! Also, if I correctly understand, this doesn't depend on the strength of your weak learners - they just have to be "slightly" better than random. $\endgroup$ – andreister Feb 17 '12 at 11:22
  • 1
    $\begingroup$ I think what you both really mean is: there's no point in constructing costly strong learners when similar or even better skill can be reached simply by combining many cheap weak learners. Indeed, if the skill attained by strong learners was much higher than the skill reached by weak learners, well then I could totally see the point in constructing strong learners... $\endgroup$ – Antoine Sep 25 '15 at 19:00
7
$\begingroup$

I will address overfitting, which hasn't been mentioned yet, with a more intuitive explanation. Your first question was:

What are the benefits of using weak as opposed to strong learners? (e.g. why not boost with "strong" learning methods - are we more prone to overfitting?)

The main reasons, in my understanding, are:

  • Speed, as covered pretty well in the other answers;
  • Accuracy improvement: if you already have a strong learner, the benefits of boosting are less relevant;
  • Avoid overfitting, as you guessed. Think about it this way:

What boosting does is to combine many different hypothesis from the hypothesis space so that we end up with a better final hypothesis. The great power of boosting, therefore, comes from the diversity of the hypothesis combined.

If we use a strong learner, this diversity tends to decrease: after each iteration there won't be many errors (since the model is complex), which won't make boosting change the new hypothesis much. With very similar hypothesis, the ensemble will be very similar to a single complex model, which in turn tends to overfit!

$\endgroup$
  • 3
    $\begingroup$ This is the real answer. $\endgroup$ – Matthew Drury Apr 13 '18 at 0:29
6
$\begingroup$

In boosting we use weak learners mostly since they are trained faster compared to strong learners. Think about it. If I use Multi-Layer Neural Network as the learner, then I need to train lots of them. On the other hand, a decision tree may be a lot faster, then I can train lots of them.

Let's say I use 100 learners. I train NN in 100 seconds and decision tree in 10 seconds. My first boosting with NN will take 100*100 seconds while second boosting with decision tree will take 100*10 seconds.

That said I have seen articles, which uses strong learners in boosting. But in that problems that strong learners were fast in my opinion.

I tried to train MLP on KDD99 Intrusion Detection Dataset, (4+ Million) using Weka. It took more than 72 hours on my machine. But boosting (AdaBoostM1 with Decision Tree - Decision Stump) took only 3 hours. In this problem it is clear that I can not use boosting with a strong learner, that is a learner which takes too much time.

$\endgroup$
  • 1
    $\begingroup$ "I have seen articles, which uses strong learners in boosting" - any references? $\endgroup$ – tdc Feb 16 '12 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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