Random Forest, in depth: correlated averaging, out-of-bag estimates, MDI versus permutation importance, and tuning

Why averaging trees works

Suppose each tree's prediction at a point has variance σ², and any two trees are correlated with coefficient ρ. The average of B such trees then has variance

Var(average) = ρ σ² + (1 − ρ) σ² / B

The second term goes to zero as you add trees. The first does not, however many trees you add. That one line explains how forests are designed. Adding trees can never push the error below ρσ², so the real lever is ρ, the correlation between trees. Bagging alone (bootstrap rows, all features at every split) leaves ρ high, because a strong feature wins the top split of almost every tree, and the trees end up looking alike. Breiman's random forest (2001) adds a second randomisation: each split may only choose among mtry randomly drawn features. Now the strong feature is sometimes unavailable, other structure gets used, and ρ drops. Each tree gets a little worse and the average gets better.

Breiman also bounded the forest's generalisation error by ρ̄(1 − s²)/s², where s is the strength (the average margin of the trees) and ρ̄ their average correlation. The trade-off is the same: shrinking mtry lowers both ρ and s, and the best value balances the two. The relative variance of the average, ρ + (1 − ρ)/B, makes the diminishing returns concrete:

In the worked example below, 50 trees using √d features per split had an average pairwise correlation of 0.60 in their predicted probabilities. Using all features (plain bagging) raised it to 0.70. Going past about a hundred trees mostly buys stability, not accuracy.

The algorithm and a from-scratch forest

The algorithm itself is short:

for b in 1..B:
    S_b  = draw n rows from the training set with replacement
    T_b  = grow a tree on S_b; at every node:
               F = sample mtry features without replacement
               split on the best (feature, threshold) among F
           stop only at min_samples_leaf / max_depth (no pruning)
predict(x) = majority vote (or mean probability) of T_1..T_B   # classification
predict(x) = mean of T_1(x)..T_B(x)                            # regression

Here it is as runnable Python, with scikit-learn's single tree doing the split search. Passing max_features to the tree is what makes it a forest rather than plain bagging, because the tree redraws that feature subset at every node:

import numpy as np
from sklearn.tree import DecisionTreeClassifier

def fit_forest(X, y, n_trees=200, max_features="sqrt", seed=0):
    rng = np.random.default_rng(seed)
    n, classes = len(y), np.unique(y)
    trees, votes = [], np.zeros((n, len(classes)))
    for _ in range(n_trees):
        idx = rng.integers(0, n, size=n)              # bootstrap: n draws with replacement
        oob = np.setdiff1d(np.arange(n), idx)          # about 36.8% of rows
        t = DecisionTreeClassifier(max_features=max_features,  # fresh feature subset per split
                                   random_state=int(rng.integers(2**31)))
        t.fit(X[idx], y[idx])
        trees.append(t)
        if len(oob):
            p = t.predict_proba(X[oob])               # columns follow t.classes_
            cols = np.searchsorted(classes, t.classes_)
            votes[np.ix_(oob, cols)] += p
    seen = votes.sum(axis=1) > 0
    oob_acc = np.mean(classes[votes[seen].argmax(axis=1)] == y[seen])
    return trees, classes, oob_acc

def predict(trees, classes, X):
    probs = np.zeros((len(X), len(classes)))
    for t in trees:
        probs[:, np.searchsorted(classes, t.classes_)] += t.predict_proba(X)
    return classes[probs.argmax(axis=1)]

On a 3,000-row synthetic problem (2,250 training rows, 10 features, 4 of them informative), this reached 0.941 out-of-bag accuracy and 0.957 on the held-out rows. The searchsorted mapping matters: a bootstrap sample can miss a rare class entirely, and then that tree's probability columns no longer line up with the global class list.

Out-of-bag estimation

A bootstrap of n rows leaves any given row out with probability (1 − 1/n)ⁿ, which tends to 1/e ≈ 0.368. For n = 1,000 it is 0.3677. So every row is out of bag for roughly a third of the trees, and those trees can score it as if it were unseen. Aggregating only those votes for each row gives the out-of-bag (OOB) estimate. It costs no extra training, and with enough trees it closely tracks cross-validation error.

In scikit-learn, set oob_score=True and read oob_score_ after fitting. Three caveats. With few trees, some rows are never out of bag and the library warns that the estimate is unreliable; this happened at B = 10 in the run below. Each row is scored by only about B/e trees, so the OOB estimate is slightly pessimistic for small forests. And OOB assumes rows are exchangeable. For time series or grouped data, such as several rows per customer, a row's twin is usually in the bag, so OOB is optimistic. Use a time-ordered or grouped split instead.

Worked example

The data: 4,000 rows from make_classification with shuffle=False, so the column roles are known: x0–x3 informative, x4–x5 redundant (linear combinations of the informative ones), x6–x9 pure noise. An eleventh column of random integers from 0 to 1,999 stands in for a row ID that leaked into the features. Training used 3,000 rows and testing the other 1,000, with scikit-learn 1.8.0 on a laptop:

Three things stand out. Going from 10 to 100 trees helped a lot, and going from 100 to 500 did not help at all. That matches the variance table. The max_features setting moved test accuracy by half a point here. It matters more when a few features dominate. And the 300-tree default model (OOB 0.917, test 0.910) grew trees with mean depth 20 and 225 leaves, 134,932 nodes in total, and pickled to 10.9 MB. With min_samples_leaf=5 the pickle shrank to 6.4 MB and test accuracy fell from 0.910 to 0.903. That is a typical size-accuracy trade, and worth measuring rather than assuming.

Feature importance: MDI versus permutation

A forest reports feature_importances_, the mean decrease in impurity (MDI): the total impurity reduction from splits on each feature, averaged over trees. It is computed on training data, and that causes two well-known problems. Features with many possible split points get more chances to look useful by accident. And correlated features split the credit in arbitrary ways. Permutation importance (sklearn.inspection.permutation_importance) instead shuffles one column of held-out data and measures how much the score drops. Same 300-tree model, test set, 10 repeats:

Look at x2 and x5. x2 is truly informative, yet permuting it costs under two points of accuracy, because the redundant columns are built partly from it and cover for it. x5 holds no information of its own, yet MDI ranks it above x2. Both measures answer real questions, but different ones. MDI describes how the model was built; permutation describes what the model relies on for unseen data. Both blur a group of correlated features: shuffle one of them and the others cover for it. If the question is whether a group matters, permute the whole group together or drop it and retrain. Here the fake row ID did not stand out under either measure. A leak that actually correlates with the label, such as a time-ordered ID, would top both lists, and that is how to spot one.

Tuning

Forests are known for working well with defaults, and mostly they do. These are the knobs that matter, with scikit-learn 1.8 defaults:

Tune max_features and min_samples_leaf with OOB or cross-validation. Fix n_estimators large enough at the end. For broader searches, Bayesian optimisation beats grid search, but forests have so few sensitive knobs that a small grid is usually enough.

Operational guidance

Serving cost is the price of averaging. A prediction walks B root-to-leaf paths, each about as long as the tree depth, so latency grows with B times depth, and memory grows with the total node count. Production habits:

• Cap size with min_samples_leaf or max_leaf_nodes and measure the pickle. Unbounded trees on a million rows can reach gigabytes.
• Batch predictions. Per-row calls pay Python overhead B times; vectorised predict_proba on thousands of rows amortises it.
• Use warm_start=True and raise n_estimators to add trees to a fitted forest instead of retraining, which is useful when you're looking for the OOB plateau.
• Pin random_state and the library version in the model artifact. Retraining with a different seed changes individual predictions even when accuracy stays the same.
• Monitor the input distribution, not just accuracy. Trees cannot extrapolate: a feature beyond its training range falls into the last leaf, and the model quietly predicts a constant there.

Failure modes

• Extrapolation. A regression forest predicts the average of training targets in a leaf, so it can never output a value beyond the training range. Trends over time flatten out at the edge.
• Leakage that OOB cannot see. Duplicate rows, several rows per entity, or future data put a row's copy in the bag. OOB and random cross-validation then both look excellent and production fails.
• Poor probability calibration. Forest vote fractions are often pulled away from 0 and 1. If downstream decisions need real probabilities, calibrate on held-out data with CalibratedClassifierCV.
• Misreading MDI as causal or as reliance. See the importance table. High-cardinality and correlated features distort it.
• Sparse, high-dimensional data. On text-like data with many weak signals, a random feature subset at a split often contains nothing useful. Linear models or boosting usually win.

Trade-offs

Compared with gradient boosting, a forest reduces variance by averaging deep, independent trees; boosting reduces bias by adding shallow trees one after another, each fitting the previous ones' errors. Boosting usually wins on accuracy for tabular data once it is tuned. A forest is harder to break: it has fewer sensitive hyperparameters, can't overfit by adding trees, parallelises perfectly and gives you OOB validation for free. It is a strong first baseline and a robust choice when you can't afford tuning. If the forest and a tuned booster are within noise of each other, keep the forest. For the underlying bias-variance picture, see the bias-variance trade-off.

What to do next

1. Fit RandomForestClassifier(oob_score=True, n_jobs=-1) on your data and record OOB and held-out scores side by side. If they disagree badly, look for leakage or grouping.
2. Plot OOB score against n_estimators with warm_start, and pick the plateau.
3. Grid max_features over sqrt, 0.33 and 0.5 and min_samples_leaf over 1, 3 and 10.
4. Compare feature_importances_ with permutation_importance on held-out data, and investigate any feature that ranks high on only one of them.
5. Measure pickle size and batch prediction latency before deploying, and cap leaf size if either is too big.
6. Train a gradient-boosted model on the same split, and keep the forest unless the booster wins clearly.