Statistically Consistent Saliency Estimation
Authors: Emre Barut
Shunyan Luo
Venue:  (2020)
Keywords: Deep Learning Interpretation
Saliency Estimation
High Dimensional Statistics

Abstract: The use of deep learning for a wide range of data problems has increased the need for understanding and diagnosing these models, and deep learning interpretation techniques have become an essential tool for data analysts. Although numerous model interpretation methods have been proposed in recent years, most of these procedures are based on heuristics with little or no theoretical guarantees. In this work, we propose a statistical framework for saliency estimation for black box computer vision models. We build a model-agnostic estimation procedure that is statistically consistent and passes the saliency checks of Adebayo et al. (2018). Our method requires solving a linear program, whose solution can be efficiently computed in polynomial time. Through our theoretical analysis, we establish an upper bound on the number of model evaluations needed to recover the region of importance with high probability, and build a new perturbation scheme for estimation of local gradients that is shown to be more efficient than the commonly used random perturbation schemes. Validity of the new method is demonstrated through sensitivity analysis.


Under review as a conference paper at ICLR 2020
STATISTICALLY CONSISTENT SALIENCY ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
The use of deep learning for a wide range of data problems has increased the need for understanding and diagnosing these models, and deep learning interpretation techniques have become an essential tool for data analysts. Although numerous model interpretation methods have been proposed in recent years, most of these procedures are based on heuristics with little or no theoretical guarantees. In this work, we propose statistical framework for saliency estimation for black box computer vision models. We build model-agnostic estimation procedure that is statistically consistent and passes the saliency checks of Adebayo et al.) (201 8b). Our method requires solving a linear program, whose solution can be efficietlly computed in polynomial time. Through our theoretical analysis, we establish an upper bound on the number of model evaluations needed to recover the region of importance with high probability, and build a new perturbation scheme for esti- mation of local gradients that is shown to be more efficient than the commonly used random perturbation schemes. Validity of the new method is demonstrated through sensitivity analysis.
INTRODUCTION
Deep learning models have achieved great predictive performance in many tasks. However, these complex, often un-tractable models are difficult to interpret and understand. This lack of inter- pretability is major barrier for their wide adoption, especially in domains (e.g., medicine) where models need to be qualitatively understood and/or verified for robustness.
In order to address these issues, several interpretation approaches have been proposed in the last few years. A group of methods are based on visualizations, either by quantifying the effect of particular neurons or features, or by creating new images that maximize the target score for specific classes (Fr-) han et al. 2009; Simonyan et al. 2013 Zeiler & Fergus, 2014). A large collection of the techniques build saliency maps by attributing the gradients of the neural network to the input image through various procedures or by finding perturbations that significantly change the output output(Springenbrg let al. 2014: Bach et al., [2015] [Monavvo al.] 2017 Shrikumar et al.) [017]] Zhou et al. 2016
Selvaraju et al. 2017 7] (Smikovv et al. 2017 Fong & Vedaldi 2017
Adebayo et al. 201 8a
Dumitru
al. 2018 Singla al. (019)).
Another class of approaches treat the deep learner as a black-box. In this domain, Baehrens et al. (2010) use Parzen window classifier approximate the target classifier locally. Ribeiro et al. 2016) propose the LIME procedure, where small perturbations on the instance are used to obtain additional samples with which a sparse linear model is fit. Lundberg & Lee (2017) 7) propose SHapley Additive exPlanation(SH.. SHAP), which combines the Shapley value from the game theory with the additive feature attribution methods. They also make connections of the SHAP procedure with various existing methods including IRP, LIME and DeepI.IFT, CCen et al. (2019) propose L- and C-Shapley procedures which can reliably approximate the Shapley values in linear time with respect to the number of features.
Majority of the listed methods are heuristics which are constructed according to certain desirable qualities. For these methods, it is not clear what the main estimand is, if it can be consistently esti- mated or (and how) the estimand can be computed more efficiently. In fact, according to the recent research by Adebayo et al. (2018)) most methods with great visual inspection lack sensitivity the model and the data generating process. Theoretical explanation for why guided back back proppppaanttioonn and deconvolutional methods perform image recovery is provided by Nie al. (0018).

---

Under review as a conference paper at ICLR 2020
In this work, we propose statistically valid technique for model-agnostic saliency estimation, and prove its consistency under reasonable assumptions. Furthermore, our method passes the sanity checks given by AAdebayo et al. (2018b). Through analysis, obtain insights into how to improve the accuracy and reliability of our approach.
We note that there is recent work by Burns et al. (2019) where they provide saliency estimation technique with theoretical guarantees more specifically, FDR control. Although their procedure very promising from a statistical perspective, and theoretically valid under very general set of assumptions, their technique requires human input and has a significant computational load as it uses generative model for filling in certain regions of the target image.
Our main contributions are as follows:
We introduce a new saliency estimation framework for CNNs and propose a new method based on input perturbation. Our procedure requires solving linear program, and hence the estimates can be computed very efficiently. Furthermore, the optimization problem can be recast as "parametric simplex" (Vanderbei] 2014), which allows the computation of the full solution path in an expedient manner.
We establish conditions under which the signiticant pixels in the input can be identified with high probability. We present finite-sample convergence rates that can be used to determine the number of necessary model evaluations.
We find that the noise distribution for the perturbation has substantial effect the vergence rate. We propose a new perturbation scheme which uses a highly correlated Gaus- sian, instead of the widely used independent Gaussian distribution.
In the following section, we define the linearly estimated gradient (LEG), which is the saliency parameter of interest (i.e. the estimand), and introduce our statistical framework. In section 3, we propose regularized estimation procedure for LEG that penalizes the anisotropic total-variation. We provide our theoretical results in Section 4 and the result of our numerical comparisons in Section 5.
1.1 NOTATION
For matrix B, we use vec( and vee (B) to denote its vectorization and inverse vectorization, respectively. The transpose of matrix B is given by D" and use B for its pseudo-inverse. The largest and smallest eigenvalue of a symmetric matrix B are denoted by Amax (B) and Amin ( (B). For set S, we use 5C to denote its complement. For vector use uy to refer to its components indexed by elements in S. The g-norm for a vector is given by [|ull, and we use [| for the Frobenius norm of matrix B. The vector size p whose values are all equal to I is denoted by 1p. Similarly, we use 1p, xp2 and Op Opixpz to denote whose entries are equal 1 and respectively. Finally, for a continuous distribution F, we use F + to denote a distribution that is mean-shiieeee shifted by øo, i.e. F(z) G(z - 2o) for all 2, where G == + To.
TRP and set S E [., P)),
X P2 matrix
LINEARLY ESTIMATED GRADIENT
In gradient based saliency approaches, the main goal to recover the gradient of the deep learner
with respect to the input. More specifically, let f(r) be a deep learner, f X + [0, 1]. where X is the input space, c.g., [0, 255 28x28 for the MNIST dataset, where the input are given as 28 by 28 sized images. In this notation, the output is the probability of specific class, for instance Pmodet (x a 9); although this can be modified to check for comparative quantities by setting the output as
(m Then, local saliency is defined the derivative of f(-) with respect to the input, evaluated at point of interest Ty E X, i.e. Vzf(x)) However, in practice, local saliency is often too noisy and one instead uses average of the gradient around Zn (Shrikumar et al.) 2017: Smilkov al. 2017).
f(x) = fo(x)) - Pma)) is 9) - Pmodet (z is 7).
(I)
In order to study the saliency procedure from a statistical perspective, we start by defining an esti- mand, whose definition is motivated by the LIME procedure (Ribeiro al. 2016).
2

---

Under review as a conference paper at ICLR 2020
Definition 1 (LBG). For continuous distribution F, initial point zu X with X R xps and a function f X + [-1,1], the linearly estimated gradient (LEG), y E IP xPa is given by
70, F) arg min Ez-r-ao [f(()) -(xo) -ve(l)² vec(no ==)
9
LEG is based first order Taylor series expansion of the function f(x) around the point of interest Zo. The estimand is proxy for the local gradient, and is the coefficient that gives the best linear approximation, in terms of the squared error, among all possible choices. The distribution F determines the range of points the analyst wants to consider. We visually demonstrate LEG on two toy examples with single pixel (i.e. p1 = P2 1) in Figure
f(x)
f(x)
V vef fx) k=R
7(P2)
Yf, zo.
((F))
F
F
F2
C
(a) Comparison of the gradient vs. L.E.
(b) Effect of F on LEG
Figure 1: Visual demonstrations of LEG for single input. LEG seeks to find local linear approx- imation of f(x) in a neighborhood around zn; choice of the distribution, F, determines the size of the neighborhood. In Figure La] we compare LEG to the gradient, which is very localized. If f f(x) a highly varying function, then the gradient is too noisy, and the saliency score provided by LEG more meaningful. In Figure 1b, show LEG for two different distributions. For the distribution with the larger variance, LEG evaluates the input's 's effect on the output for a larger neighborhood around zo.
We note that the variance of has large effect on LEG. As F converges to a point mass at 0, ((x) is twice continuously differentiable in the neighborhood of then 7 - V (xr). On the other hand, if has high variance, then samples from vi + are substantially different from zo and LEG might longer be useful for interpreting the model at zp. This phenomenon can also described in terms of local vs global interpretation: for with a small variance, LEG provides a very local interpretation, i.e. gradient that is valid in small neighborhood around 2o, and as the variance of increases, LEG produces a more global interpretation, since a larger neighborhood around no is considered in the caleulation.
LEG has an analytical solution as the next lemma shows.
Lemma 1. Let Z be the random variable with a centered distribution F, i.e. Z ~ and E[Z] 0pz Assume that covariance of vec(Z) exists, and positive-defiiite Let Cov(vec(2) then
T(S F) vec- 'S-'''ES-PPP (( + +2) ((xx)))ec(())
(2)
Proof of the lemma is provided the Appendix.
affine transformation of high dimensional integral where the integrand is (f(rn + 2) - f(xo)) (z).2z This analysis also suggests an empirical estimate for the LEG, by replacing the expectation with the empirical mean. The empirical mean can be obtained by sampling æ from F + Ho, calculating f (x), and then applying Lemma 1. More formally, let 21,..., In be random samples from F To, and let ........ Yn be the function ovaluations with y; = f(x)). Further, let J = f(x;) (xx) and 2; = IG Fn- Then, the empirical LEG estimate is given by
Lemma shows that the LEG can be written
3

---

Under review as a conference paper at ICLR 2020
Alf. zo. F) vec-1
Σ-1
vec (012.)
n
As the function f(x is bounded and F has positive-definit covariance matrix, then it follows that as - o0, Ý + 7. However, classical linear model theory (Ravishanker & Dey, (001) shows that rate of the convergence is very slow, on the order of X PPPp//P///////// 1mp2//., n. where p1 and p2 are the dimensions of X. This severely limits the practicality of the empirical approach. In the next section propose regularization in order to obtaín faster convergence rates.
EFFICIENT ESTIMATION OF LEG
For interpretation of image classifiers, one expects that the saliency scores are located at a certain region, i.e. contiguous body or union of such bodies. This idea has lead to various procedures that estimate saliency scores by penalizing the local differences of the solution, often utilizing some form of the total variation (TV) penalty (Fong & Vedaldi 2017). The approach is very sensible from a practical point of view: Firstly, it produces estimates that are easy to interpret as the impor- tant regions can be easily identified; secondly, penalization significantly shrinks the variance of the estimate and helps produce reliable solutions with less model evaluations.
In the light of the above, we propose to estimate the LEG coefficient with anisotropic L1 TV penalty.
Definition 2 (LEG-TV).. For a hyperparameter, L 2 O, the TV-penalized LEG estimate is given as 3 vec-l (g) where g the solution of the following linear program
min 8
Dgll1
s.l. D+T
vec (ī,zz) - Ey
S SL,
(4)
where D E RCCP:p--P:--axpppp is the differencing matrix with Dij = 1, Di,k = -1 if the jth and the ttt component of g are connected on the two dimensional grid.
Our method is based on the "high confidence set" approach which has been successful in numerous applications in high dimensional statistics (Candes & Tao 2007 Cai al. 2011 Fan 2013). The set of that satisfy the constraint in the formulation is our high confidence set; if Z is chosen properly, this set contains that the distance between and 5 is small. When combined with the TV penalty in the objective function, the procedure seeks to find a solution that both belongs to the confidence set and has sparse differences on the grid. Thus, the estimator is extremely effective at recovering y that have small total variation.
true LEG coefficient, >(, aro F), with high probability] This setup ensures
The proposed method enjoys low computational complexity. The problem in equation 4 is linear program and can be solved in polynomial time, for instance by using a primal-dual interior-poin method for which the time complexity is O ((p12))..5) (Nocedal & Wright 2006). However, in practice, solutions can be obtained much faster using simplex solvers. In our implementations, we use MOSEK, commercial grade simplex solver by ApS (2019), and are able obtain solution in less than seconds on standard 8-core PC for problem of size ally, the alternative formulation (provided in the Appendix) can be solved using parametric simplex approaches which yield the whole solution path in I. [Vanderbei] 2014). The last point is often necessity in deployment when L needs be tuned according to some criteria.
P2 = 28. Addition-
We note that the procedure does not require any knowledge about the underlying neural network and completely model-agnostic. In fact, applications where security or privacy could concern and returning multiple prediction values needs to be avoided, the term given by Σ vec (ū:z,) can be computed on the side and supplied alongside the prediction.
See Lemma 2 in the appendix.
4

---

Under review as a conference paper at ICLR 2020
In Figure show the resulting estimates of the method with 500 model evaluations for a VGG-19 (Simonyan & Zisserman, 2014) network. For the distribution F. we use a multivariate Gaussian distribution with the proposed perturbation scheme in Section 4.2 We compute sepa- rately for each channel, and then sum the absolute values the different channels to obtain the final saliency score.
(a) Shark
(b) Soccer
(c) Whistle
Figure 2: LEG estimates for various images. Target classes are provided in the captions. LEG correctly detects the main object all of the instances. Third image labeled as "cellphone" but the VGG-19 network misclassifies it as "whistle". More results are provided in the Appendix.
4 THEORETICAL ANALYSIS AND IMPLEMENTATION
In this section, analyze the procedure from theoretical perspective and derive finite sample convergence rates of the proposed LEG-TV estimator. As we noted earlier, this analysis also gives us insight on the properties of the ideal perturbation distribution.
4.1 CONSISTENCY
first present our condition, which has a major role the convergence rate our estimator. The condition is akin to the restricted eigenvalue condition (Bickel et al. 2009) with adjustments specific to our problem.
Assumption 1. Let D+ the pseudo-inverss of the differencing matrix D, and denote elements of singular value decomposition of D as U.O.V where D UQVT. Furthermore, denote the last P1P2 - P1 - columns of U that correspond to zero singular values as U2. For the covariance matrix Σ,, and any set S with size 8, it holds that
where
AT ED+
inf Ass Asali A =0
(5)
|
The following theorem is our main result. Theorem 1. Let " 7(f Fu, F) and Σ Cov (vec(Z)), where Z F and E[Z]
Opt xps-
Let & be the LEG-TV estimate with L = D || log (p1P2/c) /n. If Assumption holds for the covariance matrix E with constant K, then with probability 1
1 CC
slog
11 - ml 1 1
K.
Ca
where E I. is mean shift parameter, is the number of non-zero elements in Dr", Op 1/4 and Ca is the minimal positive singular value of D.
4 2 D+ 11 x Pi
The proof is built on top of the "high confidence set" approach Fan 20033). In the proof, we first establish that, for appropriately chosen value of L, 7" T Fu, F) satisfies the constraint in equation 4 with high probability. Then, we make use of TV sparsity of & and 7 to argue that the two quantities cannot be too far away from each other, since both are in the constraint set. The full proof is provided in the Appendix.
Our theorem has two major implications:
5

---

Under review as a conference paper at ICLR 2020
1. We recover the true parameter the number of model evaluations increase. That is, TV penalized LEG is statistically consistent model interpretation scheme. Furthermore, our result states that, ignoring the log terms, one needs n = O(s (PIP2)1(2) many model evaluations to reliably recover y*.
2. Our bound depends on the constant K, which further depends on the choice of for the perturbation scheme. It is possible to obtain faster rates of convergence with carefully tuned choice of Σ. As a side note, since y also depends on Σ, the estimand changes when E is adjusted. In other words, our result states that certain estimands require less samples.
We note that our procedure identifies the LEG coefficient up mean shift parameter, m, which is the average of the true LEG coefficient y. In practice, the average can be consistently estimated (for instance, using the empirical version LEG in equation B). and the mean can be subtracted to yield consistent estimates for y, However, in our numerical studies, we see that this mean shift is almost non-existent: LEG-TV yields solutions that has no mean differences with the LEG coefficient, which we define as the solution of the empirical version as n + Co.
4.2 PERTURBATION SCHEME
In main result, established that the convergence of our estimator depends the quantity which is related to the spectral properties of E. In this subsection we explore the ramifications of the assumption.
Our main result in Theorem 1 states that the rate of convergence to the true LEG coefficient is inversely proportional the term s. Thus, perturbation schemes for which the restricted eigenvalues are large, as defined in Definition 1, yield saliency maps that require less samples to estimate the LEG.
We note that most of the saliency estimation procedures that make use of perturbations take these perturbations to be independent, which results in covariance matrix that is equal to the identity matrix, Σ = ((P((1))) (p)))) for some o² > 0. For LEG estimation without penalization, i.c. using equation T this choice is also optimal
the convergence rates under the normal setup depend on 1/Amin Ej. However, when one seeks to find an estimate for which the solution is sparse in the TV norm, this choice no longer ideal as demonstrated by our theorem.
In order to choose the covariance matrix of our perturbation scheme in manner that maximizes the bound equation 5 one also needs some prior information about the size of S, 8. As that requires estimation of and a complex optimization procedure, we instead propose a heuristic: we choose This choice
so that its eigenvectors match D A for vectors A with unit-norm and U, A the one vector it is orthogonal to the rest of the eigenvectors. Our proposed perturbation scheme is as follows:
fixes P1P2 1 many of the cigenvectors of Σ. For the last eigenvector,
1. Compute the singular value decomposition D, and let D UOVT.
2. Le 0202((ee (VO2VT= PiP2 1p1p2 1T'
for some choice of g² > 0.
As D+ VO+ with the proposed >, the numerator in equation 5 reduces to o² A'A and hence 0². Without any additional assumptions on S, this is the maximal value for x.
Figure 3: Selected eigenvectors of the proposed The eigenvectors, which contain the principal directions of the distribution, have maxima and minima in adjacent locations. Distributions drawn with these properties perform as object detectors as they can be used to detect existence (or non- existence) of significant pixels these locations.

---

Under review as a conference paper at ICLR 2020
We plot some of the eigenvectors for proposed E with P1 P2 28 in Figure B These eigenvectors are the principal directions of the perturbation distribution F, and the samples drawn from F' contain combination of these directions. We see these samples will have sharp contrasts at certain locations. This result is very intuitive: The perturbation scheme is created for a specific problem where boundaries for objects are assumed to exist, and large jumps in the magnitude of the distribution help our method recover these boundaries efficiently.
We conclude this section with demonstration of the perturbation scheme using Gaussian noise. In Figure we plot digit from the MNIST dataset (LeCun et al. 1998). along with instances obtained by independent perturbation and by our suggested distribution.
J
S
S
S
(a) Original digit
(b) Independent noise
(c) New perturbation scheme
Figure 4: Demonstration of the new perturbation scheme example from the MNIST dataset. Noise samples of the new scheme have a checkerboard pattern and their perturbations are uniformly distributed across the image.
4.3 IMPLEMENTATION DETAILS
LEG-TV procedure has two tuning parameters: (i) F, which determines the structure of the pertur- bation; and (ii) L, which controls the sparsity of the chosen interpretation.
Regarding F, we propose use multivariate Gaussian distribution it is easy to sample from. For Σ, we propose theoretically driven heuristic for determining the correlation structure of Σ in Section 4.2 However, the choice of the magnitude of Σ, i.e. a², left to the user. this quantity chosen too low, then the added perturbations are small in magnitude, and the predictions of the not change, resulting value of o², the results have too much variance as some of the pixel values are set to the minimum or the maximum pixel intensity. In our implementations, we find that setting o² to be between 0.05 and 0.30 results in reasonable solutions. We determine this range by computing perturbations of various sizes on numerous images using the VGG-19 classifier. The provided range is found to create perturbations large enough to change the prediction probabilities but small enough to avoid major changes in the image. Most of our presented results are given for o² 0.10.
neural network
LEG near zero. On the other hand, with very large
For the choice of L, propose two solutions: The first the theoretically suggested quantity given in Theorem 1, although this often results in estimates that are too conservative. Our second method heuristic based on some of the quantities in the optimization problem and we use this for our demonstrations. We set L = K2 where K is constant between 0 and 1 and Lmax is the smallest value of L for which the solution in equation 4 would result with g 0; i.c. Lmax n - (Ei= vec(ū:z;) |]. We use Kr 0.05 Kr. 0.10 in our implementations. We note that possible to obtain the solution for all T. by using a parametric simplex solver (Vanderbei] 2014), or by starting with large initial L, then using the solution of the program warm-start for a smaller choice of L. Both approaches return the solution path for all L, and might be more desirable in practice than relying on heuristics.
5 EXAMPLES
In this section, we demonstrate the robustness and validity of our procedure by two numerical ex- periments. In (.11 we perform sanity checks as laid out by Adebayo et al. (2018)), and show that the LEG-TV estimator fails to detect objects when the weights of the neural network are chosen randomly. In Section 5.2] we implement sensitivity analysis in which methods to compute regions importance, and then perturb these regions order to see their fect the prediction. For the deep learner,
use various saliency
VGG-19 (Simonyan & Zisserman 2014). For
7

---

Under review as a conference paper at ICLR 2020
computational efficiency, compute saliency maps 28 by 28 grid (i.e. 22x228) although the standard imput for VGG-19 is 224 by 224. The perturbations on the image are scaled up by 8 via upsampling in order for the dimensions to match.
5.1 SANITY CHECKS
In Adebayo et al. (2018b), the validity of saliency estimation procedures are tested by varying the weights of the neural network. a technique named, "cascading randomization", authors propose to replace the fitted weights of CNN layer by layer, and compute the saliency scores with each change. As a deep learner with randomly chosen weights should have no prediction power, one expects
the same effect in the resulting saliency scores: namely, more of the weights are perturbed, the explanation offered by interpretability methods should become more and more meaningless. Surprisingly, AAdbbay AAdeaay et al. (2018b) show that most commonly adopted interpretation procedures provide some saliency even after full randomization, and conclude that these methods act edge detectors.
Our procedure treats the classifier as a black-box and the explanations offered by LEG-TV are based solely on the predictions made by the neural network. During the sanity check, when the weights of the neural network are randomly perturbed, the predictions change significantly and no longer the underlying function to
depend on the input. Thus, we expect the local linear approximations be flat, which would result in saliency scores of zero for all of the pixels. Finally, small artifacts that might arise in this process, such as positive or negative saliency scores with no spatial structure, should be smoothed over due to the TV penalty, further robustifying our procedure.
In order to verify our intuition, we perform cascading randomization on the weights VGG-19 network. For all of the images in analysis, find that the LEG-TV estimate, is reduced to zero after randomization of either the top (i.e. logits) or the second top layer (i.e. second fully connected layer). The results of our experiment for two images after the weights are perturbed, the LEG-TV method fails to detect any signal that could be used for interpretation. In fact, due penalization, the estimate is interpretation given by our proposed method is reliable and is dependent on the classifier.
given in Figure It is seen that
zero. These results show that the
CASCADING RANDOMIZATION
Image
original
dense
block1_ccme __coov|
14/20
Figure 5: Results of the sanity check with cascading randomization. The network weights are replaced by random numbers in cascading order, starting from the last layer. LEG is equal to for all pixel values immediately after the first randomization.
5.2 SENSITIVITY ANALYSIS
For our second validity test, we use various interpretation models to compute regions of high impor- tance. We then mask these regions by decreasing the value of the pixels to zero which is equivalent to painting them black. We compute and assess the difference the predictions for the target class with each perturbation.
8

---

Under review as a conference paper at ICLR 2020
We compare method against four alternatives: GradCAM (Selvaraju et al.
2017 7). LIME (Ribeiro
et al. 20166) SHAP (Lundberg & Lee 2017) and C-Shapley (Chen et al. 2019). The last three methods are chosen they are model-agnostic like LEG, and do not make use of the architecture of the neural network. GradCAM chosen due to its popularity.
The saliency maps using C-Shapley and LEG-TV are computed for 28 by 28 grid. In order to make the comparison between the methods more fair, we downsize the saliency maps resulting from GradCAM, LIME and SHAP the same size. Interestingly, performance of these estimators; that is, the perturbations identified using the low resolution saliency maps result in faster drops the predicted score. For LEG-TV, LIME and SHAP, the saliency scores are computed using 3000 model evaluations, where as C-Shapley requires 3136 (28 x 28 x8) evaluations. For LEG-TV, we provide two solutions, a sparse solution which corresponds to larger choice of the penalty parameter I and noisy solution which is obtained with smaller choice of L, denoted by LEG and LEGO, respectively. We present the results for 500 images that are randomly chosen from subsample of the ImageNet dataset Deng al. 2009
find that this step improves the
2 The average of the log odds ratios across the 500 images are provided in Figure 6 We see that as the size of the perturbation increases, the predictions for the target class drop for all of the methods. The slope is sharpest for SHAP and LEGO, suggesting that these two methods identify pixels that are crucial for the predictions.
0-
Method
-5-
SHAP
LEG0
LEG
GradCAM
Log
C_SHAP
-10
LIME
0.0
0.4 Perturbation Size
0.6
0.8
Figure 6: Results of sensitivity analysis. Log of the predicted probability for the target class is plotted versus the size of the perturbation. The locations for the perturbations are determined by the saliency procedures. Predictions should decrease a fast rate for interpretability methods that can reliably identify regions of importance. In that regard, SHAP and LEGO appear to be the most accurate in determining the critical pixels, followed by LEG, GradCAM, C-Shapley and LIME.
In Figure 7 we plot the top 10% most salient pixels according to different procedures for three images in the dataset. The pixels chosen by SHAP appear to correspond to specific convolution pattern and the chosen region is not contiguous. On the other hand, pixels identified by LEG-TV are visually meaningful to the human eye and contain pixels that more likely to be relevant for the prediction. LEG-TV selects different parts of the crane the first image, and the face of the Pekinese dog in the second. In the last image, where soap dispenser is misclassified bottle, LEG-TV TV relates the classification to the label and the barcode of the bottle parts that are often on soda bottles. For the same image, LEG-TV also selects the fixtures in the background, which could have been mistaken by the classifier as the cap of the soda bottle.
soda
DISCUSSION
We have proposed statistical framework for saliency estimation that relies on local linear approxi- mations. Utilizing the new framework, we have built computationally efficient saliency estimator that has theoretical guarantees. Using our theoretical analysis, we have identified how the sample complexity of the estimator can be improved by altering the model evaluation scheme. Finally,
The dataset is provided by fastai (oward et al. 2019 and can he found at http://files.. fast. aisttai/dat//mmaeeee
sample-train.targg

---

Under review as a conference paper at ICLR 2020
Original
SHAP
LEGO
LEG
GradCAM
C-Shap
LIME
Crane
Pekinese
Soda Bottle
(Incorrect
class)
Figure Masked regions at 10% perturbation by various saliency procedures.
have shown through empirical studies that (i) unlike most of its competitors, our method passes the recently proposed sanity checks for saliency estimation; and (ii) pixels identified through our approach are highly relevant for the predictions, and our method often chooses regions with higher saliency compared to regions suggested by its alternatives.
REFERENCES
Julius Adebayo, Justin Gilmer, Ian Goodfellow, and Been Kim. Local explanation methods for deep neural networks lack sensitivity parameter values. arXiv preprint arXiv:1810.03307, 2018a.
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. In Advances in Neural Information Processing Systems, pp- 2018b.
MOSEK ApS. MOSEK Optimizer API for Python 9.1.6, 2019. URL htRl:tttt/://csnccet com/ 9.
html
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e0130140, 2015.
David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus- Robert Müller. How to explain individual classification decisions. Journal of Machine Learning Research, 11(Jun):1803-138 2010.
Peter J Bickel, Ya' acov Ritov, Alexandre B Tsybakov, al. Simultaneous analysis of lasso and dantzig selector. The Annals of Statistics, (7(4):1775-11) 2009.
Collin Burns, Jesse Thomason, and Wesley Tansey. Interpreting black box models with statistical guarantees. arXiv preprint arXiv: 11904.00045, 2019.
Tony Cai, Weidong Liu, and Xi Luo. constrained minimization approach sparse precision matrix estimation. Journal of the Americun Statistical Association, 106(494):594-607, 2011.
Emmanuel Candes and Terence Tao. The dantzig selector: Statistical estimation when p is much larger than n. The annals of Statistics, 33 2007.
Jianbo Chen, Le Song. Martin J. Wainwright, and Michael I. Jordan. L-shapley and e-shapley: Efficient model interpretation for structured data. In International Conference Learning Rep- resentations, 2019. URL htt.hhtss//// htpp///eneeeeeeeeeeeeeeeeeeeeeee net/ ttt.:ete.oormmm155113333...00
Deng, W. Dong, R. Socher, L.-.. Li. K. Li, and L. Fei-Fei. ImageNet: A Lcrge-Scale Hierarchical Image Database. In CVPR09, 2009.
10

---

Under review as a conference paper at ICLR 2020
Maximilian Alber Klaus-Robert Müller Dumitru, Erhan Been Kim Sven Dähne Pieter, Jan Kinder- mans, and Kristof T Schütt. Learning how to explain neural networks: Patternnet and patternat- tribution. In International Conference on Learning Representations, 2018.
Dumitru Erhan, Yoshua Bengio, Aaron Courville, and Pascal Vincent. Visualizing higher-layer features of a deep network. University of Montreal, 1341(3):1, 2009.
Jianqing Fan. Features of big data and sparsest solution in high confidence set. Past, present, and future of statistical science, pp. 507-523, 2013.
Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful perturba- tion. In Proceedings of the IEEE International Conference Computer Vision, pp. 1429-343,, 2017.
Brian R Gaines, Juhyun Kim, and Hua Zhou. Algorithms for fitting the constrained lasso. Journal of Computational and Graphical Statistics, 2774) 2018.
Jeremy Howard et al. fastai. httpps://githiii http:://gggtaa..cccaaaaaaaaaaaaa
2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pp. 17764477, 2017.
Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojciech Samek, and Klaus-Robert Müller. Explaining nonlinear classification decisions with deep taylor decomposition. Pattern Recognition, 65:211-220 2017.
Weili Nie, Yang Zhang, and Ankit Patel. A theoretical explanation for perplexing behaviors of backpropagation-based visualizations. arXiv preprint arXiv: 07039, 2018.
Jorge Nocedal and Stephen J Wright. Numerical optimization second edition. Numerical optimiza- lion, pp. 497-528, 2006.
N. Ravishanker and D.K. Dey. A First Course in Linear Model Theory. Chapman & Hal//CRC Texts in Statistical Science, Taylor & Francis, 2001. ISBN 9781584882473. URL https:
//books. wttpe//cmmmmooooo/dddsrreeee
9XBMC
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and duta mining, pp. 1 1144 ACM, 2016.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient- based local- ization. In Proceedings of the IEEE International Conference Computer Vision, pp. 618-620 2017.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In Proceedings of the 34th International Conference on Ma- chine Learning- Volume 70, pp. 3145-3153. JMLR. org, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 100i 1556, 2014.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Vi- sualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 2013.
Sahil Singla, Eric Wallace, Shi Feng, and Soheil Feizi. Understanding impacts of high-order loss approximations and features in deep learning interpretation. In International Conference Ma- chine Learning, pp. 5848-5856, 2019.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Vićgas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. arXiv preprint arXiv: nete:0766....33 2017.

---

Under review as a conference paper at ICLR 2020
Jost Tobias Springenberg. Alexey Dosovitskiy. Thomas Brox, and Martin Riedmiller. Striving for simplicity: The all convolutional net. arXiv preprint arXiv:1412.6806, 2014.
Robert Vanderbei. Linear Programming: Foundations and Extensions. Springer, 2014.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In
European conference computer vision, pp. 818-833 Springer, 2014.
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2921-2929, 2016.
A APPENDIX
A. ALTERNATIVE FORMULATION
Our linear program can also be recast by a change of variables and setting a Dg. In this case, the elements of a correspond to differences between adjoint pixels. This program can be written as:
min ||0l11
a SL
s.t.
D
Σ f(E)2, -DD-
U.
where D+ the pseudo-inverse of and U2 is related to the left singular vectors of D. More precisely, letting D UOVT denote the singular value decomposition of D) U2 is the submatrix that corresponds to the columns of U for which θ, is zero. The linearity constraint ensures that the differences between the adjoint pixels is proper. Derivation of the alternative formulation follows from Theorem in Gaines et al. 20188) and is omitted.
This formulation can be expressed in the standard augmented form, i.e. min Am of x. by writ- ing ø [a+, 0t-, 04,,8,,,, 1-1²"
U2
U2 ++ D+
A
D+
lmxm
0
b
Llm D* y - -L1m D D*
1m
+
-Imxm
where y == E 2, and m 2p1P2 P1 can be obtained by setting 7 D (a+ a-).
P2. The y coefficient in the original formulation
A.2 PROOF OF THEOREM
Our proof depends on the following lemma.
Lemma 2. For 2 / D+ 1 log (piP2/c) /n, 72" is in the feasibility set with probability -,, that is
D+
(5x) (.)) 8x
D+
L.
Proof. For case of notation, let D+E [ f Z. and note that G D+ Fur-
thermore, let f (āx) D+ We also assume that the images have been rescaled so that the maximum value o; (without rescaling, the maximum would be given as the largest intensity, iec. 255). Since, the function values are also in the range given by [-2,2], we can bound | that is
|=tم J ( a < <2|1D Il, max | s I2
12

---

Under review as a conference paper at ICLR 2020
The proof follows by applying the McDiarmid's inequality (Vershynin 2018 for each row of the difference and then taking the supremum over the terms. By application of McDiarmid's ' inequality, have that
Σ 71
zi G3 21 21
<
2
Let == D+ log (pip2 /6) /.. Then, taking union bound over all variables, we have
1 G2 2
Σ zij
P
max n
Now note that that the feasibility set for any L' 2 contains that of and thus y is automatically included.
We now present the proof of the theorem. Note that the technique is based on the Confidence Set approach by Fan (013).. In the proof, we use y refer vec(?) for ease of presentation.
Proof. First, let the high probability set for which Lemma 2 holds by A. All of the following statements hold true for A. We let A = D ( >-) We know that || < ||yr' I| since both are in the feasibility set, as stated in Lemma Let and the complement of S as SC. By assumption the Theorem, we have that the cardinality of $ i.e. |S| Now let As the elements of A in S. Then, using the above statement, show that || 2 || II Note,
Dy", Dÿ and define S {j : a * 0},
||â]] = ||a" + AAl 1
|aa + As + ||Agoll
|a*]|, 111 - ||Aa|1 l1 + | ll
||ā]] - -I ||, + |lAsc I
and ||ss|| 2 /|Agell, || follows immediately. Furthermore
A 2/$
| 2 A N
|
As
/V2
where the last line uses the previous result. Additionally, note that
DTD+ED+ | | ΣD+ DDED+*++++
< Al|
where the first inequality follows by Holder's inequality and the second follows from Lemma 2 and the fact that both f and 7* are in the feasibility set for L / log (PiP2/e) /n. We further bound the right hand side of the inequality by using the previous result, which gives
T D' < 4LV3 A 2-
Next, bound || by combining the previous results. Now, by assumption of the Theorem, have that
|a < E
< <4L
Dividing both sides by ||A||2, we obtain that
C
log PIP2/e
|Dj - Dy <
a
n
13

---

Under review as a conference paper at ICLR 2020
Finally, note that
DD ~ = + - >
CD [Iml + - - P1P2
P1P2 + 3 35
Σ 75
where D is the smallest singular value of that positive. This follows from the fact that D has only right singular value, whose eigenvector is given by vector of ones multiplied by
1/pPIP2. Letting (p1p2) - E, 2 - -E 9/5) concludes the proof.
A.3
PROOF OF LEMMA
Proof. Let
(gg) = En-F-oo [f(a) f(x,) - vec(g)" veo(ro - vec(#o-xx) =))²
Note that h(g is quadratic and convex in g. Taking the derivative with respect to vec(g), and setting zero we obtain
EgaF+ao [-2 vec(x0 2) (f(x) f(r)) vec(2o x²²² vec(g"))] 0,
where g" is the minimizer. After reorganizing the terms and setting
we get
E [vec(=) (s + 2) - [(xo))] = Ez-F [vec(z) vec(=) vec(g") ) Σ vec(g"), where we use that D = Cov(vec(z)) in the last equation. The result follows trivially.
A.4 EQUIVALENCY OF LEG-TV WITH EMPIRICAL LEG IF L =
Lemma 3. For the LEG-TV estimate with I, = 0, if the one vector is an eigenvector of Σ, i.e. Elpip ALpipg then the solution equal to the empirical LEG estimate up location shift. That is, 7 = all p1ppp for some a E R.
Before the proof, we note that the eigenvector condition on V can satisfied either with independent noise suggested scheme in Section
Proof. Note that, if L = 0, then we have that
n
D
vec (Jizs) D-TEg-
As the only right singular vector of D with zero singular value is the one vector, the above statement is true iff
vec (jizz) Eg cl P1P27
for some E R. Solving for g, obtain,
-=-ー vec (Uizs) cl pipa
PiPs = -1 E vec (jiz;) -.
x P1p27
where the fact that the vector is eigenvector of E-1 with eigenvalue X - Setting a concludes the proof.
14

---

Under review as a conference paper at ICLR 2020
A.5
EXAMPLES ON MNIST
Oriinal
LBC EXOCT
LES
sallency
desplit
drp
00C
SHAP
7
7
7
Orignnl
IFC exArT
IFG
salleccy
deeplit
+rp
ore
SHAP
2
2
2
Original
LEC exact
LEG
safency
desplit
SHAP
LEG
SHAP
Original
LSG
sallency
SHAP
4
Original
sallency
deeplitt
Originel
LEC exect
LEG
sallency
deeplitt
etrp
OCC
SAAP
4
Original
LBG exact
LEG
saliency
deeplit
etrp
occ
SHAP
Figure 8: Saliency estimates from various procedures on the MNIST dataset for a LeNet (LeCun al. 1998). The listed procedures the empirical version of LEG [LEG-Exact], LEG, Direct Saliency, DeepLIFT (Shrikumar et al. 2017). ELRP (Bach et al. 2015), Occlusion Maps and SHAP (Lundberg & Lee 2017)
15

---

Under review as a conference paper at ICLR 2020
A.6 EXAMPLES ON IMAGENET
(a) Balloon
(b) Beacon
(c) Bear
(d) Bookcase
Daisy
(l) Elephant
(g) Helmet Crab
(h) Ice Cream
Lemon
(j) Lifeboat
Figure 9: LEG estimates for various images from the ImageNet dataset. Target classes are provided
in the captions.
16

---

Under review as a conference paper at ICLR 2020
(a) Mailbox
(b) Pineapple
(c) Plane
(d) Shark
(e) Soccer
(I Tiger Cat
ONLY
Traffic Light
(h) Tree Snake
(i) Vulture
(i) Yorkie
Figure 10: LEG estimates for various images from the ImageNet dataset. Target classes are provided in the captions.
17


Reviews:
[{"review_id": "rkgorCQj5B", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary\nThis paper proposes an attribution method, linearly estimated gradient (LEG) for deep networks in the image setting.\nThe paper also introduces a variant of the estimator called LEG-TV, which includes a TV penalty, and provides a \ntheorem on the convergence rate of the estimator. The paper finds that the LEG attributions pass sanity\nchecks. \n\nMy recommendation\nOverall, I am recommending this paper as a weak accept. There are several points to address with\nregards to the exposition and flow of the paper, which is my biggest issue with this paper. I believe\nthe authors can address this point and I am willing to raise my point on this basis. The paper also\nprovide some theoretical analysis of the proposed method, which is typically lacking for most\nof the interpretation methods in this domain. \n\n\nPossible Improvements\n- The LEG method is not sufficiently motivated. Here, I am specifically referring to the functional\nform of the estimated itself in definition 1. See the question section  for some of the issues \nI raised there. \n- From figure 4, we see that the method passes the proposed sanity checks which seem like a \nkey motivation for this work, however, the authors don't give an explanation for why this is the\ncase.\n- The paper notes that LEG can be estimated using an LP; it would have been great for the authors\nto completely spell this out in the appendix or somewhere in the text. What is the exact form of the\nLP? What are the constraints? \n- As the authors know, the two evaluations presented in the paper: sanity checks, and the zeroing\nout procedure (in figure 5) don't actually tell us which method is a good method, just rule out a method.\nI would encourage the authors to design a toy task where the ground truth attributions are know, then\ntrain a model to be 100 percent or so accurate on this task. You can then obtain LEG-TV estimates\nfrom this model and compare to the ground-truth. \n- I found the proof of lemma 1 confusing, the authors say it follows trivially, but I don't see it. For example, \nthere should be a factor of 2 somewhere after taking the derivative wrt to $vec(g)$, but I don't see it. It is\nfine for the authors to spell out the derivation here if possible. \n-The paper ends quite abruptly with no conclusion or discussion. It would be great to include a wrap up\nsection that puts the contributions into context. \n- I get the sense that this method should be computationally intensive, though the paper says otherwise.\nIt is fine for a method to be computationally intensive, but can the authors speak to this issue?\n\n\nSome Questions\nDefinition 1: I had a difficult time understanding this definition. What is $g$ here? I assume\nit is the gradient based on the reference to the first order Taylor expansion. In addition, why\nis the estimand squared? Further, What does it mean to take expectation wrt $F + x_0$. I was\nparticularly confused by the last point, because F is a continuous distribution, while presumably\n$x_0$ is the point of interest. The paper notes in several places that it can sample from $F + x_0$,\nis this equivalent to sampling from $F$ and adding point $x_0$?\n\nWhat is LEG0 in figure 5?\n\nIs $\\kappa$ in your theorem 1, the condition number of the covariance matrix of the perturbation?\n\n\nConclusion\nOverall, the paper provides a nice method along with analysis on convergence rates and other statistical\nproperties. Several of the key issues/questions I have about the paper are raised above. None of these\nshould be dealbreakers but would require the authors to flesh out more details and possibly justify\ncertain choices. In general, I think more effort should be put into the flow and writing of the paper.\nOverall, this is an interesting contribution.\n\n\n## After reading author responses\nI believe the authors have clarified and improved the readability of the paper and clarified several of the questions\nthat 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\nare useful of decision making or understanding of a model by either a generic end user or the model developer. \nThis is a huge problem in this area that deserves significant attention. This said, the goal of this current paper is to\ntake a step towards developing a principled method, so this is a step in that direction perhaps. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SyekXJ1AYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nIn particular, having an upper bound on the number of model evaluations to recover the region of\nimportance with high probability is significant. Moreover, they have proposed a new perturbation scheme for estimation of gradients that works better than random perturbation schemes.\n\nI have some questions listed below:\n- Can the proposed approach be integrated with different types of Saliency map methods?\n\n- Can you explain the differences of the proposed approach and the group feature formulation of https://arxiv.org/abs/1902.00407 ?\n\n- Is there a quantitative way to assess the performance of the proposed approach?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xcj6rAKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work proposes a statistical framework for saliency estimation for black box\ncomputer 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.\n\nThe 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\nsolved by any linear programming software, for which many open-source implementations exist\"), and if the author could remark on the empirical running time.\n\nAlso, 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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkxs5ykUcB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nDefinition 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. \n\nAfter 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.\n\nOverall, 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. \n\nWeakness: \n1. Theorem 1 provides a nice characterization for the property of the proposed LEG-TV estimate. But there are two weaknesses. \n\nFirst, 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.\n\nSecond, 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.\n\n2. Can the authors be more specific on the time complexity and sample complexity of the proposed algorithms?\n\n3. 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).\n\nThe 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.\n-----------------------------------------------------------------------------------------------------\n--------------------------------------Post Author Response--------------------------------\n-----------------------------------------------------------------------------------------------------\n\nThe 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. \n      \n      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.\n      \n      A typo: The first paragraph of Section 3: \" less model evaluations.\" should be \" fewer model evaluations.\"\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eTWxW2FB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nMy 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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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