Pruning Trees by Penalized Empirical Risk

Why Penalize the Number of Leaves?

A grown tree can fit the training observations closely by creating many small terminal regions. But a small training error alone does not account for the complexity of the fitted partition. Pruning offers a controlled comparison: start with a fixed grown tree, consider trees formed by collapsing some of its branches, and balance each candidate’s empirical risk against its number of leaves.

The penalty is a selection criterion, not a claim that pruning must reduce training error. A collapse generally makes the fitted tree less flexible, so its empirical risk can rise. Pruning is preferred when that rise is smaller than the reduction in the complexity penalty.

Definition: Let $T_0$ be a fixed grown tree, and let $\mathcal{S}(T_0)$ be the set of trees obtained by pruning it: each candidate is formed by collapsing zero or more internal nodes, without adding splits. Write $|T|$ for the number of terminal leaves of $T$, and $\hat f_T$ for its fitted prediction rule. For observations $(X_i,Y_i)$, $i=1,\ldots,n$, and a loss function $L$, define $$ \widehat R_n(T)=\frac{1}{n}\sum_{i=1}^n L\bigl(Y_i,\hat f_T(X_i)\bigr). $$ For a penalty parameter $\lambda\geq 0$, the penalized empirical-risk criterion is $$ C_\lambda(T)=\widehat R_n(T)+\lambda |T|,\qquad T\in\mathcal{S}(T_0). $$ A subtree is preferred to another candidate when it has a smaller value of $C_\lambda$; ties may be resolved by a stated rule.

The leaf predictions are fitted to the training observations in their respective regions. For squared-error regression, a nonempty leaf is assigned its sample mean. For classification with zero-one loss, it is assigned a most frequent class, with a fixed rule for ties. We assume throughout that candidate leaves contain observations, so their fitted predictions are defined. The empirical risk is averaged over all $n$ observations, not just those in a particular leaf.

The factor $\lambda$ sets the trade-off. Because $\widehat R_n$ is an average loss, $\lambda$ is measured in the same units as that loss. If instead risk were recorded as a sum, the corresponding penalty would need to be scaled consistently.

What Fitting and Pruning Change

A useful starting fact is that refining a partition cannot worsen its best training fit, provided the refined model can reproduce the coarser model. This compares empirical risks only; the penalty may move in the opposite direction.

Proposition: Suppose $T_1$ refines $T_2$, meaning that every leaf of $T_1$ lies within a leaf of $T_2$. Assume the prediction class available in each refined leaf can represent the prediction used on its containing coarse leaf. If leaf predictions are chosen to minimize the summed training loss within their leaves, then $$ \widehat R_n(T_1)\leq \widehat R_n(T_2). $$

Proof. Take the fitted predictions of $T_2$. Construct a candidate fit on $T_1$ by assigning each refined leaf the prediction of the $T_2$ leaf that contains it. Every training observation then receives exactly the same prediction under this candidate fit as under $T_2$, so its total loss is unchanged. By assumption, the fitted predictions for $T_1$ minimize training loss over the predictions available on that tree. Their total loss therefore cannot exceed the loss of this particular candidate fit. Dividing both totals by $n$ proves the inequality. $\square$

In particular, retaining an extra split cannot increase the minimum empirical risk under these conditions. It does increase the leaf penalty by $\lambda$ when it adds one leaf. The net choice depends on the size of the risk reduction.

A One-Branch Pruning Comparison

Suppose a candidate tree $T_{\mathrm{keep}}$ retains a split, while $T_{\mathrm{prune}}$ collapses that split and is otherwise unchanged. If the collapse removes exactly one leaf, then $|T_{\mathrm{prune}}|=|T_{\mathrm{keep}}|-1$. Subtracting their criteria gives

C_\lambda(T_{\mathrm{prune}})-C_\lambda(T_{\mathrm{keep}}) = \widehat R_n(T_{\mathrm{prune}})-\widehat R_n(T_{\mathrm{keep}})-\lambda.

Thus pruning is preferred precisely when its increase in empirical risk is less than $\lambda$. At equality, the two candidates tie. This comparison applies when only that split is changed; it does not, by itself, establish which tree is best among all possible prunings.

Worked Example: A Regression Branch and Its Pruning Threshold

Consider a tree with eight observations. One internal node divides four observations into two leaves with responses $0,2$ and $4,6$. The other branch contains four further observations and is left unchanged. Use squared-error loss and leafwise sample means. Compare retaining the first split with collapsing it.

Retain the split. The two leaf means are $1$ and $5$. The squared-error sums are $$ (0-1)^2+(2-1)^2=2,\qquad (4-5)^2+(6-5)^2=2. $$ The affected observations contribute $4/8=0.5$ to the full-sample empirical risk.

Collapse the split. The merged leaf mean is $(0+2+4+6)/4=3$. Its squared-error sum is $$ (0-3)^2+(2-3)^2+(4-3)^2+(6-3)^2=9+1+1+9=20. $$ The affected observations now contribute $20/8=2.5$ to the full-sample risk. The risk increase is $2.5-0.5=2$, and the number of leaves falls by one.

The change in penalized criterion is therefore $2-\lambda$. For $\lambda<2$, retaining the split has the smaller criterion; for $\lambda>2$, collapsing it does. At $\lambda=2$, they tie. The risk contributions from the unchanged branch are identical in the two candidates and cancel from the comparison.

Why the Regression Risk Increase Has This Form

For a direct merge of child leaves, the risk increase can be expressed using the child sample means. This gives a precise account of what is lost by replacing several fitted constants with one.

Result: Suppose a node has $J$ child leaves, with $n_j>0$ observations and response mean $\bar Y_j$ in child $j$. Let $N=\sum_{j=1}^J n_j$, and let $\bar Y=\sum_{j=1}^J n_j\bar Y_j/N$ be the mean after merging all those observations. Under squared-error loss and leafwise sample-mean fitting, the increase in the summed squared error caused by the merge is $$ \sum_{j=1}^J n_j(\bar Y_j-\bar Y)^2. $$ The corresponding increase in full-sample empirical risk is this quantity divided by $n$.

Derivation. Write the responses in child $j$ as $Y_{ij}$, $i=1,\ldots,n_j$. For each child, $\sum_i(Y_{ij}-\bar Y_j)=0$. Expanding each squared deviation from the merged mean gives

\begin{aligned} \sum_{i=1}^{n_j}(Y_{ij}-\bar Y)^2 &=\sum_{i=1}^{n_j}\bigl[(Y_{ij}-\bar Y_j)+(\bar Y_j-\bar Y)\bigr]^2\\ &=\sum_{i=1}^{n_j}(Y_{ij}-\bar Y_j)^2 +n_j(\bar Y_j-\bar Y)^2\\ &\quad+2(\bar Y_j-\bar Y)\sum_{i=1}^{n_j}(Y_{ij}-\bar Y_j)\\ &=\sum_{i=1}^{n_j}(Y_{ij}-\bar Y_j)^2+n_j(\bar Y_j-\bar Y)^2. \end{aligned}

Summing over $j$, the first terms are exactly the summed squared error before merging. Subtracting them leaves $\sum_j n_j(\bar Y_j-\bar Y)^2$. Dividing by $n$ converts the increase in summed loss to the increase in $\widehat R_n$. $\square$

The result concerns a direct merge of leaves whose fitted predictions are their sample means. If a collapsed node contains deeper subtrees, the same idea can compare the merged mean with all of their observations, but it must account for the entire risk of those descendant leaves—not just the immediate child means.

Worked Classification Comparison

Worked Example: Collapsing a Two-Leaf Classifier

Suppose an internal node has two child leaves. The first contains four positive and one negative observation; the second contains one positive and four negative observations. Fit each leaf by its majority class and use zero-one loss. There are ten observations in the full sample, and other parts of the tree, if any, are unchanged.

With the split retained, each leaf misclassifies one observation, for two errors total. Its contribution to full-sample empirical risk is $2/10=0.2$.

After the merge, the node contains five observations of each class. Either class prediction makes five errors, so the merged leaf contributes $5/10=0.5$ to the full-sample risk. The risk increase is $0.5-0.2=0.3$, while the leaf count decreases by one.

The change in penalized criterion is $0.3-\lambda$. Pruning is preferred when $\lambda>0.3$, retaining the split is preferred when $\lambda<0.3$, and the candidates tie when $\lambda=0.3$. This calculation illustrates that the same penalty logic applies with a different empirical loss; the risk increase must be computed for the loss and leaf prediction rule actually used.

Penalized Risk Can Favor a Large Pruning Step

It is tempting to imagine that increasing $\lambda$ will always select a tree obtained by one small, locally favorable collapse at a time. A comparison among all candidate prunings need not behave that way. The criterion adds up total risk and total leaf count, so a larger collapse can win even when an intermediate candidate is not preferred.

Worked Example: Comparing All Prunings of a Small Regression Tree

Consider a four-leaf tree with eight responses. Its left branch has leaves $\{0,2\}$ and $\{4,6\}$; its right branch has leaves $\{2,4\}$ and $\{6,8\}$. Fit each leaf by its mean and use average squared error.

In every two-observation leaf, the responses differ by $2$, so the mean is their midpoint and the squared-error sum is $1^2+1^2=2$. Across four leaves the sum is $8$, giving risk $8/8=1$ with four leaves.

Merging either pair of leaves under one branch combines responses $\{0,2,4,6\}$ or $\{2,4,6,8\}$. Each group has mean $3$ or $5$, respectively, and squared-error sum $20$. Replacing the two original leaf sums $2+2=4$ by $20$ increases the full-sample risk by $16/8=2$. Thus either three-leaf pruning has risk $3$. Merging both branches gives risk $1+2+2=5$ with two leaves.

Finally, the root-only fit has mean $4$. Its squared-error sum is $$ (0-4)^2+(2-4)^2+(4-4)^2+(6-4)^2 +(2-4)^2+(4-4)^2+(6-4)^2+(8-4)^2=48, $$ so its average risk is $48/8=6$. The candidate risks and penalized criteria are:

Leaves	Empirical risk	Penalized criterion
4	1	$1+4\lambda$
3	3	$3+3\lambda$
2	5	$5+2\lambda$
1	6	$6+\lambda$

For $\lambda=1.8$, these values are $8.2$, $8.4$, $8.6$, and $7.8$, respectively. The root-only tree has the smallest criterion, even though the intermediate three- and two-leaf candidates do not. This is why choosing among candidate prunings requires comparing their full penalized criteria, not merely applying a local rule and assuming each next collapse is preferred.

Common Pitfalls and Practical Meaning

Assuming pruning lowers training risk. A collapse restricts the set of fits, so the optimized empirical risk can rise. What pruning may lower is the combined criterion, through the reduction in leaf penalty.
Using the wrong risk scale. The examples use average loss over all $n$ observations. A local error count must be divided by $n$ before comparing it with $\lambda$ in that criterion.
Counting removed splits instead of removed leaves. The specified penalty is proportional to $|T|$, the number of terminal leaves. For a binary split that is collapsed while everything else is fixed, the leaf count falls by one; other tree operations need not have that change.
Confusing a local comparison with a global choice. A risk increase smaller than $\lambda$ supports that particular collapse against its corresponding retained tree. It does not prove that the result is best among every subtree of $T_0$.

Penalized empirical risk makes the complexity preference explicit: each additional leaf must earn its place by reducing training loss enough to offset its penalty. This offers a transparent way to compare prunings of a fixed grown tree. It does not, by itself, guarantee low prediction error on new observations; the criterion is computed from the training sample, and its practical value depends on choosing a penalty appropriate to the problem and loss scale.

Check Your Understanding

Use the definitions and comparisons above to test your understanding.

For a candidate tree with empirical risk $0.12$ and six leaves, what is its penalized criterion when $\lambda=0.01$?
A collapse removes one leaf and raises average empirical risk by $0.04$. For which values of $\lambda$ is the collapsed tree preferred?
Why can a refined tree have no greater optimized training risk, yet have a worse penalized criterion?
In a squared-error merge, what information about child leaves determines the increase in summed loss?
Why is it not valid to infer that a globally preferred pruning must be reached through a sequence of individually preferred one-leaf collapses?

Leaves	Empirical risk	Penalized criterion
4	1	\(1+4\lambda\)
3	3	\(3+3\lambda\)
2	5	\(5+2\lambda\)
1	6	\(6+\lambda\)