Tree pruning techniques: Visual walkthrough — AI-ML deep dive

We answer one question: out of an over-grown tree, which branch do we cut first, and when?

Step 1 — What an over-grown tree even looks like

Two names we will reuse constantly, anchored to that picture:

The tilde ( $~$ ) just means "the leaves of", so $\tilde{T}$ = "the set of leaves of tree $T$ ", and the bars $∣ \dots ∣$ mean "how many are in this set" — the same bars you'd use to count marbles in a bag.

Step 2 — Measuring how wrong the tree is

Step 3 — Two wishes fighting: one knob to referee them

Why this tool — why addition and a multiplier, not something fancier? Because we want a straight-line exchange rate: one extra leaf always costs exactly $α$ more, no matter how many you already have. That linear "one price per leaf" is the simplest fair penalty — the same idea behind regularization, where we add a penalty term to stop a model from getting too complex.

The two extremes (memorize these — they are the whole story):

$α$	rent per leaf	what wins	result
$α = 0$	free	accuracy only	keep the full tree
$α \to \infty$	infinite	simplicity only	collapse to the root

So sliding $α$ from $0$ up to $\infty$ walks us from the giant tree down to a single node — a whole family of trees, one per $α$ .

Step 4 — The real question: cut this branch, or keep it?

Two more names, both read straight off s04:

Step 5 — Writing both options' costs and letting them race

Cost of each option, term by term:

$keep subtree R_{α} (Keep) = its error R (T_{t}) + α its leaves ∣ \tilde{T_{t}} ∣$

$collapse to leaf R_{α} (Cut) = leaf error R (t) + α \cdot one leaf 1$

We should cut when cutting costs no more than keeping:

$Cut R (t) + α \leq Keep R (T_{t}) + α ∣ \tilde{T_{t}} ∣$

Step 6 — Solving for the tipping-point $α$

Move all $α$ -terms to one side, error-terms to the other:

$α - α ∣ \tilde{T_{t}} ∣ \leq R (T_{t}) - R (t)$ $α (1 - ∣ \tilde{T_{t}} ∣) \leq R (T_{t}) - R (t)$

Now divide by $(1 - ∣ \tilde{T_{t}} ∣)$ . Careful: since a real subtree has more than one leaf, $∣ \tilde{T_{t}} ∣ > 1$ , so $(1 - ∣ \tilde{T_{t}} ∣)$ is negative — and dividing an inequality by a negative number flips the $\leq$ into $\geq$ :

$α \geq \frac{R ( T _{t} ) - R ( t )}{1 - ∣ T _{t} ~ ∣}$

Multiply top and bottom by $- 1$ (flips both signs, cancels out — inequality unchanged) to make it read cleanly:

Reading every symbol:

Numerator $R (t) - R (T_{t})$ = the extra error you pay by collapsing (Step 4 said it's $\geq 0$ ). Small numerator ⇒ the subtree was barely helping ⇒ cheap to cut.
Denominator $∣ \tilde{T_{t}} ∣ - 1$ = how many leaves you delete (you go from $∣ \tilde{T_{t}} ∣$ leaves down to $1$ ). Big denominator ⇒ you free lots of "rent" ⇒ better deal.
The whole fraction = extra error per leaf saved — a fair price per unit, so nodes of different sizes can be compared apples-to-apples.

Step 7 — Edge cases you must never trip on

A single-leaf "subtree" ( $∣ \tilde{T_{t}} ∣ = 1$ ): denominator $= 1 - 1 = 0$ → division by zero, undefined. But this is fine: a subtree that is already one leaf has nothing below it to cut. We simply never compute $α_{eff}$ for leaves — only for internal nodes, where $∣ \tilde{T_{t}} ∣ \geq 2$ .
A perfectly pure subtree ( $R (T_{t}) = 0$ ): then $α_{eff} (t) = R (t) / (∣ \tilde{T_{t}} ∣ - 1)$ . Since $R (t) \geq 0$ , this is $\geq 0$ — well-defined. It just means "cutting costs you the collapsed leaf's full error."
A split that helped nothing ( $R (t) = R (T_{t})$ ): numerator $= 0$ → $α_{eff} = 0$ . This node dies at the very first whiff of penalty ( $α = 0^{+}$ ). Correct — a split with zero accuracy gain but extra leaves is pure waste.

Step 8 — Sweeping $α$ builds a nested family of trees

The loop:

Grow the full tree $T_{0}$ .
Compute $α_{eff}$ at every internal node.
Prune the smallest- $α_{eff}$ node → tree $T_{1}$ ; record that $α$ as $α_{1}$ .
Recompute and repeat → $T_{2}, T_{3}, \dots$ until only the root is left.
Result: a nested chain $T_{0} \supset T_{1} \supset \dots \supset {root}$ with increasing $α_{1} < α_{2} < \dots$ ( $\supset$ means "contains" — each tree is a pruned-back version of the one before).

Which tree in the chain is best? Not the training-error winner (that's always $T_{0}$ — see the mistake below). We pick with cross-validation: try each $α$ , measure error on held-out folds, keep the $α$ with the lowest CV error. The CV curve is U-shaped — too little pruning overfits (high variance), too much underfits (high bias).

Worked check — the numbers behind the pictures

The one-picture summary

Figure s09 compresses the whole story: the $α$ -axis at the bottom; above it the shrinking trees ( $T_{0} \to$ root) appearing as $α$ climbs past each recorded $α_{eff}$ ; and overlaid, the U-shaped CV-error curve whose minimum marks the $α$ we finally choose.

Recall Feynman retelling — the walkthrough in plain words

You grew a huge tree that memorized everything, even the flukes. Every leaf is a room, and every room charges rent $α$ . Your total cost is mistakes you make plus rent on all your rooms. When rent is free ( $α = 0$ ) you keep every room; when rent is sky-high you knock the whole house down to one room. To decide which branch to knock down first, you look at each branch and ask: "if I collapse this bushy branch into one room, how much extra wrongness do I take on, and how many rooms of rent do I stop paying?" Extra-wrongness ÷ rooms-saved is the branch's price per room — its $α_{eff}$ . The branch with the cheapest price is the weakest link; you cut it first. Cut, recompute, cut again — the prices you pay only go up — until just the root remains. That gives you a whole ladder of trees, tiny to huge. You don't trust your own homework (training error) to pick one, because homework always says "keep everything." You test each tree on hidden animals (cross-validation). Too big overfits, too small underfits — so the error curve dips in the middle. You pick the dip. Done.

Connections

Parent: Tree Pruning Techniques
Decision Trees (CART) · Gini Impurity & Entropy · Bias-Variance Tradeoff · Cross-Validation · Regularization · Random Forests