Cost-Complexity Pruning

Grow a decision tree without stopping and it keeps splitting until every leaf holds one or two observations — a perfect training fit and a badly overfit model. You could stop early with a fixed rule, but that requires guessing a threshold in advance and applies it uniformly, even to branches that would have benefited from growing further. Cost-complexity pruning grows the tree all the way out, then trims it back afterward, guided by an explicit penalty on size.

The analogy: growing a hedge, then trimming it back

Rather than guessing in advance how tall each part of a hedge should be, let it grow out fully and unevenly. Then trim it back using one rule: cut any branch whose extra height isn't earning its keep relative to how much taller it makes the hedge overall. Different parts get cut back by different amounts, proportional to what they actually contribute.

The mechanics: penalizing tree size directly

Define a cost over tree $T$ with $|T|$ leaves:

$$C_\alpha(T) = \sum_{\text{leaves } m} \sum_{i \in m} (y_i - \hat y_m)^2 \;+\; \alpha |T| .$$

In plain English: the first term is training error; the second charges $\alpha$ per leaf, so a bigger tree pays a bigger tax regardless of fit. At $\alpha=0$ the fully-grown tree wins outright; as $\alpha$ rises, small fit gains from extra leaves stop being worth their cost, and the optimal subtree shrinks. Pruning computes, as $\alpha$ increases from 0, the nested sequence of optimal subtrees, then picks the $\alpha$ (and subtree) that does best on held-out data.

Worked example: pruning a small tree

A fully-grown tree for predicting default has 6 leaves, training error 4. Collapsing two sibling leaves into one gives 5 leaves, error 6. At $\alpha=0$: 6-leaf tree wins (leaves free). At $\alpha=1$: 6-leaf costs $4+6=10$, pruned costs $6+5=11$ — full tree still wins. At $\alpha=3$: 6-leaf costs $4+18=22$, pruned costs $6+15=21$ — now pruning wins, since the extra leaf's marginal gain no longer justifies its cost. Sweeping $\alpha$ this way and cross-validating picks the value that generalizes best.

Drag model complexity above and watch training error keep falling while test error eventually turns back up — exactly the trade-off $\alpha$ controls: a large tree (low $\alpha$) chases training error down but overfits, while enough pruning (higher $\alpha$) finds the complexity that minimizes error on new data.

What this means in practice

Cost-complexity pruning turns "grow a tree" into a properly regularized procedure: grow fully (cheap), then use held-out data to pick how far to trim, rather than guessing stopping rules while growing. It's why "depth" and "leaf count" are treated as tunable regularization knobs in every tree-based method, not arbitrary settings.