On Computing Probabilistic Explanations for Decision Trees
Authors: Marcelo Arenas
Pablo Barcelo
Miguel Romero Orth
Bernardo Subercaseaux
Venue: NeurIPS 2022 Accept (2022)
Keywords: explainability
formal XAI
decision trees
computational complexity
sufficient reasons

Abstract:   Formal XAI (explainable AI) is a growing area that focuses on computing explanations with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the most studied cases is that of explaining the choices taken by decision trees, as they are traditionally deemed as one of the most interpretable classes of models. Recent work has focused on studying the computation of sufficient reasons, a kind of explanation in which given a decision tree $T$ and an instance $x$, one explains the decision $T(x)$ by providing a subset $y$ of the features of $x$ such that for any other instance $z$ compatible with $y$, it holds that  $T(z) = T(x)$, intuitively meaning that the features in $y$ are already enough to fully justify the classification of $x$ by $T$. 
It has been argued, however, that sufficient reasons constitute a restrictive notion of explanation. For such a reason, the community has started to study their probabilistic counterpart, in which one requires that the probability of $T(z) = T(x)$ must be at least some value $\delta \in (0, 1]$, where $z$ is a random instance that is compatible with $y$. Our paper settles the computational complexity of $\delta$-sufficient-reasons over decision trees, showing that both (1) finding $\delta$-sufficient-reasons  that are minimal in size, and (2) finding $\delta$-sufficient-reasons that are minimal inclusion-wise, do not admit polynomial-time algorithms (unless P = NP).
   This is in stark contrast with the deterministic case ($\delta = 1$) where inclusion-wise minimal sufficient-reasons are easy to compute. By doing this, we answer two open problems originally raised by Izza et al., and extend the hardness of explanations for Boolean circuits presented by W{\"a}ldchen et al. to the more restricted case of decision trees. On the positive side, we identify structural restrictions of decision trees that make the problem tractable, and show how SAT solvers might be able to tackle these problems in practical settings.

On Computing Probabilistic Explanations for Decision Trees
Marcelo Arenas 12,44 Pablo Barceló2.4.5, Miguel Romero 355, Bernardo Subercaseaux
Authors are listed in alphabetical order.
Correspondence at bsuberca@cs. cmu.
Department Computer Science, PUC Chile Institute for Mathematical and Computational Engineering, PUC Chile Faculty of Engineering and Science, UAI Chile
Millenium Institute for Foundational Research on Data, Chile CENIA Chile Carnegie Mellon University, Pittsburgh, USA
Abstract
Formal XAI (explainable AI) is growing area that focuses on computing explana- tions with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the most studied cases is that of explaining the choices taken by decision trees, as they are traditionally deemed as one of the most interpretable classes of models. Recent work has focused on studying the computation of suffi- cient reasons, kind of explanation in which given decision tree T and an instance one explains the decision T(x) by providing a subset y of the features of x such that for any other instance z compatible with y. it holds that T(z) T(x),, intuitively meaning that the features in y are already enough to fully justify the has been argued, however, that sufficient reasons
classification of ae by constitute restrictive notion of explanation. For such reason, the community has started to study their probabilistic counterpart, in which one requires that the probability of (=)) T(x) must be at least some value (0, 1]. where is random instance that compatible with y. Our paper settles the computational decision trees, showing that both (1) finding S-sufficient-reasonn that are minimal in size, and (2) finding d-sufficient-reasonss that are minimal Inclusion-wise do not admit polynomial-ting algorithms (un- less PTIME = NP). This is in stark contrast with the deterministic case (6 = 1) where inclusionwwis minimal sufficient-reasen this, we answer two open problems originally raised by Izza et al., and extend the hardness of explanations for Boolean circuits presented by Wäldchen al. to the more restricted case of decision trees. On the positive side, we identify structural restrictions of decision trees that make the problem tractable, and show how SAT solvers might be able to tackle these problems in practical settings.
complexity of d-sufficient-reaseee
easy compute. By doing
Introduction
Context. The trust that Al models generate in people has been repetitively linked to our ability of explaining the decision of said models (Arrieta al., 2020), thus suggesting the area of explainable Al (XAI) as fundamental for the deployment of trustworthy models. A sub-area of explainability that has received considerable attention over the last years, showing quick progress in theoretical and practical terms, is that of local explanations. i.e., explanations for the outcome of particular input to an ML model after the model has been trained. Several queries and scores have been proposed to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

specify explanations of this kind. These include, e.g., queries based on prime implicants (Shih et al., 2018) or anchors (Ribeiro al., 2018), which are parts of an instance that are sufficient to explain its classification, as well as scores that intend to quantify the impact of a single feature in the output of such a classification (Lunddberg and Lee, 2017; Yan and Procaccia, 2021).
A remarkable achievement of this area of research has been the development of formal notions of explainability. The benefits brought about by this principled approach have been highlighted, in a very thorough and convincing way, in a recent survey by Marques-Silyy and Ignatiev (2022). A prime example of this kind of approach is given by sufficient reasons, which are also known as prime implicant explanations (Shih et al., 2018) or abductive explanations (Ignatiev et al., 2021).
Given ML model MM of dimension and Boolean input instance for x: under M is a subset y of the features of æt, such that any instance z compatible with y receives the same classification result as x M. In more intuitive words, is a sufficient reason for under M if the features in y suffices to explain the output of M on œ. In the formal explainability approach, one then aims to find sufficient reasons y that satisfy one of the following optimality criteria: (a) they are minimum, i.e. there are no sufficient reasons with fewer features than y, or (b) they are minimal, i.e., there are no sufficient reasons that are strictly contained in y.
{0, 1)".. sufficient reason
The XAI community has studied for which Boolean ML models the problem of com- puting (minimum or minimal) sufficient reasons is computationally tractable and for which it is computationally hard (sec, c.g., (Barceló et al., 2020; Marques-Sill Silluuuc--ilvaaaaa et al., 2020, 2021)). It has been argued, however, that for practical applications sufficient reasons might be too rigid, as they are specified under worst-case conditions. That is, y is a sufficient reason for x under M if every "completion" of y is classified by .M in the same way as œ. As several authors have noted already, there is a natural way in which this notion can be relaxed in order to become more suitable for real-world explainability tasks: Instead of asking for each completion of y yield the same result as x on M, we could allow for a small fragment of the completions of y to be classified differently than x (Izza et al., 2021; Wäldchen et al., 2021; Wang et al., 2021). More precisely, we would like to ensure that a random completion of y is classified as x with probability at least E (0, 1], a threshold that the recipient of the explanation controls. We call y a ô-sufficient reason for under M.
Problem.
The study of the cost of computing minimum 8-sufficient reasons for expressive Boolean ML models based propositional formulas was started by Wäldchen et al. (2021). They show, in particular, that the decision problem of checking if x admits a 6-sufficient reason of a certain size & under a model M, where .M is specified as a CNF formula, is NPPP -comllete. This result shows that the problem is very difficult for complex models, at least in theoretical terms. Nonetheless, it leaves the door open for obtaining tractability results over simpler Boolean models, starting from those which are often deemed to be "easy interpret", e.g., decision frees (Gilpin al., 2018; Izza et al., 2020a; Lipton, 2018). In particular, the study of the cost of computing both minimum and minimal o-sufficient reasons for decision trees was initiated by Izza et al. (2021, 2022), but nothing beyond the fact that the problem lies in NP has been obtained. Work by Blanc et al. (2021) has shown that it possible to obtain efficient algorithms that succeed with certain probability, and that instead of finding a smallest (either cardinality or inclusion- d-sufficient reason, find d-sufficient reasons that are small compared the average size of ō-sufficient reasons for the considered model.
Our results. In this paper we provide an in-depth study of the complexity of the problem of minimum and minimal d-sufficient reasons for decision trees.
1. We start by pinpointing the exact computational complexity of these problems by showing that, under the assumption that PTIME & NP, none of them can be solved in polynomial time. We start with minimum d-sufficient reasons and show that the problem is hard even if 6 is an arbitrary fixed constant in (0, 1]. Our proof takes as basis the fact that, assuming PTIME of NP, the problem of computing minimum sufficient reasons for decision trees is not tractable (Barceló et al., 2020). The reduction, however, is non-trivia and requires several involved constructions and a careful analysis. The proof for minimal 8-sufficient reasons is even more difficult, and the result more surprising, as in this case we cannot start from a similar problem over decision trees: computing minimal sufficient reasons over decision trees (or, equivalently, minimal 8-sufficient reasons for 5 1) admits a simple polynomial time algorithm. Our result then implies that such a good behavior is lost when the input parameter ó is allowed to be smaller than 1..

---

2. To deal with the high computational complexity of the problems, we look for structural restrictions of that, at the same time, represent meaningful practical instances and ensure that these problems can be solved in polynomial time. The first restriction, called bounded split number, assumes there is a constant 2 1 such that, for each node u of a decision tree T of dimension the number of features that are mentioned in both Tu. the subtree of T rooted at u, and T T.. the subtree of T obtained by removing Tu. is at most c. We show that the problems of computing minimum and minimal 8-sufficient reasons over decision trees with bounded split number can be solved in polynomial time. The second restriction is monotonicity. Intuitively, a Boolean ML model M is monotone, if the class of instances that are classified positively by .M is closed under the operation of replacing Os with 1s. For example, if M is of dimension 3 and it classifies the input (1. (1,0,0) 0) as positive, then so it does for all the instances in {11,0, O, 1). (1, 1,0, (1, 1,,,1)} 1) We show that computing minimal 6-sufficient reasons for monotone decision trees is tractable problem. (This good behavior extends to any class of monotone ML models for which counting the number of positive instances is tractable; e.g., monotone free binary decision diagrams (Wegener, 2004)).
3. In spite of the intractability results we obtain in the paper, we show experimentally that our problems can be solved over practical instances by using SAT solvers. This requires finding efficient encodings of such problems conjunctive normal form (CNF) formulas, which we then check for satisfiability. This is particularly non-trivial for probabilistic sufficient reasons, as it requires dealing with the arithmetical nature of the probabilities involved through a Boolean encoding.
Organization of the paper. We introduce the main terminology used the paper in Section 2, and we define the problems of computing minimum and minimal d-sufficient reasons in Section 3. The intractability of the these problems is proved in Section 4, while some tractable restrictions of them are provided in Section 5. Our Boolean encodings can be found in Section 6. Finally, we discuss some future work in Section 7.
2 BBckkrrund
An instance of dimension n, with n 2 1, is tuple E {0. 1 We use notation x[i] to refer to the i-th component of this tuple, or equivalently, its i-th feature. Moreover, we consider an abstract notion of a model of dimension n. and we define it as a Boolean function M : {0, 1}" + f0.1). That is, M assigns a Boolean value to each instance of dimension nt, so that we focus on binary classifiers with Boolean input features. Restricting inputs and outputs to be Boolean makes our setting cleaner while still covering several relevant practical scenarios.
A partial instance of dimension is a tuple y E 10,1, Intuitively. if ylil = L. then the value of the i-th feature is undefined. Notice that an instance a particular case of a partial instance where all features are assigned value either 0 or 1. Given two partial instances æ. y of dimension n,, we say that y is subsumed by æ denoted by y S x., if for every i E (1..... n) such that y * 1. it holds that y/il = ==. That is, y is subsumed by æ if it is possible to obtain æ from y by replacing some undefined values. Moreover, we say that y is properly subsumed by x. denoted by y S. x, if y S x and y j æ. Notice that a partial instance y can be thought of as compact representation of the set of instances z such that y is subsumed by z, where such instances z are called the completions of y and are grouped in the set COMP(y).
binary decision diagram (BDD) of dimension n is a rooted directed acyclic graph M with labels on edges and nodes such that: (i) each leaf (a node with no outgoing edges) is labeled with true or false; (ii) each internal node (a node that is not a leaf) labeled with a feature i E {1, n): and (iii) each internal node has two outgoing edges, one labeled 1 and the other one labeled O. Every instance x E {0, 1)" defines a unique path u U1 ... 24 from the root U1 to a leaf un of M such that: if the label of u; is {1,.... n), where i E (1..... h- 1). then the edge from u; to 2441 is labeled with æ [j]. Moreover, the instance x is positive, denoted by MMxx)
1, if the label of us is true; otherwise the instance æ is negative, which is denoted by M(x) = O. A BDD M is free if for every path from the root to a leaf, no two nodes on that path have the same label. A decision tree
is simply free BDD whose underlying directed acyclic graph is rooted tree.
3

---

3 Probabilistic Sufficient Reasons
Sufficient reasons are partial instances obtained by removing from an instance z components that do not affect the final classification. Formally, fix dimension Given a decision tree T. instance 2, and partial instance with y S Σ, we call y a sufficient reason for æ under T if Txx) = T(*) for every z E CoMP(Y). In other words, the features of y that take value either decision taken by T on æ, as T(x) would not change if the remaining features (i.e., those that are undefined in yy were change in 2: thus implying that the classification T(x) is consequence of the features defined in y. We say that a sufficient reason y for æ under I is minimal, if it is minimal under the order induced by S. that is, if there no sufficient reason y' for under '' such that y' S y. Also, we define a minimum sufficient reason for æ under I as sufficient reason for æ under that maximizes the value y == Ki f1.....n) n} y = 1}|-
explain the
turns out that minimal sufficient reasons can be computed efficiently for decision trees with a very simple algorithm, assuming sub-routine check whether given partial instance is sufficient reason (not necessarily minimal) of another given instance. As shown in Algorithm 1, the idea of the algorithm is as follows: start with candidate answer y which is initially equal to æ; the instance to explain, and maintain the invariant that y is a sufficient reason for æ; while trying to remove defined components from y until longer possible. It not hard to see that one can check whether partial instance is a sufficient reason for an instance æ in linear time over decision trees (Audemard et al., 2021). This algorithm is well known (see e.g., (Huang et al., 2021)) I)), and relies on the following simple observation, tracing back to Goldsmith et al. (2005).
Observation 1. For any class of models C, if a partial instance y of dimension n is sufficient reason for an instance x under a model M but not minimal sufficient reason, then there is partial instance y which is equal to except that g = 1. yli + for some i E {1....,7) n) which also a sufficient reason for x under M.
Algorithm 1: Minimal Sufficient Reason
Input: Decision tree T and instance æ, both of dimension n Output: A minimal sufficient reason y for under T.
<-
2 while true do reduced +- false
for E [l.....,1] do g+- y y <
if CheckSuffiiien/eesonn[] ÿ. æ)) then
+ y
reduced <- true break
10
11
if (rreduced) or lyyl then
12
return y
The following theorem shows stark contrast between the complexity of computing minimal and minimum sufficient reasons over decision trees.
Theorem (Barceló et al. (2020)). Assuming PTIME + NP, there is no polynomial time algorithm that, given decision tree T and an instance of the same dimension, computes a minimum sufficient reason for x under T.
Arguably, the notion of sufficient reason is natural notion of explanation for the result of classifier. However, such concept imposes a severe restriction by asking all completions of partial instance to be classified in the same way. To overcome this limitation, a probabilistic generalization reasons was proposed by Wäldchen et al. (2021) and Izza et al. (2021). More precisely, this notion allows to settle a confidence E (0, on the fraction of completions partial instance that yield the same classification.
sufficient

---

p(0) p((1,2) J
2
p(11)) = 3
p((1,3)) =
false
({2)) - p((2,3)
true
p(3)) = p((1,2,3) =
false
true
Figure 1: The decision tree 7 and the values p(X) from Example 1.
Definition (Probabilistic sufficient reasons). Given a value d E (0, 11, a d-sufficient reason (6-SR for short) for instance under decision tree T is partial instance y such that and
Pr, (T)(T(>) = ( | x COMP(y)] = 1x COMP(N) ( T(z) T(>) N
2
Minimal and minimum 5-sufficient reasons defined analogously in the of minimal and minimum sufficient reasons.
Example 1. Consider the decision tree over features (1, 2. shown in Figure and the input
instance a: 1. Notice that T(x) = 1. For each X [ {1, 3), we show the probability p(X) := Pr, [z) ( = E COMP y )}. where yxx is the partial instance that is obtained from æ by fixing yx [ = 1 for each i X. We observe, for instance, that itself is neither minimum a minimal 1-SR for æ under T. as V(1.3) = (1, L, 1) is also a 1-SR. In turn, 2/1.33 is both minimal and minimum 1-SR for under T. The partial instance (1,3)) 3. is not, however, minimal minimum 3/4-SR for æ under T, as D(1} (1, 1, is also a 3/4-SR.
Example 2. Consider the decision tree T over features {1, 2, shown in Figure 2 and the input instance x = 1,) Notice that T(x) = 1. Exactly as in Example 1, we display as well the probabilities p(X) for each X _ {1, 3J. Interestingly, this example illustrates that Observation I does not hold when < 1. Indeed, consider that ((22333) is a 5/8-SR which is not minimal, as ye is also a 5/8-SR,
we remove any single feature from 1112333+ we obtain partial instance which
a S/s-SR.
As illustrated on Example 2, it is not true in general that if y' c then [r=[T(=) = T(x)) z COMP(Y') )] S Pry (T=[T(z) T(x:) e COMP(y)),
which means that standard algorithms for finding minimal sets holding monotone predicates (see e.g.. (Marques-Silva et al., 2013)) cannot used to compute minimal 6-SRs.
The problems of computing minimum and minimal 8-SR on decision trees were defined and left open by (Izza et al., 2021, 2022). These problems are formally defined follows.
PROBLEM:
INPUT
decision tree of dimension n, an instance of dimen- sion n and & E (0, 1] minimum 8-SR for æ under T
OUTPUT:
PROBLEM:
Compute-Mininn Minnimal-SiiR A decision T' of dimension n, an instance of dimen- sion n and 8 E (0, 1] A minimal 8-SR for under T
INPUT
OUTPUT:
4 The Complexity of Probabilistic Sufficient Reasons on Decision Trees
In what follows, we show that neither Compute-Mininum-SR nor Compute-Minimal-St can be solved in polynomial time (unless PTIME NP). We first consider the problem
5

---

T
2
true
3
3
2
true
false
true
false
false
true
p(0) =
p((1,2)) = 1
p((1)) p((1,3)) 1
p([2)) p((2,3)) =
p((3)) p((1,2,3))
Figure 2: The decision tree and the values p(X) from Example 2.
Compute-Minimum: and in fact prove a stronger result by considering the family of prob- lems 6- Coompute-Minimmmt where 5 (0, 1] is assumed to be fixed. More precisely, obtain cannot solved efficiently. Moreover,
as a corollary of Theorem that I-Compute-Minne Minitee--iiiimm----e non-trivial modification of the proof of this theorem shows that this negative result continues to hold for every fixed E (0,
Theorem Fix (0, 1]. Then assuming that PTIME + NP, there is no polynomial -tmme algorithm for 3-Compute- Siaittte-Miiiumm-SS-
Let us now look at the problem Compute-Minimal Miniuule-MMiial--SRR. When = 1, this problem can solved in polynomial time as stated in Theorem 1. However, is conjectured by Izza al. (2021) that assuming PTIME * NP, this positive behavior does not extend to the general problem Compute-Minimar in which 8 is input confidence parameter. Our main result confirms that this conjecture is correct.
Theorem 3. Assuming that PTIME * Compute-Minimal-SR.
NP, there is polynomial-time algorithm for
Proof sketch. We first show that the following decision problem, called Check-Sub-SS is NP-hard. This problem takes as input a tuple (T, (T.x), for T decision tree of dimension n, and x E {0, 1, 1... 1m
partial instance, and the goal is to decide whether there is partial instance
with Pr (T(2)
1 E COMP y 2 Pr [T(>) = z E COMP(z)) (=)] We then show that if Compute-Minimal- SR admits a polynomial time algorithm, then Check-Sur Sub-SR is in PTIME, which contradicts the assumption that PTIME * NP. The latter reduction requires an involved construction exploiting certain properties of the hard instances for Check-Sur Sub-SR.
NP-hard, we use a polynomial time reduction from decision problem over formulas in CNF, called Linimal-Expected Clauses, and which we also show to be NP-hard. Both the NP-hardness of Minimal- Minimal-EEppctee Expected-Clalle Expected- Clacuees to Check- Sub-ShuuSSSR -R may be of independent interest.
To show that Check- Sub-Suuburr
and the reduction from Minimal-
We now define the problem
Let yp be CNF formula over variables X fIi...., Fn J. Partial assignments of the variables in X, as well as the notions of subsumption and completions over them, are defined exactly same way as for partial instances over features. For partial assignment j over X, we denote by E(p, (1) the expected number of clauses of satisfied by a random completion of μ. We then consider the following problem for fixed k 2 (recall that KFCNF formula is CNF formula where each clause has at most & literals);
LitimallEEppeted-CCle

---

PROBLEM: 4--iinimal-Exxeeeee--aaauu
I
a, for k-CNF formula and a partial assignment
OUTPUT:
Yes, if there is partial assignment μ Ş such that ( ()) (l),0)
and No otherwise
We show that d--inimmll-Exeecee--aaaaee
is NP-hard even for k 2, via reduction from the well-known clique problem. Finally, the reduction from Moiiniml-Expecteer Clauses to Check-Sute Sacck-Sub-RR builds an instance (T, æ²) from (p, o)) in a way that there is direct correspondence between partial assignments a and partial instances y S æ. satisfying that
Expected-Clauses
Pr (T()) = 2 E COMP(y)) (s p)
m
where m is the number of clauses of yp This implies that (42, op Snrected-Clauser and only if (T, x:) is Yes-instance for Check-Sub-SR.
) is Yes-instance for k-Minimal-
Tractable Cases
We now study restrictions on decision that lead to polynomial time algorithms for Compute-Mininum-SR or Compute-Minimal-SR, hence avoiding the general intractability re- sults shown in the previous section. We identify two such restrictions: bounded split number and monotonicity.
5.1 Bounded split number
Let be decision tree of dimension n. For set U of nodes T, we denote by F(U) the set of features from [1....,7) n labeling the nodes in U. For each node of T. we denote by N the set of nodes appearing in T., that the subtree of T' rooted set of nodes of T minus the set of nodes No. We define the split number of the decision tree T to be
On the other hand, we denote by NI the
max node T [((N)) n ((NN)
Intuitively, the split number of a decision tree T is a measure of the interaction (number of common features) between the subtrees of the form Tu and their exterior. A small split number allows us to essentially treat each subtree Tu independently (in particular, the left and right subtrees below any node), which in turn leads to efficient algorithms for the problems Compute-Minimum- Minimun-SSSS and Compute-Minine Manuue--iiimma-SR.
Theorem 4. Let c 2 1 be a fixed integer. Both be solved in polynomial time for decision trees with split number most
and Compute-MinimallSS
Proof Sketch. It suffices provide a polynomial time algorithm for Compute- Sorpoutt-Miiiuuu-s-e (The same algorithm works for turn, using standard arguments, it enough to provide a polynomial time algorithm for the following decision problem Check-Minimum-
Mon-ian--iminnnne as minimum 8-SR is in particular minimal.) In
Given tuple (T. æ. 5, k), where T is a decision tree of is an integer, decide whether COMP(y)) 2 8.
dimension n, x E {0, 1, 1 a partial instance, E (0, 1], and
there is partial instance C such that ly| < k and [T=)) =
an instance (T, k). where T has split number most c, we apply dynamic programming over T bottom-up manner. Let C (1...,, n.) be the set of features defined æ, that is, features i with æ[i] * Those are the features we could eventually remove when looking for y. For each node in T. we solve a polynomial number of subproblems over the subtree T,, We define
In order solve Bineck-Mnnimmm-SS
Int(u) = F(N+) (FF(N)) nz
New(u) = (F(NH) \ Int(u)) n z.
In other words, Int(u) are the features appearing both inside and outside T., while New(u) are the features only inside Tu, that is, the new features introduced below u. Both sets are restricted Z as features not in Z play role in the process.

---

Each particular subproblem is indexed by possible size E (o...., .) and possible set J S Int(u) and the goal is to compute the quantity:
max Pr (T)(2) = COMP(y)).
Pu.s
VE Cu.a.
where Cu,s.J is the space of partial instances y S with | and such that y x for i E and y = 1 for E Int(u) \ J. In other words, the set / fixes the behavior on Int(u) (keep features in J, remove features in Int(u) J) and hence the maximization occurs over choices on the set New(u) (which features are kept and which features are removed). The key idea is that pu,s,J can be computed inductively using the information already computed for the children u1 and u2 of Intuitively, this holds since the common features between Tw, and Twz are at most c, which is a fixed constant, and hence can efficiently synchronize the information stored for in and u2. Finally, to solve the instance (T, æ; ō, k) we simply check whether Pr, 2 8, for the root r of T.
5.2 Monotonicity
Monotonic classifiers have been studied in the context of XAI as they often present tractable cases for different explanations, as shown by Marques-Sile Silva et al. (2021). The computation of minimal sufficient reasons for monotone models was known to be in PTIME since the work of Goldsmith et al. (2005). We show that this is also the case for computing minimal 6-SRs under a mild assumption on the class of models.
Let us define the ordering for instances in {0, 13"h as follows:
iff a11| S =|1), for all E n..
We can now define monotonicity as follows. A model M of dimension is said to be monotone if for every pair of instances x, x 13". holds that 3 = M(x) & M(z).
We now prove that the problem of computing minimal probabilistic sufficient reasons can be solved in polynomial time for any class C of monotone Boolean models for which the problem of counting positive completions can be solved efficiently. Formally, the latter problem is defined as follows: given model M C of dimension and partial instance y 1, 13". compute { COMP(y) MMxx)= = 1H. We call this problem
Theorem 5. Let e be a class of monotone Boolean models such that the problem be solved in polynomial time. Then Compute-Minimal-SR
C- C-Count-Posiine Cirtiiettoolltionnss can be solved in polynomial time over
Proof sketch. Consider partial instance y of dimension and {1, (1.-.., We write y {i) for the partial instance y that is exactly equal to y save for the fact that y 1. We make use of the following lemma, which is probabilistic counterpart Observation
n). Suppose (8] 1.
Lemma 1. Let E be a class of monotone models, M E e a model of dimension n, and x E {0. 1)" an instance. Consider any 8 E (0, 1). Then if y S is a 8-SR for under M which is not minimal, then there is partial instance y (i), for some E {1,..., n.,, that is also a 5-SR for x under M.
With this lemma we can prove Theorem 5. In fact, it can be shown then that slight variant of Algorithm computes in polynomial time a minimal 8-SR for a under M.
L
As corollary, the computation of minimal probabilistic sufficient reasons can be carried out in polynomial time not only over monotone decision trees, but also over monotone free BDDs.
Corollary 1. The problem of computing minimal 8-SRs can be solved in polynomial time over the class of monotone free BDDs.
6 SAT to the Rescue!
Despite the theoretical intractability results presented earlier on, many NP-complete problems can be solved over practical instances with the aid of SAT solvers. By definition, any NP-complete problem can be encoded as CNF satisfiability (SAT) problem, which is then solved by highly optimized program, SAT solver. In particular, if satisfying assignment is found for the CNF instance, one
8

---

can translate such an assignment back to solution for the original problem. In fact, this paradigm has been successfully used the literature for other explainability problems (Ignatiev al., 2021, 2022; Izza et al., 2020b). The effectiveness of this approach is highly dependent the particular encoding being used (Biere et al., 2009), where the aspect that arguably impacts performance the most is the size of the encoding, measured as the number of clauses of the resulting CNF formula.
In this section we present an encoding that uses some standard automated reasoning tools (e.g.. sequential encondings (Sinz, 2005)) combined with ad-hoc bit-blasting (Biere et al., 2009), where the arithmetic operations required for probabilistic reasoning are implemented as Boolean circuits and then encoded as CNF by Tseitin transformations. The appendix describes experimentation both over synthetic datasets and standard datasets (MNIST) and reports empirical results. A recent report by Izza et al. (2022) also uses automated reasoning for this problem, although through an SMT solver. problem.
Let us consider the following decision version of the
PROBLEM:
Decide-Minimum-S9F
INPUT
decision tree of dimension n, an instance as of dimen- sion an integer k S and 8 E (0.
OUTPUT:
Yes there is 6-SR y for x under with ly) S k, and No otherwise.
This problem is NP-complete. Membership already proven by Izza al. (2021). Hardness follows directly from Theorem 2, as if one were able to solve Decide-Minimum-- in polynomial time, then a simple binary search over would allow solving Compute-Minimund in polynomial time.
6.1 Deterministic Encoding
Let us first propose an encoding for the particular case of 8 1. First, create Boolean variables fa for E {l...., n). with representing that ylil # I. where y is the desired 6-SR. Then, for every node u of the tree T, create a variable ru representing that node u is reachable by a completion of y. meaning that there exists completion of y that goes through node when evaluated over T. We then want to enforce that:
1. TRoor = L, where ROOT is the root of T. This means that the root is always reachable.
2. The desired 8-SR satisfies n - 1y/1 S k, meaning that Σ St S k.
3. If T(x) = 1, and F' is the set of false leaves of T, then Te = 0 for every E F. This means that if we want to explain positive instance, the completions of the explanation must all be positive (recall we assume 5 = 1), and thus no false leaf should be reachable. Conversely, If (xx) 0, and G is the set of true leaves of T, then r 0 for every & E G.
4. The semantics of reachability is consistent: if a node is reachable, and its labeled with feature then if f. meaning that feature is undefined in y, both children of should be reachable too. In case f. = 1, only the child along the edge corresponding to x(i] should be reachable.
Let us analyze the size of this encoding. Condition requires a single clause to be enforced. Condition 2 can be enforced with O(nk) variables and clauses using the linear encoding of Sinz (2005). Condition 3 requires at most one clause per Icaf of T'' and thus at most O(IT)) clauses. Condition 4 can be implemented with a constant number of clauses per node. We thus incur in total of Onk + (T') variables and clauses, which is pretty much optimal considering 2(n + (?"]) is a lower bound on the representation of the input.
Note as well that from a satisfying assignment we can trivially recover the desired explanation as
[i]
if 1
y [i]
otherwise.
An efficient encoding supporting values of 5 different than 1 is significantly more challenging and involved, and thus we only provide an outline here. An exhaustive description, together with the implementation, is provided in the supplementary material.

---

6.2 Probabilistic Encoding
In order encode that (T) T(x) | = E COMP(Y)) 2 6, we will directly encode that H= E COMP(H) T(*) T())} 2 [22 where we assume for simplicity that the ceiling can be take safely, in order to have a value we can represent by an integer. This assumption is not erucial. As before, we will have fi variables representing whether y|i] * 1 or not, and enforce that Σ Si S k. Now define variables Cj for j E {0. [O.....n] nn), such that Cj is true exactly when 2x=1 Ji = j. This can again be done efficiently via a linear encoding. Let I, for i E (O....,?) , a series of variables that represent the bits of an integer L. The integer will correspond to the value of [221v111. Note that as y can only take n + different values, there are only 1 different values that t can take. Moreover, the value of the Cj variables completely determines the value of t, and thus
manually encode how the ej variables determine the bits f,- We now assume that we have access to through its bits 4, Our goal now is to build a binary representation of
1 COMP(y)
T(z) = H[
so that then implement the condition
t with Boolean eircuit their bits. In order to represent a, we will decompose the number of instances = according to the leaves of T as follows. If L is the set of leaves of ' whose label matches T(x), then
H= COMP(y) ((2) [(*))
E| E=E CCMP(y) | T(2) 0)}
EEL
where notation T()) ~ l means that the evaluation of z under T ends in the leaf É. For given leaf f, we can compute its weight wy == 1[= E COMP(Y) T(z) ~ {)}l as described next. Let Fe be the set of labels appearing in the unique path from the root of T down to &. Now let uy be the number of undefined features of y along said unique path, and thus 2s can be defined as follows: ue = |Fe \ {i ft = 1H. The sets F/ depend only on T and thus can be precomputed. Therefore can use a linear encoding again to define the values Ug. It is simple to observe now that W/ = 2", which means that by representing the values ug we can trivially represent the values wy in binary (they will simply consist of a 1 in their (ue + 1)-th position right-to-left), and then implement a Boolean addition circuit compute a E, We- This concludes the outline of the encoding. Its number of variables clauses can be shown be most On [T] + nk).
7 Conclusions and Future Work
The results proven in this paper suggest that minimal (or minimum) explanations might be hard to obtain in practice even for decision trees, especially in problems where the feature space has large dimension. A way circumvent the limitations proven in our work is to relax the guarantee of minimality, or introduce some probability of error, as done in the work of Blanc et al. (2021). A promising direction of future research is to better understand the kind of guarantees and settings in which is still possible to obtain tractability.
Our work leaves open some interesting technical questions: (1) What is the parameterized complexity of computing minimum d-SRs over decision trees, assuming that the parameter is the size of the explanation one is looking for? It is not hard see that W(2) hardness follows from our proofs (i.e., they are parameterized reductions all the way to Set Cover), but membership in any class is fully open. (2) Does Theorem 2 continue to hold for monotone decision trees? That is, is it the case that computing minimum d-SRs over monotone decision trees is hard for every fixed ō E (0, 1]2 (3) Is it the case that the hardness of computation for minimal sufficient reasons holds for fixed If so, does it hold for every fixed such a ō, or only for some? (4) Is it possible to extend the positive behavior of decision trees with bounded split number to free BDDs?
(0, 1j?
Acknowledgments
Barceló is funded by Fondecyt grant 1200967. Arenas and Barceló have been funded by ANID Millennium Science Initiative Program Code ICN17002. Barceló has also been funded by National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Romero is funded by Fondecyt grant 1 11209956, the Data Observatory Foundation, and the National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Subercaseaux is supported by NSF awards CCF- 2015445. CC51955785, and CCF2006953.
10

---

References
A. B. Arricta, N. Blaz-Rodriguez, J. D. Ser, A. Bennetot, S. Tabik, A. Barbado, S. Garcia, S. Gil- Lopez, D. Molina, R. Benjamins, R. Chatila, and F. Herrera. Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible Al. Information Fusion, 58:82-115, June 2020, doi: 10. i0.1016/.inffuus22199.9 1016/j httffus.iifff.mmm/m/ 2019.022222 12.012.
URL attpps//doo org/10.
G. Audemard, S. Bellart, L. Bounia, Koriche, Lagniez, and P. Marquis. On the computational intelligibility of boolean classifiers. In M. Bienvenu, G. Lakemeyer, and E. Erdem, editors, Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning. KR 2021, Online event, November 3-12, 2021, pages 74-86, 2021. doi: 10.24963/kr. 2021/8. URL https: //tp://d.ooooot// org/ 10. 24963/2K...... 2021/8.
Barceló, M. Monet, J. Pérez, and B. Subercaseaux. Model interpretability through the lens of computational complexity. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15487-15498. Curran Associates, Inc., 2020. URL httpthtsssp/occeeiiiiieeooooeeee www.ediinnnnnnnss...mee.. wwwpurrissccpppae///.eeeee pccppaprr/222//ilee biadda14888
.df.
A. Biere, A. Biere, M. Heule, H. van Maaren, and T. Walsh. Handbook of Satisfiability; Volume 185 Frontiers in Artificial Intelligence and Applications. IOS Press, NLD, 2009. ISBN 1586039296.
A. Biere, K. Fazekas, M. Fleury, and M. Heisinger. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT Competition 2020. In T. Balyo, N. Froleyks, M. Heule, M. Iser, M. Järvisalo, and M. Suda, editors. Proc. of SAT Competition 2020 Solver and Benchmark Descriptions, volume B-2020-1 of Department of Computer Science Report Series B, pages 51-53. University of Helsinki, 2020.
G. Blanc, J. Lange, and L.-Y. Tan. Provably efficient, succinet, and precise explanations. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Advances in Neural Information Processing Systems, 2021. URL /ttps://openree/////
A. Choi, W. Shi, A. Shih, and A. Darwiche. Compiling neural networks into tractable boolean circuits. intelligence, 2017.
L. Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 2012.
L. H. Gilpin, D. Bau, B. Z. Yuan, A. Bajwa, M. A. Specter, and L. Kagal. Explaining explanations: An overview of interpretability of machine learning. In Bonchi, F. Provost, Eliassi-Rad, W. Wang, C. Cattuto, and R. Ghani, editors, DSAA, pages 80-89, 2018.
J. Goldsmith, M. Hagen, and M. Mundhenk. Complexity of DNF and isomorphism of monotone formulas. In Mathematical Foundations of Computer Science 2005, pages 410-421. Spriger Berlin Heidelberg, 2005. doi: (000//1159944 36. URL httph:tt////ttt http:://doooooooooo 1000//1..000/114434455 36.
X. Huang, Y. Izza, A. Ignatiev, and J. Marques-Silva, On efficiently explaining graph-based classifiers. In M. Bienvenu, G. Lakemeyer, and E. Erdem, editors, Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021, pages 356-367, 2021. doi: 10.24963/ks.2221//44 URL attpps://ol. org/10. 24963 kr. 2021/34.
A. Ignatiev N. Narodytska, N. Asher, and Marques-Silva. From contrastive to abductive ex- planations and back again. In AIxIA 2020 Advances in Artificial Intelligence, pages 335- 355. Springer International Publishing, 2021. doi: https://doi. org//o//// 10.
URL
A. Ignatiev, Y. Izza, P. J. Stuckey, and J. Marques-Silva. Using maxsat for efficient explanations of tree ensembles. In AAAI, 2022.
Y. Izza, A. Ignatiev, and J. Marques-Silve On explaining decision trees. CoRR, abs/2010.11034 2020a.
11

---

Y. Izza, A. Ignatiev, and J. Marques-Silva. On explaining decision trees, 2020b. URL https: //arxiv. org/ htg/abb/2000... 11034.
Y. Izza, A. Ignatiev, N. Narodytska, M. C. Cooper, and J. Marques-Silva. Efficient explanations with relevant sets. ArXiv, abs/2106.00546, 2021.
Y. Izza, A. Ignatiev, N. Narodytska, M. C. Cooper, and J. Marques-Silva. Provably precise, suc- cinct and efficient explanations for decision trees, 2022. URL https://aa// httpaaawww......a.a.r/rrraaaaaaa 02200 09569.
Z. C. Lipton. The mythos of model interpretabilityy Quene, 16(3):11-57, 2018.
S. M. Lundberg and S.-I. Lee. unified approach to interpreting model predictions. In NeurIPS, pages 4765-4774, 2017.
J. Marques-Silva and A. Ignatiev. Delivering trustworthy ai through formal xai. In AAAI, 2022.
J. Marques-Silva, M. Janota, and A. Belov. Minimal sets over monotone predicates in boolean formulae. In N. Sharygina and H. Veith, editors, Computer Aided Verification, pages 592-607, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. ISBN
J. Marques-Silva. T. Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska. Explaining naive bayes and other linear classifiers with polynomial time and delay. In NeurIPS, 2020.
J. Marques-Silva,
Silva, T. Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska. Explanations for monotonic classifiers. In ICML, pages 7469-7479, 2021.
Marques-Silva, Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska. Explanations for monotonic classifiers. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7479. PMLR, 18 28-24 Jul 2021. URL https http:///ccceee....///// mlr press/v139/ marques- parques-silva22e silvalia. html.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28300 2011.
M. T. Ribeiro, Singh, and C. Guestrin. Anchors: High-precision model-agnostic explanations. In AAAL, pages 1527-1535, 2018.
A. Shih, A. Choi, and A. Darwiche. A symbolic approach to explaining bayesian network classifiers. arXiv preprint arXiv: 1805.000000000 0036644 2018
C. Sinz. Towards an optimal CNF encoding of boolean cardinality constraints. In Principles and Practice of Constraint Programming CP 2005, pages 827-831. Springer Berlin Heidelberg, 2005. doi: 10.1007/1 1564751 _33. URL https://dol. org/ 10. 1007 0110//166475175
S. Wäldchen, J. MacDonald, S. Hauch, and G. Kutyniok. The computational complexity of under- standing binary classifier decisions. Artif. Intell, Res., 70:351-387, 2021.
E. Wang, P. Khosravi, and G. den Broeck. Probabilistic sufficient explanations. In Z. Zhou, editor, IJCAI, pages 3082-3088, 2021.
I. Wegener. Branching Programs and Binary Decision Diagrams. Society for Industrial and Applied Mathematics, Jan. 2000. doi: 00.11337119788888877999999 URL httpt:///ddo org/10. 1137/1. 9780898719789.
I. Wegener. Bdds design, analysis, complexity, and applications. Discret. Appl. Math., 138(1-2): 229-251, 2004.
T. Yan and A. D. Procaccia. If you like shapley then you'll 'll love the core. In AAAI, pages 5751-5759, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The paper provides several
negative results concerning the studied problems
(c) Did you discuss any potential negative societal impacts of your work? [No] We do foresee negative societal consequences of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Absolutely.
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes] All of them.
(b) Did you include complete proofs of all theoretical results? [Yes] But due the space constraints, the complete proofs are included in the appendix.
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 URL)? [Yes]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(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 assets either in the supplemental material URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you're rou're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "vCE9U9rdVp4", "reviewer": "Reviewer_BptY", "summary": "After rebuttal: The authors clarified my misunderstanding and I acknowledge that the problem seems to be practically harder than I thought. Some reservations about the relevance of decision trees for NeurIPS, the choice of the dataset and the speed of the SAT encodings remain, but I will change my overall evaluation to weak accept and lower my confidence.\n\n---\n\nThe paper studies computing delta-sufficient reasons for decision trees. It shows that finding subset and cardinality minimal delta-sufficient reasons is not possible in polynomial time assuming P!=NP. A SAT-encoding is presented and the appendix shows some runtime results for trees with up to 200 leaves. ", "questions": "Please correct me if I am wrong about the difficulty of the problem. Are the decision trees available for inspection in the code repository? I would be interested in looking at the decision trees of depth 20 in order to understand why the problem could be more complicated. It would also be interesting to know what the theoretical upper bound for the number of leaves compared to their actual number is. What is actually the background of the generated trees? Have they been generated randomly or do they achieve better performance with increasing number of leaves? Why has MNIST actually been chosen for the experiments? It does not really seem a natural choice for decision trees. Can we actually learn anything from the decision tree/ the explanations for MNIST? Why not consider a tabular dataset? ", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While this is a solid technical paper, I do not think that it is a good contribution for NeurIPS. It seems to me that the contribution is mainly interesting from a theoretical perspective. Please correct me if am wrong, but it seems to me that the complexity arises only from considering all possible extensions of the minimal sufficient reasons. However, considering all these candidates seems unnecessary in a decision tree because decision trees are typically not exponentially large. Indeed, all trees in the experiments have at most 200 leaves. This means that there are at most 200 decision paths that have to be analyzed. The SAT encodings need more than 4 seconds even if the trees have only 20 leaves, which seems rather slow. The runtime remains the same as the number of leaves increases, but this is probably because the encoding (exponentially) depends on the number of features (that presumably did not change in the experiments) and not on the number of decision paths (which is exponentially bounded by the number of features, but typically significantly smaller than the worst-case bound). It seems that the problem could be solved more efficiently by considering the decision nodes and their possible extensions in the tree. From an explanation perspective, it would also be nice to see some examples of explanations generated with this approach. Overall, I think that the current state of the paper could be a nice contribution for a smaller conference on theoretical aspects. However, for a major conference like NeurIPS, the significance is not sufficiently clear.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MkzqlbydPdn", "reviewer": "Reviewer_megZ", "summary": "A sufficient reason (SR) for a decision taken by a classifier on input x\nis a subset e of the assignment x (when viewed as a set of literals)\nwhich is sufficient to account for the decision. For obvious reasons \nthe user may be interested in minimum-cardinality or (more modestly)\nsubset-minimal SR's. SR's are a basic notion in the formal approach to \nexplaining decisions of classifiers, however it is a very strict notion,\nleading to SR's which contain too many features for the user to grasp.\nThus, from a practical point of view, a more useful notion is a delta-SR \ne which allows a certain degree of error, in that only a fraction delta<1 of \nthe completions of the partial assignment e need to be classified the same as x.\n\nThis paper settles the computational complexity of certain problems concerned with\nfinding delta-SR's over decision trees, showing notably that even finding a subset-minimal \ndelta-SR is intractable (assuming P not equal to NP). \n\nThey show that this intractability can be avoided if extra restrictions are applied\n(such as a structural property of the decision tree or monotonicity of the classifier).\nThey also give a SAT encoding for finding smallest delta-SR's.", "questions": "(1) Can the notion of split number be generalised to DAGs (such as d-DNNFs)? \n\n(2) Is bounded split number not the same as bounded treewidth? It is well known that\nbounded treewidth allows polynomial-time counting for many combinatorial problems\n(see, for example, Michael Jakl, Reinhard Pichler, Stefan Rümmele & Stefan Woltran,\nFast Counting with Bounded Treewidth, LPAR 2008, pp 436–450 or articles cited therein)\n\n(3) Have you tested the loss in accuracy if you restrict yourself to learning\nDT's with bounded split number? ", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main complexity results are negative but nonetheless very interesting since they\nshow intractability even for decision trees, which is one of the simplest possible\nML models. It is not too difficult to show that the simple greedy-deletion algorithm\nwhich can be used to find SR's of decision trees in polynomial time no longer\nworks for delta-SR's due to the non-hereditary nature of delta-SR's (e.g. we can\nhave A \\subset B \\subset C with A,C both delta-SR's but not B). But, NP-hardness\nis not at all obvious. The constructions required to prove this in the supplementary \nmaterial are far from straightforward.\n\nThere are also some positive results, concerning DT's with bounded split number or\nmonotone free BDD's (Corollary 1). The authors also give a SAT encoding which provides a\nway of calculating delta-SR's, but as is shown in the supplementary material this is\nonly practical for decision trees of very modest size (20 leaves, 36 features).\nThis simply confirms, in practice, the theoretical intractability proved in the paper.\n\nMinor points:\n- perhaps reword 1st sentence of abstract since formal XAI is not just\nconcerned with explaining decisions of ML models.\n- line 286: a citation is required so the reader can easily find out what free BDDs are \nand find a proof that counting is polytime.\n- line 308: in the output, don't you mean n-|..| \\leq k instead of |..| \\leq k?\n- line 325: \"its labeled\" should be \"it is labeled\"\n- line 342: \"can be take safely\" should be \"can be taken safely\"\n- line 346: missing \"be\" before \"a series\"\n- line 365: missing \"and\" before \"clauses\"?\n- I am confused by Question 2 in Future Work which seems to have been answered by Corollary 1.\n- line 376: delete \"a\" in \"every fixed such a\"\n- use {} in latex to impose capitals in bibliography entries (e.g. {XAI})\n- the arXiv paper by Izza et al occurs twice in the bibliography\n- line 636: Do you mean \\neg y_i instead of y_i ? Below you seem to be assuming that\nthese variables are negated.\n- line 682: Let us say\n- line 687: do you mean 4e instead of M?\n- line 719: delete \"that\"\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JwP59BxcXnE", "reviewer": "Reviewer_A6C9", "summary": "In the setting of explainable artificial intelligence, this paper investigates probabilistic explanations for decision tree predictions. Namely, given a decision tree $T$, a data instance $e$ and a confidence parameter $\\delta \\in (0,1]$, a $\\delta$-sufficient reason for $e$ given $T$ is a monomial that covers $e$ and for which the proportion of satisfying assignments $e'$ such that $T(e') = T(e)$ is at least $\\delta$. A minimal $\\delta$-sufficient reason is a  $\\delta$-sufficient reason that is subset minimal, and a minimum $\\delta$-sufficient reason is $\\delta$-sufficient reason of minimum size. Based on these definitions, the authors prove that the problems of finding minimal/minimum $\\delta$-sufficient reasons are NP-hard. They also consider tractable cases by considering restrictions on the structure (bounded split number) and the semantics (monotonicity) of decision trees. Finally, they propose a propositional SAT encoding for computing minimum $\\delta$-sufficient reasons.\n", "questions": "Yes, I have a few questions about tractable cases:\n* A natural class of shallow (and interpretable) models is the family of decision trees of bounded depth, say $d$. Are the problems of finding minimal/minimum $\\delta$-sufficient reasons still intractable for fixed $d$? Are they fixed-parameter tractable with respect to $d$?\n* Theorem 5 is interesting but leaves open a natural case: the well-studied class of monotone DNF. As we know, counting the number of satisfying assignments of a DNF admits an FPRAS. So, do we still have an FPRAS result for computing minimal/minimum $\\delta$-sufficient reasons when the predictor is representable by a monotone DNF formula?  ", "limitations": "Overall, I think that the key results of this paper are of theoretical nature, and hence, this paper should stick to the theoretical side. Indeed, as mentioned above, the experimental study is still at an early stage. So, focusing on theoretical results (Section 4 and 5) should leave some room for presenting the proof of the main result (Theorem 2) in more detail, and for examining more tractable cases - or showing that natural subclasses remain intractable.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I would say that the paper includes some good ideas, but it requires more polishing. For the moment, the paper is not self-contained and should be re-organized.\n\nLet us start with the positive aspects.  Based on the recent work by Izza et al. (2022), the problem of finding a $\\delta$-sufficient reason of size at most $k$ belongs to NP, and the optimization version of this problem belongs to $\\Theta_2^P$. So, a key question is to determine whether such a problem is NP-hard, or not. This is arguably the main result of this paper (Section 4): the authors have proven that the problems of computing minimal/minimum $\\delta$-sufficient reasons are NP-hard. The work spent on finding tractable subclasses (Section 5) is interesting but would deserve further investigation (see comments in the section \"Limitations\").\n\nUnfortunately, the paper is not self-contained. In particular, the main result of this study (Theorem 3) includes a sketch of proof that could be improved. To this point, I was merely confused by the sentence “Finally, the reduction from k-Minimal-Expected-Clauses to Check-Sub-SR builds an instance $(T, e)$ from $(\\phi, \\sigma)$ in a way that there is a direct correspondence between partial assignments $\\mu \\subseteq \\sigma$ and partial instances $e’ \\subseteq e$, satisfying that [...]”. As we know, unless P = \\#P, we cannot find a polynomial translation from a $k$-CNF formula $\\phi$ to an equivalent decision tree $T$ (even for $k = 2$). In fact, the construction of $T$ is more sophisticated (notably, it is not equivalent to $\\phi$), and the overall proof is clarified in the Supplementary Material. \n\nMy last major comment is about the SAT encoding of the (decision version of the) minimum $\\delta$-sufficient reason problem (Section 6.2). While this encoding looks elegant, the experiments reported in the Supplementary Material are at a preliminary stage. Read again my comment below, but if the authors really want to provide a propositional SAT encoding, it should be tested on various datasets, and it should be compared with the SMT encoding proposed by Izza et al.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept