# Explainable Global Fairness Verification of Tree-Based Classifiers

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 60 references that are in the map.
- First posted on arXiv 27 Sep 2022.

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

- [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)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Fairness in Machine Learning: A Survey](https://mlsanity.com/paper/2010.04053/) (2020)
- [Fairness in Machine Learning](https://mlsanity.com/paper/2012.15816/) (2020)
- [Fairness Testing: Testing Software for Discrimination](https://mlsanity.com/paper/1709.03221/) (2017)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Automated Directed Fairness Testing](https://mlsanity.com/paper/1807.00468/) (2018)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Learning Certified Individually Fair Representations](https://mlsanity.com/paper/2002.10312/) (2020)
- [Counterfactual Explainable Recommendation](https://mlsanity.com/paper/2108.10539/) (2021)
- [FlipTest: Fairness Testing via Optimal Transport](https://mlsanity.com/paper/1906.09218/) (2019)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Verifying Individual Fairness in Machine Learning Models](https://mlsanity.com/paper/2006.11737/) (2020)
- [Probabilistic Verification of Fairness Properties via Concentration](https://mlsanity.com/paper/1812.02573/) (2018)
- [Evasion and Hardening of Tree Ensemble Classifiers](https://mlsanity.com/paper/1509.07892/) (2015)
- [Perfectly Parallel Fairness Certification of Neural Networks](https://mlsanity.com/paper/1912.02499/) (2019)
- [Interpreting Tree Ensembles with inTrees](https://mlsanity.com/paper/1408.5456/) (2014)
- [Explainability for fair machine learning](https://mlsanity.com/paper/2010.07389/) (2020)
- [Justicia: A Stochastic SAT Approach to Formally Verify Fairness](https://mlsanity.com/paper/2009.06516/) (2020)
- [A Statistical Test for Probabilistic Fairness](https://mlsanity.com/paper/2012.04800/) (2020)
- [Interpretable Random Forests via Rule Extraction](https://mlsanity.com/paper/2004.14841/) (2020)
- [Marrying Fairness and Explainability in Supervised Learning](https://mlsanity.com/paper/2204.02947/) (2022)
- [Machine learning fairness notions: Bridging the gap with real-world applications](https://mlsanity.com/paper/2006.16745/) (2020)
- [Probabilistic Verification of Neural Networks Against Group Fairness](https://mlsanity.com/paper/2107.08362/) (2021)
- [CertiFair: A Framework for Certified Global Fairness of Neural Networks](https://mlsanity.com/paper/2205.09927/) (2022)
- [Can Explainable AI Explain Unfairness? A Framework for Evaluating Explainable AI](https://mlsanity.com/paper/2106.07483/) (2021)
- [Explainable Fairness in Recommendation](https://mlsanity.com/paper/2204.11159/) (2022)
- [Learning Security Classifiers with Verified Global Robustness Properties](https://mlsanity.com/paper/2105.11363/) (2021)

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

- [Data-Aware and Scalable Sensitivity Analysis for Decision Tree Ensembles](https://mlsanity.com/paper/2602.07453/) (2026)
- [Search-Based Fairness Testing: An Overview](https://mlsanity.com/paper/2311.06175/) (2023)
- [TA3: Testing Against Adversarial Attacks on Machine Learning Models](https://mlsanity.com/paper/2410.05334/) (2024)
- [Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach](https://mlsanity.com/paper/2605.13830/) (2026)
- [PINE: Pruning Boosted Tree Ensembles with Conformal In-Distribution Prediction Equivalence](https://mlsanity.com/paper/2605.28068/) (2026)

## Abstract (arXiv)

We present a new approach to the global fairness verification of tree-based classifiers. Given a tree-based classifier and a set of sensitive features potentially leading to discrimination, our analysis synthesizes sufficient conditions for fairness, expressed as a set of traditional propositional logic formulas, which are readily understandable by human experts. The verified fairness guarantees are global, in that the formulas predicate over all the possible inputs of the classifier, rather than just a few specific test instances. Our analysis is formally proved both sound and complete. Experimental results on public datasets show that the analysis is precise, explainable to human experts and efficient enough for practical adoption.