The Search for Optimal Robust Classification Trees
Pushing the limits of exhaustive search
Demirören (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Emir Demirovic – Mentor (TU Delft - Algorithmics)
Jacobus G.M. van der Linden – Mentor (TU Delft - Algorithmics)
D.A. Vos – Mentor (TU Delft - Algorithmics)
J.A. Baaijens – Graduation committee member (TU Delft - Pattern Recognition and Bioinformatics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Interpretability distinguishes decision trees from most other machine learning models; what they still have in common is that they are vulnerable to adversarial examples. Various robust decision tree algorithms exist; however, they either do not provide optimal results or are not scalable with data that has continuous features. In this work, we demonstrate RobTree, a scalable optimal robust decision tree algorithm for continuous features. We propose new theorems that reduce the number of thresholds to be considered to half of what was previously considered and give way to pruning techniques. The results of this paper indicate that RobTree vastly outperforms the state-of-the-art in terms of runtime for trees of depth two up to two orders of magnitude.