Evaluations and Methods for Explanation through Robustness Analysis
Authors: Cheng-Yu Hsieh
Chih-Kuan Yeh
Xuanqing Liu
Pradeep Ravikumar
Seungyeon Kim
Sanjiv Kumar
Cho-Jui Hsieh
Venue:  (2020)
Keywords: Interpretability
Explanations
Adversarial Robustness

Abstract: Among multiple ways of interpreting a machine learning model, measuring the importance of a set of features tied to a prediction is probably one of the most intuitive way to explain a model. In this paper, we establish the link between a set of features to a prediction with a new evaluation criteria, robustness analysis, which measures the minimum tolerance of adversarial perturbation. By measuring the tolerance level for an adversarial attack, we can extract a set of features that provides most robust support for a current prediction, and also can extract a set of features that contrasts the current prediction to a target class by setting a targeted adversarial attack. By applying this methodology to various prediction tasks across multiple domains, we observed the derived explanations are indeed capturing the significant feature set qualitatively and quantitatively.

Under review as a conference paper at ICLR 2020
EVALUATIONS AND METHODS FOR EXPLANATION THROUGH ROBUSTNESS ANALYSIS
Anonymous authors Paper under double-blind review
ABSTRACT
Among multiple ways of interpreting a machine learning model, measuring the importance of a set of features tied to a prediction is probably one of the most intuitive way to explain a model. this paper, we establish the link between a set of features to a prediction with new evaluation criterion, robustness analysis, which measures the minimum distortion distance of adversarial perturbation. By measuring the tolerance level for adversarial attack, we extract set of features that provides the most robust support for a current prediction, and also target class
can extract of features that contrasts the current prediction by setting a targeted adversarial attack. By applying this methodology to various prediction tasks across multiple domains, we observe the derived explanations are indeed capturing the significant feature set qualitatively and quantitatively.
INTRODUCTION
With the significant progress of recent machine learning research, various machine learning models have been being rapidly adopted to countless real-world applications. This rapid adaptation increas- ingly questions the machine learning model's credibility, fairness, and more generally interpretabil- ity. In the line of this research, researchers have explored various notions of model interpretability. Some researchers directly answer the trustability (Ribeiro et al., 2016) or the fairness of model (Zhao et al., 2017), while some other researchers seek to actually improve the model's performance by understanding the model's 's weak points (Koh & Liang, 2017). Even though the goal of such various model interpretability tasks varies, vast majority of them are built upon extracting relevant features for prediction, so called feature-based explanation.
Feature-based explanation is commonly based on measuring the fidelity of the explanation to the model, which is essentially how close the sum of attribution scores for a set of features approxi- mates the function value difference before and after removing the set of features. Depending on their design, the fidelity-based attribution evaluation varies: completeness (Sundararajan et al., 2017), sensitivity-n (Ancona et al., 2018), infidelity (Yeh et al., 2019), and causal local explanation metric (Plumb et al., 2018). The idea of smallest sufficient region (SSR) and smallest destroying region (SDR) (Fong& & Vedaldi, 2017: Dabkowski & Gal, 2017) is worth noting because considers the ranking of the feature attribution scores, not the actual score itself. Intuitively, for faithful attribu- tion score, removing the most salient features would naturally lead to a large difference in prediction score. Therefore, SDR-based evaluations measure how much the function value changes when the most high-valued salient features are removed.
Although the aforementioned attribution evaluations made success in many cases, setting features with an arbitrary reference values to zero-out the input is limited, in the sense that it only considers the prediction at the reference value while ignoring the rest of the input space. Furthermore, the choice of reference value inherently introduces bias. For example, if we set the feature value to rgb images, this introduces bias in the attribution map that favors the bright pixels. As a result, explanations that optimize upon such evaluations often omit important dark objects and the pertinent negative features in the image, which is the part of the image that does not contain object but is crucial to the prediction (Dhurandhar et al., 2018). An alternative way to remove pixels is to use sampling from some predefined distribution or a generative model (Chang et al., 2018), which nevertheless could still introduce some bias with respect to the defined distribution. Morcover, they require a generative model that approximates the data distribution, which may not be available in certain domains.

---

Under review as a conference paper at ICLR 2020
In this paper, remove such inherit bias by taking different perspective the input perturbation. We start from an intuition that if set of features are important to make a specific prediction, keeping them in the same values would preserve the prediction even though other irrelevant features are modified. In other words, the model would be more sensitive on the changes of those important or relevant features than the ones that not. Unlike the foremost approaches including SDDR and SSR that perturbs features to a specific reference point, we consider the minimum norm of perturbation to arbitrary directions, not just a reference point, that can change model's prediction, also known as "minimum adversarial perturbation" in the literature (Goodfellow et al., 2014; Weng et al., 2018b).
Based on this idea, we define new evaluation criteria test the importance of a set of features. By computing the minimum adversarial perturbation on the complementary set of features that can alter the model's decision, we could test the degree of importance of the set. Although explicitly computing the importance value is NP-hard (Katz et al., 2017), Carlini & Wagner (2017) and Madry et al. (2017) showed that the perturbations computed by adversarial attacks can serve as reasonably tight upper bounds, which lead to an efficient approximation for the proposed evaluation.
Furthermore, we can derive a new explanation framework by formulating the model explanation to two-player min-max game between explanator and adversarial attacker. The explanator aims to find a set of important features to maximize the minimum perturbation computed by the attacker. This framework empirically performs much better than previous approaches quantitatively, with very inspiring examples.
To summarize contributions:
We define new evaluation criteria for feature-based explanations based on robustness anal- ysis. The evaluation criteria consider the worst case perturbations when a set of features are anchored, which does not introduce bias into the evaluation.
We design efficient algorithms to generate explanations that maximize the proposed crite- ria, which perform favorably against baseline methods the proposed evaluation criteria.
Experiments in computer vision and NLP models demonstrate that the proposed explana- tion can indeed identify some important features that are not captured by previous methods. Furthermore, our method is able to extract a set of features that contrasts the current pre- diction to target class.
2 ROBUSTNESS ANALYSIS FOR EVALUATING FEATURE-BASER EXPLANATIONS
2.1 PROBLEM NOTATION
Let consider the following setting: a general K-way classification problem with input space X' C IRd, output space y = {1,..., K). and a predictor function J x + y where f(x) denotes the output class for some input example x ( æa] E X. Then, for particular prediction f()) = despite the different forms of existing feature-based explanations ranging from attributing an importance value to each feature, ranking the features by their importance, to simply identify a set of important features, a common goal of them is to extract a compact set of relevant features with respect to the prediction.
2.2 EVALUATION THRROUGH ROBUSTNESS ANALYSIS
We note that however, given an explanation that identifies a set of said to be relevant features, how can we evaluate the quality of such explanation, or in other words, justify whether the distinguished features are truly relevant to the prediction? While one generally has no ground truth about the underlying true relevance of the features, recent studies take an axiomatic approach to define what properties the relevant features should hold and evaluate the explanations through verifying the identified relevant features satisfy the properties. One such properties that is widely adopted in the literature is to assume that the importance of a set of features corresponds to the degree of change removed from the original input. Nevertheless,
in prediction when the features in the previous section, the practice of approximating removal of features by setting their value to some reference point poses the risk of introducing bias in the evaluation. As result, to escape from the caveat, we follow a similar concept but propose two new criteria to evaluate the importance of features based on the following assumptions.
discussed
2

---

Under review as a conference paper at ICLR 2020
Assumption 1 When the values of the most salient features are anchored (fixed), perturbation the complementary set of features has weaker influence on the model's prediction. In other words, the model could tolerate larger degree of perturbation on the less important and non-anchored features.
Assumption perturbation is allowed on set of important features, small perturbation could easily change the model prediction even when we fix the values for the rest of the features.
Based on these two assumptions, we propose a new framework for evaluating explanations. The evaluation is based on the adversarial robustness when set of features are fixed, which is formally defined below.
Definition 2.1 The minimum adversarial perturbation norm on set of features S, which we will also name as Robustness-S, can be defined as:
= ==x = {min ||0| s.t. f(x + +6) + y, 8g = =3,
(I)
where 5 = U is the complementary set of features, and ög = 0 means that the perturbation value on features in S is constraint to be O.
Assume that we are given an explanation that partitions the input features into relevant set S, and an irrelevant set S,. Assumption implies that the quality of the relevant set can be measured by Ss - the robustness of irrelevant set when the relevant set is anchored. Specifically, Assumption infers that higher robustness on S, follows from a larger coverage of pertinent features in set S,; and thus an explanation is considered better if it Ieads to higher robustness against perturbation in ST. On the other hand, based on Assumption an explanation that has included important salient features in S, should lead to smaller robustness level on cs.- Therefore, Assumption and 2 build up our proposed evaluation criteria Robustness-S,, and Robustness-S, respectively, as listed below.
Robustness-S, measures the minimum adversarial distortion Es, when the set of important fea- tures S,, typically represented by the high-weight features in an attribution map, are anchored and perturbation is only allowed in low-weight regions. The higher the score the better the explanation. To measure Robustness-Sp.. we would need first determine the size of [S We can set [S,] the amount of anchors that an user is interested in or we may vary the size of [S,]| and evaluate the corre- sponding Robustness-S, at different points. By varying the size of S.,), we could plot an evaluation curve for each explanation and in turn measure the area under curve (AUC), which corresponds to the average Robustness-S3 S, at different sizes of relevant set.
Robustness-S, measures the minimum distortion distance es, when the set of important features S, are the only region that is perturbable, and the rest of feature values are anchored. Contrary to Robustness-Si lower scores on this metric indicate better explanation. We similarly define AUC of Robustness-S, as the average of Robustness-S, when we vary the size of |s
Evaluation Procedure Note that both Robustness- and Robustness-S, are sensitive to the car- dinality of S,. For instance, including all features in S, will make d 0. Therefore, we will only use these criteria to evaluate relevant sets with the same cardinality. For example, to evaluate feature attribution method that assigns weight with each feature, we can sort the features by the decending order of weights and then for each set of top-K features with K = 1, 1.2.... d, we evaluate Nobustness-5,(65 and plot curve. A larger (smaller) area under curve indicates better feature attribution ranking. (See examples in Figure 1).
Untargeted v.s. Targeted Explanation Definition 2.1 corresponds to the untargeted adversarial robustness perturbation that changes the predicted class to any label except y is considered as a successful attack. Instead of doing this, our formulation can also extend to targeted adversarial robustness, where we replace (1) by
ES.1 (min ||0|| s.t. f(x 0 t: =
where t is the targeted class. Using this definition, our approach will try to address the question "Why is this example classified as y instead of t", and the important features that optimize this criterion will highlight the contrast between class and t. We will give several interesting results in the experiment section.
3

---

Under review as a conference paper at ICLR 2020
Comparing to existing measurement The proposed criteria the first glance look similar to SSR- and SDR-based mcasurements. We note that, however, the key differences between our pro- posed criteria and SSR- (SDR-) based criteria are in two-folds: 1) Conceptually, to measure whether a set of features is important, instead of concerning the prediction change before and after removing consider whether perturbation
the features, prediction. 2) Practically, our proposed criteria allow us to eschew the difficulty of modeling feature removal as discussed in section 1. In fact, as most implementations of removal-basee criteria set the values of the features of interest to some fixed reference point, our criteria could be viewed as generalized versions where we consider all possible reference points by allowing perturbations in any directions. As a result, the proposed criteria enjoys a broader view of prediction behavior around the input, and in turn could capture a broader range of important features like the pertinent negative features in Dhurandhar et al. (2018), we shall show in the experiment section.
the feature values would significantly alter the
Robustness Evaluation under Fixed Anchor Set It is known that computing the exact minimum distortion distance in modern neural networks is intractable (Katz et al., 2017), so many different methods have been developed to estimate the value. Adversarial attacks, such as C&W (Carlini & Wagner, 2017) and PGD attack (Madry et al., 2017), aim to find a feasible solution of (1), which leads to upper bound of Cg- They are based on gradient based optimizers which are usually efficient. On the other hand, neural network verification methods aim to provide a lower bound of e'g ensure that the model prediction will not change within certain perturbation range (Singh al., 2018: Wong & Kolter, 2018: Weng et al., 2018:: Gehr et al., 2018; Zhang et al., 2018; Wang et al., 2018: Zhang et al., 2019). However, these methods are usually time consuming (often > 50 times slower than a backpropagation).
The proposed framework can be combined with any method that aims approximately compute (1), including attack, verification, and some other statistical estimations. However, for simplicity we only choose evaluate (1) by the state-of-the-art projected gradient descent (PGD) attack (Madry et al., 2017), since the verification methods are too slow and often lead to much looser estimation as reported in some recent studies (Salman et al., 2019).
3 NEW EXPLANATIONS TOWARDS OPTIMIZING THE CRITERIA
Given the new evaluation criteria, natural follow-up question is how to design explanations that optimize the measurements. Recall that under the proposed criteria the goal of an optimal expla- nation is to maximize (minimize) robustness-S, (robustness-S,) under the cardinality constraint on S,. Searching for such explanations thus leads to the following optimization problems, (3) for Robustness-S, and (4) for Robustness-S,:
maximize Sr) S.E(0.13
minimize (.E(0,1)a subject to
g(x,
(3)
(4)
subject to || S K,
||S/|lo S K,
where S() computes the value in Eq. (1), the minimum distortion distance when the features in set S, is not allowed to be perturbed, and K is a pre-defined size constraint on the set S,.
3.1 GREEDY ALGORITHM
Directly solving (3) and (4) is challenging since g is implicit function computed by solving (1) approximately, and furthermore, the discrete input constraint makes it intractible to find the optimal solution. As result, we propose greedy-styled algorithm, where we iteratively add the most promising feature into S. that optimizes the objective at each local step until S, reaches the size constraint. In other words, we initialize the S, as empty, and sequentially solve the following subproblem at every step t:
arg max g( Ui), or arg min g( Ui), Vi e S,
where St. is the anchor set at step t, and S = 6. We repeat this subprocedure until the size of set St reaches K. We name this method as Greedy. A straightforward way for solving (5) is to exhaustively search over every single feature. However, considering a single feature at a time ignores the correlation between features, which tends to introduce noise (see experimental results). If
4

---

Under review as a conference paper at ICLR 2020
Explanations Grad
IG
SHAP
LOO
BBMP
Reg-Greedy
Greedy
One-Step Reg
Robustness-S Sr 88.00
85.98
75.48
76.59
81.31
98.01
83.57
86.37
Robustness-S.
91.72
91.97
101.49
98.82
173.90
82.81
171.56
83,59
Table I: Area under curve of the proposed criteria for various explanations MNIST. The higher the better for Robustness-S,, ;,; the lower the better for Robustness-S,, Robustness measured with (1).
consider multiple features a single step, searching over all possible combinations will become intractable. For example, considering all possible conbinations of two features requires (dd) evaluations of function g at every step. To consider the joint influence between features efficiently, we propose a smoothed regression version of solving (5) in the following subsection.
3.2 REGRESSION GREEDY
As considering the correlation between features by searching over all possible subsets of Sy at every step is computationally infeasible, we instead propose to approximate the function y by learning mapping from the binary space of {0, 13 where ones indicate the inclusion of corresponding feature indices and zeros otherwise, to their resulting function value g(z, {0, 1)at. Specifically, we can sample subset Q {0, 1 ]d and then consider the following linear regression:
w" arg argmiin min 60
Exeo
(w" (w g(xx2))² 2))
(6)
After the regression is learned, we can treat the coefficients w that correspond to each feature as their approximated effect on the function value of 9 when they are included into the set S,.. By learning such regression where we sample from the possible subsets, we are able to capture the joint relationships between features, and as well smooth out possible noises. In fact, the greedy approach can be viewed as a special case of Reg-Greedd where the sampled subset Q, in (6), in each iterative step contains exactly the one-hot encoded vectors with the "on" indices correspond to the remaining feature indices. That is, each one-hot vector indicates the inclusion of corresponding single feature into the relevant set. In this case, the coefficients of the learned linear regression would be equivalent to the difference in objective value before and after the corresponding feature is included into the relevant set. To take into account feature interactions, Reg-Greedy samples from the whole distribution of {0, 1)dd where most of the sampled vectors in Q contains multiple "on" indices. In this way, the learned regression captures feature correlations on the objective value and could smooth out possible noises encountered by greedy. There has been a great line of research on studying the interaction between features including the well-known Shapley value which tackles the problem through cooperative game theory perspective. And Lundberg & Lee (2017) proposed a way to use regression with a special kernel to approximate the Shapley value. However, sampling from the whole distribution of {0. 1) ] could still incur exponential complexity, and using only a reasonable amount of samples might not be able to precisely capture the behavior of the highly non- linear objective function g. Therefore, we propose the Regression Greedy (Reg-Greedy approach, where we still run greedy steps to incrementally add indices to St. but each iteration we run this regression and use the weights to decide which index to be added to S Note that at each step the samples Q must be in restricted domain, where indices that already chosen in St should be and we sample 0/1 only for the rest of the indices. We distinguish Reg-Greedy from one- step regression (One-Step Reg) which directly determines the importance of each feature by merely solving (6) once. By combining regression in a greedy procedure, we are able to gradually narrow down our sampling space (by sampling only from restricted domain), focusing on the feature interactions between remaining features and the ones that are already added into the relevant set. This enables us to find from the remaining features that have the greatest interaction with the current relevant set, and could in turn maximally optimize the objective value when added into the relevant set. In practice, a sample complexity of (d) for learning the regression could generally work well.
4 EXPERIMENTS
We present both qualitative and quantitative comparisons in the experiments. For || - Ilp in (1) and (2), we consider p = 2, i..., the &, norm for all experiments. In quantitative results, including eval- uation curves and the corresponding AUC, we report the average over 50 random examples. For
5

---

Under review as a conference paper at ICLR 2020
340
2.-
8
SIAP LOC3
22
8
2.9
175
14
15
13
25
23
25
Figure Different Robustness-S, (left) with varying |S,| and Robustness-S, (right) with varying |.,|- For Robustness-S, (left), the higher the better; for Robustness-S, (right), the lower the better. We omit points in the plot with value too high fit the scale of y-axis.
Figure 2:
Visualization on our proposed methods. The top features selected by Reg- Greedy are less noisy.
Explanations
Grad
IG
SHAP
LOO
BBMP
Reg-Greedy
Greedy
One-Step Reg
Robustness-33 Sp 27.13
26.01
18.25
23.54
22.60
31.62
21.16 58.45
24.54
Robustness-S. S, 45.53
46.28
60.02
52.77
154.14
43.97
47.07
Table 2: Area under curve of the proposed criteria for various explanations ImageNet. The higher the better for Robustness-S,; the lower the better for Robustness-S5 Robustness measured with (I).
Explanations
Grad
IG
SHAP
LOO
ВBMP
Reg-Greedy
Insertion
250.81
262.74
200.50
192.44
102.53
379.15
Deletion 281.88
273.71
362.68
442.65
527.80
159.77
Table 3: Area under curve of the Insertion and Deletion criteria for various explanations MNIST. The higher the better for Insertion; the lower the better for Deletion.
Explanations
Grad
IG
SHAP
LOO
BBMP
Reg eeg-Greedy
Rank Correlation
0.3001
0.3042
0. 100
0.4966
0.1775
0.1835
Table 4: Rank correlation between explanations with respect to original and randomized model.
the proposed algorithms, we consider Reg-Greedy (See 3.2), One-Step Reg (Sec 3.2) and Greedy (Sec 3.1). For other baselines include vanilla gradient (Grad) (Shrikumar al., 2017) and in- tegrated gradient (IG) (Sundararajan et al., 2017) from gradient- based approaches; leave-one-out (LOO), or occlusion-1, (Zeiler & Fergus, 2014; Li al., 2016) and SHAP (Lundberg Lee, 2017) from perturbation- (BBMP) (Fong Vedaldi, 2017) from SSR/SDR -ased approaches. We perform our experiments on two image datasets, MNIST and ImageNet, as well as a text dataset YahooAnswers.
approaches (Ancona et al., 2018), and black-box meaningful perturbation
4.1 QUANTITATIVE ANALYSIS ACROSS DIFFERENT EXPLANATIONS
The proposed measurements: Robustness-5, and Robustness-S,. We compare different expla- nations under the two proposed criteria, robustness-St S, and robustness-S,. and plot their evaluation curves respectively. For ease of comparison, we calculate the area under curve (AUC) for each cor- responding evaluation. We list the results in Table 3, and leave the plots in appendix A. As shown in Table 3, under both criteria, comparing to regression-basee methods, the pure greedy method usu- ally suffers degraded performances that could be due to the ignorance of feature correlations, which ultimately results in the introduction of noise shown in Figure 2. Furthermore from the table, method consistently outperforms others on both crite-
observe that the proposed regression-gress ria. On one hand, this suggests that the proposed algorithm indeed successfully optimizes towards the criteria; on the other hand, this might indicate the proposed criteria do capture different charac- teristics of explanations which most of the current explanations do possess. Another somewhat

---

Under review as a conference paper at ICLR 2020
Targel:
Target:
Original
Groedy
7
7
Input
Target:
Target: 2
/
9
Input
Target:
Target:
Figure 3: Visualization on top 20 percent relevant features provided by existing explanations.
Figure 4: Visualization of targeted explanation. In each row, we highlight relevant regions explaining why the input is not predicted as the target class.
LRP
Ageinet
Against
Against
Againsst2
N/A
N/A
Figure 5: Comparisons between different targeted explanations against different targeted class on MNIST.
interesting finding from the table that while vanilla gradient has generally been viewed as a base- line method, it nonetheless performs competitively on the proposed criteria. To investigate deeper into such observation, we shall visualize the explanations in the following subsection. For simplic- ity will just apply Reg-Greedy with Robustness-S,, criterion in the qualitative comparisons with previous methods.
Existing commonly adopted measurements: Insertion and Deletion. Indeed, might not be surprising that Reg-Greedy achieves the best performances the proposed criteria it is explicitly designed to optimize. To more objectively showcase the usefulness of the proposed explanation, compare Reg-Greedy with other explanations existing commonly used quantitative measure- ments. Particularly, we adopt the Deletion and Insertion criteria proposed by Petsiuk et al. (2018), (2016).
which are generalized variants of the region perturbation criterion presented in Samek The Deletion criterion measures the probability drop in the predicted class as top-relevant features, indicated by the given explanation, are progressively removed from the input. On the other hand, the Insertion criterion measures the increase in probability of the predicted class as top-relevant fea- tures are gradually revealed from the input whose features are originally all masked. Similar to our proposed criteria, quick drop (and thus small area under curve) or a sharp increase (that leads to a large area under curve) in Deletion and Insertion respectively suggest good explanation as the selected top-important features could indeed greatly influence the prediction. In the experiments, we follow Samek et al. (2016) to remove features by setting their values to randomly sampled val- ues. We plot the evaluation curves and report corresponding AUCs in Figure 12 and Table 3. On these additional two criteria, we observe that our proposed method consistently performs favorably against other explanations.
Sanity Check. As pointed out in recent literature that appropriate explanation should at least be loosely related the model being explained (Adebayo et al., 2018), to ensure that our proposed expla- nation does indeed reflect the model behavior, conduct the sanity check proposed by (Adebayo et al., NeurIPS' 18) to check if our explanations are adequately different when the model parameters randomly re-initialized. In the experiment, randomly re-initialize the last fully-connected

---

Under review as a conference paper at ICLR 2020
layer of the neural network model. We then compute the rank correlation between explanation com- puted w.r.t. the original model and that w.r.t. the randomized model. From Table 4, we observe that Reg- eeg-Greedy has a much lower rank correlation comparing to Grad, IG, and LOO, suggesting that Beg-Greedy is indeed sensitive to model parameter change and is able to pass the sanity check.
4.2 QUALITATIVE VISUALIZATIONS
Visualized Explanations on MNIST. Figure 3 illustrates the top features identified by various explanation methods. From this figure, we observe that Gradient, IG, SHAP mainly highlights the white pixels in the digit, while gradient and IG are more noisy compared to SHAP. In the con- trary, Reg-Greedy focuses on both the "crucial positive" of the digits "pertinent negative" of regions around the digit. For example, in the first row, a 7 might have been predicted as 4 or 0 if the pixels highlighted by Reg-Greedy are set to 1. Similarly. 1 may be turned to a 4 or 7 given additional white pixels to its left, and a 9 may become 7 if deleted the lower circular part of its head. As a re- sult, Reg-Greedy focuses on "the region in which perturbing will lead to easier prediction change", which includes both the crucial positive pixels and pertinent negative pixels, and provides additional insights that are not captured by the baseline explanations. The superiority of Reg-Greedy is also validated by the better performance on the Robustness-55 S, score.
Targeted Explanation. Recall that in section 2.2, we discussed about the possibility of defining the robustness measurement by considering a targeted distortion distance as formulated in (2). Here, we provide examples, as shown in Figure 4, where we answer the question of "why the input digit is an A but not a B" by defining a targeted perturbation distance towards class B as our robustness measurement. In each row of the figure, we provide targeted explanation towards two different target classes for a same input image. Interestingly, as the target classes changes, the generated explanation varies in an interpretatble way. For example, in the first row, we explain why the input digit 7 is not classified as 9 (middle column) or a 2 (rightmost column). The resulting explanation against 9 highlights the upper-left part of the 7. Semantically, this region is indeed pertinent to the classification between 7 and 9, since turning on the highlighted pixel values in the region (currently black in the original image) will then make the resemble a 9. However, the targeted explanation against 2 highlights very different but also meaningful region, which is the lower-right part of the 7; since adding a horizontal stroke on the area would turn a into a 2. This finding demonstrates special characteristic of our explanation which cannot be easily found in most of the existing methods.
While the capability of capturing not only the crucial positive but also the pertinent negative features have also been observed in some recently proposed explanations such as Layer-wise Relevance Propagation (LRP) (Bach et al., 2015), as reported in Samek et al. (2016), as well as the explanation technique proposed in Oramas et al. (2019). Both of the above mentioned methods are not explicitly designed to handle the targeted explanation task which attempt to answer the question "what are the important features that lead to the prediction of class A but not class B", and thus has different limitations. For example, the ability of LRP to capture pertinent negative features in fact heavily depends on the input range. In Samek et al. (2016) where inputs are normalized to have zero mean and a standard deviation of one, the black background will have non-zero value, and LRP would have non-zero attributions on the black background pixels which allows the explanation to capture pertinent negative features. However, as later shown in Dhurandhar et al. (2018) 8), if the input pixel intensity is normalized into the range between 0 and (where background pixels have the values 0), LRP failed to highlight the pertinent negative pixels, as background would always have zero attribution (since LRP is equivalent multiplication between Grad and input in a Rectified Linear Unit (ReLU) network as shown in Ancona et al. (2018)). In Oramas et al. (2019), unlike our targeted explanation where we know exactly which targeted class the explanation is suggesting against (and by varying the targeted class we observe varying corresponding explanation given), their method by design does not convey such information. The pertinent negative features highlighted by their method by construction is not directly related to specific target class, and users in fact need to infer what target class the pertinent negative features are preventing against. To further grasp the difference, we compare our explanation with theirs in Figure 5 (we borrow the results from Oramas et al. (2019) for visualization of their method). Qualitatively, we also observe that our method seems to be giving the most natural explanations. For example, in the first row of left image where the highlighted features are against the class 0, in addition to the left vertical gap (which when presence would make 2 looks like a 0) that is roughly highlighted by all three methods, our method is the
8

---

Under review as a conference paper at ICLR 2020
Originl
Grad
10
LOO
BAMP
SHAP
Pin Greeddy
Input
of cleats I get. High Mid--out: am playing on the line?
Greedy
of footbell(s) Bleatsj0) Ahouldded get. High Cun[z] or Mid- out [B] am playing on the line?
Grad
of footballis éleatsis) should bot Hightt] Cut or Mii--out. am playing!il on the line?
of football(1] Rloatsi0) get. High
Cut Mid--out out.. (44 am[2] playing anjil the line?
Figure 7: Explanations text classification Figure 6: Visualization of different explanations model where the predicted label for this sen- ImageNet, where the predicted class for each input is "fish", "bird", "dog", and "sea lion".
tence is "sport".
only one that highlights the right tail part (green circled) of the digit 2 which might also serve as crucial evidence against O. Furthermore, as we change the targeted class to (the second row), while LRP seems to be providing similar explanations, we observe that explanation has drastic change and highlights the green circled part which when turned off will make becomes a 7. These results might suggest our method is more capable of handling such targeted explanation task.
Visualized Explanations on ImageNet. On ImageNet, quantitatively on both of the proposed criteria. We plot the evaluation curves (in appendix A), and compute the corresponding AUC, listed in Table 2. In general, observe similar trends as the experiments shown in MNIST. In particular, Reg- ergedyy enjoys an overall superior performances than existing explanations qualitatively demonstrate that our method provides more compact explanations that focuses more on the actual object being classified.
well compare different explanations
the criteria. In addition, several visualization results in Figure also
Text Classification. We demonstrate how explanation method could be applied to text clas- sification models. Note that a length-n sentence is usually represented by n embedding vectors, and thus when applying vector to the set S, and choose the one with largest reward. Since there are only at most n choices, the Greedy algorithm doesn't ' suffer much from noise and has similar behavior with Reg-Greedy.
Greedy algorithm, at each iteration will try to add each embedding
We perform experiments on an LSTM network which learns to classify a given sentence into one of the ten classes (Society, Science, Health, ... We showcase an example with explanations gen- erated with different methods in Figure 7. We note that although the top-5 relevant keyword sets generated by the three methods do not vary much, the rankings within the highlighted keywords for each explanation are in fact different. We observe that our method Greedy tends to generate expla- nation that matches human intuition the most. Particularly, to predict the label of "sport", one might consider "cleats", "football", and "cut" as the strongest indications towards the concept "sport".
5 RELATED WORK
Our work proposes objective measurement of fcature-based explanation by measuring the "mini- mum adversarial perturbation" adversarial literature, which is estimated by adversarial attack. We provide necessarily incomplete review related works in objective measurement of explanations and adversarial robustness.
Objective Measurements for Explanations Evaluation of explanations has been a difficult prob- lem mainly due to the absence of ground truth (Ancona et al., 2018; Sundararajan et al., 2017). Although one could rely on human intuitions to assess the quality of the generated explanations (Lundberg & Lee, 2017; Doshi-Velez & Kim, 2017), for example, judging whether the explanation focuses on the object of interest in an image classification task, these evaluations subject human perceptions are prone to fall into the pitfall of favoring user-frient user-friendly explanations, such attribu- tions that visually aligns better with the input image, which might not reflect the model behavior (Adebayo et al., 2018). As result, in addition to subjective measurements, recent literature has also proposed objective measurements, which is also called functionally -rouuddd evaluations (Doshi- Velez & Kim, 2017). We roughly categorize existing objective measurements into two families.

---

Under review as a conference paper at ICLR 2020
This first family of explanation evaluation is called fidelity-basedd measurement. This includes that Completeness or Sum to Delta which requires the sum of attributions to equal the prediction difference of the original imput and baseline (Sundararajan sensitivity-n which further generalizes completeness to any subset of the feature (Ancona et al., 2018); local accuracy Ribeiro al. (2016); Lundherg & Lee (2017); and infidelity which is frame- work that encompasses several (Ych et al., 2019). The general philosophy for this line of methods is to require the sum of attribution value faithfully reflect the change in prediction function value given the presence or absence of certain subset of features. The second family of explanation evaluation are removal-basse -based and preservation- based measurements, which focus on identifying the most im- portant set of features with respect to a particular prediction. The underlying assumption made is that by removing the most (least) salient feature, the resulting function value should drop (increase) the most. (Samek et al., 2016) proposed this idea as an evaluation to evaluate the ranking of feature- attribution score. Later on, Fong & Vedaldi (2017) derive explanations by solving an optimization problem to optimize the evaluation. And Dabkowski & Gal (2017) proposed to learn the explanation generating process by training an auxiliary model.
al., 2017; Shrikumar al., 2017);
We note the implicitly in the evaluation process of both fidelity and removal (preservation) based measurement involves computing the change in function value given some set of features being ab- sent. However, it is difficult carefully model the concept of feature absence in practice, as most models by construction are not able to handle inputs with real missing features. As a result, previous work has compromised by using approximation This includes setting the values of the features to be removed by zero (Ancona et al., 2018; Sun- dararajan al., 2017) or the mean value (Lundberg & Lee, 2017). blurred value (Fong & Vedaldi, 2017), random value (Samek et al., 2016; Dabkowski & Gal, 2017), or more advanced generative model that attempts to model the given data distribution (Chang et al., 2018). Unfortunately, such approximations that represent feature absence by setting the their values to some predefined distribu- tion would inevitably introduce bias into the evaluation process. With the presence of this inherent caveat, we are thus inspired to adopt another angle to tackle the explanation problem.
estimate the effect of removing certain features.
Adversarial Robustness Adversarial robustness has been extensively studied in the past few years. The adversarial robustness of machine learning model on a given sample can be defined as the shortest distance from the sample to the decision boundary, which corresponds to our definition in (I). Algorithmss have been proposed for finding adversarial examples (feasible solutions of (1)), including (Goodfellow et al., 2014; Carlini & Wagner, 2017: Madry et al., 2017). However, those algorithms only work for neural networks, while for other models such as tree hased models or near- est neighbor classifiers, adversarial examples can be found by decision based attacks (Brendel et al., 2017: Cheng et al., 2018: Chen al., 2019). Therefore the proposed framework can also be used in other decision based classifiers. On the other hand, several works aim to solve the neural network verification problem, which is equivalent to finding a lower bound of (1), Examples include (Singh et al., 2018; Wong & Kolter, 2018; Zhang et al., 2018). In principal, our work also apply these verification methods for getting an approximate solution of (1), but in practice they are very slow to run and often gives loose lower bounds on regular trained networks.
Our work is also closely related to related works that consider the question "For situation A, why was the outcome B and not C", which we call counterfactual explanations. Xu al. (2018) add group sparsity regularization to adversarial attack to enforce semantic structure for the perturbation, which is more interpretable. Ribeiro et al. (2018) find set of features that once fixed, probability of the prediction is high when perturbing other features. Goyal et al. (2019) show how one could change the input feature such that the system would output a different class, where the change is limited to replacing a part of input feature by part of an distractor image. Dhurandhar et al. (2018) consider the pertinent negative in a binary setting by solving a carefully designed loss function.
CONCLUSION
In this paper, we establish the link between a set of features to a prediction with a new evaluation criteria, robustness analysis, which measures the minimum tolerance of adversarial perturbation. Furthermore, we develop a new explanation method to find important set of features to optimize this new criterion. Experimental results demonstrate that the proposed new explanations are indeed capturing significant feature sets across multiple domains.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Julius Adebayo, Justin Gilmer, Michael Muelly, lan Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in Neural Information Processing Systems, pp- 9525-9536, 2018.
Marco Ancona, Enea Ceolini, Cengiz Oztireli, and Markus Gross. A unified view of gradient- based attribution methods for deep neural networks. International Conference on Learning Representa- lions, 2018.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus- Müller, and Wojciech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e0130100, 2015.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv:1712.04248, 2017.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39 57. IEEE, 2017.
Chun-Hao Chang, Elliot Creager, Andrew A. Goldenberg, and David Kristjanson Duvenaud, Ex- plaining image classifiers by counterfactual generation. In ICLR 2019, 2018.
Hongge Chen, Huan Zhang, Duane Boning, and Cho-Jui Hsieh. Robust decision trees against ad- versarial examples. In ICML, 2019.
Minhao Cheng,
Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization- based approach. arXiv preprint WrXiv:1807.04457, 2018.
Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. In NIPS, 2017.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances Neural Information Processing Systems, pp. 592-603, 2018.
Finale Doshi- Velez and Been Kim. Towards rigorous science of interpretable machine learning. arXiv preprint arXiv:1702. 780200800, 2017.
Ruth C. Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful pertur- bation. 2017 IEEE International Conference Computer Vision (ICCV), pp. 3449-3457, 2017.
Timon Gehr, Matthew Mirman, Dana Trachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Mar- tin Vechev, Ai2: Safety and robustness certification of neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh, and Stefan Lee. Counterfactual visual explanations. In International Conference on Machine Learning, pp. 2376-2384, 2019.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An
efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
Pang Wei Koh and Perey Liang. Understanding black-box predictions via influence functions. In International Conference Machine Learning, pp. 1885-1894, 2017.
Jiwei Li, Will Monroe, and Dan Jurafsky. Understanding neural networks through representation
erasure. CoRR, Abs.026 2016. URL
08200.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pp. 4765-4774, 2017.

---

Under review as a conference paper at ICLR 2020
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint urXiv:1706.060s.. 2017.
Jose Oramas, Kaili Wang. and Tinne Tuytelaars. Visual explanation by interpretation: Improving visual feedback capabilities of deep neural networks. In International Conference on Learning Representations, 2019. URL https: wwoooppervviiiiee net. ftte//formmiiiiiii z jc5Fm.
Vitali Petsiuk, Abir Das, and Kate Saenko. Rise: Randomized input sampling for explanation of black-box models. arXiv preprint arXiv:1806.07421, 2018.
Gregory Plumb, Denali Molitor, and Ameet Talwalkar. Model agnostic supervised local explana- tions. In Advances in Neural Information Processing Systems, pp. 2515-2524, 2018.
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 Data Mining, pp. 1135-1144 144. ACM, 2016.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: ffigh-precision model-agnostic explanations. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Hadi Salman, Greg Yang, Huan Zhang. Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robust verification of neural networks. arXiv preprint arXiv: 08022, 2019.
Wojeiech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus-Robert Müller. Evaluating the visualization what a deep neural network has Iearned. IEEE transactions neural networks and learning systems, 28(11):260-22773 2016.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. International Conference Machine Learning, 2017.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp- 10802-10813, 2018
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, 2017.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pp. 6367- 6377, 2018.
Tsui- Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Bon- ing, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5273-5282 2018a.
Tsui- Wei Weng, Huan Zhang. Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. arXiv preprint arXiv: 118.0110577 2018b.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5283-5292, 2018.
Kaidi Xu, Sijia Liu, Pu Zhao, Pin-Yo Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus, Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability.. arXiv preprint arXiv:1800 01664. 2018.
Chih-Kuan Yeh, Cheng- Yu Hsich, Arun Sai Suggala, David I. Inouye, and Pradeep Ravikumar, On the (in)fidelity and sensitivity for explanations. CoRR, abs/1 M0s/1901..e 00992, 2019.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference computer vision, pp. $18-833. Springer, 2014.
12

---

Under review as a conference paper at ICLR 2020
Huan Zhang, Tsui-We Weng. Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural net- work robustness certification with general activation functions. In Advances in neural information processing systems, pp. 4939-4948, 2018.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsieh. Recurjac: An efficient recursive algorithm for bounding jacobian matrix of neural networks and its applications. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5757-5764, 2019.
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai- Wei Chang. Men also like shopping: Reducing gender bias amplification using corpus-level constraints. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 2979-2989,
2017.
13

---

Under review as a conference paper at ICLR 2020
A EVALUATION CURVES
239
Percot 0206
Figure& 8: Comparisons between our proposed methods under different criteria. From left to right: untargeted Robustness-Sp, targeted Robustness-2 Sr untargeted Robustness- targeted Robustness- Sr. We omit points in the plot with value too high to fit in the scale of y-axis.
POTUEE220 22 HARO WEw.AAALOOOO
Parortage Hakward wed.raaaantttttttttttttt Cat.anaan
Figure 9: Comparisons between proposed methods and existing explanations under different cri- teria. From left to right: untargeted Robustness-S,. targeted Robustness-S, untargeted Robustness- S,, targeted Robustness-S,.. We omit points in the plot with value too high fit in the scale of y-axis.
0.64
Perertaze Pidear 7100
Perortaar of Pide Puture---aa
Perortaac Pwdwaan www.urrr--d
Figure 10: Comparisons between our proposed methods under different criteria ImageNet. From left to right: untargeted Robustness-S,, targeted Robustness-S -S, untargeted Robustness-Se targeted Robustness-S,. We omit points in the plot with value too high fit in the scale of y-axis.
Nepcleet/
150
D. 5. Pecertaze Pndearn 7230
Necertaze Pndearr Fult
Netortaac Fedewart FesteeddEa
3.
Figure 11: Comparisons between our proposed methods under different criteria on ImageNet. From left to right: untargeted Robustness-S,.. targeted Robustness-S3 SS, untargeted Robustness-S,, targeted Robustness-S.. We omit points in the plot with value too high fit in the scale of y-axis.
14

---

Under review as a conference paper at ICLR 2020
B EVALUATION ON EXISTING OBJECTIVE MEASUREMENTS
Output Logits (pre-softnaa)
Reg-tready
Ourput Logits (pre-sofhmaa)
15.0
SHAP
LOO
10.0
5.0
25
40 45
10 15
20
25
30
25
43
Percentage Relevant Features Inserted (151)4)
Percentage of Relevant Fectures nemoved (1514)
Comparisons between explanations under different criteria change in output logits as relevant features are inserted into the input. Right figure: change in output logits as relevant features are removed from the input.
Figure 12:
MNIST. Left figure:
Explanations
Grad
IG
SHAP
LOO
BBMP
Reg-Greedy
Insertion
250.81
262.74
200.50
192.44
102.53
379.15
Deletion
281.88
273.71
362.68
442.65
527.80
159.77
Table 5: Area under curve of the Insertion and Deletion criteria for various explanations on MNIST. The higher the better for Insertion; the lower the better for Deletion.
C T-TEST ON AUC
Explanations
Grad
IG
SHAP
LOO
BBMP
Rohustness-S,
win
win
win
win
win
Robustness-S.
win
win
win
win
win
Table 6: The proposed Reg-Greed versus other explanations on MNIST under our proposed criteria with Student's 1-test 95% confidence level.
Explanations
Grad
IG
SHAP
LOO
BBMP
Insertion
win
Deletion
win
win
win
win
win
Table 7: The proposed Reg-Greedy versus other explanations on MNIST under Insertion and Dele- tion criteria with Student's 's r-test at 95% confidence level.
D SANITY CHECK
Explanations
Grad
SHAP
LOO
BBMP
Reg-Greedy
Rank Correlation
0.3001
0.3042
0.1108
0.4966
0.1775
0.1835
Table 8: Rank correlation between explanations with respect to original and randomized model.
15

---

Under review as a conference paper at ICLR 2020
E
COMPARISONS ON TARGETED EXPLANATION
Ours
LRP
Oramas et al.
Ours
LRP
Oramas al.
Against 0
Against 4
Against7
Against
N/A
N/A
Figure 13: Comparisons between different targeted explanations against different targeted class on
MNIST.
F HEATMAP VISUALIZATION ON MNIST
Original
Grad
IG
LOO
BBMP
SHAP
Reg-Greedy
7
7
9
9
Figure 14: Heatmap Visualization of different explanations on MNIST.
16


Reviews:
[{"review_id": "ryxIu2xOqS", "reviewer": "AnonReviewer4", "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": "SUMMARY\n\nThe authors propose an intuitive new measure (definition 2.1) of feature importance based on a robustness criterion (with two variants of equations 3 and 4). Two optimisers are proposed for finding the most important features according to this measure, in order to explain why a classifier is making a certain prediction.\n\nThe experiments are both qualitative (showing pixel-wise importance maps for image problems) and quantitative (showing how well the various feature importance scoring algorithms do albeit on the measure explicitly optimised by the new proposed algorithms).\n\nCOMMENTS\n\nThe paper organisation is clear enough though the English needs a little work to make it read really nicely.\n\nThe proposed measures are natural and intuitive. Especially the Robustness-$\\hat{S_r}$ is an interesting twist on the more obvious Robustness-$S_r$.\n\nWhile the measures are interesting, the justification for them is somewhat weak. This amounts to \n\n1) Quantitative experiments which seem to only test how well each method works in relation to the very metric which only your proposed method directly optimises - this is nice but not surprising. Also, the way you define the AUC of your measure seems a little strange. I don't know why different baselines appear in different comparisons as in e.g. tables 1 and 2. Finally your curves in appendix A don't seem to have the same number of points for each method in all cases? \n\n2) Qualitative examples with images and text. These are nice, but alas only qualitative. Also, it seems as though not all baselines are included in all examples (even figures 3 and 5, which are analogous, include different baselines). \n\nIt seems like the paper needs either 1) a quantitative evaluation that is not subjective. Surely, the evaluation metric should not match the (novel) objective of the proposed method? Or, 2) a theoretical result in support of the new measures.\n\nThe Reg-Greedy algorithm is a major contribution of this paper, but receives very little explanation. Indeed, perhaps the clearest quantitative statement of the paper is that Reg-Greedy beats Greedy. Is this a common method for optimising w.r.t. a subset? Is it similar to other methods? I felt that Reg-Greedy is a really nice idea but the paper did not do it justice.\n\nDETAILS\n\nPerhaps unifying (3) and (4) by defining a single g that subsumes both cases would be neater.\n\nPlease define g in equation (1) rather than in words after equation (4).\n\nIt should be S_r in the subscripts of (3) and (4)\n\n\"Crutial\" spelling\n\nFINALLY\n\nI'm open to be swayed on any of the above points, pending the author feedback.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1l10XwCtS", "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": "\n\nThe manuscript proposes a method for model explanation and two metrics for the evaluation of methods for model explanation based on robustness analysis. More specifically, two complementary, yet very related, criteria are proposed: i) robustness to perturbations on irrelevant features and ii) robustness to perturbations in relevant features. Moreover, different from existing works which defined the perturbation values following different somewhat-fixed procedures, the proposed method aims at allowing perturbations in any directions.\n\nA greedy algorithm optimizing these criteria is proposed in order to produce a method able to highlight important features of the input and justify/explain model predictions.\nIn addition, the proposed robustness criteria are used as metrics to assess the performance of methods for model explanation.\n\nExperiments on models addressing image classification and text classification, shows the performance of the proposed method w.r.t. existing work.\n\nThe manuscript has a good flow, and its content is easy to follow. The proposed method is sound, well motivated, and very well founded. The formal presentation of the proposed method is good. I appreciate the fact that evaluation covers different modalities of data, i.e. text and images.\n\nMy main criticism over the manuscript is the following:\n\nIn Sec. 3.3, when describing the first criterion, it is stated that the size |S_r|, i.e, the amount of anchors, could be defined by the used. In my opinion, this may not be applicable since in theory the amount of relevant/irrelevant features is unknown before hand. In that case the proposed AUC-based method seems more adequate. Could you comment on this?\n\n\nIn  Sec. 3, a pre-defined size K is introduced. Later in Sec. 3.1 it is stated that the greedy algorithm uses this size as a stopping criterion for the optimization of the proposed robustness criteria. Could you indicate how this size K is defined in practice? Is there a principled way to define it? What is the effect of this parameter on the performance of the proposed method? An ablation study focused on this parameter would provide further insights into the inner workings of the proposed method and would improve the manuscript.\n\n\nIn Sec.4 it is stated that only 50 random examples are considered when reporting results. When comparing the performance across the different methods, are these random 50 examples fixed or always re-sampled? Also, given the size of the considered datasets, where the number of images in their test sets is in the order of the thousands, it is hard to grasp how representative are the reported results?\n\nIn the same paragraph discussed above, it is mentioned that the GRAD method performs competitively on the proposed criteria. It might be interesting to further positioning the proposed method w.r.t. GRAD. Given the comparable performance achieved by GRAD and its relative simplicity, it would be hard to motivate why not choose GRAD instead of the proposed method? Could you provide some discussion on this?\n\nIn Sec.4 (pag. 6) it is stated the the proposed regression-greedy method outperforms other methods in these criteria. In my opinion this trend shouldn't be surprising given the fact that the proposed method is specifically optimized on such criteria as it is clearly stated by the title of Sec.3.\n\nFig.3 and Fig.4 display binary images indicating the top-n features selected by different methods. Perhaps it would be more informative to have a heatmap highlighting/grading the entire input space. This may throw more light on the performance of the compared methods.\n\nIn Adebayo et al., NIPS'18 (and very related efforts), there are presented a set of sanity checks to be applied to explanation methods to ensure their predictions are relate to the class and model being predicted. Could you provide any indication on whether the proposed method passes these checks?\n\nIn Sec.4 (visualization) it is stated that the proposed method effectively highlights crucial positive pixels as well as pertinent negative pixels. A similar capability has also being reported earlier in Samek et al., Trans NNLS'16 and Oramas et al. ICLR'19. Since the visualization analysis (discussed in pag.6) focuses exclusively on this capability. There should be a comparison between the proposed method and the two mentioned works.\n\n", "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 carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an approach for finding an explainable subset of features by choosing features that simultaneously are: most important for the prediction task, and robust against adversarial perturbation. The paper provides quantitative and qualitative evidence that the proposed method works.

The paper had two reviews (both borderline), and the while the authors responded enthusiastically, the reviewers did not further engage during the discussion period.

The paper has a promising idea, but the presentation and execution in its current form have been found to be not convincing by the reviewers. Unfortunately, the submission as it stands is not yet suitable for ICLR.
Decision: Reject