Counterfactual reasoning is at the very heart of causal inference (Pearl, 2009a;b;Morgan & Winship, 2015). Counterfactuals are answers to "what would have happened if" questions: if a person has been denied a loan, would their application have been approved if their annual income were $20k higher? In explainable ML, there is a growing interest in the use of counterfactual explanations (Wachter et al., 2017) to understand the predictions of black box models: given a model f and an instance x , we would like to efficiently determine how a few features of x can be changed to obtain a similar instance x for which f (x ) = f (x ).
It is natural to seek sparse counterfactuals, meaning that x Proceedings of the 39 th International Conference on Machine Learning, Baltimore, Maryland, USA, PMLR 162, 2022. Copyright 2022 by the author(s). differs from x in as few features as possible. Ideally, we would like counterfactuals that are optimally sparse: Definition 1.1 (Sparsity and optimality). For a model f : X d → {0, 1} and two instances x , x such that f (x ) = f (x ), the sparsity of x as a counterfactual for x is the number of features on which they differ: the quantity |∆(x , x )|, where ∆(x , x ) := {i ∈ [d] :
The counterfactual complexity of x with respect to f is the quantity:
and we say that x is an optimal counterfactual for x if |∆(x , x )| = ∆ f (x ).
Another desideratum that has received significant attention, motivated by the need for actionable recourse (Ustun et al., 2019), is that of diversity in counterfactual explanations (Wachter et al., 2017;Russell, 2019;Mothilal et al., 2020;Karimi et al., 2020): a wide range of counterfactuals instead of just a single one.
Our first result is an efficient algorithm for finding all optimal counterfactuals for any monotone f in the setting of binary features: Theorem 1.2. Given queries to a monotone model f : {0, 1} d → {0, 1} with sensitivity S(f ) and an instance x , our algorithm makes
• log d queries to f and w.h.p.foot_0 returns all optimal counterfactuals for x .
We will define and discuss sensitivity in the body of the paper (see Section 1.4), mentioning for now that it is a wellstudied discrete analogue of the Lipschitz constant, and this quantity is often much smaller than d.
Next, we consider the setting of general feature spaces. In this setting it is infeasible to return all optimal counterfactuals due to the sheer number of them. We are nevertheless able to efficiently return the collection of all subsets of features induced by these optimal counterfactuals: Theorem 1.3. Given queries to a monotone model f : X d → {0, 1} with sensitivity S(f ) and an instance x , our algorithm makes S(f ) O(∆ f (x )) • log d queries to f and w.h.p. returns the collection C f (x ) = {∆(x , x ) : x is an optimal counterfactual for x }.
Theorems 1.2 and 1.3 give the first algorithms with query complexity that evades the curse of dimensionality, and indeed, strongly so. We contrast our query complexity to that of ball search, a simple and natural algorithm for finding counterfactuals: first query f on x and all instances that differ from x by a single feature. (By the monotonicity of f , for any feature, it suffices to query f on the instance that differs maximally from x on that feature.) Next, query f on the instances that differ by two features, and so on, until a counterfactual is found. This algorithm has query complexity d O(∆ f (x )) , an exponentially worse dependence on d than ours. Prior to our work, this was the best known query complexity even just to return a single optimal counterfactual.
Lower bounds. We complement Theorems 1.2 and 1.3 with a couple of lower bounds. All our lower bounds hold even in the setting of binary features (X = {0, 1}), and against randomized algorithms that are only required to successfully return an optimal counterfactual with a small probability (say 0.01). We first show that the query complexity of our algorithm is essentially optimal: Theorem 1.4 (Optimality of Theorems 1.2 and 1.3, see Theorem C.1 for the formal version). For any algorithm A and S ∈ N, there is a monotone model f : {0, 1} d → {0, 1} with S(f ) = S and an instance x such that A must make S Ω(∆ f (x )) + Ω(log d) many queries to f , even just to find a single optimal counterfactual for x .
We also establish the inherent limitations of local search algorithms, a broad and natural class of algorithms for finding counterfactuals. A local search algorithm is any algorithm whose first query is x , and whose every subsequent query differs from a previous one by exactly one feature. For example, ball search is a local search algorithm. We show that no local search algorithm can achieve the query complexity that our algorithm does, even for low-sensitivity monotone functions:
Theorem 1.5 (Lower bound for local search algorithms, see Theorem C.5 for the formal version). For any local search algorithm A and d ∈ N, there is a monotone model f : {0, 1} d → {0, 1} with S(f ) = 1 and an instance x with ∆ f (x ) = 1, such that A must make Ω(d) many queries to f to find a single optimal counterfactual for x .
Theorems 1.2 and 1.3 circumvent the lower bound of Theorem 1.5 via a novel approach that is not based on local search. The crux of our approach is a new algorithm for understanding monotone black box models that we believe will see further utility beyond counterfactual explanations: using only queries to a monotone black box model f , this algorithm allows us to navigate a decision tree representation T of f without actually building T in full. Crucially, since we strive to handle arbitrarily complex models f , this tree T may be too large to build efficiently in its entirety.
With this algorithm, given any instance x , we will build only the "necessary part" of T to find all optimal counterfactuals for x . We show that just a tiny portion of T suffices for this purpose: it suffices to build only the root-to-leaf path ρ in T that x follows and the paths that are "close to" ρ in T in a sense that we will make precise (see the beginning of Section 3 for more details on this notion of " path distance"). Writing h to denote the depth of T , we prove that we only have to construct h O(∆ f (x )) many nodes in T , which is only an exponentially small part of T . Next, by bringing together classical (Nisan, 1989) and recentlydevelop results (Blanc et al., 2022) about the structure of monotone functions, we are able to bound the depth of T and in terms of f 's sensitivity.
To summarize, our overall approach allows us to enjoy the benefits of having access to a highly interpretable representation of a black box model f -a decision tree representationwithout paying the price associated with T being intractably large for most complex models of interest.
Our work is theoretical in nature: we give an algorithm with strong bounds on its query complexity and all the counterfactuals that it returns are guaranteed to be optimal. We view our main contribution as proving the curse of dimensionality can be strongly evaded for a broad and natural class of models-all monotone models.
There is a substantial body of empirical work on counterfactual explanations. The algorithms in these works either do not guarantee optimal counterfactuals or do not come with a formal analysis of their query complexity. Many of these works rely on classic optimization tools: the algorithms of (Wachter et al., 2017;Mothilal et al., 2020) are based on gradient descent and hence are restricted to differentiable models, whereas the algorithms of (Russell, 2019;Ustun et al., 2019) use mixed integer programming and are limited to linear models. (Karimi et al., 2020) encode the problem of finding optimal counterfactuals as a satisfiability problem, which they then solve using SMT solvers.
The importance of diversity in counterfactual explanations has been highlighted in several works (Wachter et al., 2017;Russell, 2019;Mothilal et al., 2020;Karimi et al., 2020). Significant motivation comes from the need for actionable recourse (Ustun et al., 2019): a large set of counterfactuals is more likely to contain one that is actionable (e.g. in the context of a loan denial, an applicant can plausibly work towards earning a higher income but cannot change their history of defaults).
Regarding our techniques, they are in the spirit of a recent line of theoretical work on implicit learning algorithms: algorithms that are able to access their hypotheses efficiently without constructing them in full (Kong & Valiant, 2018;Blum & Hu, 2018;Kong et al., 2020;Backurs et al., 2020;Blanc et al., 2021). In particular, Blanc, Lange, and Tan (Blanc et al., 2021) show how, given queries to a model f , one can efficiently navigate an implicit decision tree hypothesis T that is ε-close to f under the uniform distribution. The presence of errors in the hypothesis, and the fact that these errors are measured with respect to the uniform distribution, are significant limitations of their result. Our work shows how these limitations can be overcome, in a strong sense, in the case of monotone models f : our implicit decision tree hypothesis T computes f exactly, which is crucial for our application to finding counterfactuals. Another limitation of (Blanc et al., 2021)'s analysis is that it only applies to the setting of binary features; we do not need this assumption.
Finally, we mention that counterfactual explanations are part of a broader landscape of local explanations (Strumbelj & Kononenko, 2010;Baehrens et al., 2010;Simonyan et al., 2014;Ribeiro et al., 2016;Koh & Liang, 2017;Lundberg & Lee, 2017;Ribeiro et al., 2018), which seek to explain a model's prediction for specific inputs. Global explanations, on the other hand, approximate the entire model with a simple and interpretable one (Craven & Shavlik, 1995;Breiman & Shang, 1996;Van Assche & Blockeel, 2007;Zhou & Hooker, 2016;Vandewiele et al., 2017;Bastani et al., 2017;Vidal & Schiffer, 2020;Lakkaraju et al., 2019;2020).
We rely on a few standard notions from the study of Boolean functions.
Definition 1.6 (Sensitivity). For a function f : X d → {0, 1} and an instance x ∈ X d , the sensitivity of f at x is the quantity
where i ← a denotes x with its i-th feature set to a. That is, S f (x) is the number of features i of x for which there is a way of changing x i that flips f 's value on x.
The sensitivity of f is the quantity S(f ) = max
The sensitivity of a function can be viewed as a discrete analogue of the Lipschitz constant, with low-sensitivity discrete functions being considered smooth. To see this analogy, we observe that for all x ∈ X d and δ ∈ (0, 1),
See (Gopalan et al., 2016) for more on this perspective. Introduced by Cook, Dwork, and Reischuk (Cook et al., 1986), the sensitivity of discrete functions is the subject of intensive study in theoretical computer science; it is, for example, the key notion in the recent breakthrough Sensitivity Theorem of Huang (Huang, 2019) (see also (Knuth, 2019)), resolving a longstanding conjecture of Nisan and Szegedy (Nisan & Szegedy, 1994).
Monotonicity. For a model f : X d → {0, 1}, we assume an ordering ≤ on the elements of X which we lift coordinatewise to a partial ordering on X d . That is, for x, y ∈ X d , x ≤ y if and only if x i ≤ y i for all i ∈ [d]. We say f is monotone if it is monotone with respect to such an ordering. We'll also assume that X has a maximum and minimum element.
Structure of the rest of this paper. We first prove Theorem 1.2, which focuses on functions with Boolean features. To do so, we will recall the notion of an implicit decision tree from (Blanc et al., 2021) in Section 2. Then, in Section 3, we prove Theorem 1.2 assuming a sufficiently good implicit decision tree exists. In Section 4, we complete the proof of Theorem 1.2 by showing how to build that implicit decision tree.
Given Theorem 1.2, we show how to extend our algorithm to the setting of arbitrary features by reducing to the Boolean setting and prove Theorem 1.3 in Section 5. Finally, we prove our lower bounds, Theorems 1.4 and 1.5, in Appendix C.
Our algorithm for finding counterfactuals will rely on having access to a decision tree T which exactly represents the model f : {0, 1} d → {0, 1}. At a high level, for an instance x , the algorithm follows a unique root-to-leaf path ρ in T searches all root-to-leaf paths in T that are "close to" ρ in a sense that make precise in the next section. In general, the size of T will be exponentially larger than the search space of our counterfactual finding algorithm, and hence it is advantageous to avoid computing the entire tree. Instead, we maintain an implicit copy of the tree T . This copy allows us to compute only the parts of the tree that we need to find optimal counterfactuals for x .
Restrictions. An implicit decision tree T , a notion introduced in (Blanc et al., 2021), is an algorithm which given query access to f can navigate T without building it in full. A node in T is specified by a restriction which is a partial function ρ : [d] {0, 1} indicating which (if any) features are fixed to specific values. These features and their values correspond to those queried along a path in the tree. We write Dom(ρ) ⊆ [d] to denote the domain of the restriction. The size of a restriction |ρ| is |Dom(ρ)|, the number of values on which it is defined. We write
which is formed by inserting features specified by ρ into the instance x. For example, ρ = {1 → 1, 4 → 1} is the restriction where the 1st and 4th features are fixed to
Definition 2.1 (Implicit decision tree). An implicit decision tree (IDT) T for f : {0, 1} d → {0, 1} is an algorithm which has query access to f and supports the following operations. For a restriction ρ : [d] {0, 1} corresponding to features queried along a root-to-ρ path in T and auxiliary information A ⊆ [d]:
updated auxiliary information.
If each operation uses at most q queries to f with high probability then the algorithm is a q-query implicit decision tree for f .foot_1
The role of auxiliary information. Our algorithm for finding counterfactuals updates the auxiliary information after each query and we assume that the auxiliary information being passed to the algorithm originates from the previous query (the auxiliary information at the root can be arbitrary). Internally, the auxiliary information will be a subset of features and will allow us to precompute parts of the tree instead of node by node. This way, most calls to QUERY(ρ, A) will simply return the appropriate feature index from A until all such features in A are exhausted after which a new A is computed from scratch. The example below illustrates the reuse of auxiliary information between IDT operations. For a more detailed illustration of an IDT and the precomputation of parts of the tree using auxiliary information see Figure 4.
Example. Figure 3 in Appendix D illustrates how the IDT operations can be used to walk down a decision tree T representing a function f . In this case, we make three calls to QUERY f (•, •) corresponding to the depth of this particular root-to-leaf path. In general, if a q-query IDT has depth at most k, then the root-to-leaf path corresponding to an instance x can be constructed using O(k) calls to the IDT operations and therefore O(kq) queries to f .
Our key technical lemma. For our intended application, it will be important that the IDT exactly represents f . The work of (Blanc et al., 2021) design a relaxed variant of IDTs that only approximates models f with respect to the uniform distribution over instances. Both the presence of errors and the uniform-distribution assumption are not ideal, and can be seen to be inherent to the proof technique of (Blanc et al., 2021). In this work we use recently developed structural results for monotone models (Blanc et al., 2022) to overcome these limitations. Our key technical lemma is the following.
Lemma 2.2 (Exact IDTs for monotone models). Let f : {0, 1} d → {0, 1} be monotone. Then there is an S(f ) O(1) • log d-query IDT for f with depth at most S(f ) O(1) .
In the next section we prove Theorem 1.2 assuming Lemma 2.2. We then prove Lemma 2.2 in Section 4.
3. Using IDTs to find optimal counterfactuals: Proof of Theorem 1.2
Suppose we may access an implicit decision tree T for f as described in Definition 2.1. We present an algorithm for finding counterfactuals using these operations and analyze its query complexity in terms of the depth h of T and the query complexity of the IDT-Lemma 2.2 provides strong bounds on both quantities in terms of the sensitivity of f .
Intuition. Given an instance x , it follows a unique rootto-leaf path ρ in T . We begin with a simple observation: if there is a counterfactual x of distance 1 from x , it must belong to the set I 1 of all instances that differ from x on a single feature queried along ρ. The size of I 1 is the length of ρ, which is at most the depth h of T . Building on this observation, if x is a counterfactual of distance 2 from x , there must be an instance x ∈ I 1 such that x differs from
x on a single feature queried on the path π that x follows in T . This reasoning leads to a bound of h O(∆ f (x )) on the size of our search space-all paths in T of "path distance" ∆ f (x ) from ρ-which stands in contrast to d O(∆ f (x )) , the size of the search space of ball search.
Our algorithm for finding optimal countefactuals will call on a subroutine, FINDMINIMAL (Figure 1), for finding minimal counterfactuals:
denote the features that x and x differ on. Then f (x ) = f (x ) for all instances x ∈ I that differ from x only on the features in a strict subset U ⊂ V .
We observe that optimal counterfactuals are minimal, but minimal counterfactuals may not be optimal.
Our pseudocode for FINDMINIMAL uses the following notation. Recall that a restriction is a partial function ρ : [d] {0, 1}, which we can equivalently represent as a string ρ ∈ {0, 1, * } d . We use the notation ρ i←b to denote the restriction ρ with ρ i overwritten with b. For x ∈ {0, 1} d , we define x overwritten by ρ, denoted x ρ ∈ {0, 1} d , to be the following hybrid input: for all i ∈ [d], k,A) returns all minimal counterfactuals x for x among those that are consistent with ρ and satisfy
Proof. We begin by noting all instances that are consistent with ρ differ from x on at least the features on which x and x ρ differ. Therefore, if f (x ρ ) = f (x ), FINDMINIMAL correctly returns {x ρ } in Line 1.
We therefore assume that f (x ρ ) = f (x ) and proceed by induction on the height of the subtree of T rooted at ρ. If ρ is a leaf, then f takes the same value on all instances x that are consistent with ρ, and hence f (x ) = f (x ρ ) = f (x ). In this case FINDMINIMAL correctly returns ∅ in Line 2.
For the inductive step, suppose ρ is an internal node. If k = 0, the only instance that is of distance 0 from x ρ is x ρ itself, so FINDMINIMAL again correctly returns ∅ in Line 2. Otherwise, the search space of all instances x that are consistent with ρ and satisfy ∆ f (x , x ρ ) ≤ k can be partitioned into:
• Those that are consistent with ρ i←x i and satisfy
• Those that are consistent with ρ i←x i and satisfy
where i is the feature that is queried at ρ (Line 3a). FIND-MINIMAL recurses on these two sets in Line 3b, and correctness follows by our induction hypothesis.
Remark 3.3 (Correctness of auxiliary information). Our proof of Lemma 3.2 relies on the correctness of the IDT operations, which only hold if our calls to them use the "correct" auxiliary information A. This will be the case given the way we use FINDMINIMAL in our overall algorithm FINDOPTIMAL. FINDOPTIMAL calls FINDMINIMAL with ρ being the empty restriction and A = ∅. In its recursive execution, FINDMINIMAL with auxiliary information A recursively calls itself with A where A is the auxiliary information returned by QUERY(ρ, A) in Line 3a: the correctness of A follows from the correctness of A and the QUERY operation. Lemma 3.4 (Query complexity of FINDMINIMAL). FINDMINIMAL f (ρ, x, k, A) makes h O(k) calls to the IDT operations and h O(k) additional queries to f , where h is the height of the subtree of T rooted at ρ.
Proof. We claim that both quantities are bounded by
The proof is by induction on h. When h = 0 (i.e. ρ is a leaf in T ), FINDMINIMAL queries f on x and x ρ , makes one call to ISLEAF, and terminates. When h ≥ 1, there are at most two queries to f (on x and x ρ ), two calls to IDT operations (ISLEAF and QUERY), in addition to those made recursively. We therefore have the following recursive relation:
Applying the induction hypothesis, we can bound
With the helper algorithm FINDMINIMAL in hand, our overall algorithm for finding optimal counterfactuals is simple:
Theorem 1.2 is a straightforward consequence of Lemmas 2.2, 3.2 and 3.4: FINDMINIMAL f (ρ, x , k, A):
Given: Access to f via queries and IDT operations for a tree T that represents f . Restriction ρ corresponding to a path in T , instance x , distance bound k, auxiliary information A.
Output: All minimal counterfactuals x for x among those that are consistent with ρ and satisfy
2. Else if ISLEAF(ρ, A) or k = 0, return ∅.
3. Else: Given: Instance x and queries to f .
The set C of all optimal counterfactuls for x .
3. Return C.
Figure 2: Algorithm for finding optimal counterfactuals, using FINDMINIMAL as its main subroutine.
Theorem 3.5 (Formal version of Theorem 1.2). Let f : {0, 1} n → {0, 1} be a monotone function. Then FINDOPTIMAL f (x ), using the IDT operations given in Lemma 2.2, returns all optimal counterfactuals for x and makes S(f
Proof. The correctness of FINDOPTIMAL follows from that of FINDMINIMAL: FINDOPTIMAL calls FINDMINIMAL f ( * d , x , k, ∅) for k = 1, 2, 3, . . . until a call returns a nonempty set. This happens exactly when k reaches ∆ f (x ).
It remains to analyze the query complexity of FIND-OPTIMAL. By Lemma 2.2, the height of T is at most S(f ) O(1) . Therefore by Lemma 3.4 we have that FINDMINIMAL f ( * d , x , k, ∅) uses at most S(f ) O(k) IDT operations and additional queries to f . By Lemma 2.2, each IDT operation can be supported with S(f ) O(1) •log d queries to f . The overall query complexity of FINDOPTIMAL is therefore upper bounded by
Proof of Lemma 2.2
In this section, we prove Lemma 2.2. Our implementation of IDTs will be based on known algorithms for finding certificates. These certificates will be stored in the auxiliary information of the IDT and will be used to select which features to query in the decision tree.
At a high level, a certificate of f on x ∈ {0, 1} d is a set of features W ⊆ [d] that "witness" f 's value on x in the sense that f (y) = f (x ) for all y ∈ {0, 1} d that agree with x on the coordinates in W .
Definition 4.1 (Certificate complexity). For a model f : {0, 1} d → {0, 1} and an input x , the complexity of certifying f 's value on x , C(f, x ), is the quantity:
The certificate complexity of f is the quantity C(f
Example. Because the set W = [d] is always a certificate of f on x , we typically want small certificates satisfying |W | ≤ C(f ). For a specific example, consider the function f : {0, 1} 5 → {0, 1} defined by the decision tree in Figure 3. Then W = {1, 3, 5} is a certificate of f on x = 10000 since f outputs 0 on any input y satisfying y 1 = 1, y 3 = 0, and y 5 = 0. Indeed, for an arbitrary instance x the indices queried along the root-to-leaf path for x constitute a certificate of f on x .
In general, we say W ⊆ [d] is a certificate of f if there exists some x ∈ {0, 1} d such that W is a certificate of f on x. Our algorithm relies on a query-efficient procedure CERT(f ) which takes a monotone f and returns the features in small certificate of f . The features in this certificate will be exactly the features we query in our IDT for f . "Small certificate" here means having size at most C(f ) O(1) . For monotone functions, this size bound is equivalently S(f ) O(1) using the fact that certificate complexity equals sensitivity for monotone models f : Nisan, 1989)). For a monotone model f :
The authors of (Blanc et al., 2022) recently developed a query-efficient implementation of CERT(•) for monotone f . We restate their result here in terms of S(f ) using Fact 4.2.
Theorem 4.3 (Theorem 5 of (Blanc et al., 2022)). Let f : {0, 1} d → {0, 1} be monotone. Then there is an algorithm that computes a certificate of f of size S(f ) O(1) with high probability using S(f ) O(1) • log d queries to f .
Figure 3 depicts the overall structure of an IDT. Conceptually, the tree can be divided into subtree "blocks". For a subtree rooted at ρ, this block is the complete binary tree that exhaustively queries all features in CERT(f ρ ), a small certificate for f ρ . One call to CERT(f ρ ) yields a set of features to query in the tree and so we store this set as auxiliary information until we need to call CERT(•) again. The overall depth of the tree is the number of consecutive blocks in a root-to-leaf path times the depth of each block. The depth of each block is the size of the certificate returned by CERT(•) and so Theorem 4.3 ensures that this depth is small. In the next section, we give the implementation details of the IDT operations which yield this IDT structure. Then, we show how to bound the number of consecutive blocks which provides a bound on the overall depth of the IDT. This procedure stores a list of features in the auxiliary information, A, which is then queried iteratively until all features have been exhausted after which a new set of features is computed using CERT. The set A specifies a complete binary tree of depth |A| -the tree which exhaustively queries all of the features in A. In this way, the entire IDT is a collection of complete subtree blocks each of which originates from a certificate output by CERT. Figure 4 illustrates the computation path of a particular input through an IDT using auxiliary information to store subtree blocks.
ISLEAF f (•, •). When f is monotone, one can check whether it's the constant function by querying f on the all 0s input and the all 1s input. Therefore, to check whether ρ is a leaf, we can query f ρ on these two inputs and output Yes if and only if f ρ is determined to be the constant function.
We also use the following lemma (implicit in Theorem 6 of (Blanc et al., 2022)) which states that f quickly becomes the constant function after being repeatedly restricted by a certificate. Alternatively, consecutive blocks in an IDT quickly terminate in a leaf node. More specifically, suppose A = CERT(f ) is a certificate for f . So, there is some restriction ρ : [d] {0, 1} with Dom(ρ) = A such that f ρ is a constant function. Equivalently, there is some way of setting each feature in A to a value in {0, 1} such that f ρ is the constant function. In general, for an arbitrary restriction ρ : [d] {0, 1} with Dom(ρ) = A (an arbitrary setting of each feature in A to {0, 1}), f ρ may be nonconstant. However, one can show f ρ is "closer" to a constant than f in the sense that f ρ has smaller certificate complexity. The following lemma captures this behavior and states more specifically that f becomes constant after O(S(f )) many such restrictions. For more details, see the proof of the lemma in Appendix A.
Lemma 4.4 (Implicit in Theorem 6 of (Blanc et al., 2022)). Let f : {0, 1} d → {0, 1} be monotone. Let ρ 1 , . . . , ρ be a series of restrictions and A 1 , . . . , A ⊆
We prove that our implementations of QUERY f and ISLEAF f suffice to prove the lemma statement. First, we show that the implementations require at most S(f ) O(1) • log d queries to f , then we show the depth of the IDT is at most S(f ) O(1) .
The procedure ISLEAF uses O(1) queries to f . A call to QUERY(ρ, A) returns either a feature in A or queries CERT(f ). Theorem 4.3 shows that CERT(f ) requires at most S(f ) O(1) • log d to f and hence QUERY(ρ, A) requires at most S(f ) O(1) • log d queries to f . It remains to show that the depth of the IDT is at most S(f ) O(1) . Let ρ be an arbitrary leaf of the IDT. By construction, Dom(ρ) can be partitioned into blocks of features A 1 , . . . , A where each A i is a certificate of f restricted on the features in A 1 ∪ • • • ∪ A i-1 . Lemma 4.4 ensures that f becomes constant after being restricted by = S(f ) O(1) many such certificates.
Proof of Theorem 1.3
For a monotone model f : X d → {0, 1} and an instance x ∈ X d , we reduce the problem of computing C f (x ) to the problem of computing C f x (y) where f x : {0, 1} d → {0, 1} is a Boolean model defined in terms of f and x and y ∈ {0, 1} d is a specific Boolean input to f x .
The reduction. We assume f : X d → {0, 1} is monotone with respect to some total ordering on X. Write X for the top element of X and X for the bottom element of X.
Assuming f is nonconstant, we then have f (X d ) = 1 and f (X d ) = 0. For x ∈ X d and y ∈ {0, 1} d , we define x ↑ y, x ↓ y ∈ X d as instances satisfying
That is, x ↑ y is the instance formed by "snapping" a subset of features, specified by y, to their largest possible value X. In x ↓ y, features are snapped in the opposite direction. Note that relative to the ordering ≤ on X, we have x ↓ y ≤ x ≤ x ↑ y for all y ∈ {0, 1} d . Given a monotone f : X d → {0, 1}, we write x ↑↓ f y to denote snapping x in a direction specified by f (x):
We will just write x ↑↓ y when f is known from context. We then define the Boolean function
Note that f x is monotone since y ≤ y implies x ↑↓ y ≤ x ↑↓ y .
Properties of f x . We establish two important properties of the reduction f x . The first property states that the set
The second property states that the sensitivity of f x is at most the sensitivity of f . For a proof, see Appendix B.
Lemma 5.1. Let f :
Let f : X d → {0, 1} be monotone and x ∈ X d . Assume without loss of generality f (x ) = 1. Using Theorem 3.5, we compute and return the set
which ensures we have returned the desired set. Moreover, since these two sets are equal we have that
We can then write the query bound as
which completes the proof.
We have given a query-optimal algorithm for finding counterfactuals for monotone models. Our algorithm achieves a logarithmic dependence on the dimension d, which is exponentially smaller than the previous best known query complexity of d O(∆ f (x )) , achievable by brute-force local search.
There are several concrete avenues for future work. The key enabling ingredient in our overall algorithm is our implicit decision tree algorithm for monotone models. This gives us a way to efficiently navigate an interpretable representation of a black box model f -a decision tree representationeven in the case of complex models for which this representation is intractably large. This is a potentially versatile technique for understanding black box models -can we use it to efficiently compute other types of explanations?
The query complexity of our algorithm scales with the sensitivity of f , a discrete analogue of the Lipschitz constant.
Can our lower bounds be evaded by running our algorithm, or variants of it, for smoothed versions f of f , obtained from f by adding a small amount of noise? Finally, while we have focused on sparsity as our notion of distance in this work, it would be interesting to extend our techniques to accommodate other distance functions.
In this section, we prove Lemma 4.4. We say a certificate S ⊆
We write C 0 (f ) = max x∈f -1 (0) {C(f, x)} to denote the 0-certificate complexity of f and C 1 (f ) = max x∈f -1 (1) {C(f, x)} for the 1-certificate complexity of f . Our proof will reference the fact that the intersection of a 1-certificate with a 0-certificate is necessarily nonempty (since otherwise there would be some instance x ∈ {0, 1} d having both a 0-certificate and a 1-certificate).
Fact A.1. Let S 0 be a 0-certificate of f : {0, 1} d → {0, 1} and let S 1 be a 1-certificate of f . Then S 0 ∩ S 1 = ∅.
Proof of Lemma 4.4. Let ρ be a restriction of f : {0, 1} d → {0, 1} such that Dom(ρ) = CERT(f ). We'll show that
The result then follows by induction. Suppose without loss of generality that Dom(ρ) is a 1-certificate of f . Then we claim C 0 (f ρ ) ≤ C 0 (f ) -1. Consider any x ∈ f -1 ρ (0). Consider the string x ∈ {0, 1} d formed by inserting ρ into the string x so that f (x ) = f ρ (x). Let S 0 be a 0-certificate of f on x with
It follows each such restriction ρ decreases C 0 (f ) + C 1 (f ) by at least 1. Thus, after at most 2C(f ) ≥ C 0 (f ) + C 1 (f ) restrictions f becomes the constant function.
For (1), fix an input x ∈ X d . Suppose without loss of generality that f (x) = 1 (the arguments for f (x) = 0 are symmetric) so that f
We will show that if y ∈ {0, 1} d is a counterfactual for 1 d then there exists a counterfactual x ∈ X d for x satisfying ∆(x, x ) = ∆(y, 1 d ) and likewise if there is a counterfactual x for x then there is a counterfactual y for 1 d satisfying the same ∆(x, x ) = ∆(y, 1 d ). It then follows that ∆ f (x) = ∆ fx(1 d ) and also
which shows that x ↓ y ∈ X d is a counterfactual for x. Moreover, by definition, ∆(x ↓ y, x) = ∆(y, 1 d ).
On the other hand, suppose x ∈ X d is a counterfactual for x. Let y ∈ {0, 1} d be the instance defined by
by monotonicity. Hence, y is a counterfactual for 1 d and again we have ∆(x ↓ y, x) = ∆(y, 1 d ).
For (2), let y ∈ {0, 1} d be an instance satisfying S fx (y) = S(f x ). Then f x (y) = f (x ↑↓ y). In particular,
as desired.
C.1. Optimality of Theorem 3.5
We prove the following (slightly more general and formal) version of Theorem 1.4.
Theorem C.1. Fix any constant c < 1 and success probability ε > 0. For any algorithm A, and S, d, ∆ ∈ N such that S ≤ d and ∆ ≤ S c , there is a monotone model f : {0, 1} d → {0, 1} with S(f ) ≤ S and instance x with ∆ f (x ) = ∆ such that A must make q = S Ω(∆) + Ω(log d)
queries to find a single optimal counterfactual for x with success probability ε.
We'll allow the algorithm A to use randomness. In order to give lower bounds against randomized algorithms, we'll use the easy direction of Yao's Lemma.
Lemma C.2 ( (Yao, 1977)). For any q ∈ N, let R q and D q be the set of all q-query randomized and deterministic algorithms respectively, and let I be the set all of possible pairs f : {0, 1} n → {0, 1} and x ∈ {0, 1} n (i.e. instances of the counterfactual problem).
For any distribution µ supported on I,
where error R (f, x ) is the probability that R does not return an optimal counterfactual for x , and error D (f, x ) = 1[D does not return an optimal counterfactual for x ].
First, we show that s Ω(∆) queries are necessary.
Lemma C.3. For any ∆, d, S, q ∈ N where S ≤ d, and A a q-query randomized algorithm, there exists some monotone function f : {0, 1} d → {0, 1} with S(f ) ≤ S and input x ∈ {0, 1} satisfying ∆ f (x ) = ∆ on which A successfully returns an optimal counterfactual for x with probability at most q+1 ( S ∆ )
.
Proof. We will apply Yao's Lemma: To apply it, we need to define a distribution over input instances (f , x ). That distribution is simple. With probability 1, x = (0, . . . , 0). Then, we sample a uniformly random z from the S ∆ elements of {0, 1} S with Hamming weight equal to ∆ and set f : {0, 1} d → {0, 1} as
First, we note that it is always true that S(f ) ≤ S. This is because f (x) only depends on the first S-coordinates of x, so flipping any of the other d -S coordinates cannot change f 's output. Second, we note that the input x being z concatenated with d -S many 0s satisfies f (x ) = f (x ) and |x -x | = ∆. Therefore, ∆ f (x ) ≤ ∆. Furthermore, x is the only counterfactual for x at distance ≤ ∆, and so the algorithm succeeds if and only if it outputs x .
Consider an arbitrary q-query deterministic algorithm A . By Yao's Lemma, it is sufficient to prove that the probability A outputs x given the random instance (f , x ) is at most q+1 ( S ∆ )
. As A is deterministic, the queries it makes and answer it outputs are a deterministic function of the answers to its previous queries. Let g : {0, 1} d → {0, 1} be defined as
We will consider one possible execution path of A , when f and g give the same answer on each query A makes. Specifically, the execution path of A when every query it makes is answered consistently with g. In that case, A will make (the deterministic) queries x (1) , . . . , x (q) . We compute
Pr[The first S coordinates of x (j) equal z] ≤ q S ∆ .
Lastly, if A follows the single execution path corresponding to every query it makes being answered consistently with g, it will output some answer x (g) . This answer is correct if and only if it equals x , which occurs with probability at most 1 ( S ∆ ) for any choice of x (g) . Therefore,
= Pr[A returns an optimal counterfactual, All queries consistent with g] + Pr[A returns an optimal counterfactual, Any query inconsistent with g]
The desired result follows from Yao's Lemma.
Next we show that log d queries are necessary. Lemma C.4. For any d, q ∈ N and A a q-query randomized algorithm, there exists a monotone model f : {0, 1} d → {0, 1} satisfying S(f ) = 1 and input x where ∆ f (x ) = 1 on which A successful returns an optimal counterfactual for x with probability at most 2 q d .
Proof. Once again, we will pick a distribution over input instances (f , x ) and apply Yao's Lemma. With probability 1, we set x = (0, . . . , 0). Then, we sample a uniformly random i ∈ [d] and set
First, we note that S(f ) = 1, as the f is only sensitive on the i th coordinate. Furthermore, the input that is 1 on the i th coordinate and 0 everywhere else is a counterfactual for x of distance 1. This is the only optimal counterfactual.
All that remains is to argue that any q-query deterministic algorithm fails to return an optimal counterfactual for x . A q-query deterministic algorithm can only output 2 q different answers. However, based on the choice of i, there are d unique choices for the optimal counterfactual. Therefore, the probability the algorithm can output the optimal counterfactual is at most 2 q d .
Proof of Theorem C.1. It's sufficient to show that q = max(S Ω(∆) , Ω(log d))
where we treat ε and c as constants. By Lemma C.3, we have that
Then, by Lemma C.4, 2 q d ≥ ε, and so q ≥ log(εd) = Ω(log d).
Recall that an algorithm for finding a counterfactual for x is local if its first query is x and every subsequent query differs from a previous query by exactly one feature.
Theorem C.5. For any local search algorithm A, d ∈ N, and ε > 0, there is a monotone model f : {0, 1} d → {0, 1} with S(f ) = 1 and an instance x with ∆ f (x ) such that A must make q ≥ εd queries in order to find a single optimal counterfactual for x .
Proof. As in the proof of Lemma C.4, we apply Yao's Lemma with the distribution with x = (0, . . . , 0) with probability 1 and f (x) = x i where i ∈ [d] is chosen uniformly at random. Once again, S(f ) = 1 as f is only sensitive on the i th and there is a counterfactual from x of distance 1.
Since we are applying Yao's Lemma, it is sufficient to reason about deterministic local algorithms. A be a q-query local and deterministic algorithm. We will consider one execution path of A , namely that in which all its queries return 0. In that case, it will make the deterministic queries x (1) , . . . , x (q) . As A is local, the queries x (1) , . . . , x (q) must all be adjacent, and since x (1) = (0, . . . , 0), the number of coordinates j ∈ [d] on which x (t) j = 1 for some t ∈ [q] is at most q -1. The probability that f (x (t) ) = 1 for some t ∈ [q] is the probability that f (x (t) ) i = 1 for some t ∈ [q] which is at most q-1 d . Therefore A follows a single execution path with probability at least 1 -q-1 d . At the end of that execution path, it outputs a single "guess" counterfactual y. However, y is an optimal counterfactual for x only if y i = 1 and y j = 0 for all j = i, which can occur with probability at most 1 d for any single y. Therefore, the probability A outputs a correct counterfactual is at most
Pr[y is an optimal counterfactual for x ] + Pr[A does not output y] ≤
By applying Yao's Lemma, we conclude that any randomized q-query local algorithm succeeds in finding an optimal counterfactual with probability at most q d . Therefore, to succeed with probability ε, we must have q ≥ εd.
x 1
x The IDT operations allow one to construct the dotted path without constructing the entire tree. Each triangular block corresponds to the subtree exhaustively querying all the features in a certificate of a restriction of f . The depth of each block is C(f ) O(1) , the number of features in a certificate of f . The total number of blocks intersecting any root-to-leaf path is at most C(f ) O(1) and so the overall depth of the IDT is at most C(f ) O(1) .
Throughout we write "with high probability" or w.h.p. to indicate probability at least 1 -1/poly(d).
Note that the term "query" here is being used in two separate ways. A variable being "queried" on a path simply means that variable appears as an internal node on that path. The IDT itself has "query access" to f meaning it may query the value of f (x) for various x in its implementation.