Feature attribution (SHAP, LIME)

Core concepts

Feature attribution assigns a numerical importance score to each input feature for a single prediction. Unlike global feature importance (e.g., permutation importance), attribution is instance-specific: the same feature can be critical for one prediction and irrelevant for another.

The challenge: modern models (deep nets, ensembles) are non-linear, interactive compositions. A feature's contribution depends on other features' values. We need a principled way to decompose $f(x)$ into additive contributions.

Figure — Feature attribution (SHAP, LIME)

LIME: Local Interpretable Model-agnostic Explanations

The core idea

LIME treats the model as a black box and builds a locally faithful linear approximation.

WHY linear? Humans interpret linear models easily: "feature $x_i$ increases prediction by $w_i$ per unit." Even if $f$ is globally non-linear, near $x$ it might be roughly linear.

HOW it works:

Generate perturbations: Sample new instances $z \in \mathcal{Z}$ near $x$ by randomly togling/perturbing features.
Weigh by proximity: Assign weight $\pi_x(z) = \exp\left(-\frac{d(x, z)^2}{\sigma^2}\right)$ so close neighbors matter more.
Fit local linear model: Solve

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

where $G$ is the class of linear models, $\mathcal{L}$ is weighted squared loss, $\Omega(g)$ penalizes complexity (e.g., L1 to select few features).

The coefficients of $g$ are the LIME explanations: $g(z) = w_0 + \sum_{i=1}^d w_i z_i$ .

Worked example LIME for image classification

Task: Explain why a CNN classified an image as "dog." Step 1 – Segment image: Divide into superpixels (e.g., 50 regions).

Step 2 – Perturb: Create samples by turning superpixels on/off (mask with gray). E.g., sample $z_1$ has regions {3, 7, 12 ...} visible, others masked.

Step 3 – Get predictions: $f(z_1) = 0.92$ (dog), $f(z_2) = 0.15$ (dog), etc.

Step 4 – Weight by similarity: $\pi_x(z) = \exp\left(-\frac{\text{\#different pixels}}{2\sigma^2}\right)$ .

Step 5 – Fit linear model: Each superpixel is a binary feature (on/off). Fit $g(z) = w_0 + \sum_{j=1}^{50} w_j z_j$ via weighted regression. Positive $w_j$ means superpixel $j$ increases "dog" score.

Result: Top 5 positive-weight superpixels highlight the dog's face. This is the explanation.

WHY mask with gray? We need a "neutral" baseline that doesn't confuse the model. Gray is close to the ImageNet mean.

SHAP: SHapley Additive exPlanations

Game-theoretic foundation

SHAP is grounded in Shapley values from cooperative game theory. Imagine features are players in a coalition, and the "payout" is the model's prediction.

The question: How much does each player (feature) contribute to the difference between $f(x)$ and the average prediction $f(\emptyset)$ ?

Definition Shapley value

For feature $i$ , the Shapley value is:

\phi_i(f, x) = \sum_{S \subseteq \{1,\ldots,d\} \setminus \{i\}} \frac{|S|! (d - |S| - 1)!}{d!} \left[f_S(x_{S \cup \{i\}}) - f_S(x_S)\right]

WHAT this says: Consider all subsets $S$ that don't include $i$ . Add $i$ to $S$ and measure the marginal gain. Average over all orderings (the factorials are combinatorial weights).

WHY these weights? They come from the axiom that players in symmetric roles get equal credit. It's the unique attribution satisfying:

Efficiency: $\sum_{i=1}^d \phi_i = f(x) - f(\emptyset)$ (contributions sum to the total deviation).
Symmetry: If $i$ and $j$ contribute equally in all coalitions, $\phi_i = \phi_j$ .
Dummy: If $i$ never changes the prediction, $\phi_i = 0$ .
Linearity: For $f = f_1 + f_2$ , $\phi_i(f) = \phi_i(f_1) + \phi_i(f_2)$ .

DERIVATION from scratch:

Setup: We have $d$ features. For a subset $S$ , define $f_S(x_S)$ as the expected prediction when we observe features in $S$ and marginalize out features not in $S$ :

f_S(x_S) = \mathbb{E}_{X_{-S}}[f(x_S, X_{-S})]

WHY marginalize? We replace missing features with their typical distribution, not zeros.

Marginal contribution: When we add feature $i$ to coalition $S$ , the gain is: $\Delta_i(S) = f_{S \cup \{i\}}(x_{S \cup \{i\}}) - f_S(x_S)$
Average over all orderings: There are $d!$ orderings of features. For each ordering, $i$ arrives after some set $S$ . The number of orderings where $i$ arrives after exactly the features in $S$ is $|S|! \cdot (d - |S| - 1)!$ . So the probability of that configuration is:

\frac{|S|! (d - |S| - 1)!}{d!}

Weighted average of $\Delta_i(S)$ over all $S \not\ni i$ gives the Shapley value.

Result: $\phi_i$ is the fair credit to feature $i$ for moving the prediction from baseline $f(\emptyset)$ to $f(x)$ .

Computing SHAP: the challenge

Exact Shapley values require $2^d$ evaluations (all subsets). For high-dimensional data, this is intractable.

Solutions:

KernelSHAP (model-agnostic): Approximates Shapley values by fitting a weighted linear model (like LIME, but with specific Shapley weights). Converges to true Shapley as samples →∞.
TreeSHAP (for tree models): Exploits tree structure to compute exact Shapley values in polynomial time. HOW: Traverse the tree, track feature splits, and compute expectations over paths.
DepSHAP (for neural nets): Approximates using backpropagation + reference values.

Worked example SHAP for loan default

Scenario: Model predicts P(default) = 0.72 for applicant Bob. Base rate $\phi_0 = 0.20$ .

Features:

Credit score: 580
Income: $45k
Debt-to-income: 0.45
Age: 28 Step 1 – Sample coalitions: For subset $S = \{\text{credit, income}\}$ , compute $f_S$ by averaging predictions over many random samples where debt and age are replaced by their distribution values, but credit=580 and income=45k are fixed.

Step 2 – Marginal gains:

Add credit to $\emptyset$ : $f_{\{credit\}} - f_{\emptyset} = 0.35 - 0.20 = +0.15$
Add income to $\{credit\}$ : $f_{\{credit, income\}} - f_{\{credit\}} = 0.40 - 0.35 = +0.05$
Add debt to $\{credit, income\}$ : $f_{\{credit, income, debt\}} - f_{\{credit, income\}} = 0.58 - 0.40 = +0.18$
Add age to $\{credit, income, debt\}$ : $f_{\text{all}} - f_{\{credit, income, debt\}} = 0.72 - 0.58 = +0.14$

Step 3 – Average over orderings: Repeat for all $4! = 24$ orderings. The Shapley value $\phi_{\text{debt}}$ is the average marginal contribution of debt across all orderings.

Result (after exact computation):

$\phi_{\text{credit}} = +0.12$ (low score increases default risk)
$\phi_{\text{income}} = -0.05$ (moderate income slightly protective)
$\phi_{\text{debt}} = +0.31$ (high debt ratio is the biggest driver)
$\phi_{\text{age}} = +0.14$ (young age adds risk)

Check: $0.20 + 0.12 - 0.05 + 0.31 + 0.14 = 0.72$ . ✓

WHY this ordering-average? Because features interact. If we know credit is low, adding debt has a different effect than if credit were high. Averaging over orderings accounts for all interaction contexts.

Worked example TreeSHAP in action

Task: Random forest with 3 features (A, B, C) predicts house price. One tree splits: A >5 → B > 3 → leaf₁( $250k), else leaf₂($ 180k).

Instance: A=6, B=4, C=1. Prediction = $250k. Base =$ 200k.

TreeSHAP algorithm:

Trace path: root → (A > 5: yes) → (B > 3: yes) → leaf₁.
At each split, compute: if feature were unknown, what fraction of training data goes left vs right? That fraction weights the alternative branch.
Feature A: caused split to right (toward $250k). If A were unknown, 60\% of data goes left ($ 180k), 40% right ( $250k). Expected without A:$ 0.6 \cdot 180 + 0.4 \cdot 250 = 208 $. Marginal contribution of A =$ 250- 208 = +42$.
Feature B: within the A > 5 branch, caused split to higher leaf. Expected without B (in A > 5 branch): $220$ . Marginal = $250 - 220 = +30$ .
Feature C: never split on. $\phi_C = 0$ . Sum: $\phi_A + \phi_B + \phi_C = 42 + 30 + 0 = 72$ . But wait, $250 - 200 = 50$ . Error? No: TreeSHAP uses training data fractions as the integration measure. The numbers here are illustrative; exact TreeSHAP accounts for all coalitions via the tree's coverage statistics.

LIME vs SHAP: the tradeoffs

| Aspect | LIME | SHAP | |--------|------| | Foundation | Locally faithful linear model | Shapley values (game theory) | | Guarantees | None (approximation-dependent) | Efficiency, symmetry, dummy axioms | | Compute cost | $O(n_{\text{samples}})$ , flexible | $O(2^d)$ exact; TreeSHAP $O(TLD^2)$ , KernelSHAP $O(n \cdot 2^d)$ approx | | Stability | High variance with few samples | More stable (principled) | | Additivity | No guarantee $\sum w_i \approx f(x) - \text{base}$ | Exact: $\sum \phi_i = f(x) - \phi_0$ | | Use case | Quick, interpretable, when consistency isn't critical | When you need theoretically sound, consistent explanations |

WHY use LIME? Speed + simplicity. You can explain a one-off prediction in seconds with reasonable samples. Good for protyping, user-facing apps where "roughly right" is enough.

WHY use SHAP? When decisions are high-stakes (healthcare, finance) and you need defensible, consistent explanations. SHAP's additivity means you can decompose a prediction exactly. TreeSHAP is also fast for tree models.

Recall Explain to a12-year-old

Imagine your teacher gives you a grade on a group project. You want to know: "How much did I contribute vs my teammates?"

LIME is like asking few classmates nearby: "If I weren't in the group, would the grade be lower?" Then you average their answers. It's quick, but if you ask different people, you might get different answers.

SHAP is like the teacher carefully calculating: "If I imagine all possible groups with and without you, and average how much the grade changes when you're added, that's your exact contribution." It's fair, everyone agrees on it, but it takes longer to compute.

Both help you understand why the grade (prediction) is what it is, one feature (person) at a time.

Connections 6.301-Global-vs-local-interpretability – Feature attribution is the canonical local method.

6.2.03-Attention-mechanisms – Attention weights are a form of feature attribution (though not Shapley-based).
5.4.02-Permutation-importance – Global feature importance; SHAP can be aggregated to recover similar rankings.
6.3.03-Counterfactual-explanations – Alternative local explanation: "change $x_i$ to $x_i'$ to flip the prediction."
3.5.04-Tree-ensembleinterpretation – TreeSHAP leverages tree structure for fast exact computation.

#flashcards/ai-ml

What is feature attribution? :: Assigning a numerical importance score to each input feature for a single prediction, showing how much each feature contributed to that specific output.

What makes LIME "local"?

LIME fits a simple interpretable model (linear) in a small neighborhood around the instance

x

, weighted by proximity

\pi_x(z) = \exp(-d(x,z)^2/\sigma^2)

Derive the LIME objective function :: Start with weighted squared loss $\mathcal{L} = \sum_z \pi_x(z)[f(z) - g(z)]^2$ (closeness to $f$ near $x$ ), add complexity penalty $\Omega(g) = \lambda \|w\|_1$ (sparsity), minimize their sum to get locally faithful sparse linear $g$ .

What are Shapley values?

The unique fair attribution satisfying efficiency (

\sum \phi_i = f(x) - f(\emptyset)

), symmetry, dummy, and linearity. For feature

i

\phi_i = \sum_S \frac{|S|!(d-|S|-1)!}{d!}[f_{S \cup \{i\}} - f_S]

, the marginal contribution averaged over all coalitions.

Why do SHAP values sum to the prediction?

By the efficiency axiom of Shapley values:

f(x) = \phi_0 + \sum_{i=1}^d \phi_i(x)

, where

\phi_0

is the base rate. This is exact, not approximate.

How does TreeSHAP achieve polynomial time?

Exploits tree structure: for each split, compute the fraction of training data going each direction, use that to weight the alternative branch's expectation. No need to enumerate all

2^d

subsets explicitly.

LIME high variance mistake and fix

Using too few perturbations (e.g., 10) makes the linear fit unstable; explanations vary wildly between runs. Fix: Use 1,000–10,000 samples and check stability across multiple runs.

Key difference: LIME vs SHAP guarantees :: LIME is an approximation with no theoretical guarantees on fidelity or additivity. SHAP has axiom-based guarantees: efficiency, symmetry, dummy player, making it theoretically sound and consistent.

When to use LIME over SHAP?

When you need speed and simplicity for protyping or low-stakes user-facing explanations, and approximate local fidelity is sufficient. LIME can explain any model type with flexible sampling.

What is

f_S(x_S)

in Shapley derivation?

The expected prediction when features in subset

S

are observed at

x_S

and features not in

S

are marginalized:

f_S(x_S) = \mathbb{E}_{X_{-S}}[f(x_S, X_{-S})]

. This defines the baseline for computing marginal contributions.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Feature attribution ka matlab hai ki jab model koi ek prediction deta hai—jaise "is loan application ko reject karo"—to hum ye samajhna chahte hain ki konsi feature ne kitna contribute kiya. Global importance sirf overall batati hai (credit score important hai), lekin local attribution kehti hai "is specific case mein, Alice ki520 credit score ne -0.3 ka negative push diya."

LIME ka approach simple hai: model ko black-box maan lo, instance x ke pas kuch fake samples banao (perturbations), unpe model run karo, aur ek linear approximation fit kar lo. Jo weights milenge wo batayenge ki local region mein kaun si feature kitna matter karti hai. Fast hai, lekin thoda unstable bhi—kam samples pe explanation change ho sakta hai.

SHAPzyada mathematical hai, game theory se ata hai (Shapley values). Ye guarantee deta hai ki sabhi features ka contribution exactly add up hoga prediction tak. TreeSHAP tree models ke liye bahut fast hai. SHAP ka fayda: consistent aur fair explanations. Agar high-stakes decision hai (medical, financial), to SHAP better choice hai kyunki theoretically sound hai. Dono methods AI ko transparent banate hain—"black box" ko "glass box" mein convert karte hain, jo trust aur debugging ke liye zaroori hai.