Stability Guarantees for Feature Attributions with Multiplicative Smoothing

We first present explainable models as a formalism for rigorously studying explanations. Let $\mathcal{X}=\mathbb{R}^{n}$ be the space of inputs, a classifier $f:\mathcal{X}\to[0,1]^{m}$ maps inputs $x\in\mathcal{X}$ to $m$ class probabilities that sum to $1$, where the class of $f(x)\in[0,1]^{m}$ is taken to be the largest coordinate. Similarly, an explanation method $\varphi:\mathcal{X}\to\{0,1\}^{n}$ maps an input $x\in\mathcal{X}$ to an explanation $\varphi(x)\in\{0,1\}^{n}$ that indicates which features are considered explanatory for the prediction $f(x)$. In particular, we may pick and adapt $\varphi$ from among a selection of existing feature attribution methods like LIME [6], SHAP [7], and many others [5, 8, 23, 24, 25], wherein $\varphi$ 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 it makes sense to jointly study the model and explanation method: given a classifier $f$ and explanation method $\varphi$, we call the pairing $\langle f,\varphi\rangle$ an explainable model. Given some $x\in\mathcal{X}$, the explainable model $\langle f,\varphi\rangle$ maps $x$ to both a prediction and explanation. We show this in Figure 2, where $\langle f,\varphi\rangle(x)\in[0,1]^{m}\times\{0,1\}^{n}$ pairs the class probabilities and the feature attribution.

For an input $x\in\mathcal{X}$, we will evaluate the quality of the binary feature attribution $\varphi(x)$ through its masking on $x$. That is, we will study the behavior of $f$ on the masked input $x\odot\varphi(x)\in\mathcal{X}$, where $\odot$ is the element-wise vector product. To do this, we define a notion of prediction equivalence: for two $x,x^{\prime}\in\mathcal{X}$, we write $f(x)\cong f(x^{\prime})$ to mean that $f(x)$ and $f(x^{\prime})$ yield the same class. This allows us to formalize the intuition that an explanation $\varphi(x)$ should recover the prediction of $x$ under $f$.

Evaluating $f$ on $x\odot\varphi(x)$ this way lets us apply the model as-is and therefore avoids the challenge of constructing a 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 $\langle f,\varphi\rangle$ to generate explanations that are stable and concise (i.e. sparse). The former is our central guarantee and is ensured through smoothing. The latter implies that $\varphi(x)$ has few ones entries, and is a desirable property since a good explanation should not contain too much redundant information. However, sparsity is a more difficult property to enforce, as this is contingent on the model having high accuracy with respect to heavily masked inputs. For sparsity, we present a simple heuristic in Section 2.4 and evaluate its effectiveness in Section 4.

Given an explainable model $\langle f,\varphi\rangle$ and some $x\in\mathcal{X}$, stability means that the prediction does not change even if one adds more explanatory features to $\varphi(x)$. For instance, the model-explanation pair in Figure 1 is not stable, as the inclusion of a single feature group (patch) changes the prediction. To formalize this notion of stability, we first introduce a partial ordering: for $\alpha,\alpha^{\prime}\in\{0,1\}^{n}$, we write $\alpha\succeq\alpha^{\prime}$ iff $\alpha_{i}\geq\alpha_{i}^{\prime}$ for all $i=1,\ldots,n$. That is, $\alpha\succeq\alpha^{\prime}$ iff $\alpha$ includes all the features selected by $\alpha^{\prime}$.

Note that the constant explanation $\varphi(x)=\mathbf{1}$, the vector of ones, makes $\langle f,\varphi\rangle$ trivially stable at every $x\in\mathcal{X}$, though this is not a concise explanation. Additionally, stability at $x$ implies consistency at $x$.

Unfortunately, stability is a difficult property to enforce in general, as it requires that $f$ satisfy a 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=\lVert\varphi(x)\rVert_{1}$ is the number of ones in $\varphi(x)$, then there are $2^{n-k}$ possible $\alpha\succeq\varphi(x)$ to check. This large space of possible $\alpha\succeq\varphi(x)$ motivates us to examine instead relaxations of stability. We introduce lower and upper relaxations of stability below.

Incremental stability is the lower relaxation since it considers the case where the mask $\alpha$ has only a few features more than $\varphi(x)$. For instance, if one can probably add up to $r$ features to a masked $x\odot\varphi(x)$ without altering the prediction, then $\langle f,\varphi\rangle$ would be incrementally stable at $x$ with radius $r$. We next introduce the upper relaxation that we call decremental stability.

Decremental stability is a subtractive form of stability, in contrast to the additive nature of incremental stability. Particularly, decremental stability considers the case where $\alpha$ has much more features than $\varphi(x)$. If one can provably remove up to $r$ non-explanatory features from the full $x$ without altering the prediction, then $\langle f,\varphi\rangle$ is decrementally stable at $x$ with radius $r$. Note also that decremental stability necessarily entails consistency of $\langle f,\varphi\rangle$, but for simplicity of definitions, we do not enforce this for incremental stability. Furthermore, observe that for a sufficiently large radius of $r=\lceil(n-\lVert\varphi(x)\rVert_{1})/2\rceil$, incremental and decremental stability together imply stability.

If $f:\mathcal{X}\to[0,1]^{m}$ is Lipschitz with respect to the masking of features, then we can guarantee relaxed stability properties for the explainable model $\langle f,\varphi\rangle$. In particular, we require for all $x\in\mathcal{X}$ that $f(x\odot\alpha)$ is Lipschitz with respect to the mask $\alpha\in\{0,1\}^{n}$. This then allows us to establish our main result (Theorem 3.3), which we preview below in Remark 2.6.

Observe that Lipschitz smoothness is, in fact, a stronger assumption than necessary, as besides $\alpha\succeq\varphi(x)$, it also imposes guarantees on $\alpha\preceq\varphi(x)$. Nevertheless, Lipschitz smoothness is one of the few classes of properties that can be guaranteed and analyzed at scale on arbitrary models [22, 28].

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 a stable explainable model. Let $\psi:\mathcal{X}\to\mathbb{R}^{n}$ be such a continuous-valued method like LIME [6] or SHAP [7], and fix some desired incremental stability radius $r_{\mathrm{inc}}$ and decremental stability radius $r_{\mathrm{dec}}$. Given some $x\in\mathcal{X}$ a simple construction for binary $\varphi(x)\in\{0,1\}^{n}$ is described next.

Note that the above method of constructing $\varphi(x)$ does not impose sparsity guarantees in the way that we may guarantee stability through Lipschitz smoothness. Instead, the ordering from a continuous-valued $\psi(x)$ serves as a greedy heuristic for constructing $\varphi(x)$. We show in Section 4 that some feature attributions (e.g., SHAP [7]) tend to yield sparser selections on average compared to others (e.g., Vanilla Gradient Saliency [5]).

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-\lambda$ by sampling binary masks $s\in\{0,1\}^{n}$ from some distribution $\mathcal{D}$ where each coordinate is distributed as $\mathrm{Pr}[s_{i}=1]=\lambda$. Then define $f$ as:

where $\mathcal{B}(\lambda)$ is the Beronulli distribution with parameter $\lambda\in[0,1]$. We give an overview of evaluating $f(x)$ in Figure 3. Importantly, our main results on smoothness (Theorem 3.2) and stability (Theorem 3.3) hold provided each coordinate of $\mathcal{D}$ is marginally Bernoulli with parameter $\lambda$, and so we avoid fixing a particular choice for now. However, it will be easy to intuit the exposition with $\mathcal{D}=\mathcal{B}^{n}(\lambda)$, the coordinate-wise i.i.d. Bernoulli distribution with parameter $\lambda$.

We can equivalently parametrize $f$ using the mapping $g(x,\alpha)=f(x\odot\alpha)$, where it follows that:

Note that one could have alternatively first defined $g$ and then $f$ due to the identity $g(x,\mathbf{1})=f(x)$. We require that the relationship between $f$ and $g$ follows an identity that we call masking equivalence:

This follows by the definition of $g$, and the relevance to stability is this: if masking equivalence holds, then we can rewrite stability properties involving $f$ in terms of $g$’s second parameter as follows:

where incremental and decremental stability may be analogously defined. This translation is useful, as we will prove that $g$ is $\lambda$-Lipschitz in its second parameter (Theorem 3.2), which then allows us to establish the desired stability properties (Theorem 3.3).

Since many choices are valid, we have not given an explicit construction for $\mathcal{D}$. Rather, so long as each coordinate of $s\sim\mathcal{D}$ obeys $s_{i}\sim\mathcal{B}(\lambda)$ then the Lipschitz properties for $g$ follow. The implication here is that although simple distributions like $\mathcal{B}^{n}(\lambda)$ suffice for $\mathcal{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, 22], 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 $\mathcal{D}_{\mathrm{add}}$ and $\mathcal{D}_{\mathrm{mult}}$ be any two distributions on $\mathbb{R}^{n}$:

Particularly, additive smoothing has counterexamples for masking equivalence.

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 $\alpha$ are changed into non-zero values. This then causes each sample of $h(x\odot\tilde{\alpha})$ within $g(x,\alpha)$ to observe more features of $x$ than it would have been able to otherwise.

Our core technical result is in showing that $f$ as defined in (2) is Lipschitz to the masking of features. We present MuS in terms of $g$, where it is parametric with respect to the distribution $\mathcal{D}$: so long as $\mathcal{D}$ satisfies a coordinate-wise Bernoulli condition, then it is usable with MuS.

The strength of this result is in its weak assumptions. First, the theorem applies to any model $h$ and input $x\in\mathcal{X}$. It further suffices that each coordinate is distributed as $s_{i}\sim\mathcal{B}(\lambda)$, and we emphasize that statistical independence between different $s_{i},s_{j}$ is not assumed. This allows us to construct $\mathcal{D}$ with structured dependence in Section 3.3, such that we may exactly and efficiently evaluate $g(x,\alpha)$ at a sample complexity of $N\ll 2^{n}$. A 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 $\mathcal{B}^{n}(\lambda)$ do satisfy the requirements of Theorem 3.2 — but costs $2^{n}$ samples because of coordinate-wise independence. Whatever choice of $\mathcal{D}$, one can guarantee stability so long as $g$ is Lipschitz in its second argument.

Note that it is only in the case where the radius $\geq 1$ that non-trivial stability guarantees exist. Because each $g_{k}$ has range in $[0,1]$, this means that a Lipschitz constant of $\lambda\leq 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.

We now present $\mathcal{L}_{qv}(\lambda)$, a distribution on $\{0,1\}^{n}$ that allows for efficient and exact evaluation of a MuS-smoothed 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, we use a seed vector $v$, where with an integer quantization parameter $q>1$ there will only exist $q$ distinct choices of $s\sim\mathcal{L}_{qv}(\lambda)$. All the while, we still enforce that any such $s$ is coordinate-wise Bernoulli with $s_{i}\sim\mathcal{B}(\lambda)$. Thus, for a sufficiently small quantization parameter (i.e., $q\ll 2^{n}$), we may tractably enumerate through all $q$ possible choices of $s$ and thereby evaluate a MuS-smoothed model with only $q$ samples.

The seed vector $v$ is the source of our structured coordinate-wise dependence, and the one-dimensional source of randomness $s_{\mathrm{base}}$ is used to generate the $n$-dimensional $s$. Such $s\sim\mathcal{L}_{qv}(\lambda)$ then satisfies the conditions for use in MuS (Theorem 3.2), and this noise allows for an exact evaluation of the smoothed classifier in $q$ samples. We have found $q=64$ to be sufficient in practice and that values as low as $q=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 our experiments.

We study how much radius of consistent and incremental (resp. decremental) stability is achieved, and how often. We take an explainable model $\langle f,\varphi\rangle$ where $f$ is Vision Transformer and $\varphi$ is SHAP with top-25% feature selection. We plot the rate at which a property holds (e.g., consistent and incrementally stable with radius $r$) as 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 $N_{\mathrm{cert}}=2000$ samples from ImageNet1K; on the right we have the empirical radii for $N_{\mathrm{emp}}=250$ samples obtained by applying a standard box attack [33] strategy with $q=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.e., achieves a larger confidence gap. Moreover, our empirical radii often cover up to half of the input, which suggests that our certified analysis is quite conservative.

We next investigate how smoothing impacts the classifier accuracy. As $\lambda$ 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 vs. radius of decremental stability.

We show the results in Figure 5, where the clean accuracy (in parentheses) decreases with $\lambda$ 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-trivial noise from MuS while maintaining high accuracy.

Finally, we explore which feature attribution method is best suited to stability guarantees of explainable model $\langle f,\varphi\rangle$. All four methods $\psi\in\{\text{LIME},\text{SHAP},\text{VGrad},\text{IGrad}\}$ are continuous-valued, for which we samples $N=250$ inputs from each model’s respective dataset. For each input $x$, we use the feature importance ranking generated by $\psi(x)$ to iteratively build $\varphi(x)$ in a greedy manner like in Section 2.4. For some $x$, let $k_{x}=\varphi(x)/n$ be the number fraction of features needed for $\langle f,\varphi\rangle$ to be consistent, incrementally stable with radius $1$, and decrementally stable with radius $1$. We then plot the average $k_{x}$ for different methods at $\lambda\in\{1/8,\ldots,4/8\}$ in Figure 6, where note that SHAP tends to require fewer features to achieve the desired properties, while VGrad tends to require more. However, we do not believe these to be decisive results, as many curves are relatively close, especially for Vision Transformer and ResNet50.