Generalized and Scalable Optimal Sparse Decision Trees

Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, Margo Seltzer
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:6150-6160, 2020.

Abstract

Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find optimal decision trees. These new techniques have the potential to trigger a paradigm shift, where, it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions, without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several order of magnitude relative to the state-of-the art.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-lin20g, title = {Generalized and Scalable Optimal Sparse Decision Trees}, author = {Lin, Jimmy and Zhong, Chudi and Hu, Diane and Rudin, Cynthia and Seltzer, Margo}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {6150--6160}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/lin20g/lin20g.pdf}, url = {https://proceedings.mlr.press/v119/lin20g.html}, abstract = {Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find optimal decision trees. These new techniques have the potential to trigger a paradigm shift, where, it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions, without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several order of magnitude relative to the state-of-the art.} }
Endnote
%0 Conference Paper %T Generalized and Scalable Optimal Sparse Decision Trees %A Jimmy Lin %A Chudi Zhong %A Diane Hu %A Cynthia Rudin %A Margo Seltzer %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-lin20g %I PMLR %P 6150--6160 %U https://proceedings.mlr.press/v119/lin20g.html %V 119 %X Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find optimal decision trees. These new techniques have the potential to trigger a paradigm shift, where, it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions, without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several order of magnitude relative to the state-of-the art.
APA
Lin, J., Zhong, C., Hu, D., Rudin, C. & Seltzer, M.. (2020). Generalized and Scalable Optimal Sparse Decision Trees. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:6150-6160 Available from https://proceedings.mlr.press/v119/lin20g.html.

Related Material