14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This material from the class STAT 897D at Penn state should be relevant to this question: onlinecourses.science.psu.edu/stat857/node/60 $\endgroup$
    – Raphvanns
    Dec 17, 2018 at 18:43
  • $\begingroup$ I guess this scikit-learn tutorial does a nice job by showing the mapping between $\alpha$-values and the size of the resulting tree (even though it does not go as far as showing the optimal subtree according to each $\alpha$-value). $\endgroup$
    – Tanguy
    Apr 2, 2020 at 22:21

2 Answers 2

14
$\begingroup$

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:

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

exampletreetransformation

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).

$\endgroup$
4
  • $\begingroup$ Thank for making this very clear by adding visuals and end-notes. I still have another question though. I was reading sklearn's documentation on minimal cost complexity pruning and they refer to a vague "non-terminal node" (which I understand can be any node in the tree!). Similarly, your demonstration generalizes to any subtree. So my question is: is it actually possible to start pruning a tree at a high level (in other words, start pruning the tree at a higher level than the nodes "carrying" the leaves)? $\endgroup$
    – Tanguy
    Apr 2, 2020 at 21:30
  • $\begingroup$ Besides, can you define what is the external and internal crossvalidation? I have never encountered those concepts in crossvalidation yet. $\endgroup$
    – Tanguy
    Apr 7, 2020 at 11:15
  • 1
    $\begingroup$ 1. A non-terminal node is any node except a leaf node (see e.g. wikipedia) 2. Pruning can happen at any non-terminal node, so yes, it might be even the node right below the root node. 3. Internal / external is also called inner / outer (I will replace these) in so called nested cross-validation. The outer is the "normal" one for selecting the best model, the inner is for (hyper)parameter optimization of the corresponding learning algorithm. You will find more information searching for these terms. Thank you for pointing this out. $\endgroup$
    – steffen
    Apr 9, 2020 at 19:45
  • $\begingroup$ FYI, here is another cross validation strategy. I did not get the $T_{max}T^{(v)}T_{max}$ term though (maybe the author was actually refering to $T^{(v)}_{max}$ ?). Besides, there seems to an error in the sentence "we will find $\alpha_k$ from the list such that $\alpha_k <= \alpha_{k+1}$". I believe the author meant "such that $\alpha_k <= \alpha$". $\endgroup$
    – Tanguy
    Apr 11, 2020 at 14:50
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.