ELLIS Delft Talk by Emir Demirović: Optimal Decision Trees (with Constraints) via Dynamic Programming and Search
11 November 2024 16:00 till 17:00 - Location: Hybrid: Building 28, Room Hilbert (2.W510) / Zoom - By: ELLIS Delft | Add to my calendar
by Emir Demirović | Delft University of Technology
Abstract
Decision trees are an effective and concise way of conveying information, easily understood by virtually everyone. Given the recent interest in explainable AI and related fields, decision trees stand out as a popular choice. From the algorithmic side, the unique structure of decision trees is interesting since it may be exploited to obtain more efficient algorithms than structure-oblivious approaches.
In this talk, I will give an overview of the research we have been doing on constructing optimal regression/decision trees, i.e., trees that best represent tabular data whilst respecting different types of constraints such as fairness and size. We show that our techniques based on dynamic programming and search are able to obtain orders of magnitude improvements in runtime over state-of-the-art approaches. Our framework is also able to support a range of different objectives and constraints, e.g., fairness, survival analysis, nonlinear metrics such as F1-score. The success of our approach is attributed to a series of specialised techniques that exploit properties unique to decision/regression trees.
The talk summarises about half a dozen of our papers (AAAI’21/24, JMLR’22, NeurIPS’22, ICML’23/24) and is meant to be accessible to all backgrounds, with plenty of time for discussion.
Speaker Biography
Emir Demirović is an assistant professor at TU Delft (Netherlands). He leads the Constraint Solving ("ConSol") research group, which advances combinatorial optimisation algorithms for a wide range of (real-world) problems, and co-directs the explainable AI in transportation lab ("XAIT") as part of the Delft AI Labs. Prior to his appointment at TU Delft, Emir worked at the University of Melbourne, Vienna University of Technology, National Institute of Informatics (internship), and at a production planning and scheduling company.
The focus point of Emir's current work is solving techniques based on constraint programming, optimising decision trees, and explainable methods for combinatorial optimisation. He is also interested in industrial applications, robust/resilient optimisation, and the integration of optimisation and machine learning.