# Don’t Lie to Me!
Robust and Efficient Explainability with Verified Perturbation Analysis

Thomas Fel1,2,522footnotemark: 2 Melanie Ducoffe2,722footnotemark: 2 David
Vigouroux2,422footnotemark: 2 Rémi Cadène1,3
Mikael Capelle6 Claire Nicodème5 Thomas Serre1,2

1Carney Institute for Brain Science, Brown University, USA
2Artificial and Natural Intelligence Toulouse Institute
3Sorbonne Université, CNRS, France 4IRT Saint-Exupery, France
5Innovation & Research Division, SNCF 6Thales Alenia Space, France
7Airbus AI Research

###### Abstract

A plethora of attribution methods have recently been developed to explain deep
neural networks. These methods use different classes of perturbations (e.g,
occlusion, blurring, masking, etc) to estimate the importance of individual
image pixels to drive a model’s decision. Nevertheless, the space of possible
perturbations is vast and current attribution methods typically require
significant computation time to accurately sample the space in order to
achieve high-quality explanations. In this work, we introduce EVA (Explaining
using Verified Perturbation Analysis) – the first explainability method which
comes with guarantees that an entire set of possible perturbations has been
exhaustively searched. We leverage recent progress in verified perturbation
analysis methods to directly propagate bounds through a neural network to
exhaustively probe a – potentially infinite-size – set of perturbations in a
single forward pass. Our approach takes advantage of the beneficial properties
of verified perturbation analysis, i.e., time efficiency and guaranteed
complete – sampling agnostic – coverage of the perturbation space – to
identify image pixels that drive a model’s decision. We evaluate EVA
systematically and demonstrate state-of-the-art results on multiple
benchmarks. Our code is freely available: github.com/deel-ai/formal-
explainability

Figure 1:  Manifold exploration of current attribution methods. Current
methods assign an importance score to individual pixels using perturbations
around a given input image $\bm{x}$. Saliency [56] uses infinitesimal
perturbations around $\bm{x}$, Occlusion [71] switches individual pixel
intensities on/off. More recent approaches [49, 43, 48, 17, 46] use (Quasi-)
random sampling methods in specific perturbation spaces (occlusion of segments
of pixels, blurring, …). However, the choice of the perturbation space
undoubtedly biases the results – potentially even introducing serious
artifacts [64, 29, 26, 38]. We propose to use verified perturbation analysis
to efficiently perform a complete coverage of a perturbation space around
$\bm{x}$ to produce reliable and faithful explanations.

##  1 Introduction

††footnotetext: Proceedings of the IEEE / CVF Computer Vision and Pattern
Recognition Conference (CVPR), 2023.

Deep neural networks are now being widely deployed in many applications from
medicine, transportation, and security to finance, with broad societal
implications [40]. They are routinely used to making safety-critical decisions
– often without an explanation as their decisions are notoriously hard to
interpret.

Many explainability methods have been proposed to gain insight into how
network models arrive at a particular decision [71, 49, 43, 61, 55, 65, 48,
53, 17, 46, 24]. The applications of these methods are multiple – from helping
to improve or debug their decisions to helping instill confidence in the
reliability of their decisions [14]. Unfortunately, a severe limitation of
these approaches is that they are subject to a confirmation bias: while they
appear to offer useful explanations to a human experimenter, they may produce
incorrect explanations [2, 23, 59]. In other words, just because the
explanations make sense to humans does not mean that they actually convey what
is actually happening within the model. Therefore, the community is actively
seeking for better benchmarks involving humans [29, 45, 12, 37].

In the meantime, it has been shown that some of our current and commonly used
benchmarks are biased and that explainability methods reflect these biases –
ultimately providing the wrong explanation for the behavior of the model [64,
29, 25]. For example, some of the current fidelity metrics [48, 7, 34, 27, 18]
mask one or a few of the input variables (with a fixed value such as a gray
mask) in order to assess how much they contribute to the output of the system.
Trivially, if these variables are already set to the mask value in a given
image (e.g., gray), masking these variables will not yield any effect on the
model’s output and the importance of these variables is poised to be
underestimated. Finally, these methods rely on sampling a space of
perturbations that is far too vast to be fully explored – e.g., LIME on a
image divided in $64$ segments image would need more than $10^{19}$ samples to
test all possible perturbations. As a result, current attribution methods may
be subject to bias and are potentially not entirely reliable.

To address the baseline issue, a growing body of work is starting to leverage
adversarial methods [29, 8, 42, 50, 31] to derive explanations that reflect
the robustness of the model to local adversarial perturbations. Specifically,
a pixel or an image region is considered important if it allows the easy
generation of an adversarial example. That is if a small perturbation of that
pixel or image region yields a large change in the model’s output. This idea
has led to the design of several novel robustness metrics to evaluate the
quality of explanations, such as Robustness-Sr[29]. For a better ranking on
those robustness metrics, several methods have been proposed that make
intensive use of adversarial attacks [29, 70], such as Greedy-AS for
Robustness-Sr. However, these methods are computationally very costly – in
some cases, requiring over 50 000 adversarial attacks per explanation –
severely limiting the widespread adoption of these methods in real-world
scenarios.

In this work, we propose to address this limitation by introducing EVA
(Explaining using Verified perturbation Analysis), a new explainability method
based on robustness analysis. Verified perturbation analysis is a rapidly
growing toolkit of methods to derive bounds on the outputs of neural networks
in the presence of input perturbations. In contrast to current attributions
methods based on gradient estimation or sampling, verified perturbation
analysis allows the full exploration of the perturbation space, see Fig. 1. We
use a tractable certified upper bound of robustness confidence to derive a new
estimator to help quantify the importance of input variables (i.e., those that
matter the most). That is, the variables most likely to change the predictor’s
decision.

We can summarize our main contributions as follows:

  * •

We introduce EVA, the first explainability method guaranteed to explore its
entire set of perturbations using Verified Perturbation Analysis.

  * •

We propose a method to scale EVA to large vision models and show that the
exhaustive exploration of all possible perturbations can be done efficiently.

  * •

We systematically evaluate our approach using several image datasets and show
that it yields convincing results on a large range of explainability metrics

  * •

Finally, we demonstrate that we can use the proposed method to generate class-
specific explanations, and we study the effects of several verified
perturbation analysis methods as a hyperparameter of the generated
explanations.

##  2 Related Work

#### Attribution Methods.

Our approach builds on prior attribution methods in order to explain the
prediction of a deep neural network via the identification of input variables
that support the prediction (typically pixels or image regions for images –
which lead to importance maps shown in Fig. 1). “Saliency” was first
introduced in [4] and consists in using the gradient of a classification
score. It was later refined in [57, 72, 63, 65, 61] in the context of deep
convolutional networks for classification. However, the image gradient only
reflects the model’s operation within an infinitesimal neighborhood around an
input.Hence, it can yield misleading importance estimates [22] since gradients
of the current large vision models are noisy [61]. Other methods rely on
different image perturbations applied to images to produce importance maps
that reflect the corresponding change in classification score resulting from
the perturbation. Methods such as “Occlusion” [72], “LIME” [49], “RISE” [48],
“Sobol” [17] or “HSIC” [46] leverage different sampling strategies to explore
the space of perturbations around the image. For instance, Occlusion uses
binary masks to occlude individual image regions, one at a time. RISE and HSIC
combines these discrete masks to perturb multiple regions simultaneously.
Sobol uses continuous masks for a finer exploration of the perturbation space.

Nevertheless, none of these methods are able to systematically cover the full
space of perturbations. As a result, the corresponding explanations may not
reliably reflect the true importance of pixels. In contrast, our approach
comes with strong guarantees that can be derived from the verified
perturbation analysis framework as it provides bounds on the perturbation
space.

#### Robustness-based Explanation.

To try to address the aforementioned limitations, several groups [32, 33, 60,
29, 8, 42, 19] have focused on the development of a new set of robustness-
based evaluation metrics for trustworthy explanations. These new metrics are
in contrast with the previous ones, which consisted in removing the pixels
considered important in an explanation by substituting them with a fixed
baseline – which inevitably introduces bias and artifacts [29, 64, 26, 38,
25]. Key to these new metrics is the assumption that when the important pixels
are in their nominal (fixed) state, then perturbations applied to the
complementary pixels – deemed unimportant – should not affect the model’s
decision to any great extent. The corollary that follows is that perturbations
limited to the pixels considered important should easily influence the model’s
decision [42, 29]. Going further along the path of robustness, abductive
reasoning was used in [32] to compute optimal subsets with guarantees. The
challenge consists in looking for the subset with the smallest possible
cardinality – to guarantee the decision of the model. This work constituted
one of the early successes of formal methods for explainability, but the
approach was limited to low-dimensional problems and shallow neural networks.
It was later extended to relax the subset minimum explanation by either
providing multiple explanations, aggregating pixels in bundles [6] or by using
local surrogates [9].

Some heuristics-oriented works also propose to optimize these new robustness
based criteria and design new methods using a generative model [47] or
adversarial attacks [29]. The latter approach requires searching for the
existence or lack of an adversarial example for a multitude of $\ell_{p}$
balls around the input of interest. As a result, the induced computational
cost is quite high as the authors used more than $50000$ computations of
adversarial examples to generate a single explanation.

More importantly, a failure to find an adversarial perturbation for a given
radius does not guarantee that none exists. In fact, it is not uncommon for
adversarial attacks to fail to converge – or fail to find an adversarial
example – which will result in a failure to output an importance score. Our
method addresses these issues while drastically reducing the computation cost.
An added benefit of our approach is that verified perturbation analysis
provides additional guarantees and hence opens the doors of certification
which is a necessity for safety-critical applications.

#### Verified Perturbation Analysis.

This growing field of research focuses on the development of methods that
outer-approximate neural network outputs given some input perturbations.
Simply put, for a given input $\bm{x}$ and a bounded perturbation
$\bm{\delta}$, verification methods yield minimum $\underline{\bm{f}}(\bm{x})$
and maximum $\overline{\bm{f}}(\bm{x})$ bounds on the output of a model.
Formally $\forall~{}\bm{\delta}~{}s.t~{}||\bm{\delta}||_{p}\leq\varepsilon$:

$\underline{\bm{f}}(\bm{x})\leq\bm{f}(\bm{x}+\bm{\delta})\leq\overline{\bm{f}}(\bm{x}).$

This allows us to explore the whole perturbation space without having to
explicitly sample points in that space.

Early works focused on computing reachable lower and upper bounds based on
satisfiability modulo theories [36, 16], and mixed-integer linear programming
problems [66]. While these early results were encouraging, the proposed
methods struggled even for small networks and image datasets. More recent work
has led to the independent development of methods for computing looser
certified lower and upper bounds more efficiently thanks to convex linear
relaxations either in the primal or dual space [51]. While looser, those
bounds remain tight enough to yield non-ubiquitous robustness properties on
medium size neural networks. CROWN (hereafter called Backward) uses Linear
Relaxation-based Perturbation Analysis (LiRPA) and achieves the tightest bound
for efficient single neuron linear relaxation [73, 58, 67]. In addition,
linear relaxation methods offer a wide range of possibilities with a vast
trade-off between “tigthness” of the bounds and efficiency. These methods form
two broad classes: ‘forward’ methods which propagate constant bounds (more
generally affine relaxations from the input to the output of the network) also
called Interval Bound Propagation (IBP, Forward, IBP+Forward) vs. ‘backward’
methods which bound the output of the network by affine relaxations given the
internal layers of the network, starting from the output to the input. Note
that these methods can be combined, e.g. (CROWN + IBP + Forward). For a
thorough description of the LiRPA framework and theoretical analysis of the
worst-case complexities of each variant, see [68]. In this work, we remain
purposefully agnostic to the verification method used and opt for the most
accurate LiRPA method applicable to the predictor. Our approach is based on
the formal verification framework DecoMon, based on Keras [15].

##  3 Explainability with Verified Perturbation Analysis

#### Notation.

We consider a standard supervised machine-learning classification setting with
input space $\mathcal{X}\subseteq\mathbb{R}^{d}$, an output space
$\mathcal{Y}\subseteq\mathbb{R}^{c}$, and a predictor function
$\bm{f}:\mathcal{X}\to\mathcal{Y}$ that maps an input vector
$\bm{x}~{}=~{}(x_{1},~{}\ldots{},~{}x_{d})$ to an output
$\bm{f}(\bm{x})~{}=~{}\left(\bm{f}_{1}(\bm{x}),~{}\ldots{},~{}\bm{f}_{c}(\bm{x})\right)$.
We denote
$\mathcal{B}~{}=~{}\\{\bm{\delta}\in\mathbb{R}^{d}~{}:~{}||\bm{\delta}||_{p}\leq\varepsilon\\}$
the perturbation ball with radius $\varepsilon>0$, with
$p\in\\{1,2,\infty\\}$. For any subset of indices
$\bm{u}\subseteq\\{1,~{}\ldots{},~{}d\\}$, we denote $\mathcal{B}_{\bm{u}}$
the ball without perturbation on the variables in $\bm{u}$:
$\mathcal{B}_{\bm{u}}=\\{\bm{\delta}~{}:~{}\bm{\delta}\in\mathcal{B},~{}\bm{\delta}_{\bm{u}}=0\\}$
and $\mathcal{B}(\bm{x})$ the perturbation ball centered on $\bm{x}$. We
denote the lower (resp. upper) bounds obtained with verification perturbation
analysis as
$\underline{\bm{f}}(\bm{x},\mathcal{B})~{}=~{}\left(\underline{\bm{f}}_{1}(\bm{x},\mathcal{B}),~{}\ldots{},~{}\underline{\bm{f}}_{c}(\bm{x},\mathcal{B})\right)$,
and
$\overline{\bm{f}}(\bm{x},\mathcal{B})=\left(\overline{\bm{f}}_{1}(\bm{x},\mathcal{B}),~{}\ldots{},~{}\overline{\bm{f}}_{c}(\bm{x},\mathcal{B})\right)$.
Intuitively, these bounds delimit the output prediction for any perturbed
sample in $\mathcal{B}(\bm{x})$.

###  3.1 The importance of setting the importance right

Different attribution methods implicitly assume different definitions of the
notion of importance for input variables based either on game theory [43], the
notion of conditional expectation of the score logits [48], their variance
[17] or on some measure of statistical dependency between different areas of
an input image and the output of the model [46]. In this work, we build on
robustness-based explainability methods [29] which assume that a variable is
important if small perturbations of this variable lead to large changes in the
model decision. Conversely, a variable is said to be unimportant if changes to
this variable only yield small changes in the model decision. From this
intuitive assertion, we construct an estimator that we call Adversarial
overlap.

###  3.2 Adversarial overlap

We go one step beyond previous work and propose to compute importance by
taking into account not only the ability of individual variables to change the
network’s decision but also its confidence in the prediction. Adversarial
overlap measures the extent to which a modification on a group of pixels can
generate overlap between classes, i.e. generate a point close to $\bm{x}$ such
that the attainable maximum of an unfavorable class $c^{\prime}$ can match the
minimum of the initially predicted class $c$.

Indeed, if a modification of a pixel – or group of pixels – allows generating
a new image that changes the decision of $\bm{f}$, this variable must be
considered important. Conversely, if the decision does not change regardless
of the value of the pixel, then the pixel can be left at its nominal value and
should be considered unimportant.

Among the set of possible variable perturbations $\bm{\delta}$ around a point
$\bm{x}$, we, therefore, look for points that can modify the decision with the
most confidence. Hence our scoring criterion can be formulated as follows:

$\textit{AO}_{c}(\bm{x},\mathcal{B})=\max_{\begin{subarray}{c}\bm{\delta}\in\mathcal{B}\\\
c^{\prime}\neq{}c\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta})-\bm{f}_{c}(\bm{x}+\bm{\delta}).$
(1)

Intuitively, this score represents the confidence of the “best” adversarial
perturbation that can be found in the perturbation ball $\mathcal{B}$ around
$\bm{x}$. Throughout the article, when $c$ is not specified, it is assumed
that $c=\operatorname*{arg\,max}\bm{f}(\bm{x})$.

In order to estimate this criterion, a naive strategy could be to use
adversarial attacks to search within $\mathcal{B}$. However, when they
converge - which is not ensured, such methods only explore certain points of
the considered space, thus giving no guarantee regarding the optimality of the
solution. Moreover, adversarial methods have no guarantee of success and
therefore cannot ensure a valid score under every circumstance. Finally, the
large dimensions of the current datasets make exhaustive searches impossible.

To overcome these issues, we take advantage of one of the main results from
verified perturbation analysis to derive a guaranteed upper bound on the
criterion introduced in Eq. 1. We can upper bound the adversarial overlap
criterion as follows:

$\textit{AO}(\bm{x},\mathcal{B})\leq\overline{\textit{AO}}(\bm{x},\mathcal{B})=\max\limits_{c^{\prime}\neq
c}\overline{\bm{f}}_{c^{\prime}}(\bm{x},\mathcal{B})-\underline{\bm{f}}_{c}(\bm{x},\mathcal{B}).$

The computation of this upper bound becomes tractable using any verified
perturbation analysis method.

For example, $\overline{\textit{AO}}(\bm{x},\mathcal{B})\leq 0$ guarantees
that no adversarial perturbation is possible in the perturbation space.††Note
that with adversarial attacks, failure to find an adversarial example does not
guarantee that it does not exist. Our upper bound
$\overline{\textit{AO}}(\bm{x},\mathcal{B})$ corresponds to the difference
between the verified lower bound of the class of interest $c$ and the maximum
over the verified upper bounds among the other classes. Thus, when important
variables are modified (e.g the head of the dog in Fig. 2, using
${\color[rgb]{0.9921875,0.1171875,0.3828125}\mathcal{B}}$), the lower bound
for the class of interest will get smaller than the upper bound of the
adversary class. On the other hand, this overlap is not possible when
important variables are fixed (e.g in Fig. 2 when the head of the dog is
fixed, using
${\color[rgb]{0.24609375,0.31640625,0.7109375}\mathcal{B}_{\bm{u}}}$). We now
demonstrate how to leverage this score to derive an efficient estimator of
variable importance.

Figure 2:  EVA attribution method. In order to compute the importance for a
group of variables $\bm{u}$ – for instance the dog’s head – the first step (1)
consists in designing the perturbation ball
${\color[rgb]{0.24609375,0.31640625,0.7109375}\mathcal{B}_{\bm{u}}}(\bm{x})$.
This ball is centered in $\bm{x}$ and contain all the possible images
perturbed by
${\color[rgb]{0.24609375,0.31640625,0.7109375}\bm{\delta}}~{}s.t~{}||{\color[rgb]{0.24609375,0.31640625,0.7109375}\bm{\delta}}||_{p}\leq\varepsilon,||{\color[rgb]{0.24609375,0.31640625,0.7109375}\bm{\delta}}_{\bm{u}}||_{p}=0$
which do not perturb the variables
${\color[rgb]{0.24609375,0.31640625,0.7109375}\bm{u}}$. Using verified
perturbation analysis, we then compute the adversarial overlap
$\overline{\textit{AO}}(\bm{x},{\color[rgb]{0.24609375,0.31640625,0.7109375}\mathcal{B}_{\bm{u}}})$
which corresponds to the overlapping between the class $c$ – here dog – and
$c^{\prime}$, the maximum among the other classes. Finally, the importance
score for the variable $\bm{u}$ corresponds to the drop in adversarial overlap
when $\bm{u}$ cannot be perturbed, thus the difference between
$\overline{\textit{AO}}(\bm{x},{\color[rgb]{0.9921875,0.1171875,0.3828125}\mathcal{B}})$
and
$\overline{\textit{AO}}(\bm{x},{\color[rgb]{0.24609375,0.31640625,0.7109375}\mathcal{B}_{\bm{u}}})$.
Specifically, this measures how important the variables $\bm{u}$ are for
changing the model’s decision.

###  3.3 EVA

We are willing to assign a higher importance score for a variable allowing (1)
a change in a decision, (2) a greater adversarial – thus a solid change of
decision. Modifying all variables gives us an idea of the robustness of the
model. In the same way, the modification of all variables without the subset
$\bm{u}$ allows quantifying the change of the strongest adversarial
perturbation and thus quantifies the importance of the variables $\bm{u}$.
Intuitively, if an important variable $\bm{u}$ is discarded, then it will be
more difficult, if not impossible, to succeed in finding any adversarial
perturbation. Specifically, removing the possibility to modify
$\bm{x}_{\bm{u}}$ allows us to reveal its importance by taking into account
its possible interactions.

The complexity of current models means that the variables are not only treated
individually in neural network models but collectively. In order to capture
these higher-order interactions, our method consists in measuring the
adversarial overlap allowed by all the variables together
$\overline{\textit{AO}}(\bm{x},\mathcal{B})$ – thus taking into account their
interactions – and then forbidding to play on a group of variables
$\overline{\textit{AO}}(\bm{x},\mathcal{B}_{\bm{u}})$ to estimate the
importance of $\bm{u}$. Making the interactions of $\bm{u}$ disappear reveals
their importance. Note that several works have mentioned the importance of
taking into account the interactions of the variables when calculating the
importance [48, 17, 20, 30]. Formally, we introduce EVA (Explainability using
Verified perturbation Analysis) that measure the drop in adversarial overlap
when we fixed the variables $\bm{u}$:

$\bm{\text{EVA}}(\bm{x},\bm{u},\mathcal{B})\equiv\overline{\textit{AO}}(\bm{x},\mathcal{B})-\overline{\textit{AO}}(\bm{x},\mathcal{B}_{\bm{u}}).$
(2)

As explained in Fig. 2, the estimator requires two passes of the perturbation
analysis method; one for $\overline{\textit{AO}}(\mathcal{B})$, and the other
for $\overline{\textit{AO}}(\mathcal{B}_{\bm{u}})$: the first term consists in
measuring the adversarial overlap by modifying all the variables, the second
term measures the adversarial surface when fixing the variables of interest
$\bm{u}$. In other words, EVA measures the adversarial overlap that would be
left if the variables $\bm{u}$ were to be fixed.

From a theoretical point of view, we notice that EVA \- under reasonable
assumptions - yield the optimal subset of variables to minimize the
theoretical Robustness-Sr metric (see Theorem C.6). From a computational point
of view, we can note that the first term of the adversarial overlap
$\overline{\textit{AO}}(\bm{x},\mathcal{B})$ – as it does not depend on
$\bm{u}$ – can be calculated once and re-used to evaluate the importance of
any other variables considered. Moreover, contrary to an iterative process
method [21, 29, 32], each importance can be evaluated independently and thus
benefit from the parallelization of modern neural networks. Finally, the
experiments in Section 4 show that even with two calls to
$\overline{\textit{AO}}$ per variables, our method remains much faster than
the one based on sampling or on adversarial attacks (such as Greedy-AS or
Greedy-AO, see appendix B).

In this work, the verified perturbation-based analysis considered is not
always adapted to high dimensional models, especially those running on
ImageNet [13]. We are confident that the verification methods will progress
towards more scalability in the near future, enabling the original version of
EVA on deeper models.

In the meantime, we introduce an empirical method that allows to scale EVA to
high dimensional models. This method sacrifices theoretical guarantees, but
the results section reveals that it may be a good compromise.

Figure 3: Scaling strategy. In order to scale to very large models, we propose
to estimate the bounds of an intermediate layer’s activations empirically by
(1) Sampling $N$ input perturbations and (2) calculating empirical bounds on
the resulting activations for the layer $\bm{h}(\cdot)$. We can then form the
set
${\color[rgb]{0.9921875,0.1171875,0.3828125}\mathcal{P}_{\mathcal{B}}^{\bm{x}}}$
which is a subset of the true bounds
${\color[rgb]{0.24609375,0.31640625,0.7109375}\mathcal{H}_{\mathcal{B}}^{\bm{x}}}$
since the sampling is never exhaustive. We can then plug this set into a
verified perturbation analysis method (3) and continue the forward propagation
of the inputs through the rest of the network.

###  3.4 Scaling to larger models

We propose a second version of EVA, which is a combination of sampling and
verification perturbation analysis. The aim of this hybrid method is twofold:
(i) take advantage of sampling to approach the bounds of an intermediate layer
in a potentially very large model, (ii) then complete only the rest of the
propagations with verified perturbation analysis and thus move towards the
native EVA method which benefits from theoretical guarantees. Note that,
combining verification methods with empirical methods (a.k.a adversarial
training) has notably been proposed in [5] for robust training.

Specifically, our technique consists of splitting the model into two parts,
and (i) estimating the bounds of an intermediate layer using sampling, (ii)
propagating these empirical intermediate bounds onto the second part of the
model with verified perturbation analysis methods.

For the first step (i) we consider the original predictor $\bm{f}$ as a
composition of functions $\bm{f}(\bm{x})=\bm{g}\circ\bm{h}(\bm{x})$. For deep
neural networks, $\bm{h}(\cdot)$ is a function that maps input to an
intermediate feature space and $\bm{g}(\cdot)$ is a function that maps this
same feature space to the classification.

We propose to empirically estimate bounds
$(\underline{\bm{h}}_{\mathcal{B}}^{\bm{x}},\overline{\bm{h}}_{\mathcal{B}}^{\bm{x}})$
for the intermediate activations $\bm{h}(\cdot)\in\mathbb{R}^{d^{\prime}}$
using Monte-Carlo sampling on the perturbation $\bm{\delta}\in\mathcal{B}$.
Formally:

$\begin{split}\forall
j\in[0,\ldots,d^{\prime}],~{}&\underline{\bm{h}}_{\mathcal{B}}^{\bm{x}}[j]=\min\limits_{\bm{\delta}_{1},\ldots\bm{\delta}_{i},\ldots\bm{\delta}_{n}\overset{\mathrm{iid}}{\sim}U(\mathcal{B})}\bm{h}(\bm{x}+\bm{\delta}_{i})[j]\\\
&\overline{\bm{h}}_{\mathcal{B}}^{\bm{x}}[j]=\max\limits_{\bm{\delta}_{1},\ldots\bm{\delta}_{i},\ldots\bm{\delta}_{n}\overset{\mathrm{iid}}{\sim}U(\mathcal{B})}\bm{h}(\bm{x}+\bm{\delta}_{i})[j].\end{split}$

Obviously, since the sampling is never exhaustive, the bounds obtained
underestimate the true maximum
$\overline{\bm{h}}_{\mathcal{B}}^{\bm{x}}\leq\max\bm{h}(\bm{x}+\bm{\delta})$
and overestimates the true minimum
$\underline{\bm{h}}_{\mathcal{B}}^{\bm{x}}\geq\min\bm{h}(\bm{x}+\bm{\delta})$
as illustrated in the Fig. 3. In a similar way, we define
$\underline{\bm{h}}_{\mathcal{B}_{\bm{u}}}^{\bm{x}}$ and
$\overline{\bm{h}}_{\mathcal{B}_{\bm{u}}}^{\bm{x}}$ when
$\bm{\delta}\in\mathcal{B}_{\bm{u}}$. Once the empirical bounds are estimated,
we may proceed to the second step and use the obtained bounds to form the new
perturbation set

$\mathcal{P}^{\bm{x}}_{\mathcal{B}}=[\underline{\bm{h}}_{\mathcal{B}}^{\bm{x}}-\bm{h}(\bm{x}),\overline{\bm{h}}_{\mathcal{B}}^{\bm{x}}-\bm{h}(\bm{x})].$

Intuitively, this set bounds the intermediate activations obtained empirically
and can then be fed to a verified perturbation verification method.

We then carry out the end of the bounds propagation in the usual way, using
verified perturbation analysis. This amounts to computing bounds for the
outputs of the network for all possible activations contained in our empirical
bounds. The only change is that we no longer operate in the pixel space
$\bm{x}$ with the ball $\mathcal{B}$, but in the activation space
$\bm{h}(\cdot)$ with the perturbations set
$\mathcal{P}^{\bm{x}}_{\mathcal{B}}$. The importance score of a set of
variables $\bm{u}$ is then :

$\text{EVA}\textsubscript{hybrid}(\bm{x},\bm{u},\mathcal{B})\equiv\text{EVA}(\bm{h}(\bm{x}),\bm{u},\mathcal{P}^{\bm{x}}_{\mathcal{B}}).$

This hybrid approach allows us to use EVA on state-of-the-art models and thus
to benefit from our method while remaining tractable. We believe this
extension to be a promising step towards robust explanations on deeper
networks.

##  4 Experiments

|  |  | MNIST |  | Cifar-10 |  | ImageNet
---|---|---|---|---|---|---|---
|  |  |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$ |  Time |  |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$ |  Time |  |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$ |  Time
Saliency[56] |  |  |  .193 |  .633 |  .378 |  .071 |  0.04 |  |  .171 |  .172 |  -.021 |  .026 |  0.16 |  |  .057 |  .126 |  .035 |  .769 |  0.36
GradInput[3] |  |  |  .222 |  .611 |  .107 |  .074 |  0.04 |  |  .200 |  .143 |  -.018 |  .095 |  0.17 |  |  .057 |  .050 |  .023 |  .814 |  0.36
SmoothGrad[61] |  |  |  .185 |  .621 |  .331 |  .070 |  1.91 |  |  .174 |  .181 |  .092 |  .048 |  9.07 |  |  .051 |  .069 |  .019 |  .809 |  9.63
VarGrad[54] |  |  |  .207 |  .555 |  .216 |  .077 |  1.76 |  |  .183 |  .211 |  -.012 |  .193 |  9.07 |  |  .098 |  .201 |  .021 |  .787 |  9.62
InteGrad[65] |  |  |  .209 |  .615 |  .108 |  .074 |  1.77 |  |  .194 |  .171 |  -.016 |  .154 |  7.19 |  |  .058 |  .052 |  .023 |  .813 |  8.39
Occlusion[3] |  |  |  .247 |  .545 |  .137 |  .082 |  0.04 |  |  .217 |  .290 |  .105 |  .232 |  1.13 |  |  .100 |  .266 |  .026 |  .821 |  4.97
GradCAM[53] |  |  |  n/a |  n/a |  n/a |  n/a |  n/a |  |  .297 |  .282 |  .056 |  .195 |  0.39 |  |  .073 |  .232 |  .036 |  .817 |  0.18
GradCAM++[10] |  |  |  n/a |  n/a |  n/a |  n/a |  n/a |  |  .270 |  .326 |  .102 |  .094 |  0.39 |  |  .074 |  .285 |  .054 |  .800 |  0.19
RISE[48] |  |  |  .248 |  .558 |  .133 |  .093 |  2.26 |  |  .196 |  .273 |  .157 |  .385 |  20.5 |  |  .074 |  .276 |  .154 |  .818 |  1215
Greedy-AS[29] |  |  |  .260 |  .497 |  .110 |  .061 |  335 |  |  .205 |  .264 |  -.003 |  .013 |  4618 |  |  .088 |  .047 |  .023 |  .612 |  180056
EVA (ours) |  |  |  .089 |  .736 |  .428 |  .069 |  1.29 |  |  .164 |  .290 |  .352 |  .025 |  12.7 |  |  .070 |  .289 |  .048 |  .758 |  6454

Table 1: Results on Deletion (Del.), Insertion (Ins.), $\mu$Fidelity (Fid.)
and Robustness-Sr (Rob.) metrics. Time in seconds corresponds to the
generation of 500 (MNIST/CIFAR-10) and 100 (ImageNet) explanations on an
Nvidia P100. Note that EVA is the only method with guarantees that the entire
set of possible perturbations has been exhaustively searched. Verified
perturbation analysis with IBP + Forward + Backward is used for MNIST, with
Forward only for CIFAR-10 and with our hybrid strategy described in
Section.3.4 for ImageNet. Grad-CAM and Grad-CAM++ are not calculated on the
MNIST dataset since the network only has dense layers. The first and second
best results are in bold and underlined, respectively.

To evaluate the benefits and reliability of our explainability method, we
performed several experiments on a standard dataset, using a set of common
explainability metrics against EVA. In order to test the fidelity of the
explanations produced by our method, we compare them to that of 10 other
explainability methods using the (1) Deletion, (2) Insertion, and (3)
MuFidelity metrics. As it has been shown that these metrics can exhibit
biases, we completed the benchmark by adding the (4) Robustness-Sr metric.
Each score is averaged over 500 samples.

We evaluated these 4 metrics on 3 image classification datasets, namely MNIST
[41], CIFAR-10 [39] and ImageNet [13]. Through these experiments, the
explanations were generated using EVA estimator introduced in Equation 2. The
importance scores were not evaluated pixel-wise but on each cell of the image
after having cut it into a grid of 12 sides (see Fig. 2). For MNIST and
Cifar-10, we used $\varepsilon=0.5$, whereas for ImageNet $\varepsilon=5$.
Concerning the verified perturbation analysis method, we used
(IBP+Forward+Backward) for MNIST, and (IBP+Forward) on Cifar-10 and
$p=\infty$. For computational purposes, we used the hybrid approach introduce
in Section 3.4 for ImageNet using the penultimate layer (FC-4096) as the
intermediate layer $\bm{h}(\cdot)$. We give in Appendix the complete set of
hyperparameters used for the other explainability methods, metrics considered
as well as the architecture of the models used on MNIST and Cifar-10.

###  4.1 Comparison with the state of the art

There is a general consensus that fidelity is a crucial criterion for an
explanation method. That is, if an explanation is used to make a critical
decision, then users are expecting it to reflect the true decision-making
process underlying the model and not just a consensus with humans. Failure to
do so could have disastrous consequences. Pragmatically, these metrics assume
that the more faithful an explanation is, the faster the prediction score
should drop when pixels considered important are changed. In Table 1, we
present the results of the Deletion [48] (or $1-AOPC$ [52]) metric for the
MNIST and Cifar-10 datasets on 500 images sampled from the test set.
TensorFlow [1] and the Keras API [11] were used to run the models and Xplique
[18] for the explainability methods. In order to evaluate the methods, the
metrics require a baseline and several were proposed [64, 29], but we chose to
keep the choice of [29] using their random baseline.

We observe that EVA is the explainability method getting the best Deletion,
Insertion, and $\mu$Fidelity scores on MNIST, and is just behind Greedy-AS on
Robustness-Sr. This can be explained by the fact that the Robustness metric
uses the adversarial attack PGD [44], which is the same one used to generate
Greedy-AS, thus biasing the adversarial search. Indeed, if PGD does not find
an adversarial perturbation using a subset $\bm{u}$ does not give a guarantee
of the robustness of the model, just that the adversarial perturbation could
be difficult to reach with PGD.

For Cifar-10, EVA remains overall the most faithful method according to
Deletion and $\mu$Fidelity, and obtains the second score in Insertion behind
Grad-Cam++ [10]. Finally, we notice that if Greedy-AS [29] allows us to obtain
a good Robustness-Sr score, but this comes with a considerable computation
time, which is not the case of EVA which is much more efficient. Eventually,
EVA is a very good compromise for its relevance to commonly accepted
explainability metrics and more recent robustness metrics.

#### ImageNet

After having demonstrated the potential of the method on vision datasets of
limited size, we consider the case of ImageNet which has a significantly
higher level of dimension. The use of verified perturbation analysis methods
other than IBP is not easily scalable on these datasets. We, therefore, used
the hybrid method introduced in Section 3.4 in order to estimate the bounds in
a latent space and then plug those bounds into the perturbation analysis to
get the final adversarial overlap score.

Table 1 shows the results obtained with the empirical method proposed in
Section 3.4. We observe that even with this relaxed estimation, EVA is able to
score high on all the metrics. Indeed, EVA obtains the best score on the
Insertion metric and ranks second on $\mu$Fidelity and Robustness-Sr. Greedy-
AS ranks first on Robustness-Sr at the expense of the other scores where it
performs poorly. Finally, both RISE and SmoothGrad perform well on all the
fidelity metrics but collapse on the robustness metric. Extending results with
ablations of EVA, including Greedy-AO, are available in Table 3.

Qualitatively, Fig. 5 shows examples of explanations produced on the ImageNet
VGG-16 model. The explanations produced by EVA are more localized than Grad-
CAM or RISE, while being less noisy than the gradient-based or Greedy-AS
methods.

In addition, as the literature on verified perturbation analysis is evolving
rapidly we can conjecture that the advances will benefit the proposed
explainability method. Indeed, EVA proved to be the most effective on the
benchmark when an accurate formal method was used. After demonstrating the
performance of the proposed method, we study its ability to generate class
explanations specific.

###  4.2 Tighter bounds lead to improved explanations

| Tightness$\downarrow$ |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$
---|---|---|---|---|---
IBP | 4.58 |  .148 |  .588 |  .222 |  .077
Forward | 2.66 |  .150 |  .580 |  .209 |  .078
Backward | 2.36 |  .115 |  .607 |  .274 |  .074
IBP + Fo. + Ba. | 1.55 |  .089 |  .736 |  .428 |  .069

Table 2: Impact of the verified perturbation analysis method on EVA. Results
of EVAon Tightness, Deletion (Del.), Insertion (Ins.), Fidelity (Fid.) and
${Robustness\text{-}S\textsubscript{r}}$ (Rob.) metrics obtained on MNIST. The
Tightness score corresponds to the average adversarial surface. A lower
Tightness score indicates that the method is more precise: it reaches tighter
bound, resulting in better explanations and superior scores on the other
metrics. The first and second best results are respectively in bold and
underlined.

The choice of the verified perturbation analysis method is a hyperparameter of
EVA. Hence, it is interesting to see the effect of the choice of this
hyperparameter on the previous benchmark. We recall that only the MNIST
dataset could benefit from the (IBP+Forward+Backward) combo. Table 2 reports
the results of the fidelity metrics using other verified perturbation analysis
methods. We also report a tightness score which corresponds to the average of
the adversarial overlap :
$\mathbb{E}_{\bm{x}\sim\mathcal{X}}(\overline{\textit{AO}}(\bm{x},\mathcal{B}))$.
Specifically, a low score indicates that the verification method is precise,
meaning that the over-approximation is closer to the actual value. It should
be noted that the true value is intractable, but remains the same across all
three tested cases. We observe that the tighter the bounds, the higher the
scores. This allows us to conjecture that the more scalable the formal methods
will become, the better the quality of the generated explanations will be. We
perform additional experiments to ensure that the certified component of EVA
score is significant by comparing EVA to a sampling-based version of EVA. The
details of these experiments are available in Appendix B.

###  4.3 Targeted Explanations

Figure 4: Targeted explanations. Generated explanations for a decision other
than the one predicted by the model. The class explained is indicated at the
bottom of each sample, e.g., the first sample is a ‘4’ and the explanation is
for the class ‘9’. As indicated in section 4.3, the red areas indicate that a
black line should be added and the blue areas that it should be removed. More
examples are available in the Appendix.

In some cases, it is instructive to look at the explanations for unpredicted
classes in order to get information about the internal mechanisms of the
models studied. Such explanations allow us to highlight contrastive features:
elements that should be changed or whose absence is critical. Our method
allows us to obtain such explanations: for a given input, we are then
exclusively interested in the class we are trying to explain, without looking
at the other decisions. Formally, for a given targeted class $c^{\prime}$ the
adversarial overlap (Equation 1) become
$\textit{AO}(\bm{x},\mathcal{B})=\max_{\begin{subarray}{c}\bm{\delta}\in\mathcal{B}\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta})-\bm{f}_{c}(\bm{x}+\bm{\delta})$.
Moreover, by splitting the perturbation ball into a positive one
$\mathcal{B}^{(+)}=\big{\\{}\bm{\delta}\in\mathcal{B}~{}:~{}\bm{\delta}_{i}\geq
0,~{}\forall i\in\\{1,...,d\\}\big{\\}}$ and a negative one
$\mathcal{B}^{(-)}=\big{\\{}\bm{\delta}\in\mathcal{B}~{}:~{}\bm{\delta}_{i}\leq
0,~{}\forall i\in\\{1,...,d\\}\big{\\}}$, one can deduce which direction –
adding or removing the black line in the case of gray-scaled images – will
impact the most the model decision.

We generate targeted explanations on the MNIST dataset using
(IBP+Forward+Backward). For several inputs, we generate the explanation for
the 10 classes. Fig. 7 shows 4 examples of targeted explanations, the target
class $c^{\prime}$ is indicated at the bottom. The red areas indicate that
adding a black line increases the adversarial overlap with the target class.
Conversely, the blue areas indicate where the increase of the score requires
removing black lines. All other results can be found in the Appendix. In
addition to favorable results on the fidelity metrics and guarantees provided
by the verification methods, EVA can provide targeted explanations that are
easily understandable by humans, which are two qualities that make them a
candidate of choice to meet the recent General Data Protection Regulation
(GDPR) adopted in Europe [35]. More examples are available in the Appendix H.

##  5 Conclusion

In this work, we presented the first explainability method that uses
verification perturbation analysis that exhaustively explores the perturbation
space to generate explanations. We presented an efficient estimator that
yields explanations that are state-of-the-art on current metrics. We also
described a simple strategy to scale up perturbation verification methods to
complex models. Finally, we showed that this estimator can be used to form
easily interpretable targeted explanations.

We hope that this work will for searching for safer and more efficient
explanation methods for neural networks – and that it will inspire further
synergies with the field of formal verification.

## References

  * [1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.
  * [2] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim.  Sanity checks for saliency maps.  In Advances in Neural Information Processing Systems (NIPS), 2018\.
  * [3] Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross.  Towards better understanding of gradient-based attribution methods for deep neural networks.  In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
  * [4] David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Robert Müller.  How to explain individual classification decisions.  The Journal of Machine Learning Research, 11:1803–1831, 2010.
  * [5] Mislav Balunovic and Martin Vechev.  Adversarial training and provable defenses: Bridging the gap.  In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
  * [6] Shahaf Bassan and Guy Katz.  Towards formal approximated minimal explanations of neural networks.  arXiv preprint arXiv:2210.13915, 2022.
  * [7] Umang Bhatt, Adrian Weller, and José M. F. Moura.  Evaluating and aggregating feature-based model explanations.  In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2020.
  * [8] Akhilan Boopathy, Sijia Liu, Gaoyuan Zhang, Cynthia Liu, Pin-Yu Chen, Shiyu Chang, and Luca Daniel.  Proper network interpretability helps adversarial robustness in classification.  In Proceedings of the International Conference on Machine Learning (ICML), 2020.
  * [9] Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure, and Karim Tabia.  Asteryx: A model-agnostic sat-based approach for symbolic and score-based explanations.  In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 120–129, 2021.
  * [10] Aditya Chattopadhay, Anirban Sarkar, Prantik Howlader, and Vineeth N Balasubramanian.  Grad-cam++: Generalized gradient-based visual explanations for deep convolutional networks.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2018.
  * [11] François Chollet et al.  Keras.  https://keras.io, 2015.
  * [12] Julien Colin, Thomas Fel, Rémi Cadène, and Thomas Serre.  What i cannot predict, i do not understand: A human-centered evaluation framework for explainability methods.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [13] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A Large-Scale Hierarchical Image Database.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
  * [14] Finale Doshi-Velez and Been Kim.  Towards a rigorous science of interpretable machine learning.  ArXiv e-print, 2017.
  * [15] Ducoffe, Melanie.  Decomon: Automatic certified perturbation analysis of neural networks, 2021.
  * [16] Ruediger Ehlers.  Formal verification of piece-wise linear feed-forward neural networks.  In International Symposium on Automated Technology for Verification and Analysis, pages 269–286. Springer, 2017.
  * [17] Thomas Fel, Remi Cadene, Mathieu Chalvidal, Matthieu Cord, David Vigouroux, and Thomas Serre.  Look at the variance! efficient black-box explanations with sobol-based sensitivity analysis.  In Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [18] Thomas Fel, Lucas Hervier, David Vigouroux, Antonin Poche, Justin Plakoo, Remi Cadene, Mathieu Chalvidal, Julien Colin, Thibaut Boissin, Louis Béthune, Agustin Picard, Claire Nicodeme, Laurent Gardes, Gregory Flandin, and Thomas Serre.  Xplique: A deep learning explainability toolbox.  Workshop, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
  * [19] Thomas Fel and David Vigouroux.  Representativity and consistency measures for deep neural network explanations.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2022.
  * [20] Gabriel Ferrettini, Elodie Escriva, Julien Aligon, Jean-Baptiste Excoffier, and Chantal Soulé-Dupuy.  Coalitional strategies for efficient individual prediction explanation.  Information Systems Frontiers, pages 1–27, 2021.
  * [21] Ruth C. Fong and Andrea Vedaldi.  Interpretable explanations of black boxes by meaningful perturbation.  In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2017.
  * [22] Sahra Ghalebikesabi, Lucile Ter-Minassian, Karla DiazOrdaz, and Chris C Holmes.  On locality of local explanation models.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [23] Amirata Ghorbani, Abubakar Abid, and James Zou.  Interpretation of neural networks is fragile.  In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2017.
  * [24] Mara Graziani, Iam Palatnik de Sousa, Marley MBR Vellasco, Eduardo Costa da Silva, Henning Müller, and Vincent Andrearczyk.  Sharpening local interpretable model-agnostic explanations for histopathology: improved understandability and reliability.  In Medical Image Computing and Computer Assisted Intervention (MICCAI). Springer, 2021.
  * [25] Peter Hase, Harry Xie, and Mohit Bansal.  The out-of-distribution problem in explainability and search methods for feature importance explanations.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [26] Johannes Haug, Stefan Zürn, Peter El-Jiz, and Gjergji Kasneci.  On baselines for local feature attributions.  arXiv preprint arXiv:2101.00905, 2021.
  * [27] Anna Hedström, Leander Weber, Dilyara Bareeva, Franz Motzkus, Wojciech Samek, Sebastian Lapuschkin, and Marina M-C Höhne.  Quantus: an explainable ai toolkit for responsible evaluation of neural network explanations.  The Journal of Machine Learning Research (JMLR), 2022.
  * [28] Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim.  A benchmark for interpretability methods in deep neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [29] Cheng-Yu Hsieh, Chih-Kuan Yeh, Xuanqing Liu, Pradeep Ravikumar, Seungyeon Kim, Sanjiv Kumar, and Cho-Jui Hsieh.  Evaluations and methods for explanation through robustness analysis.  In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
  * [30] Marouane Il Idrissi, Nicolas Bousquet, Fabrice Gamboa, Bertrand Iooss, and Jean-Michel Loubes.  On the coalitional decomposition of parameters of interest, 2023.
  * [31] Marouane Il Idrissi, Vincent Chabridon, and Bertrand Iooss.  Developments and applications of shapley effects to reliability-oriented sensitivity analysis with correlated inputs.  Environmental Modelling & Software, 2021.
  * [32] Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva.  Abduction-based explanations for machine learning models.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [33] Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva.  On relating explanations and adversarial examples.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [34] Alon Jacovi and Yoav Goldberg.  Towards faithfully interpretable nlp systems: How should we define and evaluate faithfulness?  Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL Short Papers), 2020.
  * [35] Margot E Kaminski.  The right to explanation, explained.  In Research Handbook on Information Law and Governance. Edward Elgar Publishing, 2021.
  * [36] Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer.  Reluplex: An efficient smt solver for verifying deep neural networks.  In International Conference on Computer Aided Verification, pages 97–117. Springer, 2017.
  * [37] Sunnie S. Y. Kim, Nicole Meister, Vikram V. Ramaswamy, Ruth Fong, and Olga Russakovsky.  HIVE: Evaluating the human interpretability of visual explanations.  In Proceedings of the IEEE European Conference on Computer Vision (ECCV), 2022.
  * [38] 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.  2019\.
  * [39] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images, 2009.
  * [40] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  Nature, 2015.
  * [41] Yann LeCun and Corinna Cortes.  MNIST handwritten digit database, 2010.
  * [42] Zhong Qiu Lin, Mohammad Javad Shafiee, Stanislav Bochkarev, Michael St Jules, Xiao Yu Wang, and Alexander Wong.  Do explanations reflect decisions? a machine-centric strategy to quantify the performance of explainability algorithms.  In Advances in Neural Information Processing Systems (NIPS), 2019\.
  * [43] Scott Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In Advances in Neural Information Processing Systems (NIPS), 2017\.
  * [44] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  Proceedings of the International Conference on Learning Representations (ICLR), 2018.
  * [45] Giang Nguyen, Daeyoung Kim, and Anh Nguyen.  The effectiveness of feature attribution methods and its correlation with automatic evaluation scores.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [46] Paul Novello, Thomas Fel, and David Vigouroux.  Making sense of dependence: Efficient black-box explanations using dependence measure.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [47] Matthew O’Shaughnessy, Gregory Canal, Marissa Connor, Mark Davenport, and Christopher Rozell.  Generative causal explanations of black-box classifiers.  In Advances in Neural Information Processing Systems (NeurIPS), 2020\.
  * [48] Vitali Petsiuk, Abir Das, and Kate Saenko.  Rise: Randomized input sampling for explanation of black-box models.  In Proceedings of the British Machine Vision Conference (BMVC), 2018\.
  * [49] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  ”why should i trust you?”: Explaining the predictions of any classifier.  In Knowledge Discovery and Data Mining (KDD), 2016.
  * [50] Alexis Ross, Himabindu Lakkaraju, and Osbert Bastani.  Learning models for actionable recourse.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [51] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang.  A convex relaxation barrier to tight robustness verification of neural networks.  Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [52] Wojciech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus-Robert Müller.  Evaluating the visualization of what a deep neural network has learned.  IEEE transactions on neural networks and learning systems, 2016\.
  * [53] 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 (ICCV), 2017.
  * [54] Junghoon Seo, Jeongyeol Choe, Jamyoung Koo, Seunghyeon Jeon, Beomsu Kim, and Taegyun Jeon.  Noise-adding methods of saliency map as series of higher order partial derivative.  In Workshop on Human Interpretability in Machine Learning, Proceedings of the International Conference on Machine Learning (ICML), 2018\.
  * [55] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje.  Learning important features through propagating activation differences.  In Proceedings of the International Conference on Machine Learning (ICML), 2017.
  * [56] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  In Workshop, Proceedings of the International Conference on Learning Representations (ICLR), 2013.
  * [57] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  In Workshop Proceedings of the International Conference on Learning Representations (ICLR), 2014.
  * [58] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev.  An abstract domain for certifying neural networks.  Proceedings of the ACM on Programming Languages, 2019.
  * [59] Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh.  Counterfactual explanations can be manipulated.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [60] Dylan Slack, Anna Hilgard, Sameer Singh, and Himabindu Lakkaraju.  Reliable post hoc explanations: Modeling uncertainty in explainability.  Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
  * [61] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  In Workshop on Visualization for Deep Learning, Proceedings of the International Conference on Machine Learning (ICML), 2017.
  * [62] Matthew Sotoudeh and Aditya V. Thakur.  Computing linear restrictions of neural networks.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [63] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller.  Striving for simplicity: The all convolutional net.  In Workshop Proceedings of the International Conference on Learning Representations (ICLR), 2014.
  * [64] Pascal Sturmfels, Scott Lundberg, and Su-In Lee.  Visualizing the impact of feature attribution baselines.  Distill, 2020.
  * [65] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In Proceedings of the International Conference on Machine Learning (ICML), 2017.
  * [66] Vincent Tjeng and Russ Tedrake.  Verifying neural networks with mixed integer programming.  Proceedings of the International Conference on Learning Representations (ICLR), 15, 2019.
  * [67] Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter.  Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification.  Advances in Neural Information Processing Systems (NeurIPS), 2021\.
  * [68] Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh.  Automatic perturbation analysis for scalable certified robustness and beyond.  Advances in Neural Information Processing Systems (NeurIPS), 2020\.
  * [69] Chih-Kuan Yeh, Cheng-Yu Hsieh, Arun Sai Suggala, David I. Inouye, and Pradeep Ravikumar.  On the (in)fidelity and sensitivity for explanations.  In Advances in Neural Information Processing Systems (NeurIPS), 2019\.
  * [70] Fan Yin, Zhouxing Shi, Cho-Jui Hsieh, and Kai-Wei Chang.  On the sensitivity and stability of model interpretations in nlp.  In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2631–2647, 2022.
  * [71] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In Proceedings of the IEEE European Conference on Computer Vision (ECCV), 2014.
  * [72] Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks.  In Proceedings of the IEEE European Conference on Computer Vision (ECCV), 2014.
  * [73] Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel.  Efficient neural network robustness certification with general activation functions.  Advances in Neural Information Processing Systems (NeurIPS), 2018\.

##  Appendix A Qualitative comparison

Regarding the visual consistency of our method, Figure 5 shows a side-by-side
comparison between our method and the attribution methods tested in our
benchmark. To allow better visualization, the gradient-based methods were 2
percentile clipped.

Figure 5: Qualitative comparison with other attribution methods. To allow for
better visualization, the gradient-based methods (Saliency, Gradient-Input,
SmoothGrad, Integrated-Gradient, VarGrad) are clipped at the 2nd percentile.
For more results and details on each method and choice of hyperparameters, see
Appendix.

##  Appendix B Ablation studies

|  |  | MNIST |  | Cifar-10 |  | ImageNet
---|---|---|---|---|---|---|---
|  |  |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$ |  Time |  |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$ |  Time |  |  Del.$\downarrow$ |  Ins.$\uparrow$ |  Fid.$\uparrow$ |  Rob.$\downarrow$ |  Time
Greedy-AS[29] |  |  |  .260 |  .497 |  .110 |  .061 |  335 |  |  .205 |  .264 |  -.003 |  .013 |  4618 |  |  .088 |  .047 |  .023 |  .612 |  180056
Greedy-AO |  |  |  .237 |  .572 |  .244 |  .063 |  290 |  |  .162 |  .283 |  .041 |  .024 |  2874 |  |  .086 |  .050 |  .023 |  .752 |  26762
EVAemp |  |  |  .101 |  .621 |  .378 |  .067 |  14.4 |  |  .184 |  .270 |  .397 |  .022 |  186.6 |  |  .070 |  .289 |  .048 |  .758 |  6454
EVA (ours) |  |  |  .089 |  .736 |  .428 |  .069 |  1.29 |  |  .164 |  .290 |  .352 |  .025 |  12.7 |

Table 3:  Results on Deletion (Del.), Insertion (Ins.), $\mu$Fidelity (Fid.)
and Robustness-Sr (Rob.) metrics. Time in seconds corresponds to the
generation of 100 explanations on an Nvidia P100. Note that EVA is the only
method with guarantees that the entire set of possible perturbations has been
exhaustively searched. Verified perturbation analysis with IBP + Forward +
Backward is used for MNIST, with Forward only for CIFAR-10 and with our hybrid
strategy described in Section.3.4 for ImageNet. Grad-CAM and Grad-CAM++ are
not calculated on the MNIST dataset since the network only has dense layers.
Greedy-AO is the equivalent of Greedy-AS but with the AO estimator. The first
and second best results are in bold and underlined, respectively.

For a more thorough understanding of the impact of the different components
that made EVA - the adversarial overlap and the use of verification tools- we
proposed different ablation versions of EVA which are the following: (i)
Empirical EVA, (ii) GreedyAO which is the equivalent of Greedy-AS but with the
AO estimator. This allow us to perform ablation on the proposed AO estimator.
Results can be found in Table 3.

###  B.1 Empirical EVA.

In this section, we describe the ablation consisting in estimating EVA without
any use of verified perturbation analysis – thus without any guarantees.

A first intuitive approach would be to replace verification perturbation
analysis with adversarial attacks (as used in Greedy-AS [29]); we denote this
approach as Greedy-AO. In addition, we go further with a purely statistical
approach based on a uniform sampling of the domain; we denote this approach
EVAemp.

This estimator proves to be a very good alternative in terms of computation
time but also with respect to the considered metrics as shown in Section 4.
Unfortunately the lack of guarantee makes it not as relevant as EVA. Formally,
it consists in directly estimating empirically AO using $N$ randomly sampled
perturbations.

$\hat{\textit{AO}}(\bm{x},\mathcal{B})=\max_{\begin{subarray}{c}\bm{\delta}_{1},\cdots\bm{\delta}_{i},\cdots\bm{\delta}_{N}\overset{\mathrm{iid}}{\sim}U(\mathcal{B})\\\
c^{\prime}\neq{}c\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta}_{i})-\bm{f}_{c}(\bm{x}+\bm{\delta}_{i}).$
(3)

We then denote accordingly EVAemp which uses $\hat{\textit{AO}}$:

$\text{EVA}\textsubscript{emp}(\bm{x},\bm{u},\mathcal{B})=\hat{\textit{AO}}(\bm{x},\mathcal{B})-\hat{\textit{AO}}(\bm{x},\mathcal{B}_{\bm{u}})$
(4)

##  Appendix C EVA and ${Robustness\text{-}S\textsubscript{r}}$

We show here that the explanations generated by EVA provide an optimal
solution from a certain stage to the ${Robustness\text{-}S\textsubscript{r}}$
metric proposed by [29]. We admit a unique closest adversarial perturbation
$\bm{\delta}^{*}=\min||\bm{\delta}||_{p}:\bm{f}(\bm{x}+\bm{\delta})\neq\bm{f}(\bm{x})$,
and we define $\varepsilon$, the radius of $\mathcal{B}$ as
$\varepsilon=||\bm{\delta}||_{p}$. Note that $||\bm{\delta}||_{p}$ can be
obtained by binary search using the verified perturbation analysis method.

We briefly recall the ${Robustness\text{-}S\textsubscript{r}}$ metric. With
$\bm{x}=(x_{1},...,x_{d})$, the set $\mathcal{U}=\\{1,...,d\\}$, $\bm{u}$ a
subset of $\mathcal{U}$ : $\bm{u}\subseteq\mathcal{U}$ and $\overline{\bm{u}}$
its complementary. Moreover, we denote the minimum distance to an adversarial
example $\varepsilon^{*}_{\bm{u}}$:

$\varepsilon^{*}_{\bm{u}}=\big{\\{}\min||\bm{\delta}||_{p}~{}:~{}\bm{f}(\bm{x}+\bm{\delta})\neq\bm{f}(\bm{x}),\bm{\delta}_{\overline{\bm{u}}}=0\big{\\}}$

The ${Robustness\text{-}S\textsubscript{r}}$ score is the AUC of the curve
formed by the points
$\\{(1,\varepsilon^{*}_{(1)}),...,(d,\varepsilon^{*}_{(d)})\\}$ where
$\varepsilon^{*}_{(k)}$ is the minimum distance to an adversarial example for
the $k$ most important variables. From this, we can deduce that
$||\bm{\delta}^{*}||\leq\varepsilon^{*}_{\bm{u}}$,
$\forall\bm{u}\subseteq\\{1,...,d\\}$.

The goal here is to minimize this score, which means for a number of variables
$|\bm{u}|=k$, finding the set of variables $\bm{u}^{*}$ such that
$\varepsilon^{*}_{\bm{u}}$ is minimal. We call this set the optimal set at
$k$.

######  Definition C.1.

The optimal set at $k$ is the set of variables $\bm{u}^{*}_{k}$ such that

$\bm{u}^{*}_{k}=\underset{\bm{u}\subseteq\mathcal{U},~{}|\bm{u}|=k}{\operatorname*{arg\,min}~{}~{}\varepsilon^{*}_{\bm{u}}}.$

We note that finding the minimum cardinal of a variable to guarantee a
decision is also a standard research problem [32, 33] and is called subset-
minimal explanations.

Intuitively, the optimal set is the combination of variables that allows
finding the closest adversarial example. Thus, minimizing
${Robustness\text{-}S\textsubscript{r}}$ means finding the optimal set
$\bm{u}^{*}$ for each $k$. Note that this set can vary drastically from one
step to another, it is therefore potentially impossible for attribution to
satisfy this optimality criterion at each step. Nevertheless, an optimal set
that is always reached at some step is the one allowing to build
$\bm{\delta}^{*}$. We start by defining the notion of an essential variable
before showing the optimality of $\bm{\delta}^{*}$.

######  Definition C.2.

Given an adversarial perturbation $\bm{\delta}$, we call essentials variables
$\bm{u}$ all variables such that $|\bm{\delta}_{i}|>0,i\in\bm{u}$. Conversely,
we call inessentials variables variables that are not essential.

For example, if $\bm{\delta}^{*}$ has $k$ essential variables, it is reachable
by modifying only $k$ variables. This allows us to characterize the optimal
set at step $k$.

######  Proposition C.3.

Let $\bm{u}$ be the set of essential variables of $\bm{\delta}^{*}$, then
$\bm{u}$ is an optimal set for $k$, with $k\in[\\![|\bm{u}|,d]\\!]$.

###### Proof.

Let $\bm{v}$ be a set such that
$\varepsilon^{*}_{\bm{v}}<\varepsilon^{*}_{\bm{u}}$, then
$\varepsilon^{*}_{\bm{v}}<||\bm{\delta}^{*}||$ which is a contradiction. ∎

Specifically, as soon as we have the variables allowing us to build
$\bm{\delta}^{*}$, then we reach the minimum possible for
${Robustness\text{-}S\textsubscript{r}}$. We will now show that EVA allows us
to reach this in $|\bm{u}|$ steps, with $|\bm{u}|\leq d$ by showing (1) that
$\bm{\delta}^{*}$ essential variables obtain a positive attribution and (2)
that $\bm{\delta}^{*}$ inessential variables obtain a zero attribution.

######  Proposition C.4.

All essential variables $\bm{u}$ w.r.t $\bm{\delta}^{*}$ have a strictly
positive importance score $\text{EVA}(\bm{u})>0$.

###### Proof.

Let us assume that $i$ is essential and $\text{EVA}(i)=0$, then
$\bm{F}(\mathcal{B})=\bm{F}(\mathcal{B}_{i})$ which implies

$\max_{\begin{subarray}{c}\bm{\delta}\in\mathcal{B}\\\
c^{\prime}\neq{}c\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta})-\bm{f}_{c}(\bm{x}+\bm{\delta})=\max_{\begin{subarray}{c}\bm{\delta}^{\prime}\in\mathcal{B}_{i}\\\
c^{\prime}\neq{}c\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta}^{\prime})-\bm{f}_{c}(\bm{x}+\bm{\delta}^{\prime})$

by uniqueness of the adversarial perturbation,
$\bm{\delta}=\bm{\delta}^{\prime}$ which is a contradiction as
$\bm{\delta}^{\prime}\notin\mathcal{B}_{i}$ since
$\bm{\delta}^{\prime}_{i}\neq 0$ by definition of an essential variable. Thus
$x_{i}$ cannot be essential, which is a contradiction. ∎

Essentially, if the variable $i$ is necessary to reach $\bm{\delta}^{*}$, then
removing it prevents the adversarial example from being reached and lowers the
adversarial overlap, giving a strictly positive attribution.

######  Proposition C.5.

All inessential variables $\bm{v}$ w.r.t. $\bm{\delta}^{*}$ have a zero
importance score $\text{EVA}(\bm{v})=0$.

###### Proof.

With $i$ being an inessential variable, then $\bm{\delta}^{*}_{i}=0$. It
follow that $\bm{\delta}^{*}\in\mathcal{B}_{i}\subseteq\mathcal{B}$. Thus

$\displaystyle\bm{F}(\mathcal{B})$
$\displaystyle=\max_{\begin{subarray}{c}\bm{\delta}\in\mathcal{B}\\\
c^{\prime}\neq{}c\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta})-\bm{f}_{c}(\bm{x}+\bm{\delta})$
$\displaystyle=\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta}^{*})-\bm{f}_{c}(\bm{x}+\bm{\delta}^{*})$

as $\bm{\delta}^{*}$ is the unique adversarial perturbation in $\mathcal{B}$,
similarly

$\displaystyle\bm{F}(\mathcal{B}_{i})$
$\displaystyle=\max_{\begin{subarray}{c}\bm{\delta}^{\prime}\in\mathcal{B}\\\
c^{\prime}\neq{}c\end{subarray}}\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta}^{\prime})-\bm{f}_{c}(\bm{x}+\bm{\delta}^{\prime})$
$\displaystyle=\bm{f}_{c^{\prime}}(\bm{x}+\bm{\delta}^{*})-\bm{f}_{c}(\bm{x}+\bm{\delta}^{*})$

thus $\bm{F}(\mathcal{B})=\bm{F}(\mathcal{B}_{i})$ and $\text{EVA}(i)=0$. ∎

Finally, since EVA ranks the essential variables of $\bm{\delta}^{*}$ before
the inessential variables, and since $\bm{\delta}^{*}$ is the optimal set from
the step $|\bm{u}|$ to the last one $d$, then EVA provide the optimal set, at
least from the step $|\bm{u}|$.

######  Theorem C.6.

EVA provide the optimal set from step $|\bm{u}|$ to the last step. With
$\bm{u}$ the essential variables of $\bm{\delta}^{*}$, EVA will rank the
$\bm{u}$ variables first and provide the optimal set from the step $|\bm{u}|$
to the last step.

###### Proof.

Let $\bm{u}$ denote the essential variables of $\bm{\delta}^{*}$ and $\bm{v}$
the inessential variables. Then according to Proposition C.4 and Proposition
C.5, $\forall i\in\bm{u},\forall j\in\bm{v}:\text{EVA}(i)>\text{EVA}(j)$. It
follow that $\bm{u}$ are the most important variables at step $|\bm{u}|$.
Finally, according to Proposition C.3, $\bm{u}$ is the optimal set for $k$,
with $k\in[\\![|\bm{u}|,d]\\!]$. ∎

Figure 6: EVA yield optimal subset of variable from step $|\bm{u}|$.
${Robustness\text{-}S\textsubscript{r}}$ measures the AUC of the distances to
the nearest adversary for the $k$ most important variables. With
$\bm{\delta}^{*}$ the nearest reachable adversarial perturbation around
$\bm{x}$, then EVA yield the optimal set – the variables allowing to reach the
nearest adversarial example for a given cardinality – at least from
$||\bm{u}||\leq d$ step to the last one, $\bm{u}$ being the so-called
essential variables.

##  Appendix D EVA and Stability

Stability is one of the most crucial properties of an explanation. Several
metrics have been proposed [7, 69] and the most common one consists in finding
around a point $\bm{x}$, another point $\bm{z}$ (in a radius $r$) such that
the explanation changes the most according to a given distance between
explanation $d$ and a distance over the inputs $\rho$:

$\textit{Stability}(\bm{x},\bm{g})=\max_{\bm{z}:\rho(\bm{z},\bm{x})\leq
r}d(\bm{g}(\bm{x}),\bm{g}(\bm{z}))$

and $\bm{g}$ an explanation functional. It can be shown that the proposed EVA
estimator is bounded by the stability of the model as well as by the radii
$\varepsilon$ and $r$, $\varepsilon$ being the radius of $\mathcal{B}$ and $r$
the radius of stability. From here, we assume $d$ and $\rho$ are the
$\ell_{2}$ distance.

Let assume that $\bm{f}$ is $L$-lipschitz. We recall that a function $\bm{f}$
is said $L$-lipschitz over $\mathcal{X}$ if and only if
$\forall(\bm{x},\bm{z})\in\mathcal{X}^{2},||\bm{f}(\bm{x})-\bm{f}(\bm{z})||\leq||\bm{x}-\bm{z}||$.

######  Theorem D.1.

EVA has bounded Stability Given a $L$-lipschitz predictor $\bm{f}$,
$\varepsilon$ the radius of $\mathcal{B}$ and $r$ the Stability radius, then

$\textit{Stability}(\bm{x},\text{EVA})\leq 4L(\varepsilon+r)$

###### Proof.

With $c^{\prime}\neq c$ we denote
$\bm{m}(\bm{x})=\bm{f}_{c^{\prime}}(\bm{x})-\bm{f}_{c}(\bm{x})$. We note that
by additivity of the Lipschitz constant $\bm{m}$ is 2$L$-Lipschitz.

$\displaystyle\textit{Stability}(\bm{x},\text{EVA})=\max_{\bm{z}:\rho(\bm{z},\bm{x})\leq
r}||\text{EVA}(\bm{x}),\text{EVA}(\bm{z})||$
$\displaystyle=\max_{\bm{z}:\rho(\bm{z},\bm{x})\leq
r}||\max_{\bm{\delta}}\bm{m}(\bm{x}+\bm{\delta})-\max_{\bm{\delta}_{\bm{u}}}\bm{m}(\bm{x}+\bm{\delta}_{\bm{u}})$
$\displaystyle~{}~{}~{}~{}-\max_{\bm{\delta}}\bm{m}(\bm{z}+\bm{\delta})+\max_{\bm{\delta}_{\bm{u}}}\bm{m}(\bm{z}+\bm{\delta}_{\bm{u}})||$
$\displaystyle\leq\max_{\bm{z}:\rho(\bm{z},\bm{x})\leq
r}||\max_{\bm{\delta}}\bm{m}(\bm{x}+\bm{\delta})-\max_{\bm{\delta}}\bm{m}(\bm{z}+\bm{\delta})||$
$\displaystyle~{}~{}~{}~{}+||\max_{\bm{\delta}_{\bm{u}}}\bm{m}(\bm{z}+\bm{\delta}_{\bm{u}})-\max_{\bm{\delta}_{\bm{u}}}\bm{m}(\bm{x}+\bm{\delta}_{\bm{u}})||$
$\displaystyle=\max_{\bm{\gamma}:||\bm{\gamma}||\leq
r}||\max_{\bm{\delta}}\bm{m}(\bm{x}+\bm{\delta})-\max_{\bm{\delta}}\bm{m}(\bm{x}+\bm{\delta}+\bm{\gamma})||$
$\displaystyle~{}~{}~{}~{}+||\max_{\bm{\delta}_{\bm{u}}}\bm{m}(\bm{x}+\bm{\delta}_{\bm{u}}+\bm{\gamma})-\max_{\bm{\delta}_{\bm{u}}}\bm{m}(\bm{x}+\bm{\delta}_{\bm{u}})||$
$\displaystyle\leq
2L(||\bm{\delta}||+||\bm{\gamma}||)+2L(||\bm{\delta}||+||\bm{\gamma}||)$
$\displaystyle=4L(\varepsilon+r)$

∎

##  Appendix E Attribution methods

In the following section, we give the formulation of the different attribution
methods used in this work. The library used to generate the attribution maps
is Xplique [18]. By simplification of notation, we define $\bm{f}(\bm{x})$ the
logit score (before softmax) for the class of interest (we omit $c$). We
recall that an attribution method provides an importance score for each input
variable $x_{i}$. We will denote the explanation functional mapping an input
of interest $\bm{x}=(x_{1},...,x_{d})\in\mathcal{X}$ as
$\bm{g}:\mathcal{X}\to\mathbb{R}^{d}$.

Saliency [56] is a visualization technique based on the gradient of a class
score relative to the input, indicating in an infinitesimal neighborhood,
which pixels must be modified to most affect the score of the class of
interest.

$\bm{g}(\bm{x})=||\nabla_{\bm{x}}\bm{f}(\bm{x})||$

Gradient $\odot$ Input [55] is based on the gradient of a class score relative
to the input, element-wise with the input, it was introduced to improve the
sharpness of the attribution maps. A theoretical analysis conducted by [3]
showed that Gradient $\odot$ Input is equivalent to $\epsilon$-LRP and
DeepLIFT [55] methods under certain conditions – using a baseline of zero, and
with all biases to zero.

$\bm{g}(\bm{x})=\bm{x}\odot||\nabla_{\bm{x}}\bm{f}(\bm{x})||$

Integrated Gradients [65] consists of summing the gradient values along the
path from a baseline state to the current value. The baseline $\bm{x}_{0}$
used is zero. This integral can be approximated with a set of $m$ points at
regular intervals between the baseline and the point of interest. In order to
approximate from a finite number of steps, we use a Trapezoidal rule and not a
left-Riemann summation, which allows for more accurate results and improved
performance (see [62] for a comparison). For all the experiments $m=100$.

$\bm{g}(\bm{x})=(\bm{x}-\bm{x}_{0})\int_{0}^{1}\nabla_{\bm{x}}\bm{f}(\bm{x}_{0}+\alpha(\bm{x}-\bm{x}_{0})))d\alpha$

SmoothGrad [61] is also a gradient-based explanation method, which, as the
name suggests, averages the gradient at several points corresponding to small
perturbations (drawn i.i.d from an isotropic normal distribution of standard
deviation $\sigma$) around the point of interest. The smoothing effect induced
by the average help reducing the visual noise, and hence improve the
explanations. The attribution is obtained by averaging after sampling $m$
points. For all the experiments, we took $m=100$ and
$\sigma=0.2\times(\bm{x}_{\max}-\bm{x}_{\min})$ where
$(\bm{x}_{\min},\bm{x}_{\max})$ being the input range of the dataset.

$\bm{g}(\bm{x})=\underset{\bm{\delta}\sim\mathcal{N}(0,\bm{I}\sigma)}{\mathbb{E}}(\nabla_{\bm{x}}\bm{f}(\bm{x}+\bm{\delta}))$

VarGrad [28] is similar to SmoothGrad as it employs the same methodology to
construct the attribution maps: using a set of $m$ noisy inputs, it aggregates
the gradients using the variance rather than the mean. For the experiment, $m$
and $\sigma$ are the same as Smoothgrad. Formally:

$\bm{g}(\bm{x})=\underset{\bm{\delta}\sim\mathcal{N}(0,\bm{I}\sigma)}{\mathbb{V}}(\nabla_{\bm{x}}\bm{f}(\bm{x}+\bm{\delta}))$

Grad-CAM [53] can only be used on Convolutional Neural Network (CNN). Thus we
couldn’t use it for the MNIST dataset. The method uses the gradient and the
feature maps $\bm{A}^{k}$ of the last convolution layer. More precisely, to
obtain the localization map for a class, we need to compute the weights
$\alpha_{c}^{k}$ associated to each of the feature map activation
$\bm{A}^{k}$, with $k$ the number of filters and $Z$ the number of features in
each feature map, with
$\alpha_{k}^{c}=\frac{1}{Z}\sum_{i}\sum_{j}\frac{\partial{\bm{f}(\bm{x})}}{\partial\bm{A}^{k}_{ij}}$
and

$\bm{g}=\max(0,\sum_{k}\alpha_{k}^{c}\bm{A}^{k})$

As the size of the explanation depends on the size (width, height) of the last
feature map, a bilinear interpolation is performed in order to find the same
dimensions as the input. For all the experiments, we used the last
convolutional layer of each model to compute the explanation.

Grad-CAM++ (G+) [10] is an extension of Grad-CAM combining the positive
partial derivatives of feature maps of a convolutional layer with a weighted
special class score. The weights $\alpha_{c}^{(k)}$ associated to each feature
map is computed as follow :

$\alpha_{k}^{c}=\sum_{i}\sum_{j}[\frac{\frac{\partial^{2}\bm{f}(\bm{x})}{(\partial\bm{A}_{ij}^{(k)})^{2}}}{2\frac{\partial^{2}\bm{f}(\bm{x})}{(\partial\bm{A}_{ij}^{(k)})^{2}}+\sum_{i}\sum_{j}\bm{A}^{(k)}_{ij}\frac{\partial^{3}\bm{f}(\bm{x})}{(\partial\bm{A}_{ij}^{(k)})^{3}}}]$

Occlusion [71] is a sensitivity method that sweeps a patch that occludes
pixels over the images using a baseline state and use the variations of the
model prediction to deduce critical areas. For all the experiments, we took a
patch size and a patch stride of $\frac{1}{7}$ of the image size. Moreover,
the baseline state $\bm{x}_{0}$ was zero.

$\bm{g}(\bm{x})_{i}=\bm{f}(\bm{x})-\bm{f}(\bm{x}_{[\bm{x}_{i}=0]})$

RISE [48] is a black-box method that consists of probing the model with $N$
randomly masked versions of the input image to deduce the importance of each
pixel using the corresponding outputs. The masks $\bm{m}\sim\mathcal{M}$ are
generated randomly in a subspace of the input space. For all the experiments,
we use a subspace of size $7\times 7$, $N=6000$, and
$\mathbb{E}(\mathcal{M})=0.5$.

$\bm{g}(\bm{x})=\frac{1}{\mathbb{E}(\mathcal{M})N}\sum_{i=0}^{N}\bm{f}(\bm{x}\odot\bm{m}_{i})\bm{m}_{i}$

Greedy-AS [29] is a greedy-like method which aggregates step by step the most
important pixels – the pixels that allow us to obtain the closest possible
adversarial example. Starting from an empty set, we evaluate the importance of
the variables at each step. Formally, with $\bm{u}$ the feature set chosen at
the current step and $\overline{\bm{u}}$ his complement. We define
$b:\mathcal{P}(\overline{\bm{u}})\to\\{0,1\\}^{|\overline{\bm{u}}|}$ a
function which binarizes a sub-set of the unchosen elements. Then, given the
set of selected elements $\bm{u}$, we find the importance of the elements
still not selected, while taking into account their interactions. This amounts
to solving the following regression problem:

$\bm{w}^{t},c^{t}=\operatorname*{arg\,min}\underset{\bm{v}\in\mathcal{P}(\overline{\bm{u}})}{\sum}\big{(}(\bm{w}^{t}b(\bm{v})+c)-v(\bm{u}\cup\bm{v})\big{)}^{2}$

The weights obtained indicate the importance of each variable by taking into
account these interactions. We specify that $v(\cdot)$ is defined here as the
minimization of the distance to the nearest adversarial example using the
variables $\bm{u}\cup\bm{v}$. In the experiments, the minimization of this
objective is approximated using PGD [44] adversarial attacks, a regression
step (computation of $\bm{w^{t}}$) adds $10$% of the variables and $\bm{v}$ is
sampled using 1000 samples from $\mathcal{P}(\bm{u})$. Finally, the variables
added first to get a better score.

##  Appendix F Evaluation

For the purpose of the experiments, three fidelity metrics have been chosen.
For the whole set of metrics, $\bm{f}(\bm{x})$ score is the score after the
softmax of the models.

#### Deletion.

[48] The first metric is Deletion, it consists in measuring the drop in the
score when the important variables are set to a baseline state. Intuitively, a
sharper drop indicates that the explanation method has well-identified the
important variables for the decision. The operation is repeated on the whole
image until all the pixels are at a baseline state. Formally, at step $k$,
with $\bm{u}$ the most important variables according to an attribution method,
the Deletion(k) score is given by:

$\text{Deletion}^{(k)}=\bm{f}(\bm{x}_{[\bm{x}_{\bm{u}}=\bm{x}_{0}]})$

We then measure the AUC of the Deletion scores. For all the experiments, and
as recommended by [29], the baseline state is not fixed but is a value drawn
on a uniform distribution $\bm{x}_{0}\sim\mathcal{U}(0,1)$.

#### Insertion.

[48] Insertion consists in performing the inverse of Deletion, starting with
an image in a baseline state and then progressively adding the most important
variables. Formally, at step $k$, with $\bm{u}$ the most important variables
according to an attribution method, the Insertion(k) score is given by:

$\text{Insertion}^{(k)}=\bm{f}(\bm{x}_{[\bm{x}_{\overline{\bm{u}}}=\bm{x}_{0}]})$

The baseline is the same as for Deletion.

####  $\mu$Fidelity

[7] consists in measuring the correlation between the fall of the score when
variables are put at a baseline state and the importance of these variables.
Formally:

$\mu\text{Fidelity}=\underset{\bm{u}\subseteq\\{1,...,d\\}\atop|\bm{u}|=k}{\operatorname{Corr}}\left(\sum_{i\in\bm{u}}\bm{g}(\bm{x})_{i},\bm{f}(\bm{x})-\bm{f}(\bm{x}_{[\bm{x}_{\bm{u}}=\bm{x}_{0}]})\right)$

For all experiments, $k$ is equal to 20% of the total number of variables and
the baseline is the same as the one used by Deletion.

##  Appendix G Models

The models used were all trained using Tensorflow [1]. For MNIST, the model is
a stacking of 5 dense layers composed of (256, 128, 64, 32, 10) neurons
respectively. It achieves an accuracy score above 98% on the test set.
Concerning the Cifar-10 model, it is composed of 3 Convolutional layers of
(128, 80, 64) filters, a MaxPooling (2, 2), and to Dense layer of (64, 10)
neurons respectively, and achieves 75% of accuracy on the test set. For
ImageNet, we used a pre-trained VGG16 [57].

##  Appendix H Targeted explanations

Figure 7: Targeted Explanations Attribution-generated explanations for a
decision other than the one predicted. Each column represents the class
explained, e.g., the first column looks for an explanation for the class ‘0’
for each of the samples. As indicated in section 4.3, the red areas indicate
that a black line should be added and the blue areas that it should be
removed. More examples are available in the Appendix.

In order to generate targeted explanations, we split the calls to
$\text{EVA}(\cdot,\cdot)$ in two: the first one with ‘positive’ perturbations
from $\mathcal{B}^{(+)}$ (only positive noise), a call with ‘negative’
perturbations from $\mathcal{B}^{(-)}$ (only negative-valued noise) as defined
in Section 4.3.

We then get two explanations, one for positive noise
$\bm{\phi}^{(+)}_{\bm{u}}=\bm{F}_{c}(\mathcal{B}^{(+)}(\bm{x}))-\bm{F}_{c}(\mathcal{B}^{(+)}_{\bm{u}}(\bm{x}))$,
the other for negative noise
$\bm{\phi}^{(-)}_{\bm{u}}=\bm{F}_{c}(\mathcal{B}^{(-)}(\bm{x}))-\bm{F}_{c}(\mathcal{B}^{(-)}_{\bm{u}}(\bm{x}))$.
Intuitively, high importance for $\bm{\phi}^{(+)}_{\bm{u}}$ means that the
model is sensitive to the addition of a white line. Conversely, high
importance for $\bm{\phi}^{(-)}_{\bm{u}}$ means that removing it changes the
decision model. These two explanations being opposed, we construct the final
explanation as
$\bm{\phi}_{\bm{u}}=\bm{\phi}^{(+)}_{\bm{u}}-\bm{\phi}^{(-)}_{\bm{u}}$. More
examples of results are given in Fig. 7.