170
$\begingroup$

Gradient tree boosting as proposed by Friedman uses decision trees as base learners. I'm wondering if we should make the base decision tree as complex as possible (fully grown) or simpler? Is there any explanation for the choice?

Random Forest is another ensemble method using decision trees as base learners. Based on my understanding, we generally use the almost fully grown decision trees in each iteration. Am I right?

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
227
$\begingroup$

$\text{error = bias + variance}$

  • Boosting is based on weak learners (high bias, low variance). In terms of decision trees, weak learners are shallow trees, sometimes even as small as decision stumps (trees with two leaves). Boosting reduces error mainly by reducing bias (and also to some extent variance, by aggregating the output from many models).
  • On the other hand, Random Forest uses as you said fully grown decision trees (low bias, high variance). It tackles the error reduction task in the opposite way: by reducing variance. The trees are made uncorrelated to maximize the decrease in variance, but the algorithm cannot reduce bias (which is slightly higher than the bias of an individual tree in the forest). Hence the need for large, unpruned trees, so that the bias is initially as low as possible.

Please note that unlike Boosting (which is sequential), RF grows trees in parallel. The term iterative that you used is thus inappropriate.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ "The trees are made uncorrelated to maximize the decrease in variance, but the algorithm cannot reduce bias (which is slightly higher than the bias of an individual tree in the forest)" -- the part about "slightly higher than the bias of an individual tree in the forest" seems incorrect. See web.stanford.edu/~hastie/Papers/ESLII.pdf section 15.4.2: "As in bagging, the bias of a random forest is the same as the bias of any of the individual sampled trees." Maybe you mean "slighly higher than the bias of a single fully-grown tree fit to the original data"? $\endgroup$
    – Adrian
    Commented Sep 17, 2017 at 5:24
  • 2
    $\begingroup$ @gung I think there is a key question unanswered in OP, which is: why not use a fully grown tree at the 1st step of GBM? Why use a sequence of weak learner is better than one single fully grown tree? I am curious about that $\endgroup$
    – KevinKim
    Commented Sep 13, 2018 at 5:45
  • $\begingroup$ Isn't error = bias + variance + unobserved error? $\endgroup$
    – David
    Commented Jun 22, 2020 at 22:36
  • $\begingroup$ @ftxx Either a deep tree or a combination of shallow trees is capable of including the effects of individual predictor variables and interactions between small numbers of predictors. However, the deep tree can also include interactions between large numbers of predictors, which aren't included in the shallow trees. But in most real-world problems, the dominant contributions won't be from very high-degree interaction terms, so these are more likely to contribute extra variance (overfitting), without giving greater test-set accuracy. [see Elements of Statistical Learning (2nd ed.), sec. 10.11] $\endgroup$
    – Tim Goodman
    Commented Mar 3, 2021 at 17:45
  • $\begingroup$ @David bias + variance + irreducible error, but as the name suggests, neither of these methods can reduce the latter. $\endgroup$
    – Tim Goodman
    Commented Mar 3, 2021 at 17:52
70
$\begingroup$

This question is addressed in this very nice post. Please take a look at it and the references therein. http://fastml.com/what-is-better-gradient-boosted-trees-or-random-forest/

Notice in the article that the speaks about calibration, and links to another (nice) blog post about it. Still, I find that the paper Obtaining Calibrated Probabilities from Boosting gives you a better understanding of what calibration in the context of boosted classifiers is, and what are standard methods to perform it.

And finally one aspect missing (a bit more theoretical). Both RF and GBM are ensemble methods, meaning you build a classifier out a big number of smaller classifiers. Now the fundamental difference lies on the method used:

  1. RF uses decision trees, which are very prone to overfitting. In order to achieve higher accuracy, RF decides to create a large number of them based on bagging. The basic idea is to resample the data over and over and for each sample train a new classifier. Different classifiers overfit the data in a different way, and through voting those differences are averaged out.
  2. GBM is a boosting method, which builds on weak classifiers. The idea is to add a classifier at a time, so that the next classifier is trained to improve the already trained ensemble. Notice that for RF each iteration the classifier is trained independently from the rest.
Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Would it be a fair conclusion from your answer that RF overfits more than GBM? $\endgroup$
    – 8forty
    Commented May 8, 2018 at 22:42
  • 7
    $\begingroup$ @8forty I wouldn't draw that conclusion - while a single tree in RF will overfit more than a single tree in GBM (because these are much smaller), in RF these overfit will be averaged out when employing a lot of trees, while in GBM the more trees you add, the higher the risk of overfitting. In short, as N (number of trees used) goes to infinity, I expect RF to overfit much less than GBM $\endgroup$
    – Ant
    Commented Jun 28, 2018 at 15:49
  • 2
    $\begingroup$ The references in the answer are useful. Also, scikit-learn.org/stable/modules/calibration.html - this is a thorough discussion of the probability calibration. You can do this step as a postprocessing to improve the results. $\endgroup$
    – Serhii Kushchenko
    Commented Nov 14, 2019 at 13:59
4
$\begingroup$

Although the above answers are really great, I would like to explain the difference in a very simple language.

  • Bagging technique that is Bootstrap Aggregation where we build separate decision trees using bootstrapped set of samples and average the resulting predictions. Each individual decision tree are grown deep without any pruning and hence each of them has high variance and low bias but averaging them reduces the overall variance. They result in improved accuracy over prediction with a single tree.

  • Bagging technique suffers from a disadvantage that of any of the predictor is very very strong than the other predictors. Each bagged tree will look similar because most of them will use that strong predictor. Hence the predictions from the bagged trees will be highly correlated. Unfortunately, averaging many highly correlated quantities does not lead to as large of a reduction in variance as averaging many uncorrelated quantities.

  • Random Forest overcome this problem by forcing each split to consider only a subset of the predictors that are random. The main difference between bagging and random forests is the choice of predictor subset size. If a random forest is built using all the predictors, then it is equal to bagging.

  • Boosting works in a similar way, except that the trees are grown sequentially: each tree is grown using information from previously grown trees. Boosting does not involve bootstrap sampling; instead each tree is fit on a modified version of the original data set.Unlike in bagging, the construction of each tree depends strongly on the trees that have already been grown. Because the growth of a particular tree takes into account the other trees that have already been grown, smaller trees are typically sufficient. These small trees are mostly Stump which have single split.

Improve this answer
$\endgroup$

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