Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees
<|reference_start|>Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees: Decision Tree (DT) Learning is a fundamental problem in Interpretable Machine Learning, yet it poses a formidable optimisation challenge. Despite numerous efforts dating back to the early 1990's, practical algorithms have only recently emerged, primarily leveraging Dynamic Programming (DP) and Branch & Bound (B&B) techniques. These methods fall into two categories: algorithms like DL8.5, MurTree and STreeD utilise an efficient DP strategy but lack effective bounds for pruning the search space; while algorithms like OSDT and GOSDT employ more efficient pruning bounds but at the expense of a less refined DP strategy. We introduce Branches, a new algorithm that combines the strengths of both approaches. Using DP and B&B with a novel analytical bound for efficient pruning, Branches offers both speed and sparsity optimisation. Unlike other methods, it also handles non-binary features. Theoretical analysis shows its lower complexity compared to existing methods, and empirical results confirm that Branches outperforms the state-of-the-art in speed, iterations, and optimality.<|reference_end|>
@article{chaouki2024branches:,
    title={Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for
  Optimal Decision Trees},
    author={Ayman Chaouki, Jesse Read, Albert Bifet},
    journal={arXiv preprint arXiv:2406.02175},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.02175},
    primaryClass={cs.LG}
}