# Provably Precise, Succinct and Efficient Explanations for Decision Trees

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 19 May 2022.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Probabilistic Sufficient Explanations](https://mlsanity.com/paper/2105.10118/) (2021)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)
- [Efficient Contrastive Explanations on Demand](https://mlsanity.com/paper/2412.18262/) (2024)
- [Explainable Evidential Clustering](https://mlsanity.com/paper/2507.12192/) (2025)

## Abstract (arXiv)

Decision trees (DTs) embody interpretable classifiers. DTs have been advocated for deployment in high-risk applications, but also for explaining other complex classifiers. Nevertheless, recent work has demonstrated that predictions in DTs ought to be explained with rigorous approaches. Although rigorous explanations can be computed in polynomial time for DTs, their size may be beyond the cognitive limits of human decision makers. This paper investigates the computation of δ-relevant sets for DTs. δ-relevant sets denote explanations that are succinct and provably precise. These sets represent generalizations of rigorous explanations, which are precise with probability one, and so they enable trading off explanation size for precision. The paper proposes two logic encodings for computing smallest δ-relevant sets for DTs. The paper further devises a polynomial-time algorithm for computing δ-relevant sets which are not guaranteed to be subset-minimal, but for which the experiments show to be most often subset-minimal in practice. The experimental results also demonstrate the practical efficiency of computing smallest δ-relevant sets.