Shapley Residuals: Quantifying the limits of the Shapley value for explanations
Authors: I. Elizabeth Kumar
Carlos Scheidegger
Suresh Venkatasubramanian
Sorelle Friedler
Venue: NeurIPS 2021 Poster (2021)
Keywords: shapley
shap
xai
explainability

Abstract: Popular feature importance techniques compute additive approximations to nonlinear models by first defining a cooperative game describing the value of different subsets of the model's features, then calculating the resulting game's Shapley values to attribute credit additively between the features. However, the specific modeling settings in which the Shapley values are a poor approximation for the true game have not been well-described. In this paper we utilize an interpretation of Shapley values as the result of an orthogonal projection between vector spaces to calculate a residual representing the kernel component of that projection. We provide an algorithm for computing these residuals, characterize different modeling settings based on the value of the residuals, and demonstrate that they capture information about model predictions that Shapley values cannot. Shapley residuals can thus act as a warning to practitioners against overestimating the degree to which Shapley-value-based explanations give them insight into a model.


Shapley Residuals: Quantifying the limits of the Shapley value for explanations
I. Elizabeth Kumar Department of Computer Science Brown University Providence, RI 02912 iekumar@brown, edu
Carlos Scheidegger
Department of Computer Science
University of Arizona
Tucson, AZ 85721
cscheidRcs ar www.araiaa...... edu
Suresh Venkatasubramanian Department of Computer Science
Sorelle A. Friedler Computer Science Dept. Haverford College Haverford, PA 19041 sorelleêcs haverford edu
Brown University Providence, RI 02912 suresh@brow edu
Abstract
Popular feature importance techniques compute additive approximations to nonlin- ear models by first defining cooperative game describing the value of different subsets of the model's features, then calculating the resulting game's Shapley values attribute credit additively between the features. However, the specific modeling settings in which the Shapley values are poor approximation for the true game have not been well-described. of Shapley values as the result of an orthogonal projection between vector spaces to caleulate residual representing the kernel component that projection. We provide an algorithm for computing these residuals, characterize different modeling settings based on the value of the residuals, and demonstrate that they capture infor- mation about model predictions that Shapley values cannot. Shapley residuals can thus act as a warning to practitioners against overestimating the degree to which caaplly-vallu-baaae explanations give them insight into model.
this paper we utilize an interpretation
Introduction
There have been many recent efforts to quantify the importance of features to a model [19, 4, 1, 15, 12, 13]. Many of these determine the importance through estimating the Shapley value of game designed to assign importance to sets of features [4, 12. 5, 13, 14, 25]. These Shapley-value based feature importance methods are used widely in practice [2].
At the same time, there have been increasing concerns that these game theoretic values may not completely capture human technical notions of feature importance [10, 21, 24). A particularly salient issue that users have misconceptions about what Shapley values represent and what ac- tionable information can be gleaned from them [8]. Non-linear complex models, and models built on correlated features, do not have Shapley values that can be interpreted as the effect of a direct intervention [10], e.g., that increasing variable value changes the model outcome in predictable way. The goal of this work is to quantify the extent of these concerns and provide a theoretical foundation for understanding the limits of Shapley values.
In this work, we introduce Shapley Residuals, vector-vall valued objects that capture a specific type of quantitative information lost by Shapley values. Shapley residuals can be associated with individual
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

variables, as well as with sets of variables. When the residual of feature exhibits large norm, the associated Shapley value should be taken with skepticism: the resulting importance is not just due to the variable acting by itself. On the other hand, if residual is small, most of the effect of the variable on the model is explainable by the variable acting independently (we make these statements precise in Section 3). The Shapley residual, then, communicates important details about what the explanation actually represents.
To build an intuition for why this is an important problem, consider an algorithm which makes admissions decisions purely on the basis of gender and department: f(g d) = + d -2dg, where otherwise, and there are two departments, represented by
-1 if the applicant is male and and -1. In this contrived scenario, the applicant is admitted if f(g. d) > 0 (which only happens when 9 and d have different signs) and is rejected otherwise. Clearly, the admissions decision affected by gender-yet if each of the two variables are distributed with mean the KernelSHAP values [12] which are supposed to explain the decision 111,1) 0 are both O, since to compute the Shapley value, each features' univariate and interaction influences are averaged together and cancel each other out. In this way, the computation of the Shapley value has implicitly obscured discriminatory effect, and the corresponding nonzero Shapley residuals would demonstrate that the Shapley values not telling the whole story.
To more precisely describe what Shapley residuals capture, consider the following two motivating scenarios. First, suppose practitioner uses Shapley values to determine the effect of data interven- tions on model outcomes. Consider two models fi and fz. In a real-world scenario, the practitioner will often only have black-box access to such models, and the models will often be significantly more complex. Here, we use these simple models:
J1 (xI, 12, 23) f2(21, T2,
21 + 222 + 233
+ 2x2I33
Suppose the practitioner seeks to explain the output (1,11,1) 3 or 1,,1, 3, using KemneSSHAP to compute local feature importances. For both models, the Shapley values of æ1, T2. and 23 are all 1. Despite that, intervening by increasing the value of xg changes f2 more than increasing the value of 11; in fI, this clearly does not happen. The Shapley residuals for all variables in fi are zero, indicating that variables in fi do not interact (as prove in Section 3). The Shapley residuals for 22 and 23 in /2, on the other hand, are nonzero, while the Shapley residual of æ is still zero. Finally, the Shapley residual for the set of variables {x2, Fz is also zero. As show in Section 3, these statements imply the following behavior for variables of f2: x1 has no interactions with other variables (its residual is zero); 22 and I3 interact with other variables (their residuals are non zero); 22 and I3 only interact with each other (the residual of the set {x2, 233 is zero). Thus, access Shapley residuals gives warning that intervening on 22 F3 in could act differently than I1 due to an interaction between T2 and 33-
Table 1: KemeeSHAA game for Example - the input (1, 1, 1) to (211, = + 20223 where Iy are iid (O, 1) features.
Hypercube Coordinate
(S) Definition
u(S) Value given i.i.d.
S
for explaining (1, 1,,1 with KernelSHAP
I; N 1)
0
(0,0,0)
Eif(x)
0
{x1
(1,0,0)
[ff(x) ) Ø1 =
{x2
(0,1.0)
[[
=1
0
(0,0.1)
[[(x))
T3
O
(21.
(1,1.))
E.f(x) = 1,82 =1
1
(31.
(1,0,1)
/ [1 1,
33
1
[3)
(0.1,1)
f
22
1, 23
2
{I1, 22)
(L,1.))
E [.f(()
1,
1,33
3
In the second scenario, consider data generating distribution where a controls the correlation between two features in X and a regression target y:
(X,y) ~ (N (0.0)) i .)).xx(3..1)
a

---

We examine a regression model x21, = 3121 + B2zz determined via linear least squares. Assume access to infinitely many IID samples from (X, 3). 3 (3. 1). Suppose practitioner wanted to explain the output of [(1, 1) 31 + B2, this time using Conditional Expectation SHAP [24]. The Shapley values are 31 + a0 - -81)/2 for 21 and f8 + +0(3 - /2/ for x2. When a R 0, Shapley values correspond to model weights $1, B2, and support a (valid) interventional interpretation that changing #1 yields a larger change to the output of f than does 22. However, if a Rs 1, Shapley values do not support this interpretation. A practitioner employing Shapley values alone lacks the information to distinguish these scenarios. Shapley residuals provide useful diagnostic information; the norm of the residuals for 21 and 22 is exactly linearly proportional to
In these simple scenarios, is clear that Shapley residuals capture, respectively, variable interactions and mismatches between dependent features in the data and independent variables in the model. As we show in Section 6, these observations apply to real-world scenarios as well.
In summary, we:
introduce Shapley residuals (Section 3), which characterize the limits of Shapley values as explanatory mechanisms for cooperative games,
study the properties Shapley residuals both in general and in context of existing formula- tions for explanatory games (Sections 3, 4 and 5),
show via number of experiments that Shapley residuals capture meaningful information for model explanations in realistic scenarios (Section 6),
discuss the limitations of Shapley residuals themselves (Section 7).
2 Background
In this section, we begin by setting up the mathematical definitions and background we'll need for the rest of the paper. To help illustrate these ideas, we'll use the running example from the introduction of function f = I1 + 2x2233; we refer to this as Example 1. We begin by describing Shapley values and cooperative games.
Games. A cooperative game consists of d players and a value function e : 2|d + R where [d] A SEN 2 2'd. Without loss of generality we will assume that v(0) = 0, and that we can identify the game with v. Let the space of games be denoted by G.
The quantity v(S) represents the value of the game for a coalition of players
The Shapley value a way to fairly allocate the value of the grand coalition v((d) among the players.
Definition (Shapley values[20]). The Shapley values @r(u), i E [d] are the unique values satisfying the properties
Efficiency: EL. v((d).
Dummy: US (1)) = v(S) for all C [d] \ {i), then Φ.(v) = O.
Symmetry: 1f U (+}) = u(S u (f)) for all S c [d] \ (i.j}. then (x(()= = (v(
Linearity: uf o' are two games on d players, then 0: + a'v') aQ.(v) + a' (1').
Given a model f(1 .2..... za). the features from to d can be considered players in a game in which the payoff is some measure of the importance or influence of subset of features. The Shapley value (v) can then be viewed as a fairly attributed "influence" of i on the outcome v(d)). In KernelSHAP, for instance, function's 's prediction a certain input given data distribution is modeled as game as shown in Table 1.
It will be useful for us to visualize a game as a function over the vertices of d-dimensional hypercube. Each coordinate corresponds to the presence or absence vertex corresponds to a subset of players. Specifically, we can think of the set N as the d-dimensional hypercube G = (V = N, F)) with each vertex labeled by set S S [d] and edges between sets S and S U {i} for all E [d] S. We depict this interpretation in Figure ((a).
certain player, and each
3

---

X2
(1,1,1): (2))2)
(0,1,0) : (x2]
Ve(S.
x1
(0,0,0)
(a) Graphical representation of
(b) Graphical representation of Ve
Figure 1: Visualizing the game and gradient of the game corresponding to Example 1.
Gradients on the hypercube. Let RV be the space of functions from V to R and let R be the space of functions from E R. In particular, the game v is an element of TBV.
The differential operator V RVV - RØ is then defined as Vu(S, (+]) = v(S Ui) v(S) for any R R. Essentially V is discrete gradient operator G, mapping functions vertices to functions on edges (see Figure 1(b)).
We will also define partial gradient V. RV + >
Ve (U), = (u(SUU - uSS)
i
otherwise
Intuitively, Vi evaluates gradient for edges corresponding to the insertion of i, and takes the value 0 everywhere else. On the hypercube, only edges on the ith axis of V will take a nonzero value. See the Edge Space portion of Figure 2(a) for an illustration of this procedure on the running example.
2.1 Geometric characterization of Shapley values
geometric interpretation of Shapley values dates back at least to Kleinberg and Weiss [9], showing they can be expressed in terms of projections from the space of games to the space of cooperative games with independently contributing players. A key advance was made by Stern and Tettenhorst [22], building on earlier work by Candogan et al. [3] who proposed viewing the game as scalar function defined on the hypercube and studying its discrete gradient. To understand this advance, we first introduce a special class of games.
Inessential games Let I denote the space of games such that for all S S [d] vSS) E(es)(())) (((i)). Z is called the space of inessential games. Intuitively an inessential game is one in which the player interactions are simple and additive: every player adds a fixed value v({i)) to coalition S 'independent of the composition of S. Inessentiality is key feature of what makes Shapley values attractive for feature importance - if each contribution is fixed and combines additively, we have natural interpretation for how much each feature contributes to the overall model output. Specifically, if game is inessential, it then follows that the Shapley value for player i is v v((i)). In our running example using KemneISHA,, this E[f(x) 1], the contribution (averaged over other variables) of the variable ZT.
In general though, a game might not be inessential. The key insight of Stern and Tettenhorst [22] was to express inessentiality of games in terms of gradients on the hypercube.
Proposition 1 ([22, Prop 3.3]). The game is inessential if and only for each i [d] there exists E VRV such that V.U = Vv.
The main result by Stern and Tettenhorst [22] is decomposition of an arbitrary game into games that are "close to being inessential" and allow extraction of Shapley values. If is not inessential, we cannot be sure to find o such that V,u Ve, but can find the "closest" such i the solution to the least squares problem
min RERV a0)))=
Vr
Theorem (Stern and Tettenhorst [22]). Given game v, let v. be defined as above, Then
1. Σe =v =v

---

2. Uf (+)) = v(S) all S C. [d], then =0
3. For any a, a' E R. and games v, v', (ov + a'v'); = ae;; + a'ea
4. If is a permutation of [d] and π o is the game л o v(() = vS)( then oTO)); = (x())
Consider the mapping (())(S) Eies v/([d). The above result implies this is a Shapley mapping and therefore (v) = 0z are the Shapley values of We illustrate the construction in Figure ((a).
Shapley Residuals
The inessentiality of game is inextricably linked to the meaningfulness of Shapley values for the reasons given above. The idea we explore now is the converse: can the degree to which a game not inessential provide insights into where Shapley values are not able to capture feature influence?
By the fundamental theorem of linear algebra, we can write
V Ve; +
where r; is orthogonal to Vo, This allows us to interpret ry (a vector with one value for each edge of the hypercube) measure of deviation from inessentiality, because by Proposition 1, this vector is identically and only if the game is inessential.
We can generalize these ideas further to subsets of players. We begin with a generalized notion of inessentiality:
Definition 2. The game is inessential relative to S if v(S) + v(C \S) for all S and C such that S C [d].
That is, each coalition containing S obtains value equal to the subcoalition S working separately from C \ S; this sense, inessentiality with respect to can speak to the lack of interactions between S and its complement. In addition, inessentiality relative to single player is the same as inessentiality relative to the singleton set {i}.
Next, we generalize the notion of partial derivative.
Definition 3. For a subset C [d]. let Vs: RV - F. be the operator Vig = =Eies V, or
Vu (u,Cuu((t ii= and S,
Tsu(C,cu =
otherwise.
We prove result similar to Proposition for relative inessentiality.
Proposition 2. The game is inessential relative to S if and only if there exists E TVV such that Vst Veg.
To understand the limits of Shapley values, we propose to quantify the degree of deviation from inessentiality with the following definition:
Definition 4 (Shapley Residuals). We call r; V&U Ve, the Shapley Residual of player i. Analogously, rs Eies Tú is the Shapley Residual of set S.
Shapley Residuals a novel diagnostic tool for feature importance, and enjoy number of relevant properties.
Proposition I inessential, then u inessential relative to all E [d] and all subsets [d]. If o is inessential with respect to each player of i.j.... then v is inessential relative to the set (i.)....,2).
The proof of this proposition is in the appendix. The following corollaries are straightforward.
Corollary 1. is inessential iff r; = 0 for each E [d] Corollary 2. is inessential relative to isf rs Eies =
This allows us to interpret EieN ||r as the deviation from inessentiality and Eies rz|l2 the deviation from inessentiality of e relative to S.
5

---

Verteex spaie
Edige spaice
Edge space
Thetk.5 b15.2)
arg dels
Varrox space
Vertax space
91
(a) The decomposition of game proposed by
(b) The construction of Shapley residuals
Stern and Tettenhorst [22]
Figure 2: Visualizing the decomposition of game and its residuals.
In this paper we will focus on the computation and evaluation of residuals with respect individual players i. rs for S = {i}. Figure 2(b) illustrates the construction of residuals. Algorithm I describes how to compute residuals.
Algorithm 1 Exactly calculate the ith Shapley value and Shapley residual of
Compute Vi7
Solve U; argmin EERV V Vr
Compute Ve;
Return Shapley residual = V,0 Ve;
Return Shapley value di (S) vV) where S is the of all players
4 Feature Importance, Inessentiality and Residuals
We have established that the norm of the residual characterizes the degree to which the value function v is not inessential with respect to the player We now show how to interpret this when attributing feature importance via Shapley values for two popular methods. As has been noted, the different methods for Shapley value-based explanation (whether local or global) all reduce to specific choice for the game which point the Shapley values of estimated and returned [24, 10, 16].
The definitions of Shapley sampling values [23], well as SHAP values [12], are derived from defining v as the conditional expected model output on data point when only the features in S are known: wCond (S) = E[](X)]X; æs) We call this Conditional Expectation SHAP after Sundararajan and Najmi [24].
The Interventional SHAP value function, which defines KernelSHAP, is derived from defining v by taking expectation of f over the joint distribution of Š while fixing the feature values from S: u/ (S)= = [[ Xs|)] Notably, the two values are the same if the features in are independent from those S.
We will show that the residual rs captures the degree to which interactions between the features in S and its complement arise the model or the data, depending on which form of Shapley-based feature importance is used to define the value function v.
We can take an unconstrained minimum here and subtract (0) at the end because adding constant value does not change Vv.

---

4.1 Inessentiality and Interactions
Interventional SHAP Recall the problem of explaining two models where fi (21, 42) I1 I2 + 23 and f2( 22, 23) 21 + 2xy22. Note that in the first model all three variables contribute independently to the model output, whereas in the second model the variables 42 and 23 interact in their contribution. We can compute the associated residuals 1,,2,77 23 and their norms for these two models. For the first one, residuals are identically zero. However, in the second model if 22 and Iy are nonzero for certain input, they will have nonzero residual. In other words, the residual captures feature interactions in the model. Our first result, which we prove in the appendix, shows that this intuition can be made precise.
Lemma Let f X {X1, X2, Xa} - Y be multivariate function. Suppose can be decomposed as f(x) = g(xs) + h(ag),, for some functions {Xj : E S} - Y and h (X, j $ S} + Y. Let = {21, 22, 3 E X. Then U/2 is relatively inessential with respect to the set S.
This important because the model really does decompose additively for a certain variable the practitioner understands what to expect when variable is perturbed. The Interventional Shapley residuals thus quantify the extent to which the SHAP values must be augmented with more information to capture interaction effects in the model.
Conditional Expectation SHAP As the residual for Interventional SHAP can be thought of as detecting feature interactions in model, the residuals of Conditional Expectation SHAP can detect
1 a 1 and let Y = f(X)= =
feature interactions in the data. Let X ~ (NO, OJT, Σ) for E
a
33 X (note that ordinary least squares will recover f in the limit of infinite data). Given input æ1, 22, the SHAP values of f are Φ1 3 + + - Φ2 B232 + a -1 That is to say, they linearly dependent on the correlation between the variables. In particular, consider explaining the input [1, 1] to the function 2 + 322; the SHAP values are Φ1 = 1 + and Φ2 = 3 - a and the residuals are both 2a. Notably, as interaction between variables increases in the data (measured by a), the residual increases and the SHAP values deviate further and further from the coefficients of the actual model. We can make this intuition precise.
2
Lemma 2. Let f : X = {X1, X2, Xa) - Y be a multivariate function. Suppose f can g(xs) h(ss), for some functions g {X; : (X, j S} + Y. Let = {21, 22, ...,. 2n} } E X. Suppose further that all X, : E S are distributed independently from all X₃ 4 S. Then CCon is relatively inessential with respect to set S.
be decomposed fxx
S} Y and
The residual on Conditional Expectation SHAP thus quantifies the extent which an interpretation of the SHAP values can be interpreted as interventional, because depending the causal structure of the data, correlated features could imply that perturbing a feature could result in the perturbation of a different feature well.
Inspecting Shapley residuals in practice Shapley residuals vectors in the same space as gradients, and are generally nigh-dimensional entities; a full study of their properties remains an important topic for future work. The characterization in this section shows that the norm of the residual vectors captures important limitations of Shapley values. Thus, our experiments use the scaled norm of the residual vectors, defined to be the norm of the residual vector divided by the norm of the discrete gradient vector. Normalized residuals make them easier to compare across experiments.
5 Relationship with Other Interaction Indices
[25], similarly recognizing that Shapley values lose information about interactions, proposed Shapley- Taylor Interaction Indices, generalization of Shapley values which attributes influence among interaction terms. Specifically, the Chapley-Taylor explanation for x of order k assigns values 15 to subsets of features of size [S] < such that Σ 15 f(x). The terms for the subsets for which |S] < represent discrete Taylor series around v0)). When |S| = k. 73 is defined similarly to the Shapley value: a discrete derivative averaged over permutations.
7

---

Our residuals capture fundamentally different information about interactions than Stapley-Taylos Consider some subset for which S < k. Our residual rs 0 when the marginal value of adding S to coalition W is constant with respect to sets for which W n = 0; in other words, it is about the presence or absence of interactions of 5 with other variables. The Shapley- -aaeo- interaction index Tg. on the other hand, is O when (S) can be inferred from the values of v(W) for {W C S). The Taylor terms of the Shapley-Taylor explanation thus capture information about how the players in S interact with each other when no other variables are involved. For instance, if for certain game ((i)) + v v(()) = v({i,}}) this means that the term o(i,j)) provides no interaction information about the two players, and ((.s) for explanation sizes k > 2 will be 0.
However, the Taylor indices for a coalition S say nothing about whether the variables within S interact once a player outside of $ is involved. Consider three-player game between a, b, and c, where o(fa}) + o({b)) = (((a, b]) and o v(fa)) + v(fc)) v(fa, c}); this would make I (a, and I (a.c) equal to 0, implying that a and b do not interact, and and do not interact. But it could be that v is not relatively inessential with respect to a. If e((a,, b. c}) v(fb, c)) * v(fa, - (10)-v((cc))) v(fc)). then a's relative contribution with respect to changes once b is involved. This constitutes an interaction between and that is not described by the Shapley-Taylor index for {a. c). but is rather captured by the third-order interaction of {a, b, et. In this scenario, our residuals would show ra o 0, alerting us to the fact that a interacts with {b, e); additionally, it would have [(a.b) F O. alerting us to the fact that {a, b} interacts with c.
In general, since r, captures information about all of i's interactions, we can state the following connection between the two Shapley extensions:
Lemma 3. Given subset S, |S| < k. if S..rr, 0, then the Shapley-Taylor index 1/ 0.
We have focused our attention on Shapley- Taylor interaction indices because of their proposed use for explanations. It should be noted that they (as well as the Shapley interaction index proposed in [13]) are special cases of general class of interaction indexes investigated in long line of work starting with [17] and surveyed in [6] (including the Trabisch-Roubenst indices). All of these differ from Shapley residuals the latter are meant to represent the information lost when computing singleton Shapley values, not their higher-dimensional extensions, which are
Shapley and Banzhaf interaction
based on different notion of a derivative.
Experiments
Having theoretically justified Shapley residuals in previous sections, we focus illustrating what these residuals can help us understand about models on a real-world dataset. Throughout, we use our own implementation of KerneISHAP to calculate the exact Shapley values and residuals (see Algorithm 1 in Section 3).² Some additional experiments can be found in the appendix.
On comparisons to other feature importance methods We note that Shapley residuals are not a feature importance evaluation method, nor are they "explanation method" in and of themselves. Rather, they are a quantification of the (valuable) information lost by Shapley values. A direct comparison of different feature influence evaluation methods makes sense when there is clear objective to compare against. Such an objective doesn't it really exist here. Rather, we choose to provide an internal validation that lays out the mathematical foundation on which the method rests. This allows a user to decide the context in which to employ one method or another. For example, as we discussed in Section 5, Hhapley-Taylor indices and Shapley residuals appear to capture different kinds of interactions that are potentially of interest to user. There is no meaningful way to compare them in a vacuum because one not "better" than another.
Consider the Shapley values and residuals for an occupancy detection dataset (20,560 instances) used to predict whether an office room is occupied. The attributes include date stamp for an hour and day of the week. A decision tree model with maximum depth 3 is trained on 75% of the data using the features light and hour. When
Variable Interactions in Occupancy Detection
"Code is provided in the supplementary material hhttps://archiie uus.uci.
8

---

SHAP
Light CAN
Procedon
Prodage
Phodugen
37
R75
Pixnd
800
(a) KemelSHAP values
(b) KermelSHAP scaled residual (c) KernelSHAP sampling for (10,320)
norms
Figure 3: Shapley values and residuals on a decision tree for the Occupancy Detection task
evaluated on the remaining test set, the ROC-AUC for this decision tree is 0.991. We then calculate Shapley values and residuals (using 50 randomly sampled background rows from the test set) for 1000 randomly sampled test instances. The results for the variable "light" are shown in Figure 3.
The reason that the cluster of points in the middle has high residual is illustrated in Figure 3(c). Calculating the expected prediction while fixing a light value of 320, unlike most other possible values, results in mix of low and high predictions. These average 0.4, while both the overall expectation and particular prediction for occupancy probability for those points are 0.25.
(H L)] = 224
+.01
B[S(10, L) = .25
+.16
|
EH 320)
.40
-.39
f(10, 320) .01
Figure 4: Geometric representation of the KernelSHAP game for 320), where arrows the right indicate inclusion of the light feature and arrows down indicate inclusion of the hour feature.
Specifically, the KernelSHAP game for L) = P Ploccupant = T) for 320 and = 10 shown in Figure 4. L 320 is positive indicator of occupaney if H is unknown (+.16) but is "negative" indicator of occupancy is H is known to be 10 (-24), due to the interactions the model in this area of the feature space. The light Shapley value is close 0 for points in this range, then, because it is the average of positive and negative number - not because is of "low importance" and the non-inessentiality of this feature is what is being captured by the residual.
7 Limitations and Future Work
Usability considerations Our motivation for this work is to contribute further to the theoretical foundation Shapley-value-based feature importance measures and, critically, introduce Shapley residuals to quantify missing importance. Our goal is that residuals be a warning attached to specific Shapley values and thus alert practitioners to model complexities and importances that have previously gone unattended. Further research is needed to investigate whether these residuals can be effectively utilized by humans make better decisions about their models. An empirical, numan-centerd investigation is critical because, like Shapley values themselves, the meaning of these residuals may be hard for practitioners to understand, and therefore errors in the interpretation of these residuals may cause unanticipated negative consequences.
Performance considerations SHAP implementations provide partial evaluation of the game vector [12, 11]. which provides analysts with results even in dighediiensional settings. Unfortunately. there is no assumption-free provable bound on the relationship between partially evaluated game vectors and actual Shapley values. Our goal here is more precisely characterize the information not conveyed by Shapley values and so we always compute the full vector. Thus, the runtime is ultimately exponential in the number of variables to analyze. This currently limits the number of

---

variables for which Shapley residuals can be practically computed to 20 to 30 (with corresponding vectors of length between a million and billion elements). Since the derivative operator sparse and well-conditioned, the least squares problem is efficiently solved by the LSQR method [18]. Still, in future work, we hope efficiently identify whether particular residual nonzero, and approximate properties of residuals which capture the entirety of non-linear interactions of a particular feature.
Conclusion A goal interpretable machine learning, and within Shapley-value-base feature importance, is to give rigorous theoretical foundation to interpretability notions so that practitioners can better understand the impacts of their models. This is especially important in contexts where models make high-stakes decisions about people, e.g., via criminal risk assessments and interview screening algorithms. We believe people have the right to understand those decisions, and particularly which features were important for the decision. Putting such feature importance measurements solid theoretical grounds important for the validity of these feature importance claims. Their validity is important part of the ethics of algorithms societal interventions.
8 Acknowledgements
This research was funded in part by the NSF under grants DMR 1928882, IIS 1955162, and IIS 1956286, and by the DARPA SD2 program.
References
[1] Philip Adler, Casey Falk, Sorelle A Friedler, Tionney Nix, Gabriel Rybeck, Carlos Scheidegger, Brandon Smith, and Suresh Venkatasubramamiin.. Auditing black-box models for indirect influence. Knowledge and Information Systems, 54(1):95-12) 122, 2018.
[2] Umang Bhatt, Alice Xiang, Shubham Sharma, Adrian Weller, Ankur Taly, Yunhan Jia, Joydeep Ghosh, Ruchir Puri, José MF Moura, and Peter Eckersley. Explainable machine learning in deployment. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 648-657, 2020.
[3] Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decomposi- tions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3): 474-503, 2011.
[4] Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transpareney via quantitative input influence: Theory and experiments with learning systems. In 2016 IEEE symposhum on security and privacy (SP), pages 198-617. IEEE, 2016.
[5] Christopher Frye, Ilya Feige, and Colin Rowat. Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability. arXiv preprint arXiv:/910.00 1910.0658, 2019.
[6] Katsushige Fujimoto, Ivan Kojadinovic, and Jean-Luc Marichal. Axiomatic characterizations of probabilistic and pardinal-rroaabllistie interaction indices. Games and Economic Behavior, 55(1):72-99, 2006. ISSN 0899-8256. doi: https://doi.org// 1016/j geb. URL https://www. https://ww..eceeneddreed sciencedirect.
[7] Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of game theory, 28(4):547-565, 1999.
[8] Harmanpreet Kaur, Harsha Nori, Samuel Jenkins, Rich Caruana, Hanna Wallach, and Jennifer Wortman Vaughan. Interpreting interpretability: Understanding data scientists' use of inter- pretability tools for machine learning. In Proceedings of the 2020 CHI Conference Human Factors in Computing Systems, CHI '20 pages 1-14, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 97814508 778145066000. doi: D0.1145/3133331
URL
https: bittps//cche //oo:./ddoooooooo http://///oooo/..////// 1145/3313831 /t55//33313311333621199
[9] Norman L Kleinberg and Jeffrey H Weiss. Weak values, the core, and new axioms for the shapley value. Mathematical Social Sciences. 12(1):21-30, 1986.
[10] I Elizabeth Kumar, Suresh Venkatasubramanian, Carlos Scheidegger, and Sorelle Friedler. Problems with caapley-vllue-bare explanations as feature importance measures. arXiv preprint arXiv:2002.11097 2020. 37th International Conference on Machine Learning, to appear.
10

---

[11] Scott M Lundberg. shap: A game theoretic approach to explain the output of any machine learning model, 2021. URL https:
how.a//oooommmmduoo/oaaaaaaaaaa _kennel py#
L281-L374.
[12] Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. In Advances in neural information processing systems, pages 4765-4774, 2017.
[13] Scott M Lundberg, Gabriel G Erion, and Su-In Lec. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv: 03880388. 2018.
[14] Scott M Lundberg. Bala Nair, Monica S Vavilala, Mayumi Horibe, Michael J Eisses, Trevor Adams, David Liston, Daniel King-Wai Wai Low, Shu-Fang Newman, Jerry Kim, al. Explain- able machine-learning predictions for the prevention of hypoxaemia during surgery. Nature biomedical engineering, 2(10)749--76, 2018.
[15] Charles Marx, Richard Phillips, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubra- manian. Disentangling influence: Using disentangled representations to audit model predictions. In Advances Neural Information Processing Systems, pages 4498 4508, 2019.
[16] Luke Merrick and Ankur Taly. The explanation game: Explaining machine learning models with cooperative game theory, 2019.
[17] Guillermo Owen. Multilinear extensions of games. Management Science, 18(5):664- P79, 1972. ISSN 00251909, 15265501. URL http: /ttp///wwwtrrrrr//oo////ooo/o/// org/stablee/261111
[18] Christopher C Paige and Michael A Saunders. Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software (TOMS), 8(1):43-71, 1982.
[19] Marco Tulio Ríbeiro, Sameer Singh, and Carlos Guestrin. "why should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1 1135-1144, 2016.
[20] Lloyd S Shapley, value for n-person games. Technical report, Rand Corp Santa Monica CA, 1952.
[21] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling LIME and SHAP: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 180-186, 2020.
[22] Ari Stern and Alexander Tettenhorst. Hodge decomposition and the shapley value of a coopera- tive game. Games and Economic Behavior, 113:186-198, 2019.
[23] Erik Štrumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41(3):647-665, 2014.
[24] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation, arXiv preprint arXiv:1908, 1908: 08474, 2019. 37th International Conference on Machine Learning, to appear.
[25] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In Hal Daume III and Aarti Singh, editors, Proceedings the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9259-9268. PMLR, 13-18 Jul 2020. URL attp://proceeding mlr, press/v119/ sundarara 2n20a. html.


Reviews:
[{"review_id": "qqtux32Tiye", "reviewer": "Reviewer_6Qs2", "summary": "In a cooperative game in characteristic function form, the value function $v$ maps from all subsets of agents, $N = {1, \\ldots, n}$, producing an image with $2^N$ elements.  Shapley's value (perhaps the most widely used measure of feature importance in handling ML's attribution problem) ascribes a number to each agent, for a set of $N$ values.  \n\nAs $N < 2^N$, Shapley's value does not - in general - fully encode the game.  An exception occurs when the game is _inessential_, so that $v(S) = \\sum_{i \\in S} v(i)$.  Specifically, when features _interact_, Shapley's value may be restrictive.\n\nThis paper builds on Stern and Tettenhorst's 2019 _Games and Economic Behavior_ paper, which provided a way of assessing a game's deviation from _inessentiality_, by means of Shapley residuals, $r_i$.\n\nDefinition 4 defines _Shapley residuals_, $r_S$, for sets of agents/features.  A series of results (Proposition 1, Corollaries 1, 2) then allow the norms of $r_S$ to be interpreted as a deviation from essentiality and - thus - a measure of Shapley's value's failure to fully encode the game.\n\nLemma 2 then makes precise the relationship between the absence of interactions between variables and inessentiality.\n\nSection 5 compares the Shapley residual to the Shapley-Taylor interaction index.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nThere is a lot of work on variants of Shapley values, with interaction effects being one focus of that.  This paper's approach, to consider the 'poorness of fit' of a Shapley value is, in my experience, novel.\n\n**Quality**\n\nIn general, I found the paper to be of high quality.\n\nThere are some minor errors which should be fixed:\n- lines 5-6 should probably not claim that Shapley values don't approximate the _game_: they're not meant to; they're meant to be fair values that could arise from _playing_ the game.  Maybe something like: \"Shapley values are a poor measure of interaction effects in the machine learning model, and corresponding game\"?\n- the example in lines 35-45 seems to get something wrong: we only have $f(g,d) > 0$ when $g$ and $d$ have _opposite_ signs.\n- line 113: should be $v(S \\cup i) - v(S)$, not $v(S \\cup i) - u(S)$\n- line 141: I think that this should read: \"_If_ $v$ is not inessential...\"\n\n**Clarity**\n\nThe paper was well and clearly written.\n\nI had trouble understanding the figures illustrating the paper's geometric methods.  I would therefore welcome suggestions from the authors about how these could be clarified.  Would illustrating the $n=2$ case be clearer?\n\n**Significance**\n\nMeasures of feature importance are clearly of importance to the ML community, and the Shapley family leads among these.  Thus, trying to understand its limitations is an important task.  This paper provides novel insights into that.\n\nThe paper emphasizes its differences with the Shapley-Taylor interaction index.  The paper would have felt a bit more rounded if it also compared the Shapley residuals to the Grabisch-Roubens index, which kick-started the interaction index literature.\n\nAs the paper's project is ultimately a negative one - to reveal when Shapley value fails to capture interactions - it leaves open the question of what 'the right' interaction index might be.  As the Shapley residuals live in the same space as interaction indices, it's not clear that computing one of these should be more expensive.  I accept the reply, though, that a paper along these lines is a separate paper.\n\nAs a sequel, it could be informative for the authors to compare various measures of joint feature importance in light of their residuals.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "pRfZsInoUg", "reviewer": "Reviewer_YXMR", "summary": "This paper introduces Shapley Residuals, a new measure that can be calculated in addition to SHAP values. This measure quantifies in some sense the information lost by Shapley Value due to interactions or correlations between features. This measure can help practitioners to identify scenarios when a score given to a certain feature by SHAP may not correctly quantify the effect of this feature on the prediction due to interactions or correlations. The paper provides theoretical grounding for the residuals, along with toy examples and an experiment with UCI dataset.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n\nthe paper is well written and provides a novel way to quantify the information lost by SHAP values, a well-known problem that has been investigated extensively in recent literature (https://arxiv.org/abs/2002.11097, https://arxiv.org/abs/1908.08474).\n\nThe authors provide a solid theoretical grounding for the new measure suggested and address the most common variants of SHAP. The paper contains several examples that are easy to understand and help motivate this work well. In addition, the authors describe in what sense the Shapley Residuals are different from existing feature interaction measures and also discuss the limitations of their work.\n\nWeaknesses: \nMy main concern about this paper is its maturity which can mainly affect its impact. As the authors describe in the paper, the use and meaning of their new suggested measure are not 100% clear yet. In addition, the authors do not suggest an efficient approximation for calculating the residuals, which makes this method currently not feasible for datasets with more than ~20 features.\n\nMoreover, I think that additional empirical results with real datasets might help to get a better understanding of how often these residuals can come into play (e.g as in https://arxiv.org/abs/2006.16234).\n\nOverall, IMHO the novelty and theoretical grounding of this work are worth publish and may enable further research to overcome the challenges I discussed above.\n\nAdditional notes:\nOn line 39 it said that f(g, d) > 0 iff g and d are for the same sign. If I follow correctly, the opposite is true.\nOn the end of line 113 u(S) should be \\nu(S)\nAlso in line 116 \\nu should be used instead of u\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think that the authors addressed these topics well", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "Txju8yvcDsP", "reviewer": "Reviewer_Tdmx", "summary": "This paper presents Shapley residual as a measure of player interactions for the interpretation games arising in machine learing applications.  The definition of Shapley residual is based on a classical notion of ineseentiality in cooperative games.  Intuitively, it captures how much deviation a game is from being inessential (or modular in combinatorics) .   ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality & quality:  \n\n-  I like the idea of introducing Shapley residuals as complementary information for black-box model interpretation, also the theoretical foundation from game inessentiality is solid, though the proofs do not need lots of creativity.  As far as I know, this is the paper adapted from one paper of ICML 2020 Workshop on Human Interpretability in Machine Learning (WHI 2020).\n\n- The algorithm for caculating Shapley residuals (Algorithm 1) needs exponential computational complexity (at least $2^n$),  it is better to explore a bit approximating algorithms, such as sampling based ones to have a speedup.\n\n\n\nClarity & experiments:  \n\n-  I like the illustrating examples  ($f_1, f_2$ and so on) along the main text. However, it is better to control the amount of illstration a bit, so you would have enough space for more technical details in the main text.  \n\n- Better to give a bit more detailed explanations of the experimental results. \n\n-  Though it is computationally intractable to precisely compute Shapley values, one can still compute them for games with player number up to, say 25.  Would be nice to see these results other than results with around 10 players.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No\n\nCould discuss potential negative societal impact resulted from biases when interpreating model outputs using Shapley values and Shapley residuals.   \n\n\n-------------------\nChange of the rate: \nI have read the feedback for me and also for other reviews. Some of the comments were not properly addressed. Also considering theoretical novelty, now I think the paper is bellow the acceptance bar. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Oa-yctkklAF", "reviewer": "Reviewer_tknB", "summary": "The authors focus on the limits of the Shapley value-based explanation that cannot explain the synergy effect among more than two features. To resolve this, they provide a new measurement called Shapley residual, which measure excess of adding a feature to some set of features. Experimental results show that the Shapley residual can capture more information that the Shapley cannot explain.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nIt seems to be a new insight for the Shapley-based explanation to measure a difference from inessentiality. This idea is completely converse from the previous work by [Stern and Tettenhorst 2019], who tries to approximate a game as a combination of inessential games.\n\nQuality:\n The proposed propositions seems to be technically sound and experimental results support claims of the paper.\n To my knowledge, the definition of the Shapley residual is new and the theoretical and experimental results are correct, but some theoretical results seem to be trivial, e.g., Proposition 1, and the definition does not seem to be sufficient to measure interactions among multi players (details are written in the significance).\n\nClarity:\nAlmost parts of the paper are well written and well-organized. I can easily follow the content.\n\nSignificance:\nThe definitions about Shapley residual (Definitions 3 and 4), that is, the definitions of $\\Delta_S$ and $r_S$,  does not seem to be sufficient for generalizing the marginal value contributed by more than two players. When we compute $r_S$, it lacks to measure the interaction among players S because $r_S$ is the summation of $r_i$. An easy example that the definition does not work is a supermodular game (or convex game). When we consider to add i and j to C on a supermodular function v, evidently the marginal values of summation of i and j and ij holds $v(C \\cup i) - v(C) + v(C \\cup j) - v(C) \\le v(C \\cup ij) - v(C)$, which implies proposed definition underestimate the marginal contribution and seems not care about the interaction between i and j for adding to C. So, I think it would be better to modify the definition for evaluating more accurately.\n\nTypo:\nIn Theorem 1, it would be better to use the same notation as this paper, that is, N should be written to [d].", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As described in the significance, a limitation of the paper is the definition of the Shapley residual, which may not evaluate the interaction of more than two players, which does not show that the Shapley residual works well on any cooperative games. Thus, I think the paper needs further generalization of the definitions.\nIn addition, as described in Conclusion section, the proposed spend exponential time in the number of players to find Shapley residual.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a way  to detect when local feature importance scores might be providing misleading signal due to feature interaction. This is an interesting problem that was not addressed before. The techniques used are not surprising but are sound. The main limitations of this work are the missing discussion about computational complexity and the fact that an earlier version of this paper appeared in an ICML workshop.
Decision: Accept (Poster)