Regression Trees

A regression tree predicts a numerical response by asking a sequence of questions about the predictors. Each observation follows one path to a terminal region, or leaf, and receives the fitted value assigned to that region.

Interactions without a full expansion¶

In the model $f(x_1,x_2)=\beta_0+\beta_1x_1+\beta_2x_2+\beta_{12}x_1x_2$, increasing $x_1$ by one changes the fitted mean by $\beta_1+\beta_{12}x_2$. The effect depends on $x_2$, which is the meaning of an interaction.

With $p$ predictors, including one product for every subset gives $2^p$ terms including the intercept. There are $2^p−p−1$ interactions involving at least two distinct predictors. This count concerns products with each variable appearing at most once; allowing arbitrary powers creates a different expansion.

A tree can express conditional behavior by splitting on one predictor only after a condition on another has been met. It does not require us to enumerate every possible product in advance.

A partition model¶

Let $R_1,\ldots,R_M$ be disjoint regions covering the input space. Then

Exactly one indicator is one for each input, so the prediction is the constant of its leaf. A fixed collection of regions would give a linear basis model. An estimated tree is different because the regions themselves are chosen using the responses.

Why a leaf predicts its mean¶

For a fixed nonempty region $R$, minimize $\sum_{i:x_i\in R}(y_i−c)^2$. Its derivative is

giving $\widehat c=\bar y_R$. This is specific to squared error; other losses can imply different leaf predictions.

For an illustrative leaf with responses $2,3,7$, the prediction is 4 and the residual sum of squares is $4+1+9=14$. Splitting it into responses $(2,3)$ and $(7)$ gives means 2.5 and 7, with total residual sum of squares 0.5. The training improvement is 13.5, although prediction improvement still needs validation.

Choosing a split¶

Within a node $R$, a candidate feature $j$ and threshold $s$ produce

For a numerical feature, only boundaries between distinct sorted observed values need examination. Every threshold inside such a gap gives the same allocation of training observations. Enforce any minimum node size before comparing candidates.

Repeat this search inside the resulting nodes. This procedure is greedy: it chooses the best immediate split, not the globally best complete tree. Ties can occur, and small changes to the sample can change an early split and all branches below it.

Pruning¶

A large initial tree can fit noise. For a subtree $T$, let $|T|$ denote its number of leaves and define

The first term rewards fit; the second charges for leaves. In the lecture notation, $N_mQ_m(T)$ is the residual sum of squares in leaf $m$, so summing it over leaves gives the same RSS.

Pruning replaces a branch by a single leaf. Its RSS increases, but its complexity charge decreases. In the numerical example above, replacing one leaf by two reduces RSS by 13.5 and adds one leaf. This local comparison favors keeping the split when $\alpha<13.5$, with a tie at 13.5.

In a complete tree, compare candidate subtrees along a pruning sequence. Select complexity using validation predictions, then assess the selected procedure separately. The smallest training RSS always favors a sufficiently large tree and is not a tuning criterion by itself.

The classification tree notes use the same partition idea with a categorical response. The response type changes the loss, splitting criterion, and leaf prediction.