Fast Hierarchical Games for Image Explanations

Jacopo Teneggi, Alexandre Luster, Jeremias Sulam

TL;DR

Shapley values offer an axiomatic, theoretically rigorous way to explain model predictions, but computing them for high-resolution images is computationally intractable ($O(2^n)$ for $n$ pixels). Hierarchical Shap (h-Shap) solves this bottleneck for Multiple Instance Learning (MIL) tasks by organizing image features into recursive quadtree games, pruning irrelevant regions top-down. The result is an exact or provably bounded Shapley attribution that runs one to two orders of magnitude faster than existing SHAP baselines while achieving state-of-the-art localization accuracy.

What Problem Does This Paper Address?

Deep convolutional networks often operate as opaque black boxes. In high-stakes applications like medical imaging or autonomous driving, trust demands knowing why a model flagged an image. Feature-removal techniques rooted in cooperative game theory (Shapley values) possess desirable mathematical properties (efficiency, symmetry, linearity, nullity), but calculating them exactly requires evaluating exponentially many feature subsets.

For standard megapixel images, direct computation would take trillions of years. Existing workarounds—such as GradientExplainer, DeepExplainer, and PartitionExplainer—rely on heuristic sampling or gradient-based approximations that either suffer from memory bottlenecks on large inputs, produce noisy single-pixel attributions, or lack rigorous error bounds.

Methods

The authors introduce Hierarchical Shap (h-Shap), which recasts attribution into a hierarchy of small, low-dimensional cooperative games:

  • Recursive Tree Partitioning: An image is hierarchically split into symmetric subregions (e.g., a quadtree where each parent node splits into $\gamma = 4$ quadrants).
  • Top-Down Pruning: At each node $S$, the algorithm computes Shapley coefficients for its $\gamma$ children. Evaluating a 4-player game requires only $2^4 = 16$ forward passes. If a subregion has an attribution below a threshold $\tau$, its entire branch is pruned.
  • Search Strategies: The method supports depth-first search (dh-Shap) with an absolute threshold $\tau$, or breadth-first search (bh-Shap) using a relative percentile threshold across nodes at the same depth.
  • Controlled Granularity ($s$): Users specify a minimum patch size $s$, terminating search early to obtain coarser, region-level saliency maps while reducing compute.
  • Baseline Masking: Missing features are replaced with their unconditional expectation over the training set.

Datasets

The authors evaluated h-Shap across three binary classification tasks where ground-truth localization is known:

  1. Synthetic Shapes: $100 \times 120$ images with non-overlapping geometric shapes, labeled positive if at least one cross is present. Ground truth is pixel-accurate cross masks.
  2. BBBC041v1 Malaria Smears: $1200 \times 1600$ microscopy images classified for the presence of Plasmodium vivax trophozoites (and extended to multiclass trophozoite/ring detection) with bounding-box ground truth.
  3. LISA Traffic Light: $960 \times 1280$ daytime driving frames labeled for the presence of a green traffic light, evaluated against annotated bounding boxes.

Key Insights and Ideas

  • Decoupling Image Size from Game Complexity: Instead of playing one intractable $n$-player game, h-Shap plays a series of trivial $\gamma$-player games. The computational upper bound drops from $O(2^n)$ to $O(2^\gamma k \log_\gamma n)$, where $k$ is the number of relevant leaf patches.
  • Exploiting the MIL Structure: In Multiple Instance Learning, an image is positive if at least one local region contains the target concept (acting effectively as a logical OR). If a coarse quadrant contains no target concept, none of its sub-patches can either, guaranteeing that pruning discards zero true positives.
  • Exact Recovery and Theoretical Bounds: Under MIL data generation assumptions (Assumption A1), h-Shap at pixel scale ($s=1$) recovers the exact Shapley values. For $s > 1$, the cosine similarity between true and hierarchical attributions is bounded below by: $$\frac{\langle \Phi, \hat{\Phi}\rangle}{\|\Phi\|_2 \|\hat{\Phi}\|_2} \ge \max\left\{\frac{1}{\sqrt{s}},\, \sqrt{\frac{k}{n}}\right\}$$

Key Results

  • Runtime: h-Shap is 10$\times$ to 100$\times$ faster than PartitionExplainer, DeepExplainer, and GradientExplainer across high-resolution benchmarks. Grad-CAM was the only method faster than h-Shap, but at a severe cost in explanation fidelity.
  • Attribution Accuracy: Across all datasets, h-Shap achieved the highest $F_1$ scores against ground-truth masks. On the synthetic task, competing methods suffered when only one target object was present, whereas h-Shap maintained consistent precision regardless of object count.
  • Ablation Performance: Progressively removing top-scoring features identified by h-Shap produced the steepest drop in prediction logits toward zero, confirming that it zeroes in on discriminative pixels without erasing confounding background structures.

Limitations and Future Work

  • The MIL Assumption: h-Shap assumes the target concept behaves like an OR operation over local features. If a class requires long-range feature combinations, or if the minimal patch size $s$ is chosen smaller than the object itself (destroying recognizability), the assumption breaks down.
  • Rigid Quadtree Boundaries: Target concepts bisected by quadrant split lines can suffer boundary artifacts. The authors suggest cycle-spinning (spatial shifts and averaging) or data-dependent superpixel partitioning as natural remedies.
  • Independent Baseline: Masking features with unconditional mean values assumes approximate local feature independence; incorporating interventional or conditional generative inpainting remains future work.

Summary updated

Abstract

As modern complex neural networks keep breaking records and solving harder problems, their predictions also become less and less intelligible. The current lack of interpretability often undermines the deployment of accurate machine learning tools in sensitive settings. In this work, we present a model-agnostic explanation method for image classification based on a hierarchical extension of Shapley coefficients–Hierarchical Shap (h-Shap)–that resolves some of the limitations of current approaches. Unlike other Shapley-based explanation methods, h-Shap is scalable and can be computed without the need of approximation. Under certain distributional assumptions, such as those common in multiple instance learning, h-Shap retrieves the exact Shapley coefficients with an exponential improvement in computational complexity. We compare our hierarchical approach with popular Shapley-based and non-Shapley-based methods on a synthetic dataset, a medical imaging scenario, and a general computer vision problem, showing that h-Shap outperforms the state-of-the-art in both accuracy and runtime. Code and experiments are made publicly available.
BibTeX
@article{teneggi2023fast,
  author = {Jacopo Teneggi and Alexandre Luster and Jeremias Sulam},
  title = {{Fast Hierarchical Games for Image Explanations}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2023},
  doi = {10.1109/tpami.2022.3189849},
}

Loading related content...

Figure