AdaBoost - why decision stumps instead of trees?

Question

Since the original AdaBoost article it has been found out that boosting reduces both variance and bias in the classifier (in contrast to bagging, which only reduces variance). Original AdaBoost (and default Scikit-learn implementation) uses decision stumps, i.e. decision trees with depth 1.

Why is that? Why shouldn't we just use full decision trees, or decision trees with some pruning? Weighting samples works for entire trees, after all, and more recent boosting algorithms (e.g. gradient boosting in Scikit-learn, XGBoost, LightGBM) grow deep trees. This would also allow different tree growing algorithms to be boosted in this simple way, instead of only decision stumps.

Answer 1

The reason for using 'stumps' in boosting but full-height trees in random forests is to do with how the aggregation and fitting is done.

In random forests, the trees in the ensemble are fitted independently to independent bootstrap samples, so any error caused by growing the trees too far is independent for each tree and tends to cancel out in the ensemble average.

In boosting, the trees are fitted sequentially, with each one trained on (in some sense) the residuals from the previous classifier. Once a boosted ensemble starts overfitting, it will keep overfitting; the errors won't just cancel out.

For this reason, it's worth having individual trees be short when boosting and tall when bagging. It's not clear that 'stumps' are optimal for boosting -- there are recommendations for trees with, say, 6 leaves to include interactions better -- but that's an explanation for the basic idea.

Answer 2

If you think about the gradient-boosted CART (aka an atom of gbm), the model is "boxes"(1).

This (data):

Is represented by a (CART fit) as this:

Each leaf-tip is a mean. Each split is perpendicular to an axis. It is trying to adjust the box bounds and the mean height to minimize error in representation.

From the above, you see the motivation for oblique forests.

If you have a deeper tree, then there are many splits and means per level of boosting. We know there is weakness in an individual tree, it is literally a "weak learner". If you have a stump, then every line is boosted as it is made. The "boostings" to "split-and-mean" ratio is at its upper extreme value. If you have a deep tree, or even one whose depth is limited by leaf-count or other control metrics, then that ratio is arguably at its opposite extreme.

$$ \text {root to leaf ratio} = \frac {\text {number of tree roots}}{\text{mean splits per tree}}$$

So why the stump? A wonderful young woman over at Microsoft described the gbm like a tiger-mom, where the student is force to study over and over. For a student that is poor or content that is very difficult, the learning rate is lower and the iterations are higher. This makes a model that is larger, takes more to train, and takes more to execute. If the student is good then they can move faster through the content, and they can take bigger steps; similarly if the content is easier then progress is easier to make. In that case a deeper tree, with a larger learning rate, and with a smaller ensemble-count is possible. It makes a smaller file, with fewer parameters, that trains quickly and runs quickly.

All of these are elements of the "art" where the practitioner must make decisions using some limited design of experiments. Exhaustive grid searching can be expensive (in terms of time and money) here.

I like the "philosophy" section:

• RF is an example of a tool that is useful in doing analyses of scientific data.
• But the cleverest algorithms are no substitute for human intelligence and knowledge of the data in the problem.
• Take the output of random forests not as absolute truth, but as smart computer generated guesses that may be helpful in leading to a deeper understanding of the problem.