Optimal Sparse Regression Trees
Rui Zhang, Rui Xin, Margo Seltzer, Cynthia Rudin
Abstract
Regression trees are one of the oldest forms of AI models, and their predictions can be made without a calculator, which makes them broadly useful, particularly for high-stakes applications. Within the large literature on regression trees, there has been little effort towards full provable optimization, mainly due to the computational hardness of the problem. This work proposes a dynamic programming-with-bounds approach to the construction of provably-optimal sparse regression trees. We leverage a novel lower bound based on an optimal solution to the k-Means clustering algorithm on one dimensional data. We are often able to find optimal sparse trees in seconds, even for challenging datasets that involve large numbers of samples and highly-correlated features.
BibTeX
@article{Zhang_Xin_Seltzer_Rudin_2023, title={Optimal Sparse Regression Trees}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26334}, DOI={10.1609/aaai.v37i9.26334}, abstractNote={Regression trees are one of the oldest forms of AI models, and their predictions can be made without a calculator, which makes them broadly useful, particularly for high-stakes applications. Within the large literature on regression trees, there has been little effort towards full provable optimization, mainly due to the computational hardness of the problem. This work proposes a dynamic programming-with-bounds approach to the construction of provably-optimal sparse regression trees. We leverage a novel lower bound based on an optimal solution to the k-Means clustering algorithm on one dimensional data. We are often able to find optimal sparse trees in seconds, even for challenging datasets that involve large numbers of samples and highly-correlated features.}, number={9}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Zhang, Rui and Xin, Rui and Seltzer, Margo and Rudin, Cynthia}, year={2023}, month={Jun.}, pages={11270-11279} }