Exercises — Tree pruning techniques

• $\alpha =0$: no size tax, so the cost is pure error $R(T)$ → the full tree wins → (b) and (c) (a fully grown tree has the lowest training error).
• $\alpha \to \infty$: the term $\alpha |\tilde{T}|$ dominates everything, so the cheapest tree is the one with the fewest leaves — the root → (a).

Picture: on figure s01, (b)/(c) are the far-left end, (a) is the far-right end.

Pre-pruning stops the tree early (decides before/while growing); post-pruning grows fully then chops.

• max_depth → pre (caps growth)
• ccp_alpha → post (cost-complexity, applied after full growth)
• reduced-error pruning → post (validation-set chopping)
• min_samples_leaf → pre
• min_impurity_decrease → pre

Mnemonic: "PRE stops, POST chops."

${\alpha }_{\text{eff}}(t)=\frac{R(t)-R(T_t)}{|{\tilde{T}}_t|-1}=\frac{0.12-0.03}{4-1}=\frac{0.09}{3}=0.03$ What this means: $0.03$ is the "price per leaf removed." Only once the penalty $\alpha \ge 0.03$ does collapsing this node pay for itself.

$R_{\alpha }(T)=0.04+0.008\times 12=0.04+0.096=0.136$ $R_{\alpha }(T^{\prime })=0.09+0.008\times 5=0.09+0.040=0.130$ Since $0.130<0.136$, prune to $T^{\prime }$. We paid $0.05$ extra training error to shed $7$ leaves; at this $\alpha$ the trade is a net win.

$R_{\alpha }(T)=0.04+0.005\times 12=0.04+0.060=0.100$ $R_{\alpha }(T^{\prime })=0.09+0.005\times 5=0.09+0.025=0.115$ Now $0.100<0.115$, so keep the full tree $T$. The same two trees — only $\alpha$ changed — and the decision flipped. This is exactly why $\alpha$ must be chosen with care (Cross-Validation).

Compute ${\alpha }_{\text{eff}}$ for each and take the smallest: ${\alpha }_A=\frac{0.20-0.14}{4-1}=\frac{0.06}{3}=0.020$ ${\alpha }_B=\frac{0.10-0.06}{3-1}=\frac{0.04}{2}=0.020$ ${\alpha }_C=\frac{0.15-0.11}{5-1}=\frac{0.04}{4}=0.010$ Smallest is ${\alpha }_C=0.010$, so node C is the weakest link — it's cheapest to remove per leaf saved, so it gets guillotined first. (A and B tie at $0.020$; a tie is broken by convention, e.g. lower node id — but neither is first here.)

A subtree $T_t$ is grown by splitting node $t$ to reduce impurity/error. Each split can only keep or lower the training error, so the whole subtree's error $R(T_t)$ is $\le$ the collapsed-node error $R(t)$. Hence $R(t)-R(T_t)\ge 0$. A negative numerator would mean the subtree is worse on training data than the single leaf — impossible for a properly grown tree because CART never accepts a split that increases training error. If you ever see it, your $R(t)$ and $R(T_t)$ are on different datasets (e.g. validation vs training) — that's a different (and valid) game, but not cost-complexity's numerator. See Decision Trees (CART).

At each step we prune the node with the smallest current ${\alpha }_{\text{eff}}$ and record that $\alpha$; the next step's smallest is $\ge$ the previous, so recorded thresholds increase: ${\alpha }_1<{\alpha }_2<\dots$ The sequence is nested because every prune only removes a subtree from the previous tree — we never add anything back. So each $T_{i+1}$ is literally $T_i$ with one subtree collapsed → $T_{i+1}\subset T_i$. On figure s01 this is why the tree size only steps down as we cross each dashed line, never up.

Pick the $\alpha$ with minimum CV error: $\alpha =0.010$ (CV error $0.132$). Shape: the curve is U-shaped in $\alpha$.

• Left side ($\alpha$ small): tree is large → high variance, it overfits noise, CV error high (Bias-Variance Tradeoff).
• Right side ($\alpha$ large): tree is tiny → high bias, it underfits, CV error high again.
• The minimum is the sweet spot. This is exactly why "just crank $\alpha$" is wrong — past the bottom of the U, error climbs.

REP rule: replace the subtree with a leaf if validation accuracy does not decrease (leaf $\ge$ keep).

• N1: leaf $0.84\ge 0.82$ → prune (accuracy even rose — subtree was overfitting).
• N2: leaf $0.88\ge 0.88$ → prune (tie; simpler wins by Occam).
• N3: leaf $0.86<0.90$ → keep (pruning would lose real signal). Why validation and not training: on the training set the subtree always ties or beats the leaf, so training never votes to prune. The validation set is data the tree did not memorize, so it exposes fake (noise-fitting) splits.

Derivation. Keeping costs $R_{\alpha }(T_t)=R(T_t)+\alpha |{\tilde{T}}_t|$. Collapsing to one leaf costs $R_{\alpha }(t)=R(t)+\alpha \cdot 1$. Prune when collapsing is no worse: $R(t)+\alpha \le R(T_t)+\alpha |{\tilde{T}}_t|$ $R(t)-R(T_t)\le \alpha (|{\tilde{T}}_t|-1)$ Since $|{\tilde{T}}_t|-1>0$, divide safely: $\alpha \ge \frac{R(t)-R(T_t)}{|{\tilde{T}}_t|-1}={\alpha }_{\text{eff}}(t)$ Break-even for this node: ${\alpha }_{\text{eff}}=\frac{0.11-0.05}{6-1}=\frac{0.06}{5}=0.012$ So pruning is at least as good for all $\alpha \ge 0.012$; below that, keeping the subtree wins. This ties back to Regularization: $\alpha$ is a regularization strength on tree size.

(a) ${\alpha }_P=\frac{0.16-0.10}{4-1}=\frac{0.06}{3}=0.020$ ${\alpha }_Q=\frac{0.22-0.10}{7-1}=\frac{0.12}{6}=0.020$ They tie at $0.020$. (b) Both become worth pruning at the same $\alpha =0.020$. Weakest-link breaks ties by a fixed rule (e.g. prune the node that removes more error, or lowest node index); either way both are recorded at $\alpha =0.020$ and the sequence collapses them one after another at that same threshold. So recorded $\alpha$: first prune at $0.020$, second prune at $0.020$. (c) Prune P first: it removes $|{\tilde{T}}_P|-1=3$ leaves. Remaining leaves $=10-3=7$. (Then pruning Q removes $7-1=6$ leaves → $7-6=1$; but Q sits in the original $T_0$ leaf count — since P and Q are disjoint, after both prunes: $10-3-6=1$ leaf, i.e. the root plus P and Q each as leaves would over-count; disjoint means removing $3$ then $6$ from the $10$, leaving $10-3-6=1$? Careful: $10$ leaves total, P's subtree owns $4$, Q's owns $7$ — but $4+7=11>10$, so they cannot both be disjoint subtrees of a 10-leaf tree.)

Resolution of (c): the disjoint counts $4+7=11$ exceed the tree's $10$ leaves, which is impossible — so as stated the two subtrees cannot both be disjoint inside $T_0$. The teaching point: always sanity-check that $\sum (\text{disjoint subtree leaves})\le |{\tilde{T}}_0|$. Taking the intended answer for the first prune only: after pruning P, $10-3=7$ leaves remain, and its recorded $\alpha =0.020$.

For: pruning each tree lowers per-tree variance and shrinks memory/inference cost. Against: a random forest already controls variance by averaging many high-variance, low-bias trees — pruning raises each tree's bias, and the ensemble relies on deep, decorrelated trees to average well, so heavy pruning can hurt accuracy. Verdict: light pruning (or a small ccp_alpha) can trim size cheaply, but the aggressive pruning we'd use for a single tree is usually counterproductive in a forest — the variance reduction it targets is already handled by averaging.

The knob $\alpha$ is a ::: tax on the number of leaves (bigger $\alpha$ → smaller tree) The weakest link is the node with the ::: smallest ${\alpha }_{\text{eff}}$ ${\alpha }_{\text{eff}}=\frac{R(t)-R(T_t)}{|{\tilde{T}}_t|-1}$ divides by $|{\tilde{T}}_t|-1$ because ::: that is the number of leaves actually removed when the subtree collapses The CV-error-vs-$\alpha$ curve is shaped like ::: a U (overfit on the left, underfit on the right) REP uses a validation set instead of training because ::: training error never votes to prune (it always drops with more splits)