Tree Correlation And The Bagging Variance Floor

Why Tree Correlation Matters

Bagging averages predictions from multiple trees fitted using resampled data. Averaging can reduce the variability of predictions, but the reduction depends not only on how many trees are included. It also depends on how similarly those trees behave. If their predictions tend to move together, averaging them leaves some shared variation in place.

The focus here is the variance of the ensemble prediction at a fixed input \(x\), with the observed training data held fixed. The randomness may come from the bootstrap samples used to fit the trees or from other random choices in fitting them. The same calculation can be applied to repeated training samples if the trees satisfy the assumptions below. It describes a variance component; it does not, by itself, measure all sources of uncertainty in a prediction.

Definition: Let \(T_b(x)\) be the prediction from tree \(b\) at input \(x\), for \(b=1,\ldots,B\). The bagged prediction is \(\bar T_B(x)=B^{-1}\sum_{b=1}^B T_b(x)\). For the standard equal-correlation calculation, assume that each tree prediction has the same variance \(\sigma_T^2\), and that every distinct pair of tree predictions has the same correlation \(\rho\). Thus \(\operatorname{Cov}(T_b(x),T_c(x))=\rho\sigma_T^2\) when \(b\ne c\).

The assumption of equal pairwise correlation is a simplifying model, not a claim that every pair of fitted trees in practice has exactly the same correlation. It gives a useful way to isolate two effects: the number of trees, \(B\), and their shared dependence, \(\rho\). In this tutorial, \(\sigma_T^2\) and \(\rho\) refer to variation across the tree-fitting randomness at the fixed input \(x\).

Deriving the Bagging Variance Formula

The variance of a sum includes both the individual variances and the covariances between distinct terms. With \(B\) trees there are \(B\) individual variance terms, but \(B(B-1)\) ordered covariance terms in the expansion of the variance of the sum. Dividing by \(B^2\) gives the variance of the average.

Write the average as a scaled sum.
\(\bar T_B(x)=B^{-1}\sum_{b=1}^B T_b(x)\), so \(\operatorname{Var}(\bar T_B(x))=B^{-2}\operatorname{Var}(\sum_{b=1}^B T_b(x))\).

Expand the variance of the sum.
There are \(B\) terms with variance \(\sigma_T^2\) and \(B(B-1)\) ordered distinct-pair covariance terms, each equal to \(\rho\sigma_T^2\).

Divide by \(B^2\) and simplify.
The resulting variance separates into a correlation component and a component that decreases as the number of trees grows.

\begin{aligned} \operatorname{Var}(\bar T_B(x)) &=\frac{1}{B^2}\left[B\sigma_T^2+B(B-1)\rho\sigma_T^2\right]\\ &=\sigma_T^2\left(\frac{1}{B}+\frac{B-1}{B}\rho\right)\\ &=\sigma_T^2\left(\rho+\frac{1-\rho}{B}\right). \end{aligned}

Theorem: Under the equal-variance and equal-pairwise-correlation assumptions, the variance of the average of \(B\) tree predictions is \(\sigma_T^2\left(\rho+(1-\rho)/B\right)\). This formula concerns the variance of the averaged prediction, not the variance of an individual tree.

The calculation also explains why independence is a special case. If \(\rho=0\), the trees have zero pairwise covariance and the variance is \(\sigma_T^2/B\). If the predictions are perfectly correlated, \(\rho=1\), the formula gives \(\sigma_T^2\): averaging does not reduce their shared variation. For positive \(\rho\), the variance approaches \(\rho\sigma_T^2\) as \(B\) increases. This positive limiting value is the variance floor.

The floor is a limit, not necessarily the variance at any finite number of trees. For \(0<\rho<1\), each finite \(B\) leaves an additional term, \(\sigma_T^2(1-\rho)/B\), above the limit. If \(\rho=0\), there is no positive floor in this model. The equal-correlation assumptions also constrain \(\rho\): for a group of \(B\) variables with common variance and common pairwise correlation, \(\rho\) cannot be less than \(-1/(B-1)\). In applications of bagged trees, positive correlation is the usual concern.

Worked Examples

Worked Example: Variance With a Given Number of Trees

At a fixed hypothetical risk profile, suppose the variance of a randomly fitted tree’s regression prediction is \(100\) squared prediction units, and the pairwise correlation between tree predictions is \(0.25\). A bagged model averages \(16\) trees. Calculate the ensemble prediction variance and compare it with the limiting variance as the number of trees grows.

Method and assumptions. Use the equal-variance, equal-correlation formula with \(\sigma_T^2=100\), \(\rho=0.25\), and \(B=16\). The common prediction scale is held fixed across trees.

Finite ensemble variance. Substitute the values:

\begin{aligned} \operatorname{Var}(\bar T_{16}(x)) &=100\left(0.25+\frac{1-0.25}{16}\right)\\ &=100\left(0.25+\frac{0.75}{16}\right)\\ &=100(0.25+0.046875)\\ &=100(0.296875)\\ &=29.6875. \end{aligned}

As a check using the unsimplified expansion, the \(16\) individual variance terms sum to \(16(100)=1{,}600\). The \(16(15)=240\) ordered covariance terms each equal \(0.25(100)=25\), for a covariance contribution of \(240(25)=6{,}000\). Thus the sum’s variance is \(1{,}600+6{,}000=7{,}600\); dividing by \(16^2=256\) gives \(7{,}600/256=29.6875\).

Limiting variance. As \(B\) grows without bound, the term \((1-\rho)/B\) tends to zero. The limit is \(100(0.25)=25\) squared prediction units. The variance at \(16\) trees is above this floor, as expected. The common mistake this calculation avoids is using the independent-tree result \(100/16=6.25\), which incorrectly discards the positive covariance between tree predictions.

Worked Example: Finding the Minimum Number of Trees

For a second hypothetical prediction task, each tree prediction has variance \(64\), and the pairwise correlation is \(0.10\). How many trees are needed for the variance of their average to be no more than \(12.8\)?

Method and assumptions. Apply the equal-correlation formula and solve the resulting inequality for the integer \(B\). The variance floor is \(64(0.10)=6.4\), so the target of \(12.8\) is above the limit and can be attainable.

\begin{aligned} 64\left(0.10+\frac{0.90}{B}\right)&\le 12.8\\ 6.4+\frac{57.6}{B}&\le 12.8\\ \frac{57.6}{B}&\le 6.4\\ B&\ge 9. \end{aligned}

Since the number of trees must be an integer, the minimum is \(9\). Check it directly: \(64(0.10+0.90/9)=64(0.10+0.10)=12.8\). With \(8\) trees, the variance would be \(64(0.10+0.90/8)=64(0.2125)=13.6\), which exceeds the target. The common mistake this calculation avoids is solving only for the decreasing term while forgetting the fixed floor of \(6.4\).

Worked Example: Comparing Two Correlation Levels

Suppose two hypothetical ensembles each average \(40\) trees, with individual prediction variance \(36\). Their pairwise correlations are \(0.30\) for Ensemble A and \(0.10\) for Ensemble B. Calculate both ensemble variances and their limiting variances.

Method and assumptions. The tree counts and individual variances are equal, so substitute each correlation into the same formula. This comparison isolates the effect of correlation; it does not assert how either correlation level was obtained.

For Ensemble A:

\begin{aligned} \operatorname{Var}(\bar T_{40,A}(x)) &=36\left(0.30+\frac{0.70}{40}\right)\\ &=36(0.30+0.0175)\\ &=36(0.3175)=11.43. \end{aligned}

Its limiting variance is \(36(0.30)=10.8\).

For Ensemble B:

\begin{aligned} \operatorname{Var}(\bar T_{40,B}(x)) &=36\left(0.10+\frac{0.90}{40}\right)\\ &=36(0.10+0.0225)\\ &=36(0.1225)=4.41. \end{aligned}

Its limiting variance is \(36(0.10)=3.6\). Both finite variances exceed their respective floors. Ensemble B has the smaller variance here because its lower correlation leaves less shared variation, even though both ensembles contain the same number of trees. The common mistake this calculation avoids is assuming that equal tree counts alone imply equal variance reduction.

Variance, Bias, and Prediction Error

A variance calculation should not be mistaken for a complete evaluation of prediction accuracy. Let \(f(x)\) be a fixed target value at input \(x\), and suppose each tree prediction has the same expected value \(\mu_T(x)\). Its bias at \(x\) is \(\mu_T(x)-f(x)\). Averaging predictions preserves that expected value:

E[\bar T_B(x)]=\frac{1}{B}\sum_{b=1}^B E[T_b(x)]=\mu_T(x).

Consequently, the ensemble does not change this shared bias merely by averaging. For a fixed target, its mean squared prediction error over the tree-fitting randomness is the squared bias plus the prediction variance:

E\left[(\bar T_B(x)-f(x))^2\right] = \left(\mu_T(x)-f(x)\right)^2+ \operatorname{Var}(\bar T_B(x)).

This identity follows by writing \(\bar T_B(x)-f(x)\) as \((\bar T_B(x)-E[\bar T_B(x)])+(E[\bar T_B(x)]-f(x))\). On squaring and taking expectations, the cross term is zero because \(E[\bar T_B(x)-E[\bar T_B(x)]]=0\). The identity is for a fixed target and this randomness; additional uncertainty in the target or data-generating process requires a broader error analysis.

When the Simple Formula Does Not Apply

The formula \(\sigma_T^2(\rho+(1-\rho)/B)\) requires equal marginal variances and a common pairwise correlation. If the tree predictions have different variances or correlations, use the general covariance expansion instead:

\operatorname{Var}(\bar T_B(x)) = \frac{1}{B^2} \left[ \sum_{b=1}^B \operatorname{Var}(T_b(x)) + 2\sum_{1\le b<c\le B}\operatorname{Cov}(T_b(x),T_c(x)) \right].

The second sum counts each unordered pair once and therefore has the factor \(2\). A further caution applies to classification: the formula applies directly to numerical tree outputs, such as estimated class probabilities, when the assumptions hold. A final class label formed by thresholding an averaged probability is a nonlinear transformation, so its variance is not given by this formula.

Common Exam Traps

Treating the trees as independent without being told they are. The independent formula \(\sigma_T^2/B\) is valid when pairwise covariance is zero. Positive correlation adds a shared component.
Calling the finite-\(B\) variance the floor. For positive \(\rho\), the floor is the limit \(\rho\sigma_T^2\); at finite \(B\), the additional term \(\sigma_T^2(1-\rho)/B\) remains.
Confusing tree correlation with the number of trees. Increasing \(B\) reduces the \(1/B\) component, but does not remove the positive correlation component under this model.
Interpreting lower variance as guaranteed lower total error. Bias and any uncertainty not represented by the tree-fitting randomness are not removed by this variance calculation.

Key takeaway: Under equal tree variances and equal pairwise correlation, bagged prediction variance is \(\sigma_T^2\left(\rho+(1-\rho)/B\right)\). More trees reduce the finite-ensemble component, while positive correlation leaves a limiting variance of \(\rho\sigma_T^2\).

Check Your Understanding

For each problem, use the equal-variance, equal-correlation model at a fixed input unless stated otherwise.

Each tree prediction has variance \(49\), pairwise correlation \(0.20\), and the ensemble contains \(20\) trees. Find the variance of the averaged prediction. (Answer: \(11.76\))
Five trees have individual prediction variance \(25\) and pairwise correlation \(0\). Find the ensemble variance and state whether this is a positive-floor case. (Answer: variance \(5\); no positive variance floor)
An ensemble has \(10\) trees, individual prediction variance \(100\), and pairwise correlation \(0.40\). Find its variance and its limiting variance as the tree count increases. (Answer: variance \(46\); limiting variance \(40\))
An ensemble of \(5\) trees has individual prediction variance \(16\) and averaged prediction variance \(9\). Under the equal-correlation model, solve for the pairwise correlation. (Answer: \(0.4531\), to four decimal places)
Individual tree predictions have variance \(100\) and pairwise correlation \(0.05\). Find the smallest integer number of trees for which the ensemble variance is at most \(10\). Verify that one fewer tree fails the target. (Answer: \(19\) trees; \(19\) gives variance \(10\), while \(18\) gives approximately \(10.2778\))

What You'll Learn