Title: ROBUST SALIENCY MAPS WITH DISTRIBUTION-PRESERVING DECOYS

Abstract: Saliency methods help to make deep neural network predictions more interpretable by identifying particular features, such as pixels in an image, that contribute most strongly to the network's prediction. Unfortunately, recent evidence suggests that many saliency methods perform poorly when gradients are saturated or in the presence of strong inter-feature dependence or noise injected by an adversarial attack. In this work, we propose a data-driven technique that uses the distributionpreserving decoys to infer robust saliency scores in conjunction with a pre-trained convolutional neural network classifier and any off-the-shelf saliency method. We formulate the generation of decoys as an optimization problem, potentially applicable to any convolutional network architecture. We also propose a novel decoy-enhanced saliency score, which provably compensates for gradient saturation and considers joint activation patterns of pixels in a single-layer convolutional neural network. Empirical results on the ImageNet data set using three different deep neural network architectures-VGGNet, AlexNet and ResNet-show both qualitatively and quantitatively that decoy-enhanced saliency scores outperform raw scores produced by three existing saliency methods. Grad Grad + Decoys IntGrad IntGrad + Decoys SGrad + Decoys SGrad

1. INTRODUCTION:

Deep neural networks (DNNs) deliver remarkable performance in an increasingly wide range of application domains, but they often do so in an inscrutable fashion, delivering predictions without accompanying explanations. In a practical setting such as automated analysis of pathology images, if a patient sample is classified as malignant, then the physician will want to know which parts of the image contribute to this diagnosis. Thus, in general, a DNN that delivers explanations alongside its predictions will enhance the credibility and utility of its predictions for end users (Lipton, 2016) . Two primary classes of methods have been developed for interpreting CNN models. The first class of methods, often referred to as saliency maps, use gradients of classification outcome as a per-pixel importance score to characterize the influence of individual pixels to the prediction (Simonyan et al., 2013; Selvaraju et al., 2016; Binder et al., 2016; Shrikumar et al., 2016; Smilkov et al., 2017; Sundararajan et al., 2017; Levine et al., 2019) . Despite providing apparently meaningful interpretations in practice, these methods exhibit fundamental limitations. First, saliency maps evaluate pixel-wise importance in an isolated fashion by design, implicitly assuming that other pixels are fixed (Singla et al., 2019) . Worse still, the presence of gradient saturation often breaks the assumption that important features in general correspond to large gradients (Sundararajan et al., 2016; Shrikumar et al., 2016; Smilkov et al., 2017) . Specifically, an important pixel may contribute a strong joint effect on the prediction when considered in conjunction with neighboring pixels. However, that important feature may have a tiny gradient locally, in the sense that its marginal contribution is diminishing due to the flattened output of the layer. Finally, Ghorbani et al. (2017) and Kindermans et al. (2017) systematically revealed the fragility of widely-used saliency methods by showing that even an imperceivable perturbation or simple shift transformation of the input data can lead to a large change in the resulting saliency scores. In light of this observation, a key challenge for any saliency method is ensuring that the saliency scores are robust to gradient saturation and perturbations.

A second class of interpretability methods, often based on counterfactual, perturb (i.e., nullifying, blurring, adding noise, or inpainting ) small regions of the image to modify the classifier prediction (Fong & Vedaldi, 2017; Dabkowski & Gal, 2017; Chang et al., 2017; Fan et al., 2017; Chang et al., 2019; Yousefzadeh & O'Leary, 2019; Goyal et al., 2019) . Despite identifying meaningful regions in practice, these methods exhibit several limitations. First, counterfactual-based methods implicitly assume that regions containing the object are the ones most contributed to the prediction (Fan et al., 2017) . However, Moosavi-Dezfooli et al. (2017) revealed that counterfactual-based methods are also vulnerable to the adversarial attacks, which force these explanation methods to output nonrelated backgrounds rather than the meaningful objects as important subregions. In addition, the counterfactual images may be potentially far away from the distribution from which the training samples were drawn (Burns et al., 2019) , causing the classifier behavior ill-defined. Though some efforts have been made to train the saliency extractor and the classifier simultaneously (Fan et al., 2017; Zołna et al., 2019) , the robustness of the resulting explanations are not guaranteed in most cases (Hendrycks & Dietterich, 2019) . In light of this, for any perturbation-based method, a key challenge is ensuring that the perturbations are effective yet preserving the training distribution.

In this work, we propose a data-driven technique to infer robust saliency maps with distributionpreserving perturbations. Given an image of interest, the core idea of this method is to generate a population of perturbed images, referred to as decoy images, that resemble the neural network's intermediate representation of the original image but are conditionally independent of its label. The resulting decoy images capture the variation of the image data originating from either sensor noise or adversarial attacks. The major differences between the proposed and counterfactual-based methods are threefold. First, unlike counterfactual images that seek the minimum set of features to exclude so as to minimize the prediction score or to include so as to maximize the prediction score (Fong & Vedaldi, 2017) , saliency map methods like the one we propose in this paper aim to characterize the influence of each feature on the prediction score. Second, unlike counterfactual images that are optimized toward the aforementioned objective with respect to the decision boundary, decoys are designed to be independent of labels, without changing the decision boundary at all. Finally, unlike counterfactual images which could potentially be out-of-distribution by adding noise (Smilkov et al., 2017 ), rescaling (Sundararajan et al., 2017 ), blurring (Fong & Vedaldi, 2017) , or inpainting the image (Chang et al., 2017) , decoys are plausibly constructed in the sense that their intermediate representations are non-discriminative from the original input data by design.

In addition, we propose a novel decoy-enhanced saliency score, which considers an ensemble of saliency maps across multiple decoy images. We also derive a closed-form formula for the decoyenhanced saliency score generated from a single-layer convolutional neural network. This analysis shows that the proposed saliency score for each pixel can be decomposed into two components: the range of values for a given pixel among the decoys and the number of neurons jointly activated by that pixel and its neighbors. The former compensates for gradient saturation (Sundararajan et al., 2016) in the sense that an important pixel can vary without strongly affecting the prediction, due to the joint effect of nearby pixels. The latter compensates for the way in which saliency maps treat each pixel independently (Singla et al., 2019) in the sense that the importance of a pixel is jointly determined by the importance of pixels in its vicinity. This closed-form result may provide insights to help design better defensive strategies against adversarial attacks.

We apply the proposed method to the ImageNet dataset (Russakovsky et al., 2015) in conjunction with three standard saliency methods. We demonstrate empirically that decoy-enhanced saliency scores perform better than the original saliency scores, both qualitatively and quantitatively, even in the presence of various adversarial perturbations to the image. A common instance of this setting is image classification, in which case the input x corresponds to the pixels of an image. A saliency method aims to find the subset of features in the input x that most strongly lead the neural network to make its prediction. Thus, each pixel is assigned a saliency score, encoded in an explanation map E : R d → R d , in which the pixels with higher scores represent higher "importance" to the final prediction. A variety of saliency methods have been proposed in the literature. Some, such as edge or other generic feature detectors (Adebayo et al., 2018) , are independent of the predictive model. In this work, we focus on three methods that do depend on the predictor. The vanilla gradient method (Simonyan et al., 2013) simply calculates the gradient of the class score with respect to the input x, which is defined as E grad (x) = x F c (x). The SmoothGrad method (Smilkov et al., 2017) seeks to reduce noise in the saliency map by averaging over explanations of noisy copies of an input, defined as

2. PROBLEM SETTING:

E sg (x) = 1 N N i=1 E grad (x+g i ) with noise vectors g i ∼ N (0, σ 2

). The integrated gradients method (Sundararajan et al., 2017) aims to tackle the problem of gradient saturation. The method starts from a baseline input x 0 and sums over the gradient with respect to scaled versions of the input ranging from the baseline to the observed input, defined as

E ig (x) = (x -x 0 ) × 1 0 x F c (x 0 + α(x -x 0 ))dα.

In this setting, we are given three inputs: a pre-trained neural network model F with L layers, an image of interest x, and a saliency method E such that E(x; F ) is a saliency map of the same dimensions as x. As illustrated in Figure 1 , the robust saliency map can be obtained in two steps: 1) constructing decoy images, and 2) computing decoy-enhanced saliency scores. (1) The swap(x, P) operation swaps image patches between x and x (Figure 2 ). Hence, if P = {10}, then x swap(x,P) is a new image which is almost equivalent to x except that the 10 th patch is exchanged from x. A "valid" patch is a local region receptive to the convolutional filter of a given CNN, for example, the 3 × 3 area in VGGNet (Simonyan & Zisserman, 2014) . The swappable condition ensures that the original image x and its decoy x are indistinguishable in terms of the intermediate representation at layer . Note in particular that the construction of decoys relies solely on the first layers of the neural network F 1 , F 2 , • • • , F and is independent of the succeeding layers F +1 , • • • , F L . In other words, x is conditionally independent of the classification task F (x) given the input x; i.e., x |= F (x)|x. See Supplementary Section A6 for the explanation why decoys exist.

3. DEFINITION OF DECOYS:



3.1. GENERATE DECOYS BY OPTIMIZATION:

Given an image of interest x ∈ R d and a patch mask M ∈ {0, 1} d , we want to construct a decoy image x = G (x, M) ∈ R d , with respect to a specified neural network layer , so that x is as different as possible from x. For this purpose, we optimize the following objective function:

maximize x ((x -x) • s) + 1 , s.t. F (x) -F (x) ∞ ≤ , (x -x) • (1 -M) = 0, and x ∈ [0, 1] d .

(2)

where (•) + = max(•, 0), and s = 1 or s = -1 depends on whether we intend to investigate the upward or downward limit of x deviating from x, respectively. The operators • 1 and • ∞ correspond to the L 1 and L ∞ norms, respectively. The constraint (x -x) • (1 -M) = 0 ensures that x and x differ only in the area marked by the patch mask M, where • denotes entry-wise multiplication. The final constraint ensures that the values in x fall into an appropriate range for image pixels, [0, 1] in the normalized image case. In principle, the formulation in Equation 2 is applicable to any convolutional neural network architecture ranging from simple convolutional networks to more sophisticated ones (e.g., , AlexNet (Krizhevsky et al., 2012) , Inception network (Szegedy et al., 2016) and ResNet (He et al., 2016) , etc.).

As illustrated in Figure 1 , we can construct a population of n independently-sampled patch masks

M 1 , M 2 , • • • , M n

, so that each possible image patch is covered by at least one patch mask. Thus we can construct a population of n decoy images x1 , x2 , • • • , xn with respect to different patch masks. Note that the input image x is also a trivially valid decoy, by definition; i.e., it satisfies Equation 1 and the conditional independence requirement (i.e., x |= F (x)|x).

3.2. DECOY-ENHANCED SALIENCY SCORES:

Given the generated population of decoy images x1 , x2 , • • • , xn , the given saliency method E can be applied to each decoy image, following the fundamental rule that the saliency method should be agnostic to information revealing which image is a decoy and which is not. In this way, we obtain a corresponding population of decoy saliency maps

E(x 1 ; F ), E(x 2 ; F ), • • • , E(x n ; F ) .

Now the pixel-wise variation for each feature x j can be characterized by a population of feature values

Xj = x1 j , x2 j , • • • , xn j .

Accordingly, instead of merely quantifying the saliency of each feature x j via a single value E(x; F ) j , we can now characterize the uncertainty of the feature's saliency via the corresponding population of saliency scores Ẽj

= E(x 1 ; F ) j , E(x 2 ; F ) j , • • • , E(x n ; F ) j ) .

We define the decoy-enhanced saliency score Z j for each feature x j as

EQUATION

That is, Z j is determined by the empirical variation of the decoy's saliency scores.

3.3. EXAMPLE: SINGLE-LAYER CNN:

Consider a single-layer convolutional neural network with decoy swappable patch size 1 × 1 and convolutional size

3 × 3. The input of this CNN is x ∈ R d , unrolled from a √ d × √ d grayscale image matrix. Similarly, we have a 3 × 3 convolutional filter unrolled into g ∈ R 9 , where g is indexed as g k for k ∈ K, here K = - √ d -1, - √ d, - √ d + 1, -1, 0, 1, √ d -1, √ d, √ d + 1

, corresponding to the index shift in matrix form from the top-left to bottom-right pixel, respectively. We denote (g * x) ∈ R d as the output of the convolution operation on the input x, where (g * x) i = k∈K g k x i+k . For simplicity, we further assume that there are no pathological cases such as (g * x) i = 0. Such a neural network can be represented as

EQUATION

where relu(•) is the entry-wise ReLU operator (Glorot et al., 2011) , W ∈ R d×C represents the combined weights of the neural network, and b ∈ R C represents the biases. The terms o ∈ R C and p ∈ R C are the logits and the predicted class probabilities, respectively. The entry-wise softmax operator for target class c is defined as

p c = e oc C c =1 e o c , for c ∈ {1, 2, • • • , C}.

In this case, we have the following result: Proposition 1. Z j is bounded by:

EQUATION

where x is the decoy which maximizes E(x; F ) j -E(x; F ) j , ãj = 1 {(g * x) j ≥ 0}, and C 1 > 0 and C 2 > 0 are bounded constants. See Supplementary Section A7 for the full proof.

Proposition 1 indicates that the saliency statistic is determined by two factors: the range of values associated with pixel j among the decoys (|(x -x) j |) and the number of neurons jointly activated by pixel j and its neighbors ( k∈K ãj+k ). The former explains the gradient saturation problem (Sundararajan et al., 2016) in the sense that important features may have more room to fluctuate without influencing the joint effect on the prediction. The latter compensates for way in which saliency maps treat each pixel independently (Singla et al., 2019) in the sense that the importance of a pixel x j is jointly determined by the surrounding pixels (i.e., the 3 × 3 localized region in our setting), potentially capturing meaningful patterns such as edges, texture, etc. In this way, the proposed saliency statistic not only compensates for gradient saturation but takes joint activation patterns into consideration as well. Indeed, the bound provided by Proposition 1 can be considered a motivation for defining the decoy-enhanced saliency score as we have in Equation 3.

3.4. IMPLEMENTATION DETAILS:

We solve Equation 2 by augmenting a constraint as a penalty in the objective function:

EQUATION

)

When the constant c > 0 is properly chosen, Equations 2 and 6 are equivalent in the sense that the optimal solution to Equation 2 equals the optimal solution to Equation 6. Our strategy is to set c to a small value initially and run the optimization. If it fails, then we double c and repeat until success. The sensitivity of choosing c is reported in Supplementary Section A9.

To eliminate the constraint on pixel values (x ∈ [0, 1] d ), we use the change-of-variable trick (Carlini & Wagner, 2017) . Note that other transformations are possible yet unexplored in this paper. Specifically, instead of optimizing over x, we introduce

x satisfying xi = 1 2 (tanh(x i ) + 1), for all i ∈ {1, 2, • • • , d}. Because tanh(x i ) ∈ [-1, 1] implies xi ∈ [0, 1], any solution to x is naturally valid.

To eliminate of the patch mask constraint ((x -x) • (1 -M) = 0), we use projected gradient descent during the optimization stage. Specifically, after performing each step of standard gradient descent, we enforce

x = x • M + x • (1 -M).

Putting these ideas together, we minimize the following objective function:

EQUATION

Because the L ∞ norm is not fully differentiable, we adopt the trick introduced by Carlini & Wagner (2017) . Specifically, in each iteration we solve:

EQUATION

where τ > 0 is initialized with a large value (1 in our experiment). After each iteration, if the second term in Equation 8 is zero, indicating that τ is too large, then we reduce τ by a factor of 0.95 and repeat; otherwise, we terminate the optimization. The run time of optimization is reported in Supplementary Section A10.

4. EXPERIMENTS:

To evaluate the effectiveness of our proposed method, we perform extensive experiments on deep learning models that target image classification tasks. The performance of our method is assessed both qualitatively and quantitatively. The results show that our proposed method identifies intuitively more coherent saliency maps than existing state-of-the-art saliency methods alone. The method also achieves quantitatively better alignment to truly important features and demonstrates stronger robustness to adversarial manipulation.

Our experiments primarily use the VGG16 model (Simonyan & Zisserman, 2014) pretrained on the ImageNet dataset (Russakovsky et al., 2015) . We also demonstrate the applicability of our method to other well-studied CNN architectures such as AlexNet (Krizhevsky et al., 2012) and ResNet (He et al., 2016) . The settings for all experiments are reported in Supplementary Section A13. 

4.1. BENCHMARKS AND VISUALIZATION METHODOLOGIES:

To benchmark the performance of our proposed method, we considered the following baseline saliency methods: the vanilla gradient method (Simonyan et al., 2013) , SmoothGrad (Smilkov et al., 2017) and integrated gradients (Sundararajan et al., 2017) .

To evaluate our decoy generation method, we used the following two methods to replace the proposed decoy generation method: blurring and inpainting. In particular, given an image with a few masked patches (i.e., x • (1 -M)), instead of generating a decoy image (i.e., x) by solving the optimization function in Equation 2, we fill the missing parts by replacing the original missing patches with blurring or using the state-of-the-art inpainting method (Yu et al., 2018) . 1 Using the decoy images generated by these two substitute methods, we then computed the decoy-enhanced saliency scores for the three baseline saliency methods. We compared the results of blurring and inpainting with our method, both qualitatively and quantitatively.

A heatmap is a typical way of displaying a saliency map. Our strategy for projecting a saliency map onto a heatmap is as follows. Saliency methods produce signed values for input features (pixels in our experiment), where the sign of the value indicates the direction of influence for the corresponding feature to the predicted class. We first took the absolute value of the saliency maps, as suggested by Smilkov et al. (2017) . Then we used the maximum value across all color channels, as suggested by Simonyan et al. (2013) , to arrive at a single saliency value for each pixel. To avoid outlier pixels with extremely high saliency values leading to an almost entirely black heatmap, we winsorized those outlier saliency values to a relatively high value (e.g., 95 th percentile), as suggested by Smilkov et al. (2017) , to achieve better visibility. Finally, the values are linearly rescaled to the range [0, 1].

4.2. COMPARISON CRITERIA:

To comprehensively evaluate our proposed method against the aforementioned baseline saliency methods, we focus on the following three goals.

First, we aim to achieve visual coherence of the identified saliency map. Intuitively, we would prefer a saliency method that produces a saliency map that aligns cleanly with the object of interest.

Second, we use a saliency fidelity metric (Dabkowski & Gal, 2017 ) that quantifies the influence of important features identified by a saliency method, defined as

S F (E(x; F ), x, c) = -(log(F c (E(x; F ) • x)) -log(F c (E(x; F ) mean • x)))

, where c indicates the predicted class of input x and the saliency map E(x; F ) is normalized into a [0, 1] range, as described in Section 4.1. The function F c (E(x; F ) • x) performs entry-wise multiplication between E(x; F ) and x, encoding the overlaps between the object of interest and the concentration of information by the saliency map. The rationale here is that, by viewing the saliency score of the feature as its contribution to the predicted class, a good saliency method will be able to weight important features more highly than less important ones, giving rise to better predicted class scores. Accordingly, a lower value for the saliency fidelity metric implies a faithful saliency method. Note that we subtract the influence of mean saliency E(x; F ) mean (i.e., . the mean of E(x; F ) on each channel) to eliminate the influence of bias in E(x; F ). As a result, we can exclude some trivial cases (e.g., E(x; F ) = 1).

Third, we aim for robustness to adversarial manipulations (Ghorbani et al., 2017) . Adversarial attacks aim to apply imperceptible perturbations to an input image that do not affect the predicted class but produce a very different saliency map relative to the map from the unperturbed image. Ghorbani et al. To quantify the robustness of a saliency method E to adversarial attack, we use the sensitivity metric (Alvarez-Melis & Jaakkola, 2018) , defined as

S S (E(•, F ), x, x) = (E(x,F )-E(x,F )) 2 x-x 2

, where x is the perturbed image of x. A small value means that similar inputs do not lead to substantially different saliency maps.

4.3. RESULTS:

We applied all three state-of-the-art saliency methods and their decoys to a dozen randomly sampled images from ImageNet dataset. A side-by-side comparison of the resulting saliency maps (Figure 3 ) suggests that decoys consistently help to reduce noise and produce more visually coherent saliency maps. For example, in Figure 3 , the gradient method without decoys highlights the region corresponding to the dog's head, but in a scattered format. In contrast, the decoy-enhanced gradient method not only highlights the missing body but identifies the dog head with more details such as ears, cheek, and nose. The visual coherence is also quantitatively supported by the saliency fidelity metric S F , which is consistently higher with decoys than without decoys. The sanity check (Adebayo et al., 2018) of decoy-enhanced saliency method is reported in Supplementary Section A8.

Figure 3 also shows the comparison of our decoy generation method with blurring and inpainting. Our decoy generation method consistently outperforms both competing methods, achieving higher fidelity scores on all of the three baseline saliency methods. The reason is as follows. As is discussed in Proposition 1, to obtain a higher decoy score, a set of decoy images should satisfy the following two requirements: first, they produce similar intermediate representation when provided as input to the target neural network; second, they exhibit large decoy variation. In this paper, we design our decoy generation objective function based on these two requirements. In contrast, neither blurring nor inpainting is designed to meet these requirements. Specifically, blurring may violate the intermediate representation constraint and inpainting may not be able to produce enough decoy variation.

It is worth mentioning that combining image blurring or inpainting with our decoy-enhanced saliency scores can still improve upon the baseline saliency maps. The empirical validity of using image blurring is explained in Supplementary Section A11. From the practitioners' perspective, blurry images can be used as more efficient alternatives to combine with the decoy-enhanced saliency score to achieve comparable performance. However, it is worth mentioning that decoy images are still necessary to justify the theoretical soundness of the decoy-enhanced saliency score.

Next, to test the robustness of the methods we subjected each to the three aforementioned adversarial attacks (Figure 4 ). Though not fully resistant to adversarial attacks, we observe that enhancing existing saliency methods with decoys consistently mitigates the impact of adversarial manipulations, leading to visually more coherent saliency maps as well as lower sensitivity scores. We believe the extra benefits in the robustness is brought by our decoy-enhanced saliency score. In a normal situation (when the image doesn't suffer from an adversarial attack), an important pixel is not important in an isolated fashion. Instead, the important pixel tends to contribute a strong joint effect in conjunction with neighboring important pixels, to potentially capture meaningful patterns such as edges, texture, etc. In light of this observation, this particular important pixel will have more room to fluctuate without influencing the joint effect on the prediction. In such case, some elements of Ẽj will be high and others will be low, contributing a large Z j . In the unusual situation when an isolated important pixels is indeed observed (i.e., a pixel is very important for all decoy images and has no room for fluctuation.), we tend to believe that the pixel has been adversarial attacked. In this case, all elements of Ẽj will be high and the proposed decoy-enhanced saliency score Z j will be low, which is what we want.

4.4. SENSITIVITY OF DECOY SETTINGS:

We also conduct experiments to understand the impact of decoy settings on the performance of different saliency methods. Specifically, we focus on the choice of network layer , because the intermediate representations can vary significantly at different layers. Accordingly, we vary the value of for VGG16 and compare the differences of decoy-enhanced saliency scores from the three saliency methods, ranging from the first convolutional layer to the last pooling layer. As shown in Figure 5 and Supplementary Section A14, the decoy-enhanced saliency scores generated from different layers for the same image are of similar qualities. We also compute the S F score for each saliency map. The mean and standard deviation, respectively, for the scores obtained by the gradient, integrated gradient and SmoothGrad methods are as follows: (-0.11, 0.02), (-0.18, 0.02), (-0.21, 0.01). These quantitative results also support the conclusion that our method is not sensitive to layer. This is likely because, as previous research has shown (Chan et al., 2015; Saxe et al., 2011) , the final classification results of a DNN are not highly related to the intermediate representations. As a result, decoys for the same sample with the same label from different layers should yield similar results.

4.5. APPLICABILITY TO OTHER NEURAL ARCHITECTURES:

In addition to the VGG16 model (Simonyan & Zisserman, 2014) , we generate saliency maps for other neural architectures: AlexNet (Krizhevsky et al., 2012) and ResNet (He et al., 2016) . We visualize their saliency maps in Figure 6 and Supplementary Section A14. From Figure 6 , we observe that all the saliency maps accurately highlight the contour of the dog and achieve higher fidelity score than the baseline saliency methods. This indicates that we can apply our method to various neural architectures and expect consistent performance. It should be noted that, in comparison with saliency maps derived from other neural architectures, the maps tied to AlexNet are relatively vague. We hypothesize that this is due to the relative simplicity of the AlexNet architecture.

5. DISCUSSION AND CONCLUSION:

In this work, we have used distribution-preserving decoys as a way to produce more robust saliency scores. First, we formulate decoy generation as an optimization problem, in principle applicable to any network architecture. We demonstrate the superior performance of our method relative to three standard saliency methods, both qualitatively and quantitatively, even in the presence of various adversarial perturbations to the image. Second, by deriving a closed-form formula for the decoyenhanced saliency score, we show that our saliency scores compensate for the frequently violated assumption in saliency methods that important features in general correspond to large gradients.

Although we have shown that decoys can be used to produce more robust saliency scores, there remain some interesting directions for future work. For example, one could potentially reframe interpretability as hypothesis testing and use decoys to deliver a set of salient pixels, subject to false discovery rate control at some pre-specified level (Burns et al., 2019; Lu et al., 2018) . 

A6 EXISTENCE OF DECOYS:

As illustrated in Figure A7 , the original image and the decoy image shares exactly the same intermediate representation with respect to convolutional and max pooling.

A7 PROOF OF PROPOSITION 1:

Consider a single-layer convolutional neural network with decoy swappable patch size 1 × 1 and convolutional size 3 × 3. The input of this CNN is x ∈ R d , unrolled from a √ d × √ d grayscale image matrix. Similarly, we have a 3 × 3 convolutional filter unrolled into g ∈ R 9 , where g is indexed as

g k for k ∈ K, here K = - √ d -1, - √ d, - √ d + 1, -1, 0, 1, √ d -1, √ d, √ d + 1 , corresponding

to the index shift in matrix form from the top-left to bottom-right pixel, respectively. We denote (g * x) ∈ R d as the output of the convolution operation on the input x, where (g * x) i = k∈K g k x i+k .

For simplicity, we further assume that there are no pathologic cases such as (g * x) i = 0. Such a neural network can be represented as

EQUATION

where relu(•) is the entry-wise ReLU operator, W ∈ R d×C represents the combined weights of the neural network, and b ∈ R C represents the biases. The terms o ∈ R C and p ∈ R C are the logits and the predicted class probabilities, respectively. The entry-wise softmax operator for target class c is defined as

p c = e oc C c =1 e o c , for c ∈ {1, 2, • • • , C}.

The gradient of p c with respct to x can be written as follows, using the denominator layout notation of the derivative of a vector:

EQUATION

where

EQUATION

and

EQUATION

Then, we can write ∂pc ∂o c as follows:

EQUATION

where P•c corresponds to the c-th column of P and P = diag(p) -pp T .

We then define ∂m ∂x as B ∈ R d×d , in which

EQUATION

where a j is denoted as a j = 1 {(g * x) j ≥ 0}. Then, we have

EQUATION

Given Equations 11, 13 and 15, Equation 10 can be rewritten as

EQUATION

Further, we define the Hessian as H, where H ij can be written as follows:

EQUATION

After computing the gradient and the Hessian, we now derive the decoy-enhanced saliency score Z j for x j , given a population of saliency scores Ẽj = E(x 1 ; F ) j , E(x 2 ; F ) j , • • • , E(x n ; F ) j ) .

According to Equation 3, Z j can always be decomposed into Z j = Z + j + Z - j where Z + j = max( Ẽj ) -E(x; F ) j and Z - j = E(x; F ) j -min( Ẽj ), respectively. Without loss of generality, we only focus on Z + j , noting that a smilar analysis is applicable to Z - j as well.

Let x ∈ x1 , x2 , • • • , xn denote the decoy which maximizes E(x; F ) j -E(x; F ) j .

The second-order Taylor expansion of the predicted F c (x) for target class c around x is as follows:

EQUATION

)

where ∆ = xx and H x is the Hessian of the neural network model on the decoy x whose entries are (H x) i,j = ∂ 2 F c ∂ xi∂ xj . By definition of the swappable condition in Equation 1, F c (x) = F c (x). Therefore, the following equation holds:

xF c (x) T ∆ ≈ - 1 2 ∆ T H x∆ (20)

Consider the case that the swappable patches are of size 1 × 1 at position i; then Equation 20 can be decomposed into

EQUATION

Then, according to Equation 21, we have

EQUATION

where C 1 = xj p c and C 2 = max k∈K g k W (j+k)• P•c , respectively. Note that both C 1 and C 2 are linear combinations of the gradient, which is bounded by some Lipschitz constant (Szegedy et al., 2013) .

A8 SANITY CHECK FOR DECOY-ENHANCED SALIENCY MAPS:

As suggested by Adebayo et al. (2018) , any valid saliency methods should pass the sanity check in the sense that the saliency method should be dependent on the learned parameters of the predictive model, instead of edge or other generic feature detectors. We performed the model parameter randomization test (Adebayo et al., 2018) by comparing the output of the proposed saliency method on a pretrained VGG16 network with the output of the proposed saliency method on a weight-randomized VGG16 network. If the proposed saliency method indeed depends on the learned parameters of the model, it is expected that the outputs between the two cases differ substantially.

Following the cascading randomization strategy (Adebayo et al., 2018) , the weights of pretrained VGG16 network are randomized from the top to bottom layers in a cascading fashion. This cascading randomization procedure is designed to destroy the learned weights successively. As illustrated in Figure A8 , the cascading randomization destroys the decoy-enhanced saliency maps combined with three existing saliency methods, qualitatively. The conclusion is also supported by quantitative comparison measured by the structural similarity index (SSIM), shown in Figure A9 . 

A9 SENSITIVITY OF HYPERPARAMETER SELECTION:

The optimization formulated in Equation 6 involves one hyperparamer, c, the initial coefficient to weigh the intermediate representation difference between the decoy and the original image. Note that we use the same hyperparameter setting across all the images, rather than for each image separately.

To evaluate how the selection of c affects the performance, we carried out optimizations with respect to a wide range of c ∈ 10 1 , 10 2 , 10 3 , 10 4 , 10 5 . As illustrated in Figure A10 , the choice of initial coefficient c makes a negligible difference of three state-of-the-art saliency methods, both qualitatively and quantitatively.

A10 RUN TIME OF DECOY OPTIMIZATION:

To evaluate the computational cost of optimizing Equation 6, we carried out the run time comparison between optimizing one decoy and calculating three types of state-of-the-art saliency methods. The comparison is repeated 500 times with respect to different patch masks. As illustrated in Figure A11 , on average optimizing one decoy takes 37.7% of the run time of the fastest, vanilla gradient-based saliency method. For other methods, the optimization is even less expensive, in a relative sense.

A11 VALIDITY OF GENERATING DECOY BY BLURRING:

As shown in Figure 3 , combining blurry images with our decoy-enhanced saliency scores achieves empirically good performance even though the blurry images violate the design of decoys which resemble the intermediate representation of the original image. To understand why blurry images are empirically good, we compared the relative difference between the intermediate representation of the original images and the decoy/blurry images. Here, the relative difference is defined as the Running time in seconds Because the decoy images are designed to preserve the intermediate representation of the original images, the relative difference is expected to be small. On the other hand, for the blurry images, the relative difference should be arbitrary since there is no such constraint. As illustrated in Figure A12 , in the first maxpool layer (i.e., a layer near the bottom of the network), the relative difference is large for blurry images (0.307 on average) and very small for decoy images (0.006 on average) as expected. However, in the last fully-connected layer (i.e., a layer near the top of the network), the relative difference is much smaller for blurry images (0.034 on average) and remains small for decoy images (0.002 on average). In conclusion, even though the blurry images violate the constraint of decoys, this violation would be mitigated in deeper layers of the network. 

A12 OBJECT LOCALIZATION:

A standard method to evaluate saliency maps is by object localization (Dabkowski & Gal, 2017; Fong & Vedaldi, 2017) , where the model was trained with the class label only without access to any localization data. We carried out Imagenet ILSVRC'14 localization task (Russakovsky et al., 2015) which contains 50K ImageNet validation images with annotated bounding boxes as ground truth.

For each of the image in the dataset, we first calculated the gradient-based saliency maps with and without using blurry decoys, based on a pretrained VGG16 network. Following the preprocessing steps suggested by Dabkowski & Gal (2017); Fong & Vedaldi (2017) , for each calculated saliency maps, a bounding box for the most dominant object is predicted by thresholding the corresponding saliency map and extracting the tightest bounding box that contains the whole remaining saliency map.

We investigated three different thresholding strategies suggested by Fong & Vedaldi (2017), including value thresholding, energy thresholding, and mean thresholding. Following the evaluation protocol suggested by Dabkowski & Gal (2017); Fong & Vedaldi (2017) , the extracted localization box has to have Intersect over Union (IoU) greater than 0.5 with any of the ground truth bounding boxes in order to consider the localization successful, otherwise it is regarded as failure. As shown in Table A1 , in terms of accuracy, decoy-enhanced saliency maps perform better than vanilla saliency maps without decoys. 

:

We directly used the well-trained inpainting model provide byYu et al. (2018).

Figures and Tables:

Consider a multi-label classification task in which a pre-trained neural network model implements a function F : R d → R C that maps from the given input x ∈ R d to C predicted classes. The score for each class c ∈ {1, • • • , C} is F c (x), and the predicted class is the one with maximum score, i.e., arg max c∈{1,••• ,C} F c (x).

Figure 1: Workflow for creating decoy-enhanced saliency maps.

Figure 2: An illustrative example of the swap operator swapping image patches between original and decoy images.

Figure 3: Visualization of saliency maps comparing three state-of-the-art saliency methods with and without decoy images generated from three techniques (i.e., our decoy generation method, blurring, and inpainting). More examples can be found in Supplementary Section A14.

Figure 4: Visualization of saliency maps under adversarial attacks. More examples can be found in Supplementary Section A14. (2017) propose three different attacks: (1) the top-k attack seeks to decrease the important scores of the top-k important features; (2) the target attack aims to increase the feature importance of a pre-specified region in the input image; (3) the mass-center attack aims to spatially change the center of mass of the original saliency map. In this paper, we specify the bottom-right 4 × 4 region of the original image for the target attack and select k = 5000 in the top-k attack.

Figure 5: Generating decoys with respect to different DNN layers.

Figure 6: Visualization of saliency maps under different CNN architectures.

Figure A7: A toy example to illustrate why decoys exist.

Figure A8: Cascading randomization on VGG16 network. The figure shows the original saliency map (first column) for the terrier. Progression from left to right corresponds to complete randomization of the pretrained VGG16 network weights from the top layer to the bottom layer.

0.20 sF: -0.23 sF: -0.18

Figure A10: Visualization of saliency maps optimized using different hyperparamer c.

Figure A11: Run time to optimize one decoy and calculate three state-of-the-art saliency maps of the decoy. The comparison is conducted in the same CPU to guarantee fairness.

Figure A12: Relative difference between the intermediate representation of the original images and decoy/blurry images.

65 sF: 0.23 sF:5.80 sF: 3.20 sF: 0.46 sF: -0.06 sF: 4.45 sF: 2.64 sF: 4.36 sF: 1.96 sF: 3.20 sF: 2.81 sF: 7.80 sF: 2.22 sF: 4.19 sF: -0.03 sF: 2.30 sF: -1.26 sF: 3.23 sF: 0.004 sF: 0.12 sF: -0.04 sF: 1.20 sF: 0.23 (a) Original and decoy-enhanced saliency maps on AlexNet. 99 sF: 7.55 sF: 10.58 sF: 6.96 sF: 7.64 sF: 7.44 sF: 10.38 sF: 9.83 sF: 10.47 sF: 6.56 sF: 8.33 sF: 7.75 sF: 3.84 sF: 2.28 sF: 1.97 sF: 1.15 sF: 0.26 sF: -0.02 sF: 6.83 sF: 2.66 sF: 0.23 sF: 0.05 sF: 0.01 sF: 0.01 (b) Original and decoy-enhanced saliency maps on ResNet.

Figure A15: The illustration of the performances of the proposed approach of more images on AlexNet and ResNet.

Figure A16: Demonstrations of decoy-enhanced saliency maps generated from each convolutional and pooling layer in VGG16.

Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S Huang. Generative image inpainting with contextual attention. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5505-5514, 2018. Konrad Zołna, Krzysztof J Geras, and Kyunghyun Cho. Classifier-agnostic saliency map extraction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 10087-10088, 2019.

Table content: <table><tr><td>Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow,</td></tr><tr><td>and Rob Fergus. Intriguing properties of neural networks. arXiv:1312.6199, 2013.</td></tr><tr><td>Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking</td></tr><tr><td>the inception architecture for computer vision. In Proceedings of the IEEE conference on Computer</td></tr><tr><td>Vision and Pattern Recognition, pp. 2818-2826, 2016.</td></tr><tr><td>Roozbeh Yousefzadeh and Dianne P O'Leary. Interpreting neural networks using flip points. arXiv</td></tr><tr><td>preprint arXiv:1903.08789, 2019.</td></tr><tr><td>Jiahui Yu,</td></tr></table>

Peer review (iclr2020):
Given a model and an image, the proposed method generates perturbations of the image, such that the model output in intermediate layers of the network does not change. Their method first generates such perturbed images, and then uses those to generate a saliency map in order to interpret the classification.??The idea is overall interesting, but its relationship with many other methods is not adequately examined. Significant portion of recent literature is ignored, especially studies on counterfactuals and decision boundaries in the context of image classification.??For numerical results, they compare their results with raw scores generated by three other methods, but the results are quite thin and disorganized with respect to adversarial robustness and interpretability. Your proposed computational method possibly needs to be changed, too.?? Details are explained below:?? Authors have cited the paper on *Sanity Checks for Saliency Maps*, but have not used it to verify their own results, not with respect to saliency map, and not with respect to computational cost.??Several recent methods on saliency maps have not been considered, for example:? 1. Certifiably robust interpretation in deep learning? 2. Interpreting Neural Networks Using Flip Points 3. Explaining Image Classifiers by Counterfactual Generation ?4. Counterfactual Visual Explanations? It*s not clear how your proposed saliency scores relate to methods that consider counterfactuals and the decision boundaries. For any image, there is a counterfactual image closest to it. One can also compute the closest image on the decision boundary of the model. Such image can reveal which pixels should be changed in order to change or to keep the classification. The relationship between the current method and those methods needs to be established. ?Assume that for an image, you compute the closest image to it on the decision boundary and let’s call the distance between them r (distance measured in l1 or l2 norm). Then, consider a ball centered at that image with radius r. All images inside that ball would have the same label as the original image and you can obtain all of them only by solving one optimization problem for finding closest point on the decision boundary. Would this be a less expensive computation compared to solving your proposed decoy optimization many times? There are many hyper parameters in your optimization problem, and it seems that for each image, hyper-parameters should be tuned separately. However, if you seek the closest image on the decision boundary, your results would be independent of hyper-parameters. As you have mentioned, your optimization problem seems quite hard to solve, but no details are given on how long it takes to solve it for a single image. You have mentioned sometimes you cannot solve it if c is not chosen well. This information needs to be reported. Is it solvable at all with a large mask? How many trials did it take to obtain your saliency maps? Your optimization is nonlinear, non-convex, non-differentiable, …. . How did you deal with non-convexity? Do you arrive at the same solution each time you solve it? These are vital information to about an optimization method. Proposition 1 is quite obvious. Its discussion seems obvious, too, given how you have defined the Z. In your proof, you have considered a single layer network, i.e. a simple linear transformation. It might be better to explain your proof for Proposition 1 as an observation and use it as the motivation on how you have defined Z. ?Overall, you are taking a data-driven approach to interpret the classification of an image. The additional computational cost of your proposed method needs to be compared to other methods that are not data-driven. For example, how does your computational cost compare with the references above? On page 12, one equation is referenced with ??. At the beginning of section 3.4, you are using a standard optimization technique to augment a constraint as a penalty in the objective function. You can explain it as such, instead of saying we solve an alternative formulation. See Numerical Optimization by Nocedal and Wright. The necessity to transform the variable via tanh, instead of performing projection is not explained. Does it make the process faster? Strategy for choosing a good initial value for c (in the penalty term) and how to increase it is not explained well. How many iterations does it take to find the solution? Any classification model is defined by its decision boundaries, so interpreting the classification without considering the decision boundaries seems inconclusive. In summary, it would be best to compare your results with other methods, some of which are mentioned above. It would also be necessary to justify the additional data-driven cost that you are prescribing and to explain why your goals cannot be achieved otherwise with less expensive computation.