Validity of pruning algorithm in regression trees

Question

I am reading the book "The elements of Statistical Learning"(pdf available online for free) and in particular I'm trying to better understand the validity of the algorithm presented in section 9.2.2, p.308.

Initially we construct the tree in such a way that the $L^2$-norm:

\begin{align} C(T) = \sum_{m=1}^{|T|}\sum_{x_i\in R_m}^{}(y_i-\bar{y}_m)^2 \end{align}

is minimized. Here $|T|$ is the number of terminal nodes, $\{R_m\}_m$ are the disjoint regions referring to the terminal nodes and $\bar{y}_m$ is the average value in region $R_m$.a

Then when we want to prune the initial tree $T_0$, we introduce a cost function depending on a tuning variable $a$, \begin{align} C_a(T) = C(T) + a|T| \end{align}

and we say that for a fixed $a$ we can show that there exists a unique tree $T_a$ minimizing $C_a(T)$. My questions are the following:

1) I don't understand why C_a(T) is defined in that way, i.e. why this addition a|T| is added to C(T) and not another function depending on $a$? 2) How does the cost C_a(T_a) relate to C(T_0)? 3) Why the choice of T_a is a good choice of subtree to consider?

Thanks in advance.

Answer 1

The cost function $$ C_\alpha(T) = \sum_{m=1}^{|T|}\sum_{x_i\in R_m}^{}(y_i-\bar{y}_m)^2 + \alpha |T| $$ balances the training error of a tree $T$ (first term) and its number of terminal nodes (second term). Notice that we're considering only the cost of trees $T$ that can be obtained by pruning the original (unpruned) tree $T_0$ (including $T_0$ itself, of course). Pruning is done because trees that are grown too high suffer from overfitting, meaning (informally) that a small change in the training data would produce a very different regression tree. The bias-variance trade-off tells us that, in general, overfitting gets in the way of good generalization (compare the public and private leaderboards at Kaggle competitions to have a live picture of this phenomenon). When $\alpha=0$, the subtree that minimizes the cost is $T_0$ itself (formally, $T_0=\arg \min_T C_0(T)$), otherwise the tree growing algorithm would not have produced $T_0$ as the solution in the first place. When you raise the value of $\alpha$, you're giving a chance for subtrees of smaller size, that have a larger training error, to be chosen, and this process may produce a tree that generalizes better (has a smaller test error). In practice, the value of $\alpha$ is chosen by some form of cross-validation. The more general idea behind this is that Machine Learning methods "like to overfit", and some sort of "regularization" is needed to stop this from happening. The regularizer in Bayesian Machine Learning methods is the prior distribution, which is kind of ironic, because for a very long time it was thought (not by everyone, of course) that we should always rely on diffuse priors and let the data speak for themselves (through the likelihood function). Well, if you're only interested in prediction performance, it seems that we shouldn't just let the data "sing" for themselves, because, like a group of sirens, the data will try to drive the learning method/model to the rocks of overfitting (students know this phenomenon very well: in general, memorization is "easier" than true learning, but not as useful when trying to extend what you already know to a larger domain). Finally, when we grow a forest of trees, we don't care about overfitting of each one of the trees (so we grow each of them high and don't prune), because mechanisms like bootstrap aggregation and random subspaces can take care of the variance of the whole ensemble. Random Forests do exactly this, with great success (thanks to Leo Breiman and Adele Cutler).

Answer 2

If you do not add the $a|T|$ penalty term in your loss function, it will try to fit the training set as best as possible. This will render the model with only few options to "generalize" to perturbed/other data sets. Thus low insample bias will lead to higher test-set variance.

Remember, what you are really trying to do is not to fit the full complexity of a training set but to identify its "regularities" which are common to all data sets that are derived from the same underlying data generating process.

For that to happen, the model needs to avoid fitting noise, which will happen for overly complex models. Instead, restricted models will try to mimic lower dimensional (smooth) topological sub-spaces.

More formally, your training bias/optimisim can be defined as

$$ opt=Err_{in}-Err_{train} $$ where $opt$ refers to the optimism in your training set. This is because $Err_{train}$ refers to your training error and $Err_{in}$ to your in-sample error, which arises from sampling from the same training distribution.

According to Tibshirani one can quite generally show that

$$ E[op]=\frac{2}{N}\sum_{i}^N Cov(\hat{y}_i,y_i) $$

Thus, the amount by which your training error underestimates the true error depends on how strongly $y_i$ affects its own predictions $\hat{y}_i$. The harder we fit the data, the greater the $Cov$ term wil be, thereby increasing optimism.

Thus, the covariance will increase the more sophisticated and flexible your model is. For instance, in a classical regression model of the form $Y=f(X)+\epsilon$, the Covariance has a clear dependency with respect to the number of covariates/regressors $d$, ie,

$$ \sum_i Cov(\hat{y}_i,y_i)=d \sigma^2_\epsilon $$

So your ultimate training cost function will look like

$$ E[Err_{in}=E[Err_{train}]+2\frac{d}{N}\sigma^2_\epsilon $$

Equally, in decision trees pruning will ensure to limit the possibilities to (over-) fit your training data, although there is no functional relationship known how the prune level affects the training bias. However, the bias will be monotonously related to the tree complexity $|T|$, thus

$$ E[Err_{in}]\equiv E[Err_{train}]+ h(|T|) $$

where $h$ is a monotonously increasing function. Thus, in the absence of further evidence, you assume linearity, i.e. $h(x)=a x$ (the constant term can be thrown away as it does not affect the optimization problem).