added a post

1 files changed, 295 insertions, 0 deletions

diff --git a/posts/2018-12-02-lime-shapley.md b/posts/2018-12-02-lime-shapley.md
new file mode 100644
index 0000000..88b1b20
--- /dev/null
+++ b/posts/2018-12-02-lime-shapley.md
@@ -0,0 +1,295 @@
+---
+title: Shapley, LIME and SHAP
+date: 2018-12-02
+template: post
+comments: true
+---
+
+In this post I explain LIME (Ribeiro et. al. 2016), the Shapley values
+(Shapley, 1953) and the SHAP values (Lundberg-Lee, 2017).
+
+Shapley values {#Shapley values}
+--------------
+
+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)).$$
+
+$\phi_i(v)$ is 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}**Efficiency**.
+    $\sum_i \phi_i(v) = v(N) - v(\emptyset)$.
+-   []{#Symmetry}**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}**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}**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 {#LIME}
+----
+
+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 be the count
+of the $j$th word in the vocabulary.
+
+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 last section of 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}**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.
+
+Shapley values and LIME {#Shapley values and LIME}
+-----------------------
+
+The connection between the Shapley values and LIME is noted in
+Lundberg-Lee (2016), 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}**Problem**. minimises
+$\sum_{S \subset N} (w(S) - v(S))^2 q(s)$ over $w$ subject to
+$w(N) = v(N) - v(\emptyset)$.
+
+[]{#Claim}**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}**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.
+
+[]{#Proof}**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 \subset N} s q(s) v(S) - \sum_{s = 1}^n s {n - 1 \choose s - 1} q(s) (v(N) - v(\emptyset))\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$
+
+SHAP {#SHAP}
+----
+
+The SHAP paper (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.
+
+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$.
+
+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 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 a further specialisation, that is, 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}$$
+
+How about DeepLIFT? {#How about DeepLIFT?}
+-------------------
+
+TODO
+
+References {#References}
+----------
+
+-   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.