# Verifying Tree Ensembles by Reasoning about Potential Instances

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2020.

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

- ["Why Would I Trust Your Numbers?" On the Explainability of Expected Values in Soccer](https://mlsanity.com/paper/2105.13778/) (2021)
- [Verifiable Learning for Robust Tree Ensembles](https://mlsanity.com/paper/2305.03626/) (2023)
- [Scaling up Memory-Efficient Formal Verification Tools for Tree Ensembles](https://mlsanity.com/paper/2105.02595/) (2021)
- [Faster Repeated Evasion Attacks in Tree Ensembles](https://mlsanity.com/paper/2402.08586/) (2024)
- [Probabilistic ML Verification via Weighted Model Integration](https://mlsanity.com/paper/2402.04892/) (2024)
- [Verifiable Boosted Tree Ensembles](https://mlsanity.com/paper/2402.14988/) (2024)

## Abstract (arXiv)

Imagine being able to ask questions to a black box model such as "Which adversarial examples exist?", "Does a specific attribute have a disproportionate effect on the model's prediction?" or "What kind of predictions could possibly be made for a partially described example?" This last question is particularly important if your partial description does not correspond to any observed example in your data, as it provides insight into how the model will extrapolate to unseen data. These capabilities would be extremely helpful as they would allow a user to better understand the model's behavior, particularly as it relates to issues such as robustness, fairness, and bias. In this paper, we propose such an approach for an ensemble of trees. Since, in general, this task is intractable we present a strategy that (1) can prune part of the input space given the question asked to simplify the problem; and (2) follows a divide and conquer approach that is incremental and can always return some answers and indicates which parts of the input domains are still uncertain. The usefulness of our approach is shown on a diverse set of use cases.