Why Put Limits on Tree Growth?
A regression tree grows by splitting a predictor-space region into smaller regions. In each terminal region, it predicts the mean response among the training observations there. Splitting can reduce training squared error, but a rule that allows every possible split can produce a very large tree. Stopping rules constrain growth by specifying when a node is eligible to split and when a proposed split is adequate.
These rules are applied during recursive construction: at a node, first check whether splitting is permitted, then check whether a candidate split satisfies the required constraints. A node that fails a stopping condition remains terminal. The constraints are distinct, so a split with a large error reduction can still be disallowed by a size or depth rule.
Four Common Stopping Constraints
Use depth to describe a node’s position in the tree. Here, the root has depth 0, its two children have depth 1, and each further split increases the depth by 1. A stated maximum depth \(D_{\max}\) means nodes at depth \(D_{\max}\) may not split. This convention should be checked whenever a question gives a depth value, since software or problem statements can use different conventions.
A minimum node size for splitting is a requirement that the node itself contain at least a specified number of observations before it may be considered for splitting. A minimum leaf size is a requirement that each child resulting from a proposed split contain at least a specified number of observations. One condition concerns the parent node; the other concerns both children.
For a proposed split, let \(\operatorname{SSE}(t)\) be the sum of squared deviations from the mean response in parent node \(t\). Let \(t_L\) and \(t_R\) be its two child nodes. The split’s absolute error reduction is
A minimum error-reduction rule requires \(\Delta(t)\) to meet a stated threshold. Unless a problem says otherwise, treat this as an absolute reduction measured in squared-response units, and require \(\Delta(t)\geq \Delta_{\min}\). Some procedures instead specify a relative reduction, such as a fraction of the parent error. The threshold’s definition and units must therefore be read carefully.
A candidate split is allowed only if it satisfies every applicable condition: the node is shallow enough to split, its size is sufficient, both children meet the minimum leaf size, and its error reduction meets the threshold. If the tree-building procedure chooses the best valid split at a node, that choice is made only among candidates that pass these constraints.
Why Splitting Reduces Training Error
The error-reduction formula follows from the fact that splitting a node replaces one fitted mean with two child means. In a node containing responses \(y_1,\ldots,y_n\), write \(\bar y\) for their mean. For a proposed partition into left and right children with sizes \(n_L,n_R\) and means \(\bar y_L,\bar y_R\), the parent sum of squared errors can be decomposed as follows:
To see why, for an observation in the left child write \(y_i-\bar y=(y_i-\bar y_L)+(\bar y_L-\bar y)\), and expand the square. The cross-product sums to zero because \(\sum_{i\in L}(y_i-\bar y_L)=0\). The same argument applies to the right child. The final two terms are nonnegative, so the parent error is at least the sum of the child errors. In particular,
This explains why an unconstrained split cannot increase training within-node squared error when each node predicts its own sample mean. It does not imply that every split should be accepted: stopping rules can reject a nonnegative reduction that is too small or that produces an impermissibly small child.
Worked Example: Applying Depth and an Error Threshold
A hypothetical model predicts claim amounts using a regression tree. At the root, there are 20 observations and the parent SSE is 200. A candidate split creates children with 9 and 11 observations and SSEs 80 and 90. The constraints are maximum depth 2, minimum node size 8, minimum leaf size 5, and minimum absolute error reduction 5. At the left child, a proposed split would create child sizes 4 and 5 with SSEs 30 and 45. At the right child, a proposed split would create sizes 6 and 5 with SSEs 40 and 44. Decide which nodes split, assuming these are the candidates under consideration.
Method. Check each candidate against every applicable constraint, using depth 0 for the root. A node at depth 2 cannot split.
Root. The root has size 20, which is at least 8. The proposed children have sizes 9 and 11, both at least 5. Its error reduction is \(200-(80+90)=30\), and \(30\geq 5\). Therefore the root splits.
Left child. It is at depth 1, has size 9 (at least 8), and its proposed children have sizes 4 and 5 (both at least 5 is false). Its error reduction would be \(80-(30+45)=5\), which meets the reduction threshold, but the child of size 4 violates minimum leaf size. The left child does not split.
Right child. It is at depth 1 and has size 11, so it passes the node-size condition. Its proposed children have sizes 6 and 5, so they pass the minimum leaf condition. Its error reduction is \(90-(40+44)=6\), which meets the threshold. The right child splits, producing nodes at depth 2. Those nodes cannot split because the maximum depth is 2.
Check. The resulting tree has a root split and a split at the right child only. The left candidate passes the error threshold but fails the leaf-size rule; the right candidate passes the applicable rules and reaches, but does not exceed, the maximum depth. The mistake to avoid is treating a sufficient error reduction as permission to ignore a different stopping constraint.
Separate Node Eligibility From Child Eligibility
Minimum node size and minimum leaf size are easy to confuse. Suppose a rule requires a node to contain at least 10 observations before splitting. A node with 9 observations is not eligible, even if a proposed partition could produce children that each meet a minimum leaf size of 3. Conversely, a node may have enough observations to be eligible but still have no acceptable split because every candidate puts too few observations in one child.
This distinction is especially important when a question provides split summaries. The node’s count determines whether it can be considered; the two child counts determine whether a particular split can be used. A high error reduction does not repair a failure of either count requirement.
Worked Example: A Large Gain Does Not Rescue an Invalid Child
A node has 10 observations and parent SSE 90. The minimum node size is 10, the minimum leaf size is 3, and the minimum absolute error reduction is 12. Two candidate splits are reported. Candidate A creates child sizes 2 and 8 with SSEs 8 and 20. Candidate B creates child sizes 4 and 6 with SSEs 35 and 40. Determine which split is permitted.
Method. Check parent eligibility, then child sizes, then calculate the error reduction for each candidate that meets the size conditions.
The node has 10 observations, so it meets the minimum node size exactly and is eligible to consider splits. Candidate A has error reduction \(90-(8+20)=62\), but its child of size 2 is smaller than the required 3. Candidate A is invalid regardless of its large gain.
Candidate B has child sizes 4 and 6, both at least 3. Its reduction is \(90-(35+40)=15\), and \(15\geq12\). Candidate B is permitted. Since the given rules do not include a requirement to choose the candidate with the largest reduction, the question asks only which candidates pass; here, only Candidate B passes.
Check. Candidate B reduces the parent SSE from 90 to \(35+40=75\), a reduction of 15. It satisfies the parent-size, child-size, and error-reduction conditions. The common mistake is choosing Candidate A solely because its reduction is larger.
Applying Several Rules in Sequence
In practice, a clean decision sequence avoids mixing up the different conditions. Start with rules that make the node ineligible, such as maximum depth or minimum node size. Then assess whether each proposed split produces sufficiently large children. Only after those checks, compare the split’s error reduction with its threshold. A candidate that fails at any stage is rejected.
Stop if its depth has reached the maximum or its observation count is below the minimum size required for splitting.
For a proposed split, verify that both resulting nodes meet the minimum leaf size.
Subtract the sum of the two child SSEs from the parent SSE.
Accept the candidate only if its reduction meets the stated absolute or relative requirement.
If several candidates pass, the rule for selecting among them must also be stated or provided by the problem. Stopping constraints define which splits are allowed; by themselves, they do not say how to rank multiple allowed candidates.
Worked Example: Combining Size and Minimum Reduction Rules
A hypothetical tree predicts repair costs. The root has 16 observations and SSE 100. Its proposed split produces two nodes of size 8, with SSEs 50 and 42. The minimum node size is 8, the minimum leaf size is 4, and the minimum absolute reduction is 6. At the left child, the only candidate split creates sizes 3 and 5. At the right child, a candidate split creates sizes 4 and 4, with child SSEs 35 and 5; the right child’s SSE before splitting is 42. The maximum depth is 3. Decide which nodes split.
Method. Apply the conditions in sequence at the root and then at each child.
Root. Its size is 16, at least 8. Its children have sizes 8 and 8, both at least 4. The reduction is \(100-(50+42)=8\), and \(8\geq6\). Therefore, the root splits.
Left child. Its size is 8, so it is eligible under the minimum node-size rule, and it is at depth 1, below the maximum depth. However, its only candidate creates a child of size 3, which is below the minimum leaf size of 4. The left child does not split.
Right child. Its size is also 8 and its candidate children each have size 4, so it passes both size checks. Its reduction is \(42-(35+5)=2\), and \(2<6\). The right child does not split.
Check. Only the root splits. The left child has no candidate satisfying minimum leaf size, and the right child’s reduction is \(42-(35+5)=2<6\). The maximum-depth rule does not prevent either child from being considered here; the decisive failures are the leaf-size and reduction rules.
Absolute and Relative Thresholds
An absolute reduction threshold is expressed in the units of SSE. If the response scale changes, its squared-error scale changes too, so the same numerical threshold may no longer have the same practical meaning. A relative threshold instead compares the reduction with the parent error. For example, if a rule requires at least 10% reduction, the condition is
The positive-parent-error condition matters: if the parent SSE is zero, this relative ratio is undefined, and the procedure must specify how to handle that case. Do not substitute a relative calculation for an absolute threshold or vice versa. If the stated rule says “reduce SSE by at least 6,” compare the reduction itself with 6; if it says “reduce SSE by at least 10%,” compare the ratio with 0.10.
Common Stopping-Rule Errors
- Checking only the gain. A large reduction cannot override a maximum-depth, minimum-node-size, or minimum-leaf-size restriction.
- Using the wrong node count. Minimum node size applies to the node being considered; minimum leaf size applies separately to both children of a proposed split.
- Comparing child SSE with the threshold. The absolute reduction is parent SSE minus the sum of child SSEs, not the SSE of either child alone.
- Reversing the subtraction. Compute \(\operatorname{SSE}(t)-\{\operatorname{SSE}(t_L)+\operatorname{SSE}(t_R)\}\), not the child total minus the parent SSE.
- Ignoring equality. If the condition is “at least” a threshold, equality passes: \(\Delta(t)=\Delta_{\min}\) is sufficient.
- Assuming a split must happen. A node can be eligible to split but remain terminal if no candidate satisfies all the requirements.
Stopping rules are useful because they make the construction of a tree more controlled: they limit how far partitioning proceeds and prevent splits that fail specified size or error-reduction requirements. They do not, by themselves, guarantee that the resulting tree is best for a separate evaluation criterion. For decisions on an exam, keep the scope precise: determine eligibility and apply the given conditions, without inferring an unstated rule.
Check Your Understanding
For each problem, apply only the stopping rules stated. Assume depth 0 for the root and that an error-reduction threshold is met when the reduction is equal to it.
- A root at depth 0 has SSE 70. A candidate split produces child SSEs 31 and 35, with child sizes 6 and 7. The maximum depth is 1, the minimum leaf size is 5, and the minimum reduction is 4. Does the root split? (Answer: Yes. The reduction is \(70-(31+35)=4\), both children meet minimum leaf size, and the root is below the maximum depth.)
- A node contains 8 observations. The minimum node size for splitting is 9. A proposed split would create child sizes 4 and 4 and reduce SSE by 20. Can it split? (Answer: No. Its parent node has fewer than 9 observations, regardless of the child sizes and reduction.)
- A node has SSE 64. A candidate creates child SSEs 27 and 29, with both child sizes at least the required minimum. The minimum absolute reduction is 8, and depth and node-size rules permit splitting. Is the candidate accepted? (Answer: Yes. The reduction is \(64-(27+29)=8\), which meets the threshold exactly.)
- A root split is permitted and creates left and right children. The left child’s only candidate violates minimum leaf size. The right child has parent SSE 42 and candidate child SSEs 35 and 5. The minimum reduction is 6. Which nodes split after the root? (Answer: Neither child splits. The left child fails minimum leaf size, and the right child’s reduction is \(42-(35+5)=2<6\).)
- A node has SSE 80, and a size-valid candidate would reduce its SSE by 8. The rule requires a relative reduction of at least 10%, and the parent SSE is positive. Does the candidate meet the threshold? (Answer: Yes. Its relative reduction is \(8/80=0.10\), exactly 10%.)