Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Summary
The 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. 

strengths_and_weaknesses: * Strength:

The 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.  

* Weakness:

I 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?

The 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)?


* Minor issues: 
1. There are some presentation issues in technical details:
Eq. (2), the brackets of the trace operation are missing. 

2. There are some minor grammar issues that could be further improved. Here are some examples. 
  Line 141-142 This sentence has grammar issues and needs to be rephrased; 
  Line 177 Let ${x_1…X_n} $ a set of -> Let ${x_1…X_n}$ be a set of;
  Line 190 Let a Bernoulli Variable -> Let x be a Bernoulli variable; 
questions: 1. How the decomposition property is related to the actual explainability of the proposed method (See details above in the weakness).
2. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths
- good job of placing research in broader field
- the theory is well founded and the implementation algorithm is clear
- the experiments and results are clear
- thorough exploration across popular attribution methods and across various architectures with better performance and faster execution times

Weakness
- The spatial interactions in the model section is anecdotal. 
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. 
- 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? 
- 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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.

The proposed method uses the Hilbert-Schmidt Independence Criterion (HSIC).
It 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. 

Given 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.

They 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). 

Overall, the claimed contributions of the proposed approach are:
- 1) a new method based on HSIC
- 2) a derivation that shows an orthogonal decomposition property exists for a specific kernel
- 3) experiments showing the method is useful on ImageNet in terms of quality and speed
- 4) demonstration of versatility on object detection and in pairwise patch interactions

strengths_and_weaknesses: 
Strengths
---------
+ Speed ups of 5-8x over previous black-box attribution methods (Sobol and RISE) seem useful
+ The RKHS foundations of the proposed methods are technically interesting
+ Focus on pairwise interactions between patches is useful
+ Experiments compare to a variety of "state of the art" white and black box methods

Weaknesses
----------
- W1: Technical communication could be better, some key details are difficult to parse [see below]
- W2: Orthogonal decomposition property in particular is not well explained or justified
- W3: Qualitative visual examples are only shown for the presented method; difficult to assess relative value over baselines
- 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?


### W1: Technical communication issues

In Sec 3.1, there are several issues:

1) the definition of "n" versus "d" is not clearly established.
It is not clear how the elementwise product between x (a vector of size n) and M (a vector of size d) is well-defined. 
It is not clear if "patches" or individual pixels are used.

2) the way that "baseline" value \mu is defined is not clear
Is this value the same for every pixel in image? How is it defined? is it learned?

In Sec 3.2, further issues:

3) It is difficult to do a dimensionality analysis of Eq 2 
Looking at Eq 2, the trace of a product of pxp matrices should be a scalar.
But surely the HSIC is computed for each pixel/patch in the image, right?
This equation's presentation should be modified to more clearly indicate how you get a scalar for each pixel/patch of the saliency "heatmap" 


4) Using symbol "x" here as a general random variable collides with readers' previous understanding of x as the input image. 
I 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.
For example, in Eq 4 you need x to be discrete, but this collides with reader's already formed assumption that x is a pixel.

### W2: Orthogonal decomposition is not clear

I 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.

Lines 176-182 were particularly hard to read for me.
Why is the "sum of indices" equal to one?
Why does this imply something beneficial?
questions: 
### Q1: What was done to ensure fair comparison of timings in Table 1?

How many perturbations p are Sobol or RISE using? How was this selected?
Shouldn't an "efficient" and "accurate" version of both methods be also possible?


### Q2: In Table 2, why use 5000 samples for D-RISE but fewer for your method?

Again, seems like this choice will impact the speed of baselines.
How can we be sure this choice is fair?

### Q3: What does it mean for a method to score better on Insertion than Deletion?

RISE is notably better on that Insertion metric than others. 
What's the intuition here? Are there ways to visually understand why that is?


Minor Presentation Issues
-------------------------
Please adjust for revision, but no need to discuss in rebuttal 

- Lines 25-28 read awkwardly, consider revising for flow
- Fig 1 gives impression that x has a distribution, but the distribution is over binary mask, right?
- Lines 46-49: A distribution over what exactly? Over perturbed values? Over pixels observed in a region/patch?
- Lines 123-126: Why use the symbol x twice (italicized and not)? Please redefine
- Line 171: "networkss" typo
limitations: Limitations
-----------
There are likely a number of choices that could be very sensitive to overall performance that are under-explored here:
- number of patches used / size of the 'grid'
- choice of the kernel functions (both "k" and "l")
- choice of the lengthscale of the RBF kernel (maybe median is OK, but could you improve performance by optimizing?)

As a blackbox method, there may be cases where white box methods are possible and preferred, but this is adequately addressed by the paper.

The 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).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

---


The 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. 
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.  

The '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.

Overall, 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.

Some comments

- 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. 

- 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.

- 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.

questions: The main points from my review above that could change my opinion are the following (please correct me if I am wrong):

1) 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. 

2) 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.  

3a) 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. 

3b) I am also missing muFidelity in the table.

4) 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"?

limitations: Yes
review_title: null

Meta-review: metareview: The paper proposes a novel black-box explanation method.  The proposed method uses HSIC to measure the dependence between randomly-masked inputs and the corresponding outputs, and identifies relevance patches.  Based on the decomposition property, the proposed method can also find interactions between patches.  Experiments quantitatively show that the proposed method outperforms (or is comparable on some evaluation measures) existing black-box methods with less computation costs.  Quantitative gains are demonstrated by finding the cause of wrong prediction in an object detection task, and interaction between patches.

Reviewers raised concerns mainly on clarity, which the authors well addressed.  I expect that the presentation of the final version will be much clearer.

A good paper with an interesting idea of using HSIC, which brings benefit on the explanation performance and computation time.  Furthermore, it allows explaining interactions, which most existing methods do not.  The advantages of the proposed methods are demonstrated quantitatively and qualitatively. 
confidence: Certain
Decision: Accept