Random Forests

You are in an interview for a fraud-detection team, and the interviewer puts this in front of you: a pruned decision tree scores 0.99 accuracy on the training set and 0.71 ROC-AUC on holdout, then asks what you would change first. The answer they are fishing for is not a finer hyperparameter search on that one tree. It is: train many trees on different resamples of the data and average their predictions. That is bagging, and a random forest is bagging with one extra ingredient that makes it actually work.

Bootstrapping is the first ingredient. Each tree gets a sample of n rows drawn with replacement from the original training set. The probability that a given row is never drawn in n tries is (1 − 1/n)^n, which converges to e⁻¹ ≈ 0.368. So each tree trains on roughly 63.2% of the rows (the in-bag set) and leaves about 36.8% out (the out-of-bag set, which pays off in the third chapter). Different trees therefore see different data, make different mistakes, and averaging cancels part of the noise.

Why does averaging help at all? For B trees with per-tree variance σ² and pairwise correlation ρ, the variance of their mean is:

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

Read that formula carefully — it explains both the power and the ceiling of the method. Adding trees drives the second term toward zero, and that part is fully under your control. The first term, ρ·σ², never shrinks: it is the correlation floor. If every tree makes the same mistakes, ρ = 1 and averaging buys nothing. Deep trees trained on one dataset are highly correlated because they all discover the same dominant split at the root, which is why plain bagging of decision trees improves accuracy only slightly. Lowering that floor is the entire point of a random forest.

from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import roc_auc_score

X_train, X_test, y_train, y_test = train_test_split(X, y, stratify=y, test_size=0.25)

forest = RandomForestClassifier(
    n_estimators=500,      # B in the variance formula
    bootstrap=True,        # sample rows with replacement (the default)
    random_state=42,
    n_jobs=-1,
)
forest.fit(X_train, y_train)
print(roc_auc_score(y_test, forest.predict_proba(X_test)[:, 1]))

Notice what n_estimators=500 does not do: it does not make the forest overfit faster. Each tree is grown deep on its own bootstrap, so training error keeps sinking, but generalization error plateaus — extra trees cost memory and inference latency, not accuracy. That is a different shape from boosting, where each additional round can push a model past the point of no return. An interview follow-up you should be ready for: bagging reduces variance by averaging independent-ish learners; boosting reduces bias by sequentially correcting errors. You will make that contrast precise in Gradient Boosting Machines.

The pruning trade-offs from Tree Pruning and Hyperparameters do not disappear inside a forest — they move. You generally leave individual trees deep and control the ensemble from the outside with max_features, min_samples_leaf, and the number of trees, because aggressive per-tree pruning fights the decorrelation you are paying for. Stating that inversion cleanly — regularize the ensemble, not its members — signals that you understand where the variance actually lives. The ingredient that makes decorrelation real is random feature selection at every split, which is the next chapter.

Bootstrap sampling alone changes which rows a tree sees. If a single feature — say, transaction_amount — dominates the data, then every tree picks it at the root, most trees pick it again at the next node, and you are back to highly correlated learners with a high correlation floor ρ. Averaging them barely helps. Random forests break this with a second source of randomness: at each node, the split search only considers a random subset of the features.

That is feature bagging (Breiman called it the "random subspace" idea). With p features, each node draws mtry candidates, finds the best split among them, and moves on. The conventional values:

For 100 features, √p = 10 — each split competes among 10 candidates instead of 100. If transaction_amount happens to be excluded at a node, the tree must settle for the second-best feature, and now two trees built on the same bootstrap can disagree about the root split. The disagreement is the point: decorrelation is bought with a little per-tree strength, and √p sits near the sweet spot.

import numpy as np
from sklearn.ensemble import RandomForestClassifier

scores = {}
for mtry in ["sqrt", 0.25, 0.5, 1.0]:
    rf = RandomForestClassifier(
        n_estimators=300,
        max_features=mtry,   # fraction or count of features offered to each split
        min_samples_leaf=5,  # ensemble-level regularization, not per-tree pruning
        oob_score=True,
        random_state=42,
        n_jobs=-1,
    ).fit(X, y)
    scores[mtry] = rf.oob_score_

print({k: round(v, 4) for k, v in scores.items()})

Run that on real data and you will usually see a shallow arc: too few features per split and accuracy drops because trees are too weak; too many and it drops back because trees converge on the same splits. max_features is one of the few random-forest hyperparameters with a real optimum worth tuning, alongside min_samples_leaf (larger values smooth the leaves and fight noise) and n_estimators (raise it until OOB error stops moving — usually 300–1000).

Note the rightmost column's shape: accuracy peaks near √p and decays toward the plain-bagging baseline as candidates approach p. A tuning table worth running on your own data (200 features, illustrative values) makes the arc visible:

A related variant, ExtraTreesClassifier, adds a third randomness source — split thresholds drawn uniformly at random instead of searched — trading individual tree strength for extra decorrelation and speed. It shares the same max_features semantics, so the same tuning logic transfers.

Two details interviewers probe. First, feature sampling happens at every node, not once per tree — that is what keeps splitting all the way down diverse, not just the root. Second, randomness cuts both ways: an irrelevant feature can occasionally win a subspace split, which is why forests tolerate noisy inputs but also why you should drop obviously useless columns instead of hoping the ensemble handles them. Note also that nothing here is scale-sensitive: a forest splits on thresholds, so 50,000 dollars and 30 years need no standardization. Distance-based models are not so forgiving, as Distance and Similarity Metrics will show.

The result of this machinery is a set of trees that disagree productively — and a free validation estimate, because every row was left out of roughly a third of them.

Each row sits out of about 36.8% of the trees' bootstrap samples. That is not wasted data — it is a validation set with no extra splitting, and it is the trick that makes random forests cheap to tune.

The mechanics: for row i, collect predictions from only the trees where i was out-of-bag, then aggregate those predictions — majority vote for classification, mean for regression. The out-of-bag (OOB) error is computed over all n rows exactly as if they had never been seen:

rf = RandomForestClassifier(
    n_estimators=500,
    oob_score=True,          # requires bootstrap=True
    random_state=42,
    n_jobs=-1,
).fit(X_train, y_train)

print(rf.oob_score_)                 # e.g. 0.913
print(rf.oob_decision_function_[:3]) # per-class vote fractions for the first rows

With 500 trees, each row is validated by roughly 0.368 × 500 ≈ 184 independent models — the same order as a 5-fold cross-validation estimate, produced during the single fit you were going to run anyway. Every prediction comes from a tree that never saw that row, so the estimate is honest about generalization.

Three caveats keep OOB from being a free lunch. First, if you tune aggressively against OOB — sweeping max_features, min_samples_leaf, depths — the OOB number starts to overfit your validation, exactly as a holdout would. Keep a final untouched test set for the number you report. Second, in a heavily imbalanced problem a bootstrap can omit most minority rows entirely, so per-row minority estimates are noisier than the headline accuracy suggests; check the OOB score for your positive class, not just overall accuracy. Third, OOB requires bootstrap=True — turn bootstrap off and the score silently disappears.

Watch OOB error while raising n_estimators: it drops sharply over the first ~100 trees and then flattens. That plateau is a signature of bagging — you are averaging away variance, and once it is gone, more trees do nothing. Contrast this with boosting's U-shaped validation curve, where the number of rounds is a genuine overfitting knob.

A workable OOB-driven recipe, in order: raise n_estimators to ~800 once so the OOB curve is stable, sweep max_features and min_samples_leaf against OOB, then evaluate the winner once on a held-out test set you never touched during the sweep. For regression, oob_score_ reports R² from the same per-row aggregation; for classification it reports accuracy — which is the wrong number on an imbalanced problem, so pull the OOB probabilities and score them yourself:

oob_probs = rf.oob_decision_function_[:, 1]          # P(class=1) for each row
print(average_precision_score(y_train, oob_probs))    # the metric that matters here

Where forests genuinely lose is extrapolation. Every leaf prediction is an average of training targets, so a random forest regressor can never predict outside the range of y it has seen — feed it a linear trend and it follows the curve inside the data, then flattens or jitters beyond it. Combined with flat performance ceilings on some structured tasks, that pushes practitioners toward boosting, where each new tree fits the residuals the ensemble still gets wrong. That sequential correction is the subject of Gradient Boosting Machines.