Phase B · attribution / XAI

KernelSHAP / Shapley

Lundberg & Lee 2017

← back to the method catalogue

What it does?

KernelSHAP estimates Shapley values, the game-theoretic fair share of each input. The Shapley value asks how much each input contributes to the output on average, over every possible order in which the inputs could be added. It is the unique attribution that satisfies a set of fairness axioms, which is why it is widely trusted. Computing it exactly is exponential, so KernelSHAP approximates it by sampling many coalitions, subsets of inputs that are present, evaluating the output for each, and solving a weighted least-squares problem whose solution approximates the Shapley values. We apply it to the VCS by sampling coalitions of candidate causes, re-running the program for each, and correlating the estimated Shapley values with the true causal contributions. Because every coalition is a real re-run of the machine, the method works on a sprite's position where gradients fail. Given enough coalitions it recovers much of the true contribution on both content and position outputs, so it is among the more faithful attribution methods, and it reports its own completeness as a check. Its cost is the number of coalitions needed to converge. On the VCS we can watch that convergence against the exact answer, which turns a theoretical fairness guarantee into a measured faithfulness number.

KernelSHAP / Shapley result

Top row (image domain, as in Paper 1): the game frame, then the oracle's true causal region and this method's attributed region — each painted onto the frame through the screen footprint of the RAM cells it implicates (brighter = more important). A faithful method's heat matches the oracle's. Bottom: per-cell importance — oracle (green) vs method (blue) — and the deletion/insertion faithfulness curves (perturb the ranked causes and watch the output move). Note: the image-domain overlay footprints are illustrative, computed on the pre-redesign boot frame; the bars, curves and all reported numbers come from the re-run records on the shared gameplay states. pearson_corr_with_oracle = 0.690 — this example only (pong, state f90+15); the audit aggregate is below.

Reading this example's causal region

This example explains the content of RAM $36 (byte 54) — the most causally-active concept byte at this state. Its strongest true-causes are: RAM $36 (the play area — ball / paddles); RAM $31 (17% of its footprint sits in the score band, the rest in the play area). The score digits appear in the region because RAM $31 reaches them: perturbing it over the 30-frame NOOP window changes the game outcome, and hence the score — a downstream effect, not direct rendering.

Perturbation family · fair shares from game theory

Learn the method — a beginner's guide

New to explainable AI? This block explains the method as it is used on neural networks, then how we run the very same method on an Atari 2600, where — unlike for a network — we know the right answer. Every implementation step links to the code. See also the XAI primer for the shared vocabulary.

Shapley valueCooperative game theoryWeighted least squaresLagrange multiplierBinomial coefficient

The idea in plain words

Three friends share a taxi and the fare is 30 euros. How should they split it fairly, if each lives at a different distance? Game theory has a famous answer: the Shapley value. Imagine the friends joining the ride one after another, in every possible order. Each time someone joins, note how much the fare goes up. A person's fair share is the average increase they cause, over all orders. Lloyd Shapley proved this is the only split that obeys a few fairness rules, for example: the shares add up to the total, and two people who always contribute the same pay the same.

For a neural network, the “players” are the input features and the “total” is the output minus a baseline output. A feature's Shapley value is its fair share of the prediction. Unlike occlusion, which removes one feature at a time, Shapley values look at every coalition (subset) of features, so backups and interactions are shared out correctly. The catch: \(n\) features have \(2^n\) coalitions. KernelSHAP estimates the values from a random sample of coalitions by solving one cleverly weighted linear regression.

How it works on a neural network

Let \(N\) be the set of \(n\) features and \(v(S)\) the model output when only the features in \(S\) are present (the others replaced by a baseline). The Shapley value of feature \(i\) is

\[ \phi_i \;=\; \sum_{S \subseteq N\setminus\{i\}} \frac{|S|!\,(n-|S|-1)!}{n!}\,\big[v(S\cup\{i\}) - v(S)\big] , \]

the order-averaged marginal contribution. The values always satisfy efficiency: \(\sum_i \phi_i = v(N) - v(\varnothing)\). Lundberg and Lee showed that the same \(\phi\) solves a weighted least-squares problem over coalitions \(z\in\{0,1\}^n\):

\[ \min_{\phi}\; \sum_{z} \pi(z)\Big(v(z) - v(\varnothing) - \textstyle\sum_i z_i\phi_i\Big)^2 \quad\text{s.t.}\;\; \sum_i\phi_i = v(N)-v(\varnothing),\qquad \pi(z) = \frac{n-1}{\binom{n}{|z|}\,|z|\,(n-|z|)} . \]

The Shapley kernel \(\pi\) puts most weight on very small and very large coalitions. KernelSHAP samples coalitions instead of enumerating all \(2^n\), and solves this regression.

Toy example: exact Shapley values of a 3-player game. \(f(x) = 4x_1x_2 + 2x_3\) at \(x = (1,1,1)\), baseline 0. The coalition values are \(v(\varnothing)=0\), \(v(1)=v(2)=0\), \(v(3)=2\), \(v(12)=4\), \(v(13)=v(23)=2\), \(v(123)=6\). Walk through the 6 orders and record what each player adds:

order\(x_1\) adds\(x_2\) adds\(x_3\) adds
1,2,3042
1,3,2042
2,1,3402
2,3,1402
3,1,2042
3,2,1402

Averages: \(\phi = (2, 2, 2)\), and \(2+2+2 = 6 = v(123)-v(\varnothing)\). The product term \(4x_1x_2\) is split evenly between its two players. Occlusion on the same toy gives \((4, 4, 2)\), which sums to 10: it counts the shared term twice. With \(n = 3\) the kernel gives every coalition of size 1 or 2 the same weight \(\pi = 1/3\), and the constrained regression over those 6 coalitions returns exactly \((2,2,2)\).

Recipe

  1. Choose the output \(y\), the features, and the “absent” baseline (a fixed value or a background dataset).
  2. Evaluate the two endpoints: all features present, \(v(N)\), and all absent, \(v(\varnothing)\).
  3. Sample coalitions \(z\): draw a size \(s\) with probability proportional to the kernel mass of that size, then a random subset of that size.
  4. Run the model once per distinct coalition (absent features set to the baseline), recording \(v(z)\).
  5. Solve the kernel-weighted least squares for \(\phi\) under the efficiency constraint \(\sum_i\phi_i = v(N)-v(\varnothing)\).
  6. Check convergence: re-solve with fewer coalitions and see whether \(\phi\) has settled.

From a neural network to the Atari

The model \(f\)The cartridge program on the bit-exact emulated Atari 2600 VCS (jutari).
The players (features)The candidate RAM cells, de-duplicated (8 to 23 per core game). TIA and joystick causes are not players.
Feature absent / backgroundOne fixed baseline: the cell is set to 0 with intervene_ram!. No background dataset is averaged over.
Value \(v(z)\) of a coalitiondeepcopy the checkpoint, zero the absent cells, run 15 frames of the real ROM, read \(y\). No surrogate model of \(f\) is trained.
Sampling budget512 sampled coalitions plus the two endpoints; repeated draws are merged, so each distinct coalition costs one re-run.
“Ground-truth importance”The oracle's single-cause |Δy| per cause, from real re-runs.

How we apply it to the VCS

The value function is the real machine. In textbook SHAP, \(v(S)\) is often approximated (e.g. by averaging over a background dataset). Here coalition_value computes it exactly: copy the checkpoint, zero every absent candidate cell with intervene_ram!, play the recorded 15 actions with env_step!, read the output. The only approximations left are the coalition sampling and the additive form of the explanation.

  1. Endpoints. \(f_0 = v(\varnothing)\) (all candidate cells zeroed) and \(f_1 = v(N)\) (intact) are each one real run.
  2. Sampling. sample_coalitions draws 512 coalitions: a size \(s\in\{1,\dots,C-1\}\) with probability \(\propto (C-1)/(s(C-s))\), then a uniform random subset of that size. Identical draws are merged by dedup_coalitions; their kernel weights are summed.
  3. Solve. kernelshap_solve solves the weighted least squares (tiny ridge \(10^{-8}\)) and projects the answer onto \(\sum_i\phi_i = f_1 - f_0\) with a Lagrange multiplier. The runner records the remaining completeness residual as a check.
  4. To causes. Each RAM cause gets \(|\phi|\) of its cell (the signed \(\phi\) are kept in the record); TIA and joystick causes get 0.
  5. Convergence. The solve is repeated on the first \(N/8\), \(N/4\), \(N/2\) draws of the same pool, so the record shows faithfulness versus compute at no extra re-runs.

An implementation detail worth knowing. The coalitions are drawn in proportion to the kernel and then also weighted by the kernel \(\pi(s)\) in the solve. Textbook KernelSHAP does one or the other, not both. Our estimate therefore leans even more on near-empty and near-full coalitions (“only this cell kept”, “only this cell zeroed”) than exact Shapley values would. Efficiency still holds exactly, by the constraint.

How is this different from the oracle? The oracle measures each cause alone at the real state, in two directions (+17 and →0). Shapley values average a cell's effect over many coalitions of other cells being zeroed, and split shared effects fairly. So when two cells form an AND-like pair, the oracle (like occlusion) gives each one the full effect, while SHAP gives each half. Agreement in ranking is what we score.

Read the code

XAI the interpretability method   substrate the bit-exact emulator it runs on (jutari, Julia).

Reading the result

Bars are \(|\phi|\) per cause next to the oracle's true effect. TIA and joystick causes are zero for SHAP by construction, and both causes of a byte share a height. Where the oracle shows two cells with large, similar effects, SHAP may show them at about half height each: that is fair sharing, not an error. Check the completeness residual (should be near zero) and the convergence block: if agreement still changes between \(N/2\) and \(N\), more coalitions would help. Expect SHAP to recover much of the true structure on both content and position outputs.

Pitfalls

Try it yourself

julia --project=jutari tools/xai_study/phaseB_attribution/kernelshap.jl --games core

Writes kernelshap_<game>_{content,ball_pixel}.json/.npz into tools/xai_study/phaseB_attribution/out/, with the signed \(\phi\), the completeness residual and the convergence sweep. Change the budget with --n-coalitions.

Original papers & further reading

Read next: LIME · RISE · Occlusion · Integrated Gradients

How it's scored

The score is the Pearson correlation of the estimated Shapley values with the oracle's exact causal map, reported raw, and the grading is always against the intervention oracle. KernelSHAP samples coalitions of candidate causes, re-runs the machine for each, and solves a weighted least-squares problem to approximate each cause's Shapley value, so every coalition is a real intervention and the method works on a sprite's position where the gradient family scores zero. That is why it does not collapse on the position regime. Given enough coalitions it recovers much of the true contribution on both content and position outputs, so it is among the more faithful attribution methods. It also reports its own completeness, that the Shapley values sum to the difference between the intact and fully masked outputs, which is an internal consistency check. The cost the score implicitly reflects is convergence: too few coalitions leave the estimate noisy. The grading is always against the oracle, never against another method. The audit box reports the measured all-regime faithfulness across the 44 scored games. On the VCS the theoretical fairness of the Shapley value becomes a measured faithfulness number, tested against an exact answer the method never sees on a real network.

The score is measured against the §1 intervention oracle — never against another interpretability method. F (faithful) is always vs the oracle; see the execution stack. How each of F / S / M is actually computed for this method (and whether it matches the paper) is in the box just below; the numbers are in the In the audit box under it.

How F, S, M are computed here

The exact formula this method uses for each score, read from its runner, and whether it matches the paper's §3 (F ∧ S ∧ M triad) definition. From the committed audit fsm_math_phaseB.json.

AxisFormula (as computed) What it measuresMatches §3?
F
faithfulness		\(F = \rho_{\mathrm{Pearson}}\!\left(\mathrm{attr},\ |\Delta y(u)|\right)\)Raw Pearson correlation between the method's per-cause attribution magnitudes and the oracle's true absolute causal effects |Delta_y(u)|, scored separately for the content and position output regimes.✓ matches kernelshap.jl: SHAP map per cause, F = pearson(shap_attr, oracle_abs_delta); triad_extra_dict(f.pearson, attr, f.oracle_abs_delta). Record: out/kernelshap_air_raid_content.json (metric_name=pearson_corr_with_oracle, value=0.79). Scorer pilot_ig_vs_oracle.jl pearson() (raw Statistics.cor, zero-variance->0); F = pearson(attr, oracle_abs_delta) where oracle_abs_delta = abs.(cmap.delta) (true |Delta_y| per cause). Also reports spearman, precision@k, deletion/insertion AUC (paper's auxiliary F metrics). Per-regime split: separate *_content.json and *_position.json records, each carrying its own extra.triad.{F,S,M}.
how it's measured — call stack:
  1. per-cause KernelSHAP attribution — kernelshap.jl:338
  2. raw Pearson of attribution vs oracle |Δy(u)| — pilot_ig_vs_oracle.jl:173
  3. assemble the F∧S∧M triad record — kernelshap.jl:720
  4. true causal effect Δy(u) by bit-exact re-run — oracle_intervene.jl:242
S
sufficiency		\(S = \dfrac{\#\{\,u_{\mathrm{held}}:\ |\hat{y}-y|\le\varepsilon\,\}}{|\mathrm{held\text{-}out}|}\in[0,1]\)Fit Delta_y = a*attr + b on a calibration half of the do(u) causes, predict the disjoint held-out half, and report the fraction of held-out causes whose predicted output lands within an epsilon band of the oracle's bit-exact re-run.✓ matches common/triad_sm.jl sufficiency_score() (interleaved calib/held split by seed, least-squares 1-D fit Delta_y~a*attr+b on calib, epsilon = max(0.5, 0.10*heldout_spread)); assembled in triad_extra_dict(). The new §3 (sec:triad) admits the fraction-within-tolerance [0,1] special case of the held-out predictive test, which this held-out do(u) fit-then-predict estimator satisfies, so it matches. (Detail: epsilon is a self-scaled band 0.10*spread; the [-1,1] correlation form is available but this method reports the [0,1] hit fraction.)
how it's measured — call stack:
  1. sufficiency_score: fit Δy=a·attr+b on a calib half, predict held-out within ε — triad_sm.jl:111
  2. assemble the F∧S∧M triad record (calls sufficiency_score) — triad_sm.jl:173
  3. true causal effect Δy(u) by bit-exact re-run — oracle_intervene.jl:242
M
minimality		\(M = |U^{\star}| / |\hat{U}| \in (0,1]\quad U^{\star}=\{u:\Delta y(u)>0\},\ \hat{U}=\{u:|\mathrm{attr}(u)|>\tau\}\)Ratio of the number of oracle causal movers (causes with nonzero true Delta_y) to the number of cells the method names above 1e-6 of its own max attribution; null when the oracle finds no mover or the method names nothing.✓ matches common/triad_sm.jl minimality_score() with name_frac=1e-6, mover_floor=0.0; the above-threshold named set is used (topk kept but not passed), see triad_extra_dict(). This is the paper's M = |U*|/|U_hat| in (0,1] (standardized everywhere), so it matches the new §3. (Detail: |U*| is taken as all oracle movers with Delta_y>0, an upper bound on the strictly-smallest reproducing subset, so M can be optimistic.)
how it's measured — call stack:
  1. minimality_score: |U*| oracle movers / |U_hat| named cells — triad_sm.jl:57
  2. assemble the triad record (calls minimality_score) — triad_sm.jl:178
  3. true causal effect Δy(u) by bit-exact re-run — oracle_intervene.jl:242

✓ matches = the same quantity as §3; ◐ partial = the same kind of estimator but a differing detail; ✗ does not match = a different quantity (see the note). Definitions: F = agreement with the oracle's true causal effects Δy(u); S = held-out predictive score in [−1, 1]; M = |U*|/|Û| (true-minimal-set size / named-set size).

In the audit

This is the method's entry in the actual cross-method audit — scored on the paper's correctness triad, each axis a mean over 44 of the 44 scored games (88 committed §R records), not the single example shown above. Tradition: gradient. The example figure (Pong) is one of those records.

0.650F — faithfulness vs oracle (mean over 44 games, ±0.062 CI95)
0.637S — sufficiency: held-out predictive (n/a where the paper does not define this axis)
0.565M — minimality: true-minimal-set / named-set (n/a otherwise)
88committed records aggregated
0.00human-plausibility proxy

F faithfulness (scored vs the oracle for every method) · S sufficiency (held-out predictive score in [−1, 1]; a negative value means the explanation predicts held-out interventions worse than the unperturbed baseline; reported for the predictive methods across all three phases where the calibration/held-out split is defined) · M minimality (true-minimal-set / named-set; where the method names a cause set) — n/a otherwise, per the paper's F ∧ S ∧ M triad.

Source: leaderboard.json · the whole leaderboard is on the methods page and the Paper 2 audit.

Results per game

This method's faithfulness on each of the 44 scored games (all-regime F, and the content vs position split). Click a header to sort. Every number is read from site_data.json (methods.kernelshap.per_game).

GameF (all)content-Fposition-FSMNote
Enduro0.9891.0000.9790.8750.833recovers the true causes
Fishing Derby0.9580.9480.9680.9500.722recovers the true causes
Montezuma's Revenge0.9431.0000.8870.9380.400recovers the true causes
Space Invaders0.9101.0000.8200.9170.294recovers the true causes
Name This Game0.8940.7881.0000.9171.000recovers the true causes
Riverraid0.8931.0000.7870.9570.432recovers the true causes
Krull0.8760.9990.7520.8650.190recovers the true causes
Alien0.8550.7790.9310.7140.750recovers the true causes
Boxing0.8530.8170.8890.7500.795recovers the true causes
Gopher0.8060.7760.8350.9290.762holds up on position
Bowling0.8020.7670.8380.8810.225holds up on position
Ice Hockey0.7880.7610.8150.5910.500holds up on position
Frostbite0.7830.7630.8040.4000.395holds up on position
Phoenix0.7650.9090.6220.4621.000
Pacman0.7500.7760.7250.4441.000
Demon Attack0.7220.7350.7080.8750.350
Kung-Fu Master0.7200.7450.6960.8000.806
Jamesbond0.7190.7470.6910.8930.288
Skiing0.7000.8100.5900.4500.833
Pitfall0.6970.6860.7070.8820.344holds up on position
Q*bert0.6930.9990.3870.5001.000
Bank Heist0.6690.9000.4380.8330.900
Ms. Pac-Man0.6590.8100.5070.4750.816
Freeway0.6330.3870.8790.6000.536holds up on position
Breakout0.6290.7500.5090.5500.806
Pong0.6250.6900.5590.3890.281
Private Eye0.6200.5030.7370.9600.229holds up on position
Air Raid0.6070.6020.6120.5000.423holds up on position
Atlantis0.5960.5460.6460.4500.417holds up on position
Double Dunk0.5890.7970.3810.6150.500
Video Pinball0.5400.7700.3090.5000.500
Tennis0.5001.0000.0000.5000.817position gradient vanishes
Kangaroo0.5000.9990.0000.5000.767position gradient vanishes
Assault0.4820.2640.6990.9050.263holds up on position
Asterix0.4760.4590.4940.1500.417
Road Runner0.4740.0000.9480.5000.306holds up on position
Carnival0.4140.8270.0000.4470.417position gradient vanishes
Yars' Revenge0.4060.7710.0410.4640.673
Centipede0.3730.7470.0000.4000.472position gradient vanishes
Venture0.3680.7360.0000.4740.500position gradient vanishes
Seaquest0.3570.0000.7140.4790.432holds up on position
Berzerk0.3480.6910.0040.4810.260position gradient vanishes
Chopper Command0.3420.0000.6840.4520.400holds up on position
Hero0.2660.0000.5320.4170.500holds up on position

Call stack — how it runs on jutari / jaxtari

The path from this method's runner (main) into the bit-exact VCS substrate, and the computation it involves. Every step links to the exact source on main. From callstack_phaseB.json.

Applied on the substrate

  1. env reset + per-frame step of the bit-exact VCS (coalition re-runs step the horizon) — env_reset! / env_step! jutari
  2. shared gameplay-state testbed — build_shared_testbed jutari

The computation (intervention path)

  1. coalition value f(S): mask the absent cells to 0 via the oracle's occlude! (RAM->0), step the horizon, read y — coalition_value -> intervene_ram! jutari intervene_ram! call at kernelshap.jl:159 -> jutari_oracle.jl:174
  2. sample coalitions with sizes from the Shapley-kernel weighting — sample_coalitions runner
  3. solve the weighted least-squares KernelSHAP system for the Shapley values phi — kernelshap_solve runner
  4. snapshot RAM+screen after each coalition re-run — snapshot jutari

Scored against the exact intervention oracle Δy(u): run_intervention.

Implementation
tools/xai_study/phaseB_attribution/kernelshap.jl
Reference
Lundberg & Lee 2017
Record
kernelshap_pong_content.json
All records
phaseB_attribution/out

The figure is generated from the committed record by docs/gen_method_figures.py; the game frame and each RAM cell's screen footprint are produced by render_scenes.jl / cell_footprints.jl.