# Verifiable Learning for Robust Tree Ensembles

arXiv: https://arxiv.org/abs/2305.03626 · HTML: https://mlsanity.com/paper/2305.03626/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 54 references that are in the map.
- First posted on arXiv 5 May 2023.

## Builds on (most cited first, 30 of 30)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [Certified Training: Small Boxes are All You Need](https://mlsanity.com/paper/2210.04871/) (2022)
- [Evasion and Hardening of Tree Ensemble Classifiers](https://mlsanity.com/paper/1509.07892/) (2015)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [On the Certified Robustness for Ensemble Models and Beyond](https://mlsanity.com/paper/2107.10873/) (2021)
- [Robustness Verification of Tree-based Models](https://mlsanity.com/paper/1906.03849/) (2019)
- [Efficient Exact Verification of Binarized Neural Networks](https://mlsanity.com/paper/2005.03597/) (2020)
- [Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks](https://mlsanity.com/paper/1906.03526/) (2019)
- [Efficient Training of Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/2012.10438/) (2020)
- [Adversarial EXEmples: A Survey and Experimental Evaluation of Practical Attacks on Machine Learning for Windows Malware Detection](https://mlsanity.com/paper/2008.07125/) (2020)
- [Learning Security Classifiers with Verified Global Robustness Properties](https://mlsanity.com/paper/2105.11363/) (2021)
- [Formal Verification of Input-Output Mappings of Tree Ensembles](https://mlsanity.com/paper/1905.04194/) (2019)
- [Verifying Robustness of Gradient Boosted Models](https://mlsanity.com/paper/1906.10991/) (2019)
- [Treant: Training Evasion-Aware Decision Trees](https://mlsanity.com/paper/1907.01197/) (2019)
- [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (2021)
- [Verification of Neural Networks: Enhancing Scalability through Pruning](https://mlsanity.com/paper/2003.07636/) (2020)
- [Verifying Tree Ensembles by Reasoning about Potential Instances](https://mlsanity.com/paper/2001.11905/) (2020)
- [Genetic Adversarial Training of Decision Trees](https://mlsanity.com/paper/2012.11352/) (2020)
- [Certifying Decision Trees Against Evasion Attacks by Program Analysis](https://mlsanity.com/paper/2007.02771/) (2020)
- [Beyond Robustness: Resilience Verification of Tree-Based Classifiers](https://mlsanity.com/paper/2112.02705/) (2021)
- [Feature Partitioning for Robust Tree Ensembles and their Certification in Adversarial Scenarios](https://mlsanity.com/paper/2004.03295/) (2020)

## Built on by (most cited first, 3 of 3)

- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [Verifiable Boosted Tree Ensembles](https://mlsanity.com/paper/2402.14988/) (2024)
- [Trustworthy Data- and ML-Ops for Intelligent Transportation Systems and Logistics](https://mlsanity.com/paper/2610.01282/) (2026)

## Abstract (arXiv)

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.