Worked Regression Tree Risk Calculation

What a Regression Tree Risk Calculation Separates

A regression tree replaces a response surface by constants on cells of the predictor space. For a small data set, it is possible to calculate exactly what each candidate tree fits, how much squared error remains in the observed data, and how a complexity penalty changes the choice. These quantities answer different questions: training error describes fit to the observed responses, while cell approximation error describes how well a partition can represent a specified regression function.

We will use one data set throughout the empirical calculations, and separately specify a predictor distribution and regression function for the population approximation calculation. Keeping these calculations distinct is essential: a low empirical error does not, by itself, establish a low population approximation error.

Definition: Let a tree partition the predictor space into $K$ nonempty cells $A_1,\ldots,A_K$. For observations $(x_i,y_i)$, $i=1,\ldots,n$, the fitted value in cell $A_j$ is the mean response of observations in that cell: $$ \hat c_j=\frac{1}{n_j}\sum_{i:x_i\in A_j}y_i,\qquad n_j=\sum_{i=1}^n \mathbf{1}\{x_i\in A_j\}>0. $$ The tree's empirical squared-error risk is $$ \hat R(\mathcal P)=\frac{1}{n}\sum_{j=1}^K\sum_{i:x_i\in A_j}(y_i-\hat c_j)^2. $$

The factor $1/n$ makes this an average squared error. Some calculations report the unnormalized sum instead; either convention is valid, but the convention must be used consistently when comparing risks or setting a penalty. Empty cells have no fitted sample mean and are excluded from this definition; here all candidate cells contain observations.

Worked Empirical Calculations

Consider four observations with predictor values $x_i$ and responses $y_i$. The candidate split thresholds are $1,2,3$. A threshold $t$ places observations with $x_i<t$ in the left cell and observations with $x_i\ge t$ in the right cell.

Observation	$x_i$	$y_i$
1	0.5	0
2	1.5	1
3	2.5	3
4	3.5	4

Worked Example: Leaf Means and Empirical Squared Error

First fit the tree with one split at $t=2$. Its left responses are $0,1$, and its right responses are $3,4$. The leaf means are $$ \hat c_L=\frac{0+1}{2}=\frac12,\qquad \hat c_R=\frac{3+4}{2}=\frac72. $$

The left-cell sum of squared errors is $$ (0-\tfrac12)^2+(1-\tfrac12)^2=\tfrac14+\tfrac14=\tfrac12, $$ and the right-cell sum is $$ (3-\tfrac72)^2+(4-\tfrac72)^2=\tfrac14+\tfrac14=\tfrac12. $$ Thus the total squared error is $1$, and the empirical squared-error risk is $1/4=0.25$.

For comparison, the root-only tree has one leaf mean $(0+1+3+4)/4=2$. Its total squared error is $$ (0-2)^2+(1-2)^2+(3-2)^2+(4-2)^2=4+1+1+4=10, $$ so its empirical risk is $10/4=2.5$. The split at 2 reduces the observed average squared error from $2.5$ to $0.25$.

Result: For any nonempty leaf containing $m$ responses $z_1,\ldots,z_m$, their sample mean $\bar z=m^{-1}\sum_{i=1}^m z_i$ minimizes $\sum_{i=1}^m(z_i-c)^2$ over all constants $c$. More precisely, $$ \sum_{i=1}^m(z_i-c)^2=\sum_{i=1}^m(z_i-\bar z)^2+m(c-\bar z)^2. $$

To verify the identity, write $z_i-c=(z_i-\bar z)+(\bar z-c)$, square, and sum. The cross term vanishes because $\sum_i(z_i-\bar z)=0$. Since $m(c-\bar z)^2\ge 0$, the sum is minimized at $c=\bar z$; this is the unique minimizer when $m>0$. Applying the identity separately in every cell proves that the cell means minimize the tree's empirical squared error among all predictions that are constant on its fixed cells. $\square$

Cell Approximation Error Is a Population Quantity

To calculate approximation error, specify a predictor distribution and a target regression function. Suppose $X$ is uniform on $[0,4]$, and the regression function is $m(x)=E[Y\mid X=x]=x$. For a cell $A_j$ with positive probability, the best constant approximation to $m(X)$ in squared-error risk is its conditional mean $c_j=E[m(X)\mid X\in A_j]$. The cell approximation error is the expected squared difference between the regression function and these cellwise constants.

Definition: For a partition $\mathcal P=\{A_1,\ldots,A_K\}$, its cell approximation error for regression function $m$ is $$ R_{\mathrm{app}}(\mathcal P)=\sum_{j=1}^K E\!\left[(m(X)-c_j)^2\mathbf{1}\{X\in A_j\}\right], \qquad c_j=E[m(X)\mid X\in A_j], $$ where cells of probability zero are omitted.

Worked Example: Approximation Error for a Split at 2

For a split at 2, the cells are $[0,2)$ and $[2,4]$. Because $X$ is uniform and $m(x)=x$, the conditional mean of $m(X)$ on each cell is its midpoint: $1$ on the first cell and $3$ on the second. The density of $X$ is $1/4$, so $$ R_{\mathrm{app}}=\frac14\left\{\int_0^2(x-1)^2\,dx+\int_2^4(x-3)^2\,dx\right\}. $$ Each integral is $2/3$: for example, $\int_0^2(x-1)^2dx=[(x-1)^3/3]_0^2=2/3$. Therefore $$ R_{\mathrm{app}}=\frac14\left(\frac23+\frac23\right)=\frac13. $$

For the root-only partition, the best constant is $2$, and $$ R_{\mathrm{app}}=\frac14\int_0^4(x-2)^2\,dx=\frac14\cdot\frac{16}{3}=\frac43. $$ Thus the split reduces this function-approximation error from $4/3$ to $1/3$. These values are population quantities under the specified uniform distribution, not calculations from the four observed responses.

Result: If $E[Y^2]<\infty$, $m(X)=E[Y\mid X]$, and $g(X)$ is a square-integrable predictor, then $$ E[(Y-g(X))^2]=E[\operatorname{Var}(Y\mid X)]+E[(m(X)-g(X))^2]. $$

For the proof, condition on $X$ and write $Y-g(X)=(Y-m(X))+(m(X)-g(X))$. The conditional expectation of the squared expression is $$ E[(Y-m(X))^2\mid X]+(m(X)-g(X))^2 +2(m(X)-g(X))E[Y-m(X)\mid X]. $$ The final term is zero by the definition of conditional expectation, and the first term is $\operatorname{Var}(Y\mid X)$. Taking expectations gives the identity. The finite second-moment and square-integrability assumptions ensure the terms are defined. $\square$

For a predictor constant on each partition cell, the second term is the approximation error when the constant in each cell is its conditional mean. The first term, the conditional noise variance averaged over $X$, does not depend on the partition. This decomposition explains why approximation error is useful for comparing representational ability, while empirical training risk also reflects the particular observed responses.

Worked Example: Approximation Error for Several Thresholds

For any interval cell of width $w$ under the uniform distribution on $[0,4]$, the conditional mean of $m(X)=X$ is the interval midpoint. Its contribution to $R_{\mathrm{app}}$ is the integral of the squared distance from that midpoint, multiplied by the density $1/4$: $$ \frac14\int_{-w/2}^{w/2}u^2\,du=\frac{w^3}{48}. $$ A root-only tree has width $4$, giving $4^3/48=4/3$, as above.

A split at 1 produces widths 1 and 3, so its approximation error is $$ \frac{1^3+3^3}{48}=\frac{28}{48}=\frac{7}{12}. $$ A split at 3 gives the same result by symmetry. A split at 2 has widths 2 and 2, giving $(8+8)/48=1/3$. Finally, splitting at all three thresholds gives four width-1 cells and error $4/48=1/12$. The finer partition approximates the linear function more closely, though it uses more leaves.

Choosing a Tree With a Complexity Penalty

A tree with more leaves can reduce empirical error, sometimes simply by fitting the observed responses more closely. One simple selection rule adds a penalty proportional to the number of leaves. For a penalty parameter $\lambda\ge 0$, define $$ \hat R_\lambda(\mathcal P)=\hat R(\mathcal P)+\lambda K. $$ Here $\hat R$ is the empirical risk divided by $n$, and $\lambda$ is measured in squared-response units. This calculation illustrates the trade-off for a specified candidate set; it does not claim that one penalty value is universally appropriate.

Worked Example: Selecting Among All Subsets of Three Thresholds

Use candidate thresholds $\{1,2,3\}$, and allow any subset of them as the internal splits. For one split, the empirical risks are $7/6$ at 1, $1/4$ at 2, and $7/6$ at 3. For example, at 1 the right-cell mean is $8/3$, with squared error $$ (1-\tfrac83)^2+(3-\tfrac83)^2+(4-\tfrac83)^2 =\frac{25+1+16}{9}=\frac{14}{3}; $$ the left-cell error is zero, so the average risk is $(14/3)/4=7/6$.

With two splits, the choices $\{1,2\}$ and $\{2,3\}$ each have total squared error $1/2$, hence risk $1/8$. For $\{1,3\}$, the middle responses $1,3$ have mean $2$ and total squared error $2$, hence risk $1/2$. With all three splits, each observation has its own leaf, so the empirical risk is zero. The root-only risk is $5/2$.

Set $\lambda=0.4$. The penalized risks are:

Root only, $K=1$: $2.5+0.4(1)=2.9$.
One split at 1 or 3, $K=2$: $7/6+0.8=59/30$, approximately $1.967$.
One split at 2, $K=2$: $0.25+0.8=1.05$.
Two splits at $\{1,2\}$ or $\{2,3\}$, $K=3$: $0.125+1.2=1.325$.
Two splits at $\{1,3\}$, $K=3$: $0.5+1.2=1.7$.
All three splits, $K=4$: $0+1.6=1.6$.

The smallest value is $1.05$, so this penalized criterion selects the single split at 2. The four-leaf tree fits the observed responses perfectly, but its larger complexity penalty makes it less attractive under this choice of $\lambda$.

Common Pitfalls and Interpretation

A frequent mistake is to treat every quantity called “risk” as interchangeable. The empirical risk above is computed from the observed $y_i$; the cell approximation error is an expectation under the specified distribution of $X$ and uses the specified function $m$. They need not move together for a particular finite sample. In addition, the penalty comparison is meaningful only when the same risk normalization and leaf-count convention are applied to every candidate.

Using a global mean in every leaf. The squared-error minimizing constant is the mean within that leaf, not the overall sample mean.
Comparing total error to average error inconsistently. Dividing every candidate's sum by the same $n$ preserves the unpenalized ranking, but changes the relative scale of a penalty unless its value is adjusted too.
Calling training error approximation error. Training error depends on observed responses; approximation error depends on $m$, the predictor distribution, and the partition.
Assuming a finer tree must win after penalization. Its unpenalized training error cannot increase when a partition is refined and leaf means are refitted, but the complexity penalty can make the refined tree's criterion larger.

Key takeaway: Calculate each leaf mean first, then sum within-leaf squared deviations and divide by $n$ if using average empirical risk. Compute cell approximation error separately from the target function and predictor distribution. Only then compare candidate trees using an explicitly stated penalty.

Check Your Understanding

Use the definitions and calculations above to answer the following.

For responses $2,5,5$ in one leaf, find the leaf mean and the sum of squared errors.
Why does the empirical squared-error minimizing constant in a fixed leaf equal the sample mean?
Under $X\sim\operatorname{Unif}[0,4]$ and $m(x)=x$, what widths are created by a split at 1, and how do they determine the approximation error?
For the data in the table, why does the four-leaf tree have zero empirical risk but nonzero cell approximation error?
If a penalty is added to total squared error rather than average squared error, what must be considered when interpreting the same numerical penalty value?