ShapBPT: Image Feature Attributions Using Data-Aware Binary Partition Trees

AI summary

Overview

Research area: Explainable AI for Computer Vision (XCV) — specifically, pixel-level feature attribution using hierarchical Shapley values.

Technical level: Intermediate. The core idea (partitioning an image into meaningful regions before attributing importance) is intuitive, but the paper leans heavily on cooperative game theory (Shapley values, semivalues, coalition structures), and the mathematical formalism in the Methodology and Technical Appendix is dense.

Scope: The paper proposes ShapBPT, a model-agnostic image explainer that combines the Owen approximation of Shapley values with a data-aware Binary Partition Tree built from the image's own morphology, and evaluates it across seven computer-vision tasks plus a human preference study.

What This Paper Is About

Explaining why an image classifier made a prediction usually means scoring individual pixels by importance. Existing Shapley-based explainers such as SHAP's Partition Explainer split the image using fixed geometric grids (axis-aligned rectangles), which ignore what the image actually contains. This paper asks whether partitioning the image according to its own morphological structure — regions of similar color and coherent shape — produces feature attributions that both converge faster and match the objects a human would point to.

Key Contributions

1. A new model-agnostic XCV method, ShapBPT, that integrates an adaptive multiscale partitioning algorithm (the Binary Partition Tree, repurposed from MPEG-7 image encoding) with the Owen approximation of the Shapley coefficients, overcoming the inflexible fixed hierarchies used by state-of-the-art methods such as SHAP's Partition Explainer.

2. A hybrid two-stage strategy that satisfies two requirements the authors identify as necessary for an effective binary hierarchical coalition structure: (R1) as few recursive cuts as possible to reach relevant regions, and (R2) partitions that are not fixed in advance. The BPT supplies a refinable a-priori hierarchy aligned with image morphology, while an a-posteriori splitting strategy follows the distribution of Shapley values.

3. An empirical assessment across multiple vision tasks, models and datasets (experiments E1–E7 covering ResNet50, SwinViT, Yolo11s, a CNN, a VAE-GAN, ViT-Base16, and an ideal linear model), comparing ShapBPT against Shapley-based and gradient-based explainers on both response-based (AUC) and ground-truth-based (IoU) scores.

4. A controlled 20-participant human-subject study (E8) measuring which explanation maps people found most helpful for understanding a model's prediction.

Main Findings

• BPT partitions beat axis-aligned partitions consistently: Across various models, scoring methods and datasets, BPT outperformed AA and the other compared methods, supporting the intuition that tailoring partitions to the characteristics of the data is beneficial.

• Budget efficiency: BPT-100 (a budget of 100 model evaluations) already surpassed most competing methods, indicating the method maintains its advantage under resource constraints.

• Faster convergence: The authors report a significantly faster convergence rate for ShapBPT, attributed to the fact that on average fewer recursive applications of the Owen formula are needed to accurately localize objects with a data-aware partition hierarchy than with other hierarchies.

• Strong on Vision Transformers: ShapBPT worked well with SwinViT (E3) and ViT-Base16 (E7), transformer models known for robustness to partial object occlusion. In E3, all methods except BPT produced noticeably more confused saliency maps that attributed importance to background features.

• Contrast with LIME and GradCAM: BPT explanations share similarities with LIME's region-focused output but without LIME's typical noise and without relying on a fixed, inflexible segmentation; they also resemble GradCAM's maps but without GradCAM's blurriness.

• Human preference (E8): With 20 participants each ranking four explanation maps on four randomly selected images from E1 (80 rank-lists per method), BPT ranked first in 51% of cases with an average rank of 1.79, followed by GradCAM (33% first-place, mean 2.41) and LIME (10%, mean 2.56), with AA seldom preferred (6%, mean 3.24). A Friedman test gave χ²(k=3) = 19.56, p-value = 0.0002, rejecting H0.

• Statistical significance: One-way ANOVA tests for each score, testing the null hypothesis of equal means across all sample populations at a p-value significance threshold of 0.05, rejected the null hypothesis in all cases.

• Reported model accuracies: The E1 ResNet50 (1K-V2 pretrained from PyTorch) has accuracy 80.858%; the E3 SwinViT has accuracy 81.4%.

Methodology in Plain English

The paper starts from a standard idea in explainable AI: a prediction can be attributed to features by treating them as players in a cooperative game (a "coalition game") and computing Shapley values — a fair way of dividing the total payoff among players. Because exact Shapley values are at least #P-hard to compute and images have hundreds or thousands of pixels, the authors use the Owen approximation, which first groups features into coalitions and only allows restricted cooperation between groups. This is the same family of ideas used by SHAP's Partition Explainer.

The novelty lies in how the image is grouped. Instead of splitting the image into rectangles along the longest axis (an axis-aligned, or AA, hierarchy), the authors build a Binary Partition Tree bottom-up: they start with every pixel as its own indivisible partition and iteratively merge adjacent partitions, choosing at each step the pair that minimizes a data-aware distance function combining squared color range, area, and perimeter. The resulting quasi-balanced binary tree has leaves at pixels and a single root covering the whole image, so it fits directly into the recursive Owen formula.

Refinement is adaptive rather than fixed-depth: given a total budget b of evaluations of the masked model, the algorithm iteratively splits the partition that maximizes the sum of Shapley values within it, at a cost of 2 model evaluations per split. The authors prove (Theorem 1) that for a balanced tree of depth d, the time complexity is on the order of O(4^d) evaluations of the masking function — which is why a data-aware hierarchy that reaches relevant regions in fewer cuts matters so much.

They then compare methods using two families of scores: response-based AUC+ and AUC−, which measure how well ranked explanation coefficients align with the black-box model's output without any notion of a "correct" answer, and ground-truth-based AU-IoU and max-IoU, which compare the top-q quantile of important pixels against a known ground-truth mask G.

Why This Matters

Impact on research. As far as the authors know, this is the first XCV method that combines the Owen formula with a data-aware partition hierarchy for image data. It closes what the paper describes as a gap — no prior Shapley method had leveraged data-aware hierarchies for computer-vision tasks — and it proposes a recursive Owen formulation (their Eq. 4) that the authors state is not found in published literature, providing a full derivation in the Technical Appendix.

Real-world applications:

• Medical and industrial anomaly detection, where the XCV task is separating true anomalies from noise (demonstrated on the MVTec hazelnut category with a convolutional VAE-GAN).
• Object detection systems such as Yolo11s on MS-COCO, where explanations must highlight detected objects.
• Facial attribute analysis, localizing regions that positively or negatively influence predictions such as "brown hair" or "eyeglasses" (CelebA-HQ).
• General image classification auditing for regulators and practitioners who need to verify which pixels drove a decision, in a budget-efficient way.

Industry relevance. The method is released with a Python package (pip install shap-bpt), a code repository, and a separate tests repository. Its ability to remain competitive at a budget of 100 model evaluations matters for deployment economics, since each evaluation requires a forward pass through the model being explained. The work was funded under the European Union's Horizon Chips JU program (Grant Agreement No. 101139769, DistriMuSe project).

Future Directions

• Integrating SegmentAnything (SAM): The authors tested SAM as a segmentation source for LIME and found it improves on quickshift but is significantly slower. They note SAM does not generate a regular hierarchical coalition structure, which is a key requirement of the Owen formula, so constructing a SAM-compatible HCS demands new algorithmic machinery — left explicitly as future work.
• Extending beyond binary hierarchies: The Technical Appendix presents a generalized recursive form for m-ary hierarchies (m > 2), leaving open how different branching structures trade off against the O(4^d) cost.
• Broader task and modality coverage: The evaluation is limited to the seven reported experiments on color images; whether the data-aware hierarchy strategy transfers to video, 3D data, or other modalities is not explored.
• Scaling the human evaluation: The user study covers 20 participants and four images from E1 only, so the generality of the human-preference result beyond that setting remains an open question.

Target Audience

Researchers and practitioners in explainable AI and computer vision who need pixel-level attributions, particularly those already familiar with SHAP, LIME, or gradient-based explainers and looking for a model-agnostic alternative with better alignment to image structure. It also suits engineers deploying interpretability tooling who care about the number of model evaluations required, and graduate students studying the intersection of cooperative game theory and visual interpretability.

Authors’ abstract

Pixel-level feature attributions are an important tool in eXplainable AI for Computer Vision (XCV), providing visual insights into how image features influence model predictions. The Owen formula for hierarchical Shapley values has been widely used to interpret machine learning (ML) models and their learned representations. However, existing hierarchical Shapley approaches do not exploit the multiscale structure of image data, leading to slow convergence and weak alignment with the actual morphological features. Moreover, no prior Shapley method has leveraged data-aware hierarchies for Computer Vision tasks, leaving a gap in model interpretability of structured visual data. To address this, this paper introduces ShapBPT, a novel data-aware XCV method based on the hierarchical Shapley formula. ShapBPT assigns Shapley coefficients to a multiscale hierarchical structure tailored for images, the Binary Partition Tree (BPT). By using this data-aware hierarchical partitioning, ShapBPT ensures that feature attributions align with intrinsic image morphology, effectively prioritizing relevant regions while reducing computational overhead. This advancement connects hierarchical Shapley methods with image data, providing a more efficient and semantically meaningful approach to visual interpretability. Experimental results confirm ShapBPT's effectiveness, demonstrating superior alignment with image structures and improved efficiency over existing XCV methods, and a 20-subject user study confirming that ShapBPT explanations are preferred by humans.