Making Sense of Dependence: Efficient Black-box Explanations Using Dependence Measure

1 Introduction

• XAI explanations have supported model debugging, development strategies, and failure understanding, while AI outputs increasingly contribute to critical decisions.The introduction frames explanations as important across links in the decision chain.Source: §1 · p. 1
• Gradient and activation approaches can be misleading near an input and require model implementation access, limiting their use with third-party APIs.The gradient reflects only an infinitesimal neighborhood around the input.Source: §1 · p. 1
• Black-box perturbation methods address unavailable internals but use costly Monte Carlo evaluations to account for complex neural-network interactions.The forward-pass burden grows costly for increasingly large recent networks.Source: §1 · p. 2
• The proposed method measures dependence between patch perturbations and model outputs using HSIC and RKHS embeddings rather than variance-based analysis.The paper says HSIC captures more diverse information than variance-based indices and can be estimated more efficiently.Source: §1 · p. 2
• The authors report improved or matched ImageNet fidelity metrics, reduced computational cost, object-detection explanations, and pairwise patch-interaction evaluation.A new kernel gives HSIC an ANOVA-like orthogonal decomposition property.Source: §1 · p. 2

Attribution methods for white-box models

• White-box attribution uses gradients or activations, but gradients focus on an infinitesimal neighborhood and activation explanations depend strongly on layer choice.These methods require internal computations, unlike the proposed model-agnostic approach.Source: §2 · p. 3

Attribution methods for black-box models

• Occlusion masks one region at a time and can miss higher-order interactions that appear when multiple regions are masked together.LIME, RISE, Sobol, and the proposed work instead use random perturbations of multiple regions.Source: §2 · p. 3
• Black-box methods can rival or surpass white-box methods without internal states, yet their execution time remains a disadvantage.The paper proposes dependence-measure-based global sensitivity analysis to reach lower computation times than some white-box methods.Source: §2 · p. 3

Global sensitivity analysis using dependence measures

• Dependence-measure sensitivity analysis uses RKHS representations to capture more diverse information than variance-based indices with fewer model evaluations.The paper identifies HSIC as its dependence measure.Source: §2 · p. 3

3 Explanations using Hilbert-Schmidt Independence Criterion

• HSIC attribution assigns patch importance through dependence between patch perturbations and model outputs, with lower independence indicating greater importance.The section builds the attribution method within a sensitivity-analysis framework.Source: §3 · p. 3, §3.1 · p. 4

3.1 Sensitivity analysis of perturbed black-box models

• Binary, independently sampled patch masks perturb images by retaining patch information or replacing it with a black-image baseline.Nearest-neighbor upsampling maps the mask to image resolution before applying the inpainting operator.Source: §3.1 · p. 4

3.2 Hilbert-Schmidt Independence Criterion

• HSIC measures dependence through RKHS embeddings, and its empirical estimate scores each patch perturbation against the corresponding output.The paper gives an O(p^2) computation for the empirical formula.Source: §3.2 · pp. 4–5

3.3 Orthogonalisation of HSIC to enable evaluation of interactions

• With binary masks sampled from Bernoulli(1/2), the specified input kernel gives an orthogonal decomposition that supports measuring pairwise patch interactions.Without the decomposition property, subtracting individual patch scores may leave individual importance in the interaction measure.Source: §3.3 · pp. 5–6

3.4 Sample efficiency of HSIC estimator

• For the same estimation error of O(1/√p), HSIC requires p forward passes instead of p × (d + 2) for Sobol indices.The paper presents this sample-efficiency result as bridging the efficiency gap between black-box and white-box approaches.Source: §3.4 · p. 6

3.5 Implementation of the method

• The implementation samples masks with Latin Hypercube Sampling, vectorizes HSIC computation, and bilinearly upsamples patch scores to image resolution.The authors state that HSIC computation time is negligible compared with the model forward passes.Source: §3.5 · p. 6

4.1 Fidelity of classification explanations

• HSIC is best among tested black-box methods on Deletion across architectures; RISE leads Insertion, while HSIC remains competitive on that metric.The comparison covers ImageNet classification explanations; the table reports Deletion and Insertion scores and execution times.Source: Table 1 · p. 7, §4.1 · p. 8
• The efficient variant achieves competitive classification results more than 8 times faster than RISE and improves on Sobol’s execution time by a factor of 5.The accurate variant’s reported time-improvement factors are 5 and 3; HSIC also beats Integrated Gradients’ execution time.Source: §4.1 · p. 8

4.2 Estimator efficiency

• HSIC converges much faster than RISE and Sobol when explanations are compared with a 13,000-forward-pass reference.The experiment uses Spearman rank correlation on 100 ImageNet validation images with EfficientNet and 7 × 7 masks.Source: §4.2 · pp. 8–9, Figure 2 · p. 8

4.3 Explanation of object detection

• On YOLOv4 detections from COCO, HSIC is best on Insertion and µFidelity, not Deletion, and is 5 and 6 times faster than D-RISE and Kernel Shap.The table covers 1,000 images; execution times are averaged over those images.Source: Table 2 · p. 9, §4.3 · p. 9
• For a zebra misclassified as a cat, HSIC’s explanation highlights the cat at the image’s bottom-right corner.The figure also includes standard detection explanations.Source: Figure 3 · p. 9, §4.3 · p. 9

4.4 Finding spacial interactions in the model

• HSIC’s orthogonal decomposition estimates specific patch-pair interactions by subtracting each patch’s independent contribution from the joint-patch HSIC.This identifies regions that affect the output only when perturbed jointly.Source: §4.4 · pp. 9–10
• The puma example’s right- and left-mustache interaction scores 9.2, exceeding the eye/forehead independent-patch score of 8.2.The figure contrasts independent-patch heatmaps with important interactions shown in red; selected images were chosen qualitatively.Source: §4.4 · p. 10, Figure 4 · p. 10

5 Conclusion

• HSIC attribution is black-box, captures complex information through RKHS representations, and supports patch-interaction explanations.The conclusion says it reduces the computational burden of traditional black-box methods and is closer in efficiency to white-box methods.Source: §5 · p. 10

A On the Orthogonal Decomposition Property 1

• The appendix introduces the orthogonal decomposition property and uses a pedagogical example to motivate its importance for assessing interactions.It then states the property and points to a kernel constraint used to obtain it.Source: A On the Orthogonal Decomposition… · p. 15, §A.1 · p. 15

A.1 Orthogonal Decomposition Property

• The decomposition property requires constraints on kA; the appendix states that these permit indices HSIC(xA,y) to satisfy the property for any output kernel l.The appendix introduces terms for subsets of input variables and their corresponding vector xA.Source: §A.1 · p. 15

A.2 Motivating example

• The motivating example shows why joint effects matter: x2 and x3 each have zero individual HSIC with the output, despite their relevance to it.Assessing joint HSIC without the decomposition property can also suggest interactions between x1 and x2 or x1 and x3 because of x1's individual effect.Source: §A.2 · p. 16, Table 1 · p. 16
• With a decomposition-satisfying Sobolev kernel, HSIC_inter(x1,x2,y) and HSIC_inter(x1,x3,y) are approximately zero, while HSIC_inter(x2,x3,y) is significant.The appendix contrasts this with RBF, whose values are described as not relevant when the decomposition property does not hold.Source: §A.2 · p. 16, Table 2 · p. 16

A.3 Proof of Proposition 1

• The appendix recalls and proves Proposition 1, which was defined in Section 3.3.Source: §A.3 · pp. 16–17
• Proposition 1 states that kA satisfies the decomposition property under Assumption 1, with a Bernoulli variable of parameter 1/2 and a Dirac kernel in the construction.The proposition refers to k0 as defined in equation (4).Source: §A.3 · pp. 16–17
• The proof uses two iid random Bernoulli variables of parameter p with probability density functions ps and pt; it also considers Bernoulli variables x and x′, samples x ∼ x and x′ ∼ x′, and kernel k(x, x′) = δ(x = x′).Source: §A.3 · p. 17

B Complete fidelity results

• The complete fidelity results include Deletion and Insertion scores on 1,000 ImageNet validation images, with execution times averaged over 100 ResNet50 explanations.The caption states that lower Deletion and higher Insertion scores are better.Source: Table 3 · p. 18
• The µFidelity table reports scores on 1,000 ImageNet validation images, with execution times averaged over 100 ResNet50 explanations.Higher µFidelity is better, according to the caption.Source: Table 4 · p. 18

C.1 Visualizations

• The visualization appendix samples object-detection explanations from the first 40 COCO images and describes HSIC as more robust than RISE and KernelShap.The text says the other methods are often blurry and sometimes fail.Source: §C.1 · p. 18, Figure 2 · p. 19, Figure 3 · p. 19

C.2 Error explanations oh HSIC against RISE

• HSIC finds an explanation for YOLOv4's cat-for-zebra error, while RISE and KernelShap fail even with different grid sizes.Source: §C.2 · p. 20
• The cited example concerns a model error: YOLOv4 recognizes a cat instead of a zebra.Source: §C.2 · p. 20
• Figure 4 contrasts HSIC's explanation with blurry explanations from RISE and KernelShap at different grid sizes.Source: §C.2 · p. 20

• Figure 5 presents ImageNet explanations with HSIC eff.Source: Figure 5 · p. 21
• Figure 6 presents ImageNet explanations with HSIC acc.Source: Figure 6 · p. 22

E Attribution methods

• Saliency uses class-score gradients, while Gradient ⊙Input multiplies those gradients element-wise by the input to sharpen attribution maps.Source: E Attribution methods · p. 22
• Integrated Gradients sums gradients along a path from a zero baseline; SmoothGrad averages gradients around noisy inputs, while VarGrad aggregates their variance.Integrated Gradients uses a trapezoidal approximation; SmoothGrad and VarGrad use 80 samples with σ = 0.2 × (xmax − xmin).Source: E Attribution methods · p. 23
• Grad-CAM uses gradients and last-layer feature maps, while Grad-CAM++ combines positive partial derivatives with a weighted class score.The maps are resized to input dimensions by bilinear interpolation, and the experiments use each model’s last convolutional layer.Source: E Attribution methods · p. 23
• Occlusion assigns prediction changes from masking image patches to the occluded regions; RISE estimates pixel importance from outputs on randomly masked inputs.The experiments use a zero occlusion baseline and RISE masks generated from a 7 × 7 subspace with E(M) = 0.5.Source: E Attribution methods · pp. 23–24

F.1 Definitions

• Deletion measures score drops as important variables are set to baseline, whereas Insertion adds important variables progressively from a baseline image.The reported metrics are AUCs, with a zero baseline for Deletion and the same baseline for Insertion.Source: §F.1 · p. 24
• µFidelity measures the correlation between importance scores and score falls after variables are set to baseline.The experiments set k to 20% of the variables and use the Deletion baseline.Source: §F.1 · p. 24

F.2 Trade-off between Insertion and Deletion

• Deletion and Insertion AUCs emphasize early-ranked patches because the most important patches are removed or added first.Source: §F.2 · p. 24
• Deletion evaluates sequential removals near the original image, whereas Insertion begins from a far-off black baseline that may influence its score.Source: §F.2 · p. 24
• Deletion improves as HSIC maps become sharper, while Insertion improves as they become more spread out; RISE shines on Insertion and HSIC dominates Deletion.The grid-search comparison is for MobileNetV2 on 1,000 ImageNet validation images, averaged over 27 runs.Source: Table 5 · p. 25, §F.2 · p. 25

G Additional experiments on stability

• HSIC scores are more stable than RISE and Sobol as forward passes vary, supporting use of fewer passes.The experiment uses ResNet50 on 100 ImageNet validation images; Figure 7 plots Deletion score against forward passes.Source: Figure 7 · p. 25, G Additional experiments on stability · p. 25

Checklist

• The authors identify HSIC’s computation complexity as a limitation and report that a vectorized implementation alleviates it.Source: Checklist · p. 26