Optimal Robust Decision Trees

Optimal Robust Decision Trees: A dynamic programming approach

Bien, Benedict (TU Delft Electrical Engineering, Mathematics and Computer Science)

Demirović, E. (graduation committee)
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-25

Decision trees are integral to machine learning, with their robustness being a critical measure of effectiveness against adversarial data manipulations. Despite advancements in algorithms, current solutions are either optimal but lack scalability or scale well, but do not guarrantee optimality. This paper presents a novel adaptation of the Murtree algorithm to address these challenges in the pursuit of optimal robust decision trees. We introduce a new method for modeling an adversary as a network flow problem, and provide a dynamic programming approach to solve optimal robust decision trees beyond a depth of two. The performance of our proposed algorithm is compared with bruteforce solutions across varying decision tree depths, feature numbers, and data sizes. This research contributes a significant advancement towards obtaining efficient and effective solutions for optimal robust decision trees, potentially setting a new performance benchmark in this area.

Decision Trees
Dynamic Programming
Algorithmics
Robustness
Combinatorial Optimization

http://resolver.tudelft.nl/uuid:ae6547f3-f3ac-43b8-bc46-474ecc341952

This is my code repository: https://github.com/andreasbien/OptimalRobustDecisionTree

Student theses

bachelor thesis

© 2023 Benedict Bien