1
$\begingroup$

As a follow-up on Randomness in Random Forests I wonder if the Random Forest approach, by using bootstrap samples, is really making usage of the bootstrapping. This means, are RFs really trying to estimate the underlying distribution of the samples? When I think about it, it makes sense as it's probably a difference wether the data follows a uniform distribution or a gaussian distribution. So, I'd assume the growing of the trees depends on it? But to be honest, I also wouldn't be surprised wether the trees are really random and independent of the samples itself.

$\endgroup$

1 Answer 1

3
$\begingroup$

Bootstrap is used in this case to improve performances, not to estimate underlying distributions. Bootstrap is needed to generate multiple sample to be used to train weakly correlated classifiers (or regressors) that you want to aggregate together. The idea was already present in bagging (see the 1996 article by Breiman: "Bagging Predictors").

Note that it is not the only way to aggregate predictors (e.g. there is also Boosting).

Now, the point is: why does aggregation works? An intuitive explanation goes as follows. Consider estimators: $\hat f_{1}(x),\hat f_{2}(x),\ldots,\hat f_{B}(x)$. Say these are regressors, and that we generated each of them on different bootstrap subsamples, say $B$ of them. One way to aggregate them is to take as final prediction the average prediction: $$ \hat f(x) = \frac{1}{B}\sum_{i=1}^{B}\hat f_{i}(x).$$ Now, consider the bias of this predictor: $$ \text{bias}(\hat f(x))=\mathbb{E}\hat f(x) - \mathbb{E}(Y\mid x)= \frac{1}{B}\sum_{i=1}^{B}\mathbb{E}\hat f_{i}(x) - \mathbb{E}(Y\mid x) = \frac{1}{B}\sum_{i=1}^{B}\text{bias}(\hat f_{i}(x))$$ (the second equality follows from linearity of expectation). In the case where the predictors are all unbiased, the aggregated predictor is still unbiased.

Now, the variance: $$ \begin{aligned} \mathbb{V}\{\hat{f}(x)\} &=\mathbb{E}\left(\hat{f}(X)-\mathbb{E}\hat{f}(X)\right)^{2} \\ &=\mathbb{E}\left(\frac{1}{B} \sum_{i=1}^{B} \hat{f}_{i}(x)-\frac{1}{B} \sum_{i=1}^{B} \mathbb{E} \hat{f}_{i}(x)\right)^{2} \\ &=\mathbb{E}\left(\frac{1}{B} \sum_{i=1}^{B}\left(\hat{f}_{i}(x)-\mathbb{E} \hat{f}_{i}(x)\right)\right)^{2} \\ &=\frac{1}{B^{2}} \sum_{i=1}^{B} \mathbb{V}\left\{\hat{f}_{i}(x)\right\}+\frac{1}{B^{2}} \sum \sum_{i \neq j} \operatorname{Cov}\left\{\hat{f}_{i}(x), \hat{f}_{j}(x)\right\} \end{aligned} $$ Say that all the predictors variances are roughly equal to $\sigma^{2}$ and predictors are almost "independent" so that the covariances are all $\approx 0$, then the aggregated variance above is roughly equal to: $$ \frac{\sigma^{2}}{B}.$$

Thus, we are able to reduce variance of the predictor significantly while affecting the bias only a little. However, this work if and only if covariances are almost $0$; this is why in random forests we use bootstrap and subsample the covariates. This makes trees in the forests weakly correlated in two ways:

  • bootstrap produces independent samples to train predictors on independent information;
  • feature sampling provide yet another way to train predictors using different information.

Things don't go well if predictors are strongly correlated: see Hastie et al. (2009) Element of Statistical Learning, pp 597 - 601 (Analysis of Random Forests).

Of course, in reality biases and covariances are not exactly $0$, but the idea still applies: gain on variance more than what you loose on bias.


Bias/variance equations were adapted from Lecture Notes by Prof. Joachim M. Bhumann (ETH), who also cites a paper from Bhulmann and Yu 1999 for further details on why Bagging works.

$\endgroup$
2
  • $\begingroup$ This is a nice answer, thank you! I have to go through the details in time but I think I got the idea already. Just a follow-up question: When the covariances are almost 0, are they still called "weakly correlated"? I would have said "almost non-correlated". And, tbh, I can't identify exactly how the $ \frac{\sigma^2}{B} $ term is constructed? $\endgroup$
    – Ben
    Commented Aug 10, 2021 at 6:49
  • 1
    $\begingroup$ AFAIK, "weakly correlated" or "almost non-correlated" are non-technical terms (i.e. they do not signify that the correlation falls in a given interval). So you can use the one you think better expresses what you have in mind. In any case, you will have to be more specific when you want to make any formal statement. About the variance term, for illustration purposes it is assumed $\mathbb{V}(f_i(x)) = \sigma^2$ for all $i$; sum over $i=1\ldots B$ and divide by $B^2$ obtaining $\frac{\sigma^2}{B}$. Covariances are (almost) all 0; neglect them. Expectations are over the training samples distrib. $\endgroup$
    – lcorag
    Commented Aug 10, 2021 at 8:05

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