Random Forests

Background

Breiman (2001) combined bagging (Bootstrap AGGregating) with random feature selection to reduce tree correlation
One of the most robust and widely-deployed algorithms in production ML
Provides both strong accuracy and reliable feature importance estimates

The Concept

Random forests train many decision trees, each on a random bootstrap sample of data and a random subset of features. Predictions are aggregated by majority vote (classification) or averaging (regression). Diversity among trees reduces variance without increasing bias much.

How it Links

Directly extends decision trees via bagging and feature randomization
Feature importance from forests is widely used in feature selection and model interpretability
Connects to bootstrap theory, ensemble learning, and the bias-variance trade-off

Concrete Example

Diagnosing disease from a patient record: each of 500 trees trained on slightly different patient subsets votes on the diagnosis. Because each tree saw different examples, they disagree on hard cases in ways that tend to cancel out - making the ensemble more reliable than any single tree.

Prerequisites

Decision trees (CART, ID3, C4.5), Bias, variance, over/under-fitting, Evaluation metrics

Learning outcomes

Explain bagging as variance reduction by averaging i.i.d. (or correlated) bootstrap-trained learners.
Derive the variance of an average of n correlated estimators with pairwise correlation rho, and read off why decorrelation matters.
Describe the random-feature-subspace trick that distinguishes random forests from plain bagging.
Compute OOB error and explain why it approximates a held-out set without one.
Compare impurity-based and permutation-based feature importance, and recognize when each lies.

TL;DR

A random forest is a bag of decorrelated decision trees. Each tree is grown with the standard CART procedure [5] on a bootstrap sample of the data [1], and at each split only a random subset of features is considered [2]. The forest predicts the majority class (classification) or the mean (regression) across trees. The two sources of randomness average away most of the high variance that single trees suffer from, while leaving bias roughly unchanged. Out-of-bag (OOB) error is a free held-out estimate that uses the roughly $37\%$ of trees each example was not in. Feature importance comes in two flavours: impurity-based (cheap, biased toward high-cardinality features [4]) and permutation-based (expensive, far more reliable). Extra Trees [3] drop the bootstrap and pick split thresholds at random, trading a sliver of accuracy for speed.

Intuition

Single decision trees have low bias and high variance: any small perturbation of the training set produces a different tree. Averaging many such trees cancels the variance and keeps the bias, if the trees are independent enough. Random forests engineer that independence with two tricks:

Bagging. Train each tree on a bootstrap sample (sampling $n$ examples with replacement from the training set of size $n$ ). Each tree sees a slightly different dataset.
Random feature subspaces. At every split, only consider a random subset of $m$ features (typically $m = \sqrt{d}$ for classification, $m = d/3$ for regression). This forces different trees to make different splits, even on similar data.

Why decorrelation matters more than independence

Bagging alone reduces variance by a factor of $n$ only when trees are independent. In practice they are highly correlated because they share most of the data. Random forests deliberately decorrelate the trees with feature subsampling, paying a small extra bias for a big drop in correlation. The algebra below makes this precise: the asymptotic variance floor of $n$ correlated estimators is $\rho \sigma^{2}$ , so dropping $\rho$ even slightly matters more than adding more trees.

Math

Variance reduction from averaging correlated estimators

Setup

Let $X_1, \dots, X_n$ be identically distributed estimators with variance $\sigma^{2}$ and pairwise correlation $\operatorname{Corr}(X_i, X_j) = \rho$ for $i \ne j$ . The ensemble estimator is the average

\bar{X} = \frac{1}{n}\sum_{i=1}^{n} X_i.

Variance of the average

\operatorname{Var}(\bar{X}) = \frac{1}{n^{2}} \operatorname{Var}\!\left(\sum_{i=1}^{n} X_i\right) = \frac{1}{n^{2}}\!\left[\sum_{i=1}^{n}\operatorname{Var}(X_i) + \sum_{i \ne j}\operatorname{Cov}(X_i, X_j)\right].

Substituting $\operatorname{Var}(X_i) = \sigma^{2}$ and $\operatorname{Cov}(X_i, X_j) = \rho \sigma^{2}$ :

\operatorname{Var}(\bar{X}) = \frac{1}{n^{2}}\!\left[n \sigma^{2} + n(n-1)\rho \sigma^{2}\right] = \rho \sigma^{2} + \frac{1 - \rho}{n} \sigma^{2}.

What this tells us

\boxed{\,\operatorname{Var}(\bar{X}) = \rho \sigma^{2} + \frac{1 - \rho}{n} \sigma^{2}.\,}

Two regimes:

As $n \to \infty$ : the variance converges to $\rho \sigma^{2}$ . Adding more trees past a certain point reduces variance only along the second term.
As $\rho \to 0$ : the variance converges to $\sigma^{2}/n$ , the i.i.d. ideal.

Bagging alone tries to push $n$ large while $\rho$ stays high (trees see overlapping data). Random forests instead push $\rho$ down via feature subsampling, which is why they reliably outperform plain bagging on the same dataset [2][6].

Effect of $m$ (features per split)

Smaller $m$ -> lower $\rho$ between trees (they are forced to disagree on splits) but higher per-tree bias (the split criterion is evaluated over a smaller candidate set). The optimum is empirical; $m \approx \sqrt{d}$ for classification and $m \approx d/3$ for regression are Breiman’s defaults and remain the sklearn defaults.

Out-of-bag error: a free held-out estimate

How OOB works

For each tree, the bootstrap sample contains $n$ draws with replacement from a training set of size $n$ . The probability that a given example is not in a particular bootstrap sample is

\left(1 - \frac{1}{n}\right)^{n} \xrightarrow{n \to \infty} \frac{1}{e} \approx 0.368.

So every example is “out of the bag” for roughly $37\%$ of the trees. To compute OOB error, predict each training example using only the trees for which it was OOB, then compare to the true label.

Why the estimate is good

Each example’s OOB prediction averages over $\approx 0.37 B$ trees (for a forest of $B$ trees). For modestly sized forests this is enough trees that the estimate is stable. Crucially, the OOB prediction never used that example for training, so the estimate is held-out by construction. Empirically the OOB error tracks cross-validated error closely, with no extra training cost.

Caveats

OOB error is a biased estimate when the forest is small (few OOB trees per example).
It is not a substitute for a true held-out test set when you also do hyperparameter tuning - the standard rule “do CV on a fold that you do not touch” still applies.
OOB scoring assumes i.i.d. data; for time-series, group, or stratified splits you still need explicit cross-validation.

Algorithm

Step	Operation
1	For tree b = 1..B (parallel):
2	Draw a bootstrap sample S_b of size n from the training set (with replacement).
3	Grow a decision tree T_b on S_b. At each split, sample m features uniformly at random (without replacement) and pick the best split among them.
4	Grow until min_samples_leaf or max_depth is reached. NO post-pruning.
5	Predict: average tree predictions for regression; majority-vote (or class probabilities averaged) for classification.
6	OOB scoring: for each example i, average the trees b such that i is NOT in S_b, then compare to y_i.

# Random forest pseudocode (sklearn-style)
def random_forest_fit(X, y, B=100, m=None):
    n, d = X.shape
    m = m or int(round(d ** 0.5))            # classification default
    forest = []
    in_bag = np.zeros((B, n), dtype=bool)
    for b in range(B):
        idx = rng.integers(0, n, size=n)     # bootstrap with replacement
        in_bag[b, idx] = True
        # Each tree's split routine samples m features per node.
        tree = DecisionTreeClassifier(max_features=m, max_depth=None,
                                      min_samples_leaf=1).fit(X[idx], y[idx])
        forest.append(tree)
    return forest, in_bag
 
def random_forest_predict(forest, X):
    votes = np.stack([t.predict(X) for t in forest])    # (B, n_test)
    return np.apply_along_axis(lambda c: np.bincount(c).argmax(), 0, votes)

How RF compares to a single tree and to gradient boosting

Property	Single decision tree	Random forest	Gradient boosting (GBDT)
Bias	low (deep tree)	low (same as a single deep tree)	low (sequential bias correction)
Variance	very high	low (averaged over decorrelated trees)	low to moderate (depends on learning rate, depth)
Training	one tree, sequential	B trees, embarrassingly parallel	B trees, strictly sequential
Tree depth	deep, may need pruning	deep (no pruning - variance handled by averaging)	shallow stumps (depth 3-8)
Sensitive to noisy labels?	yes (memorises)	no (averaging absorbs noise)	yes (sequentially fits noise into residuals)
Overfitting risk	severe	mild (more trees rarely hurts)	high (early stopping is mandatory)
Interpretability	high (one rule list)	medium (feature importance, partial dependence)	medium (same tools as RF, plus SHAP)

Implementations

The numpy version is a thin bagging wrapper around the from-scratch CART implementation from the Decision Trees page: sample with replacement, fit a tree, repeat, and majority-vote at predict time. The sklearn versions are the production one-liners.

python

import numpy as np

# Reuses the build_tree / predict_one helpers from the Decision Trees page.
# Here we add a thin bagging wrapper around them.

def bag_fit(X, y, build_tree, B=50, max_depth=8, seed=0):
  rng = np.random.default_rng(seed)
  n = X.shape[0]
  forest = []
  in_bag = np.zeros((B, n), dtype=bool)
  for b in range(B):
      idx = rng.integers(0, n, size=n)         # bootstrap with replacement
      in_bag[b, idx] = True
      tree = build_tree(X[idx], y[idx], max_depth=max_depth)
      forest.append(tree)
  return forest, in_bag

def bag_predict(forest, X, predict_one):
  preds = np.stack([
      np.array([predict_one(t, x) for x in X]) for t in forest
  ])                                            # (B, n_test)
  out = np.zeros(X.shape[0], dtype=int)
  for j in range(X.shape[0]):
      vals, counts = np.unique(preds[:, j], return_counts=True)
      out[j] = int(vals[np.argmax(counts)])
  return out

def oob_score(forest, in_bag, X, y, predict_one):
  n = X.shape[0]
  preds = np.full(n, -1, dtype=int)
  for i in range(n):
      oob_trees = [forest[b] for b in range(len(forest)) if not in_bag[b, i]]
      if not oob_trees:
          continue
      votes = [predict_one(t, X[i]) for t in oob_trees]
      vals, counts = np.unique(votes, return_counts=True)
      preds[i] = int(vals[np.argmax(counts)])
  mask = preds >= 0
  return float((preds[mask] == y[mask]).mean())

About 30 lines of bagging on top of the from-scratch CART. Add per-node feature subsampling inside build_tree to turn this into a full random forest.

Run a small sklearn random forest live in the browser:

Idle (packages: numpy, scikit-learn)

(no output yet)

Real-world uses

Domain	System	Why random forests
Tabular Kaggle / business analytics	Default first model on any tabular dataset	Strong baseline with little tuning, robust to noisy features, OOB makes the train/test split nearly free.
Fraud and AML detection	Bank and payment-platform risk models	Handles heterogeneous categorical and continuous features, gives ranked feature importance for analyst review.
Genomics and bioinformatics	GWAS variant prioritization, microbiome classification	Works under d much larger than n with thousands of correlated features; permutation importance distinguishes signal.
Remote sensing	Pixel-level land-cover classification (e.g. Sentinel-2 + Random Forests)	Mixed numeric features (band reflectances) and noisy labels; large training sets are routine.
Autonomous-vehicle perception (early)	Random-forest object detectors before CNNs (Microsoft Kinect body-part classifier 2011)	Real-time inference on commodity hardware, robust to noisy depth pixels.

Pitfalls

Impurity importance is biased toward high-cardinality features

The default feature_importances_ in sklearn averages the impurity decrease each feature contributes across all trees. Strobl et al. 2007 showed this estimator systematically over-rewards features with many distinct values (continuous or high-cardinality categoricals) because they offer many candidate thresholds and therefore many opportunities to “win” a split, even when they are pure noise [4]. Use permutation importance (sklearn’s permutation_importance) for any reporting or feature-selection decision, and never publish impurity importance without this caveat.

Cannot extrapolate beyond the training range

Each tree predicts a leaf-constant value, and so does the forest (the average of leaf-constants). Test points outside the convex hull of the training data get the closest training-region’s mean - the forest does not know there is “more line” to extend. For target variables that grow unboundedly in time or covariate value (e.g. future house prices, energy demand growth), use a model with a parametric tail.

Correlated features split importance arbitrarily

If $x_1$ and $x_2$ are highly correlated and both informative, the forest splits the credit between them roughly at random across trees. Importance scores for correlated groups are therefore not directly interpretable; use grouped permutation importance (permute the group together) or compute SHAP values with a TreeSHAP background distribution to get coherent per-group attributions.

Memory grows with tree depth and B

A fully grown forest with $B$ deep trees can occupy gigabytes of RAM in production. max_depth, min_samples_leaf, and max_leaf_nodes are not just regularizers; they are also operational caps. For latency-sensitive serving, prefer HistGradientBoosting or compile the forest with treelite / m2cgen.

OOB is your free CV - use it

Setting oob_score=True adds about 5% to training time and gives an out-of-sample error estimate that closely tracks 5-fold CV in most cases. For early-stage experimentation it is the cheapest way to know your forest’s generalization gap.

Interview Q&A

Derive the variance of an average of n correlated estimators with pairwise correlation rho. What does it imply for ensembles?research

Let $X_1, \dots, X_n$ be identically distributed with $\operatorname{Var}(X_i) = \sigma^{2}$ and $\operatorname{Corr}(X_i, X_j) = \rho$ for $i \ne j$ . Then

\operatorname{Var}\!\left(\frac{1}{n}\sum_{i=1}^{n} X_i\right) = \frac{1}{n^{2}}\!\left[\sum_{i} \operatorname{Var}(X_i) + \sum_{i \ne j}\operatorname{Cov}(X_i, X_j)\right] = \frac{1}{n^{2}}\!\bigl[n \sigma^{2} + n(n-1)\rho \sigma^{2}\bigr],

which simplifies to

\operatorname{Var}(\bar{X}) = \rho \sigma^{2} + \frac{1 - \rho}{n} \sigma^{2}.

Two consequences:

Variance floor. As $n \to \infty$ , $\operatorname{Var}(\bar{X}) \to \rho \sigma^{2}$ . Adding trees indefinitely cannot drive variance below $\rho \sigma^{2}$ , so $\rho$ matters more asymptotically than $n$ .
Decorrelation pays. Reducing $\rho$ from say $0.6$ to $0.3$ halves the asymptotic variance for free, regardless of $n$ . This is exactly the role of the random-feature-subspace trick in random forests [2][6].

In practice, the variance reduction is the only knob random forests turn (bias is essentially that of a deep tree). Boosting, by contrast, attacks bias.

Why do random forests pick a random subset of features at each split?onsite

Bagging alone trains each tree on a bootstrap sample, but trees still see the same set of $d$ features and tend to pick similar splits at the top of the tree (one or two strong features dominate). The result is a forest of highly correlated trees with $\rho$ near $1$ , and the variance formula above shows averaging in this regime barely helps.

Random forests force decorrelation by sampling $m$ features uniformly at random at every node, where $m \ll d$ (typically $\sqrt{d}$ for classification). A strong feature only gets considered in a fraction $m/d$ of nodes, so different trees split on different features near the root and produce different leaf partitions. The trees are individually slightly weaker (the criterion is evaluated over a smaller candidate set) but collectively far less correlated, and the average wins by the variance formula [2].

Sketch the bias-variance picture for ensembles: bagging vs boosting.research

Both methods average many weak trees, but they target different terms of the mean-squared error decomposition:

Bagging (and random forests). Each tree is grown deep, so individually it is low-bias, high-variance. The bootstrap and feature-subspace tricks decorrelate the trees so that averaging cancels variance without changing bias. Net effect: same bias as a single deep tree, much lower variance. More trees almost never hurt.
Boosting. Each tree is shallow (typically depth 3-8), so individually it is high-bias, low-variance. The trees are trained sequentially on residuals, so each one corrects the bias of the running ensemble. Net effect: bias drops with iteration count, variance grows slowly as the model fits ever finer residual structure. Too many iterations overfits, hence the early stopping requirement.

A rough mental model: bagging fixes “high-variance models” by averaging; boosting fixes “high-bias models” by stacking. Random forests sit firmly in the first camp [6].

Why is permutation importance preferred over impurity importance for correlated features?onsite

Impurity importance (Mean Decrease in Impurity, MDI) sums the impurity drop a feature contributes across every node it splits on, weighted by the proportion of samples reaching that node. Two structural biases:

High-cardinality favoritism. Features with many distinct values offer many candidate thresholds, so even noise features can sometimes split better than a coarser informative feature. Strobl et al. 2007 demonstrated this directly: random forests assign substantial impurity importance to a randomly generated feature whenever its cardinality is high [4].
Correlation double-counting. If $x_1$ and $x_2$ are perfectly correlated, the splitter chooses one essentially at random. Across many trees the credit splits roughly evenly between them, giving each apparent half-importance even though either alone explains the target as well as the pair.

Permutation importance instead measures the drop in held-out score when the values of one feature are randomly shuffled. The feature still has the same marginal distribution, so any score drop is causal for the model’s predictions. It is more expensive (one full pass per feature) but is honest about correlated groups (each correlated feature shows roughly the same individual importance, which is correct - permuting one alone leaves the model with the other to compensate). For final reporting, prefer permutation importance, or grouped permutation importance for known feature groups.

Derive the OOB sample fraction. Why is OOB error a reasonable proxy for held-out error?onsite

Each bootstrap sample draws $n$ items with replacement from $n$ . The probability that example $i$ is not in a particular bootstrap sample is

P(i \notin S_b) = \left(1 - \frac{1}{n}\right)^{n} \xrightarrow{n \to \infty} e^{-1} \approx 0.368.

So in a forest of $B$ trees, example $i$ is OOB for roughly $0.368 B$ of them. The OOB prediction for example $i$ aggregates only those trees, none of which saw $i$ during training. This is exactly the held-out-prediction setup, with two caveats:

The OOB prediction averages over $\sim 0.37 B$ trees instead of $B$ , so it is slightly noisier than the full-forest prediction. For $B \ge 200$ the gap is negligible.
OOB error is itself a random variable (depends on the bootstrap draws); for small $B$ it can be high-variance.

Empirically, OOB error tracks 10-fold CV within a few tenths of a percent on most datasets, making it the cheapest reliable estimate of forest generalization. It does not substitute for a real held-out set when you also tune hyperparameters, because OOB is computed on the same data those hyperparameters touched [2].

Check yourself

Score: 0 / 5(0 answered)

1. In a random forest, what is the asymptotic variance of the average of n trees with pairwise correlation rho and per-tree variance sigma^2?
2. Why does a random forest sample features at each split rather than once per tree?
3. What fraction of trees, on average, is each example "out of bag" for?
4. Which feature-importance method is biased toward high-cardinality features?
5. How does Extra Trees differ from a standard random forest?

Build it yourself

A short evening project:

Add per-node feature subsampling to the from-scratch CART you wrote on the Decision Trees page. That is the only delta needed to turn bagging into a real random forest.
Implement OOB scoring by tracking which bootstrap rows each tree saw, and confirm OOB accuracy tracks a 5-fold CV estimate to within a percentage point on a synthetic make_classification dataset.
Implement permutation importance: shuffle each test column in turn, re-score, record the drop. Compare the ranking with sklearn’s feature_importances_ on a dataset that includes one obviously high-cardinality noise feature and watch the two rankings disagree.
Stretch: add an Extra-Trees variant by replacing exhaustive threshold search with a single random threshold per (feature, node). Time the speedup and confirm accuracy stays within 1-2 points.

Interactive Demo

Random Forest Decision Boundary

Watch how individual tree boundaries (dashed lines) average out to a stable forest boundary (bold line) as you add more trees.

Number of Trees5

Trees

Forest boundary

x = 4.79

OOB Error est.

19.9%

Individual tree Forest boundary Class A Class B

Tip: Increase the number of trees and watch individual decision boundaries average out to a smoother consensus boundary - and the OOB error decrease.

References

Breiman, L. (1996). Bagging Predictors. Machine Learning 24(2), 123-140. doi:10.1007/BF00058655
Breiman, L. (2001). Random Forests. Machine Learning 45, 5-32. doi:10.1023/A:1010933404324
Geurts, P., Ernst, D., and Wehenkel, L. (2006). Extremely Randomized Trees. Machine Learning 63, 3-42. doi:10.1007/s10994-006-6226-1
Strobl, C., Boulesteix, A.-L., Zeileis, A., and Hothorn, T. (2007). Bias in random forest variable importance measures: illustrations, sources and a solution. BMC Bioinformatics 8:25. doi:10.1186/1471-2105-8-25
Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth & Brooks/Cole. ISBN 978-0-412-04841-8
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/

Decision Trees Gradient Boosting