Tree Pruning and Complexity Control

A decision tree is built by recursive binary splitting: at each node, the algorithm picks the feature and threshold that most reduces impurity (measured by entropy, Gini index, or variance), guided by the Entropy and Information Gain framework for classification. If this process runs unchecked, it continues until every leaf is pure or contains a single example. The resulting full tree has near-zero training error but typically high test error, because many of its deepest splits fit sampling noise rather than real structure in the data-generating process.

Overfitting in trees arises because the greedy splitting criterion only ever looks at whether a split reduces impurity on the training set, with no notion of how many data points support that reduction, or whether it would replicate on a fresh sample. A split that isolates a single mislabeled outlier lowers training impurity to zero in that leaf, but adds pure noise to the decision boundary. This is exactly the variance term in the bias-variance decomposition: small perturbations of the training sample produce very different trees.

Complexity control addresses this by explicitly penalizing tree size. Two mechanisms are used in practice: 1. Pre-pruning (stopping rules): halt the greedy growth early using thresholds such as maximum depth, minimum samples required to split a node, minimum samples per leaf, or a minimum required impurity decrease. Growth stops as soon as a rule is triggered. 2. Post-pruning (cost-complexity pruning): grow the tree fully (or near-fully), then remove subtrees that do not "earn" their complexity, using a global penalized objective. Post-pruning is generally preferred because pre-pruning is myopic: a split might look useless in isolation (small impurity gain) but enable a very informative split immediately below it. Growing fully and pruning back considers the whole subtree's value, not just one split at a time.

Cost-complexity pruning (also called weakest-link pruning) defines, for any subtree `T` of a fully grown tree `T₀`, a penalized objective: ``` R_α(T) = R(T) + α · |T| ``` Here `R(T)` is the total training misclassification rate (or sum of squared errors for regression), summed over all leaves, `|T|` is the number of leaves in `T`, and `α ≥ 0` is a complexity parameter. Large `α` penalizes leaves heavily and favors small trees; `α = 0` recovers the full tree, since adding leaves can never increase `R(T)`. For a fixed `α`, the tree `T_α` that minimizes `R_α(T)` among all subtrees of `T₀` is well defined and unique in a strong sense: as `α` increases from 0 to infinity, there is a nested sequence of optimal subtrees, ``` T₀ ⊃ T₁ ⊃ T₂ ⊃ ... ⊃ {root} ``` each obtained from the previous one by collapsing one or more subtrees into leaves. This nesting is what makes the algorithm efficient: instead of searching over all `2^(number of internal nodes)` possible subtrees, we only need to find the finitely many "breakpoints" of `α` at which the optimal subtree changes.

The weakest-link algorithm

For any internal node `t`, define the subtree rooted at `t` as `T_t`. Compare pruning `T_t` back to a single leaf versus keeping it: ``` R(t) = training error if node t is turned into a single leaf R(T_t) = sum of training error over all leaves of the subtree T_t ``` Since `T_t` was grown to reduce error, `R(T_t) ≤ R(t)` always. Define the effective alpha of node `t`: ``` g(t) = ( R(t) − R(T_t) ) / ( |T_t| − 1 ) ``` This is the per-leaf error reduction that the subtree `T_t` buys over collapsing it — the break-even penalty at which pruning `t` becomes worthwhile. The node (or nodes) with the smallest `g(t)` is the weakest link: it contributes the least error reduction per extra leaf, so it is the first to be pruned as `α` increases from 0. ```pseudocode function COST_COMPLEXITY_PRUNING(T0):

# T0: fully grown tree

# Returns: sequence of trees T0 ⊃ T1 ⊃ ... ⊃ {root}

# and matching alphas 0 = a0 < a1 < a2 < ... trees = [T0] alphas = [0] T = COPY(T0) while T is not just the root: best_g = +infinity best_node = null

# bottom-up pass: compute g(t) for every internal node for each internal node t in T (post-order traversal): R_t = training_error_if_leaf(t) # R(t) R_Tt = sum_of_leaf_errors(subtree_at(t)) # R(T_t) size = number_of_leaves(subtree_at(t)) # |T_t| g_t = (R_t - R_Tt) / (size - 1) if g_t < best_g: best_g = g_t best_node = t

# prune the weakest link: collapse best_node into a leaf T = COLLAPSE_TO_LEAF(T, best_node) trees.append(COPY(T)) alphas.append(best_g) return trees, alphas ``` ```pseudocode function SELECT_BEST_ALPHA(trees, alphas, D):

# D: training data, used via K-fold cross-validation best_score = +infinity best_alpha = null for each alpha_k in alphas: cv_error = 0 for fold f = 1 .. K: train_fold, val_fold = split(D, f) T0_fold = GROW_FULL_TREE(train_fold) trees_fold, alphas_fold = COST_COMPLEXITY_PRUNING(T0_fold) T_fold = tree in trees_fold matching pruning strength alpha_k cv_error += ERROR(T_fold, val_fold) cv_error /= K if cv_error < best_score: best_score = cv_error best_alpha = alpha_k return best_alpha ``` The final model prunes the fully grown tree on the entire training set using `best_alpha` (re-running `COST_COMPLEXITY_PRUNING` once on all the data, then stopping at the tree matching `best_alpha`), combining the statistical strength of cross-validation with a single deployed tree.

Growing the full tree. With `n` training points and `d` features, finding the best split at one node costs `O(d · n log n)` (sorting each feature) in the naive implementation, or `O(d · n)` if features are pre-sorted once and split points scanned incrementally. Over a balanced tree of depth `O(log n)`, the total work across one full level is `O(d · n)`, and summing over `O(log n)` levels gives `O(d · n log n)` total construction time. In the worst case (a completely unbalanced tree, e.g. one example peeled off per split), this degrades to `O(d · n²)`.

Computing the pruning sequence. For weakest-link pruning, one pass over all internal nodes (post-order traversal) computes `R(t)`, `R(T_t)`, and `|T_t|` for every node in `O(|T₀|)` time total, since each leaf's error is aggregated up to its ancestors exactly once. Naively, the outer loop of `COST_COMPLEXITY_PRUNING` repeats this for each of up to `O(|T₀|)` pruning steps, giving `O(|T₀|²)` time overall. In practice this is fast because `|T₀|` (number of leaves) is typically `O(n)` in the worst case but much smaller in balanced trees, and an amortized bottom-up implementation that updates only ancestors of the pruned node after each step reduces the total work to `O(|T₀| log |T₀|)` for balanced trees. Space is `O(|T₀|)` to store the tree and the pruning sequence.

Cross-validation cost. Selecting `α` with `K`-fold cross-validation multiplies the growth-plus-pruning cost by `K`, since a full tree must be grown and pruned on each fold. This is the dominant cost in practice but is embarrassingly parallel across folds.

Why the nested sequence exists (correctness argument). The key fact underlying the whole algorithm is: > If `T_α` minimizes `R_α(T)` over subtrees of `T₀`, and `α₂ > α₁`, then the minimizer `T_{α₂}` is a subtree of `T_{α₁}`. Proof sketch. Fix a node `t`. The function `α ↦ R(t) + α` (the cost of collapsing `t` to a leaf) is linear and increasing in `α`, while `α ↦ R(T_t) + α·|T_t|` (the cost of keeping the subtree) is also linear and increasing, but with a steeper slope (`|T_t| > 1` versus slope `1` for the leaf). Two increasing lines with different slopes cross at most once. Since `R(T_t) ≤ R(t)`, the subtree line starts below (or equal to) the leaf line at `α = 0`, and because it has a steeper slope, it must eventually cross above the leaf line as `α` grows. That crossing point is exactly ``` g(t) = ( R(t) − R(T_t) ) / ( |T_t| − 1 ) ``` Below `g(t)` the subtree is worth keeping; above `g(t)` it is worth collapsing. Because every subtree has such a threshold, and thresholds only get crossed (not un-crossed) as `α` rises monotonically, subtrees can only be removed, never re-added, as `α` increases — giving the nested chain `T₀ ⊃ T₁ ⊃ ...`. This justifies picking, at each step, the node with the globally smallest `g(t)`: it is the first threshold to be crossed, hence the correct next pruning event. This greedy bottom-up selection is optimal precisely because of this crossing-point monotonicity, not merely a heuristic.

Honest tradeoffs. Cost-complexity pruning is a discrete, greedy search over a specific nested family of subtrees; it does not search all `2^{|internal nodes|}` possible subtrees, but this restriction is exactly what the monotonicity argument shows is safe — the optimum for any `α` lies within this family. The real cost is statistical, not computational: the quality of the chosen `α` depends entirely on how well cross-validation estimates generalization error, which needs enough data to split into folds reliably. On small datasets, pruning decisions can be noisy, which is one motivation for ensembling many trees, as in Random Forests, rather than committing to one pruned tree.

Consider a small regression tree predicting a house price (in $1000s) from square footage, grown fully on 8 training points until every leaf has one point. Suppose the fully grown tree `T₀` has 4 leaves, arranged as two sibling pairs under two internal nodes, `A` and `B`, both children of the root.

Reading the table: node `B`'s split barely reduces error (9.0 → 8.0), so its `g(B) = 1.0` is the smallest. This is the weakest link — it is pruned first, at `α₁ = 1.0`. Collapsing `B` gives tree `T₁` with 3 leaves: `A`'s two leaves plus `B` collapsed into one. Recomputing on `T₁`: only the root's `g` value needs updating (the effective alpha for keeping the whole tree `T₁` versus collapsing everything to a single leaf). Suppose this comes out to `g(root) ≈ 3.0`. Since there is only one internal node choice left, the next prune, at `α₂ = 3.0`, collapses everything to the root — a single leaf predicting the overall mean price. The pruning path is therefore:

Suppose 5-fold cross-validation is now run, evaluating a tree of each size on held-out folds. Typical behavior: `T₀` (4 leaves) has the lowest training error (12.0) but the highest cross-validated error, because its finest split (inside `B`) fits noise. `T₁` (3 leaves) has the lowest cross-validated error, say 14.5, versus 16.0 for `T₀` and 22.0 for `T₂`. Cross-validation therefore selects `α ≈ 1.0`, and the deployed model is `T₁`: keep the informative split at `A`, discard the noisy split at `B`. This matches intuition — `A`'s split earned a large error reduction (6.0 per leaf) while `B`'s barely helped (1.0 per leaf) relative to the added complexity.

The cost-complexity pruning algorithm, along with the CART (Classification and Regression Trees) framework that formalized decision tree growth and pruning together, was introduced by statisticians working on nonparametric regression and classification in the early 1980s. Their central insight — that model selection over a nested family of trees can be reduced to a single scalar penalty tunable by cross-validation — became a template later reused for penalized regression and model selection generally.

Pruned decision trees remain a staple wherever interpretability matters as much as accuracy: credit scoring models that must be explained to regulators, clinical decision rules, and early warning systems in operations. Statistical software packages (rpart in R, scikit-learn's `DecisionTreeClassifier`/`Regressor` with `ccp_alpha`) implement cost-complexity pruning essentially as described here, exposing the `α` parameter directly for practitioners to tune via cross-validation. More broadly, the bias-variance reasoning behind pruning underlies the design of every tree-based ensemble. Gradient boosted trees use shallow, heavily pruned or depth-limited trees as weak learners precisely because a single tree's high variance is undesirable when trees are combined sequentially. Random Forests take the opposite tack: instead of pruning each tree to reduce its individual variance, they grow many trees deep (low bias, high variance) and average their predictions, letting averaging — rather than pruning — cancel out variance. Understanding pruning is therefore a prerequisite for understanding why ensembles are built the way they are, and it is the clearest concrete illustration of the The Bias–Variance Tradeoff and the search-for-signal logic behind Entropy and Information Gain-based splitting.

Ask the tutor: How would the pruning path change if I used Gini impurity instead of misclassification rate for R(t)?