function minimalSufficientFactors(\(y\) , \(\tau \) )

sorted_factors = \(\mathsf {topological\_sort}(\mathcal {C}, \preceq )\) 
cands = []
\(c\)  in sorted_factors
\(\exists (c^{\prime }, \_) \in \mbox{ cands }: c^{\prime }\preceq c\) 
continue
ps = probSufficiency(\(c\) , \(y\) )
ps \(\ge \tau \) 
cands.append(\(c\) , ps)
cum_pn=probNecessity(\(\lbrace c|(c, \_) \in \mbox{cands}\rbrace , y\) , True)
return cands, cum_pn

Encoding Existing Measures
Explanatory measures can be shown to play a central role in many seemingly unrelated XAI tools, albeit under different assumptions about the basis tuple \(\mathcal {B}\) . In this section, we relate our framework to a number of existing methods.
Feature attributions.
Several popular feature attribution algorithms are based on Shapley values [1]}, which decompose the predictions of any target function as a sum of weights over \(d\)  input features:
\( f(\mathbf {x}_i) = \phi _0 + \sum _{j=1}^{d}\phi _j,\) 
where \(\phi _0\)  represents a baseline expectation and \(\phi _j\)  the weight assigned to \(X_j\)  at point \(\mathbf {x}_i\) . Let \(v: 2^d \mapsto \mathbb {R}\)  be a value function such that \(v(S)\)  is the payoff associated with feature subset \(S \subseteq [d]\)  and \(v(\lbrace \emptyset \rbrace ) = 0\) . Define the complement \(R = [d] \backslash S\)  such that we may rewrite any \(\mathbf {x}_i\)  as a pair of subvectors, \((\mathbf {x}_i^S, \mathbf {x}_i^R)\) . Payoffs are given by:
\(v(S) = \mathop {\mathbb {E}}[f(\mathbf {x}_i^S, \mathbf {X}^R)],\) 
although this introduces some ambiguity regarding the reference distribution for \(\mathbf {X}^R\)  (more on this below). The Shapley value \(\phi _j\)  is then \(j\) 's average marginal contribution to all subsets that exclude it:
\( \phi _j = \sum _{S \subseteq [d] \backslash \lbrace j\rbrace } \frac{|S|!(d - |S| - 1)!}{d!} v(S \cup \lbrace j\rbrace ) - v(S).\) 
It can be shown that this is the unique solution to the attribution problem that satisfies certain desirable properties, including efficiency, linearity, sensitivity, and symmetry.
Reformulating this in our framework, we find that the value function \(v\)  is a sufficiency measure. To see this, let each \(\mathbf {z} \sim \mathcal {D}\)  be a sample in which a random subset of variables \(S\)  are held at their original values, while remaining features \(R\)  are drawn from a fixed distribution \(\mathcal {D}(\cdot |S)\) .The diversity of Shapley value algorithms is largely due to variation in how this distribution is defined. Popular choices include the marginal \(P(\mathbf {X}^R)\)  [2]}; conditional \(P(\mathbf {X}^R|\mathbf {x}^S)\)  [3]}; and interventional \(P(\mathbf {X}^R|do(\mathbf {x}^S))\)  [4]} distributions.
Proposition 1 
Let \(c_S(\mathbf {z}) = 1\)  iff \(\mathbf {x} \subseteq \mathbf {z}\)  was constructed by holding \(\mathbf {x}^S\)  fixed and sampling \(\mathbf {X}^R\)  according to \(\mathcal {D}(\cdot |S)\) . Then \(v(S) = PS(c_S, y)\) .

Thus, the Shapley value \(\phi _j\)  measures \(X_j\) 's average marginal increase to the sufficiency of a random feature subset. The advantage of our method is that, by focusing on particular subsets instead of weighting them all equally, we disregard irrelevant permutations and home in on just those that meet a \(\tau \) -minimality criterion. [5]} observe that, “since there is no standard procedure for converting Shapley values into a statement about a model’s behavior, developers rely on their own mental model of what the values represent” (p. 8). By contrast, necessary and sufficient factors are more transparent and informative, offering a direct path to what Shapley values crudely summarize.

Rule lists.
Rule lists are sequences of if-then statements that describe a hyperrectangle in feature space, creating partitions that can be visualized as decision or regression trees. Rule lists have long been popular in XAI. While early work in this area tended to focus on global methods [6]}, [7]}, more recent efforts have prioritized local explanation tasks [8]}, [9]}.
We focus in particular on the Anchors algorithm [10]}, which learns a set of Boolean conditions \(A\)  (the eponymous “anchors”) such that \(A(\mathbf {x}_i) = 1\)  and
\( P_{\mathcal {D}_{(\mathbf {x}|A)}}(f(\mathbf {x}_i) = f(\mathbf {x})) \ge \tau .\) 
The lhs of Eq. REF  is termed the precision, prec(\(A\) ), and probability is taken over a synthetic distribution in which the conditions in \(A\)  hold while other features are perturbed. Once \(\tau \)  is fixed, the goal is to maximize coverage, formally defined as \({E}[A(\mathbf {x}) = 1]\) , i.e. the proportion of datapoints to which the anchor applies.
The formal similarities between Eq. REF  and Def. REF  are immediately apparent, and the authors themselves acknowledge that Anchors are intended to provide “sufficient conditions” for model predictions.
Proposition 2 
Let \(c_A(\mathbf {z}) = 1\)  iff \(A(\mathbf {x}) = 1\) . Then \(\text{prec}(A) = PS(c_A, y)\) .

While Anchors outputs just a single explanation, our method generates a ranked list of candidates, thereby offering a more comprehensive view of model behavior. Moreover, our necessity measure adds another dimension of explanatory information entirely lacking in Anchors.

Counterfactuals.
Counterfactual explanations identify one or several nearest neighbors with different outcomes, e.g. all datapoints \(\mathbf {x}\)  within an \(\epsilon \) -ball of \(\mathbf {x}_i\)  such that labels \(f(\mathbf {x})\)  and \(f(\mathbf {x}_i)\)  differ (for classification) or \(f(\mathbf {x}) > f(\mathbf {x}_i) + \delta \)  (for regression).The term “counterfactual” is used in XAI to refer to any point with an alternative outcome, whereas in the causal literature it denotes a space characterized by incompatible conditioning events. We generally intend the former unless explicitly stated otherwise. The optimization problem is:
\( \mathbf {x}^* = \operatornamewithlimits{argmin}_{\mathbf {x}\in \text{CF}(\mathbf {x}_i)} ~cost(\mathbf {x}_i, \mathbf {x}),\) 
where \(\text{CF}(\mathbf {x}_i)\)  denotes a counterfactual space such that \(f(\mathbf {x}_i) \ne f(\mathbf {x})\)  and \(cost\)  is a user-supplied cost function, typically equated with some distance measure. [11]} recommend using generative adversarial networks to solve Eq. REF , while others have proposed alternatives designed to ensure that counterfactuals are coherent and actionable [12]}, [13]}, [14]}.
As with Shapley values, the variation in these proposals is reducible to the choice of context \(\mathcal {D}\) .
For counterfactuals, we rewrite the objective as a search for minimal perturbations sufficient to flip an outcome.
<TABLE>Proposition 3 
Let \(cost\)  be a function representing \(\preceq \) , and let \(c\)  be some factor spanning reference values. Then the counterfactual recourse objective is:
\(c^* = \operatornamewithlimits{argmin}_{c \in \mathcal {C}} ~cost(c) ~~\textrm {s.t.} ~PS(c, 1 - y) \ge \tau ,\) 
where \(\tau \)  denotes a decision threshold. Counterfactual outputs will then be any \(\mathbf {z} \sim \mathcal {D}\)  such that \(c^*(\mathbf {z}) = 1\) .


Probabilities of causation.
Our framework can describe [15]}'s aforementioned probabilities of causation, however in this case \(\mathcal {D}\)  must be constructed with care.
Proposition 4 
Consider the bivariate Boolean setting, as in Sect. . We have two counterfactual distributions: an input space \(\mathcal {I}\) , in which we observe \(x, y\)  but intervene to set \(X = x^{\prime }\) ; and a reference space \(\mathcal {R}\) , in which we observe \(x^{\prime }, y^{\prime }\)  but intervene to set \(X = x\) . Let \(\mathcal {D}\)  denote a uniform mixture over both spaces, and let auxiliary variable \(W\)  tag each sample with a label indicating whether it comes from the original (\(W = 1\) ) or contrastive (\(W = 0\) ) counterfactual space. Define \(c(\mathbf {z}) = w\) . Then we have \(\texttt {suf}(x, y) = PS(c, y)\)  and \(\texttt {nec}(x, y) = PS(1 - c, y^{\prime })\) .

In other words, we regard Pearl's notion of necessity as sufficiency of the negated factor for the alternative outcome. By contrast, [15]} has no analogue for our probability of necessity. This is true of any measure that defines sufficiency and necessity via inverse, rather than converse probabilities.
Whereas we can recover all four explanatory measures, corresponding to the classical definitions and their contrapositive forms, definitions that prohibit conditioning on outcomes are constrained.
Remark 3 We have assumed that factors and outcomes are Boolean throughout. Results can be extended to probabilistic versions of either or both variables, so long as \(c(\mathbf {Z})~ \rotatebox {90}{\XMLaddatt {origin}{c}\models }~Y~|~\mathbf {Z}\) . This conditional independence holds whenever \(\mathbf {W}~ \rotatebox {90}{\XMLaddatt {origin}{c}\models }~Y~|~\mathbf {X}\) , which is true for all cases we consider. However, we defend the Boolean assumption on the grounds that it is (a) well motivated by contrastivist epistemologies [17]}, [18]}, [19]} and (b) not especially restrictive, given that partitions of arbitrary complexity may be defined over \(\mathbf {Z}\)  and \(Y\) .


Experiments
<FIGURE>In this section, we demonstrate the use of LENS on a variety of tasks and compare results with popular XAI tools, using the basis configurations detailed in Table REF . A comprehensive discussion of experimental design, including datasets and pre-processing pipelines, is left to Appendix . Code for reproducing all results will be made publicly available.
Contexts.
We consider a range of contexts \(\mathcal {D}\)  in our experiments. For the input-to-reference (I2R) setting, we replace input values with reference values for feature subsets \(S\) ; for the reference-to-input (R2I) setting, we replace reference values with input values.
We use R2I for examining sufficiency/necessity of the original model prediction, and I2R for examining sufficiency/necessity of a contrastive model prediction.
We sample from the empirical data in all experiments, except in Sect. REF , where we assume access to a structural causal model (SCM).

Partial Orderings.
We consider two types of partial orderings in our experiments. The first, \(\preceq _{subset}\) , evaluates subset relationships. For instance, if \(c(\mathbf {z}) = {1}[\mathbf {x}[\mathsf {gender} = \text{``female''}]]\)  and \(c^{\prime }(\mathbf {z}) = {1}[\mathbf {x}[\mathsf {gender} = \text{``female''} \wedge \mathsf {age \ge 40}]]\) , then we say that \(c \preceq _{subset} c^{\prime }\) .
The second, \(c \preceq _{cost} c^{\prime } := c \preceq _{subset} c^{\prime } ~\wedge ~ cost(c) \le cost(c^{\prime })\) , adds the additional constraint that \(c\)  has a lower cost than \(c^{\prime }\) .
The cost function could be arbitrary.
Here, we consider distance measures over either the entire state space or just the intervention targets corresponding to \(c\) .

Feature Attributions
Feature attributions are often used to identify the top-\(k\)  most important features for a given model outcome [20]}. However, we argue that these feature sets may not be explanatory with respect to a given prediction.
To show this, we compute R2I and I2R sufficiency – i.e., \(PS(c, y)\)  and \(PS(1 - c, 1 - y)\) , respectively – for the top-\(k\)  most influential features (\(k \in [1,9]\) ) as identified by SHAP [2]} and LENS.
Fig. REF  shows results from the R2I setting for German credit [22]} and SpamAssassin datasets [23]}.
Our method attains higher \(PS\)  for all cardinalities. We repeat the experiment over 50 inputs, plotting means and 95% confidence intervals for all \(k\) .
Results indicate that our ranking procedure delivers more informative explanations than SHAP at any fixed degree of sparsity.
Results from the I2R setting are in Appendix .
<TABLE><TABLE><TABLE>
Rule Lists
Sentiment sensitivity analysis.
Next, we use LENS to study model weaknesses by considering minimal factors with high R2I and I2R sufficiency in text models. Our goal is to answer questions of the form, “What are words with/without which our model would output the original/opposite prediction for an input sentence?”
For this experiment, we train an LSTM network on the IMDB dataset for sentiment analysis [24]}.
If the model mislabels a sample, we investigate further; if it does not, we inspect the most explanatory factors to learn more about model behavior. For the purpose of this example, we only inspect sentences of length 10 or shorter.
We provide two examples below and
compare with Anchors (see Table REF ).
<TABLE>Consider our first example: read book forget movie is a sentence we would expect to receive a negative prediction, but our model classifies it as positive. Since we are investigating a positive prediction, our reference space is conditioned on a negative label. For this model, the classic UNK token receives a positive prediction. Thus we opt for an alternative, PLATE. Performing interventions on all possible combinations of words with our token, we find the conjunction of read, forget, and movie is a sufficient factor for a positive prediction (R2I). We also find that changing any of read, forget, or movie to PLATE would result in a negative prediction (I2R). Anchors, on the other hand, perturbs the data stochastically (see Appendix ), suggesting the conjunction read AND book.
Next, we investigate the sentence: you better choose paul verhoeven even watched. Since the label here is negative, we use the UNK token. We find that this prediction is brittle – a change of most single words would be sufficient to flip the outcome. Anchors, on the other hand, reports a conjunction including most words in the sentence. Taking the R2I view, we still find a more concise explanation: choose or even would be enough to attain a negative prediction. These brief examples illustrate how LENS may be used to find brittle predictions across samples, search for similarities between errors, or test for model reliance on sensitive attributes (e.g., gender pronouns).

Anchors comparison.
Anchors also includes a tabular variant, against which we compare LENS's performance in terms of R2I sufficiency. We present the results of this comparison in Fig. REF , and include additional comparisons in Appendix . We sample 100 inputs from the German dataset, and query both methods with \(\tau =0.9\)  using the classifier from Sect. REF . Anchors satisfies a PAC bound controlled by parameter \(\delta \) . At the default value \(\delta =0.1\) , Anchors fails
to meet the \(\tau \)  threshold on 14% of samples; LENS meets it on 100% of samples. This result accords with Thm. REF , and demonstrates the benefits of algorithmic soundness and completeness. Note that we also go beyond Anchors in providing multiple explanations instead of just a single output, as well as a cumulative probability measure with no analogue in their algorithm.
<FIGURE>
Counterfactuals
Adversarial examples: spam emails.
R2I sufficiency answers questions of the form, “What would be sufficient for the model to predict \(y\) ?”. This is particularly valuable in cases with unfavorable outcomes \(y^{\prime }\) . Inspired by adversarial interpretability approaches [25]}, [26]}, we train an MLP classifier on the SpamAssassin dataset and search for minimal factors sufficient to relabel a sample of spam emails as non-spam.
Our examples follow some patterns common to spam emails: received from unusual email addresses, includes suspicious keywords such as enlargement or advertisement in the subject line, etc. We identify minimal changes that will flip labels to non-spam with high probability. Options include altering the incoming email address to more common domains, and changing the subject or first sentences (see Tables REF ). These results can improve understanding of both a model's behavior and a dataset's properties.

Diverse counterfactuals.
Our explanatory measures can also be used to secure algorithmic recourse.
For this experiment, we benchmark against DiCE [27]}, which aims to provide diverse recourse options for any underlying prediction model. We illustrate the differences between our respective approaches on the Adult dataset [28]}, using an MLP and following the procedure from the original DiCE paper.
<FIGURE>According to DiCE, a diverse set of counterfactuals is one that differs in values assigned to features, and can thus produce a counterfactual set that includes different interventions on the same variables (e.g., CF1: \(\mathsf {age} = 91, \mathsf {occupation}\)  = “retired”; CF2: \(\mathsf {age} = 44, \mathsf {occupation}\)  = “teacher”).
Instead, we look at diversity of counterfactuals in terms of intervention targets, i.e. features changed (in this case, from input to reference values) and their effects.
We present minimal cost interventions that would lead to recourse for each feature set, but we summarize the set of paths to recourse via subsets of features changed.
Thus, DiCE provides answers of the form “Because you are not 91 and retired” or “Because you are not 44 and a teacher”; we answer “Because of your age and occupation”, and present the lowest cost intervention on these features sufficient to flip the prediction.
With this intuition in mind, we compare outputs given by DiCE and LENS for various inputs. For simplicity, we let all features vary independently.
We consider two metrics for comparison: (a) the mean cost of proposed factors,
and (b) the number of minimally valid candidates proposed, where a factor \(c\)  from a method \(M\)  is minimally valid iff for all \(c^{\prime }\)  proposed by \(M^{\prime }\) , \(\lnot {(c^{\prime } \prec _{cost} c)}\)  (i.e., \(M^{\prime }\)  does not report a factor better than \(c\) ).
We report results based on 50 randomly sampled inputs from the Adult dataset, where references are fixed by conditioning on the opposite prediction. The cost comparison results are shown in Fig. REF , where we find that LENS identifies lower cost factors for the vast majority of inputs.
Furthermore, DiCE finds no minimally valid candidates that LENS did not already account for.
Thus LENS emphasizes minimality and diversity of intervention targets, while still identifying low cost intervention values.

Causal vs. non-causal recourse.
When a user relies on XAI methods to plan interventions on real-world systems, causal relationships between predictors cannot be ignored. In the following example, we consider the DAG in Fig. REF , intended to represent dependencies in the German credit dataset. For illustrative purposes, we assume access to the structural equations of this data generating process. (There are various ways to extend our approach using only partial causal knowledge as input [29]}, [4]}.) We construct \(D\)  by sampling from the SCM under a series of different possible interventions. Table REF  describes an example of how using our framework with augmented causal knowledge can lead to different recourse options. Computing explanations under the assumption of feature independence results in factors that span a large part of the DAG depicted in Fig. REF . However, encoding structural relationships in \(D\) , we find that LENS assigns high explanatory value to nodes that appear early in the topological ordering.
This is because intervening on a single root factor may result in various downstream changes once effects are fully propagated.
<FIGURE>
Conclusion
We have presented a unified framework for XAI that foregrounds necessity and sufficiency, which we argue are the fundamental building blocks of successful explanations. We defined simple measures of both, and showed how they undergird various XAI methods. We illustrated illuminating connections between our explanatory measures and [15]}'s probabilities of causation, extending our scope to SCMs. We introduced a sound and complete algorithm for identifying minimally sufficient factors, and demonstrated our method on a range of tasks and datasets. Our approach prioritizes completeness over efficiency, suitable for settings of limited dimensionality. Yet our experiments demonstrate that empirical sampling on datasets of moderate dimensionality can produce compelling results. Datasets of higher dimensionality can be represented as lower dimensional abstractions favorable to explanations (see discussion in Appendix ). Future research will explore approximations that perform well on larger datasets, model-specific variants optimized for, e.g., convolutional neural networks, and developing a graphical user interface.

Acknowledgments
David Watson was supported in part by ONR grant N62909-19-1-2096.

Appendix

Proofs
Theorems
Proof of Theorem  REF
Theorem With oracle estimates of \(PS(c, y)\)  for all \(c \in \mathcal {C}\) , Alg. REF  is sound and complete.

Proof. Soundness and completeness follow directly from the specification of (P1) \(\mathcal {C}\)  and (P2) \(\preceq \)  in the algorithm's input \(\mathcal {B}\) , along with (P3) access to oracle estimates of \(PS(c, y)\)  for all \(c \in \mathcal {C}\) . Recall that the partial ordering must be complete and transitive, as noted in Sect. .
Assume that Alg. REF  generates a false positive, i.e. outputs some \(c\)  that is not \(\tau \) -minimal. Then by Def. REF , either the algorithm failed to properly evaluate \(PS(c, y)\) , thereby violating (P3), or failed to identify some \(c^{\prime }\)  such that (i) \(PS(c^{\prime }, y) \ge \tau \)  and (ii) \(c^{\prime } \prec c\) . (i) is impossible by (P3), and (ii) is impossible by (P2). Thus there can be no false positives.
Assume that Alg. REF  generates a false negative, i.e. fails to output some \(c\)  that is in fact \(\tau \) -minimal. By (P1), this \(c\)  cannot exist outside the finite set \(\mathcal {C}\) . Therefore there must be some \(c \in \mathcal {C}\)  for which either the algorithm failed to properly evaluate \(PS(c, y)\) , thereby violating (P3), or wrongly identified some \(c^{\prime }\)  such that (i) \(PS(c^{\prime }, y) \ge \tau \)  and (ii) \(c^{\prime } \prec c\) . Once again, (i) is impossible by (P3), and (ii) is impossible by (P2). Thus there can be no false negatives.

Proof of Theorem  REF
Theorem With sample estimates of \(\hat{PS}(c, y)\)  for all \(c \in \mathcal {C}\) , Alg. REF  is optimal, in the frequentist sense.

Proof. A testing procedure is uniformly most powerful (UMP) if it attains the lowest type II error \(\beta \)  of all tests with fixed type I error \(\alpha \) . Let \(\Theta _0, \Theta _1\)  denote a partition of the parameter space into null and alternative regions. The goal in frequentist inference is to test the null hypothesis \(H_0: \theta \in \Theta _0\)  against the alternative \(H_1: \theta \in \Theta _1\)  for some parameter \(\theta \) . Let \(\psi (X)\)  be a testing procedure of the form \({1}[T(X) \ge c_{\alpha }]\) , where \(X\)  denotes a finite sample, \(T(X)\)  is a test statistic, and \(c_{\alpha }\)  is the critical value. This latter parameter defines a rejection region such that test statistics integrate to \(\alpha \)  under \(H_0\) . We say that \(\psi (X)\)  is UMP iff, for any other test \(\psi ^{\prime }(X)\)  such that
\(\sup _{\theta \in \Theta _0} {E}_{\theta }[\psi ^{\prime }(X)] \le \alpha ,\) 

we have
\((\forall \theta \in \Theta _1) ~{E}_{\theta }[\psi ^{\prime }(X)] \le {E}_{\theta }[\psi (X)],\) 

where \({E}_{\theta \in \Theta _1}[\psi (X)]\)  denotes the power of the test to detect the true \(\theta \) , \(1 - \beta _{\psi }(\theta )\) . The UMP-optimality of Alg. REF  follows from the UMP-optimality of the binomial test (see [32]}, Ch. 3), which is used to decide between \(H_0: PS(c, y) < \tau \)  and \(H_1: PS(c, y) \ge \tau \)  on the basis of observed proportions \(\hat{PS}(c, y)\) , estimated from \(n\)  samples for all \(c \in \mathcal {C}\) . The proof now takes the same structure as that of Thm. REF , with (P3) replaced by (P\(3^{\prime }\) ): access to UMP estimates of \(PS(c, y)\) . False positives are no longer impossible but bounded at level \(\alpha \) ; false negatives are no longer impossible but occur with frequency \(\beta \) . Because no procedure can find more \(\tau \) -minimal factors for any fixed \(\alpha \) , Alg. REF  is UMP.

Propositions
Proof of Proposition  REF
Proposition Let \(c_S(\mathbf {z}) = 1\)  iff \(\mathbf {x} \subseteq \mathbf {z}\)  was constructed by holding \(\mathbf {x}^S\)  fixed and sampling \(\mathbf {X}^R\)  according to \(\mathcal {D}(\cdot |S)\) . Then \(v(S) = PS(c_S, y)\) .

As noted in the text, \(\mathcal {D}(\mathbf {x}|S)\)  may be defined in a variety of ways (e.g., via marginal, conditional, or interventional distributions). For any given choice, let \(c_S(\mathbf {z}) = 1\)  iff \(\mathbf {x}\)  is constructed by holding \(\mathbf {x}^S_i\)  fixed and sampling \(\mathbf {X}^R\)  according to \(\mathcal {D}(\mathbf {x}|S)\) . Since we assume binary \(Y\)  (or binarized, as discussed in ), we can rewrite Eq. REF  as a probability:
\(v(S) = P_{\mathcal {D}(\mathbf {x}|S)} (f(\mathbf {x}_i) = f(\mathbf {x})),\) 

where \(\mathbf {x}_i\)  denotes the input point. Since conditional sampling is equivalent to conditioning after sampling, this value function is equivalent to \(PS(c_S, y)\)  by Def. REF .

Proof of Proposition  REF
Proposition Let \(c_A(\mathbf {z}) = 1\)  iff \(A(\mathbf {x}) = 1\) . Then \(\text{prec}(A) = PS(c_A, y)\) .

The proof for this proposition is essentially identical, except in this case our conditioning event is \(A(\mathbf {x}) = 1\) . Let \(c_A = 1\)  iff \(A(\mathbf {x}) = 1\) . Precision prec(\(A\) ), given by the lhs of Eq. REF , is defined over a conditional distribution \(\mathcal {D}(\mathbf {x}|A)\) . Since conditional sampling is equivalent to conditioning after sampling, this probability reduces to \(PS(c_A, y)\) .

Proof of Proposition  REF
Proposition Let \(cost\)  be a function representing \(\preceq \) , and let \(c\)  be some factor spanning reference values. Then the counterfactual recourse objective is:
\(c^* = \operatornamewithlimits{argmin}_{c \in \mathcal {C}} ~cost(c) ~~\textrm {s.t.} ~PS(c, 1 - y) \ge \tau ,\) 
where \(\tau \)  denotes a decision threshold. Counterfactual outputs will then be any \(\mathbf {z} \sim \mathcal {D}\)  such that \(c^*(\mathbf {z}) = 1\) .

There are two closely related ways of expressing the counterfactual objective: as a search for optimal points, or optimal actions. We start with the latter interpretation, reframing actions as factors. We are only interested in solutions that flip the original outcome, and so we constrain the search to factors that meet an I2R sufficiency threshold, \(PS(c, 1-y_i) \ge \tau \) . Then the optimal action is attained by whatever factor (i) meets the sufficiency criterion and (ii) minimizes cost. Call this factor \(c^*\) . The optimal point is then any \(\mathbf {z}\)  such that \(c^*(\mathbf {z}) = 1\) .

Proof of Proposition  REF
Proposition Consider the bivariate Boolean setting, as in Sect. . We have two counterfactual distributions: an input space \(\mathcal {I}\) , in which we observe \(x, y\)  but intervene to set \(X = x^{\prime }\) ; and a reference space \(\mathcal {R}\) , in which we observe \(x^{\prime }, y^{\prime }\)  but intervene to set \(X = x\) . Let \(\mathcal {D}\)  denote a uniform mixture over both spaces, and let auxiliary variable \(W\)  tag each sample with a label indicating whether it comes from the original (\(W = 1\) ) or contrastive (\(W = 0\) ) counterfactual space. Define \(c(\mathbf {z}) = w\) . Then we have \(\texttt {suf}(x, y) = PS(c, y)\)  and \(\texttt {nec}(x, y) = PS(1 - c, y^{\prime })\) .

Recall from Sect.  that [15]} defines \(\texttt {suf}(x, y) := P(y_x|x^{\prime }, y^{\prime })\)  and \(\texttt {nec}(x, y) := P(y^{\prime }_{x^{\prime }}|x,y).\)  We may rewrite the former as \(P_{\mathcal {R}}(y)\) , where the reference space \(\mathcal {R}\)  denotes a counterfactual distribution conditioned on \(x^{\prime }, y^{\prime }, do(x)\) . Similarly, we may rewrite the latter as \(P_{\mathcal {I}}(y^{\prime })\) , where the input space \(\mathcal {I}\)  denotes a counterfactual distribution conditioned on \(x, y, do(x^{\prime })\) . Our context \(\mathcal {D}\)  is a uniform mixture over both spaces.
The key point here is that the auxiliary variable \(W\)  indicates whether samples are drawn from \(\mathcal {I}\)  or \(\mathcal {R}\) . Thus conditioning on different values of \(W\)  allows us to toggle between probabilities over the two spaces. Therefore, for \(c(\mathbf {z}) = w\) , we have \(\texttt {suf}(x, y) = PS(c, y)\)  and \(\texttt {nec}(x, y) = PS(1 - c, y^{\prime })\) .

Additional discussions of method
\(\tau \) -minimality and necessity
As a follow up to Remark REF  in Sect. REF , we expand here upon the relationship between \(\tau \)  and cumulative probabilities of necessity, which is similar to a precision-recall curve quantifying and qualifying errors in classification tasks. In this case, as we lower \(\tau \) , we allow more factors to be taken into account, thus covering more pathways towards a desired outcome in a cumulative sense. We provide an example of such a precision-recall curve in Fig. REF , using an R2I view of the German credit dataset. Different levels of cumulative necessity may be warranted for different tasks, depending on how important it is to survey multiple paths towards an outcome. Users can therefore adjust \(\tau \)  to accommodate desired levels of cumulative \(PN\)  over successive calls to LENS.
<FIGURE>
Enumeration, low-dimensional explanations, and abstraction

While our proposed theoretical framework is broad enough to accommodate approximation of \(PS\)  and sampling from any well-specified context \(\mathcal {D}\) , in our practical demonstration we focus on a full-enumeration based approach, and empirical values of all components. We manually apply all possible interventions under a basis \(\mathcal {B}\) . One criticism of this approach is that it is computationally infeasible in high dimensions, as the number of possible feature subsets is exponential in \(d\) . While we intend to work on statistical approximations of this approach that would be more favorable to higher dimensional settings in future work, we intentionally focused on lower-to-middle dimensional cases first.
As noted in multiple sections of [34]}, “Humans are adept at selecting one or two causes from a sometimes infinite number of causes to be the explanation.”
Various authors cited in [34]} emphasize that ideal explanations must be minimal, e.g., “ explanations that offer fewer causes and explanations that explain multiple observations are considered more believable and more valuable”, or “all things being equal, simpler explanations — those that cite fewer causes... are better explanations”.
Thus, we contend that higher-dimensional datasets are an obstacle not just computationally, but also semantically. Even if we could feasibly enumerate all \(\tau \) -minimal factors for some very large value of \(d\) , it is not clear that such explanations would be helpful to humans, who famously struggle to hold more than seven objects in short-term memory at any given time [36]}. One strategy in such cases is to use a low-dimensional representation of a high-dimensional dataset. Explanations can now be offered at a higher level of abstraction. For instance, in our SpamAssassins experiments, we started with a pure text example that can be represented via high-dimensional vectors (e.g., word embeddings).
However, we chose to pre-process the dataset and boil it down to its core elements: From and To email addresses, Subject line, First and Last sentences, etc. This way, we created a more abstract object and considered each segment as a potential intervention target, i.e. as candidate factors. We thus compressed a high-dimensional dataset into a 10-dimensional abstraction with only 10 targets of interventions. Similar strategies could be used in many cases, either through domain-knowledge or data-driven dimensionality reduction techniques.

Additional discussions of experimental results
Data pre-processing and model training
German Credit Risk. We first download the dataset from KaggleSee https://www.kaggle.com/kabure/german-credit-data-with-risk?select=german_credit_data.csv, which is a slight modification of the UCI version [22]}. We follow the pre-processing steps from a Kaggle tutorial.See https://www.kaggle.com/vigneshj6/german-credit-data-analysis-python. In particular, we map the categorical string variables in the dataset (Savings accounts, Checking account, Sex, Housing, Purpose and the outcome Risk) to numeric encodings, and mean-impute values missing values for Savings accounts and Checking account. We then train an Extra-Tree classifier [38]} using scikit-learn, with random state 0 and max depth 15. All other hyperparameters are at their default values. The model achieves a 71% accuracy.
German Credit Risk - Causal. We assume a partial ordering over the features in the dataset, as described in Fig. REF . We use this DAG to fit a structural causal model (SCM) based on the original data. In particular, we fit linear regressions for every continuous variable and a random forest classifier for every categorical variable. When sampling from \(\mathcal {D}\) , we let variables remain at their original values unless either (a) they are directly intervened on, or (b) one of their ancestors was intervened on. In the latter case, changes are propagated via the structural equations. We add stochasticity via Gaussian noise for continuous outcomes, with variance given by each model's residual mean squared error. For categorical variables, we perform multinomial sampling over predicted class probabilities. We use the same \(f\)  model as for the non-causal German credit risk description above.

SpamAssassins. The original spam assassins dataset comes in the form of raw, multi-sentence emails captured on the Apache SpamAssassins project, 2003-2015.See https://spamassassin.apache.org/old/credits.html. To utilize our method for use with this dataset, we segmented the emails to the following “features”: From, represents the from address line; To, represented the to address line; Subject, represents the subject line of the email; Urls, any URLs found in the email; Emails, any email address found in the email; First Sentence, represents the first sentence in the body of the email; Second Sentence, represents the second sentence in the body of the email; Penult Sentence, represents the penultimate sentence in the body of the email; Last Sentence, represents the last sentence in the body of the email. We use the original outcome label from the original dataset (indicated by which folder the different emails were saved). Once we obtain a dataset in the form above, we continue to pre-process by lower casing all characters, only keeping words or digits, clearing most punctuation (except for `-' and `_'), and removing stopwords based on nltk's provided list [39]}. Finally, we convert all clean strings to their mean 50-dim GloVe vector representation [40]}. We train a standard MLP classifier using scikit-learn, with random state 1, max iteration 300, and all other hyperparameters set to their default values. See https://scikit-learn.org/stable/modules/generated/sklearn.neural_network.MLPClassifier.html This model attains an accuracy of 98.3%.
IMDB. We follow the pre-processing and modeling steps taken in a standard tutorial on LSTM training for sentiment prediction with the IMDB dataset.See https://github.com/hansmichaels/sentiment-analysis-IMDB-Review-using-LSTM/blob/master/sentiment_analysis.py.ipynb. The CSV is included in the repository named above, and can be additionally downloaded from Kaggle or ai.standford.See https://www.kaggle.com/lakshmi25npathi/imdb-dataset-of-50k-movie-reviews or http://ai.stanford.edu/~amaas/data/sentiment/. In particular, these include removal of HTML-tags, non-alphabetical characters, and stopwords based on the the list provided in the ntlk package, as well as changing all alphabetical characters to lower-case. We then train a standard LSTM model, with 32 as the embedding dimension and 64 as the dimensionality of the output space of the LSTM layer, and an additional dense layer with output size 1. We use the sigmoid activation function, binary cross-entropy loss, and optimize with Adam [41]}. All other hyperparameters are set to their default values as specified by Keras.See https://keras.io The model achieves an accuracy of 87.03%.
<TABLE>Adult Income. We obtain the adult income dataset via DiCE's implementation.See https://github.com/interpretml/DiCE. to maximize comparability of our methods DiCE in turn followed the pre-processing steps of Haojun Zhu 2016.See https://rpubs.com/H_Zhu/235617. We further use a pretrained MLP model trained by DiCE for our recourse comparison, which is a single layer, non-linear model trained with TensorFlow, and stored in their repository as `adult.h5'.
Tasks
Comparison with attributions. For completeness, we also include here comparison of cumulative attribution scores per cardinality with probabilities of sufficiency as defined in LENS for I2R view, see Fig. REF .
<FIGURE>Sentiment sensitivity analysis. We identify sentences in the original IMDB dataset that are up to 10 words long. Out of those, for the first example we only look at wrongly predicted sentences to identify a suitable example. For the other example, we simply consider a random example from the 10-word maximum length examples. We noted that Anchors uses stochastic word-level perturbations for this setting. This leads them to identify explanations of higher cardinality for some sentences, which include elements that are not strictly necessary. In other words, their outputs are not minimal, as required for descriptions of “actual causes” by [42]}, [43]}.
Comparison with anchors. To complete the picture of our comparison with Anchors on the German Credit Risk dataset, we provide here additional results. In the main text, we included a comparison of Anchors's single output precision against the mean degree of sufficiency attained by our multiple suggestions per input. We sample 100 different inputs from the German Credit dataset and repeat this same comparison. Here we additionally consider the minimum and maximum probability of sufficiency \(PS(c, y)\)  attained by LENS against Anchors. Note that even when considering minimum \(PS\)  suggestions by LENS, i.e. our worst output, the method shows more consistent performance. We qualify this discussion by noting that, by setting Anchors's \(\delta \)  hyperparameter to a lower value, one could possibly get comparable results to ours. We still see value in emphasizing this difference, however, as [10]} do not discuss this parameter in detail in either their original article or subsequent notebook guides. They use default settings in their own experiments, and we expect most practitioners will do the same.
<FIGURE>Recourse: DiCE comparison
First, we provide a single illustrative example of the lack of diversity in intervention targets we identify in DiCE's output. Let us consider one example, shown in Table REF . While DiCE outputs are diverse in terms of values and target combinations, they tend to have great overlap in intervention targets. For instance, Age and Education appear in almost all of them. Our method would focus on minimal paths to recourse that would involve different combinations of features.
<FIGURE>Next, we also provide additional results from our cost comparison with DiCE's output in Fig. REF . While in the main text we include a comparison of our mean cost output against DiCE's, here we additionally include a comparison of min and max cost of the methods' respective outputs. We see that even when considering minimum and maximum cost, our method tends to suggest better cost recourse options. In particular, note that all of DiCE's outputs are already subsets of LENS's two top suggestions. The higher costs incurred by LENS for the next two lines are a reflection of this fact: due to \(\tau \) -minimality, LENS is forced to find other intervention that are no longer supersets of options already listed above.
references
