Cost-Complexity Pruning and the Weakest-Link Sequence

A tree grown to purity has zero training error and no useful structure. Every leaf holds one sample or a group that shares a label, and the splits near the bottom encode accidents of the sample rather than properties of the population. Stopping the growth early is the obvious remedy, but it is a bad one: the split that looks marginal at depth three may be the precondition for a decisive split at depth four, and a stopping rule cannot see that future. Cost-complexity pruning takes the opposite route. Grow the tree too large, then collapse it back in a way that is driven by measured cost rather than by a local guess.

A family of trees indexed by one number

The objective is a penalized training error

$$ R_\alpha(T) = R(T) + \alpha,|T| $$

where $R(T)$ is the error of tree $T$ on the training data, $|T|$ is its number of leaves, and $\alpha \ge 0$ is a penalty per leaf. At $\alpha = 0$ the minimum is the maximal tree, since adding leaves can only reduce training error. As $\alpha$ grows, each additional leaf must buy at least $\alpha$ in error reduction to be worth keeping, and beyond some finite $\alpha$ the best tree is the single root node.

The formulation is a Lagrange multiplier on tree size, and it is deliberately crude: size is a proxy for variance, not a measurement of it. The justification is that the family it generates is nested and small. Rather than searching over the exponential set of subtrees, the algorithm walks down a chain from the full tree to the root, one collapse at a time.

The weakest link

For any internal node $t$, let $R(t)$ be the error if that node were made a leaf, and let $R(T_t)$ and $|T_t|$ be the error and leaf count of the subtree rooted at $t$. Collapsing at $t$ raises the training error by $R(t) - R(T_t)$ and removes $|T_t| - 1$ leaves. The penalty parameter at which that collapse becomes a tie is therefore

$$ g(t) = \frac{R(t) - R(T_t)}{|T_t| - 1} $$

which is the increase in error per leaf removed. The node with the smallest $g(t)$ is the weakest link: the cheapest place, per leaf, to give up purity. Pruning there is optimal for $\alpha = g(t)$, because any other collapse has a strictly worse ratio and would cost more error for the same reduction in leaves.

The procedure then repeats on the pruned tree, recomputing $g$ for the remaining internal nodes. A parent whose child was just collapsed now has a new, smaller subtree, so its $g$ changes and it can become the weakest link later. Each iteration removes at least one leaf, so the loop terminates after at most $|T_{\max}| - 1$ steps, producing the sequence

$$ T_{\max} = T_0 \supset T_1 \supset \dots \supset T_m = {\text{root}} $$

with breakpoints $\alpha_0 = 0 < \alpha_1 < \dots$. Between breakpoints the minimizing tree does not change, so the entire search over $\alpha \in [0, \infty)$ reduces to choosing among $m+1$ candidates. Recomputing $g$ naively at every step costs a pass over the tree per collapse, so the whole sequence is $O(|T_{\max}|^2)$ in the worst case; implementations instead maintain the per-node statistics incrementally and keep the candidates in a priority queue, which is closer to $O(|T_{\max}| \log |T_{\max}|)$.

Computing the sequence in code

The recursion is straightforward if each node already knows its training error as a leaf and the error of its subtree. The version below assumes that information is available and returns the sequence of (alpha, leaf count, subtree error) triples plus a pruning decision per node. It is the shape of the algorithm rather than a complete implementation: in a real tree the errors come from the counts of samples routed to each node.

def prune_sequence(nodes, root):
    # nodes[t] = dict(leaf_error=..., subtree_error=..., leaf_count=..., children=[...])
    seq = []

    def visit(t):
        if not nodes[t]["children"]:
            return nodes[t]["leaf_error"], 1
        err = 0.0
        leaves = 0
        for c in nodes[t]["children"]:
            e, l = visit(c)
            err += e
            leaves += l
        nodes[t]["subtree_error"] = err
        nodes[t]["leaf_count"] = leaves
        return err, leaves

    visit(root)
    while True:
        # Weakest link over the current tree.
        best, best_t = None, None
        for t, nd in nodes.items():
            if not nd["children"]:
                continue
            g = (nd["leaf_error"] - nd["subtree_error"]) / (nd["leaf_count"] - 1)
            if best is None or g < best:
                best, best_t = g, t
        if best_t is None:
            break
        seq.append((best, nodes[best_t]["leaf_count"], nodes[best_t]["subtree_error"]))
        collapse(nodes, best_t)   # turn t into a leaf, drop its descendants
    return seq

The loop as written rescans every node to find the minimum, which is the $O(|T|^2)$ version. A heap keyed on $g$, with the parent of a collapsed node reinserted after the collapse, brings the sequence down to $O(|T| \log |T|)$.

Selecting alpha across folds

The sequence’s practical value is that the candidate trees are nested. Standard $k$-fold cross-validation would normally refit the model $k$ times per hyperparameter value; here each fold’s tree is pruned once, and every candidate in the sequence is then scored by routing the held-out fold through it. The cost is one growth per fold plus one pruning pass per fold, independent of how many candidates the sequence contains.

Selection is usually by minimum mean cross-validated error, with an optional rule that prefers the smallest tree whose error is within one standard error of the minimum. That one-standard-error rule trades a small, statistically invisible increase in error for a substantially smaller tree, and it is the standard defence against the minimum being an artefact of the fold split.

A detail that surprises people: the pruning criterion $R$ should be the same loss used for evaluation, typically misclassification rate or squared error, not the growth impurity. A tree grown with entropy but pruned on misclassification will have its sequence computed on a different scale than its growth, which is fine and intentional, but a tree grown and pruned on entropy will over-prune on classification problems because entropy reductions on small nodes are large relative to the error they actually remove.

Where the criterion misfires

Several failure modes are structural rather than incidental.

The error plateau bites again. When $R$ is misclassification rate and both children of a node keep the same majority class, $R(t) = R(T_t)$, so $g(t) = 0$ and the node is pruned immediately at $\alpha = 0$. Whole branches that separate classes without changing any local majority vanish. This is the same non-strict-concavity problem discussed in the comparison of impurity criteria, now applied one level up. Using the class probabilities or the negative log-likelihood as $R$ removes it, at the cost of a criterion that no longer matches the reported error rate.

Weak nodes dominate the sequence. With many classes, a subtree containing a rare class may have $R(t) - R(T_t)$ of a single sample, giving $g(t) \approx 0$ and early pruning of exactly the branch that detects the rare class. Class weighting in $R$ is the usual adjustment.

Size is not variance. Two trees with the same leaf count can differ substantially in variance, and $\alpha$ cannot distinguish them. The penalty also ignores depth, so a chain of single-child splits costs nothing until it ends in a leaf, which is why implementations usually disallow splits that produce an empty child.

Ties collapse the sequence. When several internal nodes share the same minimal $g$, pruning only one of them would leave a tree that no value of $\alpha$ actually selects: the other nodes have the same ratio and would be cut at the same price. The correct step prunes every node with $g(t) = \min g$ at once, which is why the number of distinct trees in the sequence is at most the number of distinct values of $g$ and can be much smaller than the leaf count. Implementations that cut a single node per iteration still produce a usable sequence, but the intermediate entries are artefacts of the tie-break order rather than candidates at any specific $\alpha$.

The multiplier is not comparable across datasets. $\alpha$ is in units of error per leaf, so its useful range depends on the sample size and on the loss. A value tuned on 10,000 rows says nothing about 100 rows. Only the sequence and the cross-validated choice transfer.

Pruning a single tree is also the baseline that bagging and boosting are measured against, and it interacts with both. A bagged ensemble of pruned trees has less diversity than one of maximal trees, which can reduce the variance benefit; the resampling argument is in bagging and the variance it removes. Boosted trees are usually shallow and unpruned, since the stagewise sum performs its own control of capacity through the learning rate and the number of rounds rather than through per-tree pruning.