Making Sense of Dependence: Efficient Black-box Explanations Using Dependence Measure
Authors: Paul Novello
Thomas FEL
David Vigouroux
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep learning
machine learning
explainability
interpretability
computer vision
black box
dependence measure
kernel methods
sensitivity analysis

Abstract: This paper presents a new efficient black-box attribution method built on Hilbert-Schmidt Independence Criterion (HSIC). Based on Reproducing Kernel Hilbert Spaces (RKHS), HSIC measures the dependence between regions of an input image and the output of a model using the kernel embedding of their distributions. It thus provides explanations enriched by RKHS representation capabilities. HSIC can be estimated very efficiently, significantly reducing the computational cost compared to other black-box attribution methods.
Our experiments show that HSIC is up to 8 times faster than the previous best black-box attribution methods while being as faithful.
Indeed, we improve or match the state-of-the-art of both black-box and white-box attribution methods for several fidelity metrics on Imagenet with various recent model architectures.
Importantly, we show that these advances can be transposed to efficiently and faithfully explain object detection models such as YOLOv4. 
Finally, we extend the traditional attribution methods by proposing a new kernel enabling an ANOVA-like orthogonal decomposition of importance scores based on HSIC, allowing us to evaluate not only the importance of each image patch but also the importance of their pairwise interactions. Our implementation is available at \url{https://github.com/paulnovello/HSIC-Attribution-Method}.

Making Sense of Dependence: Efficient Black-box Explanations Using Dependence Measure
Paul Novello
Thomas Fel 2
David Vigouroux
IRT Saint Exupery, France, Artificial and Natural Intelligence Toulouse Institute, Université de Toulouse, France Carney Institute for Brain Science, Brown University, USA
p www.:oellllooi--aaaaeeeppppepppa com
Abstract
This paper presents new efficient black-box attribution method built on Hilbert- Schmidt Independence Criterion (HSIC). Based on Reproducing Kernel Hilbert Spaces (RKHS). HSIC measures the dependence between regions of an input image and the output of a model using the kernel embedding of their distributions. It thus provides explanations enriched by RKHS representation capabilities. HSIC can be estimated very efficiently, significantly reducing the computational cost compared other black-box attribution methods. Our experiments show that HSIC is up to 8 times faster than the previous best black-box attribution methods while being as faithful. Indeed, we improve or match the of-te-of-the-art of both black-box and white-bo box attribution methods for several fidelity metrics on Imagenet with various recent model architectures. Importantly, we show that these advances can be trans- posed to efficiently and faithfully explain object detection models such as YOLOv4. Finally, we extend the traditional attribution methods by proposing a new kernel enabling an ANOVA-like orthogonal decomposition of importance scores based on HSIC, allowing us to evaluate not only the importance of each image patch but also the importance of their pairwise interactions. Our implementation is available at htttss://githaai
http:///gggghaabcccaaaaooolllloo cow.paulnovello/ HHICSSSICCAAA Attribution Satttinototttooooooooe Methhd
Introduction
Artificial Intelligence has established itself as the reference technique for tackling many real-world automation tasks. Consequently, the diversity of its applications is growing and reaching fields where its outputs can contribute critical decision-making, In such cases, it is essential to be able to provide explanations for each link of the decision chain, including AI algorithms. Over the past decade, many techniques have emerged explain the predictions of these algorithms 43 36 41
15
26 38 marking the birth of new field called Explainable Artificial Intelligence (XAI). The tools developed in this research field, mostly designed explain neural networks, have already proven helpful. For instance, it has been used in model debugging, identification of new development strategies for practitioners, and failure understanding.
52 32
31
27
Initial approaches are based on analyzing the internal state neural networks during inference, often relying on input gradients activation values of hidden layers 43
25] However, 41
15]
the gradient only reflects the model's operation in an infinitesimal neighborhood around an input and can therefore be misleading (18). Furthermore, their applicability limited to the case where the final user has access to the implementation of the model. Therefore, such methods cannot be applied in the most common use cases, e.g. when models are made available by third parties through API calls or specialized hardware. In order to address this issue, some black-box approaches have
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

M
Px
PP
f())
+(.)
|| [((x)) px) (w(y) mylllis
Px
g
Mly
F
Figure HSIC Explainability method. We sample random binary masks M that we use to perturb the input image X. We obtain perturbed output and measure the dependence between the distribution of each patch PM of the binary mask and that the output Py. We use a dependence measure, Hilbert Schmidt Independence Criterion (HSIC), based on the kernel embedding of this distribution in a Reproducing Kernel Hilbert Space (RKHS). Each patch is then assigned the value of this measure: the more independent a patch is from y, the less important is to explain it.
been recently proposed, relying on the perturbation of the input and the observation of its effect on the output [55] 36 32 II]. One challenge of such perturbation methods is assessing this effect together with taking into account complex interactions inherent to deep neural networks. To account for these characteristics, black-box methods resort to complex Monte Carlo methods that require high number of model forward passes, which can be expensive for recent neural networks that are
growing larger.
In [ 29], the authors propose methods reduce the required number of forward passes, but the obtained performance improvements still do not make them close to white-box methods. In this work, similarly to [1]. we cast perturbation studies as Global Sensitivity Analysis (GSA) 34 However, we rely on a whole different approach based on dependence measure rather than analysis of variance. We measure the dependence between patch- whiee perturbations of an input image and the model's output by comparing the distribution of perturbed inputs and outputs embedded in a Reproducing Kernel Hilbert Space (RKHS). More specifically, we use Hribbet-Schhidt Independence Criterion (HSIC), a dependence measure based on the Hilhert-Schmidt norm of the empirical cross-covariance operator evaluated between the represented distribution. HSIC leverages the rich theory of RKHS, thereby capturing more diverse information than variance-based indices such as Sobol. In addition, can be estimated more efficiently, even bridging the performance gap between black-box and white-box methods.
Our contributions are as follows: (1) we introduce a new efficient black-box attribution method relying on HSIC; (2) we derive new kernel that confers an Analysis of Variance (ANOVA)-like orthogonal decomposition property, allowing us to go beyond usual attribution methods and evaluate interactions between patches of the image; (3) we conduct experiments to assess the fidelity of our method on ImageNet and show that improves or matches the state-of-the art for different metrics while bridging the computational gap between black-box and white-box attribution methods; (4) we demonstrate its versatility and its potential by successfully applying it to a less common test case: explanations of object detection; and new test case: evaluation of pairwise interactions between patches of the input image.
2
Related work
Our work builds on prior efforts aiming to develop attribution methods in order to explain the prediction of deep neural network by pointing to input variables that support the prediction typically pixels groups of pixels, i.c. patches in the image which lead to importance maps.
Attribution methods for white-box models A large number of attribution methods have been developed relying on the gradient of the decision studied. The first method was introduced in g and improved in 43 55 50] and consists of explaining the decisions of a convolution model by

---

back propaagatgg the gradient from the output to the input, indicating which pixels affect the decision score the most. However, this family of methods is limited because they focus on the influence of individual pixels in an infinitesimal neighborhood around the input image in the image space. For instance, has been shown that gradients often vanish when the prediction score to explained
near the maximum value [52]. Integrated Gradient [52] and SmoothGrad [55 partially address this issue by accumulating gradients. Another family of attribution methods relies on the neural network's s activations. Popular examples include CAM (56), which computes an attribution score based weighted sum of feature channel activities - right before the classification layer. GradCAM [4]] extends CAM via the use of gradients, reweighting each feature channel to take into account their importance for the predicted class. Nevertheless, the choice of the layer has a huge impact on the quality of the explanation. In comparison, our proposed approach is model-agnostic and hence does not require access to internal computations.
Attribution methods for black-box models In this paper, we extend the problem by restricting it to a black-box model: the analytical form and potential internal states of the model are unknown. Several methods compute influence scores for each individual pixel or group of pixels.
The first method, Occlusion [55], masks individual image regions one at time with an occluding mask set to bascline value and assigns the corresponding prediction scores all pixels within the occluded region. Then the explanation is given by these prediction scores and can be easily interpreted. However, occlusion fails to account for the joint (higher-order) interactions between multiple image regions. For instance, occluding two image regions one at time may only decrease the model's 's prediction minimally (say single eye or mouth component on face), while occluding these two regions together may yield substantial change in the model's prediction if these two regions interact non-linearly as is expected for deep neural network. Our work, together with related methods such LIME (36). RISE (32 and more recently Sobol [1] addresses this problem by randomly perturbating the input image in multiple regions at a time.
Surprisingly, RISE [32] and Sobol Attribution [[T] have recently shown that black-box attribution methods can rival and even surpass the white-box methods commonly used without recourse to internal states. However, despite the efforts in [ to limit their computational overhead, black-box methods remain far from white- box methods in terms of execution time. In this work, we show that is possible to match or even surpass the performances of current black-box methods while reaching computation times lower than some white-box methods by using dependence measure-basse Global Sensitivity Analysis (GSA).
Global sensitivity analysis using dependence measures Our attribution method builds on the GSA framework. The approach was introduced in the 70s 77 and was popularized with variance-based sensitivity analysis and Sobol indices
[46]. It consists of evaluating the sensitivity of a model's output of interest to some input design variables. GSA is currently used in many fields, especially for the study of physical phenomena [4 34). Recently, dependence measure- measure-based sensitivity analysis was introduced [8] and was shown to circumvent some practical issues of variance- based sensitivity analysis. In particular, by relying on the representation capabilities of RKHS, the dependence measure that we use in this work, HSIC (20), captures more diverse information than traditional variance- indices for far fewer model evaluations.
3 Explanations using Hilbert-Schmidt Independence Criterion
In this section, we describe sensitivity analysis-based attribution methods, define Hilbert-Schmidt Independence Criterion (HSIC) 20 and explain how we can use it and adapt it to design a new black-box attribution method whose efficiency competes with white-box methods. We also explain the theoretical advantages of HSIC that we can build on to go beyond traditional attribution methods.
3.1 Sensitivity analysis of perturbed black-box models
Let f X' Xi,.., + y' be the model under study, 2; E X: the input variables and y = [x11,.., xn)) E ) the output value of the model f. GSA studies the sensitivity of to each input sr; by considering them as iid (independent and identically distributed) random variables and assessing the link between their distribution and that of the output after an initial input sampling. Given input
3

---

vector X (zi,..., En), a prediction y y= f can thus be explained using sensitivity analysis by applying random perturbations x (x1, ....... ).) x; Fx, of the original X and analyzing the importance of each x; for explaining the variations of y which is considered a random variable,
y ~ Py.
For image data, the inputs z; are pixels. However, pixel perturbations would only emphasize low level explanations. To obtain high level and meaningful explanations, we rather consider a random perturbation mask M = (M .... Ma) E [0, 1]. We upsample this mask using a Nearest Neighbor interpolation method to obtain u (M) E [0, 1|" patch-perturbater vector that we apply on the input
image X using mask operator T X' [0, 1] - X. More specifically, we use the inpainting operator defined by T T .M) X @ u M) - (1 (MM)),, with @ the Hadamard product and baseline value (here, lr is black image with all pixels' value 0 [36 (55). Hence, the mask M aggregates the patch-wise random perturbations M, that are sampled independently for each patch (M, are iid). practice, the perturbations contained in the mask are binary perturbations, simulate whether the information contained in the patch is kept in the image or not.. We thereby assess the effect of each image patch, represented by Md on the output.
The perturbation methodology thus consists of (1) sampling p masks (M ,.... M
} from M PM (with PM = M,, x ... x M,,)) (2) applying them to the original input vector, leading to perturbed input vectors (e.g., partially masked images) {T(X, MM)), T(X, M (et) (3) [f(T(XX )), .... f(T(X, MM and (4) sta- tistically assessing the effect of each mask M, on y by estimating a sensitivity measure between each FM, and yy from the previous sampling. In this paper, we consider that the more independent M, is
computing the predictions {g(", ..... y "i.,,.".."))
from y, the less important the corresponding image patch is to explain [ In the following, we describe HSIC, dependence measure, and how to use it in practice.
3.2 Hilbert-Schmidt Independence Criterion
Let x and y be two random variables of probability distribution Ixx and Py defined on X' and V. HSIC measures the dependence between Pxx and Pyy based on their embedding in Reproducing Kernel Hilbert Space (RKHS). Let yp X' - F and 1/ - two continuous feature mapping between X, V and two RKHS F, G, such that the inner product between the feature embeddings of x, E X in F is given by the kernel k<x, = (1(xx), vp(x") (and [ly. y/) = (v(y), (yy))) for y. E y). The cross-covariance operator Cxy G + F between the random variables and is defined in [17 and can be written.
Cxy Exyl(<(()) Hx) & (v(y) My]],
where /x = Ex [x))) and Myy By [v)) are the mean embedding of x and y in F and G. When F and & are universal RKHS on the compact domains X' and V. then ||Cxy || = 0 if and only if
and y are independent, where || || denotes the Hilbert Schmidt norm (see (21)) In (20). the authors define HSIC as ||Cxy 11:ss which can be written:
HSIC(x,y) =Ex, y. (k(a,, x' My, s/)) + Ex,x [k(2, Ex,x x') By ((,,)))
(I)
2Fx,y Ex [k( x' ") [[, v')),,
where x, x' and y' are pairwise iid. HSIC can also be expressed in terms of Maximum Mean Discrepancy (MMD), which is distance between mean embeddings defined in an RKHS (ST), More specifically, let the product RKHS P = F x G with kernel v( y), (a', v/)) = k(z, x' 2y)(y.v v'). Then, HSIC(x, = > (PxxP Px.y), where Ye is the MMD operator on P. HSIC thus measures the distance between P xy and Py 1x x embedded in P [8. Since x 1 Ly = F = PxPx, the closer these distributions are, the sense of the MMD, the more independent they are.
Thus, given a set of inputs { p.,,ppppp and the associated outputs (y1,-... Up),
20 shows that
HSIC can be estimated by
1
H = (p - 1)2 tr(KHHH).
(2)
where H, L, K E RPXP and K3₃ k(x;, .ry), Li.j 1e,, Us) and H,j 8) = j) p1 Using this formula, HP can be computed with (pp²) complexity. In this work, the input variables Mj are the patch perturbations. Therefore, we compute HP i... the estimation of the HSIC between a patch M, and the output y, for each patch (i {I, d)), see Algorithm I We denote

---

The proof is in Appendix A. As a practical consequence, if we sample binary masks from a Bernoulli variable of parameter = 1/2, i.c. M, ~ B(p) for i E {I,..., d). and use the kernel defined in equation (5). we can assess not only the importance of each patch in the image but also the importance M...y =M. for clarity. In the next section, we discuss the kemelss & and I and show that we can obtain a valuable ANOVA-like orthogonal decomposition property for HSIC-based indices, allowing assess interactions between input variables.
3.3
Orthogonalisation of HSIC to enable evaluation of interactions
One question of interest in explainability is the measurement of the importance of specific group of variables. Indeed, it is notorious that neural networks are highly non-linear, and as it has been demonstrated in several works [14 11,, the effects of the groups of variables are far from being additive. Concretely, some areas of the image may only be important in interaction with other areas, affecting the output only when both areas are perturbed at the same time as we shall see in Section 4.4 (for instance, for mustaches of a puma).
Let {XI,..,,Xn, E X be set of n univariate random variables. For any subset A (4,, HAI C (1....,n) we denote XA = (Xi, aaaa) the vector of input variables with indices using Sobol indices based GSA, it is possible to measure the interactions between variables using ANOVA decomposition.
When
HSIC, the corresponding decomposition property (which is not ANOVA since HSIC does not measure the variance) can be stated follows:
Property 1 (Orthogonal decomposition property). The orthogonal decomposition property is fulfilled
if:
HSIC(x,y) = Σ
HSICA:
(3)
AC 1C(1....)
where each term HSICA given by HSICA > (-1)AAI-BIHS (-I)AA-)IIHIC((xE..)))
BCA
and HSIC(XB.y) y) defined as in equation
! with kernels I and KA-
In Appendix A, we introduce an example to illustrate why this property is necessary in order to properly assess the importance interactions. This property was lacking for dependence measure- based sensitivity analysis until the work of (9], which shows that when using HSIC, a specific choice of kernel can enable this decomposition. For any choice of and characteristic univariate kernel k, it is possible to obtain the orthogonal decomposition property by defining the input kernel AA such that
II + ko(x;,,))), s.t. ko(x,x') k(xx J [M ()PP()) (()(()))( BEA
k (a
(4)
These conditions can be stringent, especially the right one, which implies to compute integrals (analytically or empirically). It can be non trivial for continuous input distributions pa and classical kernel choices such as Radial Basis Function (RBF) of bandwidth o, k(x,=') exp(1Ix x =x'1l/2 2/o)/
This condition is alleviated when using discrete input variables of known densities, for which the integrals can be computed analytically. In particular, in this work, we rely on Proposition [
Proposition Let x; be Bernoulli variable of parameter p = 1.2 and 6(x = x') the Dirac kernel. Then the following kernel KA satisfies the decomposition property:
1 II ko(o,, s.t. ko(x, 8(x x²) 5
k x'
(5)
of the interactions between patches. It allows to go beyond classical attribution methods and reveal areas of the image that are only important in interaction with other areas, i.e. that affect the output only when both areas are perturbated at the same time. Concretely, for two image patches indexed by i and j. the interaction HSIC, Hixj. can be obtained with 9
Hg = HP (M. H H My
(6)
5

---

We insist on the fact that if the decomposition property is not valid, subtracting HM, and H M to H. M, does not ensure that we assess the importance of the interactions only. Traces of the independent importance of M, and M, may remain in the obtained metric. Some qualitative benefits of such a property are illustrated in Section 4.4 This decomposition holds for any choice of kernel I: y + G. Therefore, in the following, we use the RBF kernel, with the common practice of choosing the bandwidth the median of the output 8 20 48
3.4 Sample efficiency of HSIC estimator
Several types of metrics are classically used for sensitivity analysis. The most famous one, Sobol
indices 47 and its variants [6 [ classically require p² model evaluations [23] to reach an estimation error of O Recent design of experiments managed to reduce this requirement to p x (d + 2) 39 (Theorem 1). but with the increase complexity of state-of-the-art architectures and the high dimensionality of inputs (although mitigated by the use of d patches instead of all pixels), it can still be cumbersome. Despite this drawback, [11] uses Sobol indices to obtain explanations and still achieves execution time improvement compared to other state-of-the th-tte-arttttt attribution methods, which are even less efficient in terms of samples requirements.
HSIC is much less expensive to estimate than Sobol indices: for a same estimation error of O
p forward passes are needed instead of p (d + 2) (0 (Theorem 1). This allows using far fewer samples to obtain relevant explanations, thereby dramatically increasing the efficiency of the method compared to previous black-box approaches. This huge advantage empirically illustrated in Section where we demonstrate that our method defines new standard in terms of efficiency for black- box attribution methods. It even bridges the efficiency gap between black-box and white-box approaches.
4.2]
3.5
Implementation of the method
A summary of the whole attribution method is provided in Algorithm [ The computation of H."" is O(p²) but it is possible to vectorize it using any library optimized for tensor operations (e.g. tensorflow). As a result, the computation time of HP is negligible compared to that of the p forward passes. Furthermore, we implemented a sampling based on Latin Hypercube Sampling [30], a Quasi- Monte Carlo (QMC) method designed efficiently fill the input space Monte Carlo integration. Once the grid of HP is obtained, we use bilinear upsampling to be able to apply it to the image.
Algorithm 1 Explanations using HSIC-based sensitivity analysis attribution method
1: Inputs: d the dimension of the masks, p the number of forward pass, X an input image.
2: Sample p binary masks (M(), ...., M using LHS.
3: Compute the perturbed inputs (T(X, (()) )),., ((,,,(XXX)))) M(
4: Compute the predictions (1)(1) :.... (t, (P) ...
(f(T(X, (O,(XMM))) M())), f(T(X (()))
5: for E {1,.....d d) do
6: Compute HP using equation 2 and assign this value to the i-th patch of the input image.
4 Experiments
This section showcases the benefits of our approach compared to other attribution methods. These benefits are threefold. First, the computational cost of HSIC attribution method is significantly lower than previous state-of-the-art methods, even bridging the performance gap between black-box and white-box methods. Second, our method improves oftee-of-hhharn for several fidelity metrics, for blo as well as white-box methods. Finally, the orthogonal decomposition property of HSIC allows to go beyond usual attribution methods and assess interactions between image patches.
In Section 4.1 we compute explanations of the predictions in the ILSVRC-2011 [10 classification task (ImageNet), for four common architectures, namely MobileNet (40], ResNet50 [22], EfficientNet [53] and VGG16 44 Then, we compare those explanations with these of other tfate-of-the-ar black-box and boxte-box attribution methods in terms of fidelity and efficiency. In Section 4.2] we
investigate the convergence of our method by measuring its correlation with high sample estimator

---

Method
ResNet50
VGG16
EfficientNer
MobileNerV2
Exec. time (s)
Del. (4)
Saliency
43
0.158
0.120
0.091
0.113
0.360
White box
Grad.-Input
42
0.153
0.116
0.084
0.110
0.023
Integ--Gral
52
0.138
0.114
0.078
0.096
1.024
SmoothGrrad
45
0.127
0.128
0.094
0.088
0.063
GradCAM+
41
0.124
0.125
0.112
0.106
0.127
VarGrad 41
0.134
0.229
0.224
0.097
0.097
LIME
0.186
0.258
0.186
0.148
6.480
Kernel Shap 29
0.185
0.165
0.164
0.149
4.097
Black-box box-
RISE 332
0.114
0.106
0.113
0.115
8.427
Sobol 11
0.121
0.109
0.104
0.107
5.254
HP eff. (ours)
0.106
0.100
0.095
0.094
0.956
H, acc. (ours)
0.105
0.099
0.094
0.093
1.668
Ins. (1)
Saliency
0.357
0.286
0.224
0.246
0.360
White-box box
Grad.-Input
42
0.363
0.272
0.220
0.231
0.023
Integ.-Grad.
52
0.386
0.276
0.248
0,258
1.024
SmoothGrad
45
0.379
0.229
0.172
0.246
0.063
GradCAM++
41
0,497
0,413
0.316
0.387
0.127
VarGrad
41
0.527
0.241
0.222
0.399
0.097
LIME 37
0.472
0.273
0.223
0.384
6.480
Black-box
Kernel Shap
0.480
0.393
0.367
0,383
4.097
RISE 332
0.554
0.485
0.439
0,443
8.427
Sobol
0.370
0.313
0.309
0.331
5.254
HP eff. (ours)
0.470
0.387
0.357
0.381
0.956
H/ acc. (ours)
0.481
0.395
0.366
0.392
1.668
Table 1: Deletion and Insertion scores obtained 1,000 ImageNet validation set images (For Deletion, lower better and for Insertion, higher is better). The execution times are averaged over 100 explanations of ResNet50 predictions with an RTX Quadro 8000 GPU. The first and second best results are bolded and underlined.
and comparing with RISE 32 and Sobol [[]. the remaining sections, we conduct additional
experiments that show the versatility of method. In Section 4.3 we evaluate HSIC attribution
method to explain object detection on COCO dataset [28] with YOIOv4 [35]. We conclude the
experiments with Section 4.4 where showease the use of the HSIC orthogonal decomposition
property to assess interactions between image patches.
4.1 Fidelity of classification explanations
In this section, we evaluate the fidelity of the explanations with three fidelity metrics. The first, Deletion [32), assumes that the more faithful an explanation is, the quicker the prediction score should drop when pixels that are considered important are shut down. The second one, Insertion [32], instead adds pixels on baseline image, starting with pixels that are associated with the highest importance scores of the explanation. Finally, jFiieliity 4 creates random pixels subsets which are assigned baseline value and measure the correlation between the drop in the score and the importance of the explanation. Those metrics are further described in Appendix
In Table we report the results of several different attribution methods for explaining the classification of MobileNet [40], ResNet50 (22), EfficientNet [53] and VGG16 44] 1000 images sampled from the ImageNet validation dataset. The models used for the experiments have been accessed from tensorflow [ with the keras API (6]. We introduce two variants of our method, H." eff. and 7. acc. The words "eff" and "acc" stand for efficient and accurate because we use 764 and = 1536 samples, respectively. We use our method with a grid size 7 (d 49). evaluate the different methods, we use the Xplique [12. library dedicated to explainability. For black-box and white-box methods, we bold the best result and underline the second. When the differences between some methods not statistically significant, highlight both. Note that for μFidelity, the estimation

---

variance is high (typically about 20%), so we only use the bold notation and leave the Table in Appendix B. The exact error bars are also left in the Appendix to make the presentation lighter.
For the Deletion metric, our method obtains the best results among the tested black-box methods for all the architectures in both its efficiency and accurate variants. Except for EfficientNet, we even beat all tested white-box methods. RISE is still the best of black-box methods for the Insertion metric, but the accurate variant is systematically second. Besides, our methods are among the best of both black-box and white-box methods.
While HSIC is systematically better in Deletion, This could be explained by how these metrics are constructed. Deletion and Insertion metrics consist in measuring Area Under the Curve (AUC) of scores that respectively decrease and increase when deleting and adding patches, starting from a haseline image (see Appendix F for a detailed definition). Since Deletion measures drop in the score starting from the original image, the faster the score drops, the better the metric. Hence, Deletion will favor methods that sharply identify important regions. On the contrary, since Insertion starts from an arbitrary baseline image, if the explanation map is more spread out, more relevant secondary information will be added, so the score will be better, As we can see in the maps of Appendix C. RISE saliency maps are way more spread out than HSIC's, which are sharper. It may explain why RISE is better in the Insertion benchmark and why HSIC attribution method dominates the Deletion benchmark. We provide additional quantitative examples to illustrate this link in Appendix F. Note that even if RISE dominates Insertion, it is far behind in Deletion. This is not the case for HSIC, which is still competitive in Insertion while dominating Deletion.
note that RISE overshadows it in Insertion.
These results, such, already satisfactory. But it goes even further: obtained these results with far fewer forward passes than other state-of-the-art black-box attribution methods. With the efficient variants, competitive results are obtained more than times faster than RISE, the current standard of black-box attribution methods. It improves on Sobol, a recent and promising attribution method that was already branded as more efficient, by factor 5. The time improvement factors for the accurate variant of our method are still very appealing (5 and 3). We even beat the execution time of Integrated Gradients white-box method [52]. popular and successful white-bor box method. The efficiency of HSIC attribution method is investigated more thoroughly in the next section.
4.2 Estimator efficiency
The advantage of black-box attribution methods lies in providing explanations without access to the model's internal state or the gradients. However, this advantage comes cost since many forward passes are needed to obtain meaningful explana- tions. This cost all the more constraining since recent architectures are increasingly heavy in terms of computational time.
0.8
Rise
1 1- Spearman's
Sobol
0.6
Hsic
0.4
0.2
1000
2000
3000
4000
5000
6000
Forwards
Therefore, it is critical for such attribution methods to as few forward passes possible. Results reported in Section 1 attest that our approach based on HP2" shines in that regard, and we refer to this section for more comments. It motivates us study the efficiency of our method further. To that end, we compute an "asymptotical"" explanation with 13, 000 forward passes, for HSIC, Sobol and RISE attribution methods, on 100 images of ImageNet validation set.
Figure 2: Spearman rank correlation of HSIC, Sobol and RISE attribution methods explanations on 100 Ima- geNet validation images with an "asymptotical" expla- nation based on 13, 000 samples.
We apply the three methods on EfficientNet with d= 7 x masks and image patches, like in [32 and [II]. We then compute explanations for increasing number of forward passes and compare the obtained explanation with the baseline "asymptotical" explanation. We use Spearman rank This experiment allows
correlation 49 like theoretically and empirically argued in 19
54 13
'This explanation is not theoretically asymptotical (hence the quotation marks), but we use this designation because it is obtained with very high number of forward passes

---

comparing the convergence speed of our method with RISE and Sobol. The curves are plotted in Figure and show that our method, HSIC converges much faster than RISE and Sobol.
4.3 Explanation of object detection
Explaining model's predictions is more challenging for object detection than for image classification. Indeed, recent object detection models usually predict three pieces information: localization (bounding box corners), objectness score (probability that bounding box contains object of any class), classification information (probability each different possible class). Recently, has been demonstrated that possible a score aggregating for the previous information. for localization, cosine similarity for the class probability, and focus on high objectness areas, As result, they can use RISE to explain the object detection using this score as the output of the model.
attribution methods explain object detection constructing (33 the authors combine intersection over union
In this section, test method for explaining the object detections of YOLOv4 35 COCO dataset [28] compared to the approach presented in [331, D-RISE. We also compare the explanations with these of Kernel Shap [29]. another black- box attribution method. The explanations for 1, 000 validation images are evaluated with the Deletion, Insertion, and (Fidelltyy metrics. This experiment
time-consuming, use HP eff. and 5000 samples for D-RISE and Kernel Shap.
Method
Delction (1)
Insertion (t)
/Fidelity (t)
Exec. time (s)
D-RISE 133
0.074
0.634
0.442
155
Kernel Shap. 129
0.070
0.646
0.476
192
Hd (ours)
0.088
0.658
0.568
34
Table 2: Fidelity metrics obtained from explanations of YOLOv4 object detections on 1, 000 images of COCO validation data set. Execution times are averaged on the 1, 000 images on RTX 3080 GPUs.
Even if our method is not the best for Deletion, is for Insertion and μFFidelity, and more importantly, is 5 and 6 times faster than D-RISE and Kernel Shap. Figure displays visualizations of object detection explanations. While the first images show standard detection explanation, the rightmost one is more interesting since it emphasizes an error the object detector. The model identifies a zebra
and method manages to explain this error by emphasizing the cat at the bottom right corner the image. Note that we did not obtain such an explanation with D-RISE, even with a high sample number and different grid sizes visualizations be found in Appendix C).
Figure Visualisations of object detection explanations. The first three images show standard explanations, while the bottom right explains misclassification. The zebra has been detected as cat, and our method manages to explain why by emphasizing the cat at the bottom right corner.
4.4 Finding spacial interactions in the model
Usual attribution methods provide explanations in the form of heat maps that assign each pixel (or patch) an importance score. However, the scope of such explanations is limited since the reason for prediction may not be explained only by the single importance of independent patches. In [II, the authors use Sobol total indices that account for the importance of patch in interaction with other patches, but they cannot localize the interactions. Thanks to its orthogonal decomposition property, our HSIC-based attribution method is able not only to assess the importance of each patch, but also the importance of interactions between specific patches by computing the HSIC of the joint patches

---

and subtracting the contribution of each patch taken independently is then possible to identify regions of the image that affect the output only when both areas are perturbated jointly.
H!
H
Figure Upper row: Hº, estimated HSIC for each image patch. Bottom row: highest H2x; between images patches. For the classification of the puma, the eye forehead is the most important independent patch, but the right and left mustaches' interactions are even more important.
We illustrate this property in Figure 4 For each image, we computed all the possible interactions between patches and reported the most important ones. Note that not all images exhibit significant interactions, so performed qualitative selection for pedagogical purposes. On the upper row, we plot usual heatmaps that traduce the importance of each patch taken independently. On the bottom row, important interactions are represented in red. We can see that the middle part of the snake body is not the only important element in the picture, that one part of the mountain interacts with one of the skiers, so do the mustaches of the puma and two corners of the roof. Note that for each image, the maximum values of HP are 40.6, 11 4, 8.2 and 18.8 and the maximum values of H2x are 19.6, 6.6, 9.2 and 6.3 respectively. Thanks to the orthogonal decomposition property, these metrics can be compared and we can deduce that some interactions are as significant as some important independent patches. For the image with a puma, the interactions between the mustaches are even more important than the eye / forehead for identifying the animal (Hf 9.2 when and j are the right and left mustaches and H 8.2 when i is the eye forehead).
Conclusion
We have introduced new attribution method based on a dependence measure, HillbertSSchmic Independence Criterion, which leverages representation capabilities of Reproducing Kernel Hilbert Spaces, thus being able to capture complex information. This attribution method black-box, so it is applicable even when the implementation of the neural network to explain is not available. Nonetheless, it alleviates the computational burden of traditional black-box methods, improving on the sfate-of-the-art of both black-box and white-box attribution methods while being closer to the latter than the former in terms of efficiency. In addition, we showed how the rich framework of RKHS could be used to assess and localize interactions between pairs of patches of the input image that are relevant for explaining the output. We hope that the introduced framework will open up research avenues for attribution methods beyond traditional pixel-wise or patch-wise explanations.
Acknowledgements
This work has benefited from the AI Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future- PIA3" program under the Grant agreement ANR-I9-P3IA-00044 The authors gratefully acknowledge the support of the DEEL project Part of this work was performed using HPC resources from CALMIP (Grant 2022-P22034). Additional support for computing hardware provided by Google via the TensorFlow Research Cloud (TFRC) program and by the Center for Computation and Visualization (CCV) at Brown University (NIH grant S100D025181)
With decomposition property, is also possible to obtain HSIC "total" indices, like Sobol, but not bring significant qualitative or quantitative advantages. https: / //www/wwww//c// deel. ai/
10

---

References
[1] M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Joze- fowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, I. Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Va- sudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org.
[2] J. Adebayo, J. Gilmer, M. Muelly. I. Goodfellow, M. Hardt, and B. Kim. Sanity checks for saliency maps. Advances in Neural Information Processing Systems (NeurlPS), 2018.
[3] D. Baehrens, T. Schroeter, S. Harmeling, M. Kawanabe, K. Hansen, and K.-R. Müller. How to explain individual classification decisions. The Journal of Machine Learning Research,
11:1803-1831, 2010.
[4] U. Bhatt, A. Weller, and J. M. F. Moura. Evaluating and aggregating feature-based model explanations. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2020.
[5] E. Borgonovo. A new uncertainty importance measure. Reliability Engineering & System Safety, 92(6):771 -844, 2007.
[6] F. Chollet et al. Keras. https://keres io. 2015.
[7] R. Cukier, C. Fortuin, K. E. Shuler, A. Petschek, and J. Schaibly. Study of the sensitivity of coupled reaction systems to uncertainties in rate coefficients. theory. The Journal of chemical physics, 59(8):8873-387 1973.
[8] S. Da Veiga. Global sensitivity analysis with dependence measures. Journal of Statistical Computation and Simulation, 85(7):1283-1305, May 2015.
[9] Da Veiga. Kernel-based anova decomposition and shapley effects appliictonoiioiiinnnn to global sensitivity analysis. arXiv preprint arXiv:2 101 055477, 2021.
[10] J. Deng, W. Dong, R. Socher, L.-J. Li. K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
[11] T. Fel, R. Cadene, M. Chalvidal, M. Cord, D. Vigouroux, and T. Serre. Look at the Variance! Efficient Black-box Explanations with Sobol-based Sensitivity Analysis. 211.:21 [cs], Nov. 2021.
[12] T. Fel, L. Hervier, D. Vigouroux, A. Poche, J. Plakoo, R. Cadene, M. Chalvidal, J. Colin, T. Boissin, L. Bethune, A. Picard, C. Nicodeme, L. Gardes, G. Flandin, and T. Serre. Xplique: A deep learning explainability toolbox. Workshop on Explainable Artificial Intelligence for Computer Vision (CVPR), 2022.
[13] Fel and D. Vigouroux. Representativity and consistency measures for deep neural network explanations. Proceedings of the IEEE Winter Conference on Applications of Computer Vision (WACV), 2022.
[14] G. Ferrettini, E. Escriva, J. Aligon, J.-B. Excoffier, and C. Soulé-Dupuy. Coalitional strategies for efficient individual prediction explanation. Information Systems Frontiers, pages 1-27, 2021.
[15) R. C. Fong and A. Vedaldi. Interpretable explanations of black boxes by meaningful perturbation. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
[16] J.-C. Fort, T. Klein, and N. Rachdi. New sensitivity analysis subordinated a contrast. Communications in Statistics Theory and Methods, 45(15):4349-4366 2016.
[17] K. Fukumizu, F. R. Bach, and M. I. Jordan. Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces. Mach. Learn. Res., 5:73-99, dec 2004.
[18] S. Ghalebikesabi, L. Minasins, K. DiazOrdaz, and C. C. Holmes. On locality of local explanation models. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[19] A. Ghorbani, A. Abid, and Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), 2017.

---

[20] A. Gretton, O. Bousquet, A. Smola, and B. Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. In Proceedings of the 16th International Conference on Algorithmic Learning Theory, 05, page 63-77, Berlin, Heidelberg, 2005. Springer- Verlag.
[21] A. Gretton, R. Herbrich, A. Smola, O. Bousquet, and B. Scholkopf. Kernel methods for measuring independence. Journal of Machine Learning Research, 6(70):2055-2129, 2005.
[22] K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. In Proceedings of the IEEE European Conference on Computer Vision (ECCV), 2016.
[23] T. Homma and A. Saltelli. Importance measures in global sensitivity analysis of nonlinear models. Reliability Engineering & System Safety, 52(1):1-17, 1996.
[24] B. Tooss and P. Lemaître. A review on global sensitivity analysis methods. Uncertainty management in Simulation-Optimization of Complex Systems: Algorithms and Applications, 2015.
[25] A. Kapishnikov, T. Bolukbasi, F. Viégas, and M. Terry. Xrai: Better attributions through regions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
[26] B. Kim, M. Wattenberg, J. Gilmer, C. Cai, Wexler, F. Viegas, et al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (tcav). In International conference on machine learning. Proceedings of the International Conference on Machine Learning (ICML), 2018.
[27] P. W. Koh and P. Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1894, PMLR, 2017.
[28] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick. Microsoft coco: Common objects in context. In Proceedings of the IEEE European Conference on Computer Vision (ECCV). Springer, 2014.
[29] S. M. Lundberg and S.-I. Lee. A unified approach to interpreting model predictions. In Proceedings the 3 International Conference on Neural Information Processing Systems, NIPS' 17, page 4768-4777, 4777, Red Hook, NY, USA, 2017. Curran Associates Inc.
[30] M. D. McKay. Latin hypercube sampling as tool in uncertainty analysis of computer models. In Proceedings of the 24th Conference on Winter Simulation, WSC '92, page 557-564, New York, NY, USA, 1992. Association for Computing Machinery.
[31] C. Olah, A. Mordvintsev, and L. Schubert. Feature visualization. Distill, 2017.
[32] V. Petsiuk, A. Das, and K. Saenko. Rise: Randomized input sampling for explanation of black-box models. In Proceedings of the British Machine Vision Conference (BMVC), 2018.
[33] V. Petsiuk, R. Jain, V. Manjunatha, V. I. Morariu, A. Mehra, V. Ordonez, and K. Saenko. Black-box explanation of object detectors via saliency maps. 202/ IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1 1438-114447 2021.
[34] S. Razavi, A. Jakeman, A. Saltelli, C. Pricur, B. looss, E. Borgonovo, E. Plischke, S. Lo Piano, T. Iwanaga, W. Becker, S. Tarantola, J. H. Guillaume, J. Jakeman, H. Gupta, N. Melillo, G. Ra- bitti, V. Chabridon, Q. Duan, X. Sun, S. Smith, R. Sheikholeslami, N. Hosseini, M. Asadzadeh, A. Puy, S. Kucherenko, and H. R. Maier. The future of sensitivity analysis: An essential discipline for systems modeling and policy support. Environmental Modelling & &Software, 137:104954, 2021.
[35] J. Redmon and A. Farhadi. Yolo9000: better, faster, stronger. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7263-7271, 2017.
[36] M. T. Ribeiro, S. Singh, and C. Guestrin. "why should trust you?" explaining the predictions of any classifier. In Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining, 2016.
[37] M. T. Ribeiro, S. Singh, and C. Guestrin. "why should i trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, page 1 1135-1144, New York, NY, USA, 2016. Association for Computing Machinery.
[38] A. Ross, H. Lakkaraju, and O. Bastani. Learning models for actionable recourse, Advances in Neural Information Processing Systems (NeurIPS), 2021.
12

---

[39] A. Saltelli. Making best use of model evaluations to compute sensitivity indices. Computer Physics Communications, 145(2):280-295 297, May 2002.
[40] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
[41] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra. Grad-cam: Visual explanations from deep networks via gradient- gradient-based localization. In Proceedings of the IEEE International Conference Computer Vision (ICCV), 2017.
[42] A. Shrikumar, P. Greenside, A. Shcherbina, and A. Kundaje. Not just a black box: Learning important features through propagating activation differences. arXiv preprint arXiv:1605.0177 1605.01713, 2016.
[43] K. Simonyan, A. Vedaldi, and A. Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Workshop Proceedings of the International Conference on Learning Representations (ICLR), 2014.
[44] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of the International Conference Learning Representations (ICLR), 2015.
[45] D. Smilkov, N. Thorat, B. Kim, F. Viégas, and M. Wattenberg. Smoothgrad: removing noise by adding noise. In Workshop Visualization for Deep Learning, ICML, 2017.
[46] I. M. Sobol. Sensitivity analysis for non-linear mathematical models. Mathematical modelling and computational experiment, 1:407-414 1993.
[47] I. M. Sobol. Sensitivity estimates for nonlinear mathematical models. MMCE, 4(1):407-414, 1993.
[48] A. Spagnol, R. L. Riche, and S. Da Veiga. Global sensitivity analysis for optimization with variable selection. SIAM/ASA J. Uncertain. Quantification, 7:417-443, 2018.
[49] C. Spearman. The proof and measurement of association between two things. American Journal of Psychology, 1904.
[50] J. T. Springenherg, A. Dosovitskiy, T. Brox, and M. Riedmiller. Striving for simplicity: The all convolutional net. In Workshop Proceedings of the International Conference on Learning Representations (ICLR), 2014.
[51] B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R. Lanckriet. Hilbert space embeddings and metries on probability measures. J. Mach. Learn. Res., 11:1517-1561, aug 2010.
[52] M. Sundararajan, A. Taly, and Q. Yan. Axiomatic attribution for deep networks. In Proceedings of the International Conference on Machine Learning (ICML), 2017.
[53] M. Tan and Q Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In Proceedings of the International Conference on Machine Learning (ICML). PMLR, 2019.
[54] R. Tomsett, D. Harborne, Chakraborty, P. Gurram, and A. Preece. Sanity checks for saliency metrics. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2019.
[55] M. D. Zeiler and R. Fergus. Visualizing and understanding convolutional networks. In Proceed- ings of the IEEE European Conference on Computer Vision (ECCV), 2014.
[56] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations stem from the complexity of computing HSIC mentioned Sections 3.2 and 3.4. We provided vectorized implementation to alleviate this limitation.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] J There is no negative societal impact specific to this work that is not shared with common XAI techniques.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Appendix A
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] URL is found in page 1.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] Error bars have been computed but left in the Appendix to make the presentation of Tables and 2 lighter. Nonetheless, they taken into account in the tables and the comments to assess the statistical significance of results (d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "n47yNBtYXI", "reviewer": "Reviewer_dSej", "summary": "Summary\nThe paper is motivated to improve the explainability of vision inference results. Specifically, they propose to measure the dependence between certain perturbation of regions of the input images and the actual labels in RKHSs. This helps to understand how much independent $M_i$ is from $y$, so that the approach may determine how important each perturbed fraction of the image are associated with the final inference results. The approach then is able to locate the pivotal input parts that most possible has led to the final inference. Empirical results validate that, in certain scenarios, the proposed method provides better explanation in comparison to current SOTA methods. \n", "questions": "1. How the decomposition property is related to the actual explainability of the proposed method (See details above in the weakness).\n2. How the algorithm flow is connected to the eventual implementation of pixelwise explanation of the input image (See comments above regarding the algorithm flow)?  ", "limitations": "Yes, the authors have discussed the limitations. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strength:\n\nThe method proposes to introduce the HSIC metric in order to detect the dependence between certain fraction of the input and the actual label. The approach correspondingly gives analysis in why measuring such dependence help better explain the inference result through joint interactions among  different patches, a perspective that other SOTA methods haven’t examined. Empirical results show that the proposed method can better locate the essential parts of the image.  \n\n* Weakness:\n\nI am not quite sure how \"Proposition 1\", i.e., the decomposition property is related to the actual explainability of the proposed method. Is it a condition to enable the incorporation of HSIC metric in this specific scenario? It seems to me there is some gap here between the analysis and the actual motivation to improve explanation. In other words, why “it does not ensure that we assess the importance of the interactions only (line 199-200)” if the decomposition property does not hold? And how this links to the eventual inference?\n\nThe description of the algorithm could be further clarified. The current algorithm flow is a bit vague in how we can obtain the eventual explanation and to diagnose the model. Take for example, how do we link to the eventual pixel level highlights of the image parts (explanation like image Figure 3) through the construction of Eq.(2)?\n\n\n* Minor issues: \n1. There are some presentation issues in technical details:\nEq. (2), the brackets of the trace operation are missing. \n\n2. There are some minor grammar issues that could be further improved. Here are some examples. \n  Line 141-142 This sentence has grammar issues and needs to be rephrased; \n  Line 177 Let ${x_1…X_n} $ a set of -> Let ${x_1…X_n}$ be a set of;\n  Line 190 Let a Bernoulli Variable -> Let x be a Bernoulli variable; ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jg052CJhnFs", "reviewer": "Reviewer_QhZj", "summary": "The paper presents a new method for obtaining saliency maps that can explain a deep image classifier's predictions. The method is \"black box\" in the sense that it only relies on the ability to evaluate a model's predictions (obtain the predicted label \"y\" for any desired input \"x\"). It does not require any knowledge or access of the internals of the prediction function (e.g. the ability to compute gradients) as \"white box\" methods would.\n\nThe proposed method uses the Hilbert-Schmidt Independence Criterion (HSIC).\nIt assumes the selection of two kernel functions: \"k\" defines the similarity between two images (x and x') and \"l\" defines the similarity between two labels (y and y'). These kernels have associated feature embeddings. \n\nGiven p possible masks that perturb an original image x, and the associated outputs, the HSIC concretely computes (see Eq 2) the norm of the cross-covariance between the embeddings of perturbed images and embeddings of their predictions. The scalar quantity HSIC can be computed for each of the patches in an image.\n\nThey further describe how *interactions* between two patches in the same image can be given an HSIC score (Eq 5), which allows higher-order reasoning about importance (e.g. in an image of a face, perhaps each eye individually is not so important but the combination of the two eyes is). \n\nOverall, the claimed contributions of the proposed approach are:\n- 1) a new method based on HSIC\n- 2) a derivation that shows an orthogonal decomposition property exists for a specific kernel\n- 3) experiments showing the method is useful on ImageNet in terms of quality and speed\n- 4) demonstration of versatility on object detection and in pairwise patch interactions\n", "questions": "\n### Q1: What was done to ensure fair comparison of timings in Table 1?\n\nHow many perturbations p are Sobol or RISE using? How was this selected?\nShouldn't an \"efficient\" and \"accurate\" version of both methods be also possible?\n\n\n### Q2: In Table 2, why use 5000 samples for D-RISE but fewer for your method?\n\nAgain, seems like this choice will impact the speed of baselines.\nHow can we be sure this choice is fair?\n\n### Q3: What does it mean for a method to score better on Insertion than Deletion?\n\nRISE is notably better on that Insertion metric than others. \nWhat's the intuition here? Are there ways to visually understand why that is?\n\n\nMinor Presentation Issues\n-------------------------\nPlease adjust for revision, but no need to discuss in rebuttal \n\n- Lines 25-28 read awkwardly, consider revising for flow\n- Fig 1 gives impression that x has a distribution, but the distribution is over binary mask, right?\n- Lines 46-49: A distribution over what exactly? Over perturbed values? Over pixels observed in a region/patch?\n- Lines 123-126: Why use the symbol x twice (italicized and not)? Please redefine\n- Line 171: \"networkss\" typo", "limitations": "Limitations\n-----------\nThere are likely a number of choices that could be very sensitive to overall performance that are under-explored here:\n- number of patches used / size of the 'grid'\n- choice of the kernel functions (both \"k\" and \"l\")\n- choice of the lengthscale of the RBF kernel (maybe median is OK, but could you improve performance by optimizing?)\n\nAs a blackbox method, there may be cases where white box methods are possible and preferred, but this is adequately addressed by the paper.\n\nThe discussion of negative societal impact was a bit light, though unobjectionable (I agree that for a new technical method like this, it will share the same possible for misuse as related methods like Sobol or RISE). ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths\n---------\n+ Speed ups of 5-8x over previous black-box attribution methods (Sobol and RISE) seem useful\n+ The RKHS foundations of the proposed methods are technically interesting\n+ Focus on pairwise interactions between patches is useful\n+ Experiments compare to a variety of \"state of the art\" white and black box methods\n\nWeaknesses\n----------\n- W1: Technical communication could be better, some key details are difficult to parse [see below]\n- W2: Orthogonal decomposition property in particular is not well explained or justified\n- W3: Qualitative visual examples are only shown for the presented method; difficult to assess relative value over baselines\n- W4: Some of the visual explanations are puzzling: Why is a Puma's mouth more important than eyes? Why is only the number 11 important on the clock?\n\n\n### W1: Technical communication issues\n\nIn Sec 3.1, there are several issues:\n\n1) the definition of \"n\" versus \"d\" is not clearly established.\nIt is not clear how the elementwise product between x (a vector of size n) and M (a vector of size d) is well-defined. \nIt is not clear if \"patches\" or individual pixels are used.\n\n2) the way that \"baseline\" value \\mu is defined is not clear\nIs this value the same for every pixel in image? How is it defined? is it learned?\n\nIn Sec 3.2, further issues:\n\n3) It is difficult to do a dimensionality analysis of Eq 2 \nLooking at Eq 2, the trace of a product of pxp matrices should be a scalar.\nBut surely the HSIC is computed for each pixel/patch in the image, right?\nThis equation's presentation should be modified to more clearly indicate how you get a scalar for each pixel/patch of the saliency \"heatmap\" \n\n\n4) Using symbol \"x\" here as a general random variable collides with readers' previous understanding of x as the input image. \nI think you want to distinguish the two.... there isn't a distribution over the input image, instead there's a distribution over *perturbations* of this image.\nFor example, in Eq 4 you need x to be discrete, but this collides with reader's already formed assumption that x is a pixel.\n\n### W2: Orthogonal decomposition is not clear\n\nI understand at a high level that assessing the interaction between two patches in the image is important and it is not additive. But the technical details of the proposed \"orthogonal decomposition\" were not clear to me.\n\nLines 176-182 were particularly hard to read for me.\nWhy is the \"sum of indices\" equal to one?\nWhy does this imply something beneficial?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MxOtw2o5BfL", "reviewer": "Reviewer_eNpV", "summary": "After rebuttal: The authors answered my questions. The ideas are interesting, but the improvement of the state-of-the-art is perhaps not that significant and the presentation could be improved (which the authors can probably do if accepted). I increased my rating to weak accept.\n\n---\n\n\nThe authors propose a new attribution method based on the Hilbert-Schmidt Independence Criterion. The paper explains the technical background, defines and motivates the attribution method and proposes a simple sampling algorithm to approximate it. The authors also discuss how the new method can be better suited for capturing the joint effects of features. In the experiments, the paper evaluates 'fidelity', 'efficiency' and finding spatial interactions. ", "questions": "The main points from my review above that could change my opinion are the following (please correct me if I am wrong):\n\n1) The main motivation for the particular choice of the attribution method seems to be that it features a decomposition property that allows separting the joint effect of features from their individual effects. While this is theoretically interesting, it could be discussed and evaluated in more detail if it gives much better explanations than simply considering pairs of features that could then be evaluated by a standard method. \n\n2) Previous results from the literature seem to suggest that the estimator applied here needs fewer samples. However, the discussion is somewhat disconnected from the actual algorithm and it would be good to be more explicit about which guarantees (please refer to the theorem number) from which paper can be applied here and why.  \n\n3a) Table 1 shows Deletion and Insertion results, but muFidelity seems to be missing. The proposed approach works best with respect to Deletion, but not with respect to Insertion, which is dominated by RISE. This indicates that there could be a tradeoff between Insetion and Deletion similar to Precision and Recall. Perhaps it's just a coincidence, but it would be good to discuss why the proposed method does better with respect to one measure, but not with respect to the other. \n\n3b) I am also missing muFidelity in the table.\n\n4) The runtime experiment is probably supposed to illustrate the convergence speed. While the graph intuitively indicates faster convergence, it should be discussed in more detail what it actually shows and why the experiment has been set up in this way. In particular, what is the \"baseline asymptotical explanation\"?\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea seems novel and is relevant for NeurIPS. The main motivation for the particular choice of the attribution method seems to be that it features a decomposition property that allows separting the joint effect of features from their individual effects. While this is theoretically interesting, it could be discussed and evaluated in more detail if it gives much better explanations than simply considering pairs of features that could then be evaluated by a standard method.  To get an 'efficient method' the authors use a sampling algorithm. Previous results from the literature seem to suggest that the estimator applied here needs fewer samples. However, the discussion is somewhat disconnected from the actual algorithm and it would be good to be more explicit about which guarantees (please refer to the theorem number) from which paper can be applied here and why.  \n\nThe 'fidelity' evaluation is based on the measures Deletion, Insertion and muFidelity. They are explained in the appendix, which should be mentioned in the main part (I almost missed it). I suppose that Insertion is based on AUC symmetrical to Deletion, but it would be good to make this explicit). Table 1 shows Deletion and Insertion results, but muFidelity seems to be missing. The proposed approach works best with respect to Deletion, but not with respect to Insertion, which is dominated by RISE. This indicates that there could be a tradeoff between Insetion and Deletion similar to Precision and Recall. Perhaps it's just a coincidence, but it would be good to discuss why the proposed method does better with respect to one measure, but not with respect to the other. I am also missing muFidelity in the table. The runtime experiment is probably supposed to illustrate the convergence speed. While the graph intuitively indicates faster convergence, it should be discussed in more detail what it actually shows and why the experiment has been set up in this way. In particular, what is the \"baseline asymptotical explanation\"? Interactions are investigated by means of examples. The picked examples are intuitive. While such an evaluation by example seems always a bit weak, it does make sense that the joint effect of features can be more important than their individual effects.\n\nOverall, the paper does not contain ground-breaking results, but shows improvements in some areas (Deletion, Runtime). There are some interesting ideas in the paper, but they should be discussed and evaluated in more detail in my opinion (e.g. feature interaction, runtime and approximation error guarantees). The code is available for reproducibility, although I did not have time to check it. At the moment, I consider this as a borderline paper.\n\nSome comments\n\n- I find the black-box/white-box distinction in this paper confusing. White-box sometimes refers to a model that is 'interpretable', while black-box refers to one that is not. Here, white-box just means that the model can be accessed, while black-box means that it cannot. Why not simply call it available/unavailable to avoid confusion? I am also not convinced that availability is really an issue in many cases. Of course, an end-user does not have access to the model, but in many applications, the explanation module should probably be part of the user interface. I may be wrong, and some concrete examples could convince me otherwise. \n\n- Parts of the paper are very vague and convoluted. For example, lines 37-41 would be perhaps be easier to understand when just writing that perturbation methods rely on sampling and evaluating a sample can be expensive for recent neural network architectures that are growing larger.\n\n- line 31: the paper refers to [18] for a statement about gradients, but the paper does not really seem to discuss the issue. Please clarify or delete.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "J4uRUY0SjSF", "reviewer": "Reviewer_Zkzj", "summary": "The authors present a black-box attribution method based on Hilbert-Schmidt Independence Criterion. By leveraging representation capabilities of RKHS, this method provides a dependence measure to capture more diverse information than traditional variance-based indices and does so more efficiently. This method randomly perturbs an input image in multiple regions at a time (similar to LIME, RISE, and Sobol) to identify higher-order interactions between patches. They demonstrate it on various applications including image classification and object detection tasks.  The authors quantify the efficacy of explanations using Deletion, Insertion, and uFidelity. The results show that their method is largely better than other attribution methods across a variety of neural networks, old and new. ", "questions": "- The difference in explanations between Hi and Hixj is surprising that they are different. Shouldn't attributions from each image patch overlap with the attributions from interactions? Second-order effects are usually smaller. \n- Is there an XOR situation that could highlight that Hixj is able to uncover unique interactions that would be missed by attributions of individual patches? \n- Is there a way to quantify expected interactions? ", "limitations": "The challenge is that quantitative comparisons is difficult without ground truth. The Deletion, Insertion and uFidelity metrics provide a quantitative way to compare methods but they are all flawed. Moreover, these explanations provided by these methods are quite limited as regions are highlighted. It is not clear what about those regions, i.e. edges, textures, shapes, are important. A section on limitations of attribution maps should be provided as the language term explanation used in this paper is a bit loose. Notwithstanding, it has the makings of a valuable contribution for attribution-based interpretations with clear benefits compared to existing methods. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- good job of placing research in broader field\n- the theory is well founded and the implementation algorithm is clear\n- the experiments and results are clear\n- thorough exploration across popular attribution methods and across various architectures with better performance and faster execution times\n\nWeakness\n- The spatial interactions in the model section is anecdotal. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept