We now turn high-variance single trees into one of the most robust models in machine learning. The recipe has two ingredients: bagging (train many trees on bootstrap resamples and average them) and the random forest twist (also randomize the features at each split). Together they slash variance while keeping bias low, producing an excellent, low-tuning default for tabular data.

Bagging: bootstrap aggregating

Bagging (Breiman, 1996) trains \(B\) models on \(B\) bootstrap samples — datasets of size \(n\) drawn with replacement from the training set — and aggregates their predictions: average for regression, majority vote (or averaged probabilities) for classification.

Recall the averaging law: \(B\) trees each with variance \(\sigma^2\) and pairwise correlation \(\rho\) have averaged variance \(\rho\sigma^2+\frac{1-\rho}{B}\sigma^2\). Bagging drives the second term toward zero by using many trees. But the trees are trained on overlapping bootstrap samples, so they remain correlated (\(\rho\) stays high), and the first term \(\rho\sigma^2\) sets a floor on how much bagging alone can help. Removing that floor is exactly the random-forest idea.

Random forests: decorrelate the trees

A random forest (Breiman, 2001) is bagging plus feature subsampling: at each split, only a random subset of \(m\) features (out of \(p\)) is considered. This stops every tree from latching onto the same one or two dominant features, decorrelating the trees (\(\rho\downarrow\)) so that averaging helps far more. Typical defaults: \(m=\sqrt{p}\) for classification, \(m=p/3\) for regression. Trees are grown deep and unpruned — variance is handled by the ensemble, not by each tree.

Out-of-bag (OOB) error: free validation

Each bootstrap sample omits about \(1/e\approx 37\%\) of the data — these are the out-of-bag samples for that tree. Predict each training point using only the trees that did not see it, and you get an almost-free, nearly unbiased estimate of test error — no separate validation split needed. OOB error is a hallmark convenience of random forests, great for quick model assessment and even feature-importance estimates.

Why \(\approx 37\%\)? The probability a specific point is not chosen in one draw is \(1-\tfrac1n\); over \(n\) draws it is \((1-\tfrac1n)^n\to e^{-1}\approx 0.368\). So each tree trains on \(\approx 63\%\) of the unique points and can be validated on the remaining \(\approx 37\%\).

Why forests are such a good default

Random forests are forgiving: they rarely overfit as you add trees (more trees only stabilize the average — you cannot overfit by growing the forest, only by other means), need little tuning, handle thousands of features, give OOB error and importances for free, and parallelize trivially (trees are independent). The main costs: the model is a black box (hundreds of deep trees), larger memory/inference, and they usually trail well-tuned gradient boosting by a small margin in accuracy.

Misconceptions to avoid. (1) “More trees can overfit” — no; more trees reduce variance and plateau. Overfitting comes from too-deep trees on too-little data or leakage, not from \(B\). (2) Default impurity importances are trustworthy — they are biased toward high-cardinality and correlated features; prefer permutation importance (Chapter [ch:importance]). (3) \(m\) doesn’t matter — with many correlated/irrelevant features, tuning max_features noticeably affects decorrelation and accuracy. (4) Forests extrapolate — they still cannot, being averages of non-extrapolating trees.

Random forests are the canonical variance-reduction-by-averaging method, and that idea recurs everywhere: deep ensembles (averaging several independently trained neural networks) are essentially bagging for deep learning, and remain a top method for accuracy and uncertainty estimation. Bayesian model averaging, Monte-Carlo dropout, and snapshot ensembles are all variations on “average decorrelated predictors.” Random forests also remain a go-to for quick, robust baselines, feature screening (importances), and embedded uses like isolation forests for anomaly detection (Chapter [ch:specialized]).

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_breast_cancer
X, y = load_breast_cancer(return_X_y=True)
rf = RandomForestClassifier(n_estimators=500, max_features="sqrt",
                            oob_score=True, n_jobs=-1, random_state=0).fit(X, y)
print("OOB accuracy:", round(rf.oob_score_, 3))     # free validation estimate
import numpy as np
top = np.argsort(rf.feature_importances_)[::-1][:3]
print("top feature indices:", top)

Chapter summary

  • Bagging averages trees trained on bootstrap resamples, cutting variance — but correlated trees leave a floor \(\rho\sigma^2\).

  • Random forests add per-split feature subsampling (\(m\approx\sqrt p\) or \(p/3\)) to decorrelate trees and average better.

  • Trees are grown deep and unpruned; variance control comes from the ensemble.

  • OOB error (\(\approx 37\%\) held out per tree) gives near-free, unbiased test-error and importance estimates.

  • Forests are robust, low-tuning, parallel defaults; the deep-learning analog is the deep ensemble.