skip to content

How does cost-complexity pruning use alpha to shrink a fully grown decision tree?

level: middleimportance: must knowfreq 55%

answer

  1. penalise size, not just error
  2. a price per leaf
  3. error plus alpha times leaf count
  4. collapse the cheapest subtree first
  5. one nested path, alpha picked by validation

basics

~20 s

Cost-complexity pruning scores a tree as training error plus alpha times its leaf count, then collapses the subtree with the smallest error cost per leaf removed. Larger alpha yields a smaller tree, and alpha is chosen by cross-validation.

solid answer

~50 s

Grow the tree fully, then judge candidate subtrees by `R_alpha(T) = R(T) + alpha * |leaves(T)|`, where `R(T)` is the training cost — misclassification cost or total weighted leaf impurity — and alpha is a price per leaf. At alpha 0 the full tree wins; as alpha rises, leaves must pay for themselves. The weakest-link procedure computes, for each internal node, `g(t) = (R(t) - R(subtree at t)) / (|leaves of subtree| - 1)`: the extra error per leaf saved by collapsing that node. The node with the smallest `g(t)` is collapsed first, and repeating this yields a nested sequence of subtrees, each optimal over a range of alpha, ending at the root. On a 400-node school-dropout-risk tree, sweeping alpha walks that sequence down to roughly 15 nodes. You then cross-validate the trees in the sequence and keep the alpha whose tree generalises best.

code

python · 15 lines
python
# Weakest-link step of cost-complexity pruning, on a tree fitted to 400 rows.
# Collapsing an internal node to a leaf raises training error but removes leaves.
n = 400
# node -> (errors if collapsed to a leaf, errors kept as a subtree, leaves in subtree)
nodes = {"A": (48, 30, 7), "B": (22, 20, 3), "C": (61, 25, 13)}

def effective_alpha(collapsed, kept, leaves):
    return ((collapsed - kept) / n) / (leaves - 1)

for name in sorted(nodes):
    collapsed, kept, leaves = nodes[name]
    print(name, "effective alpha =", round(effective_alpha(collapsed, kept, leaves), 5))

weakest = min(nodes, key=lambda k: effective_alpha(*nodes[k]))
print("pruned first:", weakest)

go deeper

for a junior

Recall that cost-complexity pruning grows the tree first and then cuts it back, and that a single knob called alpha trades training error against the number of leaves: bigger alpha, smaller tree.

for a middle

Be able to write the objective as training cost plus alpha times leaf count, describe the weakest-link ratio that decides which subtree collapses first, and explain why the resulting subtrees form one nested sequence.

for a senior

Show how you select alpha out of sample, why its value is tied to the error scale of the specific dataset, and how you would justify the resulting tree size to someone who has to read and act on the rules.

for a principal

Own the call between a small, auditable pruned tree and a larger or ensembled model that scores better — including who bears the cost of an unexplainable decision in your domain, and how that shapes the size you are willing to ship.

## The idea Pre-pruning decides during growth; cost-complexity pruning decides afterwards. You deliberately grow the tree too large, then ask: of all the subtrees of this tree that share its root, which is the right size? Comparing them on training error alone is useless — training error falls monotonically as leaves are added, so the full tree always wins. So you charge for size. Define, for a subtree `T`: ``` R_alpha(T) = R(T) + alpha * |leaves(T)| ``` `R(T)` is the *resubstitution cost* on the training data: for a classification tree, the misclassification rate (optionally weighted by misclassification costs); for a regression tree, the total squared error, or equivalently the summed weighted impurity of the leaves. `|leaves(T)|` is the number of terminal nodes. `alpha >= 0` is the complexity parameter — the price you charge per leaf, in the same units as the error. At `alpha = 0` the objective is training error, so the full tree is optimal. As alpha grows, each leaf has to justify its existence by the error it removes. At a large enough alpha the root alone wins. ## Weakest-link pruning You do not enumerate subtrees — there are exponentially many. Breiman's weakest-link procedure walks the sequence directly. For an internal node `t`, let `T_t` be the subtree rooted at it. Collapsing `t` into a leaf raises training error from `R(T_t)` to `R(t)` and removes `|leaves(T_t)| - 1` leaves. The break-even price is ``` g(t) = ( R(t) - R(T_t) ) / ( |leaves(T_t)| - 1 ) ``` the extra error paid per leaf saved. Below that alpha the subtree is worth keeping; above it, collapsing is cheaper. The node with the smallest `g(t)` is the weakest link: it is the first place the tree becomes not worth its size. Collapse it, recompute, and repeat. This produces a **nested** sequence `T_0 ⊃ T_1 ⊃ ... ⊃ {root}` with an increasing sequence of alpha thresholds. Two facts make this the standard method: for every alpha there is a unique smallest subtree minimising `R_alpha`, and every such minimiser appears in this one sequence. So a single pass over the fitted tree gives you the entire pruning path, and choosing alpha reduces to choosing a point on a short list. Concretely, a 400-node school-dropout-risk tree might collapse through a few dozen subtrees as alpha rises, arriving at something near 15 nodes — a model a caseworker can actually read — with held-out accuracy at or above the original. ## Choosing alpha Alpha is a hyperparameter, so it is chosen out of sample. The usual recipe: fit the full tree and its pruning path, cross-validate the pruned tree at each candidate alpha (in practice, at values inside each interval of the path where the subtree is constant), and keep the alpha with the best mean validation score. Then refit on all the data and prune at that alpha. Note the scale-dependence: because `R(T)` is measured in error units, a good alpha for one dataset says nothing about another. Never carry a number across problems. ## Why post-pruning is different from stopping early Because the tree is grown first, every subtree is evaluated *as a whole*. A node whose own split buys almost nothing but whose descendants buy a lot has a large `R(t) - R(T_t)` and therefore a high `g(t)`, so it survives pruning. A pre-pruning threshold applied at that same node during growth would have refused the split and never seen the descendants. That is the structural argument for post-pruning, and the price is compute: you pay to grow the full tree before discarding most of it. ## What interviewers probe Common checks: that alpha multiplies leaf count, not depth; that raising alpha shrinks rather than grows the tree; that the sequence is nested rather than a fresh search per alpha; and that alpha comes from validation, not from looking at training error. A candidate who says "I set alpha to 0.01 because that usually works" has missed that alpha lives on the error scale of the specific problem. Related variants exist — reduced-error pruning collapses nodes greedily while a held-out set's error does not worsen, and pessimistic pruning uses a statistical correction to the training error instead of a separate set — but cost-complexity pruning is the one attached to CART and the one worth being able to derive.

  • How do you pick a value for alpha in practice?
    Fit the full tree once, derive its pruning path, then cross-validate the subtree corresponding to each alpha on the path and keep the alpha with the best mean held-out score, refitting on all the data at that value. Because alpha is measured in the same units as the training error, a value tuned on one dataset carries no meaning on another.
  • Why is the sequence of pruned subtrees nested?
    Each step collapses one weakest-link subtree into a leaf, so the result is by construction a subtree of the previous tree. Breiman's result is that for every alpha the smallest minimising subtree is unique and already appears in this one chain, so the exponential space of subtrees never has to be searched — one pass gives the whole path.
  • What exactly is R(T) in the objective?
    The resubstitution cost on the training data: misclassification rate for a classification tree, possibly weighted by class or misclassification costs, and total squared error for a regression tree. It falls monotonically as leaves are added, which is precisely why a size penalty is required to make the comparison between subtrees meaningful.

saying these in an interview costs you the question

  • Says larger alpha grows a bigger tree
  • Thinks alpha penalises depth rather than leaf count
  • Picks alpha by looking at training error
  • Claims each alpha needs a separate search over subtrees
  • Reuses an alpha value across different datasets

context

resolving links…