On the Explanatory Power of Decision Trees
Year: 2021

Abstract:
Decision trees have long been recognized as models of choice in sensitive applica1 tions where interpretability is of paramount importance. In this paper, we examine 2 the computational ability of Boolean decision trees in deriving, minimizing, and 3 counting sufficient reasons and contrastive explanations. We prove that the set 4 of all sufficient reasons of minimal size for an instance given a decision tree can 5 be exponentially larger than the size of the input (the instance and the decision 6 tree). Therefore, generating the full set of sufficient reasons can be out of reach. In 7 addition, computing a single sufficient reason does not prove enough in general; 8 indeed, two sufficient reasons for the same instance may differ on many features. 9 To deal with this issue and generate synthetic views of the set of all sufficient 10 reasons, we introduce the notions of relevant features and of necessary features that 11 characterize the (possibly negated) features appearing in at least one or in every 12 sufficient reason, and we show that they can be computed in polynomial time. We 13 also introduce the notion of explanatory importance, that indicates how frequent 14 each (possibly negated) feature is in the set of all sufficient reasons. We show how 15 the explanatory importance of a feature and the number of sufficient reasons can be 16 obtained via a model counting operation, which turns out to be practical in many 17 cases. We also explain how to enumerate sufficient reasons of minimal size. We 18 finally show that, unlike sufficient reasons, the set of all contrastive explanations 19 for an instance given a decision tree can be derived, minimized and counted in 20 polynomial time. 21

Decision trees have long been recognized as models of choice in sensitive applica-1 tions where interpretability is of paramount importance. In this paper, we examine2 the computational ability of Boolean decision trees in deriving, minimizing, and3 counting sufficient reasons and contrastive explanations. We prove that the set4 of all sufficient reasons of minimal size for an instance given a decision tree can5 be exponentially larger than the size of the input (the instance and the decision6 tree). Therefore, generating the full set of sufficient reasons can be out of reach. In7 addition, computing a single sufficient reason does not prove enough in general;8 indeed, two sufficient reasons for the same instance may differ on many features.9 To deal with this issue and generate synthetic views of the set of all sufficient10 reasons, we introduce the notions of relevant features and of necessary features that11 characterize the (possibly negated) features appearing in at least one or in every12 sufficient reason, and we show that they can be computed in polynomial time. We13 also introduce the notion of explanatory importance, that indicates how frequent14 each (possibly negated) feature is in the set of all sufficient reasons. We show how15 the explanatory importance of a feature and the number of sufficient reasons can be16 obtained via a model counting operation, which turns out to be practical in many17 cases. We also explain how to enumerate sufficient reasons of minimal size. We18 finally show that, unlike sufficient reasons, the set of all contrastive explanations19 for an instance given a decision tree can be derived, minimized and counted in20 polynomial time.21
1 Introduction22
In essence, explaining a decision to a person is to give the details or reasons that help a person23 (the explainee) understand why the decision has been made. This is a significant issue especially24 when decisions are made by Machine Learning (ML) models, such as random forests, Markov25 networks, support vector machines, and deep neural networks. Actually, with the growing number26 of applications that rely on ML techniques, researches on eXplainable AI (XAI) have become27 increasingly important, by providing efficient methods for interpreting ML models, and explaining28 their decisions (see for instance [10, 11, 12, 13, 16, 19, 22, 23, 24, 28, 30]).29
When dealing with Boolean classifiers, which is what we do in this paper, two decisions are possible,30 only: 1 for the instances classified as positive instances, and 0 for the remaining ones (the negative31 instances). Whatever the way x has been classified, an explainee may seek for explanations from32 two distinct types [23]. On the one hand, abductive explanations for x are intended to explain why x33 has been classified in the way it has been classified by the ML model (thus, addressing the “Why?”34 question). On the other hand, the purpose of contrastive (also known as counterfactual) explanations35 for x is to explain why x has not been classified by the ML model as the explainee expected it (thus,36 addressing the “Why not?” question). In both cases, explanations that are as simple as possible are37 preferred (where simplicity is modeled as irredundancy, or even as size minimality).38
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
Although there is no formal notion of interpretability [21], for classification problems, decision trees39 [3, 26] are arguably among the most interpretable ML models. Because of their interpretability,40 decision trees are often considered as target models for distilling a black-box model into a compre-41 hensible one [4, 10]. Furthermore, decision trees are often the components of choice for building42 (less interpretable, but potentially more accurate) ensemble classifiers, such as random forests [2] and43 gradient boosted decision trees [5].44
The interpretability of decision trees is endowed with two key characteristics. On the one hand,45 decision trees are transparent: each node in a decision tree has some meaning, and the principles used46 for generating all nodes can be explained. On the other hand, decision trees are locally explainable:47 by construction of a decision tree T , any input instance x is mapped to a unique root-to-leaf path48 that yields to a decision label. The subset of (positive and negative) features tTx occurring in the49 path used to find the right label 1 or 0 for x in the decision tree T can be viewed as a “direct reason”50 for classifying x as a positive instance or as a negative instance. tTx is an abductive explanation for51 x given T , which explains why x has been classified by T as it has been classified. Indeed, every52 instance x′ that coincides with x on tTx is classified by T in the same way as x. However, such53 “direct reasons” can contain arbitrarily many redundant features [17]. This motivates to take account54 for other types of abductive explanations in the case of decision trees, namely, sufficient reasons [7]55 (also known as prime implicant explanations [29]), that are irredundant abductive explanations, and56 minimal sufficient reasons (i.e., those sufficient reasons of minimal size).57
In this paper, we examine the computational ability of Boolean decision trees in deriving, minimizing58 and counting sufficient reasons and contrastive explanations. We prove that the set of all sufficient59 reasons of minimal size for an instance given a decision tree can be exponentially larger than the size60 of the input. When this is the case, generating the full set of sufficient reasons (i.e., the complete61 reason for the instance [7]) is typically out of reach. In addition, computing a single sufficient reason62 does not prove enough in general; indeed; two sufficient reasons for the same instance may differ on63 many features. To deal with this issue and generate synthetic views of the set of all sufficient reasons,64 we introduce the notions of relevant features and of necessary features that characterize the (possibly65 negated) features appearing in at least one or in every sufficient reason, and we show that they can be66 computed in polynomial time. We also introduce the notion of explanatory importance, that indicates67 how frequent each (possibly negated) feature is in the set of all sufficient reasons. Though deriving68 the explanatory importance of a feature in the set of sufficient reasons and determining the cardinality69 of this set are two computationally demanding tasks, we show how they can be achieved thanks to70 model counting operation, which turns out to be practical in many cases. We also explain how to71 enumerate sufficient reasons of minimal size, which is a way to count them when they are not too72 numerous. We finally show that, from a computational standpoint, contrastive explanations highly73 depart from sufficient reasons. Indeed, the set of all contrastive explanations for an instance given a74 decision tree can be computed in polynomial time. As a consequence, such explanations can also be75 minimized and counted in polynomial time.76
The rest of the paper is organized as follows. Preliminaries about decision trees, abductive reasons,77 and contrastive explanations are given in Section 2. The computation of all sufficient reasons is78 considered in Section 3. Necessary and relevant features are presented in this section, as well as79 the approach for assessing the explanatory importance of a feature and for counting the number of80 sufficient reasons. We also explain there how minimal sufficient reasons can be enumerated. An81 algorithm for computing all the contrastive explanations for the instance given the decision tree is82 presented in Section 4. Experimental results are reported in Section 5. Finally, Section 6 concludes83 the paper. All the proofs and additional empirical results are reported as a supplementary material.84
2 Decision Trees, Abductive and Contrastive Explanations85
For an integer n, let [n] be the set {1, · · · , n}. By Fn we denote the class of all Boolean functions86 from {0, 1}n to {0, 1}, and we use Xn = {x1, · · · , xn} to denote the set of input Boolean variables,87 corresponding to the features under consideration. Any assignment x ∈ {0, 1}n is called an instance.88 If f(x) = 1 for some f ∈ Fn, then x is called a model of f . x is a positive instance when f(x) = 189 and a negative instance when f(x) = 0.90
We refer to f as a propositional formula when it is described using the Boolean connectives ∧91 (conjunction), ∨ (disjunction) and ¬ (negation), together with the Boolean constants 1 (true) and 092
(false). As usual, a literal ` is a variable xi (a positive literal) or its negation ¬xi, also denoted xi (a93 negative literal). A positive literal xi is associated with a positive feature (i.e., xi is set to 1), while a94 negative literal xi is associated with a negative feature (i.e., xi is set to 0). A term (or monomial) t is95 a conjunction of literals, and a clause c is a disjunction of literals. A DNF formula is a disjunction96 of terms and a CNF formula is a conjunction of clauses. The set of variables occurring in a formula97 f is denoted Var(f). A formula f is consistent if and only if it has a model. A CNF formula is98 monotone whenever every occurrence of a literal in the formula has the same polarity (i.e., if a literal99 occurs positively (resp. negatively) in the formula, then it does not have any negative (resp. positive)100 occurrence in the formula). A formula f1 implies a formula f2, noted f1 |= f2, if and only if every101 model of f1 is a model of f2. Two formulae f1 and f2 are equivalent, noted f1 ≡ f2 whenever they102 have the same models. The conditioning of a formula f by a literal `, denoted f | `, is the formula103 obtained from f by replacing each occurrence of xi with 1 (resp. 0) and each occurrence of xi with 0104 (resp. 1) if ` = xi (resp. ` = xi).105
In what follows, we shall often treat assignments as terms, and terms and clauses as sets of literals.106 Given an assignment z ∈ {0, 1}n, the corresponding term is defined as107
tz = n∧ i=1 xzii where x 0 i = xi and x 1 i = xi
A term t covers an assignment z if t ⊆ tz . An implicant of a Boolean function f is a term that implies108 f . A prime implicant of f is an implicant t of f such that no proper subset of t is an implicant of f .109 Dually, an implicate of a Boolean function f is a clause that is implied by f , and a prime implicate of110 f is an implicate c of f such that no proper subset of c is an implicate of f .111
With these basic notions in hand, we shall focus on the following representation class of Boolean112 functions:113 Definition 1 (Decision Tree). A (Boolean) decision tree is a binary tree T , each of whose internal114 nodes is labeled with one of n input Boolean variables, and whose leaves are labeled 0 or 1. Every115 variable is assumed (without loss of generality) to appear at most once on any root-to-leaf path116 (read-once property). The value T (x) ∈ {0, 1} of T on an input instance x is given by the label of117 the leaf reached from the root as follows: at each node, go to the left or right child depending on118 whether the input value of the corresponding variable is 0 or 1, respectively. The size of T , denoted119 |T |, is given by the number of its nodes.120
The class of decision trees over Xn is denoted DTn. It is well-known that any decision tree T ∈ DTn121 can be transformed in linear time into an equivalent disjunction of terms, denoted DNF(T ), where122 each term corresponds to a path from the root to a leaf labeled with 1. Dually, T can be transformed123 in linear time into a conjunction of clauses, denoted CNF(T ), where each clause is the negation of the124 term describing a path from the root to a leaf labeled with 0.125
For illustration, the following toy example will be used throughout the paper as a running example:126 Example 1. The decision tree in Figure 1 separates Cattleya orchids from other orchids using the127 following features: x1: “has fragrant flowers”, x2: “has one or two leaves”, x3: “has large flowers”,128 and x4: “is sympodial”.129
As a salient characteristic, decision trees convey a single explicit abductive explanation for classifying130 any input instance:131 Definition 2 (Direct Reason). Let T ∈ DTn and x ∈ {0, 1}n. The direct reason for x given T is the132 term, denoted tTx , corresponding to the unique root-to-leaf path of T that is compatible with x.133
Another important notion of abductive explanations is the following concept of sufficient reason[7],134 that, unlike the notion of direct reason, is not specific to decision trees:135 Definition 3 (Sufficient Reason). Let f ∈ Fn and x ∈ {0, 1}n such that f(x) = 1 (resp. f(x) = 0).136 A sufficient reason for x given f is a prime implicant t of f (resp. ¬f ) that covers x. sr(x, f)137 denotes the set of sufficient reasons for x given f .138
Thus, a sufficient reason [7] (also known as prime implicant explanation [29]) for an instance x given139 a class described by a Boolean function f is a subset t of the characteristics of x that is minimal w.r.t.140 set inclusion such that any instance x′ sharing this set t of characteristics is classified by f as x is.141 Thus, when f(x) = 1, t is a sufficient reason for x given f if and only if t is a prime implicant of f142 such that x implies t, and when f(x) = 0, t is a sufficient reason for x given f if and only if t is a143 prime implicant of ¬f such that t covers x. Accordingly, sufficient reasons are suited to explain why144 the instance at hand x has been classified by f as it has been classified. Unlike direct reasons [17],145 sufficient reasons do not contain any redundant feature.146
When considering the sufficient reasons of the input instance, one may be interested in focusing on147 the shortest ones, alias the minimal sufficient reasons. Those reasons are valuable since conciseness148 is often a desirable property of explanations (Occam’s razor). Formally:149 Definition 4 (Minimal Sufficient Reason). Let f ∈ Fn and x ∈ {0, 1}n. A minimal sufficient reason150 for x given f is a sufficient reason for x given f that contains a minimal number of literals.151
Finally, unlike direct and (possibly minimal) sufficient reasons that aim to explain the classification152 of the instance x under consideration as achieved by the classifier f , contrastive explanations are153 valuable when x has not been classified by f as expected by the explainee. In this case, one looks for154 minimal subsets of the features that when switched in x are enough to get instances that are classified155 positively (resp. negatively) by f if x is classified negatively (resp. positively) by f . Formally, a156 contrastive explanation for x given f [15] is a subset t of the characteristics of x that is minimal157 w.r.t. set inclusion among those such that at least one instance x′ that coincides with x except on the158 characteristics from t is not classified by f as x is.159 Definition 5 (Contrastive Explanation). Let f ∈ Fn and x ∈ {0, 1}n such that f(x) = 1 (resp.160 f(x) = 0). A contrastive explanation for x given f is a term t over Xn such that t ⊆ tx, tx \ t is not161 an implicant of f (resp. ¬f ), and for every ` ∈ t, t \ {`} does not satisfy this last condition.162 Example 2. Based on our running example, we can observe that T (x) = 1 for the instance163 x = (1, 1, 1, 1). The direct reason for x given T is the term tTx = x1 ∧ x2 ∧ x3 ∧ x4. x1 ∧ x4 and164 x2 ∧ x3 ∧ x4 are the sufficient reasons for x given T . x1 ∧ x4 is the unique minimal sufficient reason165 for x given T . x4, x1 ∧ x2, and x1 ∧ x3 are the contrastive explanations for x given T . Thus, the166 instance (1, 1, 1, 0) that differs with x only on x4 is not classified by T as x is ((1, 1, 1, 0) is classified167 as a negative instance).168
We mention in passing that when dealing with decision trees T , we could have focused only on169 explanations for the positive instances x given T . This comes from the fact that DTn is closed under170 negation, in the sense that for any T ∈ DTn, ¬T can be obtained by just replacing from T the label171 of each leaf with its complement. So, for any instance x ∈ {0, 1}n, a direct reason (resp. sufficient172 reason, minimal sufficient reason, contrastive explanation) explaining why T (x) = 0 is precisely the173 same as a direct reason (resp. sufficient reason, minimal sufficient reason, contrastive explanation)174 explaining why (¬T )(x) = 1. Considering T or its negation ¬T has no computational impact since175 ¬T can be computed in time linear in the size of T .176
3 Computing All Sufficient Reasons177
Sufficient reasons can be exponentially numerous. When switching from the direct reason for178 an instance (that is unique but not always redundancy-free) to its sufficient reasons, a main obstacle179 to be dealt with lies in the number of reasons to be considered. Indeed, even for the restricted class180
of decision trees with logarithmic depth, an input instance can have exponentially many sufficient181 reasons:182
Proposition 1. There is a decision tree T ∈ DTn of depth log2(n+1) such that for any x ∈ {0, 1}n,183 the number of sufficient reasons for x given T is at least b 32 n+1 2 c.184
By definition, the minimal sufficient reasons for x given T cannot be more numerous than its185 sufficient reasons. However, focusing on minimal sufficient reasons does not solve the problem since186 an instance can also have exponentially many minimal sufficient reasons:187
Proposition 2. For every n ∈ N such that n is odd, there is a decision tree T ∈ DTn of depth n+12188 such that T contains 2n + 1 nodes and there is an instance x ∈ {0, 1}n such that the number of189 minimal sufficient reasons for x given T is equal to 2 √ n−1.190
In many practical cases, the number of sufficient reasons for an instance given a decision tree can191 be very large. Figure 2 (top) shows an mnist instance (the leftmost subfigure) that has 482 185 073192 664 sufficient reasons. Among them there are very dissimilar sufficient reasons. As an illustration,193 the two rightmost subfigures present two sufficient reasons for this instance, and they differ on many194 features (blue (resp. red) dots correspond to pixels on (resp. off)).195
For such datasets, computing the set of all the sufficient reasons for a given instance is not always196 feasible. Furthermore, if the computation succeeds but the number of sufficient reasons is huge, their197 (disjunctively interpreted) set, alias the complete reason for the instance [7], can hardly be considered198 as intelligible by the explainee. Finally, due to the number of sufficient reasons and their diversity,199 deriving one of them is not informative enough. Thus, one needs to design approaches to synthesizing200 their set while avoiding the two pitfalls (the computational one and the informational one).201
Synthesizing the set of sufficient reasons. In this objective, the following notions of necessary /202 (ir)relevant features appear useful. These notions of necessity and relevance echo the ones that have203 been considered in [9] for logic-based abduction.204
Definition 6 (Explanatory Features). Let f ∈ Fn, and x ∈ {0, 1}n be an instance. Let e be an205 explanation type.1206
• A literal ` over Xn is a necessary feature for the family e of explanations for x given f if207 and only if ` belongs to every explanation t for x given f such that t is of type e. Nece(x, f)208 denotes the set of all necessary features for the family e of explanations for x given f .209
• A literal ` over Xn is a relevant feature for the family e of explanations for x given f if210 and only if ` belongs to at least one explanation t for x given f such that t is of type e.211 Rele(x, f) denotes the set of all relevant features for the family e of explanations for x212
1For instance, e can be s when the sufficient reasons for x given f are targeted or c when the contrastive explanations for x given f are targeted.
given f . Irre(x, f), which is the complement of Rele(x, f) in the set of all literals over213 Xn, denotes the set of all irrelevant features for the family e of explanations for x given f .214
The necessary (resp. irrelevant) features for the family s of sufficient reasons for x given f are the215 most (resp. less) important features for explaining the classification of x by f , since they belong to216 every (resp. no) sufficient reason for x given f .217
When a single sufficient reason t for x given f has been computed, the cardinality of t deprived from218 the features of Necs(x, f) is small, and the cardinality of the symmetric difference between t and219 Rels(x, f) is small as well, t can be viewed as a good representative of the complete reason for x220 given f in the sense that a sufficient reason t′ for x given f that differs a lot from t cannot exist.221
In the case when f is a decision tree T , though the set of all sufficient reasons for x given T cannot222 be generated when it is too large, Necs(x, f), Rels(x, f), and Irrs(x, f) can be derived efficiently:223 Proposition 3. Let T ∈ DTn, and x ∈ {0, 1}n. Computing Necs(x, T ), Rels(x, f), and Irrs(x, T )224 can be done in O((n+ |T |)× |T |) time.225
Going a step further consists in evaluating the explanatory importance of every (positive or negative)226 feature:227 Definition 7 (Explanatory Importance). Let f ∈ Fn, and x ∈ {0, 1}n be an instance. Let e be an explanation type, and Ee(x, f) the set of all explanations for x given f that are of type e. The explanatory importance of a literal ` over Xn for x given f w.r.t. e is given by
Impe(`,x, f) = #({t ∈ Ee(x, f) : ` ∈ t})
#(Ee(x, f)) .
Example 3. On the running example, we have Necs(x, T ) = {x4}, and Rels(x, T ) = {x1, x2, x3,228 x4}. We also have Imps(x4,x, T ) = 1, Imps(x1,x, T ) = Imps(x2,x, T ) = Imps(x3,x, T ) = 12 ,229 and Imps(`,x, T ) = 0 for every other literal ` (the negative ones over {x1, x2, x3, x4}).230
The notion of explanatory importance must not be confused with the notions of feature importance231 (which can be defined and assessed in many different ways): the former is local (i.e., relative to an232 instance) and not global, it concerns literals and not variables (polarity matters), and it is about the233 explanation task, not the prediction one.234
In order to compute the explanatory importance of a literal, a straightforward approach consists in235 enumerating the explanations of Ee(x, f). This is feasible when this set is not too large, which is not236 always the case for sufficient reasons even when f is a decision tree T . Thus, for dealing with the237 remaining case, an alternative approach must be looked for.238
We designed such an approach for computing Imps(`,x, T ). We know that sr(x, T ) is by construc-239 tion the set of prime implicants of g = {c ∩ tx : c ∈ CNF(T )}. Thus, we exploited the translation240 presented in [18] showing how to associate in polynomial time with a given CNF formula (here,241 g) another formula (over a distinct set of variables), let us say h, such that the models of h are242 in one-to-one correspondence with the prime implicants of g. In our case, the translation can be243 simplified because g is a monotone CNF formula. Since h is not primarily a CNF formula, leveraging244 Tseitin transformation [31], we turned h in linear time into a query-equivalent CNF formula i. Note245 that every auxiliary variable that is introduced in i is defined from the other variables (those occurring246 in h), so that the number of models of i is the same as the number of models of h. Finally, we took247 advantage of the compilation-based model counter D4 [20] to compile i into a d-DNNF circuit [6],248 and this enabled us to compute in time polynomial in the size of i both the number of sufficient249 reasons and the explanatory importance of every literal (indeed, the d-DNNF language supports in250 polytime the model counting query and the conditioning transformation [8]). We show in Section251 5 that, despite a high complexity in the worst case (the size of i can be exponential in |T |), this252 approach based on knowledge compilation proves quite efficient in practice.253
Clearly enough, when Impe(`,x, T ) has been computed for every `, one can easily generate ex-254 planatory heat maps. Figure 2 (bottom) shows an mnist instance (the leftmost subfigure) that has255 19 115 685 sufficient reasons, 6 necessary literals, and 94 relevant literals. The central subfigure256 is the corresponding heat map. Blue (resp. red) pixels correspond to positive (resp. negative)257 literals in the instance, and the intensity of the color aims to reflect the explanatory importance of258 the corresponding literal. The rightmost subfigure gives the explanatory features (dark pixels are259 associated with necessary literals, and light pixels to relevant literals).260
Enumerating the minimal sufficient reasons. An approach to synthesizing the set of sufficient261 reasons consists in focusing on the minimal ones. Indeed, though the set of minimal sufficient reasons262 for an instance given a decision tree can be exponentially large, the number of minimal sufficient263 reasons cannot exceed the number of sufficient reasons, and it can be significantly lower in practice.264
However, unlike sufficient reasons that can be generated in polynomial time using a greedy algorithm265 (see e.g., [17]), computing minimal reasons is not an easy task:266 Proposition 4. Let T ∈ DTn and x ∈ {0, 1}n. Computing a minimal sufficient reason for x given T267 is NP-hard.268
Despite this intractability result, minimal sufficient reasons can be generated in many practical cases.269 A common approach for handling NP-optimization problems is to rely on modern constraint solvers.270 One follows this direction here and casts the task of finding minimal sufficient reasons as a Boolean271 constraint optimization problem. We first need to recall that a PARTIAL MAXSAT problem consists272 of a pair (Csoft, Chard) where Csoft and Chard are (finite) set of clauses. The goal is to find a Boolean273 assignment that maximizes the number of clauses c in Csoft that are satisfied, while satisfying all274 clauses in Chard.275 Proposition 5. Let T be a decision tree in DTn and x ∈ {0, 1}n be an instance such that T (x) = 1. Let (Csoft, Chard) be an instance of the PARTIAL MAXSAT problem such that:
Csoft = {xi : xi ∈ tx} ∪ {xi : xi ∈ tx} and Chard = {c ∩ tx : c ∈ CNF(T )}.
The intersection of tx with tx∗ where x∗ is an optimal solution of (Chard, Csoft), is a minimal276 sufficient reason for x given T .277
Clearly enough, if x is such that T (x) = 0, then it is enough to consider the same instance of278 PARTIAL MAXSAT as above, except that Chard = {c ∩ tx : c ∈ CNF(¬T )}.279 Finally, one can take advantage of this PARTIAL MAXSAT characterization for generating a preset280 number of minimal sufficient reasons (basically, one generates a first reason t, then one adds to Chard281 the negation of t as a clause as well as a CNF encoding of a cardinality constraint for ensuring that the282 next reasons to be generated have the same size as the one of t, and we resume until the bound is283 reached or no solution exists).284
4 Computing All Contrastive Explanations285
Interestingly, it has been shown that sufficient reasons and contrastive explanations are connected286 by a minimal hitting set duality [15]. This duality can be leveraged to derive one of the two sets of287 explanations from the other one using algorithms for computing minimal hitting sets [27, 32].288
However, in the case of decision trees, a more direct and much more efficient approach to derive all289 the contrastive explanations for x ∈ {0, 1}n given T ∈ DTn can be designed. Indeed, unlike what290 happens for sufficient reasons (see Section 3), the set of all contrastive explanations for x ∈ {0, 1}n291 given a decision tree T ∈ DTn can be computed in polynomial time from x and T :292 Proposition 6. The set of all contrastive explanations for x ∈ {0, 1}n given a decision tree T ∈ DTn293 can be computed in time polynomial in n+ |T | as min({c ∩ tx : c ∈ CNF(f)},⊆).294 Example 4. On the running example, we have CNF(T ) = {x1 ∨x2, x1 ∨x2 ∨x3, x1 ∨x2 ∨x3 ∨x4,295 x1∨x2∨x3∨x4, x1∨x2∨x3∨x4, x1∨x2∨x3∨x4, x1∨x2∨x3∨x4}. Thus, with x = (1, 1, 1, 1), we296 have min({c∩ tx : c ∈ CNF(f)},⊆) = {x1∨x2, x1∨x3, x4}, which corresponds to the contrastive297 explanations x1 ∧ x2, x1 ∧ x3, x4 for x given T (viewing clauses and terms as sets of literals).298
As straightforward consequences of Proposition 6, computing necessary / relevant features and299 computing the explanatory importance of features w.r.t. contrastive explanations can be achieved in300 time polynomial in n + |T |. Similarly, statistics about the size of contrastive explanations can be301 easily established, and contrastive explanations can be easily minimized and counted.302
5 Experiments303
Empirical setting. We have considered 90 datasets, which are standard benchmarks from the well-304 known repositories Kaggle (www.kaggle.com), OpenML (www.openml.org), and UCI (archive.305
ics.uci.edu/ml/). mnist38 and mnist49 are subsets of the mnist dataset, restricted to the306 instances of 3 and 8 (resp. 4 and 9) digits. Because some datasets are suited to the multi-label307 classification task, we used the standard “one versus all” policy to deal with them: all the classes but308 the target one are considered as the complementary class of the target. Categorical features have been309 treated as arbitrary numbers (the scale is nominal). As to numeric features, no data preprocessing has310 taken place: these features have been binarized on-the-fly by the decision tree learning algorithm that311 has been used.312
For every benchmark b, a 10-fold cross validation process has been achieved. Namely, a set of 10313 decision trees Tb have been computed and evaluated from the labelled instances of b, partitioned into314 10 parts. One part was used as the test set and the remaining 9 parts as the training set for generating315 a decision tree. This tree is thus in 1-to-1 correspondence with the test set chosen within the whole316 dataset b. The classification performance for b was measured as the mean accuracy obtained over the317 10 decision trees generated from b. The CART algorithm, and more specifically its implementation318 provided by the Scikit-Learn library [25] has been used to learn decision trees. All hyper-parameters319 of the learning algorithm have been set to their default value. Notably, decision trees have been320 learned using the Gini criterion, and without any maximal depth or any other manual limitation.321
For each benchmark b, each decision tree Tb, and a subset of at most 100 instances x picked up322 at random in the test set following a uniform distribution, we computed a sufficient reason for x323 given Tb (using the standard greedy algorithm run on the direct reason tTbx ), and a minimal sufficient324 reason for x given Tb using the PARTIAL MAXSAT encoding presented in Proposition 5. This325 enabled us to draw some statistics (median, maximum) about the sizes of the reasons that have been326 generated. Using the algorithm presented in the proof of Proposition 3, we also derived the necessary327 and relevant explanatory features for each x, and again drew some statistics about them. Exploiting328 the model counter D4, we computed the number of sufficient reasons for x given Tb, as well as the329 explanatory importance of every feature. Taking advantage of the algorithm given in Proposition330 4, we computed the number of contrastive explanations for x given Tb, and drew some statistics331 about those numbers and about the sizes of the contrastive explanations. Finally, using the approach332 described in Section 3, we enumerated all the minimal sufficient reasons for x given Tb up to a limit333 of 10 000, and again drew some statistics about the numbers of minimal sufficient reasons. Of course,334 for each computation, we measured the corresponding runtimes since this is fundamental to determine335 the extent to which the algorithms are practical (details are provided as a supplementary material).336
All the experiments have been conducted on a computer equipped with Intel(R) XEON E5-2637 CPU337 @ 3.5 GHz and 128 GiB of memory. D4 [20] was run with its default parameters. For computing338
minimal reasons, we used the Pysat library [14], which provides the implementation of the RC2339 PARTIAL MAXSAT solver. This solver was run using the parameters corresponding to the “Glucose”340 setting. A time-out of 100s per instance was set for D4.341
Results. Table 1 (top and bottom) reports an excerpt of our results, focusing on 12 benchmarks342 out of 90 (the selected datasets are among those containing many instances and/or many features).343 The leftmost column gives the name of the dataset b. Columns %A, %N , and #B give, respectively,344 the mean accuracy over the 10 decision trees, the average number of nodes in those trees, and the345 average number of binary features they are based on. The next columns give statistics (median,346 maximum) about, respectively, the size of the sufficient reasons (|Sufficient|) and of the minimal347 sufficient reasons (|Minimal|) that have been computed, as well as about the number of necessary348 (#Nec. Features) and relevant (#Rel. Features) features that appear in the full set of sufficient349 reasons for the instance. Table 1 (bottom) give statistics (median, maximum) about, respectively, the350 number of sufficient reasons (#Sufficient), the number of contrastive explanations (#Contrastive)351 and their sizes (|Contrastive|), and finally the number of minimal sufficient reasons (#Minimal).352
As to the computation times, it turns out that all the algorithms described in the previous sections353 proved as efficient in practice. This is not surprising for those algorithms having a polytime worst-case354 complexity (the greedy algorithm for computing a sufficient reason, the one for deriving explanatory355 features, and the one for computing all the contrastive explanations). It was less obvious at first356 sight for the algorithms used for counting the number of sufficient reasons and for computing the357 explanatory importance of features. However, all the computations that have been run have terminated358 in due time, except for 3 datasets out of 90, namely adult, bank_marketing, and bank. For these359 datasets, the time limit of 100s has been reached for, respectively, 203, 150, and 336 instances out of360 1000 (in this case, the median number of sufficient reasons has not been reported). Notably, for all361 the 90 datasets but those 3, the median time required for counting the number of sufficient reasons362 and computing the explanatory importance of features never exceeded 1s. Computing a minimal363 sufficient reason, and more generally all such reasons looked challenging as well, due to both the364 intrinsic complexity of computing a minimal sufficient reason and to their number. Nevertheless,365 our enumeration algorithm succeeded in deriving all the minimal sufficient reasons for every dataset366 except 3 out of 90, namely farm-ads, mnist49, and gisette. For these datasets, the limit of 10367 000 reasons has been reached for, respectively, 5, 16, and 3 instances out of 1000. Interestingly,368 the median time needed to derive all the minimal sufficient reasons for the instances for which the369 computation has been successful exceeded 1s only for 2 datasets (adult and bank_marketing).370
Beyond providing evidence that the number of reasons can be huge, our experiments have highlighted371 that the greedy algorithm for deriving a sufficient reason computes in practice a minimal sufficient372 reason in many cases. They have also shown that the number of explanatory relevant features for an373 instance is typically much lower than the number of binary features used to describe it, and that the374 number of explanatory necessary features is also significantly lower than the number of explanatory375 relevant features. The gap between the two explains the possibly enormous number of sufficient376 reasons. When considering the full set of reasons, a considerable difference between the number of377 sufficient reasons and the number of minimal sufficient reasons can also be observed. Finally, like378 minimal sufficient reasons, the number of contrastive explanations appears in many cases not very379 large, which is a good point from an intelligibility perspective.380
6 Conclusion381
In light of our results, it turns out that the explanatory power of decision trees goes far beyond its382 ability to generate direct reasons. From a decision tree, the explanatory importance of features and383 the minimal sufficient reasons for an instance can be computed efficiently most of the time. For384 decision trees, fully addressing the “Why not?” question also appears as easier than fully addressing385 the “Why?” question: computing the full set of sufficient reasons for the instance at hand is typically386 out of reach, while computing its full set of contrastive explanations is tractable.387
Accordingly, the language of decision trees appears not only as appealing for the learning purpose,388 but also as a good target when one needs to reason on the various forms of explanations (abductive389 and contrastive ones) associated with the predictions made. This coheres with (and completes) the390 results reported in [1], showing that many other explanation and verification tasks are tractable for391 decision tree classifiers.392
References393
[1] G. Audemard, F. Koriche, and P. Marquis. On tractable XAI queries based on compiled394 representations. In Proc. of KR’20, pages 838–849, 2020.395
[2] L. Breiman. Random forests. Machine Learning, 45(1):5–32, 2001.396
[3] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees.397 Wadsworth, 1984.398
[4] L. Breiman and N. Shang. Born again trees. Technical report,399 https://www.stat.berkeley.edu/ breiman/BAtrees.pdf, 1996.400
[5] T. Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In Proc. of KDD’16, page401 785–794, 2016.402
[6] A. Darwiche. Decomposable negation normal form. Journal of the Association for Computing403 Machinery, 48(4):608–647, 2001.404
[7] A. Darwiche and A. Hirth. On the reasons behind decisions. In Proc. of ECAI’20, pages405 712–720, 2020.406
[8] A. Darwiche and P. Marquis. A knowledge compilation map. Journal of Artificial Intelligence407 Research, 17:229–264, 2002.408
[9] Th. Eiter and G. Gottlob. The complexity of logic-based abduction. Journal of the Association409 for Computing Machinery, 42(1):3–42, 1995.410
[10] N. Frosst and G. E. Hinton. Distilling a neural network into a soft decision tree. In Proc. of411 the First International Workshop on Comprehensibility and Explanation in AI and ML, volume412 2071 of CEUR Workshop Proceedings. CEUR-WS.org, 2017.413
[11] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi. A survey of414 methods for explaining black box models. ACM Computing Surveys, 51(5):93:1–93:42, 2019.415
[12] S. Hooker, D. Erhan, P-J. Kindermans, and B. Kim. A benchmark for interpretability methods416 in deep neural networks. In Proc. of NeurIPS’19, pages 9737–9748, 2019.417
[13] J. Huysmans, K. Dejaeger, C. Mues, J. Vanthienen, and B. Baesens. An empirical evaluation of418 the comprehensibility of decision table, tree and rule based predictive models. Decis. Support419 Syst., 51(1):141–154, 2011.420
[14] A. Ignatiev, A. Morgado, and J. Marques-Silva. PySAT: A Python toolkit for prototyping with421 SAT oracles. In Proc. of SAT’18, pages 428–437, 2018.422
[15] A. Ignatiev, N. Narodytska, N. Asher, and J. Marques-Silva. On relating ’why?’ and ’why not?’423 explanations. CoRR, abs/2012.11067, 2020.424
[16] A. Ignatiev, N. Narodytska, and J. Marques-Silva. Abduction-based explanations for machine425 learning models. In Proc. of AAAI’19, pages 1511–1519, 2019.426
[17] Y. Izza, A. Ignatiev, and J. Marques-Silva. On explaining decision trees. CoRR, abs/2010.11034,427 2020.428
[18] S. Jabbour, J. Marques-Silva, L. Sais, and Y. Salhi. Enumerating prime implicants of proposi-429 tional formulae in conjunctive normal form. In Proc. of JELIA’14, pages 152–165, 2014.430
[19] B. Kim, M. Wattenberg, J. Gilmer, C. Cai, J. Wexler, F. Viegas, and R. Sayres. Interpretability431 beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In432 Proc. of ICML’18, pages 2668–2677, 2018.433
[20] J.-M. Lagniez and P. Marquis. An Improved Decision-DNNF Compiler. In Proc. of IJCAI’17,434 pages 667–673, 2017.435
[21] Z. C. Lipton. The mythos of model interpretability. Communications of the ACM, 61(10):36–43,436 2018.437
[22] S. Lundberg and S-I. Lee. A unified approach to interpreting model predictions. In I. Guyon,438 U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors,439 Proc. of NIPS’17, pages 4765–4774, 2017.440
[23] T. Miller. Explanation in artificial intelligence: Insights from the social sciences. Artificial441 Intelligence, 267:1–38, 2019.442
[24] Ch. Molnar. Interpretable Machine Learning - A Guide for Making Black Box Models Explain-443 able. Leanpub, 2019.444
[25] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,445 P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher,446 M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine447 Learning Research, 12:2825–2830, 2011.448
[26] J. R. Quinlan. Induction of decision trees. Machine Learning, 1(1):81–106, 1986.449 [27] R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence, 32:57–95, 1987.450 [28] M. Ribeiro, S. Singh, and C. Guestrin. “Why should I trust you?”: Explaining the predictions451 of any classifier. In Proc. of KDD’16, pages 97–101, 2016.452 [29] A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining Bayesian network453 classifiers. In Proc. of IJCAI’18, pages 5103–5111, 2018.454 [30] A. Shih, A. Darwiche, and A. Choi. Verifying binarized neural networks by Angluin-style455 learning. In Proc. of SAT’19, pages 354–370, 2019.456 [31] G.S. Tseitin. On the complexity of derivation in propositional calculus, chapter Structures in457 Constructive Mathematics and Mathematical Logic, pages 115–125. Steklov Mathematical458 Institute, 1968.459
[32] F. Wotawa. A variant of Reiter’s hitting-set algorithm. Inf. Process. Lett., 79(1):45–51, 2001.460
Checklist461
1. For all authors...462 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s463 contributions and scope? [Yes]464 (b) Did you describe the limitations of your work? [Yes]465 (c) Did you discuss any potential negative societal impacts of your work? [No] One cannot466 expect any negative impact (the paper is about explaining predictions).467 (d) Have you read the ethics review guidelines and ensured that your paper conforms to468 them? [Yes]469 2. If you are including theoretical results...470
(a) Did you state the full set of assumptions of all theoretical results? [Yes]471 (b) Did you include complete proofs of all theoretical results? [Yes] As a supplementary472 material.473 3. If you ran experiments...474
(a) Did you include the code, data, and instructions needed to reproduce the main experi-475 mental results (either in the supplemental material or as a URL)? [Yes]476
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they477 were chosen)? [Yes]478
(c) Did you report error bars (e.g., with respect to the random seed after running experi-479 ments multiple times)? [No] But the results we obtained have been averaged over a480 number of trials.481
(d) Did you include the total amount of compute and the type of resources used (e.g., type482 of GPUs, internal cluster, or cloud provider)? [Yes]483
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...484 (a) If your work uses existing assets, did you cite the creators? [Yes]485 (b) Did you mention the license of the assets? [Yes]486 (c) Did you include any new assets either in the supplemental material or as a URL? [Yes]487 The pieces of software we used are furnished as a supplementary material.488 (d) Did you discuss whether and how consent was obtained from people whose data you’re489 using/curating? [No] This issue is irrelevant for this paper.490 (e) Did you discuss whether the data you are using/curating contains personally identifiable491 information or offensive content? [No] The datasets we used are anonymized and do492 not contain personally identifiable information or offensive content.493
5. If you used crowdsourcing or conducted research with human subjects...494 (a) Did you include the full text of instructions given to participants and screenshots, if495 applicable? [No] We did not use crowdsourcing or conducted research with human496 subjects.497
(b) Did you describe any potential participant risks, with links to Institutional Review498 Board (IRB) approvals, if applicable? [No] We did not use crowdsourcing or conducted499 research with human subjects.500
(c) Did you include the estimated hourly wage paid to participants and the total amount501 spent on participant compensation? [No] We did not use crowdsourcing or conducted502 research with human subjects.503

Review summaries:
This paper considers the explainability of decision trees.  By conventional wisdom, decision trees are considered interpretable, although this paper explores this notion much more deeply.  Namely, they show that "good" explanations (in some specific sense) are not necessarily tractable with decision trees, and that explaining the behavior of a decision can still be a non-trivial problem.  The authors further provide another novel way of assigning weight to the importance of a feature in a classifier's decision.