How to choose $\alpha$ in cost-complexity pruning?

Question

In the following lectures Tree Methods, they describe a tree algorithm for cost complexity pruning on page 21. It says we apply cost complexity pruning to the large tree in order to obtain a sequence of best subtrees, as a function of $\alpha$. My initial thought was that we have a set of $\alpha$ (i.e. $\alpha \in [0.1, 0.2, 0.3])$. And then we compute the K-fold cross-validation for each set $\alpha$ and choose the $\alpha$ corresponding to the lowest K-fold cross validation.

For reference, the K-fold cross-validation that I am referring to is described on slide 15 in the following Cross-Validation.

However, after some thinking and reading; I found there is a theorem that the sequence of subtrees went through by weakest link pruning will contain the subtree $T_\alpha$. Where $T_\alpha$ is the subtree that minimizes the cost complexity criterion

$$ C_\alpha (T) = \sum_{m=1}^{|T|} \sum_{i: x_i \in R_m} (y_i - \hat y_{R_m})^2 + \alpha|T| $$ described on slide 19 in the Tree Methods slides.

Since this theorem exists I thought it might be plausible that you can deduce a neat mapping of each $\alpha \in \mathbb{R}$ to the optimal subtree $T_\alpha$. Or at least we can see that for a certain interval of $\alpha$s it will correspond to a specific subtree. I found this theorem on page 308 of the Elements of Statistical Learning book of print 4. It would be great if someone could clarify the algorithm and it would help to know if such a mapping exists.

Answer 1

Yes, such a mapping does exist, but it is less useful than expected.

The overall goal is to minimize the cost-complexity function $$ C_\alpha (T) = R(T)+ \alpha|T| $$

where $|T|$ is the number of leaves in tree $T$ and $R(T)$ a loss function calculated across these leaves.

First step is to calculate a sequence of subtrees $T^0\supseteq T^{1}...\supseteq T^{n-1}\supseteq T^{n}$ where $T_n$ is the tree consisting only of the root node and $T_0$ the whole tree.

This is done by successively replacing a subtree $T_t$ with root node $t$ with a leaf (i.e. collapsing this subtree). In each step the subtree $T_t$ is selected, which minimizes the decrease in the cost-complexity function and hence is the weakest link of the tree.

As formula: Minimize $$ C_\alpha(T-T_t) - C_\alpha(T)\\ =R(T-T_t)+ \alpha|T-T_t| - (R(T)+ \alpha|T|)\\ =R(T-T_t)-R(T)+\alpha(|T-T_t|-|T|)\\ =^1 R(T)-R(T_t)+R(t)-R(T) + \alpha(|T|-|T_t|+1-|T|)\\ =R(t)-R(T_t) + \alpha(1-|T_t|)\\ $$

This is 0 exactly when

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

So minimizing $C_\alpha(T-T_t) - C_\alpha(T)$ means minimizing $\alpha=\frac{R(t)-R(T_t)}{|T_t|-1}$

So starting with the whole tree $T^0$ (and $\alpha^0=0$) in each step s the algorithm

• selects the node t which minimizes $\frac{R(t)-R(T^{s-1}_t)}{|T^{s-1}_t|-1}$
• set $T^s=T^{s-1}-T_t$, $\alpha^s=\frac{R(t)-R(T^{s-1}_t)}{|T^{s-1}_t|-1}$

until the tree consists only of the root node.

Hence as output we get a sequence of subtrees

$T^0\supseteq T^{1}...\supseteq T^{n-1}\supseteq T^{n}$

alongside with the corresponding $\alpha$-values

$0=\alpha^0\leq\alpha^1\leq...\alpha^{n-1}\leq\alpha^{n}$

Using these values one can define a mapping from $\alpha$ to a list of subtrees.

BUT

The cost-complexity function and so the loss / error function have been calculated on the training data, hence the danger of self-validation and overfitting is present. Because of this the final $\alpha$ is determined by crossvalidation.$^2$

Calculating the sequence of subtrees of the tree trained on all the training-data (before optimization via inner crossvalidation) at least gives us an interval of possible $\alpha$-values to select from.

Sources:

• cost-complexity pruning explained by Alexey Grigorev
• Cost-complexity pruning of random forests by Kiran Bangalore Ravi, Jean Serra
• The Elements of Statistical Learning by Friedman et. al

The original source all the sources above are referring to is Breiman, L., Friedman, J., Olshen, R. and Stone, C. (1984). Classification and Regression Trees, Wadsworth, New York. Unfortunately I was not able to get my hands on it.

---

Appendix

(1) Why is this true ?

$$ =R(T-T_t)-R(T)+\alpha(|T-T_t|-|T|)\\ =R(T)-R(T_t)+R(t)-R(T) + \alpha(|T|-|T_t|+1-|T|)\\ $$

It is easier to understand with an image

Let's look at $R(T-T_t)=R(T)-R(T_t)+R(t)$

The error / loss function $R$ is calculated across all leaves of the input tree. The transformation $T-T_t$ collapses the subtree $T_t$ into into one leaf $t$. So $R(T-T_t)$ is

• $R(T)$ (across all leaves)
• - $R(T_t)$ (across the leaves of the "removed" subtree $T_t$)
• + $R(t)$ (across the freshly added leaf $t$ the subtree $T_t$ has been collapsed to)

Same logic applies to part calculating the number of leaves.

---

(2) How to determine $\alpha$ by crossvalidation ?

I am not sure if this is canon, but this how I would do it.

Input: Training data provided by the outer surrounding crossvalidation

1. Train tree on entire training data
2. Calculate sequence of subtrees $S$ and $\alpha$s $A$ to test.
3. Apply inner crossvalidation. For every run: Train tree on training data provided by inner crossvalidation
   1. Calculate sequence of subtrees
   2. For each $\alpha$ in $A$, keep subtree which minimizes $C_\alpha(T)$
   3. Evaluate these test-trees on test-set
4. Select $\alpha$ with best performance based on inner crossvalidation
5. Find subtree in the sequence $S$ built based on entire training data for that $\alpha$
6. Return that subtree

A similar approach is described in a lecture in Stanford University(starting at slide 10).

Answer 2

The tuning parameter alpha controls the tradeoff between the complexity of the tree and its accuracy/fit. 'alpha' being the penalty and 'T' the number of terminal nodes of the tree, as you increase alpha, branches get pruned in a predictable fashion ground up i.e there exists a different subtree that minimizes the cost complexity criterion for each value of the penalty.

As you mentioned, you can select an optimal value of alpha by using K-fold cross validation - build as large a tree as you can on each fold while aiming to minimize the cost complexity criterion for a different value of alpha. Averaging the results of all the trees and predicting on the kth fold would give you error rates for each alpha. Pick the penalty that minimizes the cross validation error.

Equation 9.16 in the 4th printing of ESL is simply a different representation of the same (cost complexity) criterion.