# On Explaining Decision Trees

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

## Key facts

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

## Built on by (most cited first, 30 of 49)

- [Leveraging Explanations in Interactive Machine Learning: An Overview](https://mlsanity.com/paper/2207.14526/) (2022)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks](https://mlsanity.com/paper/2210.13915/) (2022)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [Foundations of Symbolic Languages for Model Interpretability](https://mlsanity.com/paper/2110.02376/) (2021)
- [ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanations](https://mlsanity.com/paper/2206.11900/) (2022)
- [Probabilistic Sufficient Explanations](https://mlsanity.com/paper/2105.10118/) (2021)
- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [Efficient Explanations With Relevant Sets](https://mlsanity.com/paper/2106.00546/) (2021)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [Model Learning with Personalized Interpretability Estimation (ML-PIE)](https://mlsanity.com/paper/2104.06060/) (2021)
- [Interpretability Guarantees with Merlin-Arthur Classifiers](https://mlsanity.com/paper/2206.00759/) (2022)
- [On the Explanatory Power of Decision Trees](https://mlsanity.com/paper/2108.05266/) (2021)
- [A Mathematical Philosophy of Explanations in Mechanistic Interpretability -- The Strange Science Part I.i](https://mlsanity.com/paper/2505.00808/) (2025)
- [Efficient Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2205.06936/) (2022)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)
- [Self-Explaining Neural Networks for Business Process Monitoring](https://mlsanity.com/paper/2503.18067/) (2025)
- [From global to local MDI variable importances for random forests and when they are Shapley values](https://mlsanity.com/paper/2111.02218/) (2021)
- [A Uniform Language to Explain Decision Trees](https://mlsanity.com/paper/2310.11636/) (2023)
- [Explaining a Deep Reinforcement Learning Docking Agent Using Linear Model Trees with User Adapted Visualization](https://mlsanity.com/paper/2203.00368/) (2022)

## Abstract (arXiv)

Decision trees (DTs) epitomize what have become to be known as interpretable machine learning (ML) models. This is informally motivated by paths in DTs being often much smaller than the total number of features. This paper shows that in some settings DTs can hardly be deemed interpretable, with paths in a DT being arbitrarily larger than a PI-explanation, i.e. a subset-minimal set of feature values that entails the prediction. As a result, the paper proposes a novel model for computing PI-explanations of DTs, which enables computing one PI-explanation in polynomial time. Moreover, it is shown that enumeration of PI-explanations can be reduced to the enumeration of minimal hitting sets. Experimental results were obtained on a wide range of publicly available datasets with well-known DT-learning tools, and confirm that in most cases DTs have paths that are proper supersets of PI-explanations.