Search Strategies for Optimal Classification and Regression Trees

Learning Optimal Decision Trees (ODTs) is an NP-hard problem, leading to a proliferation of specialized search algorithms. While these methods aim to improve scalability, they often rely on distinct, isolated techniques, making it difficult to determine which algorithmic components actually drive performance gains. The authors address this by developing a general, unified algorithmic framework that instantiates various search strategies—including depth-first, best-first, and AND-OR search—within a single, consistent structure. This framework allows for a principled, empirical comparison of 18 different search strategies across both classification and regression tasks.

The framework models ODT construction as an AND-OR search tree, where OR nodes represent branching decisions and AND nodes combine subproblems. The search process is governed by three core procedures: Select (choosing the next node to expand), Expand (adding new nodes to the search tree), and BackPropagate (updating bounds and pruning the search space). By modularizing these components, the authors can isolate the impact of different priority orderings and heuristics, providing a common lens to evaluate methods that were previously studied in isolation.

The study demonstrates that the choice of search strategy has a profound impact on both runtime and solution quality. For classification tasks, the best-performing strategy provides superior anytime performance, meaning it finds high-quality solutions faster than existing state-of-the-art approaches. For regression tasks, the framework achieves runtime improvements of more than an order of magnitude. The results highlight that simple heuristics, such as prioritizing nodes with smaller support and lower bounds, can be highly effective, challenging some of the more complex strategies proposed in recent literature.