Why decorrelating the trees helps

Section of Ensembles, random forests, and boosting, part of Statistical learning

Type	Section
Taught in	Ensembles, random forests, and boosting
Part	Statistical learning

The diversity term said that disagreement helps. The variance of an average says the same thing with a correlation. Suppose the T tree predictions at a fixed x each have variance \sigma^2 and every pair has correlation \rho. Expand the variance of the sum, using \operatorname{Var}(f_t)=\sigma^2 and \operatorname{Cov}(f_t,f_s)=\rho\sigma^2 for t\ne s. There are T variance terms and T(T-1) covariance terms:

\begin{align*} \operatorname{Var}\Biggl(\frac1T\sum_{t=1}^T f_t\Biggr) &=\frac{1}{T^2}\Bigl(T\sigma^2+T(T-1)\rho\sigma^2\Bigr)\\ &=\frac{\sigma^2}{T}\bigl(1+(T-1)\rho\bigr)\\ &=\rho\sigma^2+\frac{1-\rho}{T}\sigma^2. \end{align*}

Adding trees shrinks only the second term. The first term, \rho\sigma^2, is a floor set by the correlation between trees, and no number of additional copies of a highly correlated tree will remove it. The calculation assumes a common variance and a common pairwise correlation. It does not assume normality. Bootstrap samples reduce \rho somewhat, because each tree misses a different third of the cases: the omission probability (1-1/n)^n tends to e^{-1}\approx 0.368. Restricting each split to k random variables reduces \rho much more, because the trees are then forbidden from always cutting on the same strongest predictor. That reduction in \rho is the quantitative form of the diversity term. The reason to randomise the candidate predictors is to lower the floor, not to improve any one tree.

Why decorrelating the trees helps

Used in

See also