Phase B · attribution / XAI

LIME

Ribeiro et al. 2016

← back to the method catalogue

What it does?

LIME explains one prediction by fitting a simple model nearby. Around the input of interest it generates many perturbed versions, records the output for each, and then fits a sparse linear surrogate to that local data. The weights of the surrogate are read as the explanation: which inputs, locally, push the output up or down. The idea is that even a complicated system is roughly linear in a small neighbourhood, so a linear fit there is both faithful and easy to read. LIME is model-agnostic and one of the most cited attribution methods. We apply it to the VCS by perturbing the candidate causes around the live state, re-running the program to get outputs, and fitting a local linear model whose weights we correlate with the true causal map. Because the perturbations are real re-runs, LIME works on a sprite's position where gradients fail. It fits both content and position structure reasonably well, so it lands among the more faithful attribution methods. Its main caveats are the usual ones: the explanation depends on how the neighbourhood is sampled and on the surrogate's fit quality, so it can be unstable across runs. On the VCS we can check its surrogate against the exact answer, which is a test the method never gets on a real network.

LIME 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.686 — 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 · fit a local surrogate

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.

Surrogate modelWeighted least squaresRidge regressionCoefficient of determination (R²)Cosine similarity

The idea in plain words

A deep network is a very curvy function. But zoom in far enough on any smooth curve and it looks like a straight line. LIME uses this idea. To explain one prediction, it builds a simple model (a straight-line, i.e. linear, model) that imitates the network only near this one input. Such a stand-in model is called a surrogate. The weights of the surrogate are the explanation: a large positive weight means “this part pushes the output up, around here”.

How do you get data to fit the surrogate? You make it. Switch random parts of the input off (for an image: grey out random superpixels, patches of similar colour), run the network on each version, and record the outputs. Versions that are close to the original get a high weight in the fit, far-away versions a low one. Then fit the line. LIME is model-agnostic: it treats the model as a black box, so it works for networks, random forests, or, as here, a game console.

How it works on a neural network

Describe each perturbed version by a binary vector \(z \in \{0,1\}^d\): \(z_j = 1\) if part \(j\) is present, \(0\) if it was switched off. The original input is \(z = \mathbf 1\) (all present). Sample \(z_1,\dots,z_N\), run the model on each, \(y_k = f(h(z_k))\), where \(h\) maps \(z\) back to a real input. Weight each sample by its closeness to the original, \(\pi_k = \exp(-D(z_k,\mathbf 1)^2/\sigma^2)\), with distance \(D\) and kernel width \(\sigma\). Then solve the weighted least-squares problem

\[ (w, b) \;=\; \arg\min_{w,b}\; \sum_{k=1}^{N} \pi_k\,\big(y_k - w\cdot z_k - b\big)^2 . \]

The coefficients \(w_j\) are the attribution. The library version also keeps only the top few features (a sparse fit) and adds a small ridge penalty. The fit's \(R^2\) (the share of the output variation the line explains) tells you how linear the neighbourhood really is.

Toy example. Two parts, \(f(z) = 3z_1 + 2z_1z_2\). The four possible samples are \(f(1,1)=5\), \(f(1,0)=3\), \(f(0,1)=0\), \(f(0,0)=0\). Give the original weight 1, the two one-off samples weight 0.5, the all-off sample 0.25. Solving the \(3\times3\) normal equations gives \(w_1 = 13/3 \approx 4.33\), \(w_2 = 4/3 \approx 1.33\), \(b = -8/9\). Compare with the truth at the original: switching off \(z_1\) costs 5, switching off \(z_2\) costs 2. With equal weights the fit would give \(w_1 = 4\), \(w_2 = 1\), \(b = -0.5\). The locality weights pull the line toward the original, so \(w_2\) moves from 1 toward the local value 2. No line can fit the interaction term \(2z_1z_2\) exactly; the surrogate spreads it over both coefficients, and \(R^2 < 1\) shows it.

Recipe

  1. Choose the output \(y\), the interpretable parts, a number of samples \(N\), a keep-probability and a kernel width \(\sigma\).
  2. Draw \(N\) random present/absent vectors \(z_k\) (include the original \(z=\mathbf 1\)).
  3. Turn each \(z_k\) into a real input (absent parts set to the baseline), run the model, record \(y_k\).
  4. Weight each sample by its closeness to the original, \(\pi_k = \exp(-D(z_k,\mathbf 1)^2/\sigma^2)\).
  5. Fit \(y \approx w\cdot z + b\) by weighted least squares; report \(w\) and the fit's \(R^2\).
  6. Repeat with other random seeds to see how stable \(w\) is.

From a neural network to the Atari

The black-box model \(f\)The cartridge program on the bit-exact emulated Atari 2600 VCS (jutari).
Superpixels (interpretable parts)The candidate RAM cells, de-duplicated (8 to 23 per core game). TIA and joystick causes are not in the interpretable space.
\(h(z)\): switch parts offdeepcopy the checkpoint and intervene_ram!(env, j, 0) for every absent cell; then 15 frames of the real ROM.
Samples \(N\), kernel \(\pi\)\(N = 300\), keep-prob 0.5, the first sample is the all-present original; cosine-distance kernel with \(\sigma = 0.75\sqrt{d}\).
Surrogate \(g(z)=w\cdot z+b\)Weighted least squares with a tiny ridge (\(10^{-6}\)) on the coefficients; all cells kept (no sparsity step).
“Ground-truth importance”The oracle's single-cause |Δy| per cause, from real re-runs.

How we apply it to the VCS

Sampling. lime_sample draws \(N = 300\) present/absent vectors over the candidate RAM cells. Row 1 is forced to the original (all present); every other cell is present with probability 0.5. For each row, masked_read_y copies the checkpoint, zeroes the absent cells with intervene_ram!, plays the recorded 15 actions with env_step!, and reads \(y\). These 300 real-emulator runs are the whole cost of one fit.

Weights. lime_weights uses the cosine distance between \(z\) and \(\mathbf 1\) and the kernel \(\exp(-D^2/\sigma^2)\) with the LIME library's default width \(\sigma = 0.75\sqrt{d}\) (\(d\) = number of cells). Cosine distance here lies between 0 and 1, while \(\sigma\) is above 2 for 8 or more cells, so all weights stay between roughly 0.8 and 1. In practice the fit is close to an unweighted least-squares fit over a broad neighbourhood (about half the cells zeroed per sample), not a tight local one.

Fit. fit_weighted_linear solves the ridge-regularised normal equations and returns the coefficients, the intercept and the weighted \(R^2\). Each RAM cause gets \(|w_j|\) of its cell; TIA and joystick causes get 0. The sign is dropped because the oracle column is a magnitude.

Stability. LIME depends on its random samples, so the runner refits from 5 independent seeds (5 × 300 re-runs per output) and records the spread of the oracle correlation, of \(R^2\), and the average cosine similarity between the coefficient vectors.

How is this different from the oracle? The oracle asks one exact question per cause: “change only this, at the real state, what happens?” LIME asks many joint questions (half the cells zeroed at once) and then compresses the answers into one line. If the game logic were additive, the line's coefficients would equal the zeroing effects. Where it is not (thresholds, AND-like interactions, sprite timing), the line averages the effect over damaged contexts, and the \(R^2\) tells you how much it missed.

Read the code

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

Reading the result

Bars are \(|w_j|\) per cause next to the oracle's true effect; TIA and joystick causes are zero for LIME by construction, and both causes of a byte share a height. Read the record's surrogate \(R^2\) before trusting the bars: a low value is LIME admitting that a line is a poor model of the game near this state. Also read the stability block: if refits with other seeds disagree, the ranking is partly sampling luck. Expect LIME to track the main structure on both content and position outputs reasonably well.

Pitfalls

Try it yourself

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

Writes lime_<game>_{content,ball_pixel}.json/.npz into tools/xai_study/phaseB_attribution/out/, with the surrogate \(R^2\) and the stability block. Knobs: --n-samples, --kernel-width, --stability-seeds.

Original papers & further reading

Read next: KernelSHAP / Shapley · RISE · Occlusion · Linear probing + control tasks

How it's scored

The score is the Pearson correlation of the local linear surrogate's weights with the oracle's exact causal map, reported raw, and the grading is always against the intervention oracle. LIME fits a sparse linear model to real re-runs of the machine around the live state, so its perturbations are valid interventions and it works on a sprite's position where the gradient family scores zero. That is why there is no position collapse here. It fits both content and position structure reasonably well, so it lands among the more faithful attribution methods. The surrogate also reports its own fit quality, the local R-squared, which acts as an internal check on how linear the neighbourhood really is. The main caveats the score reflects are the usual ones for LIME: the explanation depends on how the neighbourhood is sampled and on the surrogate's fit, so it can vary across runs, and we report that stability alongside the correlation. The grading never compares LIME to another method, only to the oracle. The audit box reports the measured all-regime faithfulness across the 44 scored games, so the number reflects the whole scored set. On the VCS we can test the surrogate against the exact answer, which a real network never allows.

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 lime.jl: pr = pearson(attr, odelta); a stability sweep over K seeds reports corr mean/std but the headline F is the single-run pearson; triad_extra_dict(f.pearson, attr, f.oracle_abs_delta). Record: out/lime_air_raid_content.json (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 LIME attribution — lime.jl:331
  2. raw Pearson of attribution vs oracle |Δy(u)| — pilot_ig_vs_oracle.jl:173
  3. assemble the F∧S∧M triad record — lime.jl:689
  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.640F — faithfulness vs oracle (mean over 44 games, ±0.063 CI95)
0.646S — sufficiency: held-out predictive (n/a where the paper does not define this axis)
0.553M — 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.lime.per_game).

GameF (all)content-Fposition-FSMNote
Enduro0.9851.0000.9700.8750.833recovers the true causes
Fishing Derby0.9580.9480.9680.9500.722recovers the true causes
Riverraid0.9331.0000.8670.8700.432recovers the true causes
Krull0.9300.9990.8600.8460.190recovers the true causes
Montezuma's Revenge0.9230.9750.8710.8750.400recovers the true causes
Name This Game0.8940.7881.0000.9171.000recovers the true causes
Space Invaders0.8781.0000.7560.9170.294recovers the true causes
Bowling0.8730.9040.8430.8810.225recovers the true causes
Boxing0.8440.8170.8700.6670.795holds up on position
Alien0.8430.7790.9070.7140.750holds up on position
Gopher0.8040.7760.8330.9290.762holds up on position
Ice Hockey0.7830.7370.8290.6360.500holds up on position
Phoenix0.7650.9090.6220.4621.000
Pacman0.7500.7760.7250.4441.000
Private Eye0.7340.7310.7370.9600.229holds up on position
Demon Attack0.7320.7670.6980.8750.350
Kung-Fu Master0.7100.7450.6760.8000.806
Frostbite0.7020.5800.8240.5000.395holds up on position
Pitfall0.7000.6930.7060.8820.344holds up on position
Skiing0.6990.8100.5880.4500.833
Q*bert0.6930.9990.3870.5001.000
Jamesbond0.6840.7270.6400.8930.288
Freeway0.6680.4580.8790.6000.536holds up on position
Bank Heist0.6630.9000.4270.8330.900
Atlantis0.6400.6320.6480.4500.417holds up on position
Breakout0.6320.7500.5150.5500.806
Pong0.6200.6860.5540.3890.281
Ms. Pac-Man0.5820.8100.3520.4750.816
Video Pinball0.5430.7700.3150.5000.500
Asterix0.5060.5250.4870.5000.417
Tennis0.5001.0000.0000.5000.817position gradient vanishes
Kangaroo0.5000.9990.0000.5000.767position gradient vanishes
Road Runner0.4710.0000.9410.4740.167holds up on position
Double Dunk0.4540.7970.1110.5380.500
Air Raid0.4370.3830.4900.7140.423
Yars' Revenge0.4060.7710.0410.4640.673
Assault0.3960.0920.6990.9050.263holds up on position
Centipede0.3790.7570.0000.4500.472position gradient vanishes
Seaquest0.3570.0000.7140.4790.413holds up on position
Berzerk0.3520.6950.0100.4810.260position gradient vanishes
Chopper Command0.3430.0000.6870.4520.400holds up on position
Hero0.3340.1360.5320.4170.280holds up on position
Carnival0.3310.6610.0000.4470.417position gradient vanishes
Venture0.2260.4510.0000.4740.500position gradient vanishes

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 (masked re-runs step the horizon) — env_reset! / env_step! jutari
  2. shared gameplay-state testbed — build_shared_testbed jutari

The computation (intervention path)

  1. masked forward: absent cells -> 0 via the oracle's occlude! (RAM->0), step the horizon, read y — masked_read_y -> intervene_ram! jutari intervene_ram! call at lime.jl:145 -> jutari_oracle.jl:174
  2. draw the perturbation design matrix Z (Bernoulli present-mask, anchor row = all-present) and outputs — lime_sample runner
  3. LIME locality kernel pi(z) = exp(-cosine_dist(z,1)^2 / sigma^2) — lime_weights runner
  4. fit the weighted ridge linear surrogate; coefficients are the attributions — fit_weighted_linear runner
  5. snapshot RAM+screen after each masked re-run — snapshot jutari

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

Implementation
tools/xai_study/phaseB_attribution/lime.jl
Reference
Ribeiro et al. 2016
Record
lime_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.