Provably efficient, succinct, and precise explanations
Authors: Guy Blanc
Jane Lange
Li-Yang Tan
Venue: NeurIPS 2021 Poster (2021)
Keywords: theory
blackbox explanations
provable guarantees

Abstract: We consider the problem of explaining the predictions of an arbitrary blackbox model $f$: given query access to $f$ and an instance $x$, output a small set of $x$'s features that in conjunction essentially determines $f(x)$. We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. 
  
We obtain our algorithm via a connection to the problem of {\sl implicitly} learning decision trees.  The implicit nature of this learning task allows for efficient algorithms even when the complexity of~$f$ necessitates an intractably large surrogate decision tree.  We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. 
  
Our approach of “explaining by implicit learning” shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both.

Provably efficient, succinct, and precise explanations
Guy Blanc" Stanford University gblanc@stanford. edu
Jane Lange'
Massachusetts Institute of Technology j jlange@mit.
Li- Yang Tan" Stanford University
1 liyangdes.. stanford.
Abstract
We consider the problem of explaining the predictions of an arbitrary blackbox model f: given query access to f and an instance æ, output small set of z's features that in conjunction essentially determines f(x). We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient.
We obtain our algorithm via connection to the problem of implicitly learning de- cision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of f necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory.
Our approach of "explaining by implicit learning" shares elements of two previously disparate methods post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both.
Introduction
Modern machine learning systems have access to unprecedented amounts computational resources and data, enabling them to rapidly train sophisticated models. These models achieve remarkable performance on a wide range tasks, but their success appears to come at price: the complexity of these models, responsible for their expressivity and accuracy, makes their inner workings inscrutable to human beings, rendering them powerful but opaque blackboxes. As these blackboxes become central in mission- mission-critical systems and their predictions increasingly relied upon in high-stakes decisions, there a growing urgency to address their lack of interpretability [DVK17 Lip18).
There has therefore been surge of interest in the problem of explaining the predictions of black- box models: why did model assign an instance the label (x)) While there are numerous possibilities for what qualifies as explanation (see e.g. 1SK BSH 10 SVZ14] [SG116 KL17 LL17 STY17). in this work we consider an explanation to set x's features that conjunction essentially determines f(x) [RSGI8] Following terminology from complexity theory, we call such an explanation a certificate.
We seek succinct and precise certificates. Intuitively, this means that we would like the set of features be as small as possible, and for it to nonetheless be a sufficient explanation for f(x) with high probability; more formally, we have the following definition:
Alphabetical order.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Definition 1 (Succinct and precise certificates), Let f {=1} + {+1} be classifier and a E [+1]² be an instance. We say that a set C' _ [d] features is size-k e-enro certificate for if both of the following hold:
Succinctness:
C| S ki
Precision:
[f(y)= # f(x) yc = sc] S. yー (-(1
Pr
where we write "yc- xc' mean that y and agree on all the features C.
Our main result. We give efficient certificate- seefficatt-findin finding algorithm with provable guarantees the succinctness and precision of the certificates that it returns. Our algorithm is model agnostic, requiring assumptions about the structure of f.
Theorem 1.
Our algorithm s is given input instance I and parameters E, ô E (0, 1). It makes queries to a blackbox model f and returns a certificate of (x) for x with the following guarantees.
With probability 1 1-6 8 over uniform random instance ~ {=1]á, of (x) is an E-error certificate of size (oly(C(f),1/e) 1/8), where C(J) is the "average certificate complexity" of f. The time and query complexity of ad is poly(d,
There is a sizable literature on certificate finding and related problems, studying them from both algorithmic and hardness perspectives. Previous algorithms, which we overview next, were either efficient but lacked provable guarantees on the succinetness and precision of the certificates that they return, or achieved such guarantees but were inefficient. Furthermore, our algorithm circumvents several hardness results for finding succinct and precise certificates, which we also discuss next.
1.1 Prior work on certificate finding
Efficient heuristics. Recent work of Ribeiro, Singh, and Guestrin RSGI88] studies certificates (which they term anchors) from an empirical perspective. They demonstrate, through experiments and user studies, the effectiveness of certificates as explanations across a variety of domains and tasks. Their work highlights the ease of understanding of certificates by human beings and their clarity of scope. The authors also point out several advantages of certificates over LIME explanations [RSG16).
Their work gives an efficient heuristic, based on greedy search, for finding high-precision certificates. However, there are no guarantees on the succinetness of these certificates, and in fact, it is easy to construct classifiers f {=1]d + {+1} with near-minimal certificate complexity, C(f) = for which their heuristic returns certificates of near-maxima size, (2(d). (We elaborate on this in the body of this paper.) This should be contrasted with the guarantees of Thcorem I specifically, the bound on the sizes of the certificates that our algorithm returns.
Prime implicants. A separate line of work has focused on finding prime implicants [gn20 DH20 INM19 INMST9 SCD18). In the terminology of Definitonn 1, implicant is O-error certificate, and an implicant prime its error increases whenever a single feature is removed from it. We note that implicant being prime (i.e. of minimal size) is not equivalent it being the most succinet (i.e. of minimum size): a classifier f {=1]d + {+1} can have an implicant of size and also prime implicants of size d 1.
While O-error certificates are desirable for their perfect precision, it is often impossible to find them efficiently. With assumptions f, even verifying that certificate has 0 error requires querying on the potentially exponentially many possible instances consistent with that certificate. Existing algorithms therefore focus specific model classes. For example, [DH20] gives algorithm for enumerating all prime implicants for a restricted class of circuits. Still, there are numerous hardness results even for model-specific algorithms. For CNF formulas, determining whether certificate is O-error NP-complete. For general size-m circuits, finding the an (-error certificate that has size within m 1- of the smallest possible is NP -complete for any E > 0 [mma01].
Setting aside the computational intractability of finding 0-error certificates, we note that they are in general much less succinet than s-error certificates. is easy to construct examples where size-1 exists, but the only O-error certificate is the trivial one of size d containing
certificate with

---

all features. In general, there is natural tradeoff between the two desiderata of succinctness and precision, and our algorithm allows the user choose their desired tradeoff rather than forcing them to choose perfect precision at the cost of succinetness.
Hardness of finding approximate certificates. There are also intractability results for finding the smallest s-error certificate. [WMHK21] show that for any E, determining whether there exists an e-error certificate of size k for a given circuit and instance is -complete. Furthermore, they show that assuming P + NP, there is no efficient algorithm that can even approximate the size the smallest E-error certificate to within a factor of d² a for any o >> 0.
Theorem circumvents these hardness results because our algorithm is only expected to succeed for most (at least a 1 - 6 fraction) rather than all instances, and only returns small certificate relative to the average certificate complexity of the model, rather than smallest for a particular instance.
1.2 Our approach and techniques
We connect certificate finding to a new algorithmic problem that we introduce, that of implicitly learning decision trees. The key to this connection is a deep result from complexity theory, Smyth's 's theorem (Smy02), which enables us relate the certificate and decision tree complexities of functions. We then show how recently developed decision tree learning algorithms [BLT20b] [BLLT20] can be extended to solve the implicit learning problem. In more detail, there are three modular components to our approach:
Implicitly learning decision trees. Decision trees are the canonical example of an in- terpretable model. Their predictions admit simple explanations: certificate for an instance x is the root-to-leaf path in the tree that x follows. A natural and well- studied approach to explaining blackbox model f is therefore first learn deci- sion tree T' that well-approximates f. and with this surrogate decision tree in hand, can then output a certificate for any instance by returning the corresponding path in [CS95] BS%6 VAB07 ZH16 VLJ+ 17 BKB17 VS20). A limitation of this approach lies in the fact that many models of interest are inherently complex and cannot be well- approximated by a decision tree of tractable size.
To circumvent this, we introduce the problem of implicitly learning decision trees. Roughly speaking, an algorithm for this task allows one to efficiently navigate a surrogate decision tree T for f witthout building T in full. With such an algorithm, the complexity of finding a certificate scales with the depth of T. making it exponentially more efficient than building T full, the complexity of which scales with its overall size.
Relating certificate and decision tree complexities. To translate algorithms for implicitly learning decision trees into algorithms for finding certificates, we apply a theorem of Smyth that relates the certificate complexity of a function to its decision tree complexity. The notion of certificates is central to complexity theory, where it is basis of the complexity class NP. (Smyth's 's result resolved longstanding conjecture of Tardos Tar89) that was motivated by the relationship between P and NP coNP.)
An efficient algorithm with provable guarantees. With the two items above in hand, we are able to leverage recent advances in decision tree learning design certificate-fiddi algorithms. Specifically, we show that the decision tree learning algorithm of Blanc, Gupta, Lange, and Tan [BGLT20] can be extended to the setting of implicit learning. Our resulting certificate-findig algorithm is simple: it constructs a certificate C for an instance æ by recursively adding C the most noise stabilizing feature. Fruitful connections between noise stability and learnability have long been known [OS00] KKMS08]; our work further demonstrates its utility for certificate finding.
Our overall approach falls within the framework of Local Computation Algorithms [RTVXII] Such algorithms solve computational problems for which the output-in our case, the surrogate decision tree- is so large that returning it in its entirety would be intractable. Local computation algorithms are able access and return only select parts of the output-in our case, the path through the tree that corresponds to the specific instance z of cnferest-fffiiientt) and consistently.
3

---

1.3 Discussion of broader context: global and local explanations
Existing approaches to post-hoc explanations mostly fall into two categories. Global explanations seek capture the behavior of the entire model f. often by approximating it with simple and interpretable model such as a decision tree [CS95 BS%6 VAB07 ZH16 VIJ=17 BKB17 VS20 or a of rules [LKCL19] LAB20]. A limitation of such approaches, alluded above and also discussed in numerous prior works (see e.g. (RSGI)) (RSGT8). is that complex models often cannot be well-approximated by simple ones. In other words, using a simple surrogate model necessarily results in low fidelity to the original model.
Our work falls in the second category of local explanations [SK10 BSH 10 SVZ14 RSG16 KL17
LL17 RSG18). These seek to explain f's label for specific instances z. Several of these approaches based on notions of f being "simple around z": for example, LIME explanations [RSGI6] show that ʃ is "approximately linear around x², and certificates, the focus of our work, show that f is "approximately constant in subspace containing x². The corresponding algorithms can therefore he run on models that are too complex to be faithfully represented by a simple global surrogate model.
While work falls in the category of local explanations, we believe that our new approach of "explaining by implicit learning" enjoys advantages of both local and global methods. The local explanations that our algorithm returns are all consistent with single decision tree T that well- approximates f globally. The implicit nature of the learning task allows for T to be intractably large, hence allowing for corresponding algorithms to be run complex models f. circumventing the limitation of global methods discussed above. On the other hand, the existence of a single global surrogate decision tree, albeit one that may be too large to construct in full, affords several ad advantages of global methods. We list a few examples:
Partial information about global structure. Our implicit learning algorithm can efficiently construct the subgraph of T comprising the root-to-leaf paths of a few specific instances; alternatively, it can construct the subtree of T rooted a certain node, or the first few layers of T. All of these could shed light on the global behavior of f.
Feature importance information. Our implicit decision tree T has useful properties beyond being a good approximator of f. As we will show, its structure carries valuable semantic information about f, since the feature queried any internal node is the most "noise stabilizing" feature the subfunction f.- The features in the certificates that our algorithm returns can be ordered accordingly, each being the most noise stabilizing feature of the subfunction determined by x's value on the previous features.
Measures of similarity between instances. Every decision tree T naturally induces "sim- ilarity distance" between instances, given by the depth of their lowest common ancestor within T. Therefore pairs of instances that share a long common path in 7' before diverging (or do not diverge at all) are considered very similar, whereas pairs of instances that diverge early on, say at the root, are considered very dissimilar. (Such tree-based distance functions have been influential in the study of hierarchical clustering; see e.g. (Das16].) .) This distance between two instances can be easily calculated from the certificates that our algorithm returns for them.
1.4 Preliminaries
Feature and distributional assumptions. We focus on binary features and the uniform distribu- tion over instances. Several aspects of our approach extend to more general feature spaces and distributions; we elaborate on this in the conclusion. We use boldface to denote random variables (e.g. æ ~ {d)) and unless otherwise stated, all probabilities and expectations are with respect to the uniform distribution.
Decision tree and certificate complexity. The depth of a decision tree is the length of the longest root-to-leaf path, and its size is the number of leaves.
Definition 2 (Decision tree complexity). The e-error decision tree complexity of f {#1]d + {+1}, denoted D(f, E), is the smallest k for which there exists a depth-k k decision tree T satisfying Pr(T(()) # f()) S E.

---

[d] corresponding to Definition 3 (Certificate complexity). For function f {=1]2 + {+1} and an instance x E {+1]², the g-error certificate complexity f at x, denoted C x; 6,,) is the size of the smallest s-error certificate for a. That is, c(f,2,)) E) is the size of the smallest C _ for which
Pr w-(+1
[f(y) # f(z) yc = xcl S
The e-error certificate complexity of f is the quantity
c(f,))
am/+1p- [C 2c)
E
When E = 0. we simply write C(f,2) and C(f).
2 Implicitly learning decision trees
Our motivation for introducing the problem of implicitly learning decision trees is based simple but key property of decision trees. For any instance I, only a tiny portion of T"s overall structure is "relevant" for its operation on the root-to-leaf path in 7 that follows. The depth of a decision tree is, in general, exponentially smaller than its overall size, so this is indeed a tiny portion.
This natural modularity of decision trees is perhaps the most fundamental reason that decision trees are so interpretable, and we design our overall approach of "explaining by implicitly learning" to take advantage of it. For contrast, consider polynomials instead of decision trees: for polynomial p and an instance æ, all the monomials of are "relevant" for p's operation on æ.
An algorithm for implicitly learning decision trees allows one to efficiently navigate decision tree hypothesis for target function without constructing the tree full.
Definition (Implicitly learning decision trees). An algorithm for implicitly learning decision trees is given query access to target function [=1]d + {=1} and supports the following basic operations on a decision tree hypothesis T for f:
1. ISLEAF(T, a) which, given some node o, returns whether leaf in T.
2. QUERY(T, ai) which, given a non-leaf node o, returns the index the feature that T queries at node
3. LEAFVALUE(T, a) which, given leaf node returns the output value of that leaf.
We assume that is represented restriction of a subset of the features (+13d corresponding the features queried along to the root-to-a path T.
The focus of our paper will be on the connections between implicit learning decision trees and our efficiently finding certificates. As discussed in |Section 1.3) we believe that the former problem is of independent interest and will see applications beyond certificates; we return to this point in the conclusion.
2.1 The connection between implicitly learning DT's and certificate finding
Since an implicit learning algorithm is not required to fully construct the decision tree hypothesis, this definition allows for efficient algorithms even when the complexity of f necessitates a surrogate decision tree of intractably large size. Building on this, we now show that algorithms for implicitly learning decision trees yield certificate-findin algorithms with efficiency that scales with the depth of the decision tree hypothesis 7 rather than its overall size.
Lemma 2.1 (Implicitly learning decision trees = certificate finding). Let f (+1)d + {=1} and E, 8 E (0, 1). Suppose there is algorithm for implicitly learning f where the decision tree hypothesis T satisfies:
1. T is (68/2)-close to f, meaning Pr Pra-((t)a( ((x) # f(x)) S c8/2.
2. T has depth k.
5

---

FINDCERTIFICTTEU.TT.
Given:
Query access {=1}" - {+1}, algorithm for implicitly learning f with T its decision tree hypothesis, instance {=1]d, precision parameter and confidence parameter
Output: An g-error certificate for æ of size most the depth of T, or 1 no certificate found.
1. Initialize Ø.
2. Initialize C +- Ø.
3. While not IsLEAF(T,
(a) Set <- QUE)Y(T,.))
(b) Add to
(c) Set a <
4. Using queries to f. check whether the following holds with confidence at least 1 - 8, indicating if C' is an E-emrr certificate for
(f(0) + f(x) yc xcl Se. (~(1)
Pr
If so, output C. Otherwise, output
Figure How an algorithm for implicitly learning decision trees can be used design certificate-findigg algorithm.
Suppose each of the operations in Definition 4 is supported in time Then there is algorithm, FINDCERTIFICATEE which on x ~ [+1]a runs time +Olog)) /8)/e²) and finds an s-error certificate of size most i with probability least 1 8.
Proof. Consider the algorithm FINDCERTIFICATE given in Figure By design, the certificates that returns E-error and has size most k. the depth of T. Each iteration of the algorithm takes time Ott), and the number of iterations is at most the depth of the root-to-leaf path in T that follows, which is at most the additional time complexity of the random sampling step (llo((18))/
remains to prove that FINDCERTIFICATE SNTERTFFICATE(F T, x 6, outputs with probability at most 8. Let of (x) the certificate checked in Step 4 or FINDCERTIHICATE. We prove that s (æ) is an E-error certificate for x with probability at least 1 - 8. First, we union bound the definition of an E-error certificate follows:
(f()) + f(x) Var(s) = Ea)())) (~(1))
Pr
& Pr [f()) + T(y) Val(m) = Id((m)
(~11)=
+ Pr [T()) # T(x) yd(()) = =I((m)
Pr [T(x) + f(x) (d(() In)(
Our goal is to prove for random (+1}d, the probability that the sum of three terms is more than is at most The second term is simplest: whenever ( = [x)) and æ visit the same leaf in T, so T(y) * T(x) with probability 0. Hence, if the sum of the three terms is more than e, must be the case that either the first term or the third term is more than s/2. The third term is just
Pr[T(w)) # fx:). independent of the choice of y. This is at most ]0 ] since T is 1eo close to f. Finally, since
I 2<1=11
Pr a-i
(f(D)= + T(y) Vo((w) ]
(s(y) T(y)] < foe, w~i
Pr
the first probability is more than E/2 with probability at most by Markov's inequality.

---

3 Certificate complexity, decision tree complexity, and Smyth's theorem
Our notion of certificates as defined in Definitionn local, specific to each instance x, whereas Smyth's 's theorem concerns a global notion of certificates, defined for the entire function f.
Notation. Fix function f {+1}² + { and let a collection of subsets C S [d]. We write *x = 66" if there exists O-error certificate C' & & for æ, and we write 'æ /fr "6" otherwise.
Given two collections E1 and E_1 of subsets, we define corresponding function P%,,8_ {#1}* 1 as follows:
if - E1 and x 1 8-1 if f and E1
Cc (x)
otherwise.
Definition 5 (Global certificate complexity). The global e-error certificate complexity of f {+1]d {=1}, denoted GC(f,e), is the smallest for which there exists two collections E9 and E-11 of size-k subsets satisfying Pr[f(x) + P' [x)] S s.
Recalling Definition 2 it is straightforward to verify that GC(ʃ,e) < e) for all f: [+1]2 [+1) and E >> O. Briefly, give a depth-k g-error decision tree for f. takes 61 to the collection of size-k certificates corresponding to paths leading 1-leafs, and 6-1 to be the collection of size-k certificates corresponding to paths leading to ---eefs. It is easy to see that Pr[f(=) + (6,,)_,)))) E.
Smyth Smy02], resolving longstanding conjecture of Tardos Tar89 proved surprising converse to the elementary inequality above:
Theorem 2. For all f: {+1)2 + [+1] and e > 0, we have e(f < O(GC(f, /30)2///>>))))
We derive as a corollary of Smyth's theorem relationship between certificate and decision tree complexities:
Corollary 3.1 (Bounding decision tree complexity in terms of certificate complexity). For all (=13 + {=1} and > we have D(f, < /EE))
Proof. Letk C(f). By Markov's inequality, we have that P
30k/e") >
(e3 (e$)3)). For every x E f1) (resp. x E f-1(-1)) that contributes to this probability, we include
in 61 (resp. x)1) its certificate of size 30k/e3. It follows that (ran( + &6, (a) <
e3 2/3 and hence = /3/0) < 30k/e3. 3. By Smyth's 's theorem, D(f,e) < O(CC(f, ( and this completes the proof.
4 An efficient algorithm with provable guarantees
The notion noise sensitivity underlies our implicit learning algorithm and its provable guarantees:
Definition (Noise sensitivity). For f {+1]" + {+1} and p (0, 1), the noise sensitivity of f noise rate is the quantity
NS.
E (+1))"
Pr Pr + +((a)))((a)))
where x' m x means that x' is drawn by independently rerandomizing each coordinate of x with probability
Strong connections between noise sensitivity and learnability have long been known KOS04
BOW08 KKMSO0, DHK 10 K4n14]. Most relevant for us is the work of Blanc, Gupta, Lange, and Tan [GLT220, which gives new decision tree learning algorithm with a noise-sensitivitt--uee
splitting criterion, and shows that it achieves strong provable performance guarantees. Our algorithm an implicit version of theirs that enjoys the exponential efficiency gains made possible by the
implicit setting.
7

---

4.1 Greedy noise stabilizing decision frees
Definition (Noise stabilizing score). For f {+1]² - {+1} and p E (0, (0, the noise stabilizing score, or simply the score, of the i-th feature with respect to f and p is the quantity:
Score == NS,(J)
E
(J)
(-(=1)
where fi=b is the restriction of obtained by fixing the i-th feature b.
We associate with every function f {+1)+= {+1] its greedy noise stabilizing decision tree. Definition 8 (Greedy noise stabilizing decision tree). The greedy noise stabilizing decision tree for f: {+1]2² - {+1] at noise rate p. denoted Y y.p is the complete depth-d decision tree where at every internal node the feature i that is queried is the one with the highest noise stabilizing score with respect to the subfunction fa. the restriction of f by the root-to-c path. Every leaf of fwv is labeled according to f value for the unique instance that follows the root-to-l path.
f.p has maximum depth d, the dimension of I's feature space. Since the succinetness of the certificates that of our sertificate-findin algorithm returns scales with the depth of the decision tree hypothesis, we will truncate Y f at much smaller depth < Furthermore, with query access one can only obtain high-accuracy estimates of the noise stabilizing scores of each of its features, and not the exact values of these scores. These algorithmic considerations motivate the following variant Definition 8
Definition (Depth-k 7-approximate greedy noise stabilizing decision tree). Let {=1)< - {+1} and p (0, 1). For k S d and 1) (0, 1), a depth-k 1-approximate greedy noise stabilizing decision tree for f at noise rate p, denoted Tk.27 is complete depth-k decision tree where: f.p'
At every internal node a, the feature i that is queried has noise stabilizing score with respect to f that is within of the highest:
Score: 2 Score;(Ja.1) - for all j + i.
Every leaf & is labeled sign(E(fe))
4.2 Proof of Theorem 1
We now show that, owing to the simple top-down inductive definition of kk. fip there is an efficient
algorithm for implicitly learning any target function f with r f.P as the decision tree hypothesis.
Lemma 4.1 (Implicit learning with mk- as the decision tree hypothesis). Let f [+1)4 - {+1} be a function. For k I d and 17, p E (0, 1), given query access to f, all the operations of Definition can be supported in time ((d² /n²²) with T as the decision tree hypothesis.
Proof. Since T is a complete tree of depth k; we return TRUE for ISLEAF f.p- a.) iff a corre- sponds to a path of length exactly k. Note that query access to f gives us query access to all its subfunctions fa for any Therefore, by standard random sampling arguments, of the noise sensitivity of fa that is accurate to within In w.h.p. using O(1/n²) queries to f. This allows us obtain high-accuracy estimates of the noise stabilizing scores of all the features of fa in time (dd² /m²2), and hence support QUERY (Tkk. f.p a) queries by returning the feature with the highest empirical score. Similarly, high accuracy and returning its sign.
estimate
support LEAFVALUE( f.p.o) a) queries by approximating E[fa] to
We will need a structural theorem of BLT20a| that bounds the distance between f and the greedy noise stabilizing decision tree r
Theorem (Lemma 2.1 of (BLT20a). Let finctton f {=1]² + {+1} be a function. Consider kkn where f.
k= ((((.))))))) n= 0 p= O(eDD((()))
Then Pr[p # f(x)) < O(s).
8

---

We are now ready to put all the pieces together and establish Theorem
Proof of Theorem 1 By our corollary to Smyth's theorem, Corollary 3.1 we have the bound E() I O(C(T)>/(=6))) Combining this with Theorem we get that
1. Pr(m (x) + f(=)) - O(ed), where
2. k S ((( 3
1oly(CU))
These correspond exactly to the two items in the assumption of Lemma 2.1 with "T" being fip and the theorem follows.
Comparison with the certificate-fndingg algorithm of [RSG18]. We conclude this section by comparing our resulting certificate-finel findinnfiinngggi algorithm the heuristic proposed in [RSGT8).
Different greedy choice. Both our algorithm and [ ' heuristic are greedy in nature. Our algorithm builds certificate by iteratively adding to it the most noise stabilizing feature of f, and recursing on the subfunction obtained by restricting f according to x's value for this feature. Our approach therefore be viewed using noise stability precision certificate. contrast, [RSG18] takes a more direct approach and iteratively adds to the certificate the feature that results in the largest gain in estimated precision.
proxy for progress towards high-
Provable performance guarantees.
RSGT8 s heuristic is efficient and returns high-aceuracy cer- tificates, but it is easy to construct examples showing that it fails to return succinct certificates. As simple example, consider f(x) = x; ① xy,, the parity of two unknown features i, E [d]. Every instance has certificate of size two, C {i,j]. but since any certificate comprising single feature {k} has the same precision (regardless of whether E {i,j)), [RSGI8]* heuristic may include in its certificate all d 2 irrelevant features. In contrast, since C(J) 2. Theorem 1 shows that our algorithm returns high-an accuracy certificate of constant-sizz with high probability. ([RSG18) also considers an extension of their algorithm that incorporates beam search; similar hard functions can be constructed for this extension.)
Conclusion
Certificates are simple and intuitive explanations that have been shown be effective across domains and applications [RSGI8). In this work we have designed an efficient cetificate-finding algorithm and proved that it returns succinet and precise certificates. Prior algorithms were either efficient but lacked such performance guarantees, or achieved such guarantees but were inefficient. Our algorithm also circumvents known intractability results for finding succinct and precise certificates.
L Limitations of our work. The main limitation, and perhaps the most immediate avenue for future work, is the feature and distributional assumptions of Theorem We not believe that these are inherently necessary for the provable guarantees that achieve. The main bottleneck relaxing these assumptions is the decision tree learning algorithm of (BGLT20): their analysis relies on the assumptions of binary features and the uniform distribution, and consequently, does extension of their algorithm to the implicit setting.
Other aspects of our approach go through for more general feature spaces and distributions. Smyth's 's theorem holds for arbitrary product spaces, and does our corollary relating decision tree and certificate complexities. The overarching connection between implicitly learning decision trees and certificate finding holds for arbitrary feature spaces and distributions.
Future directions.
There are numerous other avenues for future work; we list few concrete ones:
Improved algorithms and guarantees for specific models. Our algorithm is model agnostic, requiring no assumptions about the model f that seeks to explain, and therefore can be run on any model. It would be interesting to develop improved algorithms, or to improve upon the guarantees of our algorithms, for specific classes of models, such as deep neural networks and random forests, by leveraging knowledge of their structure.

---

Instantiating our approach with other notions of feature importance. Our certificate-fidin algorithm proceeds by iteratively adding the certificate the most noise-stabilizing feature. It would be interesting to analyze natural variants of our algorithm that are based on other notions of feature importance (e.g. Shapley values [L.17.. Can we determine the optimal notion of feature importance that will lead to the most efficient algorithm with the strongest guarantees on the succinctness and precision of the certificates that it returns?
Implicit learning of other interpretable models. As discussed in the introduction, we believe that overall approach of "explaining by implicit learning" enjoys advantages of both local and global approaches to post-hoc explanations. Can our techniques be extended to give implicit learning algorithms for generalized decision trees, ones that branch predicates more expressive than singleton variables? Can we develop implicit learning algorithms for other interpretable models beyond decision trees?
Beyond explainability: implicit decision trees as a robust model. The motivating application of our work is that of explaining blackbox models, and therefore the key feature of decision trees that we have focused on their interpretability. Decision trees have advantages beyond interpretability, and it would be interesting to explore further applications of algorithms for implicitly learning decision trees. For example, can our techniques combined with those of Moshkovitz, Yang, and Chaudhuri [MYC2]] to robustify arbitrary models, making them more resilient to noise and adversarial examples?
More broadly, our work built on new connections between post-hoc explainability and the areas of learning theory, local computation algorithms, and complexity theory. It would be interesting to identify other avenues through which ideas from thcoretical computer science can be utilized to contribute theory of explainable MI.
Acknowledgments and Disclosure of Funding
We are grateful to the anonymous reviewers, whose comments and suggestions have helped improve this paper. Guy and Li-Yang are supported by NSF CAREER Award 1942123. Jane is supported by NSF Award CCF-2006664.
References
[BGLT20] Guy Blanc, Neha Gupta, Jane Lange, and LinY Tan. Universal guarantees for decision tree induction via higher-order splitting criterion. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurlPS), 2020.
[BKB17] Osbert Bastani, Carolyn Kim, and Hamsa Bastani. Interpretability via model extraction. In Proceedings of the 4th Workshop on Fairness, Accountability, and Transparency in Machine Learning (FAT/ML), 2017.
[BLT20a] Guy Blanc, Jane Lange, and Li- Yang Tan. Testing and reconstruction via decision trees. ArXiv preprint, abs/2012.087355, 2020.
[BLT20b] Guy Blanc, Jane Lange, and Li- Ling Tan. Top-down induction of decision trees: rigorous guarantees and inherent limitations. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151, pages 1-44, 2020.
[BOW08] Eric Blais, Ryan O'Donnell, and Karl Wimmer. Polynomial regression under arbitrary product distributions. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 193-204, 2008.
[BS96] Leo Breiman and Nong Shang. Born again trees. Technical report, University of California, Berkeley. 1996.
[BSH+ 10] David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Robert Müller. How to explain individual classification decisions. Journal of Machine Learning Research, 11061):1803-1811 2010.
10

---

[CS95] Mark Craven and Jude Shavlik. Extracting tree- strustruet representations of trained networks. Proceedings of the 8th Conference on Advances in Neural Information Processing Systems (NeurIPS), 8:24-30, 1995.
[Das16] Sanjoy Dasgupta. A cost function for similarity-basee hierarchical clustering. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), page 118-127, 2016.
[DH20] Adnan Darwiche and Auguste Hirth. On the reasons behind decisions. European Conference on Artificial Intelligence (ECAI), 2020.
[DK + 10] Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghavendra, Rocco Servedio, and Li- Tan. Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. In Proceedings of the 42nd Annual Symposium on Theory of Computing (STOC), pages 533 542, 2010.
[DVK17] Finale Doshi-Veld and Been Kim. Towards a rigorous science of interpretable machine learning. ArXiv preprint, 2bs//1002.860082,,200 2017.
[lgn20] Alexey Ignatiev. Towards trustable explainable ai. In Christian Bessiere, editor, Pro- ceedings of the Twenty-Ninth International Joins Conference on Artificial Intelligence, IJCAI-20, pages 5154-5158. International Joint Conferences Artificial Intelligence Organization, 7 2020. Early Career.
[INM19] Alexey Ignatiev, Nina Narodytska, and João Marques-Silva, On validating, repairing and refining heuristic ML explanations. CoRR, 0bss/1907.02/ 000999000......... 2019.
[NMS19] Alexey Ignatiev, Nina Narodytska, and Joao Marques-Sill Silla. Abduction based explana- tions for machine learning models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1511-1519, 2019.
[Kan14] [4] Daniel Kane, The average sensitivity of an intersection of halfspaces. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 437-440, 2014.
[KKMS08] Adam Kalai, Adam Klivans, Yishay Mansour, and Rocco A. Servedio. Agnostically learning halfspaces, SIAM Journal on Computing, 3776) 2008.
[KL17] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1885-1894, 2017.
[KOS04] Adam Klivans, Ryan O'Donnell, and Rocco Servedio. Learning intersections and thresholds of halfspaces. Journal of Computer and System Sciences, 68(4):808-840, 2004.
[LAB20) Himabindu Lakkaraju, Nino Arsov, and Osbert Bastani. Robust and stable black box explanations. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119, pages 5628-5638, 2020.
[Lip18] Zachary C. Lipton. The mythos of model interpretability: In machine learning, the concept of interpretability is both important and slippery. Queue, 16(3):31-57, June 2018.
[LKCL19] Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec. Faithful and customizable explanations of black box models. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society (AIES), page 131-138, 2019.
[LL17] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Proceedings of the 31st Annunal Conference on Advances Neural Information Processing Systems (NeurIPS), pages 4765-4774, 2017.
11

---

[MYC2]] Michal Moshkovitz, Yao- Yuan Yang, and Kamalika Chaudhuri. Connecting inter- pretability and robustness in decision trees through separation. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages 7839-7849, 2021.
[RSG16] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?":
Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pages 1135-1144, 2016.
[RSG18] Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pages 1527-1535, 2018.
[RTVXII] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algo- rithms. In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS), pages 223-238, 2011.
[SCD18] Andy Shih, Arthur Choi, and Adnan Darwiche. A symbolic approach explaining bayesian network classifiers. IJCAI 18, page 5103-5111. AAAI Press, 2018.
[SK10] Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifi- cations using game theory. Journal of Machine Learning Research, 11:1-18, March 2010.
[Smy02] Clifford Smyth. Reimer's Inequality and Tardos' Conjecture. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), page 218-221, 2002.
[STY17] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of the 34th International Conference on Machine Learning (ICML), page 3319-3328 2017.
[SVZ14] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and salieney maps. In Workshop at International Conference on Learning Representations (ICLR), 2014.
[Trr89] Gábor Tardos. Query complexity, or why is it difficult to separate NP n CoNPA from PA by random oracles A? Combinatorica, 9(4):385 392,, 1989.
[Uma01]
Christopher Umans. The minimum equivalent dnf problem and shortest implicants. Journal of Computer and System Sciences, 63(4):597-611, 2001.
[VAB07] Anneleen Van Assche and Hendrik Blockeel. Seeing the forest through the trees: Learning comprehensible model from ensemble. In European Conference on Machine Learning (ECML), pages 418 0889 2007.
[VLJ+17] Gilles Vandewiele, Kiani Lannoye, Olivier Janssens, Femke Ongenae, Filip De Turck, and Sofie Van Hoecke. A genetic algorithm for interpretable model extraction from decision tree ensembles. In Trends and Applications in Knowledge Discovery and Data Mining, pages 104-115, 2017.
[VS20] Thibaut Vidal and Maximilian Schiffer. Born-again tree ensembles. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 9743-9753, 2020.
[WMHK21] Stephan Waeldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok. The com- putational complexity of understanding binary classifier decisions. Artif. Int. Res., 70:351-387, 2021.
[7H16] Yichen Zhou and Giles Hooker. Interpreting models via single tree approximation, 2016.
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] See feefSectionn 3
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) See Section 1.4
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect 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 (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to 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": "MRQ6wHbCSaW", "reviewer": "Reviewer_NH6L", "summary": "The authors consider the paper of providing concise and approximately precise explanation for a black box binary function f on a specific instance x, where the explanation is a certificate for f(x), namely a small subsets of coordinates of x which determines f(x). The idea is the exploit decision trees T  that well approximate f and the possibility to implici construct only path of T used on instance x, using the tests on this path as a certificate. \n", "questions": "", "limitations": "", "rating": 8, "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": "The authors provides strong guarantees on the succintness and precision of an explanation that can be used to describe the behavior of a black box function f. \nThey exploit recent results on decision tree learning with universal guarantee (BLT,ICML20, BGLT,NeurIPS20] and Smyths's result on existence of decision tree approximating certificate complexity. The possibility of  implicitly building the decision tree with universal guarantee leads to the efficient construction of the local explanation. A strong point of the result is the fact that the underlying decision tree guaranteeing the approximate certificate complexity only depends on f and not on x. \nAlthough the main technical contribution leading to main result are from previous papers, the overall contribution is strong enough to justify acceptance. \n\nStrengths: the model inherits from previous works on which it leverage the leack of assumption on f. \nWeakness: binary features and uniform distribution assumptions. The guarantee is with respect to the average certificate size. What could be said with respect to guarantee relative to the smallest certificate for the input instance x? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no potential negative social impacts to be considered. \nLimitations (including weakness reported above) are discussed in the final section", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "HWxH4b-Ikv3", "reviewer": "Reviewer_ikim", "summary": "Given a definition of a succinct and precise certificate (or\nexplanation), the paper proposes an efficient algorithm for the\ncomputation of such a certificate.", "questions": "", "limitations": "", "rating": 8, "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": "The paper proposes an algorithm for computing succinct and precise\ncertificates (or explanations), which strong theoretical guarantees.\nThe proposed contribution is significant.\n\nConcretely, the paper proposes to exploit recently proposed algorithms\nfor implicitly learning a decision tree for the generation of succinct\nand precise certificates. The algorithm proposed in the paper is shown\nin Figure 1, and builds on earlier work on implicit tree learning.\n\n\nAdditional comments:\n\nThe paper should include experiments supporting the proposed\nalgorithm.\n\nDefinition 1 seems equivalent to Definition 2.1 in:\nS. Waldchen, J. MacDonald, S. Hauch, G. Kutyniok: The Computational\nComplexity of Understanding Binary Classifier Decisions. J. Artif.\nIntell. Res. 70: 351-387 (2021)\nThe paper cites an older version of this paper. It would be important\nto cite the published paper, and of course clarifying whether the\ndefinitions are the same.\n\nThe paper relates with [RSG18] (end of section 4.1). It shows that for\na concrete example, the proposed algorithm computes a better\ncertificate than [RSG18]. However, given other examples of the\nlimitations of [RSG18], could these be problematic for the work\nproposed in this paper? One example is the assessment in:\n\nA. Ignatiev: Towards Trustable Explainable AI. IJCAI 2020: 5154-5158\n\nbut also, in the papers cited by this paper.\n\nMoreover, there is recent work related with explanations for decision\ntrees. The point is that decision trees may contain paths that are\narbitrarily larger than a succinct explanation. Could this in practice\nimpact the results proposed in the paper.\n\nA few references on explaining decision trees:\n\nY. Izza, A. Ignatiev, J. Marques-Silva: On Explaining Decision\nTrees. CoRR abs/2010.11034 (2020)\n\nP. Barcelo, M. Monet, J. Perez, B. Subercaseaux: Model\nInterpretability through the lens of Computational Complexity. NeurIPS\n2020\n\nG. Audemard, S. Bellart, L. Bounia, F. Koriche, J.-M. Lagniez,\nP. Marquis: On the Computational Intelligibility of Boolean\nClassifiers. CoRR abs/2104.06172 (2021)\n\nX. Huang, Y. Izza, A. Ignatiev, J. Marques-Silva: On Efficiently\nExplaining Graph-Based Classifiers. CoRR abs/2106.01350 (2021)\n\nThe paper analyzes the use of prime implicants as explanations and\nargues that smallest prime implicants can be arbitrarily smaller than\nplain prime implicants. This is correct. However, existing\nexperimental data suggests that the difference is not significant in\npractice. For example, this is the case for neural networks:\n\nA. Ignatiev, N. Narodytska, J. Marques-Silva: Abduction-Based\nExplanations for Machine Learning Models. AAAI 2019: 1511-1519", "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": {}}, {"review_id": "85F-FCU8PpW", "reviewer": "Reviewer_GLcW", "summary": "The paper considers a new algorithm for creating  explanations of predictions of arbitrary black box models. \nIn this paper, an explanation is a subset of the input features that explain the prediction in the sense that changing the input features,\nnot in the explanation subset at random, has only a small probability of changing the model prediction.\n\nThe paper considers only binary features and binary classification and assumes uniform distribution over the input. \nThe main result is an algorithm that with probability 1-delta over the random choice of input provides an explanation (subset of features) that is polynomial in the average size of\nthe smallest explanation when averaged over all inputs (and 1/delta, 1/epsilon where epsilon is error allowed).\n\nThe main algorithm assumes an existing decision tree algorithms, and simply builds the path from the root to the leaf where the input data point would end up,\nthe explanation being the features queried in the nodes on the way. This is possible due to the assumption of uniform distribution over the binary features.\n\nThe main component of the theorem is based on a result from complexity theory, that bound certificate complexity (an explanation is a certificate)\nof a function, polynomially in terms of the decision tree complexity (depth) of the function, which leads to the polynomial in the bound given.\n\nThe second important part is the decision tree construction algorithm required for the explanation algorithm. This methods is based on recent results on decision trees and that\nworks for only uniform distribution over binary features and binary classes, providing the limiting features of the result shown.\nThe algorithm is sped up with random sampling which is straightforward by the same assumptions.\n\n", "questions": "", "limitations": "", "rating": 6, "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": "Overall the method and framework proposed is well formulated and explained. \nIn terms of the results there are several limitations that need to be overcome for this to be actually useful for explaining predictions as the paper also mentions.\n\nWhile creating explanations as considered in this paper for several formulations is computationally hard this is circumvented here which is of course positive.\nAnother plus is that the paper is well written and the problem well formulated and defined and and easy to follow. \n\nHowever, the proposed method works only for binary features with uniform distribution over the features and is based on a randomly sampled input to explain.\nThis makes the main theorem somewhat vague. \nThe polynomial increase in explanation size may seem theoretically succinct but it is not clear that it is since the polynomial's powers seem non-trivial.\nHence the succinctness of these explanations remain to be seen.\nThe limits of the results shown in this paper means that they seem of theoretical interest only for now. \n\n**Update**. \nI have read all the the reviews and author comments. \nPersonally, while i think experiments could be interesting i do not mind them not being in the paper. Experiments like this are not easy and including one or two plots may not be enough anyways. Hence i agree with the authors that experiments is a logical next step from here and i do not think the paper should be rejected due to lack of experiments.\n\nI think the approach makes sense and may work well in practice perhaps with some fine-tuning as argued in the rebuttal by the authors. Furthermore the results shown opens the door for several follow up directions the two main directions being actually doing experiments with this approach and improving the conditions for which it may work (as the authors state most of the approach actually generalize to a more general setting).\n\nHence as it stands now after the rebuttal i will increase my score to a 6.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "386uow_BhzT", "reviewer": "Reviewer_XbsB", "summary": "The authors propose a local explanation method based on certificates, i.e. sets of important features that closely (in conjunction) determine the prediction of a given black-box model. The obtained certificates provide guarantees regarding two sensible properties: succinctness and precision (i.e., intuitively, they remain small/sparse and, with high probability, also locally faithful w.r.t. the black-box model). The authors propose an implicitly learned Decision Tree to obtain certificates. This implicit approach reduces the computation time compared to related methods. The authors further demonstrate the relationship between the complexities of such implicit Decision Trees and the corresponding certificates.", "questions": "", "limitations": "", "rating": 5, "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": "The proposed method is relevant to researchers and practitioners concerned with model-agnostic (local) explainability. Indeed, the discussed certificates are an interesting alternative to popular local attribution methods like SHAP or LIME.\nThe paper is written well, with only a few minor errors (word repetitions etc.), which could be removed in the final version.\nThe formalization and theoretical motivation appear to be sound. The noise-sensitivity based splitting criterion is adapted from previous work. While the proposed implicit decision tree learning approach is novel, it raises the question why an explanatory decision tree needs to be learnt implicitly. Efficiency cannot be the only criterion (because similar explanatory mechanisms can also be learnt in an offline setting; their application to locally explain a given instance would still be very efficient).\nThe proposed method and formalizations assume a Bernoulli target and binary-valued features. Although the authors address this limitation and argue that the approach may be rephrased more generally, this remains to be shown.\nThe paper is missing an experimental evaluation of the proposed method on real-world data. In particular, the paper would benefit from a comparison between certificates and local attribution methods (e.g. SHAP, LIME), or a comparison with the ‘anchors’ and ‘prime implicants’ methods mentioned in the related works section. I would also like to see how the precision error $\\epsilon$ and the succinctness parameter $k$ behave in practice (can I actually set a small $\\epsilon$ and still obtain small $k$, i.e. sparse certificates, or vice versa?).\nFinally, note that the proposed implicit algorithm will always return certificates of size $k$ or no certificate at all. This is because the implicit tree learning algorithm stops only after having reached a path length of size $k$. Only then do the authors check whether the obtained certificate adheres to the $\\epsilon$-precision property (see FindCertificate() algorithm, Figure 1). That is, the proposed algorithm potentially misses smaller certificates along the path to the leaf node, which might already satisfy the precision property. The authors should argue why this is a desired behavior or adjust the algorithm accordingly (e.g. by making algorithm step 4 part of the training loop, i.e. changing it to algorithm step 3(d), in Figure 1).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A limitation of the proposed work is the restriction regarding the possible data distribution, which is addressed by the authors. Another, and in my opinion more severe limitation, is the lack of empirical evaluations. It is unclear how the proposed method behaves in practice and compared to other feature-based explanation techniques.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no apparent ethical concerns regarding this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Let me start by saying that throughout the discussion the reviewers all agreed that the paper discusses an interesting problem and makes a step towards creating succinct explanations. However, despite the fact that this work seems promising, it was judged as not quite ready for publication at this time.

We believe that if you revise the paper according to the comments provided by the reviewers then this work will undoubtedly evolve into a strong publication in the future.

Thanks for submitting your work to NeurIPS!
Decision: Accept (Poster)