Why Adaboost with Decision Trees?

Question

I've been reading a bit on boosting algorithms for classification tasks and Adaboost in particular. I understand that the purpose of Adaboost is to take several "weak learners" and, through a set of iterations on training data, push classifiers to learn to predict classes that the model(s) repeatedly make mistakes on. However, I was wondering why so many of the readings I've done have used decision trees as the weak classifier. Is there a particular reason for this? Are there certain classifiers that make particularly good or bad candidates for Adaboost?

Answer 1

I talked about this in an answer to a related SO question. Decision trees are just generally a very good fit for boosting, much more so than other algorithms. The bullet point/ summary version is this:

1. Decision trees are non-linear. Boosting with linear models simply doesn't work well.
2. The weak learner needs to be consistently better than random guessing. You don't normal need to do any parameter tuning to a decision tree to get that behavior. Training an SVM really does need a parameter search. Since the data is re-weighted on each iteration, you likely need to do another parameter search on each iteration. So you are increasing the amount of work you have to do by a large margin.
3. Decision trees are reasonably fast to train. Since we are going to be building 100s or 1000s of them, thats a good property. They are also fast to classify, which is again important when you need 100s or 1000s to run before you can output your decision.
4. By changing the depth you have a simple and easy control over the bias/variance trade off, knowing that boosting can reduce bias but also significantly reduces variance. Boosting is known to overfit, so the easy nob to tune is helpful in that regard.

Answer 2

I do not have a text-book answer. However here are some thoughts.

Boosting can be seen in direct comparison with bagging. These are two different approaches of the bias variance tradeoff dilemma. While bagging have as weak learners, some learners with low bias and high variance, by averaging the bagging ensemble decrease the variance for a little bias. Boosting on the other hand works well with different weak learners. The boosting weak learners have high bias and low variance. By building up one learner on the top of another, the boosting ensemble tries to decrease the bias, for a little variance.

As a consequence, if you consider for example to use bagging and boosting with trees as weak learners, the best way to use is small/short trees with boosting and very detailed trees with bagging. This is why very often a boosting procedure uses a decision stump as weak learner, which is the shortest possible tree (a single if condition on a single dimension). This decision stump is very stable, so it has very low variance.

I do not see any reason to use trees with boosting procedures. However, short trees are simple, easy to implement and easy to understand. However, I think that in order to be succesfull with a boosting procedure, your weak learner has to have low variance, has to be rigid, with very few degrees of freedom. For example I see no point to have as a weak learner a neural network.

Additionally, you have to note that for some kind of boosting procedures, gradient boosting for example, Breiman found that if the weak learner is a tree, some optimization in the way how boosting works can be done. Thus we have gradient boosting trees. There is a nice exposure of boosting in the ESTL book.