Stability Guarantees for Feature Attributions with Multiplicative Smoothing
Authors: Anton Xue
Rajeev Alur
Eric Wong
Venue: NeurIPS 2023 poster (2023)
Keywords: Feature Attribution
Smoothing
Explainable
Interpretable
Provable Guarantees

Abstract: Explanation methods for machine learning models tend not to provide any formal guarantees and may not reflect the underlying decision-making process.
In this work, we analyze stability as a property for reliable feature attribution methods. 
We prove that relaxed variants of stability are guaranteed if the model is sufficiently Lipschitz with respect to the masking of features. 
We develop a smoothing method called Multiplicative Smoothing (MuS) to achieve such a model.
We show that MuS overcomes the theoretical limitations of standard smoothing techniques and can be integrated with any classifier and feature attribution method.
We evaluate MuS on vision and language models with various feature attribution methods, such as LIME and SHAP, and demonstrate that MuS endows feature attributions with non-trivial stability guarantees.

Stability Guarantees for Feature Attributions with Multiplicative Smoothing
Anton Xue
Rajeev Alur Eric Wong
Department of Computer and Information Science
University of Pennsylvania Philadelphia. PA 19104
{antonxue aluu, exwoourreewow@@eeeeo exwong)@seas www.u.eennn.. edu
Abstract
Explanation methods for machine learning models tend not to provide any formal guarantees and may not reflect the underlying decision-making process. In this work, analyze stability as a property for reliable feature attribution methods. We prove that relaxed variants of stability are guaranteed if the model is sufficiently Lipschitz with respect to the masking of features. We develop a smoothing method called Multiplicative Smoothing (MuS) to achieve such a model. We show that MuS overcomes the theoretical limitations of standard smoothing techniques and can be integrated with any classifier and feature attribution method. We evaluate MuS on vision and language models with various feature attribution methods, such as LIME and SHAP, and demonstrate that MuS endows feature attributions with non-trivial stability guarantees.
Introduction
Modern machine learning models are incredibly powerful challenging prediction tasks but notori- ously black-box in their decision-making, One can therefore achieve impressive performance without fully understanding why. In settings like medical diagnosis [1 2] and legal analysis [ 4. where accurate and well-justified decisions are important, such power without proof is insufficient. In order to fully wield the power of such models while ensuring reliability and trust, a user needs accurate and insightful explanations of model behavior.
One popular family of explanation methods is feature attributions S 6 8. Given a model and input, feature attribution method generates score for each input feature that denotes its importance to the overall prediction. For instance, consider Figure [ in which the Vision Transformer [9] classifier predicts the full image (left) "Goldfish". We then use a feature attribution method like SHAP 7 to score each feature and select the top-25%, for which the masked image (middle) is consistently predicted prediction confidence so much that now yields "Axolou!.. This suggests that the explanation is brittle 101, small changes easily cause it induce some other class. In this paper, study how to overcome such behavior by analyzing the stability an explanation: we consider an explanation to be stable if, once the explanatory features are included, the addition of more features does not change the prediction.
"Goldfish". However, adding a single patch of features (right) alters the
Stability implies that the selected features are enough explain the prediction 13 14 and that this selection maintains strong explanatory power even in the presence of additional information [0 [5] Similar properties studied in literature and identified as useful for interpretability [6]. and we emphasize that our main focus on analyzing and achieving provable guarantees. Stability guarantees, in particular, are useful they allow one to predict how model behavior varies with the explanation. Given a stable explanation, one can include more features, e.g., adding context, while
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Goldfish (98.72%) Cockroach (0.0218%)
Goldfish (95.86%) Axolotl (1.62%)
Axoloti (53. (4%)
Goldfish (30.24%)
Pneumonia (25.50%)
Pneumonia (29.56%)
Pneumonia (50.05%)
Figure I: (Top) Classification by Vision Transformer 19. (Bottom) Pneumonia detection from an X-ray image by DenseNet-Reste Resll24 from TorchXRay Vision [II]. Both are 224 x 224 pixel images whose attributions are derived from SHAP [7] with top-25% selection. A single 28 x 28 pixel patch of difference between the two attributions (marked green) significantly affects prediction confidence.
maintaining confidence in the consistency of the underlying explanatory power. Crucially, we observe that such guarantees only make sense when jointly considering the model and explanation method: the explanation method necessarily depends on the model to yield explanation, and stability is then evaluated with respect to the model.
Thus far, existing works on feature attributions with formal guarantees face computational tractability and explanatory utility challenges. While some methods take an axiomatic approach [8] 17 others use metrics that appear reasonable but may not reliably reflect useful model behavior, common and known limitation [8]] Such explanations have been criticized as plausible guess at best, and
completely misleading [1 at worst.
In this paper, we study how to construct explainable models with provable stability guarantees. We jointly consider the classification model and explanation method and present formalization for studying such properties that we call explainable models. We focus on binary feature attributions [20] wherein each feature is either marked as explanatory (1) or not explanatory (0). We present method to solve this problem, inspired by techniques from adversarial robustness, particularly randomized smoothing [21 [22]. Our method can take any off-the-shel classifier and feature attribution method efficiently yield an explainable model that satisfies provable stability guarantees. In summary, our contributions are follows:
We formalize stability as key property for binary feature attributions and study this in the framework of explainable models. We prove that relaxed variants of stability are guaranteed if the model sufficiently Lipschitz with respect to the masking of features.
To achieve the sufficient Lipschitz condition, we develop smoothing method called Mul- tiplicative Smoothing (MuS). We show that MuS achieves strong smoothness conditions, overcomes key theoretical and practical limitations of standard smoothing techniques, and can be integrated with any classifier and feature attribution method.
We evaluate MuS on vision and language models along with different feature attribution methods. We demonstrate that MuS- MuS-smoothed explainable models achieve strong stability guarantees at small cost to accuracy.

---

2 Overview
We observe that formal guarantees for explanations must take into account both the model and explanation method, and for this, we present in Section 2. pairing that we call explainable models. This formulation allows us to describe the desired stability properties in Section 2.2 We show in Section 2.3 that a classifier with sufficient Lipschitz smoothness with respect to feature masking allows us to yield provable guarantees of stability. Finally, in Section [.4], we show how to adapt existing feature attribution methods into our explainable model framework.
2.1 Explainable Models
We first present explainable models as a formalism for rigorously studying explanations. Let X' E" be the space of inputs, a classifier f X' + [0, 1|"h maps inputs x E X' to m class probabilities that sum to 1, where the class of f(x) E [0, 11 is taken be the largest coordinate. Similarly, an explanation method 9 : X + {0, 1]"h maps input E X' to an explanation po E {0. 1)" that indicates which features are considered explanatory for the prediction [(x). In particular, we may pick and adapt from among selection of existing feature attribution methods like LIME (6) SHAP [7) and many others 8 23 24 25), wherein yp may be thought of as a top-k feature selector. Note that the selection of input features necessarily depends on the explanation method executing or analyzing the model, and so makes sense to jointly study the model and explanation method: given a classifier f and explanation method yo, we call the pairing (f, sp) an explainable model. Given some r E X. the explainable model (f. up) maps x to both a prediction and explanation. We show this in Figure 2. where (x) [0, 1|"" x {0, } pairs the class probabilities and the feature attribution.
H.
(f,0) "Goldfish",
where:
Figure 2: An explainable model (f, up) outputs both a classification and a feature attribution. The feature attribution is a binary-valued mask (white 1, black 0) that can be applied over the original input. Here f is Vision Transformer and yo SHAP with top-25% feature selection.
For input E X, we will evaluate the quality of the binary feature attribution (p(x)) through its masking on x. That is, we will study the behavior of f on the masked input x @ up(x) E X, where @ is the semment-wise vector product. To do this, define notion of prediction equivalence: for two I, x, E X. we write fx) = f(x') ) to mean that f(z) and fx') yield the same class. This allows us to formalize the intuition that explanation (xx) should recover the prediction of under f.
Definition 2.1. The explainable model (J, up) is consistent at if f(x) & f(x ② s(x))
Evaluating ff on x O p(z) this way lets us apply the model as-is and therefore avoids the challenge of constructing surrogate model that is accurate to the original (26). Moreover, this approach is reasonable, especially in domains like vision - where one intuitively expects that a masked image retaining only the important features should induce the intended prediction. Indeed, architectures like Vision Transformer
[9] can maintain high accuracy with only a fraction of the image present (27].
Particularly, we would like for (f)+)) to generate explanations that are stable and concise (i.e. sparse). The former is our central guarantee and ensured through smoothing. The latter implies that (fx) has few ones entries, and is desirable property since good explanation should not contain too much redundant information. However, sparsity is a more difficult property to enforce, as this contingent the model having high accuracy with respect heavily masked inputs. For sparsity, we present a simple heuristic in Section 2.4 and evaluate its effectiveness in Section
2.2 Stability Properties Explainable Models
Given an explainable model (f. () and some E X, stability means that the prediction does not change even if one adds more explanatory features to (x)). For instance, the model-explanation pair in Figure not stable, the inclusion of a single feature group (patch) changes the prediction. To formalize this notion of stability, we first introduce partial ordering: for a, a' E (0, 1)", we write a' iff a, a for all i I,...,n. That is, a' iff includes all the features selected by a'.
3

---

Definition 2.2. The explainable model (f.4p) is stable at a if f(x aa) = f(z @ p(x)) for all z ((x).
Note that the constant explanation ()x)) 1, the vector of ones, makes (f.v) sp) trivially stable at every I E X. though this is not a concise explanation. Additionally, stability at z implies consistency at æ.
Unfortunately, stability is a difficult property to enforce in general, as it requires that of satisfy monotone-like behavior with respect to feature inclusion which is especially challenging for complex models like neural networks. Checking stability without additional assumptions on f is also hard: if k = (1)(()) is the number of ones in g(z)), then there are 2 possible a (f(x to check. This large space of possible ł pzz) motivates us to examine instead relaxations of stability, We introduce lower and upper relaxations of stability below.
Definition 2.3. The explainable model (f, incrementally stable at x with radius r if f(x f( O v(x)) for all a ž pp()) where ||a (0x)]]( S
Incremental stability the lower relaxation since it considers the case where the mask a has only a few features more than pzz). For instance, if one can probably add up to r features to a masked a @ p(z) without altering the prediction, then (ʃs up) would be incrementally stable x with radius We next introduce the upper relaxation that we call decremental stability.
The explainable model (f, (p) is decrementally stable at z with radius if f(( f( ((x)) for all a Zzz p(z) where || - al11 S
Definition 2.4.
Decremental stability is subtractive form of stability, in contrast to the additive nature of incremental stability. Particularly, decremental stability considers the case where a has much more features than ((z). If one can provably remove up to non-explanatory features from the full z without altering the prediction, then (f, .p) is decrementally stable at x with radius r. Note also that decremental stability necessarily entails consistency of (f, v). but for simplicity of definitions, we do not enforce this for incremental stability. Furthermore, observe that for a sufficiently large radius of r = [n - /1)/==(x)))/2))))) incremental and decremental stability together imply stability.
Remark 2.5. Similar notions to the above have been proposed in the literature, and we refer to Io for an extensive survey. particular, for (T6], consistency akin to preservation, and stability similar to continuity, except
concerned with adding features. In this regard, incremental stability is most similar to incremental addition and decremental stability to incremental deletion.
2.3 Lipschitz Smoothness Entails Stability Guarantees
If f.f: X' + J0, 1| is Lipschitz with respect to the masking of features, then we can guarantee relaxed stability properties for the explainable model (f, :p). particular, we require for all x X that f(z O a. is Lipschitz with respect to the mask E f0, 1)". This then allows us to establish our main result (Theorem 3.3). which we preview below in Remark
Remark 2.6 (Sketch of main result). Consider an explainable model (f. ()) where for all x E X the function g(2, a) f(x @ a)) is X-Lipschitz in a E 13" with respect to the Ee norm. Then at any I, the radius of incremental stability Tine and radius of decremental stability rdec are respectively:
Tine 92(2, (px)) - gB( ((())
-9(xx11) - (1(
Tdec
2
2
where ga 9n is called the confidence gap, with 9n the top-two class probabilities: kt argmax (x, o)).
94(2, a) = Sk (z, gD(a, a) = max (1
(1)
15k5m
i
Observe that Lipschitz smoothness is. in fact, stronger assumption than necessary, as besides a > pxx), it also imposes guarantees on a 3 spx)). Nevertheless, Lipschitz smoothness is one of the few classes of properties that can be guaranteed and analyzed at scale on arbitrary models 22 28
2.4 Adapting Existing Feature Attribution Methods
Most existing feature attribution methods assign a real-valued score to feature importance, rather than a binary value. We therefore need to convert this to a binary-valued method for use with

---

stable explainable model. Let àh X' + R" be such continuous-valued method like LIME [6 or SHAP 77.. and fix some desired incremental stability radius iine and decremental stability radius Tdec- Given some E X' simple construction for binary so(x) E {0, 1)"
tM is described next.
Remark 2.7 (Iterative construction of ((xx)), Consider any x E X and let p be an index ordering on (b)x) from high-to-low (i.e. most probable class first), Initialize o -,, and for each i E p: assign 04 6 then check whether (J s:: : x + 0)) is now consistent, incrementally stable with radius Tine- and decrementally stable with radius Idec- If terminate with xp(z) a, and continue otherwise.
Note that the above method of constructing pzz) does not impose sparsity guarantees in the way that we may guarantee stability through Lipschitz smoothness. Instead, the ordering from a continuous- valued ()(r) serves as a greedy heuristic for constructing ((z)). We show in Section that some feature attributions (e.g., SHAP (7) tend to yield sparser selections on average compared to others (e.g., Vanilla Gradient Saliency
3 Multiplicative Smoothing for Lipschitz Constants
In this section, we present our main technical contribution of Multiplicative Smoothing (MuS). The goal is to transform an arbitrary base classifier h X - [0, 1] into a smoothed classifier f + [0, 11 that is Lipschitz with respect to the masking of features. This then allows one to couple f with an explanation method oo order form an explainable model (f, up) with provable stability guarantees.
We give an overview of our MuS in Section 3.1 where illustrate that a principal motivation for its development is because standard smoothing techniques may violate a property that we call masking equivalence. We present the Lipschitz constant of the smoothed classifier f in Section 3.2 and show how this is used to certify stability. Finally, we give an efficient computation of MuS in Section 3.3 allowing us to exactly evaluate f at low sample complexity.
Stage 1
Stage 2
Stage 3
Sample masks
Apply maskings
0.6
h
Masks D
0.2
Goldfiih
Easer
Lipstck
Figure 3: Evaluating f()) is done in three stages. (Stage 1) Generate N samples of binary masks g(1), ...., s(N) E {0,1)% where each coordinate is Bernoulli with parameter À (here X 1/4), N. (Stage 2) Apply each mask on the input to yield O g0) for i = 1, ,., (Stage 3) Average over h(x @ s ()) to compute f(x). and note that the predicted class is given by weighted average.
3.1 Technical Overview of MuS
Our key insight is that randomly dropping (i.e., zeroing) features will attain the desired smoothness. In particular, we uniformly drop features with probability 1 A by sampling binary masks s E {0. 1)" from some distribution D where each coordinate is distributed Pr[s, = 1] = A. Then define as:
f(x)
= E hxx ②+) 8);
such that 8; ~ B(A) for 1....,n
B
where ((A) is the Beronulli distribution with parameter À []. We give overview of eval- Importantly, our main results on smoothness (Theorem 3.2h and stability (Theorem 3.3 hold provided each coordinate of D is marginally Bernoulli with parameter X, and so we avoid fixing particular choice for now. However, will be easy to intuit the exposition with D 8d (A), the coordinate-wise i.i.d. Bernoulli distribution with parameter X.
uating f(x in Figure 3
We can equivalently parametrize f using the mapping g(x, a) = f(x O a), where it follows that:
g(2, a) = E anD
h(x 3 a),
ā = a O s.
(3)
5

---

Note that one could have alternatively first defined g and then f due to the identity g 1) fx)). We require that the relationship between f and follows an identity that we call masking equivalence:
g(x o a. 1) = f(z o a) g(x, a),
for all X and {0.
(4)
This follows by the definition of 9. and the relevance to stability is this: if masking equivalence holds, then we rewrite stability properties involving S' in terms of g second parameter as follows:
f(x a)) = g(z, ax) = g( se(x)) f(x @ (xx)),
for all or = ( (c.f. Definition 2.2
where incremental and decremental stability may be analogously defined. This translation is useful, will prove that 9 is X-Lipschitz in its second parameter (Theorem 3.2. which then allows to establish the desired stability properties (Theorem 3.3
Since many choices are valid, we have not given an explicit construction for D. Rather, so long as each coordinate of s ~ 'D oheys 8; ~ (()) then the Lipsehitz properties for g follow. The implication here is that although simple distributions like (A) suffice for D, they may not be sample efficient. We show in Section 3.3 how to exploit a structured statistical dependence in order to reduce the sample complexity of computing MuS.
Importantly, we are motivated to develop MuS because standard smoothing techniques, namely additive smoothing [21] may fail to satisfy masking equivalence. Additive smoothing is by far the most popular smoothing technique and differs from our scheme (3) in how noise is applied, where let Dadd and D Dmmitt be any two distributions on Ih:
a + 8 ~ Dadd, a @aOs Dimlt;
additive noise
g( = E h(r anD
ā =
multiplicative noise
Particularly, additive smoothing has counterexamples for masking equivalence. Proposition 3.1. There exists h X + [0, 1] and distribution D. where for g x (x,
E a)), aND
a
we have (x, a)) + g (x @ a, 1) for some x E X and a E 10
Proof. Observe that it suffices to have h x. a such that h(x @ (a 8)) (( for a non-empty set of 8 E IR". Let 'D be a distribution on these 8, then:
g (xx a) = E Mr @ (a +)) > E (1)+s) a~D
anD
Intuitively, this occurs because additive smoothing primarily applies noise by perturbing feature values, rather than completely masking them. As such, there might be "information leakage" when non-explanatory bits of are changed into non-zero values. This then causes each sample of @+) within g(z, ar) to observe more features than would have been able to otherwise.
3.2 Certifying Stability Properties with Lipschitz Classifiers
Our core technical result is in showing that I as defined in ( is Lipschitz to the masking of features. We present MuS terms of g, where is parametric with respect to the distribution D: so long as D satisfies a coordinate-wise Bernoulli condition, then it is usable with MuS.
Theorem 3.2 (MuS). Let 'D be any distribution on (0, 1)"1 where each coordinates of 8 ~ D is distributed as s; B()). Consider any h X + [0, 1] and define g : X x {0, 10" + [0, 1] as
g(2, a)
E h(x 3 a), a
anD
Then the function g(x, : (0, 13a - [0. 1] is X-Lipschitz in the E norm for all x E X.
The strength of this result is in its weak assumptions. First, the theorem applies to any model h and input x E X. further suffices that each coordinate distributed as 8; ~ B()), and we emphasize that statistical independence between different s; S, is not assumed. This allows to construct

---

D with structured dependence in Section 3.3 such that we may exactly and efficiently evaluate g(x, a) at a sample complexity N < 2" low sample complexity is important for making MuS practically usable, as otherwise, one must settle for the expected value subject to probabilistic guarantees. For instance, simpler distributions like 8" (A) do satisfy the requirements of Theorem 3.2 but costs 2n samples because of coordinate-wis independence. Whatever choice of D, one can guarantee stability so long as is Lipschitz in its second argument.
Theorem 3.3 (Stability). Consider any h : X - [0, 1jth with coordinates h1,.... .......... hm- Fix X E [0, and let 91..... 9m be the respectively smoothed coordinates as in Theorem [.2] using which we analogously define g : x {0, 1]" [0, 1|mh. Also define f f(x = g(x, 1). Then for any explanation method &p and input E X, the explainable model (S, sp) is incrementally stable with radius Tine and decrementally stable with radius rdec:
(a(xx)((a) gB(z, p(x))
gA 1) 9B (I, 1)
Vine
Tdec
2x
2A
where 9A- 9R is the confidence gap as in
Note that is only in the case where the radius 2 1 that non-trivial stability guarantees exist. Because each 9s has range in [0. 1], this means that a Lipschitz constant of À S 1/2 is necessary to attain at least one radius of stability. We present in Appendix A.2 some extensions to MuS that allow one to achieve higher coverage of features.
3.3 Exploiting Structured Dependency
We now present Eye (A), a distribution on {0, 1}" that allows for efficient and exact evaluation of a MuS-smeothed classifier. Our construction is an adaption of [28] from uniform to Bernoulli noise, where the primary insight is that one can parametrize n-dimensional noise using a single dimension via structured coordinate- wise dependence. In particular, integer quantization parameter > there will only exist distinct choices of s ~ (A). All the while, we still enforce that any such is coordinate-wise Bernoulli with s; B()). Thus, for sufficiently small quantization parameter (i.e., < 2"), we may tractably enumerate through all possible choices of and thereby evaluate a MuS-smoothe model with only q samples.
seed vector v, where with
Proposition 3.4. Fix integer q > 1 and consider any vector E {0. 1/q...... ........................... 1)/1) and sealar E (1/9. .t/....../////
.// q). Define 8 ~ L (A) to be a random vector in {0, 1)" with coordinates given by
8 = I[t, S A], Then there are distinct values of and each coordinate is distributed as 8; ~ (
14 = 12 + 8base
mod 1,
Stase ~
./44)) 1/(22)
Proof. First, observe that each of the distinct values of 8base defines a unique value of s since we have assumed and À to be fixed. Next, observe that each t; has q unique values uniformly distributed as t; (((1q..... ..t....////) q Pr[t, < ^] X, which implies that s B()).
1/(2q). Because À E (l/g.....q/ q/4) we therefore have
The seed vector is the source of our structured coordinate- wise dependence, and the dieedimnnsionll source of randomness $base is used to generate the n-dimensional Such (A)(A) then satisfies the conditions for use in MuS (Theorem 3.2). and this noise allows for an exact evaluation of the smoothed classifier in samples. We have found q 64 to be sufficient in practice and that values as low as 16 also yield good performance. We remark that one drawback is that one may get an unlucky seed v, but we have not yet observed this in experiments.
Empirical Evaluations
We evaluate the quality of MuS different classification models and explanation methods as they relate to stability guarantees. To that end, we perform the following experiments.
(E1) How good are the stability guarantees? A natural measure of quality for stability guarantees over a dataset exists: what radii are achieved, and at what frequency. We investigate how different combinations of models, explanation methods, and X affect this measure.
7

---

(E2) What is the cost of smoothing? To increase the radius of a provable stability guarantee, we must decrease the Lipschitz constant X. However, À decreases, more features are dropped during the smoothing process. This experiment investigates this stability-accuracy trade-off.
(E3) Which explanation method is best? We evaluate which existing feature attribution methods are amenable to strong stability guarantees. We examine LIME [6], SHAP 77. Vanilla Gradient Saliency (VGrad) [5], and Integrated Gradients (IGrad) [ with focus on the size of the explanation.
(Experimental Setup) We use on two vision models (Vision Transformer [ and ResNer50 (29]) and one language model (RoBERTa (O)). We use ImageNetI [31]
vision dataset and Tweet- Eval (32] sentiment analysis as our language dataset. We use feature grouping from Appendix [A.2.]
on I K to reduce the 3 x 224 x 224 dimensional input into 64 superpixel patches. We report stability radii r in terms of the fraction of features, i.e., r/n. n. quantized noise in Section 3.3 with g 64 unless specified otherwise. We refer Appendix B for training details and the comprehensive experiments.
In all our experiments, we use the
Certified Consistent and Stable
Certified Consistent Dec Stable
(0.840)
(0.840)
Prop Hold Rate
A=4/8 (0.801)
A=4/8 (0.801)
A-2/8 (0.672)
A-2/8 (0.6 (0.672)
X-1/8 (0.515)
2-1/8 (0.515)
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
Empirical Consistent and Inc Stable
Empirical Consistent and Dec Stable
0.8
X=8/8 (0.844)
0.8
A=8/8 (0.844)
Prop Hold Rate
A=4/8 (0.816)
4= (0.816)
0.6
(0.708)
(0.708)
A-188 (0.496)
2-1/8 (0.496)
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Fraction of Features
Fraction of Features
Figure 4: Rate of consistency and incremental (decremental) stability up to radius vs. fraction of
feature coverage r/n. Left: certified Neert 2000; Right: empirical Nemp 250 with g = 16.
4.1 (E1) Quality of Stability Guarantees
We study how much radius of consistent and incremental (resp. decremental) stability is achieved, and how often. We take an explainable model (f, (p) where f is Vision Transformer and is SHAP with t0p-25% feature selection. We plot the rate at which a property holds (e.g., consistent and incrementally stable with radius r) a function of radius (expressed as a fraction of features r/n).
We show our results in Figure 4 where on the left we have the certified guarantees for Necrt = 2000 samples from ImageNet1 K; on the right we have the empirical radii for Nemp = 250 samples obtained by applying standard box attack (33 strategy with y = 16. We observe from the certified results that the decremental stability radii are larger than those of incremental stability. This is reasonable since the base classifier sees much more of the input when analyzing decremental stability and is thus more confident on average, i.c., achieves larger confidence gap. Morcover, empirical radii often cover up to half of the input, which suggests that our certified analysis quite conservative.
4.2 (E2) Stability-Accurace Trade-Offs
We next investigate how smoothing impacts the classifier accuracy. As À decreases due to more smoothing, the base classifier sees increasingly zeroed-out features - which should hurt accuracy. We took N = 2000 samples for each classifier on their respective datasets and plotted the certified accuracy radius of decremental stability.
8

---

Vision Transformer
ResNet50
RoBERTa
0.8
A-8/8 10.835)
A-8/8 (G.756)
0.8
Certified Accuracy
A=4/8 (0.791)
4/ (0.722)
2=4/8 10.7481
A-2/8 (0.752)
2-2/8 (C.646)
0.6
2-2/8 (0.633)
1=1/8 10.695)
A=1/8 (0.571)
2=18 (0.566)
A=1/20 (0.390)
0.4
A=1/10 10.501)
0.4
A=1220 (0.467)
0.2
0.10 Fraction of Features
0.15
0.05
0:10
0.0
0.3
0.5
Frection Features
Fractior of Features
Figure 5: Certified accuracy decremental stability radius. N 2000.
We show the results Figure 5 where the clean accuracy (in parentheses) decreases with as expected. This accuracy drop is especially pronounced for ResNet50, and we suspect that the transformer architecture of Vision Transformer and RoBERTa makes them more resilient to the randomized masking of features. Nevertheless, this experiment demonstrates that large models, especially transformers, can tolerate non-tri con-trivial noise from MuS while maintaining high accuracy.
Vision Iransformer
ResNet50
RoBeRla
0.80
0.70
VGrad
VSrad
WS-ad
Fraction of Footures
IGrad
0.78
IGrad
0.8
IGred
0.68
LIME
0.76
LIME
0.7
LIME
SHAP
SHAP
0.66
0.74
0.0-
0.72
0.64
0.125
0,250
0.375
0.500
0.125
0.250
0.375
0.5 0.500
0.125
0.750
0.375
0.500
Lipschitz Constant
Lipschitz Constant À
Lipschitz Constant
Figure 6: Average k/n vs. A, where k = ||((x)] | is the number of features for (f, sp) to be consistent, incrementally stable with radius 1, and decrementally stable with radius 1. 250.
4.3
EE3) Which Explanation Method to Pick?
Finally, explore which feature attribution method is best suited to stability guarantees of explain- able model (f, sp). All four methods vo E (LIME, SHAP, VGrad, IGrad) are continuous-valued, for which we samples N = 250 inputs from each model's respective dataset. For each input x, the feature importance ranking generated by (zx to iteratively build p(x) in a greedy manner like in Section 2.4 For some x, let k. s(x)//n /n be the number fraction of features needed for (S, s)) to be consistent, incrementally stable with radius 1, and decrementally stable with radius 1. We then plot the average k, for different methods at X E (1/8,... 4/8) in Figure where note that SHAP tends to require fewer features to achieve the desired properties, while VGrad tends to require more. However, we do believe these be decisive results, as many curves are relatively close, especially for Vision Transformer and ResNet50.
Related Works
For extensive surveys on explainability methods see 16
20 34
35
36
37
38 Notable feature
attribution methods include Vanilla Gradient Saliency [5] SmoothGrad [23 Integrated Gradients [8] Grad-CAM (39], Occlusion
40,
LIME [6), SHAP 7) and their variants. Of these. Shapley value-
based [17 methods 7
24
25 are rooted in axiomatic principles, as are Integrated Gradients g
41. The work of 42 finds confidence intervals over attribution scores. A study of common
feature attribution methods is done in 43]. Similar to our approach is [44), which studies binary- valued classifiers and presents an algorithm with succinetness and probabilistic precision guarantees.
Different metrics for evaluating feature attributions are studied in [16 18
47
48
49
50
51
Whether an attribution correctly identifies relevant features is a well-known issue
52
53 Many
methods also susceptible to adversarial attacks [54] (5). As negative result,
[56] shows that

---

feature attributions have provably poor performance on sufficiently rich model classes. Related to feature attributions are data attributions [57 58 59, which assigns values training data points. Also related to formal guarantees are formal methods-based approaches towards explainability [60]
Conclusion
We study provable stability guarantees for binary feature attribution methods through the framework of explainable models. A selection of features is stable if the additional inclusion of other features does alter its explanatory power. We show that if the classifier is Lipschitz with respect the masking of features, then one can guarantee relaxed variants of stability. To achieve this Lipschitz condition, we develop smoothing method called Multiplicative Smoothing (MuS). This method is parametric to the choice of noise distribution, allowing us to construct and exploit distributions with structured dependence for exact and efficient evaluation. We evaluate MuS on vision and language models and demonstrate that MuS yields strong stability guarantees at only small cost to accuracy.
Acknowledgements
This research was partially supported by NSF award SLES 2331783 and a gift from AWS AL
References
[1] Mauricio Reyes, Raphael Meier, Sérgio Pereira, Carlos A Silva, Fried-Michael Dahlweid, Hendrik von Kobligk,, Ronald M Summers, and Roland Wiest. On the interpretability of artificial intelligence in radiology: challenges and opportunities. Radiology: artificial intelligence, 190043, 2020.
[2] Erico Tjoa and Cuntai Guan. A survey on explainable artificial intelligence (xai): Toward medical xai. IEEE transactions on neural networks and learning systems, 32((1))44993 4813, 2020.
[3] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech., 31:841, 2017.
[4] Adrien Bibal, Michael Lognoul, Alexandre De Streel, and Benoît Frénay. Legal requirements on explainability in machine learning. Artificial Intelligence and Law, 29:149 169, 2021.
[5] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034, 2013.
[6] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. whhy should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016.
[7] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
[8] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, In International conference on machine learning, pages 3319-3328. PMLR, 2017.
[9] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11 1929, 2020.
[10] Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3681-3688. 2019.
10

---

[11] Joseph Paul Cohen, Joseph D. Viviano, Paul Bertin, Paul Morrison, Parsa Torabian, Matteo Guarrera, Matthew P Lungren, Akshay Chaudhari, Rupert Brooks, Mohammad Hashir, and Hadrien Bertrand. Tay Vision: A library of chest X-ray datasets and models. In Medical Imaging with Deep Learning, 2022.
[12] Gavin Brown. A new perspective for information theoretic feature selection. In Artificial intelligence and statistics, pages 49-56. PMLR, 2009.
[13] Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information--theorttic perspective on model interpretation. In International Conference on Machine Learning, pages 883-892. PMLR, 2018.
[14] Xiaoping Li, Yadi Wang, and Rubén Ruiz. A survey on sparse learning models for feature selection. IEEE transactions on cybernetics, 12(3):1642-1660, 2020.
[15] Akhilan Boopathy, Sijia Liu, Gaoyuan Zhang, Cymthia Liu, Pin-Yr Chen, Shiyu Chang, and Luca Daniel. Proper network interpretability helps adversarial robustness in classification. In International Conference Machine Learning, pages 1014-1023, PMLR, 2020.
[16] Meike Nauta, Jan Trienes, Shreyasi Pathak, Elisa Nguyen, Michelle Peters, Yasmin Schmitt, Jörg Schlötterer, Maurice van Keulen, and Christin Seifert. From anecdotal evidence to quantitative evaluation methods: A systematic review evaluating explainable ai. arXiv preprint arXiv: Wxxi::200.081161 20,,, 2022.
[17] L.S. Shapley. A value for n-person games. Contributions to the Theory of Games, pages 307-317, 1953.
[18] Yilun Zhou, Serena Booth, Marco Tulio Ribeiro, and Julie Shah. Do feature attribution methods correctly attribute features? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 0033,9633, 2022.
[19] Alon Jacovi and Yoav Goldberg. Towards faithfully interpretable nlp systems: How should we define and evaluate faithfulness? In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4198-4205, 2020.
[20] Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P Trevino, Jiliang Tang, and Huan Liu. Feature selection: A data perspective. ACM computing surveys (CSUR), 50(6):1-45, 2017.
[21] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320. PMLR, 2019.
[22] Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference Machine Learning, pages 10693-10705. PMLR, 2020.
[23] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. arXiv preprint urXiv:1706.03825 2017.
[24] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International conference machine learning, pages 9269-9278. PMLR, 2020.
[25] Yongchan Kwon and James Zou. Weightedshap: analyzing and improving shapley based feature attributions. arXiv preprint arXiv:2209.13422, 2022.
[26] Reza Alizadeh, Janet K Allen, and Farrokh Mistree. Managing computational complexity using surrogate models: a critical review. Research in Engineering Design, 31:275-299 2020.
[27] Hadi Salman, Saachi Jain, Eric Wong, and Aleksander Madry. Certified patch robustness via smoothed vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15137-151477 2022.
[28] Alexander J Levine and Soheil Feizi. Improved, deterministic smoothing for I certified robustness. In International Conference Machine Learning, pages 6254-6264. PMLR, 2021.
11

---

[29] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[30] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprini arXiv: 1907. 1692, 2019.
[31] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 115:211-231 2522, 2015.
[32] Francesco Barbieri, Jose Camacho-Colladde Leonardo Neves, and Luis Espinosa-Anke. Tweet- eval: Unified benchmark and comparative evaluation for tweet classification. arXiv preprint arXiv:2010. 12200..22211... 2020.
[33] Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26,
2017.
(34] Nadia Burkart and Marco F Huber. A survey on the explainability of supervised machine learning. Journal of Artificial Intelligence Research, 70:245-317, 2021.
[35] Jianlong Zhou, Amir H Gandomi, Fang Chen, and Andreas Holzinger. Evaluating the quality of machine learning explanations: A survey on methods and metrics. Electronics, 10(5):593, 2021.
[36] Qing Lyu, Marianna Apidianaki, and Chris Callison- Towards faithful model explanation in nlp: A survey. arXiv preprint arXiv:2209. 1326, 2022.
[37] Xuhong Li, Haoyi Xiong, Xingjian Li, Xuanyu Wu, Xiao Zhang, Ji Liu, Jiang Bian, and Dejing Dou. Interpretable deep learning: Interpretation, interpretability, trustworthiness, and beyond. Knowledge and Information Systems, 64(12):319-33334 2022.
[38] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108 07258, 2021.
[39] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE international conference on computer vision, pages 618-626, 2017.
[40] Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part 13, pages 818-833. Springer. 2014.
[41] Daniel D Lundstrom, Tianjian Huang, and Meisam Razaviyayn. A rigorous study of integrated gradients method and extensions to internal neuron attributions. In International Conference on Machine Learning, pages 14485-14555 PMLR, 2022.
[42] Dylan Slack, Anna Hilgard, Sameer Singh, and Himabindu Lakkaraju. Reliable post hoc explanations: Modeling uncertainty in explainability. Advances in neural information processing 2021.
systems,
[43] Tessa Han, Suraj Srinivas, and Himabindu Lakkaraju. Which explanation should choose? a function approximation perspective to characterizing post hoc explanations. arXiv preprint arXiv:2206.01254, 2022.
[44] Guy Blanc, Jane Lange, and Li- Yang Tan. Provably efficient, succinet, and precise explanations. Advances in Neural Information Processing Systems, 34:6129-611 6141, 2021.
[45] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in neural information processing systems, 31, 2018.
12

---

[46] Sara Hooker. Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. A benchmark for in- terpretability methods in deep neural networks. Advances in neural information processing systems, 32, 2019.
[47] Jay Young Sarthak Jain, Nazneen Fatema Rajani, Eric Lehman, Caiming Xiong, Richard Socher, and Byron C Wallace. Eraser: A benchmark to evaluate rationalized nlp models. arXiv preprint arXiv:I911.0344 2019.
[48] Jasmijn Bastings, Sebastian Ebert, Polina Zablotskaia, Anders Sandholm, and Katja Filippova. will you find these shortcuts?" a protocol for evaluating the faithfulness of input salience methods for text classification. arXiv preprint arXiv:2111.0736) 2021.
[49] Yao Rong, Tobias Leemann, Vadim Borisov, Gjergji Kasneci, and Enkelejda Kasneci. A consis- tent and efficient evaluation strategy for attribution methods. arXiv preprint arXiv:2202.00449, 2022.
[50] Yilun Zhou and Julie Shah. The solvability of interpretability evaluation metrics. arXiv preprint arXiv:2205.0860 08696, 2022.
[51] Julius Adebayo. Michael Muelly, Harold Abelson, and Been Kim. Post hoc explanations may be ineffective for detecting unknown spurious correlation. In International Conference on Learning Representations, 2022.
[52] Mengjiao Yang and Been Kim. Benchmarking attribution methods with relative feature impor- tance. arXiv preprint
2019.
[53] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber, Kristof T Schütt, Sven Dähne, Dumitru Erhan, and Been Kim. The (un) reliability of saliency methods. In Explainable AI: Interpreting, Explaining and Visualizing Deep Learning, pages 267-280. Springer, 2019.
[54] Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual expla- nations can be manipulated. Advances in neural information processing systems, 34:62-75, 2021.
[55] Adam Ivankay, Ivan Girardi, Chiara Marchiori, and Pascal Frossard. Fooling explanations in text classifiers. arXiv preprint arXiv:2206.03178, 2022.
[56] Blair Bilodeau, Natasha Jaques, Pang Wei Koh, and Been Kim. Impossibility theorems for feature attribution. arXiv preprint arXiv:2212.11870, 2022.
[57] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885-1894. PMLR, 2017.
[58] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclere, and Aleksander Madry, Datamodels: Predicting predictions from training data. arXiv preprint arXiv:2202.00622. 2022.
[59] Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Madry. Trak: Attributing model behavior at scale. arXiv preprint arXiv:2303. 2023.
[60] Shahaf Bassan and Guy Katz. Towards formal xai: Formally approximate minimal explanations of neural networks. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 187-207. Springer, 2023.
[61] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.690, 2014.
[62] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning scale. arXiv preprint 1rXiv:1611.012330 2016.
[63] Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robust- ness (python library), 2019.
13

---

A
Proofs and Theoretical Discussions
In this Section, we present the proofs of our main results and some extensions to MuS.
A.1 Proofs of Main Results
A.1.1 Proof of Theorem 3.2
Proof. By linearity, we have:
g(æ,a) g(z, a')
E anD
a=aos, o' a o s.
so it suffices to analyze an arbitrary term by fixing some s D. Consider any X, let a, a' E {0, 10" and define 8 = a' Observe that o; # a' exactly when |6 = and = 1.
Since 8 ~ (A), we thus have Pr[as + at} = \lozl. and applying the union bound:
n
Pr + anD
Pr
11ō1k A|18112,
aND
and so:
1g(2, - - a')l
E [h(2 ( 112 ((xoa'))
lnD
Pr lā + ā'] snD
Pr lä a')
E -20d)) á'
RND
Note that E|Mx - a'] and
- -g6,0))
Pr la fa] SnD
E (( h M a')
BND
S because h(-)) E [0
$ Pr z + á'l MDD
S A||o|1 1.
Thus, g(x,-) is X-Lipschitz in the e norm.
A.1.2 Proof of Theorem 3.3
Proof. We first show incremental stability. Consider any x E X, then by masking equivalence:
f(x f()))(z) g( o p(x). 1) ((x)),
and let gA. ga be the top-two class probabilities of as defined in ( By Theorem 3.2 both gA, Jn Lipschitz in their second parameter, and so for all E {0, 1)":
[ ((x)) 94 a)Il1 _ \|(((r) - a:|1
(19n(x, - gn(a, a)Il S Al(p(x) - a:]]
Observe that if is sufficiently close to ((x),
2x||((x) - all: S ga(a, (lx)) gn(e, sfx)),
then the top-class index of ((z ((x) and g(z, a:) are the same. This means that g(x, p(x)) s g( and thus f(r @ p(())) = f(r @ a). thus proving incremental stability with radius d(z, (2x))
The decremental stability case is similar, except replace (p(x) with
A.2 Some Basic Extensions
Below, we present some extensions MuS that help increase the fraction of the input to which we can guarantce stability.
14

---

A.2.1 Feature Grouping
We have so far assumed that X' = R", but sometimes it may be desirable to group features together, e.g., color channels of the same pixel. Our results also hold for more general X R R
where for such x E X and a E I" we lift O as
i x R" + X,
(x = 2, -laa; = 1] E R
All of our proofs are identical under this construction, with the exception of the dimensionalities of terms like (x o a:). Figure 1 gives
gives an example of feature grouping.
B All Experiments
Models, Datasets, and Explanation Methods We evaluate on two vision models (Vision Trans- former [9] and ResNet50 (2]) and one language model (RoBERTa 30). For the vision dataset, we use 1mageNer1 K [31] for the language dataset, we use TweetEval [3 sentiment analysis. We
use four explanation methods in SHAP 77]. LIME [6], Integrated Gradients (IGrad) [8]. and Vanilla
Gradient Saliency (VGrad) [5] where we take (xx) the top-k weighted features.
Training Details We used Adam [6] as our optimizer with default parameters and learn- ing rate of 10-6 for 5 epochs. Because we consider À E {1/8, 2/8, 3/8, 8/8} and E (Vision Transformer, ResNet50, RoBERTa), there are a total of 15 different models for most ex- periments. To train with a particular X: for each training input æ. we generate two random maskings one where of the features are zeroed and one where A/2 of the features are zeroed. This additional X/2 zeroing is to account for the fact that inputs to a smoothed model will be subject to masking by as well as ((r),, where the scaling factor of 1/2 is informed by our prior experience about the size of stable explanation.
Miscellaneous Preprocessing For images in ImageNet K feature grouping (Section A.2. to group the 3 x 224 x 224 dimensional image into patches of size 3 x 28 x 28, such that there remains 64 feature groups. Each feature of feature group then receives the same value of noise during smoothing. We report radii of stability as a fraction of the feature groups covered. For example, if some input from ImageNetIK, we get an incremental stability radius of r, then we report r r/64 as the fraction of features up to which we are guaranteed to be stable. This is especially amenable to evaluating RoBERTa TweetEval where inputs do not have uniform token lengths, i.e, do not have uniform feature dimensions. In all of our experiments, we use the quantized noise as in Section 3.3 with a quantization parameter of q = 64, with the exception of Appendix [ and Appendix B.3, Our experiments are organized as follows:
(Section B.
What is the quality of stability guarantees?
(Section B.
What is the theoretical vs empirical stability that can be guaranteed?
-We g
64 for theoretical guarantees, q 16 for empirical guarantees.
(Section B.3 What are the stability-accuracy trade-offs?
We use q E (16,32, 64, 128} to study the effect of g on MuS-smoothed performance. Which explanation method is best?
(Section
B.4
(Section B.5
Does additive smoothing improve empirical stability?
(Section
B.6
Does adversarial training improve empirical stability?
B.1 Quality of Stability Guarantees
Here we study what radii of stability are certifiable, and how often these can be achieved with different models and explanation methods. We therefore consider explainable models (f. sp) constructed from base models h E (Vision Transformer, ResNet50, RoBERTa) and explanation methods & E {SHAP, LIME, IGrad, VGrad) with top-k E {1/8, 2/8, 3/8} feature selection. We take N 2000 samples from each model's respective datasets and compute the following value for each radius:
value(r) # (f.v) consistent and inc (dec) stable with radius < r)
N Plots of incremental stability are the left; plots of decremental stability are the right.
15

---

Vision Transformer, SHAP
IncStab
1/8)
A-8/8 (0.628)
A-8/8 (0.628)
0.6
A-4/8 (0.577)
0.8
A-4/8 (0.577)
A-2/8 (0.387)
A-2/8 (0.387)
Hold
0.4
A-1/8 (0.075)
0.4
A-1/8 (0.075)
A-1/16 (0.001)
Am1/16 (0.001)
0.2
0.2
0.00
0.03
0.04
0.06
0.00
0.02
0.03
0.05
0.06
0.8
Cons+incStab (SHAP-2/8)
0.8
Cons+ DecStab (SHAP-2/8)
Am4/8 (0.001)
Am4/8 (0.801)
(0.672)
Prop Hold
A-1/8 (0.515)
1,1/8 (0.515)
0.2
0.2
0.0
0.00
0.03
0.06
0.02
0.05
ConseincStab (SHAP-3/8)
Cons+ DecStab (SHAP-3/8)
Prop Hold Rate
0.8
X=8/8 (0.896)
0.8
A=8/8 (0.896)
Am4/8 (0.867)
Am4/8 (0.867)
0.0
X-2/8 (0.787)
0.0
A-2/0 (0.787)
A=1/8 (0.679)
1=1/8 (0.679)
X-1/16 (0.326)
>=1/16 (0.326)
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
Fraction of Features
Fraction of Features
Vision Transformer, LIME
0.8
0.8
Cons iicss-iinnee incStab (LIME-12) 1/8)
Cons + DecStab ILIME 1/8)
A=8/8
0.6
A-4/8 (0.512)
0.6
A-4/8 (0.512)
A=2/8
(0.379)
Prop Hold
A-1/8 (0.074)
A-1/8 (0.074)
A-1/16 (0.001)
A-1/16 (0.001)
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.8
0.8
(LIME-2/8)
DerStab
2-8/8 (0.727)
A-8/8 (0.727)
2-2/8 (0.638)
2-2/8 (0.638)
Prop Hold
1=1/8
(0.494)
A-1/16 (0.053)
A- 1-16 (0.053)
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.05
0.8
Cons+incStab (LIME-3/8)
0.8
+ DecStab (LIME-3/8)
A-8/8 (0.815)
A-8/8 (0.815)
0.6
A=4/8 (0.805)
0.6
(0.805)
2-2/8 (0.762)
A-2/8 (0.762)
A=1/8 (0.666)
(0.666)
0.4
0.4
A-1/16 (0.325)
A- 1/16 (0.325)
Prop
0.0
0.0
0.00
0.03
0.06
0.00
0.02
0.03
0.05
0.06
Fraction of Features
Fraction of Features
Figure 7: (Top) Vision Transformer with SHAP. (Bottom) Vision Transformer with LIME, (Left) consistent and incrementally stable. (Right) consistent decrementally stable.
16

---

Vision Transformer, IGrad
0.8
A-8/8 (0.534)
A-8/8 (0.534)
0.8
A-4/8 (0.500)
0.6
A-4/8 (0.500)
A-2/8 (0.390)
A=2/8 (0.390)
Hold
0.4
A-1/8 (0.087)
0.4
A=1/0 (0.087)
A-1/16 (0.001)
Am1/16 (0.001)
0.0
0.00
0.03
0.04
0.06
0.00
0.02
0.03
0.05
0.06
0.8
0.8
Cons+incStab (IOrad-2/8)
Cons+ DecStab (IGrad-2/8)
0.6
Am4/8 (0.724)
0.6
Am4/8 (0.724)
(0.631)
Prop Hold
0.4
A-1/8 (0.486)
0.4
1/1/8 (0.486)
(0.064)
(0.064)
0.0
0.03
0.06
0.02
0.05
Cons+incStab (IGrad-3/8)
Cons+ DecStab (IGrad-3/8)
Prop Rate
X=8/8 (0.852)
A=8/8 (0.852)
0.6
Am4/8 (0.825)
0.6
Am4/8 (0.825)
X-2/8 (0.741]
A-2/0 (0.741)
A=1/8 (0.667)
1=1/8 (0.867)
0.4
X-1/16 (0.339)
0.4
A-1/16 (0.339)
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
Fraction of Features
Fraction of Features
Vision Transformer, VGrad
0.8
0.8
Cons IncStab (VGrad 1/8)
Cons P DecStab (VGrad 1/8)
(0.353)
A=8/8 (0.353)
0.6
A-4/8 (0.342)
0.6
A-4/8 (0.342)
(0.227)
A-2/8 (0.227)
Prop Hold
A-18 (0.049)
A-1/8 (0.049)
A-1/16 (0.001)
A-1/16 (0.001)
0.2
0.2
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.8
0.8
Cons IncStab (VGrad-2/8)
Cons DecStab (VGrad-2/8)
A-8/8 (0.634)
A-8/8 (0.634)
A-2/8 (0.519)
2-2/8 (0.519)
Prop Hold
0.4
(0.371)
0.4
A=1/8 (0.371)
A-1/16 (0.035)
A-1/16 (0.035)
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.05
0.8
0.8
Cons+incStab (VGrad-3/8)
Cons-DecStab (VGrad-3/8)
A-8/8 (0.782)
A-8/8 (0.702)
0.6
0.6
A=4/8 (0.768)
A-2/8 (0.680)
A-2/8 (0.680)
Hold
0.4
A-1/8 (0.578)
A-1/16 (0.266)
A-1/26 (0.266)
0.2
0.0
0.0
0.00
0.03
0.06
0.00
0.02
0.03
0.05
0.06
Fraction of Features
Fraction of Features
Figure 8: (Top) Vision Transformer with IGrad. (Bottom) Vision Transformer with VGrad. (Left) consistent and incrementally stable. (Right) consistent decrementally stable.
17

---

ResNet50, SHAP
1/8)
A-8/8 (0.652)
A=8/8 (0.652)
0.8
A-4/8 (0.602)
0.8
A-4/8 (0.602)
A-2/8 (0.480)
A-2/8 (0.480)
Hold
0.4
A-1/8 (0.131)
0.4
A-1/0 (0.131)
A-1/16 (0.001)
Am1/16 (0.001)
0.2
0.2
0.00
0.03
0.04
0.06
0.00
0.02
0.03
0.05
0.06
0.8
Cons+incStab (SHAP-2/8)
0.8
Cons+ DecStab (SHAP-2/8)
0.6
Am4/8
(0.764)
0.0
Am4/8 (0.764)
(0.667)
Prop Hold
0.4
A-1/8 (0.549)
0.4
1/1/8 (0.549)
0.2
0.2
0.03
0.06
0.02
0.05
ConseincStab (SHAP-3/8)
Cons+ DecStab (SHAP-3/8)
Prop Rate
X=8/8 (0.851)
A=8/8 (0.851)
0.6
A-4/8 (0.825)
0.6
Am4/8 (0.825)
X-2/8 (0.755)
A-2/0 (0.755)
A=1/8 (0.673)
1=1/8 (0.673)
0.4
X-1/16 (0.386)
0.4
A=1/16 (0.386)
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
Fraction of Features
Fraction of Features
ResNet50, LIME
0.8
0.8
Cons e incStab (LIME-1/9
Cons + DecStab (LIME 1/8)
A=8/8 (0.386)
0.6
A-4/8 (0.395)
0.6
A-4/8 (0.395)
A=2/8 3093
(0.309)
Prop Hold
A-188 (0.067)
A-1/8 (0.067)
A-1/16 (0.001)
A-1/16 (0.001)
0.2
0.2
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.8
0.8
(LIME-2/8)
DerStab
2-8/8 (0.593)
A-8/8 (0.593)
2-2/0 (0.529)
2-2/8 (0.529)
Prop Hold
0.4
1=1/8
0.4
(0.408)
A-1/16 (0.051)
A-1/16 (0.051)
0.2
0.2
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.05
Cons+incStab (LIME-3/8)
DecStab (LIME-3/8)
A-8/8 (0.715)
A-8/8 (0.715)
A=4/8 (0.712)
(0.712)
A-2/8 (0.644)
A-2/8 (0.644)
Prop Hold
0.4
A=1/8
0.4
(0.566)
A-1/16 (0.283)
1-1/16 (0.283)
0.2
0.2
0.0
0.00
0.03
0.06
0.00
0.02
0.03
0.05
0.06
Fraction of Features
Fraction of Features
Figure 9: (Top) ResNet50 with SHAP. (Bottom) ResNet50 with LIME. (Left) consistent and incre-
mentally stable. (Right) consistent and decrementally stable.
18

---

ResNet50, IGrad
A-8/8 (0.505)
A-8/8 (0.505)
0.8
A-4/8 (0.485)
0.6
A-4/8 (0.485)
A-2/8 (0.373)
A=2/8 (0.373)
Hold
0.4
A-1/8 (0.084)
0.4
A=1/8 (0.084)
A-1/16 (0.001)
Am1/16 (0.001)
0.0
0.30
0.03
0.04
0.06
0.00
0.02
0.03
0.05
0.06
0.8
0.8
Cons+incStab (IOrad-2/8)
Cons+ DecStab (IGrad-2/8)
0.6
Am4/8 (0.690)
0.6
Am4/8 (0.690)
(0.595)
Prop Hold
0.4
A-1/8 [0.461]
0.4
1/1/8 (0.4611)
0.03
0.06
0.02
0.05
0.8
0.8
Cons+incstab (IGrad-3/8)
Cons+ DecStab (IGrad-3/8)
X=8/8 (0.788)
A=8/8 (0.788)
0.6
A-4/8 (0.775)
0.6
Am4/8 (0.775)
X-2/8 [0.701]
A-2/0 (0.701)
Prop Hold
0.4
A=1/8 (0.616)
0.4
A=1/8 (0.616)
X-1/16 (0.328)
A=1/16 (0.328)
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
Fraction of Features
Fraction of Features
ResNet50, VGrad
0.8
0.8
Cons IncStab (VGrad 1/8)
Cons DecStab (VGrad 1/8)
(0.415)
A=8/8 (0.415)
0.6
A-4/8 (0.412)
0.6
A-4/8 (0.412)
(0.310)
A-2/8 (0.310)
Prop Hold
A-18 (0.079)
A-1/8 (0.079)
A-1/16 (0.001)
A-1/16 (0.001)
0.2
0.2
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.8
0.8
Cons IncStab (VGrad-2/8)
Cons DecStab (VGrad
A-8/8 (0.641)
A-8/8 (0.641)
A-2/8 (0.529)
2-2/8 (0. (0.529)
Hold
0.4
0.4
A=1/8
A-1/16 (0.059)
A-1/16 (0.059)
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
0.05
Cons+incStab (VGrad-3/8)
Cons+DecStab (VGrad-3/8)
A-8/8 (0.750)
A-888 (0.750)
A=4/8 (0.729)
A-2/8 (0.658)
A-2/8 (0.658)
Hold
0.4
(0.575)
0.4
A-1/8 (0.575)
A-1/16 (0.294)
A-1/26 (0.294)
0.2
0.2
0.0
0.00
0.03
0.06
0.00
0.02
0.05
0.06
Fraction of Features
Fraction of Features
Figure 10: (Top) ResNe150 with IGrad. (Bottom) ResNet50 with VGrad. (Left) consistent and incrementally stable. (Right) consistent and decrementally stable.
19

---

RoBERTA, SHAP
1/8)
A-8/8 (0.740)
A-8/8 (0.740)
A-4/8 (0.787)
A-4/8 (0.787)
2-2/8 (0.734)
A-2/8 (0.734)
1-1/8 (0.788)
A=1/8 (0.788)
A-1/16 (0.958)
Am1/16 (0.958)
Prop
0.0
0.5
Cons+incStab (SHAP-2/8)
Cons+ DecStab (SHAP-2/8)
0.8
0.8
Am4/8 (0.834)
Am4/8 (0.834)
Prop Hold
0.0
1/1/8 (0.839)
(0.810)
0.8
1/1/8 (0.839)
0.4
ConseincStab (SHAP-3/8)
Cons+ DecStab (SHAP-3/8)
0.8
X=8/B (0.864)
0.8
A=8/8 (0.864)
A-4/8 (0.048)
Am4/8 (0.848)
Prop Hold
0.6
X-2/8 (0.029)
A=1/8 (0.866)
0.6-
A-2/8 (0.829)
A=1/8 (0.866)
0.4
X-1/16 (0.960)
0.4
A=1/16 (0.960)
0.2
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Fraction of Features
Fraction of Features
RoBERTA, LIME
Cons + incStab (LIME-1/9
Cons + DecStab ILIME 1/8)
0.8
A=8/8 (0.659)
0.8
A-4/8 (0.700)
A-4/8 (0.700)
0.6
2=2/8 691)
0.6-
(0.691)
Prop Hold
1-188 (0.783)
A-1/8 (0.783)
0.4
1-1/16 (0.958)
0.4
1-1/16 (0.958)
0.2
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.5
0.0
0.1
0.2
0.3
0.4
0.5
2/8)
DerStab
2-8/8 (0. 734)
A-8/8 (0.734)
0.6
2-2/0 (0. (707
0.6
2-2/8 (0.770)
Prop Hold
1=1
(0.804)
0.4
1-1/16 (0.958)
0.4
A-1/16 (0.958)
0.2
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Cons+incStab (LIME-3/8)
Cons + DecStab (LIME-3/8)
A-8/8 (0.780)
A-8/8 (0.788)
A=4488 (0.819)
(0.819)
2 (0.808)
A-2/8 (0.808)
A=1/8
(0.839)
1-1/16 (0.958)
A-1/16 (0.958)
Prop
0.0
0.5
Fraction of Features
Fraction of Features
Figure 11: (Top) RoBERTa with SHAP. (Bottom) RoBERTa with LIME. (Left) consistent and incrementally stable. (Right) consistent and decrementally stable.
20

---

RoBERTA, IGrad
A-8/8 (0.663)
A-8/8 (0.663)
A-4/8 (0.768)
A-4/8 (0.768)
A-2/8 [0.731]
A=2/8 (0.731)
A-1/8 (0.788)
A=1/8 (0.788)
A-1/16 (0.958)
Am1/16 (0.958)
Prop
0.0
0.5
Cons+incStab (IOrad-2/8)
DecstDe (IGrad-2/8)
0.8
0.8
Am4/8 (0.008)
Am4/8 (0.808)
Prop Hold
0.0
A-1/8 (0.836)
(0.799)
0.8
1/1/8 (0.836)
0.4
Cons+incstab (IGrad-3/8)
Cons+DecStab (IGrad-3/8)
0.8
X=8/8 (0.808)
0.8
A=8/8 (0.808)
A-4/8 (0.847)
Am4/8 (0.847)
Prop Hold
0.6
X-2/8 (0.044)
A=1/8 (0.877)
0.6-
A-2/0 (0.044)
A=1/8 (0.877)
0.4
X-1/16 (0.961)
0.4
A=1/16 (0.961)
0.2
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Fraction of Features
Fraction of Features
RoBERTA, VGrad
Cons IncStab (VGrad 1/8)
Cons DecStab (VGrad-1/p 1/8)
Prop Hold Rate
0.8
(0.596)
0.8
(0.596)
A-4/8 (0.611)
A-4/8 (0.611)
0.6
(0.637)
0.6-
A-2/8 (0.637)
A-18 (0.783)
A-1/8 (0.783)
0.4
A-1/16 (0.958)
0.4
A-1/16 (0.958)
0.2
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Cons IncStab (VGrad-2p)
Cons DecStab (VGrad 2/rrdd-2/8)
A-8/8 (0.682)
A-8/8 (0.682)
(0.709)
0.6
A-2/8 (0.716)
0.6
2-2/8 (0.716)
Prop Hold
(0.795)
A=1/8 (0.795)
0.4
A- 1/16 (0.958)
0.4
A-1/16 (0.958)
0.2
0.2
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Cons-incStab (VGrad-3/8)
Cons+DecStab (VGrad-3/8)
A-8/8 (0.753)
A-8/8 (0.753)
A=4/8 (0.776)
A-2/8 (0.780)
A-2/8 (0.780)
(0.819)
A-1/8 (0.819)
A-1/16 (0.958)
A-1/26 (0.958)
0.0
0.5
0.5
Fraction of Features
Fraction of Features
Figure 12: (Top) RoBERTa with IGrad. (Bottom) RoBERTa with VGrad. (Left) consistent and incrementally stable. (Right) consistent and decrementally stable.
21

---

B.2 Theoretical vs Empirical
We compare the certifiable theoretical stability guarantees with what is empirically attained via standard box attack search [33]. This is an extension of Section 4.2 where we now show all models as evaluated with top25%. We take q 64 with Neert 2000 for the certified plots, and
q 64 with Nemp 250 for the empirical plots. This is because box attack is time-intensive.
Vision Transformer, SHAP top-25%
08
Cort Conss-ine Inchlab
0.8
Cart Cons DecSrab
Hold Rabe
0.6
A-4Mt (3. 821)
0.6
k-418 (0. (0.801)
X-2/8
(0.672)
0.4
(3.515)
0.4
(0.513)
0.00
0.31
0.22
0.03
0.04
0L05
0.08
0.01
0.01
0.37
0.03
0.04
0.05
0.06
0.8
Fmp Stab--
0.-
Emp Cone- DeeStah
0.6
A-48
36
Am4 (0-816)
Prop Hold
2-28 (3 7081
A- 2/8 (0.768)
0.4
04
(0.49))
0.
0.1
0.2
0.3
0.1
0.5
0.0
0.1
0.2
0.3
0.4
0.3
Iraction Feetures
Iraction leeatures
ResNet50, SHAP top-25%
0.8
Cert Stea
A8
Cert Cons+ Dec
Prop Hold Rato
0.6
1-88 (3.826)
06
A-8 (0.806)
A=28 (3 6676
A-218 (0.667)
0.4
3- 3-188 (3.549)
0.1
2- (0.549)
02
02
0.0
0.0
0.00
0.91
8.02
6.03
0.04
0.05
0.06
0.00
0.01
0.02
0.03
0.04
0.05
Emp
Emp
Prop Hold Rate
A-p (3 004)
Juays (o.004)
0.6
0.0
(0.776)
(3:654)
(0.664)
0.4
A-1/8 (0 (3.556)
2- (0.556)
0.
0.0
0.2
0.2
0.3
Praction of Features
Fraction of Features
RoBERTa, SHAP top-25%
Cort IncStab
DecStab
Prop hold Rete
A=88 (a 3261
A-8i8 (0.925)
3-48 (3.834)
X-418 (0.834)
0.4
A=1/8 (0.839)
0.0
X=1/8 (0.339)
02-
02-
0.
0.8
0.8
Prop Hold
Lmp CorssiicSSal
Emp Coro Dtab
0.4
(0.516)
A= (0.610)
A-418
A-2,8 (0.816)
A-2 (0.016)
1-1 (0.852)
A-1
0.2
0.3
00
0.1
0.2
0.3
0.4
Fraction
Fraction
Figure 13: With SHAP 25%. (Top) Vision Transformer. (Middle) ResNet50. (Bottom) RoBERTa.
22

---

B.3 Stability-Accuraccy Trade-Off's
We study how the accuracy degrades with X. We consider smoothed model f constructed from base classifier h E {Vision Transformer, ResNet50, RoBERTa) and vary À E {1/16, 1/8, 2/8, 4/8, 8/8}. We then take N 2000 samples from each respective dataset and measure the accuracy of f at different radii. We use f(x)) _ true_ __lbell to mean that f attained the correct prediction at E X, and we plot the following value at each radius r:
value(r) #(= f()) = true _abbel and dec stable with radius S r)
N
Below, we show the plots for different quantization parameters of q E (16, 32, 64, 128). The q = 64 plots are identical to that of Figure [ We see that increasing q generally improves the performance of MuS, but at a computational cost since this requires evaluations of h.
Vision Transformer (q= 16)
ResNet50 (6)
RoBERTa (q=16) 16)
0.8
A-8/8 (0.835)
A-8/8 (0.756)
0.0
2-88 (0.8311
Certified Accuracy
A-4/8 (0.733)
A-4/8 (0.722)
A-4/8 (0.740)
2-2/8 749)
A-2/8 (0
0.6-
1-1/0 (0.636)
A-1/U (0.334)
1=10 (0.5881
A=1/26 (0.592)
0.4
A=1/16 (0.48C)
>=1/28 (0.485)
0.2
0.2
0.0
0.00
0.05
0.10
0.15
0.00
0.05
0.10
0.15
0.0
0.1
0.2
0.3
0.4
0.5
Fraction of reatures
Fraction reatures
Hraction Heatures
Vision Transfomner (q=32)
ResNet50 (q=32)
RoBERTa (q=32)
0.8
A-8/8 (0.835)
A-8/8 (C.756)
0.8
A-8/8 (0.8311
Certified Accuracy
A=4/8 (0.730)
4=4 (0.727)
4,4/8 (0.751)
A-2/8 [0.754)
A-2/8 (C.648)
0.6
2=2/8 (0.646)
A-1/8 10.693)
A-1/8 (0.557)
X-18 (0.5531
A=1/16 (0.617)
0.4
A=1/16 10 (0.492)
0.4-
A=1/266 (0 465)
0.2
0.0
0.00
0.05
0.10
0.15
0.00
0.05
0.10
0.15
0.0
0.1
0.2
0.3
0.4
0.5
Fraction of Festures
Frection Features
Fraction Features
Vision Transformer (q=64)
ResNet50 (q=64)
RoBERTa (q=64)
(0.825)
A-B/U (c.726)
0.3
(0.831)
Certified Accuracy
A-4/8 (0.791
Am4/8 (0:722)
Am4/8 (0,748)
0.6-
A=2/8 (0.752)
2=2/8 (0.646)
0.6
A=2/8 (0.655)
1-1/8 (0.635)
A-1/8 (C.571)
(0.566)
A-1/16 (0. 598)
0.4
A-1/16 [0.501)
0.4
A-1/26 (D 467)
0.2
0.0
0.05
0.10
0.15
0.05
0.10
0.15
0.0
0.3
0.5
Fraction of Features
Fraction of Features
Fractior of Features
Vision Transformer (q= 128)
ResNet50 (q=128)
RoBERTa (q=128)
0.8
À=888 (0.805)
Am8/8 (0.756)
0.8
A=888 (0.831)
Certified Accuracy
A-4/8 (0.795)
A-4/9 (0.733)
2-4/8 (0.7571
0.6
A-2 (0.755)
0.6
A-2/8 (0 646)
0.6
A-2/8 60.6671
[0.691)
A-1/U (0.572)
(0.561)
0.4
A=1/26 (0.524)
0.4
Aw1/16 10.513)
0.4-
A=1/28 (0.464)
0.2
0.2
0.0
0.0
0.0
0.10
0.15
0.05
0.10
0.3
0.5
Fraction of Features
Fraction of reatures
traction of Heatures
Figure 14: Certified accuracy plots for different quantization parameters of g E (16,32, 64, 128).
23

---

B.4 Which Explanation Method is the Best?
We first investigate how many features are needed yield consistent and non-trivially stable explana- tions, as done by the greedy selection algorithm in Section 2.4 For some E X, let k2 denote the fraction features that (ff sp) needs to be consistent, incrementally stable, and decrementally stable with radius 1. We vary À E {1/8,... ..... 4/8), where recall X < 4/8 is needed for non-trivial stability, and use 250 samples to plot the average h This part is identical to Section
Vision Transformer
ResNet50
RoBERTa
0.80
VGrad
Fraction of Features
IGrad
8.78
IGred
0.8
IGred
0.68
0.76
0.7
SHAP
SHAP
SHAP
0.66
0.74
0.72
0.64
0.70
0.4
0.68
0.125
0.250
2.3/5
0.500
0.125
0.375 Lipschitz Constant A
0.250
3.500
0.125
0.250
0.375
0.500
Lipschitz Constant
Lipschitz Constant
Figure 15: (Left) Vision Transformer. (Middle) ResNet50, (Right) RoBERTa.
We next investigate the ability of each method to predict features that lead to high accuracy. Let f(x O p(z)) e true_label, mean that the masked input x @ (xx) yields the correct prediction. We then plot this accuracy as we vary the top-k (1/8, 2/8, 3/8} for different methods y,, and (1/8..... 8/8}, using N = 2000 samples.
Vision Transforeer
obx)-Maseed Accuracy
0.5
0.7
0.4
0.65
Top-1/8
Top-2/B
Top-3/8
VGrac
ViGaad
VGrad
(Grad
IGre
0.55
IGrd
LIME
0.4
UME
SHAP
SHAP
SHAP
0.2
0.3
0.4
0.5
0.2
0.3
0.4
0.5
0.2
0.3
0.4
0.5
Lipschitz Constant
Lipschitz Constant
Lipschitz Constant
ResNet50
Mix]-Makkdd Accuracy
0.60
Top-1/8
Top-2/8
0.55
Top-3/8
VGrad
VGrad
ICrad
IGrad
0.50
Irra
SHAP
SHAP
SHAP
0.3
0.2
0.3
0.4
0.5
0.2
0.3
0.4
0.5
0.2
0.3
0.5
Lipschitz Constant
Lipschitz
Lipschitz Constant
RoBERTa
60x) Marskkee Accuracy
0.70
0.75
0.70
0.65
0.50
0.55
Top-1/U
0.60
Top-2/8
Top-318
VSrad
0.35
VGrad
VGr
0.50
IGrad
IGrad
0.55
IGrad
0.50
0.45
SKAP
0.45
SHAP
0.30
St AP
0.2
0.3
0.
0.5
0.2
0.3
0.4
0.5
0.2
0.3
0.4
0.5
Lipschitz Constant
Lipschitz Constant
Lipschitz Constant
Figure 16: (Top) Vision Transformer. (Middle) ResNet50, (Bottom) RoBERTa.
24

---

B.5 Empirical Stability of Additive Smoothing
We now study how well additive smoothing impacts empirical robustness compared to multiplicative smoothing. Although additive smoothing cannot yield theoretical stability guarantees (c.f. Proposi- [.1] we nevertheless investigate its empirical performance. We use explanations generated by top-25% and use Vision Transformer as our base model h. We fine-tuned different variants of Vision Transformer at À E (8/8, 4/8, 2/8, 1/8} and used these in two general classes models: Vision Transformer with multiplicative smoothing, and Vision Transformer with additive smoothing. We call these two /uus and Sadd respectively, and define them as follows:
mms (x)
E h(x snD
8),
Sadd(
E 8-28 1122.11/2
h(x s)
where for multiplicative smoothing, D is in Theorem 3.2
Over N 250 samples from Ima- K, we check how often incremental stability of radius 2 is obtained, and plot our results in Figure [7 (left). We see that multiplicative smoothing yields better empirical performance than additive smoothing.
B.6 Empirical Stability of Adversarial Training
Similar to Section B.5
we also check how adversarial training 62 affects empirical stability. We
consider ResNet50 with different adversarial training setups from the Robustness Python library 63
and compare them to their respective MuS suS-wrapped variants. As with Section B.5 we take N 250
samples from ImageNetIK, and plot our results in Figure 17 (right).
Incrementally Stable with Radius = 1
Incrementally Stable with Radius = 1
1.0
Additive Smoothing
Adv Robust Trained
Multiplicative Smoothing
MuS- MuS-Wrapped
0.0
0,448
Fraction Samples
0.716
Fraction Samples
0.632
0.356
0.36
0.32
0.28
0.2
0.184
0.156
0.0
0.6
8=8/8
4=8/8
2=
1=1/8
Pretrain Only L2 (t=3.0)
L (E=4)
L= (s=8)
Figure 17: How often does each model empirically attain incremental stability of radius 2 1? We check every a' 2 a where ||a' all2 (Left) Additive smoothing vs. multiplicative smoothing. (Right) ResNet50 with different adversarial training setups vs. their respective MuS-wrapped variants.
25

---

B.7 Discussion
Effect of Smoothing We observe that smoothing can yield non-trivial stability guarantees, espe- cially for Vision Transformer and RoBERTa, as evidenced in Appendix [.1 We see that smoothing least detrimental on these two transformer-based architectures, and most negatively impacts the performance of ResNet50. We conjecture that although different training set-ups may improve performance across every category, this still serves to illustrate the general trend.
Theoretical vs Empirical It is expected that the certifiable radii of stability is more conservative
than what empirically observed. As mentioned in Section 3.2 for each X, there maximum radius to which stability can be guaranteed, which is an inherent limitation of using confidence gaps and Lipschitz constants as the main theoretical technique. We emphasize that the notion of stability need not be tied to smoothing, though we are currently not aware of other viable approaches.
Why these Explanation Methods? We chose SHAP, LIME, IGrad, and VGrad from among the large variety of methods available primarily due to their popularity, and because we believe that they are collectively representative of many techniques. particular, we believe that LIME remains representative baseline for surrogate model-based explanation methods. SHAP and IGrad are, to our knowledge, the two most well-known families of axiomatic feature attribution methods. Finally, we believe that VGrad is representative of traditional gradient saliency-based approach.
Which Explanation Method the Best? Based on our experiments in Appendix B.4 we see that SHAP generally achieves higher accuracy using the same amount of top-k features as other methods. On the other hand, VGrad tends to perform poorly. We remark that there are well-known critiques against the usefulness of saliency-based explanation methods [53].
C Miscellaneous
Relevance to Other Explanation Methods Our key theoretical contribution of MuS in Theorem 3.2 a general-purpose smoothing method that distinct from standard smoothing techniques, namely additive smoothing. Therefore, MuS is applicable to other problem domains beyond what is studied in this paper and would be useful where small Lipschitz constants with respect maskings are desirable.
Broader Impacts Reliable explanations are necessary for making increasingly important as machine learning models are integrated with fields like medicine, law, and business where the primary users may not be well-versed in the technical limitations of different methods. Formal guarantees are thus important for ensuring the predictability and reliability of complex systems, which then allows users to construct accurate mental models of interaction and behavior. In this work, we study particular kind of guarantee known as stability, which is key to feature attribution-ban explanation methods.
decisions and are
26


Reviews:
[{"review_id": "Eh9tdbJSrO", "reviewer": "Reviewer_Qhau", "summary": "This paper studies the stability of binary attributions. The attribution is defined to be stable if the prediction does not change when adding additional features. The multiplicative smoothing is proposed to achieve the Lipschitz condition, which is proved to infer the relaxation of stability. Experiments verify that the smoothing technique is useful for stability.", "questions": "1. I'm interested in the performance comparison of additive smoothing and multiplicative smoothing on the stability setting.", "limitations": "See weakness", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to understand. The problem of attribution stability is novel. \n2. The proposed multiplicative smoothing is effective under the defined stability setting and can be applied to any models.", "weaknesses": "1. For the smoothing technique, my main concern is its application scope, which currently focuses only on binary attribution methods. Although a method is proposed to convert non-binary attributions into binary ones, this conversion process disregards the continuous information in the attribution maps. The potential loss of information during this conversion is significant, especially when dealing with features grouped into 64 patches.\n2. The motivation behind this work can be emphasized further. While it is mentioned that explanations can be fragile, more details are necessary to inform readers about the specific circumstances under which explanations may fail. In order for the stabilty of explanations to be meaningful, classifiers must rely solely on attributions, or more features added on attributions, to make correct decisions. However, it remains unclear why practitioners would opt to use attributions for decision-making when they already have access to the original input data.\n3. The accuracy drop can also be a weakness of the proposed method. While the decrease is expected, a significant decrease in accuracy may suggest a limited usefulness of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their constructive comments. We will include additional exposition, discussion, and examples in our revised manuscript to better motivate our work and clarify our contributions. Furthermore, we have attached a Rebuttal Supplemental document with relevant material.\n\n### Weakness 1: Application scope of binary attributions.\n\nThe Reviewer accurately notes that the continuous-valued case is indeed more general. However, it is also more challenging: it is not clear how to formally specify many explanation-relevant properties, nor how one may achieve such properties. For instance, it is not clear to us how stability-like properties should be formulated for the continuous case. Surprisingly, formal explanation properties of any kind are rarely studied, even in the binary case. We therefore begin with binary attributions as a first step towards explanation stability.\n\nMoreover, we do not aim to introduce novel binary attributions. Rather, our simple binarization schemes are solely intended to show a proof-of-concept that one can certify stability guarantees via existing methods. Importantly, to our knowledge, there do not exist any continuous nor binary attribution methods that explicitly consider our notion of stability. We therefore test MuS with very popular methods (e.g. LIME, SHAP, etc), which all happen to be continuous-valued and are far more well-known than any binary variant.\n\n### Weakness 2a: Classifier must solely rely on attributions.\n\nThe Reviewer's observation is correct. In fact, this highlights an important question: how does one evaluate the \"quality\" of a feature selection? Our choice for quality evaluation is most natural in the context of vision models, wherein revealing parts of an image is analogous to revealing information of the input. If another quality metric were used (e.g. Reference [15]), then our stability definition will no longer apply.\n\n### Weakness 2b: Usefulness of feature attributions.\n\nA major ongoing use case of feature attributions is in the application of machine learning to medicine [1,2,3]. Many such explanation methods are already deployed, but there is often a glaring absence of formal guarantees. This is especially concerning, because such explanations are intended to help medical personnel make critical decisions about patient care. As we cannot expect a general user to understand the technical nuances of ML explanations, it is important that these explanations should be engineered with useful formal guarantees by construction. Our work on explanation stability is a step in this direction.\n\nWe will also include a medical example from Section 1 of the Rebuttal Supplementals. Here, a detector from TorchXRayVision predicts an image to have pneumonia with 25.5% confidence. Suppose a doctor then observes two similar feature selections with dramatically different pneumonia detection confidences (e.g. 29.56% vs 50.05%), they may lose trust in the model and explanation. The objective of our work is to analyze and understand how to prevent such scenarios.\n\n### Weakness 3: Accuracy drop of smoothing.\n\nSince our submission, we have fine-tuned the models for more epochs and obtained better evaluation numerics. An example of one such new improvement is in Section 2 of the Rebuttal Supplementals, in which we rerun the Figure 5 experiments and observe substantial accuracy improvements, especially for ResNet50.\n\nWe will also emphasize that these numbers include heavy noise stress tests (i.e. $\\lambda = 1/16$). This is a higher noise than what is typical in smoothing papers and leads to very small $1/16$-Lipschitz constants.\n\nMoreover, we will include discussion that the relative difference in smoothed classifier accuracy of these experiments are useful in guiding model selection for MuS users. In particular, this experiment demonstrates the relative advantage of transformer-based architectures over CNN-based ones on vision tasks.\n\n### Question 1: Comparison with additive smoothing.\n\nWe thank the Reviewer for suggesting this experiment. Note that classic additive smoothing approaches, which add noise directly to the input, use a radius that is typically too small to cover the deletion of even one feature, so we would not expect it to work well. We verified this in the following experiment similar to Section 4.1, with $L^1$-smoothing noise from distributions as in Reference [21, 27]: \n\nWe use SHAP-top25% and test how often Vision Transformer is incrementally stable with radius $r \\geq 1$ on $\\lambda =  8/8, 4/8, 2/8, 1/8$. We use $N=250$ samples from ImageNet. The numbers are as follows, and are also plotted in Section 3 of the Rebuttal Supplementals:\n\nAdd: 0.184, 0.320, 0.360, 0.156\n\nMuS: 0.716, 0.660, 0.512, 0.364\n\nThis shows that MuS consistently outperforms classic additive smoothing in terms of achieving radius $r \\geq 1$ incremental stability, as expected. We will include this experiment and discussion in our revised manuscript. \n\nWe note that the Reviewer may be also interested in using additive smoothing not in the classical setting, but to directly smooth the $\\alpha$ parameter in the explainable model framework from our paper. However, obtaining stability in this way is not theoretically possible, which is formalized in Proposition 3.1. This is precisely why we had to develop multiplicative smoothing.\n\n### Supplemental References:\n\n[1] A. M. Antoniadi, Y. Du, Y. Guendouz, L. Wei, C. Mazo, B. A. Becker, and C. Mooney. Current Challenges and Future Opportunities for XAI in Machine Learning-Based Clinical Decision Support Systems: A Systematic Review. Applied Sciences, 2021.\n\n[2] W. T. Hrinivich, T. Wang, and C. Wang. Interpretable and explainable machine learning models in oncology. Frontiers in Oncology, 2023.\n\n[3] S. Khedkar, P. Gandi, G. Shinde, and V. Subramanian. Deep Learning and Explainable AI in Healthcare Using EHR. Deep Learning Techniques for Biomedical and Health Informatics, 2020.\n"}, {"review_id": "0NqOjPttyO", "reviewer": "Reviewer_7LaM", "summary": "The draft addresses an important problem of feature attribution method selection and formalizes a notion of attribution stability to do this. The approach is based on modifying classifiers to make them Lipschitz wrt to feature masking. Once done, the new classifier has provable radii of stability defined as L1 distances within which the found sparse explanation is sufficient and adding new features will not change the prediction.\n\nThe approach is tested on vision and NLP tasks with four different explanation methods.\n\nDespite some weaknesses the paper is a good contribution to the field of feature attribution explanations.", "questions": "- typo in the last word of line 44\n- nitpick: logits are usually defined as pre-softmax values, not probabilities (line 71)\n- Figures are not readable in black and white\n", "limitations": "No dedicated Limitations section but limitations mentioned in the text", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- new measurable definition of explanation stability\n- a method to convert any classier into a one that permits the stability calculation\n- theoretical analysis; efficient computation\n- comprehensive empirical evaluation", "weaknesses": "- The need to modify the classifier, before guarantees can be calculated, somewhat diminishes the practical value. In practice, we would be interested in the classifier that actually does the prediction, not a smoothed version of it; as the authors in Sec. 4.1 measured the drop of accuracy from the smoothing to be tens of %s, it could be a no-go for critical classifiers.\n- The proposed stability is operationalized only for binarized explanations and features as image patches, which throws the classifier into the out-of-distribution regime and, on top of smoothing, further complicates drawing conclusions from the approach. In fact all feature attribution methods compared with proposed stability are continuous and require binarization before they can be used.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their positive reception of our paper. We have rerun some experiments under more generous time budgets to improve our experimental results and better address the highlighted weaknesses. We include some of these in the Rebuttal Supplementals, and we address each of the Reviewer's comments below.\n\n### Weakness 1: Need to modify the classifier and weakness of our Figure 5 evaluations.\n\nWe thank the Reviewer for highlighting a need to better discuss this weakness of smoothing methods, especially in the context of our initial experiments in Figure 5. After our submission, we reran a number of our experiments after fine-tuning our models for more epochs and observed substantial performance gains, for instance on experiments of Figure 5 (see Section 2 of Rebuttal Supplementals).\n\nAlthough the new numbers are improved, they do still exhibit similar trends, and we comment on both the old and new numbers here. The Reviewer is correct in pointing out that under greater noise (i.e. $\\lambda = 1/16$) there is non-trivial accuracy degradation. Fortunately, these are much improved in our new experiments. We will revise our discussion to also emphasize that the extreme-noise case is effectively a stress test, as $\\lambda = 1/16$ is more noise than what many smoothing papers consider.\n\nMoreover, we will also include commentary on the fact that one unit of radius in our setting can certify a much greater amount of perturbation to the input than what classical additive smoothing methods can achieve. For instance, we segment 3x224x224 ($n=150528$ features) images into 64 patches, so one unit of radius is then 1/64 of the image. By contrast, many additive smoothing methods struggle to certify more than tens out of the 150k+ features. This difference is largely due to the fact that we are Lipschitz with respect to input feature maskings (which we express as $L^1$-Lipschitz to the $\\alpha$), rather than $L^p$-norm Lipschitz to the input.\n\nIn addition, we have expanded our discussion to state that the experiments of Figure 5 may be used to guide model selection for potential users of MuS. In particular, at least on vision-based problems, Vision Transformer experiences higher smoothed accuracy compared to ResNet50. This shows that transformer-based architectures may be more compatible with MuS than CNN-based models.\n\n### Weakness 2: Focus on binarized explanations.\n\nThe objective of our work is to achieve provable guarantees for feature attributions. To do so, we first focus on the simpler case of binary attributions. Importantly, explanation-relevant guarantees currently do not exist for either continuous-valued or binary attributions. The Reviewer is correct in identifying that the continuous-valued case is more general, however, it is not trivial as to (1) what kind of formal properties should be imposed on continuous-valued attributions, and (2) how one may achieve such properties in a computationally reasonable manner. For instance, it is not clear to us how one should specify properties like stability for continuous-valued attributions. We thus focus on the binary case first.\n\n### Questions: Typos, wording, etc.\n\nWe thank the Reviewer for pointing these out. We have corrected the typo on L44, as well as others that we have found. We have also reworded \"logit\" to \"class probability\" and \"confidence\" where applicable, and we believe that this change also makes the paper more accessible to a non-ML audience while improving its technical clarity. Moreover, we will modify our figures to improve black/white readability where possible. We show in Section 2 of the Rebuttal Supplementals of one such example with different line styles.\n"}, {"review_id": "JlbJcVuQaK", "reviewer": "Reviewer_dPnc", "summary": "This paper presents a technique for extracting feature attributions that are certifiably stable in the sense that the model's predictions are consistent on supersets of attributed features. As the title suggests, the approach is based on multiplicative smoothing, a novel type of Bernoulli smoothing based on masking, rather than perturbing, input features. Notably, the paper shows how to construct a distribution with coordinate-wise Bernoulli features that requires significantly fewer samples to obtain a certificate.", "questions": "1. Were the models used in figures 4 and 5 trained on appropriately augmented data?\n2. Have you attempted to use denoising methods as an intermediate step after sampling from the smoothing distribution?\n3. Are there other existing methods for obtaining Lipschitz models, perhaps without smoothing, that could also work with your certificates?", "limitations": "The paper does not have an explicit limitations section, but these points are discussed where it is appropriate.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work introduces a new type of attribution stability that is not addressed by prior work on robust feature attribution, and presents rigorous yet practical techniques for obtaining stable explanations. \n\nAs the core technique is based on randomized smoothing, it is applicable broadly to different types of models and even different feature attribution methods. Thus, it complements a large body of existing work, and gives concrete, practical ways to improve it with respect to stability.\n\nWhile smoothing-based certification methods are typically very expensive, the structured dependency sampling described in section 3.3 gives a clever way to avoid this, making the approach reasonably inexpensive.\n\nThe empirical results give a sense of what the guarantees look like on real data, and compare several widely-used attribution methods under the certification regime.\n\nThe writing is polished and clear on most of the important points. Overall the paper is an enjoyable read.", "weaknesses": "The accuracy penalty imposed by multiplicative smoothing is large (a related small point: the horizontal axis between figures 4 and 5 isn't the same, making these results a little harder to line up). It doesn't seem that the models were trained with augmentations that match smoothing noise, or that denoising was used on smoothing samples, so there may be opportunities to improve on this. Without improvements, the results in Figure 5 pull somewhat against the practical significance of the work.\n\nThe writing is a bit unclear around the sufficiency of Lipschitzness and masking equivalence. A less-careful read of the paper that focuses more on early sections might come away with the impression that most techniques for obtaining Lipschitz models will suffice for the stability guarantees sketched in remark 2.6. The authors might consider moving some of the intuitions from proposition 3.1 into this discussion.\n\nThe notion of stability at the center of this work is different than what I would have expected, being familiar with some prior work on this topic and reading the abstract. I agree that the model needs to play a central role in characterizing the stability of explanations, but it's less clear that being stable to added features is always an important property. The paper might have wider appeal if the authors are able to justify this, using examples or otherwise (Figure 1 is indeed an example, but doesn't address the question of why the classifier's behavior over the right two images is harmful or undesirable).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their positive impression of our paper and helpful comments on how to improve readability, especially on the notion of masking equivalence and our particular definition of stability. Moreover, since our submission, we have fine-tuned our models for longer and rerun a number of experiments, generally yielding substantially better numerics, especially on ResNet50. We include some examples in the Rebuttal Supplementals, and we respond to each of the Reviewer's comments below.\n\n### Weakness 1 / Question 1: Accuracy penalty and training with augmented data.\n\nAfter our submission, we have had the opportunity to rerun some of our evaluations under more generous time constraints. In particular, the original numbers for Figures 4 and 5 were run with models after only one epoch of fine-tuning on the properly augmented data. Our rerun experiments use models with five epochs of fine-tuning, and we achieve better results, substantially so for ResNet50. We have included some of the new figures in Section 2 of the Rebuttal Supplementals.\n\nIn addition, we have reworked the discussion to better emphasize that the case of $\\lambda = 1/16$ is essentially a stress test since this tends to be more noise than what many smoothing papers employ in their experiments. Notably, because smoothed variants of Vision Transformer tend to outperform the smoothed ResNet50 counterpart, we will include additional discussion of how these experiments can inform model selection for potential users of MuS.\n\n### Weakness 2: Exposition on the sufficiency of Lipschitzness and masking equivalence.\n\nThis is a great suggestion on where to position the presentation on masking equivalence. We will work this into our revised manuscript.\n\n### Weakness 3: \"Non-standard\" notion of stability and its desirability.\n\nThe Reviewer makes an acute observation that the naming of \"stability\" is tricky. Indeed, we considered other possible names (e.g. \"monotone\", \"sufficient\", \"convincing\", \"upwards-consistent\", \"robust\", etc) but each choice came with its own advantages and disadvantages. In the end, we felt that \"stable\" was the most descriptive name that was the least potentially confusing, even though it risks conflation with terminology from adversarial robustness. We will revise the exposition to better distinguish and clarify our definitions.\n\nWe also thank the Reviewer for pointing out that the benefits of stability are not sufficiently well-motivated. We plan to better motivate the need for formal guarantees by using more examples from medicine. In particular, we have constructed an example using chest X-ray images (see Section 1 of Rebuttal Supplementals) to use as a non-trivial example in our Introduction. We believe that this should better motivate readers outside of the ML-explainablity community.\n\n### Question 2: Denoising steps.\n\nWe have not attempted to use denoising methods as an intermediate step. This is a great suggestion and seems like a viable strategy for improving performance. Importantly, however, directly applying additive $L^p$-based denoising methods would not work in our setting, as our multiplicative noise drops features. An appropriate \"denoiser\" in our noising scheme therefore needs to fill in the dropped features via some data imputation method. Investigating such a denoiser is an interesting future direction.\n\n### Question 3: Other methods for obtaining Lipschitz models.\n\nWe are not aware of other methods for obtaining Lipschitz models that conform to our criteria for stability. To our knowledge, our method is the only one among smoothing-based methods. We are not aware of any non-smoothing approaches, but this would be an interesting direction for future research.\n"}, {"review_id": "0mwoIzk1Pe", "reviewer": "Reviewer_JJJj", "summary": "In this paper the authors have introduced a framework to measure the stability of feature attribution methods. They do so by introducing two relaxed notions of stability called incremental stability and descremental stability which check for stability in a neighbourhood of the original feature set. They show that size of these stable neighbourhoods can be measured for lipschitz smooth classification functions and then present a methdology to convert any classified into a Lipschitz smooth classifier using random sampling. Finally they conclude the paper with numerical experiments to illustrate the benefits of their approach. ", "questions": "I think it is important to provide a discussion about what the impact of Mulitplicative smoothening is on the original classifier. \nHow is the stability metric of the smoothened classifier associated to the original classifier. \n", "limitations": "Adequately addressed. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I feel that this paper has several strengths. \nUnderstanding the stability of feature attribution methods is a key requirement to evaluate them. This paper presents a novel and efficient approach to understanding these stability metrics which can then be used to compare quality of the features identified by the different methods. The stabiilty metric makes intuitive sense and the theoretical results justify the measurement techniques for them. They also present a way of how this stability metric can be extended to any classifier. \nOverall, I believe this paper makes a key contribution in this area. \n", "weaknesses": "The metric seems more descriptive than prescriptive. It would be difficult to some how incorporate he metric into the optimization problem so as to guide the network and method towards more stable models and feature attributers. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their time and comments. We will include additional discussion based on these comments, especially regarding how practitioners may apply and train for stability. Moreover, we remark that we have also attached a Rebuttal Supplemental document with additional examples and experiments. Below we address the Reviewer's comments.\n\n### Weaknesses: Descriptive vs prescriptive metric; clarity for practitioners.\n\nThe Reviewer makes a valid point that an optimization problem formulation is useful for practitioners looking to work with MuS and stability. We initially omitted an optimization formulation because we encountered a lot of difficulties in its specification, as any such formulation must consider many problem-dependent nuances, described below. Nevertheless, we believe that the Reviewer makes a strong case for the utility of an optimization formulation, even if in a restricted setting. We will include in the Appendix some formulations and also present discussions about implementation details. Below we further discuss the details and challenges of an optimization formulation for stability.\n\nThe primary challenge with expressing stability metric as an optimization problem is that it is necessarily dependent on both the classifier model and explainer method. As such, any optimization formulation that maximizes stability should simultaneously train both the classifier and explainer. If one decides to parametrize and train the explainer, this opens a Pandora's box of feature attribution design, which is beyond the scope of our paper. If one fixes the explainer and optimizes only the model, then the optimization formulation is easier to write, although this is a more restrictive case as it neglects the explainer design. Nevertheless, we agree that the latter would be useful for practitioners looking to apply MuS, and we will include a model-only formulation in the Appendix.\n\n### Questions: Impact of MuS and relation of stability metric with respect to the original classifier.\n\nWe do not provide any guarantees for the original classifier. Our guarantees are only with respect to the smoothed classifier. Because the original classifier may be an arbitrary $h : \\mathbb{R}^n \\to [0,1]^m$ function, it is challenging to establish any kind of formal guarantees. Only by smoothing the original (\"base\") classifier can we establish any kind of non-trivial guarantees. However, it would be interesting to consider what additional properties we could guarantee if one could assume certain qualities about the original classifier.\n"}, {"review_id": "IltsPxIixZ", "reviewer": "Reviewer_WjBG", "summary": "This paper aims to make the classifier robust to feature removal and addition. The authors find that adding a patch to the mask obtained from explanation method may cause the classifier to make substantially different prediction. They introduce the notion of incremental\nstability and decremental stability to measure classifier's stability w.r.t mask change. They introduce MuS to any base classifier and show that MuS provides stability guarantee for this classifier. ", "questions": "1. Are robust models also sensitive to mask removal or addition?\n2. There are many works discussing robust attributions (e.g., [1], [2]) and establishing the connection between the robustness of explanations and the robustness of black-box models (e.g., [3], [4]). What's the relationship between these works and this paper?\n\n[1] Dombrowski et al., Explanations can be manipulated and geometry is to blame, NeurIPS 2019\n\n[2] Wang et al., Smoothed Geometry for Robust Attribution, NeurIPS 2020\n\n[3] Tan et al., Robust Explanation for Free or At the Cost of Faithfulness, ICML 2023\n\n[4] Agarwal et al., Rethinking Stability for Attribution-based Explanations, ICLR 2022", "limitations": "Listed is Weakness and Questions sections.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The notion of incremental stability and decremental stability is novel. \n2. They motivate multiplicative masking instead of the widely-adopted additive masking by pointing out the inconsistency involved in additive masking. \n3. Certified stability guarantee is obtained. \n4. A sample-efficient algorithm is introduced to reduce the sample complexity to sample from Bernoulli distribution. \n", "weaknesses": "1. Although masks can be sampled efficiently, to get the final prediction, a lot of inference steps are involved. This might be time-consuming. The authors do not talk about how this could be tackled. \n2. MuS seems to be similar with Randomized Smoothing with Bernoulli distribution. By averaging predictions under several masks, the classifier use information from the whole image to make prediction. It is not too surprising that the classifier is more robust to mask change. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the helpful comments, questions, and references. We will include additional exposition and discussion to better clarify our sample complexity, especially relative to other smoothing methods. Moreover, we will include discussions on the listed references, which we believe will help us better clarify our position in the context of ML-explainability literature. Additionally, we have attached a Rebuttal Supplemental with material relevant to our response.\n\n### Weakness 1: Sample efficiency of inference.\n\nThe Reviewer is correct in identifying that requiring multiple model evaluations is a fundamental bottleneck for smoothing methods. We will emphasize in our revisions that our sample efficiency is significant relative to other smoothing methods: we require $<100$ samples to get deterministic guarantees whereas other smoothing methods often require $>10000$ samples to get probabilistic guarantees.\n\n### Weakness 2: Similarity with Randomized Smoothing from Bernoulli Distribution.\n\nThe Reviewer makes a good observation, and in fact, a Bernoulli distribution was one of our intermediate steps when developing MuS. We again emphasize that our formulation of MuS (Theorem 3.2) critically does not require coordinate-wise independence in its distribution (see also above discussion of Weakness 1). The advantage of this over a Bernoulli distribution is that we can then deterministically evaluate the smoothed classifier in $\\ll 2^n$ samples via the construction in Section 3.3 (inspired from Reference [27]).\n\nWe agree that for image classifiers especially, it is not surprising that a Bernoulli-like noising should preserve decent accuracy. Indeed our experiments, namely Figure 5, affirm this intuition (see also new version in Section 2 of Rebuttal Supplementals). Because using a Bernoulli distribution seemed so simple, we do not claim novelty on this idea alone, although we could not find other papers that explicitly discuss this. Instead, we only claim novelty on the distribution of Theorem 3.2 in conjunction with the sample-efficient construction in Section 3.3.\n\n### Question 1: Robust model sensitivity to mask addition and removal.\n\nThe Reviewer raises an interesting question, and we have run additional experiments with robust models. In particular, we consider four versions of pre-trained ResNet50 from the \"robustness\" Python package: non-robust (\"base\"), $L^2 (\\varepsilon = 3.0)$, $L^\\infty (\\varepsilon = 4)$, and $L^\\infty (\\varepsilon = 8)$. As we cannot provably certify the stability of non-MuS models, we instead empirically test how often they are able to hit radius $r=1$ of incremental stability with and without using MuS. We use SHAP-top25% for the explanation method and take $N=250$ samples from ImageNet. Our $r=1$ incremental stability rates for the four models are listed below and also included in Section 3 of the Rebuttal Supplementals:\n\nWithout MuS: 0.208, 0.176, 0.180, 0.232\n\nWith MuS: 0.324, 0.432, 0.356, 0.448\n\nWe observe that using MuS uniformly improves the empirical incremental stability rates.\n\n### Question 2: Discussion with robust feature attributions.\n\nWe thank the Reviewer for providing the references, and we will include discussions of these in our revised manuscript. An important difference is that we consider Lipschitz with respect to input maskings (expressed as $L^1$ Lipschitz in $\\alpha$), whereas the listed references focus on adversarial robustness with respect to $L^p$ norms on continuous domains. This means that the domain and metric over which we define Lipschitz smoothness is fundamentally different than that of the listed references. An important consequence is that one unit of radius in our case easily achieves orders of magnitude more coverage on input features than that of the standard $L^p$-robustness case. For instance, in our examples and experiments we partition 3x224x224 images ($n=150528$ features) into 64 patches: one unit of radius in our setting then certifies 1/64 of the total 150k+ features. This is significantly more feature coverage compared to what is typical from $L^p$ smoothing-based methods, which often struggle to certify more than tens out of 150k+ features.\n\nWe emphasize that this coverage improvement is due to our definition of Lipschitz-to-feature-maskings being fundamentally different from Lipschitz-to-$L^p$ norms on continuous spaces. Although $L^p$-robustness can in theory be used to certify properties of feature maskings, the certifiable radius is often too small to be useful. Crucially, our motivation to pursue this feature-masking variant of Lipschitz smoothness, and therefore MuS, is due to the insufficiency of common additive smoothing methods in our setting. This is because additive smoothing methods violate a condition that we call masking equivalence (Proposition 3.1), and therefore make them inadequate for use in the stability analysis of our context.\n"}, {"review_id": "75ES1Rd9YK", "reviewer": "Reviewer_WB7f", "summary": "The paper is about the stability of explanations in the feature attribution setting for image classification tasks. They illustrate that in certain settings, swapping/removing a pixel of an explanation completely changes the classifiers prediction, which is undesired.\n\nThey define what a \"stable\" explanation is formally and introduce Multiplicative Smoothing as a method to obtain these stable explanations. In principle it's multiplying the image with feature attribution masks such that the classifier becomes smooth in the sense that it doesn't suddenly (non-smoothly) change it's prediction from for example cat to goldfish. \n\nExperiments demonstrate the efficacy of MuS. ", "questions": "1. What's smoothness exactly, never got a good intuition what this exactly means.\n2. Don't understand what the experiments do, please explain how and why these experiments demonstrate that MuS is working as intended. \n3. Is it correct to understand that the paper is in some sense looking for the \"minimal\" set up features that explains a class that won't change with some perturbation ? \n\n-----\n\nPost rebuttal: Authors did a good job explaining what's going on, left some feedback for exposition, raised to 6, it's an interesting paper. ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. It's clear what the paper is trying to achieve\n2. Solution proposal is simple and thoroughly explained with good theoretical justification.\n", "weaknesses": "1. It's a bit unclear what exactly smoothness refers to, currently it seems to refer to no discontinuous jumps when removing a feature attribution pixel in classification output? \n2. The experiments are a bit unintuitive, needs clarification what's being tested here and why. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their time and comments. We will accordingly update our exposition to better clarify our methods, experiments, and contributions. Below we group some of the Reviewer's comments and questions in our response.\n\n### Weakness 1 / Question 1: Meaning of smoothness.\n\nEach coordinate of our smoothed classifier is $\\lambda$-Lipschitz with respect to the binary attribution $\\alpha$ in the $L^1$ norm. Recall that on binary vectors the $L^1$ metric measures bit flips. We will add an explicit definition of this in Section 2.3, and clarify this in the discussion of Theorem 3.2.\n\nLipschitz smoothness means that whenever we mask/unmask a few features of the input $x$, the change in classifier confidence is provably bounded. In other words: if we fix $x$ and consider two binary attributions $\\alpha$ and $\\alpha'$, the prediction confidences of $f(x \\odot \\alpha)$ and $f(x \\odot \\alpha')$ will be similar provided that $\\alpha$ and $\\alpha'$ do not differ on too many bits.\n\nIf the predicted class of $f(x \\odot \\alpha)$ is substantially more confident than the second-best class, then using any other sufficiently similar binary attribution $\\alpha'$ will induce the same class. That is, $f(x \\odot \\alpha)$ and $f(x \\odot \\alpha')$ will provably yield the same class if: (1) there is a sufficient confidence gap between the first-best and second-best class, and (2) if $\\alpha$ and $\\alpha'$ do not differ by too many bit flips. This condition is computationally fast to check if $f$ is Lipschitz smooth, and we use MuS to guarantee Lipschitz smoothness in a sample-efficient and deterministic manner.\n\n### Weakness 2 / Question 2: Clarity of experiments.\n\nWe thank the Reviewer for raising this concern. We will amend our experiments section to better clarify each experiment.\n\n**Experiment 1 (Section 4.1):** This experiment shows that off-the-shelf classifier-explainer pairs can indeed achieve non-trivial stability guarantees. This is a significant result since there did not previously exist any stability-like guarantees for explanations. Moreover, our chosen classifiers and explanation methods were not customized for stability, so it is remarkable that MuS can still prove non-trivial stability in a large number of cases without much custom engineering. As our proposed method is classifier and explainer-agnostic, we do not investigate new model architectures nor explanation methods in this paper, and instead opt to use existing ones to test MuS.\n\n**Experiment 2 (Section 4.2):** This experiment evaluates the accuracy degradation of the smoothed classifier as a function of $\\lambda$. Because smoothing methods inject noise when evaluating the original (\"base\") classifier, it is expected that greater smoothness (i.e. smaller Lipschitz constants) is achieved at a cost to smoothed-classifier accuracy. Much of smoothing literature, ours included, is concerned with navigating this smoothness-accuracy trade-off. Figure 5 (see also Section 2 of Rebuttal Supplementals) shows the certified accuracy curve of different classifiers under different amounts of noise, where the far-left value (in parentheses) is the overall accuracy of the smoothed classifier. In particular, the $\\lambda=1/16$ curve is effectively a stress test of when the smoothed classifier is subject to extreme amounts of noise, higher than what is common in smoothing literature. It is at these extreme noises that one begins to see non-trivial accuracy degradation in the smoothed model.\n\n**Experiment 3 (Section 4.3):** This experiment does not directly evaluate the efficacy of MuS. Rather, it evaluates which of our four chosen feature attribution methods (Vanilla Gradient Saliency, Integrated Gradients, LIME, SHAP) are best suited for achieving certified stability if naively applied. In particular, we interpret higher attribution values to mean more important features, and we iteratively select the next-most-important feature into $\\alpha$ until a stopping condition is achieved (consistency, radius-1 incremental, and decremental stability). The resulting $\\alpha$ is then a proxy for the relative \"efficiency\" or \"density\" (the $k/n$ measure) of our chosen attribution methods. As stability-like guarantees do not exist for either continuous or binary attribution methods, we opted to simply use the most popular ones (which happen to be continuous) as a proof of concept test for efficiency. We remark that the construction of this $\\alpha$ is technically a feature selection method, but we emphasize that this is only intended for crudely testing our four chosen methods.\n\n### Question 3: Objective of paper.\n\nWe believe there is a misunderstanding, and we will revise our exposition to better clarify our story. The focus of our paper is on analyzing and proving guarantees given an explanation. Our goal is not to find a minimal feature selection, nor to present a feature selection algorithm. We are agnostic to the selection method, which we assume is given. We do this because there do not yet exist feature attribution methods with useful explanation-relevant formal guarantees, so it would be premature to overly fixate on any particular one.\n\nWe study binary feature attributions and ask: what properties are desirable, which conditions allow us to provably satisfy these properties, and how can we achieve said conditions? Our desired properties are stability (Definition 2.2), incremental stability (Definition 2.3), and decremental stability (Definition 2.4). Because our notion of stability is hard to show in general, we focus on the latter two: the condition that allows us to provably guarantee incremental/decremental stability is Lipschitz smoothness (Remark 2.6 and Theorem 3.3). We achieve Lipschitz smoothness using MuS (Theorem 3.2). Along with a sample-efficient noise construction in Section 3.3, we present a computationally efficient method for proving when a binary attribution is incrementally/decrementally stable.\n\n"}]

Author rebuttal:
We thank the Reviewers for their time and constructive feedback. The Reviewers have raised many insightful comments and useful suggestions on how to improve the expositional narrative, technical presentation, and experimental evaluations. In addition, the Reviewers have also suggested a number of additional examples and experiments that we believe will help bolster the presentation of our paper. We have attached a Rebuttal Supplemental material that includes a selection of the relevant example and experiment figures.

Meta-review: This paper looks at stability of model predictions around a set of explanatory features, giving a formal notion of a radius of stability which can be achieved if the model is λ-Lipschitz (i.e. the value does not change too fast). They propose a smoothing method, multiplicative smoothing or MuS, which can be applied to any classifier by sampling masks at inference time, and measure the quality of stability guarantees, stability-accuracy tradeoff, and stability around explanations from different methods such as SHAP or gradients.

Reviewers agree that this is a strong paper, appreciating elegant and effective solution to the important problem of explanation stability, as well as the theoretical analysis paired with clear empirical evaluation. There were some concerns about the limitations of the binary-masking formulation, evaluation cost, as well as the accuracy drop caused by the smoothing, and also that the description of Lipschitz-smoothness could be hard to follow - although many of these points were addressed by the rebuttal and two reviewers raised their scores as a result of the discussion.
Decision: Accept (poster)