Module 9 · Trees & ensembles
Decision trees — prediction by twenty questions
A tree predicts by playing twenty questions with the features: is x ≤ 1.3? then is x ≤ −0.4? … until it lands in a leaf, then answers with a constant — the average outcome of the training points in that leaf. The fitted function is a staircase: flat within each region, jumping at the boundaries.
Growing the tree (CART-style) is greedy: consider every possible split of every feature, take the one that most reduces squared error (or, for classification, node impurity — Gini or entropy) right now, and recurse on each half. Greedy means fast, and occasionally short-sighted: a split that looks mediocre now might unlock great splits later, and the algorithm will never know. In practice you grow deliberately too deep, then prune back using cost-complexity — penalizing leaves the way λ penalized coefficients in Module 3 — with the pruning level chosen by cross-validation.
Why does everyone love trees anyway? They handle mixed feature types, ignore monotone transformations, deal with missing values gracefully, capture interactions automatically, and the fitted rule can be read aloud. Their sins: staircases approximate smooth trends badly, and single trees are unstable — jiggle the data and a different first split can cascade into a completely different tree.
🎛 Regression tree lab
Leaves (regions)
4
each answers with its mean
Train MSE
0.217
Test MSE
0.244
Red dashed verticals are the split points the tree chose greedily — each one is the cut that most reduced squared error at that moment. Depth 0 is a single mean; each extra level doubles the potential regions. Notice the failure mode: the prediction is piecewise-constant, so a smooth slope gets approximated by a staircase, and at high depth with tiny leaves each step chases one noisy point. Trees buy interpretability and interactions cheaply, but pay in smoothness and variance — which is exactly what ensembles will fix. Educational tool.
Cousins in the additive family
The same chapter of ideas contains gentler relatives. Generalized additive models (GAMs) keep a formula structure — f(x) = f₁(x₁) + f₂(x₂) + … — but let each fⱼ be a smooth spline: interpretable per-feature curves, no interactions unless you add them. MARSbuilds a formula out of hinge functions max(0, x−t), adding them greedily like tree splits but producing a continuous, piecewise-linear surface. Both trade away some of the tree's freedom for smoothness — the recurring bargain of this curriculum.
Things to try
- • Step depth 0 → 1 → 2 and watch where the first splits land: always attacking the biggest remaining error. Greedy in action.
- • Set depth 7 with min-leaf 1: a private step for every noisy point, test MSE up. Now raise min-leaf to 10 — a cheap, effective brake.
- • Find the smooth rising stretch of the green curve and note the staircase awkwardly straddling it — a linear model handles that stretch with one coefficient; the tree needs many splits.