Tree Pruning

Pruning is structural regularization for decision trees, trading off training fit against model complexity. Cost-complexity pruning minimizes $R_\alpha(T) = R(T) + \alpha |T|$, where $R(T)$ is the empirical risk — for classification the weighted misclassification rate over leaves $R(T) = \sum_{t \in \text{leaves}(T)} \frac{|D_t|}{|D|} \cdot \text{err}(t)$, for regression the weighted MSE — $|T|$ is the number of leaves, and $\alpha \geq 0$ penalizes each leaf. Pre-pruning stops growth before a split if validation error does not drop (or samples fall below a threshold); post-pruning (CART) grows the full tree first, then bottom-up considers each internal node $t$: replacing subtree $T_t$ by a leaf $t$ changes the cost from $R(T_t) + \alpha |T_t|$ to $R(t) + \alpha$, and equality yields the critical $\alpha = \frac{R(t) - R(T_t)}{|T_t| - 1}$ — prune whenever $\alpha$ exceeds this value. CART starts from $\alpha = 0$ and repeatedly prunes the node with the smallest critical $\alpha$ (weakest-link pruning), producing a nested sequence $T_0 \supset T_1 \supset \cdots \supset T_k$, then selects the tree minimizing validation error, i.e. picks $\alpha^*$. C4.5 uses pessimistic pruning with a continuity-corrected error $R_{pe}(t) = \frac{\text{err}(t) + \frac{|T_t|}{2}}{|D_t|}$.

classic questions about tree overfitting and how max_depth / min_samples_leaf relate to $\alpha$; it is also the bridge to XGBoost's $\gamma$ (minimum split gain, equivalent to post-pruning) and to why random forests skip pruning and rely on randomization.

a fully grown tree can drive training error to zero but has huge variance — pre-pruning is cheap (stop as you grow) but shortsighted (a split with no immediate gain may unlock big gains deeper, so early stopping underfits); post-pruning is global and generalizes better but costs more. Cost-complexity pruning reduces tree selection to a one-dimensional problem: the exponential set of subtrees collapses to a nested chain of $|T| + 1$ candidates, and one cross-validation pass fixes $\alpha^*$ — the canonical answer to the bias-variance tradeoff in trees.

Whiteboard cost-complexity $R_\alpha(T) = R(T) + \alpha |T|$: meaning of each symbol; how does the optimal subtree shrink as $\alpha$ grows?

Derive the pruning criterion: why prune node $t$ to a leaf iff $\frac{R(t) - R(T_t)}{|T_t| - 1} \leq \alpha$?

Pre-pruning vs post-pruning: time cost, over/underfitting risk, and generalization comparison

CART weakest-link pruning: how is the nested subtree sequence generated? How is $\alpha^*$ chosen by cross-validation?

How pruning affects bias-variance; relationship with XGBoost's $\gamma$, max_depth, and min_samples_leaf