Shapley, LIME and SHAP
Published on 2018-12-02

A coalitional game \((v, N)\) of \(n\) players involves

• The set \(N = \{1, 2, ..., n\}\) that represents the players.
• A function \(v: 2^N \to \mathbb R\), where \(v(S)\) is the worth of coalition \(S \subset N\).

The Shapley values \(\phi_i(v)\) of such a game specify a fair way to distribute the total worth \(v(N)\) to the players. It is defined as (in the following, for a set \(S \subset N\) we use the convention \(s = |S|\) to be the number of elements of set \(S\) and the shorthand \(S - i := S \setminus \{i\}\) and \(S + i := S \cup \{i\}\))

\[\phi_i(v) = \sum_{S: i \in S} {(n - s)! (s - 1)! \over n!} (v(S) - v(S - i)).\]

It is not hard to see that \(\phi_i(v)\) can be viewed as an expectation:

\[\phi_i(v) = \mathbb E_{S \sim \nu_i} (v(S) - v(S - i))\]

where \(\nu_i(S) = n^{-1} {n - 1 \choose s - 1}^{-1} 1_{i \in S}\), that is, first pick the size \(s\) uniformly from \(\{1, 2, ..., n\}\), then pick \(S\) uniformly from the subsets of \(N\) that has size \(s\) and contains \(i\).

The Shapley values satisfy some nice properties which are readily verified, including:

• Efficiency. \(\sum_i \phi_i(v) = v(N) - v(\emptyset)\).
• Symmetry. If for some \(i, j \in N\), for all \(S \subset N\), we have \(v(S + i) = v(S + j)\), then \(\phi_i(v) = \phi_j(v)\).
• Null player. If for some \(i \in N\), for all \(S \subset N\), we have \(v(S + i) = v(S)\), then \(\phi_i(v) = 0\).
• Linearity. \(\phi_i\) is linear in games. That is \(\phi_i(v) + \phi_i(w) = \phi_i(v + w)\), where \(v + w\) is defined by \((v + w)(S) := v(S) + w(S)\).

In the literature, an added assumption \(v(\emptyset) = 0\) is often given, in which case the Efficiency property is defined as \(\sum_i \phi_i(v) = v(N)\). Here I discard this assumption to avoid minor inconsistencies across different sources. For example, in the LIME paper, the local model is defined without an intercept, even though the underlying \(v(\emptyset)\) may not be \(0\). In the SHAP paper, an intercept \(\phi_0 = v(\emptyset)\) is added which fixes this problem when making connections to the Shapley values.

Conversely, according to Strumbelj-Kononenko (2010), it was shown in Shapley's original paper (Shapley, 1953) that these four properties together with \(v(\emptyset) = 0\) defines the Shapley values.

LIME (Ribeiro et. al. 2016) is a model that offers a way to explain feature contributions of supervised learning models locally.

Let \(f: X_1 \times X_2 \times ... \times X_n \to \mathbb R\) be a function. We can think of \(f\) as a model, where \(X_j\) is the space of $j$th feature. For example, in a language model, \(X_j\) may correspond to the count of the $j$th word in the vocabulary, i.e. the bag-of-words model.

The output may be something like housing price, or log-probability of something.

LIME tries to assign a value to each feature locally. By locally, we mean that given a specific sample \(x \in X := \prod_{i = 1}^n X_i\), we want to fit a model around it.

More specifically, let \(h_x: 2^N \to X\) be a function defined by

\[(h_x(S))_i = \begin{cases} x_i, & \text{if }i \in S; \\ 0, & \text{otherwise.} \end{cases}\]

That is, \(h_x(S)\) masks the features that are not in \(S\), or in other words, we are perturbing the sample \(x\). Specifically, \(h_x(N) = x\). Alternatively, the \(0\) in the "otherwise" case can be replaced by some kind of default value (see the section titled SHAP in this post).

For a set \(S \subset N\), let us denote \(1_S \in \{0, 1\}^n\) to be an $n$-bit where the $k$th bit is \(1\) if and only if \(k \in S\).

Basically, LIME samples \(S_1, S_2, ..., S_m \subset N\) to obtain a set of perturbed samples \(x_i = h_x(S_i)\) in the \(X\) space, and then fits a linear model \(g\) using \(1_{S_i}\) as the input samples and \(f(h_x(S_i))\) as the output samples:

*Problem*(LIME). Find \(w = (w_1, w_2, ..., w_n)\) that minimises

\[\sum_i (w \cdot 1_{S_i} - f(h_x(S_i)))^2 \pi_x(h_x(S_i))\]

where \(\pi_x(x')\) is a function that penalises $x'$s that are far away from \(x\). In the LIME paper the Gaussian kernel was used:

\[\pi_x(x') = \exp\left({- \|x - x'\|^2 \over \sigma^2}\right).\]

Then \(w_i\) represents the importance of the $i$th feature.

The LIME model has a more general framework, but the specific model considered in the paper is the one described above, with a Lasso for feature selection.

Remark. One difference between our account here and the one in the LIME paper is: the dimension of the data space may differ from \(n\) (see Section 3.1 of that paper). But in the case of text data, they do use bag-of-words (our \(X\)) for an "intermediate" representation. So my understanding is, in their context, there is an "original" data space (let's call it \(X'\)). And there is a one-one correspondence between \(X'\) and \(X\) (let's call it \(r: X' \to X\)), so that given a sample \(x' \in X'\), we can compute the output of \(S\) in the local model with \(f(r^{-1}(h_{r(x')}(S)))\). As an example, in the example of \(X\) being the bag of words, \(X'\) may be the embedding vector space, so that \(r(x') = A^{-1} x'\), where \(A\) is the word embedding matrix. Therefore, without loss of generality, we assume the input space to be \(X\) which is of dimension \(n\).

The connection between the Shapley values and LIME is noted in Lundberg-Lee (2017), but the underlying connection goes back to 1988 (Charnes et. al.).

To see the connection, we need to modify LIME a bit.

First, we need to make LIME less efficient by considering all the \(2^n\) subsets instead of the \(m\) samples \(S_1, S_2, ..., S_{m}\).

Then we need to relax the definition of \(\pi_x\). It no longer needs to penalise samples that are far away from \(x\). In fact, we will see later than the choice of \(\pi_x(x')\) that yields the Shapley values is high when \(x'\) is very close or very far away from \(x\), and low otherwise. We further add the restriction that \(\pi_x(h_x(S))\) only depends on the size of \(S\), thus we rewrite it as \(q(s)\) instead.

We also denote \(v(S) := f(h_x(S))\) and \(w(S) = \sum_{i \in S} w_i\).

Finally, we add the Efficiency property as a constraint: \(\sum_{i = 1}^n w_i = f(x) - f(h_x(\emptyset)) = v(N) - v(\emptyset)\).

Then the problem becomes a weighted linear regression:

Problem. minimises \(\sum_{S \subset N} (w(S) - v(S))^2 q(s)\) over \(w\) subject to \(w(N) = v(N) - v(\emptyset)\).

Claim (Charnes et. al. 1988). The solution to this problem is

\[w_i = {1 \over n} (v(N) - v(\emptyset)) + \left(\sum_{s = 1}^{n - 1} {n - 2 \choose s - 1} q(s)\right)^{-1} \sum_{S \subset N: i \in S} \left({n - s \over n} q(s) v(S) - {s - 1 \over n} q(s - 1) v(S - i)\right). \qquad (-1)\]

Specifically, if we choose

\[q(s) = c {n - 2 \choose s - 1}^{-1}\]

for any constant \(c\), then \(w_i = \phi_i(v)\) are the Shapley values.

Remark. Don't worry about this specific choice of \(q(s)\) when \(s = 0\) or \(n\), because \(q(0)\) and \(q(n)\) do not appear on the right hand side of (-1). Therefore they can be defined to be of any value. A common convention of the binomial coefficients is to set \({\ell \choose k} = 0\) if \(k < 0\) or \(k > \ell\), in which case \(q(0) = q(n) = \infty\).

In Lundberg-Lee (2017), \(c\) is chosen to be \(1 / n\), see Theorem 2 there.

In Charnes et. al. 1988, the $w_i$s defined in (-1) are called the generalised Shapley values.

Proof. The Lagrangian is

\[L(w, \lambda) = \sum_{S \subset N} (v(S) - w(S))^2 q(s) - \lambda(w(N) - v(N) + v(\emptyset)).\]

and by making \(\partial_{w_i} L(w, \lambda) = 0\) we have

\[{1 \over 2} \lambda = \sum_{S \subset N: i \in S} (w(S) - v(S)) q(s). \qquad (0)\]

Summing (0) over \(i\) and divide by \(n\), we have

\[{1 \over 2} \lambda = {1 \over n} \sum_i \sum_{S: i \in S} (w(S) q(s) - v(S) q(s)). \qquad (1)\]

We examine each of the two terms on the right hand side.

Counting the terms involving \(w_i\) and \(w_j\) for \(j \neq i\), and using \(w(N) = v(N) - v(\emptyset)\) we have

\[\begin{aligned} &\sum_{S \subset N: i \in S} w(S) q(s) \\ &= \sum_{s = 1}^n {n - 1 \choose s - 1} q(s) w_i + \sum_{j \neq i}\sum_{s = 2}^n {n - 2 \choose s - 2} q(s) w_j \\ &= q(1) w_i + \sum_{s = 2}^n q(s) \left({n - 1 \choose s - 1} w_i + \sum_{j \neq i} {n - 2 \choose s - 2} w_j\right) \\ &= q(1) w_i + \sum_{s = 2}^n \left({n - 2 \choose s - 1} w_i + {n - 2 \choose s - 2} (v(N) - v(\emptyset))\right) q(s) \\ &= \sum_{s = 1}^{n - 1} {n - 2 \choose s - 1} q(s) w_i + \sum_{s = 2}^n {n - 2 \choose s - 2} q(s) (v(N) - v(\emptyset)). \qquad (2) \end{aligned}\]

Summing (2) over \(i\), we obtain

\[\begin{aligned} &\sum_i \sum_{S: i \in S} w(S) q(s)\\ &= \sum_{s = 1}^{n - 1} {n - 2 \choose s - 1} q(s) (v(N) - v(\emptyset)) + \sum_{s = 2}^n n {n - 2 \choose s - 2} q(s) (v(N) - v(\emptyset))\\ &= \sum_{s = 1}^n s{n - 1 \choose s - 1} q(s) (v(N) - v(\emptyset)). \qquad (3) \end{aligned}\]

For the second term in (1), we have

\[\sum_i \sum_{S: i \in S} v(S) q(s) = \sum_{S \subset N} s v(S) q(s). \qquad (4)\]

Plugging (3)(4) in (1), we have

\[{1 \over 2} \lambda = {1 \over n} \left(\sum_{s = 1}^n s {n - 1 \choose s - 1} q(s) (v(N) - v(\emptyset)) - \sum_{S \subset N} s q(s) v(S) \right). \qquad (5)\]

Plugging (5)(2) in (0) and solve for \(w_i\), we have

\[w_i = {1 \over n} (v(N) - v(\emptyset)) + \left(\sum_{s = 1}^{n - 1} {n - 2 \choose s - 1} q(s) \right)^{-1} \left( \sum_{S: i \in S} q(s) v(S) - {1 \over n} \sum_{S \subset N} s q(s) v(S) \right). \qquad (6)\]

By splitting all subsets of \(N\) into ones that contain \(i\) and ones that do not and pair them up, we have

\[\sum_{S \subset N} s q(s) v(S) = \sum_{S: i \in S} (s q(s) v(S) + (s - 1) q(s - 1) v(S - i)).\]

Plugging this back into (6) we get the desired result. \(\square\)

The paper that coined the term "SHAP values" (Lundberg-Lee 2017) is not clear in its definition of the "SHAP values" and its relation to LIME, so the following is my interpretation of their interpretation model, which coincide with a model studied in Strumbelj-Kononenko 2014.

Recall that we want to calculate feature contributions to a model \(f\) at a sample \(x\).

Let \(\mu\) be a probability density function over the input space \(X = X_1 \times ... \times X_n\). A natural choice would be the density that generates the data, or one that approximates such density (e.g. empirical distribution).

The feature contribution (SHAP value) is thus defined as the Shapley value \(\phi_i(v)\), where

\[v(S) = \mathbb E_{z \sim \mu} (f(z) | z_S = x_S). \qquad (7)\]

So it is a conditional expectation where \(z_i\) is clamped for \(i \in S\). In fact, the definition of feature contributions in this form predates Lundberg-Lee 2017. For example, it can be found in Strumbelj-Kononenko 2014.

One simplification is to assume the \(n\) features are independent, thus \(\mu = \mu_1 \times \mu_2 \times ... \times \mu_n\). In this case, (7) becomes

\[v(S) = \mathbb E_{z_{N \setminus S} \sim \mu_{N \setminus S}} f(x_S, z_{N \setminus S}) \qquad (8)\]

For example, Strumbelj-Kononenko (2010) considers this scenario where \(\mu\) is the uniform distribution over \(X\), see Definition 4 there.

A further simplification is model linearity, which means \(f\) is linear. In this case, (8) becomes

\[v(S) = f(x_S, \mathbb E_{\mu_{N \setminus S}} z_{N \setminus S}). \qquad (9)\]

It is worth noting that to make the modified LIME model considered in the previous section fall under the linear SHAP framework (9), we need to make two further specialisations, the first is rather cosmetic: we need to change the definition of \(h_x(S)\) to

\[(h_x(S))_i = \begin{cases} x_i, & \text{if }i \in S; \\ \mathbb E_{\mu_i} z_i, & \text{otherwise.} \end{cases}\]

But we also need to boldly assume the original \(f\) to be linear, which in my view, defeats the purpose of interpretability, because linear models are interpretable by themselves.

One may argue that perhaps we do not need linearity to define \(v(S)\) as in (9). If we do so, however, then (9) loses mathematical meaning. A bigger question is: how effective is SHAP? An even bigger question: in general, how do we evaluate models of interpretation?

The quest of the SHAP paper can be decoupled into two independent components: showing the niceties of Shapley values and choosing the coalitional game \(v\).

The SHAP paper argues that Shapley values \(\phi_i(v)\) are a good measurement because they are the only values satisfying the some nice properties including the Efficiency property mentioned at the beginning of the post, invariance under permutation and monotonicity, see the paragraph below Theorem 1 there, which refers to Theorem 2 of Young (1985).

Indeed, both efficiency (the "additive feature attribution methods" in the paper) and monotonicity are meaningful when considering \(\phi_i(v)\) as the feature contribution of the $i$th feature.

The question is thus reduced to the second component: what constitutes a nice choice of \(v\)?

The SHAP paper answers this question with 3 options with increasing simplification: (7)(8)(9) in the previous section of this post (corresponding to (9)(11)(12) in the paper). They are intuitive, but it will be interesting to see more concrete (or even mathematical) justifications of such choices.

• Charnes, A., B. Golany, M. Keane, and J. Rousseau. "Extremal Principle Solutions of Games in Characteristic Function Form: Core, Chebychev and Shapley Value Generalizations." In Econometrics of Planning and Efficiency, edited by Jati K. Sengupta and Gopal K. Kadekodi, 123–33. Dordrecht: Springer Netherlands, 1988. https://doi.org/10.1007/978-94-009-3677-5_7.
• Lundberg, Scott, and Su-In Lee. "A Unified Approach to Interpreting Model Predictions." ArXiv:1705.07874 [Cs, Stat], May 22, 2017. http://arxiv.org/abs/1705.07874.
• Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. "'Why Should I Trust You?': Explaining the Predictions of Any Classifier." ArXiv:1602.04938 [Cs, Stat], February 16, 2016. http://arxiv.org/abs/1602.04938.
• Shapley, L. S. "17. A Value for n-Person Games." In Contributions to the Theory of Games (AM-28), Volume II, Vol. 2. Princeton: Princeton University Press, 1953. https://doi.org/10.1515/9781400881970-018.
• Strumbelj, Erik, and Igor Kononenko. "An Efficient Explanation of Individual Classifications Using Game Theory." J. Mach. Learn. Res. 11 (March 2010): 1–18.
• Strumbelj, Erik, and Igor Kononenko. "Explaining Prediction Models and Individual Predictions with Feature Contributions." Knowledge and Information Systems 41, no. 3 (December 2014): 647–65. https://doi.org/10.1007/s10115-013-0679-x.
• Young, H. P. "Monotonic Solutions of Cooperative Games." International Journal of Game Theory 14, no. 2 (June 1, 1985): 65–72. https://doi.org/10.1007/BF01769885.