Verifiable Learning for Robust Tree Ensembles

• URL: http://arxiv.org/abs/2305.03626v4
• Date: Sat, 11 Nov 2023 16:53:33 GMT
• Title: Verifiable Learning for Robust Tree Ensembles
• Authors: Stefano Calzavara, Lorenzo Cazzaro, Giulio Ermanno Pibiri, Nicola Prezza
• Abstract summary: A class of decision tree ensembles called large-spread ensembles admit a security verification algorithm running in restricted time. We show the benefits of this idea by designing a new training algorithm that automatically learns a large-spread decision tree ensemble from labelled data. Experimental results on public datasets confirm that large-spread ensembles trained using our algorithm can be verified in a matter of seconds.
• Score: 8.207928136395184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Verifying the robustness of machine learning models against evasion attacks at test time is an important research problem. Unfortunately, prior work established that this problem is NP-hard for decision tree ensembles, hence bound to be intractable for specific inputs. In this paper, we identify a restricted class of decision tree ensembles, called large-spread ensembles, which admit a security verification algorithm running in polynomial time. We then propose a new approach called verifiable learning, which advocates the training of such restricted model classes which are amenable for efficient verification. We show the benefits of this idea by designing a new training algorithm that automatically learns a large-spread decision tree ensemble from labelled data, thus enabling its security verification in polynomial time. Experimental results on public datasets confirm that large-spread ensembles trained using our algorithm can be verified in a matter of seconds, using standard commercial hardware. Moreover, large-spread ensembles are more robust than traditional ensembles against evasion attacks, at the cost of an acceptable loss of accuracy in the non-adversarial setting.

Related papers

• Verifiable Boosted Tree Ensembles [7.107477567356262]
  Verifiable learning advocates for training machine learning models amenable to efficient security verification. This study expands prior work on verifiable learning from basic ensemble methods. We present a pseudo-polynomial time algorithm to verify robustness against attackers based on the $L_in$-norm.
  arXiv  Detail & Related papers  (2024-02-22T21:56:20Z)
• Interpretable Anomaly Detection via Discrete Optimization [1.7150329136228712]
  We propose a framework for learning inherently interpretable anomaly detectors from sequential data. We show that this problem is computationally hard and develop two learning algorithms based on constraint optimization. Using a prototype implementation, we demonstrate that our approach shows promising results in terms of accuracy and F1 score.
  arXiv  Detail & Related papers  (2023-03-24T16:19:15Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• Scalable Whitebox Attacks on Tree-based Models [2.3186641356561646]
  This paper proposes a novel whitebox adversarial robustness testing approach for tree ensemble models. By leveraging sampling and the log-derivative trick, the proposed approach can scale up to testing tasks that were previously unmanageable.
  arXiv  Detail & Related papers  (2022-03-31T21:36:20Z)
• Automated Decision-based Adversarial Attacks [48.01183253407982]
  We consider the practical and challenging decision-based black-box adversarial setting. Under this setting, the attacker can only acquire the final classification labels by querying the target model. We propose to automatically discover decision-based adversarial attack algorithms.
  arXiv  Detail & Related papers  (2021-05-09T13:15:10Z)
• Efficient Encrypted Inference on Ensembles of Decision Trees [21.570003967858355]
  Data privacy concerns often prevent the use of cloud-based machine learning services for sensitive personal data. We propose a framework to transfer knowledge extracted by complex decision tree ensembles to shallow neural networks. Our system is highly scalable and can perform efficient inference on batched encrypted (134 bits of security) data with amortized time in milliseconds.
  arXiv  Detail & Related papers  (2021-03-05T01:06:30Z)
• Discriminative Nearest Neighbor Few-Shot Intent Detection by Transferring Natural Language Inference [150.07326223077405]
  Few-shot learning is attracting much attention to mitigate data scarcity. We present a discriminative nearest neighbor classification with deep self-attention. We propose to boost the discriminative ability by transferring a natural language inference (NLI) model.
  arXiv  Detail & Related papers  (2020-10-25T00:39:32Z)
• Embedding and Extraction of Knowledge in Tree Ensemble Classifiers [11.762762974386684]
  This paper studies the embedding and extraction of knowledge in tree ensemble classifiers. We propose two novel, and effective, embedding algorithms, one of which is for black-box settings and the other for white-box settings. We develop an algorithm to extract the embedded knowledge, by reducing the problem to be solvable with an SMT (satisfiability modulo theories) solver.
  arXiv  Detail & Related papers  (2020-10-16T10:09:01Z)
• Bayesian Optimization with Machine Learning Algorithms Towards Anomaly Detection [66.05992706105224]
  In this paper, an effective anomaly detection framework is proposed utilizing Bayesian Optimization technique. The performance of the considered algorithms is evaluated using the ISCX 2012 dataset. Experimental results show the effectiveness of the proposed framework in term of accuracy rate, precision, low-false alarm rate, and recall.
  arXiv  Detail & Related papers  (2020-08-05T19:29:35Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

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.