Overfitting & cost-complexity pruning

The top row is training data — five of those points are quietly mislabeled, noise a real dataset would have. Drag depth up: watch the tree stop finding the boundary and start carving out tiny one-point regions instead, each one built to rescue a single mislabeled point.

Nothing stops a tree from growing until every training point is classified perfectly — split enough times and you can isolate any single point into its own leaf. The question isn't whether it can memorize noise, it's whether doing so helps on data it hasn't seen:

• gap — the difference between training and validation accuracy; a growing gap signals overfitting.
• $\text{accuracy}_{\text{train}}$ — the fraction of training points the tree classifies correctly.
• $\text{accuracy}_{\text{validation}}$ — the fraction of held-out (never-trained-on) points the tree classifies correctly.

The gap tells you that a tree is overfitting, but it needs a validation set to compute. Cost-complexity pruning finds the right size using only training data, by charging a fixed toll for every leaf a tree keeps:

• $R_\alpha(T)$ — tree $T$'s cost-complexity score at penalty strength $\alpha$; smaller is better.
• $R(T)$ — $T$'s training misclassification rate, $1 - \text{accuracy}_{\text{train}}$.
• $\alpha$ — the price charged per leaf; $\alpha = 0$ charges nothing, larger $\alpha$ charges more.
• $|T|$ — $T$'s leaf count, i.e. how many regions it carved feature space into.

1. alpha=0 reduces to pure training error

   With no penalty, $R_\alpha(T)$ is just $R(T)$ — whichever tree fits training data best wins, no matter how many leaves it took to get there. This is exactly the overfitting problem, restated as an objective.

2. Growing alpha makes extra leaves cost more than they're worth

   Each split only pays for itself if the training-error improvement it buys is bigger than $\alpha$. As $\alpha$ rises, splits that were only rescuing one or two noisy points stop being worth their toll first.

3. This finds the right complexity blind — no validation set needed

   Real pruning algorithms (e.g. scikit-learn's ccp_alpha) minimize exactly this objective. It's not magic: it works because $\alpha$ acts as a stand-in for "how much do I trust that this split reflects real structure, not noise" — the same judgment a validation set makes empirically.

The bottom row is validation data the tree never trained on — clean, no mislabeled points. Depth 1 or 2 already gets every single one right. Push the depth slider past that and watch validation accuracy start dropping while training accuracy keeps climbing. The α buttons show a different way to catch this: cost-complexity pruning picks a depth using only the training-side numbers above, no validation peek required — watch its pick shrink as α grows.

1. Depth 1, the shallow tree

   One split at $x = 9.5$:

   • Training accuracy: $20/25 = 80\%$ (the 5 mislabeled points are the only misses)
   • Validation accuracy: $24/24 = 100\%$
   • Leaves: $|T|=2$, so $R(T) = 1-0.80 = 0.20$
2. Depth 5, the overgrown tree

   Splitting all the way to depth 5, rescuing 4 of the 5 noisy points:

   • Training accuracy: $24/25 = 96\%$
   • Validation accuracy: $20/24 \approx 83\%$ — it falls even as training accuracy climbed
   • Leaves: $|T|=10$, so $R(T) = 1-0.96 = 0.04$

   (Depth 6 adds one more leaf for zero extra training accuracy, so it never wins at any $\alpha \geq 0$ — pruning drops that redundant split for free.)

3. alpha=0: raw training error wins, and the overgrown tree looks unbeatable

   $R_0(\text{depth }1) = 0.20 + 0 \times 2 = 0.20$, while $R_0(\text{depth }5) = 0.04 + 0 \times 10 = 0.04$. Depth 5 wins by this metric alone — exactly the overfitting trap, since it's also the worse tree on validation data.

4. alpha=0.02: an exact tie, and ties favor the smaller tree

   $R_{0.02}(\text{depth }1) = 0.20 + 0.02 \times 2 = 0.24$ and $R_{0.02}(\text{depth }5) = 0.04 + 0.02 \times 10 = 0.24$ — dead even. Real weakest-link pruning (and the code here) breaks such ties in favor of the smaller tree, so $\alpha = 0.02$ is already enough to recover depth 1 — and depth 1 is also the validation-optimal tree.

5. alpha=0.03: no longer even close

   $R_{0.03}(\text{depth }1) = 0.20 + 0.03 \times 2 = 0.26$, while $R_{0.03}(\text{depth }5) = 0.04 + 0.03 \times 10 = 0.34$. Depth 1 wins outright now — cost-complexity pruning found the right size using only training-side arithmetic, no validation set required.