Tree pruning techniques: Question bank — AI-ML deep dive

Before the traps, three pictures build the mental model everything below leans on. Refer back to them as you answer — most traps are just a misreading of one of these figures.

The symbols this page uses (all defined here)

Definition Every symbol, in plain words

$T$ = a tree. $T_{t}$ = the subtree hanging off internal node $t$ (node $t$ plus everything below it).
$\tilde{T}$ = the set of leaves (the boxes at the bottom that make a prediction). $∣ \tilde{T} ∣$ = how many leaves there are — our size / complexity measure.
$R (T)$ = the tree's total error. For classification this is the fraction of samples misclassified; for regression it is the total impurity, e.g. sum of squared errors around each leaf's mean. So "error" and "impurity" are the same quantity in two dialects.
$R (t)$ = the error you would get if you collapsed node $t$ into a single leaf — i.e. threw away its whole subtree and just predicted the majority class (classification) or the leaf mean (regression) for everyone landing there. It is the "what if I cut here?" error.
$R (T_{t})$ = the error of the full subtree kept intact. Because more splits can only fit the training data better, $R (t) \geq R (T_{t})$ always.
$α \geq 0$ = the penalty per leaf — a tax. The cost-complexity objective is $R_{α} (T) = R (T) + α ∣ \tilde{T} ∣$ .
$α_{eff} (t) = \frac{R ( t ) - R ( T _{t} )}{∣ T ~ _{t} ∣ - 1}$ = the "price per leaf saved" for pruning node $t$ : extra error gained, divided by leaves removed.

Picture 1 — the U-shaped cross-validation curve

Look at the amber curve. On the left ( $α$ small) the tree is huge and memorizes noise — train error is tiny but test error is high (overfitting, high variance). On the right ( $α$ large) the tree is a stump — both errors are high (underfitting, high bias). The minimum of the amber curve in the middle is the $α$ cross-validation hands us. Every "why can't I just crank $α$ ?" trap is answered by this single dip.

Picture 2 — weakest-link pruning as a nested sequence

Each step raises $α$ and snips the node with the smallest $α_{eff}$ (the cheapest cut — the cyan-circled "weakest link"). The trees form a strictly shrinking chain $T_{0} \supset T_{1} \supset \dots \supset {root}$ : a branch, once cut, never grows back. That monotone shrinking is why "bigger $α$ → smaller tree" and "the sequence is nested" are both true.

Picture 3 — where $α_{eff}$ comes from

The left tree keeps subtree $T_{t}$ ; the right collapses it to one leaf. The rise in error ( $R (t) - R (T_{t})$ , the amber gap) is the cost; the leaves removed ( $∣ \tilde{T}_{t} ∣ - 1$ ) is the benefit. Their ratio is the per-leaf price $α_{eff}$ . Keep this picture in mind for every question about the formula.

True or false — justify

A fully grown tree with pure leaves has zero training error.

In classification, true — each leaf holds one class, so nothing it trained on is misclassified. In regression there is no "class," so "pure" means each leaf has zero variance (often one sample), and the impurity

R (T)

hits zero the same way. Either dialect: the train error bottoms out, which is precisely why training error can never tell you to prune.

Setting

α = 0

in cost-complexity pruning returns the original full tree.

True — with no tax on leaves,

R_{α} (T) = R (T)

, so the objective only minimizes error; the tree that fits training data best is the biggest one. This is the far-left edge of Picture 1.

Increasing

α

can only make the pruned tree smaller or leave it unchanged, never larger.

True — Picture 2 shows the chain is monotone: each weakest-link cut removes a node and no operation ever re-attaches one, so raising the tax can only shed leaves.

The effective alpha

α_{eff} (t)

can be negative.

False in a properly grown tree — since collapsing throws away splits that were chosen to reduce error,

R (t) \geq R (T_{t})

, so the numerator (the amber gap in Picture 3) is

\geq 0

and the denominator is positive, forcing

α_{eff} \geq 0

Pre-pruning and post-pruning always produce the same final tree.

False — pre-pruning decides during growth and may kill a split that looks worthless now but unlocks two great splits below it (the XOR case: the first split alone has zero information gain). Post-pruning grows everything first, so it can see that hidden value before cutting — a mistake it structurally cannot make.

Reduced-Error Pruning requires a separate validation set.

True — REP keeps a cut only if it doesn't hurt accuracy on data the tree never trained on. Judge with training accuracy instead and it never recommends a cut, because training error only falls as splits are added.

The cross-validation curve of test error versus

α

is U-shaped.

True — this is Picture 1: overfitting inflates the left arm (high variance), underfitting inflates the right arm (high bias), and the dip between them is the sweet spot (Bias-Variance Tradeoff).

Cost-complexity pruning is a form of regularization.

True —

R_{α} (T) = R (T) + α ∣ \tilde{T} ∣

is literally "fit +

λ \times

complexity," the same shape as ridge/lasso penalties;

α

plays the role of the regularization strength

λ

(Regularization).

A subtree with only one leaf (

∣ \tilde{T}_{t} ∣ = 1

) has a well-defined

α_{eff}

False — the denominator

∣ \tilde{T}_{t} ∣ - 1

is zero (division undefined). But a one-leaf "subtree" is already a leaf: there is nothing below to cut, so the formula is never evaluated there in the first place.

Random Forests need aggressive pruning of individual trees.

False — a forest deliberately builds many deep, high-variance trees so their independent errors average out; pruning each one would raise its bias and blunt the very variance the averaging was designed to cancel (Random Forests).

Spot the error

"Bigger

α

means we keep more branches, so the tree grows."

Error —

α

is the tax per leaf, not a budget. As Picture 2's chain moves right, higher tax makes surviving leaves more expensive, so the tree shrinks; at

α \to \infty

only the root survives.

"We picked the best

α

by choosing the one with the lowest training error."

Error — training error falls monotonically as splits are added, so this always crowns

α = 0

(no pruning) — the overfit left edge of Picture 1. You must minimize a held-out curve (CV or a validation set), not the train curve.

"The node with the largest

α_{eff}

is the weakest link and gets pruned first."

Error — reversed. The smallest

α_{eff}

is the cheapest cut (least error gained per leaf saved), so it is the weakest link and is guillotined first; that is exactly the cyan-circled node in Picture 2.

"Since post-pruning grows the full tree, it overfits more than pre-pruning."

Error — post-pruning grows big only to see the whole subtree, then cuts back; the delivered tree is the pruned one. Growing first is a diagnostic step, not the final model, so it need not overfit.

"REP: if replacing a subtree with a leaf drops validation accuracy from 90% to 90%, we should keep the subtree to be safe."

Error — accuracy is unchanged, so the extra branches buy nothing on held-out data. By Occam's razor prune to the simpler tree; complexity with no payoff is pure risk of future overfitting.

"The numerator

R (t) - R (T_{t})

measures how much simpler the tree gets."

Error — the amber gap in Picture 3 is the error you pay to collapse (a cost), not simplicity. The denominator

∣ \tilde{T}_{t} ∣ - 1

counts the simplicity gained (leaves removed);

α_{eff}

is cost per unit of simplicity.

"min_impurity_decrease is a post-pruning knob."

Error — it acts during growth, refusing to make a split whose impurity drop is too small, so it is pre-pruning (early stopping). The only post-pruning knob in scikit-learn is ccp_alpha.

Why questions

Why divide by

∣ \tilde{T}_{t} ∣ - 1

rather than by

∣ \tilde{T}_{t} ∣

α_{eff}

Because collapsing a

k

-leaf subtree to a single leaf removes exactly

k - 1

leaves (the one you keep isn't "saved"). Dividing the total error-cost by the leaves actually removed turns a lump cost into a fair per-leaf exchange rate — apples to apples across nodes of different sizes.

Why is post-pruning usually preferred over pre-pruning for accuracy-critical tasks?

The horizon effect: a greedy early-stopping rule only sees the immediate gain of one split. In XOR-like data the first split's information gain is exactly zero, so pre-pruning halts — yet the two splits below it would perfectly separate the classes. Post-pruning grows past the horizon and only then judges the whole subtree, so it never discards a delayed payoff.

Why does pruning trade a small rise in training error for a larger drop in test error?

The deepest branches typically carve out tiny regions around a handful of noisy training points — high variance, low signal. Cutting them nudges training fit up slightly (you lose those memorized points) but removes the wild swings that made predictions on new data erratic, so the test error, which was dominated by that variance, drops more.

Why must the data used to select

α

differ from the data used to grow the tree?

The grown tree has already adapted to its training set, so it looks great there no matter how overfit it is — training error is a biased, over-optimistic judge. Only data the tree hasn't adapted to reveals whether a branch generalizes; this is why we select

α

by Cross-Validation, rotating the held-out fold to use all data fairly.

Why is

R (t) \geq R (T_{t})

guaranteed, and why does that matter for the algorithm?

Splits are chosen to reduce impurity, so keeping a subtree can only match or beat the collapsed leaf — the full subtree is never worse on training data. This guarantees the

α_{eff}

numerator is non-negative, so every threshold is a real

α \geq 0

and the weakest-link sequence is well-ordered from small to large

α

Why does sweeping

α

from

0

\infty

produce a nested sequence of trees, not arbitrary ones?

Each increment of

α

crosses exactly one node's

α_{eff}

threshold and snips that cheapest node from the current tree. Since you only ever remove from what already exists and never re-grow, every tree is a subtree of the one before — a shrinking chain, not a fresh recomputation.

Why is a single deep tree risky where a Random Forest of deep trees is safe?

One deep tree's prediction swings wildly with small data changes (high variance) and nothing averages that away. A forest grows many decorrelated deep trees and averages them; independent errors partly cancel, so the ensemble keeps low bias (deep trees) while the averaging supplies the variance reduction that pruning would otherwise provide.

Edge cases

What tree remains as

α \to \infty

Only the root — a single leaf predicting the majority class (classification) or the global mean (regression). This is the far-right point of Picture 1, where the leaf-tax swamps any accuracy a split could buy.

What happens to

α_{eff}

if collapsing a node changes error by exactly zero (

R (t) = R (T_{t})

The numerator (amber gap in Picture 3) is zero, so

α_{eff} = 0

. The subtree bought no accuracy at all, so it is the very first thing pruned — pure complexity for no benefit, cut even at the mildest tax.

Two nodes tie for the smallest

α_{eff}

— what does weakest-link pruning do?

Both cuts cost the same per leaf, so the algorithm prunes one (implementations pick deterministically) and re-evaluates; the recorded

α

threshold is identical either way, so the resulting nested sequence is unaffected by the tie-break.

If cross-validation picks

α = 0

as best, what does that tell you?

The minimum of Picture 1's amber curve sits at the far left — the full tree already generalizes best. The underlying signal is genuinely complex enough that even the deepest splits capture real structure rather than noise, so no pruning is warranted.

Can over-pruning ever raise test error above the unpruned tree's?

Yes — cut too far and you climb the right arm of Picture 1 (rising bias / underfitting). If the signal is complex, that right arm can rise above the

α = 0

height, so an over-pruned stump underperforms even the overfit giant.

A node's subtree has 2 leaves — what is its

α_{eff}

denominator, and why is this the smallest prunable case?

The denominator is

2 - 1 = 1

. Two leaves is the smallest subtree that can be pruned (merging them removes exactly one leaf), so it is the boundary where

α_{eff}

first becomes well-defined; anything smaller is already a single leaf with nothing to cut.

How does "pure leaf" and "zero training error" translate from classification to regression?

In classification a pure leaf holds one class and contributes zero misclassifications. In regression there are no classes: a "pure" leaf has zero variance (its samples share the target value, often a lone sample), contributing zero to the sum-of-squares impurity

R (T)

. Both dialects reach

R (T) = 0

by isolating points — and both thereby overfit, which is why pruning matters equally in each.

Recall One-line summary of every trap family

Training error can't prune, only held-out data can; ==big $α$ → small tree (Picture 2); smallest $α_{eff}$ is cut first (Picture 3); the CV curve is U-shaped, so pick the minimum, not the extreme== (Picture 1).

Connections

Tree pruning techniques — the parent note this bank drills.
Cross-Validation · Bias-Variance Tradeoff · Regularization · Decision Trees (CART) · Random Forests · Gini Impurity & Entropy
2.3.04 Tree pruning techniques (Hinglish)