Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach

Mim Van Den Bos, Jacobus G. M. Van Der Linden, Emir Demirović
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:48994-49007, 2024.

Abstract

Regression trees are a human-comprehensible machine-learning model that can represent complex relationships. They are typically trained using greedy heuristics because computing optimal regression trees is NP-hard. Contrary to this standard practice, we consider optimal methods and improve the scalability of optimal methods by developing three new dynamic programming approaches. First, we improve the performance of a piecewise constant regression tree method using a special algorithm for trees of depth two. Second, we provide the first optimal dynamic programming method for piecewise multiple linear regression. Third, we develop the first optimal method for piecewise simple linear regression, for which we also provide a special algorithm for trees of depth two. The experimental results show that our methods improve scalability by one or more orders of magnitude over the state-of-the-art optimal methods while performing similarly or better in out-of-sample performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-van-den-bos24a, title = {Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach}, author = {Van Den Bos, Mim and Van Der Linden, Jacobus G. M. and Demirovi\'{c}, Emir}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {48994--49007}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/van-den-bos24a/van-den-bos24a.pdf}, url = {https://proceedings.mlr.press/v235/van-den-bos24a.html}, abstract = {Regression trees are a human-comprehensible machine-learning model that can represent complex relationships. They are typically trained using greedy heuristics because computing optimal regression trees is NP-hard. Contrary to this standard practice, we consider optimal methods and improve the scalability of optimal methods by developing three new dynamic programming approaches. First, we improve the performance of a piecewise constant regression tree method using a special algorithm for trees of depth two. Second, we provide the first optimal dynamic programming method for piecewise multiple linear regression. Third, we develop the first optimal method for piecewise simple linear regression, for which we also provide a special algorithm for trees of depth two. The experimental results show that our methods improve scalability by one or more orders of magnitude over the state-of-the-art optimal methods while performing similarly or better in out-of-sample performance.} }
Endnote
%0 Conference Paper %T Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach %A Mim Van Den Bos %A Jacobus G. M. Van Der Linden %A Emir Demirović %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-van-den-bos24a %I PMLR %P 48994--49007 %U https://proceedings.mlr.press/v235/van-den-bos24a.html %V 235 %X Regression trees are a human-comprehensible machine-learning model that can represent complex relationships. They are typically trained using greedy heuristics because computing optimal regression trees is NP-hard. Contrary to this standard practice, we consider optimal methods and improve the scalability of optimal methods by developing three new dynamic programming approaches. First, we improve the performance of a piecewise constant regression tree method using a special algorithm for trees of depth two. Second, we provide the first optimal dynamic programming method for piecewise multiple linear regression. Third, we develop the first optimal method for piecewise simple linear regression, for which we also provide a special algorithm for trees of depth two. The experimental results show that our methods improve scalability by one or more orders of magnitude over the state-of-the-art optimal methods while performing similarly or better in out-of-sample performance.
APA
Van Den Bos, M., Van Der Linden, J.G.M. & Demirović, E.. (2024). Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:48994-49007 Available from https://proceedings.mlr.press/v235/van-den-bos24a.html.

Related Material