Optimal Regression Trees via Dynamic Programming

Optimal Regression Trees via Dynamic Programming: Optimization techniques for learning Regression Trees

van den Bos, Mim (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics; TU Delft Software Technology)

Demirović, E. (mentor)
van der Linden, J.G.M. (mentor)
Kulahcioglu Ozkan, Burcu (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2023-06-22

Decision trees make decisions in a way interpretable to humans, this is important when machines are increasingly used to aid in making high-stakes and socially sensitive decisions. While heuristics have been used for a long time to find decision trees with reasonable accuracy, recent approaches find fully optimal trees. Due to the computational hardness of finding fully optimal decision trees, it is only practically possible to find shallow trees for a limited dataset size. However, continuous algorithmic improvements keep pushing the scale of feasible solutions. Dynamic Programming approaches promise to find scalable optimal decision trees but need to be adapted for different objectives, such as regression. We combine and adapt the algorithmic techniques of two Dynamic Programming methods, creating a new method that improves the scalability of optimal regression trees. This new method often achieves an order of magnitude speed improvement over a previous state-of-the-art method.

Decision Trees
Dynamic Programming
Regression
Combinatorial Optimisation
Optimal Decision Tree
Interpretable Machine Learning
Algorithms

http://resolver.tudelft.nl/uuid:377edc0f-00b9-4481-840f-0fde43c494b9

https://github.com/mimvdb/regression-murtree Repository link Experiment setup

Student theses

bachelor thesis

© 2023 Mim van den Bos