Why the First Split Is Not the Whole Decision
A regression tree is built by dividing predictor space into regions and assigning each terminal region the mean response of its training observations. When a tree is grown one split at a time, a common rule is to choose the available split that most reduces the current within-node sum of squares. This is a greedy rule: it optimizes the next step, not necessarily the entire tree.
That distinction matters when the desired tree has a fixed number of terminal nodes. A root split with a large immediate improvement can leave branches that are difficult to refine. A different root split may improve the error less at first, yet make a much more useful next split available. The right comparison is therefore between the training errors of complete trees of the required size, not just between their root-split gains.
These definitions assume unweighted observations and squared-error loss, with each terminal node predicting its sample mean. “Fixed size” here means a fixed number of terminal nodes; it does not mean a fixed tree depth. Candidate splits must respect the predictors and split rules available in the problem. The globally best tree is best only among those admissible trees and under the stated training-error criterion.
Why the Split-Gain Formula Works
Suppose a node with \(n\) observations is divided into children \(L\) and \(R\), with sizes \(n_L\) and \(n_R\), where \(n=n_L+n_R\). Let their response means be \(\bar{y}_L\) and \(\bar{y}_R\), and let \(\bar{y}\) be the mean in the parent. The immediate reduction in within-node sum of squares is
To justify the first equality, write each response in a child as its deviation from that child’s mean plus the child mean’s deviation from the parent mean. For the left child, for example,
because the cross-product term is zero: \(\sum_{i\in L}(y_i-\bar{y}_L)=0\). The same identity holds for the right child. Subtracting the children’s within-node sums of squares leaves the two between-child terms shown above. Finally, \(\bar{y}=(n_L\bar{y}_L+n_R\bar{y}_R)/n\); substituting this weighted mean into those terms gives the final expression. The formula measures only the immediate reduction from this split. It does not include improvements from any later splits.
Worked Example: A Greedy Root Gives the Worse Three-Leaf Tree
A hypothetical portfolio records the response \(Y\), a claim-cost measure in thousands of dollars, for four policy renewals. Two binary predictors, \(U\) and \(V\), each have values 0 and 1. Build a three-terminal-node tree. Compare the greedy root with the best tree among the two possible root predictors, allowing one child to be split once.
| \(U\) | \(V\) | \(Y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 9.5 |
| 1 | 0 | 10 |
| 1 | 1 | 1.5 |
Method. Calculate each root’s immediate gain, then add the best available gain from splitting one of its children. With four observations and two binary predictors, a root fixes one predictor and a child can be divided by the other predictor. This exhausts the possible one-child continuations for either root.
The overall response mean is \((0+9.5+10+1.5)/4=21/4=5.25\). For a root split on \(U\), the \(U=0\) child has mean \((0+9.5)/2=4.75\), and the \(U=1\) child has mean \((10+1.5)/2=5.75\). The immediate gain is
For a root split on \(V\), the \(V=0\) child has mean \((0+10)/2=5\), and the \(V=1\) child has mean \((9.5+1.5)/2=5.5\). Its immediate gain is \(2(5-5.25)^2+2(5.5-5.25)^2=2(0.0625)+2(0.0625)=0.25\). Thus the greedy rule chooses \(U\), because \(1>0.25\).
Now evaluate the continuation after each root. Under root \(U\), splitting the \(U=0\) child by \(V\) separates 0 and 9.5. Its gain is \((9.5-0)^2/2=45.125\). Splitting the \(U=1\) child instead separates 10 and 1.5, giving \((10-1.5)^2/2=36.125\). The best three-leaf tree rooted at \(U\) therefore has total reduction \(1+45.125=46.125\).
Under root \(V\), splitting the \(V=0\) child by \(U\) separates 0 and 10, giving \((10-0)^2/2=50\). Splitting the \(V=1\) child separates 9.5 and 1.5, giving \((9.5-1.5)^2/2=32\). The best three-leaf tree rooted at \(V\) has total reduction \(0.25+50=50.25\), which is greater than 46.125.
Check the comparison using the total sum of squares. The mean is 5.25, so the total is \(27.5625+18.0625+22.5625+14.0625=82.25\). The best \(U\)-rooted tree has training error \(82.25-46.125=36.125\); the best \(V\)-rooted tree has training error \(82.25-50.25=32\). The lower-error tree starts with the smaller immediate gain. Common mistake avoided: selecting \(U\) for the whole three-leaf tree simply because its root gain is larger.
Compare Complete Trees, Not Just Root Scores
The example illustrates a useful accounting principle. If a root has gain \(\Delta_{\text{root}}\), and later splits have gains \(\Delta_2,\ldots,\Delta_k\), then the total reduction from the unsplit root is their sum. This follows because each split reduces the current total within-node sum of squares by its own gain. The final training error is the original error minus that total reduction.
This sum makes the greedy limitation concrete. A greedy algorithm selects the largest available \(\Delta_{\text{root}}\), but a fixed-size tree comparison depends on the root gain and the gains its descendants can achieve. A smaller first term can be outweighed by larger later terms. Greedy splitting is a computationally practical construction rule; it is not, in general, an exhaustive optimization over every tree of the requested size.
Worked Example: A Second Dataset Reverses the Root Ranking
A hypothetical service team records a response \(Y\), in thousands of dollars, for four cases with binary predictors \(A\) and \(B\). As before, the goal is a three-terminal-node regression tree. Determine whether the root with the greater immediate gain also gives the better complete tree.
| \(A\) | \(B\) | \(Y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 8 |
| 1 | 0 | 9 |
| 1 | 1 | 2 |
Method. Compare each root’s immediate gain, then calculate the best child-split gain available under that root. The overall mean is \((0+8+9+2)/4=4.75\). The \(A\)-group means are 4 and 5.5, so the immediate gain is \(2(4-4.75)^2+2(5.5-4.75)^2=2(0.5625)+2(0.5625)=2.25\). The \(B\)-group means are 4.5 and 5, giving \(2(4.5-4.75)^2+2(5-4.75)^2=0.25\). Greedy splitting chooses \(A\).
After root \(A\), splitting the \(A=0\) child separates 0 and 8, for gain \(8^2/2=32\). Splitting the \(A=1\) child separates 9 and 2, for gain \(7^2/2=24.5\). The best \(A\)-rooted three-leaf tree has total reduction \(2.25+32=34.25\).
After root \(B\), splitting the \(B=0\) child separates 0 and 9, for gain \(9^2/2=40.5\). Splitting the \(B=1\) child separates 8 and 2, for gain \(6^2/2=18\). The best \(B\)-rooted tree has total reduction \(0.25+40.5=40.75\), exceeding 34.25. The total sum of squares is \(58.75\), since the mean is 4.75 and the squared deviations sum to \(22.5625+10.5625+18.0625+7.5625=58.75\). Thus the best trees’ errors are \(58.75-34.25=24.5\) for root \(A\) and \(58.75-40.75=18\) for root \(B\). Common mistake avoided: treating the root ranking as if it ranked the resulting three-leaf trees.
A Third Check: Verify the Leaf Errors
Gain arithmetic is efficient, but terminal-node predictions provide an independent check. For each tree, predict with each leaf’s sample mean and sum the squared residuals. This also helps distinguish a tree’s structure from its split labels: two candidate trees should be compared by their resulting leaves and errors, not by how attractive one branch looks in isolation.
Worked Example: Checking Three-Leaf Predictions Directly
For a hypothetical set of four risk records, the response \(Y\) is measured in thousands of dollars and the predictors \(C\) and \(D\) are binary.
| \(C\) | \(D\) | \(Y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 7 |
| 1 | 0 | 8 |
| 1 | 1 | 1 |
Method. First compare root gains, then calculate each best three-leaf tree’s terminal predictions and squared error. The grand mean is \((0+7+8+1)/4=4\). For root \(C\), the two means are 3.5 and 4.5, so the gain is \(2(3.5-4)^2+2(4.5-4)^2=1\). For root \(D\), both child means are 4, so its gain is 0. Greedy splitting therefore chooses \(C\).
With root \(C\), splitting the \(C=0\) child produces two leaves with predictions 0 and 7; the \(C=1\) child remains a leaf with prediction \((8+1)/2=4.5\). Its squared error is \((8-4.5)^2+(1-4.5)^2=12.25+12.25=24.5\). Splitting the other \(C\) child instead gives the same error, since its two responses also differ by 7.
With root \(D\), split the \(D=0\) child into the observations with responses 0 and 8. The remaining \(D=1\) leaf predicts \((7+1)/2=4\). Its squared error is \((7-4)^2+(1-4)^2=9+9=18\). To check against the unsplit error, the total sum of squares around 4 is \(16+9+16+9=50\). The \(C\)-rooted tree reduces it by \(50-24.5=25.5\), whereas the \(D\)-rooted tree reduces it by \(50-18=32\). Thus the root with zero immediate gain gives the better three-leaf tree. Common mistake avoided: assuming a root with no immediate improvement cannot be part of a useful larger tree.
What the Counterexample Does—and Does Not—Show
The examples do not show that greedy splitting always chooses a poor tree. They show that its local decision rule does not guarantee the globally smallest training error among trees with the same number of terminal nodes. A strong root split may work well; the issue is that its immediate score alone cannot certify it as the best root for the final tree.
A full global search must compare complete admissible trees. As the number of observations, candidate splits, and terminal nodes increases, the number of possible tree structures can grow rapidly. This is why a greedy construction is useful in practice, even though it can miss a better fixed-size tree. In an exam-style calculation, when the data and candidate structures are small enough, explicitly compare the best continuation from each plausible root rather than stopping at the first-split scores.
Use the reduction in total within-node sum of squares, not the error of just one child.
For each candidate root, identify how many additional splits are available and which children can be split.
Add the gains from all splits in each complete tree, or calculate its terminal-node sum of squares directly.
Exam trap: the greatest immediate reduction is the answer only when the question asks for the next greedy split. If it asks for the best tree of a specified size, compare all relevant complete trees. Also ensure the compared trees have the same number of leaves; otherwise a lower error may simply reflect a larger model.
Check Your Understanding
For each problem, distinguish the immediate split score from the total performance of the complete tree.
- A parent node has six observations. A candidate split produces child sizes 3 and 3 with means 2 and 6. Find its immediate reduction in within-node sum of squares. (Answer: 24)
- Two candidate roots have immediate gains 12 and 10. For a three-leaf tree, the best additional gain after the first root is 3; after the second root it is 9. Which root gives the lower-error three-leaf tree, and by how much in total reduction? (Answer: The second root; its total reduction is 21 versus 15, a difference of 6.)
- For the four responses \(\begin{smallmatrix}0&5\\6&1\end{smallmatrix}\), rows represent \(A=0,1\) and columns represent \(B=0,1\). Compare the best three-leaf tree rooted by rows with the best one rooted by columns. (Answer: The column-rooted tree; its total reduction is 18, versus 13.5 for the row-rooted tree.)
- A greedy root gives a reduction of 14 and its best continuation adds 3. Another root gives a reduction of 12 and its best continuation adds 9. Which is globally better at three leaves, and what are the two total reductions? (Answer: The second root is better; total reductions are 21 versus 17.)
- The original unsplit tree has sum of squares 70. One three-leaf tree reduces it by 28, while another reduces it by 33. State both final errors and identify the better tree. (Answer: The errors are 42 and 37; the second tree is better.)