Decision trees and random forests

Everything so far drew smooth boundaries from global models. Trees are the opposite end of the design space: local, hierarchical, axis-aligned, zero smoothness — and the raw material of the two ensemble methods (forests here, boosting next lesson) that dominate tabular machine learning. The intellectual arc of this lesson is a bias–variance story with a twist: a single tree’s problem is variance, and the fix is not shrinkage but averaging.

CART: recursive greedy partitioning

A binary decision tree splits the input space with questions of the form $x_j \le t$, recursively, until leaves are pure enough; a leaf predicts its majority class (or class frequencies). Growing the optimal tree is NP-hard, so CART is greedy: at each node, try every feature $j$ and every threshold $t$ (only midpoints between sorted data values matter — finitely many), and keep the split minimizing the children’s weighted impurity. For class proportions $p_k$:

Both are maximal at 50/50 and zero when pure; they disagree rarely enough that the choice is a footnote. The split criterion for parent $P$ with children $L, R$:

(Why not split directly on accuracy? Misclassification rate is piecewise-linear in $p$ — whole families of genuinely-progressing splits leave it unchanged, so the greedy search stalls. Gini/entropy are strictly concave, rewarding any purification. That detail is the difference between a criterion that works and one that plateaus.)

What this buys and costs, structurally:

• Axis-aligned boxes. The boundary is a union of rectangles — staircases along diagonals (visible in the widget), but naturally expressive for rule-like, interaction-heavy tabular structure (the XOR that defeated every linear model is two splits for a tree).
• Invariance to monotone feature transforms. Only the order of values matters: no standardization, logs, or scaling ever needed — a real reason trees are the low-friction tabular default.
• Native handling of mixed types and (in serious implementations) missing values via surrogate splits.
• Interpretability while small — a depth-3 tree is a readable flowchart; a depth-10 tree is not, and the forest that fixes the tree destroys the flowchart entirely. Interpretability was a property of the weak model.

The variance problem

An unpruned tree drives training error toward zero — with $n$ leaves available it can isolate every point. The bias–variance ledger reads: low bias, enormous variance. The hierarchy is the multiplier: change a handful of samples and the root split can flip, and every decision below inherits the change — the whole partition reorganizes. In the widget, refitting on a bootstrap resample redraws visibly different boxes at depth 8; that instability is the variance term from the regularization lesson, made visual. Classical pruning (grow, then cut back by cost-complexity $\alpha \cdot \#\text{leaves}$ — capacity control in the ridge spirit) trades some variance back for bias. The modern answer is better.

Bagging, and the correlation ceiling

Bootstrap aggregating (Breiman, 1996): draw $B$ bootstrap resamples, grow a deep tree on each, average their predictions (vote, or average probabilities). The arithmetic of averaging is the whole theory. For $B$ estimators of variance $\sigma^2$ with pairwise correlation $\rho$:

The second term dies as $B$ grows (more trees never hurt — no overfitting in $B$, only diminishing returns), but the first does not: correlation between the trees is the floor. Bagged trees are correlated for an obvious reason — every resample still contains the same dominant features, so every tree opens with similar root splits and the “committee” is really one opinion echoed $B$ times.

Random forests attack $\rho$ directly: at every split, only a random subset of $m$ features (typically $\sqrt{d}$) is even considered. Strong features are periodically benched, forcing trees to discover different structure; individual trees get slightly worse ($\sigma^2$ up a little), but decorrelation ($\rho$ down a lot) wins the product. That is the entire trick — one line of code, aimed squarely at the first term of a variance formula. Two free by-products: out-of-bag evaluation (each tree never saw ~36.8% of the data — recall $(1 - 1/n)^n \to e^{-1}$ — so honest validation comes without a held-out set) and permutation feature importance (shuffle a feature, watch OOB error move).

Practical grammar of forests

Honest failure modes, because defaults breed complacency: forests cannot extrapolate (predictions are averages of training targets — beyond the data’s range they go flat, a real trap on trending time series); axis-alignment makes rotated boundaries expensive; very high-cardinality categoricals and impurity-based importances mislead (prefer permutation importance); and the smooth-probability look does not mean calibrated — forests are typically under-confident at the extremes (lesson 3’s isotonic fix applies).

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=400, max_features="sqrt", oob_score=True, n_jobs=-1
).fit(X_tr, y_tr)
print(rf.oob_score_)          # honest accuracy, no validation split spent

Exercises