Exercises — Feature attribution (SHAP, LIME)

(a) is global, (b) is local. Global statements average behaviour over all inputs (like 5.4.02-Permutation-importance). Local statements — the entire point of SHAP/LIME — describe this one prediction. The tell: (b) names a specific instance ("Bob") and a signed number for that instance.

$g$ is a linear model. Chosen because linear coefficients are directly human-readable: "$w_i$ = change in output per unit of feature $i$." The bet is that even a wildly non-linear $f$ looks approximately straight in a small neighbourhood of $x$.

The marginal contribution of feature $i$: how much the prediction changes when we add $i$ to a coalition $S$ that did not already contain it.

${\Delta }_3(\{1,2\})=f(\{1,2,3\})-f(\{1,2\})=0.72-0.60=\boxed{0.12}$. That is the gain from revealing feature 3 once features 1 and 2 are already known.

For each ordering, feature 1 arrives after whatever came before it. Its marginal contribution is $f(\text{before}\cup \{1\})-f(\text{before})$:

${\varphi }_1=\frac{0.30+0.30+0.30+0.32+0.30+0.32}{6}=\frac{1.84}{6}=0.30\overline{6}\approx \boxed{0.3067}.$ Averaging over all orderings is exactly what the factorial weights in the Shapley formula do — each of the 6 orderings is equally likely.

${\varphi }_2$ — marginal of feature 2 by ordering:

• after $\varnothing$: $0.30-0.20=0.10$ (twice: orderings 2,1,3 and 2,3,1)
• after $\{1\}$: $0.60-0.50=0.10$ (ordering 1,2,3)
• after $\{3\}$: $0.40-0.25=0.15$ (ordering 3,2,1)
• after $\{1,3\}$: $0.72-0.55=0.17$ (orderings 1,3,2 and 3,1,2)

Sum $=0.10+0.10+0.10+0.15+0.17+0.17=0.79$, so ${\varphi }_2=0.79/6\approx 0.1317$.

${\varphi }_3$ — marginal of feature 3:

• after $\varnothing$: $0.25-0.20=0.05$ (×2)
• after $\{1\}$: $0.55-0.50=0.05$
• after $\{2\}$: $0.40-0.30=0.10$
• after $\{1,2\}$: $0.72-0.60=0.12$ (×2)

Sum $=0.05+0.05+0.05+0.10+0.12+0.12=0.49$, so ${\varphi }_3=0.49/6\approx 0.0817$.

Efficiency check: ${\varphi }_1+{\varphi }_2+{\varphi }_3=0.3067+0.1317+0.0817=0.5200$. And $f(N)-f(\varnothing )=0.72-0.20=0.52$. ✓ They match exactly — no residual.

${\varphi }_4=0$, guaranteed by the Dummy axiom. Every marginal ${\Delta }_4(S)=f(S\cup \{4\})-f(S)=0$, so the weighted average of zeros is zero. Intuition: a player who adds nothing to any team deserves no credit.

Pair up orderings by swapping the positions of $i$ and $j$. In each pair, the coalition $S$ that precedes $i$ in one ordering is exactly the coalition that precedes $j$ in the swapped ordering. By the symmetry premise, ${\Delta }_i(S)={\Delta }_j(S)$ for that $S$. Every marginal of $i$ has an equal partner marginal of $j$ under the same combinatorial weight, so the two weighted sums are identical: ${\varphi }_i={\varphi }_j$. This is the Symmetry axiom.

${\varphi }_1(f)={\varphi }_1(f^{(1)})+{\varphi }_1(f^{(2)})=0.18+0.12=\boxed{0.30}$, by the Additivity (Linearity) axiom. Because every marginal ${\Delta }_1(S)$ of the summed model splits as ${\Delta }_1^{(1)}(S)+{\Delta }_1^{(2)}(S)$, and Shapley is a linear (weighted-average) functional of those marginals, the whole computation distributes over the sum. This is exactly why TreeSHAP can attribute each tree independently and add — a random forest's explanation is the sum of its trees' explanations.

What is $d(x,z)$? It is a distance metric — a non-negative function measuring how far the perturbation $z$ sits from the explained point $x$. It must satisfy the metric axioms: (i) $d(x,z)\ge 0$ with $d(x,x)=0$; (ii) symmetry $d(x,z)=d(z,x)$; (iii) the triangle inequality $d(x,y)\le d(x,z)+d(z,y)$. In LIME's tabular case $d$ is typically Euclidean distance on (normalised) features; for images it is a cosine or Hamming-style distance on the on/off superpixel mask (the "#different pixels" count from the parent note). The only structural requirement here is that $d$ grows as $z$ moves away from $x$, so that far perturbations are down-weighted.

With ${\sigma }^2=0.25$:

• $d=0$: $\pi =\exp (0)=1$.
• $d=0.25$: $\pi =\exp (-0.0625/0.25)=\exp (-0.25)\approx 0.7788$.
• $d=1.0$: $\pi =\exp (-1/0.25)=\exp (-4)\approx 0.0183$.

As $\sigma \to \infty$: every exponent $-d^2/{\sigma }^2\to 0$, so all weights approach $1$. The kernel stops distinguishing near from far, and LIME degenerates into a global linear fit — losing the "local" in Local Interpretable. That is why $\sigma$ literally sets the radius of the neighbourhood being explained.

(a) By the additive decomposition $f(x)={\varphi }_0+{\sum }_i{\varphi }_i$ (this is the Efficiency axiom rearranged, with ${\varphi }_0$ the base value): $f(x)=0.20+(-0.10)+(-0.03)+0.40+0.25=\mathrm{0.72.}$ (b) debt ($+0.40$) is the largest positive driver — it does most of the work raising risk. credit ($-0.10$) and income ($-0.03$) both lower risk (negative $\varphi$), consistent with Bob having some protective factors that the strong debt signal overwhelms. This mirrors the loan example in the parent note.

Why this exact shape? The Shapley value is a weighted average of marginal contributions with the combinatorial weights $\frac{|S|!(d-|S|-1)!}{d!}$. Lundberg & Lee's key result is that if you set up the coalition sampling as a weighted least-squares problem, there is a unique kernel over coalition sizes whose least-squares solution's coefficients equal those Shapley weights — and it is exactly $\pi (S)$ above. Concretely, the factor $\frac{1}{\left(\genfrac{}{}{0ex}{}{d}{|S|}\right)|S|(d-|S|)}$ counteracts two things at once: $\left(\genfrac{}{}{0ex}{}{d}{|S|}\right)$ removes the over-counting of same-size coalitions (there are many of them), and $|S|(d-|S|)$ up-weights the informative extremes — coalitions with almost no features or almost all features — because those pin down single-feature marginals most sharply. Feed these weights into the linear fit and the fitted coefficients provably satisfy Efficiency, Symmetry, Dummy and Additivity; converge the sampling and you get the true ${\varphi }_i$.

Which coalitions each emphasises:

• LIME's ${\pi }_x(z)=e^{-d^2/{\sigma }^2}$ emphasises perturbations geometrically close to $x$ — local fidelity, no axiomatic guarantee.
• KernelSHAP's $\pi (S)$ emphasises very small and very large coalitions (where $|S|$ or $d-|S|$ is tiny, the denominator shrinks and $\pi$ blows up) and down-weights medium ones — the shape that forces the linear fit onto the Shapley solution. Same regression skeleton, opposite weighting philosophy.

Feature $i=1$; the coalitions $S\subseteq \{2,3\}$ not containing 1 are $\varnothing ,\{2\},\{3\},\{2,3\}$. Compute weights (with $d=3$):

• $|S|=0$: $\frac{0!2!}{3!}=\frac{2}{6}=\frac{1}{3}$.
• $|S|=1$: $\frac{1!1!}{3!}=\frac{1}{6}$ (each of $\{2\}$ and $\{3\}$).
• $|S|=2$: $\frac{2!0!}{3!}=\frac{2}{6}=\frac{1}{3}$.

Marginals of feature 1:

• $S=\varnothing$: $0.50-0.20=0.30$
• $S=\{2\}$: $0.60-0.30=0.30$
• $S=\{3\}$: $0.55-0.25=0.30$
• $S=\{2,3\}$: $0.72-0.40=0.32$

Weighted sum:

Same as the ordering average — the weights are the fraction of orderings that produce each coalition. Note $\frac{1}{3}+\frac{1}{6}+\frac{1}{6}+\frac{1}{3}=1$: the weights form a probability distribution. ✓

Not necessarily a bug. They answer different questions and are on different scales:

• SHAP's ${\varphi }_{\text{debt}}$ is a marginal contribution to this prediction, guaranteed to satisfy efficiency (the $\varphi$'s sum to $f(x)-{\varphi }_0$).
• LIME's coefficient is the slope of a local linear surrogate, in whatever units the (possibly binarised/normalised) perturbation features use, with no efficiency constraint and dependent on $\sigma$ and the sampling.

Different objectives, different weightings ⇒ different numbers are expected. The right check is direction and rank consistency (both call debt the dominant positive driver), plus SHAP's efficiency sum. Contradictory signs would be the real red flag. This connects to why 6.3.03-Counterfactual-explanations are sometimes preferred: they sidestep the "which number is true" debate by answering "what minimal change flips the decision?"

(a) Why polynomial. Brute-force Shapley needs $2^d$ coalition evaluations — exponential in the number of features $d$ — because it re-evaluates the model for every subset. TreeSHAP never enumerates subsets. Instead it walks each tree once and, at every node, tracks the proportion of training paths that flow down each branch. Whether a feature is "present" or "marginalised" is handled by pushing a weighted fraction of the sample down both children at that feature's split and combining the leaf outputs. The combinatorial Shapley weights are folded directly into this traversal, so the cost per tree is polynomial in its size and depth — roughly $O(L{D}^2)$ for a tree with $L$ leaves and depth $D$, times $T$ trees, giving $O(TL{D}^2)$ overall. No $2^d$ anywhere, because the tree structure already encodes which feature interactions actually occur.

(b) Why prefer it over KernelSHAP. TreeSHAP returns exact Shapley values with zero sampling variance, while KernelSHAP only converges to them as the number of sampled coalitions $\to \infty$ and is noisy under a finite budget — the same instability the parent note flags for LIME's small-sample fits. So for a random forest TreeSHAP gives you exactness and speed simultaneously; there is no reason to fall back on an approximation. The Additivity axiom (Ex 3.4) is what makes this legal: you can attribute each tree independently and sum. See 3.5.04-Tree-ensembleinterpretation.

Efficiency axiom in words ::: The Shapley values sum exactly to $f(x)-{\varphi }_0$, no leftover residual. What $\sigma \to \infty$ does to LIME ::: Every weight $\to 1$, so LIME becomes a global linear fit and loses locality. Why zeros are wrong for "removing" a feature ::: Absent features must be marginalised over their distribution; zero is itself an informative, possibly out-of-distribution value.