Cost-Complexity Pruning and Subtree Oracles

From a Maximal Tree to a Pruning Sequence

A fitted tree can have many subtrees, but cost-complexity pruning organizes them into a sequence indexed by a penalty on the number of leaves. The sequence is useful for two related reasons: it gives a systematic set of simpler alternatives to a large tree, and it provides a finite collection of candidates that can be compared by a separate risk criterion.

Begin with a fixed maximal tree $T_0$, constructed from training data. A pruning of $T_0$ is obtained by replacing one or more internal nodes by terminal leaves. For any node $t$, let $T_t$ denote the subtree rooted at $t$. Let $R_n(T)$ be the empirical loss of the fitted tree $T$, and let $R_n(t)$ be the empirical loss if all observations reaching node $t$ are instead predicted by the best single-leaf prediction for that node. Assume the empirical loss is additive across leaves, as it is for the usual sum or average of leafwise losses.

Definition: For a penalty $\alpha\geq 0$, the cost-complexity objective of a subtree $T$ is $$ C_\alpha(T)=R_n(T)+\alpha |T|, $$ where $|T|$ is the number of terminal leaves. The weakest-link value at an internal node $t$ of the current tree is $$ g_T(t)=\frac{R_n(t)-R_n(T_t)}{|T_t|-1}. $$ The numerator is the empirical-risk increase from collapsing $T_t$ to one leaf; the denominator is the number of leaves removed.

For a loss minimized by fitting the best available prediction at each leaf, $R_n(t)\geq R_n(T_t)$. Thus the weakest-link value is nonnegative. If $T_t$ has $m$ leaves, collapsing it changes the objective by

C_\alpha(T\setminus T_t)-C_\alpha(T) =R_n(t)-R_n(T_t)-\alpha(m-1) =(m-1)\{g_T(t)-\alpha\}.

This identity gives the breakpoint directly. When $\alpha<g_T(t)$, this particular collapse increases the objective; when $\alpha>g_T(t)$, it decreases the objective. At equality, the two choices have the same objective. Because a collapse changes the current tree, the weakest-link values must be recalculated after pruning.

Worked Example: Calculating the First Weakest Link

Suppose a current tree has four leaves. Its empirical risk is $0.50$. One internal node $A$ has a two-leaf subtree with risk $0.20$, and collapsing $A$ gives risk $0.34$. Another internal node $B$ has a two-leaf subtree with risk $0.30$, and collapsing $B$ gives risk $0.50$. Collapsing the root gives risk $0.95$.

For $A$, the risk increase is $0.34-0.20=0.14$, and one leaf is removed. Hence $g_T(A)=0.14/1=0.14$. For $B$, the increase is $0.50-0.30=0.20$, so $g_T(B)=0.20$. The root collapse removes three leaves and increases risk by $0.95-0.50=0.45$, giving $g_T(\text{root})=0.45/3=0.15$.

The smallest value is $0.14$, so $A$ is the first weakest link. After collapsing $A$, the risk is $0.50+0.14=0.64$, and the tree has three leaves. The updated root value is $(0.95-0.64)/(3-1)=0.155$. Node $B$ still has value $0.20$, so the root is now the weakest link. The resulting sequence is the original four-leaf tree, the tree with $A$ collapsed, and the root-only tree.

Why the Sequence Is Nested

The weakest-link procedure starts at $T_0$, finds the internal node or nodes with the smallest current $g_T(t)$, collapses them, and repeats on the smaller tree. Ties require a convention: simultaneous tied collapses can be made together, with a tied ancestor taking precedence over a descendant because collapsing the ancestor already removes that descendant. This produces a nested sequence

T_0\supset T_1\supset\cdots\supset T_J,

where $T_J$ is the root-only tree. “Nested” means that every later tree is a pruning of every earlier one. The sequence is not necessarily the list of every possible pruning: a pruning can be skipped because it is never optimal for any value of $\alpha$.

Theorem: For a fixed finite maximal tree and additive leafwise empirical risk, weakest-link pruning produces a nested sequence of subtrees that minimize $C_\alpha(T)$ over prunings of the maximal tree as $\alpha$ increases, with a consistent tie convention. The transition from a current subtree occurs at its smallest weakest-link value; after that collapse, the values are recomputed on the smaller tree.

Here is the key comparison behind the result. Consider any pruning of the current tree. The pruned portions can be represented by roots of disjoint subtrees: no selected root is a descendant of another selected root. The change in cost-complexity objective is the sum of the changes for these separate collapses. For a collapse rooted at $t$, that change is $(|T_t|-1)\{g_T(t)-\alpha\}$. Therefore, if $\alpha$ is no greater than the smallest current weakest-link value, every such term is nonnegative, and no combination of collapses improves on the current tree.

As $\alpha$ passes the smallest value, the corresponding collapse is the first one whose objective change becomes negative. Among disjoint collapses, objective changes add; when collapses are nested, the ancestor collapse is evaluated as one candidate on the current tree, and the descendant is reconsidered only if the ancestor remains. Thus the first breakpoint is determined by the current minimum. Applying the same argument to the resulting smaller tree gives the next breakpoint and, by repetition, the full nested sequence. At a breakpoint, adjacent candidates tie; the stated convention chooses one nested representative of the minimizers. $\square$

Worked Example: Reading the Breakpoints

Suppose three successive prunings have risks and leaf counts $R_n(T_0)=0.12$, $|T_0|=3$; $R_n(T_1)=0.18$, $|T_1|=2$; and $R_n(T_2)=0.31$, $|T_2|=1$. The crossing between $T_0$ and $T_1$ is $(0.18-0.12)/(3-2)=0.06$. The crossing between $T_1$ and $T_2$ is $(0.31-0.18)/(2-1)=0.13$.

At $\alpha=0.04$, the three objectives are $0.12+3(0.04)=0.24$, $0.18+2(0.04)=0.26$, and $0.31+0.04=0.35$; $T_0$ minimizes the objective. At $\alpha=0.10$, they are $0.42$, $0.38$, and $0.41$; $T_1$ minimizes it. At $\alpha=0.15$, they are $0.57$, $0.48$, and $0.46$; $T_2$ minimizes it. The increasing penalty moves the optimum toward smaller subtrees.

A Finite-Sample Oracle Comparison

The cost-complexity sequence is constructed from training data. To compare its candidates with a finite-sample guarantee, suppose a separate validation sample is independent of the data used to construct the sequence. Conditional on the training data, the candidate trees are then fixed. Assume validation losses lie in $[0,1]$, and let $R_j$ be the conditional expected loss and $\widehat R_j$ the average validation loss for $T_j$.

For each candidate choose a positive number $A_j$, and define $\epsilon_j=\sqrt{A_j/n}$, where $n$ is the validation sample size. Hoeffding’s inequality gives $P(|\widehat R_j-R_j|>\epsilon_j\mid\mathcal D_{\rm tr})\leq 2\exp(-2A_j)$. A union bound therefore gives simultaneous control over the whole sequence.

Theorem: Let $T_0,\ldots,T_J$ be fixed conditional on training data, and suppose the validation observations are independent and identically distributed, independent of the training data, with each candidate’s loss in $[0,1]$. Select $$ \widehat j\in\arg\min_{0\leq j\leq J}\{\widehat R_j+\epsilon_j\}. $$ With conditional probability at least $1-2\sum_{j=0}^J e^{-2A_j}$, $$ R_{\widehat j}\leq \min_{0\leq j\leq J}\{R_j+2\epsilon_j\}. $$

To prove the assertion, let $E$ be the event that $|\widehat R_j-R_j|\leq\epsilon_j$ for every $j$. The union bound and the preceding Hoeffding inequality give $P(E\mid\mathcal D_{\rm tr})\geq1-2\sum_j e^{-2A_j}$. On $E$,

R_{\widehat j} \leq \widehat R_{\widehat j}+\epsilon_{\widehat j} \leq \widehat R_j+\epsilon_j \leq R_j+2\epsilon_j

for every $j$. The middle inequality follows from the definition of $\widehat j$, and the other two follow from the simultaneous deviation bounds. Taking the minimum over $j$ proves the result. $\square$

This is an oracle comparison because its right side uses the best true risk among the sequence, which need not be known when selecting a tree. The penalty is candidate-specific: a less stable or more complex candidate can be assigned a larger deviation allowance. The guarantee compares only with the subtrees in the sequence, not with every tree or every predictor.

Worked Example: Computing the Validation Oracle Bounds

Suppose $n=1000$, and three candidates have conditional risks $0.23$, $0.21$, and $0.19$. Use $A_1=\log(40)$, $A_2=4.20$, and $A_3=\log(100)$. Their oracle upper bounds $R_j+2\sqrt{A_j/n}$ are calculated from the unrounded penalties.

For the first candidate, $2\sqrt{\log(40)/1000}\approx0.121472$, so its bound is $0.23+2\sqrt{\log(40)/1000}\approx0.351472$, or approximately $0.3515$. For the second, $2\sqrt{4.20/1000}=0.129615$, so its bound is $0.21+0.129615=0.339615$, or approximately $0.3396$. For the third, $2\sqrt{\log(100)/1000}\approx0.135723$, so its bound is $0.19+2\sqrt{\log(100)/1000}\approx0.325723$, or approximately $0.3257$.

The third candidate has the smallest displayed upper bound, despite having the largest deviation allowance, because its conditional risk is sufficiently lower. The theorem says that the risk of the selected candidate is bounded by the smallest of these candidate-specific bounds on the simultaneous-concentration event.

Scope and Common Pitfall

The pruning penalty $\alpha |T|$ and the validation allowance $\epsilon_j$ play different roles. The first defines the cost-complexity path within the fixed maximal tree. The second controls uncertainty when comparing candidates on validation data. A validation penalty that is constant across candidates does not affect which candidate minimizes the penalized validation criterion; the candidate-specific allowances above can affect that choice.

Using training data twice without control. If the same data both determine the tree sequence and evaluate its candidates, the candidates are data-dependent relative to the empirical risks. The finite-candidate Hoeffding argument above does not apply just by counting the subtrees in the realized sequence. Use independent validation data or a suitable uniform bound for the full data-dependent class.
Ignoring the loss assumption. The stated validation theorem requires losses bounded in $[0,1]$. For a different loss, its concentration inequality and corresponding penalty must be justified rather than assumed.
Assuming every pruning appears on the path. The weakest-link sequence contains the relevant cost-complexity minimizers, not necessarily every combinatorially possible subtree.

Cost-complexity pruning therefore supplies an ordered, interpretable set of size-controlled candidates. The finite-sample comparison then makes a distinct statement: under independent validation and bounded loss, a penalized selection from that finite sequence performs, up to its deviation allowance, as well as the best candidate in the sequence.

Check Your Understanding

Use the definitions and results above to answer these questions.

If collapsing a subtree increases empirical risk by $0.18$ and removes three leaves, what is its weakest-link value?
Why must weakest-link values be recalculated after a pruning step?
For the validation theorem, which data must be independent, and why is conditioning on the training data useful?
Explain why the oracle comparison is against the best subtree in the sequence rather than the best possible tree.
What fails in the stated finite-candidate argument if validation losses are unbounded?

Cost-Complexity Pruning and Subtree Oracles

What You'll Learn