On the Explanatory Power of Decision Trees
Authors: Gilles AUDEMARD
Steve Bellart
Louenas Bounia
Frédéric Koriche
Jean-Marie Lagniez
Pierre Marquis
Venue: NeurIPS 2021 Submitted (2021)
Keywords: explainable AI
decision tree

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.

On the Explanatory Power of Decision Trees
Anonymous Author(s) Affiliation Address email
Abstract
Decision trees have long been recognized as models of choice in sensitive applica- tions where interpretability is of paramount importance. In this paper, examine the computational ability of Boolean decision trees in deriving, minimizing, and counting sufficient reasons and contrastive explanations. We prove that the set 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 he out of reach. addition, computing 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 least 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 feature and the number of sufficient reasons can be obtained via 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 decision tree can be derived, minimized and counted polynomial time.
3
5
10
11
12
or in every
13
14
15
16
17
18
20
Introduction
23 In essence, explaining a decision to a person to give the details or reasons that help a person (the explainee) understand why the decision has been made. This is significant issue especially 25 when decisions are made by Machine Learning (ML) models, such as random forests, Markov networks, support vector machines, and deep neural networks. Actually, with the growing number 27 of applications that rely on MI. techniques, researches on eXplainable AI (XAI) have become increasingly important, by providing efficient methods for interpreting ML models, and explaining
29 their decisions (see for instance [10 11 [ [3, 19 22 23 24 28 30).
When dealing with Boolean classifiers, which is what we do in this paper, two decisions are possible, 31 only: for the instances classified as positive instances, and 0 for the remaining ones (the negative instances). Whatever the way has been classified, explainee may seek for explanations from 33 two distinct types [23]. On the one hand, abductive explanations for z are intended to explain why æ has been classified in the way it has been classified by the ML model (thus, addressing the "Why?" 35 question). On the other hand, the purpose of contrastive (also known as counterfactual) explanations for is to explain why has not been classified by the ML model the explainee expected it (thus,
37 addressing the "Why not?" question). In both cases, explanations that are as simple as possible are size minimality).
preferred (where simplicity modeled irredundancy,
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

39
Although there is no formal notion of interpretabillty [2I], for classification problems, decision trees
40
B [6 are arguably among the most interpretable ML models. Because of their interpretability. decision trees are often considered as target models for distilling a black-box model into compre-
41
42
hensible one 4 1Q] Furthermore, decision trees are often the components of choice for building
43
(less interpretable, but potentially more accurate) ensemble classifiers, such as random forests (2) and gradient boosted decision trees [5]
44
45
The interpretability of decision trees is endowed with two key characteristics. On the one hand, decision trees are transparent: each node in a decision tree has some meaning, and the principles used for generating all nodes can be explained. On the other hand, decision trees are locally explainable: by construction of a decision tree T, any imput instance æ is mapped to unique root-to-leaf path that yields to decision label. The subset of (positive and negative) features ty occurring in the
46
47
48
49
50 path used to find the right label or O for x in the decision tree T can be viewed as a "direct reason" " for classifying x as a positive instance or as a negative instance. 1/ is an abductive explanation for
51
52 a given T. which explains why x has been classified by T as has been classified. Indeed, every instance x' that coincides with on Ey is classified by T in the same way as However, such 54 "direct reasons" can contain arbitrarily many redundant features [7.. This motivates to take account for other types of abductive explanations in the case of decision trees, namely, sufficient reasons 7 (also known as prime implicant explanations (291), that are irredundant abductive explanations, and minimal sufficient reasons (i.e., those sufficient reasons of minimal size).
53
56
58 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. When this is the case, generating the full set of sufficient reasons (i.e., the complete reason for the instance (7] is typically 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. Though deriving the explanatory importance of feature in the set of sufficient reasons and determining the cardinality of this set are two computationally demanding tasks, we show how they can be achieved thanks to model counting operation, which turns out to be practical in many cases. We also explain how to enumerate sufficient reasons of minimal size, which is a way to count them when they are not too numerous. We finally show that, from computational standpoint, contrastive explanations highly depart from sufficient reasons, Indeed, the set of all contrastive explanations for an instance given a decision tree can be computed in polynomial time. As a consequence, such explanations can also be minimized and counted in polynomial time.
59
60
61
62
63
64
65
66
68
69
70
71
72
73
74
75
78
The rest of the paper is organized as follows. Preliminaries about decision trees, abductive reasons, and contrastive explanations are given in Section 2 The computation of all sufficient reasons is considered in Section 3 Necessary and relevant features are presented in this section, as well as the approach for assessing the explanatory importance of a feature and for counting the number of
78
79
80
81 sufficient reasons. We also explain there how minimal sufficient reasons can be enumerated. An
82 algorithm for computing all the contrastive explanations for the instance given the decision tree is
83 presented in Section Experimental results are reported in Section [ Finally, Section 6 concludes
84 the paper. All the proofs and additional empirical results are reported as supplementary material.
2 Decision Trees, Abductive and Contrastive Explanations
85
86
For an integer nt, let [n]] be the set {1, m). By F, we denote the class of all Boolean functions from (0. 1)a to {0, 1}. and we use X,, = fz1. F to denote the set of input Boolean variables,
87
88 corresponding to the features under consideration. Any assignment a E (0, 1)a is called instance.
89 If f(=) = 1 for some f E Fa. then x is called a model of f. x is a positive instance when f(x) = 1
90 and negative instance when ((x) = 0.
91 We refer to I as a propositional formula when described using the Boolean connectives A (conjunction), V (disjunction) and - (negation), together with the Boolean constants 1 (true) and 0

---

2's
FF
2
Z4
T4
JF4
IF
0
Figure I: A decision tree T for recognizing Cattleya orchids. The left (resp. right) child of any decision node labelled by æ; corresponds to the assignment zi to (resp. 1).
93
(false). As usual, literal f is variable (a positive literal) or its negation -.; also denoted T; (a negative literal). positive literal z; is associated with a positive feature (i.e., 24, is set to 1). while negative literal F, is associated with negative feature (i.e., F; is set to 0), A term (or monomial) t is conjunction of literals, and a clause is disjunction of literals. A DNF formula of terms and CNF formula is conjunction of clauses. The set of variables occurring in formula denoted Var(f). formula f is consistent and only if it has a model. CNF formula is monotone whenever every occurrence of literal in the formula has the same polarity (i.e., if literal occurs positively (resp. negatively) in the formula, then it does not have any negative (resp. positive) occurrence in the formula). A formula fi implies a formula f2, noted fi - f2. if and only if every model of fi is a model of f2. Two formulae fi and f2 are equivalent, noted fi = f2 whenever they have the same models. The conditioning of formula f by literal E, denoted f é, is the formula obtained from f by replacing each occurrence of x; with (resp. 0) and each occurrence of T. with 0 (resp. 1) if I; (resp. = F.).
94
95
96
disjunction
97
96
99
100
102
104
106
In what follows, we shall often treat assignments as terms, and terms and clauses as sets of literals. Given an assignment E {0, 1)", the corresponding term is defined as
107
1- A 2 where x. = F; and x! = 22
A term covers an assignment if tz. An implicant of Boolean function f is term that implies f. A prime implicant of ff is an implicant of such that no proper subset of is an implicant of f. Dually, an implicate of Boolean function f is a clause that is implied by and prime implicate of is an implicate e of f such that no proper subset of e is an implicate of
109
111
112
With these basic notions in hand, we shall focus on the following representation class of Boolean functions:
113
Definition (Decision Tree). A (Boolean) decision tree a binary tree T, each of whose internal nodes is labeled with one of imput Boolean variables, and whose leaves are labeled 0 or 1. Every variable assumed (without loss of generality) to appear at most once on any root-to-leaf path pread-once property). The value T(x)) E {0,1) 1} T on an input instance x is given by the label of the leaf reached from the root as follows: at each node, go to the left right child depending on whether the input value of the corresponding variable is 0 or 1, respectively. The size of T, denoted
115
116
117
118
119
120
[T) is given by the number of its nodes.
The class of decision trees over X,, is denoted DT,, It is well-known that any decision tree T E DT, can be transformed in linear time into an equivalent disjunction of terms, denoted DTF where each term corresponds to a path from the root to leaf labeled with 1. Dually, T can be transformed linear time into conjunction of clauses, denoted CNF(T), where each clause is the negation of the term describing a path from the root to a leaf labeled with O.
122
123
124
126
For illustration, the following toy example will be used throughout the paper as a running example:
Example 1. The decision tree in Figure 7 separates Cautleya orchids from other orchids using the following features: Z1: "has fragrant flowers", N2. "has one or two leaves". Zz. "has large flowers". and zzz "is sympodial".
128
3

---

130
As a salient characteristic, decision trees convey a single explicit abductive explanation for classifying any ipput instance:
131
132
Definition 2 (Direct Reason), Let T E DIn and x E 10, The direct reason for x given T is the term, denoted 1g- corresponding to the unique root-to-leaf path of that is compatible with x.
133
134
Another important notion of abductive explanations is the following concept of sufficient reason that, unlike the notion of direct reason, is not specific to decision trees:
135
136
Definition (Sufficient Reason). Let f E Fn and I E {0, 1 such that f(x) = 1 (resp. f(x) = 0). A sufficient reason for z given f is prime implicant t of f (resp. -f) that covers sr(z, ( f) denotes the set of sufficient reasons for x: given f.
138
139
Thus, a sufficient reason 7 (also known as prime implicant explanation [29] for an instance x given a class described by a Boolean function f is subset of the characteristics of æ that is minimal w.r.t. set inclusion such that any instance x' sharing this set of characteristics is classified by f as æ is. Thus, when f(æ)= = 1, t is a sufficient reason for I given f if and only if t is a prime implicant of f such that æ implies t, and when fx)
140
141
142
143
t is sufficient reason for æ given if and only if is a prime implicant of -f such that covers æ. Accordingly, sufficient reasons are suited to explain why the instance at hand æ has been classified by f as it has been classified. Unlike direct reasons [7] sufficient reasons do not contain any redundant feature.
144
145
148
147
When considering the sufficient reasons of the input instance, one may be interested in focusing on the shortest ones, alias the minimal sufficient reasons. Those reasons are valuable since conciseness often desirable property of explanations (Occam's razor). Formally:
148
149
Definition& 4 (Minimal Sufficient Reason). Let f e Fn and {0, 1)" A minimal sufficient reason for x given f is a sufficient reason for x given f that contains a minimal number of literals.
151
152
Finally, unlike direct and (possibly minimal) sufficient reasons that aim explain the classification of the instance x under consideration as achieved by the classifier J. contrastive explanations are valuable when has not been classified by expected by the explainee. In this case, one looks for minimal subsets of the features that when switched in æ are enough to get instances that are classified positively (resp. negatively) by if æ is classified negatively (resp. positively) by f. Formally, contrastive explanation for x given f [15] is a subset ł of the characteristies of æ that is minimal w.r.t set inclusion among those such that at least one instance x' that coincides with æ except on the characteristics from t is not classified by f as x is.
153
154
155
156
157
158
159
160
Definition 5 (Contrastive Explanation). Let f E Fn and x E (0.1)" such that f(x) = 1 (resp. f(x) = 0). A contrastive explanation for æ given is term over X,, such that t S tw. tu t is not an implicant of J (resp. -f), and for every E E I, L), [E} does not satisfy this last condition.
162
165
Example 2. Based on our running example, we can observe that T(x) = 1 for the instance = (1, 1,,1,1, 1, The direct reason for given T is the term 1/2 x1 A x2 A xz A Na. I1 A xa and I2 23 A x. are the sufficient reasons for x given T. X1 A AT, is the unique minimal sufficient reason for x given T. IA. 21 A 22, and xı A 23 are the contrastive explanations for x given T. Thus, the
165
186
187
instance (1, 1, 1,0) 0) that differs with x only on xs is not classified by T as x is ((1, 1, 1, 0) is classified as a negative instance).
189
We mention in passing that when dealing with decision trees T, we could have focused only on explanations for the positive instances æ given T. This comes from the fact that DT,, is closed under negation, in the sense that for any T E DT,,- -T can be obtained by just replacing from T the label of each leaf with its complement. So, for any instance x E {0. 1 a direct reason (resp. sufficient reason, minimal sufficient reason, contrastive explanation) explaining why T(x) = 0 is precisely the
170
171
172
173
174
same as a direct reason (resp. sufficient reason, minimal sufficient reason, contrastive explanation) explaining why (z) = 1. Considering T or its negation -T' has no computational impact since
175
178
-I can be computed in time linear in the size of T.
3 Computing All Sufficient Reasons
177
178
Sufficient reasons can be exponentially numerous. When switching from the direct reason for 179 an instance (that unique but not always redundancy-free to its sufficient reasons, a main obstacle to be dealt with lies in the number of reasons to be considered. Indeed, even for the restricted class

---

3
Figure 2: Two sufficient reasons for an mnist instance (top), and an explanatory heat map and the explanatory features for an mnist instance (bottom).
of decision trees with logarithmic depth, an input instance have exponentially many sufficient reasons:
182
185
Proposition There is a decision tree T DT, of depth log (n + 1) such that for any x E {0, 13". the number of sufficient reasons for æ given is at least
184
185
By definition, the minimal sufficient reasons for x given T cannot be more numerous than its sufficient reasons. However, focusing on minimal sufficient reasons does not solve the problem since an instance can also have exponentially many minimal sufficient reasons:
186
187
188
such that n is odd, there is a decision tree T DT,, of depth n+1 such that contains 2n nodes and there is an instance x E {0, 1)" such that the number of minimal sufficient reasons for given T is equal to 2yn-I.
Proposition 2. For every
189
191
In many practical cases, the number of sufficient reasons for an instance given a decision tree can (top) shows mnist instance (the leftmost subfigure) that has 482 185 073 664 sufficient reasons. Among them there are very dissimilar sufficient reasons. As an illustration, the two rightmost subfigures present two sufficient reasons for this instance, and they differ on many features (blue (resp. red) dots correspond to pixels on (resp. off)).
be very large. Figure (top)
193
185
For such datasets, computing the set of all the sufficient reasons for given instance is not always feasible. Furthermore, the computation succeeds but the number of sufficient reasons is huge, their (disjunctively interpreted) set, alias the complete reason for the instance 77, can hardly be considered as intelligible by the explainee. Finally, due to the number of sufficient reasons and their diversity, deriving one of them is not informative enough. Thus, one needs to design approaches to synthesizing their set while avoiding the two pitfalls (the computational one and the informational one).
197
199
201
Synthesizing the set of sufficient reasons. In this objective, the following notions of necessary / reelevann features appear useful. These notions of necessity and relevance echo the ones that have been considered in [9] for logic-based abduction.
203
204
Definition 6 (Exp (Explanatory Features). Let f E F... and x {0,1)" be instance. Let be explanation rype.
206
207
A literal over Xn, is necessary feature for the family e of explanations for x given f if and only if belongs to every explanation t. for a given f such that is of type e. Nece(æ, f) denotes the set of all necessary features for the family of explanations for given f.
208
209
210
A literal over Xn a relevant feature for the family e of explanations for æ given f if and only if & belongs to at least one explanation t for x given f such that t is of type e. Rel,( f) denotes the set of all relevant features for the family of explanations for
212
For instance, can be when the sufficient reasons for given f are targeted or when the contrastive explanations for given are targeted.
5

---

213
given f. Irre(a,f) which is the complement of Rele(x.1 f) in the set of all literals over X denotes the set of all irrelevant features for the family of explanations for a given f.
214
215
The necessary (resp. irrelevant) features for the family & of sufficient reasons for x given f are the most (resp. less) important features for explaining the classification of æ by ʃ. since they belong to every (resp. no) sufficient reason for x given J.
216
217
When single sufficient reason t for a given f has been computed, the cardinality of t deprived from the features of Necs(2: f) is small, and the cardinality of the symmetric difference between t and Rel (x, f) is small well, & can be viewed as a good representative of the complete reason for æ given f in the sense that a sufficient reason for x given f that differs a lot from cannot exist.
219
221
222
In the case when f is a decision tree T, though the set of all sufficient reasons for æ given T cannot be generated when it is too large, Nec, (x. f), Rel, (2. f). and Irr (rr,(x/)) f) can be derived efficiently: and Ix,,(x,7 T)
223
224
Proposition 3. Let T E DT and x E {0, 1 1).. Computing (e,, T), can be done in O( + (T]) (T]) time.
225
226
Going a step further consists in evaluating the explanatory importance of every (positive or negative) feature:
227
Definition 7 (Explanatory Importance). Let f E Fr and æ E {0, be an instance. Let be an explanation type, and Ee(x, f) the set of all explanations for x given that are of type e. The explanatory importance of a literal l over Xn for x given f w.r.t e is given by
Imp, (e, 2l, #(11 E Ee J) :EE)))
#(E f))
Example 3. On the running example, we have (xc,((xT)) T) = (x1), }. and Rel, T) (I1, I2. Iz.
229
J.). We also have Imp, (I., ar, Tr = 1, Imp, (1), x, T) = Imp,, (x2, x. T) = Imp e (53, x, T) = 2 and Tmp, (C, ar, T) 0.ror every other literal E (the negative ones over {21, U2 33, }.
230
231
The notion of explanatory importance must not be confused with the notions of feature importance (which can be defined and assessed in many different ways): the former is local (i.e., relative to an instance) and not global, it concerns literals and not variables (polarity matters), and it is about the explanation task, not the prediction one.
233
235
In order to compute the explanatory importance of a literal, straightforward approach consists in enumerating the explanations of (z, f). This is feasible when this set is not too large, which is not always the case for sufficient reasons even when f a decision tree T. Thus, for dealing with the remaining case, an alternative approach must be looked for.
236
237
238
239
(,, We designed such an approach for computing Imp,,e, æx T). We know that sa T) is by construc-
tion the set of prime implicants of g = (cn La c E CTF( Thus, we exploited the translation presented in (18) showing how to associate in polynomial time with a given CNF formula (here,
240
241
242
g) another formula (over a distinct set of variables), let us say h, such that the models of h are in one-to-one correspondence with the prime implicants of g. In our case, the translation can be simplified because is a monotone CNF formula. Since h is not primarily a CNF formula, leveraging Tsetin transformation
243
24
245
3T we turned h in linear time into a query--quivatee that every auxiliary variable that is introduced in i is defined from the other variables (those occurring in h), so that the number of models of é the same as the number of models of h. Finally, we took advantage of the compilation -bsed model counter D4 (20] to compile i into d-DNNF circuit (6], and this enabled us to compute in time polynomial reasons and the explanatory importance of every literal (indeed, the d D-DNNF language supports in polytime the model counting query and the conditioning transformation (8). We show in Section that, despite a high complexity in the worst case (the size of can be exponential in [T),, this approach based on knowledge compilation proves quite efficient in practice.
CNF formula i. Note
246
247
249
the size of i both the number of sufficient
251
253
254
Clearly enough, when Imp_ (f. xz T) has been computed for every L, one can easily generate ex- planatory heat maps. Figure (botttom) shows an mnist instance (the leftmost subfigure) that has 19 115 685 sufficient reasons, 6 necessary literals, and 94 relevant literals. The central subfigure is the corresponding heat map. Blue (resp. red) pixels correspond to positive (resp. negative)
255
256
257
literals in the instance, and the intensity of the color aims to reflect the explanatory importance of the corresponding literal. The rightmost subfigure gives the explanatory features (dark pixels are associated with necessary literals, and light pixels to relevant literals).
259

---

261
Enumerating the minimal sufficient reasons. An approach to synthesizing the set of sufficient reasons consists focusing on the minimal ones. Indeed. though the set of minimal sufficient reasons for an instance given decision tree can be exponentially large, the number of minimal sufficient reasons cannot exceed the number of sufficient reasons, and it can be significantly lower in practice.
262
264
285
However, unlike sufficient reasons that can be generated in polynomial time using greedy algorithm (see e.g.. (7). computing minimal reasons is not an easy task:
268
267
Proposition 4. Let T E n and a E {0, 1 1)". Computing a minimal sufficient reason for a given T
268
NP-hard.
269
Despite this intractability result, minimal sufficient reasons can be generated in many practical cases. A common approach for handling NP- -pPotiiiintioon problems is rely on modern constraint solvers. One follows this direction here and casts the task of finding minimal sufficient reasons as a Boolcan constraint optimization problem. We first need to recall that PARTIAL MAXSAT problem consists of pair (Caaft, Chard) where Czoft and Chard are (finite) set of clauses. The goal is to find Boolean assignment that maximizes the number of clauses in Csoft that are satisfied, while satisfying all
271
273
275
clauses in Chard-
Proposition 5. Let T be decision tree in DI, and x (0, 1)"h be an instance such that ((x) 1. Let (Suuft, Crava) be an instance of the PARTIAL MAXSAT problem such that:
Croft = { Is E [wm) U (m:: I3 E ) and Chard = {c tu : c CNF(T))
278
The intersection of to with tx- where x² is an optimal solution of (Chard, Csoft), is minimal 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 of PARTIAL MAXSAT as above, except that Chard = {c n tm c CNF(-T))
279
280
Finally, one can take advantage of this PARTIAL MAXSAT characterization for generating a preset number of minimal sufficient reasons (basically, one generates first reason t. then one adds to Chard the negation of l as clause well as a CNF encoding of a cardinality constraint for ensuring that the next reasons to be generated have the same size as the one of I, and we resume until the bound is reached or no solution exists).
281
283
4
Computing All Contrastive Explanations
206
Interestingly, has been shown that sufficient reasons and contrastive explanations are connected by minimal hitting set duality [15]. This duality can be leveraged to derive one of the two sets of
287
206
explanations from the other one using algorithms for computing minimal hitting sets [27 32
289
However, in the case of decision trees, a more direct and much more efficient approach to derive all the contrastive ex explanations for (0, 11 given T DT,, can be designed. Indeed, unlike what happens for sufficient reasons (see Section 3 the set of all contrastive explanations for x E {0, 1)" given& a decision tree T E DT, can be computed in polynomial time from x and T::
281
282
283
Proposition 6. The set of all contrastive explanations for x E {0, 1)" given a decision tree T E DT, main(fc (fc n th
294
can be computed in time polynomial in n + [T'] as min
CNF(f)), S).
285
Example 4. On the running example, we have CNF(T) = {an V 22, In VI v3, In V V IA, Ji Vx2 V.r V22 VI3V T. VV3
296
Thus, with x 1,,1,111, 1), we ( V2, I1 V 23, J1 which corresponds to the contrastive
297
have min min(fcnt, tx : c CNF explanations ø1 T2, 31 I3, 21 for x given T' (viewing clauses and terms as sets of literals).
298
299
As straightforward consequences of Proposition 6 computing necessary / relevant features and computing the explanatory importance of features w.r.t. contrastive explanations can be achieved in time polynomial in n + [2). Similarly, statistics about the size of contrastive explanations can be easily established, and contrastive explanations can be easily minimized and counted.
301
302
5 Experiments
304
Empirical setting. We have considered 90 datasets, which are standard benchmarks from the well- known repositories Kaggle (ww..wwgwgg kaggle. com), OpenML openml. org), and UCI (archive

---

Table 1: Empirical results based 12 datasets.
Decusion
ISufficiend
IMinimall
WNec. Pestures
#Rol. Features
Daiisee
S.A
IN
4B
med
med
194
med
mix
med
mas
recidivism
63.41
13828. 50
147.60
14
22
13
22
19
60
96
adult
$1.36
12934.00
2974.80
16
36
16
36
263
543
bank marketing
21
247
bunk
$8, 99
5523.60
977.80
13
24
13
24
15
200
330
lending loan
13.49
2610.40
1131.40
16
31
16
31
25
226
442
contraceptive
50,44
1252.20
58.60
20
11
20
compas
christine
63.35
855:20
426
12
47
12
47
201
fanm ads
86.75
$64.80
264.60
20
99
20
99
16
92
73
192
miiste9
95.47
$39.60
267.90
30
22
30
166
spambase
91.94
535.40
15
mmist38
96.07
505.60
251.40
19
28
19
28
93.50
157
#Suticient
#Consrastive
Koontastivel
#Minimal
Dataset
med
max
med
max
med
mod
max
recidivism
10087
9734080
54
145
16
2
164
adult
157383572200 5000000000
201
256
marketting
2 716037752113844400000000
bank
2 99339911979018800000
150
277
13
168
lending Joan
45922 4990259918895575
9482432422 X0TTE22AA01100000000000000000000
157
311
12
3
192
20.50
4272
21
52
compas
16
33
chrasine
63108
2167728434744
71
151
2
4096
farm ads
1177.50
921895392
59
166
10
2
L0000
maiss4y
7392388
10000
spambase
15712
2535069312
mnis.38
14849376
16922386736600
62
107
11
32
3072
306
ics. uci. edu/ml/) ml/) mnist38 and mnist49 are subsets of the mnist dataset, restricted to the instances of 3 and (resp. and 9) digits. Because some datasets are suited the multi-label classification task, we used the standard "one versus all" policy to deal with them: all the classes but the target one are considered as the complementary class of the target. Categorical features have been treated as arbitrary numbers (the scale is nominal). As to numeric features, no data preprocessing has taken place: these features have been binarized on- on-the-fly by the decision tree learning algorithm that has been used.
307
309
311
313
For every benchmark b, a 10-fold cross validation process has been achieved. Namely, set of 10 decision trees Tú have been computed and evaluated from the labelled instances of b, partitioned into 10 parts. One part was used as the test set and the remaining 9 parts as the training set for generating a decision tree. This tree is thus in 1-to-1 correspondence with the test set chosen within the whole
314
315
316
317
dataset b. The classification performance for was measured as the mean accuracy obtained over the 10 decision trees generated from b. The CART algorithm, and more specifically its implementation provided by the Scikit-Learn library 25 has been used to learn decision trees. All hyper-parametie of the learning algorithm have been set to their default value. Notably, decision trees have been learned using the Gini criterion, and without any maximal depth or any other manual limitation.
319
321
322
For each benchmark 6, each decision tree Th, and a subset of at most 100 instances æ picked up random in the test set following a uniform distribution, we computed a sufficient reason for æ given T3 (using the standard greedy algorithm run on the direct reason fT)), and minimal sufficient reason for æ given T3 using the PARTIAL MAXSAT encoding presented in Proposition [ This enabled us to draw some statistics (median, maximum) about the sizes of the reasons that have been generated. Using the algorithm presented in the proof Proposition we also derived the necessary and relevant explanatory features for each and again drew some statistics about them. Exploiting the model counter D4, we computed the number of sufficient reasons for & given Tb, as well as the explanatory importance of every feature. Taking advantage of the algorithm given in Proposition we computed the number of contrastive explanations for æ given Tù. and drew some statistics about those numbers and about the sizes of the contrastive explanations. Finally, using the approach described in Section 3 we enumerated all the minimal sufficient reasons for x given T, up to a limit statistics about the numbers of minimal sufficient reasons. Of course, for each computation, we measured the corresponding runtimes since this fundamental to determine the extent to which the algorithms are practical (details are provided
323
324
325
327
329
331
333
of 10 000, and again drew
335
336
supplementary material).
337
All the experiments have been conducted on computer equipped with Intel(R) XEON E5-2637 CPU @ 3.5 GHz and 128 GiB of memory. D4 [20] was run with its default parameters. For computing

---

339
minimal reasons, we used the Pysat library [14, which provides the implementation of the RC2
340
PARTIAL MAXSAT solver. This solver was run using the parameters corresponding to the "Glucose" setting. A time-out of 100s per instance was set for D4.
342
Results. Table (top and bottom) reports an excerpt of our results, focusing on 12 benchmarks out of 90 (the selected datasets are among those containing many instances and/or many features). The leftmost column gives the name of the dataset b. Columns %A, %N,, and # B give, respectively, the mean accuracy over the 10 decision trees, the average number of nodes in those trees, and the average number of binary features they are based on. The next columns give statistics (median, maximum) about, respectively. the size of the sufficient reasons (ISufficientl) and of the minimal sufficient reasons (lMinimall) that have been computed, as well as about the number of necessary NeN. Features) and relevant (#Rel. Features) features that appear in the full set of sufficient reasons for the instance. Table T (bottom) give statistics (median, maximum) about, respectively, the number of sufficient reasons (Fufffciient), the number of contrastive explanations (# Contrastivve) and their sizes (IContrastivel), and finally the number of minimal sufficient reasons (# (#Minimal).
343
344
346
348
350
352
As to the computation times, it turns out that all the algorithms described in the previous sections proved as efficient in practice. This is not surprising for those algorithms having a polytime worst-case complexity (the greedy algorithm for computing sufficient reason, the one for deriving explanatory features, and the one for computing all the contrastive explanations).
354
356
was less obvious at first sight for the algorithms used for counting the number of sufficient reasons and for computing the explanatory importance of features. However, all the computations that have been run have terminated in due time, except for 3 datasets out of 90, namely adult, fannkmarketing. and bank. For these datasets, the time limit of 100s has been reached for, respectively, 203, 150, and 336 instances out of 1000 (in this case, the median number of sufficient reasons has not been reported). Notably, for all the 90 datasets but those 3, the median time required for counting the number of sufficient reasons and computing the explanatory importance of features never exceeded Is. Computing a minimal sufficient reason, and more generally all such reasons looked challenging as well, due to both the intrinsic complexity of computing a minimal sufficient reason and to their number. Nevertheless, our enumeration algorithm succeeded in deriving all the minimal sufficient reasons for every dataset except out of 90, namely farm-ads mnist49, and gisette. For these datasets, the limit of 10 000 reasons has been reached for, respectively, 5, 16, and 3 instances out of 1000. Interestingly, the median time needed to derive all the minimal sufficient reasons for the instances for which the computation has been successful exceeded Is only for 2 datasets (adult and bank_ Bank_marketing)
358
360
362
363
364
365
366
387
388
389
370
Beyond providing evidence that the number of reasons can be huge, experiments have highlighted that the greedy algorithm for deriving a sufficient reason computes in practice a minimal sufficient reason in many cases. They have also shown that the number of explanatory relevant features for an instance is typically much lower than the number of binary features used to describe it, and that the number of explanatory necessary features is also significantly lower than the number of explanatory relevant features. The gap between the two explains the possibly enormous number of sufficient reasons. When considering the full set of reasons, a considerable difference between the number of sufficient reasons and the number of minimal sufficient reasons can also be observed. Finally, like minimal sufficient reasons, the number of contrastive explanations appears in many cases not very large, which is a good point from an intelligibility perspective.
372
373
374
375
378
377
378
379
380
6
Conclusion
382 In light of our results, it turns out that the explanatory power of decision trees goes far beyond its ability to generate direct reasons. From a decision tree, the explanatory importance of features and the minimal sufficient reasons for an instance can be computed efficiently most of the time. For decision trees, fully addressing the "Why not?" question also appears easier than fully addressing the "Why?" question: computing the full set of sufficient reasons for the instance at hand is typically out of reach, while computing its full set of contrastive explanations is tractable.
384
386
387
388
Accordingly, the language of decision trees appears not only as appealing for the learning purpose,
389
but also as good target when one needs to reason on the various forms of explanations (abductive and contrastive ones) associated with the predictions made. This coheres with (and completes) the results reported in [I] showing that many other explanation and verification tasks are tractable for decision tree classifiers.
390
392
9

---

References
393
394
[1] G. Audemard, F. Koriche, and P. Marquis. On tractable XAI queries based on compiled representations. In Proc. of KR 20, pages 838 849, 2020.
395
396
[2] L. Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
397
[] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
398
[4] L. Breiman and N. Shang.
Born again trees.
Technical report,
400
http::/wwww.stt.bbkekkle..ce
Saiman/BAtrres.pple 1996.
401
[5] Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In Proc. of KDD 16, page 785-794, 2016.
[6] A. Darwiche. Decomposable negation normal form. Journal of the Association for Computing Machinery, 48 4844)6608-647, 2001.
404
405
[7] A. Darwiche and A. Hirth. On the reasons behind decisions. In Proc. of ECAI'20, pages 712-720, 2020.
407
[8] A. Darwiche and P. Marquis, A knowledge compilation map. Journal of Artificial Intelligence Research, 1:229-2664, 2002.
408
409
[9] Th. Eiter and G. Gottlob. The complexity of logic- based abduction. Journal of the Association for Computing Machinery, 42(1):3-42, 1995.
410
411
[10] N. Frosst and G. E. Hinton. Distilling a neural network into a soft decision tree. In Proc. of the First International Workshop on Comprehensibility and Explanation in Al and MI., volume 2071 of CEUR Workshop Proceedings. CEUR-WSS WS.org, 2017.
413
414
[1]] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi. A survey of 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 methods in deep neural networks. In Proc. of NewrlPS' 19, pages 9747-9748, 2019.
417
418
[13] J. Huysmans, K. Dejaeger, C. Mues, J. Vanthienen, and B. Baesens. An empirical evaluation of
the comprchensibility of decision table, tree and rule based predictive models. Decis. Support Syst., 51(1):141-154, 2011.
420
421
[14] A. Ignatiev, A. Morgado, and J. Marques- Silva. PySAT: A Python toolkit for prototyping with SAT oracles. In Proc. of SAT' 18, pages
423
[15] A. Ignatiev, N. Narodytska, N. Asher, and J. Marques-Silva. On relating 'why?" and 'why not?' explanations. CoRR, abs/2012. 1067, 2020.
424
425
[16] A. Ignatiev, N. Narodytska, and J. Marques-Silva Abduction based explanations for machine learning models. In Proc. of AAA/ 19, pages 1511-1519, 2019.
426
427
[17] Y. Izza, A. Ignatiev, and J. Marques-Silva. On explaining decision trees. CoRR, abs/2010.11034
428
2020.
429
[18] S. Jabbour, Marques-Silva. L. Sais, and Y. Salhi. Enumerating prime implicants of proposi-
430
tional formulae in conjunctive normal form. In Proc. of JELIA 14, pages 152-165, 2014.
431
[19] B. Kim, M. Wattenberg, J. Gilmer, C. Cai, J. Wexler, F. Viegas, and R. Sayres. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In Proc. of ICML' 18, pages 2668-2677, 2018
432
433
434
[20] J.-M. Lagniez and P. Marquis. An Improved Decision-DNNF Compiler. In Proc. of 1JCAI'17, pages 667-673, 2017.
435
[21] Z. C. Lipton. The mythos of model interpretability. Communications of the ACM, 61(10):36 43, 2018.
437
438
[22] S. Lundberg and S-I. Lee. unified approach to interpreting model predictions. In I. Guyon,
U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Proc. of 17, pages 4765-4774, 2017.
440
441
[23] Miller. Explanation artificial intelligence: Insights from the social sciences. Artificial Intelligence, 267:1-38, 2019.
10

---

[24]
Ch. Molnar. Interpretable Machine Learning A Guide for Making Black Box Models Explain- able. Leanpub, 2019.
444
[25]
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, 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 Machine Learning Research, 12:2825-2830, 2011.
448
449
[26] J. R. Quinlan. Induction of decision trees. Machine Learning, 1(1):81-106, 1986.
450
[27] R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence, 32:57-95, 1987.
[28] M. Ribeiro, S. Singh, and C. Guestrin. "Why should trust you?": Explaining the predictions
452
of any classifier. In Proc. of KDD'I6, pages 97-101, 2016.
453
[29] A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining Bayesian network classifiers. In Proc. of IJCAI' 18, pages 5103-5111, 2018.
455
[3 A. Shih, A. Darwiche, and A. Choi. Verifying binarized neural networks by Angluin-style learning. In Proc. of SAT' 19, pages 354-370, 2019.
456
[3] G.S. Tseitin. On the complexity of derivation propositional calculus, chapter Structures in Constructive Mathematics and Mathematical Logic, pages 115-125. Steklov Mathematical Institute, 1968.
458
459
[32] F. Wotawa. A variant of Reiter's hitting-set set algorithm. Inf. Process. Lett., 79(1):45-51) 2001.

---

Checklist
461
462
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
464
contributions and scope? [Yes]
465
(b) Did you descrihe the limitations of your work? [Yes]
486
(c) Did you discuss any potential negative societal impacts of your work? [No] One cannot expect any negative impact (the paper is about explaining predictions).
467
468
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results... 470
471
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
472
(b) Did you include complete proofs of all theoretical results? [Yes] As a supplementary material.
473
474
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
476
477
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
478
479
(c) Did you report error bars (e-g., with respect the random seed after running experi-
ments multiple times)? [No] But the results we obtained have been averaged over number of trials.
481
482
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
488
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
485
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as URL? [Yes] The pieces of software we used are furnished as a supplementary material.
488
489
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] This issue is irrelevant for this paper.
490
491
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] The datasets we used are anonymized and do not contain personally identifiable information or offensive content.
493
494
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] We did not use crowdsourcing or conducted research with human subjects.
486
487
498
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No] We did not use crowdsourcing or conducted research with human subjects.
499
500
501
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No] We did not use crowdsourcing or conducted research with human subjects.
503
12


Reviews:
[{"review_id": "tKyb-5VMxIV", "reviewer": "Reviewer_7f2X", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I generally have a favorable opinion on this paper, since it highlights how explaining decision trees is not a solved problem per se, even though almost all people dismiss the explanation of decision trees as uninteresting up front (see, e.g., funding agencies but also including me).\n\nIf expressed purely in terms of logic, then the given results are probably not too surprising.  When one considers the results in the context of explaining decision trees, then they become more interesting.  For example, some of the (negative) results emphasize to me that one should not limit oneself to subsets of the instances being explained (i.e., not just terms as used in prime-implicant explanations and Anchor explanations).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "addressed", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "YBqLo8NQHF", "reviewer": "Reviewer_7zMv", "summary": "The paper argues that information other than what is presented explicitly in a decision tree can be extracted, in some cases efficiently, that is better at explaining the decisions taken according to the decision tree. The paper proceeds to show some statistics about the type of information that is argued for, when considering various datasets.\n", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Ultimately, this is a paper about properties of classical logic and prime implicants. It has nothing to do with a conference on machine learning. Also, just by reading the introduction one can see that the claims made are not surprising, follow from very basic proof techniques, and are probably established in some form or another in any textbook on classical logic for undergraduate students. \n\nTo complicate matters further, the terminology used in the paper is non-standard. E.g., using \"sufficient reason\" for a prime implicant, and then using \"minimal sufficient reason\" to talk about the size of the implicant (not its set-theoretic minimality) is against the intuitive meaning of the concepts \"sufficiency\" and \"minimal sufficiency\", which naturally correspond to implicants and prime implicants.\n\nThe motivation of the paper is also awkward. It first discusses explainability and decision trees to motivate the use of prime implicants, but then shows a mnist dataset and talks about explanations in terms of pixels. Do the authors suggest that one would learn a decision tree with the the pixels being the features? This confounding of decision trees and pixel-based examples seems to run throughout the paper. Perhaps the discussion of decision trees should be dropped altogether (and also the results about computing prime implicants, which is not a novel contribution), and the paper should focus on the introduction of the metric on explanatory power and its empirical evaluation?\n\nIn line with the above, I was expecting the empirical study to give some evidence in support of an otherwise ad hoc definition of explanatory power, but unfortunately the empirical study was an (unneeded) confirmation that formulas can have numerous prime implicants, but few size-minimal prime implicants.\n\nI also found that the paper might be presenting false dilemmas in attempting to motivate things; e.g., the intractability of computing all sufficient reasons, or the intractability of computing even a single minimal sufficient reason. If one wishes to compute all the sufficient reasons, why not simply make do with the path of the decision tree? Is there any evidence that humans find the former more appropriate than the latter as a reasonable explanation? As for the minimal sufficient reason, what evidence is there that minimality (which is in the size of the reason, not in the set theoretic sense) is warranted? I was under the impression, but I could be wrong, that from the early days of AI people realized that size-minimality is a bad compass when judging abductive proofs.\n\nEven if there is something interesting from page 6 onwards, the first half of the paper is sufficiently trivial to diminish the value of the paper.\n\n--- after reading the author response ---\n\nI would like to thank the authors for their response. I am still not clear on certain aspects of the paper.\n\nClearly, using logic for explainability of ML is relevant to the conference. I didn't mean to suggest otherwise. But this paper is about properties of classical logic. The connection to explainability is not that evident. In particular, regarding the point on whether minimality of prime implicants is a reasonable requirement to impose on the explanations, I wonder: if A by itself explains the label of a data point, and B&C together explain the label of that same data point, does minimality suggest that the first explanation is better than the second? \n\nWhat if the label to predict is whether someone can repay their loan, and feature A is \"they live in the suburbs\", whereas features B&C are \"they have low income & they have other loans\". Is it still the case that A is a better explanation than B&C (assuming that both are indeed prime implicants)? As I said in my review, size-minimality is not necessarily what one might be looking for. Maybe it makes sense for the particular application domain (with features being pixels), but the theory developed in this paper is not specific to such features (on the contrary, given the use of DTs I would say it is more geared towards domains amenable to traditional learning and feature-engineering).\n\nI quickly scanned the two papers cited by the authors in their response. Indeed, at least one of the papers discusses minimum-cardinality as a criterion, but does so as part of a comprehensive look at various minimality criteria that have been considered in the literature. That paper mentions conditions under which every minimality criterion is applicable, and their goal is not to take sides. In the submitted paper, on the other hand, the authors do take a side, and they need to argue why minimal-cardinality is the right approach. Just claiming that past works did not disqualify size-minimal abductive proofs is quite different from disqualifying all non-size-minimal proofs.\n\nJust because the use of the results in this paper are for the purposes of XAI, this does not make them novel. Establishing bounds on the number of prime implicants, the complexity of computing them, etc., are questions in logic, and even if classical logic textbooks do not talk about XAI, they do talk about bounds on prime implicants and their complexity (including in the papers cited by the authors).\n\nThe response of the authors that minimality is good for explainability because \"a sufficient reason that includes hundreds of features can hardly be considered as intelligible\" seems to present yet another false dilemma: is minimality the opposite of hundreds of features? What if a minimal sufficient reason did indeed have hundred of features? Would the minimality still make it okay? Or what if a non-minimal sufficient reason had just 3 features? Would its non-minimality make it a bad choice (e.g., the B&C example above)?\n\nI feel that all the above need to be clarified, perhaps by rethinking how to position this work: Does this work really have to do with decision-trees and their explanatory power, or with computing minimal sufficient reasons irrespective of what the original model is? What are the implied assumptions on the use of the theory? Are you assuming traditional engineered features for which DTs have been used, or unstructured data and images? Perhaps narrowing down a bit the scope of this work would give it more traction. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Seems fine.\n", "review_text": "", "extra_scores": {"ethical_concerns": "Not something obvious.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "E8T072v-BO", "reviewer": "Reviewer_DBdD", "summary": "The paper states a number of results about computing abductive and\ncontrastive explanations for decision trees. The paper includes some\nexperiments on computing explanations about decision trees.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper states a number of results about abductive explanations and\ncontrastive explanations of decision tres. \n\nMain claims:\n\nProposition 1 states a lower bound on the worst-case number of\nsufficient reasons for a prediction.\n\nProposition 2 states a similar results but for the number of minimal \nsufficient reasons.\n\nProposition 3 states that some specific sets of features can be\ncomputed in polynomial time.\n\nProposition 4 states the NP-hardness of computing a minimal sufficient\nreason.\n\nProposition 5 states the correctness of a partial MaxSAT encoding for\ncomputing a minimal sufficient reason.\n\nProposition 6 states that contrastive explanations can be computed in\npolynomial time.\n\nAdditional Comments:\n\nStarting on page 2, the paper delves into 'abductive explanations'.\nHowever, 'abductive explanations' were introduced in [16], but the\npaper never relates with this earlier work. My understanding is that\nthe 'abductive explanations' proposed in [16] are related with\n'sufficient reasons' proposed in later work [7] and with\n'PI-explanations' proposed in earlier work [29]. The main difference \nis that 'PI-explanations' and 'sufficient reasons' are studied in the\ncontext of boolean classifiers and this is not the case with\n'abductive explanations'. The paper refers to 'abductive explanations'\nas something different, without relating with [16], and does not state\nthe relationship. This should be corrected.\n\nA similar comment applies to the relationship between abductive and\ncontrastive explanations and \"Why?\" and \"Why Not?\" explanations. This\nis discussed in detail in [15]. Granted that the paper cites [15], but\nnot when introducing contrastive explanations.\n\nThe definitions of sufficient reason and contrastive explanations\nare much more complicated that other treatments, e.g. [15], or even\nmore recent papers on the same subject.\n\nIt would be important to relate Definition 6 with recent work on\nexplainability, concretely reference [1].\n\nThe paper discusses decision trees with boolean features, but this is\ntoo restrictive. For example, there are situations where features are\nreal-valued. Also, the encodings of decision trees to DNF and CNF\nassume one want to analyze a prediction of 1. This should be\nclarified, as this impacts the later results.\n\nThe decision not to include the proofs in the paper means that\nimportant information is being left out of the paper. The proofs or at\nleast the most relevant ones should be included in the paper.\n\nRegarding the results stated in the paper, a few observations can be\nmade.\n\nProposition 4 has been proved in earlier work:\n\n[R1] P. Barcelo, M. Monet, J. Perez, B. Subercaseaux: Model \nInterpretability through the lens of Computational Complexity. NeurIPS\n2020\n\nwhich the paper does not reference. Concretely, Proposition 4 is one\nof the results included in the proof Proposition 6 of the paper\nabove.\n\nThe issue of the encoding described above becomes problematic when\ndiscussing Propositions 5 and 6. It seems to me the paper is focusing\non a prediction of 1. Is that the case? If so, why? It seems to me\nthere is no need for that, as long as one does not reason in terms of\nthe encoding.\n\nRegarding Proposition 6 in the paper, the proof exploits the CNF\nencoding proposed earlier in the paper. This is unnecessary and makes\nthe result depend on the value of the prediction. A simpler proof of\nthe same result is available in the following work:\n\n[R2] X. Huang, Y. Izza, A. Ignatiev, J. Marques-Silva: On Efficiently \nExplaining Graph-Based Classifiers. CoRR abs/2106.01350 (2021)\n\nWith respect to the experiments, the decision to binarize features\nshould be explained in detail. Binarization requires the explanation\nalgorithms to be aware that binarization took place. This is discussed\nfor example in [R2] above.\n\nAlso, although the paper makes a good point that the number of minimal\nsufficient explanations is in general much smaller than the number of\nsufficient explanations, it offers no evidence that the size of\nminimal sufficient explanations is significantly smaller than the size\nof sufficient explanations.\n\nOverall, I believe some of the stated results provide interesting\ninsights about explanations in decision trees. However, the writing is\nunnecessarily complicated. Also, the should do a much better job of\nrelating with earlier work. In addition, some of the results stated in\nthe paper are already known. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a borderline paper.
While decision tree is a fundamental classifier in machine learning, the paper addresses a more philosophical problem using tools from logic that may be not so relevant for most of the audience.
Another issue is the novelty: The authors confirmed that they missed the fact that Proposition 4 was already proved, and I suspect other results are also known. A much simpler proof for Proposition 6 is available online. While it was published after NeurIPS deadline, it is another indicator that some of the results in the paper are known, or at least can be explained in a more trivial way. 
Decision: Reject