Learned Look-Ahead Splitting Rule for CART

1 Introduction

• Greedy CART can reject a locally weak split even when it enables a substantially better subtree, as in the interaction-driven XOR example.In the noiseless example, either first split has no population-level squared-error gain, while the subsequent split perfectly separates the response regions.Source: §1 · p. 1

1.1 Review of Regular CART

• For continuous outcomes, CART recursively partitions covariate space into leaves with constant predictions, choosing each split for its immediate reduction in squared prediction error.Tree growth stops when a condition such as maximum depth, minimum leaf size, or minimum improvement is met.Source: §1.1 · pp. 2–3

Algorithm 1: Regular CART for a continuous outcome

• After growing a large tree, CART may prune branches to simplify it; cost-complexity pruning removes the branch with the smallest empirical-risk increase per terminal leaf removed.The final tree may be selected from the resulting subtree sequence using BIC or cross-validation.Source: Algorithm 1: Regular CART for a… · pp. 3–4

Algorithm 2: Look-ahead CART for a continuous outcome

• For each candidate, the method forces the split, grows conventional CART subtrees on both children, and selects the split with the greatest resulting error reduction.The selected split is applied and the procedure repeats until all leaves are terminal.Source: Algorithm 2: Look-ahead CART for a… · p. 5

2 Look-Ahead Method

• Look-ahead CART prioritizes splits for the prediction-error improvement attainable downstream, retaining CART’s recursive structure and interpretability.The approach may be especially beneficial for hierarchical or interaction-driven signals.Source: §2 · p. 4, Algorithm 2: Look-ahead CART for a… · p. 5

Algorithm 2: Look-ahead CART for a continuous outcome

• Full look-ahead is computationally burdensome because it grows two CARTs for every candidate split at each node.The paper suggests early stopping of downstream trees or limiting candidate splits per predictor to reduce cost.Source: Algorithm 2: Look-ahead CART for a… · p. 5

3 Smart Look-Ahead Method

• The method estimates a candidate split’s downstream improvement from node-level features, avoiding explicit subtree growth for each candidate.A learner predicts the improvement associated with a split using features derived from the node and split.Source: §3 · pp. 5–6

Algorithm 3: Training the learned look-ahead value model

• Bootstrap CART trees supply training examples pairing node features with the proportion of variation explained by each node’s subtree.The feature set includes node sample size and depth, correlations between the outcome and predictors, and variation explained by depth-1 and depth-2 greedy CARTs.Source: §3 · p. 6
• The auxiliary learner’s accuracy in predicting downstream improvements from node characteristics determines the smart algorithm’s effectiveness.Source: Algorithm 3: Training the learned… · p. 7
• After offline training, evaluating candidate splits is typically faster than growing downstream CARTs, but training overhead may outweigh savings for one small-data analysis.The method is particularly appealing for large trees with extensive split searches.Source: Algorithm 3: Training the learned… · p. 7

4 Theoretical Properties

• The comparison establishes a finite-sample relationship for training empirical risk, but does not order out-of-sample prediction risks.Source: §4 · p. 7
• The comparison assumes unpruned growth with shared split candidates, leaf-size and depth limits, stopping rules, and deterministic tie-breaking.Stopping rules are local to each node, and exact look-ahead evaluations grow candidate trees to completion using conventional CART.Source: §4 · p. 7
• With local stopping rules, minimizing candidate completion risk is equivalent to maximizing the local look-ahead improvement.Source: §4 · p. 8

T GD = CGD(T0)

• The exact full look-ahead tree has training MSE no greater than the conventional tree.The theorem compares terminal-tree training risks.Source: T GD = CGD(T0) · p. 8
• The exact full-look-ahead theorem does not generally extend to limited-depth look-ahead, pruning, or out-of-sample prediction risk.Source: T GD = CGD(T0) · p. 8
• With approximation error at most ε, smart look-ahead's exact improvement is at most 2ε below the exact choice at each split.Across the M splits, this yields a finite-sample training-risk bound relative to conventional CART.Source: T GD = CGD(T0) · p. 9
• Under the local stopping rules, maximizing look-ahead improvement is equivalent to minimizing the conventional completion risk of a candidate action.Source: T GD = CGD(T0) · p. 9

Simulation design

• A simulation study compares conventional greedy CART, full look-ahead CART, and smart look-ahead CART with learned split values for prediction accuracy across four settings, using independent predictors, noise features, and trees capped at depth 6.Source: §5 · pp. 9–10

Simulation results

• In the first three interaction settings, look-ahead methods substantially outperformed conventional CART, and Smart LA 2 performed similarly to or better than full look-ahead.These results summarize 400 repetitions per setting at n = 1000; pruning did not materially change the pattern but helped stabilize predictive performance.Source: §5 · p. 10, Figure 1 · p. 11
• Smart LA 1 underperformed full look-ahead but still beat conventional CART, while Smart LA 2 incurred higher computational cost than Smart LA 1.Smart LA 1’s weaker performance was also reflected in the lower R2 of its auxiliary random-forest model.Source: §5 · pp. 10–11
• In the interaction-free fourth setting, all methods performed similarly and conventional CART was slightly better, consistent with look-ahead offering no particular advantage there.The four settings are summarized in Figure 1 as test-set MSE distributions.Source: §5 · p. 11, Figure 1 · p. 11

Computational comparison

• As candidate cutoffs increased, smart look-ahead became substantially faster because full look-ahead repeatedly fits subtrees for candidate splits.With few cutoffs, full look-ahead was faster because training the smart method’s auxiliary model outweighed its scoring savings.Source: §5 · p. 11, Figure 2 · p. 13

6 Example

• The two real-data examples compare full and smart look-ahead methods with conventional CART using repeated 80/20 random train–test splits because the data-generating mechanism is unknown.Each example includes both smart variants, with and without BIC-based pruning.Source: §6 · p. 13, §6.1 · p. 14, §6.2 · p. 16

6.1 Parkinsons Telemonitoring

• The Parkinson’s analysis used 100 observation-level 80/20 train–test partitions and excluded subject ID and time since baseline from predictors.The dataset includes 5,875 observations from 42 individuals with early-stage Parkinson’s disease.Source: §6.1 · pp. 13–14
• For both motor and total UPDRS, full look-ahead achieved the lowest mean test MSE; Smart LA 2 beat conventional CART on both outcomes, while Smart LA 1 was similar on motor and worse on total UPDRS.Pruning had little effect on mean test MSE across methods.Source: §6.1 · p. 14, Figure 3 · p. 14, Table 2 · p. 15
• Patient-level cross-validation produced much larger test error than training error, indicating the trees were more suitable for updated UPDRS prediction in existing patients than for prediction in new patients.Observation-level validation may be overly optimistic for evaluating new-patient prediction because each patient contributes multiple observations.Source: §6.1 · p. 15

6.2 Concrete Compressive Strength

• The concrete-strength example uses 1,030 observations with eight predictors and evaluates methods over 100 independent 80/20 train–test partitions.Ten candidate splits per predictor were considered.Source: §6.2 · pp. 15–16
• For concrete compressive strength, full look-ahead achieved lower training and test MSE than conventional CART; Smart LA 1 modestly reduced both, while Smart LA 2 yielded larger reductions and performed closer to full look-ahead.Figure 4 shows test-MSE distributions across 100 independent train–test partitions; Table 3 reports means across 100 repetitions.Source: §6.2 · p. 16, Figure 4 · p. 16, Table 3 · p. 16

• Simulations suggest look-ahead splitting can improve prediction in interaction-driven settings, with smart look-ahead retaining much of the benefit when many candidate splits are evaluated.Source: §7 · p. 17
• The framework resembles approximate dynamic programming: splits are actions, prediction-error reductions are rewards, and smart look-ahead approximates a split’s long-term value.The authors suggest future policy-improvement approaches could use full look-ahead near the root and cheaper methods deeper in the tree.Source: §7 · p. 17
• The framework can use other outcome criteria, but scalability, auxiliary-model overfitting, pruning, out-of-sample guarantees, and rollout depth remain open questions.Source: §7 · p. 17

• The simulation tables cover four settings at n=500 and n=2000, with 400 repetitions and metrics for training/test MSE, leaves, and RF R2.They compare Conventional, Full LA, Smart LA 1, and Smart LA 2.Source: Table 4 · p. 19, Table 5 · p. 20
• The full look-ahead figures show unpruned final regression trees for motor UPDRS, total UPDRS, and Concrete Compressive Strength.Each tree uses all observations.Source: Figure 5 · p. 21, Figure 7 · p. 22, Figure 9 · p. 23
• The second smart look-ahead figures show unpruned final regression trees for motor UPDRS, total UPDRS, and Concrete Compressive Strength.Each tree uses all observations.Source: Figure 6 · p. 21, Figure 8 · p. 22, Figure 10 · p. 24