Random Forests

A random forest is an ensemble of decision trees, each trained on an independent bootstrap sample of the training data, in which every candidate split considers only a random subset of the available features rather than all of them. Formally, given training data of size $n$, the forest builds $B$ trees $T_1, \dots, T_B$. Tree $T_b$ is grown on a bootstrap sample $\mathcal{D}_b$ drawn with replacement from the original $n$ observations, and at each internal node the algorithm picks the best split using only $m < p$ features drawn uniformly at random from the full set of $p$ predictors (a fresh random subset at every single node, not once per tree). Predictions are aggregated by averaging (regression) or majority vote (classification) across all $B$ trees. The two random ingredients serve different purposes. Bootstrap resampling, inherited from Bagging and the Bootstrap, makes each tree see a slightly different training set, which alone reduces variance somewhat but leaves trees correlated — because in most resamples the single strongest predictor still dominates the top splits. Restricting the split search to $m$ random features is the added mechanism that breaks this correlation: with a smaller $m$, strong predictors are sometimes simply unavailable at a given node, forcing the tree to use other, otherwise-shadowed features. This produces trees whose errors are less alike, which is precisely the condition under which averaging helps most. Random forests deliberately grow trees deep — often to purity or a minimum leaf size of 1 (regression) or a few observations (classification) — rather than pruning them, unlike the pruning strategy used for single trees under Tree Pruning and Complexity Control. This is not an oversight: a single unpruned tree has low bias but very high variance, and averaging is the mechanism used to control variance instead of pruning. Pruning each individual tree would push bias up for no compensating benefit, since the ensemble's decorrelation already tames the variance.

Growing a random forest of $B$ trees proceeds by repeating a bootstrap-and-grow procedure independently for each tree, then aggregating. ``` function RANDOM_FOREST_TRAIN(data D of size n, num_trees B, mtry m, max_leaf_size k): forest = [] for b = 1 to B: D_b = SAMPLE_WITH_REPLACEMENT(D, size = n) # bootstrap sample OOB_b = { i in D : i not in D_b } # out-of-bag indices for tree b T_b = GROW_TREE(D_b, m, k) forest.append( (T_b, OOB_b) ) return forest function GROW_TREE(data, m, k): node = new node if STOPPING_CONDITION(data, k): # e.g. |data| <= k, or pure node node.prediction = AGGREGATE(data.labels) # mean (regression) / majority (classification) return node F = RANDOM_SUBSET(all_features, size = m) # fresh draw at THIS node best_split = None for feature in F: for threshold in CANDIDATE_THRESHOLDS(data, feature): gain = IMPURITY_DECREASE(data, feature, threshold) if best_split is None or gain > best_split.gain: best_split = (feature, threshold, gain) if best_split is None or best_split.gain <= 0: node.prediction = AGGREGATE(data.labels) return node left_data, right_data = SPLIT(data, best_split.feature, best_split.threshold) node.split = best_split node.left = GROW_TREE(left_data, m, k) node.right = GROW_TREE(right_data, m, k) return node function PREDICT(forest, x): predictions = [ TREE_PREDICT(T_b, x) for (T_b, _) in forest ] return AGGREGATE(predictions) # mean or majority vote function OOB_ERROR(forest, D): errors = 0 for i in D: preds_i = [ TREE_PREDICT(T_b, x_i) for (T_b, OOB_b) in forest if i in OOB_b ] if preds_i is empty: continue # rare, skip y_hat_i = AGGREGATE(preds_i) errors += LOSS(y_hat_i, y_i) return errors / n ``` Two parameters dominate behavior: `mtry`, the number of features considered per split ($m$), and `num_trees` ($B$). Standard defaults are $m = \lfloor \sqrt{p} \rfloor$ for classification and $m = \lfloor p/3 \rfloor$ for regression, though both can be tuned via OOB error without touching a held-out set. Increasing $B$ never hurts expected performance in the large-$B$ limit (it only costs computation), because averaging more independent, identically-distributed error terms only reduces variance further; $B$ is typically chosen large enough that OOB error has stabilized (hundreds to a few thousand trees). The out-of-bag mechanism deserves its own emphasis. Each bootstrap sample of size $n$ drawn with replacement excludes, on average, a fraction

of the original observations as $n \to \infty$. Those excluded points are "out-of-bag" for that tree and were never used to fit it, so predicting them with that tree gives an honest holdout prediction. Aggregating each observation's OOB predictions across only the trees that never saw it produces an estimate of test error that behaves like cross-validation, without any explicit validation split or refitting.

Time complexity. Growing one unpruned tree on $n$ observations with $p$ total features, but only $m$ considered per split, costs $O(m \cdot n \log n)$ under the standard assumption of a roughly balanced tree of depth $O(\log n)$: at each of $O(\log n)$ levels, sorting or scanning to find the best threshold across $n$ points and $m$ candidate features costs $O(m n)$ total per level (with pre-sorted features maintained across splits, a common implementation trick). Across all levels this gives $O(m n \log n)$ per tree, and $O(B \cdot m \cdot n \log n)$ for the whole forest. In the worst case of a highly unbalanced tree (e.g., pathological data), a single tree can degrade toward $O(m n^2)$, but with reasonable stopping rules (minimum leaf size) this is rarely observed in practice. Prediction for one query point is $O(B \log n)$, since each tree is traversed root-to-leaf in $O(\text{depth})$.

Space complexity. Storing $B$ trees costs $O(B \cdot n)$ in the worst case (one leaf per training point) though typically far less with a minimum leaf size; training additionally needs $O(n)$ working memory per tree if sorted feature copies are cached, or $O(mn)$ if all $m$ candidate feature columns are held simultaneously during a split search.

Why decorrelation reduces variance — the core argument. Suppose each tree's prediction at a fixed test point $x$ is a random variable (random over the bootstrap sample and feature subsets) with the same variance $\sigma^2$ and pairwise correlation $\rho$ between any two trees. The variance of the average of $B$ such identically distributed, equally correlated predictors is

As $B \to \infty$, the second term vanishes, leaving $\rho \sigma^2$ as an irreducible floor. Plain bagging (no feature subsetting) reduces the second term but does nothing about $\rho$; because dominant predictors tend to win the top split in nearly every bootstrap tree, $\rho$ stays uncomfortably high. Restricting each split to a random subset of $m < p$ features actively lowers $\rho$: with smaller $m$, the top predictor is simply unavailable at many nodes across many trees, forcing structurally different splits and less-correlated errors. This is the entire justification for random forests over plain bagged trees — a strictly smaller $\rho$ at the (small) cost of a possibly slightly larger per-tree $\sigma^2$, since restricting the split search can occasionally miss the globally best split. The bias–variance decomposition of the ensemble prediction is otherwise the same as for any averaged estimator: bias is approximately the bias of a single deep tree (small, since deep trees are low-bias), while variance is governed by the formula above.

Why OOB error is (nearly) unbiased. For observation $i$, only trees whose bootstrap sample excluded $i$ are used to predict it — by construction these trees never touched $y_i$ during fitting, so the prediction is a genuine out-of-sample prediction, structurally identical to a leave-some-out cross-validation fold. Since roughly 36.8% of trees exclude any given point, and this holds independently, symmetrically, across all $n$ points and all $B$ trees, averaging these excluded-tree predictions and comparing to the true label yields an estimate whose expectation converges to the true generalization error as $B \to \infty$. It is not perfectly unbiased for any finite training set (it slightly underestimates error compared to a fully independent test set drawn from the population, since OOB points still come from the same finite dataset), but empirically it tracks held-out test error very closely and is the standard practical proxy.

Honest tradeoffs. Random forests reduce variance but cannot reduce the bias of a deep tree below what a single fully grown tree already achieves; on problems where the true signal requires extrapolation beyond the training range, or is dominated by a strong additive/linear structure, forests can underperform simpler models. They are also comparatively memory-hungry (storing hundreds of full trees) and slower at prediction time than a single tree or a linear model, and their internal randomness makes exact reproducibility require careful seeding. Compared to boosting, forests parallelize trivially (each tree is independent) but typically need more trees to reach comparable accuracy on structured, low-noise problems.

Consider a small illustrative regression dataset predicting a patient's length of hospital stay (days) from three features: age, prior admissions count, and a lab marker. Suppose $n = 8$ patients and we grow $B = 5$ trees with $m = 2$ of the 3 features considered per split. The table shows which patients land in each tree's bootstrap sample (✓ = in-bag, blank = out-of-bag), abbreviated for illustration.

For patient P1, out-of-bag trees are $T_3$ and $T_5$ (the two trees whose bootstrap draw skipped P1). Suppose $T_3(\text{P1}) = 3.6$ and $T_5(\text{P1}) = 4.4$. The OOB prediction is the average over exactly the trees that never trained on P1:

compared to true $y = 4$: squared error $= 0.0$. For P5, out-of-bag trees are $T_1$ and $T_2$; suppose their predictions are $2.9$ and $3.4$, giving $\hat{y}_{\text{OOB}}(\text{P5}) = 3.15$ against true $y=2$, squared error $= 1.32$. Repeating this for all 8 patients (using only each patient's own out-of-bag trees) and averaging the squared errors yields the OOB mean-squared-error — a stand-in for test MSE, computed with zero extra data held aside. Now trace the effect of `mtry`. If $m = 3$ (i.e. every feature considered at every split, equivalent to plain bagging), suppose the lab marker is overwhelmingly the strongest predictor: nearly every tree's root split uses it, so $T_1, \dots, T_5$ make strongly correlated errors — $\rho$ is high, and the variance-reduction formula above shows the averaged variance stays close to $\rho \sigma^2$, not much smaller than a single tree. Dropping to $m = 2$ or $m = 1$ forces roughly a third to two-thirds of trees to split first on age or prior admissions instead, since the lab marker is randomly excluded from the candidate set at many root nodes; the resulting trees disagree more, $\rho$ falls, and the OOB MSE measured across a full run typically decreases — this is the direct, checkable signature of decorrelation actually working, and is the standard way practitioners tune `mtry`: sweep a few candidate values and pick the one with lowest OOB error. Finally, consider importance. Suppose across all trees, splitting on "prior admissions" reduces impurity by a cumulative amount much larger than splitting on "age," even though a permutation test — shuffling the age column and remeasuring OOB error — shows only a small increase in error, while shuffling prior admissions causes a large jump. This divergence between the two importance measures is expected and explained below.

Leo Breiman spent an early career in mathematical probability before turning to applied statistics and, later, machine learning, where he became one of the most influential bridge-builders between statistical theory and algorithmic prediction. His 1996 paper on bagging demonstrated that averaging bootstrap-resampled unstable predictors reduces variance; his 2001 paper "Random Forests" extended this by adding random feature subsetting, proving foundational variance bounds and popularizing out-of-bag error estimation as a built-in validation mechanism. Breiman's broader "two cultures" perspective — contrasting data-modeling statistics with algorithmic, prediction-focused modeling — anticipated much of the philosophy underlying modern machine learning.

Random forests are a default baseline wherever tabular, structured data with mixed feature types needs a robust predictor without heavy tuning. In genomics and bioinformatics, they classify tumor subtypes from gene-expression matrices with far more features than samples, since random feature subsetting tolerates high dimensionality gracefully. In finance, they underlie credit-risk and fraud-detection models where interpretability of variable importance, alongside reasonable accuracy, is valued over squeezing out the last fraction of a percent of performance. Ecology and remote sensing use random forests for land-cover classification from satellite imagery, exploiting their robustness to noisy, correlated spectral bands. Search and recommendation systems have historically used forests (and their close relatives) as one component among several models for ranking. Statistical software ecosystems — R's `randomForest` and `ranger`, Python's `scikit-learn` `RandomForestClassifier`/`Regressor` — make the algorithm a near-universal first attempt on new tabular datasets before reaching for more elaborate ensembles. The conceptual lineage continues directly into Stacking and Model Blending, where random forests are frequently one of several diverse base learners whose predictions are themselves combined by a meta-model, and into gradient boosting, which replaces independent-tree averaging with sequential, error-correcting tree fitting.

Ask the tutor: How exactly does lowering `mtry` trade off per-tree bias against inter-tree correlation, and where is the optimal point for a dataset with only a few truly informative features among many noise features?