Split Instability Near Empirical Ties

Why Nearly Tied Splits Deserve Attention

A greedy tree algorithm chooses, at each node, a candidate split with the largest empirical improvement in fit. If one split improves the fit substantially more than every alternative, a small data perturbation is unlikely to change the choice. If two candidates have almost equal gains, however, even a small change in one response can reverse their ordering. The resulting tree can have a different structure although the data, fitted values, and predictive performance have changed very little.

The key is to separate two questions. Structural stability asks whether the selected split, and hence the tree partition, remains the same. Risk stability asks whether prediction performance changes. A near-tie directly threatens the first; it does not, by itself, answer the second.

Empirical Gain at a Fixed Node

Consider a regression-tree node containing $n$ observations with responses $y=(y_1,\ldots,y_n)^\top$. A candidate split $s$ divides these observations into two nonempty groups. The parent prediction is the mean of all $n$ responses, and the two child predictions are the means within their respective groups. We use squared-error loss and define gain as the reduction in empirical mean squared error. The candidate partitions are treated as fixed in the definitions and stability result below.

Definition: For a candidate split $s$, let $\operatorname{SSE}_{\mathrm{parent}}$ be the sum of squared residuals from the parent mean, and let $\operatorname{SSE}_{s}$ be the sum of squared residuals from the two child means. Its empirical gain is $$ G_s(y)=\frac{\operatorname{SSE}_{\mathrm{parent}}-\operatorname{SSE}_{s}}{n}. $$ A split with larger gain is preferred by the greedy squared-error rule. The gain gap between two candidates $s$ and $t$ is $\lvert G_s(y)-G_t(y)\rvert$.

A useful equivalent expression uses orthogonal projections. Let $P_0$ be the projection onto vectors that are constant across the parent node, and let $P_s$ be the projection onto vectors constant within each of the two child groups of split $s$. Since every parent-constant vector is also child-constant, the range of $P_0$ is contained in the range of $P_s$. Thus $Q_s=P_s-P_0$ is the orthogonal projection onto the part of the child-constant space orthogonal to the parent-constant space. The reduction in the residual sum of squares is $y^\top Q_s y$, so

G_s(y)=\frac{1}{n}y^\top Q_s y.

This expression makes the effect of perturbing responses precise. It applies when the split memberships stay fixed. If a predictor changes enough to move observations from one child to another, then the matrices $P_s$ and $Q_s$ can change too; the bound below does not cover that additional source of instability.

Worked Example: A Small Response Change Reverses a Near-Tie

Suppose four observations are divided by two available candidate splits, $A$ and $B$. Split $A$ assigns observations $\{1,2\}$ to one child and $\{3,4\}$ to the other. Split $B$ assigns $\{1,3\}$ and $\{2,4\}$. These two partitions can arise from two different predictors. Take responses $y=(0,1,1.02,0.02)$.

For either split, each child has size two. If the two child means are $u$ and $v$, the between-group sum of squares is $2(u-\bar y)^2+2(v-\bar y)^2$, where $\bar y=(u+v)/2$. Since $u-\bar y=(u-v)/2$ and $v-\bar y=(v-u)/2$, this sum is $$ 2\left(\frac{u-v}{2}\right)^2+2\left(\frac{v-u}{2}\right)^2=(u-v)^2. $$ The gain divides this between-group sum of squares by $n=4$, so it is $(u-v)^2/4$.

For split $A$, the child means are $(0+1)/2=0.5$ and $(1.02+0.02)/2=0.52$. Therefore $G_A=(0.52-0.5)^2/4=0.0001$. For split $B$, both child means equal $(0+1.02)/2=(1+0.02)/2=0.51$, so $G_B=0$. Split $A$ wins, but only by $0.0001$.

Now change only the third response from $1.02$ to $0.98$, a perturbation of magnitude $0.04$. Under $A$, the child means are $0.5$ and $(0.98+0.02)/2=0.5$, giving gain zero. Under $B$, the means are $(0+0.98)/2=0.49$ and $(1+0.02)/2=0.51$, giving gain $(0.51-0.49)^2/4=0.0001$. Now $B$ wins. The selected structure changes because the original gains were close; the calculation alone says nothing about whether prediction risk changed materially.

A Perturbation Bound for Fixed Candidate Splits

The following result gives a sufficient condition for the ordering of two gains to survive a response perturbation. Write the perturbed response vector as $y+d$, where $d$ is the vector of response changes. Norms below are Euclidean norms, and the candidate partitions are held fixed.

Theorem: Let $s$ and $t$ be two fixed candidate splits at a node with $n$ observations. For any response vectors $y$ and $d$, $$ \left| \{G_s(y+d)-G_t(y+d)\}-\{G_s(y)-G_t(y)\}\right| \leq \frac{4\|y\|\|d\|+2\|d\|^2}{n}. $$ In particular, if $G_s(y)>G_t(y)$ and $$ G_s(y)-G_t(y)>\frac{4\|y\|\|d\|+2\|d\|^2}{n}, $$ then $G_s(y+d)>G_t(y+d)$; the perturbation cannot reverse their ordering.

Proof. Let $A=Q_s-Q_t$. By the projection representation, $$ G_s(y)-G_t(y)=\frac{1}{n}y^\top A y. $$ Each orthogonal projection has operator norm at most one, so the triangle inequality gives $\|A\|_{\mathrm{op}}\leq\|Q_s\|_{\mathrm{op}}+\|Q_t\|_{\mathrm{op}}\leq2$. Expanding the perturbed quadratic form gives

(y+d)^\top A(y+d)-y^\top Ay =2y^\top Ad+d^\top Ad.

By the Cauchy–Schwarz inequality and the definition of operator norm, $$ \left|2y^\top Ad+d^\top Ad\right| \leq 2\|y\|\|A\|_{\mathrm{op}}\|d\|+\|A\|_{\mathrm{op}}\|d\|^2 \leq 4\|y\|\|d\|+2\|d\|^2. $$ Dividing by $n$ proves the bound. If the original gap in favor of $s$ exceeds this bound, the perturbed difference is still positive: its decrease in absolute value cannot be as large as the original positive gap. Therefore $s$ remains ahead of $t$. $\square$

This is a sufficient condition, not a necessary one. The bound can be conservative because it uses the full response norm and a worst-case operator-norm bound. In practice, it is most useful for its qualitative message: a larger gain gap provides more protection against perturbation, while a small gap can make the selected split fragile.

Worked Example: Checking a Stability Guarantee

Return to the four responses $y=(0,1,1.02,0.02)$, for which the gain gap between $A$ and $B$ is $0.0001$. Suppose instead of the larger change above, the third response changes by $10^{-6}$, so $\|d\|=10^{-6}$. The squared norm of the response vector is $$ \|y\|^2=0^2+1^2+1.02^2+0.02^2=2.0408, $$ so $\|y\|=\sqrt{2.0408}<1.43$. The theorem's bound is therefore less than $$ \frac{4(1.43)(10^{-6})+2(10^{-6})^2}{4} <1.431\times10^{-6}. $$ This is smaller than $0.0001=10^{-4}$. Because $A$'s original advantage exceeds the bound, the theorem guarantees that this perturbation cannot make $B$ overtake $A$. The calculation is a guarantee for these fixed partitions; it is not a guarantee for a perturbation that also changes which observations fall into each candidate child.

Split Structure and Prediction Risk Are Different

A tree's structure records which variables and thresholds define its cells. Prediction risk instead evaluates the predictions those cells produce on a target distribution. Different structures can yield similar predictions, especially when their differences affect a small-probability region or when the fitted values in the affected cells are close.

For squared-error prediction, this distinction can be made exact. Let $m(x)=E[Y\mid X=x]$, assume $E[Y^2]<\infty$, and let $h(X)$ be any square-integrable predictor. Its risk is $R(h)=E[(Y-h(X))^2]$. Conditioning on $X$ and using $E[Y-m(X)\mid X]=0$ gives

Result: Under the stated square-integrability conditions, $$ R(h)=E[(Y-m(X))^2]+E[(h(X)-m(X))^2]. $$ Consequently, for two predictors $h_1,h_2$, their risk difference is $$ R(h_1)-R(h_2) =E[(h_1(X)-m(X))^2-(h_2(X)-m(X))^2]. $$

Derivation. Write $Y-h(X)=(Y-m(X))+(m(X)-h(X))$, square, and take expectations. The cross term has expectation zero because $$ E[(Y-m(X))(m(X)-h(X))] =E\left[(m(X)-h(X))E[Y-m(X)\mid X]\right]=0. $$ All terms are integrable by square integrability, so the conditional expectation identity applies. Subtracting the resulting risk expressions for $h_1$ and $h_2$ cancels the common noise term $E[(Y-m(X))^2]$, giving the stated difference. $\square$

This identity also shows why a structural change need not entail a large risk change. If two predictors differ only on a region of small probability, their excess risks can be close even if the partitions are not identical. Conversely, if the altered split separates regions with substantially different conditional means, a structural change can matter. Risk must be assessed from the predictions and the distribution of $X$, not inferred from the split label alone.

Worked Example: Different Thresholds, Small Risk Difference

Let $X$ be uniform on $[0,1]$ and let $Y=0$ with probability one, so $m(x)=0$ and the Bayes risk is zero. Consider two one-split predictors. The first predicts $1$ when $X\leq0.5$ and $0$ otherwise. The second predicts $1$ when $X\leq0.5001$ and $0$ otherwise. Their thresholds and tree partitions differ.

For the first predictor, the squared prediction error is $1$ on an interval of length $0.5$ and zero elsewhere. Since $X$ is uniform, $R(h_1)=0.5$. For the second, the corresponding interval has length $0.5001$, so $R(h_2)=0.5001$. The risk difference is $0.0001$, even though the fitted partitions are not the same.

More generally, if two predictors agree outside a set $D$ with $P(X\in D)=p$, and each has squared deviation from $m(X)$ between $0$ and $M^2$ on $D$, then $$ |R(h_1)-R(h_2)| \leq E\left[\left|(h_1(X)-m(X))^2-(h_2(X)-m(X))^2\right|\right] \leq M^2p. $$ The first inequality follows from the risk-difference identity and the triangle inequality; the second follows because the integrand is zero outside $D$ and is at most $M^2$ on $D$. Here the differing region has probability $0.0001$, and both squared deviations are at most one there, matching the calculated risk difference.

What the Stability Calculation Does—and Does Not—Say

The perturbation theorem addresses a local question: with the candidate partitions fixed, can response changes reverse the empirical ordering of two splits? It does not establish that the chosen tree is statistically optimal, nor that the winning split will remain the same in a new sample. It also does not cover changes in predictor values that alter candidate thresholds, move observations across child boundaries, or change which splits satisfy a minimum-leaf-size rule.

There is another important limitation. A guarantee for a pair of candidates is not automatically a guarantee for the entire candidate set. To certify the overall winner, the leading candidate's gain must exceed every competitor's gain by enough to withstand its corresponding perturbation bound. If the algorithm uses deterministic tie-breaking, exact ties are resolved by that rule, but the tie-breaking convention does not make the split empirically well separated.

Common Mistake

Wrong reasoning: “The selected split changed after a small perturbation, so the predictor must have become much worse.” A split change records a change in the maximizing candidate, not the size of a risk change.
Correction: First compare the empirical gain gap to the perturbation scale to assess structural fragility. Then assess prediction risk using fitted values and the target distribution. The two assessments answer different questions.
Another limitation to avoid: Applying the fixed-partition perturbation bound after predictor perturbations have changed the child memberships. In that case the projection matrices themselves change, so the displayed theorem alone does not apply.

Key takeaway: A small empirical gain gap makes a greedy split vulnerable to response perturbations. That vulnerability concerns the selected tree structure; it does not by itself imply a substantial change in prediction risk.

Check Your Understanding

Use the definitions and results above to answer the following questions.

For a fixed candidate split, what does its empirical gain measure, and why is it nonnegative?
In the perturbation theorem, why must the candidate partitions be held fixed?
If the leading gain exceeds the theorem's bound for each competitor, what can be concluded about the selected split?
Why does a changed split not, by itself, establish that prediction risk increased?
In the uniform-$X$ example, what probability mass lies between the two thresholds, and how does it determine the risk difference?