# CART algorithm (Classification and regression trees) question

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