Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*

Decision Tree (DT) Learning is a fundamental problem in Interpretable Machine Learning, yet it poses a formidable optimisation challenge. Practical algorithms have recently emerged, primarily leveraging Dynamic Programming and Branch \& Bound. However, most of these approaches rely on a Depth-First-Search strategy, which is inefficient when searching for DTs at high depths and requires the definition of a maximum depth hyperparameter. Best-First-Search was also employed by other methods to circumvent these issues. The downside of this strategy is its higher memory consumption, as such, it has to be designed in a fully efficient manner that takes full advantage of the problem's structure. We formulate the problem as an AND/OR graph search which we solve with a novel AO*-type algorithm called Branches. We prove both optimality and complexity guarantees for Branches and we show that it is more efficient than the state of the art theoretically and on a variety of experiments. Furthermore, Branches supports non-binary features unlike the other methods, we show that this property can further induce larger gains in computational efficiency.

Decision Trees are flowchart-like predictive models that are easy to interpret for humans. Such interpretability is very important in sensitive domains such as healthcare and the criminal justice system. However, while this property is very popular, finding Decision Trees that optimally balance between accuracy and interpretability is a highly difficult task. The current proposed methods either consume too much time or too much memory or both, making them difficult to scale for large datasets. To address this issue, we introduce Branches, a new algorithm that seeks these optimal Decision Trees efficiently. This efficiency allows Branches to quickly find optimal solutions in settings that can be challenging for the state of the art. Furthermore, our work paves the way for promising future research directions aimed at enhancing the scalability of optimal decision tree learning to large datasets.