ml-models / Classical ML / Random forests core

Random forests

One deep decision tree memorizes its training set and changes a lot when the data changes. A random forest grows hundreds of them on resampled data, gives each split only a random handful of features, and averages the votes. This page derives why that works, and covers out-of-bag error, the two kinds of feature importance, and extremely randomized trees.

On this page
  1. Problem
  2. Intuition
  3. Mechanics
  4. Why averaging reduces variance
  5. Bagging
  6. Feature subsampling
  7. Prediction
  8. Out-of-bag error
  9. Feature importance
  10. Extremely randomized trees
  11. Worked example
  12. Importance on the same forest
  13. Implementation
  14. Tradeoffs
  15. Connections
  16. Read first
  17. Read next
  18. References

Problem

A fully grown decision tree has low bias: it can carve the feature space into as many boxes as there are training points. It pays for that with high variance. Move a few training points and the first split can change, and with it everything below. In the example on this page one such tree scores 1.00 on its training data and 0.757 on fresh data.

The bias–variance decomposition says the expected error is bias² plus variance plus noise. If we could average many trees, each fit to a different sample from the same distribution, the bias would stay the same and the variance would shrink. We only have one training set, so we need a way to make many different trees from it, and those trees need to disagree with each other for the average to help.

Intuition

Ask one expert and you get their quirks along with their knowledge. Ask a hundred experts who trained on overlapping but different material, and whose quirks point in different directions, and the quirks cancel while the shared knowledge adds up. But if all hundred studied the same textbook, they share the same quirks, and averaging removes little.

A random forest manufactures that diversity in two ways. Bagging (bootstrap aggregating) trains each tree on a bootstrap sample: n rows drawn with replacement from the n training rows. Feature subsampling lets each split consider only a random subset of the features, so a single strong feature cannot dominate the top of every tree. The rows each tree never saw give a free validation set, the out-of-bag sample.

How a random forest is trained and how it predicts The training set of n rows feeds B bootstrap samples, each drawn with replacement and each leaving about 37 percent of rows out of bag. Each sample grows one tree, and at every split the tree looks at only max_features randomly chosen features. To predict, every tree gives a class probability and the forest averages them. training set n rows, p features bootstrap 1 n draws, ≈37% left out tree 1 each split: max_features bootstrap 2 n draws, ≈37% left out tree 2 each split: max_features bootstrap B n draws, ≈37% left out tree B each split: max_features ⋮ average mean of P(y | x)

Two sources of randomness, rows per tree and features per split, then one average.

Mechanics

Why averaging reduces variance

Treat the prediction of tree b at a point x as a random variable Tb (random over the training set and the tree's own resampling). The trees are identically distributed, each with variance σ², and any two have correlation ρ, because they were grown from the same training set. The variance of their average is

Var(1/B · Σb Tb) = (1/B²)[B σ² + B(B − 1) ρ σ²] = ρ σ² + (1 − ρ) σ² / B

The second term vanishes as B grows; the first does not. More trees can only bring the variance down to ρσ², so the way to go further is to make ρ smaller without raising σ² or the bias too much. That is exactly what feature subsampling does. Adding trees never makes the expected error worse; past a point it just stops helping, so n_estimators is a compute budget, not a knob that overfits.

Bagging

A bootstrap sample draws n row indices uniformly with replacement. A given row is missed by one draw with probability 1 − 1/n, so by all of them with probability

(1 − 1/n)n → e−1 ≈ 0.368     (n = 100: 0.3660)

Each tree therefore sees about 63% of the distinct rows, some of them several times. scikit-learn does not copy the rows: _parallel_build_trees turns the drawn indices into counts with np.bincount and passes them to the tree as sample_weight, which gives the same splits. max_samples draws fewer rows per tree. The general BaggingClassifier wraps any estimator and can also subsample features once per estimator (random subspaces) instead of once per split.

Feature subsampling

At every node, the splitter shuffles the features and evaluates them one at a time until it has visited max_features of them, then keeps the best split found. If every feature drawn so far is constant in that node it keeps drawing, so a split is found whenever one exists. Defaults at 1.9.1:

  • RandomForestClassifier: max_features="sqrt", √p features per split, with bootstrap=True and n_estimators=100.
  • RandomForestRegressor: max_features=1.0, all features, which makes it plain bagged trees. The docstring notes that Breiman suggested p/3 and that Geurts et al. later found using all features works as well empirically.
  • max_features=None (or p) on a classifier turns feature subsampling off and gives bagging.

Smaller max_features lowers ρ but each tree gets weaker (σ² and bias rise), so it is the forest's main tuning knob. The trees are grown to full depth by default (max_depth=None, min_samples_leaf=1): low bias, and averaging is left to deal with the variance.

Prediction

scikit-learn's classifier averages the trees' class probabilities (each leaf's class fractions) and predicts the argmax, a "soft" vote. Breiman's paper used a majority vote of hard labels; with fully grown trees whose leaves are mostly pure the two rarely differ. The regressor averages the trees' predictions.

Out-of-bag error

For each training row, average only the trees whose bootstrap sample did not contain it, about 37% of them, and score that prediction. Each row is predicted by models that never saw it, so the out-of-bag (OOB) score estimates test performance without a held-out set or cross-validation. scikit-learn computes it with oob_score=True; it regenerates each tree's unsampled indices from the tree's saved random state, averages their predict_proba, and stores oob_score_ (accuracy by default) and oob_decision_function_. It requires bootstrap=True, and warns when some rows were in every tree's sample.

Feature importance

  • Impurity importance (feature_importances_, "Gini importance"): for each split, the node's weighted impurity minus its children's, summed per feature, normalized per tree, averaged over trees and normalized to sum to 1. It is free, but it is measured on training data, and a feature with many distinct values offers many thresholds to overfit with. The scikit-learn docstring warns about exactly this and points to permutation importance.
  • Permutation importance (sklearn.inspection.permutation_importance): score the fitted model on a dataset (preferably held out), shuffle one column, score again; the importance is the drop, averaged over n_repeats=5 shuffles by default. It works for any model and measures what the model relies on for these predictions. Two correlated features can share the credit, so each looks less important than it is.

Extremely randomized trees

Geurts, Ernst and Wehenkel (2006) push randomization further. For each of the max_features candidate features, the splitter draws one threshold uniformly between that feature's minimum and maximum in the node, and keeps the best of these random splits. ExtraTreesClassifier also defaults to bootstrap=False, so every tree sees the whole training set and the randomness comes only from the splits. Training is faster (no sorting to find thresholds), ρ falls further, and each tree is a bit worse; in practice extra trees and random forests are often close, and which wins depends on the data.

ComponentShape/ParamsMeaningSource
Random forest RandomForestClassifier(n_estimators=100, *, criterion="gini", max_depth=None, max_features="sqrt", bootstrap=True, oob_score=False, max_samples=None, …) Bagged best-split trees with per-split feature sampling. _forest.py 1174-1573
Bootstrap indices _generate_sample_indices(random_state, n_samples, n_samples_bootstrap, sample_weight) → (n_samples_bootstrap,) randint(0, n_samples, n_samples_bootstrap), or a weighted draw if sample_weight is given. _forest.py 95-113
Out-of-bag rows _generate_unsampled_indices(…) Regenerates the bootstrap, keeps rows with bincount == 0. _forest.py 116-129
Tree fitting _parallel_build_trees(tree, bootstrap, X, y, sample_weight, …) Bootstrap counts become the tree's sample_weight; "balanced_subsample" reweights per tree. _forest.py 132-179
Sample count _get_n_samples_bootstrap(n_samples, max_samples, sample_weight) None → n; int as given; float as a fraction of n (or of the weight total). _bootstrap.py 10-69
OOB predictions _compute_oob_predictions(X, y) → (n_samples, n_classes, n_outputs) Sums each tree's predict_proba on its unsampled rows and divides by the count per row. _forest.py 540-600, 786-808
Forest prediction predict_proba(X) → (n_samples, n_classes) Mean of the trees' class probabilities; predict takes the argmax. _forest.py 921-967, 882-919
Impurity importance feature_importances_ → (n_features,) Mean of per-tree importances over non-stump trees, renormalized to sum to 1. _forest.py 627-660
Split search node_split_best / node_split_random Fisher–Yates draw of up to max_features features; best threshold, or one uniform threshold per feature. _splitter.pyx 262-504, 507-736
Extra trees ExtraTreesClassifier(n_estimators=100, *, max_features="sqrt", bootstrap=False, …) Random-threshold trees on the full training set. _forest.py 1961-2346
Generic bagging BaggingClassifier(estimator=None, n_estimators=10, *, max_samples=None, max_features=1.0, bootstrap=True, bootstrap_features=False, …) Rows and features drawn once per estimator: pasting, bagging, random subspaces or random patches. _bagging.py 683-1189, 64-95
Permutation importance permutation_importance(estimator, X, y, *, scoring=None, n_repeats=5, …, max_samples=1.0) importances = baseline_score − permuted_score, with mean and std over repeats. _permutation_importance.py 114-313, 31-111

Worked example

Data. 100 training and 400 test rows with four features: x0 and x1 uniform on [0, 1], a continuous noise feature, and a binary noise feature. The label is 1 when x0 + x1 > 1, flipped for 10% of rows, so no model can beat about 0.90 on average. A diagonal boundary is awkward for axis-aligned trees, which must approximate it with a staircase.

Models. One fully grown tree on all the data; then 100 fully grown trees each for bagging (all 4 features per split), a random forest (2 = √4 features per split), and extra trees (2 features, random thresholds, no bootstrap). The code is the pure-Python version of the steps above, deterministic from fixed seeds.

ModelTrain accuracyTest accuracyMean single-tree test accuracyOOB accuracy
One tree1.0000.757——
Bagging, max_features 41.0000.8050.7360.790
Random forest, max_features 21.0000.8120.7080.780
Extra trees, max_features 21.0000.8050.710— (no bootstrap)
  • Every ensemble beats the single tree by about 5 points even though its own trees are individually worse: the forest's trees average 0.708 on the test set, below the single tree's 0.757, because each saw only ~63% of the rows and a random half of the features per split.
  • The forest's trees left out 37.1% of rows on average, against the formula's 36.6%. Its OOB accuracy, 0.780, is within a few points of the test accuracy, 0.812, computed without touching the test set. It runs slightly low because each OOB prediction averages only about 37 trees.
  • With this little data the three ensembles finish within about one point of each other; at 400 test rows one point is 4 predictions, so the ranking among them is not meaningful here.

Correlation. To measure ρ and σ², the same recipe was rerun on 20 fresh training sets of 100 rows, 20 trees each, scored at 100 fixed points. σ² is the variance of a single tree's predicted probability over all 400 trees; ρσ² is the part that comes from the training set, the variance of the per-set average with the within-set part removed.

Recipeσ² (one tree)ρρσ² (B → ∞)Variance at B = 10Variance at B = 100
Bagging, max_features 40.14580.1880.02740.03920.0286
Random forest, max_features 20.16340.1190.01950.03390.0210
Extra trees, max_features 20.16430.1380.02260.03680.0240

Restricting each split to 2 features raises a single tree's variance from 0.146 to 0.163 but cuts the correlation from 0.19 to 0.12, and the floor ρσ² falls from 0.0274 to 0.0195. With 20 training sets these estimates are rough, but the direction is the point: decorrelation buys more than the weaker trees cost.

Test accuracy against the number of trees Test accuracy of bagging, a random forest and extra trees as trees are added one at a time, from 1 to 100. All three start near 0.7 with one tree, climb steeply over the first ten trees and level off near 0.8, above the single full tree's 0.757 and below the noise ceiling of 0.9. 0.70.750.80.850.9 1255075100 number of trees B noise ceiling ≈ 0.9 one full tree bagging random forest extra trees

Most of the gain comes from the first 10–20 trees; after that the curves flatten instead of overfitting.

Variance of the averaged prediction against the number of trees Two curves of rho sigma squared plus one minus rho times sigma squared over B, for B from 1 to 50, using the measured values. Bagging starts at 0.146 and flattens toward 0.027; the random forest starts higher at 0.163 but crosses below by B = 2 and flattens toward 0.020. 00.050.10.15 11020304050 number of trees B bagging: ρσ² random forest: ρσ²

Adding trees removes the (1 − ρ)σ²/B term; only a smaller ρ lowers the floor.

Importance on the same forest

FeatureImpurity importance (training data)Permutation importance (test data, 5 repeats)
x₀0.4440.212 ± 0.023
x₁0.3710.182 ± 0.011
noise, continuous0.1570.015 ± 0.008
noise, binary0.0280.003 ± 0.005

The forest's test accuracy is 0.812. Shuffling x0 drops it by 0.21, while shuffling either noise feature barely moves it. Impurity importance still gives the continuous noise feature 15.7% of the total, because fully grown trees keep splitting on it to purify their last leaves in the training data. The binary noise feature has a single threshold to offer and gets 2.8%. That is the high-cardinality bias the scikit-learn docstring warns about.

Trees in a forest have pairwise correlation 0.3 and variance 0.2 each. What is the variance of an average of 100 of them, and of infinitely many?

0.3 × 0.2 + 0.7 × 0.2 / 100 = 0.0614; the limit is ρσ² = 0.06. Going from 100 trees to infinitely many removes only 0.0014.

Implementation

from sklearn.ensemble import RandomForestClassifier, ExtraTreesClassifier
from sklearn.inspection import permutation_importance

forest = RandomForestClassifier(
    n_estimators=500,        # more trees: slower, never worse in expectation
    max_features="sqrt",     # the main knob: smaller = less correlated trees
    min_samples_leaf=1,      # raise it for smoother probabilities and smaller trees
    oob_score=True,          # free generalization estimate (needs bootstrap=True)
    n_jobs=-1, random_state=0,
).fit(X_train, y_train)

forest.oob_score_                      # accuracy on out-of-bag rows
forest.oob_decision_function_          # (n_samples, n_classes) OOB probabilities
forest.feature_importances_            # impurity-based, from training data

result = permutation_importance(forest, X_val, y_val, n_repeats=10, random_state=0)
result.importances_mean, result.importances_std

extra = ExtraTreesClassifier(n_estimators=500, random_state=0).fit(X_train, y_train)

Trees are independent, so n_jobs=-1 fits them in parallel across cores. The forest keeps every tree in memory; on large data, fully grown trees have about as many leaves as rows, so min_samples_leaf, max_depth or max_samples are the levers for model size.

Tradeoffs

  • Strong default. Random forests need little tuning and no feature scaling, and (at 1.9.1) handle missing values natively. They are a standard first baseline on tabular data.
  • Versus gradient boosting. A forest averages deep, independent trees to reduce variance; gradient boosting adds shallow trees one after another to reduce bias. Tuned boosting usually wins on accuracy, but needs more tuning and can overfit with too many rounds, which a forest cannot.
  • No extrapolation. Each tree predicts an average of training targets, so a regression forest's output is bounded by the training targets' range. Trends outside the training range are lost.
  • Size and latency. Hundreds of deep trees can take hundreds of megabytes and many node lookups per prediction, where a linear model takes one dot product.
  • Probabilities. Averaged leaf fractions are smoother than a single tree's, but they tend to avoid the extremes 0 and 1; calibrate them if you need real probabilities.
  • Interpretability. One tree can be read; a forest cannot. Use permutation importance on held-out data rather than impurity importance, and keep in mind that correlated features split the credit.
  • OOB caveats. The OOB score uses fewer trees per row than the full forest, so it is slightly pessimistic for small forests, and it is not available without bootstrap (the extra-trees default).
Why does a random forest with max_features = p (all features) usually do worse than with √p, even though each tree is better?

With all features, every tree tends to pick the same strong features near the root, so the trees are highly correlated and averaging removes little variance: the ρσ² floor stays high. Subsampling features decorrelates them.

Connections

Read first

Read next

No page builds on this one yet.

References