Year: 2019

Abstract:
Deep learning interpretation is essential to explain the reasoning behind model predictions. Understanding the robustness of interpretation methods is important especially in sensitive domains such as medical applications since interpretation results are often used in downstream tasks. Although gradient-based saliency maps are popular methods for deep learning interpretation, recent works show that they can be vulnerable to adversarial attacks. In this paper, we address this problem and provide a certifiable defense method for deep learning interpretation. We show that a sparsified version of the popular SmoothGrad method, which computes the average saliency maps over random perturbations of the input, is certifiably robust against adversarial perturbations. We obtain this result by extending recent bounds for certifiably robust smooth classifiers to the interpretation setting. Experiments on ImageNet samples validate our theory.

text: Deep learning interpretation is essential to explain the reasoning behind model predictions. Understanding the robustness of interpretation methods is important especially in sensitive domains such as medical applications since interpretation results are often used in downstream tasks. Although gradient-based saliency maps are popular methods for deep learning interpretation, recent works show that they can be vulnerable to adversarial attacks. In this paper, we address this problem and provide a certifiable defense method for deep learning interpretation. We show that a sparsified version of the popular SmoothGrad method, which computes the average saliency maps over random perturbations of the input, is certifiably robust against adversarial perturbations. We obtain this result by extending recent bounds for certifiably robust smooth classifiers to the interpretation setting. Experiments on ImageNet samples validate our theory.

heading: 1 INTRODUCTION

heading: 1.1 MOTIVATION
text: The growing use of deep learning in a wide range of highly-sensitive applications, such as autonomous driving, medicine, finance, and even the legal system (Teichmann et al., 2018; Quellec et al., 2017; Fischer & Krauss, 2018; Nissan, 2017), raises concerns about human trust in machine learning systems. Interpretations, which explain why certain predictions are made, are critical for establishing this trust between users and the machine learning system. Moreover, the interpretation results themselves are often used for downstream tasks. For example, gradient-based saliency maps have been used in medical applications: Quellec et al. (2017) uses gradient-based interpretation techniques to highlight signs of retinal disease in retinal fundus photographs (see Figure 1-b.) Similarly, BenTaieb et al. (2016) uses a gradient-based saliency map as part of a pipeline to automatically analyse histopathology slides of colon tumours. Techniques like these are also used in medical research to annotate datasets (Lahiani et al., 2019). Outside of the medical field, gradientbased interpretations can be used in general-purpose image segmentation tasks (Hong et al., 2015).
However, Ghorbani et al. (2019) has shown that several gradient-based interpretation methods are sensitive to adversarial examples, obtained by adding a small perturbation to the input image. These adversarial examples maintain the original class label while greatly distorting the saliency map (Figure 1-a: see ‘Gradient’ interpretation method). Although adversarial attacks and defenses on image classification have been studied extensively in recent years (Szegedy et al., 2014; Uesato et al., 2018; Goodfellow et al., 2015; Athalye et al., 2018a;b; Buckman et al., 2018; Kurakin et al., 2017; Papernot & McDaniel, 2016; Carlini & Wagner, 2017; Madry et al., 2018), less attention has been paid to effectively defending deep learning interpretation against adversarial examples (Lee et al., 2019; Etmann et al., 2019). This is partially due to the difficulty of protecting high-dimensional saliency maps compared to defending a class label, as well as to the lack of a ground truth for interpretation. Interestingly, we have observed that the standard adversarial training used for the classification robustness does not lead to robust interpretations (see Section 4). This calls for better understanding the robustness of interpretation methods and developing defenses with performance guarantees.

heading: 1.2 PROPOSED APPROACH AND MAIN CONTRIBUTIONS
text: In the last couple of years, several approaches have been proposed for interpreting neural network outputs (Simonyan et al., 2014; Sundararajan et al., 2017; Alvarez-Melis & Jaakkola, 2018; Adebayo et al., 2018; Huang et al., 2017). Specifically, Simonyan et al. (2014) computes the elementwise absolute value of the gradient of the largest class score with respect to the input. To define some notation, let g(x) be this most basic form of the gradient-based saliency map, for an input image x ∈ Rn. For simplicity, we also assume that elements of g(x) have been linearly normalized to be between 0 and 1. g(x) represents, to a first order linear approximation, the importance of each pixel in determining the class label. Numerous variations of this method have been introduced, which we review in the appendix.
A popular saliency map method which extends the basic gradient method is SmoothGrad (Smilkov et al., 2017), which takes the average gradient over random perturbations of the input. Formally, we define the smoothing function as:
ḡ(x) ∶= E [g(x + )] , (1.1)
where has a normal distribution (i.e. ∼ N (0, σ2I)). We will discuss other smoothing functions in Section 2.3 while the empirical smoothing function which computes the average over finitely many
perturbations of the input will be discussed in Section 2.2. We refer to the basic method described in the above equation as the scaled SmoothGrad 1.
Since a ground truth label for interpretation is not available, we use a similarity metric between the original and perturbed saliency maps as an estimate of the interpretation robustness. Ghorbani et al. (2019) introduced a top-K overlap metric for this purpose: define R(x, x̃,K) as the number of overlapping elements between top K largest elements of saliency maps of x and the perturbed image x̃. Ghorbani et al. (2019) developed an L∞ attack on R(x, x̃,K), which we adapt to the L2 case to test empirical robustness: see the appendix for details. This top-K overlap metric is naturally motivated: absolute magnitude has little meaning in saliency maps, which are nearly always presented as normalized. Moreover, it is common (Sundararajan et al., 2017) to clip the highest values when displaying saliency maps, so that more than a few pixels are clearly visible. This suggests that relative ranks of salience values (and not their absolute values) are important for interpretation.
Note that for an input x, R(x, x̃,K) depends on the specific perturbation x̃. We define R∗(x,K) as the robustness measure with respect to the worst perturbation of x. That is,
R∗(x,K) ∶= min x̃ R(x, x̃,K) (1.2)
∥x̃ − x∥2 ≤ ρ.
For deep learning models, this optimization is non-convex in general. Thus, characterizing the true robustness of interpretation methods is likely intractable for most modern classifier models.
In this paper, we show that a lower bound on the true robustness value of an interpretation method (i.e. a robustness certificate) can be computed efficiently. In other words, for a given input x, we compute a robustness certificateRcert such thatRcert(x,K) ≤ R∗(x,K). To establish the robustness certificate for saliency map methods, we prove the following result for a general function h(.) whose range is between 0 and 1: Theorem 2. Let h(x) be the output of an interpretation method whose range is between 0 and 1 and let h̄ be its smoothed version defined as in equation 1.1. Let h̄i(x) and h̄[i](x) be the i-th element and the i-th largest elements of h̄(x), respectively. Let Φ be the cdf of the normal distribution. If
Φ(Φ−1 (h̄[i](x)) − 2ρ
σ ) ≥ h̄[2K−i](x), (1.3)
then for the smoothed interpretation method, we have Rcert(x,K) ≥ i.
Intuitively, this means that, if there is a sufficiently large gap between the i-th largest element of the smoothed saliency map and its (2K − i)-th largest element, then we can certify that at least i elements in the top K largest elements of the original smoothed saliency map will also be in the top K elements of adversarially perturbed saliency map. We present a more general version of this result with empirical expectations for smoothing in Section 2, as well as another rank-based robustness certificate in Section 3. The proof of this bound relies on an extension of Cohen et al. (2019) which addresses certified robustness in the classification case. Proofs for all theorems are given in the appendix.
Evaluating the robustness certificate for the scaled SmoothGrad method on ImageNet samples produces vacuous bounds (Figure 1-c). This motivated us to develop variations of SmoothGrad with larger robustness certificates. One such variation is Sparsified SmoothGrad which is defined by smoothing a sparsification function that maps the largest elements of g(x) to one and the rest to zero. Sparsified SmoothGrad obtains a considerably larger value of the robustness certificate (Figure 1-c) while producing high-quality saliency maps (Figure 3). We study other variations of Sparsified SmoothGrad in Section 2.
A considerably different certification result for robust interpretation is provided by Lee et al. (2019). That work provides a certified L2 radius in which a first-order gradient saliency map is exactly identical to the saliency map for the unperturbed image. The method depends on the network structure being locally linear (ReLU-based): the inner radius of the locally linear region is directly calculated.
1The original definition of SmoothGrad does not normalize and take the absolute values of gradient elements before averaging. We start with the definition of equation 1.1 because it can more easily be compared to our certifiably robust interpretation scheme discussed in Section 2.
By contrast, our method makes no demands on the structure of the classifier, and could be applied to saliency maps generated by methods other than computing simple gradients: any bounded saliency function can be used as h(x) in our Theorem 1. Additionally, our certification method is computationally inexpensive enough to allow certificates to be computed on ImageNet-scale samples.

heading: 2 SMOOTHING FOR CERTIFIABLY ROBUST INTERPRETATION

heading: 2.1 NOTATION
text: We introduce the following notations to indicate Gaussian smoothing: for a function h, we define population and empirical smoothed functions, respectively, as:
h̄(x) =E ∼N (0,σ2I)[h(x + )],
h̃(x) = 1
q
q
∑ i=1 h(x + i), i ∼ N (0, σ
2I). (2.1)
In other words, h̄(x) represents the expected value of h(x) when smoothed under normal perturbations of with some standard deviation σ while h̃(x) represents an empirical estimate of h̄(x) using q samples. We call σ2 the smoothing variance and q the number of smoothing perturbations.
We use vi to denote the ith element of the vector v. Similarly hi(x) denotes the ith element of the output h(x). We also define, for any h(x), rank(h(x), i) as the ordinal rank of hi(x) in h(x) (in the descending order): rank(h(x), i) = j denotes that hi(x) is the jth largest element in h(x). We use x[i] to denote the ith largest element in x. If i is not an integer, the ceiling of i is used.

heading: 2.2 ROBUSTNESS CERTIFICATE
text: In order to derive a robustness certificate for saliency maps, we present an extension of the classification robustness result of Cohen et al. (2019) to real-valued functions, rather than discrete classification functions. In our case, we will apply this to the saliency map vector g. First, we define a floor function to simplify notation.
Definition 2.1. The Floor function is a function L ∶ [0,1]→ [0,1], such that
L(z) = Φ(Φ−1 (z) − 2ρ
σ )
where ρ denotes the L2 norm of the adversarial distortion and σ2 denotes the smoothing variance. Φ is the cdf function for the standard normal distribution and Φ−1 is its inverse.
Below (Theorem 1) is a general result which can be used to derive robustness certificates for interpretation methods. In particular, it is used to derive our robustness certificate, Theorem 2, later in the section:
Theorem 1. Let h ∶ Rn → [0,1]n be a real-valued function. Let L(.) be the floor function defined as in equation 2.1 with parameters σ2 and ρ. Using σ2 ∈ R as the smoothing variance for h, ∀ i, j ∈ [n], x, x̃ ∈ Rn where ∥x − x̃∥ ≤ ρ:
L (h̄i(x)) ≥ h̄j(x)⇒ h̄i(x̃) ≥ h̄j(x̃).
Note that this theorem is valid for any general function. However, we will use it for our case where h̄(x) is a smoothed saliency map. Theorem 1 states that, for a given saliency map vector h̄(x), if L(h̄i(x)) ≥ h̄j(x), then if x is perturbed inside an L2 norm ball of radius at most ρ, h̄i(x̃) ≥ h̄j(x̃). This result extends Theorem 1 in Cohen et al. (2019) in two ways: first, it provides a guarantee about the difference in the values of two quantities, which in general might not be related, while the original result compared probabilities of two mutually exclusive events. Second, we are considering a real-valued function h, rather than a classification output which can only take discrete values. This bound can be compared directly to Lecuyer et al. (2019)’s result which similarly concerns unrelated elements in a vector. Just as in the classification case (as noted by Cohen et al. (2019)), Theorem 1 gives a significantly tighter bound than that of Lecuyer et al. (2019) (see details in the appendix).
We can extend Theorem 1 to use empirical estimates of smoothed functions. Following Lecuyer et al. (2019), we derive upper and lower bounds of the expected value function h̄(x) in terms of h̃(x), by applying Hoeffding’s Lemma. To present our result for the empirical case, we first define an empirical floor function to derive a similar lower bound when the population mean is estimated using a finite number of samples:
Definition 2.2. The Empirical Floor function is a function L̂ ∶ [0,1] → [0,1], such that for given values of ρ, σ, p, q, n, where ρ denotes the maximum L2 distortion, σ2 denotes the smoothing variance, p denotes the probability bound, q denotes the number of perturbations, and n is the size of input of the function:
L̂(z) = Φ(Φ−1 (z − c) − 2ρ
σ ) − c, where c ∶=
√ ln(2n(1 − p)−1)
2q .
Corollary 1. Let h ∶ Rn → [0,1]n be a function such that for given values of q, σ, ∀ i, j ∈ [n], x, x̃ ∈ Rn, ∥x − x̃∥2 ≤ ρ, with probability at least p,
L̂(h̃i(x)) ≥ h̃j(x)⇒ h̄i(x̃) ≥ h̄j(x̃). (2.2)
Note that unlike the population case, this certificate bound is probabilistic. Also note that this bound compares the empirical expectation of the saliency map at an observed point to the true population expectation at all nearby points. This convention is in line with recent works providing probabilistic certificates for smoothed classifiers (Cohen et al., 2019; Salman et al., 2019).
Theorem 1 allows us to derive certificates for the top-K overlap (denoted by R). In particular:
Theorem 2. ∀ x, x̃ ∈ Rn, ∥x − x̃∥2 ≤ ρ, σ ∈ R, q ∈ N, define Rcert(x,K) as the largest i ≤ K such that L̂(h̃[i](x)) ≥ h̃[2K−i](x). Then, with probability at least p,
Rcert(x, K) ≤ R(x, x̃, K). (2.3)
where R(x, x̃, K) denotes the top-K overlap between h̃(x) and h̄(x̃).
Intuitively, if there is a sufficiently large gap between the ith and (2K − i)th largest elements of an empirical smoothed saliency map, then we can certify that the overlap between top K elements of the observed saliency map and any possible perturbed population smoothed saliency map is at least i with probability at least p. If the observed saliency map is possibly adversarially corrupted up to a radius of ρ, it is thus still guaranteed to be similar to the “ground truth” population saliency map.
Note that it requires some modifications of SmoothGrad (Smilkov et al., 2017) for our bounds to be directly applicable. Smilkov et al. (2017) in particular defines two methods, which we will call SmoothGrad and Quadratic SmoothGrad. SmoothGrad takes the mean over samples of the signed gradient values, with absolute value typically taken after smoothing for visualization. Quadratic SmoothGrad takes the mean of the elementwise squares of gradient values. Both methods, therefore, require modification for our bounds to be applied: we define scaled SmoothGrad g̃(x), such that g(x) is the elementwise absolute value of the gradient, linearly scaled so that the largest element is one. We can similarly define a scaled Quadratic SmoothGrad. We can then apply Theorem 2 directly to scaled SmoothGrad (or scaled Quadratic SmoothGrad), simply by scaling the components of g(x) (or g(x)⊙g(x)) to lie in the interval [0,1]. However, we observe that this gives vacuous bounds for both of them when using the suggested hyperparameters from Smilkov et al. (2017). One issue is that the suggested value for q (number of perturbations) is 50 which is too small to give useful bounds in Corollary 1. For a standard size image from the ImageNet dataset (n = 224 × 224 × 3 = 150,528), with p = 0.95, this gives c = 0.395 (using Definition 2.2). Note that even for a small ρ:
L̂(z) = Φ(Φ−1 (z − c) − 2ρ
σ ) − c ≈ Φ (Φ−1 (z − c)) − c = z − 2c
Thus the gap between z and L̂(z) is at least 0.79. We can see from Corollary 1 that a gap of 0.79 (on a scale of 1) is far too large to be of any practical use. We instead take q = 213, which gives a more manageable estimation error of c = 0.031. However, we found that even with this adjustment, the bounds computed using Theorem 2 are not satisfactory for either scaled SmoothGrad and or scaled Quadratic SmoothGrad (see details in the appendix). This prompted the development of Sparsified SmoothGrad described in Section 2.3.

heading: 2.3 SPARSIFIED SMOOTHGRAD AND ITS RELAXATION
text: Scaled SmoothGrad and Quadratic SmoothGrad give vacuous robustness certificates using our proposed method, as demonstrated in Figure 1. We therefore develop a new method, Sparsified SmoothGrad, which has (1) non-vacuous robustness certificates at ImageNet scale (Figure 2a), (2) similar high-quality visual output to SmoothGrad (Figure 3), and (3) theoretical guarantees that aid in setting its hyper-parameters (Section 3).
The Sparsified SmoothGrad is defined as g̃[τ], where g[τ] is defined as follows:
g [τ] i (x) = { 0, if gi(x) < g[τn](x) 1, if gi(x) ≥ g[τn](x)
(2.4)
In other words, τ controls the degree of sparsification: a fraction τ of elements (the largest τn elements of g(x)) are assigned to 1, and the rest are set to 0.
For some applications, it may be desirable to have at least some differentiable elements in the computed saliency map. For this purpose, we also propose Relaxed Sparsified SmoothGrad:
g [γ,τ] i (x) = ⎧⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎩ 0, if gi(x) < g[τn](x) 1, if gi(x) ≥ g[γn](x) gi(x) g[γn](x) , otherwise
(2.5)
Here, τ controls the degree of sparsification and γ controls the degree of clipping: a fraction γ of elements are clipped to 1. Elements neither clipped nor sparsified are linearly scaled between 0 and 1. Note that Relaxed Sparsified SmoothGrad is a generalization of Sparsified SmoothGrad. With no clipping (γ = 0), we again achieve nearly-vacuous results. However, with only a small degree of clipping (γ = 0.01), we achieve results very similar (although slightly worse) than sparsifed SmoothGrad; see Figure 2b. We use Relaxed Sparsified SmoothGrad in this paper to test the performance of first-order adversarial attacks against Sparsified SmoothGrad-like techniques.

heading: 3 RANK CERTIFICATE FOR THE PROPOSED SPARSIFIED SMOOTHGRAD
text: In this section, we show that if the median rank of a saliency map element over smoothing perturbations is sufficiently small (i.e. near the top rank), then for an adversarially perturbed input, that
element will certifiably remain near the top rank of the proposed Sparsified SmoothGrad method with high probability. This provides a theoretical justification for the certifiable robustness of the proposed Sparsified SmoothGrad method.
To present this result, we first define the certified rank of an element in the saliency map as follows: Definition 3.1 (Certified Rank). For a given input x and a given saliency map method (denoted by h ∶ Rn → Rn), let the maximum adversarial distortion be ρ, i.e. ∥x̃−x∥2 ≤ ρ. Then, for a probability p, the certified rank for an element at index i (denoted by rankcert(x, i)) is defined as the minimum k such that the following condition holds:
L̂(h̃i(x)) ≥ h̃[k](x).
If the i-th element of the saliency map has a certified rank of k, using Corollary 1, we will have:
h̄i(x̃) ≥ h̄[k](x̃) with probability at least p.
That is, the ith element of the population smoothed saliency map is guaranteed to be as large as the smallest n − k + 1 elements of the smoothed saliency map of any adversarially perturbed input.
Note that certified rank depends on the particular perturbations used to generate the smoothed saliency map h̃(x). In the following result, we show that if the median rank of a gradient element at index i, over a set of randomly generated perturbations, is less than a specified threshold value, then the certified rank of that element in the Sparsified SmoothGrad saliency map generated using those perturbations can be upper bounded. Theorem 3. Let U be the set of q random perturbations for a given input x using the smoothing variance σ2. Using the Sparsified SmoothGrad method, with probability p, we have
Median ∈U
[rank(g(x + ), i)] ≤ ⌈τn⌉ ⇒ rankcert(x, i) ≤ ⌈τn⌉
L̂( 1 2 ) , (3.1)
where τ is the sparsification parameter of the Sparsified SmoothGrad method.
For instance, if ρ ≪ σ and for sufficiently large number of smoothing perturbations (i.e. q → ∞), we have L̂(1/2) → 1/2. If we set τ = K/(2n), then for indices whose median ranks are less than or equal to K/2, their certified ranks will be less than or equal to K. That is, even after adversarially perturbing the input, they will certifiably remain among the top K elements of the Sparsified SmoothGrad saliency map. We present a more general form of this result in the appendix.

heading: 4 EMPIRICAL RESULTS
text: To test the empirical robustness of Sparsified SmoothGrad, we used an L2 attack on R(x, K) adapted from the L∞ attack defined by Ghorbani et al. (2019); see the appendix for details of our proposed attack. We test Relaxed Sparsified SmoothGrad (γ = .01; τ = .05, .1, .2), rather than Sparsified SmoothGrad because our attack is gradient-based and Sparsified SmoothGrad has no defined gradients. We tested on ResNet-18 with CIFAR-10 with the attacker using a separately-trained, fully differentiable version of ResNet-18, with SoftPlus activations in place of ReLU. We present our results in Figure 4. We observe that our method is significantly more robust than the SmoothGrad method while its robustness is on par with the Quadratic SmoothGrad method with the same number of smoothing perturbations. We note that our robustness certificate appears to be loose for the large perturbation magnitudes used in these experiments; see the appendix for a direct comparison.
The attack introduced by Ghorbani et al. (2019) (and its L2 extension that we introduced) does not change the the original classification of the image, so protecting against adversarial attacks on classification is an insufficient defence. To demonstrate this, we compare a model trained adversarially for classification with a baseline model. Specifically, we adversarially train a simple CNN classification model on MNIST (see appendix for model architecture) using a state-of-the-art L2 adversarial training procedure provided by Rony et al. (2019). We used the code available for this adversarial training procedure directly. While, as predicted by Tsipras et al. (2018), the resulting model produced high-quality saliency maps, the model was not significantly more robust to adversarial perturbation tailored for the interpretation than a naively trained classifier (Figure 5, top-K overlap of 58.5% with adversarial training for classification vs. 57.3% on the baseline). This highlights that adversarial training for classification does not suffice to provide adversarial robustness for interpretation. In appendix D, we propose an adversarial training approach which successfully defends interpretations against adversarial attack (top-K overlap greater than 80% under the same attack) while also producing high-quality saliency maps. However, unlike the proposed Sparsified SmoothGrad, this approach is not certifiably robust.

heading: 5 CONCLUSION
text: In this work, we studied the robustness of deep learning interpretation against adversarial attacks. We introduced a sparsified variant of the popular SmoothGrad method which computes the average saliency maps over random perturbations of the input. By establishing an easy-to-compute robustness certificate for the interpretation problem, we showed that the proposed Sparsified SmoothGrad is certifiably robust to adversarial attacks while producing high-quality saliency maps. We provided experiments on ImageNet samples validating our theory.

heading: A PROOFS
text: Theorem 1. Let h ∶ Rn → [0,1]n be a bounded, real-valued function, σ2 ∈ R be the smoothing variance for h, then ∀ i, j ∈ [n], x, x̃ ∈ Rn where x̃ − x = δ such that ∥δ∥2 ≤ ρ:
Φ(Φ−1 (h̄i(x)) − 2ρ
σ ) ≥ h̄j(x)⇒ h̄i(x̃) ≥ h̄j(x̃)
where Φ denotes the cdf function for the standard normal distribution and Φ−1 is its inverse.
We will prove this by first proving a more general lemma2: Lemma 1. For any bounded function h ∶ R→ [0,1] and smoothing variance σ2 ∈ R, Φ−1(h̄(x)) is Lipschitz-continuous with respect to x, with Lipschitz constant σ−1.
Proof. By the definition of Lipschitz continuity, we must show that ∀δ ∈ Rn,
Φ−1(h̄(x)) − ∥δ∥2 σ ≤ Φ−1(h̄(x + δ)) ≤ Φ−1(h̄(x)) + ∥δ∥2 σ
(A.1)
We first define a new, randomized function H ∶ R→ {0,1},
H(x) ∼ Bern (h(x))
Then ∀ x ∈ Rn:
E [H(x + )] = E [EH [H(x + )]] = E [h(x + )] = h̄(x) (A.2)
Now, we apply the following Lemma (Lemma 4 from Cohen et al. (2019)):
Lemma (Lemma 4 from (Cohen et al., 2019)). Let X ∼ N (x, σ2I) and Y ∼ N (x + δ, σ2I). Let f ∶ Rn → {0,1} be any deterministic or random function, Then:
1. If S = {z ∈ Rn ∶ δT z ≤ β} for some β and Pr(f(X) = 1) ≥ Pr(X ∈ S), then Pr(f(Y ) = 1) ≥ Pr(Y ∈ S)
2. If S = {z ∈ Rn ∶ δT z ≥ β} for some β and Pr(f(X) = 1) ≤ Pr(X ∈ S), then Pr(f(Y ) = 1) ≤ Pr(Y ∈ S)
Using the same technique as used in the proof of Theorem 1 in Cohen et al. (2019), we fix x, δ and define,
β = σ∥δ∥2Φ −1 (E [H(x + )])
Also define the half-spaces:
S− = {z ∶ δ T z ≤ β + δTx} = {z ∶ δT (z − x) ≤ β}
S+ = {z ∶ δ T z ≥ −β + δTx} = {z ∶ δT (z − x) ≥ −β}
Applying algebra from the proof of Theorem 1 in Cohen et al. (2019), we have,
Pr(X ∈ S−) = Φ( β
σ∥δ∥2 ) = E [H(x + )] (A.3)
Pr(X ∈ S+) = 1 −Φ( −β
σ∥δ∥2 ) = 1 − (1 −Φ(
β
σ∥δ∥2 )) = E [H(x + )] (A.4)
Pr(Y ∈ S−) = Φ( β
σ∥δ∥2 − ∥δ∥2 σ ) = Φ(Φ−1(E [H(x + )]) − ∥δ∥2 σ ) (A.5)
Pr(Y ∈ S+) = Φ( −(−β)
σ∥δ∥2 + ∥δ∥2 σ ) = Φ(Φ−1(E [H(x + )]) + ∥δ∥2 σ ) (A.6)
2We note that Salman et al. (2019) has recently and independently published a different proof of this lemma.
Using equation A.3
Pr(H(X) = 1) = E [H(X)] = E [H(x + )] ≥ Pr(X ∈ S−)
Applying Statement 1 of Cohen’s lemma, using f =H and S = S−:
E [H(x + δ + )] = Pr(H(x + δ + ) = 1) = Pr(H(Y ) = 1) ≥ Pr(Y ∈ S−) (A.7)
Using equation A.4,
Pr(H(X) = 1) = E [H(X)] = E [H(x + )] ≤ Pr(X ∈ S+)
Applying Statement 2 of Cohen’s lemma, using f =H and S = S+:
E [H(x + δ + )] = Pr(H(x + δ + ) = 1) = Pr(H(Y ) = 1) ≤ Pr(Y ∈ S+) (A.8)
Using equation A.7 and equation A.8:
Pr(Y ∈ S−) ≤ E [H(x + δ + )] ≤ Pr(Y ∈ S+)
Then by equation A.5 and equation A.6:
Φ(Φ−1(E [H(x + )]) − ∥δ∥2 σ ) ≤ E [H(x + δ + )] ≤ Φ(Φ−1(E [H(x + )]) + ∥δ∥2 σ )
Noting that Φ−1 is a monotonically increasing function, we have:
Φ−1(E [H(x + )]) − ∥δ∥2 σ ≤ Φ−1(E [H(x + δ + )]) ≤ Φ−1(E [H(x + )]) + ∥δ∥2 σ
Using equation A.2 yields equation A.1, which completes the proof.
We now proceed with the proof of Theorem 1.
Proof. Applying Lemma 1 to hi and hj gives (recalling that x̃ = δ + x ):
Φ−1(h̄i(x)) − ρ σ ≤ Φ−1(h̄i(x)) − ∥δ∥2 σ ≤ Φ−1(h̄i(x̃)) (A.9)
Φ−1(h̄j(x̃)) ≤ Φ −1 (h̄j(x)) + ∥δ∥2 σ ≤ Φ−1(h̄j(x)) + ρ σ (A.10)
Then we have:
Φ(Φ−1 (h̄i(x)) − 2ρ
σ ) ≥ h̄j(x)
Ô⇒ Φ−1 (h̄i(x)) − ρ σ ≥ Φ−1 (h̄j(x)) + ρ σ (by monotonicity of Φ−1)
Ô⇒ Φ−1(h̄i(x̃)) ≥ Φ −1 (h̄j(x)) +
ρ σ (by equation A.9 )
Ô⇒ Φ−1(h̄i(x̃)) ≥ Φ −1 (h̄j(x̃)) (by equation A.10 )
Ô⇒ h̄i(x̃) ≥ h̄j(x̃) (by monotonicity of Φ)
which proves the implication.
Corollary 1. Let h ∶ Rn → [0,1]n be a function such that for given values of q, σ:
h̃(x) = 1
q
q
∑ i=1
h(x + i), i ∼ N(0, σ 2I) (A.11)
∀ i, j ∈ [n], x, x̃ ∈ Rn, ∥x − x̃∥2 ≤ ρ, with probability at least p,
L̂(h̃i(x)) ≥ h̃j(x)⇒ h̄i(x̃)) ≥ h̄j(x̃)
Proof. By Hoeffding’s Inequality, for any c > 0, ∀ i ∶
Pr [∣h̃i(x) − h̄i(x)∣ ≥ c] ≤ 2e −2qc2 (A.12)
Then:
Pr [⋃ i
(∣h̃i(x) − h̄i(x)∣ ≥ c)] ≤ 2ne −2qc2 (A.13)
Since we are free to choose c, we define c such that 1 − p = 2ne−2qc 2 , then:
c =
√ ln(2n(1 − p)−1)
2q (A.14)
Pr [⋃ i
(∣h̃i(x) − h̄i(x)∣ ≥ c)] ≤ 2ne −2qc2 = 1 − p
Ô⇒ 1 −Pr [⋃ i (∣h̃i(x) − h̄i(x)∣ ≥ c)] ≥ p
Ô⇒ Pr [⋂ i (∣h̃i(x) − h̄i(x)∣ < c)] ≥ p
Then with probability at least p:
h̃i(x) − c < h̄i(x) h̃j(x) + c > h̄j(x) (A.15)
So:
Φ(Φ−1 (h̃i(x) − c)) − 2ρ
σ ) ≥ h̃j(x) + c Ô⇒ Φ(Φ
−1 (h̄i(x)) − 2ρ
σ ) ≥ h̄j(x) (A.16)
The result directly follows from Theorem 1.
Theorem 2. ∀ x, x̃ ∈ Rn, ∥x − x̃∥2 ≤ ρ, σ ∈ R, q ∈ N, define Rcert(x,K) as the largest i ≤ K such that L̂(h̃[i](x)) ≥ h̃[2K−i](x). Then, with probability at least p,
Rcert(x, K) ≤ R(x, x̃, K). (A.17)
where R(x, x̃, K) denotes the top-K overlap between h̃(x) and h̄(x̃).
Proof. Note that the proof of Corollary 1 guarantees that with probability at least p, all estimates h̃(x) are within the approximation bound c of h̄(x). So we can assume that Corollary 1 will apply simultaneously to all pairs of indices i, j, with probability p. We proceed to prove by contradiction.
Let i = Rcert(x,K)
Ô⇒ L̂(h̃[i](x)) ≥ h̃[2K−i](x),
Suppose there exists x̃ such that: R(x, x̃, K) < i,
Since L̂ is a monotonically increasing function,
L̂(h̃[i](x)) ≥ h̃[2K−i](x)
Ô⇒ L̂(h̃[i′](x)) ≥ h̃[j′](x), ∀ i ′ ≤ i, j′ ≥ 2K − i,
and therefore by Corollary 1:
∀m,n rank(h̃(x),m) ≤ i, rank(h̃(x), n) ≥ 2K − i Ô⇒ h̄m(x̃)) ≥ h̄n(x̃) (A.18)
Let X be the set of indices in the top K elements in h̃(x), and X̃ be the set of indices in the top K elements in h̄(x̃). By assumption, X and X̃ share fewer than i elements, so there will be at least K − i+ 1 elements in
X̃ which are not in X . All of these elements have rank at least K + 1 in h̃(x). Thus by pigeonhole principle, there is some index l ∈ X̃ −X , such that rank(h̃(x), l) ≥ K +K − i + 1 = 2K − i + 1 ≥ 2K − i. Thus by Equation equation A.18,
∀m, where rank(h̃(x),m) ≤ i, h̄m(x̃) ≥ h̄l(x̃) (A.19)
Hence, there are i such elements where rank(h̃(x),m) ≤ i: these elements are clearly in X . Because l ∈ X̃ , Equation equation A.19 implies that these elements are all also in X̃ . Thus X and X̃ share at least i elements,which contradicts the premise. (In this proof we have implicitly assumed that the top K elements of a vector can contain more than K elements, if ties occur, but that rank is assigned arbitrarily in cases of ties. In practice, ties in smoothed scores will be very unlikely.)
A.1 GENERAL FORM AND PROOF OF THEOREM 3
We note that Theorem 3 can be used to derive a more general bound for any saliency map method that for an input x, first maps g(x) to an elementwise function that only depends on the rank of the current element in g(x) and not on the individual value of the element. We denote the composition of the gradient function and this elementwise function as g[rank]. The only properties that the function must satisfy is that it must be monotonically decreasing and non-negative. Thus, we have the following statement: Theorem 3. Let T be the threshold value and let U be the set of q random perturbations for a given input x using the smoothing variance σ2 and let p be the probability bound. If i is an element index such that:
Median ∈U [rank(g(x + ), i)] ≤ T (A.20)
Then:
rankcert(x, i) ≤ ∑ n j=1 g [rank] [j] (x)
L̂( g [rank] [T ] (x) 2 )
(A.21)
Furthermore:
n
∑ j=1
g [rank] [j] (x), L̂(
g [rank] [T ] (x)
2 ) are both independent of x. Thus RHS is a constant. (A.22)
Proof. Let the elementwise function be f ∶ N → R+, i.e f takes the rank of the element as the input and outputs a real number. Furthermore, we assume that f is a non-negative monotonically decreasing function. Thus g[rank]i (x) = f(rank(g(x), i)). We use f(i) to denote the constant value that f maps elements of rank i to. Note that g[rank][i] (x) is the i
th largest element of g[rank](x). Since f is a monotonically decreasing function:
g [rank] [i] (x) = f(i) ∀ i ∈ [n]
Thus g[rank][i] (x) is independent of x, we simply use g [rank] [i] (⋅) to denote f(i), i.e:
g [rank] [i] (⋅) = f(i) ∀ i ∈ [n]
Because Median ∈U [rank(g(x + ), i)] ≤ T , for at least half of sampling instances in U , rank(g(x + ), i) ≤ T . So in these instances g[rank]i (x + ) ≥ f(T ), The remaining half or fewer elements are mapped to other nonnegative values. Thus the sample mean:
g̃ [rank] i (x) =
1 q ∑ ∈U g [rank] i (x + ) ≥ g [rank] [T ] (⋅)/2
Using Corollary 1, ḡ[rank]i (x) is certifiably as large as all elements with indices j such that:
L̂(g [rank] [T ] (⋅)/2) ≥ g̃ [rank] j (x)
. Now we will find an upper bound on the number of elements with indices j such that:
g̃ [rank] j (x) > L̂(g [rank] [T ] (⋅)/2)
Because all the ranks from 1 to n will occur in every sample in U, we have:
∀ ∈ U, n
∑ k=1
g [rank] k (x + ) =
n
∑ k=1
g [rank] [k] (⋅)
Ô⇒ n
∑ k=1
g̃ [rank] k (x) =
n
∑ k=1
1 q ∑ ∈U g [rank] i (x + ) =
n
∑ k=1
g [rank] [k] (⋅)
Thus strictly fewer than ∑nk=1 g [rank] [k] (⋅)/L̂(g [rank] [T ] (⋅)/2) elements will have mean greater than
L̂(g [rank] [T ] (⋅)/2).
Hence, ḡi(x) is certifiably at least as large as n − (∑nk=1 g [rank] [k] (⋅)/L̂(g [rank] [T ] (⋅)/2)) + 1 elements,
which by the definition of rankcert(x, i) yields the result. Theorem 3 in the main text follows trivially, because in the Sparsified SmoothGrad case, ∑ n k=1 g [τ] [k](⋅) = T , and g [τ] [T ](⋅) = 1. Note that this represents the tightest possible realization of this general theorem.

heading: B RELATED WORKS
text: Sundararajan et al. (2017) defines a baseline, which represents an input absent of information and determines feature importance by accumulating gradient information along the path from the baseline to the original input. Alvarez-Melis & Jaakkola (2018) builds interpretable neural networks by learning basis concepts that satisfy an interpretability criteria. Adebayo et al. (2018) proposes methods to assess the quality of saliency maps. Although these methods can produce visually pleasing results, they can be sensitive to noise and adversarial perturbations.
Szegedy et al. (2014) introduced adversarial attacks for classification in deep learning. That work dealt with L2 attacks, and uses L-BFGS optimization to minimize the norm of the perturbation. Carlini & Wagner (2017) provide an L2 attack for classification which is often considered state of the art.
One strategy to make classifiers more robust to adversarial attacks is randomized smoothing. Lecuyer et al. (2019) use randomized smoothing to develop certifiably robust classifiers in both the L1 and L2 norms. They show that if Gaussian smoothing is applied to class scores, a gap between the highest smoothed class score and the next highest smoothed score implies that the highest smoothed class score will still be highest under all perturbations of some magnitude. This guarantees that the smoothed classifier will be robust under adversarial perturbation.
Li et al. (2018) and Cohen et al. (2019) consider a related formulation. Cohen gives a bound that is tight in the case of linear classifiers and gives significantly larger certified radii. In their formulation, the unsmoothed classifier c is treated as a black box outputting just a discrete class label. The smoothed classifier outputs the class observed with greatest frequency over noisy samples. Salman et al. (2019) considers adversarial attacks against smoothed classifiers.
In the last couple of years, several approaches have been proposed to for interpreting neural network outputs. Simonyan et al. (2014) computes the gradient of the class score with respect to the input. Smilkov et al. (2017) computes the average gradient-based importance values generated from several noisy versions of the input. Sundararajan et al. (2017) defines a baseline, which represents an
input absent of information and determines feature importance by accumulating gradient information along the path from the baseline to the original input. Alvarez-Melis & Jaakkola (2018) builds interpretable neural networks by learning basis concepts that satisfy an interpretability criteria. Adebayo et al. (2018) proposes methods to assess the quality of saliency maps. Although these methods can produce visually pleasing results, they can be sensitive to noise and adversarial perturbations (Ghorbani et al., 2019; Kindermans et al., 2019).
As mentioned in Section 1, several approaches have been introduced for interpreting image classification by neural networks (Simonyan et al., 2014; Smilkov et al., 2017; Sundararajan et al., 2017; Shrikumar et al., 2017).

heading: C L2 ATTACK ON SALIENCY MAPS
text: We developed an L2 norm attack on Rcert, based on Ghorbani et al. (2019)’s L∞ attack. Our algorithm is presented as Algorithm 1. We deviate from Ghorbani et al. (2019)’s attack in the following ways.:
• We use gradient descent, rather than gradient sign descent: this is a direct adaptation to the L2 norm.
• We initialize learning rate as ρ∥∇D(x0)∥2 , and then decrease learning rate with increasing iteration count, proportionately (for the most part) to the reciprocal of the iteration count. These are both standard practices for gradient descent.
• We use random initialization and random restarts, also standard optimization practices.
• If a gradient descent step would cross a decision boundary, we use backtracking line search to reduce the learning rate until the step stays on the correct-class side. This allows the optimization to get arbitrarily close to decision boundaries without crossing them.
We measured the effectiveness of our attack (Q = 100, P = 20, T = 5) against a slight modification of Ghorbani et al. (2019)’s attack, in which the image was projected (if necessary) onto the L2 ball at every iteration, and also clipped to fit within image box constraints (this was not mentioned in Ghorbani et al. (2019)’s original algorithm). For this attack, we set the (L∞) learning rate parameter at ρ/500, and ran for up to 100 iterations. We also tested against random perturbations. For random perturbations, up to 100 points were tested until a point in the correct class was identified. We tested these attacks on both “vanilla gradient” and SmoothGrad saliency maps. See Figure 6. Experimental conditions are as described in Section F for experiments on CIFAR-10. In this figure, for each attack magnitude, we discard any image on which any optimization method failed.
Algorithm 1 L2 attack on top-k overlap Input: k, image x, saliency map function h, iteration number P , random sampling iteration number
Q, L2 perturbation norm constraint ρ, classifier c, restarts number T Output: Adversarial example x̃
1: Define D(z) = −∑i, rank(h(x),i)≤k hi(z) 2: for t = 1, ..., T do 3: loop 4: δ ← Uniformly random vector on L2 = ρ sphere. 5: x0 ← x + δ 6: Clip x0 such that it falls within image box constraints. 7: if c(x0) = c(x) then break inner loop 8: if Q total iterations have passed over all t cycles of random sampling then 9: break outer loop
10: end if 11: end loop 12: α ← ρ∥∇D(x0)∥2 13: for p = 1, ..., P do 14: loop 15: xp ← xp−1 + α∇D(xp−1) 16: If necessary, project xp such that ∥xp − x∥2 ≤ ρ 17: Clip xp such that it falls within image box constraints. 18: if c(xp) = c(x) then 19: break inner loop 20: else 21: α ← α 2 22: end if 23: end loop 24: α ← pα p+1 25: end for 26: x̃t = arg maxz∈{x1,...,xP }D(z) 27: end for 28: if random sampling failed at every iteration then fail 29: x̃ = arg maxz∈{x̃1,...,x̃T }D(z)

heading: D ADVERSARIAL TRAINING FOR ROBUST SALIENCY MAPS
text: Adversarial training has been used extensively for making neural networks robust against adversarial attacks on classification (Madry et al., 2018). The key idea is to generate adversarial examples for a classification model, and then re-train the model on these adversarial examples.
In this section, we present an adversarial training approach for fortifying deep learning interpretations so that the saliency maps generated by the model (during test time) are robust against adversarial examples. We focus on “vanilla gradient” saliency maps, although the technique presented here can potentially be applied to any saliency map method which is differentiable w.r.t. the input. We solve the following optimization problem for the network weights (denoted by θ):
min θ E(x,y)∼D[ `cls(x, y) ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
Classification loss
+λ ∥g(x) − g(x̃)∥ 2 2
´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ Robustness loss
], (D.1)
where x̃ is an adversarial perturbation for the saliency map generated from x. To generate x̃, we developed an L2 attack on saliency maps by extending the L∞ attack of Ghorbani et al. (2019) (see the details in Section C). `cls(x, y) is the standard cross entropy loss, and λ is the regularization parameter to encourage consistency between saliency maps of the original and adversarially perturbed images.
We observe that the proposed adversarial training significantly improves the robustness of saliency maps. Aggregate empirical results are presented in Figure 7, and examples of saliency maps are presented in Figure 8. It is notable that the quality of the saliency maps is greatly improved for
.
unperturbed inputs, by adversarial training. We note that this observation is related to the observation made in Tsipras et al. (2018) showing that adversarial training for classification improves the quality of the gradient-based saliency maps. We observe that even for very large value of λ, only a slight reduction in classification accuracy occurs due to the added regularization term.

heading: E ADVERSARIAL TRAINING ARCHITECTURE DETAILS
text: We use the Adam optimizer and generate new adversarial examples after each batch of training according to the updated model. We use a simple convolutional neural network, with SoftPlus activations to ensure differentiability of the saliency map, on the MNIST data set (Figure 9). Adversarial perturbations of norm up to ρ = 10 standard deviations of pixel intensity were used. The adversarial attack used was the L2 attack described in Algorithm 1, with P = 15,Q = 100, T = 3. Training was performed for 30 epochs using 48,000 images from the MNIST training set, testing was on the entire MNIST test set. Instances where Algorithm 1 failed were not counted in the averages of
saliency map robustness, and were rare. (Highest frequency was for λ = 0, at 0.11%). We used the implementation of Adam Optimizer provided with PyTorch (Paszke et al., 2017), with default training parameters. These are (Table 2):

heading: F DESCRIPTION OF EXPERIMENTS IN MAIN TEXT
text: For ImageNet experiments (Figures 1-b and 2-a,b), we use ResNet-50, using the model pre-trained on ImageNet that is provided by torchvision.models, and images were pre-processed according to the recommended procedure for that model. In all of these figures, data are from the ILSV RC2012 validation set, sample size is 64, and the main data lines represent the 60th percentile in the sample of the calculated robustness certificate. Error bars represent the 48th and 72th percentile values, corresponding to a 95% confidence interval for the population quantile. For CIFAR-10 experiments, we train a ResNet-18 model on the CIFAR-10 training set (with pixel intensities normalized to σ = 1, µ = 0 in each channel) using Stochastic Gradient Descent with Momentum as implemented by PyTorch (Paszke et al., 2017). The following training parameters were used:
Twenty percent of the training data was used for validation, and early stopping was used to maximize accuracy relative to this validation set. For adversarial attacks on CIFAR samples, we train a version of ResNet-18 with SoftMax activations instead of ReLU. The adversarial attack used was the L2 attack described in Algorithm 1, with P = 20,Q = 100, T = 5. When adversarially attacking images smoothed with q = 8192 perturbations with this model, fewer perturbations are are used (512). In these experiments, the sample size is 144. Error bars represent the 95% confidence interval of the population mean. In Figure 4, instances where the adversarial attack failed were not counted at each point. For MNIST experiments in Section 4, the model architecture, attack method, and baseline
training method are the same as used for the adversarial training experiments, detailed in appendix E above. The adversarially training for classification uses the implementation provided in Rony et al. (2019), with default arguments.

heading: G ADDITIONAL EXAMPLE IMAGES
text: See Figures 10 and 11.

heading: H BOUNDS FOR SCALED SMOOTHGRAD, QUADRATIC SMOOTHGRAD, AND
text: RELAXED SPARSIFIED SMOOTHGRAD WITH γ = 0
In the text, we mention that we achieve vacuous bounds for Scaled SmoothGrad, Quadratic SmoothGrad, and Relaxed Sparsified SmoothGrad with γ = 0. Here are these bounds (Figure 12):

heading: I ADDITIONAL IMAGES FROM ADVERSARIAL TRAINING EXPERIMENT (APPENDIX D)
text: See Figure 13.

heading: J COMPARISON OF BOUNDS TO EMPIRICAL PERFORMANCE FOR RELAXED SPARSIFIED SMOOTHGRAD.
text: We present a detailed view of Figure 4, for small magnitude perturbations, with the robustness certificate shown. (Figure 14)

heading: K COMPARISON TO BOUNDS IN LECUYER ET AL. (2019)
text: Lecuyer et al. (2019) approaches the classification case for certified robustness by smoothing, by using bounds directly comparably to Theorem 1, but applying them to the class score elements, rather than the saliency map elements: bounds are certified by demonstrating that the top class score is certifiably larger than all other class scores. However, as noted by Cohen et al. (2019), these bounds are rather loose, and Cohen et al. (2019) gives significantly tighter bounds specifically for classification case, which we extend to apply to interpretation. In Figure 15, we compare our bounds for interpretation to a straightforward application of Lecuyer et al. (2019)’s results for class scores to saliency scores. Note that Lecuyer et al. (2019)’s results have a free parameter, for which we numerically maximize the bound.

Review summaries:
This paper introduces an extension of Cohen et al. (2019)’s result that allows one to derive robustness certificates for interpretation methods, as well as a bound on the top-K overlap of saliency methods. These results motivate the introduction of Sparsified SmoothGrad and a relaxation of this method that has differentiable elements. These introduced approaches adapt previous methods so the derived bounds are applicable. The proposed methods are shown to perform as well as Quadratic SmoothGrad (Smilkov et al. 2017) in CIFAR-10 experiments.