Why Greedy Splitting Can Miss Better Trees

Why the Best Next Split May Not Build the Best Tree

A greedy tree-growing rule makes a local decision: at the current stage, it chooses the available split that reduces risk the most immediately. That rule is computationally convenient, but its objective is not the same as finding the best whole tree under a fixed leaf budget. A split can have little immediate value and still create child cells where later splits are highly informative. Conversely, a larger first gain can leave too few leaves to express an important interaction.

The distinction is between one-step improvement and the total improvement of a sequence. The examples below use population squared-error risk, so the comparisons are exact rather than consequences of sampling noise. They show both zero-gain prerequisites and cases where a greedy positive-gain choice is inferior to another tree with the same number of leaves.

Population Risk and the Gain from One Split

Let $W$ denote the predictors and $Y$ a response with $E[Y^2]<\infty$. A regression tree partitions the predictor space into finitely many cells and predicts a constant in each cell. The risk of a tree $T$ is $R(T)=E[(Y-f_T(W))^2]$. For a fixed partition, the risk-minimizing prediction in each cell of positive probability is the conditional mean of $Y$ in that cell. A zero-probability cell contributes zero to population risk; its conditional mean and conditional risk are undefined.

Definition: Suppose a current leaf corresponds to a measurable cell $A$ with $P(W\in A)>0$. A candidate split divides it into disjoint child cells $A_L$ and $A_R$, both of positive probability. Its population risk gain is the risk before the split minus the risk after replacing the parent prediction by the two child conditional means. A greedy split selects the available candidate with the largest such gain at that step.

The gain is weighted by the probability of the cell being split. Thus a large improvement in a very small cell may have little effect on total population risk. The following identity makes the local calculation precise.

Theorem: Write $q=P(W\in A_L\mid W\in A)$, $\mu_L=E[Y\mid W\in A_L]$, and $\mu_R=E[Y\mid W\in A_R]$. The population risk gain from optimally splitting $A$ is $$ P(W\in A)\,q(1-q)(\mu_L-\mu_R)^2. $$

Proof. Let $\mu=E[Y\mid W\in A]=q\mu_L+(1-q)\mu_R$. For a cell $B$, the minimum conditional squared-error risk is $\operatorname{Var}(Y\mid W\in B)$. The conditional variance decomposition within $A$ gives $$ \operatorname{Var}(Y\mid W\in A) =q\operatorname{Var}(Y\mid W\in A_L) +(1-q)\operatorname{Var}(Y\mid W\in A_R) +q(\mu_L-\mu)^2+(1-q)(\mu_R-\mu)^2. $$ Subtracting the weighted child risks leaves the final two terms. Since $\mu_L-\mu=(1-q)(\mu_L-\mu_R)$ and $\mu_R-\mu=-q(\mu_L-\mu_R)$, those terms sum to $$ q(1-q)^2(\mu_L-\mu_R)^2+(1-q)q^2(\mu_L-\mu_R)^2 =q(1-q)(\mu_L-\mu_R)^2. $$ Multiplying by $P(W\in A)$ converts the conditional risk reduction to a population risk reduction. $\square$

For a finite sequence of splits, total risk reduction is the sum of the gains at the individual split nodes, each weighted by the probability of its cell. This follows by subtracting the tree risks before and after each split: every intermediate risk cancels when the differences are added. The identity explains how to calculate a whole tree’s improvement, but it does not imply that choosing the largest gain first maximizes that sum under a leaf budget.

Worked Examples: When a Prerequisite Split Has No Gain

Worked Example: An Interaction Hidden at the Root

Let $X$ and $Z$ be independent, each equally likely to be $-1$ or $1$, and let $Y=XZ$. The root prediction is $E[Y]=0$, so the root risk is $E[Y^2]=1$.

If the root is split on $X$, then $E[Y\mid X]=X E[Z]=0$. Both child means are zero, so this split has gain zero. The same calculation gives $E[Y\mid Z]=Z E[X]=0$, so splitting on $Z$ at the root also has zero gain.

Now split first on $X$, then split each resulting cell on $Z$. In the leaf indexed by $(X,Z)=(x,z)$, the response is always $xz$, so the leaf prediction is $xz$ and the risk is zero. The first split made no immediate progress, but it allowed a second-level split to express the interaction exactly. A procedure that refuses every zero-gain split would stop at the root and miss this tree.

This example also warns against overinterpreting ties: either variable can be the first split, and both choices lead to the same exact tree if the subsequent splits are allowed. The issue is not that one root choice is uniquely right, but that immediate gain alone cannot identify the value of a split sequence.

A Positive Greedy Gain Can Still Lead to a Worse Tree

Worked Example: Comparing Four-Leaf Trees

Let $A,B,C$ be independent Rademacher variables (each is equally likely to be $-1$ or $1$), and define $$ Y=A+2B+10AC. $$ Consider trees that split on these binary predictors and have four leaves. The root risk is $$ E[Y^2]=E[A^2]+4E[B^2]+100E[A^2C^2]=1+4+100=105. $$ All cross terms have expectation zero by independence and zero means.

At the root, the conditional means are $E[Y\mid A]=A$, $E[Y\mid B]=2B$, and $E[Y\mid C]=0$. Therefore the gains from splitting on $A,B,C$ are respectively $1,4,0$. A greedy rule chooses $B$, with the largest immediate gain.

After the root split on $B$, each child has probability $1/2$. In a child indexed by $B=b$, splitting on $A$ gives child means $a+2b$; the remaining term $10aC$ has conditional mean zero. The conditional gain within that node is $1$, so its population-weighted gain is $1/2$. Splitting on $C$ has zero gain there, since $E[Y\mid B=b,C=c]=2b$. With four leaves, the two root children can each be split once. Splitting both on $A$ adds a total gain of $1/2+1/2=1$. The resulting risk is $105-4-1=100$.

Compare a tree that splits first on $A$, despite its smaller root gain of $1$, and then splits both $A$-children on $C$. In a cell $A=a$, the response is $(1+10C)a+2B$. Splitting that cell on $C$ removes the $10aC$ term, reducing its conditional risk by $100$. Each $A$-cell has probability $1/2$, so the two splits contribute a total population gain of $50+50=100$. This tree has risk $105-1-100=4$, much less than the risk $100$ of the four-leaf greedy tree.

Thus, for this leaf budget, the greedy root choice is strictly worse than an available alternative tree. Its immediate advantage, $4$ instead of $1$, does not compensate for the interaction that the alternative tree captures with its remaining splits.

The comparison is about the complete tree, not about whether the greedy algorithm calculates a split gain correctly. Each local gain above is correct. The limitation is that the root decision is made without accounting for how the available descendants will use the remaining leaves.

Worked Example: A Rare Group and a Small Root Gain

Worked Example: A Rare Group with a Large Conditional Signal

Let $G$ be binary with $P(G=1)=0.1$, and let $Z$ be an independent Rademacher variable. Set $Y=10\,\mathbf{1}\{G=1\}Z$. The response has mean zero and root risk $E[Y^2]=100(0.1)=10$.

A root split on $G$ has gain zero: the mean response is zero both when $G=1$ and when $G=0$. A root split on $Z$, however, gives $E[Y\mid Z=z]=10(0.1)z=z$, so its gain is $E[(E[Y\mid Z])^2]=1$. A greedy rule therefore chooses $Z$.

With a three-leaf budget, the root-$Z$ tree can split only one of its two children again. In either child, splitting on $G$ separates the response $10z$ from zero. Conditional on that child, the variance reduction is $100(0.1)(0.9)=9$. The child has probability $1/2$, so this extra split reduces population risk by $4.5$. Starting from root risk $10$, the root-$Z$ split reduces risk by $1$, and the one additional split reduces it by $4.5$, leaving risk $4.5$.

Instead, split on $G$ at the root, then split the $G=1$ child on $Z$. The root gain is zero, but in the active cell the split on $Z$ predicts $10Z$ exactly. The $G=0$ cell always has response zero, so this three-leaf tree has risk zero. The rare group makes the root-$Z$ gain small, while the initial $G$ split reveals where the large conditional signal can be captured.

What the Examples Establish

A split’s gain describes its effect on the current partition, not its usefulness as a gateway to later splits. The first example shows that an interaction can be invisible in every root conditional mean. The second shows that even when the greedy split has a strictly larger immediate gain, another root can produce a much better tree under the same leaf budget. The third shows how a low-probability subgroup can make a prerequisite split look unpromising at the root.

These are population constructions. In practice, a tree is built from data, and observed gains can also vary because of sampling. But sampling variability is not needed for the myopic limitation: it occurs even when all risks and gains are known exactly.

Common Mistakes

Assuming larger immediate gain means a better final tree. The gain measures only the current split. Compare complete trees at the same leaf budget before making a global claim.
Concluding that a zero-gain split is useless. It may expose a later interaction, as in the examples. Whether an algorithm permits such a split is a separate design choice.
Comparing conditional and population gains without weights. A gain of $100$ within a cell of probability $0.1$ contributes only $10$ to total population risk reduction.
Assigning a conditional prediction to a zero-probability cell. Its conditional mean and conditional risk are undefined. Its contribution to total population risk is zero.

Key takeaway: Greedy splitting optimizes immediate risk reduction, not the total value of a split sequence. A small or zero-gain split can be the necessary first step toward a substantially better tree.

Check Your Understanding

Use population risk and the examples above to answer the following.

For a split of a cell with probability $0.2$, the two child probabilities conditional on that cell are $0.25$ and $0.75$, and their conditional means differ by $4$. What is the population gain?
In the interaction example $Y=XZ$, why does splitting on $X$ have zero root gain, and why can splitting on $Z$ afterward reduce risk?
In the four-leaf example, what is the root risk, and what are the risks of the tree rooted at $B$ and the alternative tree rooted at $A$?
In the rare-group example, why does splitting on $G$ first have zero immediate gain even though the resulting tree can have zero risk?
Explain why the gain from a split inside a low-probability cell must be weighted before comparing it with a root split’s gain.