A Refutation of Shapley Values for Explainability

Summary

In this paper, the authors formally define five anomalies for an explainability score and prove that for every n >= 4, there exist Boolean classifiers defined over n features that exhibit one or more of these anomalies for the SHAP score. In this way, the authors provide evidence of the inadequacy of Shapley values for explainability. The aforementioned anomalies are defined by considering the concept of abductive explanation. More precisely, given a binary classification model M : {0,1}^n -> {0,1} and a tuple v in {0,1}^n, a subset X of {1, ..., n} is said to be a weak abductive explanation of (M,v) if for every y in {0,1}^n such that y[i] = v[i] for every i in X, it holds that M(y) = M(v). In other words, the values of v for the features in X are enough to obtain the same result as M(v), so they are enough to explain the output of M for v. Moreover, a subset X of {1, ..., n} is said to be an abductive explanation of (M,v) if X is a weak abductive explanation of (M,v), and there is no weak abductive explanation X' of (M,v) such that X' is a proper subset of X. In other words, X is an abductive explanation for (M,v) if X is a minimal weak abductive explanation for (M,v). Then a feature i is said to be relevant for (M,v) if there exists an abductive explanation X of (M,v) such that i belongs to X, and otherwise i is said to be irrelevant for (M,v). With this notion of irrelevance, the anomaly I5 for the SHAP score is defined as the existence of a feature i such that i is irrelevant for (M,v), but the absolute value of the SHAP score of i is greater than the absolute value of the SHAP score of every other feature. Thus, this can be considered as an anomaly of the SHAP score, as i is an irrelevant feature that is considered more relevant according to the SHAP score that all the other features (some of which are relevant). The other four anomalies considered in the paper (I1, I2, I3, I4) are defined in a similar fashion.

Strengths

1. The five notions of anomaly studied in the paper clearly represent anomalies for explainability scores. These notions are properly formalized in the paper. 2. The paper provides valuable insights into the SHAP score, specifically providing a formal framework to assess its adequacy as an explainability score. 3. The paper provides one of the first formal results of the inadequacy of Shapley values for explainability. 4. The paper is well written.

Weaknesses

1. The results of the paper show that a tiny proportion of the Boolean classifiers defined over n features exhibit some of the anomalies I1, I2, I3, I4 or I5. For example, the paper proves that at least 2^{2^{n-1} - n - 3} Boolean classifiers exhibits anomaly I1, which is a tiny proportion of the 2^{2^n} possible Boolean classifiers defined over n features. Hence, it could be the case that the vast majority of Boolean classifiers do not exhibit the anomalies studied in the paper. 2. In practice Boolean classifiers are given in some specific formalism, such as decision trees or binary decision diagrams. The authors do not provide any results about the formalisms that are suitable to express the Boolean functions exhibiting anomalies. For example, is it possible to express the Boolean functions in the proofs of Propositions 3, 4, 5 and 6 as decision trees of polynomial size in the number n of features? If this is not possible, can these functions be expressed as FBDDs (or d-DNNFs) of polynomial size in the number n of features?

Questions

Could you please comment on the point 1. and 2. mentioned in Weaknesses.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

The following are the main limitations of this work (see Weaknesses), which are not addressed in the paper. - The results of the paper show that a tiny proportion of the Boolean classifiers defined over n features exhibits some of the anomalies I1, I2, I3, I4 or I5. - The authors do not provide any results about the practical formalisms (such as decision trees) that are suitable to express the Boolean functions exhibiting anomalies.

Summary

This paper reviews previous work on ideas of feature importance and hi-lighted inconsistencies with Shaley values. It defines ideas of importance and irrelevance of features in a Boolean ML model. These definitions are based on the idea of a minimal set of inputs needed to freeze an model output. necessary inputs are in every minimal coalition that can freeze the output, relevant inputs are in at least one minimal coalition, and irrelevant inputs are in no coalitions. They then go on to show that, among other issues, there exist Boolean models and certain inputs where irrelevant inputs are given large Shapley values, while relevant inputs are given a Shapley value of zero. Thus, the logic goes, Shapley values do not track importance. The paper's original contributions are to prove that model/input pairs with issues exist/can be found for models of any input size. Previously, only small models were exhibited to have these issues, but it was unknown if larger models also had these issues. They also give lower bounds on the number of models that have these issues.

Strengths

- Generally clear and straightforward exposition. - Good background and presentation of previous results. - Results are easy to understand. - idea of necessary, relevant, and irrelevant is intuitive.

Weaknesses

- Paper is based on a comparison of apples to oranges, without an in-depth analysis of the issue. It is possible that the whole paper is based on a misunderstanding. Further analysis is needed. - Some grammatical issues. - Contributions are not very significant.

Questions

- I believe, based on my calculations, that the paper's definition of Shapley Values in equation (3) is incorrect. For example, take model $F(x_1, x_2) = x_1$. I get that the Shapely values of the input $(1,1)$, assuming the baseline is $(0,0)$, is 1/2 for $x_1$ and 0 for $x_2$ for your definition. The Shapley value is actually 1 for $x_1$ and 0 for $x_2$, based on widely known definitions. The Shapley value satisfies the axiom of completeness, or efficiency, so the definition you gave is definitely not correct if it indeed gives the values 1/2 and 0. - The heart of the paper is a critique of Shapley values. It is asserted that there is a metric of feature importance and irrelevance and that the Shapley value assigns importance to what this other metric indicates is not important, and assigns no importance to what this other metric identifies as important. Admittedly this critique is from another paper, and this paper builds on this critique. Fundamentally, the Shaley Value indicates a feature's contribution to function value change in comparison to the function evaluated at the comparative baseline input. The metrics of AXp and CXp are metrics of the ability of inputs to determine or alter a model at an input. One is about function change from a baseline, the other is about fixing or altering an output. There does not seem to be any analysis as to whether these notions are tracking the same underlying, and undefined, concept of "importance." This paper defined "important" one way, while Shaley values define it another way. Is the problem that Shapley values do not indicate importance, or is the problem that Shapley values indicate importance according to one definition, while people are confused and think it indicates importance by another definition? The second case would account for this papers results, while problematizing the conclusion that the Shapley values do not indicate importance at all. This question needs further investigation and exposition in the paper, I believe. As an illustration, let $F$ be a model with one input defined as $F(x) = x$. Also, let the input of consideration be $x=0$. By the definition of the paper, $x$ very important because $x$ is a "necessary" input. However, The Shaley value of $x$ is $0$ at the input $0$. An inadequate analysis of this results it that the Shapley value indicated zero importance to a "necessary" input, so the Shaley value does not track importance. An equally inadequate analysis, opposite of the first, is that a "necessary" input did not cause any function change, so the idea of a "necessary" input is flawed. However, a more sophisticated analysis is that necessary inputs can have no contribution to a model changing from the baseline. Shapley values measure one thing, and "necessary" inputs measure another. In summary, it appears possible that this paper deals with two different metrics of "important," that these metrics disagree, but also, the two metrics measure different things and work in different ways. Shapley values do not indicate importance according to this paper's definition, but why is that necessarily an issue with Shapley values? Minor issues: - (39) "contributions of features to explainability". Do you mean function output? - (97) $2^\mathcal{F}$ should be $2^{|\mathcal{F}|}$ ? Sometimes you use one, sometimes another. - (108) "did" contribute", not "can" contribute - (117-118) "which corresponds to a PI-explanations" odd grammar. - please define A PI-explanations, prime implicants. Seems that unknowns are defined in terms of unknowns. - Unsure if WAXp is a function? - I1-I5 are stated in what appears to be sentence fragments. - I5 -> I2, but also, I5-> I1, and I4 -> I3, I1, and I2.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The author has not discussed the limitations of the claim that Shapley values are refuted. This statement seems not entirely supported. See questions.

Summary

The paper demonstrates / constructs functions with features whose Shapley values (i.e., attributive importance in a prediction) is misaligned with their true relevance.

Strengths

- Addresses a theoretical gap in our understanding of Shapley values.

Weaknesses

- I find the problem being investigated to be mostly a mathematical curiosity that so happened to be open and has now been addressed.

Questions

n/a

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

1 poor

Limitations

n/a

Summary

Based on definitions of feature necessity, relevancy, and irrelevancy from previous work,as well as systematic issues with Shapley values for explainability on boolean classifiers (e.g. non-zero Shapley values assigned to irrelevant features, zero Shapley values assigned to relevant features, among others) identified in previous work, the authors offer proof for their existence in functions with an arbitrary number of variables. They conclude that the existence of such systematic issues is cause for concern in using Shapley values for explainability, as misleading information about feature importance can induce errors in human decision making.

Strengths

- Originality: The work offers proof for the existence of issues with Shapley value explanations on boolean functions with an arbitrary number of variables that were previously only studied empirically. - Quality and Clarity: The theoretical framework, preliminaries, and proofs are described in a very concise manner. Despite the theoretical nature of the paper, the authors are able to concisely state to the reader what is described in each formula (e.g. lines 125-127: Thus, given an instance (v, c), a (weak) AXp is a subset of features which, if fixed to the values dictated by v, then the prediction is guaranteed to be c, independently of the values assigned to the other features). Similarly, the main idea for each proof is described in a very intuitive manner, increasing readability of the paper significantly. - Significance: The present work proves systematic issues exhibited by Shapley value explanations on boolean functions. Shapley values are one of the most popular solutions, as they are based on clearly defined axioms, i.e. properties deemed desirable for explanations. For boolean functions, the present work shows that these axioms (which Shapley values do fulfill) may be lacking for treating irrelevant and relevant features as would be expected.

Weaknesses

I am a bit concerned with the novelty, as the present work only provides proof for observations about unexpected behavior of Shapley value explanations for boolean functions that were already observed empirically in previous work (however, the authors also state themselves that these issues have been identified empirically in previous work). To raise concern about e.g. I1, it would be sufficient to simply identify a case where irrelevant values are assigned nonzero Shapley values. I also believe the title promises a bit more than is provided by the paper. The proofs and resulting claims are restricted to boolean functions, however, it would be interesting to see how and if the described issues occur in continuous settings, e.g., when explaining DNNs.

Questions

I would be interested in how the findings translate to non-boolean functions, i.e., continuous setting. E.g. the definitions of relevant, irrelevant, and necessary features over classification change makes sense in the boolean setting, but not in a continuous setting where logit values easily change with features being added. Also, it would be interesting to see some concrete recommendations as to how the identified issues might be avoided.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

restriction to boolean functions, as described in "Weaknesses" section. I think a paragraph of how the described proofs and observations may impact Shapley value explanations in more real-world settings would go a long way here, as well as suggestions on how to mitigate the proven issues.

Response to Author Rebuttal

I acknowledge having read the response of the authors. I will try to elaborate more on my two points: 1. A "theoretical gap" is a missing piece in our understanding / knowledge of something. Prior to this work, we had a gap in our understanding / knowledge on whether "Shapley values can produce misleading information regarding relative feature importance, for arbitrary many classifiers". We didn't know whether this statement was true or not. Now, because of this paper, we know. The paper has closed this gap in our understanding / knowledge. I am not sure why the authors take issue with the claim that their work addresses a theoretical gap. How can this claim be possibly construed in a negative way? 2. The rebuttal claims that the paper proves "what thousands of earlier papers have used the theoretical justification for explainability, can produce misleading information". We already knew that. The paper already acknowledges that much in the first sentence of its abstract: "Recent work demonstrated the existence of Boolean functions for which Shapley values provide misleading information about the relative importance of features in rule-based explanations.". So, we knew that Shapley values "can produce misleading information". Much more modestly than what the rebuttal claims, this paper shows that Shapley values can not only produce misleading information as known, but can do so for arbitrarily many functions. I found this particular result to be of little consequence. The functions are artificially constructed, and the result, therefore, has no apparent implication on how widespread the problem with Shapley values (that we already knew was there) really is in practice. In my opinion, which I was asked to offer as a reviewer, the result of the paper is a mathematical curiosity: can we extend the existence result of previous work, to an "arbitrarily-many cases" result? The answer seems to be positive, without any obvious real-life repercussions. I stand to be corrected if the arbitrarily many functions considered in this paper somehow relate to functions used in the relevant literature. P.S. I thank the authors for being forthcoming in terms of reporting this review.

Response to rebuttal

Thank you for your answer. I understand that the bounds provided in the paper represent lower bounds and are not tight. My point is that the bounds proved in the paper show that a tiny proportion of Boolean classifiers, defined over n features, exhibit some anomalies. More formally, if f(n) is this fraction as a function of n, then lim_{n -> infinity} f(n) = 0. Obviously, this does not preclude the existence of stronger lower bounds that demonstrate that a non-negligible proportion of Boolean classifiers exhibit some anomalies. While I believe this paper offers valuable insights, I still think it is not ready for publication. It does not show either that a significant proportion of Boolean classifiers exhibit the anomalies discussed in the paper or that popular formalisms for Boolean classifiers display such anomalies.

Response to Rebuttal

We thank the author for their clarification of the Shapley value. We agree that the formulation of Shapley values is in accord with previous literature, i.e. Lundberg and Lee (2017), and withdraw comments about the incorrectness of equation 3. Regarding the refutation of the "apples-to-oranges comparison" claim, we are not convinced. We agree that the paper, if correct, shows that for arbitrarily large domains, Shapley Values may not indicate necessary or irrelevant features. We disagree that this is a refutation of Shapley values for ML explainability. 1) It may be that Shapley values both ARE useful and legitimate for ML explainability AND do not track necessary or irrelevant features. This is because the purpose of Shapley values is to indicate feature contribution to function change relative to an input baseline. This purpose may be separate from necessary and irrelevant features. 2) Regarding the provided quotes: the word "importance" is not in any quote, only feature "contribution" and "influence." These quotes claim that Shapley values track feature contribution and influence, which different and more specific than feature importance. It is our opinion that the idea of "importance" is vague, and that when we take a high-resolution view of the matter, the issues seem to dissolve. 3) We conceded that some popular opinions may hold that Shapley values indicate feature importance, which is false for certain definition of importance. We disagree that the proper remedy is to assert Shapley values are not at all useful for ML explainability. We rather advocate for a clarification of what Shapley values are, and what they are not. We recommend that the paper move away from the "refutation" claim, and instead state the claim as: Shapley values are "incompatible" with a certain notion of feature importance.