Random forest

Definition#

A random forest (Breiman, 2001) is bagging with randomised split selection. Given training set D of size n:

for b = 1..B:
    D_b  <- bootstrap sample of size n drawn from D with replacement
    T_b  <- grow a CART tree on D_b, where at each node a random subset
            of m <= d features is considered for the split
    (trees are grown deep; typically unpruned)

Classification:  f(x) = majority vote over { T_b(x) }
Regression:      f(x) = (1/B) * SUM_b T_b(x)

• B — number of trees, n — training set size, d — number of features
• m — features sampled per split; mtry in the R literature. Defaults: sqrt(d) for classification, d/3 (R) or d (scikit-learn RandomForestRegressor) for regression

The two randomisation sources are separable, and this matters conceptually. Bootstrap alone gives Breiman's earlier bagging (1996). Feature subsampling alone gives Ho's random subspace method (1998). The combination is the random forest.

Why averaging works#

For regression with squared loss, consider B predictors each with variance sigma^2 and pairwise correlation rho. The variance of their average is:

Var( (1/B) SUM_b T_b )  =  rho * sigma^2  +  ( (1 - rho) / B ) * sigma^2

• rho — average pairwise correlation between tree predictions
• sigma^2 — variance of an individual tree

This single expression explains the whole design.

The second term vanishes as B -> infinity. The first does not. The irreducible floor is rho * sigma^2, so the only way to improve a large forest is to reduce the correlation between its trees.

That is exactly what feature subsampling does. Lowering m reduces rho while raising sigma^2, since each tree is individually weaker. m trades these against each other, and the optimum is typically well below d.

The empirical numbers in the Developer section are this formula made visible: disagreement 0.385 with member accuracy 0.660 beats disagreement 0.016 with member accuracy 0.780.

Bagging alone reduces variance but leaves bias essentially unchanged, which is why the base learners are grown deep. Deep trees are low-bias and high-variance — precisely the failure mode averaging repairs.

Generalisation bound#

Breiman's bound is stated in terms of margin:

PE*  <=  rho_bar * (1 - s^2) / s^2

• PE* — generalisation error of the forest
• s — the strength, the expected margin of individual trees
• rho_bar — mean correlation between the margin functions of tree pairs

The bound is loose and rarely predictive of actual error. Its value is qualitative and it is the correct intuition: error falls with strength and rises with correlation.

The bound also implies forests do not overfit as B grows. As B -> infinity, PE converges almost surely to a limit — a consequence of the strong law of large numbers, since the trees are i.i.d. given the training set. This is a genuine and unusual guarantee: B is a computational budget, not a capacity parameter. Contrast boosting, where more rounds do eventually overfit.

Out-of-bag estimation#

Under bootstrap sampling, the probability a given observation is omitted from a given tree is:

(1 - 1/n)^n  ->  1/e  ~=  0.368   as n -> infinity

So each tree omits roughly 36.8 percent of the data, and each observation is out-of-bag for roughly 36.8 percent of the trees. Aggregating the predictions of only those trees gives a nearly unbiased estimate of generalisation error.

Bylander (2002) and others note that OOB error is mildly pessimistic, since each observation is scored by an ensemble of about 0.368 * B trees rather than the full B. The bias shrinks as B grows.

OOB is not a substitute for a held-out set when hyperparameters are selected using it — the selection bias of Cawley & Talbot (2010) applies unchanged.

Variable importance, and why the default is wrong#

Mean decrease in impurity (MDI). Sum the weighted impurity decrease over all nodes splitting on a feature, averaged over trees. Cheap, computed during fitting, and biased.

Strobl et al. (2007) identify two mechanisms. Features with more distinct values offer more candidate split points and win ties more often, so continuous and high-cardinality categorical features are inflated even under the null. And because impurity is measured on in-bag data, the bias is an in-sample overfitting artefact.

The Developer section quantifies this on a dataset with known ground truth: five pure-noise columns absorbed 39.7 percent of the MDI total.

Permutation importance (MDA). Shuffle feature j and measure the increase in error, ideally on held-out data:

Imp(j) = Err( X with column j permuted ) - Err( X )

Unbiased with respect to cardinality, but it has its own failure mode: under correlated features it evaluates the model on inputs off the data manifold, and importance is split arbitrarily among a correlated group. Conditional permutation importance (Strobl et al., 2008) permutes within strata of correlated features and addresses this.

SHAP. TreeSHAP (Lundberg et al., 2020) computes exact Shapley values for tree ensembles in O(TLD^2), giving local per-prediction attributions with additivity guarantees. It is the current default for serious attribution work on trees.

Consistency theory#

Breiman's original algorithm resisted analysis for a decade, because the splits depend on the labels in a complicated way.

Biau (2012) proved consistency for a simplified variant. Scornet, Biau & Vert (2015) established the first consistency result for the original algorithm under an additive regression model. Wager & Athey (2018) proved asymptotic normality for honest forests — where the sample used to choose splits is disjoint from the sample used to fit leaf values — enabling valid confidence intervals and forming the basis of causal forests.

Honesty is not a technicality. Without it, the same data determines both the partition and the estimates within it, and the resulting intervals are invalid.

Cost#

Training     O( B * m * n log^2 n )     embarrassingly parallel over B
Prediction   O( B * depth )             typically O(B log n)
Memory       O( B * number of nodes )

Training parallelises with near-linear speedup, since trees are independent. Prediction is B times a single tree's cost, which is the real deployment constraint: a 500-tree forest is 500 tree traversals per prediction.

Variants#

Extremely randomised trees (Geurts et al., 2006) push randomisation further: split thresholds are drawn at random rather than optimised, and the full sample is used by default rather than a bootstrap. This lowers rho and variance further at some cost in bias, and it is substantially faster since no threshold search is performed. sklearn.ensemble.ExtraTreesClassifier. Frequently competitive with, occasionally better than, a random forest — and consistently under-tried.

Quantile regression forests (Meinshausen, 2006) keep the full empirical distribution of training values in each leaf rather than only the mean, yielding prediction intervals rather than point estimates.

Causal forests (Wager & Athey, 2018; Athey et al., 2019) adapt the splitting criterion to maximise heterogeneity in treatment effect rather than in outcome, estimating conditional average treatment effects with valid inference.

Isolation forests (Liu et al., 2008) invert the idea for anomaly detection: anomalies are isolated by fewer random splits, so average path length becomes an outlier score.

Key references#

• Ho, T. K. (1998). The Random Subspace Method for Constructing Decision Forests. IEEE TPAMI 20(8).
• Breiman, L. (1996). Bagging Predictors. Machine Learning 24(2).
• Breiman, L. (2001). Random Forests. Machine Learning 45(1). The founding paper.
• Geurts, P., Ernst, D. & Wehenkel, L. (2006). Extremely Randomized Trees. Machine Learning 63(1).
• Meinshausen, N. (2006). Quantile Regression Forests. JMLR 7.
• Strobl, C. et al. (2007). Bias in Random Forest Variable Importance Measures. BMC Bioinformatics 8(25).
• Biau, G. (2012). Analysis of a Random Forests Model. JMLR 13.
• Scornet, E., Biau, G. & Vert, J.-P. (2015). Consistency of Random Forests. Annals of Statistics 43(4).
• Wager, S. & Athey, S. (2018). Estimation and Inference of Heterogeneous Treatment Effects using Random Forests. JASA 113(523).
• Fernández-Delgado, M. et al. (2014). Do We Need Hundreds of Classifiers to Solve Real World Classification Problems? JMLR 15.

Current state#

Fernández-Delgado et al. (2014) compared 179 classifiers across 121 datasets and found random forests the strongest family overall. That result predates the maturity of modern gradient boosting; today tuned GBMs generally edge ahead on tabular benchmarks.

Random forests retain three practical advantages that keep them in production. They are close to hyperparameter-free — defaults are usually within a point of tuned performance, which is not remotely true of boosting. They parallelise with near-linear speedup. And OOB error removes the need for a separate validation split during development.

Grinsztajn et al. (2022) confirm that tree ensembles as a family still outperform deep learning on medium-sized tabular data, attributing this to robustness against uninformative features and to an inductive bias suited to irregular, non-smooth target functions. The eight-column experiment in the Developer section is a small instance of exactly that.

The honest summary: use a random forest as the baseline that is difficult to get wrong, then check whether gradient boosting earns the extra tuning effort.

What to learn next#

• XGBoost — building trees in sequence to fix each other's errors, instead of in parallel.
• Model evaluation — reading the vote counts a forest gives you.
• Feature engineering — the work a forest cannot do for you.