A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees
Authors: Chenxuanyin Zou, Jiayang Ren, Qiangqiang Mao, Jing Liu, Marcus Lai, Yankai Cao
Organizations: Department of Chemical and Biological Engineering University of British Columbia · Department of Electrical and Computer Engineering University of British Columbia · Department of Computer Science University of British Columbia
Despite the importance for interpretability, decision trees face severe scalability challenges. Existing global optimal methods are often limited by binary feature selection and shallow tree depths, whereas traditional heuristic approaches frequently sacrifice predictive accuracy. To overcome these limitations, this paper proposes a moving-horizon approximate branch-and-reduce method to train near-optimal deep classification trees on large-scale datasets with continuous features. Built on a hierarchical root-subtree optimization framework, the method solves the root-level problem via branch-and-reduce while approximating the induced subtree problem using greedy heuristics. Although the underlying framework is capable of guaranteeing global optimality, the approximation, which functions as a lookahead rollout in a reinforcement learning context, significantly boosts efficiency for deeper structures. A low-cost moving-horizon strategy is then employed to iteratively refine model accuracy. Extensive numerical results demonstrate that our method exceeds the testing accuracy of existing heuristic baselines while offering significantly greater scalability, in terms of both dataset size and tree depth, than global optimal solvers.
Figures & tables
Figure 1: Illustration of the Child-Subtree Approximation via RL ( x denotes the state).
Figure 2: An example of MH when d=4 .
Figure 3: Average training time across 51 small datasets on a logarithmic scale. CART and DPDT remain the fastest methods, whereas Quant-BnB and DL8.5 exhibit sharp runtime growth with depth. MHABR is slower than the heuristic baselines but scales more moderately than the global optimization baselines, requiring 26.99s at depth 8, compared with 167.2s for DL8.5 and 236.7s for LS-OCT .
Figure 4: Training/testing accuracy vs. tree depth/running time on Avila
Figure 5: Training/testing accuracy vs. tree depth/running time on Eeg
Figure 6: Training and testing accuracy of 51 small datasets across d=2,3,4,8 .
Figure 7: Theoretical relationships in terms of optimality between our algorithms and other global optimal methods
Figure 8: Ablation study of MHABR on Avila using a depth-8 tree. For instance, the depth-8 subtree represents the complete original tree, while the depth-7 subtrees are rooted at nodes 2 and 3. Similarly, the depth-6 subtrees are rooted at nodes 4, 5, 6, and 7, and this pattern continues for the other depths. (a) layer-wise improvements in training accuracy from MH refinement; (b) runtime with and without the reduction strategy across subtree depths; (c) effect of the termination tolerance ϵ ; and (d) effect of the mini-batch ratio θ .
Symbol
Description
Data and decision-tree notation
{(xi,yi)}i=1n
Dataset of n feature–label pairs.
Y
Set of class labels.
n , p , nc
Numbers of samples, features, and classes, respectively.
[n]
Index set {1,…,n} .
I⊆[n]
Index set of samples in a tree or subtree.
Table 7: Summary of notation used in this paper.
Dataset
Depth
Train
Test
TAO
MHABR
TAO
MHABR
Balance-scale
d=2
72.5 (1.6)
72.7 (0.7)
69.5 (2.9)
68.5 (2.0)
d=3
76.9 (1.1)
76.8 (1.4)
71.6 (1.9)
74.8 (2.2)
d=4
84.0 (1.5)
84.1 (1.1)
79.8 (3.1)
78.9 (2.7)
Banknote-auth.
d=2
91.9 (0.4)
92.8 (0.4)
90.6 (0.9)
91.3 (1.1)
d=3
96.0 (0.5)
98.3 (0.4)
95.7 (1.2)
97.2 (0.6)
Table 8: Performance comparison between TAO and MHABR . Results are reported as mean accuracy with standard deviation in parentheses. Best results for each dataset, depth, and split are highlighted in bold.
Figure 9: Illustration of a canonical XOR failure mode. A depth-1 greedy split may fail to separate the classes, whereas a depth-2 lookahead can recover the correct interaction structure.
Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.
Jiancheng Tu, Wenqi Fan
Department of Computing, The Hong Kong Polytechnic University · Department of Management and Marketing, The Hong Kong Polytechnic University
Optimal decision trees (ODTs) are compact, interpretable machine learning models that globally optimize a given objective, but their scalability remains challenging. While recent work has proposed a variety of search strategies to improve scalability, the precise contribution of each strategy remains unclear. To address this gap, we introduce a general algorithmic framework for ODTs that instantiates previously used search strategies and enables the definition of new ones. This provides a common lens through which to understand and compare different strategies, which we use to empirically investigate the effect of 18 search strategies. Compared to the state of the art, the best strategy in our evaluation achieves significantly better anytime performance for classification, and improves runtime by more than an order of magnitude for regression.
Jacobus G. M. van der Linden, Mim van den Bos, Emir Demirović
Decision trees are attractive for tabular prediction tasks because each prediction follows an interpretable sequence of feature-threshold tests. Under a strict maximum-depth budget, however, conventional binary trees can be under-expressive, since each internal node makes only a single threshold decision. We study shallow-depth tree induction, where the goal is to improve accuracy while keeping root-to-leaf paths short. We propose the Multi-Branch Neural Decision Tree with Adaptive Pruning (MBNDT), a single axis-aligned tree trained end-to-end with differentiable multi-way splits. Each internal node learns ordered thresholds over a selected feature and a branch mask that adapts its effective arity, and the trained model is converted to a deterministic single-path tree for inference. Across 21 OpenML binary-classification benchmarks, MBNDT achieves the best average rank and mean balanced accuracy among depth-constrained single-tree baselines; a controlled ablation isolates multi-way splitting as the source of the gain. These gains come with an explicit trade-off: MBNDT realizes more leaves than the other single-tree baselines, making it best suited when accuracy under short, bounded decision paths is prioritized over minimal global tree size.
Hanul Park, Jeonghoon Choi, Juseong Kim +2
Department of Information Convergence Engineering, Pusan National University, Busan, Rep. of Korea · School of Computer Science and Engineering, Pusan National University, Busan, Rep. of Korea