Why a Small Data Change Can Reshape a Tree
A regression tree is built through a sequence of local choices. At a node, the algorithm compares candidate splits and selects one with the smallest combined squared error in its child nodes. It then repeats the search within the resulting nodes. This greedy procedure is useful because it gives a concrete way to construct a piecewise-constant prediction rule, but it also creates a potential weakness: a small change to the training data can reverse the ranking of two nearly competitive first splits.
When the first split changes, the observations assigned to the next nodes can change as well. The algorithm then searches different groups of observations for later splits. Consequently, the final trees need not differ only in the location of one threshold; they can have different partitions and different predictions in entire regions of predictor space. This is called instability with respect to the training data.
The basic calculation is the within-node sum of squared errors. If a node contains responses \(y_1,\ldots,y_n\), its prediction is their mean, and its error is the sum of squared deviations from that mean. A candidate split is assessed by adding the errors of its two children. The node’s total error before splitting is the same for every candidate, so minimizing the children’s combined error is equivalent to maximizing the reduction in error.
Why Close Split Scores Are Vulnerable
For a proposed split, let the two child groups have sizes \(n_L\) and \(n_R\), with response means \(\bar y_L\) and \(\bar y_R\). The reduction in squared error is proportional to the squared difference between those means, with a factor determined by the group sizes. This makes the split score sensitive to changes in responses that shift the group means. If the best and second-best candidates have nearly equal scores, a small shift can change which one ranks first.
To see why this identity holds, write each parent-node response as its deviation from its child mean plus that child mean’s deviation from the parent mean. When the squared terms are summed, the cross-products within each child add to zero because deviations from a child mean sum to zero. The remaining terms are the two child errors plus the between-child contribution. If the parent mean is \(\bar y\), that contribution is \(n_L(\bar y_L-\bar y)^2+n_R(\bar y_R-\bar y)^2\). Using \(\bar y=(n_L\bar y_L+n_R\bar y_R)/(n_L+n_R)\) reduces it to the expression displayed above. Thus the split’s error reduction depends on the separation of the child means as well as their sizes.
The choice of split is an argmin: the algorithm selects whichever candidate has the smallest error. An argmin can change abruptly even when the underlying scores change only slightly. A useful diagnostic is therefore not just the winning score, but also its margin over the next-best candidate. A narrow margin signals that the choice may be sensitive; it does not guarantee that a change will occur.
Worked Example: A Small Response Change Reverses the First Split
A hypothetical insurer models a claim-cost index \(y\) using one ordered predictor \(x\). The six training records have \(x=1,2,3,4,5,6\). Their responses are \(0,0,10,10,0,c\), where the last response is first recorded as \(-0.1\), then revised to \(+0.1\). Compare all possible first splits and trace one later split in each resulting tree. Use the sum of squared errors (SSE) to select splits.
Method. For each threshold between adjacent \(x\) values, calculate the SSE in each child and add them. For a group of \(n\) responses, the calculation can be made as \(\sum y_i^2-(\sum y_i)^2/n\). A singleton group has SSE zero.
Before the revision, \(c=-0.1\). The five candidate thresholds are \(1.5,2.5,3.5,4.5,5.5\). At \(x=4.5\), the left group is \((0,0,10,10)\), with mean \(5\) and SSE \(200-20^2/4=100\). The right group is \((0,-0.1)\), with mean \(-0.05\) and SSE \(0.01-(-0.1)^2/2=0.005\). The total is \(100.005\).
At \(x=2.5\), the left group has SSE zero. The right group \((10,10,0,-0.1)\) has sum \(19.9\), sum of squares \(200.01\), and SSE \(200.01-19.9^2/4=101.0075\). The other candidate totals are:
- At \(x=1.5\): \(200.01-19.9^2/5=120.808\).
- At \(x=3.5\): \(200/3+(100.01-9.9^2/3)=134.0067\), to four decimal places.
- At \(x=5.5\): the first five responses have SSE \(200-20^2/5=120\), and the singleton has SSE zero.
Therefore, with \(c=-0.1\), the first split is \(x\leq 4.5\), with total SSE \(100.005\). If the left child is split once more at \(x=2.5\), its two child means are \(0\) and \(10\), each with SSE zero. The right child remains a terminal node with mean \(-0.05\).
After the revision, \(c=+0.1\). At \(x=2.5\), the left child still has SSE zero. The right child \((10,10,0,0.1)\) has sum \(20.1\), sum of squares \(200.01\), and SSE \(200.01-20.1^2/4=99.0075\). At \(x=4.5\), the left child has SSE \(100\), and the right child \((0,0.1)\) has SSE \(0.005\), for a total of \(100.005\). The other candidate totals are \(119.208\) at \(x=1.5\), \(132.6733\) at \(x=3.5\) to four decimal places, and \(120\) at \(x=5.5\). The first split is now \(x\leq2.5\).
The right child \((10,10,0,0.1)\) can next be split at \(x=4.5\). Its children have means \(10\) and \(0.05\), and their combined SSE is \(0+0.005=0.005\). The resulting three terminal-node predictions are \(0\) for \(x=1,2\), \(10\) for \(x=3,4\), and \(0.05\) for \(x=5,6\). Before the response revision, the three predictions after the additional split were \(0\) for \(x=1,2\), \(10\) for \(x=3,4\), and \(-0.05\) for \(x=5,6\). The early partition changes, even though in this particular tree the first four records end up in the same final groups.
Check. The first split changes from \(x\leq4.5\) to \(x\leq2.5\), and the stated totals are the smallest among the five candidate thresholds in their respective versions of the data. The revised response differs by only \(0.2\), but that is enough to reverse the first-split ranking.
Small Data Changes Can Also Alter Predictions Sharply
A changed threshold does not always produce a large prediction change. In the preceding example, the additional split led to similar final groups for most observed \(x\) values. In other samples, however, a changed first split places a group of observations into a different node, which changes the mean used to predict throughout that region. The next example distinguishes a fragile choice from a split with a clear score margin.
Worked Example: A Split With a Clear Error Margin
A hypothetical pension administrator fits a tree to an index of processing time. Four ordered training records have \(x=1,2,3,4\) and responses \(1,2,8,9\). Then a data correction changes the response at \(x=2\) from \(2\) to \(2.2\). Find the first split before and after the correction, and compare the terminal predictions.
Method. Compare the SSE totals for the three possible thresholds. Before correction, the threshold \(x=1.5\) gives a right-child SSE of \(149-19^2/3=86/3\), while the left child is a singleton. At \(x=2.5\), each pair has SSE \(0.5\), so the total is \(1\). At \(x=3.5\), the left group \((1,2,8)\) has SSE \(69-11^2/3=86/3\); the right child is a singleton. Thus \(x=2.5\) wins, with a margin of \(86/3-1=83/3\) over the next-best score.
After correction, at \(x=1.5\) the right group \((2.2,8,9)\) has sum \(19.2\), sum of squares \(149.84\), and SSE \(149.84-19.2^2/3=26.96\). At \(x=2.5\), the left group \((1,2.2)\) has mean \(1.6\) and SSE \(0.72\); the right group \((8,9)\) has SSE \(0.5\). The total is \(1.22\). At \(x=3.5\), the left group \((1,2.2,8)\) has SSE \(69.84-11.2^2/3=28.0267\), to four decimal places. Therefore, \(x=2.5\) remains the first split.
The terminal predictions are the child means. Before correction they are \(1.5\) for \(x\leq2.5\) and \(8.5\) for \(x>2.5\). After correction they are \(1.6\) and \(8.5\), respectively. The corrected best score, \(1.22\), remains far below the next-best score, \(26.96\). In this example, the data change affects one leaf mean but does not change the first partition.
Check. The winning threshold is \(x=2.5\) in both fits. The two sets of terminal predictions agree with the means of their corresponding child responses.
Common mistake avoided: concluding that every small response change must change the tree. Sensitivity depends on the relative split scores. Here, the corrected winning score is still well separated from its competitors.
Worked Example: Omitting One Record Changes the Root and a Prediction
Return to a hypothetical claim-cost index with ordered predictor values \(x=1,\ldots,6\) and responses \((0,0,10,10,0,-0.1)\). Compare the first split with the split after the final record is omitted. Consider the root-only tree so that the prediction at each \(x\) is the mean in its root child.
Method. With all six records, the candidate totals at \(x=2.5\) and \(x=4.5\) are \(101.0075\) and \(100.005\), respectively, as calculated in the first example. The other totals are \(120.808\), \(134.0067\), and \(120\). Thus the root split is \(x\leq4.5\). Its right-child mean is \((0-0.1)/2=-0.05\), so the root-only prediction at \(x=5\) is \(-0.05\).
After omitting the record at \(x=6\), the responses are \((0,0,10,10,0)\). At \(x=2.5\), the left child has SSE zero, and the right child \((10,10,0)\) has SSE \(200-20^2/3=200/3\), or \(66.6667\) to four decimal places. At \(x=1.5\), the right group \((0,10,10,0)\) has SSE \(200-20^2/4=100\). At \(x=3.5\), the left group \((0,0,10)\) has SSE \(200/3\), and the right pair \((10,0)\) has SSE \(50\), for a total of \(116.6667\). At \(x=4.5\), the left group has SSE \(100\), and the singleton has SSE zero. The first split is therefore \(x\leq2.5\).
The right-child mean in this root-only tree is now \((10+10+0)/3=20/3=6.6667\), to four decimal places. Thus the prediction at \(x=5\) changes from \(-0.05\) to \(6.6667\) when the last record is omitted. The omitted observation is only one of six records, yet it helped determine which observations were grouped together at the root.
Check. With all records, \(100.005<101.0075\), so the root is at \(x=4.5\). Without the final record, \(66.6667<100\), so the root is at \(x=2.5\). The two stated root-only predictions are the corresponding child means.
Common mistake avoided: assuming that a small change in sample composition must have a small effect on every prediction. Tree predictions are means within selected regions; changing the region membership can change the mean substantially.
How to Assess Instability
When evaluating a fitted tree, compare the first-split score with the runner-up and then check whether plausible small data changes reverse their order. If the winner has a narrow margin, treat the early split as fragile and inspect how later partitions depend on it. If the score margin is large, a small perturbation may change node means without changing the first split, as in the second example.
A useful sensitivity check is to refit after making a defensible small change, such as correcting a questionable response or omitting one record, and then compare:
- the selected first threshold and the observations assigned to each child;
- the later splits within the affected children;
- the terminal-node means and predictions in regions that changed membership.
This check describes how dependent the fitted tree is on particular observations. It does not replace a model assessment procedure, and it does not justify changing data merely to obtain a preferred tree. The data change must have a legitimate reason, and the original and altered fits should be interpreted in that context.
Common Exam Trap
A frequent error is to judge candidate splits by the sizes of their child means alone, or to compare only one child’s SSE. Neither procedure evaluates the split correctly. The criterion is the sum of both child SSEs; both groups contribute to the post-split error. In the first example, comparing only the right child at \(x=2.5\) would overlook the left child’s error in settings where that group is not constant, and could give the wrong ranking.
Another trap is to treat an unchanged first split as proof that the whole tree is unchanged. Even if the root remains fixed, a response change can alter which later split wins inside a child. Conversely, a changed root does not guarantee that every final prediction changes by a large amount. Trace the partitions and calculate the affected node means rather than inferring the consequences from the root threshold alone.
Check Your Understanding
For each problem, compare the relevant child SSE totals before deciding whether a split changes.
- A tree has ordered predictor values \(x=1,2,3,4\) and responses \((0,0,6,6)\). Find the SSE at each possible first split and identify the best threshold. (Answer: \(x=2.5\), with SSE \(0\); the other two totals are \(24\) each.)
- For responses \((1,3,7,9)\) at \(x=1,2,3,4\), calculate the total SSE at \(x=2.5\). Then change the response at \(x=2\) from \(3\) to \(3.2\); give the new total at that threshold. (Answer: \(2\) before the change and \(2.72\) after.)
- A two-leaf tree splits observations \((2,4)\) from \((8,10)\). Find both terminal predictions. If the response \(4\) is corrected to \(6\), with the split membership fixed, what are the new predictions? (Answer: \(3\) and \(9\) before; \(4\) and \(9\) after.)
- A one-dimensional training sample has \(x=1,2,3,4,5\) and responses \((0,0,9,9,0)\). Compare the total SSE at \(x=2.5\) with the total at \(x=4.5\). Which is smaller? (Answer: \(x=2.5\) has SSE \(54\); \(x=4.5\) has SSE \(81\), so \(x=2.5\) is better.)