3
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Question: GBM's use random subsets in both columns (variables) and rows (samples). How does that interact with "runaway overfitting"? $\endgroup$ Jun 10, 2021 at 16:18
  • $\begingroup$ Both row and column subsetting reduce overfitting. The extra room to fit that they give could be used to grow somewhat deeper trees, but it can also be used to add more trees to the ensemble. It's still true that boosting has an increasing tendency to overfit with more trees and random forests doesn't. $\endgroup$ Jun 11, 2021 at 2:32
1
$\begingroup$

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

This (data):
enter image description here

Is represented by a (CART fit) as this:

enter image description here

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.
$\endgroup$
4
  • $\begingroup$ So in short: I can use deeper trees, the decision stump was just a design decision, deeper trees may work well, they just boost in slightly different way. Is that correct? $\endgroup$
    – qalis
    Apr 22, 2021 at 13:42
  • $\begingroup$ @qalis - I'm not disagreeing, but you are boiling a lot down to a little. I think GBM can do way more, but they are taught in a way that gives a few a very strong advantage. I think that has to do with the wisdom of the field. I get really good results with 1500 trees and lambda = 0.001, but conventional wisdom says use 50 trees and lambda of 0.1. The conventional wisdom finds my parameters counter-intuitive. I think deeper trees may work much better in some cases, and not as well in others, but mileage may vary. $\endgroup$ Apr 22, 2021 at 13:54
  • 1
    $\begingroup$ Your 2nd figure likely does not represent a boosted decision tree ensemble, but a single decision tree with many many nodes. An ensemble, in general, and surely a gbm ensemble, will NOT consist of boxes; it has much smoother decision boundaries, because of the averaging over trees. $\endgroup$ May 1, 2021 at 22:56
  • $\begingroup$ @MarjoleinFokkema - you are exactly correct. That is a single CART and not a series ensemble of them, aka a gbm. It is the "atom", not the molecule or polymer. $\endgroup$ May 2, 2021 at 2:33

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.