Bagging and Random Forests

Average \(B\) estimators, each with variance \(\sigma^2\) and pairwise correlation \(\rho\), and the variance of the average is

The second term vanishes as \(B\) grows. The first does not. That formula is the whole theory of bagging in one line: adding trees buys you the second term for free, and everything interesting is a fight to reduce \(\rho\).

Bagging (bootstrap aggregating) fits each model on a bootstrap resample of the training data and averages the predictions (Breiman, 1996, Bagging Predictors, Machine Learning 24(2)). It reduces variance and leaves bias roughly unchanged, which is why it works spectacularly on deep unpruned trees, the highest-variance and lowest-bias models available, and does almost nothing for linear regression.

What the feature subsampling adds

Bootstrap resamples overlap heavily: each contains about 63.2% of the distinct original points, since \(P(\text{a given point is never drawn}) = (1 - 1/n)^n \to e^{-1} \approx 0.368\). Trees fit on such similar data make correlated errors, so \(\rho\) stays high and the floor term dominates.

Random forests attack \(\rho\) directly by choosing each split from a random subset of \(m\) features rather than all \(p\) (Breiman, 2001, Random Forests, Machine Learning 45(1)). If one feature dominates, plain bagged trees all split on it at the root and are near-identical; forcing most trees to consider it unavailable produces genuinely different structures. The usual defaults are \(m = \sqrt{p}\) for classification and \(p/3\) for regression, and \(m\) is the single most consequential hyperparameter: small \(m\) decorrelates more and raises individual-tree bias, large \(m\) approaches plain bagging.

Extremely randomised trees push further and also randomise the threshold within each chosen feature rather than optimising it, trading more bias for still lower correlation, and running substantially faster because no threshold sweep is needed.

Out-of-bag estimation

The 36.8% of points excluded from each bootstrap are out-of-bag for that tree. Predicting each training point using only the trees that did not see it yields a validation estimate at no extra cost, over the whole training set, without a held-out split. On a 10,000-row dataset that is a free, reasonably reliable generalisation estimate.

Two caveats matter. It is slightly pessimistic, since each point is scored by roughly a third of the forest rather than all of it. And it is invalid the moment there is any dependence structure the bootstrap does not respect, which includes time-ordered data and repeated measurements per entity.

When it breaks

More trees never overfit, and never help past a point either. Averaging more draws from the same distribution converges; the generalisation error flattens and stays flat. Beyond a few hundred trees you are buying inference latency and memory, not accuracy. The tuning knobs that matter are \(m\), minimum leaf size, and whether trees are grown fully.

Correlation has a floor set by the data. When a handful of features carry nearly all the signal, trees remain correlated no matter how you subsample, \(\rho\) stays high, and the variance reduction is modest. This is the regime where boosting, which reduces bias rather than variance, tends to win.

Probabilities are the vote share, and that is not a calibrated probability. Random forest predicted probabilities are systematically pushed away from 0 and 1, because achieving a 0.01 output requires nearly every tree to agree. Isotonic regression or Platt scaling on held-out data fixes it when the number is used for a threshold or an expected-value calculation.

Memory is the practical ceiling. 500 fully grown trees on a million rows can reach tens of thousands of nodes each. Unlike boosting, which typically uses shallow trees, a forest's individual models are deep by design, and the serialised model can reach gigabytes.

Imbalance survives averaging. If every tree predicts the majority class, so does the average. Balanced class weights or balanced bootstrap sampling per tree are the interventions; more trees are not.