Random Forest

Decision trees are accurate on training data but unstable — high variance. Leo Breiman's insight (2001): don't fight the variance of one tree; average many diverse trees and let their errors cancel. The result is one of the most reliable algorithms in all of ML — a near-unbeatable default for tabular data with essentially no tuning.

The statistics of averaging

Average \(B\) estimators, each with variance \(\sigma^2\) and pairwise correlation \(\rho\). The ensemble's variance is

The second term vanishes as \(B\) grows — but the first does not. Averaging identical trees achieves nothing (\(\rho = 1\)); the whole game is making trees accurate yet decorrelated. Random forests inject randomness twice:

1. Bagging (bootstrap aggregating)

Each tree trains on a bootstrap sample: \(n\) rows drawn with replacement from the training set. Each sample leaves out about \(1 - (1 - 1/n)^n \approx 1/e \approx 37\%\) of the rows, so every tree sees a different perturbed dataset.

2. Feature subsampling

At every split, only a random subset of features is eligible (typically \(\sqrt{d}\) for classification, \(d/3\) for regression). Without this, all trees would open with the same dominant feature and remain highly correlated; restricting candidates forces different trees to discover different structure — this is the step that turns bagging into a random forest.

Prediction: majority vote (classification) or mean (regression) over all trees.

flowchart TD
    D[Training data] --> B1[bootstrap 1] & B2[bootstrap 2] & B3[bootstrap ...B]
    B1 --> T1[tree 1<br><small>√d features/split</small>]
    B2 --> T2[tree 2]
    B3 --> T3[tree B]
    T1 & T2 & T3 --> V[vote / average]

The single tree carves noise islands with hard 0/1 confidence; the forest's averaged vote yields a smooth, calibrated-looking boundary that ignores individual noise points — variance visibly averaged away.

Out-of-bag evaluation: free validation

The ~37% of rows a tree never saw are its out-of-bag (OOB) samples. Predict each row using only the trees that didn't train on it, and you get an honest generalization estimate without a validation split — conceptually a built-in cross-validation:

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=300,        # more = better, plateaus; never overfits via B
    max_features='sqrt',     # the decorrelation knob
    min_samples_leaf=1,      # tree depth control if needed
    oob_score=True,
    n_jobs=-1,               # trees train in parallel
    random_state=0,
)
rf.fit(X_train, y_train)
rf.oob_score_                # ≈ honest accuracy estimate, no split spent

Key facts about \(B\) (n_estimators): adding trees cannot overfit — it only stabilizes the average (the \((1-\rho)\sigma^2/B\) term shrinks). Performance plateaus; the only cost of more trees is compute. Overfitting, when it happens, comes from the individual trees being too deep on too-noisy data — control with min_samples_leaf or max_depth.

Feature importance

Two standard measures:

• Impurity-based (rf.feature_importances_): total impurity decrease contributed by each feature across all trees. Fast, but biased toward high-cardinality features (more possible thresholds = more chances to look useful) and computed on training data;
• Permutation importance: shuffle one feature's column in validation data and measure the score drop. Slower, model-agnostic, and more trustworthy — the bridge to Explainability.

from sklearn.inspection import permutation_importance
imp = permutation_importance(rf, X_val, y_val, n_repeats=10, random_state=0)

Practical profile

Class materials

Quiz