Exercises — Overfitting in decision trees

Overfitting. A near-perfect training score with a much worse validation score is the textbook signature.

• Why this step? The gap (99 − 71 = 28 points) means the model learned training-specific noise. In the decomposition $\mathbb{E}[(y-\hat{f}{)}^2]={\text{Bias}}^2+\text{Var}+{\sigma }^2$, that is the variance term being large: tiny wobbles in the data got baked into the tree.

• (a) Underfit — both scores low and close: the tree is too simple to capture the pattern (high bias).
• (b) Overfit — perfect train, big gap (26 pts): high variance.
• (c) Good — high train, small gap (2 pts): the sweet spot.
• Why this step? We read level (are both high?) and gap (train − val). Low-and-close = bias problem; high-and-wide = variance problem.

False. A greedy split is only accepted if it does not raise training error — it either lowers it or leaves it unchanged.

• Why this step? This is exactly why trees overfit: training error can only fall as you grow, so pure greed always says "split more," and nothing stops the memorization.

The effective-$\alpha$ (weakest-link) formula from the parent note: $\alpha =\frac{R(t)-R(T_t)}{|{\tilde{T}}_t|-1}=\frac{0.15-0.03}{5-1}=\frac{0.12}{4}=0.03$

• Why this formula? $\alpha$ is the price per leaf at which keeping the subtree exactly ties with pruning it. The numerator $R(t)-R(T_t)$ is the accuracy you lose by collapsing; the denominator $|{\tilde{T}}_t|-1$ is the number of leaves you save (remove 5, add 1 back = net 4). So $\alpha$ = error paid per leaf removed = 0.03. Meaning: for any penalty $\alpha \ge 0.03$ this subtree is not worth its extra leaves and gets pruned.

${\alpha }_A=\frac{0.10-0.04}{3-1}=\frac{0.06}{2}=0.03,{\alpha }_B=\frac{0.20-0.05}{6-1}=\frac{0.15}{5}=0.03$ They tie at $\alpha =0.03$. Both are equally weak links.

• Why this step? The "weakest link" is the node with the smallest effective $\alpha$ — it costs the least accuracy per leaf saved, so it goes first. Here both cost the same 0.03 per leaf, so either can be cut first; standard implementations prune both at that $\alpha$ level.

Best depth = 6. It has the highest validation accuracy (90%) and a modest gap of $97-90=7$ points.

• Why this step? We choose the depth that maximizes validation accuracy, the bottom of the U-curve — not the one with the best training score. Depth 10 is perfect on train but has the worst val (82%) and largest gap (18 pts) = overfit.

• $\alpha =0$: no penalty on leaves → the full, deepest tree survives → low bias, high variance (overfit).
• $\alpha \to \infty$: every leaf is unaffordable → the tree collapses to a single root leaf (predict one value for everyone) → high bias, low variance (underfit).
• As $\alpha$ increases, the weakest links are cut first, so the tree shrinks smoothly: bias rises, variance falls.
• Best $\alpha$: the one whose tree has the highest cross-validated score — the balance point of the bias–variance tradeoff.
• Why this step? $\alpha$ is a knob that trades capacity for stability, exactly like a regularization strength. We don't guess it — we let cross-validation find the U-curve's bottom.

Look at the figure: XOR has two classes arranged like a checkerboard.

• A single cut on feature $x_1$ splits the plane left/right. But each side still holds a 50/50 mix of both classes — so impurity barely drops. The gain looks useless (< 0.05).
• Yet after that first cut, a second cut on $x_2$ inside each half perfectly separates the classes. The first split is the doorway to two excellent splits.
• Pre-pruning is myopic: it judges the first split in isolation, sees no gain, and stops → single node → underfit.
• Post-pruning is global: it grows the full tree, sees the two useful splits below, and keeps the whole structure.
• Why this step? This is the textbook demonstration that "small gain now" ≠ "useless" — the classic reason to prefer post-pruning.

The small gap only rules out overfitting; it does not rule out underfitting. Both scores could be capped low because the tree is too simple to express the true pattern.

• Diagnostic: grow a deeper tree. If deeper trees reach higher validation accuracy (say 96%), then depth 3 was underfitting — leaving signal on the table.
• Why this step? A tight train–val gap is necessary but not sufficient for a good model. You must also confirm the validation accuracy is as high as it can reasonably get, i.e. you're at the U-curve bottom, not stuck up its left wall.

A defensible pipeline:

1. Split data into train / validation / test (or use k-fold cross-validation). Why: you cannot detect overfitting without unseen data.
2. Grow the full tree on the training set. Why: post-pruning needs the whole tree to avoid the XOR-style myopia of early stopping.
3. Cost-complexity prune to get the nested sequence of trees, one per $\alpha$ in the weakest-link order. Why: this yields a small, ordered menu of candidate trees instead of blindly guessing knobs.
4. Cross-validate each candidate; pick the $\alpha$ with the best average validation score. Why: this locates the bottom of the U-curve robustly, not on one lucky split.
5. (Optional) Ensemble with random forests if variance is still high. Why: averaging many de-correlated deep trees drives variance down by roughly $1/n$ with little bias cost.
6. Report on the untouched test set once, at the end. Why: the test set stays sacred so your accuracy estimate isn't inflated by tuning.

• Why this ordering? Each stage attacks a different failure: (1) enables detection, (2–4) tame variance via the tradeoff knob, (5) is a stronger variance hammer, (6) keeps the final number honest.

• Best CV accuracy = 0.885 ($T_B$). Tolerance band = $0.885-0.02=0.865$.
• Trees within the band (accuracy $\ge 0.865$): $T_B$ (0.885) and $T_C$ (0.87). $T_A$ at 0.86 is outside the band.
• Among the qualifying trees, pick the smallest: $T_C$ with 4 leaves.
• Deploy $T_C$.
• Why this step? When two trees are statistically comparable, the simpler one generalizes more safely (lower variance, easier to interpret). The tolerance stops us from chasing a tiny, possibly-noise accuracy bump into a bushier, riskier tree.

$\alpha =\frac{R(t)-R(T_t)}{|{\tilde{T}}_t|-1}=\frac{0.10-0.10}{4-1}=\frac{0}{3}=0$ Effective $\alpha =0$. This subtree costs zero training accuracy to prune.

• Meaning: it is the weakest possible link — the very first thing pruned as soon as any penalty $\alpha >0$ is applied. It adds 3 leaves and buys nothing on the training set (pure over-fitting fluff).
• Why this step? The formula gracefully handles the degenerate "no-gain" subtree: numerator 0 → $\alpha =0$ → cut immediately. This is the mechanism by which cost-complexity pruning automatically deletes splits that only chase noise.

• $\alpha \to 0^{+}$: penalty vanishes → the full unpruned tree (every leaf free). One point per leaf in the limit → train error 0, minimum bias, maximum variance → overfit.
• $\alpha \to \infty$: every leaf priced out of existence → the tree collapses to a single root leaf predicting the majority class for everyone → maximum bias, minimum (zero) variance → underfit.
• The best model lives strictly between these poles, chosen by cross-validation.
• Why this step? Confirming both endpoints proves the knob spans the entire bias–variance spectrum, so a good middle must exist.

Rearrange the decomposition: $\text{Var}=\text{Test MSE}-{\text{Bias}}^2-{\sigma }^2=0.30-0.02-0.05=0.23$

• Variance = 0.23, which dwarfs both the ${\text{Bias}}^2=0.02$ and the noise floor ${\sigma }^2=0.05$.
• Diagnosis: severe overfitting — the variance term dominates the test error.
• Cure: prune (raise $\alpha$) or ensemble with random forests to slash that 0.23 variance; bias is already tiny so we can afford to trade a little of it away.
• Why this step? Splitting test error into its three parts tells you which lever to pull: a giant variance term means "reduce capacity / average trees," not "add complexity."