SHAP and LIME

Shapley values#

The Shapley value (Shapley, 1953) is the unique allocation satisfying efficiency, symmetry, dummy and additivity. For a set function $v: 2^{[d]} \to \mathbb{R}$,

$$ \phi_i(v) = \sum_{S \subseteq [d] \setminus {i}} \frac{|S|!\,(d - |S| - 1)!}{d!}\Big(v(S \cup {i}) - v(S)\Big) $$

• $[d]$ — the index set of features; $i$ the feature being credited.
• $S$ — a coalition of features excluding $i$.
• $v(S)$ — the value of coalition $S$ (below, an expected model output).
• The combinatorial factor is the probability that $S$ precedes $i$ in a uniformly random permutation.

Efficiency gives $\sum_i \phi_i = v([d]) - v(\emptyset)$, which is the additivity checked numerically above.

The value function is a modelling choice#

SHAP (Lundberg and Lee, 2017) instantiates $v$ with an expected model output. Two variants exist and are routinely confused.

$$ v_{\text{int}}(S) = \mathbb{E}{X{\bar S}}\big[f(x_S, X_{\bar S})\big], \qquad v_{\text{cond}}(S) = \mathbb{E}\big[f(X) \mid X_S = x_S\big] $$

$\bar S$ is the complement of $S$, $x_S$ the explained instance restricted to $S$, and $X_{\bar S}$ a random draw of the remaining features.

The interventional form breaks feature dependence and evaluates $f$ off-manifold. The conditional form stays on-manifold and spreads credit to correlated features that the model never reads. Chen et al. (2020), True to the Model or True to the Data?, argue the choice follows from the question: interventional for auditing the model's mechanism, conditional for reasoning about the data-generating process. Janzing et al. (2020) argue from a causal standpoint that the interventional form is the correct default for explaining $f$.

KernelSHAP#

Lundberg and Lee show that Shapley values are recovered as the solution of a weighted least-squares problem over the $2^d$ coalitions, with the Shapley kernel

$$ \pi(S) = \frac{d - 1}{\binom{d}{|S|}\,|S|\,(d - |S|)} $$

The kernel diverges at $|S| \in {0, d}$, which are handled as hard constraints. This is exactly LIME's optimisation problem with a specific kernel, a specific loss and a specific regulariser — the unification result of the paper. Sampling coalitions from $\pi$ gives an unbiased but high-variance estimator; convergence is slow in $d$.

TreeSHAP and its subtleties#

Lundberg et al. (2020), From Local Explanations to Global Understanding with Explainable AI for Trees (Nature MI), give an $O(TLD^2)$ algorithm for tree ensembles — $T$ trees, $L$ leaves, $D$ depth — versus exponential enumeration. The default tree_path_dependent mode uses the training-set coverage counts stored in the tree as an implicit conditional distribution. That is neither $v_{\text{int}}$ nor a clean $v_{\text{cond}}$, and it can assign non-zero attribution to features the model does not use, as analysed by Sundararajan and Najmi (2020). Pass an explicit background dataset for interventional values when the distinction matters.

LIME#

Ribeiro et al. (2016) solve

$$ \xi(x) = \arg\min_{g \in G} \; \mathcal{L}\big(f, g, \pi_x\big) + \Omega(g) $$

with $G$ a class of interpretable models (sparse linear), $\pi_x$ a proximity kernel around $x$, $\mathcal{L}$ a locality-weighted squared loss and $\Omega$ a complexity penalty (typically K-LASSO to a fixed feature count).

Known weaknesses, all reproducible:

• Instability. Alvarez-Melis and Jaakkola (2018) show large explanation changes for small input changes. Zafar and Khan (2019) propose deterministic sampling to address it.
• Kernel width sensitivity. No principled selection procedure exists; the default heuristic is $\sqrt{d} \times 0.75$ on scaled data, chosen empirically.
• Off-manifold sampling. Perturbations are drawn independently per feature, so correlated data produces implausible neighbours.

The adversarial result#

Slack et al. (2020) construct a scaffolding attack: a classifier that detects whether an input came from the real data distribution or from LIME/SHAP's perturbation distribution, behaves discriminatorily on the former and innocuously on the latter. Both explainers then report benign attributions for a model that is biased in deployment.

The defence is not a better attribution method. It is on-manifold perturbation, plus treating explanations as one input to an audit rather than its conclusion.

Axiomatic alternatives#

Integrated Gradients (Sundararajan et al., 2017) satisfies completeness and implementation invariance for differentiable models at the cost of a baseline choice and $O(m)$ gradient evaluations along a path. Aumann-Shapley is its cooperative-game analogue. For deep networks it is usually the cheaper defensible option; see SHAP's DeepExplainer for the hybrid.

Papers#

• Lundberg and Lee, A Unified Approach to Interpreting Model Predictions, NeurIPS 2017 — arxiv.org/abs/1705.07874
• Ribeiro, Singh and Guestrin, "Why Should I Trust You?", KDD 2016 — arxiv.org/abs/1602.04938
• Lundberg et al., Explainable AI for Trees, Nature Machine Intelligence 2020
• Chen et al., True to the Model or True to the Data?, 2020 — arxiv.org/abs/2006.16234
• Sundararajan and Najmi, The Many Shapley Values for Model Explanation, ICML 2020 — arxiv.org/abs/1908.08474
• Sundararajan, Taly and Yan, Axiomatic Attribution for Deep Networks, ICML 2017 — arxiv.org/abs/1703.01365
• Slack et al., Fooling LIME and SHAP, AIES 2020 — arxiv.org/abs/1911.02508

What to learn next#

• Privacy in machine learning — what a model leaks about the people in its training set.
• Model cards and documentation — where explanations belong in a release.
• XGBoost — the tree models TreeSHAP was built for.