Blossom: an Anytime Algorithm for Computing Optimal Decision Trees

Emir Demirović, Emmanuel Hebrard, Louis Jean
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:7533-7562, 2023.

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 this Paper

BibTeX
@InProceedings{pmlr-v202-demirovic23a, title = {Blossom: an Anytime Algorithm for Computing Optimal Decision Trees}, author = {Demirovi\'{c}, Emir and Hebrard, Emmanuel and Jean, Louis}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {7533--7562}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/demirovic23a/demirovic23a.pdf}, url = {https://proceedings.mlr.press/v202/demirovic23a.html}, 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.} }
Endnote
%0 Conference Paper %T Blossom: an Anytime Algorithm for Computing Optimal Decision Trees %A Emir Demirović %A Emmanuel Hebrard %A Louis Jean %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-demirovic23a %I PMLR %P 7533--7562 %U https://proceedings.mlr.press/v202/demirovic23a.html %V 202 %X 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.
APA
Demirović, E., Hebrard, E. & Jean, L.. (2023). Blossom: an Anytime Algorithm for Computing Optimal Decision Trees. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:7533-7562 Available from https://proceedings.mlr.press/v202/demirovic23a.html.

Related Material