Shapley Residuals: Quantifying the limits of the Shapley value for explanations
Year: 2021

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.

heading: 1 Introduction
text: 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 a 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 or technical notions of feature importance [10, 21, 24]. A particularly salient issue is that users have misconceptions about what Shapley values represent and what actionable 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., so that increasing a variable value changes the model outcome in a 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-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 (NeurIPS 2021).
variables, as well as with sets of variables. When the residual of a feature exhibits a 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 a 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) = g + d 2dg, where g = 1 if the applicant is male and g = 1 otherwise, and there are two departments, represented by d = 1 and d = 1. In this contrived scenario, the applicant is admitted if f(g, d) > 0 (which only happens when g and d have different signs) and is rejected otherwise. Clearly, the admissions decision is affected by gender–yet if each of the two variables are distributed with mean 0, the KernelSHAP values [12] which are supposed to explain the decision f(1, 1) = 0 are both 0, 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 a discriminatory effect, and the corresponding nonzero Shapley residuals would demonstrate that the Shapley values are not telling the whole story.
To more precisely describe what Shapley residuals capture, consider the following two motivating scenarios. First, suppose a practitioner uses Shapley values to determine the effect of data interventions on model outcomes. Consider two models f1 and f2. 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:
f1(x1, x2, x3) = x1 + x2 + x3 f2(x1, x2, x3) = x1 + 2x2x3
Suppose the practitioner seeks to explain the output f1(1, 1, 1) = 3 or f2(1, 1, 1) = 3, using KernelSHAP to compute local feature importances. For both models, the Shapley values of x1, x2, and x3 are all 1. Despite that, intervening by increasing the value of x2 changes f2 more than increasing the value of x1; in f1, this clearly does not happen. The Shapley residuals for all variables in f1 are zero, indicating that variables in f1 do not interact (as we prove in Section 3). The Shapley residuals for x2 and x3 in f2, on the other hand, are nonzero, while the Shapley residual of x1 is still zero. Finally, the Shapley residual for the set of variables {x2, x3} is also zero. As we 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); x2 and x3 interact with other variables (their residuals are non zero); x2 and x3 only interact with each other (the residual of the set {x2, x3} is zero). Thus, access to Shapley residuals gives warning that intervening on x2 or x3 in f2 could act differently than x1 due to an interaction between x2 and x3.
In the second scenario, consider a data generating distribution where ↵ controls the correlation between two features in X and a regression target y:
(X, y) ⇠ ✓ N ✓ (0, 0),  1 ↵ ↵ 1 ◆ , hX, (3, 1)i ◆ .
We examine a regression model f(x1, x2) = 1x1+ 2x2 determined via linear least squares. Assume access to infinitely many IID samples from (X, y), = (3, 1). Suppose a practitioner wanted to explain the output of f(1, 1) = 1 + 2, this time using Conditional Expectation SHAP [24]. The Shapley values are 1 + ↵( 2 1)/2 for x1 and 2 + ↵( 1 2)/2 for x2. When ↵ ⇡ 0, Shapley values correspond to model weights 1, 2, and support a (valid) interventional interpretation that changing x1 yields a larger change to the output of f than does x2. However, if ↵ ⇡ 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 x1 and x2 is exactly linearly proportional to ↵.
In these simple scenarios, it 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 of Shapley residuals both in general and in context of existing formulations for explanatory games (Sections 3, 4 and 5),
• show via a 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).

heading: 2 Background
text: 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 = x1 + 2x2x3; 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 v : 2[d] ! R where [d] , {1, . . . , d}. The quantity v(S) represents the value of the game for a coalition of players S 2 N , 2[d]. Without loss of generality we will assume that v(;) = 0, and that we can identify the game with v. Let the space of games be denoted by G. The Shapley value is a way to fairly allocate the value of the grand coalition v([d]) among the players. Definition 1 (Shapley values[20]). The Shapley values i(v), i 2 [d] are the unique values satisfying the properties
Efficiency: Pd
i=1 i(v) = v([d]).
Dummy: If v(S [ {i}) = v(S) for all S ⇢ [d] \ {i}, then i(v) = 0.
Symmetry: If v(S [ {i}) = v(S [ {j}) for all S ⇢ [d] \ {i, j}, then i(v) = j(v).
Linearity: If v, v0 are two games on d players, then i(↵v + ↵0v0) = ↵ i(v) + ↵0 i(v0).
Given a model f(x1, x2, ..., xd), the features from 1 to d can be considered players in a game in which the payoff v is some measure of the importance or influence of a subset of features. The Shapley value i(v) can then be viewed as a fairly attributed “influence" of i on the outcome v([d]). In KernelSHAP, for instance, a function’s prediction on a certain input given a data distribution is modeled as a game as shown in Table 1.
It will be useful for us to visualize a game as a function over the vertices of a d-dimensional hypercube. Each coordinate corresponds to the presence or absence of a certain player, and each vertex corresponds to a subset of players. Specifically, we can think of the set N as the d-dimensional hypercube G = (V = N,E) with each vertex labeled by a set S ✓ [d] and edges between sets S and S [ {i} for all i 2 [d], S. We depict this interpretation in Figure 1(a).
Gradients on the hypercube. Let RV be the space of functions from V to R and let RE be the space of functions from E to R. In particular, the game v is an element of RV . The differential operator r : RV ! RE is then defined as rv(S, S [ {i}) = v(S [ i) v(S) for any v 2 RV . Essentially r is a discrete gradient operator on G, mapping functions on vertices to functions on edges (see Figure 1(b)).
We will also define a partial gradient ri : RV ! RE :
riu(S, S [ {j}) = ⇢ u(S [ j) u(S) i = j 0 otherwise
Intuitively, ri evaluates a 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 riv will take a nonzero value. See the Edge Space portion of Figure 2(a) for an illustration of this procedure on the running example.

heading: 2.1 Geometric characterization of Shapley values
text: A 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 a 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 v such that for all S ✓ [d], v(S) =P i2S v({i}). I 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 a coalition S independent of the composition of S. Inessentiality is a key feature of what makes Shapley values attractive for feature importance – if each contribution is fixed and combines additively, we have a natural interpretation for how much each feature contributes to the overall model output. Specifically, if a game is inessential, it then follows that the Shapley value for player i is v({i}). In our running example using KernelSHAP, this is E[f(x)|xi = 1], the contribution (averaged over other variables) of the variable xi.
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 v is inessential if and only if for each i 2 [d] there exists vi 2 RV such that riv = rvi.
The main result by Stern and Tettenhorst [22] is a decomposition of an arbitrary game v into games that are “close to being inessential” and allow extraction of Shapley values. If v is not inessential, we cannot be sure to find vi such that riv = rvi, but we can find the “closest” such vi as the solution to the least squares problem
min x2RV ,x(;)=0 krx rivk
Theorem 1 (Stern and Tettenhorst [22]). Given a game v, let vi be defined as above. Then
1. P
vi = v
2. If v(S [ {i}) = v(S) for all S ⇢ [d], then vi = 0
3. For any ↵,↵0 2 R and games v, v0, (↵v + ↵0v0)i = ↵vi + ↵0v0i 4. If ⇡ is a permutation of [d] and ⇡ v is the game ⇡ v(S) = v(⇡(S)), then (⇡ v)i = v⇡(i)
Consider the mapping (v)(S) = P
i2S vi([d]). The above result implies this is a Shapley mapping and therefore i(v) = vi([d]) are the Shapley values of v. We illustrate the construction in Figure 2(a).

heading: 3 Shapley Residuals
text: The inessentiality of a 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 is 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
riv = rvi + ri where ri is orthogonal to rvi. This allows us to interpret ri (a vector with one value for each edge of the hypercube) as a measure of deviation from inessentiality, because by Proposition 1, this vector is identically 0 if 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 v is inessential relative to S if v(C) = v(S) + v(C \ S) for all S and C such that S ⇢ C ⇢ [d].
That is, each coalition containing S obtains a value equal to the subcoalition S working separately from C \ S; in this sense, inessentiality with respect to S can speak to the lack of interactions between S and its complement. In addition, inessentiality relative to a single player i is the same as inessentiality relative to the singleton set {i}. Next, we generalize the notion of a partial derivative. Definition 3. For a subset S ⇢ [d], let rS: RV ! RE be the operator rS = P i2S ri, or
rSu(C,C [ {j}) = ⇢
ru (C,C [ {i}) if i = j and i 2 S, 0 otherwise.
We can now prove a result similar to Proposition 1 for relative inessentiality. Proposition 2. The game v is inessential relative to S if and only if there exists vS 2 RV such that rSv = rvS .
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 ri = riv rvi the Shapley Residual of player i. Analogously, rS = P i2S ri is the Shapley Residual of set S.
Shapley Residuals are a novel diagnostic tool for feature importance, and enjoy a number of relevant properties. Proposition 3. If v is inessential, then v is inessential relative to all i 2 [d] and all subsets S ⇢ [d]. If v is inessential with respect to each player of i, j, . . . z then v is inessential relative to the set {i, j, . . . , z}.
The proof of this proposition is in the appendix. The following corollaries are straightforward. Corollary 1. v is inessential iff ri = 0 for each i 2 [d]. Corollary 2. v is inessential relative to S iff rS = P i2S ri = 0. This allows us to interpret P i2N ||ri||2 as the deviation from inessentiality of v and || P
i2S ri||2 as the deviation from inessentiality of v relative to S.
In this paper we will focus on the computation and evaluation of residuals with respect to individual players i.e rS for S = {i}. Figure 2(b) illustrates the construction of residuals. Algorithm 1 describes how to compute residuals.1
Algorithm 1 Exactly calculate the ith Shapley value and Shapley residual of v Compute riv Solve vi = argminx2RV ||riv rx||22 Compute rvi Return Shapley residual ri = riv rvi Return Shapley value i = vi(S) vi(;) where S is the set of all players

heading: 4 Feature Importance, Inessentiality and Residuals
text: We have established that the norm of the residual ri characterizes the degree to which the value function v is not inessential with respect to the player i. 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 a specific choice for the game v, at which point the Shapley values of v are estimated and returned [24, 10, 16].
The definitions of Shapley sampling values [23], as well as SHAP values [12], are derived from defining v as the conditional expected model output on a data point when only the features in S are known: vCondf,x (S) = E[f(X)|XS = xS ] 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 an expectation of f over the joint distribution of S̄ while fixing the feature values from S: v Int f,x (S) = E[f([xS ,XS̄ ])] Notably, the two values are the same if the features in S̄ are independent from those in S.
We will show that the residual rS captures the degree to which interactions between the features in S and its complement arise in the model or in the data, depending on which form of Shapley-based feature importance is used to define the value function v.
1We can take an unconstrained minimum here and subtract vi(;) at the end because adding a constant value to v does not change rv.

heading: 4.1 Inessentiality and Interactions
text: Interventional SHAP Recall the problem of explaining two models where f1(x1, x2, x3) = x1 + x2 + x3 and f2(x1, x2, x3) = x1 + 2x2x3. Note that in the first model all three variables contribute independently to the model output, whereas in the second model the variables x2 and x3 interact in their contribution. We can compute the associated residuals r1, r2, r3 and their norms for these two models. For the first one, all residuals are identically zero. However, in the second model if x2 and x3 are nonzero for a certain input, they will have a 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 1. Let f : X = {X1, X2, ..., Xd} ! Y be a multivariate function. Suppose f can be decomposed as f(x) = g(xS) + h(xS̄), for some functions g : {Xj : j 2 S} ! Y and h : {Xj : j 62 S} ! Y . Let z = {z1, z2, ..., zn} 2 X . Then vIntf,z is relatively inessential with respect to the set S.
This is important because if the model really does decompose additively for a certain variable i, the practitioner understands what to expect when variable i 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 a model, the residuals of Conditional Expectation SHAP can detect feature interactions in the data. Let X ⇠ N ([0, 0]T ,⌃) for ⌃ =  1 ↵ ↵ 1 , and let Y = f(X) =
TX (note that ordinary least squares will recover f in the limit of infinite data). Given input x1, x2,
the SHAP values of f are 1 = 1x1 + ↵ 2x1 1x22 2 = 2x2 + ↵ 1x2 2x1 2 . That is to say, they are linearly dependent on the correlation between the two variables. In particular, consider explaining the input [1, 1] to the function x1 + 3x2; the SHAP values are 1 = 1 + ↵ and 2 = 3 ↵ and the residuals are both 2↵. Notably, as interaction between variables increases in the data (measured by ↵), the residual increases and the SHAP values deviate further and further from the coefficients of the actual model. We can make this intuition precise. Lemma 2. Let f : X = {X1, X2, ..., Xd} ! Y be a multivariate function. Suppose f can be decomposed as f(x) = g(xS) + h(xS̄), for some functions g : {Xj : j 2 S} ! Y and h : {Xj : j 62 S} ! Y . Let z = {z1, z2, ..., zn} 2 X . Suppose further that all Xj : j 2 S are distributed independently from all Xj : j 62 S. Then vCondf,z is relatively inessential with respect to set S.
The residual on Conditional Expectation SHAP thus quantifies the extent to which an interpretation of the SHAP values can be interpreted as interventional, because depending on the causal structure of the data, correlated features could imply that perturbing a feature i could result in the perturbation of a different feature as well.
Inspecting Shapley residuals in practice Shapley residuals are vectors in the same space as gradients, and are generally high-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.

heading: 5 Relationship with Other Interaction Indices
text: [25], similarly recognizing that Shapley values lose information about interactions, proposed ShapleyTaylor Interaction Indices, a generalization of Shapley values which attributes influence among interaction terms. Specifically, the Shapley-Taylor explanation for x of order k assigns values IkS to subsets of features S of size |S|  k such that P I k S = f(x). The terms for the subsets for which |S| < k represent a discrete Taylor series around v(;). When |S| = k, IkS is defined similarly to the Shapley value: a discrete derivative averaged over permutations.
Our residuals capture fundamentally different information about interactions than Shapley-Taylor. Consider some subset S for which |S| < k. Our residual rS is 0 when the marginal value of adding S to a coalition W is constant with respect to sets for which W \ S = ;; in other words, it is about the presence or absence of interactions of S with other variables. The Shapley-Taylor interaction index IkS , on the other hand, is 0 when v(S) can be inferred from the values of v(W ) for {W ⇢ 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 a certain game v({i}) + v({j}) = v({i, j}), this means that the term v({i, j}) provides no interaction information about the two players, and Ik{i,j} 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 S is involved. Consider a three-player game between a, b, and c, where v({a}) + v({b}) = v({a, b}) and v({a}) + v({c}) = v({a, c}); this would make Ik{a,b} and I k {a,c} equal to 0, implying that a and b do not interact, and a and c do not interact. But it could be that v is not relatively inessential with respect to a. If v({a, b, c}) v({b, c}) 6= v({a, c}) v({c}), then a’s relative contribution with respect to c changes once b is involved. This constitutes an interaction between a and c that is not described by the Shapley-Taylor index for {a, c}, but is rather captured by the third-order interaction of {a, b, c}. In this scenario, our residuals would show ra 6= 0, alerting us to the fact that a interacts with {b, c}; additionally, it would have r{a,b} 6= 0, alerting us to the fact that {a, b} interacts with c. In general, since ri 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 9i 2 S s.t ri = 0, then the Shapley-Taylor index IkS = 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 a general class of interaction indexes investigated in a long line of work starting with [17] and surveyed in [6] (including the Grabisch-Roubens[7] Shapley and Banzhaf interaction 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 based on a different notion of a derivative.

heading: 6 Experiments
text: Having theoretically justified Shapley residuals in previous sections, we now focus on illustrating what these residuals can help us understand about models on a real-world dataset. Throughout, we use our own implementation of KernelSHAP to calculate the exact Shapley values and residuals (see Algorithm 1 in Section 3).2 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 an “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 a clear objective to compare against. Such an objective doesn’t 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, Shapley-Taylor indices and Shapley residuals appear to capture different kinds of interactions that are potentially of interest to a user. There is no meaningful way to compare them in a vacuum because one is not "better" than another.
Variable Interactions in Occupancy Detection Consider the Shapley values and residuals for an occupancy detection dataset3 (20,560 instances) used to predict whether an office room is occupied. The 7 attributes include a 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
2Code is provided in the supplementary material 3https://archive.ics.uci.edu/ml/datasets/Occupancy+Detection+
evaluated on the remaining test set, the ROC-AUC for this decision tree is 0.991. We then calculate the 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 a 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 a mix of low and high predictions. These average to 0.4, while both the overall expectation and particular prediction for occupancy probability for those points are 0.25.
Specifically, the KernelSHAP game for f(H,L) = P (occupant = T ) for L = 320 and H = 10 is shown in Figure 4. L = 320 is a positive indicator of occupancy if H is unknown (+.16) but is a “negative” indicator of occupancy is H is known to be 10 (-.24), due to the interactions in the model in this area of the feature space. The light Shapley value is close to 0 for points in this range, then, because it is the average of a positive and negative number – not because it is of “low importance” – and the non-inessentiality of this feature is what is being captured by the residual.

heading: 7 Limitations and Future Work
text: Usability considerations Our motivation for this work is to contribute further to the theoretical foundation of Shapley-value-based feature importance measures and, critically, to 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 to make better decisions about their models. An empirical, human-centered 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 a partial evaluation of the game vector [12, 11], which provides analysts with results even in high-dimensional 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 a billion elements). Since the derivative operator is sparse and well-conditioned, the least squares problem is efficiently solved by the LSQR method [18]. Still, in future work, we hope to efficiently identify whether a particular residual is nonzero, and approximate properties of residuals which capture the entirety of non-linear interactions of a particular feature.
Conclusion A goal in interpretable machine learning, and within Shapley-value-based feature importance, is to give a 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 on solid theoretical grounds is important for the validity of these feature importance claims. Their validity is an important part of the ethics of algorithms as societal interventions.

heading: 8 Acknowledgements
text: This research was funded in part by the NSF under grants DMR 1928882, IIS 1955162, and IIS 1956286, and by the DARPA SD2 program.

Review summaries:
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) .   

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.

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. 

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.    As $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.  This 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$.  Definition 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.  Lemma 2 then makes precise the relationship between the absence of interactions between variables and inessentiality.  Section 5 compares the Shapley residual to the Shapley-Taylor interaction index.