Provably efficient, succinct, and precise explanations
Year: 2021

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 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.

heading: 1 Introduction
text: Modern machine learning systems have access to unprecedented amounts of computational resources and data, enabling them to rapidly train sophisticated models. These models achieve remarkable performance on a wide range of tasks, but their success appears to come at a 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-critical systems and their predictions increasingly relied upon in high-stakes decisions, there is a growing urgency to address their lack of interpretability [DVK17, Lip18].
There has therefore been a surge of interest in the problem of explaining the predictions of blackbox models: why did a model f assign an instance x the label f(x)? While there are numerous possibilities for what qualifies as an explanation (see e.g. [SK10, BSH+10, SVZ14, RSG16, KL17, LL17, STY17]), in this work we consider an explanation to be a set of x’s features that in conjunction essentially determines f(x) [RSG18]. 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 to 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 (NeurIPS 2021).
Definition 1 (Succinct and precise certificates). Let f : {±1}d → {±1} be a classifier and x ∈ {±1}d be an instance. We say that a set C ⊆ [d] of features is a size-k ε-error certificate for x if both of the following hold:
◦ Succinctness: |C| ≤ k,
◦ Precision: Pr y∼{±1}d
[ f(y) 6= f(x) | yC = xC ] ≤ ε,
where we write ‘yC = xC’ to mean that y and x agree on all the features in C.
Our main result. We give an efficient certificate-finding algorithm with provable guarantees on the succinctness and precision of the certificates that it returns. Our algorithm is model agnostic, requiring no assumptions about the structure of f .
Theorem 1. Our algorithm A is given as input an instance x and parameters ε, δ ∈ (0, 1). It makes queries to a blackbox model f and returns a certificate A (x) for x with the following guarantees.
With probability 1− δ over a uniform random instance x ∼ {±1}d, A (x) is an ε-error certificate of size poly(C(f), 1/ε, 1/δ), where C(f) is the “average certificate complexity" of f . The time and query complexity of A is poly(d, C(f), 1/ε, 1/δ).
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 succinctness 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.

heading: 1.1 Prior work on certificate finding
text: Efficient heuristics. Recent work of Ribeiro, Singh, and Guestrin [RSG18] 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 succinctness of these certificates, and in fact, it is easy to construct classifiers f : {±1}d → {±1} with near-minimal certificate complexity, C(f) = 2, for which their heuristic returns certificates of near-maximal size, Ω(d). (We elaborate on this in the body of this paper.) This should be contrasted with the guarantees of Theorem 1; specifically, the dimension-independent bound on the sizes of the certificates that our algorithm returns.
Prime implicants. A separate line of work has focused on finding prime implicants [Ign20, DH20, INM19, INMS19, SCD18]. In the terminology of Definition 1, an implicant is a 0-error certificate, and an implicant is prime if its error increases whenever a single feature is removed from it. We note that an implicant being prime (i.e. of minimal size) is not equivalent to it being the most succinct (i.e. of minimum size): a classifier f : {±1}d → {±1} can have an implicant of size 1 and also prime implicants of size d− 1. While 0-error certificates are desirable for their perfect precision, it is often impossible to find them efficiently. With no assumptions on f , even verifying that a certificate has 0 error requires querying f on the potentially exponentially many possible instances consistent with that certificate. Existing algorithms therefore focus on specific model classes. For example, [DH20] gives an 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 a certificate is 0-error is NP-complete. For general size-m circuits, finding the an 0-error certificate that has size within m1−ε of the smallest possible is NPNP-complete for any ε > 0 [Uma01].
Setting aside the computational intractability of finding 0-error certificates, we note that they are in general much less succinct than ε-error certificates. It is easy to construct examples where a size-1 certificate with 0.01-error exists, but the only 0-error certificate is the trivial one of size d containing
all features. In general, there is a natural tradeoff between the two desiderata of succinctness and precision, and our algorithm allows the user to choose their desired tradeoff rather than forcing them to choose perfect precision at the cost of succinctness.
Hardness of finding approximate certificates. There are also intractability results for finding the smallest ε-error certificate. [WMHK21] show that for any ε, determining whether there exists an ε-error certificate of size k for a given circuit and instance is NPPP-complete. Furthermore, they show that assuming P 6= NP, there is no efficient algorithm that can even approximate the size of the smallest ε-error certificate to within a factor of d1−α for any α > 0.
Theorem 1 circumvents these hardness results because our algorithm is only expected to succeed for most (at least a 1− δ fraction) rather than all instances, and only returns a small certificate relative to the average certificate complexity of the model, rather than smallest for a particular instance.

heading: 1.2 Our approach and techniques
text: 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 theorem [Smy02], which enables us to relate the certificate and decision tree complexities of functions. We then show how recently developed decision tree learning algorithms [BLT20b, BGLT20] 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 interpretable model. Their predictions admit simple explanations: a certificate for an instance x is the root-to-leaf path in the tree that x follows. A natural and wellstudied approach to explaining a blackbox model f is therefore to first learn a decision tree T that well-approximates f , and with this surrogate decision tree T in hand, one can then output a certificate for any instance x by returning the corresponding path in T [CS95, BS96, 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 wellapproximated 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—without 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 in 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 result resolved a 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 to design certificate-finding 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-finding algorithm is simple: it constructs a certificate C for an instance x by recursively adding to C the most noise stabilizing feature. Fruitful connections between noise stability and learnability have long been known [KOS04, KKMS08]; our work further demonstrates its utility for certificate finding.
Our overall approach falls within the framework of Local Computation Algorithms [RTVX11]. 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 x of interest—efficiently and consistently.

heading: 1.3 Discussion of broader context: global and local explanations
text: Existing approaches to post-hoc explanations mostly fall into two categories. Global explanations seek to capture the behavior of the entire model f , often by approximating it with a simple and interpretable model such as a decision tree [CS95, BS96, VAB07, ZH16, VLJ+17, BKB17, VS20] or a set of rules [LKCL19, LAB20]. A limitation of such approaches, alluded to above and also discussed in numerous prior works (see e.g. [RSG16, RSG18]), 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 x. Several of these approaches are based on notions of f being “simple around x”: for example, LIME explanations [RSG16] show that f is “approximately linear around x”, and certificates, the focus of our work, show that f is “approximately constant in a subspace containing x”. The corresponding algorithms can therefore be run on models that are too complex to be faithfully represented by a simple global surrogate model.
While our 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 a single decision tree T that wellapproximates f globally. The implicit nature of the learning task allows for T to be intractably large, hence allowing for corresponding algorithms to be run on 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 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 at 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 at any internal node v is the most “noise stabilizing” feature of the subfunction fv . 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 a “similarity 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 T 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.

heading: 1.4 Preliminaries
text: Feature and distributional assumptions. We focus on binary features and the uniform distribution 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. x ∼ {±1}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 ε-error decision tree complexity of f : {±1}d → {±1}, denoted D(f, ε), is the smallest k for which there exists a depth-k decision tree T satisfying Pr[T (x) 6= f(x)] ≤ ε.
Definition 3 (Certificate complexity). For a function f : {±1}d → {±1} and an instance x ∈ {±1}d, the ε-error certificate complexity f at x, denoted C(f, x, ε), is the size of the smallest ε-error certificate for x. That is, C(f, x, ε) is the size of the smallest set C ⊆ [d] for which
Pr y∼{±1}d
[ f(y) 6= f(x) | yC = xC ] ≤ ε.
The ε-error certificate complexity of f is the quantity
C(f, ε) := E x∼{±1}d [C(f,x, ε)].
When ε = 0, we simply write C(f, x) and C(f).

heading: 2 Implicitly learning decision trees
text: Our motivation for introducing the problem of implicitly learning decision trees is based on a simple but key property of decision trees. For any instance x, only a tiny portion of T ’s overall structure is “relevant” for its operation on x: the root-to-leaf path in T that x 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 a polynomial p and an instance x, all the monomials of p are “relevant” for p’s operation on x.
An algorithm for implicitly learning decision trees allows one to efficiently navigate a decision tree hypothesis for a target function without constructing the tree in full.
Definition 4 (Implicitly learning decision trees). An algorithm for implicitly learning decision trees is given query access to a target function f : {±1}d → {±1} and supports the following basic operations on a decision tree hypothesis T for f :
1. ISLEAF(T, α) which, given some node α, returns whether α is a leaf in T .
2. QUERY(T, α) which, given a non-leaf node α, returns the index i ∈ [d] corresponding to the feature that T queries at node α.
3. LEAFVALUE(T, α) which, given a leaf node α, returns the output value of that leaf.
We assume that α is represented as a restriction of a subset of the features {±1}d corresponding to the features queried along to the root-to-α path in 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.

heading: 2.1 The connection between implicitly learning DTs and certificate finding
text: 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-finding algorithms with efficiency that scales with the depth of the decision tree hypothesis T rather than its overall size.
Lemma 2.1 (Implicitly learning decision trees⇒ certificate finding). Let f : {±1}d → {±1} and ε, δ ∈ (0, 1). Suppose there is algorithm for implicitly learning f where the decision tree hypothesis T satisfies:
1. T is (εδ/2)-close to f , meaning Prx∼{±1}d [T (x) 6= f(x)] ≤ εδ/2.
2. T has depth k.
Suppose each of the operations in Definition 4 is supported in time t. Then there is an algorithm, FINDCERTIFICATE, which on x ∼ {±1}d runs in timeO(tk)+O(log(1/δ)/ε2) and finds an ε-error certificate of size at most k with probability at least 1− δ.
Proof. Consider the algorithm FINDCERTIFICATE given in Figure 1. By design, the certificates that it returns is ε-error and has size at most k, the depth of T . Each iteration of the algorithm takes time O(t), and the number of iterations is at most the depth of the root-to-leaf path in T that x follows, which is at most k; the additional time complexity of the random sampling step is O(log(1/δ)/ε2).
It remains to prove that FINDCERTIFICATE(f, T,x, ε, δ) outputs ⊥ with probability at most δ. Let A (x) the certificate checked in Step 4 or FINDCERTIFICATE. We prove that A (x) is an ε-error certificate for x with probability at least 1 − δ. First, we union bound the definition of an ε-error certificate as follows:
Pr y∼{±1}d
[ f(y) 6= f(x) | yA (x) = xA (x) ] ≤ Pr
y∼{±1}d [f(y) 6= T (y) | yA (x) = xA (x) ] + Pr
y∼{±1}d [T (y) 6= T (x) | yA (x) = xA (x) ] + Pr
y∼{±1}d [T (x) 6= f(x) | yA (x) = xA (x)
] .
Our goal is to prove for a random x ∼ {±1}d, the probability that the sum of three terms is more than ε is at most δ. The second term is simplest: whenever yA (x) = xA (x), y and x visit the same leaf in T , so T (y) 6= T (x) with probability 0. Hence, if the sum of the three terms is more than ε, it must be the case that either the first term or the third term is more than ε/2. The third term is just Pr[T (x) 6= f(x) ] , independent of the choice of y. This is at most 12εδ ≤ 1 2ε since T is 1 2εδ close to f . Finally, since
E x∼{±1}d
[ Pr
y∼{±1}d
[ f(y) 6= T (y) | yA (x) = xA (x) ]] = Pr
y∼{±1}d
[ f(y) 6= T (y) ] ≤ 12δε,
the first probability is more than ε/2 with probability at most δ by Markov’s inequality.

heading: 3 Certificate complexity, decision tree complexity, and Smyth’s theorem
text: Our notion of certificates as defined in Definition 1 is local, specific to each instance x, whereas Smyth’s theorem concerns a global notion of certificates, defined for the entire function f .
Notation. Fix a function f : {±1}d → {±1} and let C be a collection of subsets C ⊆ [d]. We write ‘x |= C ’ if there exists a 0-error certificate C ∈ C for x, and we write ‘x 6|= C ’ otherwise. Given two collections C1 and C−1 of subsets, we define a corresponding function ΦC1,C−1 : {±1}d → {±1,⊥} as follows:
ΦC1,C−1(x) =  1 if x |= C1 and x 6|= C−1 −1 if x |= C−1 and x 6|= C1 ⊥ otherwise.
Definition 5 (Global certificate complexity). The global ε-error certificate complexity of f : {±1}d → {±1}, denoted GC(f, ε), is the smallest k for which there exists two collections C1 and C−1 of size-k subsets satisfying Pr[f(x) 6= ΦC1,C−1(x)] ≤ ε.
Recalling Definition 2, it is straightforward to verify that GC(f, ε) ≤ D(f, ε) for all f : {±1}d → {±1} and ε > 0. Briefly, give a depth-k ε-error decision tree T for f , takes C1 to be the collection of size-k certificates corresponding to paths leading to 1-leafs, and C−1 to be the collection of size-k certificates corresponding to paths leading to −1-leafs. It is easy to see that Pr[f(x) 6= ΦC1,C−1(x)] ≤ ε. Smyth [Smy02], resolving a longstanding conjecture of Tardos [Tar89], proved a surprising converse to the elementary inequality above:
Theorem 2. For all f : {±1}d → {±1} and ε > 0, we have D(f, ε) ≤ O(GC(f, ε3/30)2/ε3).
We derive as a corollary of Smyth’s theorem a relationship between certificate and decision tree complexities:
Corollary 3.1 (Bounding decision tree complexity in terms of certificate complexity). For all f : {±1}d → {±1} and ε > 0, we have D(f, ε) ≤ O(C(f)2/ε9).
Proof. Let k := C(f). By Markov’s inequality, we have that Prx∼{±1}d [C(f,x) ≤ 30k/ε3] ≥ 1− (ε3/30). For every x ∈ f−1(1) (resp. x ∈ f−1(−1)) that contributes to this probability, we include in C1 (resp. C−1) its certificate of size 30k/ε3. It follows that Prx∼{±1}d [f(x) 6= ΦC1,C−1(x)] ≤ ε3/30 and hence GC(f, ε3/30) ≤ 30k/ε3. By Smyth’s theorem,D(f, ε) ≤ O(GC(f, ε3/30)2/ε3) = O(k2/ε9) and this completes the proof.

heading: 4 An efficient algorithm with provable guarantees
text: The notion of noise sensitivity underlies our implicit learning algorithm and its provable guarantees:
Definition 6 (Noise sensitivity). For f : {±1}d → {±1} and p ∈ (0, 1), the noise sensitivity of f at noise rate p is the quantity
NSp(f) := E x∼{±1}n
[ Pr
x′∼px [f(x) 6= f(x′)]
] ,
where x′ ∼p x means that x′ is drawn by independently rerandomizing each coordinate of x with probability p.
Strong connections between noise sensitivity and learnability have long been known [KOS04, BOW08, KKMS08, DHK+10, Kan14]. Most relevant for us is the work of Blanc, Gupta, Lange, and Tan [BGLT20], which gives a new decision tree learning algorithm with a noise-sensitivity-based splitting criterion, and shows that it achieves strong provable performance guarantees. Our algorithm is an implicit version of theirs that enjoys the exponential efficiency gains made possible by the implicit setting.

heading: 4.1 Greedy noise stabilizing decision trees
text: Definition 7 (Noise stabilizing score). For f : {±1}d → {±1} and p ∈ (0, 1), the noise stabilizing score, or simply the score, of the i-th feature with respect to f and p is the quantity:
Scoref (i, p) := NSp(f)− E b∼{±1} [NSp(fi=b)],
where fi=b is the restriction of f obtained by fixing the i-th feature to b.
We associate with every function f : {±1}d → {±1} its greedy noise stabilizing decision tree. Definition 8 (Greedy noise stabilizing decision tree). The greedy noise stabilizing decision tree for f : {±1}d → {±1} at noise rate p, denoted Υf,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 fα, the restriction of f by the root-to-α path. Every leaf ` of Υf,p is labeled according to f ’s value for the unique instance that follows the root-to-` path.
Υf,p has maximum depth d, the dimension of f ’s feature space. Since the succinctness of the certificates that of our certificate-finding algorithm returns scales with the depth of the decision tree hypothesis, we will truncate Υf at a much smaller depth k d. Furthermore, with query access to f 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 of Definition 8: Definition 9 (Depth-k η-approximate greedy noise stabilizing decision tree). Let f : {±1}d → {±1} and p ∈ (0, 1). For k ≤ d and η ∈ (0, 1), a depth-k η-approximate greedy noise stabilizing decision tree for f at noise rate p, denoted Υk,ηf,p , is a complete depth-k decision tree where:
◦ At every internal node α, the feature i that is queried has noise stabilizing score with respect to f that is within η of the highest:
Scorei(fα, p) ≥ Scorej(fα, p)− η for all j 6= i.
◦ Every leaf ` is labeled sign(E[f`]).

heading: 4.2 Proof of Theorem 1
text: We now show that, owing to the simple top-down inductive definition of Υk,ηf,p , there is an efficient algorithm for implicitly learning any target function f with Υk,ηf,p as the decision tree hypothesis.
Lemma 4.1 (Implicit learning with Υk,ηf,p as the decision tree hypothesis). Let f : {±1}d → {±1} be a function. For k ≤ d and η, p ∈ (0, 1), given query access to f , all the operations of Definition 4 can be supported in time O(d2/η2) with Υk,ηf as the decision tree hypothesis.
Proof. Since Υk,ηf is a complete tree of depth k, we return TRUE for ISLEAF(Υ k,η f,p , α) iff α corresponds to a path of length exactly k. Note that query access to f gives us query access to all its subfunctions fα for any α. Therefore, by standard random sampling arguments, we can an estimate of the noise sensitivity of fα that is accurate to within ±η w.h.p. using O(1/η2) queries to f . This allows us to obtain high-accuracy estimates of the noise stabilizing scores of all the features of fα in time O(d2/η2), and hence support QUERY(Υk,ηf,p , α) queries by returning the feature with the highest empirical score. Similarly, we can support LEAFVALUE(Υk,ηf,p , α) queries by approximating E[fα] to high accuracy and returning its sign.
We will need a structural theorem of [BLT20a] that bounds the distance between f and the greedy noise stabilizing decision tree Υk,ηf,p :
Theorem 3 (Lemma 2.1 of [BLT20a]). Let function f : {±1}d → {±1} be a function. Consider Υk,ηf,p where k = O((D(f, ε)/ε)3), η = Θ(1/k), p = O(ε/D(f, ε)). Then Pr[Υk,ηf,p(x) 6= f(x)] ≤ O(ε).
We are now ready to put all the pieces together and establish Theorem 1:
Proof of Theorem 1. By our corollary to Smyth’s theorem, Corollary 3.1, we have the bound D(f, εδ) ≤ O(C(f)2/(εδ)9). Combining this with Theorem 3, we get that
1. Pr[Υk,ηf (x) 6= f(x)] ≤ O(εδ), where
2. k ≤ O((D(f, εδ)/ε)3) ≤ poly(C(f), 1/ε, 1/δ).
These correspond exactly to the two items in the assumption of Lemma 2.1 with ‘T ’ being Υk,ηf,p , and the theorem follows.
Comparison with the certificate-finding algorithm of [RSG18]. We conclude this section by comparing our resulting certificate-finding algorithm to the heuristic proposed in [RSG18].
Different greedy choice. Both our algorithm and [RSG18]’s heuristic are greedy in nature. Our algorithm builds a 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 can therefore be viewed as using noise stability as a proxy for progress towards a highprecision certificate. In contrast, [RSG18] takes a more direct approach and iteratively adds to the certificate the feature that results in the largest gain in estimated precision.
Provable performance guarantees. [RSG18]’s heuristic is efficient and returns high-accuracy certificates, but it is easy to construct examples showing that it fails to return succinct certificates. As a simple example, consider f(x) = xi ⊕ xj , the parity of two unknown features i, j ∈ [d]. Every instance has a certificate of size two, C = {i, j}, but since any certificate comprising a single feature {k} has the same precision (regardless of whether k ∈ {i, j}), [RSG18]’s heuristic may include in its certificate all d − 2 irrelevant features. In contrast, since C(f) = 2, Theorem 1 shows that our algorithm returns a high-accuracy certificate of constant-size with high probability. ([RSG18] also considers an extension of their algorithm that incorporates beam search; similar hard functions can be constructed for this extension.)

heading: 5 Conclusion
text: Certificates are simple and intuitive explanations that have been shown to be effective across domains and applications [RSG18]. In this work we have designed an efficient certificate-finding algorithm and proved that it returns succinct 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.
Limitations of our work. The main limitation, and perhaps the most immediate avenue for future work, is the feature and distributional assumptions of Theorem 1. We do not believe that these are inherently necessary for the provable guarantees that we achieve. The main bottleneck to 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, so does our extension of their algorithm to the implicit setting.
Other aspects of our approach go through for more general feature spaces and distributions. Smyth’s theorem holds for arbitrary product spaces, and so 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 a few concrete ones:
◦ Improved algorithms and guarantees for specific models. Our algorithm is model agnostic, requiring no assumptions about the model f that it 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-finding algorithm proceeds by iteratively adding to 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 [LL17]). 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 our 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 on 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 is 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 be combined with those of Moshkovitz, Yang, and Chaudhuri [MYC21] to robustify arbitrary models, making them more resilient to noise and adversarial examples?
More broadly, our work is 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 theoretical computer science can be utilized to contribute to a theory of explainable ML.
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.

Review summaries:
The paper considers a new algorithm for creating  explanations of predictions of arbitrary black box models.  In this paper, an explanation is a subset of the input features that explain the prediction in the sense that changing the input features, not in the explanation subset at random, has only a small probability of changing the model prediction.  The paper considers only binary features and binary classification and assumes uniform distribution over the input.  The 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 the smallest explanation when averaged over all inputs (and 1/delta, 1/epsilon where epsilon is error allowed).  The 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, the 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.  The main component of the theorem is based on a result from complexity theory, that bound certificate complexity (an explanation is a certificate) of a function, polynomially in terms of the decision tree complexity (depth) of the function, which leads to the polynomial in the bound given.  The 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 works for only uniform distribution over binary features and binary classes, providing the limiting features of the result shown. The algorithm is sped up with random sampling which is straightforward by the same assumptions.  

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.

This work proposes (1) a new theoretical model for algorithms to explain the predictions of black-box classifiers and (2) an algorithm in this model that produces such explanations with polynomial guarantees on its running time for producing explanations of a given fidelity.  The model is an analogue of learning under the uniform distribution, making use of the ability to query the black-box classifier. Given a point of interest, the algorithm finds a conjunction that is relatively small with high probability (over the draw of a point of interest) and such that points matching the conjunction receive the same label as the point of interest with high probability over subsequent draws of points. All draws are w.r.t. the uniform distribution on Boolean features. Note that the size of the conjunction  therefore also corresponds directly to its coverage, which is 1/2^size.  The algorithm is an adaptation of recent decision tree learning algorithms, that greedily branch on the attribute that reduces the noise sensitivity the  most. The explanation is given by the branch that the point of interest follows in this tree. The guarantees follow from a connection between certificate  complexity and decision tree depth. 

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.