Blossom: An Anytime Algorithm for Computing Optimal Decision Trees
Abstract
We propose a simple algorithm to learn optimal decision trees of bounded depth. This algorithm is essentially an anytime version of the state-of-the-art dynamic programming approach. It has virtually no overhead compared to heuristic methods and is comparable to the best exact methods to prove optimality on most data sets. Experiments show that whereas existing exact methods hardly scale to deep trees, this algorithm learns trees comparable to standard heuristics without computational overhead, and can significantly improve their accuracy when given more computation time, even for deep trees.
Cite
Text
Demirović et al. "Blossom: An Anytime Algorithm for Computing Optimal Decision Trees." International Conference on Machine Learning, 2023.Markdown
[Demirović et al. "Blossom: An Anytime Algorithm for Computing Optimal Decision Trees." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/demirovic2023icml-blossom/)BibTeX
@inproceedings{demirovic2023icml-blossom,
title = {{Blossom: An Anytime Algorithm for Computing Optimal Decision Trees}},
author = {Demirović, Emir and Hebrard, Emmanuel and Jean, Louis},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {7533-7562},
volume = {202},
url = {https://mlanthology.org/icml/2023/demirovic2023icml-blossom/}
}