Robust Optimal Classification Trees Against Adversarial Examples
Decision trees are a popular choice of explainable model, but just like neural networks, they suffer from adversarial examples. Existing algorithms for fitting decision trees robust against adversarial examples are greedy heuristics and lack approximation guarantees. In this paper we propose 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 determines the upper bound on adversarial accuracy for any model using bipartite matching. Our experimental results demonstrate that the existing heuristics achieve close to optimal scores while ROCT achieves state-of-the-art scores.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationSimilar Papers 제목 키워드 기반
Robust Decision Trees Against Adversarial Examples
Although adversarial examples and model robustness have been extensively studied in the context of linear models and neural networks, research on this issue in tree-based models and how to make tree-based models robust a…
Adversarial AttackAdversarial DefenseEvaluating Defensive Distillation For Defending Text Processing Neural Networks Against Adversarial Examples
Adversarial examples are artificially modified input samples which lead to misclassifications, while not being detectable by humans. These adversarial examples are a challenge for many tasks such as image and text classi…
Adversarial TextClassificationGeneral Classificationimage-classification+3A Bayes-Optimal View on Adversarial Examples
Since the discovery of adversarial examples - the ability to fool modern CNN classifiers with tiny perturbations of the input, there has been much discussion whether they are a "bug" that is specific to current neural ar…
Adversarial AttackStochastic Activation Pruning for Robust Adversarial Defense
Neural networks are known to be vulnerable to adversarial examples. Carefully chosen perturbations to real images, while imperceptible to humans, induce misclassification and threaten the reliability of deep learning sys…
Adversarial DefenseCountermeasures Against Adversarial Examples in Radio Signal Classification
Deep learning algorithms have been shown to be powerful in many communication network design problems, including that in automatic modulation classification. However, they are vulnerable to carefully crafted attacks call…
ClassificationDeep Learning