Shapley Values
\( \newcommand{\states}{\mathcal{S}} \newcommand{\actions}{\mathcal{A}} \newcommand{\observations}{\mathcal{O}} \newcommand{\rewards}{\mathcal{R}} \newcommand{\traces}{\mathbf{e}} \newcommand{\transition}{P} \newcommand{\reals}{\mathbb{R}} \newcommand{\naturals}{\mathbb{N}} \newcommand{\complexs}{\mathbb{C}} \newcommand{\field}{\mathbb{F}} \newcommand{\numfield}{\mathbb{F}} \newcommand{\expected}{\mathbb{E}} \newcommand{\var}{\mathbb{V}} \newcommand{\by}{\times} \newcommand{\partialderiv}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\defineq}{\stackrel{{\tiny\mbox{def}}}{=}} \newcommand{\defeq}{\stackrel{{\tiny\mbox{def}}}{=}} \newcommand{\eye}{\Imat} \newcommand{\hadamard}{\odot} \newcommand{\trans}{\top} \newcommand{\inv}{{-1}} \newcommand{\argmax}{\operatorname{argmax}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\avec}{\mathbf{a}} \newcommand{\bvec}{\mathbf{b}} \newcommand{\cvec}{\mathbf{c}} \newcommand{\dvec}{\mathbf{d}} \newcommand{\evec}{\mathbf{e}} \newcommand{\fvec}{\mathbf{f}} \newcommand{\gvec}{\mathbf{g}} \newcommand{\hvec}{\mathbf{h}} \newcommand{\ivec}{\mathbf{i}} \newcommand{\jvec}{\mathbf{j}} \newcommand{\kvec}{\mathbf{k}} \newcommand{\lvec}{\mathbf{l}} \newcommand{\mvec}{\mathbf{m}} \newcommand{\nvec}{\mathbf{n}} \newcommand{\ovec}{\mathbf{o}} \newcommand{\pvec}{\mathbf{p}} \newcommand{\qvec}{\mathbf{q}} \newcommand{\rvec}{\mathbf{r}} \newcommand{\svec}{\mathbf{s}} \newcommand{\tvec}{\mathbf{t}} \newcommand{\uvec}{\mathbf{u}} \newcommand{\vvec}{\mathbf{v}} \newcommand{\wvec}{\mathbf{w}} \newcommand{\xvec}{\mathbf{x}} \newcommand{\yvec}{\mathbf{y}} \newcommand{\zvec}{\mathbf{z}} \newcommand{\Amat}{\mathbf{A}} \newcommand{\Bmat}{\mathbf{B}} \newcommand{\Cmat}{\mathbf{C}} \newcommand{\Dmat}{\mathbf{D}} \newcommand{\Emat}{\mathbf{E}} \newcommand{\Fmat}{\mathbf{F}} \newcommand{\Gmat}{\mathbf{G}} \newcommand{\Hmat}{\mathbf{H}} \newcommand{\Imat}{\mathbf{I}} \newcommand{\Jmat}{\mathbf{J}} \newcommand{\Kmat}{\mathbf{K}} \newcommand{\Lmat}{\mathbf{L}} \newcommand{\Mmat}{\mathbf{M}} \newcommand{\Nmat}{\mathbf{N}} \newcommand{\Omat}{\mathbf{O}} \newcommand{\Pmat}{\mathbf{P}} \newcommand{\Qmat}{\mathbf{Q}} \newcommand{\Rmat}{\mathbf{R}} \newcommand{\Smat}{\mathbf{S}} \newcommand{\Tmat}{\mathbf{T}} \newcommand{\Umat}{\mathbf{U}} \newcommand{\Vmat}{\mathbf{V}} \newcommand{\Wmat}{\mathbf{W}} \newcommand{\Xmat}{\mathbf{X}} \newcommand{\Ymat}{\mathbf{Y}} \newcommand{\Zmat}{\mathbf{Z}} \newcommand{\Sigmamat}{\boldsymbol{\Sigma}} \newcommand{\identity}{\Imat} \newcommand{\epsilonvec}{\boldsymbol{\epsilon}} \newcommand{\thetavec}{\boldsymbol{\theta}} \newcommand{\phivec}{\boldsymbol{\phi}} \newcommand{\muvec}{\boldsymbol{\mu}} \newcommand{\sigmavec}{\boldsymbol{\sigma}} \newcommand{\jacobian}{\mathbf{J}} \newcommand{\ind}{\perp!!!!\perp} \newcommand{\bigoh}{\text{O}} \)
- tags
- Causality
DONE What are shapley values?
Shapley values are a solution for a coalitional game. Specifically, they assign a value or payout according to the a player’s contribution to the overall teams win/objective/yada.
For a linear function:
\[\hat{f}(x) = \eta + \sum_{i=1}^N \beta_i x_i\]
Where \(x_i\) are the features and \(\beta_i\) are the weights of the linear function. The contribution of the $j$-th feature from instance \(\mathbf{x}\in\mathcal{X}\) is
\[\phi_j(\mathbf{x}) = \beta_j (\mathbf{x}_j - \expected[X_j])\].
for more general functions, we can’t rule out interactions between different features in the function and thus must effectively marginalize over these interactions.
\begin{align*} \phi_j(val) &= \sum_{S\subset\{1, \ldots, p\}/\{j\}} \frac{|S|! (p - |S| - 1)!}{p!} (val(S\cup\{j\}) - val(S)) \\ val_x(S) &= \int \hat{f}(\mathbf{x}) d\mathbb{P}_{X \notin S} - \expected[\hat{f}(\mathbf{x})] \end{align*}
(Molnar 2021)
(Lundberg and Lee 2017)
(Singal, Michailidis, and Ng 2021)
(Heskes et al. 2020)
(Ma and Tourani 2020)
Prove that blindly using shapley values to identify/interpret/explain a model is not appropriate. Specifically, they provde two counter examples where they show the important features aren’t guaranteed to have the largest shapley value (as compared to other features), and that the sum of SVs also don’t correspond directly with the intuitive assumption.
DONE How do we estimate Shapley Values?
(Strumbelj and Kononenko 2014)
A monte carlo method which approximates the shapley value as
\[\phi_i (x) = \frac{1}{M} \sum_{m=1}^M \hat{f}(x_{+j}) - \hat{f}(x_{-j}) \]
where \(x_{+j} = (x_1, \ldtos, x_{j-1}, x_j, z_{j+1}, \ldots)\) and \(x_{-j} = (x_1, \ldtos, x_{j-1}, z_j, z_{j+1}, \ldots)\). \(z\) is another instance sampled from the dataset. The order of features is randomly ordered.
(Song, Nelson, and Staum 2016)
The Shapley effect results in the same value as the Shapley value, but gives a different direction for optimization. To measure the global sensitivity of a function according to a set of features you can calculate the value:
\[ v_i = \sum_{\mathcal{J}\subset\mathcal{k}\\{i\}} \frac{(k - |\mathcal{J}| - 1)! |\mathcal{J}|!}{k!} (c(P_i(\pi) \cum {i}) - c(P_i(\pi)))\]
There are two cost/value functions \(c\) one can consider when calculating the global sensitivity of a function wrt to a set of features. The cost measures the variance of Y caused by the uncertainty of the inputs in \(\mathcal{J}\). The first (considered by (Owen 2014)) is
\[\tilde{c}(\mathcal{J}) = \text{Var}[\text{E}[Y | \mathbf{X}_\mathcal{J}]].\]
Another choice is
\[c(\mathcal{J}) = \text{E}[\text{Var}[Y|\mathbf{-\mathcal{J}}]]\]
where \(\mathbf{X}{-\mathcal{J}} = \mathbf{X}_{K\\J}\).
While both costs result in the same values \(v_i\), the resulting estimators are different.
The question is how does this effect the estimator in both bias and sample efficiency.
Independent Shapley Values
ISV is the style of shapley value introduced above. The empty coalition is the background input.
TODO Conditional Shapley Values
TODO Asymetric Shapley Values
Asymetric shapley values may be what we want in the bandit case. The question is does knowing the ordering of ASVs give us the minimal intervention set? (Frye et al. 2021)
Recursive Shapley Values
(Singal, Michailidis, and Ng 2021)