In boosting, why are the learners "weak"?

Question

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?

Answer 1

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 :)

Answer 2

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!

Answer 3

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.