Variance Reduction in Random Forests via Feature Subsampling

MediumClassical ML

Reported in interviews at Two Sigma

Problem statement

Consider an ensemble method that averages $B$ identically distributed (not independent) base predictors, each with variance $\sigma^2$ and pairwise correlation $\rho$.

  1. Show that the variance of the ensemble prediction $\hat{f}$ is:

$$\text{Var}(\hat{f}) = \rho \sigma^2 + \frac{(1 - \rho)}{B} \sigma^2$$

  1. In Random Forests, each tree is built using a random subset of $m$ candidate features at each split (out of $p$ total features). This feature subsampling reduces the pairwise correlation $\rho$ between trees. Suppose that in a simplified model, $\rho = \rho(m)$ is an increasing function of $m$ (i.e., fewer candidate features per split means less correlated trees), while the bias of each individual tree increases as $m$ decreases (because each tree sees fewer features and fits a weaker model).

Explain the variance-bias tradeoff as $m$ varies from $1$ to $p$, and describe a principled method for choosing $m$ that minimizes an oracle estimate of test MSE.

Show hint

How do you expand the variance of a sum of random variables that are not independent?

Relevant roles: ML Engineer, Applied Scientist, Data Scientist and Research Scientist.

Related free problems