45.08.05 · mathematical-statistics / 08-learning-methods

Bagging and Random Forests

shipped3 tiersLean: none

Anchor (Master): Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §15.3-15.4 (variance of an average of correlated trees, variable importance, the random-forest kernel and proximities); Breiman 2001 Machine Learning 45 (the $c / s^{2}$ generalisation-error bound via strength and correlation); Scornet, Biau & Vert 2015 Annals of Statistics 43 (consistency of Breiman's random forests in the additive-regression model)

Intuition Beginner

A single decision tree is sharp but jumpy. Change a handful of training cases and the tree can redraw itself from the top down, giving quite different predictions. That jumpiness is the price trees pay for being so flexible. The idea behind bagging is simple: if one tree is noisy, grow many trees on slightly different versions of the data and average their answers. The average of many noisy guesses is steadier than any single guess, the same way the average of many thermometer readings is closer to the true temperature than one reading.

Where do the slightly different versions of the data come from? You make them by resampling. Take your training set and draw a new set of the same size by picking cases at random, with replacement, so some cases appear twice and some not at all. Each resample grows its own tree. This trick is called the bootstrap, and aggregating the trees grown on bootstrap samples is "bootstrap aggregating", shortened to bagging.

Random forests add one more twist. Plain bagged trees still look alike, because they are grown on almost the same data and tend to pick the same strong feature for the top split. Trees that agree do not help much when you average them. So a random forest hides most of the features from each split: at every split it lets the tree choose only from a small random handful of features. This forces different trees to use different features, makes them disagree more, and that disagreement is exactly what makes the average better.

The payoff is a method you can hand almost any table of data and get a strong prediction with little tuning. Forests rarely embarrass themselves, which is why they are a favourite first thing to try.

Visual Beginner

Picture the same training table copied many times, each copy reshuffled by drawing rows with replacement. Each copy grows one tree. To predict, you run a new case down every tree and average the answers.

Method	What changes between trees	How much trees agree	What averaging buys
One tree	nothing — there is one	not applicable	nothing; you live with its jumpiness
Bagging	the bootstrap resample	a lot (trees look alike)	removes some jumpiness
Random forest	resample plus random features per split	less (trees disagree more)	removes more jumpiness

Reading the table top to bottom: each step makes the trees more different from one another, and more different trees give a steadier average.

Worked example Beginner

We average three trees on a single new house and watch the variance shrink. Suppose the true price is 300 (thousand dollars). Each individual tree, over the randomness of its resample, predicts a value that scatters around 300 with a spread we summarise by a variance of 90.

First, the unhelpful case: three identical trees. If every tree always gives the same number, averaging three of them gives that same number, so the variance stays 90. Identical predictors teach us nothing new by averaging.

Now three trees that move together only partly. Say any two of them have a correlation of 0.5. The variance of the average of three such trees works out from the rule "variance of an average equals the correlated part plus the leftover part divided by how many you average". The correlated part is $0.5 \times 90 = 45$ . The leftover part is $(1 - 0.5) \times 90 = 45$ , and dividing by 3 gives 15. So the average has variance $45 + 15 = 60$ .

Finally, three trees that barely move together, correlation 0.1. Correlated part $0.1 \times 90 = 9$ ; leftover $(1 - 0.1) \times 90 = 81$ , divided by 3 is 27; total $9 + 27 = 36$ .

Lining them up: variance 90 for one tree (or many identical trees), 60 when trees correlate at 0.5, and 36 when they correlate at 0.1. What this tells us: averaging helps, and it helps far more when the trees disagree. Lowering the correlation from 0.5 to 0.1 cut the variance almost in half. That is the whole reason random forests scramble the features.

Check your understanding Beginner

Exercise (easy, multiple choice).

Why does a random forest let each split choose from only a small random subset of the features?

A. To make each tree faster to grow and nothing more.

B. To force the trees to differ from one another, so averaging them removes more variance.

C. To guarantee every feature is used the same number of times.

D. To make the forest behave exactly like a single deep tree.

Hint

Averaging helps most when the things you average disagree. What makes bagged trees disagree more?

Answer

B. Hiding most features at each split stops every tree from leaning on the same dominant feature, so the trees disagree more; averaging predictors that disagree cancels more of their noise. Feedback-correct: lower agreement between trees is the lever a forest pulls. Feedback-wrong: the subset trick is about de-correlating the trees, not about speed, fairness across features, or imitating one big tree.

Formal definition Intermediate+

Let $(X, Y)$ have a joint law on $X \times Y$ with $X \subseteq R^{p}$ , and let $L = {(x_{i}, y_{i})}_{i = 1}^{n}$ be a training sample drawn i.i.d. from it. A base learner is a procedure $L \mapsto \hat{f} (\cdot; L)$ returning a predictor; here the base learner is a CART regression or classification tree 45.08.04.

Bootstrap sample. A bootstrap sample $L^{(b)}$ is obtained by drawing $n$ indices uniformly with replacement from ${1, \dots, n}$ and collecting the corresponding cases. Equivalently, $L^{(b)}$ is governed by a multinomial count vector $(N_{1}, \dots, N_{n})$ with $\sum_{i} N_{i} = n$ and each $N_{i} \sim Binomial (n, 1/ n)$ . The probability that case $i$ is omitted from a single bootstrap sample is $(1 - 1/ n)^{n} \to e^{- 1} \approx 0.368$ ; the omitted cases are the out-of-bag (OOB) cases for that sample.

Bagging. Draw $B$ bootstrap samples $L^{(1)}, \dots, L^{(B)}$ , fit a base tree to each, and aggregate. For regression the bagged predictor is the average

\hat{f}_{bag} (x) = \frac{1}{B} b = 1 \sum B \hat{f} (x; L^{(b)}),

and for classification the aggregate is the plurality vote (or, when class-probability estimates are averaged, the $ar g max$ of the averaged class proportions).

Random forest. A random forest replaces each bootstrap-fitted tree by a tree fitted with an extra source of randomness $Θ_{b}$ , an i.i.d. random vector independent across trees that, at every node, restricts the search for the best split to a random subset of $m \leq p$ of the predictors (the mtry parameter). Writing $h (x; Θ_{b})$ for the $b$ -th randomised tree (the resample is folded into $Θ_{b}$ ), the forest predictor is

\hat{f}_{rf} (x) = \frac{1}{B} b = 1 \sum B h (x; Θ_{b}) (regression), \hat{f}_{rf} (x) = majority - vote_{b} h (x; Θ_{b}) (classification) .

Plain bagging is the special case $m = p$ . The default $m$ is commonly $⌊ p /3 ⌋$ (regression) or $⌊ p ⌋$ (classification); $m$ controls a trade between individual tree strength (larger $m$ , more accurate single trees) and inter-tree correlation (smaller $m$ , more de-correlation).

Out-of-bag prediction and error. For each case $i$ , let $B_{i} = {b : i \in / L^{(b)}}$ be the bootstrap samples that omit it. The OOB prediction averages only those trees, $\hat{f}^{oob} (x_{i}) = \frac{1}{∣ B _{i} ∣} \sum_{b \in B_{i}} h (x_{i}; Θ_{b})$ , and the OOB error is the empirical risk of these predictions, $Err^{oob} = \frac{1}{n} \sum_{i = 1}^{n} L (y_{i}, \hat{f}^{oob} (x_{i}))$ , a nearly unbiased estimate of test error obtained without a separate validation set.

Variable importance. Two measures are standard. The Gini (split-improvement) importance of predictor $j$ sums, over all nodes that split on $j$ across all trees, the impurity reduction $Δ i$ achieved there 45.08.04. The permutation importance of $j$ is the increase in OOB error when the values of $X^{(j)}$ are randomly permuted among the OOB cases, breaking the association between $X^{(j)}$ and $Y$ while preserving its marginal distribution.

The notation here — $\hat{f} (\cdot; L)$ for a base learner, $L^{(b)}$ for a bootstrap sample, $Θ_{b}$ for the tree-randomising vector, $m$ for the split-subset size, $ρ$ for inter-tree correlation — is recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"Bagging reduces bias as well as variance." The bagged predictor is an average of identically distributed trees, so its expectation equals the expectation of one tree: bagging leaves the bias of the base learner essentially unchanged and acts almost purely on the variance. (Random forests can slightly raise bias, because restricting splits to $m < p$ features makes each tree a little worse; the net effect is favourable because the correlation drops faster.) The method is therefore wasted on a low-variance, high-bias learner such as a linear model.
"More trees can overfit, so $B$ must be tuned like a complexity parameter." The forest predictor converges almost surely as $B \to \infty$ (the trees are i.i.d. given the data), so adding trees only reduces Monte-Carlo noise in the average and never increases generalisation error; $B$ is a budget, not a regularisation knob. Complexity is controlled by tree depth and by $m$ , not by $B$ .
"OOB error needs a held-out set to be honest." Each OOB prediction for case $i$ uses only trees that never saw $i$ , so the OOB error is already an out-of-sample estimate; no separate validation split is required, and OOB error closely tracks $K$ -fold cross-validation error in practice.

Key theorem with proof Intermediate+

The central quantitative fact is the variance of an average of correlated trees. It explains in one line why bagging helps unstable learners, why a correlation floor caps the gain, and why random forests target that floor.

Theorem (variance of an average of correlated predictors). Let $T_{1}, \dots, T_{B}$ be identically distributed real predictions at a fixed point, each with variance $σ^{2} = Var (T_{b})$ and pairwise correlation $ρ = Corr (T_{b}, T_{b^{'}})$ for $b \neq = b^{'}$ . Then the average $\overset{ˉ}{T} = \frac{1}{B} \sum_{b = 1}^{B} T_{b}$ has

Var (\overset{ˉ}{T}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2} .

In particular $Var (\overset{ˉ}{T}) \to ρ σ^{2}$ as $B \to \infty$ , a floor set by the correlation alone. ^{[Hastie 2009]}

Proof. By bilinearity of covariance,

Var (\overset{ˉ}{T}) = \frac{1}{B ^{2}} Var (b = 1 \sum B T_{b}) = \frac{1}{B ^{2}} (b = 1 \sum B Var (T_{b}) + b \neq = b^{'} \sum Cov (T_{b}, T_{b^{'}})) .

Each variance is $σ^{2}$ , contributing $B σ^{2}$ . Each of the $B (B - 1)$ ordered off-diagonal covariances equals $Cov (T_{b}, T_{b^{'}}) = ρ σ^{2}$ by the definition of correlation for identically distributed variables. Hence

Var (\overset{ˉ}{T}) = \frac{1}{B ^{2}} (B σ^{2} + B (B - 1) ρ σ^{2}) = \frac{σ ^{2}}{B} + \frac{B - 1}{B} ρ σ^{2} = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2},

where the last equality regroups $\frac{1}{B} σ^{2} + \frac{B - 1}{B} ρ σ^{2} = ρ σ^{2} + \frac{1}{B} (1 - ρ) σ^{2}$ . As $B \to \infty$ the second term vanishes and $Var (\overset{ˉ}{T}) \to ρ σ^{2}$ . $□$

Bridge. This identity is the foundational reason ensembling works and the precise design brief for random forests. The second term, $\frac{1 - ρ}{B} σ^{2}$ , is the part averaging removes for free as $B$ grows — this is exactly what plain bagging exploits, since independent-looking resamples shrink it toward zero. The first term, $ρ σ^{2}$ , is a floor that no number of trees can lower; the only way past it is to lower $ρ$ , and that is the central insight behind random feature subsampling, which de-correlates the trees by forbidding them to all key on the same dominant predictor. The formula generalises the elementary $σ^{2} / B$ variance of an average of independent draws — set $ρ = 0$ and the floor disappears. It builds toward the strength-and-correlation generalisation bound of the Advanced results, where Breiman recasts $ρ$ and $σ$ as a competition between keeping trees accurate and keeping them different, and it appears again in the consistency theory, where the same averaging that controls variance is what lets the forest's adaptive neighbourhoods concentrate on the regression function. Putting these together, the whole chapter's distinction between variance-reduction methods here and the bias-reduction method of boosting 45.08.06 is read straight off which term of an error decomposition each one moves.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Let $\hat{f} (x; L)$ be a base regression learner with $E_{L} [\hat{f} (x; L)] = μ (x)$ . The idealised bagged predictor averages over the resampling distribution, $\hat{f}_{ag} (x) = E_{L^{*}} [\hat{f} (x; L^{*})]$ . Using $E [Z^{2}] = (E Z)^{2} + Var (Z)$ , show that the squared-error of the idealised aggregate against a target $f (x)$ is at most the average squared-error of the base learner, with the gap equal to the base learner's variance.

Hint

Compare $E_{L^{*}} [(f - \hat{f} (x; L^{*}))^{2}]$ with $(f - E_{L^{*}} \hat{f})^{2}$ .

Answer

Write $Z = \hat{f} (x; L^{*})$ and $a = f (x)$ . Then $E_{L^{*}} [(a - Z)^{2}] = a^{2} - 2 a E Z + E [Z^{2}] = a^{2} - 2 a E Z + (E Z)^{2} + Var (Z) = (a - E Z)^{2} + Var (Z) = (a - \hat{f}_{ag} (x))^{2} + Var (Z)$ . Since $Var (Z) \geq 0$ , the aggregate's squared error $(a - \hat{f}_{ag})^{2}$ is no larger than the averaged base error, the gap being exactly the resampling variance $Var (Z)$ . This is Breiman's Jensen argument: bagging gains precisely what the base learner is unstable by, and gains nothing from a deterministic (zero-variance) learner. Rubric: full credit for the variance decomposition and the identification of the gap with the base learner's variance.

Exercise 5 (medium, short-answer).

Explain why permutation importance is computed on the out-of-bag cases rather than on the training cases used to grow the trees, and what the resulting importance of a feature means.

Hint

A tree memorises its training cases. What would permuting a feature look like on data the tree has already fit?

Answer

Permuting a feature and re-scoring on the training cases would understate the damage, because a deep tree has partly memorised those cases through other correlated features, so the loss barely moves and every feature looks unimportant. Scoring on OOB cases — cases a given tree never saw — measures genuine predictive reliance: for each tree, run its OOB cases down it once normally and once with feature $j$ shuffled, and record the rise in error. Averaging the rise over trees gives the permutation importance of $j$ , the average increase in generalisation error caused by destroying $j$ 's association with the response. A large value means the forest's accuracy depends on $j$ ; a value near zero means $j$ can be scrambled without harm. Rubric: full credit for the train-set memorisation point and for stating that the importance is the OOB-error increase from breaking the feature-response link.

Exercise 6 (hard, short-answer).

The mtry parameter $m$ trades individual tree strength against inter-tree correlation. Using the variance formula and the role of $m$ , explain why both very small $m$ and very large $m$ can be worse than an intermediate value for the variance of the forest's regression prediction.

Hint

As $m$ shrinks, $ρ$ falls but the single trees get worse, which can raise $σ^{2}$ (and bias). The floor is $ρ σ^{2}$ ; both factors move with $m$ .

Answer

For large $B$ the forest variance is governed by the floor $ρ σ^{2}$ . Increasing $m$ toward $p$ lets every split pick the globally best feature, so each tree is strong and stable (smaller $σ^{2}$ and lower bias) but the trees nearly always agree on the dominant splits, so $ρ$ is large — the forest approaches plain bagging and its variance floor stays high. Decreasing $m$ toward $1$ forces splits onto random features, sharply lowering $ρ$ , but the trees become weak and erratic, raising $σ^{2}$ and the bias of each tree. Because the floor is the product $ρ σ^{2}$ , pushing $m$ to either extreme inflates one factor while deflating the other, and the product is minimised at an intermediate $m$ ; the squared-bias contribution, which also grows as $m \to 1$ , reinforces an interior optimum. This is why $m$ is the one parameter usually worth tuning, with $⌊ p /3 ⌋$ and $⌊ p ⌋$ as robust defaults. Rubric: full credit for analysing both factors of $ρ σ^{2}$ as functions of $m$ and concluding an interior optimum.

Exercise 7 (hard, symbolic).

Suppose $B$ trees can be split into $G$ groups of equal size, where trees within a group correlate at $ρ_{1}$ and trees in different groups correlate at $ρ_{0} < ρ_{1}$ , all with variance $σ^{2}$ . Derive the variance of the average $\overset{ˉ}{T}$ and check it reduces to the standard formula when $ρ_{0} = ρ_{1}$ .

Hint

Count the within-group and between-group ordered pairs separately in the double covariance sum, then divide by $B^{2}$ .

Answer

Let each group have $k = B / G$ trees. The double sum has $B$ diagonal terms ( $σ^{2}$ each), $G \cdot k (k - 1)$ ordered within-group off-diagonal pairs ( $ρ_{1} σ^{2}$ each), and $B^{2} - B - G k (k - 1)$ ordered between-group pairs ( $ρ_{0} σ^{2}$ each). Thus

Var (\overset{ˉ}{T}) = \frac{σ ^{2}}{B ^{2}} (B + G k (k - 1) ρ_{1} + (B^{2} - B - G k (k - 1)) ρ_{0}) .

With $G k = B$ this simplifies to $Var (\overset{ˉ}{T}) = ρ_{0} σ^{2} + \frac{( 1 - ρ _{0} ) σ ^{2}}{B} + \frac{( k - 1 ) ( ρ _{1} - ρ _{0} ) σ ^{2}}{B}$ . The first two terms are the standard formula with correlation $ρ_{0}$ ; the third is the penalty for the extra within-group agreement and vanishes when $ρ_{1} = ρ_{0}$ , recovering $ρ_{0} σ^{2} + \frac{1 - ρ _{0}}{B} σ^{2}$ . The lesson: clusters of similar trees (for example trees that share a dominant split) raise the variance above the all-pairs-equal ideal, which is what feature subsampling exists to prevent. Rubric: full credit for the correct pair counts, the simplified expression, and the degenerate-case check.

Advanced results Master

The variance identity sets the design target; the remaining theory makes the target operational, bounds the error in terms of it, and asks whether the forest estimate is consistent.

Theorem 1 (Breiman's strength-and-correlation bound). Model a random forest classifier as an ensemble ${h (x, Θ_{b})}$ with $Θ_{b}$ i.i.d. Define the margin $m g (X, Y) = P_{Θ} (h (X, Θ) = Y) - max_{k \neq = Y} P_{Θ} (h (X, Θ) = k)$ , the strength $s = E_{X, Y} [m g (X, Y)]$ , and the mean correlation $\overset{ρ}{ˉ}$ of the raw margin functions between two independent trees. As $B \to \infty$ the forest's generalisation error $P E^{*} = P_{X, Y} (m g (X, Y) < 0)$ converges almost surely (so forests do not overfit in $B$ ), and, when $s > 0$ ,

P E^{*} \leq \frac{ρ ˉ ( 1 - s ^{2} )}{s ^{2}}

^{[Breiman 2001]}. The bound is the classification analogue of the regression variance floor $ρ σ^{2}$ : error is small when trees are strong ( $s$ large) and weakly correlated ( $\overset{ρ}{ˉ}$ small), and the random split-feature selection is precisely the mechanism that shrinks $\overset{ρ}{ˉ}$ at a modest cost in $s$ .

Theorem 2 (almost-sure convergence in the number of trees). Because the trees are i.i.d. given the training data, for fixed $x$ the regression forest average $\frac{1}{B} \sum_{b} h (x; Θ_{b})$ converges almost surely to $E_{Θ} [h (x; Θ)]$ as $B \to \infty$ by the strong law of large numbers, and the generalisation error converges to that of the infinite forest ^{[Breiman 2001]}. Consequently $B$ is not a complexity parameter: increasing it removes Monte-Carlo noise in the aggregate and cannot increase test error. Model complexity is carried by tree depth and by $m$ .

Theorem 3 (out-of-bag error is an internal validation estimate). Fix the loss $L$ . For each case $i$ the OOB prediction averages only the $∣ B_{i} ∣$ trees that omitted $i$ , each of which is fitted without $i$ , so $E [Err^{oob}]$ estimates the risk of a forest trained on $n - O (1)$ cases. As $B \to \infty$ each $∣ B_{i} ∣ \to \infty$ almost surely (a fraction $\approx 0.368$ of trees), so the OOB prediction approaches the full infinite-subforest prediction restricted to omitting $i$ , and the OOB error tracks $K$ -fold cross-validation error without a separate split or refitting ^{[Hastie 2009]}. The same OOB machinery, with one feature permuted, yields the permutation importance.

Theorem 4 (the random-forest kernel and proximities). Define the forest proximity between two points as the fraction of trees in which they fall in the same leaf, $K_{rf} (x, x^{'}) = \frac{1}{B} \sum_{b = 1}^{B} 1 {x, x^{'} share a leaf in tree b}$ . This $K_{rf}$ is a positive-definite kernel, and the regression forest prediction is the kernel-weighted average $\hat{f}_{rf} (x) = \sum_{i} w_{i} (x) y_{i}$ with weights $w_{i} (x) \propto \sum_{b} 1 {x_{i}, x share a leaf in tree b} / N_{R_{b} (x)}$ , the potential-nearest-neighbour weighting ^{[Hastie 2009]}. A random forest is thus an adaptive kernel method whose neighbourhoods are the data-driven leaf cells, the same local-averaging reading that casts a single tree as an adaptive nearest-neighbour rule 45.08.04; the proximity matrix doubles as a similarity measure for clustering, outlier detection, and missing-value imputation.

Theorem 5 (consistency of CART-split random forests). In the additive regression model $Y = \sum_{j = 1}^{p} m_{j} (X^{(j)}) + ε$ with each $m_{j}$ continuous, $X$ uniform on $[0, 1]^{p}$ , and $ε$ centred with finite variance, Breiman's random forest — using genuine data-dependent CART splits and bootstrap resampling — is $L^{2}$ -consistent: with the number of terminal nodes $t_{n} \to \infty$ and $t_{n} (lo g n) / n \to 0$ , the forest estimate $\hat{f}_{rf, n}$ satisfies $E [(\hat{f}_{rf, n} (X) - f (X))^{2}] \to 0$ ^{[Scornet 2015]}. This is the first consistency proof for the original algorithm rather than a stylised purely-random surrogate; earlier results (Biau 2012; Biau, Devroye and Lugosi 2008) established consistency for centred or purely-random forests whose splits ignore the response.

Synthesis. The foundational reason random forests cohere as a method is that one error decomposition is being driven in a single direction: the variance floor $ρ σ^{2}$ of the Key theorem is exactly the regression face of Breiman's strength-and-correlation bound $\overset{ρ}{ˉ} (1 - s^{2}) / s^{2}$ , and the design of the algorithm — bootstrap resampling plus random split-feature selection — is the engineering that lowers $ρ$ (or $\overset{ρ}{ˉ}$ ) while spending as little tree strength $s$ as possible. This is exactly why $B$ is a budget and not a regularisation knob: averaging i.i.d. trees can only remove the $\frac{1 - ρ}{B} σ^{2}$ term, never the floor, and the strong law guarantees convergence rather than overfitting in $B$ . The central insight that unifies the diagnostics is local averaging: the proximity kernel reading shows a forest is an adaptive nearest-neighbour estimator whose weights are read off leaf co-occurrence, which is dual to the CART nearest-neighbour picture and generalises it by averaging over many randomised partitions; this is the bridge from the variance algebra to the consistency theory, since the Scornet-Biau-Vert theorem states that these adaptive neighbourhoods shrink while retaining enough points for the leaf-averages to converge to $E [Y ∣ X]$ . Putting these together, the family is organised by which term of the bias-variance split 45.06.02 each method moves: forests spend their effort on variance, leaving bias near the base tree's, whereas boosting 45.08.06 grows stunted, high-bias trees and reduces bias sequentially — variance-reduction and bias-reduction as the two routes off one decomposition.

Full proof set Master

Proposition 1 (variance of an average of correlated predictors). For identically distributed $T_{1}, \dots, T_{B}$ with variance $σ^{2}$ and pairwise correlation $ρ$ , $Var (\frac{1}{B} \sum_{b} T_{b}) = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ .

Proof. As established in the Key theorem, $Var (\overset{ˉ}{T}) = \frac{1}{B ^{2}} (B σ^{2} + B (B - 1) ρ σ^{2})$ since there are $B$ diagonal variance terms and $B (B - 1)$ ordered off-diagonal covariance terms each equal to $ρ σ^{2}$ . Dividing, $Var (\overset{ˉ}{T}) = \frac{σ ^{2}}{B} + \frac{B - 1}{B} ρ σ^{2} = ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ . $□$

Proposition 2 (idealised bagging never increases squared error; gain equals base variance). Let $Z = \hat{f} (x; L^{*})$ be a base prediction over the resampling distribution with mean $μ = E [Z]$ , and let $a = f (x)$ be a fixed target. Then $E [(a - Z)^{2}] = (a - μ)^{2} + Var (Z)$ , so the aggregate $μ$ has squared error $(a - μ)^{2} \leq E [(a - Z)^{2}]$ with gap $Var (Z)$ .

Proof. Expand $E [(a - Z)^{2}] = a^{2} - 2 a μ + E [Z^{2}]$ and substitute $E [Z^{2}] = μ^{2} + Var (Z)$ : $E [(a - Z)^{2}] = a^{2} - 2 a μ + μ^{2} + Var (Z) = (a - μ)^{2} + Var (Z)$ . Non-negativity of variance gives $(a - μ)^{2} \leq E [(a - Z)^{2}]$ , with equality iff $Var (Z) = 0$ , that is, iff the base learner is deterministic. $□$

Proposition 3 (out-of-bag fraction). The probability that a fixed case is omitted from a single size- $n$ bootstrap sample is $(1 - 1/ n)^{n}$ , which increases to $e^{- 1}$ as $n \to \infty$ ; the expected number of distinct cases appearing is $n (1 - (1 - 1/ n)^{n}) \to n (1 - e^{- 1})$ .

Proof. Each of the $n$ independent draws misses a fixed case with probability $1 - 1/ n$ , so all $n$ draws miss it with probability $(1 - 1/ n)^{n}$ . Writing $(1 - 1/ n)^{n} = exp (n lo g (1 - 1/ n)) = exp (- 1 - \frac{1}{2 n} - \dots) ↑ e^{- 1}$ as $n \to \infty$ (the bracketed series is the expansion of $n lo g (1 - 1/ n)$ , decreasing to $- 1$ in magnitude). The indicator that case $i$ appears has expectation $1 - (1 - 1/ n)^{n}$ ; summing over $i$ and using linearity gives the expected count $n (1 - (1 - 1/ n)^{n}) \to n (1 - e^{- 1}) \approx 0.632 n$ . $□$

Proposition 4 (almost-sure limit of the forest in $B$ ). For fixed $x$ and training data, with ${Θ_{b}}$ i.i.d. and $E_{Θ} ∣ h (x; Θ) ∣ < \infty$ , the forest average converges almost surely: $\frac{1}{B} \sum_{b = 1}^{B} h (x; Θ_{b}) \to E_{Θ} [h (x; Θ)]$ as $B \to \infty$ .

Proof. Conditionally on the training data, the summands $h (x; Θ_{b})$ are i.i.d. (functions of the i.i.d. $Θ_{b}$ ) with finite mean. Kolmogorov's strong law of large numbers gives $\frac{1}{B} \sum_{b} h (x; Θ_{b}) \to E_{Θ} [h (x; Θ)]$ almost surely over the sequence ${Θ_{b}}$ . The limit is the infinite-forest predictor at $x$ ; the generalisation error, a fixed functional of the predictor, converges to that of the infinite forest, so test error is non-increasing in $B$ up to Monte-Carlo fluctuation. $□$

The strength-and-correlation bound (Theorem 1), the kernel/proximity structure (Theorem 4), and the additive-model consistency theorem (Theorem 5) are stated without reproduced proof — Theorem 1 is Theorem 2.3 of ^{[Breiman 2001]}, Theorem 5 is the main theorem of ^{[Scornet 2015]}, whose proof runs through empirical-process control of the CART splits and the additive-model approximation and exceeds the scope set here.

Connections Master

CART 45.08.04 is the base learner these methods average: the instability proved there — a fully grown tree is low-bias and high-variance because its partition is a discontinuous function of the data — is the exact regime in which the variance identity of this unit predicts a large payoff from averaging, so this unit consumes the object the tree unit builds, and the nearest-neighbour reading of a single tree extends here to the forest proximity kernel.

The bias-variance decomposition 45.06.02 is the ledger that organises the whole family: bagging and random forests are deliberate moves on the variance term, leaving the bias near that of the base tree, which is why they are wasted on a low-variance learner and why the floor $ρ σ^{2}$ — not $B$ — caps their benefit; the foundational reason the formula is a clean sum of a floor plus a shrinking term is the same bilinearity of covariance that underlies that unit's orthogonal split.

Boosting 45.08.06 is the complementary method on the same decomposition: where forests reduce variance by averaging strong, de-correlated trees, boosting reduces bias by sequentially reweighting deliberately shallow, high-bias trees, so the two units together exhibit variance-reduction versus bias-reduction as the two routes off the bias-variance split, and the contrast is the cleanest illustration in the chapter of why the decomposition is the organising principle.

The bootstrap and resampling methods of 26.08.01 supply the engine: the with-replacement resample that defines a bootstrap sample, the out-of-bag complement, and the $(1 - 1/ n)^{n} \to e^{- 1}$ omission fraction are the resampling theory of that unit applied to ensembling rather than to standard-error estimation, and the OOB error is the resampling estimate of risk specialised to the forest.

Historical & philosophical context Master

Bagging was introduced by Leo Breiman (1996) in Bagging Predictors ^{[Breiman 1996]}, which framed bootstrap aggregation as a variance-reduction device and proved by a Jensen-type inequality that aggregation cannot increase squared error, with the gain governed by the instability of the base learner — making explicit that the method pays off for high-variance procedures such as CART and does little for stable ones. The bootstrap itself is due to Bradley Efron (1979), and Breiman's contribution was to repurpose it from inference about a statistic to the construction of a predictor. The random-subspace idea of restricting features was developed in parallel by Tin Kam Ho (1998) (the random subspace method) and by Yali Amit and Donald Geman (1997) (randomised trees for shape recognition).

The synthesis is Breiman (2001), Random Forests ^{[Breiman 2001]}, which combined bootstrap resampling with random split-feature selection, proved the strong-law convergence in the number of trees and the strength-and-correlation generalisation bound, and introduced out-of-bag error, permutation importance, and proximities. The statistical-learning recasting in Hastie, Tibshirani and Friedman's Elements of Statistical Learning (2009) ^{[Hastie 2009]} placed the variance-of-correlated-average identity at the centre and presented the forest as an adaptive kernel method. Rigorous consistency long lagged the empirical success: results for stylised purely-random and centred forests (Biau, Devroye and Lugosi 2008; Biau 2012) preceded the consistency proof for Breiman's actual CART-split algorithm by Erwan Scornet, Gérard Biau and Jean-Philippe Vert (2015) ^{[Scornet 2015]} in the additive-regression model, closing part of the long gap between the method's practical dominance and its theoretical understanding.

Bibliography Master

@article{breiman1996bagging,
  author  = {Breiman, Leo},
  title   = {Bagging Predictors},
  journal = {Machine Learning},
  volume  = {24},
  number  = {2},
  pages   = {123--140},
  year    = {1996}
}

@article{breiman2001randomforests,
  author  = {Breiman, Leo},
  title   = {Random Forests},
  journal = {Machine Learning},
  volume  = {45},
  number  = {1},
  pages   = {5--32},
  year    = {2001}
}

@book{hastie2009esl,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009}
}

@article{scornet2015consistency,
  author  = {Scornet, Erwan and Biau, G\'erard and Vert, Jean-Philippe},
  title   = {Consistency of Random Forests},
  journal = {The Annals of Statistics},
  volume  = {43},
  number  = {4},
  pages   = {1716--1741},
  year    = {2015}
}

@article{efron1979bootstrap,
  author  = {Efron, Bradley},
  title   = {Bootstrap Methods: Another Look at the Jackknife},
  journal = {The Annals of Statistics},
  volume  = {7},
  number  = {1},
  pages   = {1--26},
  year    = {1979}
}

@inproceedings{ho1998randomsubspace,
  author    = {Ho, Tin Kam},
  title     = {The Random Subspace Method for Constructing Decision Forests},
  journal   = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  volume    = {20},
  number    = {8},
  pages     = {832--844},
  year      = {1998}
}

@article{amitgeman1997,
  author  = {Amit, Yali and Geman, Donald},
  title   = {Shape Quantization and Recognition with Randomized Trees},
  journal = {Neural Computation},
  volume  = {9},
  number  = {7},
  pages   = {1545--1588},
  year    = {1997}
}

@article{biau2012,
  author  = {Biau, G\'erard},
  title   = {Analysis of a Random Forests Model},
  journal = {Journal of Machine Learning Research},
  volume  = {13},
  pages   = {1063--1095},
  year    = {2012}
}

Prerequisites

45.08.04
45.06.02

Tier anchors

beginner: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §8.7 (bagging) and §15.1-15.2 (random forests); a 'ask a crowd of imperfect experts and average their guesses' analogy for why averaging many noisy trees is steadier than trusting one
intermediate: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §8.7 (bagging, the bootstrap as a resampling device) and §15.2-15.3 (the random-forest algorithm, out-of-bag error, the de-correlation effect of feature subsampling); Breiman 1996 Machine Learning 24 (bagging predictors) and Breiman 2001 Machine Learning 45 (random forests, the variance formula for averaged correlated predictors and the strength/correlation generalisation bound)
master: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e §15.3-15.4 (variance of an average of correlated trees, variable importance, the random-forest kernel and proximities); Breiman 2001 Machine Learning 45 (the $c / s^{2}$ generalisation-error bound via strength and correlation); Scornet, Biau & Vert 2015 Annals of Statistics 43 (consistency of Breiman's random forests in the additive-regression model)

References

Hastie, T., Tibshirani, R. & Friedman, J. — The Elements of Statistical Learning · Springer, 2nd edition (2009). Section 8.7 introduces bagging (bootstrap aggregation): draw $B$ bootstrap samples from the training data, fit the base learner to each, and average the predictions (for regression) or vote (for classification). It frames bagging as a variance-reduction device that helps high-variance, low-bias learners such as fully grown trees and notes that for a stable, linear procedure bagging changes little. Chapter 15 develops random forests: the algorithm grows many trees on bootstrap samples but at each split considers only a random subset of $m$ of the $p$ predictors (the mtry parameter), which de-correlates the trees and so drives down the correlation floor in the variance of an average. Section 15.2 gives the variance identity $ρ σ^{2} + \frac{1 - ρ}{B} σ^{2}$ for an average of $B$ identically distributed predictors with pairwise correlation $ρ$ and common variance $σ^{2}$ ; §15.3 treats out-of-bag (OOB) error as a built-in cross-validation-like estimate using, for each observation, only the trees that did not see it; §15.3.2 covers the two variable-importance measures (the Gini/split-improvement importance accumulated during growing, and the permutation importance computed on the OOB samples); §15.4 discusses the random-forest as an adaptive kernel / proximity matrix and the analysis of forests as estimators.
Breiman, L. — Bagging predictors · Machine Learning 24 (1996), 123-140. Introduces bagging: given a learning set $L$ and a predictor $φ (\cdot, L)$ , form bootstrap replicates $L^{(b)}$ by sampling $n$ cases with replacement and aggregate $φ_{B} (x) = \frac{1}{B} \sum_{b} φ (x, L^{(b)})$ (average for regression, plurality vote for classification). Breiman shows by a Jensen-type argument that the aggregated regression predictor has mean squared error no larger than the average MSE of the base predictors, with the gap controlled by the variance of $φ (x, L)$ over $L$ , so bagging helps exactly when the base learner is unstable (high variance). The paper reports the variance-reduction gains empirically on CART trees and defines the out-of-bag observations (those omitted from a given bootstrap sample, on average a fraction $(1 - 1/ n)^{n} \to e^{- 1} \approx 0.368$ ).
Breiman, L. — Random forests · Machine Learning 45 (2001), 5-32. Defines a random forest as an ensemble of tree predictors ${h (x, Θ_{b})}$ with the $Θ_{b}$ i.i.d. random vectors (bootstrap resample plus random split-feature selection). Proves the strong-law convergence of the forest's generalisation error as $B \to \infty$ (so forests do not overfit in the number of trees), and bounds the classification generalisation error by $P E^{*} \leq \overset{ρ}{ˉ} (1 - s^{2}) / s^{2}$ , where $s$ is the strength (expected margin) of the individual trees and $\overset{ρ}{ˉ}$ the mean correlation between trees. The bound makes precise the design objective: keep tree strength high while lowering inter-tree correlation, the role of the random feature subsampling at each split. The paper introduces the permutation variable-importance measure on out-of-bag data and the proximity matrix from co-occurrence in leaves.
Scornet, E., Biau, G. & Vert, J.-P. — Consistency of random forests · Annals of Statistics 43 (2015), 1716-1741. The first $L^{2}$ -consistency proof for Breiman's original random forests (with data-dependent CART splits and bootstrap resampling, not a stylised purely-random variant) in the additive regression model $Y = \sum_{j} m_{j} (X^{(j)}) + ε$ with continuous $m_{j}$ . Establishes that, with the number of terminal nodes growing suitably with $n$ , the forest estimate converges in $L^{2}$ to the regression function. The result is the rigorous counterpart to Breiman's heuristic strength/correlation analysis and to the earlier consistency theory for simplified (purely random or centred) forests by Biau, Devroye and Lugosi.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m