Sufficient and Necessary Explanations (and What Lies in Between)

Concern 1: Limited discussion of computational aspects

We thank the reviewer for the constructive comments. While it is true that the optimization problem is not tractable, we want to stress a couple of points:

1. Our contribution is not a tractable relaxation that identifies sufficient and/or necessary subsets. Instead, we provide precise and flexible notions of sufficiency and necessity, and bring to attention that these notions do not provide a complete picture of feature importance. To demonstrate our theoretical results in practice, we relied on computational methods that are already well-known in the literature [1,2,3,4].

2. Note that while the optimization problem may be intractable, the evaluation of $\Delta_{suf}, \Delta_{nec},$ and $\Delta_{uni}$ is not. Thus, we can still use these notions to evaluate how sufficient or necessary the explanations generated by different methods are. This allows us to provide a relative ranking of which method provides the best explanations in terms of sufficiency or necessity, which was not possible prior to our contribution.

Your point is well-taken, however, and we will expand on the limitations of the computational aspects of solving the proposed problems in the revised manuscript.

[1] "Interpretable Explanations of Black Boxes by Meaningful Perturbation," Ruth Fong, Andrea Vedaldi, ICCV 2017 [2] "Understanding deep networks via extremal perturbations and smooth masks," Ruth Fong, Mandela Patrick, Andrea Vedaldi, ICCV 2019 [3] "Cartoon explanations of image classifier," Stefan Kolek, et. al. ECCV 2022 [4] "Model Interpretability and Rationale Extraction by Input Mask Optimization," Marc Brinner, ACL 2023

Concern 2: Limited link to other concepts

First, we apologize if the claims in the abstract were misleading. Theorem 5.1 does establish a connection between the unified problem and the Shapley value, albeit for a two-player game. The reviewer is correct that is different from the way Shapley coefficients are typically used for approximating important features, but this does provide a connection between game-theoretic quantities and necessity/sufficiency methods which was unknown before. We do not find this different necessarily limiting, but rather a simpler and clearer picture of feature importance. By considering a subset $S \subseteq [d]$ and its complement $S^c$, we are simply differentiating the important features from those that are not.Moreover, note that the feature scores obtained with traditional methods (including via Shapley) are often (though not always) thresholded to differentiate between important and important features. Our formulation addresses this case.

The comment is well-taken, and we will clarify these differences.

Concern 3: Comparison with existing attribution methods

We believe our empirical results do make a precise comparison of how different notions of importance differ. In particular:

1. We show that necessary and sufficient need not be the same, but that they are related. In particular, we show in the two image classification settings that the sufficient explanations are subsets of the necessary ones.

2. We show that common post-hoc methods fail in retrieving necessary features, and most simply estimate (approximately) sufficient ones (see the RSNA and CelebAHQ experiments).

3. We show that our notions do allow for solutions that balance the trade-off between these notions of importance (portrayed in the tabular examples).

Concern 4: Theorem 4.1 assuming super sufficiency/necessity

Thank you for this comment. While super-sufficiency and super-necessity will not always hold in every scenario, they are not as strict as they seem. Super-sufficiency simply states that, given sufficient set (e.g. a region of an image), this set is super-sufficient if supersets of it are also sufficient. This indeed holds in the examples we provide: the brain CT scans and CelebAHQ. For the CT scans, once we fix a region with at least one hemorrhage, any larger region that contains this hemorrhage will be sufficient for predicting the label. Similarly in the CelebAHQ example, once ones fixes the region of the image that contains the smile, every superset of this region still allows the predictor to predict smile as expected. One can reason similar situations for the super-necessary settings: given a necessary set in the brain CT examples that contains all of the hemorrhages present in an image (i.e. a necessary set), any super-set of it will also be necessary.

We hope these clarify our notions of super necessity and sufficiency, but we'd be happy to clarify further.

Concern 5: Hyperparameters

Thanks for bringing this up. We stress that, unlike other problems where the hyperparameters are hard to interpret, both $\alpha$ and $\tau$ have precise meanings: the former controls the trade-off between sufficiency and necessity of the solution, whereas the latter determines the size of the reported features. As a result, there is no ``correct'' choice for these, but rather the choice should be determined by the specific problem domain or user preferences. For instance, if one is after a sufficient explanation, then $\alpha = 1$ is the correct choice -- correspondingly, $\alpha=0$ ensures a necessary one. We demonstrate, through theory and examples, that sufficient explanations may not capture necessary ones and vice versa. As a result, if one wishes to capture all such features, then $\alpha = 0.5$ is the appropriate choice.

We will expand on this rationale in our revised version -- thanks for the comment!

Concern 6: Purpose of metric $\rho$

Thank you for this question, from which we identify two key components: one pertains to the choice of requiring $f_S(x)$ to be close to either $f(x)$ or $f_\emptyset$ (for sufficient or necessary features, resp.) instead of being close to 1 or 0 (analogous to the reviewer's suggestion of using ``using the model output directly''); the second pertains to the choice of the general metric $\rho$.

For the former: we argue that measuring the distance of the expected perturbed function $f_S(x)$ with respect to the canonical choices of $f(x)$ and $f_\emptyset$ is more general. Consider the case of searching for sufficient features, and consider as an example, the case where $f(x) = 0.9$. Searching for a predictor $f_S(x)\approx 1$ (rather than one for which $f_S(x)\approx f(x)$ might provide features that are not sufficient for the predictor $f$ to produce the output $f(x)$ (only sufficient for producing $f_S(x)\approx 1$. This difference can be particularly important in cases where the predictions of $f(x)$ are calibrated, and thus their specific values carry specific meanings that we want to account for. Likewise, for necessary features, note that requiring $f_{S^c}(x)\approx 0$ instead of $f_{S^c}(x)\approx f_\emptyset$ (say, $\approx 0.5$) will result in a subset $S^c$ that is (on average) sufficient for predicting $f_{S^c}(x)\approx 0$ instead of necessary features for $f(x)$. This would result in features that are closer to counter-factual notions of explanations. Our notions, instead, simply require necessary features to be those without which the prediction is no better than a random guess.

Lastly, we use a general metric $\rho$ to accommodate different prediction settings: a regression task, an $\ell_2$ norm might be appropriate, whereas in a multi-class classification settings the difference in maximum scores might be better suited, etc.

Concern 7: Questions about section 6.2

Thanks for bringing this up, as we realize that this could have been presented more clearly. As we comment on Sec. 6.2, and to ensure a consistent analysis, we first normalize all generated attribution scores to the interval $[0,1]$, and then obtain different important features by thresholding the scores at different values in $(0,1)$. Each threshold results in a generated explanation with a specific cardinality, or size (which is a monotonically decreasing function of the threshold). As can be seen in Fig. 2(a) and Fig(3), our results are provided as a function of this threshold (i.e. for all choices of this parameter), and we further include the sizes of the reported features by reporting $-\log(L^0)$, where $L^0$ refers to the (relative) cardinality of the reported features. As a result, this provides a complete picture that allows us to compare these methods for any value of $\tau$ (i.e. for any size of the reported important features).

Thanks for the reply! Here are our responses to your comments/concerns.

Comparisons

We have added an additional synthetic experiment where ground truths can be computed, and extensive comparisons can be made. The details are below.

The experiment is the following:

We model features $X \in \mathbb{R}^7$, where $X_i \sim \mathcal{N}(\mu_i, \sigma_i^2)$ for $i \in \set{1, 4, 5, 6, 7}$. The remaining features and response $Y$ follow:

where $\epsilon \sim \mathcal{N}(0, 1)$. For $X \in \mathcal{G}:= \set{X \mid X_2 > 10, ~X_4 > 0.5}$, the data-generating process is represented by the directed acyclic graph (DAG) shown below

with $X_5, X_6, X_7$ not connected to any variables. From the DAG, we can see that $Y \perp X_{\{1,5,6,7\}} | X_{2,3,4}$ and $Y \perp X_{\{4,5,6,7\}}$. Thus, for $f(X) = E[Y \mid X]$ and $V_{S} = p(X_{S^c} \mid x_S)$, the solutions to $P_{suf}$, $P_{nec}$, and $P_{uni}$ with $\tau = 4$ are:

In this experiment, we train a general predictor (a three-layer fully-connected neural network) to approximate $E[Y \mid X]$ and 1) validate that the sets listed above are the optimal solutions, and 2) demonstrate that common post-hoc interpretability methods do not recover these any of these sets.

Unfortunately, we cannot send figures through this forum, but we highlight the main takeaways from the experiments, and we’ll include the figures in the supplementary material.

Validating the solutions

For $type \in \set{suf, nec, uni}$, $\tau = 4$, and 100 samples $x \in \mathcal{G}$, we compute solutions, denoted as $\hat{S}_{type}$ to the sufficiency, necessity, and unified problem. We find that:

1. For $\approx$ 95% of the samples in $\mathcal{G}$, $\hat{S}_{suf} = \set{1,2,3}$, the solution to the sufficiency problem.
2. For $\approx$ 60% of the samples in $\mathcal{G}$, $\hat{S}_{nec} = \set{2,3,4}$, the solution to the necessity problem.
3. For $\approx$ 92% of the samples in $\mathcal{G}$, $\hat{S}_{uni} = \set{1,2,3,4}$, the solution the unified problem.

These results indicate that the solutions computed via an exhaustive search do typically retrieve the correct solutions (the minor discrepancies are due to $f(X)$ being an approximation of $E[Y|X]$). More importantly, this setting is a clear example of when one would not be able to identify the set $S = \set{1,2,3,4}$ as the most important one unless you directly solve the unified problem.

Comparison with other methods

For our model $f$ and 100 samples $x \in \mathcal{G}$, we use Integrated Gradients, Gradient Shapley, DeepLift, and Lime to generate attribution scores. To identify whether these methods highlight sufficient and/or necessary features, and as done before in our manuscript, we perform the following steps on the attribution scores for a sample $x$ (so that the outputs of all methods are comparable)

1. We normalize the scores to the interval [0,1] via min/max normalization.
2. We generate binary masks $S_t$ by thresholding the normalized scores with thresholds $t \in (0,1)$.
3. For $type \in \set{suf, nec, uni}$, we compute $H(S_t, S^*_{type})$, the hamming distance between $S_t$ and the true solutions to $P_{suf}$, $P_{nec}$, and $P_{uni}$

The main results from our analysis are the following:

1. There is no threshold in $t \in (0,1)$ for which any method recovers the true solution to $P_{suf}$, $S_{suf}^* = \set{2,3,4}$. Furthermore, for $t > 0.1$ the average hamming distance, $H(S_t, S^*_{suf})$, is $> 1$ for all methods, indicating that $S_t$ and $S_{suf}^*$ disagree by at least one element.

2. There is no threshold in $t \in (0,1)$ for which any method recovers the true solution to $P_{nec}$, $S_{nec}^* = \set{1,2,3}$. In fact for $t > 0.6$, the average hamming distance $H(S_t, S^*_{nec})$, is $> 2$ for all methods, indicating that $S_t$ and $S_{suf}^*$ disagree by at least 2 elements.

3. For $t \approx 0.05$, integrated gradients and deeplift recover the true solution to $P_{uni}$, $S_{uni}^* = \set{1,2,3,4}$. However, for $t > 0.1$, the average hamming distance $H(S_t, S^*_{uni})$, is $> 2$ for all methods, indicating that $S_t$ and $S_{suf}^*$ disagree by at least 2 elements.

We are in the middle of finishing this experiment, adding comparisons to the Shapley value, and updating the manuscript. We hope that the experiment and its results adequately address your concerns.

Metric

In the reviewer's example, set S is indeed more necessary than set T. We don't see any conflict between this and f_{S^c} < 0.5. Could the reviewer clarify why this is a concern?

Super-sufficiency/necessity

We provided weak evidence where super-sufficiency holds; e.g., any set that includes a brain hemorrhage in a CT scan will be super-sufficient for a 'good' predictor. However, we want to stress that these properties hold for a large class of data-generating processes. For example, they hold for distributions over $(X, Y)$ that can be modeled with a Markov Random Field. If the process can be expressed with a Markov Random Field, then the smallest $S_{suf}$ will be the parents of Y, and the smallest $S_{nec}$ will be all variables connected that have a path to $Y$. For example, consider

X1 — X2 —Y — X3— X4

X5 X6 X7

Here $S_{suf} = \set{2,3}$ and $S_{nec} = \set{1,2,3,4}$. From this, it’s clear that adding any additional elements to $S_{suf}$ or $S_{nec}$ retains the sufficiency/necessity. Thus, super-sufficiency/necessity holds. Markov random fields appear in many real-world applications such as imaging, social network analysis, and genomics [1,2,3]. Thus, there are many real-world settings where super-sufficiency/necessity indeed holds.

[1] Markov random field modeling in image analysis, Stan Z. Li Springer 2009

[2] A network-specific Markov random field approach to community detection, Dongxiao He et al. AAAI 2018

[3] A Markov random field model for network-based analysis of genomic data, Zhi Wei, Honghze Li, Bioinformatics 2007

Concern 1: Limited contribution

We thank the reviewer for voicing their concerns. We believe this work does provide a meaningful contribution to the XAI community for the following reasons:

• While previous works have established certain notions of sufficiency and necessity, we introduce a definition of necessity that is different and--we argue--that better reflects what necessity should mean (see global comment that elaborates on this).
• Importantly, we demonstrate that sufficient and necessary explanations need not be the same, but they are related (their intersection is not empty). This observation is what motivates the unified approach.
• In all previous works, it remained unclear how exactly these notions of sufficiency and necessity relate to other notions of importance, such as conditional independence and Shapley values. We provide theoretical results that provide precise relations between these seemingly different perspectives
• Lastly, through various experiments, we demonstrate how generating explanations along the necessity-sufficiency axis 1) allows us to detect important features that may otherwise be missed and 2) conclude that many post-hoc methods fall on the sufficiency side of this axis.

We do apologize that these contributions were not clearly presented in the paper. In the revised version we will make these points clear.

Concern 2: Doubt about stability

We appreciate the comment. We agree that it is critical to optimize $P_{uni}$ in a manner that leads to efficient and stable solutions. The methods we employ are well-established in the literature [1,2,3,4] leading to solutions that are good and stable in practical settings spanning image and natural language settings. We apologize for not making this clear in the original version. We will address in the revised version by making this statement clearer in a new section before the experiments.

[1] "Interpretable Explanations of Black Boxes by Meaningful Perturbation," Ruth Fong, Andrea Vedaldi, ICCV 2017 [2] "Understanding deep networks via extremal perturbations and smooth masks," Ruth Fong, Mandela Patrick, Andrea Vedaldi, ICCV 2019 [3] "Cartoon explanations of image classifier," Stefan Kolek, et. al. ECCV 2022 [4] "Model Interpretability and Rationale Extraction by Input Mask Optimization," Marc Brinner, ACL 2023

Concern 3: Synthetic setting is misused

Thanks for the comment. In the synthetic example, we focused on how the optimal feature set $S$ changes as a function of $\alpha$ with $\tau$ held constant, rather than comparing the solutions with other explanation methods (which do not depend on these parameters). Instead, we compare to other methods in more real and high-dimensional problems, including images. There, we indeed study how sufficient and necessary the ``important features'' provided by the different methods are by measuring their respective $\Delta_{suf}, \Delta_{nec}$ and $|S|$.

Concern 4: Shapley-perspective is disconnected

We are glad the reviewer enjoys the theoretical result of Theorem 5.2. The purpose of Theorem 5.2 is to motivate why minimizing $\Delta_{\uni}$ is a good idea at all, and we see our theoretical result as one such important justification. We agree with the reviewer that this was perhaps not clear enough, and we will make sure to stress it in revision.

Regarding the implication and meaning of the result, consider the following.

Denote $\Lambda_d = \{S, S^c \}$ the partition of $[d] = \{1, 2, \dots, d\}$ into two disjoint subsets, and define the characteristic function to be $v(S) = -\rho(f(x), f_{S}(x))$. Then, the following result holds.

Recall that a cooperative game is specified by a tuple $(\Lambda_d = \{S, S^c \}, v)$ and since $[d]$ can be partitioned into 2 sets $2^{d-1}$ ways, there are $2^{d-1}$ potential games. For every game, the Shapley value assigns an importance score to each of the two players (i.e. partitions) in a way that is fair (and satisfies other axiomatic properties). Note that the inequality above holds for all games; i.e. for all partitions of $[d]$. Thus, in solving for the $S$ with minimal $\Delta_{\text{uni}}$, one is identifying the game $(\Lambda_d = \{S, S^c \}, v)$ in which $S$ has the largest lower bound on its Shapley value. This result is interesting because it motivates minimizing $\Delta_{\text{uni}}$ through a game-theoretic interpretation: this is equivalent to selecting the game between players that maximize their difference of Shapley values.

We hope this clarifies the result, and provide a stronger motivation to the story in manuscript. We will stress on this clarification in the revised manuscript!

Missed opportunity with synthetic experiments

To address this concern, we conducted a new synthetic experiment which we strongly believe highlights: 1) when/how solutions to the sufficiency, necessity, and unified problems differ, and 2) how current post-hoc methods fail to identify features that are sufficient and/or necessary.

The experiment is the following:

We model features $X \in \mathbb{R}^7$, where $X_i \sim \mathcal{N}(\mu_i, \sigma_i^2)$ for $i \in \set{1, 4, 5, 6, 7}$. The remaining features and response $Y$ follow:

where $\epsilon \sim \mathcal{N}(0, 1)$. For $X \in \mathcal{G}:= \set{X \mid X_2 > 10, ~X_4 > 0.5}$, the data-generating process is represented by the directed acyclic graph (DAG) shown below

with $X_5, X_6, X_7$ not connected to any variables. From the DAG, we can see that $Y \perp X_{\{1,5,6,7\}} | X_{2,3,4}$ and $Y \perp X_{\{4,5,6,7\}}$. Thus, for $f(X) = E[Y \mid X]$ and $V_{S} = p(X_{S^c} \mid x_S)$, the solutions to $P_{suf}$, $P_{nec}$, and $P_{uni}$ with $\tau = 4$ are:

In this experiment, we train a general predictor (a three-layer fully-connected neural network) to approximate $E[Y \mid X]$ and 1) validate that the sets listed above are the optimal solutions, and 2) demonstrate that common post-hoc interpretability methods do not recover these any of these sets.

Unfortunately, we cannot send figures through this forum but we highlight the main takeaways from the experiments, and we’ll include the figures in the supplementary material.

Validating the solutions

For $type \in \set{suf, nec, uni}$, $\tau = 4$, and 100 samples $x \in \mathcal{G}$, we compute solutions, denoted as $\hat{S}_{type}$ to the sufficiency, necessity, and unified problem. We find that:

1. For $\approx$ 95% of the samples in $\mathcal{G}$, $\hat{S}_{suf} = \set{1,2,3}$, the solution to the sufficiency problem.
2. For $\approx$ 60% of the samples in $\mathcal{G}$, $\hat{S}_{nec} = \set{2,3,4}$, the solution to the necessity problem.
3. For $\approx$ 92% of the samples in $\mathcal{G}$, $\hat{S}_{uni} = \set{1,2,3,4}$, the solution the unified problem.

These results indicate that the solutions computed via an exhaustive search do typically retrieve the correct solutions (the minor discrepancies are due to $f(X)$ being an approximation of $E[Y|X]$). More importantly, this setting is a clear example of when one would not be able to identify the set $S = \set{1,2,3,4}$ as the most important one unless you directly solve the unified problem.

Comparison with other methods

For our model $f$ and 100 samples $x \in \mathcal{G}$ we use Integrated Gradients, Gradient Shapley, DeepLift, and Lime to generate attribution scores. To identify whether these methods highlight sufficient and/or necessary features, and as done before in our manuscript, we perform the following steps on the attribution scores for a sample $x$ (so that the outputs of all methods are comparable)

1. We normalize the scores to the interval [0,1] via min/max normalization.
2. We generate binary masks $S_t$ by thresholding the normalized scores with thresholds $t \in (0,1)$.
3. For $type \in \set{suf, nec, uni}$, we compute $H(S_t, S^*_{type})$, the hamming distance between $S_t$ and the true solutions to $P_{suf}$, $P_{nec}$, and $P_{uni}$

The main results from our analysis are the following:

1. There is no threshold in $t \in (0,1)$ for which any method recovers the true solution to $P_{suf}$, $S_{suf}^* = \set{2,3,4}$. Furthermore, for $t > 0.1$ the average hamming distance, $H(S_t, S^*_{suf})$, is $> 1$ for all methods, indicating that $S_t$ and $S_{suf}^*$ disagree by at least one element.

2. There is no threshold in $t \in (0,1)$ for which any method recovers the true solution to $P_{nec}$, $S_{nec}^* = \set{1,2,3}$. In fact for $t > 0.6$, the average hamming distance $H(S_t, S^*_{nec})$, is $> 2$ for all methods, indicating that $S_t$ and $S_{suf}^*$ disagree by at least 2 elements.

3. For $t \approx 0.05$, integrated gradients and deeplift recover the true solution to $P_{uni}$, $S_{uni}^* = \set{1,2,3,4}$. However, for $t > 0.1$, the average hamming distance $H(S_t, S^*_{uni})$, is $> 2$ for all methods, indicating that $S_t$ and $S_{suf}^*$ disagree by at least 2 elements.

We are currently in the middle of updating the manuscript to include this experiment, but we hope that the experiment and the results adequately address your concerns. Thank you so much for engaging with us, and we look forward to hearing if this clarifies your concerns.

Concern 1: Flawed definition of necessity

We appreciate the comments. If we understand correctly, the reviewer is saying that

1. Our notion of sufficiency is appropriate, i.e. $S$ is $\epsilon$- sufficient if $\rho(f(x), f_S(x)) \leq \epsilon$.
2. Given this notion of sufficiency, necessity should be defined by saying that $S$ necessary if its complement is not sufficient, i.e $f(x) \neq f_{S^c}(x)$. Or, formalizing this a little, the reviewer's proposal is that $S$ is $\epsilon$-necessary if $\rho(f(x), f_{S^c}(x)) \geq 1-\epsilon$.

First, we note that our definition of necessity implies the one suggested by the reviewer: if $\rho(f(x_{S^c}), f_{\emptyset}(x)) \leq \epsilon$ then $\rho(f(x), f(x_{S^c})) > 1-\tilde{\epsilon}$ where $\tilde{\epsilon} = 1 - (\rho(f(x), f_{\emptyset}(x)) - \epsilon)$. This is not surprising because if $f_{S^c}(x)$ is close to $f_{\emptyset}(x)$, then it is far from $f(x)$ as long as $f(x)$ and $f_{\emptyset}(x)$ are different.

Second, and more broadly, the reason we define the sufficiency and necessity of $S$ using the quantities $\rho(f(x), f_S(x))$ and $\rho(f_{S^c}(x), f_{\emptyset})$ is because we want our notions to reflect the natural idea that, among all subsets $S \subseteq [d]$, the complete set $S = [d]$ should be the maximally sufficient and necessary subset. This is indeed the case with our definitions: for $S = [d]$, $\rho(f(x), f_S(x)) = \rho(f(x), f_(x)) = 0$ and $\rho(f_{S^c}(x), f_{\emptyset}(x)) = \rho(f_{\emptyset}(x), f_{\emptyset}(x)) = 0$ and so $[d]$ is $0$-sufficient and necessary as desired.

We hope this clarifies why we define sufficiency and necessity in this specific way, and we'd be happy to elaborate further.

Concern 2: Flawed definition of sufficiency

Thank you for this comment. We respectfully disagree, and we believe that there is a simple example that demonstrates that there is no contradiction in having two disjoint minimal sufficient features: Consider a scenario where the label is determined by the presence of certain features (as it happens in the brain CT example in our experimental section, Sec. 7): the presence of any individual hemorrhage in the scan is sufficient to classify the scan as "positive". Assume there are two hemorrhages in the scan, $S_1$ and $S_2$, each of ``size'' of $|S_1| = |S_2| =k$ pixels (for simplicity of the argument). Then, any one of them individually is the smallest sufficient subset (of size $k$); i.e. $f_{S_1}(x) \approx f_{S_2}(x) \approx f(x)$. The same is true in many other settings where the presence of certain features determines the outcome of the task. Thus, in general, there is no reason why features in the complement of minimal sufficient ones can't provide useful information.

We hope this clarifies the confusion, and we'd be happy to elaborate further.

Concern 3: super sufficiency/necessity

While not immediately obvious, one can verify that super-sufficiency does not always hold, as conditioning on a superset of a sufficient region can significantly alter predictions. For example, a predictor might classify a small fur region of a dog image as a bear, but will eventually change towards predicting the presence of a dog as the region grows and reveals other dog-like features.

On the other hand, we indeed address the minimality of both sufficiency and necessity through the parameter $\tau$, which controls the size of feature subsets. Smaller $\tau$ emphasizes identifying the smallest sufficient and necessary sets.

Concern 4: Use of "unification"

This is valid point. We find the term "unified" appropriate because as the reviewer states, our formulation is a combination of sufficiency and necessity. Indeed, there's nothing particularly revolutionary about this convex combination of both objectives. We'd be happy to rename the resulting problem if the reviewer has a specific suggestion in mind!

Concern 5: Confusion with conditional independence perspective

Thanks for bringing up this point. The reviewer is correct that conditional independence is a relation on random variables. To be precise for $Y, X_{S},$ and $X_{S^c}$, $Y$ is independent of $X_{S^c}$ conditional on $X_S$ if, for all values of $Y, X_{S}, X_{S^c}$, we have $p(Y | X_{S}, X_{S^c}) = p(Y|X_{S})$. Informally, our result states that

Since this result pertains to conditional expectations for a fixed realization of $x$, this is a local conditional independence relation on means. However, it is still a conditional independence relation, albeit weaker than the standard notions. We apologize for loosely using the term conditional independence, which we will correct in the revised version.

Concern 1: Detailed overview of how solutions are computed

We agree with the reviewer. In the revised manuscript, we will include a section before the experiment that details how approximate solutions are computed.

Concern 2: Solutions for tabular vs. image settings

To answer the first question, the reviewer is correct. In the tabular example, exact solutions were identified by examining all subsets of a fixed cardinality $\tau$. For the second question, the relaxed approaches we use are slight variations of methods introduced in [1,2,3,4]. None of these works provide any theoretical guarantees but the methods have been demonstrated to work well in practice. The main benefit of the relaxed approach is that it is tractable since it allows for the use of gradient based methods for optimization. We will definitely include a section before the experiments that comment on the these approaches and their benefits/limitations.

[1] "Interpretable Explanations of Black Boxes by Meaningful Perturbation," Ruth Fong, Andrea Vedaldi, ICCV 2017 [2] "Understanding deep networks via extremal perturbations and smooth masks," Ruth Fong, Mandela Patrick, Andrea Vedaldi, ICCV 2019 [3] "Cartoon explanations of image classifier," Stefan Kolek, et. al. ECCV 2022 [4] "Model Interpretability and Rationale Extraction by Input Mask Optimization," Marc Brinner, ACL 2023

Concern 3: Abstract line 15

Thank you for pointing this slight issue. We have reworded the abstract as follows:

"To address this, we introduce and formalize two precise concepts—sufficiency and necessity—that characterize how sets of features contribute to the prediction of a general machine learning model."

We think it is more useful to measure the sufficiency and necessity of sets of features (rather than the importance scores of individual features) because in most settings a single feature does not contributes to a prediction (most notably, in the case of images). In reality, models often use sets of features (that may interact synergistically) to generate a prediction. We hope the reviewer finds this edit more precise, which we have incorporated to our revised version.

Concern 4: Implications of Theorem 5.1

We appreciate the comment, and we will further elaborate on Theorem 5.1. In short, the reviewer is correct. 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(x), f_{S}(x))$. Then, the following result holds.

A cooperative game is specified by a tuple $(\Lambda_d = \{S, S^c \}, v)$ and since $[d]$ can be partitioned into 2 sets $2^{d-1}$ ways, there are $2^{d-1}$ games. For every game, the Shapley value assigns an importance score to each of the two players in a way that is fair and satisfies other desirable properties. For each game, the above inequality holds. Thus, a clearer way to interpret the result is that, in solving for the $S$ with minimal $\Delta_{\text{uni}}$, one is identifying the game $(\Lambda_d, v)$ in which $S$ has the largest lower bound on its Shapley value. This result is interesting because it motivates minimizing $\Delta_{\text{uni}}$ through a game-theoretic interpretation by selecting the game with one player with the largest large Shapley value. We will stress on this clarification in the revised manuscript.

Concern 5: Notation in line 89

We thank the reviewer for pointing this out. This is actually a typo and we did not indent to use the term marginal distributions. What we intended to say is

To define feature importance precisely, we use the average restricted prediction,

where $x_S$ is fixed, and $X_{S^c}$ is a random vector drawn from an arbitrary reference distribution $V_{S^c}$, that may/may not depend on $S^c$. For example, two commonly used reference distributions are the marginal distribution $V_{S^c} = p(X_{S^c})$ and conditional distribution $V_{S^c} = p(X_{S^c} \mid x_S)$.

The revised manuscript incorporates this correction.

Concern 6: Advantage of $\tau$

First, note that some constraint on the cardinality of the subsets is needed -- otherwise, without it, the solution to the $\Delta^{uni}_V(S^*, f, x, \alpha)$ problem is achieved at $S^* = [d]$, i.e. using all features.

Perhaps the reviewer meant to switch the objective of the optimization problem with the constraint on its size; i.e, posing a problem like $min_S |S|$ s.t $\Delta^{uni}_V(S^*, f, x, \alpha) \leq \epsilon$. This problem minimizes the cardinality of $S$ directly, but it has the equivalent difficulty of setting the appropriate parameter $\epsilon$. Lastly, one could consider $\epsilon =0$ in the problem above, but this is not very useful for real settings since exact sufficiency (or necessity) might not be achieved.

Concern 1: Natural language explanation of "sufficiency" and "necessity" in Section 2

We agree with the reviewer. We have reworded the first paragraph of section 2.1 to clarify the meanings of sufficiency and necessity with the following text:

"We now present our proposed definitions of sufficiency and necessity. At a high level, these definitions were formalized to align with the following guiding principles:

1. $S$ is sufficient if it is enough to generate the original prediction, i.e. $f_S(x) \approx f(x)$.
2. $S$ is necessary if we cannot generate the original prediction without it, i.e. $f_{S^c}(x) \not\approx f(x)$.
3. The set $S = [d]$ should be maximally sufficient and necessary for $f(x)$.

The principles P1 and P2 are natural and agree with the logical notions of sufficiency and necessity. Furthermore, because the full set of features provides all the information needed to make the prediction $f(x)$, it should thus be regarded as maximally sufficient and necessary (P3). With these principles laid out, we now formally define sufficiency and necessity."

We hope this clarifies our definitions. We have also added further clarifications after the definitions of sufficiency and necessity in a revised version.

Concern 2: Experimental Setup

We apologize for the lack of clarity. 1) The $L^0$ refers to the relative cardinality of $S$ (|S|/d). 2) The threshold $t$ is used to generate the subsets $S$ and $S^c$. For a fixed $t$, all normalized importance scores higher than $t$ are included in $S$ and those lower than $t$ are not. As a result, $t$ controls the sensitivity of the choice of reporting important vs un-important features, for all methods.

Concern 3: Tabular Data Motivation

Thanks for pointing this out. Both tabular examples aim to demonstrate how optimal sets $S$ may change as we vary the levels of sufficiency and necessity we require. We argue this is an important question since, if they were very stable, one shouldn't be too concerned with the specific trade-off between sufficiently and necessity. In short, our experiments demonstrate that this is not the case: it is evident that as we demand higher levels of sufficiency (via increasing $\alpha$) the features in the optimal solution are constantly changing (measured via the Hamming distance to optimal necessary $S$).

To make this point clearer, we have added a small description before the tabular examples that clearly outlines the objectives of these experiments. Thanks for the suggestion!

Concern 4: What are the experimental takeaways

This is a great point and we would be happy to explain. We believe the experimental results yield a few key important conclusions:

1. Sufficient and necessary sets differ: One and other notions of importance convey different observations about the response of a model (on sufficiency and necessity of the studied features, respectively). Our experiments demonstrate that, while one could have a situation where necessary and sufficient features coincide, in most common experimental settings and common post-hoc methods, these two notions differ.

2. There exist domains where the sufficient sets are subsets of the necessary sets (our image classification settings highlight this). As a result, a minimal sufficient explanation will not highlight necessary features, thus falling short in reporting all important features more broadly. Without our results (cite which one in particular) one would not be able to draw this conclusion.

3. Our definitions allow us to conclude that many current post-hoc methods identify small sufficient subsets, but not necessary sets. This finding is important as it allows us to better understand the limitations of current methodology (and to propose our unification strategy as a solution).

Concern 5: Theorem 4.1 Uniqueness:

We don't have a complete answer to the uniqueness of $S^*$, but we can provide a partial answer: Arguments for uniqueness are best understood when we consider the expected predictor under the true conditional distribution, i.e. $f(x) = E[Y \mid x]$ and $V_S= p(X_S \mid x_{Sc})$. From our results in section 5, a solution $S^*$ to the unified problem then satisfies:

If the joint distribution $p(X, Y)$ satisfies the Markov properties, then it is known that $S^*$ is unique [1]. However, this known result is strong because it is a global characterization (i.e. holds for all $x$). Nonetheless, we believe this is a direction worth exploring, and we will incorporate it into our manuscript.

Additional Question: Is $f(x_{S}, X_S)$ a typo? I'd imagine one of them should be from the complement?

Yes, the reviewer is correct. The equation should be $f_S(x) = E_{X_{S_c} \sim V_{S^c}}[f(x_S, X_{S^c})]$. Thanks for pointing this out!

[1] Pearl, Judea. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2009.