Phase B · attribution / XAI

Extremal / meaningful perturbation

Fong & Vedaldi 2017; Fong et al. 2019

← back to the method catalogue

What it does?

Extremal, or meaningful, perturbation learns the smallest mask that most changes the output. Rather than sliding a fixed occluder, it optimises a soft mask over the inputs, searching for the smallest region whose removal most disrupts the output, subject to a bound on the mask's area. The learned mask is read as the explanation: the compact set of inputs the output really depends on. For images this yields a tight, optimised heat-map instead of a brute-force sweep. The method was designed to answer a specific criticism, that hand-placed occluders are arbitrary and can push the input off the data manifold. By optimising a bounded, smooth mask of real occlusion re-runs, it stays closer to valid interventions. We apply it to the VCS by optimising an area-limited mask over the candidate causes, each mask entry a genuine occlude-and-re-run, and comparing the learned mask to the true minimal cause set. Because every step is a real intervention, it works on a sprite's position where gradients fail, and it partly overlaps the true causes. Its faithfulness is moderate: the optimisation finds a compact set that is on the right track but does not exactly match the oracle's minimal set. It is a strong, on-manifold member of the intervention family and a fair test of whether optimising the mask beats simply sliding one.

Extremal / meaningful perturbation 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.469 — 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 · optimise the mask

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.

Mathematical optimizationGreedy algorithmRegularization (mathematics)Jaccard index (intersection over union)

The idea in plain words

Occlusion slides a fixed grey square and reports a number for every position. That raises two questions. Why a square? Why that size? Extremal perturbation turns the question around. It asks: what is the smallest region I must remove to destroy the prediction? The answer is a mask, a map that says for each input whether it is removed. The mask is found by optimisation, not by sliding.

The mask is the explanation. A good mask is small (it points at few inputs) and extremal (removing those inputs changes the output as much as possible). Fong and Vedaldi called the 2017 version “meaningful perturbation”, because the removal should look like a plausible change (a blur, not a random noise pattern). The 2019 version fixes the mask area in advance, say 10 % of the image, and finds the best mask of exactly that size. This removes a hard-to-tune penalty weight. It is still a black-box method: it only needs to run the model on masked inputs.

How it works on a neural network

Let \(m \in [0,1]^n\) be a soft mask (\(m_i = 1\): input \(i\) removed, \(0\): kept) and \(\Phi(x; m)\) the perturbed input, e.g. \(x\) blended with a blurred copy where \(m\) is high. The 2017 “deletion game” solves

\[ m^\star = \arg\min_{m}\; \lambda\,\|m\|_1 \;+\; f\big(\Phi(x; m)\big) , \]

trading mask size (the \(\ell_1\) regulariser \(\|m\|_1\), weighted by \(\lambda\)) against how low the class score goes. The 2019 “extremal” version replaces the penalty by a hard area constraint \(\|m\|_1 = a\cdot n\). Both are solved by gradient descent on \(m\), with smoothness tricks so the mask does not become a noisy pattern that fools the network (an adversarial mask).

Toy example. \(f(x) = 4x_1x_2 + x_3\) at \(x = (1,1,1,1)\) (\(x_4\) unused), removal sets an input to 0, and the budget is 2 inputs. Removing one input at a time changes \(f\) by 4, 4, 1, 0. A greedy search takes \(x_1\) first (change 4). Next it tries each remaining input together with \(x_1\): adding \(x_2\) still gives 4 (the product is already dead), adding \(x_3\) gives 5. So the mask is \(\{x_1, x_3\}\), which destroys the whole output with two inputs. Note what happened to \(x_2\): it is just as important as \(x_1\), but once \(x_1\) is removed it adds nothing, so it is not in the mask. A minimal mask names a sufficient set, not all important inputs.

Recipe

  1. Choose the output \(y\), a removal operator (blur, grey, zero) and an area budget \(a\) (fraction of inputs that may be removed).
  2. Start from an empty mask; record the intact output \(y(x)\).
  3. Search for the mask of at most \(\lceil a\cdot n\rceil\) inputs that maximises \(|y(x) - y(\text{masked } x)|\): gradient descent on a soft mask for a network, greedy forward selection on a black box.
  4. Stop when the budget is used up, or when adding one more input no longer increases the change.
  5. Report the mask (the selected set), and score it against the true causal set with intersection-over-union (IoU).

From a neural network to the Atari

The network \(f\)The cartridge program on the bit-exact emulated Atari 2600 VCS (jutari).
The mask \(m\) over pixelsA set of candidate causes (RAM bytes, one TIA colour register, the joystick) to remove together.
The perturbation \(\Phi(x;m)\)occlude! every cause in the set (RAM/TIA → 0) on a deepcopy of the checkpoint, then run 15 frames of the real ROM.
Gradient descent on a soft maskGreedy forward selection on a hard mask: the VCS output is discrete, so a mask gradient would be zero.
Area constraint \(a\)At most \(\lceil 0.25\cdot C\rceil\) of the \(C\) causes may be selected (--area 0.25).
“Is this mask right?”IoU of the mask with the oracle's top-\(k\) true movers, plus the same correlation and deletion/insertion scores as every other method.

How we apply it to the VCS

Why greedy, not gradients. The original optimises a soft mask by gradient descent. On the VCS that would fail for the same reason saliency fails on the position output: the machine is a discrete index computer and \(\partial y/\partial m = 0\) almost everywhere. So the runner optimises the mask directly on the real emulator with greedy forward selection, the discrete, budget-bounded cousin of the original optimiser.

  1. Single-cause pass. For every cause \(i\), masked_abs_dy removes just that cause and re-runs: \(|y(\text{occlude}\{i\}) - y(\text{intact})|\). This pass is literally occlusion.
  2. Greedy growth. Start with \(M = \varnothing\). In each step try every unselected cause \(i\): deepcopy the checkpoint, occlude! all of \(M\cup\{i\}\), run 15 env_step! frames, read \(y\). Add the cause with the largest change.
  3. Stop when \(|M| = \lceil 0.25\,C\rceil\), or when the best addition does not increase the change. If no single removal moves \(y\) at all, the mask stays empty: an honest null.
  4. Per-cause scores. Selected causes get the larger of their entry value and single-cause score, plus a constant lift (the largest single-cause score), so the mask ranks first and its internal order is kept. Unselected causes keep their single-cause occlusion score.

How is this different from the oracle? The oracle probes each cause alone, with two directions (+17 and →0). Extremal perturbation probes sets of causes, and only in the “remove” direction. It can therefore see joint effects the oracle's per-cause map does not contain. But it deliberately reports a minimal set, so a cause that is redundant given the mask (like \(x_2\) in the toy) is left out, even if the oracle ranks it high. For the IoU, causes are reduced to the cell they actually touch, because ram[i]:set and ram[i]:occlude both zero the same byte when masked.

Cost. At most \(\lceil aC\rceil\cdot C\) greedy re-runs plus \(C\) single-cause re-runs and one intact run; every one is a full 15-frame run of the real ROM from the checkpoint.

Read the code

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

Reading the result

The figure shows the per-cause scores next to the oracle, and the record lists the selected mask. The selected causes sit on top because of the lift. Check two things. First, are the mask's causes among the oracle's tallest bars? That is what the IoU measures. Second, are there tall oracle bars outside the mask? Usually there are: the mask is a small sufficient set, not the full list of important causes, so expect a partial overlap rather than a perfect match. The method works on the position output too, since it never uses a gradient.

Pitfalls

Try it yourself

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

Writes perturbation_<game>_{content,position}.json/.npz into tools/xai_study/phaseB_attribution/out/, including the mask, its growth curve and the IoU. Change the budget with --area 0.1.

Original papers & further reading

Read next: Occlusion · On-distribution counterfactual · RISE · KernelSHAP / Shapley

How it's scored

The score is the Pearson correlation of the learned mask with the oracle's exact causal map, together with the mask's overlap, measured as intersection-over-union, against the true minimal cause set. The grading is always against the intervention oracle. Every entry of the mask is a real occlude-and-re-run, so the method is a valid intervention and works even on a sprite's position, where the gradient family scores zero. That is why there is no position-collapse here. Its faithfulness is moderate rather than high: the area-bounded optimisation finds a compact set that partly overlaps the true causes but does not exactly match the oracle's minimal set, so both the correlation and the mask overlap are partial. Minimality is central to this method, because it explicitly seeks the smallest disruptive mask, so the score rewards a mask that is both on-target and small. The grading never compares the mask to another method's mask, only to the oracle's minimal set. The audit box reports the measured all-regime faithfulness across the 44 scored games, so the number reflects the whole scored set rather than the single game where the optimised mask happens to line up best with the true causes.

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 perturbation.jl: extremal-perturbation mask per cause, F = pearson(attr, oracle_abs_delta); triad_extra_dict(f.pearson, attr, f.oracle_abs_delta). Record: out/perturbation_air_raid_content.json (metric_name=pearson_corr_with_oracle, value=0.55). 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 extremal-perturbation mask attribution — perturbation.jl:373
  2. raw Pearson of attribution vs oracle |Δy(u)| — pilot_ig_vs_oracle.jl:173
  3. assemble the F∧S∧M triad record — perturbation.jl:654
  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: intervention. The example figure (Pong) is one of those records.

0.458F — faithfulness vs oracle (mean over 44 games, ±0.059 CI95)
0.608S — sufficiency: held-out predictive (n/a where the paper does not define this axis)
0.968M — 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.perturbation.per_game).

GameF (all)content-Fposition-FSMNote
Enduro0.9210.9330.9100.6251.000recovers the true causes
Fishing Derby0.8120.7880.8360.8501.000holds up on position
Phoenix0.7820.9960.5690.5381.000
Demon Attack0.7070.9610.4540.8750.875
Montezuma's Revenge0.7010.9350.4680.9061.000
Krull0.6950.9360.4550.5001.000
Riverraid0.6470.9370.3580.8701.000
Bowling0.6370.7600.5130.8811.000
Name This Game0.6290.5280.7290.6671.000holds up on position
Pacman0.6140.5220.7050.5561.000holds up on position
Boxing0.5950.5820.6090.7501.000holds up on position
Alien0.5810.5210.6410.7141.000holds up on position
Air Raid0.5780.4410.7140.7860.917holds up on position
Space Invaders0.5570.6790.4350.9170.833
Q*bert0.5540.9350.1730.4761.000
Freeway0.5190.4890.5500.5001.000holds up on position
Frostbite0.4930.5600.4250.1251.000
Ice Hockey0.4800.5120.4470.4550.875
Carnival0.4720.9450.0000.5001.000position gradient vanishes
Tennis0.4700.9400.0000.4691.000position gradient vanishes
Kangaroo0.4670.9340.0000.4691.000position gradient vanishes
Bank Heist0.4670.6960.2370.8331.000
Gopher0.4650.5310.4000.9291.000
Ms. Pac-Man0.4520.5770.3260.4751.000
Pong0.4020.4690.3350.3890.875
Jamesbond0.4020.4890.3140.8930.964
Double Dunk0.3960.5550.2370.5381.000
Atlantis0.3930.5270.2600.4000.875
Private Eye0.3470.5070.1880.9601.000
Skiing0.3400.5710.1100.4501.000
Kung-Fu Master0.3360.4820.1900.8000.958
Pitfall0.3260.4790.1730.8820.875
Road Runner0.3200.0000.6410.4471.000holds up on position
Centipede0.3140.6280.0000.4500.875position gradient vanishes
Assault0.3110.4410.1810.9050.917
Breakout0.2990.4880.1090.5501.000
Video Pinball0.2760.3520.1990.5001.000
Yars' Revenge0.2600.5200.0000.4641.000position gradient vanishes
Chopper Command0.2520.0000.5030.4521.000holds up on position
Asterix0.2510.2330.2690.1501.000
Venture0.2430.4860.0000.4741.000position gradient vanishes
Berzerk0.2140.4280.0000.4810.833position gradient vanishes
Seaquest0.1450.0000.2890.4791.000
Hero0.0440.0000.0870.4171.000no true-cause signal

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. value of a masked coalition: occlude every masked cause (do-intervention), step the horizon, read |output delta| vs intact — masked_abs_dy runner
  2. the mask operator = the oracle's occlude! (RAM/TIA -> 0, joystick masked = NOOP) — occlude! -> intervene_ram! / intervene_tia! jutari intervene_ram! jutari_oracle.jl:174, intervene_tia! jutari_oracle.jl:185
  3. extremal-perturbation search: grow the smallest mask that maximally shifts the output, then attribute per cause — extremal_mask runner
  4. 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/perturbation.jl
Reference
Fong & Vedaldi 2017; Fong et al. 2019
Record
perturbation_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.