Variance of an average

Topic: Ensembles, random forests, and boosting · more questions on this topic
‹ The error decomposition Out-of-bag counts ›

For T predictors with common variance \sigma^2 and common pairwise correlation \rho, derive

\operatorname{Var}(\bar f)=\rho\sigma^2+\frac{1-\rho}{T}\sigma^2.

Evaluate it for \rho=0.3, T=100 and for \rho=0.8, T=100. Why do random feature subsets help?

Worked answer (click to show)

There are T variance terms and T(T-1) covariance terms:

\begin{align*} \operatorname{Var}(\bar f) &=\frac{1}{T^2}\Biggl(\sum_t\operatorname{Var}(f_t)+\sum_{s\ne t}\operatorname{Cov}(f_s,f_t)\Biggr)\\ &=\frac{1}{T^2}\bigl(T\sigma^2+T(T-1)\rho\sigma^2\bigr)\\ &=\rho\sigma^2+\frac{1-\rho}{T}\sigma^2. \end{align*}

For \rho=0.3 and T=100, the variance is 0.3+0.007=0.307\,\sigma^2. For \rho=0.8 it is 0.8+0.002=0.802\,\sigma^2. Adding trees removes only the (1-\rho)\sigma^2/T term. The floor \rho\sigma^2 is reduced only by making the trees less correlated, which is why the candidate predictors at a split are randomised. Whether bootstrap samples or random feature subsets reduce correlation, and what they do to individual bias and variance, depends on the data and on the base learner.