Robust Optimal Classification Trees Against Adversarial Examples

• URL: http://arxiv.org/abs/2109.03857v1
• Date: Wed, 8 Sep 2021 18:10:49 GMT
• Title: Robust Optimal Classification Trees Against Adversarial Examples
• Authors: Dani\"el Vos and Sicco Verwer
• Abstract summary: We propose 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. We also present a method that determines the upper bound on adversarial accuracy for any model using bipartite matching.
• Score: 5.254093731341154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  We present a new discrete optimization method based on branch-and-bound (BnB) to obtain optimal decision trees. Our proposed algorithm Quant-BnB shows significant speedups compared to existing approaches for shallow optimal trees on various real datasets.
  arXiv  Detail & Related papers  (2022-06-23T17:19:29Z)
• bsnsing: A decision tree induction method based on recursive optimal boolean rule composition [2.28438857884398]
  This paper proposes a new mixed-integer programming (MIP) formulation to optimize split rule selection in the decision tree induction process. It develops an efficient search solver that is able to solve practical instances faster than commercial solvers.
  arXiv  Detail & Related papers  (2022-05-30T17:13:57Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Strong Optimal Classification Trees [8.10995244893652]
  We propose an intuitive flow-based MIO formulation for learning optimal binary classification trees. Our formulation can accommodate side constraints to enable the design of interpretable and fair decision trees. We show that our proposed approaches are 29 times faster than state-of-the-art MIO-based techniques.
  arXiv  Detail & Related papers  (2021-03-29T21:40:58Z)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)
• ENTMOOT: A Framework for Optimization over Ensemble Tree Models [57.98561336670884]
  ENTMOOT is a framework for integrating tree models into larger optimization problems. We show how ENTMOOT allows a simple integration of tree models into decision-making and black-box optimization.
  arXiv  Detail & Related papers  (2020-03-10T14:34:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.