Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Summary
This paper proposes an attribution method, linearly estimated gradient (LEG) for deep networks in the image setting.
The paper also introduces a variant of the estimator called LEG-TV, which includes a TV penalty, and provides a 
theorem on the convergence rate of the estimator. The paper finds that the LEG attributions pass sanity
checks. 

My recommendation
Overall, I am recommending this paper as a weak accept. There are several points to address with
regards to the exposition and flow of the paper, which is my biggest issue with this paper. I believe
the authors can address this point and I am willing to raise my point on this basis. The paper also
provide some theoretical analysis of the proposed method, which is typically lacking for most
of the interpretation methods in this domain. 


Possible Improvements
- The LEG method is not sufficiently motivated. Here, I am specifically referring to the functional
form of the estimated itself in definition 1. See the question section  for some of the issues 
I raised there. 
- From figure 4, we see that the method passes the proposed sanity checks which seem like a 
key motivation for this work, however, the authors don't give an explanation for why this is the
case.
- The paper notes that LEG can be estimated using an LP; it would have been great for the authors
to completely spell this out in the appendix or somewhere in the text. What is the exact form of the
LP? What are the constraints? 
- As the authors know, the two evaluations presented in the paper: sanity checks, and the zeroing
out procedure (in figure 5) don't actually tell us which method is a good method, just rule out a method.
I would encourage the authors to design a toy task where the ground truth attributions are know, then
train a model to be 100 percent or so accurate on this task. You can then obtain LEG-TV estimates
from this model and compare to the ground-truth. 
- I found the proof of lemma 1 confusing, the authors say it follows trivially, but I don't see it. For example, 
there should be a factor of 2 somewhere after taking the derivative wrt to $vec(g)$, but I don't see it. It is
fine for the authors to spell out the derivation here if possible. 
-The paper ends quite abruptly with no conclusion or discussion. It would be great to include a wrap up
section that puts the contributions into context. 
- I get the sense that this method should be computationally intensive, though the paper says otherwise.
It is fine for a method to be computationally intensive, but can the authors speak to this issue?


Some Questions
Definition 1: I had a difficult time understanding this definition. What is $g$ here? I assume
it is the gradient based on the reference to the first order Taylor expansion. In addition, why
is the estimand squared? Further, What does it mean to take expectation wrt $F + x_0$. I was
particularly confused by the last point, because F is a continuous distribution, while presumably
$x_0$ is the point of interest. The paper notes in several places that it can sample from $F + x_0$,
is this equivalent to sampling from $F$ and adding point $x_0$?

What is LEG0 in figure 5?

Is $\kappa$ in your theorem 1, the condition number of the covariance matrix of the perturbation?


Conclusion
Overall, the paper provides a nice method along with analysis on convergence rates and other statistical
properties. Several of the key issues/questions I have about the paper are raised above. None of these
should be dealbreakers but would require the authors to flesh out more details and possibly justify
certain choices. In general, I think more effort should be put into the flow and writing of the paper.
Overall, this is an interesting contribution.


## After reading author responses
I believe the authors have clarified and improved the readability of the paper and clarified several of the questions
that I had. I am raising my score to an accept. While I believe this is a valuable contribution to the sea of attribution methods that have now been published, like the authors noted, it is still not clearly if attribution methods as a whole
are useful of decision making or understanding of a model by either a generic end user or the model developer. 
This is a huge problem in this area that deserves significant attention. This said, the goal of this current paper is to
take a step towards developing a principled method, so this is a step in that direction perhaps. 
review_title: Official Blind Review #5

final_score: rating: 8: Accept
review_content: The authors propose a nice framework for interpreting differentiable models without access to model details. The framework also comes with two empirical estimates, with solid theoretical back-up. 

Definition 1 in Section 2 provides a definition for the method to study (LEG). LEG is a nice generalization of multiple existing approaches. There also seems to be a lot more to investigate for future work based on this framework. 

After the authors proposed Definition 2 (seems to be a bit too straightforward, to be discussed later), Theorem 1 is proposed to characterize its convergence. It also provides guidelines for selecting the covariance matrix $\Sigma$, as discussed in Section 4.

Overall, the paper proposes a nice framework for model interpretation. It is well backed up by theory. It should clearly be accepted, although the paper is relatively weak in experiments. Below I will discuss some weaknesses and potential improvements. 

Weakness: 
1. Theorem 1 provides a nice characterization for the property of the proposed LEG-TV estimate. But there are two weaknesses. 

First, the authors should note that the proposed definition 2 is still a bit too straightforward without intuitive explanations. For example, what is the general form of 2D Fused Lasso? How is it applied to approximate Definition 1 / Equation (2) to get the expression in Definition 2? More details may be explained to help readers understand.

Second, it should be carefully discussed that the proof of Theorem 1 depends on existing work if the connection is close. For example, the authors may add in the main content "the proof of Theorem 1 is built on top of ..." or statements like that, probably with a short sketch / intuition on the entire proof if space permits.

2. Can the authors be more specific on the time complexity and sample complexity of the proposed algorithms?

3. It seems the experimental section of the paper is not satisfactory. Almost all results are single-image analysis, instead of systematic empirical analysis on an image data set. Without such analysis, it is hard to see the advantage of the proposed method over other comparing saliency maps and model-agnostic methods. For example, is the proposed method more sample-efficient than LIME or SHAP, or other more efficient procedures such as L(C)-Shapley? Is the proposed method really selecting meaningful segments for the model? (It may be tested by evaluating the log-odds-ratio after the top selected features are masked.) It is observed that LEG is able to select connected regions (Figure 6). The same phenomenon has been observed for C-Shapley. It may be helpful if the connection is discussed (such as the connection between sampling procedure of C-Shapley and the procedure imposed by LEG-TV).

The reviewer is not conditioning the "accept" decision on adding any of the suggested improvements on experiments given the limited rebuttal period and limited space, although it may benefit the paper of some of them can be addressed.
-----------------------------------------------------------------------------------------------------
--------------------------------------Post Author Response--------------------------------
-----------------------------------------------------------------------------------------------------

The authors have addressed most of my concerns. Theorem 1 and the sketch of the proof have been discussed. Also, complexity has been discussed (the definition of $s$ is embedded in the theorem and may be made clearer). Last but not least, authors have carried out experiments in a larger scale to get more stable results. 
      
      The performance, in terms of log-odds-ratio, may not be as good as some of the comparing methods. However, the paper provides a creative framework for incorporating structure into feature attribution scores in model interpretation. So I will keep my score.
      
      A typo: The first paragraph of Section 3: " less model evaluations." should be " fewer model evaluations."


review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This work proposes a statistical framework for saliency estimation for black box
computer vision models, based on solving a convex program in (4). It also gives theoretical analysis on its consistency in Theorem 1, and run a few simulations to show the empirical performance of the proposed method.

The method proposed seems to be novel and reasonable. As a result, I tend to accept this paper. However, I would like to remark that solving (4) might be empirically difficult (depending on the size of the problem) even though it is convex and can be solved in polynomial time theoretically. I wonder if the authors could clarify the setup of their experiments (instead of writing "The problem in equation 4 can be
solved by any linear programming software, for which many open-source implementations exist"), and if the author could remark on the empirical running time.

Also, I am not sure if "Note that if L = 0, then the TV-penalization has no effect and the solution of the above procedure reduces to the empirical estimate," as the objective function is in L1 norm.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Author propose a statistical framework and a theoretically consistent procedure for saliency estimation that is close to the empirical solution and has sparse differences on the grid. I think the idea of the paper is quite interesting and the results are significant. 

In particular, having an upper bound on the number of model evaluations to recover the region of
importance with high probability is significant. Moreover, they have proposed a new perturbation scheme for estimation of gradients that works better than random perturbation schemes.

I have some questions listed below:
- Can the proposed approach be integrated with different types of Saliency map methods?

- Can you explain the differences of the proposed approach and the group feature formulation of https://arxiv.org/abs/1902.00407 ?

- Is there a quantitative way to assess the performance of the proposed approach?
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: Authors proposes an interesting statistical method to detect saliency in images. Authors provides a specific estimator that is fast to compute and characterize its performance w.r.t. parameters.

My main concern is the experiment section. "For computational efficiency, we compute saliency maps on a 28 by 28 grid (i.e. γ˜ ∈ R 28×28) although the standard input for VGG-19 is 224 by 224. T". Shouldn't we do the same thing for all baselines? The seemingly good sailency results might stem from this artifact.
review_title: Official Blind Review #2

Meta-review: This submission proposes a statistically consistent saliency estimation method for visual model explainability.

Strengths:
-The method is novel, interesting, and passes some recently proposed sanity checks for these methods.

Weaknesses:
-The evaluation was flawed in several aspects.
-The readability needed improvement.

After the author feedback period remaining issues were:
-A discussion of two points is missing: (i) why are these models so sensitive to the resolution of the saliency map? How does the performance of LEG change with the resolution (e.g. does it degrade for higher resolution?)? (ii) Figure 6 suggests that SHAP performs best at identifying "pixels that are crucial for the predictions". However, the authors use Figure 7 to argue that LEG is better at identifying salient "pixels that are more likely to be relevant for the prediction". These two observations are contradictory and should be resolved.
-The evaluation is still missing some key details for interpreting the results. For example, how representative are the 3 images chosen in Figure 7? Also, in section 5.1 the authors don't describe how many images are included in their sanity check analysis or how those images were chosen.
-The new discussion section is not actually a discussion section but a conclusion/summary section.

Because of these issues, AC believes that the work is theoretically interesting but has not been sufficiently validated experimentally and does not give the reader sufficient insight into how it works and how it compares to other methods. Note also that the submission is also now more than 9 pages long, which requires that it be held to a higher standard of acceptance.

Reviewers largely agreed with the stated shortcomings but were divided on their significance.
AC shares the recommendation to reject.
Decision: Reject