On the Explanatory Power of Decision Trees
Authors:
Preprint
Abstract
Decision trees have long been recognized as models of choice in sensitive applications where interpretability is of paramount importance. In this paper, we examine the computational ability of Boolean decision trees in deriving, minimizing, and counting sufficient reasons and contrastive explanations. We prove that the set of all sufficient reasons of minimal size for an instance given a decision tree can be exponentially larger than the size of the input (the instance and the decision tree). Therefore, generating the full set of sufficient reasons can be out of reach. In addition, computing a single sufficient reason does not prove enough in general; indeed, two sufficient reasons for the same instance may differ on many features. To deal with this issue and generate synthetic views of the set of all sufficient reasons, we introduce the notions of relevant features and of necessary features that characterize the (possibly negated) features appearing in at least one or in every sufficient reason, and we show that they can be computed in polynomial time. We also introduce the notion of explanatory importance, that indicates how frequent each (possibly negated) feature is in the set of all sufficient reasons. We show how the explanatory importance of a feature and the number of sufficient reasons can be obtained via a model counting operation, which turns out to be practical in many cases. We also explain how to enumerate sufficient reasons of minimal size. We finally show that, unlike sufficient reasons, the set of all contrastive explanations for an instance given a decision tree can be derived, minimized and counted in polynomial time.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- On Efficiently Explaining Graph-Based Classifiers2021
- Explanation in artificial intelligence: Insights from the social sciencesArtificial Intelligence, 2019
- A Survey of Methods for Explaining Black Box ModelsACM Computing Surveys, 2018
- An empirical evaluation of the comprehensibility of decision table, tree and rule based predictive modelsDecision Support Systems, 2011
- Propositional Independence - Formula-Variable Independence and ForgettingJournal of Artificial Intelligence Research, 2003
- A Knowledge Compilation MapJournal of Artificial Intelligence Research, 2002
- Decomposable negation normal formJournal of the ACM, 2001
- A variant of Reiter's hitting-set algorithmInformation Processing Letters, 2001
- A theory of diagnosis from first principlesArtificial Intelligence, 1987
- Logic Minimization Algorithms for VLSI Synthesis1984