Fast Hierarchical Games for Image Explanations

Jacopo Teneggi, Alexandre Luster, Jeremias Sulam

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.

Introduction

Deep neural networks are frequently criticized as "black boxes," a reputation that hinders their adoption in high-stakes domains like healthcare and law. To foster trust, it is essential to understand the rationale behind specific model predictions. Shapley values, derived from cooperative game theory, represent the gold standard for this task by fairly distributing "credit" for a prediction among input features (pixels).

However, calculating exact Shapley values is computationally prohibitive, requiring $2^n$ model evaluations for $n$ features. For high-resolution images, this complexity makes exact computation impossible, forcing current state-of-the-art methods like SHAP or LIME to rely on noisy or slow approximations that often fail to scale to real-world medical imaging or computer vision tasks.

Methodology: The h-Shap Framework

The authors introduce h-Shap, a method that treats image explanation as a hierarchical game. The approach relies on three core pillars:

  1. Hierarchical Partitioning: The image is partitioned into a "quadtree" structure, recursively splitting the space into quadrants.
  2. Recursive Pruning: The algorithm calculates Shapley coefficients for top-level quadrants. If a quadrant's contribution falls below a threshold ($\tau$), the algorithm assumes the target concept is absent from that area and prunes the entire branch.
  3. The MIL Assumption: This pruning is theoretically grounded in the Multiple Instance Learning (MIL) assumption, which posits that an image area is positive if and only if it contains at least one positive feature.
The expected number of visited nodes during the h-Shap search process as a function of the sparsity parameter ρ, demonstrating significant pruning compared to a full search (red dashed line).

By identifying "uninformative" blocks early, h-Shap avoids thousands of unnecessary model evaluations. This allows for two variants: dh-Shap (depth-first) and bh-Shap (breadth-first), the latter of which enables relative thresholds based on node importance at specific depths.

Experimental Evaluation

The performance of h-Shap was evaluated against five major competitors—GradientExplainer, DeepExplainer, PartitionExplainer, LIME, and Grad-CAM—across three distinct scenarios:

  • Synthetic Dataset: $100 \times 120$ pixel images where the goal was to identify geometric "crosses."
  • P. vivax (Malaria) Dataset: High-resolution ($1200 \times 1600$) blood smears for detecting infected cells.
  • LISA Traffic Light Dataset: Real-world driving sequences ($960 \times 1280$) used to identify green traffic lights.

Results and Discussion

h-Shap demonstrates a significant leap in both speed and accuracy. It is consistently 1 to 2 orders of magnitude faster than other Shapley-based methods, remaining efficient even as image resolution increases.

Qualitative comparison of saliency maps across synthetic, medical (BBBC041), and real-world (LISA) datasets. h-Shap provides superior localization and clarity compared to baseline methods.

In terms of accuracy, h-Shap outperformed all competitors in $f_1$ scores when compared against ground-truth bounding boxes. While methods like Grad-CAM are fast, they lack the precision of h-Shap. Furthermore, ablation tests—where the most important pixels are removed to observe the drop in model confidence—confirmed that h-Shap identifies the most critical features for the model's decision-making process. A key advantage is that h-Shap avoids the "dilution" effect seen in traditional approximations, where the importance of individual pixels in high-resolution images becomes mathematically obscured.

Conclusion and Future Work

While h-Shap offers a breakthrough in efficiency, it is currently optimized for the "OR" logic of Multiple Instance Learning. Future iterations may need to address complex "AND" relationships where a prediction depends on the simultaneous presence of multiple features. Additionally, the authors suggest "cycle spinning" (averaging results from shifted partitions) to mitigate boundary issues where objects are split between quadrants. Despite these areas for growth, h-Shap establishes a new state-of-the-art for fast, exact, and scalable image explanations.

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},
}
Figure