Regression Trees and Pruning

Definition A regression tree predicts a numerical target $y$ from a feature vector $\mathbf{x}$. Like a classification tree, it is a rooted binary tree whose internal nodes hold tests such as $x_j \le t$, which send an input to the left child when the test holds and to the right child otherwise, and whose leaves define disjoint regions $R_1, \dots, R_M$ that together cover feature space. Leaf $m$ holds a constant $c_m$, and the prediction is

When the tree is fitted with squared error, each constant $c_m$ is the mean of the training targets in $R_m$. With one numerical feature the fitted function is a step function, constant on intervals and jumping only at the thresholds. Every prediction is an average of training targets, so it lies between the smallest and the largest training target. An input beyond the range of the training inputs simply receives the constant of the leaf it falls into, so a regression tree never continues a trend beyond the data.

Definition Let a leaf hold $m \ge 1$ training targets $y_1, \dots, y_m$ with mean $\bar{y}$. For every constant $c$,

because the cross term $2(\bar{y} - c)\sum_{i} (y_i - \bar{y})$ is zero. The last term is positive unless $c = \bar{y}$, so the leaf mean is the unique constant with the smallest sum of squared errors in the leaf, and that smallest sum, $\sum_{i} (y_i - \bar{y})^2$, is the leaf’s sum of squared errors, or SSE. An empty leaf has no mean, which is one reason a split must leave both children nonempty. The mean is the answer for squared error in particular. Under absolute error any median of the leaf’s targets is a best constant, and with row weights the best constant under squared error is the weighted mean.

Definition Let a node hold a set $S$ of $n \ge 2$ training rows with target mean $\bar{y}_S$, and write $\operatorname{SSE}(S) = \sum_{i \in S} (y_i - \bar{y}_S)^2$. A candidate split $x_j \le t$ divides $S$ into a left part $L$ and a right part $R$, both nonempty, with $n_L$ and $n_R$ rows and means $\bar{y}_L$ and $\bar{y}_R$. The squared-error split criterion chooses, among the valid candidates, the one with the smallest total $\operatorname{SSE}(L) + \operatorname{SSE}(R)$, each child measured around its own mean, with a fixed rule for ties. The reduction is

which is never negative and is zero exactly when the two child means are equal. Thresholds for a numerical feature are the midpoints between consecutive distinct sorted values of $x_j$ in the node, so rows with equal values of $x_j$ always go to the same child. Since the SSE of a child is its number of rows times the variance of its targets, computed with that number as divisor, the criterion is the same as minimizing the size-weighted average of the children’s variances, which some software calls the mean squared error criterion.

Definition The depth of a node is the number of splits on the path from the root to it, so the root has depth $0$, and the depth of a tree is the largest depth of its leaves. A tree of depth $d$ has at most $2^d$ leaves. A maximum depth $d_{\max}$ stops growth at that depth. A minimum leaf size $m_{\min} \ge 1$ makes a split valid only when each child receives at least $m_{\min}$ training rows. A smaller maximum depth or a larger minimum leaf size gives a less flexible tree. With no depth limit and $m_{\min} = 1$, splitting can continue until every leaf has constant targets or holds a single distinct input. If no two training rows share an input with different targets, every leaf then has constant targets and the training SSE is $0$. Both settings are hyperparameters, chosen with validation data or with cross-validation inside the training data and never with the test set.

Definition Grow a large tree $T_0$ on the training data. A pruned subtree $T$ of $T_0$ comes from collapsing some internal nodes, each together with everything below it, into leaves that predict the mean of their training rows. For a complexity parameter $\alpha \ge 0$, cost-complexity pruning scores $T$ by

where $\operatorname{SSE}(T)$ is the training SSE summed over the leaves and $\lvert T \rvert$ is the number of leaves. A leaf is worth adding only if it lowers the training SSE by more than $\alpha$. For every $\alpha$ there is a smallest subtree that minimizes $R_\alpha$, and as $\alpha$ grows these subtrees are nested, each contained in the ones for smaller values, reaching the root alone at the latest when $\alpha$ exceeds the SSE of the root. Weakest-link pruning finds them. For an internal node $t$ with branch $T_t$, let $\operatorname{SSE}(t)$ be the SSE of its rows around their mean, the value if $t$ were collapsed, and compute

Collapse every node with the smallest value of $g$, recompute and repeat. The successive smallest values are the values of $\alpha$ at which the best subtree changes. Pruning uses only training data to produce the candidates, and $\alpha$ is then chosen by validation error or by cross-validation inside the training data, never by the test set. On this page $\alpha$ is measured in squared target units per leaf. Software that measures training error as $\operatorname{SSE}/n$ reaches the same tree with $\alpha/n$ in place of $\alpha$.