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-approximmted 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,z) 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. 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-a 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= @(1kk), 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": "nt5ixKueQm", "reviewer": "Reviewer_YjV9", "summary": "The submission proposes a new theoretical algorithm for computing certificates that can explain the behavior of a blackbox model f on an input data point x. The core feature of the algorithm is that it provides strong theoretical guarantees: it can be made to work correctly with high probability, produce a highly accurate certificate while running in time polynomial in the \"average\" certificate complexity of f.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The submission as a whole, and the introduction in particular, are very well written (in spite of a few typos here and there). There seems to have been a real effort put into the submission to make at least the high-level ideas accessible to non-experts. The core result is non-trivial and relies on several components: (1) the idea of learning only relevant parts of decision trees (which saves an exponential factor that separates the depth and size of a decision tree), (2) an adaptation of Smyth's result connecting global certificates with global decision trees that can be applied to the subtrees of the decision tree identified in step 1, and (3) an application of known results on noise-stabilizing features.\n\nThe result fits well in the scope of NeurIPS, and its technical contribution is sufficient to warrant publication. I could not verify the correctness of each individual claim made in the submission, but those that I could were correct. I recommend acceptance.\n\nOne specific point I am wondering about is the sentence on rows 81-82, which makes it sound as if Theorem 1 cannot be strengthened by dropping the \"probably\" part (i.e., the 1-delta probability of success) due to existing lower bounds. However, at least to me it is not clear why or whether this should be the case, since Theorem 1 also depends polynomially on the \"average certificate complexity\". If the lower bounds mentioned on rows 76-80 have small \"average certificate complexity\" then please add a remark or explanation about this; otherwise please weaken or reformulate the sentence. (If possible, I would be interested in a response concerning this point.)\n\nMinor comments:\n-row 32: \"certificates the it returns\" -> \"certificates that it returns\"\n-row 91 and elsewhere: \"an certificate\" should be \"a certificate\"\n-row 97: \"in fact\" should be \"in the fact\"\n-row 110: \"we *are* able\"\n\nEdit: I acknowledge having read the rebuttal and thank the authors for the clarifications.", "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": "N/A"}, "extra_text": {}}, {"review_id": "n1m8BjM-NnB", "reviewer": "Reviewer_f3tU", "summary": "The paper discusses the problem of providing explanations when predicting that some instance x belongs to a particular class. In this direction the authors use a decision tree in order to justify the assigned label, but the interesting part is that the decision tree is only implicitly learnt. Basically such an explanation is provided as a list of variables that one should query on the (implicit) decision tree, from the root node down to a leaf node that provides the classification for x. Furthermore, such an explanation can act as a certificate in the sense that indeed the variables mentioned in the explanation, have low error rate with high probability, when the attributes that we find along this path remain the same as in the query instance x, for any point sampled from the underlying distribution.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Provide a full review of the submission, including its originality, quality, clarity, and significance. See https://neurips.cc/Conferences/2021/Reviewer-Guidelines for guidance on questions to address in your review, and /faq for how to incorporate Markdown and LaTeX into your review.\n\nI think that the paper is looking at an interesting problem and with an interesting point of view. In several situations the message is clear, but there are other situations that I find a little bit hard to grasp/accept. For example, when discussing about global and local explanations, in lines 137-138 the authors have the statement \"...the existence of a single global surrogate decision tree, albeit one that may be too large to construct in full, affords several advantages of global methods.\" I think that this is an odd statement. \n\nQ1. Why would we not construct the tree that we want to learn fully? If the tree is too large to be constructed fully, then perhaps the dataset is too large?  \n\nGetting along, I think that near Definition 4 a figure is missing. Or, at least, it would be nice to have a figure there, or in the appendix, and also explain what is discussed. Is alpha (which is used to refer to a node) a set? It looks like that from the comment in lines 192-193. Similarly, in step 3c of the algorithm in Figure 1, alpha is obtained as a set of the queries that we have encountered in the root-to-node path. Then, one question is:\n\nQ2. How do we know which one of the variables we need to query for that particular node? Also, since we are at it, every time we have a node in a root-to-leaf path, we include the query of the node, regardless if the answer is \"yes\" or \"no\". In other words, we keep track of the coordinate that is being queried at the node, but somehow we ignore the answer to the question asked, which subsequently determines which path we will follow further below?\n\nFinally, the authors rely on implicitly learning a decision tree by revisiting a recent algorithm for decision trees that can sustain noise. The interesting thing is that the authors claim exponential efficiency gains, simply because they work in an implicit setting. This is a statement that I find hard to grasp. \n\nQ3. If this is such a beneficial approach (of implicitly learning a tree), then why not always be doing that? In which direction do we obtain exponential efficiency gains? Are there any interesting remarks connecting such gains with results that we can obtain from standard VC theory for decision trees (even if the comment has to be on gains that we obtain under a particular distribution)?\n\nQ4. In Definition 9, why does the tree have to be complete?\n\nRemarks\n\nR1. In Definition 6, I think p should be 1/2, since you are working under the uniform distribution?\n\nR2. Line 338 -> expression?\n\n*After the rebuttal:*\n\nMy opinion for the paper has improved after reading the reviews of others and the response of the author(s). Therefore I am increasing my rating from 5 to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I am satisfied with the discussion of the authors.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "Qd8IzRwys1", "reviewer": "Reviewer_22UY", "summary": "This work proposes (1) a new theoretical model for algorithms to explain the\npredictions of black-box classifiers and (2) an algorithm in this model that\nproduces such explanations with polynomial guarantees on its running time for\nproducing explanations of a given fidelity.\n\nThe model is an analogue of learning under the uniform distribution, making use\nof the ability to query the black-box classifier. Given a point of interest,\nthe algorithm finds a conjunction that is relatively small with high probability\n(over the draw of a point of interest) and such that points matching the\nconjunction receive the same label as the point of interest with high\nprobability over subsequent draws of points. All draws are w.r.t. the uniform\ndistribution on Boolean features. Note that the size of the conjunction \ntherefore also corresponds directly to its coverage, which is 1/2^size.\n\nThe algorithm is an adaptation of recent decision tree learning algorithms,\nthat greedily branch on the attribute that reduces the noise sensitivity the \nmost. The explanation is given by the branch that the point of interest follows\nin this tree. The guarantees follow from a connection between certificate \ncomplexity and decision tree depth.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Of the local explanation methods that have been proposed, I feel that anchors\nwere one of the better motivated options. So, it's interesting to propose a\nmodel that captures something like anchors, in which an algorithm can provide \nguarantees, which is what this work does. The algorithm itself is pretty simple\nand natural. I appreciate this.\n\nThe one obvious weakness of this model is that it is restricted to the uniform \ndistribution on attributes. The paper suggests that it can be generalized, and\nindeed perhaps it can be generalized to product distribution, but this is still\npretty limited. As a point of context, there is work (not referenced here) that\nconsidered an analogous model in a \"distribution-free\" (arbitrary distribution)\nsetting:\n\nJuba and Li, More accurate learning of k-DNF reference classes, AAAI 2020.\n\nThat work showed that in a distribution-free model, algorithms for finding\nsuch conjunctive explanations would give algorithms for learning DNF in the\nusual supervised learning model. Indeed, the reduction is pretty simple -- the\nexplanation-finding algorithm gives weak learners for DNF -- and so it seems\nthat these conjunctive explanations can only be found in models in which \nlearning DNF is tractable. To date, this means membership query algorithms on\nthe uniform distribution and product distributions with some caveats. \nFortunately, this is a setting where the membership queries are not an obstacle\nat all since we assume we can query the classifier on arbitrary points, but of\ncourse the distribution restrictions are a serious obstacle. In any case, these\nnegative results temper our expectations: there was not much scope for the work\nto accomplish much more than it does, given the state of the art.\n\nThe one thing that I think would have made this work significantly stronger\nwould have been experiments. Ribeiro et al. have made the code for their \nexperiments available, and it probably would not have been too difficult to\nimplement this algorithm. Even if the guarantee falls short of capturing the\nreal world, there's still a definite possibility that we would see an empirical\nadvantage to a better-motivated search algorithm than that used by Ribeiro et \nal.\n\nI hereby acknowledge that I read the authors' response and it did not detract\nfrom my original opinion of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above, I am skeptical that the setting can be generalized too much\nfurther than the one considered here. Otherwise, this was discussed well.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper relates the problem of interpreting the output of a black-box machine learning classifier at any point x by releasing an (exponentially small) fragment of a decision tree -- the conjunction labeling a path from root to leaf activated at x. This is natural if one views an "explanation" as a "certificate" for the value of a function at a given point (and ties in neatly to certificate complexity studied in computational complexity theory). In order to accomplish construct such explanations efficiently, the paper introduces and gives an algorithm for the problem of implicitly learning decision trees based on some recent developments in the area. 

Interpreting machine learning classifiers is an important goal and one that could indeed benefit from fresh theoretical approaches. This innovative paper introduces one approach that could fit the bill. We recommend acceptance. 
Decision: Accept (Poster)