Tree pruning techniques: Worked examples — AI-ML deep dive

Before we start, one symbol reminder so nobody is lost from line one:

The scenario matrix

Every question this topic can ask falls into one of these cells. The examples below are tagged with the cell they cover.

#	Case class	What's special	Covered by
C1	Compute $α_{eff}$ for one node	the basic "price per leaf"	Ex 1
C2	Degenerate: subtree has 2 leaves ( $∣ \tilde{T}_{t} ∣ - 1 = 1$ )	denominator $= 1$ , no dividing subtlety	Ex 2
C3	Choose the weakest link among several nodes	smallest $α_{eff}$ wins	Ex 3
C4	$α$ flips the keep/prune decision	compare $R_{α}$ at two $α$ values	Ex 4
C5	Limiting values $α = 0$ and $α \to \infty$	full tree vs root	Ex 5
C6	Build the full $α$ -sequence $T_{0} \supset T_{1} \supset \dots$	weakest-link pruning end-to-end	Ex 6
C7	Reduced-Error Pruning decisions	tie / worse / better on validation	Ex 7
C8	Real-world word problem (medical cost trade)	translate words → $R, α$	Ex 8
C9	Zero/degenerate: perfectly pure tree ( $R (T) = 0$ )	numerator behaviour, still prune?	Ex 9
C10	Exam twist: pick $α$ from a CV curve	U-shape, minimum not extreme	Ex 10

We'll fill them in order.

Warm-up figure: what "cost vs size" looks like

Look at the picture. The blue curve is $R (T)$ (training error): it only ever goes down as you add leaves — a tree with more boxes fits the training data better, always. The orange line is the tax $α ∣ \tilde{T} ∣$ : a straight ramp, steeper for bigger $α$ . The green curve is their sum $R_{α} (T)$ — the bill we actually minimise. Its lowest point is the tree we want. Change $α$ (tilt the orange ramp) and the green valley slides left (smaller tree) or right (bigger tree). Keep this image in mind for every example.

Worked examples

Worked example Ex 1 — Compute

$α_{eff}$ (cell C1) Node $t$ roots a subtree $T_{t}$ with 4 leaves. The subtree's total error is $R (T_{t}) = 0.03$ . Collapsed to a single leaf it would err at $R (t) = 0.12$ . Find $α_{eff} (t)$ .

Forecast: guess — is the answer above or below $0.03$ ? (The gap $0.12 - 0.03 = 0.09$ gets spread over how many leaves?)

Numerator $= R (t) - R (T_{t}) = 0.12 - 0.03 = 0.09$ . Why this step? This is the extra error you'd pay by collapsing — the subtree was more accurate, so the number is positive.
Denominator $= ∣ \tilde{T}_{t} ∣ - 1 = 4 - 1 = 3$ . Why this step? Collapsing 4 leaves into 1 removes 3 leaves; we're pricing "error per leaf removed."
$α_{eff} (t) = \frac{0.09}{3} = 0.03$ . Why this step? Fair per-unit price: below $α = 0.03$ keep the subtree, at/above it collapse.

Verify: plug $α = 0.03$ into both options. Keep: $R (T_{t}) + α \cdot 4 = 0.03 + 0.12 = 0.15$ . Prune: $R (t) + α \cdot 1 = 0.12 + 0.03 = 0.15$ . They tie exactly at $α_{eff}$ — as they must. ✓

Worked example Ex 3 — Pick the weakest link (cell C3)

A tree has three internal nodes with these numbers:

node	$R (t)$	$R (T_{t})$	$∣ \tilde{T}_{t} ∣$
A	0.20	0.10	5
B	0.09	0.05	2
C	0.15	0.06	4

Which node gets pruned first?

Forecast: the "weakest link" is the one with the smallest $α_{eff}$ — cheapest to collapse. Guess A, B, or C.

$α_{A} = \frac{0.20 - 0.10}{5 - 1} = \frac{0.10}{4} = 0.025$ .
$α_{B} = \frac{0.09 - 0.05}{2 - 1} = \frac{0.04}{1} = 0.04$ .
$α_{C} = \frac{0.15 - 0.06}{4 - 1} = \frac{0.09}{3} = 0.03$ . Why these steps? Each is the threshold $α$ at which that node becomes worth collapsing. As we raise $α$ from $0$ , the first to cross its threshold is the smallest.
Smallest is $α_{A} = 0.025$ → prune node A first. Why this step? It buys the least accuracy per leaf, so it's the fluffiest branch.

Verify: order of thresholds $0.025 < 0.03 < 0.04$ ⇒ A, then C, then B — a valid increasing sequence, exactly what weakest-link pruning produces. ✓

Worked example Ex 4 —

$α$ flips the decision (cell C4) Full tree: $R (T) = 0.05, ∣ \tilde{T} ∣ = 12$ . Candidate pruned tree: $R (T^{'}) = 0.09, ∣ \tilde{T}^{'} ∣ = 5$ . Decide keep vs prune at (a) $α = 0.005$ and (b) $α = 0.01$ .

Forecast: more tax favours the smaller tree $T^{'}$ . Guess which $α$ keeps the big tree.

At $α = 0.005$ : $R_{α} (T) = 0.05 + 0.005 \cdot 12 = 0.11$ ; $R_{α} (T^{'}) = 0.09 + 0.005 \cdot 5 = 0.115$ . Why this step? Compute the actual bill for each. Lower bill wins.
$0.11 < 0.115$ ⇒ keep the full tree at $α = 0.005$ .
At $α = 0.01$ : $R_{α} (T) = 0.05 + 0.12 = 0.17$ ; $R_{α} (T^{'}) = 0.09 + 0.05 = 0.14$ .
$0.14 < 0.17$ ⇒ prune to $T^{'}$ at $α = 0.01$ . Why this step? The extra tax now outweighs the 4% extra error, tipping the balance.

Verify: the break-even $α$ is $\frac{R ( T ^{'} ) - R ( T )}{∣ T ~ ∣ - ∣ T ~ ^{'} ∣} = \frac{0.09 - 0.05}{12 - 5} = \frac{0.04}{7} \approx 0.00571$ . Our $0.005 < 0.00571$ (keep) and $0.01 > 0.00571$ (prune) — consistent. ✓ Same trade, opposite decision: $α$ literally flips it.

Worked example Ex 5 — Limiting values

$α = 0$ and $α \to \infty$ (cell C5) Same trees as Ex 4. What happens at the two extremes?

Forecast: the parent note said " $α = 0$ keeps the giant, $α = \infty$ leaves the root." Confirm numerically.

$α = 0$ : $R_{α} (T) = 0.05$ , $R_{α} (T^{'}) = 0.09$ . Bill = pure error. $0.05 < 0.09$ ⇒ keep full tree. Why this step? With zero tax, size is free, so accuracy alone decides — and more leaves are always at least as accurate on training.
$α = 10$ (stand-in for "huge"): $R_{α} (T) = 0.05 + 120 = 120.05$ ; a single-root tree ( $∣ \tilde{T} ∣ = 1$ ) with worst-case error $R \leq 1$ costs $\leq 1 + 10 = 11$ . Root wins by miles. Why this step? When tax dwarfs error, only leaf-count matters; the minimum leaf-count is 1 (the root).

Verify: as $α \to \infty$ , $R_{α} (T) = R (T) + α ∣ \tilde{T} ∣$ grows linearly with slope $∣ \tilde{T} ∣$ ; the smallest slope belongs to the root ( $∣ \tilde{T} ∣ = 1$ ), so it eventually beats every larger tree. ✓

Worked example Ex 6 — Build the whole

$α$ -sequence (cell C6) Grow a tree $T_{0}$ with internal nodes P, Q, R having:

node	$R (t)$	$R (T_{t})$	leaves
P (root)	0.40	0.05	6
Q	0.18	0.10	3
R	0.11	0.08	2

Produce the nested sequence and the $α$ where each cut happens. (Assume, for simplicity, that pruning R doesn't change Q's or P's numbers — a self-contained toy.)

Forecast: weakest link goes first. Rank the three $α_{eff}$ , cut smallest, repeat, root last.

$α_{R} = \frac{0.11 - 0.08}{2 - 1} = 0.03$ ; $α_{Q} = \frac{0.18 - 0.10}{3 - 1} = \frac{0.08}{2} = 0.04$ ; $α_{P} = \frac{0.40 - 0.05}{6 - 1} = \frac{0.35}{5} = 0.07$ . Why this step? These are each node's collapse threshold.
$T_{0} \to T_{1}$ : cut R at $α_{1} = 0.03$ (smallest).
$T_{1} \to T_{2}$ : next smallest is Q at $α_{2} = 0.04$ .
$T_{2} \to {root}$ : cut P at $α_{3} = 0.07$ . Why these steps? Each stage removes the current weakest link; thresholds come out increasing $0.03 < 0.04 < 0.07$ , which is exactly the guarantee $α_{1} < α_{2} < α_{3}$ .

Verify: the sequence $T_{0} \supset T_{1} \supset T_{2} \supset {root}$ with $0.03 < 0.04 < 0.07$ is strictly increasing ⇒ a valid cost-complexity path. CV then picks one of these four trees. ✓

Worked example Ex 7 — Reduced-Error Pruning: tie / worse / better (cell C7)

Three subtrees are tested bottom-up on a held-out validation set. Their subtree accuracy vs collapsed-leaf accuracy:

subtree	keep-acc	leaf-acc	decision?
S1	0.88	0.88	?
S2	0.90	0.85	?
S3	0.82	0.86	?

Forecast: REP rule = prune if accuracy does not decrease. Fill the column.

S1: leaf-acc $=$ keep-acc ⇒ no decrease ⇒ prune (Occam: simpler at same accuracy).
S2: leaf-acc $0.85 <$ keep-acc $0.90$ ⇒ accuracy drops ⇒ keep the subtree.
S3: leaf-acc $0.86 >$ keep-acc $0.82$ ⇒ pruning improves validation ⇒ prune (the subtree was overfitting noise). Why these steps? Validation data isn't memorised, so any branch that only helped training shows up as "no help or harmful" here — safe to cut.

Verify: count net leaves removed if all decisions applied: prune S1, keep S2, prune S3 ⇒ 2 of 3 collapsed. Validation accuracy after ≥ before at every step (that's the REP invariant). ✓

Worked example Ex 8 — Real-world word problem (cell C8)

A hospital's triage tree has 20 leaves and misclassifies 6% of patients ( $R = 0.06$ ). A simpler 8-leaf version misclassifies 8% ( $R = 0.08$ ). The board says: "each extra leaf costs $1000/year to maintain and audit, and each 1% of misclassification costs $4000/year." Should they prune to 8 leaves?

Forecast: translate the money into an $α$ -style bill, then compare totals.

Big tree yearly cost: leaves $20\times\$ 1000 = $20{,}000 $; er r or$ 6\times$4000 = $24{,}000 $; t o t a l$ $44{,}000 $. * W h y t hi ss t e p ? * "$ R(T) $pl u s$ \alpha|\tilde T|$" is literally this: error-cost plus size-cost.
Small tree: leaves $8\times\$ 1000=$8000 $; er r or$ 8\times$4000=$32{,}000 $; t o t a l$ $40{,}000$.
$\$ 40{,}000<$44{,}000 $\Rightarrow * * p r u n e t o 8 l e a v es * * — c h e a p er o v er a l l . * W h y t hi ss t e p ? * W e a cce pt e d$ 2% $m or eer r or ($ $8000 $) t os h e d 12 l e a v es ($ $12{,}000 $s a v e d) . N e t s a v e$ $4000$.

Verify: implied $α$ = leaf-cost / error-cost-per-unit- $R$ . $1000 per leaf, and $1%$ error $= 0.01$ in $R$ costing $4000, so $\alpha = \$ 1000 / ($4000/0.01) = 1000/400000 = 0.0025 $. B r e ak - e v e n f r o m E x - 4 s t y l e :$ \frac{0.08-0.06}{20-8}=\frac{0.02}{12}\approx0.00167 < 0.0025$ ⇒ prune. Same verdict. ✓

Worked example Ex 9 — Degenerate: a perfectly pure tree (cell C9)

The full tree is pure: every leaf is perfectly classified on training, so $R (T) = 0$ with $∣ \tilde{T} ∣ = 15$ . A node $t$ 's subtree $T_{t}$ has $R (T_{t}) = 0$ (pure) and 3 leaves, but collapsing it to a leaf would give $R (t) = 0.05$ . Compute $α_{eff}$ and interpret.

Forecast: with $R (T_{t}) = 0$ the numerator is just $R (t)$ . Is the node ever worth cutting?

$α_{eff} = \frac{0.05 - 0}{3 - 1} = \frac{0.05}{2} = 0.025$ . Why this step? Even a pure subtree has a finite collapse price — you'd add $0.05$ training error to remove 2 leaves.
Interpretation: for any $α < 0.025$ this node stays; the pure full tree (training error 0) is only dismantled once tax is high enough. Why this step? Zero training error is a red flag for overfitting, not a goal. Cross-validation, not training error, tells us whether cutting helps generalisation.

Verify: at $α = 0.025$ , keep-cost $= 0 + 0.025 \cdot 3 = 0.075$ ; prune-cost $= 0.05 + 0.025 \cdot 1 = 0.075$ . Tie. ✓ The formula behaves fine at $R = 0$ ; nothing degenerate breaks.

Worked example Ex 10 — Exam twist: read

$α$ off the CV curve (cell C10) Cross-validation gives these mean validation errors for the pruned-tree sequence:

tree	$α$	CV error
$T_{0}$	0.000	0.140
$T_{1}$	0.010	0.118
$T_{2}$	0.030	0.110
$T_{3}$	0.060	0.125
root	0.200	0.300

Which tree do we deploy?

Forecast: the CV curve is U-shaped in $α$ . Neither extreme wins — pick the minimum.

Scan the CV column: $0.140, 0.118, 0.110, 0.125, 0.300$ . Why this step? Training error would keep dropping toward $T_{0}$ (misleading); CV error is the honest estimate of test error.
Minimum is $0.110$ at $α = 0.030$ ⇒ deploy $T_{2}$ . Why this step? Left of it we overfit (variance too high); right of it we over-prune (bias too high). The valley balances the Bias-Variance Tradeoff.

Verify: the sequence is U-shaped: it falls $0.140 \to 0.118 \to 0.110$ then rises $0.110 \to 0.125 \to 0.300$ . A single interior minimum at index 2 confirms $T_{2}$ . Choosing $T_{0}$ (over-fit) or the root (over-prune) both give higher CV error. ✓

The figure above is exactly Ex 10: green dots are CV error, dipping into a valley at $α = 0.03$ , while the blue dashed line (training error) slides ever downward and would fool you into keeping the biggest tree.

Quick recall

Recall Which node is pruned first, and why?

The internal node with the smallest $α_{eff}$ — it buys the least accuracy per leaf, so it's the cheapest (weakest) link. ::: smallest $α_{eff}$ $α_{eff}$ formula? ::: $\frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}$ At $α_{eff}$ exactly, keep-cost vs prune-cost? ::: they tie Which data selects the final $α$ ? ::: Cross-Validation (never training error) Shape of the CV-error-vs- $α$ curve? ::: U-shaped — pick the minimum

Connections

Tree pruning techniques (parent)
Decision Trees (CART) — where the full tree $T_{0}$ comes from
Bias-Variance Tradeoff — why the CV curve is U-shaped
Cross-Validation — how we choose $α$
Gini Impurity & Entropy — the impurity behind $R (t)$
Random Forests — an alternative to pruning (average many trees)
Regularization — $α ∣ \tilde{T} ∣$ is a complexity penalty, same spirit
2.3.04 Tree pruning techniques (Hinglish)