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

Abstract: Feature based explanations, that provide importance of each feature towards the model prediction, is arguably one of the most intuitive ways to explain a model. In this paper, we establish a novel set of evaluation criteria for such feature based explanations by robustness analysis. In contrast to existing evaluations which require us to specify some way to "remove" features that could inevitably introduces biases and artifacts, we make use of the subtler notion of smaller adversarial perturbations. By optimizing towards our proposed evaluation criteria, we obtain new explanations that are loosely necessary and sufficient for a prediction. We further extend the explanation to extract the set of features that would move the current prediction to a target class by adopting targeted adversarial attack for the robustness analysis. Through experiments across multiple domains and a user study, we validate the usefulness of our evaluation criteria and our derived explanations.

Published as a conference paper at ICLR 2021
EVALUATIONS AND METHODS FOR EXPLANATION THROUGH ROBUSTNESS ANALYSIS
Cheng- Yung-Yuudee Hsieh ; Chih-Kuan Ych², Xuanqing Liu², Pradeep Ravikumar', Seungyeon Kim Sanjiv Kumar", Cho-Jui Hsieh
Paal G. Allen School of Computer Science, University of Washington Machine Learning Department, Carnegie Mellon University
3 *Department of Computer Science, UCLA
*Google Research
cydhs iissieen ehêcs. washi washington. ingtinntoo.dn {ejyeh, pradeepr)@cs caraa.mm.eeeee edu. xqliuêcs, ucla. edu, {seungyeonk, janjivk]@google. con. chohsichêcs wwla.cllcooo edu
ABSTRACT
Feature based explanations, that provide importance of each feature towards the model prediction, is arguably one of the most intuitive ways explain model. In this paper, we establish a novel set of evaluation criteria for such feature based explanations by robustness analysis. In contrast to existing evaluations which require us to specify some way to "remove" features that could inevitably introduces biases and artifacts, we make use of the subtler notion of smaller adversarial perturbations. By optimizing towards our proposed evaluation criteria, we obtain new explanations that are loosely necessary and sufficient for a prediction. We further extend the explanation to extract the set of features that would move the current prediction to a target class by adopting targeted adversarial attack for the robustness analysis. Through experiments across multiple domains and user study, we validate the usefulness of our evaluation criteria and our derived explanations.
INTRODUCTION
There is increasing interest in machine learning models to be credible, fair, and more generally interpretable (Doshi-Velez & Kim 2017). Researchers have explored various notions of model interpretability, ranging from trustability (Ribeiro al. 2016). fairnsss of model (Zhao et al. 2017)
to characterizing the model's weak points (Koh & Liang] 2017: Ych et al.) 2018). Even though the goals of these various model interpretability tasks vary, the vast majority of them use so called
feature based explanations, that assign importance to individual features (Baehrens et al. 2010
Simonyan et al. 2013 Zeiler & Fergus 2014|
(Boch [ach al. 20155) Ribeiro al. [0166] Lundberg
Lee, Ancona et al. 2018 Sundararajan et al., 2017 Zintgraf et al. 2017 Shrikumar et al.
2017 Chang et al. 2019). There have also been a slew recent evaluation measures for feature
based explanations. such as completeness (Sundararajan et al.) 2017), sensitivity-n (Ancona et al. 2018), infidelity (Ych et al. 2019). causal local explanation metric (Plumb et al. 2018), and most relevant to the current paper, removal- and preservation-bee based criteria (Samek et al. 2016 Fong & Vedaldi 2017] Dabkowski & Gall 2017]] Petsiuk et al., 2018). A common thread all these evaluation measures is that for a good feature based explanation, the most salient features necessary, in that removing them should lead to a large difference in prediction score, and are also sufficient in that removing non-salient features should not lead a large difference in prediction score.
Thus, common evaluations and indeed even methods for feature based explanations involve measuring the function difference after "removing features", which in practice is done by setting the feature value to some reference value (also called baseline value sometimes). However, this would favor feature values that are far way from the bascline value (since this corresponds to a large perturbation, and hence is likely to lead to function value difference), causing an intrinsic bias for these methods and evaluations. For example, if we set the feature value black in RGB images, this introduces bias favoring bright pixels: explanations that optimize such evaluations often omit important dark objects such as a dark-colored dog. An alternative approach to "remove features" is to sample from
"This work done when the author was visiting UCL.A.

---

Published as a conference paper at ICLR 2021
Illustration of our explanation highlighting both perti- nent positive and negative features that support the prediction of "2". The blue circled region corresponds to pertinent positive features that when value is perturbed (from white to black) will make the digit resemble "7"; while the green and yellow circled region correspond to pertinent negative features that when turned on (black white) will shape the digit into "0","8" "9".
Figure 1:
2
some predefined distribution or a generative model (Chang et al. 2019). This nevertheless in turn incurs the bias inherent to the generative model, and accurate generative models that approximate the data distribution well might not be available in all domains.
In this work, instead of defining prediction changes with "removal" of features (which introduces biases as we argued), we alternatively consider the use of small but adversarial perturbations. is natural to assume that adversarial perturbations on irrelevant features should be ineffective, while those on relevant features should be effective. We can thus measure the necessity of a set of relevant features, provided by an explanation, by measuring the consequences of adversarialyy perturbing their feature values: if the features are indeed relevant, this should lead to an appreciable change in the predictions. Complementarily, we could measure the sufficiency of the set of relevant features via measuring consequences of adversarially perturbing its complementary set of irrelevant features: the perturbed features are irrelevant, this should not lead an appreciable change in the predictions. We emphasize that by our definition of "important features", our method may naturally identify both pertinent positive and pertinent negative features (Dhurandhar et al. 2018) since both pertinent positive and pertinent negative features are the most susceptible to adversarial perturbations, and we demonstrate the idea in Figure II While exactly computing such an effectiveness measure is Na-hard (Katz et al., (017). 7). we can leverage recent results from test-time robustness (Carlini & Wagner) 2017; Madry et al., 2017), which entail that perturbations computed by adversarial attacks can serve reasonably tight upper bounds for our proposed evaluation. Given this adversarial effectiveness evaluation measure, we further design feature based explanations that optimize this evaluation measure.
To summarize our contributions:
We define new evaluation criteria for feature based explanations by leveraging robustness analysis involving small adversarial perturbations. These reduce the bias inherent in other recent evaluation measures that focus on "removing features" via large perturbations to some reference values, sampling from some reference distribution.
We design efficient algorithms to generate explanations that optimize the proposed criteria by incorporating game theoretic notions, and demonstrate the effectiveness and interpretability of our proposed explanation on image and language datasets: via our proposed evaluation metric, additional objective metrics, well as qualitative results and user study]]
2 RELATED WORK
Our work defines a pair of new objective evaluation criteria for feature based explanations, where existing measurements can be roughly categorized into two families. This first family of explanation evaluations are based on measuring fidelity of the explanation to the model. Here, the feature based explanation is mapped to a simplified model, and the fidelity evaluations measure how well this simplified model corresponds to the actual model. A common setting is where the feature vectors are locally binarized at a given test input, to indicate presence or "removal" of a feature. A linear model with the explanation weights coefficients would then equal to the sum of attribution values for all present features. Completeness or Sun to Delta requires the sum of all attributions to equal the prediction difference between the original input and a baseline input (Sundararajan al., 2017] Shrikumar et al., 2017). while Sensitivity-n further generalize this to require the sums of subsets of attribution values to equal the prediction difference of the input with features present or absent corresponding to the subset, and the baseline (Ancona et al. 2208).. Local accuracy (Ribeiro et al. 2016 Lundberg & Lee 2017) measures the fidelity of local linear regression model corresponding to explanation weights; while Infidelity is a framework that encompasses these instances above (Yeh)
Code available htap://ttttrree/aaaooooooooooaan

---

Published as a conference paper at ICLR 2021
et al. 2019). The second family of explanation evaluations removal- and preservation-base measurements (Samek et al., 2016; Fong & Vedaldi
& Gal, 2017 Petsiuk et al. 2018), which evaluate the ranking of feature attribution score, with the key insight that removing the most (least) salient features should lead to the most (least) significant function value difference. Unlike previous evaluations, our proposed evaluation criteria are based more nuanced and smaller adversarial perturbations which do not rely on operationalizing "feature removal".
Another close line of research is counterfactual and contrastive explanations (Wachter al. 2017
Dhurandhar et al. 2018 Hendricks et al. 2018 van der Waa et al., 2018 Chang et al. 2019] Goyal
2019 Joshi et al. 2019; Poyiadzi et al., 2020). which answer the question: "what to alter in the current input to change the outcome of the model". These studies enable interpretation of a model decision through a contrastive perspective and facilitate actionable means that one can actually undertake to change the model prediction (Joshi et al. [2099] Poyiadzi et al. 2020). While "the closest possible world" provided by counterfactual explanations sheds light on the features that are "necessary" for the prediction, it could fail to identify relevant features that are "sufficient" for the current prediction, Xu et al. (2018) add group sparsity regularization to adversarial attacks that improves the semantic structure of the adversarial perturbations. Instead of outputting general adversarial perturbations, our work focuses specifically on identifying necessary and sufficient relevant features by measuring their susceptibility to adversarial perturbations. |Ribeiro et al. (2018) find a set of features that once fixed, the prediction does not change much with high probability when perturbing other features. They measure this via a sampling approach, which could be infeasible for nigh-dimensional images without super-pixels. In contrast, our method considers the class of adversarial perturbations, which is much more computationally feasible compared sampling high- dimensional spaces. Guidotti et al. (2019) exploit latent feature space to learn local decision rules with image exemplars that support the current prediction and exeepla-s that contrast the current prediction. While the explanation is capable of highlighting both areas pertinent to the prediction and areas that pushes the prediction towards another class, the method relies on an effective generative model which might not always be available in different applications.
ROBUSTNESS ANALYSIS FOR EVALUATING EXPLANATIONS
3.1 PROBLEM NOTATION
We consider the setting of a general K-way classification problem with input space X' C Rdd output space (1, K} and predictor function f X + y' where f(x) denotes the output class for some input example æ [z],.... . æa] E X. Then, for a particular prediction f(x) y. common goal of feature based explanations is to extract a compact set of relevant features with respect to the prediction. We denote the set of relevant features provided by an explanation as S, S U where U {1,..., d) is the set of all features, and use S, = U \ Sr, the complementary set of S,, to denote the set of irrelevant features. We further use æg to denote the features within æ that are restricted to the set S.
3.2 EVALUATION THROUGH ROBUSTNESS ANALYSIS
A common thread underlying evaluations of feature based explanations (Samek et al., 2016 Petsiuk cct al. 2018), even ranging over axiomatic treatments (Sundararajan et al.) 2017 Lundberg & Lee 2017). that the importance of set of features corresponds to the change in prediction of the model when the features are removed from the original input. Nevertheless, as we discussed in previous sections, operationalizing such removal of features, for instance, by setting them to some reference value, introduces biases (see Appendix and Section 5.2 for formal discussion and empirical results on the impact of reference values). To finesse this, we leverage adversarial robustness, but do so in this context, we rely on two key intuitive assumptions that motivate our method:
Assumption 1:
When the values of the important features are anchored (fixed), perturbations restricted to the complementary set of features has a weaker influence on the model prediction.
When perturbations are restricted to the set of important features, fixing the values of the rest of the features, even small perturbations could easily change the model prediction.
Assumption 2:
Based on these two assumptions, we propose a new framework leveraging the notion of adversarial robustness feature subsets, as defined below, to evaluate feature based explanations.
3

---

Published as a conference paper at ICLR 2021
Definition 3.1 Given a model f. an input and set fe S S U where U is the set of all features, the minimum adversarial perturbation norm on ss. which we will also term Robustness-S of x is defined as:
|10 ( min
s.t. f(x + + 8s 0).
Eas - I(5, 2,
(1)
where y f(x), S = U S is the complementary set of features, and dg 0 means that the perturbation is constrained to be zero along features in S.
Suppose that feature based explanation partitions the input features of into a relevant set Sr, and an irrelevant set S,, Assumption 1 implies that the quality of the relevant set can be measured by S= by keeping the relevant unchanged, and measuring the adversarial robustness norm by perturbing only the irrelevant set. Specifically, from Assumption I, a larger coverage of pertinent features in set S, entails higher robustness value Ezg." On the other hand, from Assumption 2, larger coverage of pertinent features in set S, would turn entail a smaller robustness value e since only relevant features are perturbed. More formally, we propose the following twin criteria for evaluating the quality of S, identified by any given feature based explanation.
Definition 3.2 Given input and relevant feature set Sy, define Robustness-S, and Robustness-S, of the input a as the following:
Robustness- G Robustness-S. Cas."
Following assumptions, set S, that has larger coverage of relevant features would yield higher Robustness-S, and lower Robustness-S.
Evaluation for Feature Importance Explanations. While Robustness- and Robustness-S, are defined on sets, general feature attribution based explanations could also easily fit into the evaluation framework. Given any feature attribution method that assigns importance score to each feature, we can sort the features in descending order of importance weights, and provide the top- K features as the relevant set S,.. The size K (or JS, D). can be specified by the users based on the application. An alternative approach that adopt in our experiments is to vary the size of set K and plot the corresponding values of Robustness-5) and Robustness-S, over different values of K. With Robustness-S,.
graph where the X axis is the size of K and the Y-axis is Robustness-S, we are then able to plot an evaluation curve for an explanation and in turn compute its the area under curve (AUC) to summarize its performance. A larger (smaller) AUC for Robustness-Si (Robustness-S, indicates a better feature attribution ranking. Formally, given a curve represented by set of points C = { vo).... ................................ (In, 3n)} where I;-1 < 24, we calculate the AUC of the curve by: AUC(C)= > (yi + 1/21)/2 22 * (xq - I;-1).
Relation to Insertion and Deletion Criteria. We relate the proposed criteria to a set of commonly adopted evaluation metrics: the Insertion and Deletion criteria (Samek et al. 2016 Petsiuk et al. 2018; Sturmfels et al. 2020). The Insertion score measures the model's function value when only the top-relevant features, given by an explanation, are presented in the input while the others removed (usually by setting them to some reference value representing feature missingness). The Deletion score, the other hand, measures the model's function value when the most relevant features are masked from the input. As in our evaluation framework, we could plot the evaluation curves for Insertion (Deletion) score by progressively increasing the number of top-relevant features. A larger (smaller) AUC under Insertion (Deletion) then indicates better explanation, as the identified relevant features could indeed greatly influence the model prediction. We note that optimizing the proposed Robustness-S: and Robustness-SS could roughly be seen as optimizing a lower bound for the Insertion and Deletion score respectively. This follows from the intuition: Robustness- S, considers features that when anchored, would make the prediction most robust to "adversarial perturbation". Since adversarial perturbation is the worst case of "any arbitrary perturbations", the prediction will also be robust to different removal techniques (which essentially correspond to different perturbations) considered in the evaluation of Insertion score; The same applies to the connection between Robustness-S S, and Deletion score. We shall see in the experiment section that explanation optimizing our robustness measurements enjoys competitive performances on the Insertion / Deletion criteria.
4

---

Published as a conference paper at ICLR 2021
corresponds to the untargeted adversarial robustness - a perturbation that changes the predicted class to any label other than is considered as successful attack. Our formulation can also be extended to targeted adversarial robustness, where we replace Eqn. by:
Untargeted v.s. Targeted Explanation. Definition 3.1
min || s.t. f(æ + 6) = =:: =::33=0 t:
(2)
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" by highlighting the important features that contrast between class y and t. Further examples of the "targeted explanations" are in the experiment section.
Robustness Evaluation on Feature Subset. It is known that computing the exact minimum dis- tortion distance in modern neural networks is intractable (Katz al., 2017). so many different methods have been developed to estimate the value. Adversarial attacks, such as C&W (Carlini Wagner 2017) and projected gradient descent (PGD) attack (Madry et al. 2017), aim to find a feasible solution of Eqn. which leads to upper bound of egg. They are based gradient based optimizers which are usually efficient. On the other hand, neural network verification methods aim to provide lower bound of <no to ensure that the model prediction will not change within certain perturbation range (Singh et al. 2018 Wong & Kolter 2018 [Wnng et al., 2018 Gehr et al.. 2018)
Zhang al. 2018 Wang al.] 2018: Zhang et al. 2019). The proposed framework can be combined with any method that aims to approximately compute Eqn. [ including attack, verification, and some other statistical estimations (see Appendix Bor more discussions on estimating adversarial robustness for different types of model). However, for simplicity we only choose to evaluate Eqn. by the state-of-the- PGD attack (Madry et al. 2017), since the verification methods are slow and often lead to much looser estimation as reported in some recent studies (Salman et al. 2019). Our additional constraint restricting perturbation to only be on a subset of features specifies a set that is simple to project onto, where we set the corresponding coordinates to zero at each step of PGD,
4 EXTRACTING RELEVANT FEATURES THROUGH ROBUSTNESS ANALYSIS
Our adversarial robustness based evaluations allow to evaluate any given feature based explanation. Here, we set out to design new explanations that explicitly optimize our evaluation measure. We focus on feature set based explanations, where we aim to provide an important subset of features S,.. Given our proposed evaluation measure, an optimal subset of feature S, would aim to maximize (minimize) Robustness- (Robustness-S., under cardinality constraint on the feature set, leading to the following set of optimization problems:
maximize g(f,z,Sp) S.) s.t. |S S K S.CU
(3)
minimize af, Sr) |S K S.CU
where K is a pre-defined size constraint on the set S,, and g(f, x, S) computes the the minimum
adversarial perturbation from Eqn. with set-restricted perturbations.
can be seen that this sets up an adversarial game for Eqn. (or a co-operative game for Eqn. 4.
In the adversarial game, the goal of the feature set explainer to come up with set S, such that the minimal adversarial perturbation is as large as possible, while the adversarial attacker, given set S,, aims to design adversarial perturbations that are small as possible. Conversely in the co-operative game, the explainer and attacker cooperate to minimize the perturbation norm. Directly solving these problems in Eqn. 3 and Eqn. is thus challenging, which is exacerbated by the discrete input constraint that makes it intractable to find the optimal solution. We therefore propose a greedy algorithm in the next section estimate the optimal explanation sets.
4.1 GREEDY ALGORRIHH TO COMPUTE OPTIMAL EXPLANATIONS
We first consider greedy algorithm where, after initializing S, the empty set, iteratively add to S, the most promising feature that optimizes the objective at each local step until S, reaches the size constraint. We thus sequentially solve the following sub-problem at every step t:
arg max sf, az St Ui), or arg y a. S Ui), Vi E ST
(5)
i
where St is the relevant set at step t, and S = 0. We repeat this subprocedure until the size of set SS reaches K. A straightforward approach for solving Eqn. 5 is to exhaustively search over every
5

---

Published as a conference paper at ICLR 2021
single feature. We term this method Greedy. While the method eventually selects K features for the relevant set S,, it might lose the sequence in which the features were selected. One approach to encode this order would be to output a feature explanation that assigns higher weights to those features selected earlier in the greedy iterations.
4.2 GREEDY BY SET AGGREGATION SCORE
The main downside of using the greedy algorithm to optimize the objective function is that it ignores the interactions among features. Two features that may seem irrelevant when evaluated separately might nonetheless be relevant when added simultaneously. Therefore, in each greedy step, instead of considering how each individual feature will marginally contribute to the objective 9(-), we propose choose features based on their expected marginal contribution when added to the union of S, and a random subset of unchosen features. To measure such an aggregated contribution score, we draw from cooperative game theory literature (Dubey Shapley 1979] Hammer & Holzman [992) to reduce this linear regression problem. Formally, let S and S be the ordered set of chosen and unchosen features at step t respectively, and (())) be all possible subsets of ST. We measure the expected contribution that including each unchosen feature to the relevant set would have on the objective function by learning the following regression problem:
w", w²'c'=
arg min w.c
Σ
((w" ((w"b(s) b(S) + =(S; US))?
(6)
SEP(S))
where b: P(S)))) - (0, 1315ز1 function that projects a set into its corresponding binary vector
form: b(S) = [5] E S). and v(.) is set to be the objective function in Eqn. 3 or Eqn. 4
v(S,) - - x;, x; 5.) for optimizing Eqn. 3 v(S,) = = æ. S.) for optimizing Eqn. We note that
w"' corresponds to the well-known Banzhaf value (Banzhaf III. 1964) when S 0. which can be
interpreted as the importance of each player by taking coalitions into account (Dubey & Shapley 1979). Hammer & Holzman 1992) show that the Banzhaf value is equivalent to the optimal solution of linear regression with pseudo-Boolean Boolean functions as targets, which corresponds to Eqn. 6 with S 0. At each step 6, we can thus treat the linear regression coefficients wt in Equ. as each corresponding feature's 's expected marginal contribution when added to the union of S, and a random subset of unchosen features.
We thus consider the following set- egggrgggette variant of our greedy algorithm in the previous section, which we term Greedy-AS. In each greedy step f. we choose features that are expected contribute most to the objective function, i.c. features with highest (for Eq or lowest (for Eqn. 4 aggregation score (Banzhaf value), rather than simply the highest marginal contribution to the objective function as in vanilla greedy. This allows us to additionally consider the interactions among the unchosen features when compared to vanilla greedy. The chosen features each step are then added to S and removed from S. When S is not B. the solution of Eqn. 6 can still be seen as the Banzhaf value where the players are the unchosen features in S and the value function computes the objective when subset of players is added into the current set of chosen features St We solve the linear regression problem in Eqn. by sub-sampling to lower the computational cost, and we validate the effectiveness of Greedy and Greedy-AS in the experiment section.
EXPERIMENTS
In this section, we first evaluate different model interpretability methods the proposed criteria. We justify the effectiveness of the proposed Greedy-AS. We then move onto further validating the benefits of the explanations extracted by Greedy-AS through comparisons to various existing methods both quantitatively and qualitatively. Finally, we demonstrate the flexibility of our method with the ability provide targeted explanations two image datasets, MNIST et al. (2010) and ImageNet (Deng et al.) 2009), as well as a text classification dataset, Yahoo! Answers (Zhang et al. 2015). On MNIST. we train a convolutional neural network (CNN) with 99% testing accuracy. On ImageNet, we deploy a tre-trained ResNet model obtained from the Pytorch library. On Yahoo! Answers, we train a BiL.TM sentence classifier which attains testing accuracy of 71%.
mentioned in Section 3.2 We perform the experiments on
We found that concurrent our work, greedy with choosing the players with the highest restricted Banzhaf was used in Elkind et al. (2017)

---

Published as a conference paper at ICLR 2021
Table 1: AUC of Robustness-5; and Robustness-S, for various explanations on different datasets. The higher the better for Robustness-S,; the lower the better for Robustness-Sp-
Datasets
Explanations
Grad
IG
EG
SHAP
LO0
BBMP
CFX
Random
Groody-AS
MNIST
Robustness-S.
88.00
85.98
93.24
75.48
74.14
78.58
69.88
64.44
98.01
Robustness-S,
91.72
91.97
91.05
101.49
104.38
176.61
102.81
193.75
82.81
ImageNet
Rohustness-S, S, Robustness-S.
27.13
26.01
26.88
18.25
22.29
21.56
27.12
17.98
31,62
45.53
46.28
48.82
60.02
58.46
158.01
46.10
56.11
43.97
YaswerAnswer
Rohustness-S.
1.97
1.96
1.81
1.74
1.95
1.71
2.13
Robustness 8,
2.91
3.14
2.99
3.34
4.04
2.96
7.64
2,41
Setup. In the experiments, we consider p- = 2 for || |b in Eqn. I and Equ. 2 We note that Eqn. is defined for a single data example. Given y multiple examples { }i=1 with their corresponding relevant sets provided by some explanation {-S, we compute the overall Robustness- S, (-S,) by taking the average: for instance, 1 - i=1 g(f. æ;, S.) for Robustness-S,.. We then plot the evaluation curve as discussed in Section 3.2 and report the AUC for different explanation methods. For all quantitative results, we report the average over 100 random examples. For the baseline methods, we include vanilla gradient (Grad) (Shrikumar et al. (017). integratedd gradient (IG) (Sundararajan et al.,
2017), and expected gradient (EG) (Erion et al. 2019. |Strrffels et al. 2020) from gradient-based
approaches; leave-one-out (LOO) (Zeiler & Fergus] 2014 Li et al. 2016). SHAP (Lundberg & Lee
2017) and black-box meaningful perturbationn (BBMP) (only for image examples) (Fong & Vedaldi
2017) from perturbation based approaches (Ancona et al., 2018): counterfactual explanation (CFX)
proposed by Wachter et al. (2017); Anchor (Ribeiro et al. (018) for text examples; and a Random
baseline that ranks feature importance randomly. Following common setup (Sundararajan et al. 2017]] zero the reference value for all explanations that require baseline. We
Ancona et al., 2018), leave more implementation detail in Appendix C due to space limitation.
5.1 ROBUSTNESS ANALYSIS ON MODEL INTERPRETABILIT METHOSS
Here we compare Greedy-AS and various existing explanation methods under the proposed evaluation criteria Robustness-S, and Robustness-S, We list the results Table with the detailed plots in Appendix D
We as well compare Greedy-AS with its ablated variants in Appendix E
Comparisons between Different Explanations. From Table T we observe that the proposed Greedy-AS consistently outperforms other explanation methods on both criteria (see Appendix G for the statistical significance). 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 characteristies of explanations which most of the current explanations do not possess. Another somewhat interesting finding from the table is that while Grad has generally been viewed as a baseline method, it nonetheless performs competitively on the proposed criteria. We conjecture the phenomenon results from the fact that Grad does not assume any reference value as opposed to other baselines such LOO which sets the reference value as zero mask out the inputs. Indeed, it might not be surprising that Greedy-AS achieves the best performances on the proposed criteria since is explicitly designed for so. To more objectively evaluate the usefulness of the proposed explanation, we demonstrate different advantages of our method by comparing Greedy-AS to other explanations quantitatively on existing commonly adopted measurements, and qualitatively through visualization in the following subsections.
5.2 EVALUATING GREEDY-AS
The Insertion and Deletion Metric. To further justify the proposed explanation not only performs well on the very metric it optimizes, we evaluate our method on the suite of quantitative measurements mentioned above: the Insertion and Delction criteria (Samek et al.] 2016 Petsiuk et al. 2018 Sturmfels et al. 2020). Recall that evaluations on Insertion and Deletion score require specifying a reference value to represent feature missingness. Here, we first focus on the results when the reference values are randomly sampled from an uniform distribution, i.e., (0, 1) for image inputs and random word vector for text inputs, and we shall discuss the impact varying such reference value shortly. We plot the evaluation curves (in Appendix F and report corresponding AUCs in Table On these additional two criteria, we observe that Greedy-AS performs favorably against other explanations (see Appendix G the statistical significance). The results further validate the benefits of the proposed criteria where optimizing Robustness-S. (-S,) has tight connection to optimizing the
7

---

Published as a conference paper at ICLR 2021
Table 2: AUC of the Insertion and Deletion criteria for various explanations on different datasets. The higher the better for Insertion; the lower the better for Deletion.
Datasets
Explanations
Grad
IG
EG
SHAP
1,00
BBMP
CFX
Rundom
Greedy
MNIST
Insertion
174,18
177.12
228.64
125.93
121.99
108.97
102.05
51,71
270.75
Deletion
153.58
150.90
113.21
213.32
274.77
587.08
137.69
312.07
94,24
ImageNet
Insertion
86.16
109.94
150.81
28.06
63.90
135.98
97.33
31,73
183,66
Deletion
276.78
256.51
244.88
143.27
290.10
615.13
281.12
314,82
219.52
Answers
Insertion
0.06
0.06
0,20
0.07
0.18
0.05
0.10
0.21
Deletion
2.57
2.23
2,07
2.35
2.63
1.56
Insertion (Deletion) score. We note that on ImageNet, SHAP obtains a better performance under the Deletion criterion. We however suspect such performance comes from ad adversarial artifacts (features vulnerable to perturbations while not being semantically meaningful) since SHAP seems rather noisy on ImageNet (as shown in Figure B). and the Deletion criterion has been observed to favor such artifacts in previous work (Dabkowski & Gal 2017; Chang et al. 2019). We note that although Greedy-AS exploits regions that are most susceptible to adversarial attacks, such regions may still be meaningful as shown in our visualization result.
Impact and Potential Bias of Reference Value. From T one might wonder why explana- tions like IG and SHAP would suffer relatively low performance although some of these methods (e.g., SHAP) are intentionally designed for optimizing Insertion- and Deletion-like measurements. We anticipate that such inferior performances values used in the explanations and the ones used in the evaluation (recall that we set the intrinsic reference value to zero for all explanation methods, but utilize random value for Insertion and Dele- tion). To validate the hypothesis, we evaluate all explanations on Insertion and Deletion criteria with different reference values (0, 0.25, 0.5, 0.75, 1), and list the results in Appendix HH We validate that pero-baseline SHAP and IG perform much stronger when the reference value used in Insertion / Deletion is closer to zero (matching the intrinsically-used baseline) and perform significantly worse when the reference value is set to 0.75, 1. or (0, 1). On the other hand, we observe EG that does not rely on a single reference point (but instead averaging over multiple baselines) performs much more stably across different reference values. Finally, we see that Greedy-AS performs stably among the top across different reference values, which could be the merits of not assuming any baselines (but instead consider the worst-case perturbation). These empirical results reveal potential risk of evaluations (and indeed explanations) that could largely be affected by the change of baseline values.
due to the mismatch between the intrinsic reference
Sanity Check and Sensitivity Analysis. Greedy-AS could indeed pass the sanity check proposed by /Adebayo et al. (2018). We as well conduct sensitivity analysis (Yeh et al. 2019) on Greedy-AS in Appendix
Appendix [ we conduct experiments to verify that
5.3 QUALITATIVE RESULTS
Image Classification. To complement the quantitative measurements, we show several visualiza- tion results on MNIST and ImageNet in Figure 2 and Figure 3 More examples could be found in Appendix [ On MNIST, we observe that existing explanations tend to highlight mainly on the white pixels in the digits; among which SHAP and LOO show less noisy explanations comparing to Grad and IG. On the other hand, the proposed Greedy-AS focuses on both the "crucial positive" (important white pixels) as well as the "pertinent negative" (important black regions) that together support the prediction. For example, in the first row, a 7 might have been predicted as a 4 or 0 if the pixels highlighted by Greedy-AS are set white. Similarly, a may be turned to a 4 or a 7 given additional white pixels to its left, and a 9 may become a 7 if deleted the lower circular part of its head. From the results, we see that Greedy-AS focuses on "the region where perturbation on its current value will lead to easier prediction change", which includes both the crucial positive and pertinent negative pixels. Such capability of Greedy-AS is also validated by its superior performance on the proposed robustness criteria. on which methods like LOO that highlights only the white strokes of digits show relatively low performance. The capability of capturing pertinent negative features has also been observed in explanations proposed in some recent work Dhurandhar et al. (2018): [Bah]] cet al. (2015): Oramas et al. (2019), and we further provide more detailed discussions and comparisons to these methods in Appendix M From the visualized ImageNet examples shown in Figure? 3 we observe that our method provides more compact explanations that focus mainly on the actual objects being classified. For instance, in the first image, while others tend to have noisier results; in the last image, our method focuses on one of the Japanese Spaniel whereas others highlight both the dogs and some noisy regions.
method focuses more on the face of the Maltese
8

---

Published as a conference paper at ICLR 2021
Original
Grod
10
80
SHAP
LOO
SSMP
CPX
Dreedy-AS
Origina
Dredi
EO
SHAP
LOD
BEMP
CPX
Greedy AS
7
7
9
9
Figure 2: Visualization on top 20 percent rele- vant features provided by different explanations on MNIST. We see Greedy-AS highlights both crucial positive and pertinent negative features supporting the prediction.
Figure 3: Visualization of different explanations on ImageNet, where the predicted class for each input is "Maltese", "hippopptamus", "zebra", and "Japanese Spaniel". Greedy-AS focuses more compactly on objects.
Input
Ronaldinho and kaka are my favorite players out there, why did they replace them? completely missed that part. Do they say why the switched them?
Grad
Ranaldinho and kaka are my favorite pl players out there, why did they isploci tham? completely missed that pani Do they say why the Switched them?
Bonsldinhi and kakca are my favortte players out there. ahy did than replace them' I completely missed that part. Do they say why the switched theni?
Ronskdingg and kakas are my fnvorite Blayari out there, why they replace them? completely missed that part. Do they may why the iwitched them?
SHAP
Ronoldinh
kaka are my favorite players out there. why they replose them? completel missed part, they say why switthed thom?
Ronaldinho
kakka my favorite players out there, why they replace completely missed pans
say why switched
Runaklinta
players there. and kaica favorita out there. they them? completely missed that
they repluce tham? cumpletdd
that part. say switchhd
Gready-AS
Bonaldinhä
say switcheed them?
Anchor
Bunskkinii and kaskas fovoriie out thare. why did they replace them? completely ricond that port. Do they say why the sowitched thwmn?
Most Relevant
Less Relevant
Figure 4: Explanations on text classification model which correctly predicts the label "sport". Unlike most other methods, the top-5 relevant keywords highlighted by Greedy-AS are all related to the concept "sport".
Input
Yarget:
Target:
Input
Target: 7
Target:
Input
Target: 6
Targat:
Input
Target: 2
Target:
7
8
Figure 5: Visualization of targeted explanation. For each input, we highlight relevant regions explaining why the input is not predicted as the target class. We see the explanation changes in a semantically meaningful way the target class changes.
Text Classification. Here we demonstrate our explanation method on a text classification model that classifies given sentence into one of the ten classes (Society, Science, .... Health). We showcase an example in Figure 4 (see Appendix O for more examples). We see that the top-5 keywords highlighted by Greedy-AS are all relevant to the label "sport", and Greedy-AS is less likely to select stop words as compared to other methods. Additionally, we conduct an user study where we observe that Greedy-AS generates explanation that matches user intuition the most, and we report detailed setup of the user study in Appendix P
discussed about the possibility of using targeted adversarial perturbation to answer the question of "why the inpul is predicted as A but not B". In Figure for each input digit, we provide targeted explanation towards two different target classes. Interestingly, as the target class changes, the generated explanation varies in an interpretatble way. For example, in the first image, we explain why the input digit 7 is not classified as a (middle column) or a 2 (rightmost column). The resulting explanation against 9 highlights the upper-left part of the 7. Semantically, this region 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 9. However, the targeted explanation against highlights a 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.
Targeted Explanation Analysis. In section
CONCLUSION
In this paper, establish the link between a set of features to prediction with a new evaluation criteria, robustness analysis, which measures the minimum tolerance of adversarial perturbation. Furthermore, develop 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.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This work is partially supported by NSF IIS-1901527, IIS-2008173 and IIS-2048280, C.Y. and P.R. acknowledge the support of DARPA via FA87501720152, HR001 12020006.
REFERENCES
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in Neural Information Processing Systems, pp. 9525-9536, 2018.
David Alvarez Melis and Tommi Jaakkola. Towards robust interpretability with self-explainngg neural networks. Advances in Neural Information Processing Systems, 31:7775-7784, 2018.
Marco Ancona, Enea Ceolini, Cengiz Oztireli, and Markus Gross. unified view of gradient- based attribution methods for deep neural networks. International Conference Learning Representations, 2018.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 1017):e013040, 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, 10Jun):10331888) 2010.
John F Banzhaf III. Weighted voting doesn't tt work: A mathematical analysis. Rutgers L. Rev., 19: 317, 1964.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv: 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, Anna Goldenberg, and David Duvenaud. Explaining image
classifiers by counterfactual generation. In International Conference on Learning Representations, 2019.
Hongge Chen, Huan Zhang. Duane Boning, and Cho-Jui Hsieh. Robust decision trees against adversarial examples. In JCML, 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-basel approach. arXiv preprint arXiv: 1807.00 04457, 2018.
Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. In Advances in Neural Information Processing Systems, pp. 6967-6976. 2017.
J. Deng. W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. CVPR09, 2009.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in 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.0868. 2017.
Pradeep Dubey and Lloyd S Shapley. Mathematical properties of the banzhaf power index. Mathe- maticy of Operations Research, 4(2):99-131, 1979.
10

---

Published as a conference paper at ICLR 2021
Edith Elkind, Piotr Faliszewski, Martin Lackner, Dominik Peters, and Nimrod Talmon. Committee scoring rules, banzhaf values, and approximation algorithms. In 4th workshop on exploring beyond the worst case in computational social choice (EXPLORE' 17), 2017.
Gabriel Erion, Joseph D Janizek, Pascal Sturmfels, Scott Lundberg, and Su-In Lee. Learning explainable models using attribution priors. arXiv preprint arXiv:1906. 19677 2019.
Ruth C. Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful per- turbation. 2017 IEEE International Conference on Computer Vision (ICCV), pp. 3449-3457, 2017.
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2018.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint
2014.
Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh, and Stefan Lec. Counterfactual visual explanations. In International Conference on Machine Learning, pp. 2376-2384, 2019.
Riccardo Guidotti, Anna Monreale, Stan Matwin, and Dino Pedreschi. Black box explanation by learning image exemplars in the latent feature space. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 189-205. Springer, 2019.
Peter L Hammer and Ron Holzman. Approximations of pseudo-boolean functions; applications to game theory. Zeitschrifi für Operations Research, 36(1) 3::221, 1992.
Lisa Anne Hendricks, Ronghang Hu, Trevor Darrell, and Zeynep Akata. Grounding visual explana- tions. In ECCV, 2018
S. Joshi, O. Koyejo, Warut D. Vijitbenjaronk, Been Kim, and Joydeep Ghosh. Towards realistic individual recourse and actionable explanations in black-box decision making systems. ArXiv, hass/1907.06615. 2019.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference Computer Aided Verification, pp. 97-117. Springer, 2017.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pp. 1885-1894, 2017.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. lecun. com/exab/nniss,, 2, 2010.
Jiwei Li, Will Monroe, and Dan Jurafsky. Understanding neural networks through representation
erasure. CoRR, abs/1612.0822D 2016. URL
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.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1rXiv:1706.000 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
net
Vitali Petsiuk, Abir Das, and Kate Saenko. Rise: Randomized input sampling for explanation of black-box models. arXiv preprint 1xXiv:1806.07421. 2018.
Gregory Plumb, Denali Molitor, and Ameet S Talwalkar. Model agnostic supervised local explana- tions. In Advances in Neural Information Processing Systems, pp. 2515-2524, 2018.

---

Published as a conference paper at ICLR 2021
Rafael Poyiadzi, Kacper Sokol, Raúl Santos Santos-Rodrigen Rodríguez, D. Bie, and Peter A. Flach. Face: Feasible and actionable counterfactual explanations. Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 2020.
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: High-precision model-agnostic explanations. In Teiony-Second AAAI Conference on Artificial Intelligence, 2018.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation 2019.
barrier to tight robust verification of neural networks. arXiv preprint
Wojeiech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus- Klber-Robert Müller. Evaluating the visualization of what a deep neural network has learned. IEEE transactions on neural networks and learning systems, 28(1 1):2660-2666 2673, 2016.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje.
Learning important features through propagating activation differences. International Conference on Machine Learning, 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv: 1312.6034, 2013.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püishel, and Martin Vechev. Fast and effective robustness certification. In Advances in Neural Information Processing Systems, pp. 10802-10813, 2018.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. arXiv preprint 17Xiv:1706.03825, 2017.
Pascal Sturmfels, Scott Lundberg, and Su-In Lee. Visualizing the impact of feature attribution baselines. Distill, 5(1):e22, 2020.
Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. arXiv preprint 1908..9908.00 2019.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, 2017.
Jasper van der Waa, Marcel Robeer, Jurriaan van Diggelen, Matthieu Brinkhuis, and Mark Neerincx. Contrastive Explanations with Local Foil Trees. In 2018 Workshop on Human Interpretability in Machine Learning (WHI), 2018.
S. Wachter, Brent D. Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. European Economics: Microeconomics & Industrial Organization eJournal, 2017.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis neural networks. In Advances in Neural Information Processing Systems, pp. 6367- 6377, 2018.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5273-5282, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 2283,5292, 2018.
Kaidi Xu, Sijia Liu, Pu Zhao, Pin- 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: 1888 01664, 2018.
12

---

Published as a conference paper at ICLR 2021
Chih-Kuss Kual Yeh, Joon Kim, lan En-Hsu Yen, and Pradeep K Ravikumar. Representer point selection for explaining deep neural networks. Advances in Neural Information Processing Systems, pp- 9291-9301, 2018. 2018.
Chih-Kuan Yeh, Cheng-Ye Yu Hsieh, Arun Sai Suggala, David I. Inouye, and Pradeep Ravikumar. On the (in)fidelity and sensitivity of explanations. In Advances in Neural Information Processing Systems, pp. 10965-10976, 2019.
Matthew Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference computer vision, pp. 318-833. Springer, 2014.
Huan Zhang, Tsui- Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in neural information processing systems, pp. 4939 4948, 2018.
Huan Zhang, Pengchuan Zhang, and Cho-Jui Hsich. 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.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Advances in neural information processing systems, pp. 649-657, 2015.
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.
Luisa M. Zintgraf, Taco Cohen, Tameem Adel, and Max Welling. Visualizing deep neural network decisions: Prediction difference analysis. In 5th International Conference on Learning Representations, ICIR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings, 2017. URL https: wpwnrevvivveeeeeeeoooeo ew. net furm? d B=BJ5UeUJ9x
13

---

Published as a conference paper at ICLR 2021
A BIAS FOR REFERENCE- VALUE METHODS
In Appendix A.I I.I we show that many explanations are biased to reference value (IG, SHAP, LRP, DeepLift). For example, if the reference value is zero vector (which means black pixels in image), then any black pixel will get a zero attribution value no matter if the object of interest is actually back. We note that the Expected Gradient (Erion al. 2019) not biased reference value by this theoretic definition since the baseline is actually a distribution. However, for feature values that are close to the distribution of, the attribution score will be lower (but not as our theoretic definition), when feature values are far from the distribution of, the the attribution score will be larger, which still has some biased involve. We leave further investigation of the problem to future work to use more advanced analysis to quantify such bias for explanations when the baseline follows distribution.
In Appendix A.2, we added theoretical analysis that when a feature is equal to the replaced reference value, no matter how important it actually is, it will not contribute to the Deletion score nor the Insertion score. However, the lower the deletion score is better, and the higher the insertion score is better, and choosing an important feature that corresponds to the reference value will inevitably not improve the Deletion score and Insertion score. The reference values such as blurring out or adding noise may still make the original features unchanged (such as when the main part of the image is already blurred, blurring the image will not change the image, and thus the main part of the image is biased to blurred baseline).
A.1 BIAS FOR REFERENCE- VALUE BASED EXPLANATIONS
Theorem A.1 For any reference-value based explanation with the form off, 2, x²) (x- z') % (f,, x. x²) for any meta-function K, we know that if x; = I'z, ox(f.x) = 0. That is, when ever a feature value coincides with the baseline value x', it will get 0 attribution even if is the main feature contributing to the prediction. We call such explanations biased to the reference value x'.
Corollary A.1 IG, LRP, Deeplift are biased to the reference value x'.
P.za = =EPEP.. II up I=)pp where Pse is the Following the definition in (Ancona al. 2018). let Uz. set of all paths that connect an unit to unit in a deep neural network, Wp are the weights existing in path p. = be the value of an unit before nonlinear activation, and 9() be any generic function. Note that if g() = f'O, the definition corresponds to the standard partial derivative of unit e unit i.
f/' a==
0f(z' + ta(x - -²)) da
(f,)))) = =(x; - --))= K(,,,, 2,,),, X'), where K() =
(7)
Or.
G. (f,)) = (xz - x1)) (f, x, x'), where x' = 0 and K = 00 f²1(x)
f(x)
with g =
Ox:
(8)
26 fl))
f(z) - f(z!)
(x; x²) K(J,,,a'), where K K(J,x,x') (f,z) pecplift(s,z))
Deeplift
with
Ox;
z
For example, if the reference value a' is a zero vector (which means black pixels in image), then any black pixel will get zero attribution value no matter if the object of interest is actually back.
Theorem A.2 For any average reference-value based explanation with the form o(f. xz 2²) Eng [x - x') & K(fx)) for some meta function K, i = Eet [x]]. de(f.x)) = O. That is, they are biased to the reference value E.t (x').
Corollary A.2 Averaging LRP over multiple baselines are bias the reference value Eg'~pe [x'].
d gargLRr (F x²) E.girpp [[: - x!) K(fxx))
(10)
where K(fxx)= 80 {05(z) with g [(z)
dz,
14

---

Published as a conference paper at ICLR 2021
Theorem A.3 The baseline Shapley value (Sundararajan & Najmi 2019) is biased to reference value
|S!! (IN)) 1-| - SCNV [N|
Φ BShap
(f2,,2 =
(c(S
(11)
where u(s) f(zst and N is the of all features.
These above analysis shows that more explanations are also biased to reference value. We note that by Expected Gradient (Erion al. 2019) is not biased reference value by this theoretic definition since the baseline x' is actually a distribution. However, for feature values I; that are close to the distribution of 2 the attribution score will be lower (but not our theoretic definition), when feature values x; are far from the distribution of x the the attribution score will be larger, which still shows some level of bias. We leave this future work use more advanced analysis techniques to quantify such biased for explanations when the baseline follows distribution.
A.2 BIAS FOR REFERENCE-VALE VALUE BASED EVALUATIONS
Definition A.1 (Informal) Given a data point x, reference point x', the deletion score of a model I given a set of important features featurres S (and denote the complement of S as S), which we abbreviate as DEL(x, x', S), defined as (x's) Here, x' can be a fixed value or a random value, or even blurred component (by slight abuse of notations). Similarly, we define the insertion score for data point n, reference point x', important set of features S, and a model f as INSR(1r, ,S) = f(1s; r'g).
Note that the lower the DEL score is better. and the higher the INSR score is better.
Theorem A.4 If = I then DEL(x, x', SU i g S. Similarly, if = x/p. INSR(a, x' S) INSR x', for S
The implication of Thm. A.4 is that if feature happens to correspond to the reference value, no matter how important actually is, it will not contribute to the DEL score nor the INSR score. However, the lower the DEL score is better, and the higher the INSR score is better, and choosing an important feature that corresponds to the reference value will inevitably not improve the DEL score and INSR score. Thus, DEL score and INSR score will deem feature with the same value the reference value as non-important even if the features are actually crucial.
B MORE ON ESTIMATING ADVERSARIAL ROBUSTNESS
Our work relies on measuring the adversarial perturbation norm on a subset of features, which can be constrained adversarial robustness problem. Adversarial robustness has been extensively studied in the past few years. The adversarial robustness of a machine learning model on given sample can be defined the shortest distance from the sample to the decision boundary, which
corresponds to our definition in Eqn. D Algorithms have been proposed for finding adversarial examples (feasible solutions of Eqn. [ including (Goodfellow al. 2014 Carlini & Wagner 2017,
Madry et al., 2017). However, those algorithms only work for neural networks, while for other models such tree based models or nearest neighbor classifiers, adversarial examples can found by decision based attacks (Brendel et al. 2017] Cheng et al. 2018)] [Cen et 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 lower bound Eqn. T Examples include (Singh et al. 2018 Wong Kolter 2018 Zhang et al. 2018). In principal, work can also apply these verification methods for getting approximate solution of Eqn. [ but in practice they are very slow to run and often gives loose lower bounds on regular trained networks.
15

---

Published as a conference paper at ICLR 2021
C IMPLEMENTATION DETAIL
Underlying Models Used. In the experiment conducted on MNIST dataset, we train a convolu- tional neural network (CNN) with 99% testing accuracy. The training and testing split used in the experiments are the default split as provided by the original dataset. For each instance, the inputs are loaded into the range of [0, 1 On ImageNet dataset, we deploy a pre-trained ResNet model obtained from the Pytorch library For each image, the imputs are first loaded into the range of [0. 1] and normalized using mean [0.485, 0.456, 0.406] and standard deviation [0.229, 0.224, 0.225 On Yahoo! Answers dataset, we train BiL.TMM sentence classifier which attains testing accuracy of %. For the model configuration and training hyperparameters, we strictly follow the official GLUE the pretrained GloVe word embedding to initialize the LSTM embedding layer where the hidden size is 300.
repository R Specifically, we first tokenize the dataset by word-level tokenizer; and then
Method Implementation Details and Hyperparameters. For the proposed Greedy and Greedy- AS, each greedy iteration, we include the top-5% features with highest scores into the relevant set to further speed up the selection process. As discussed in Section 3.2, we use PGD attack with binary search to approximately compute the robustness value in Eqn. T the experiments, we set the PGD attack step size to be 1.0 and number of steps to be 100. The hyperparameters are chosen such that the PGD attack could most efficiently provide the tightest upper bound on the true robustness value. As mentioned in Section 4.2] we solve Eqn. b subsampling from all possible subsets of ST. Specifically, we compute the coefficients w with respect to 5000 sampled subsets when learning the regression.
For CFX, since the original objective in (aachter et al. 2017) has no control over the number of features that could differ from the input, we add Lormorm constraint to enforce sparsity in the difference and enable selection of top-K K most relevant features.
For text classification models, in the experiments, we evaluate the top-5 keywords selected by different explanations with the proposed Robustness-S, (-S,) measurements and the existing Insertion and Deletion scores with different baseline values. In the experiments, we represent a length-n sentence by embedding vectors where each embedding vector is itself d-dimensional. To calculate the Robustness-S, of an input sentence where the relevant set contains a set indices of the top- k keywords, restrict the embedding vectors of the top-k words be fixed and only allow perturbations on the remaining (n k) d dimensions. Similarly for Robustness-S, we only allow perturbations on the d dimensions corresponding the embedding vectors of the top-k keywords. For Insertion and Deletion score, we follow the same to replace the embedding vectors of the masked words by some selected reference value.
Evaluation Curves. To plot the evaluation curves of a given explanation, measure the expla- nation's 's Robustness-S3 S, and Robustness-S, at different sizes of relevant set |Sp]. Specifically, we measure the explanation's 's performance when |S,] equals to 5%. 10%. .... 45% of the total number of features. Similarly for the Insertion and Deletion criteria, we progressively evaluate the explanation's performance when 5%, 10%, ... 45% of the features are inserted (or removed) from the inputs. After the evaluation curves are plotted, we then calculate the area under curves to summarize the explanation's 's overall performance under each criterion.
Hardware and Code. All the experiments were performed on Intel(R) Xeon(R) CPU E5-2630 v4 2.20GHz and NVIDIA GeForce GTX 1080 Ti GPU. We release our source code along with an example Jupyter notebook for more information.
16

---

Published as a conference paper at ICLR 2021
D EVALUATION CURVES UNDER ROBUSTNESS AND ROBUSTNESS-S.
We show the evaluation curves of different methods under the proposed robustness criteria on MNIST, ImangeNet, and YahoolAnswers in Figure 6 Figure 7 and Figure 8 respectively.
2.75
28
3HAP LOO
Rabustners-
Babustnesss55
2.25
22
Ransom
2.
230
14-
10
15
22
10
15
10
Percentaue of Relevent Festures (15.1d))
Percentaue of Relevent Feetures (15.1d)
Figure 6: Greedy-AS and other existing methods on MNIST.
Creesty45
18
SHOP LDG
Rebustnese 5-
Robustnese:
Nandom
66-
5
13
15
22
25
30
35
10
15
20
25
40
Percenlage of Relevant Fealures (15:1M)
Percenlage of Relevant Features (15:AA)
Figure 7: Greedy-AS and other existing methods on ImageNet.
Creacy-AS
2.25
Grad
Robustness
0.5
Robustress
1.75
0.50
CPX
Randsm
Jethor
0.45
0.40
0.50
Number of Selected Keywords
Number of Selected Keywords
Figure 8: Greedy-AS and other existing methods on Yasoor.
17

---

Published as a conference paper at ICLR 2021
Table AUC of Robustness-S, and Robustness-S, for Greedy-AS and its variants. The higher the better for Robustness-S,; the lower the better for Robustness-S,.
Datasets
Explanations
Greedy-AS
Greedy
One-Step Banzhaf
MNIST
Robustness
98.01
83.57
86.37
Robustness- Sy
82.81
171.56
83.59
ImageNet
Robustness-S.
31.62
21.16
24.54
Robustness-S, S,
43.97
58.45
47.07
E ABLATION STUDY ON GREEDY-AS
Greedy-AS could be seen combination of the original greedy procedure with the approximated contribution cach feature computed by a regression. Here, we examine the importance of both components by comparing the Greedy-AS method two baselines, where one selects important features based only on the pure Greedy method (Section (4.1) and the other utillzees only single step of regression without the iterative greedy procedure. As the latter essentially corresponds to the Banzhaf value, we term this method as One-Step Banzhaf. As shown in T the pure Greedy method suffers degraded performances comparing Greedy-AS under both critera. The inferior performance could be explained by the ignorance of feature correlations which ultimately results in the introduction of noise (see Figure 99. In addition, we also see that Greedy-AS performs better than One-Step Banzhaf. This could result from the fact that One-Step Banzhaf considers the feature interactions among all features with equal probability. However, our objective, we only care about those interactions with the most important features. By iteratively selecting the features with highest Banzhaf value Greedy-AS, we give more weight on the interactions among the most important features through iterations, and as result lead to better performance.
As discussed in Section 4.2
Original
Greedy
One-Step Banzhaf
Greedy-AS
8
Figure 9: Visualization on our proposed methods. The top features selected by Greedy-AS are less noisy.
18

---

Published as a conference paper at ICLR 2021
F EVALUATION CURVES UNDER INSERTION AND DELETION
We show the evaluation curves of different methods under the Insertion and Delction criteria MNIST and ImageNet in Figure 10 Figure
and Figure 12 respectively.
Output Logits (pre-softman)
Output Logits (tre (prersoftmad)
SHAP
17.5
LOO
12.5
75-
8
10
15
22
25
32
60
22
35
Parcentage of Relevant Features Inse rtod
Parcentage Rolovant Features Ramoved
Figure 10: Greedy-AS and other existing methods MNIST.
Ourput Logits (pre-softmax)
Ouigue Logits (pre solssol
17.9
SHAP
23.0
U00 4-
12.5
10.0
Random
3.3
2.
Parcentage of Relevant Foatures Ince Inserted
Percentage Rolovant Features Removed
Figure 11: Greedy-AS and other existing methods ImageNet.
Output Lagits (pre-softme)
Output Logits (pre-softmax
0:24
0.20
0.44
4.0
Keywords
Keywords
Figure 12: Greedy-AS and other existing methods on Yahoo!Answers.
19

---

Published as a conference paper at ICLR 2021
G STUDENT'S S t-TEST ON THE PERFORMANCE IMPROVEMENT OF GREEDY-AS OVER EXISTING METHODS
We conduct a set of Student's t-tests to further verify that the outperformances of the proposed Greedy-AS over existing methods are indeed statistically significant. We compare the AUCs of Greedy-AS and other methods across different criteria. In Table we show the t-test results on the AUCs of Robustness-S, and Robustness-Sp. well the results on the AUCs of Insertion and Deletion criteria. In the tables, win (loss) indicates that the performance improvement (drop) of Greedy-AS to the baselines is statistically significant; otherwise, we use draw to indicate insignificant difference between the performances. From the results, we positively verify the statistical significance of the performance improvements of our proposed method over existing explanations on various criteria.
Table The proposed Greedy-AS versus other explanations under various criteria with Student's
I-test at 95% confidence level.
Greedy-AS vs.
Datasets
Criteria
Grad
IG
SHAP
LOO BBMP
CFX
MNIST
Robustness-S:
win win
win
win
win
win
Robustness-S.
win win
win
win
win
win
Insertion
win win
win
win
win
win
Deletion
win win
win
win
win
win
ImageNet
Robustness-S, win win
win
win
win
win
Robustness-SS
draw win
win
win
win
draw
Insertion win win
win
win
win
win
Deletion
draw draw loss
win
win
draw
20

---

Published as a conference paper at ICLR 2021
H ANALYSIS ON THE EFFECT OF REFERENCE VALUE
We provide Table 5 and Table 6 an empirical analysis on how different reference values would affect the evaluation results of different explanation methods. The corresponding evaluation curves are shown in Figure 14 Figure [5 Figure [6 and Figure 17 We as well summarize the performances of different explanations across different reference values in Figure [3] We see that Greedy-AS performs most stably among the top across different reference values, while methods like IG, SHAP, and LOO suffer performance degradation when the reference value (used in Insertion/Deletion) moves away from zero, the intrinsic reference value these methods rely on.
Table 5: AUC of the Insertion and Deletion criteria with different reference values for various explanations on MNIST. The higher the better for Insertion; the lower the better for Deletion.
Reference Values
Explanations
Grad
IG
SHAP
LOO
BBMP
CFX
EG
Random
Greedy AS
Reference value rand UnifromtO,
Insertion
174.18
177.
125.93
121.99
108.97
102.05
228.64
51.71
270.75
Deletion
153.58
150.90
213.32
274.77
137.69
113.21
312.07
94.24
Reference value 0
Insertion
393.25
802.57
656.55
706.63
212.12
81.59
450.37
120.65
502.32
Deletion
214.81
134.64
66.36
119.91
362.95
840.78
138.57
453.01
252.44
Reference value
Insertion
293.92
424.45
412.87
453.29
142.00
77.33
341.05
78.73
455.74
Deletion
162.24
133.06
115.88
204.75
442.23
354,05
161.28
426.21
90.89
Reference value 0.5 Reference value
Insertion
218.18
317.55
136.51
189.87
42.76
86.80
382.31
49.15
479.92
Deletion
209.83
258.50
271.11
424.66
549.
90.50
392.69
155.59
Insertion
220.90
79.28
125.73
163.46
285.6
67.35
325,47
Deletion
305.17
305.38
481.67
712.46
708.93
89,38
250.57
451.18
176.85
Reference value
Insertion
234.61
206. 54
89.8 83
128.71
25.31
229.02
276.48
81.44
313.66
Deletion
364.01
372.18
647.68
956.88
823,90
101.31
310.50
495.91
223.99
Table 6: AUC of the Insertion and Deletion criteria with different reference values for various explanations on ImageNet. The higher the better for Insertion; the lower the better for Deletion.
Reference Values
Explanations
Grad
SHAP
LOO
BBMP
CFX
Random
Greedy-AS
Reference value rand ~ UnifrommO, I)
Insertion
86.16
Deletion
276.78
256.51
143.27
290.10
615.13
281.12
244.88
314.82
219.52
Reference value
Insertion
125.32
214.85
85.57
61.37
138.00
135.31
183.47
69.57
182.61
Deletion
313.04
260.75
262.78
333.98
288.52
234.34
Reference value 0.25
Insertion
291.06
329.24
39.74
163.81
243.92
287.58
245.46
103.63
293.30
Deletion
408.95
395.37
328.50
365.03
686.75
421.56
433.78
516.56
322,50
Reference value 0,5
Insertion
301.78
343.77
45.77
178.18 18
250.25
270.03
348.66
129.65
305.87
Deletion
431.17
412.70
345.84
388.64
689.08
421.89
420.31
546.30
321.11
Reference value 0.75
Insertion
222.63
217.26
29.39
131.92
243.44
215.11
248. 74
87.38
286.40
Deletion
364.28
340.24
279.51
325.71
701.97
375.87
329.11
402.97
262.36
Reference value
Insertion
136.10
89.26
109.44
189.96
Deletion
245.57
218.09
207.57
234.28
658.54
329.20
203.84
217.39
191.96
GreadyvAB
Grad
8HAP
88MP
Random
Peniing
Ranting
Paniina
Banking
Reference Value
Reference Value
Reference Value
Reference Value
Figure 13: Ranking among different explanations. From left to right: MNIST Insertion/Deletion: ImageNet Insertion/Delettin. Rankings correspond to the relative rank among all methods, i.e. 1. We see performances of zero-baseline explanations, e.g. IG/SHAP/LOO, degrade as the reference value moves away from zero.
21

---

Published as a conference paper at ICLR 2021
Cuipur sogat Eoreeaat mead
Sercentage Retevart Features insented
Percertage
Relirann Festures Insented
Percertage of Rebovare Foutuees Insoetedd
(a) Insertion with random baseline
(b) Insertion with O bascline
(c) Insertion with 0.25 baseline
Ouiputt Logtts pre-sortima)
Ourpett Logts con-oarrmmmdd
50-
16
15
2
2
30
30
(d) Insertion with 0.5 baseline
(e) Insertion with 0.75 baseline
(f) Insertion with 1 baseline
Figure 14: Evaluation curves of Insertion criteria on MNIST with different reference values.
400
23.5
bogts brrowdamee
835
50
Parcentage of Rokorut Palturea Bamooodd
Peruarapee of Redevand Fastunos Barrveed
Persintgge of Redomatt Peeturas Remrooed
(a) Deletion with random baseline
(b) Deletion with baseline
(c) Deletion with 0.25 baseline
Outtunt sogits Stresottmett
Peccntaage Rexevatc Festures Removed
Percertage Retevont Festures Romoveed
Perconaae Retewant hoatures Remivod
(d) Deletion with 0.5 baseline
(e) Deletion with 0.75 baseline
(f) Deletion with baseline
Figure 15: Evaluation eurves of Deletion criteria on MNIST with different reference values.
22

---

Published as a conference paper at ICLR 2021
Ouiteun Loatte Exreeoart maees
Output Coree sort mend
Sercentagg Retevart Festures insented
Percentace Redirann Festures Inserted
Percertage of Relevare Foatuees Insanted
(a) Insertion with random baseline
(b) Insertion with 0 bascline
(c) Insertion with 0.25 baseline
Output Logtts pre-sottimat
Ourpett Logtss (eresarfmma)
16 15
30 25. 20 25
(d) Insertion with 0.5 baseline
(e) Insertion with 0.75 baseline
(f) Insertion with I baseline
Figure 16: Evaluation curves of Insertion criteria on ImageNet with different reference values.
825
275
32.
201
bogts
25
Parcntage of Rakorat Pautures Bamosed
Peruarapee of Redovand Fastunos Burroved
Persnnagee Redomatt Peeturss Remoooed
(a) Deletion with random baseline
(b) Deletion with baseline
(c) Deletion with 0.25 baseline
12.5
Outmunt Logate
Recontage Resevart Festures Removed
Percertage Retevont Fostures Removell
Perconsage Helewant Roaturre Romivod
(d) Deletion with 0.5 baseline
(e) Deletion with 0.75 baseline
(f) Deletion with baseline
Figure 17: Evaluation curves Deletion criteria on ImageNet with different reference values.
23

---

Published as a conference paper at ICLR 2021
1 SANITY CHECK
Recent literature has pointed out that an appropriate explanation should be related to the model being explained (Adebayo et al. 2018). To ensure that our proposed explanation does indeed reflect the model behavior, we conduct the sanity check proposed by AAdebayo et al. (2018) to check if our explanations are adequately different when the model parameters are randomly re-initialized. In the experiment, we randomly re-im initialize the last fully- conneced layer of the neural network model. We then compute the rank correlation between explanation computed w.r.t. the original model and that w.r.t. the randomized model. From T we observe that Greedy-AS has much lower rank correlation comparing to Grad, IG, and LOO, suggesting that Greedy-AS indeed sensitive model parameter change and is able to pass the sanity check.
Table 7: Rank correlation between explanations with respect to original and randomized model.
Grad
IG
SHAP
LOO
BBMP
CFX
Greedy-AS
Cor:.
0.30
0.30
0.11
0.49
0.17
0.26
0.18
J EXPLANATION SENSITIVITY ANALYSIS
In a recent study, Yeh et al. (0119) proposed sensitivity measurement to evaluate how large an explanation would change when small perturbation is applied to the original input. The measurement could be seen as the lower bound of the local Lipschitz (Alvarez Melis & Jaakkola| 2018) of an explanation functional, and could calculated efficiently by sampling. Following Yeh et al. (0019). we define similar sensitivity measurement for set explanation follows.
Definition J11 Given a black-box model to be explained f. an input x, an explanation functional $(J v) that returns a set of relevant features, and radius r defining a local neighhorhood around x, we define the sensitivity for an explanation as:
(f. (.(.,))
(, = max 11
(12)
By Eqn. we see that the sensitivity of an explanation equals 0 when the relevant set returned by the explanation remains the same in all local neighhorhood of radius r centered around the original input a. On the other hand, the sensitivity equals when there exists some y within the local neighborhood of x where the relevant set returned by ( f y) is totally disjoint from @ .r). We shall however note that the sensitivity alone should not serve as the sole measurement for explanation, since meaningless constant explanation could always achieve 0 sensitivity. We show in Table & sensitivity analysis of different explanations MNIST dataset where we consider ((f, x:) to be the top-20% relevant features selected by an explanation method, and set r = 0.1 in the experiments.
From Table 8 we see that Expected Gradient has the least sensitivity since EG could be variant of the smoothing technique (Smilkov et al. (017)) (discussed in (Sturmfels et al. 2020)). which is shown to be effective approach to reduce explanation sensitivity (Yeh al. 2019). While the proposed Greedy-AS has relatively large sensitivity, we believe such result might be highly correlated to the underlying sensitivity of the model f itself (since Greedy-AS aims to faithfully reflect the decision boundary of the model around an input). Thus, one possible way to reduce the sensitivity of Greedy-AS is to consider an adversarially more robust underlying model whose decision boundary is less sensitive to perturbations. Another possible way is to consider smoothing the explanation provided by Greedy-AS. We leave further improvement on the sensitivity of Greedy-AS as a future direction.
Table 8: Sensitivity of Different Explanations.
Explanation
Grad
IG
LOO
BBMP
SHAP
CFX
BG
Random
Greedy-AS
Sensitivity
0.45
0.38
0.31
0.38
0.52
0.57
0.20
0.85
0.61
24

---

Published as a conference paper at ICLR 2021
K
VISUALIZATION ON MNIST
We provide more examples on visualized explanations on MNIST in Figure 18
Original
Grad
IG
EG
SHAP
LOO
BBMP
CFX
Greedy-AS
O
0
/
/
2
2
2
333
333336
4
5
3
7
8
9
Figure 18: Visualization of different explanations on MNIST. The highlighted pixels are the top 20% relevant pixels selected by different methods. We see that Greedy-AS focuses both on crucial positive and pertinent negative regions.
25

---

Published as a conference paper at ICLR 2021
L VISUALIZATION ON IMAGENET
We provide more examples on visualized explanations on ImageNet in Figure 19
Original
Grad
EG
SHAP
LOO
BBMP
CFX
Greedy-AS
Figure 19: Visualization of different explanations on ImageNet. We see that Greedy-AS focuses more compactly on the areas containing the actual objects being classified.
26

---

Published as a conference paper at ICLR 2021
Ours
LRP
Oramas et al.
Ours
LRP
Oramas et al.
Against
Against
Against
Against
N/A
(a) Targeted explanation for against 0 and 7 respec(b) Targeted explanation for against 4 and 2 respec- tively.
tively.
Figure 20: Comparisons between different methods for targeted explanation against different target classes on MNIST. We note that Oramas et al. (2019) could not handle arbitrarily specified target class and thus is not available to produce different explanations for different target classes.
M COMPARISONS WITH OTHER EXPLANATIONS CAPTURING PERTINENT NEGATIVE FEATURES
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. Most current 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 Bach et al. (2015) to capture pertinent negative features heavily depends on the input range. In Samek et al. (2016), the input images are normalized have zero mean and standard deviation of one where the black background will have non-zero value. In such case, LRP would have non-zero attributions on the black background pixels which allows the explanation to capture pertinent negative features. However, later shown in Dhurandhar et al. (2018), if the input pixel intensity is normalized into the range between and I where the background pixels have the values of LRP failed to highlight pertinent negative pixels since the background would always have zero attribution. This is due to the fact that LRP equivalent to multiplication between Grad and input in 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 would need to infer by themselves what target class the pertinent negative features are preventing against. To further grasp the difference, we compare our explanation with theirs in Figure 20 We borrow the results from Oramas et al. (2019) for visualization of their method. Qualitatively, we observe that our method gives the most intuitive explanations. For example, in Figure 20a the first row shows different explanations that highlight different relevant regions supporting the prediction of 2 instead of O. Among the explanations, our method is the only one that highlights the right tail part (green circled) of the digit 2 which also serves as crucial evidence of 2 against 0 in addition to the left vertical gap (which when presented would make 2 looks like a 0) that is roughly highlighted by all three methods. Furthermore, as we change the target class to 7 (as shown in the second row). the explanation provided by LRP does not seem to differ much. This suggests that LRP not sensitive the target class change and might fail to provide useful insights towards targeted explanation. On the contrary, we observe that our explanation has drastic change between different target classes. When explaining against the target 7, our explanation highlights the lower left green circled part which when turned off will make 2 becomes 7. These results might suggest our method is more capable of handling such targeted explanation task.
27

---

Published as a conference paper at ICLR 2021
N QUANTITATIVE RESULTS ON TEXT DATASET
In this section, we conduct a set of quantitative analysis on different explanations for text classification model on Yahoo! dataset.
Table 9: AUC of the different evaluation criteria for various explanations on Yasoo!'Aswers. The higher the better for Robustness-S, and Insertion; the lower the better for Robustness-S, and Deletion.
Criteria
Grad
IG
SHAP
LOO
EG
Random
Greedy-AS
CFX
Robustness-55 Sr
1.97
1.86
1.81
1.74
1.96
1.71
2.13
1.95
Robustness-S, S,
2.91
3.14
3.34
4.04
2.99
7.64
2.41
2.96
Insertion (random baseline)
0.06
0.06
0.07
0.18
0.20
0.10
0.21
0.05
Deletion (random baseline)
2.57
2.96
2.23
2.07
2.07
2.63
1.56
2.35
Insertion (zero buseline)
2.59
6.31
8.63
3.61
3.34
0.34
3.64
2.95
Deletion (zero bascline)
5.28
5.64
1.52
3.81
5.12
6.30
4.60
5.83
OXtgul Long ta freeonkkmee
Cebase Log (ore-ortmmo))
210
Number ectedd keywords
Selected
(a) Robustness-Sy S,
(b) Insertion (random baseline)
Insertion (zero baseline)
Carteen ogghn 1p 2000000
$00
450
4.00
375
3.5
Numt ber Selected Keywords
Number Selected Koyworts
Nunber of Se octed keywords
(d) Robustness-S.
(c) Deletion (random baseline)
(f) Deletion (zero baseline)
Figure 21: Evaluation curves Yahoo!Answers dataset.
28

---

Published as a conference paper at ICLR 2021
O
QUALITATIVE RESULTS ON TEXT DATASET
Input
What kind of football cleats should gee High Cut or Mid out.
aat playing en the line?
inpu
RReeiiberro sect ore rer lavnte playee out therr why dee they repluce
Gready-AS
ams playing on the
(Whuet kind of (nothel Bleati ihrold get, High Cut or Mid--ost,
Crendyy
then7 complete missed Do
(irussion lake my livente out theme leticied two?
WWart kind of (scatail dlsati should and High Cut or Mid-cut,
am ptaying en lime?
Grod
Blevrt loseplicel ressel tun bill Do they
Swee?
am playing
WWen Gini @f Bismall dleats should get, High Out or Mid-cout.
10
Rheert courgaierly wii tuan they way baatched Boal?
hake
LGD
Whet kind factball Beans should get High or Mid-cut,]
LO00
them? completthy ribraed that
and kikil laanti players oot why dii they replice wny
terr?
SHAP
Whot Bilthall eleats should get High
lake laveri players out why repluce
EG
Whot Bistaall should get High
playing
Ricosteni lake ore my linene out there inticted repicee tenn complitee
Du
Anchor
(What
playing en the tiwe?
cleats should High
Ancher
Berrt compleae misedd tuan part De they bay why the rudiched there?
CFX
What football Brani inould High Mid-curt. am playing on the line?
CRR
laa Baxe? cosephich ressel bus mar Do they bay wny the jnsiiiial taxe?
wiry
Most Relevant
Relevant
(a) Label for the sentence is: "Sports""
(b) Label for the sentence is: "Sports"
Shoeld we get of selfiare in the UB? No each assistanco or food
Input
Where can find downlosdable music videos Ingaly?
Gready-A5
Shoadd
stampe?
Mil cash assistance food
Greedy AS
Where
Bowntoadsei music videos lngali?
Shosee get instarn the UST ho cech insistanei or food
Grad
Whene can find
Bownlcassabl music videos Ingati??
80
starspe
1G
Wheni can find
BownlondiBl music Vidkos legaly?
LO0
Should we get of selttre in Bill US7 Bil Eash suentanca or faod sterroo?
LG0
Whore Bownloadsble music Wokoo logaly?
SHAP
SHAP
Where San find downloadable music Videos legaly?
Shoedd we get rdd Bostsil in thi US? No cooh Brontased or fand
EG
Bowntondibli videos laguli??
sampp?
Ancher
Hampe?
each avsistanco
Anchor
Where can find downloudable inuiti videos logaly?
DFX
Snssill
cush invintence fard
CFX
Whara
Bountoadsili music videos Ingati?
Most Rolevant
Less Relovent
Most Relevant
Relevart
(c) Label for the sentence is: "Politics & Gov(d) Label for the sentence is: "Entertainment & emment"
Music"
whot bright planet otten misttaken UF09 Both muroery
Input
to ftr original factory condition?
computer vinusse arssed restore hard drive
Greody:49 -65
annd jupiter often mataken
UEB?
event.
Greedy-A5
[o:1o orggnall fastory conditie??
[5] computte inssed get crased you (estoné your hard drive
Gred
what bright Blanei otten instataii for UMB? Both murcery
sand Biniii are often mataken for such an event.
Grad
sdginst hastory condition
vinuses pill srased you restore your hard ditiee
(w/at Briiid planel is ottan misttaen for UBM Both muroary
De Kompunne Viruses Bill trased if you restore your hard drive
and Ranther are otten motaken much avent.
original fastory Conditoo??
What brighi Hannil often mistasen UF0? both murcery
L00
De kampone
Brussi get erased you restore your buri drive
SHAP
what Bright
UF0?
muroery
SHAP
Wrused srased you restore your hard
condition?
EG
and Miniii are often mosikon for such event
Both muroery
EG
original factory condition
hard drive
Anchor
what brightt planct olten mistaken for US Both muroery
and paphher are oftan mataher for such an event.
Anchor
original
factory condition?
restore hard drive
and are often mattken for such event
What bright planel is otlenn mistanei for UPB7 Both murbery
GFX
to Hte original factory condition?
inasui you bnatoni your hard drive
Most Redavent
Lencs Relesant
Most Relevant
Leos Relevant
(e) Label for the sentence is: "Science & Math(f) Label for the sentence is: "Computers & ematics"
Internet"
traditions colebarate
Greedy-45
what kind of Busiiton you havel colobrate Nasi jusl?
Lbc. 1364
year?
[ec. 1664.
oppeer
1G
what sind 88
Esdttion you have Bitebmni New yoor?
[M0: 1100
Diseay cranceer spaeal detut cartees "Te tas Life
you Biiebrati New year?
for opuiial tie ankut fians The Lifle
111
SHAP
what Biiil of Busiitin you have selebroni New year?
apunil cales in dnkie foos. The ta Lilde
what wind @1
ausitionn you have Bélebrune Newl yoar?
apuato in
The Lifle
Anchor
what Mitl of busition
celebrate New year?
iuger
moleee in adler nartern The Wise tike
CFX
what kind
Inaiitonn you hase celebratte New year?
Eint Inder/ for metee In cartees The Ware Lifl
Most Relevant
Less Relevant
Most Retevant
Lesu Relevant
(g) Label for the sentence is: "Socicty & Cul- ture"
(h) Label for the sentence is: "Entertainment & Music"
Figure 22: More examples for explanations on text classification model.
29

---

Published as a conference paper at ICLR 2021
P USER STUDY ON TEXT DATASET
To further compare the top-5 relevant keywords provided by various explanations, we conducted an user study involving 30 different text examples (sentences) and 30 different users with Computer Science background by convenience sampling. In the study, each user is presented with a set of sentences and their corresponding categories. We then asked each user to highlight for each sentence that they consider to be most relevant to the ground truth label of the corresponding sentence. After collecting the feedback, for each sentence, we have 10 sets of different labels provided by the users. For each sentence, we then select the keywords that have the highest frequency of being marked among the users and treat those keywords as the ground truth explanation for the corresponding sentence.
keywords
We leverage such user labels to calculate the precision @ and mean Average Precision (mAP) for each explanation method. We show the results in Table 10 We observe that Greedy-AS has the highest overall precision score, while the top-1 keyword selected by Anchor and IG match user intuition the most. If we believe that users can correctly pick the correct keywords that are responsible for the model prediction, then the p@k and mAP measure how well the explanation captures the correct keywords that responsible for the model prediction. We believe the good result study provides extra evidence that our method identifies features that are responsible for the actual prediction.
Table 10: Precision of Explanations with User Labeled Ground Truth
p@] 1
p@2
p@3
p@4
p@5
mAP
Greedy-AS
0.83
0.78
0.78
0.75
0.68
0.76
Grad
0.83
0.70
0.72
0.67
0.61
0.71
IG
0.83
0.67
0.56
0.52
0.50
0.61
SHAP
0.73
0.75
0.58
0.51
0.64
LOO
0.67
0.67
0.52
0,48
0.45
0,56
EG
0.90
0.75
0.69
0.67
0.63
0.73
Anchor
0.93
CFX
0.83
0.68
0.67
0.61
0.67
Random
0.17
0.27
0.28
0.29
0.27
0.25
Q RUNTIME ANALYSIS
We show below the average runtime (wall clock time) of different methods for computing explanation for single image on MNIST and ImageNet. For Greedy and Greedy-AS, we show the time needed to compute the top-20% relevant features.
Table 11: Runtime of Different Explanations.
Explanation
Grad
IG
LOO
BBMP
SHAP
CFX
EG
Greedy
Greedy-AS
MNIST Runtime (second)
0.005
0.023
0.004
4.154
9.673
8.582
6.123
9.532
13.621
ImageNet Runtime (second)
0.024
0.138
0.849
8.536
111.794
25.577
64.270
117.781
135.838
Note that as Anchor tends to select only one keyword in each sentence, provide only its precision @ in
Table TO
30


Reviews:
[{"review_id": "ziW9dSAwJML", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Many interpretability techniques center on identifying the subset of “most relevant features”. In this work, the authors propose defining this set as the set of features that are easiest to attack adversarially (in an $L_p$ sense). \n\nFirst off, the paper was somewhat difficult to read because of a frustrating amount of vertical space LaTeX hacking, so much so that the spacing between sections and paragraphs is even less than the normal spacing between sentences. This is not a good way of squeezing everything into 8 pages. \n\nApart from that, the paper is comprehensive in its experimental evaluation, with a good suite of appropriate baselines, sanity checks, and human studies. I think that it is an interesting complement to the current suite of feature attribution techniques. Conceptually, it is quite similar; as the authors note, there have been many related techniques that try to “remove features” by adding noise to them, setting them to a baseline value, or blurring them; here, the authors instead consider adversarially perturbing them, and they propose a modified greedy strategy that seems to work well. It is a bit unclear to me why considering adversarial perturbations is a priori any more convincing than, e.g., considering blurring out or adding noise to the selected features, but they serve slightly different purposes and it's reasonable that these methods could be complementary.\n\nEmpirically, this method leads to gains under insertion and deletion metrics, compared to existing techniques. I had a couple of questions about these baseline comparisons:\n\n1. I’m a bit confused as to why BBMP does so poorly under the insertion and deletion games, given that it explicitly optimizes for these. Could the authors discuss this? From Figure 11, it looks like the implementation of BBMP seems unoptimized; at least, it returns degenerate results that are very different from the examples shown in the original paper. There's a follow-up https://arxiv.org/pdf/1910.08485.pdf that similarly optimizes for a mask of a fixed size, which seems to outperform many of the other methods here, so I'm confused why the results are so different.\n\n2. S5.2: The authors say that SHAP obtains a better performance under the deletion criterion because it exploits adversarial artifacts. Shouldn’t this problem be even worse for the Greedy(-AS) methods, which explicitly seek to exploit adversarial artifacts? Why are we not seeing that?\n\n**Details:**\n\n3. Assumptions 1 and 2 are not precisely defined; please either state them formally, or make it clear that they are informal motivations. \n\n4. Definition 3.1: is $\\epsilon_S^*$ a function of $x$ and $y$? How are the overall Robustness values calculated then? By averaging? \n\n**Update**\nThank you to the authors for the detailed responses and revisions. I have adjusted my score upwards. I think this is a useful exploration of an alternative means of quantifying feature importance, with intriguing results: somehow, optimizing for adversarial robustness also seems to optimize for the score on insertion/deletion games. Further exploration of that issue (or at least, elevating some of the many appendices on that issue to the main text) would, in my opinion, increase the impact of the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OoSoeIiVAiu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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: The goal of the paper is to present a new explanation benchmark and explanation method for ML models. I think the benchmark is interesting but insufficiently motivated, especially given existing concern in the field about the degree to which small local perturbations yield biased results because of saturation. The explanation method seems to work well, even on removal-based benchmarks, which is great! Evaluation is limited w.r.t. datasets and methods compared against, however. Overall, some serious positives and important negatives make my impression borderline, leaning reject. However, addressing the weaknesses well could definitely raise my score.\n\n**Update**: The authors' update is comprehensive, well-thought out, and demonstrates significant improvements to the paper; I have raised my score to reflect this.\n\nObjective: Use the adversarial robustness framework to develop both a benchmark for ML model explanations and new methods to actually explain ML models.\n\nStrengths: \n* I think the distinction from previous removal-based work, which to my knowledge is the primary benchmarking focus, is well-posed.\n* The adversarial robustness framework is presented very clearly and seems to get at a different question than previous benchmarks, which is a useful contribution.\n* The explanation method seems well-designed.\n* Experiments show very good results for Greedy-AS.\n* I really appreciated Table 2, because it does not seem like enough to show Greedy-AS does the best job of optimizing for the thing (only) it optimizes for. These additional results are impressive, though I wish I understood why Greedy-AS does better on them.\n\nWeaknesses:\n* From the introduction, I am a little concerned about this method because of its intentional focus on small perturbations. This is a well-known problem with gradients that integrated gradients improves on by adding a reference; gradients measure small perturbations around the input, but do a bad job detecting important features because nonlinearities often saturate around the inputs. I think there's a lot of empirical evidence that IG improves on grads for this reason. The benchmark is subject to this issue -- I tend to think a priori that a test where grads shows good performance may be a flawed test -- and I'd tend to think the explanation method would suffer for this reason as well. Overall, it is known that explanation methods exist that do not need references; these just tend to be worse on a lot of benchmarks, for reasons like saturation. There's a lot of room here to boost the value of the paper, in my opinion. (1) Explain why saturation isn't an issue with this method and (2) Tie the good results with Greedy-AS to what seems to be the key motivation for its introduction -- the independence of reference. If you could show that IG, etc are giving worse results *because* they're being biased by their reference, it'd be very helpful.\n* It makes sense to me that Greedy-AS does better on the benchmark that inspired it, but why does it do better on the removal-based methods? In some sense, this is exactly what methods like SHAP should be optimizing for, so the biggest drawback to this result (which is a good result for your method!) is that I don't have an intuition for why it should be the case. I'd also be interested to see a comparison with a method like Expected Gradients (Erion et al 2019, Sturmfels et al 2020), which averages IG-type explanations over multiple references by default. I also would like to see results on a low-dimensional, maybe tabular dataset, because when SHAP is entirely sampling-based it will have trouble with large numbers of pixels. I'd also be interested in seeing the SHAP results on text. I think it may do a lot better in that case. Even if SHAP wins on tabular or text data, this could be a good thing for your paper, because then it'd be clearer under what conditions Greedy-AS works well.\n* A related concern is the choice of explanation methods in the experiments; for example, IG is one of the best performers in the Table 1/2 benchmarks, but is not used in Figures 4 and 5. Some justifications for the methods picked in these figures would be good; right now it seems like some of the lower-performing methods are being displayed while ideally the strongest benchmarks would be displayed. I think some justification is required here before publication. \n* I'm actually more sold on the explanation method than on the benchmark; I think there's not quite enough justification for the benchmark aside from \"other methods are biased by the reference.\" However, there's not much empirical or theoretical basis for believing the use of a reference is intrinsically bad (as discussed above, references may induce bias, but small perturbations can be biased by things like saturation). I know it's hard to show why one benchmark is better than another, but if the benchmark is a key contribution I think I need more analysis on why it's a better benchmark.\n* I'd also appreciate a bit more detailed results on the non-MNIST experiments, to convince me the method works well in many settings.\n* Overall, having more non-image experiments, and associated discussion, could be helpful. Right now almost all results are images, with one small text example, and I wouldn't be surprised to see very different results on different types of data.\n* I'm concerned the method could be very slow, given that the adversarial optimization is itself embedded in a sampling-based procedure for the Greedy-AS method. Can you add some discussion of the runtime?", "extra_scores": {}, "extra_text": {}}, {"review_id": "E3pud-u7cA", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 main contribution of this work is the proposal, implementation and validation of a new evaluation criteria/measure for explanations based on robustness analysis. The main idea, as I understand it, is innovative, adversarial perturbations: other feature explanation solutions rely on removing features, the method here presented learns a set of features so that we get the smallest perturbation that change in outcome for the selected set and largest perturbation that changes outcome for the rest of the features.\n\nI think that interpretable ML and  Explainable AI need more work on evaluation, and providing measures for that is relevant in these areas. So, I wonder if other conferences in ML/AI will benefit more of this work than ICLR. In general I find the paper strong, interesting and innovative, technically sound.\n\nThe paper provides a very strong empirical analysis using various datasets, even if for me it was hard to follow all the figures, explanations, methods Greedy/Grad. It is hard to interpret some of the figures, fig 2 and 3 provided, since we need to analyze pixels, and check of they are “less noisy”, “rather noisy”, “noisy” etc….\n\nI am not very familiar with using “human study” for a user evaluation, use user study. “Human” study sounds odd to me. \n\nI was hoping that the user study announced in the abstract and introduction would validate the presented metric, and the methods studied. This is really important, since we make explanations to people. I was disappointed to see that the so called “human study” is described in just few lines, telling that 10 people (without specifiying anything else, what kind of participants were those?) labelled the sentences to show that Greedy matches best their labelling (I guess that 5 people per Grad/Greedy). It is hard to see how this user study strengthens the paper, what is the difference between this evaluation and the other presented in the paper were other “humans” observe things on the data/images? It looks to me that the user study is an afterthought, a good attempt to complement the paper, but either is properly done or removed.\n\n\nBut one of my main concerns is actually is the proposed solution, like the actual motivation or basis for it, can they really identify features that are responsible for the predictions made or just find regions that have high sensitivity to changes (adversarial perturbations)? It might be that I got lost in all the evaluations, and I cannot figure out if the real features the model used to make the prediction will be found, or just those that make the prediction change…. Is that so? Are those the same features?\n\n\nWhile reading, I found some small grammar issues; please, double-check the text. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Bl4chsMDNl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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 paper proposes an effective explanation method based on a notion of robustness defined by the authors.\nThe paper is well presented and easy to follow. It compares against state-of-the-art methods and provides valid and statistically significant experimentation. The explanations returned are different from the competitors and useful.\n\nHowever, some points that should be addressed before publication.\nFirst, I suggest to add the evaluation measures for robustness presented in \nHara, S., Ikeno, K., Soma, T., & Maehara, T. (2018). Maximally invariant data perturbation as explanation. arXiv preprint arXiv:1806.07004. \nThe evaluation of Hara is similar to the one adopted w.r.t Insertion/Deletion.\nIn addition, an evaluation measure for robustness different from everything presented in the paper but quite important for having a different validation is the one proposed in \nMelis, D. A., & Jaakkola, T. (2018). Towards robust interpretability with self-explaining neural networks. In Advances in Neural Information Processing Systems (pp. 7775-7784).\nbased on the local Lipschitz estimation.\n\nSecond, an explanation similar to the one reported in the paper is returned by the method presented in \nGuidotti, R., Monreale, A., Matwin, S., & Pedreschi, D. (2019, September). Black Box Explanation by Learning Image Exemplars in the Latent Feature Space. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 189-205). Springer, Cham.\nAnother method that should be considered for comparison as it is based on robust anchors is the one presented on:\nRibeiro, M. T., Singh, S., & Guestrin, C. (2018, February). Anchors: High-Precision Model-Agnostic Explanations. In AAAI (Vol. 18, pp. 1527-1535).\nIt would be interesting to compare the Greedy proposals with these two methods both quantitatively and qualitatively.\n\nThird, an important aspect that is missing for the model proposed is either an analysis of the complexity or even better, the running time for returning explanations. In this way, the user can understand which is the best compromise between robustness and speed.\n\nMinor issues:\n- The results on textual data are not as convincing as those on images. The authors should treat this part of the presentation carefully and with more attention.\n- The authors do not specify in the main paper (or it is not easy to find) which are the classification models explained.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors introduce new evaluation criteria and methods for identifying salient features: rather than earlier approaches which attempt to 'remove' or marginalize out features in various ways, here they consider robustness analysis with small adversarial perturbations in an Lp ball.  For text classification, a user study is included which is appreciated.

In discussion, the authors addressed many points and all reviewers converged to recommend acceptance.

A couple of points could be discussed further if space permits:
the impact of type of perturbation employed; and
the connection between optimizing for adversarial robustness and optimizing for insertion/deletion criteria.
Decision: Accept (Poster)