Why Bagging Reduces Prediction Variance

Why Average Predictions From Many Trees?

A fitted tree can change substantially when its training data change. A small change in the data may alter a split, which changes the observations in descendant nodes and can lead to different predictions. This sensitivity is one reason an individual tree can have high prediction variance. Bagging addresses it by fitting trees to bootstrap samples and averaging their predictions.

The key qualification is that the trees must not make exactly the same prediction errors. If each tree repeats the same error, averaging leaves that error unchanged. If their errors vary and are not perfectly aligned, averaging can make the ensemble prediction more stable. The reduction depends both on the number of trees and on how strongly their prediction errors move together.

For the usual variance calculation, assume the \(B\) tree predictions at \(x\) have a common variance \(\sigma^2\), and every distinct pair has the same correlation \(\rho\). These are simplifying assumptions, not requirements of bagging itself. They let us isolate the effect of averaging. In applications, tree variances and pairwise correlations need not be identical.

The correlation here is the correlation between prediction errors across repeated fits, at the same \(x\). It is not the correlation between two predictors in the data, nor the correlation between predictions at two different values of \(x\). If the trees have a common mean prediction, correlating their predictions is equivalent to correlating their centered prediction errors.

The Variance of an Average

The general variance identity for a sum includes both each prediction’s variance and every pairwise covariance. Under the equal-variance, equal-correlation assumptions, each pair has covariance \(\rho\sigma^2\). Dividing the sum by \(B\) gives the variance of the average:

The first term inside the parentheses, \(\rho\), represents the variance that averaging cannot remove under this model. The second term, \((1-\rho)/B\), shrinks as the number of trees increases. A single tree has variance \(\sigma^2\); for \(B>1\), the ensemble variance is smaller when \(\rho<1\). When \(\rho=1\), the trees move together perfectly, so the average has the same variance as one tree.

For a valid equal-correlation covariance structure, \(\rho\) cannot be arbitrary: it must satisfy \(-1/(B-1)\leq \rho\leq 1\). In common tree-ensemble settings, the correlation is typically nonnegative. With \(\rho=0\), the formula reduces to \(\sigma^2/B\), the variance of an average of independent, equally variable predictions.

Why the Formula Holds

The derivation follows from expanding the variance of a sum. For any random variables \(Z_1,\ldots,Z_B\),

There are \(B\) individual variance terms, each equal to \(\sigma^2\). There are \(B(B-1)/2\) distinct pairs, each with covariance \(\rho\sigma^2\); the factor of 2 in the identity counts each pair in both orders. Thus the covariance contribution is \(B(B-1)\rho\sigma^2\). Since the ensemble prediction divides the sum by \(B\), its variance divides by \(B^2\). Combining those terms yields the displayed result. This argument depends on the equal-variance and equal-correlation assumptions; without them, retain the individual variances and covariances rather than using the simplified expression.

Worked Calculations

What Bagging Does and Does Not Reduce

A bootstrap sample is formed by drawing observations with replacement from the available training data. Fitting a tree to each resample creates a collection of predictions that can differ at the same \(x\). Averaging those predictions smooths some of the variation across fits. The formula explains why the gain depends on both the variability of individual trees and their error correlation.

Be precise about the source of randomness. If the original training data are held fixed and each tree is fitted using an independently generated bootstrap resample, then, for a deterministic fitting procedure, the fits are independent conditional on those fixed data. Under that conditional calculation, their covariance is zero and the bootstrap-randomness component of the average’s variance is \(\sigma^2/B\). Across repeated original training samples, however, all bootstrap fits are built from data that share the same original sample. Their predictions can consequently be correlated. The variance identity applies to whichever randomness is being analyzed, but the variance and correlation must be defined over that same distribution of repeated fits.

Bagging directly changes the variability of the prediction by averaging. It does not, by averaging alone, guarantee that the expected prediction is closer to the target. If every tree has the same bias, the averaged prediction retains it. For a future response \(Y\), outcome noise also remains: even a prediction exactly equal to the conditional mean \(m(x)=\operatorname{E}[Y\mid X=x]\) cannot predict the random deviation of that future outcome from its mean. These are distinct contributions from the variance of fitted predictions.

The displayed formula concerns an arithmetic average of numerical predictions, as used for regression predictions or estimated class probabilities. It is not automatically a formula for the class label produced by majority vote. Converting probabilities or numerical predictions into a class label is a nonlinear operation, so the variance of the average does not directly give the error rate of that vote.

Common Exam Traps

• Assuming independence without being told to. The shortcut \(\sigma^2/B\) applies when the pairwise covariances are zero. With positive correlation, use \(\sigma^2\left(\rho+\frac{1-\rho}{B}\right)\).
• Dividing the correlation term by the number of trees. The shared component is \(\rho\sigma^2\), not \(\rho\sigma^2/B\). It remains in the limit as \(B\) increases.
• Confusing a variance reduction with a bias reduction. The variance formula alone does not say how close the expected prediction is to the target. For mean squared error, include squared bias.
• Leaving the randomness unspecified. State whether variance is across repeated training sets, bootstrap fits conditional on a fixed data set, or some other repeated-fitting procedure. The relevant covariance depends on that choice.
• Using the result for hard class labels without qualification. The formula is for averages of numerical predictions under its assumptions, not directly for majority-vote classification error.