Robust Decision Trees

Decision trees are a popular choice of interpretable model, but just like neural networks, they suffer from adversarial examples: adversarial perturbations that result in misclassifications. Existing algorithms for fitting decision trees that are robust against adversarial examples are greedy heuristics and, therefore, lack approximation guarantees. We propose Robust Optimal Classification Trees (ROCT), a collection of methods to train decision trees that are optimally robust against user-specified attack models. We show that the min-max optimization problem that arises in adversarial learning can be solved using a single minimization formulation for decision trees with 0-1 loss. We propose such formulations in Mixed-Integer Linear Programming and Maximum Satisfiability, which widely available solvers can optimize. We also present a method that uses bipartite matching to compute robust leaf labels in polynomial time and can be used to determine the upper bound on adversarial accuracy for any model.

Adversarially Robust Decision Tree Relabeling

Daniël Vos, and Sicco Verwer

In Machine Learning and Knowledge Discovery in Databases, Jun 2023

Abs HTML

Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. However, common decision tree learning algorithms produce models that suffer from adversarial examples. Recent work on robust decision tree learning mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods being greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accuracy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.
Robust Optimal Classification Trees against Adversarial Examples

Daniël Vos, and Sicco Verwer

Proceedings of the AAAI Conference on Artificial Intelligence, Jun 2022

HTML

Relevant papers