Tree Correlation And Ensemble Variance

Why Tree Correlation Matters

Averaging predictions from many trees can make a forest more stable than an individual tree. But the benefit depends not only on the number of trees: it also depends on whether their prediction errors tend to move together. If all trees make similar errors on the same cases, averaging them cannot remove much of that shared error.

The result in this tutorial quantifies that trade-off. It concerns the variance of the averaged prediction at a fixed predictor value, arising from the randomness in fitting or generating the trees. It does not, by itself, measure every source of error in predicting a future outcome.

Definition: At a fixed predictor value $x$, let $\hat f_b(x)$ be the prediction from tree $b$, where $b=1,\ldots,B$. Treat the fitted tree prediction as a random quantity because the training sample, bootstrap sample, or tree-building randomness can vary. Define the tree prediction error relative to the conditional mean $f(x)=E[Y\mid X=x]$ by $e_b(x)=\hat f_b(x)-f(x)$. The averaged forest prediction is $\bar f_B(x)=B^{-1}\sum_{b=1}^{B}\hat f_b(x)$, and its error is $\bar e_B(x)=B^{-1}\sum_{b=1}^{B}e_b(x)$.

The covariance calculation is conditional on the same fixed $x$. In the equal-tree case, suppose each error has variance $\sigma^2$, and every distinct pair of tree errors has the same correlation $\rho$. Thus, for $b\ne c$, $\operatorname{Cov}(e_b,e_c)=\rho\sigma^2$. These are simplifying assumptions: real forests can have different tree variances and different pairwise correlations.

Deriving the Equal-Tree Formula

The variance of a sum is the sum of the individual variances plus twice the sum of the distinct pairwise covariances. Applying that identity to the average gives the central result.

\begin{aligned} \operatorname{Var}(\bar e_B) &=\operatorname{Var}\left(\frac{1}{B}\sum_{b=1}^{B} e_b\right)\\ &=\frac{1}{B^2}\left\{\sum_{b=1}^{B}\operatorname{Var}(e_b) +2\sum_{1\le b<c\le B}\operatorname{Cov}(e_b,e_c)\right\}\\ &=\frac{1}{B^2}\left\{B\sigma^2+2\binom{B}{2}\rho\sigma^2\right\}\\ &=\frac{1}{B^2}\left\{B\sigma^2+B(B-1)\rho\sigma^2\right\}\\ &=\sigma^2\left(\rho+\frac{1-\rho}{B}\right). \end{aligned}

The key count is $\binom{B}{2}=B(B-1)/2$: there are that many distinct pairs, and each covariance appears twice in the expansion of the variance of a sum. Dividing the sum by $B^2$ then produces the formula. This derivation also explains why it is not enough to divide a single-tree variance by $B$ unless the tree errors are uncorrelated.

Theorem: If $B$ tree errors have common variance $\sigma^2$ and common pairwise correlation $\rho$, then the averaged prediction error has variance $\sigma^2\left(\rho+(1-\rho)/B\right)$. The formula applies under those equal-variance and equal-correlation assumptions. It is not a general formula for trees with arbitrary covariance structure.

The two terms have distinct interpretations. The term $\sigma^2(1-\rho)/B$ decreases as the number of trees increases. The term $\rho\sigma^2$ does not decrease with $B$, so for positive $\rho$ it is a variance floor under this model. When $\rho=0$, the result reduces to $\sigma^2/B$. If $\rho=1$, all errors are perfectly correlated and the average has variance $\sigma^2$, no matter how many trees are averaged.

For an equicorrelation model with $B>1$, the covariance matrix must be valid, which requires $-1/(B-1)\le \rho\le 1$. In applications, tree errors are often positively correlated. A fixed negative $\rho$ cannot be held constant for arbitrarily large $B$, because it would eventually violate this constraint.

Worked Examples

Worked Example: Comparing Forest Sizes at a Fixed Correlation

At a particular predictor profile, suppose each tree's prediction error relative to the conditional mean has standard deviation $\$10$, and the pairwise error correlation is $0.20$. Find the variance and standard deviation of the average prediction from 25 trees. Compare its variance with that from a single tree. Treat the predictions as dollar amounts.

Method. Use the equal-variance, equal-correlation formula. First, the single-tree variance is $\sigma^2=10^2=100$ dollars squared.

For $B=25$ and $\rho=0.20$,

\begin{aligned} \operatorname{Var}(\bar e_{25}) &=100\left(0.20+\frac{1-0.20}{25}\right)\\ &=100\left(0.20+\frac{0.80}{25}\right)\\ &=100(0.20+0.032)\\ &=100(0.232)\\ &=23.2\text{ dollars}^2. \end{aligned}

The standard deviation is $\sqrt{23.2}=\$4.8166\ldots$, or $\$4.82$ to the nearest cent. A single tree has variance $100$ dollars squared, so averaging reduces the variance by $100-23.2=76.8$ dollars squared, a reduction of $76.8/100=0.768$, or 76.8%.

As a check, the variance is less than the single-tree variance and greater than the positive-correlation floor $100(0.20)=20$ dollars squared. The calculation avoids the common mistake of treating the trees as independent and reporting $100/25=4$ dollars squared.

Worked Example: Finding the Minimum Number of Trees

For a hypothetical pricing model, suppose the variance of an individual tree's prediction error at a specified profile is $100$ units squared and the pairwise error correlation is $0.10$. How many trees are required for the averaged prediction variance to be no more than $18$ units squared?

Method. Substitute the target bound into the equal-tree formula and solve for the integer $B$. The correlation component alone contributes $100(0.10)=10$ units squared, so a target of $18$ is above the limiting floor and can be reached.

\begin{aligned} 100\left(0.10+\frac{0.90}{B}\right)&\le 18\\ 0.10+\frac{0.90}{B}&\le 0.18\\ \frac{0.90}{B}&\le 0.08\\ B&\ge \frac{0.90}{0.08}=11.25. \end{aligned}

Since the number of trees must be a whole number, the minimum is $B=12$. Check both neighboring integers:

\begin{aligned} \operatorname{Var}(\bar e_{12}) &=100\left(0.10+\frac{0.90}{12}\right) =100(0.10+0.075) =17.5,\\ \operatorname{Var}(\bar e_{11}) &=100\left(0.10+\frac{0.90}{11}\right) =100(0.181818\ldots) \approx18.1818. \end{aligned}

Thus 12 trees meet the target and 11 do not. The common mistake is to round $11.25$ down; a minimum-count requirement calls for rounding up, followed by a direct check.

Worked Example: Unequal Tree Variances and Correlations

At a fixed profile, three hypothetical trees have prediction-error standard deviations of $2$, $3$, and $4$ cost units. The error correlations for tree pairs $(1,2)$, $(1,3)$, and $(2,3)$ are $0.50$, $0.25$, and $0.10$, respectively. Calculate the variance of their equally weighted average.

Method. Because the variances and correlations are not all equal, calculate each covariance separately and use the general variance-of-a-sum identity. The individual variances are $2^2=4$, $3^2=9$, and $4^2=16$, for a total of $29$.

For each pair, covariance equals correlation multiplied by the two standard deviations:

\begin{aligned} \operatorname{Cov}(e_1,e_2)&=0.50(2)(3)=3,\\ \operatorname{Cov}(e_1,e_3)&=0.25(2)(4)=2,\\ \operatorname{Cov}(e_2,e_3)&=0.10(3)(4)=1.2. \end{aligned}

The variance of the sum is the total individual variance plus twice the sum of the three covariances. Divide by $3^2$ to obtain the variance of the average:

\begin{aligned} \operatorname{Var}(\bar e_3) &=\frac{4+9+16+2(3+2+1.2)}{9}\\ &=\frac{29+12.4}{9}\\ &=\frac{41.4}{9}\\ &=4.6\text{ cost units}^2. \end{aligned}

As a check, ignoring covariance would give $29/9\approx3.2222$, which is too small because all three pairwise covariances are positive. The equal-correlation shortcut is not appropriate here; using each covariance explicitly avoids imposing a structure the data do not have.

What the Variance Floor Does—and Does Not—Mean

The formula separates the influence of forest size from the influence of dependence among tree errors. For example, when $\rho=0.20$, even an arbitrarily large $B$ leaves a limiting variance of $0.20\sigma^2$ under the equal-correlation model. Adding trees reduces the remaining averaging component, but cannot average away the errors that move together.

This is a statement about variance, not a guarantee that the forest's overall predictive performance improves by a particular amount. The formula does not account for bias, and it does not establish that the tree errors actually have equal variance or equal correlation. If a future outcome $Y$ has conditional variance $\operatorname{Var}(Y\mid X=x)$ and is independent of the forest-fitting randomness, the conditional mean squared prediction error decomposes as

E[(\bar f_B(x)-Y)^2\mid X=x] = \operatorname{Var}(\bar f_B(x)) + \left(E[\bar f_B(x)]-f(x)\right)^2 + \operatorname{Var}(Y\mid X=x).

The first term is the forest prediction variance studied here, the second is squared bias relative to $f(x)$, and the third is outcome variation that remains even if the conditional mean were known. Therefore, a lower ensemble variance is not by itself proof of lower total prediction error.

Common Exam Traps

Assuming independence without checking. Using $\sigma^2/B$ silently assumes $\rho=0$. With positive correlation, that calculation understates the variance.
Forgetting the covariance pairs. There are $B(B-1)/2$ distinct pairs, and their covariances enter the variance expansion twice.
Confusing correlation with covariance. Correlation is dimensionless. To obtain covariance for unequal standard deviations, use $\operatorname{Cov}(e_b,e_c)=\rho_{bc}\sigma_b\sigma_c$.
Calling the floor a universal limit. The limit $\rho\sigma^2$ follows from the equal-variance, equal-correlation assumptions with fixed positive $\rho$. It need not describe a forest with varying covariances.
Equating variance with total prediction error. Bias and irreducible response variation are not included in the ensemble-variance formula.

Key takeaway: Under common tree-error variance $\sigma^2$ and common pairwise correlation $\rho$, the variance of the averaged prediction is $\sigma^2\left(\rho+(1-\rho)/B\right)$. More trees reduce the part that can be averaged away; positive correlation determines the remaining floor.

Check Your Understanding

For each problem, state the relevant assumptions and calculate the requested quantity.

At a fixed profile, tree prediction errors have variance $64$ and common pairwise correlation $0.25$. Find the variance of the average of 16 trees. (Answer: $19$ units squared)
A forest has 20 trees. Each tree's prediction-error standard deviation is $8$, and the common pairwise correlation is $0.10$. Find the variance of the averaged prediction. (Answer: $9.28$ units squared)
Individual tree-error variance is $100$, and common pairwise correlation is $0.10$. Find the smallest number of trees for which the averaged prediction variance is at most $18$. (Answer: 12 trees)
Three tree-error standard deviations are $2$, $3$, and $4$. Their pairwise correlations for pairs $(1,2)$, $(1,3)$, and $(2,3)$ are $0.20$, $0$, and $0.50$. Find the variance of the equally weighted average, rounding to four decimal places. (Answer: $4.8222$ units squared)
Under the equal-variance, equal-correlation assumptions, each tree-error variance is $81$ and pairwise correlation is $0.12$. What variance does the averaged prediction approach as the number of trees tends to infinity? (Answer: $9.72$ units squared)

What You'll Learn