Overfitting in decision trees: Worked examples

This is the drill-ground child of Overfitting in decision trees. The parent gave you the ideas: cost-complexity pruning, the effective- $α$ formula, the U-shaped validation curve. Here we hit every case class those ideas can throw at you, one worked example per cell, so no exam question can surprise you.

Everything below reuses a few objects from the parent. To keep the contract — never a symbol before its meaning — here they are in plain words:

Definition The symbols we lean on

$R (T)$ ::: the training error of a whole tree $T$ . Read it as "what fraction of training points does this tree get wrong (or its total impurity)." Bigger = worse fit.
$R (t)$ ::: the training error of a single leaf node $t$ — i.e. what error you'd get if you stopped at node $t$ and made it one leaf that predicts the majority class of the points that fall into it. It is the same kind of quantity as $R (T)$ , just measured for the tiny "tree" that is one leaf. Because a leaf can only vote one class, $R (t) \geq R (T_{t})$ always.
$∣ \tilde{T} ∣$ ::: the number of leaves (final boxes) in tree $T$ . The little tilde and $∣ \cdot ∣$ together just mean "count the leaves." More leaves = more complex = more chances to memorize noise.
$α$ (alpha) ::: the price we charge per leaf. A knob $\geq 0$ . When $α = 0$ leaves are free, so we keep the giant tree. As $α$ grows, leaves get expensive and the tree shrinks.

Formula The one formula this whole page revolves around

For a node $t$ that currently holds a subtree $T_{t}$ beneath it, the effective $α$ — the exact price of a leaf at which "keep the subtree" and "collapse it to one leaf" cost the same — is $α_{eff} (t) = \frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}$

Numerator $R (t) - R (T_{t})$ ::: how much extra training error you accept by collapsing the subtree $T_{t}$ (error $R (T_{t})$ ) into the single leaf $t$ (error $R (t)$ ). Always $\geq 0$ (a subtree fits training data at least as well as one leaf).
Denominator $∣ \tilde{T}_{t} ∣ - 1$ ::: how many leaves you delete by collapsing (you remove $∣ \tilde{T}_{t} ∣$ , add $1$ back).
So $α_{eff}$ = error you pay per leaf you save. Prune the node with the smallest such price first — that is the "weakest link." It is exactly the $α$ at which $R_{α} (keep) = R_{α} (cut)$ .

The scenario matrix

Every question this topic can ask falls into one of these cells. Each row is answered by at least one worked example below.

#	Case class	What makes it special	Example
A	Reading a train/val curve	pick the depth at the U-curve bottom	Ex 1
B	Degenerate: negligible gap	train ≈ val, tree is not overfitting	Ex 2
C	Plain effective- $α$	subtree with several leaves	Ex 3
D	Limiting input: 2-leaf stump	denominator $= 1$	Ex 4
E	Zero input: perfect subtree	$R (T_{t}) = 0$ makes $α$ pure gain	Ex 5
F	Weakest-link ordering	two nodes, which prunes first	Ex 6
G	$α$ sweep → tree size	monotone shrink as $α ↑$	Ex 7
H	Pre- vs post-pruning trap (XOR)	myopic gain $= 0$	Ex 8
I	Real-world word problem	translate business cost into a knob	Ex 9
J	Exam twist: forest vs single tree	variance $\sim 1/ n$ arithmetic	Ex 10

We will also cover the degenerate limits explicitly: $α = 0$ , $α \to \infty$ , a subtree with zero training error, and a single split (stump) where the formula's denominator is smallest.

Worked examples

Worked example Example 1 — Reading the U-curve (cell A)

A tree records: depth 3 → train $85%$ , val $83%$ ; depth 6 → train $94%$ , val $90%$ ; depth 10 → train $99.5%$ , val $86%$ ; depth 15 → train $100%$ , val $81%$ . Which depth should you deploy?

Forecast: guess the depth before reading on — is it 6 or 10?

Convert each to a train–val gap. Gaps: depth 3 → $2$ pts, depth 6 → $4$ pts, depth 10 → $13.5$ pts ( $99.5 - 86$ ), depth 15 → $19$ pts. Why this step? The gap is the fingerprint of memorization: train soaring while val lags means the tree learned noise the val set doesn't share.
Find where validation peaks. Val values: $83, 90, 86, 81$ . The maximum is $90%$ at depth 6. Why this step? We deploy on unseen data, so validation accuracy — not training accuracy — is the thing we optimize. Depth 6 sits at the bottom of the error U-curve (top of the accuracy hump). Figure s01 plots both curves: a cyan training curve climbing steadily to $100%$ and a white validation curve that rises to a hump at depth 6 then falls — the amber dot marks that depth-6 sweet spot, with the depth-15 point labelled "perfect train, worst val = overfit."
Reject depth 15. It has a perfect $100%$ train score, the textbook overfit tell, yet the worst val score. Why this step? Perfect training accuracy is a warning, not a trophy.

Verify: best val $= 90% > 86% > 83% > 81%$ ✓, and its gap ( $4$ pts) is far smaller than depth 15's ( $19$ pts). Answer depth 6 is consistent on both criteria.

Worked example Example 2 — Degenerate: negligible gap, no overfitting (cell B)

A shallow tree gets train $88%$ , val $87%$ . Someone insists "prune it more, it must be overfitting." Are they right?

Forecast: overfit or not?

Compute the gap: $88% - 87% = 1$ pt. Why this step? Overfitting requires a widening train-beats-val gap. A $1$ -pt gap is noise-level — effectively the degenerate "no gap" case, where train and validation agree.
Check the direction of both scores. Both are moderate ( $\sim 87$ – $88%$ ); train is not near $100%$ . Why this step? If anything, low-ish train accuracy hints at underfitting (high bias), the opposite problem — see Bias-Variance Tradeoff.
Conclusion: not overfitting. Pruning further would raise bias and likely lower val accuracy. Why this step? You only pay the pruning cost when there is variance to remove.

Verify: gap $= 1 \leq$ any sensible threshold (say $5$ pts) ✓. Recommendation: consider growing deeper or gathering features, not pruning.

Worked example Example 3 — Plain effective-

$α$ (cell C) Subtree $T_{t}$ has $∣ \tilde{T}_{t} ∣ = 5$ leaves and training error $R (T_{t}) = 0.03$ . Collapse it to one leaf and error rises to $R (t) = 0.11$ . Find the effective $α$ .

Forecast: bigger or smaller than $0.02$ ?

Numerator = error you accept by collapsing: $R (t) - R (T_{t}) = 0.11 - 0.03 = 0.08$ . Why this step? This is how much fit you lose by cutting — the pruning "damage."
Denominator = leaves you delete: $∣ \tilde{T}_{t} ∣ - 1 = 5 - 1 = 4$ . Why this step? Collapsing removes $5$ leaves and adds $1$ back → net $4$ gone.
Divide: $α_{eff} = \frac{0.08}{4} = 0.02$ . Why this step? Damage per leaf saved — the price at which keeping vs cutting tie.

Verify: for $α = 0.02$ , keep-cost $R_{α} (T_{t}) = 0.03 + 0.02 \cdot 5 = 0.13$ ; cut-cost $R_{α} (t) = 0.11 + 0.02 \cdot 1 = 0.13$ . Tied ✓ — exactly what "effective $α$ " means.

Worked example Example 4 — Limiting input: the 2-leaf stump (cell D)

A single split (a stump) has $∣ \tilde{T}_{t} ∣ = 2$ leaves, $R (T_{t}) = 0.10$ , and collapsing to one leaf gives $R (t) = 0.18$ . Find $α_{eff}$ .

Forecast: the denominator is as small as it can ever be — what does that do to $α$ ?

Numerator: $0.18 - 0.10 = 0.08$ . Why this step? The error jump from cutting a single split — the whole "damage" in one number.
Denominator: $∣ \tilde{T}_{t} ∣ - 1 = 2 - 1 = 1$ — the smallest legal value. Why this step? You can't prune a subtree with fewer than $2$ leaves, so $∣ \tilde{T}_{t} ∣ - 1 \geq 1$ always; the formula never divides by zero.
Divide: $α_{eff} = 0.08/1 = 0.08$ . Why this step? With denominator $1$ , the effective $α$ is simply the whole error jump — a single split is "all or nothing."

Verify: keep-cost $R_{α} (T_{t}) = 0.10 + 0.08 \cdot 2 = 0.26$ ; cut-cost $R_{α} (t) = 0.18 + 0.08 \cdot 1 = 0.26$ ✓. Tied.

Worked example Example 6 — Weakest-link ordering (cell F)

Two candidate nodes to prune:

Node $t_{1}$ : $R (t_{1}) = 0.14$ , $R (T_{t_{1}}) = 0.06$ , $∣ \tilde{T}_{t_{1}} ∣ = 5$ .
Node $t_{2}$ : $R (t_{2}) = 0.10$ , $R (T_{t_{2}}) = 0.04$ , $∣ \tilde{T}_{t_{2}} ∣ = 3$ . Which is the weakest link (pruned first)?

Forecast: which node loses the least accuracy per leaf saved?

$α$ for $t_{1}$ : $\frac{0.14 - 0.06}{5 - 1} = \frac{0.08}{4} = 0.02$ . Why this step? We apply the effective- $α$ formula to $t_{1}$ : its numerator $0.08$ is the accuracy lost by collapsing, its denominator $4$ is the leaves saved, so $0.02$ is $t_{1}$ 's price per leaf saved — the cheapness of its branch.
$α$ for $t_{2}$ : $\frac{0.10 - 0.04}{3 - 1} = \frac{0.06}{2} = 0.03$ . Why this step? Cost-complexity pruning always removes the node with the smallest effective $α$ first — so we compute $t_{2}$ 's price the same way to compare it against $t_{1}$ 's.
Compare: $0.02 < 0.03$ , so $t_{1}$ is the weakest link and gets pruned first. Why this step? $t_{1}$ 's leaves are "cheaper to lose." Figure s02 draws a horizontal $α$ number-line from $0$ to $0.05$ : node $t_{1}$ sits at $0.02$ as an amber dot labelled "PRUNE FIRST (weakest link)," while node $t_{2}$ sits further right at $0.03$ as a cyan dot labelled "kept for now" — the leftmost (smallest) $α$ is always cut first.

Verify: $min (0.02, 0.03) = 0.02 \Rightarrow t_{1}$ ✓.

Worked example Example 7 —

$α$ sweep decides tree size (cell G) Using the two nodes from Ex 6 (with $α_{eff}$ values $0.02$ and $0.03$ ), predict the tree at $α = 0$ , $α = 0.025$ , and $α \to \infty$ .

Forecast: as $α$ rises, does the tree grow or shrink?

$α = 0$ : leaves are free, nothing beats the tie-price. Keep everything → full tree. Why this step? At $α = 0$ the penalty term $α ∣ \tilde{T} ∣$ vanishes, so $R_{α} (T) = R (T)$ and the biggest tree wins.
$α = 0.025$ : any node with $α_{eff} \leq 0.025$ is pruned. That's $t_{1}$ ( $0.02 \leq 0.025$ ) but not $t_{2}$ ( $0.03 > 0.025$ ). Prune $t_{1}$ only. Why this step? A node is cut once the price of a leaf $α$ meets or exceeds that node's tie-point.
$α \to \infty$ : every leaf is infinitely expensive → collapse to the root, a single-leaf tree (predict the majority class). Why this step? This is the maximum-bias, minimum-variance extreme — the opposite end of the U-curve. Compare with Regularization: $α$ here plays the role of a regularization strength.

Verify: the pruned-tree size is monotone non-increasing in $α$ : sizes go full → (minus $t_{1}$ 's branch) → root, never growing back ✓.

Worked example Example 8 — Pre- vs post-pruning on XOR (cell H)

Data is XOR: two binary features $x_{1}, x_{2}$ ; the label is $1$ when exactly one of them is $1$ . The very first split on $x_{1}$ alone barely changes impurity (each side is still $50/50$ ). Why does pre-pruning fail here but post-pruning succeed?

Forecast: will min_impurity_decrease = 0.05 allow the first split?

Impurity of the root. All four cells equally likely, half are class $1$ → Gini $= 1 - (0. 5^{2} + 0. 5^{2}) = 0.5$ . Why this step? We need the baseline to measure any "gain."
Gain of splitting on $x_{1}$ . Each child ( $x_{1} = 0$ and $x_{1} = 1$ ) is still a $50/50$ mix → child Gini $= 0.5$ each → weighted child impurity $= 0.5$ . Gain $= 0.5 - 0.5 = 0$ . Why this step? This is the trap: individually a feature carries no information; only the combination $x_{1}, x_{2}$ does.
Pre-pruning verdict: $0 < 0.05$ , so min_impurity_decrease refuses the split → tree is one node → predicts $50%$ → underfits catastrophically. Why this step? Pre-pruning is myopic: it can't see that the second level of splits would achieve perfect separation.
Post-pruning verdict: grow the full depth-2 tree first (which hits $0$ error), then evaluate each subtree. Every subtree is genuinely useful, so nothing is cut. Solves XOR. Why this step? Post-pruning judges a whole subtree's worth, not one split's short-term gain.

Verify: first-split gain $= 0.5 - 0.5 = 0 < 0.05$ ✓ (pre-pruning stops); full depth-2 tree separates all four XOR cells → train error $0$ ✓.

Worked example Example 9 — Real-world word problem (cell I)

A hospital tree flags patients for follow-up. On training data it flags $99%$ of past cases correctly; on this month's new patients only $84%$ . A false "all-clear" (missing a sick patient) is the costly error, and the current tree has $40$ leaves — many holding a single past patient. What do you change, and using which knob?

Forecast: grow, prune, or ensemble?

Diagnose: train $99%$ vs val $84%$ → gap $= 15$ pts → strong overfitting. Why this step? Big gap = variance problem, exactly the parent's signature; it tells us the tree memorized past patients rather than learning the rule.
Spot the memorized leaves: leaves with a single patient are the hallmark of isolating noise. Why this step? A leaf backed by one patient makes a decision from a sample of size one — statistically meaningless, so it generalizes terribly.
Choose the knob: raise min_samples_leaf (e.g. to $10$ ) so every leaf must be backed by enough patients, and post-prune via cost-complexity, tuning $α$ with Cross-Validation. Why this step? min_samples_leaf directly forbids the single-patient leaves; CV picks the $α$ that maximizes real generalization instead of guessing.
Because the error costs are asymmetric, also consider ensembling with Random Forests and shifting the decision threshold toward "flag." Why this step? Averaging trees cuts variance; the threshold handles the "missing a sick patient is worse" asymmetry so we err on the side of following up.

Verify: gap $99 - 84 = 15$ pts $>$ typical $5$ -pt alarm threshold ✓ → overfitting confirmed; the fix targets variance, the correct lever. Sanity check on the knob: forcing $\geq 10$ patients per leaf caps the leaf count at $\leq 40 \cdot (1/10)$ -ish of the data's worth, killing the size-one leaves by construction ✓.

Worked example Example 10 — Exam twist: forest vs single tree (cell J)

A single deep tree has test-error variance $Var = 0.36$ . You build a Random Forest of $n = 9$ trees that are (idealized) independent. What is the forest's variance, and by what factor did it drop?

Forecast: guess the new variance before computing.

Recall the averaging law. For $n$ independent estimators each with variance $v$ , their average has variance $v / n$ . Why this step? Averaging cancels independent fluctuations — this is why ensembling attacks the variance term of the bias–variance decomposition.
Plug in: $Var_{forest} = \frac{0.36}{9} = 0.04$ . Why this step? $n = 9$ trees → variance divided by $9$ ; we substitute $v = 0.36$ and $n = 9$ into $v / n$ .
Factor of reduction: $0.36/0.04 = 9 \times$ smaller, while the bias stays essentially unchanged (each deep tree was already low-bias). Why this step? Confirms the " $\sim 1/ n$ " rule from the parent note: a single overfit tree and a $9$ -tree forest have the same low bias, but the forest's variance — the overfitting term — is $9$ times smaller, so its test error is lower.

Verify: $0.36/9 = 0.04$ ✓ and reduction factor $= 9$ ✓. (In reality trees are correlated, so the drop is milder — but the direction and mechanism are exactly this.)

Recall Quick self-test on the matrix

A subtree has $∣ \tilde{T}_{t} ∣ = 6$ , $R (T_{t}) = 0.05$ , $R (t) = 0.20$ . Effective $α$ ? ::: $\frac{0.20 - 0.05}{6 - 1} = \frac{0.15}{5} = 0.03$ . Train $91%$ , val $90%$ — overfitting? ::: No; $1$ -pt gap is noise-level (cell B). At $α \to \infty$ the pruned tree becomes… ::: A single root leaf (predict the majority class). Between $α_{eff} = 0.02$ and $0.05$ , which node prunes first? ::: The $0.02$ one — smaller effective $α$ is the weaker link. Nine independent trees cut variance $0.36$ to… ::: $0.04$ (divide by $9$ ).

Connections

Overfitting in decision trees — the parent this drill-page expands.
Decision Trees · Bias-Variance Tradeoff · Random Forests · Cross-Validation · Gini Impurity and Entropy · Regularization
🇮🇳 2.3.05 Overfitting in decision trees (Hinglish)