Sufficient and Necessary Explanations (and What Lies in Between)

## Abstract

Abstract As complex machine learning models continue to find applications in high-stakes decision making scenarios, it is crucial that we can explain and understand their predictions. Post-hoc explanation methods provide useful insights by identifying important features in an input x 𝑥 x italic_x with respect to the model output f ⁢ ( 𝐱 ) 𝑓 𝐱 f({\bf x}) italic_f ( bold_x ) . In this work we formalize and study two precise notions of feature importance for general machine learning models: sufficiency and necessity . We demonstrate how these two types of explanations, albeit intuitive and simple, can fall short in providing a complete picture of which features a model finds important. To this end, we propose a unified notion of importance that circumvents these limitations by exploring a continuum along a necessity-sufficiency axis. Our unified notion, we show, has strong ties to other popular definitions of feature importance, like those based on conditional independence and game-theoretic quantities like Shapley values. Crucially, we demonstrate how a unified perspective allows us to detect important features that could be missed by either of the previous approaches alone.

## 1 Introduction

Over recent years, modern machine learning (ML) models, mostly deep learning based, have achieved impressive results across several complex domains. We now have models that can solve difficult image classification, inpainting, and segmentation problems, perform accurate text and sentiment analysis, predict the three-dimensional conformation of proteins, and more \parencitelecun2015deep, wang2023nature. Despite their success, the rapid integration of these models into society requires caution due to their complexity and unintelligibility \parenciteexecutiveorder2023. Modern ML systems are, by and large black-boxes, consisting of millions of parameters and non-linearities that obscure their prediction-making mechanisms from users, developers, and auditors. This lack of clarity raises concerns about explainability, transparency, and accountability \parencitezednik2021solving, tomsett2018interpretable. Thus, understanding how these models work is essential for their safe deployment.

The lack of explainability has spurred research efforts in eXplainable AI (XAI), with a major focus on developing post-hoc methods to explain black-box model predictions, especially at a *local* level. For a model $f$ and input ${\bf x}\in{\mathbb{R}}^{d}$, these methods aim to identify which features in ${\bf x}$ are *important* for the model’s prediction, $f({\bf x})$. They do so by estimating a notion of importance for each feature (or groups) which allows for a ranking of importance. Popular methods include CAM \parencitezhou2016learning, LIME \parenciteribeiro2016should, gradient-based approaches \parenciteselvaraju2017grad, shrikumar2017learning, jiang2021layercam, rate-distortion techniques \parencitekolek2021cartoon, kolek2022rate, Shapley value-based explanations \parencitechen2018shapley, teneggi2022fast, mosca2022shapbased, perturbation-based methods \parencitefong2017interpretable, fong2019understanding, dabkowski2017real, among others \parencitechen2018learning, yoon2018invase, jethani2021have, wang2021probabilistic, ribeiro2018anchors. However, many of these approaches lack rigor, as the meaning of their computed scores is often ambiguous. For example, it’s not always clear what large or negative gradients signify or what high Shapley values reveal about feature importance. To address these concerns, other research has focused on developing explanation methods based on logic-based definitions \parenciteignatiev2020contrastive, darwiche2020reasons, darwiche2022computation, shih2018symbolic, conditional hypothesis testing [teneggi2023shap, tansey2022holdout], among formal notions. While these methods are a step towards rigor, they have drawbacks, including reliance on complex automated reasoners and limited ability to communicate their results in an understandable way for human decision-makers.

In this work, we advance XAI research by formalizing rigorous mathematical definitions and approaches, grounded in the intuitive concepts of *sufficiency* and *necessity*, to explain complex ML models. We begin by illustrating how sufficient and necessary explanations offer valuable, albeit incomplete, insights into feature importance. To address this issue, we propose and study a more general unified framework for explaining models. We offer two novel perspectives on our framework through the lens of conditional independence and Shapley values, and crucially, show how it reveals new insights into feature importance.

### 1.1 Summary of our Contributions

We study two key notions of importance: sufficiency and necessity, both which evaluate the importance of a set of features in ${\bf x}$, with respect to the prediction $f({\bf x})$, of an ML model. A sufficient set of features preserves the model’s output, while a necessary set, when removed or perturbed, renders the output uninformative. Although sufficiency and necessity appear complementary, their precise relationship remains unclear. When do sufficient and necessary subsets overlap or differ? When should we prioritize one over the other, or seek features that are both necessary and sufficient? To address these questions, we analyze sufficiency and necessity and propose a *unification* of both. Our contributions are summarized as follows:

- 1.
We formalize precise mathematical definitions of sufficient and necessary model explanations for arbitrary ML predictors.
- 2.
We propose a unified approach that combines sufficiency and necessity, analyzing their relationships and exploring exploring when and how they align or differ. Furthermore, we reveal its strong ties to conditional independence and Shapley values, a game-theoretic measure of feature importance.
- 3.
Through experiments of increasing complexity, illustrate how our unified perspective can reveal new, important, and more complete insights into feature importance.

## 2 Sufficiency and Necessity

Notation. We use boldface uppercase letters to denote random vectors (e.g., ${\bf X}$) and lowercase letters for their values (e.g., ${\bf x}$). For a subset $S\subseteq[d]\coloneqq\{1,\dots,d\}$, we denote its cardinality by $|S|$ and its complement ${S_{c}}=[d]\setminus S$. Subscripts index features; e.g., the vector ${\bf x}_{S}$ represents the restriction of ${\bf x}$ to the entries indexed by $S$.

Setting. We consider a supervised learning setting with an unknown distribution ${\mathcal{D}}$ over ${\mathcal{X}}\times{\mathcal{Y}}$, where ${\mathcal{X}}\subseteq\mathbb{R}^{d}$ is a $d$-dimensional feature space and ${\mathcal{Y}}\subseteq\mathbb{R}$ is the label space. We assume access to a predictor $f:{\mathcal{X}}\mapsto{\mathcal{Y}}$ that was trained on samples from ${\mathcal{D}}$. For an input $\mathbf{x}=(x_{1},\dots,x_{d})\in\mathbb{R}^{d}$, our goal is to identify the important features of $\mathbf{x}$ for the prediction $f(\mathbf{x})$. To define feature importance precisely, we use the *average restricted prediction*,

$$ $\displaystyle f_{S}(\mathbf{x})=\underset{\mathbf{X}_{\mathcal{S}}\sim\mathcal {V}_{\mathcal{S}}}{\mathbb{E}}[f(\mathbf{x}_{S},\mathbf{X}_{\mathcal{S}})]$ (1) $$

where $\mathbf{x}_{S}$ is fixed, and $\mathbf{X}_{\mathcal{S}}$ is a random vector drawn from an arbitrary reference distribution $\mathcal{V}_{\mathcal{S}}$. This strategy, popularized in \parencitelundberg2017unified, lundberg2020local, allows us to query a predictor $f$ that accepts only $d$-dimensional inputs and analyze its behavior when specific sets of features in $\mathbf{x}$ are retained or removed.

### 2.1 Definitions

We introduce two intuitive notions to quantify the importance of a subset $S$ for a prediction $f({\bf x})$. For a model $f$, we begin by evaluating its baseline behavior over an arbitrary reference distribution ${\mathcal{V}}$: $f_{\emptyset}({\bf x})={{\mathbb{E}}}[f({\bf X}_{[d]})]$. Then, for a sample ${\bf x}$ and its prediction $f({\bf x})$, we can pose two simple questions:

*Which set of features, $S$, satisfies $f_{S}({\bf x})\approx f({\bf x})$ or $f_{{S_{c}}}({\bf x})\approx f_{\emptyset}({\bf x})$*?

These questions explores the sufficiency and necessity of subset $S$, which we define formally in the following definitions

###### Definition 2.1 (Sufficiency) .

Let $\epsilon\geq 0$ and let $\rho:{\mathbb{R}}\times{\mathbb{R}}\mapsto{\mathbb{R}}$ be a metric on ${\mathbb{R}}$. A subset $S\subseteq[d]$ is $\epsilon$-sufficient with respect to a distribution ${\mathcal{V}}$ for $f$ at ${\bf x}$ if

$$ $\Delta^{{\text{suf}}}_{\mathcal{V}}(S,f,{\bf x})\triangleq\rho(f({\bf x}),f_{S }({\bf x}))\leq\epsilon.$ (2) $$

Furthermore, $S$ is $\epsilon$-super sufficient if all supersets $\widetilde{S}\supseteq S$ are $\epsilon$-sufficient.

This notion of sufficiency is straightforward: a subset $S$ is $\epsilon$-sufficient with respect to a reference distribution ${\mathcal{V}}$ if, with ${\bf x}_{S}$ fixed, the average restricted prediction $f_{S}({\bf x})$ is within $\epsilon$ from the original prediction $f({\bf x})$. This is further strengthened by super-sufficiency: a subset $S$ is $\epsilon$-super sufficient if $\rho(f({\bf x}),f_{S}({\bf x}))\leq\epsilon$ and, for any superset $\widetilde{S}$ of $S$, $\rho(f({\bf x}),f_{\widetilde{S}}({\bf x}))\leq\epsilon$. This simply means including more features in $S$ still keeps $f_{S}({\bf x})$ $\epsilon$ close to $f({\bf x})$. To find a small sufficient subset $S$ of small cardinality $\tau>0$, we can solve the following optimization problem:
{argmini*}|l|[2]
S ⊆[d]
Δ^suf_V(S, f, x)  subject to  |S| ≤τ.
We will refer to this problem as the *sufficiency problem*, or (2.1). Using analogous ideas, we also define necessity and formulate an optimization problem to find small necessary subsets.

###### Definition 2.2 (Necessity) .

Let $\epsilon\geq 0$ and denote $\rho:{\mathbb{R}}\times{\mathbb{R}}\mapsto{\mathbb{R}}$ to be metric on ${\mathbb{R}}$. A subset $S\subseteq[d]$ is $\epsilon$-necessary with respect to a distribution ${\mathcal{V}}$ for $f$ at ${\bf x}$ if

$$ $\Delta^{{\text{nec}}}_{\mathcal{V}}(S,f,{\bf x})\triangleq\rho(f_{{S_{c}}}({ \bf x}),f_{\emptyset}({\bf x}))\leq\epsilon.$ (2) $$

Furthermore, $S$ is $\epsilon$-super necessary if all supersets $\widetilde{S}\supseteq S$ are $\epsilon$-necessary.

Here, a subset $S$ is $\epsilon$-necessary if marginalizing out the features in $S$ with respect to the distribution ${\mathcal{V}}_{S}$, results in an average restricted prediction $f_{{S_{c}}}({\bf x})$ that is $\epsilon$ close to $f_{\emptyset}({\bf x})$ – the average baseline prediction of $f$ over ${\mathcal{V}}_{[d]}$. Furthermore, $S$ is $\epsilon$-super necessary if $\rho(f_{S}({\bf x}),f({\bf x}))\leq\epsilon$ and any superset $\widetilde{S}$ of $S$ is $\epsilon$-necessary. To identify a $\epsilon$-necessary subset $S$ of small cardinality $\tau>0$, one can solve the following optimization problem, which we refer to as the *necessity* problem or (2.2).
{argmini*}|l|[2]
S ⊆[d]
Δ^nec_V(S, f, x)  subject to  |S| ≤τ
.

###### Definition 2.1 (Sufficiency) .

###### Definition 2.2 (Necessity) .

## 3 Related Work

Notions of sufficiency, necessity, the duality between the two, and their connections with other feature attribution methods have been studied to varying degrees in XAI research. We comment on the main related works in this section.

Sufficiency. The notion of sufficient features has gained significant attention in recent research. \textciteshih2018symbolic explore a symbolic approach to explain Bayesian network classifiers and introduce prime implicant explanations, which are minimal subsets $S$ that make features in the complement irrelevant to the prediction $f({\bf x})$. For models represented by a finite set of first-order logic (FOL) sentences, \textciteignatiev2020contrastive refer to prime implicants as abductive explanations (AXp’s). For classifiers defined by propositional formulas and inputs with discrete features, \textcitedarwiche2020reasons refer to prime implicants as sufficient reasons and define a complete reason to be the disjunction of all sufficient reasons. They present efficient algorithms, leveraging Boolean circuits, to compute sufficient and complete reasons and demonstrate their use in identifying classifier dependence on protected features that should not inform decisions. For more complex models, \textciteribeiro2018anchors propose high-precision probabilistic explanations called anchors, which represent local, sufficient conditions. For ${\bf x}$ positively classified by $f$, \textcitewang2021probabilistic propose a greedy approach to solve (2.1) while the preservation method by \textcitefong2017interpretable relaxes $S$ to $[0,1]^{d}$.

Necessity. There has also been significant focus on identifying necessary features – those that, when altered, lead to a change in the prediction $f({\bf x})$. For models expressible by FOL sentences, \textciteignatiev2019relating define prime implicates as the minimal subsets that when changed, modify the prediction $f({\bf x})$ and relate these to adversarial examples. For Boolean models predicting on samples ${\bf x}$ with discrete features, \textciteignatiev2020contrastive and \parencitedarwiche2020reasons refer to prime implicates as contrastive explanations (CXp’s) and necessary reasons, respectively. Beyond boolean functions, for ${\bf x}$ positively classified by a classifier $f$, \textcitefong2019understanding relax $S$ to $[0,1]^{d}$ and propose the deletion method to approximately solve (2.2).

Duality Between Sufficiency and Necessity. \textcitedabkowski2017real characterize the preservation and deletion methods as discovering the *smallest sufficient* and *destroying region* (SSR and SDR). They propose combining the two but do not explore how solutions to this approach may differ from individual SSR and SDR solutions. \textciteignatiev2020contrastive show that AXp’s and CXp’s are minimal hitting sets of another by using a hitting set duality result between minimal unsatisfiable and correction subsets. The result enables the identification of AXp’s from CXp’s and vice versa.

Sufficiency, Necessity, and General Feature Attribution Methods. Precise connections between sufficiency, necessity, and other popular feature attribution methods (such as Shapley values \parenciteshapley1951notes, chen2018shapley, lundberg2017unified) remains unclear. To our knowledge, \textcitecovert2021explaining provide the only work examining these approaches \parencitefong2017interpretable, fong2019understanding, dabkowski2017real in the context of general removal-based methods, i.e., methods that remove certain input features to evaluate different notions of importance. The work of \textcitewatson21a is also relevant to our work, as it formalizes a connection between notions of sufficiency and Shapley values. With the specific payoff function (^1^11Payoff functions are an instrumental tool in game-theoretic approaches. See further Section 5.2 for further details.) defined as $v(S)=\mathbb{E}[f(\mathbf{x}_{S},\mathbf{X}_{{S_{c}}})]$, they show how each summand in the Shapley value measures the sufficiency of feature $i$ to a particular subset.

## 4 Unifying Sufficiency and Necessity

Given a model $f$, sample ${\bf x}$, and reference distribution ${\mathcal{V}}$, we can identify a small set of important features $S$ by solving either (2.1) or (2.2) (^2^22Solving (2.1) or (2.2) is NP-hard for general non-convex functions $f$. We do not concern ourselves with the computational efficiency of these problems as there exist tractable relaxations \parencitekolek2021cartoon, kolek2022rate.).
While both methods are popular \parencitekolek2021cartoon, kolek2022rate, fong2017interpretable, bhalla2023verifiable, yoon2018invase, simply identifying a small sufficient or necessary subset may not provide a complete picture of how $f$ uses ${\bf x}$ to make a prediction. To see why, consider the following scenario: for a fixed $\tau>0$, let $S^{*}$ be a $\epsilon$-sufficient solution to (2.1), so that $|S^{*}|\leq\tau$ and

$$ $\displaystyle\Delta^{{\text{suf}}}_{\mathcal{V}}(S,f,{\bf x})\leq\epsilon.$ (2) $$

While $S^{*}$ is $\epsilon$-sufficient, it can also be true that

$$ $\displaystyle\Delta^{{\text{nec}}}_{\mathcal{V}}(S,f,{\bf x})>\epsilon$ (3) $$

indicating $S^{*}$ is not $\epsilon$-necessary: indeed, this can simply happen when its complement, $S_{c}^{*}$, contains important features. This scenario raises two questions:

- 1.
How different are sufficient and necessary features?
- 2.
How does varying the levels of sufficiency and necessity affect the optimal set of important features?

In order to provide answers to these questions (and to avoid the scenario above) we propose to search for a small set $S$ that is both sufficient *and* necessary by combining problems (2.1) and (2.2). Consider $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)$, a convex combination of both $\Delta^{{\text{suf}}}_{\mathcal{V}}(S,f,{\bf x})$ and $\Delta^{{\text{nec}}}_{\mathcal{V}}(S,f,{\bf x})$

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)=\alpha \cdot\Delta^{{\text{suf}}}_{\mathcal{V}}(S,f,{\bf x})+(1-\alpha)\cdot\Delta^{{ \text{nec}}}_{\mathcal{V}}(S,f,{\bf x})$ (4) $$

where $\alpha\in[0,1]$ controls the extent to which $S$ is required to be sufficient vs. necessary. Our *unified problem*, (4), can be expressed as:
{argmini*}|l|[2]
S ⊆[d]
Δ^uni_V(S, f, x, α)  subject to  |S| ≤τ
.
When $\alpha$ is $1$ or 0 0, $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)$ reduces to $\Delta^{{\text{suf}}}_{\mathcal{V}}(S,f,{\bf x})$ or $\Delta^{{\text{nec}}}_{\mathcal{V}}(S,f,{\bf x})$, respectively. In these extreme cases, $S$ is only sufficient or necessary. In the remainder of this work we will theoretically analyze (4), characterize its solutions, and provide different interpretations of what properties the solutions have through the lens of conditional independence and game theory. In the experimental section, we will show that solutions to (4) provide insights that neither (2.1) nor (2.2) offer.

### 4.1 Solutions to the Unified Problem

We begin with a simple lemma that demonstrates why (4) enforces both sufficiency and necessity.

###### Lemma 4.1 .

Let $\alpha\in(0,1)$. For $\tau>0$, denote $S^{*}$ to be a solution to (4) for which $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)=\epsilon$. Then, $S^{*}$ is $\frac{\epsilon}{\alpha}$-sufficient and $\frac{\epsilon}{1-\alpha}$-necessary. Formally,

$$ $\displaystyle 0\leq\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x})\leq \frac{\epsilon}{\alpha}\quad\text{and}\quad 0\leq\Delta^{{\text{nec}}}_{ \mathcal{V}}(S^{*},f,{\bf x})\leq\frac{\epsilon}{1-\alpha}.$ (5) $$

The proof of this result, and all others, is included Section A.1. This result illustrates that solutions to (4) satisfy varying definitions of sufficiency and necessity. Furthermore, as $\alpha$ increases from 0 to 1, the solution shifts from being highly necessary to highly sufficient. In the following results, we will show when and how solutions to (4) are similar (and different) to those of (2.1) and (2.2). To start, we present the following lemma, which will be useful in subsequent results.

###### Lemma 4.2 .

For $0\leq\epsilon<\frac{\rho(f({\bf x}),f_{\emptyset}({\bf x}))}{2}$, denote $S^{*}_{{\text{suf}}}$ and $S^{*}_{{\text{nec}}}$ to be $\epsilon$-sufficient and $\epsilon$-necessary sets. Then, if $S^{*}_{{\text{suf}}}$ is $\epsilon$-super sufficient or $S^{*}_{{\text{nec}}}$ is $\epsilon$-super necessary, we have

$$ $\displaystyle S^{*}_{{\text{suf}}}\cap S^{*}_{{\text{nec}}}\neq\emptyset.$ (6) $$

This lemma demonstrates that, given $\epsilon$-sufficient and necessary sets $S^{*}_{{\text{suf}}}$ and $S^{*}_{{\text{nec}}}$, if either additionally satisfies the stronger notions of super sufficiency or necessity, they must share some features. This proves useful in characterizing a solution to (4), which we now do in the following theorem.

###### Theorem 4.1 .

Let $\tau_{1},\tau_{2}>0$ and $0\leq\epsilon<\frac{1}{2}\cdot\rho(f({\bf x}),f_{\emptyset}({\bf x}))$. Denote $S^{*}_{{\text{suf}}}$ and $S^{*}_{{\text{nec}}}$ to be $\epsilon$-super sufficient and $\epsilon$-super necessary solutions to (2.1) and (2.2), respectively, such that $|S^{*}_{{\text{suf}}}~{}|=\tau_{1}$ and $|S^{*}_{{\text{nec}}}|=\tau_{2}$.
Then, there exists a set $S^{*}$ such that

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(S^{*},f,{\bf x},\alpha)\leq \epsilon\quad\text{and}\quad\max(\tau_{1},\tau_{2})\leq|S^{*}|<\tau_{1}+\tau_{ 2}.$ (7) $$

Furthermore, if $S^{*}_{{\text{suf}}}\subseteq S^{*}_{{\text{nec}}}$ or $S^{*}_{{\text{nec}}}\subseteq S^{*}_{{\text{suf}}}$. then $S^{*}=S^{*}_{{\text{nec}}}$ or $S^{*}=S^{*}_{{\text{suf}}}$, respectively.

This result demonstrates that solutions to (4), (2.1), and (2.2) can be closely related. As an example, consider features that are $\epsilon$-super sufficient, $S^{*}_{{\text{suf}}}$. If we have domain knowledge that $S^{*}_{{\text{suf}}}\subseteq S^{*}_{{\text{nec}}}$, and $S^{*}_{{\text{nec}}}$ is $\epsilon$-super necessary, then $S^{*}_{{\text{nec}}}$ is in fact the solution to the (4) problem. Conversely, if we know that $S^{*}_{{\text{suf}}}$ is $\epsilon$-super necessary along with being a subset of $\epsilon$-super sufficient set $S^{*}_{{\text{suf}}}$, then $S^{*}_{{\text{suf}}}$ will be a solution to the (4) problem.

###### Lemma 4.1 .

###### Lemma 4.2 .

###### Theorem 4.1 .

## 5 Two Perspectives of the Unified Approach

In the previous section, we characterized solutions to (4) and their connections to those of (2.1) and (2.2). To better understand sufficiency, necessity, and their unification, we will provide two alternative perspectives of our unified framework through the lens of conditional independence and Shapley values.

### 5.1 A Conditional Independence Perspective

Here we demonstrate how our sufficiency, necessity, and our unified approach, can be understood as measuring conditional independence relations between features ${\bf X}$ and labels $Y$.

###### Corollary 5.1 .

Suppose for any $S\subseteq[d]$, ${\mathcal{V}}_{S}=p({{\bf X}}_{S}\mid{{\bf X}}_{{S_{c}}}={{\bf x}}_{{S_{c}}})$. Let $\alpha\in(0,1)$, $\epsilon\geq 0$, and denote $\rho:{\mathbb{R}}\times{\mathbb{R}}\mapsto{\mathbb{R}}$ to be a metric on ${\mathbb{R}}$. Furthermore, for $f({\bf X})={\mathbb{E}}[Y\mid{\bf X}]$ and $\tau>0$, let $S^{*}$ be a solution to (4) such that $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)=\epsilon$. Then, $S^{*}$ satisfies the following conditional independence relations,

$$ $\displaystyle\rho\left({\mathbb{E}}[Y\mid{\bf x}],~{}{\mathbb{E}}[Y\mid{\bf X} _{S^{*}}={\bf x}_{S^{*}}]\right)\leq\frac{\epsilon}{\alpha}\quad\text{and} \quad\rho\left({\mathbb{E}}[Y\mid{\bf X}_{S^{*}_{c}}={\bf x}_{S^{*}_{c}}],~{}{ \mathbb{E}}[Y]\right)\leq\frac{\epsilon}{1-\alpha}.$ (8) $$

The assumption in this corollary is that, $\forall~{}S\subseteq[d]$, $f_{S}({\bf x})$ is evaluated using the conditional distribution $p({\bf X}_{{S_{c}}}\mid{{\bf X}}_{S}={\bf x}_{S})$ as the reference distribution ${\mathcal{V}}_{S}$. Given the recent advancements in generative models \parencitesong2019generative, ho2020denoising, song2021scorebased, this assumption is (approximately) reasonable in many practical settings, as we will demonstrate in our experiments. With this reference distribution, the results shows that for the model $f({\bf X})={\mathbb{E}}[Y\mid{\bf X}]$ and a sample ${\bf x}$, the minimizer $S^{*}$ of (4) approximately satisfies two conditional independence properties. First, $S^{*}$ is sufficient in that, when the features in $S^{*}$ are fixed, the complement, ${S_{c}}^{*}$, offers little-to-no additional information about $Y$. Second, $S^{*}$ is necessary because when we marginalize it out and rely only on the features in ${S_{c}}^{*}$, the information gained about $Y$ is minimal and similar to ${\mathbb{E}}[Y=1]$.

###### Corollary 5.1 .

### 5.2 A Shapley Value Perspective

In the previous section, we detailed the conditional independence relations one gains from solving (4). We now present an arguably less intuitive result that shows that solving (4) is equivalent to maximizing the lower bound of Shapley value. Before presenting our result, we provide a brief background on this game-theoretic quantity.

Shapley Values. Shapley values use game theory to measure the importance of players in a game. Let the tuple $([n],v)$ represent a cooperative game with players $[n]=\{1,2,\dots,n\}$ and denote a characteristic function $v(S):\mathcal{P}([n])\to{\mathbb{R}}$, which maps the power set of $[n]$ to the reals. Then, the Shapley value \parenciteshapley1951notes for player $j$ in the cooperative game $([n],v)$ is

$$ $\displaystyle\phi^{{\text{shap}}}_{j}([n],v)=\sum_{S\subseteq[n]\setminus\{j\} }w_{S}\cdot\left[v(S\cup\{j\})-v(S)\right]$ (9) $$

where $w_{S}=\frac{|S|!(n-|S|-1)!}{n!}$. The Shapley value is the only solution concept that satisfies the desirable axioms of additivity, nullity, symmetry, and linearity \parenciteowen2013game. In the context of XAI and feature importance, Shapley values are widely used to measure local feature importance by treating input features as players in a game \parencitecovert2020understanding, teneggi2022fast, chen2018shapley, lundberg2017unified. Given a sample ${\bf x}\in{\mathbb{R}}^{d}$ and a model $f$, the goal is to evaluate the importance of each feature $j\in[d]$ for the prediction $f({\bf x})$. This is done by defining a cooperative game $([d],v)$, where $v(S)$ is a characteristic function that quantifies how the features in $S$ contribute to the prediction. Different choices of $v(S)$ can be found in \parencitelundberg2017unified, sundararajan2020many, watson2024explaining. Although computing $\phi^{{\text{shap}}}_{j}([d],v)$ is computationally intractable, several practical methods for estimation have been developed \parencitechen2023algorithms, teneggi2022fast, zhang2023towards, lundberg2020local. While Shapley values are popular across various domains \parencitemoncada2021explainable, zoabi2021machine, liu2021evaluating, few works, aside from \textcitewatson21a, explore their connections to sufficiency and necessity.

With this background, we now present our result. Recall solving (4) obtains a small subset $S$ with low $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)$. Notice that in (4) there is a natural *partitioning* of the features into two sets, $S$ and ${S_{c}}$. In the follow theorem we demonstrate that searching for a small subset $S$ with minimal $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)$ is equivalent to maximizing a lower bound on the Shapley value in a two player game.

###### Theorem 5.1 .

Consider an input ${\bf x}$ for which $f({\bf x})\neq f_{\emptyset}({\bf x})$. Denote by $\Lambda_{d}=\{S,{S_{c}}\}$ the partition of $[d]=\{1,2,\dots,d\}$, and define the characteristic function to be $v(S)=-\rho(f({\bf x}),f_{S}({\bf x}))$. Then,

$$ $\displaystyle\phi^{{\text{shap}}}_{S}(\Lambda_{d},v)\geq\rho(f({\bf x}),f_{ \emptyset}({\bf x}))-\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha).$ (10) $$

This result has important implications. When the feature space is partitioned into 2 disjoint sets, $S$ and ${S_{c}}$, where each is a player in a cooperative game, then in searching for an $S$ with small $\Delta_{{\text{uni}}}(S,{\mathcal{V}},\frac{1}{2})$, as we do in (4), we are searching for a player, $S$, with a large lower bound on its Shapley value. Note this connection we show is different from the one presented by \parencitewatson21a. They show the Shapley value of feature $i$ is a measure of this feature $i$’s sufficiency subsets $S\subseteq[d]$. In conclusion, our result provides a new and different and complementary interpretation to the sufficiency, necessity, and our proposed unified method through the lens of game theory.

###### Theorem 5.1 .

## 6 Experiments

We demonstrate our theoretical findings in multiple settings of increasingly complexity: two tabular data tasks (on synthetic data and the US adult income dataset \parenciteding2021retiring) and two high-dimensional image classification tasks using the RSNA 2019 Brain CT Hemorrhage Challenge \parenciteflanders2020construction and CelebA-HQ datasets \parenciteCelebAMask-HQ.

### 6.1 Tabular Data

In the following examples, we analyze solutions to (4) for varying levels of sufficiency vs. necessity and multiple size constraints. We learn a predictor $f$ and, for 100 new samples, solve $\eqref{eq:uni_opt}$ for $\tau\in\{3,6,9\}$ and $\alpha\in[0,1]$, with $\rho(a,b)=|a-b|$ and ${\mathcal{V}}_{S}=p({{\bf X}}_{S}\mid{{\bf X}}_{{S_{c}}}={\bf x}_{{S_{c}}})$. For a fixed $\tau$ and sample ${\bf x}$, we denote $S^{*}_{\alpha_{i}}$ to be a solution to $\eqref{eq:uni_opt}$ for $\alpha_{i}$. To analyze the stability of $S^{*}_{\alpha_{i}}$ as sufficiency and necessity vary, we report the normalized average Hamming distance \parencitehamming1950error between $S^{*}_{\alpha_{i}}$ and $S^{*}_{0}$, along with 95% confidence intervals, as a function of $\alpha$.

#### 6.1.1 Linear Regression

We begin with a regression example. Features ${\bf X}$ are distributed according to $\cal{N}({\boldsymbol{\mu}},{\bf AA^{T}})$ with $\boldsymbol{\mu}=\left[2^{i}\right]^{d}_{i=1}$ and ${\bf A}_{i,j}\sim U(0,1)$. The response is $Y=\boldsymbol{\beta}^{T}{\bf X}+\boldsymbol{\epsilon}$, with $\boldsymbol{\beta}=32\cdot[2^{-i}]_{i=1}^{d}$ and $\boldsymbol{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_{d\times d})$. With $d=10$ our model is $f({\bf X})=\hat{\boldsymbol{\beta}}^{T}{\bf X}$, where $\hat{\boldsymbol{\beta}}$ is the least squares solution.

Stability of Unified Solutions. Fig. 1(a) shows that when solutions are constrained to be small ($\tau=3$), increasing $\alpha$ to enforce greater sufficiency results in a steady increase in Hamming distance, indicating that the solutions $S^{*}_{\alpha_{i}}$ are consistently changing. When larger solutions are allowed ($\tau=6$), $S^{*}_{\alpha_{i}}$ rapidly changes with the introduction of sufficiency, as seen by the initial steep rise in Hamming distance. However, as $\alpha$ continues to increase, this distance grows more gradually. Lastly, when the solution size approaches the dimensionality of the feature space ($\tau=9$), small to intermediate levels of sufficiency do not significantly alter the solutions. However, requiring high levels of sufficiency ($\alpha>0.8$) leads to extreme changes in the solutions, as shown by a sharp increase in Hamming distance.

#### 6.1.2 American Community Survey Income (ACSIncome)

We use the ACSIncome dataset for California, including 10 demographic and socioeconomic features such as age, education, occupation, and geographic region. We train a Random Forest classifier to predict whether an individual’s annual income exceeds $50K, achieving a test accuracy $\approx 81\%$.

Figure: (a) Regression
Refer to caption: x1.png

##### Stability of Unified Solutions.

Fig. 1(b) shows that when solutions are forced to be small ($\tau=3$), increasing $\alpha$ to enforce sufficiency results in a steady increase in Hamming distance, indicating the solutions $S^{*}_{\alpha_{i}}$ are changing. For larger solutions ($\tau=6$), $S^{*}_{\alpha_{i}}$ changes significantly when low levels sufficiency are required, indicated by initial rise in the Hamming distance.
As $\alpha$ continues to increase, the Hamming distance grows more gradually. Interestingly, when the size is close to feature space’s dimensionality ($\tau=9$), the Hamming distance exhibits a behavior similar to that observed for $\tau=3$. In conclusion, both experiments show that the optimal feature set can vary significantly depending on the size allowed and balance between sufficiency and necessity.

### 6.2 Image Classification

The following two experiments explore high dimensional settings in image classification tasks. The features are pixel values and so a subset $S$ corresponds to a binary mask identifying important pixels. Since solving (2.1), (2.2), or (4) is NP-hard, we use two methods–one for each setting, described in their respective sections–which solve relaxed problems to identify sufficient and necessary masks $S$. These experiments serve two purposes. First, they will analyze the extent to which explanations generated by popular methods–including Integrated Gradients \parencitesundararajan2017axiomatic, GradientSHAP \parencitelundberg2017unified, Guided GradCAM \parenciteselvaraju2017grad, and h-Shap \parenciteteneggi2022fast–identify small sufficient and necessary subsets. To ensure consistent analysis, we normalize all generated attribution scores to the interval $[0,1]$. This is done by setting the top 1% of nonzero scores to 1 and dividing the remaining scores by the minimum score from the top 1% of nonzero scores. Then, binary masks are generated by thresholding the normalized scores using $t\in[0,1]$. For a test set of images, we perform this normalization and report the average $-\log(\Delta^{{\text{suf}}})$, $-\log(\Delta^{{\text{nec}}})$, and $-\log(L^{0})$ (across all binary masks) at different threshold values to analyze the sufficiency, necessity and size of the explanations. Finally, the second objective is to understand and visualize the similarities and differences between sufficient and necessary sets.

#### 6.2.1 RSNA CT Hemorrhage

We use the RSNA 2019 Brain CT Hemorrhage Challenge dataset comprised of 752,803 scans. Each scan is annotated by expert neuroradiologists with the presence and type(s) of hemorrhage (i.e., epidural, intraparenchymal, intraventricular, subarachnoid, or subdural). We use a ResNet18 \parencitehe2016deep classifier that was pretrained on this data \parenciteteneggi2022fast. To identify sufficient and necessary sets we solve the relaxed problem,

$$ $\displaystyle\underset{S\subseteq[0,1]^{d}}{\text{arg min}}~{}~{}\Delta^{{ \text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)+\lambda_{1}\cdot||S||_{1}+ \lambda_{\text{TV}}\cdot||S||_{TV}.$ (11) $$

Since the dataset consists of highly complex and diverse images, we employ this per-example approach that generates highly specific tailored solutions by solving an optimization problem for each sample following previous work \parencitefong2019understanding, kolek2021cartoon, kolek2022rate.(^3^33$\lambda_{1},~{}||S||_{1}$ and $\lambda_{\text{TV}},~{}||S||_{TV}$ are the $\ell_{1}$ and Total Variation norms and hyperparamters, promoting sparsity and smoothness.) To learn sufficient and/or necessary masks, we solve Eq. 11 for $\alpha\in\{0,0.5,1\}$. Details are in Section A.2.

Comparison of Post-hoc Interpretability Methods. For a set of 20 images positively classified by the ResNet model, we apply multiple post-hoc interpretability methods, as well as computing sufficient and necessary masks by our proposed approach – solving (11). The results in Fig. 2(a) show that for a threshold of $t<0.1$, many methods identify sufficient sets smaller in size than the sufficient and unified explainer, as indicated by their large values of $-\log(\Delta^{{\text{suf}}})$ and smaller values of $-\log(L^{0})$. However, for $t>0.1$, only the sufficient and unified explainer identify sufficient sets of a constant small size. Importantly, it is also evident that *no methods, besides our necessity and unified explainers, identify necessary sets*. Furthermore, as expected, the sufficient explainer does not identify necessary sets and vice versa. The unified explainer, as expected, identifies a sufficient and necessary set, albeit at the cost of the set being larger in size. In conclusion, while many methods can identify sufficient, no off-the-shelf method can identify necessary sets for small thresholds. Only when we directly optimize for such properties do we get explanations that are consistently small, sufficient and/or necessary across thresholds.

Figure: (a) Comparison of different methods.
Refer to caption: x3.png

Sufficiency vs. Necessity.
In Fig. 2(b) we visualize the sufficient and necessary features in various CT scans. The first observation is that sufficient subsets do not provide a complete picture of which features are important. Notice for all the CT scans, a sufficient set, $S^{*}_{{\text{suf}}}$ highlights one or two, but never all, brain hemorrhages in the scans. For example, in the last row, $S^{*}_{{\text{suf}}}$ only contains the left frontal lobe parenchymal hemorrhages, which happens to be one of the larger hemorrhages present. On the other hand, necessary sets, $S^{*}_{{\text{nec}}}$, contain parts of, sometimes entirely, *all* hemorrhages in the scans. In the last row, $S^{*}_{{\text{nec}}}$ contains all multifocal parenchymal hemorrhages in both right and left frontal lobes, because when all these regions are masked, the model yields a prediction $\approx 0.64$– the prediction of the model on the mean image. Finally, notice in the 2nd and 3rd columns that $S^{*}_{{\text{nec}}}$ and $S^{*}_{{\text{uni}}}$ are nearly identical, which precisely demonstrate Lemmas 4.1 and 4.1 in practice. First, since $S^{*}_{{\text{suf}}}$ is super sufficient, $S^{*}_{{\text{suf}}}$ and $S^{*}_{{\text{nec}}}$, share common features. Second, visually $S^{*}_{{\text{suf}}}\subseteq S^{*}_{{\text{nec}}}$ holds approximately and so $S^{*}_{{\text{nec}}}=S^{*}_{{\text{uni}}}$. Through this experiment we are able to highlight the differences between sufficient and necessary sets, show how each contain important and complementary information, and demonstrate our theory holding in real world settings.

#### 6.2.2 CelebA-HQ

We use a modified version of the CelebA-HQ dataset \parencitekarras2017progressive that contains 30,000 celebrity faces resized to 256$\times$256 pixels. We train a ResNet18 to classify whether a celebrity is smiling, achieving a test accuracy $\approx 94\%$. To generate sufficient or necessary masks $S$ for samples ${\bf x}$, we learn models $g_{\theta}:{\mathcal{X}}\mapsto{\mathcal{X}}$, that (approximately) solve the following optimization problem:

$$ $\displaystyle\underset{\theta\in\Theta}{\text{arg min}}~{}\underset{{\bf X} \sim\mathcal{D}_{\mathcal{X}}}{\mathbb{E}}\left[\Delta^{{\text{uni}}}_{ \mathcal{V}}(g_{\theta}({\bf X}),f,{\bf X},\alpha)+\lambda_{1}\cdot||g_{\theta }({\bf X})||_{1}+\lambda_{\text{TV}}\cdot||g_{\theta}({\bf X})||_{\text{TV}} \right].$ (12) $$

Given the structured nature of the dataset and the similarity of features across images, we use this parametric model approach because it prevents overfitting to spurious signals, an issue that can arise with per-example methods. Additionally, this approach is more efficient, as it still generates tailored per-sample explanations but only requires learning a single model rather than repeatedly solving Eq. 11 \parencitelinder2022interpreting, chen2018learning, yoon2018invase. To learn a necessary and sufficient explainer model, we solve Eq. 12 via empirical risk minimization for $\alpha\in\{0,1\}$ respectively. Implementation details and hyperparameter settings are included in Section A.2.

Figure: Figure 3: Comparison of different methods on the CelebAHQ dataset.
Refer to caption: x5.png

Comparison of Post-hoc Interpretability Methods. For a set of 100 images labeled with a smile and correctly classified by the ResNet model, we apply multiple post-hoc interpretability methods and our sufficient and necessary explainers to identify important features associated with smiling. The results in Fig. 3 illustrate that for a wide range of thresholds $t\in[0,1]$, many methods identify sufficient subsets, as $-\log(\Delta^{{\text{suf}}})$ for many of them is comparable to that of the sufficient explainer. The necessary explainer, in fact, identifies subsets that are more sufficient than those found by the sufficient explainer. The reason is that the sufficient explainer identifies subsets that are, on average, smaller for all $t\in[0,1]$, while the necessary explainer finds subsets that are constant in size for all $t\in[0,1]$ but slightly larger since, to be necessary, they must contain more features that provide additional information about the label. For other methods, as $t$ increases, subset size decreases, and the sufficiency and necessity of the solutions decline. Meanwhile, the necessary explainer naturally identifies necessary subsets, indicated by large $-\log(\Delta^{{\text{nec}}})$, whereas other methods fail to do so. In conclusion, many methods can identify sufficient sets, but not necessary ones. Directly optimizing for these criterion leads to identifying small, constant-sized subsets across thresholds.

Sufficiency vs. Necessity. In Fig. 4, we see how sufficient subsets alone may overlook important features, while solutions to (4) offer deeper insights. As stated earlier, the sufficient explainer identifies sets that are sufficient but not necessary. On the other hand, the necessary explainer has high $-\log(\Delta^{{\text{suf}}})$ and $-\log(\Delta^{{\text{nec}}})$, indicating that it identifies sufficient *and* necessary set, meaning they also serve as solutions to (4). In Fig. 4, we visualize the reasons for this phenomena. Notice that $S^{*}_{{\text{suf}}}$ precisely highlights (only) the smile. When $S^{*}_{{\text{suf}}}$ is fixed, one can generate new images (as done in \parencitezhang2023towards) for which the model produces the same predictions as it did for the original image (a smile). On the other hand, we also see why $S^{*}_{{\text{suf}}}$ is not necessary: we can fix the complement $(S^{*}_{{\text{suf}}})_{c}$ and, since there are important features in it, a smile is consistently generated, and the model produces the same prediction on these images as it did on the original. Conversely solutions to (2.2) (also solutions to (4) here) generate different explanations that provide a more complete picture of feature importance. Notice that $S^{*}_{{\text{nec}}}$ is sufficient because $S^{*}_{{\text{suf}}}\subseteq S^{*}_{{\text{nec}}}$, with the additional features mainly being the dimples and eyes, which aid in determining the presence of a smile. More importantly, Fig. 5 illustrates why $S^{*}_{{\text{nec}}}$ is necessary: when we fix the complement of ${S}^{*}_{{\text{nec}}}$ and generate new samples, half of the faces lack a smile, leading the model $f$ to predict no smile. Details on sample generation are in Section A.1.

## 7 Limitations & Broader Impacts

Figure: Figure 4: Images and model predictions by fixing and masking the sufficient subset $S^{*}_{{\text{suf}}}$
Refer to caption: x6.png

Figure: Figure 5: Images and model predictions by fixing and masking the necessary subset $S^{*}_{{\text{nec}}}$
Refer to caption: x8.png

While this work provides a novel theoretical contribution to the XAI community, there are some limitations that require careful discussion. The choice of reference distribution $\mathcal{V}_{S}$ determines the characteristics of sufficient and necessary explanations. For instance, only with the true conditional data distribution can one obtain the conditional independence results that our theory provides. Naturally, there are computational trade-offs that must be carefully studied; the ability to learn and sample from accurate conditional distributions to generate explanations with clear statistical meaning comes with a computational and statistical cost, particularly in high-dimensional settings. Thus, a key direction for future work is to explore the impact of different reference distributions and provide a principled framework for selecting a $\mathcal{V}_{S}$ that balances practical utility and computational feasibility.

Another relevant question is how well our proposed notions align with human intuition. While we aim to understand which features are sufficient and necessary *for a given predicted model*, these explanations may not always correspond to how humans perceive importance (since model might use different features to solve a task). This can be an issue in settings where interpretability is essential for trust and accountability, such as in healthcare. On the one hand, our approach can provide useful insights to further evaluate models (e.g. by verifying if the sufficient and necessary features employed by models correlate with the correct ones as informed by human experts). On the other hand, bridging the gap between our mathematical definitions of sufficiency and necessity and other human notions of importance is an area for further investigation. User studies, along with collaboration with domain experts, will be critical in determining how our formal notions of sufficiency and necessity can be adapted or extended to better meet real-world interpretability needs.

Finally, the societal impact of this work warrants discussion. While we offer a rigorous framework to understand model predictions,
these are oblivious to notions of demographic bias \parencitehardt2016equality, feldman2015certifying, bharti2024estimating. There is a risk that an “incorrect" choice of generating a sufficient vs. necessary explanation could reinforce biases or obscure the causal reasons behind predictions. Future work will study when and how our framework can be incorporate these biases in the reported important features.

## 8 Conclusion

This work formalizes notions of sufficiency and necessity as tools to evaluate feature importance and explain model predictions. We demonstrate that sufficient and necessary explanations, while insightful, often provide incomplete while complementary answers to model behavior. To address this limitation, we propose a unified approach that offers a new and more nuanced understanding of model behavior. Our unified approach expands the scope of explanations and reveals trade-offs between sufficiency and necessity, giving rise to new interpretations of feature importance. Through our theoretical contributions, we present conditions under which sufficiency and necessity align or diverge, and provide two perspectives of our unified approach through the lens of conditional independence and Shapley values. Our experimental results support our theoretical findings, providing examples of how adjusting sufficiency-necessity trade-off via our unified approach can uncover alternative sets of important features that would be missed by focusing solely on sufficiency or necessity. Furthermore, we evaluate common post-hoc interpretability methods showing that many fail to reliably identify features that are necessary or sufficient. In summary, our work contributes to a more complete understanding of feature importance through sufficiency and necessity. We believe, and hope, our framework holds potential for advancing the rigorous interpretability of ML models.

## Appendix A Appendix

### A.1 Proofs

#### A.1.1 Proof of Lemma 4.1

Lemma 4.1. Let $\alpha\in(0,1)$. For $\tau>0$, denote $S^{*}$ to be a solution to (4) for which $\Delta^{{\text{uni}}}_{\mathcal{V}}(S^{*},f,{\bf x},\alpha)=\epsilon$. Then, $S^{*}$ is $\frac{\epsilon}{\alpha}$-sufficient and $\frac{\epsilon}{1-\alpha}$-necessary. Formally,

$$ $\displaystyle 0\leq\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x})\leq \frac{\epsilon}{\alpha}\quad\text{and}\quad 0\leq\Delta^{{\text{nec}}}_{ \mathcal{V}}(S^{*},f,{\bf x})\leq\frac{\epsilon}{1-\alpha}.$ (13) $$

###### Proof.

Let $\tau>0$ and $\alpha\in(0,1)$ and denote $S^{*}$ to be a solution to (4) such that

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(S^{*},f,{\bf x},\alpha)=\epsilon.$ (14) $$

Then, by definition of being a solution to (4),

$$ $\displaystyle|S^{*}|\leq\tau.$ (15) $$

Furthermore, recall that

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(S^{*},f,{\bf x},\alpha)= \alpha\cdot\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x})+(1-\alpha) \cdot\Delta^{{\text{nec}}}_{\mathcal{V}}(S^{*},f,{\bf x})$ (16) $$

which implies

$$ $\displaystyle\alpha\cdot\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x})$ $\displaystyle=\epsilon-(1-\alpha)\cdot\Delta^{{\text{nec}}}_{\mathcal{V}}(S^{* },f,{\bf x})$ (17) $\displaystyle\leq\epsilon$ $\displaystyle~{}((1-\alpha),~{}\Delta^{{\text{nec}}}_{\mathcal{V}}(S^{*},f,{ \bf x})\geq 0)$ (18) $\displaystyle\implies\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x})\leq \frac{\epsilon}{\alpha}.$ (19) $$

Similarly,

$$ $\displaystyle(1-\alpha)\cdot\Delta^{{\text{nec}}}_{\mathcal{V}}(S^{*},f,{\bf x})$ $\displaystyle=\epsilon-\alpha\cdot\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f, {\bf x})$ (20) $\displaystyle\leq\epsilon$ $\displaystyle~{}(\alpha,~{}\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x} )\geq 0)$ (21) $\displaystyle\implies\Delta^{{\text{nec}}}_{\mathcal{V}}(S^{*},f,{\bf x})\leq \frac{\epsilon}{1-\alpha}.$ (22) $$

∎

###### Proof.

#### A.1.2 Proof of Lemma 4.2

Lemma 4.2. For $0\leq\epsilon<\frac{\rho(f({\bf x}),f_{\emptyset}({\bf x}))}{2}$, denote $S^{*}_{{\text{suf}}}$ and $S^{*}_{{\text{nec}}}$ to be $\epsilon$-sufficient and $\epsilon$-necessary sets. Then, if $S^{*}_{{\text{suf}}}$ is $\epsilon$-super sufficient or $S^{*}_{{\text{nec}}}$ is $\epsilon$-super necessary,

$$ $\displaystyle S^{*}_{{\text{suf}}}\cap S^{*}_{{\text{nec}}}\neq\emptyset.$ (23) $$

###### Proof.

We will prove the result via contradiction. First recall that,

$$ $\displaystyle f_{S}({\bf x})=\underset{{\bf X}_{{S_{c}}}\sim{\mathcal{V}}_{{S_ {c}}}}{{\mathbb{E}}}[f({\bf x}_{S},{\bf X}_{{S_{c}}})]$ (24) $$

and, for any metric $\rho:{\mathbb{R}}\times{\mathbb{R}}\mapsto{\mathbb{R}}$,

$$ $\displaystyle\Delta^{{\text{suf}}}_{\mathcal{V}}(S,f,{\bf x})$ $\displaystyle\triangleq\rho(f({\bf x}),f_{S}({\bf x}))$ (25) $\displaystyle\Delta^{{\text{nec}}}_{\mathcal{V}}(S,f,{\bf x})$ $\displaystyle\triangleq\rho(f_{{S_{c}}}({\bf x}),f_{\emptyset}({\bf x})).$ (26) $$

Since $\rho$ is a metric on ${\mathbb{R}}$, it satisfies the triangle inequality. Thus, for $a,b,c\in{\mathbb{R}}$

$$ $\displaystyle\rho(a,c)\leq\rho(a,b)+\rho(b,c).$ (27) $$

Now, let $S^{*}_{{\text{suf}}}$ be $\epsilon$-super sufficient and suppose

$$ $\displaystyle S^{*}_{{\text{suf}}}\cap S^{*}_{{\text{nec}}}=\emptyset.$ (28) $$

This implies

$$ $\displaystyle S^{*}_{{\text{suf}}}\subseteq(S^{*}_{{\text{nec}}})_{c}.$ (29) $$

Subsequently, since $S^{*}_{{\text{suf}}}$ is $\epsilon$-super sufficient,

$$ $\displaystyle\Delta^{{\text{suf}}}_{\mathcal{V}}((S^{*}_{{\text{nec}}})_{c},f, {\bf x})\leq\epsilon.$ (30) $$

As a result, observe

$$ $\displaystyle\rho(f({\bf x}),f_{\emptyset}({\bf x}))$ $\displaystyle\leq\rho(f({\bf x}),f_{(S^{*}_{{\text{nec}}})_{c}}({\bf x}))+\rho (f_{(S^{*}_{{\text{nec}}})_{c}}({\bf x}),f_{\emptyset}({\bf x}))$ triangle inequality (31) $\displaystyle=\Delta^{{\text{suf}}}_{\mathcal{V}}((S^{*}_{{\text{nec}}})_{c},f ,{\bf x})+\Delta^{{\text{nec}}}_{\mathcal{V}}((S^{*}_{{\text{nec}}})_{c},f,{ \bf x})$ (32) $\displaystyle\leq\epsilon+\Delta^{{\text{nec}}}_{\mathcal{V}}((S^{*}_{{\text{ nec}}})_{c},f,{\bf x})$ $S^{*}_{{\text{suf}}}$ is $\epsilon$ -super sufficient (33) $\displaystyle\leq 2\epsilon$ $S^{*}_{{\text{nec}}}$ is $\epsilon$ - necessary (34) $\displaystyle\implies\epsilon\geq\frac{\rho(f({\bf x}),f_{\emptyset}({\bf x})) }{2}$ (35) $$

which is a contradiction because $0\leq\epsilon<\frac{\rho(f({\bf x}),f_{\emptyset}({\bf x}))}{2}$. Thus $S^{*}_{{\text{suf}}}\cap S^{*}_{{\text{nec}}}\neq\emptyset$. The proof of this result assuming $S^{*}_{{\text{nec}}}$ is $\epsilon$-super necessary follows the same argument.
∎

###### Proof.

#### A.1.3 Proof of Theorem 4.1

Theorem 4.1. Let $\tau_{1},\tau_{2}>0$ and $0\leq\epsilon<\frac{1}{2}\cdot\rho(f({\bf x}),f_{\emptyset}({\bf x}))$. Denote $S^{*}_{{\text{suf}}}$ and $S^{*}_{{\text{nec}}}$ to be $\epsilon$-super sufficient and $\epsilon$-super necessary solutions to (2.1) and (2.2), respectively, such that $|S^{*}_{{\text{suf}}}~{}|=\tau_{1}$ and $|S^{*}_{{\text{nec}}}|=\tau_{2}$.
Then, there exists a set $S^{*}$ to (4) such that

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(S^{*},f,{\bf x},\alpha)\leq \epsilon\quad\text{and}\quad\max(\tau_{1},\tau_{2})\leq|S^{*}|<\tau_{1}+\tau_{ 2}.$ (36) $$

Furthermore, if $S^{*}_{{\text{suf}}}\subseteq S^{*}_{{\text{nec}}}$ or $S^{*}_{{\text{nec}}}\subseteq S^{*}_{{\text{suf}}}$. then $S^{*}=S^{*}_{{\text{nec}}}$ or $S^{*}=S^{*}_{{\text{suf}}}$, respectively.

###### Proof.

Consider the set $S^{*}=S^{*}_{{\text{suf}}}\cup S^{*}_{{\text{nec}}}$. This set has the following properties:

- (P1)
$S^{*}$ is $\epsilon$-sufficient because $S^{*}_{{\text{suf}}}$ is $\epsilon$-super sufficient
- (P2)
$S^{*}$ is $\epsilon$-necessary because $S^{*}_{{\text{suf}}}$ is $\epsilon$-super necessary
- (P3)
$|S^{*}|\geq\max(\tau_{1},\tau_{2})$ with $|S^{*}|=\tau_{1}$ when $S^{*}_{{\text{nec}}}\subset S^{*}_{{\text{suf}}}$ and with $|S^{*}|=\tau_{2}$ when $S^{*}_{{\text{suf}}}\subset S^{*}_{{\text{nec}}}$
- (P4)
Via Lemma 4.1, we know $S^{*}_{{\text{suf}}}\cap S^{*}_{{\text{nec}}}\neq\emptyset$ thus $|S^{*}|<\tau_{1}+\tau_{2}$

Then by (P1) and (P2)

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(S^{*},f,{\bf x},\alpha)$ $\displaystyle=\alpha\cdot\Delta^{{\text{suf}}}_{\mathcal{V}}(S^{*},f,{\bf x})+ (1-\alpha)\cdot\Delta^{{\text{nec}}}_{\mathcal{V}}(S^{*},f,{\bf x})$ (37) $\displaystyle\leq\alpha\cdot\epsilon+(1-\alpha)\cdot\epsilon=\epsilon$ (38) $$

and by (P3) and (P4) we have $\max(\tau_{1},\tau_{2})\leq|S^{*}|<\tau_{1}+\tau_{2}$,
∎

###### Proof.

#### A.1.4 Proof of Corollary 5.1

Corollary 5.1. Suppose for any $S\subseteq[d]$, ${\mathcal{V}}_{S}=p({{\bf X}}_{S}\mid{{\bf X}}_{{S_{c}}}={{\bf x}}_{{S_{c}}})$. Let $\alpha\in(0,1)$, $\epsilon\geq 0$, and denote $\rho:{\mathbb{R}}\times{\mathbb{R}}\mapsto{\mathbb{R}}$ to be a metric on ${\mathbb{R}}$. Furthermore, for $f({\bf X})={\mathbb{E}}[Y\mid{\bf X}]$ and $\tau>0$, let $S^{*}$ be a solution to (4) such that $\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)=\epsilon$. Then, $S^{*}$ satisfies the following conditional independence relations,

$$ $\displaystyle\rho\left({\mathbb{E}}[Y\mid{\bf x}],~{}{\mathbb{E}}[Y\mid{\bf X} _{S^{*}}={\bf x}_{S^{*}}]\right)\leq\frac{\epsilon}{\alpha}\quad\text{and} \quad\rho\left({\mathbb{E}}[Y\mid{\bf X}_{S^{*}_{c}}={\bf x}_{S^{*}_{c}}],~{}{ \mathbb{E}}[Y]\right)\leq\frac{\epsilon}{1-\alpha}.$ (39) $$

###### Proof.

All we need to show is that when ${\mathcal{V}}_{S}=p({{\bf X}}_{S}\mid{{\bf X}}_{{S_{c}}}={{\bf x}}_{{S_{c}}})$ and $f({\bf X})={\mathbb{E}}[Y\mid{\bf X}]$, we have

$$ $\displaystyle f_{S}({\bf x})={\mathbb{E}}[Y\mid{\bf X}_{S}={\bf x}_{S}].$ (40) $$

Once this is proven, we can simply apply Lemma 4.1.

To this end, we have by assumption that $f({\bf x})={\mathbb{E}}[Y\mid{\bf X}={\bf x}]$ and, for any $S\subseteq[d]$, ${\mathcal{V}}_{S}=p({\bf X}_{S}\mid{\bf X}_{{S_{c}}}={\bf x}_{{S_{c}}})$. Then by definition

$$ $\displaystyle f_{S}({\bf x})={\mathbb{E}}_{{\mathcal{V}}_{{S_{c}}}}[f({\bf x}_ {S},{\bf X}_{{S_{c}}})]$ $\displaystyle=\int_{{\mathcal{X}}}f({\bf x}_{S},{\bf X}_{{S_{c}}})\cdot p({\bf X }_{{S_{c}}}\mid{\bf X}_{S}={\bf x}_{S})~{}d{\bf X}_{{S_{c}}}$ (41) $\displaystyle=\int_{{\mathcal{X}}}{\mathbb{E}}[Y\mid{\bf X}_{S}={\bf x}_{S},{ \bf X}_{{S_{c}}}]\cdot p({\bf X}_{{S_{c}}}\mid{\bf X}_{S}={\bf x}_{S})~{}d{\bf X }_{{S_{c}}}$ (42) $\displaystyle=\int_{\mathcal{X}}\left(\int_{{\mathcal{Y}}}y\cdot p(y\mid{\bf X }_{S}={\bf x}_{S},{\bf X}_{{S_{c}}})~{}dy\right)\cdot p({\bf X}_{{S_{c}}}\mid{ \bf X}_{S}={\bf x}_{S})~{}d{\bf X}_{{S_{c}}}$ (43) $\displaystyle=\int_{\mathcal{Y}}y\left(\int_{{\mathcal{X}}}p(y,{\bf X}_{{S_{c} }}\mid{\bf X}_{S}={\bf x}_{S})~{}d{\bf X}_{{S_{c}}}\right)~{}dy$ (44) $\displaystyle=\int_{\mathcal{Y}}y\cdot p(y\mid{\bf X}_{S}={\bf x}_{S})~{}dy$ (45) $\displaystyle={\mathbb{E}}[Y\mid{\bf X}_{S}={\bf x}_{S}].$ (46) $$

By applying Lemma 4.1, we have the desired result.
∎

###### Proof.

#### A.1.5 Proof of Theorem 5.1

Theorem 5.1. Consider an input ${\bf x}$ for which $f({\bf x})\neq f_{\emptyset}({\bf x})$. Denote by $\Lambda_{d}=\{S,{S_{c}}\}$ the partition of $[d]=\{1,2,\dots,d\}$, and define the characteristic function to be $v(S)=-\rho(f({\bf x}),f_{S}({\bf x}))$. Then,

$$ $\displaystyle\phi^{{\text{shap}}}_{S}(\Lambda_{d},v)\geq\rho(f({\bf x}),f_{ \emptyset}({\bf x}))-\Delta^{{\text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha).$ (47) $$

###### Proof.

Before we prove the result, recall the following properties of a metric $\rho$ in the reals:

- (P1)
$\forall a,b\in\mathbb{R},~{}\rho(a,b)=0\iff a=b$
- (P2)
for $a,b,c\in{\mathbb{R}},~{}~{}~{}\rho(a,c)\leq\rho(a,b)+\rho(b,c)$.

Now, for the partition $\Lambda_{d}=\{S,{S_{c}}\}$ of $[d]=\{1,2,\dots,d\}$ and characteristic function $v(S)=-\rho(f({\bf x}),f_{S}({\bf x}))$, $\phi^{{\text{shap}}}_{S}(\Lambda_{d},v)$ is defined as

$$ $\displaystyle\phi^{{\text{shap}}}_{S}(\Lambda_{d},v)$ $\displaystyle=\frac{1}{2}\cdot\left[v(S\cup{S_{c}})-v({S_{c}})\right]+\frac{1} {2}\cdot\left[v(S)-v(\emptyset)\right]$ (48) $\displaystyle=\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{{S_{c}}}({\bf x}))-\rho (f({\bf x}),f({\bf x}))\right]+\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{ \emptyset}({\bf x}))-\rho(f({\bf x}),f_{S}({\bf x}))\right]$ (49) $\displaystyle=\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{{S_{c}}}({\bf x})) \right]+\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{\emptyset}({\bf x}))-\rho(f({ \bf x}),f_{S}({\bf x}))\right]\qquad\text{by (P1)}$ (50) $$

By (P2)

$$ $\displaystyle\rho(f({\bf x}),f_{\emptyset}({\bf x}))$ $\displaystyle\leq\rho(f({\bf x}),f_{{S_{c}}}({\bf x}))+\rho(f_{{S_{c}}}({\bf x }),f_{\emptyset}({\bf x}))$ (51) $\displaystyle\implies\rho(f({\bf x}),f_{{S_{c}}}({\bf x}))\geq\rho(f({\bf x}), f_{\emptyset}({\bf x}))-\rho(f_{{S_{c}}}({\bf x}),f_{\emptyset}({\bf x})).$ (52) $$

Thus

$$ $\displaystyle\phi^{{\text{shap}}}_{S}(\Lambda_{d},v)$ $\displaystyle=\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{{S_{c}}}({\bf x})) \right]+\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{\emptyset}({\bf x}))-\rho(f({ \bf x}),f_{S}({\bf x}))\right]$ (53) $\displaystyle\geq\frac{1}{2}\cdot\left[\rho(f({\bf x}),f_{\emptyset}({\bf x})) -\rho(f_{{S_{c}}}({\bf x}),f_{\emptyset}({\bf x}))\right]+\frac{1}{2}\cdot \left[\rho(f({\bf x}),f_{\emptyset}({\bf x}))-\rho(f({\bf x}),f_{S}({\bf x}))\right]$ (54) $\displaystyle=\rho(f({\bf x}),f_{\emptyset}({\bf x}))-\Delta^{{\text{uni}}}_{ \mathcal{V}}(S,f,{\bf x},\alpha).$ (55) $$

∎

###### Proof.

### A.2 Additional Experimental Details

In this section, we include further experimental details. All experiments were performed on a private cluster with 8 NVIDIA RTX A5000 with 24 GB of memory. All scripts were run on PyTorch 2.0.1, Python 3.11.5, and CUDA 12.2.

#### A.2.1 RSNA CT Hemorrhage

##### Dataset Details.

The RSNA 2019 Brain CT Hemorrhage Challenge dataset \parenciteflanders2020construction, contains 752803 images labeled by a panel of board-certified radiologists with the types of hemorrhage present (epidural, intraparenchymal, intraventricular, subarachnoid, subdural).

##### Implementation.

Recall for this experiment, to identify sufficient and necessary masks $S$ for a sample ${\bf x}$, we considered the relaxed optimization problem \parencitefong2019understanding, kolek2021cartoon, kolek2022rate

$$ $\displaystyle\underset{S\subseteq[0,1]^{d}}{\text{arg min}}~{}~{}\Delta^{{ \text{uni}}}_{\mathcal{V}}(S,f,{\bf x},\alpha)+\lambda_{1}\cdot||S||_{1}+ \lambda_{\text{TV}}\cdot||S||_{TV}.$ (56) $$

where $||S||_{1}$ and $||S||_{TV}$ are the $L^{1}$ and Total Variation norm of $S$, which promote sparsity and smoothness respectively and $\lambda_{\text{Sp}}$ and $\lambda_{\text{Sm}}$ are the associated. To solve this problem, a mask $S\in[0,1]^{512\times 512}$ is initialized with entries $S_{i}\sim{\mathcal{N}}(0.5,\frac{1}{36})$. For 1000 iterations, the mask $S$ is iteratively updated to minimize

$$ $\displaystyle\alpha\cdot|f({\bf x})-f_{S}({\bf x})|+(1-\alpha)\cdot|f({\bf x}) -f_{S}({\bf x})|+\lambda_{1}\cdot||S||_{1}+\lambda_{\text{TV}}\cdot||S||_{TV}$ (57) $$

where for any $S$,

$$ $\displaystyle f_{S}({\bf x})=\frac{1}{K}\sum^{K}_{i=1}f((\tilde{{\bf X}}_{S})_ {i})\quad\text{with}\quad(\tilde{{\bf X}}_{S})_{i}={\bf x}\circ\tilde{\mathbbm {1}}_{S}+(1-\tilde{\mathbbm{1}}_{S})\circ b_{i}.$ (58) $$

Here the entries $(\tilde{\mathbbm{1}}_{S})_{i}\sim\text{Bernoulli}(S_{i})$ and $b_{i}$ is the $i$th entry of a vector ${\bf b}=(b_{1},\cdots,b_{d})\sim{\mathcal{V}}$. In our implementation the reference distribution ${\mathcal{V}}$ is the unconditional mean image over the of training images and so $b_{i}$ is the simply the average value of the $i$th pixel over the training set. To allow for differentiation during optimization, we generate discrete samples $\tilde{\mathbbm{1}}_{S}$ using the Gumbel-Softmax distribution. This methodology simply implies the entries $(\tilde{{\bf X}}_{S})_{i}$ is a Bernoulli distribution with outcomes $\{b_{i},x_{i}\}$, i.e. $(\tilde{{\bf X}}_{S})_{i}$ is distributed as

$$ $\displaystyle\Pr[(\tilde{{\bf X}}_{S})_{i}=x_{i}]=S_{i}$ (59) $\displaystyle\Pr[(\tilde{{\bf X}}_{S})_{i}=b_{i}]=1-S_{i}$ (60) $$

For each $\alpha\in\{0,0.5,1\}$, during optimization we set $K=10$, $\lambda_{1}=2$ and $\lambda_{\text{TV}}=20$ and use the Adam optimizer with default $\beta$-parameters of $\beta_{1}=0.9$, $\beta_{2}=0.99$ and a fixed learning rate of 0.1.

#### A.2.2 CelebA-HQ

##### Dataset Details.

We use a modified version of the CelebA-HQ dataset \parenciteCelebAMask-HQ, karras2017progressive which contains 30,000 celebrity faces resized to 256$\times$256 pixels with several landmark locations and binary attributes (e.g., eyeglasses, bangs, smiling).

##### Implementation.

Recall for this experiment, to generate sufficient or necessary masks $S$ for samples ${\bf x}$, we learn a model $g_{\theta}:{\mathcal{X}}\mapsto[0,1]^{d}$ via solving the following optimization problem:

$$ $\displaystyle\underset{\theta\in\Theta}{\text{arg min}}~{}\underset{{\bf X} \sim\mathcal{D}_{\mathcal{X}}}{\mathbb{E}}\left[\Delta^{{\text{uni}}}_{ \mathcal{V}}(g_{\theta}({\bf X}),f,{\bf X},\alpha)+\lambda_{1}\cdot||g_{\theta }({\bf X})||_{1}+\lambda_{\text{TV}}\cdot||g_{\theta}({\bf X})||_{\text{TV}}\right]$ (61) $$

To learn sufficient and necessary explainer models, we solve Eq. 12 via empirical risk minimization for $\alpha\in\{0,1\}$ respectively. Given $N$ samples $\{{\bf X}_{i}\}^{N}_{i=1}\overset{\text{i.i.d.}}{\sim}{\mathcal{D}}_{X}$, we solve

$$ $\displaystyle\frac{1}{N}\sum^{N}_{i=1}\left[\Delta^{{\text{uni}}}_{\mathcal{V} }(g_{\theta}({\bf X}_{i}),f,{\bf X}_{i},\alpha)+\lambda_{1}\cdot||g_{\theta}({ \bf X}_{i})||_{1}+\lambda_{\text{TV}}\cdot||g_{\theta}({\bf X}_{i})||_{\text{ TV}}\right].$ (62) $$

Here

$$ $\displaystyle\Delta^{{\text{uni}}}_{\mathcal{V}}(g_{\theta}({\bf x}_{i}),f,{ \bf x}_{i},\alpha)=\alpha\cdot|f({\bf x}_{i})-f_{S}({\bf x}_{i})|+(1-\alpha) \cdot|f({\bf x}_{i})-f_{S}({\bf x}_{i})|$ (63) $$

where is $f_{S}({\bf x}_{i})$ is evaluated in the same manner as in the RSNA experiment. For $\alpha=0$,
$\lambda_{1}=0.1$ and $\lambda_{\text{TV}}=100$. For $\alpha=1$,
$\lambda_{1}=1$ and $\lambda_{\text{TV}}=10$. For both $\alpha$, during optimization we use a batch size of 32, set $K=10$ and use the Adam optimizer with default $\beta$-parameters of $\beta_{1}=0.9$, $\beta_{2}=0.99$ and a fixed learning rate of $1\times 10^{-4}$

Sampling. To generate the samples in Figs. 4 and 5, samples we use the CoPaint method \parencitezhang2023towards. We utilize their code base and pretrained diffusion models with the exact the same parameters as reported in the paper to perform conditional generation. Everything used is available at [https://github.com/UCSB-NLP-Chang/CoPaint](https://github.com/UCSB-NLP-Chang/CoPaint).

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: Questions:
- Line 89: Is $f(\mathbf{x}_{S}, \mathbf{X}_S)$  a typo? I'd imagine one of them should be from the complement?
- Theorem 4.1 shows existence of $S^{*}$, do you have any theoretical results on uniqueness? Or can there be a unique solution in the first place?
- What happens when $\rho(f(\mathbf{x}) - f_{\emptyset}(\mathbf{x})) < \varepsilon$? (i.e. prediction is close to baseline)

Notes:
- I would suggest following a more standard notation for set complements: $S^\complement$, though I know having a superscript in a subscript may not be ideal
- Figure references in Section 6.2.2 "Sufficiency vs. Necessity" paragraph may be incorrect?
- Line 414: "demonstrateLemma"
- Line 424: $g_{\theta}: \mathcal{X} \to \mathcal{X}$ is a really big typo. Only found out when I looked at A.2.
soundness: 2
strengths: The paper is mostly easy to read, every definition and theorem/results are relevant to the discussion and do not feel like the authors have included them for the sake of including math and notation. I also appreciate the authors for recognizing the need for auxiliary user studies in their limitations to highlight the fact that theoretical desiderata does not necessarily translate to real world impact/performance.
summary: To address vague notions of feature importance in many XAI methods, the paper introduces formal definitions for sufficiency and necessity for local feature-based explanations. The authors further present a unified notion of sufficiency and necessity through a joint convex optimization problem to generate explanations that are both sufficient and necessary. The empirical results show that while existing feature importance methods can identify sufficient features, they fall short in finding necessary features.
weaknesses: Having said that, the paper could improve on a couple of things:
1. Natural language explanation of "sufficiency" and "necessity" in Section 2 (I know this is in the introduction). Since they are the central concepts of the paper, it would be beneficial to really drive home what these mean in plain English for the reader.
2. The experiments section (detailed below)

The experiment setup was difficult to follow, a lot of missing details that I had to assume. For example, I couldn't find what the $L^0$ metric is defined (I am assuming that is the cardinality of the resulting $S$ for each method at thresholds). Similarly, the role of the threshold $t$ was unclear. I am assuming features with attribution/importance higher than $t$ will be included in $S$, but the paper does not explicitly mention that. It might be worth answering what the effect of adjusting $t$ is. 

Moreover, motivation for the tabular dataset experiment is very weak. What is the significance of investigating stability (and a synthetic dataset)? I know in the introduction, the authors ask the question "when do necessary and sufficient sets differ"? Perhaps this is something that the authors should mention in this section too. Note that this is not the case for the image classification experiment, which explicitly outlines its purpose (line 346).

Most importantly, I, as a reader, am unsure of the main takeaway from the experiments apart from the technical contributions of the paper at work. For example, what should we make of the result that necessary explanations are sufficient? This is an important question to answer since the abstract mentions that the paper demonstrates how strictly sufficient and/or necessary explanations fall short in providing a complete picture.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Why did you choose to use marginal distributions in defining sufficiency (L89)? Most literature on sufficient explanations relies on conditional distributions, and even in some experiments, you use conditional distributions.

2.  What advantage does controlling minimality with a parameter like \( \tau \) provide, rather than defining minimal sufficiency directly? Calibrating \( \tau \) could be complex, especially as the existence of solutions for specific \( \tau \) values is uncertain. If this choice were removed, how would it impact your approach?

3. Given the focus on local prediction, why not define necessity as an average out of a subset that diverges significantly from the current prediction of the considered observation (e.g., \(1 - \epsilon\)), instead of using the average prediction? This definition might align more closely with interpreting necessity as the minimal feature set required to maintain the current prediction of the considered observation.

4. In all your results, would it not be necessary first to assume the existence of a solution to the problem given \( \tau \)?

5. Your unifying solution is defined as a combination of sufficient and necessary subsets using weights \( \alpha \) and \( 1 - \alpha \). Why not allow for any convex combination where \( \alpha_1 + \alpha_2 = 1, alpha_1, alpha_2 in (0, 1) \)? Would that significantly impact your results?

### Missing Citation

In your related work on sufficiency, you may want to reference [1], a follow-up to Wang et al. (2021) published at NeurIPS 2022, which proposes a more tractable approach for tree-based models:

> [1]: "Consistent Sufficient Explanations and Minimal Local Rules for Explaining Any Classifier or Regressor," Salim I. Amoukou, Nicolas J.B Brunel, NeurIPS 2022.

I am willing to increase if my questions and weakness comments are addressed.
soundness: 3
strengths: - **Clarity and Novelty**: The paper is well-written and extends existing work with a creative new approach to subset explanations.
- **Theoretical Contributions**: The authors provide a thorough theoretical analysis of their method, detailing its properties and connections to existing notions of feature importance.
- **Empirical Evaluation**: The framework’s applicability is demonstrated through diverse experiments, supporting the practical relevance of the proposed subset explanations.
summary: This paper introduces a novel approach to sufficient and necessary subset explanations, proposing a method to identify subsets along a (symmetric) spectrum of necessity and sufficiency. The authors present theoretical results illustrating the properties of this unified approach and its connections to established importance measures, such as conditional independence and Shapley values. They demonstrate the effectiveness of their approach through experiments on both tabular and image data.
weaknesses: 1. It would be helpful if the main paper, prior to the experiments, provided a more detailed overview of how solutions are computed.

2. In the experiments section, you mention using a relaxed optimization approach for image data. Does this imply that, for tabular data, the exact solution is found by examining all subsets? Additionally, is there any investigation into the guarantees or potential limitations of the relaxed approach compared to the original problem?

3. In the abstract (Line 15), "feature importance" is used to describe sufficient and necessary sets. However, "feature importance" may not be the most precise term for these concepts.

4. The implications of Theorem 5.1 require further elaboration. Comparing different subsets feels akin to comparing different players in different games or players competing in their own games. If I understand correctly, searching within P_{uni} involves finding the feature subset with the highest Shapley Value in its own game, evaluated against its complementary subset. This paragraph could benefit from further clarification to ensure readers fully grasp its significance.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: See above.
soundness: 3
strengths: Interesting and up-to-date topic, well-written paper, thorough experimental study.
summary: The authors consider the problem of feature importance, i.e., quantifying the influence of different input features in the context of supervised learning, which has become quite popular in explainable AI in the recent past. They propose new measures of sufficiency and necessity of feature subsets, as well as a convex combination between the two. They also consider the optimisation problem of finding (small) sufficient/necessary feature subsets.
weaknesses: The first problem I have with this paper is that I find the definition of necessity flawed, or at least not very meaningful. The definition of sufficiency says that a feature subset S is sufficient if the function f projected to S remains eps-close to the original function using all features, which does make sense. Naturally, then, I would have expected that a subset S is called necessary if its complement is not sufficient. At least, this is the common duality between necessity and sufficiency/possibility also found in other branches of the literature (e.g., in modal/possibilistic logic).

Instead, the authors call a subset S necessary if f projected to the complement of S remains close to the default (average) prediction with no features. First, as already said, this does not establish a "duality", but apart from that, this definition is very questionable by itself. It somehow suggests that staying close to the default prediction is something bad, while moving away from it is good. Besides, it also leads to formal problems. For example, suppose that f is indeed a (close to) constant function. Then, according to the definition, all feature subsets are necessary, which is counter-intuitive. 

The pathology outlined in the beginning of Section 4 is also a consequence of the flawed definition, I would say. Here, a feature subset is sufficient, but at the same time, its complement "contains important features". Again, this is completely counter-intuitive. How can a subset be sufficient if it misses important features?

Why is super-sufficiency an interesting property? Isn't it expected that adding more features will keep sufficiency? More interesting would be minimality: S is minimally sufficient if no feature can be removed from S without losing sufficiency. Analogously for super-necessity.

The "unification" is merely a convex combination of the two measures of sufficiency and necessity. Such convex combinations are routinely used in (multi-objective) optimisation, but why should we call them unification? Sure, one obtains both measures as special cases, for alpha=0 and alpha=1, respectively, but then it's more a generalisation than a unification.

The two perspectives in Section 5 are strange and in a sense again somewhat misleading. First, the notion of conditional independence is not defined in the standard way. Normally, conditional independence is a relation on random variables (used in probabilistic graphical models, for example). But why should we speak of conditional independence in the case of (5)?

The connection to the Shapley value is flawed as well. Normally, each feature is treated as a player and assigned a Shapley value. In Theorem 5.1, however, an entire feature subset S is treated as a single player, and its complement as a second player. Why should one consider such a partition as a game, and what does it help? A different game is then needed for every player. How do we connect this to the standard Shapley value? Eventually, with only two player S and S_c, the entire game is specified by the four values v(\emptyset),  v(S), v(S_c), v([d]). These are also the values/approximations looked at in the definition of sufficiency/necessity, so it's not very surprising to find a relationship here.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: - How stable are the retrieved explanations for the image case?

- What does it mean that _one searches for a player with a large lower bound_ in a two player game in practice. Can you put the results regarding the link of $P_{\text{uni}}$ into context. At the moment this connection is made and technically presented. It is not motivated or substantiated, why this is something good/bad or in-between.
soundness: 4
strengths: - **Good Contribution**: While I think the contribution can be strengthened (see weaknesses), the presented approach is very interesting. Joining and optimizing both conditions leads to very interesting explanations, which seem to be not retrievable by other methods. The work is sound and carried out well.

- **Theoretical Connections to Game Theory**: The paper connects the novel optimization problem $P_{\text{uni}}$ with well-established concepts like the Shapley value. While I think the discussion and interpretation is under-developed (see weaknesses) this connection can have impact on the line of research regarding Shapely values and hierarchical explanations.

- **Synthetic Experiments**: I like that the paper studies the approach in synthetic environments! This is often not done anymore and can be very insightful of what the method is actually doing. The paper studies the stability of the method in this setting, which is good but leaves more to be desired.

- **Well written and structured**: The paper is clearly structured and reads well. Particularly, the related work section is very strong.
summary: The paper proposes to merge _sufficency_ and _necessity_ notions into one unified optimization problem $P_{\text{uni}}$ and solving this combined optimization problem. Therein, the paper is interesting and shows that this unified approach retrieves explanations unlike baseline methods.
weaknesses: I think this paper **is borderline**: The paper feels a lot about the _what_ is being done, and not really about the _why_ this may be useful. The paper does not really motivate the use of $P_{\text{uni}}$ outside of the image domain and would benefit a lot from a wider evaluation in different domains such as language and tabular and the interesting insights that can be generated there.

- **Limited Contribution**: The contribution of this paper is rather incremental in nature. The notions of _sufficiency_ and _necessity_ are quite established concepts. Here they are just added together (with a linear combination) and jointly optimized for. While the paper does make interesting findings because of this combined lens (see strengths). It falls short in motivating and placing the contribution well into the XAI research. It is unclear when from an XAI perspective this joint approach is superior to other techniques. The conducted experiments seem rather exemplary than confirmatory in this regard. Only a small selection of created images are presented **without** examples for the baseline explanation methods this work compares against. The contribution could be strengthened by providing a broader comparison in different domains and actually showing how the explanations of other methods differ with the the new perspective.

- **Doubt about the stability**: The experiments in the work show that sufficiency and necessity optimized together can lead to interesting insights. However, a critical aspect of retrieving these explanations is by optimizing ($P_{\text{uni}}$) in some form. This is again intractable like solving ($P_{\text{suf}}$) and ($P_{\text{nec}}$). The authors acknowledge this fact (line 215, footnote 1). However, the authors point to two references where one is un-published work (Kolek et al. 2021), and other is a workshop article (Kolek et al. 2022). This makes me doubt that the retrieved solutions to ($P_{\text{uni}}$) are easily retrievable for various models and feature spaces. Neither the paper nor the appendix discusses this issue further. While Experiment 6.1 is concerned with this fact, stability is evaluated only on a synthetic or tabular example with low feature dimensionality. While the remainder of the paper deals with image explanations, which seems to be the main motivation for this work, the stability is left undiscussed. 

- **Synthetic Setting is misused**: Given the above point stability is more interesting in higher-dimension settings (images, etc.). The synthetic environment would greatly benefit a _comparative study_ with other explanation methods. It would be interesting to see **how baselines fall short and be able to explain why** and then to show how the unification does not. This is in the current draft not done (also not in the exemplary setting of image explanations).

- **The Shapley-Perspective is Disconnected**: While I am glad about theoretical results linking this approach to game theoretic foundations (see strengths), Section 5.2 (connection of this method and Shapley) is quite disconnected to the rest of the paper. The results are presented technically but not put into context.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. The proposed computation methods in Section 6.2. How well do they approximate the actual target? Could you do this analysis in a lower-dimensional setting, where ground-truths can be computed?
2. Do you have any insights on the method compared to the actual Shapley values of the model?
3. For the comparison of post-hoc explainability methods, what is the effect of the normalization? Is it negligible? Most methods already decompose the model's prediction, wouldn't it be sufficient to divide the attributions by the model's prediction to obtain normalized scores? Why don't you rely on the ranking of the attributions directly using $\tau$?
4. Is super-necessary and super-sufficient actually observed in practice? It seems counter-intuitive to me. For instance, for images, unmasking some parts of the image could lower the prediction significantly, since they could reveal a novel concept or another concept that contains the previously predicted concept.
5.  The purpose of the metric $\rho$ is unclear to me. It seems more intuitive to me to consider the model's output directly. What is the benefit of using the metric $\rho$? Why don't you use the model output directly, which is the common choice for local explanations? For necessary explanations, this also seems somewhat problematic: Consider a binary prediction, where the prediction is $\approx 1$, and the average prediction $f_\emptyset \approx 0.5$. Masking some features could substantially change the model's prediction to the opposite class, which would be captured with sufficient explanations. However, for necessary explanations, this would yield a similarly unsatisfying result (high $\Delta^{nec}), since the opposite class (prediction $\approx 0$) is equally far from the average prediction. Is this behavior intended? What is the reasoning behind it?
6. In Section 6.2. what are the resulting sizes of explanation sets that you find? Could you give some statistics on these for the datasets? Do you consider these sizes also in the comparison with post-hoc attribution methods? If so, in which way are they accounted for? E.g. I would expect to choose attributions of features such that the number matches with $\tau$?

**Minor**
- typo line 414, missing blank after "demonstrate"
- in Appendix A, the navigation displays "Proof of Theorem 6.1", while the section title is correctly referring to Theorem 5.1.
soundness: 2
strengths: 1. The proposed necessary and sufficient explanations are an intriguing concept that complements existing approaches, such as the Shapley value that summarize "average contributions". Enriching the toolbox of interpretability methods with simple concepts is an important extension of existing work.
2. The paper is well-written, all theoretical claims are precisely stated and formally proven. The intuition behind the concepts are clear.
3. The proposed approximation method for image classification is interesting, but not sufficiently evaluated.
4. A first attempt to link the novel concepts to game-theoretic measures, such as the Shapley value, is promising.
summary: This paper proposes a novel measure to interpret predictions of black box machine learning models. Given a masking strategy for a model the authors define $\epsilon$-sufficient feature sets as sets whose masked prediction (mask= complement of S) deviates at most $\epsilon$ of the actual prediction with respect to some metric $\rho$ (deviation=$\Delta^{suf}$). In contrast, $\epsilon$-necessary feature sets are sets, where the masked prediction (mask=S) deviates at most $\epsilon$ from the fully masked prediction w.r.t $\rho$ (deviation=$\Delta^{nec}$). Given these notions, the authors aim to find the set $S$ with the smallest deviations. Instead of solving each problem individually, the authors propose to find a set that minimizes the weighted average $\Delta^{uni} := \alpha \Delta^{suf} + (1-\alpha) \Delta^{nec}$ with a hyper-parameter $0\leq \alpha \leq 1$, which they term "unified" problem, where the edge cases are the individual problems. The problem is further constrained, by finding a set with cardinality at most $\vert S \vert \leq \tau$. The main theoretical contribution is Theorem 4.1 that states the existence of $S$ with sufficiently small $\Delta^{uni}$, given sufficient and necessary solution and additional assumptions. Moreover, the solution satisfies conditional independence, if $f$ models the data-generating process (Corollary 5.1). Lastly, it is shown (Theorem 6.1) that the Shapley value of S treated as a joint player in the two-player game with S, [d]/S is bounded from below by $\Delta^{uni}$. In the experiments, the proposed is evaluated for different hyperparameter configurations on tabular data (6.1) and for image classification (6.2). For the restrictive setting in image classification, the authors propose an optimization objective that solves a relaxed version, which is specific to image classification, since exactly computing the objective is NP-hard. The authors conclude that the two proposed notions identify distinct aspects of predictions, which is showcased on examples for image classification.
weaknesses: 1. **Limited discussion on computational aspects:** The paper introduces two interesting concepts, but the main limitation in practice is the optimization problem, which optimizes over all possible subsets (2^d), similar to the Shapley value. For the Shapley value, however, there exist efficient approximation techniques by evaluating the target for a collection of sampled subsets, which are unbiased and known to converge. In contrast, in Section 6.2 the authors propose approximation strategies for which no theoretical guarantees are given. The paper would highly benefit from such theoretical guarantees and a general approximation approach. Moreover, for the given applications, it should be carefully evaluated why these approximations yield appropriate solutions (see Q1 below).
2. **Limited link to other concepts:** Theorem 5.1 is a first step towards understanding connections to other methods, such as the Shapley value. However, this result is quite limited, since it considers a drastically reduced game of two players, instead of $d$ players, which does not give insights into the actual Shapley values that are usually computed for interpretability. The paper would strongly benefit from establishing such connections more carefully (see Q2 below), in particular given the claims made in the abstract.
3. **Comparison with existing attribution methods:** The authors claim that necessary and sufficient explanations yield more insights into explanations, which are undermined by some interesting examples in image classification. It remains unclear, how these methods compare to existing attribution methods. For instance, it would be helpful to formally state the difference between these concepts and carefully evaluate empirically which questions can be answered by the novel concept, which could not be targeted with existing methods. Moreover, some choices in the comparison are unclear to me (see Q3 below).
4. **Theorem 4.1:** The key assumption here is super-sufficient and super-necessary. I am not convinced that these properties are given in real-world examples (see Q4 below).
5. **Hyperparameters:** The method requires two hyperparameters $\alpha$ and $\tau$, which need to be chosen in advance, and have a high impact on the explanations, as shown by the experiments. It remains unclear how to choose these parameters in practice. It would be helpful to understand these choices better with sensible defaults.