Overfitting in decision trees: Visual walkthrough

This is the visual companion to the parent topic on overfitting and leans on Decision Trees, the Bias-Variance Tradeoff, and Cross-Validation.

Step 1 — What a tree is, drawn as a picture

WHAT: We draw a small tree and name its parts. WHY: Every symbol later ( $T$ , $t$ , $T_{t}$ , $∣ \tilde{T} ∣$ ) refers to a part of this picture. We earn them here so nothing is mysterious later. PICTURE: Look at the figure. The circle at the top is the root. Squares at the bottom are leaves (final answers). The letter $t$ marks one internal node partway down; everything hanging below $t$ is its own little tree.

So in the picture $∣ \tilde{T}_{t} ∣ = 4$ : the pink subtree ends in four leaf-squares. Hold that number; it drives everything.

Step 2 — What "error" of a tree means

WHAT: We define $R (T)$ , the total training error. WHY: Pruning is a trade between error and size. We can't trade something we haven't measured — so we measure error first. PICTURE: Each leaf-box shows its points as dots. Correct dots are pale-yellow, wrong dots are pink. $R$ counts the pink fraction across the whole tree.

Step 3 — The counterweight: pay a price per leaf

WHAT: We define the penalized cost $R_{α} (T)$ . WHY: This turns "how big should the tree be?" into a clean tug-of-war: error pulls toward big, rent pulls toward small. The winner depends on one dial, $α$ . PICTURE: The figure is a balance scale. Left pan: error $R (T)$ (drops as leaves grow). Right pan: rent $α ∣ \tilde{T} ∣$ (rises as leaves grow). Their sum is a U-shape — the total cost dips then climbs.

Step 4 — The decision: keep the subtree, or collapse it?

WHAT: We write the two costs and compare them. WHY: Pruning globally is hard; pruning one node at a time is easy. If we can decide one node correctly, we can repeat. So we reduce the whole problem to this local comparison. PICTURE: Left panel — keep $T_{t}$ : four leaves, tiny error but four rents. Right panel — prune to leaf $t$ : one leaf, one rent, but more error. The scale tips based on $α$ .

Step 5 — Solving for the tipping point $α$

WHAT: Algebra to isolate $α$ at the tie. WHY: A single number per node summarizes the whole keep-vs-prune trade — it tells us how weak this branch is. Weak branches get cut first. PICTURE: Two straight lines of cost plotted against $α$ . They cross once; the crossing $x$ -value is $α_{eff}$ . Left of the cross the pink (keep) line is lower; right of it the yellow (prune) line is lower.

Start from the tie (equality of the two costs): $R (t) + α = R (T_{t}) + α ∣ \tilde{T}_{t} ∣$

Move all error to one side, all $α$ to the other: $R (t) - R (T_{t}) = α ∣ \tilde{T}_{t} ∣ - α = α (∣ \tilde{T}_{t} ∣ - 1)$

Divide: $α_{eff} (t) = \frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}$

Step 6 — Why the denominator is $∣ \tilde{T}_{t} ∣ - 1$ , not $∣ \tilde{T}_{t} ∣$

WHAT: A careful leaf-count of the pruning operation. WHY: Off-by-one here would misrank branches. The formula must measure the net simplification. PICTURE: Before: the subtree has $∣ \tilde{T}_{t} ∣$ leaf-squares (say 4). After: they vanish and $t$ turns into 1 leaf. Net change = remove 4, add 1 = lose 3 = $∣ \tilde{T}_{t} ∣ - 1$ .

$net leaves removed = old leaves gone ∣ \tilde{T}_{t} ∣ - node t is now a leaf 1 = ∣ \tilde{T}_{t} ∣ - 1$

Step 7 — Repeat: the weakest-link sequence

WHAT: Turn the single-node rule into a full pruning path. WHY: We don't want one tree; we want the whole family from "full" to "just the root," so Cross-Validation can later pick the best member honestly. PICTURE: A ladder. Top rung: full tree at $α = 0$ . Each step up snips the current weakest link and jumps to the next $α$ on the number line, until only the root remains.

Step 8 — Every regime of $α$ , in one line each

$α = 0$ ::: rent is free → keep everything → the full overfit tree (high variance).
$0 < α < min α_{eff}$ ::: still cheaper to keep every branch → full tree survives.
$α = α_{eff} (t)$ ::: node $t$ is exactly on the fence; at-or-above this it prunes.
$α$ large ::: many branches now overpriced → deep pruning → more bias, less variance (the Bias-Variance Tradeoff slider moving right).
$α \to \infty$ ::: even the first split can't pay rent → collapse to the root leaf → pure underfit.

The one-picture summary

Everything on one board: a tree whose weakest branch (smallest $α_{eff}$ ) is highlighted, the tie-point formula annotated over it, and the resulting cost-vs- $α$ U-curve whose minimum names the tree we keep.

Recall Feynman: the whole walkthrough in plain words

We drew a tree and named its bits: the whole thing $T$ , a middle node $t$ , the bush below it $T_{t}$ , and its leaves. We measured how wrong the tree is ( $R$ ) by counting mistakes in the leaf-boxes. Then we noticed the tree always wants to grow, so we charged rent $α$ for each leaf — total cost = error + rent. At any node we asked "keep the bush or snip it to one leaf?" and just compared the two costs. Setting them equal and doing one line of algebra gave the break-even rent $α = \frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}$ — extra mistakes per leaf saved. The minus-one is because snipping a 4-leaf bush leaves 1 leaf behind, so you only really lose 3. We cut the cheapest branch first, repeat, and get a ladder of trees from full to bare. Finally, cross-validation picks the rung that does best on new data. That's cost-complexity pruning: learn the idea, cut away the memorized typos.

Connections

Overfitting in decision trees — the parent this walkthrough expands.
Decision Trees — the object we are pruning.
Bias-Variance Tradeoff — what raising $α$ trades.
Cross-Validation — how the final $α$ is chosen.
Random Forests — the alternative variance cure (average, don't prune).
Gini Impurity and Entropy — how the per-leaf error $r (ℓ)$ can be measured.
Regularization — the same "error + penalty" idea, general form.