An Efficient Adversarial Attack for Tree Ensembles

• URL: http://arxiv.org/abs/2010.11598v1
• Date: Thu, 22 Oct 2020 10:59:49 GMT
• Title: An Efficient Adversarial Attack for Tree Ensembles
• Authors: Chong Zhang, Huan Zhang, Cho-Jui Hsieh
• Abstract summary: adversarial attacks on tree based ensembles such as gradient boosting decision trees (DTs) and random forests (RFs) We show that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach. Our code is available at https://chong-z/tree-ensemble-attack.
• Score: 91.05779257472675
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of efficient adversarial attacks on tree based ensembles such as gradient boosting decision trees (GBDTs) and random forests (RFs). Since these models are non-continuous step functions and gradient does not exist, most existing efficient adversarial attacks are not applicable. Although decision-based black-box attacks can be applied, they cannot utilize the special structure of trees. In our work, we transform the attack problem into a discrete search problem specially designed for tree ensembles, where the goal is to find a valid "leaf tuple" that leads to mis-classification while having the shortest distance to the original input. With this formulation, we show that a simple yet effective greedy algorithm can be applied to iteratively optimize the adversarial example by moving the leaf tuple to its neighborhood within hamming distance 1. Experimental results on several large GBDT and RF models with up to hundreds of trees demonstrate that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach, while also providing smaller (better) adversarial examples than decision-based black-box attacks on general $\ell_p$ ($p=1, 2, \infty$) norm perturbations. Our code is available at https://github.com/chong-z/tree-ensemble-attack.

Related papers

• Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles [45.962492329047215]
  We introduce a method to prune a tree ensemble into a reduced version that is "functionally identical" to the original model. We formalize the problem of functionally identical pruning on ensembles, introduce an exact optimization model, and provide a fast yet highly effective method to prune large ensembles.
  arXiv  Detail & Related papers  (2024-08-28T23:15:46Z)
• Optimal Sparse Regression Trees [24.03491277969824]
  This work proposes a dynamic-programming-with-bounds approach to the construction of provably-optimal sparse regression trees. We leverage a novel lower bound based on an optimal solution to the k-Means clustering algorithm in 1-dimension over the set of labels.
  arXiv  Detail & Related papers  (2022-11-28T00:43:21Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  We introduce SoftTreeMax, the first approach that integrates tree-search into policy gradient. On Atari, SoftTreeMax demonstrates up to 5x better performance in faster run-time compared with distributed PPO.
  arXiv  Detail & Related papers  (2022-09-28T09:55:47Z)
• A Large-scale Multiple-objective Method for Black-box Attack against Object Detection [70.00150794625053]
  We propose to minimize the true positive rate and maximize the false positive rate, which can encourage more false positive objects to block the generation of new true positive bounding boxes. We extend the standard Genetic Algorithm with Random Subset selection and Divide-and-Conquer, called GARSDC, which significantly improves the efficiency. Compared with the state-of-art attack methods, GARSDC decreases by an average 12.0 in the mAP and queries by about 1000 times in extensive experiments.
  arXiv  Detail & Related papers  (2022-09-16T08:36:42Z)
• Unbiased and Efficient Sampling of Dependency Trees [0.0]
  Most treebanks require that every valid dependency tree has a single edge coming out of the ROOT node. Zmigrod et al. have recently proposed algorithms for sampling with and without replacement from the single-root dependency tree distribution. We show that their fastest algorithm for sampling with replacement, Wilson-RC, is in fact biased.
  arXiv  Detail & Related papers  (2022-05-25T09:57:28Z)
• Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
  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.
  arXiv  Detail & Related papers  (2021-09-08T18:10:49Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  Sparse adversarial attacks can fool deep networks (DNNs) by only perturbing a few pixels. Recent efforts combine it with another l_infty perturbation on magnitudes. We propose a homotopy algorithm to tackle the sparsity and neural perturbation framework.
  arXiv  Detail & Related papers  (2021-06-10T20:11:36Z)
• Patch-wise++ Perturbation for Adversarial Targeted Attacks [132.58673733817838]
  We propose a patch-wise iterative method (PIM) aimed at crafting adversarial examples with high transferability. Specifically, we introduce an amplification factor to the step size in each iteration, and one pixel's overall gradient overflowing the $epsilon$-constraint is properly assigned to its surrounding regions. Compared with the current state-of-the-art attack methods, we significantly improve the success rate by 35.9% for defense models and 32.7% for normally trained models.
  arXiv  Detail & Related papers  (2020-12-31T08:40:42Z)
• Patch-wise Attack for Fooling Deep Neural Network [153.59832333877543]
  We propose a patch-wise iterative algorithm -- a black-box attack towards mainstream normally trained and defense models. We significantly improve the success rate by 9.2% for defense models and 3.7% for normally trained models on average.
  arXiv  Detail & Related papers  (2020-07-14T01:50:22Z)

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.