1. We fit a full classification tree model $T_k$ of given depth $k$ to data using the CART algorithm, and prune the tree by finding $E(k, \alpha) = min_{T\subset Tk} Err(T) + \alpha |T|$. Here, $Err(T)$ is the training error of a tree $T$ on the training data, $|T|$ is the number of leaves in $T$ and $\alpha$ is a given parameter. Which of the following is sometimes false?

$\color{blue}{(a) E(k+ 1,0) \geq E (k,0)}$

(b) $E(k+ 1,0) \leq E(k,0)$

(c) $E(k+ \alpha+1) \geq E(k,\alpha)$

(d) All three statements above are always true

$\color{blue}{Explanation:}$ By supplying the depths $k$ and $k + 1$, the Cart algorithm will return us with a tree of depth $k, T,$ and a tree of depth $k + 1, \widetilde {T}$. It is important to note that $T$ and $\widetilde {T}$ share the same first $k - 1 $ levels.

Now the pruning starts, any possible pruning of $T$ can be achieved by pruning $\widetilde {T}$, but not vise versa. Therefore $E(k, \alpha) \geq E(k + 1, \alpha)$ for any $\alpha \in R_+.$$ See Lecture 7.

So this is taken from an exam I just did. I'd like to know if there are any instances same as in the image where the CART algorithm could use a negative alpha and thus encourage a larger tree? Or does the algorithm state that alpha must be a non negative integer at all times?


Making an additional split will always decrease $Err$ (until pure leaves are reached), so any negative $\alpha$ will have the same minimizing $T$ as $\alpha=0$. So we might as well take $\alpha\geq0$. (But there is no requirement that $\alpha$ be an integer.)

Erm, unless you implement things so that even a pure node can be split, in which case a negative $\alpha$ will make the tree split even these, until every leaf consists of a single sample (and duplicates thereof) or the maximum depth is reached.


Or does the algorithm state that alpha must be a non negative integer at all times?

As far as I know that is actually the case:

In "The Elements of Statistical Learning" (1) on page 308 the authors write:

The tuning parameter $\alpha \geq 0$ governs the tradeoff between tree size and its goodness of fit to the data.

Also, the scikit-learn documentation says:

Minimal cost-complexity pruning is an algorithm used to prune a tree to avoid over-fitting, described in Chapter 3 of [BRE]. This algorithm is parameterized by $\alpha \geq 0$ known as the complexity parameter.

Both sources refer to "Classification and Regression Trees" (2) as the original source.

(1) "The Elements of Statistical Learning"; Hastie et al; 2nd Ed; 2008

(2) "Classification and Regression Trees"; Breiman, et al; 1984


𝛼 is a parameter used for regularization which is controlling the tree from being overfit , an inherent issue with CART algorithms. A negative 𝛼 would lead to a larger tree which may accentuate the overfitting issue


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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