text:
\section{Intuitions and Implementations of Procedures to Find Masking Explanations}\label{sec:procedures-details}

As introduced in \Cref{sec:methods_metrics}, for evaluation we may interest in random binary masks due to its connection to AUC, but in our method for finding masking explanations we only focus on deterministic masks.
Given a network $f$, image $x \in \mathbb{R}^{c\times hw}$ and class $a$, we wish to find a binary mask $M\in\{0,1\}^{hw}$ such that when the part of $x$ on $M$ is superimposed onto a ``distractor'' $\bar{x} \sim \mathcal{X}$ (randomly sampled from the train set) as $\tilde{x} = M  \odot x + (1-M ) \odot \bar{x}$, the output probability of the model $f(\tilde{x},a)$ is high for the class $a$.

As in \Cref{sec:completeness_and_soundness} we compute the average probability assigned to class $a$ over the sampling of the distractor $\bar{x}$, i.e. we are interested in making $\mathbb{E}_{\bar{x}\sim\mathcal{X}}[f(\tilde{x}, a)]$ high.
To avoid the hard problem of optimizing over the hypercube $\{0,1\}^{hw}$, a typical strategy (also employed in prior work) is to relax the domain of $M $ to be $[0,1]^{hw}$. Since we do not wish to learn masks of very large size, a $\ell_1$ norm penalty on $M $ (corresponding to size of the mask), leading to the following natural objective function\footnote{A standard way to maximize probability is to minimize the negative log probability}
\begin{align}
    L(M ) = \mathbb{E}_{\bar{x}\sim\mathcal{X}} \left[-\log(f(M  \odot x + (1-M ) \odot \bar{x}, a ))\right] + \lambda_1 \|M \|_1
\end{align}

However most masking-based methods employ additional ``tricks'' in order to avoid ``artifacts'' in the produced saliency maps, like Total-Variation (TV) penalty \citep{fong2017interpretable} and upsampling of the mask from a lower resolution one \citep{petsiuk2018rise}.
We also employ the same strategy by learning a low-resolution mask at scale $s$, $M \in\mathbb{R}^{hw/s^2}$, to minimize the following
\begin{align}
    L(M) = \mathbb{E}_{\bar{x}\sim\mathcal{X}} \left[-\log(f(M^{\times s} \odot x + (1-M^{\times s}) \odot \bar{x}, a))\right] + \lambda_{TV} TV(M^{\times s}) + \lambda_1 \|M^{\times s}\|_1
\end{align}
where $M^{\times s}\in\mathbb{R}^{hw}$ is obtained by upsampling $M$ by a factor of $s\in\{1,4\}$ via bilinear interpolation.

While the motivation cited for these ``trick'' is to avoid artifacts, it is not clear whether artifacts are a bad thing, since they might be relevant to the net's decision-making. Indeed, we show that while TV penalty or upsampling does produce better looking masks, they lead to a drop in the {\em  completeness metric}.
However we show that adding such tricks leads to significant improvement in the {\em soundness metric,} thus providing a novel justification for the use of such tricks, beyond just the heuristic argument of getting rid of artifacts.
In \Cref{sec:linear} we also provide theoretical justification for why TV penalty can help with soundness, even for the simple case of linear predictors on non-image data.

\looseness-1 We optimize the objective in \Cref{eq:main_obj} by parametrizing $M$ as a sigmoid of real valued weights $W\in\mathbb{R}^{hw/s^2}$, i.e. $M=\sigma(W)$, and run Adam \citep{kingma2014adam} optimizer for 2000 steps with learning rate $0.05$ and by sampling 10 distractor images at every step, for different values of $\lambda_{TV}$ and upsampling factor $s$.

\section{Practical Benefits of Completeness of all labels for Images of Multiple Objects}\label{sec:elezeb}

Images may have multiple plausible labels. \Cref{fig:elezeb} and \Cref{fig:2label} show images where the classifier net gave high probability to  a single label even though multiple objects were present. Our saliency method can produce different and meaningful masks for all labels that are valid. Extending the notion of soundness for multi-label settings is an open question.

In \Cref{fig:elezeb},  images that previously used in \citealt{gu2018understanding} can have both elephants and zebras present, but it may not be always clear from the model output if there is such a case, since the model can be much more confident on one label, e.g., elephant, than one would expect it to be. For this reason, finding masking explanations validating other labels, e.g., zebra, could provide more information on how the model makes the prediction.

We also use the relabeling provided by \citet{beyer2020we} to select ImageNet validation images with two true labels. Our results may be seen in Figure \ref{fig:2label}.

\input{table_fig/elezeb_fig}

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{figures/turtle.png}
	\includegraphics[width=0.6\textwidth]{figures/husky.png}
	\includegraphics[width=0.6\textwidth]{figures/cup.png}
	\caption{Our masks and masks by~\citet{phang2020investigating} for ImageNet images with two ground truth labels. The best-performing CA model in \citet{phang2020investigating} was used. First (leftmost) column depicts original image with original model probabilities for each ground truth class below the image. Next two columns depict our masks with target label below the image. Final two columns depict the masks for~\citet{phang2020investigating}. The masks by~\citet{phang2020investigating} are identical for different labels, and contains both classes. In contrast, our method outputs descent masks for each class accordingly.  }
	\label{fig:2label}
\end{figure}

\iffalse
\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{elephant-zebra.png}
	\caption{Images containing both elephant(s) and zebra(s), and the corresponding masked ones generated by our method and the best-performing CA model in \citet{phang2020investigating}. The masks by \citet{phang2020investigating} are identical for different labels, and contains both elephant and zebra. In contrast, our method outputs descent masks for elephant and zebra accordingly.  }
	\label{fig:elezeb}
\end{figure}
\fi

\section{Additional Results on CIFAR-10 and Imagenette}\label{sec:additionalimagenette}

\input{table_fig/cifar_table}

\input{table_fig/example_masks}

\input{table_fig/example_masks_incorrect}

\input{table_fig/imagenette_c_main}

In this section, we show additional results for CIFAR-10 and Imagenette experiments.
\begin{enumerate}[leftmargin=*]
    \item  In \Cref{tab:tv_consistency_cifar10}, we show the worst case completeness and worst case soundness on CIFAR-10 of our method with different TV penalty $\lambda_{TV}$. To showcase of generality of our definition of base metric, here we use a modified version of AUC metric where we set $s\sim \{0.2\dim(x), \ldots, 0.6\dim(x)\}$ in \Cref{def:AUCmetric}.
    \item We showcase the masks of ten randomly drawn images from Imagenette for different methods in \Cref{fig:example_masks} and \Cref{fig:example_masks_incorrect}. The masks in \Cref{fig:example_masks} is generated for model predictions, while the masks in \Cref{fig:example_masks_incorrect} is generated for incorrect labels. Note there are some wired horizontal lines and shapes for some masks. These are caused by default tie breaking of pixels of masking value 1. We also tried tie breaking according to Centered Gaussian, which does not improve the performance of those methods.

    \item We create a new dataset Imagenette-Corner based on Imagenette, where each image is a random corner of the original image\footnote{On ImageNet or Imagenette, the common way to process image is first resizing it to $256\times 256$ pixels, and then crop the center $224\times 224$ pixels. In Imagenette-Corner, instead of center cropping, we take one of the four $180\times 180$-pixel corners and resize it to $224\times 224$ pixels.}. We show the results on Imagenette-Corner in \Cref{tab:imagenette_c_main}. The results show that the good performance of Centered Gaussian on Imagenette is likely due to the bias of datasets (that objects are centered with high probability). Saliency metric on Imagenette-Corner are the same for most of the methods, likely because of the coarse selection of hyperparameters as in \citet{dabkowski2017real}.
\end{enumerate}

\section{Experimental Details and Additional Experiments}
\label{sec:additionalexpers}
	In this section we expand upon the experiments in \Cref{sec:expers} and complement them with more experiments on the ImageNet, CIFAR-10 and CIFAR-100 datasets.
	For each of the datasets we test the following:
	\begin{itemize}[leftmargin=*]
	    \item {\bf Visualization:} For various values of TV regularization (and upsampling for ImageNet), we visualize the mask and also what part of the image a sparse version of the mask highlights. We do so for masks learned for the correct label and also for the second most probable label as predicted by the model. The common trend is that while TV regularization (and upsampling) make the masks more human interpretable, it also makes it harder to find a good mask for the incorrect label, thus improving soundness.

	    \item {\bf AUC curve:} We plot the output model probability for a masked input as more pixels from the original image are selected. The 4 plots denote replacing remaining pixels with gray pixels or pixels from a random image, and masks to fit the correct or incorrect labels, i.e. most probable and second most probable labels.
	    Again, we find the TV regularization and upsampling help with soundness; i.e. inability to find mask for the second most probable label.
	    For mask $M$, if $\bar{M}(p)$ denotes the discrete mask with top $p$ fraction of the pixels from $M$ picked.
	    We plot $\mathbb{E}_{x} \left[\mathbb{E}_{x'\sim\Gamma}[f(\bar{M}(p)\odot x + (1 - \bar{M}(p)) \odot x', a)]\right]$ v/s $p$, where $\Gamma$ is either a random image or a gray image, and $a$ is either the correct label for $x$ or the second best label.
	    We note that replacing with gray and random image lead to similar looking plots, with the probability estimate of random image being more pessimistic.
	    This justifies the motivation for our procedure that learns a mask to solve a ``harder task'' of random image replacement.

	    \item {\bf Completeness/soundness:} We evaluate the completeness and soundness scores, as defined in \Cref{eq:cs} and \Cref{def:worst_cs}.
	    In particular for any input $x$, we only evaluate the scores for the top model prediction $a$ and the second most probable label $a'$ and report the worst case completeness and soundness for these 2 labels.
	    For all experiments in this section, we use $\epsilon_{1}=0$ and $\epsilon_{2}=0.1$ (from \Cref{eq:cs}).

	    \item {\bf Intrinsic metrics:} We evaluate our masks on other intrinsic metrics from prior work, and compare to baseline saliency methods.
	    Our baselines include Gradient $\odot$ Input \citep{shrikumar2017learning}, Smooth-Grad \citep{smilkov2017smoothgrad}, Real Time Saliency \citep{dabkowski2017real} (for ResNet-50 on ImageNet), and Random indicating a random Gaussian mask as a control. We use Captum \citep{kokhlikyan2020captum} for Gradient $\odot$ Input and Smooth-Grad implementations and the original author code\footnote{\url{https://github.com/PiotrDabkowski/pytorch-saliency}} for Real Time Saliency. When calculating the Saliency Metric (SM) \citep{dabkowski2017real} we tune the threshold $\delta$ on a holdout set of size 100 with $\delta$ between $0$ and $5$ in increments of $0.2$ as in prior work.

	    For the saliency method of \citet{fong2017interpretable} that we only used on the Imagenette, we adapt the most popular implementation on GitHub\footnote{\url{https://github.com/jacobgil/pytorch-explain-black-box}}. The implementation contains minor deviations from the original paper as described on its main page. For \citet{phang2020investigating}, we used their best CA model pretrained and provided in original author code\footnote{\url{https://github.com/zphang/saliency_investigation}}.
	 	\end{itemize}

\subsection{CIFAR-10 Experiments}
\label{subsection:cif10}

\input{table_fig/cif10_auc_fig}

\input{table_fig/cif10_complete_sound_table}

\input{table_fig/cif10_table}

We also run our method from \Cref{sec:procedures} on the CIFAR-10 dataset using a pretrained ResNet-164 architecture\footnote{\url{https://github.com/bearpaw/pytorch-classification}. The ResNet-110 model in this repository is actually a ResNet-164 model.}.
For all experiments we learn a mask $M\in\mathbb{R}^{32\times 32}$, thus using a scaling factor of $s=1$ (no upsampling).
We train masks for 1600 images that were correctly classified by the pretrained ResNet-164 using regularization parameter $\lambda_{TV}\in\{0, 0.001, 0.01, 0.1\}$.
We use a (fixed) L1 regularization value of .001 for all masks.

We visualize the masks learned for the correct label in \Cref{subfig:ciftrue} and in \Cref{subfig:cifsbest} we visualize the same for the second best label predicted by the ResNet-164 model.
We also visualize the masks for all labels for some randomly picked images in \Cref{fig:artifact} to demonstrate the commonness of artifact, especially for the incorrect labels.
The AUC curves in \Cref{fig:cif10_auc} suggest a similar trend to that of Imagenette, adding TV regularization results in only a mild drop in completeness, but significantly improves soundness.
Evaluation of our masks, compared to some gradient baselines, on intrinsic metrics can be found in \Cref{table:cif10}.
We report the completeness and soundness results for CIFAR-10 in Table \ref{table:cif10_complete_sound} for TV values in $(0.0,0.001,0.01,0.1)$ calculated using a ResNet-164 model.

\input{table_fig/cif10_first_fig}

\input{table_fig/artifact_fig}

\subsection{CIFAR-100 Experiments}
\label{subsection:cif100}

\input{table_fig/cif100_auc_fig}

\input{table_fig/cif100_complete_sound_table}

\input{table_fig/cif100_table}

We run the same experiment for CIFAR-100 using the corresponding ResNet\-164 model.
We visualize the masks learned for the correct label in \Cref{subfig:cif100true} and in \Cref{subfig:cif100sbest} we visualize the same for the second best label predicted by the ResNet-164 model.
The AUC curves in \Cref{fig:cif100_auc} suggest a similar trend to that of Imagenette, adding TV regularization results in only a mild drop in completeness, but significantly improves soundness.
Evaluation of our masks, compared to some gradient baselines, on intrinsic metrics can be found in \Cref{table:cif100}. We place a downarrow after the name of the metric to indicate a lower value is considered better and an uparrow when a higher value is considered better. We evaluate on a randomly selected subset of 1600 data points where the model had correct top 1 accuracy.
We report the completeness and soundness results for CIFAR-100 in Table \ref{table:cif100_complete_sound} for TV values in $(0.0,0.001,0.01,0.1)$ calculated using a ResNet-164 model.

\input{table_fig/cif100_first_fig}

\subsection{Experiments on ImageNet}

\label{subsection:rn18ImageNet}
In \Cref{subfig:imgtrue} we depict the the masks for TV values in $\{0.0,0.01\}$ for a ResNet-18 model on ImageNet for the ground truth label and in \Cref{subfig:imgsbest} we depict the same for the second best label. We also experiment with the effect of upsampling (US) the mask, whereby we learn a mask of size (56,56) and upsample to size (224,224). We use a fixed L1 regularization value of 2e-5.
We depict our results on ImageNet and ResNet-18 in \Cref{table:ImageNetResNet-18}

For the deletion metric, we note that most methods have comparable or worse performance than the random mask, which suggests that the metric does not give us much signal about the goodness of the saliency maps.
On the insertion metric, we find that mask learned by not adding the TV penalty significantly beats other methods.
The mask learned using TV penalty, on the other hand, has impressive performance on both the insertion AUC and saliency metric (SM).

\myparagraph{Completeness and Soundness on ImageNet and ResNet-18.} We report our results in \Cref{table:ImageNet_complete_sound} for TV values in $(0, 0.01)$ for both graying (Gray) and replacing with other image pixels (Random image). Additionally, we investigate the effect of upsampling (US) where we derive a (56,56) and upsample by a factor of 4 to a $(224,224)$  mask.

\input{table_fig/imagenet_complete_sound_table}

\input{table_fig/imagenet_rn18_table}

\myparagraph{Effect of ensembling.} In order to investigate the effect of ensembling we plot maps in \Cref{fig:ImageNet_varyk} as we vary the number of maps that are ensembled over as $K \in \{1,2,4\}$, where we learn multiple masks such that each of them individually validate the label, but are as disjoint as possible.
We do not upsample (using a scale of 1.0) and we use a fixed L1 regularization of 2e-5 and a fixed TV regularization of 0.0.

\input{table_fig/imagenet_rn18_fig}

\input{table_fig/imagenet_sanity_fig}

\input{table_fig/imagenet_varyk_fig}

\subsection{Effect on Sanity Checks}
\label{subsec:sanity}
Inspired by \citep{adebayo2018sanity} we randomize the last layer of a ResNet-18 network and visually inspect the resulting saliency maps in Figure \ref{fig:ImageNet_sanity}. We find that the maps appear less coherent than those of a pre-trained model. We use a fixed L1 regularization of 2e-5 and depict maps with and without upsampling (US) at TV values of $(0, 0.01)$.

\section{Additional Background information}
\label{sec:additionalbackground}

	\subsection{Additional related work}
	\label{subsec:missing}
	The pixel replacement strategy we used is closely related to hot deck imputation \citep{rubin1976inference}, where features may be replaced either by using the mean feature value (analogous to replacing with grey) or sampling from the marginal feature distribution (analogous to replacing with image pixels sampled from other training images). Some prior work \citep{carter2019made} has found that mean imputation does not significantly affect model output on the beer aroma review dataset. On Imagenette, by contrast, we found that replacement strategy can matter.

	\myparagraph{Additional saliency evaluation tests.}
	\citet{adebayo2018sanity}
proposed ``sanity checks'' for saliency maps. They note that if a model's weights are randomized, it has not learned anything, and therefore the saliency map should not look coherent. They also randomize the labels of the dataset and argue that the saliency maps for a model trained on this scrambled data should be different than the saliency maps for the model trained on the original data. We study the effect of model layer randomization on our method in Appendix section \ref{subsec:sanity} and find that randomizing the model weights does cause our saliency maps to look incoherent.
\citet{tomsett2020sanity} also discover sanity checks for saliency metrics, finding that saliency evaluation methods can yield inconsistent results. They evaluate saliency maps on reliability, i.e. how consistent the saliency maps are. To measure a method's reliability, because access to ground truth saliency maps are not available, they use three proxies 1) inter-rater reliability, i.e. how whether a saliency evaluation metric is able to consistently rank some saliency methods above others, 2) inter-method reliability, which indicates whether a saliency evaluation metric agrees across different saliency methods, and 3)internal consistency reliability, which measure whether different saliency methods are measuring the same underlying concept. \\
\myparagraph{Saliency axioms.} \citet{sundararajan2017axiomatic} identify two fundamental axioms, Sensitivity (versions a and b), and Implementation Invariance that attribution methods should satisfy.  "An attribution method satisfies Sensitivity(a) if for every input and baseline that differ in one feature but have different predictions then the differing feature should be given a non-zero attribution." The definition of Sensitivity b is "If the function implemented by the deep network does not depend (mathematically) on some variable, then the attribution to that variable is always zero.". Implementation invariance simply states that if two networks are equivalent, the saliency maps for those two networks should be the same. These axioms are not captured by completeness and soundness and are good examples of why completeness and soundness cannot be used alone in evaluating saliency maps. Other prior work \citet{carter2019made} argues that saliency explanations should be minimal \citet{carter2019made} and find sufficient input subsets which are "minimal subsets of features whose observed values alone suffice for the same decision to be reached, even if all other input feature values are missing."

	\subsection{Saliency Methods}
We give a partial list of extant saliency methods here. We broadly categorize explanations into three categories: Back-propagation based explanations, axiomatic methods, and masking methods.   { \bf Backpropagation based explanations} shape credit as it is propagated backwards through the neural network according to certain rules.  These approaches include {\bf Layerwise Relevance Propagation} \citep{binder2016layer} which satisfies completeness, {\bf Rect-Grad} which thresholds internal neuron activations \citep{kim2019saliency}, and {\bf DeepLIFT} which satisfies the summation to delta rule.

\myparagraph{Axiomatic methods.} Axiomatic methods decompose the ouput (typically the logit) according to certain axioms like fairness in Shapley based methods {\bf SHAP} \citep{NIPS2017_8a20a862} and {\bf conceptSHAP} \citep{yeh2020completeness}.  We also include gradient based approaches like {\bf Gradient} $\frac{\partial S}{\partial x}$ \citep{baehrens2010explain} which calculates the partial derivative of the logit with respect to the input. {\bf Gradient $\odot$ Input} \citep{shrikumar2017learning} $\frac{\partial S}{\partial x} \cdot x$, which elementwise multiplies the gradient explanation by the input, and {\bf Grad-CAM} \citep{selvaraju2016grad} which takes the gradient of the logit with respect to the feature map of the last convolutional unit of a DNN. {\bf Smooth-Grad} \citep{smilkov2017smoothgrad}, which averages the {\bf Gradient $\odot$ Input} explanation over several noisy copies of the input $x + \eta$, where $\eta$ is some Gaussian.
The previous methods are intrinsic in the sense that they aim to explain the model decision. The last category of saliency maps, namely masking methods, also aim to explain the model decision, but they frequently aim to do so in a way that is interpretable by a human.
Contrastive methods, such as contrastive layerwise propagation \citet{gu2018understanding}, also modify LRP by constructing class specific saliency maps, with the goal of object localization, i.e. in an image of an elephant and zebra, the saliency map for elephant should have high overlap with the elephant, and similarly for the corresponding map for zebra.

\myparagraph{Masking Methods.} Masking Methods are often evaluated using a pointing game or WSOL metric, which measures overlap with human labeled bounding boxes or explanations. These masking methods include techniques based on averaging over randomly sampled masks \citep{petsiuk2018rise}, optimizing over meaningful  mask perturbations \citep{fong2017interpretable}, and real time image saliency using a masking network \citep{dabkowski2017real}. Pixels that have been removed from the image by the mask may be replaced by graying out, by Gaussian blurring as in \citet{fong2017interpretable}, or with infillers such as CA-GAN \citep{yu2018generative} used in \citet{chang2018explaining}, or DFNet \citep{hong2019deep}. \citet{de2020decisions} find masks using differentiable masking. \citet{taghanaki2019infomask} introduce a method that results in more accurate localization of discriminatory regions via mutual information.

\myparagraph{Pruning and information theory} \citet{khakzar2019improving} improve attribution via pruning.  \citet{schulz2019restricting} improve attribution by adding noise to intermediate feature maps.

\myparagraph{Saliency and Boolean Logic.}  Previous work has also drawn connections between saliency and notions in logic. \citet{ignatiev2019relating} relates saliency explanations and adversarial examples by a generalized form of hitting set duality. \citet{ignatiev2019abduction} develops a constraint-agnostic solution for computing explanations for any ML model. \citet{macdonald2019rate} develop a rate distortion explanation for saliency maps and prove a hardness result. \citet{mu2020compositional} find a procedure for explaining neurons by identifying compositional logical concepts. \citet{zhou2018interpreting} describe network dissection, which provides labels for the neurons of the hidden representations. We are unaware of frameworks like Section~\ref{sec:stat}.

\myparagraph{Arguments about saliency.} For discussion including pro/cons  of various methods  some starting points are \citet{seo2018noise}  \citet{fryer2021shapley} \citet{gu2018understanding} \citet{sundararajan2020many}.

\myparagraph{\citet{phang2020investigating}}
We describe separately the masking procedure used by \citet{phang2020investigating}.
They begin by taking a pretrained model on ImageNet. The masker has access to the internal representations of the pre-trained model, and tries to maximize masked in accuracy and masked out entropy. They do not provide the ground truth label to the masker.

\subsection{Saliency Evaluation Methods}

Saliency evaluation methods attempt to evaluate the quality of a saliency map. Many interpret the heatmap values as a priority order of saliency.
Extrinsic evaluation metrics include the {\bf WSOL} metric, which aim to measure overlap of the saliency map with a human annotated bounding box and the {\bf Pointing Game} metric proposed by \citet{zhang2018top} in which a pixel count as a hit if it lies within a bounding box and a miss otherwise, and the metric is $\frac{\text{\# Hits}}{\text{\# Hits + \#Misses}}$.
Other more intrinsic methods include early saliency evaluation techniques like {\bf MorF} and {\bf LerF} \citet{samek2016evaluating}, which involve removing pixels either in the order of highest importance or lowest importance and observing the area of the resulting curve. {\bf  Insertion and Deletion Games} of~\citet{petsiuk2018rise} uses this too. The deletion game measures the drop in class probability as important pixels are removed, while the insertion game measures the rise in class probability as important pixels are added. (Our AUC discussion in Section~\ref{sec:stat} relates to this.)
{\bf Remove and Retrain (ROAR)} is a saliency evaluation method proposed by \citet{hooker2019benchmark}. Input features are ranked and then removed according to a saliency map. A new model is trained on the modified training set, and a larger degradation in accuracy on the modified test set compared to the original model on the original test set is regarded as a better saliency method. (NB: retraining makes this a non-intrinsic method.)
Previous work has also introduced datasets specifically designed to test saliency methods. {\bf BAM} \citet{yang2019benchmarking} creates saliency maps by pasting object pixels from MSCOCO \citet{lin2014microsoft} into scene images from MiniPlaces \citet{zhou2017places}.  The  {\bf Saliency Metric} proposed by \citet{dabkowski2017real} thresholds saliency values above some $\alpha$ chosen on a holdout set, finds the smallest bounding box containing these pixels, upsamples and measures the ratio of bounding box area to model accuracy on the cropped image, $s(a,p) = \log(\max(a,0.05)) - \log(p)$ where a is the area of the bounding box and p is the class probability of the upsampled image.

 	\subsection{Saliency computations and underlying meanings of saliency}
	For simplicity this discussion assumes the datapoints are images and the classifier is a deep net. The heatmap in the saliency method is trying to highlight the contribution of individual pixels to the final answer. This is analogous to how a human may highlight relevant portions of the image with a plan. (Classic saliency methods in vision are inspired by studies of human cognition.) Saliency methods operationalize this intuitive definition in different ways, and we try to roughly categorise these as follows.

	\myparagraph{Variational interpretation.}These interpret saliency in terms of effect on final output due to change in a single pixel --captured either via partial derivative of output with respect to pixel value (i.e., effect of infinitesimal change), or via change of output when this pixel is set to $0$ or to a random (or "gray")  value. Examples include {\bf Gradient}, {\bf Gradient $\odot$ Input}  \citet{shrikumar2017learning}, {\bf Occlusion  }

	\myparagraph{Credit attribution guided by gradient.}These  use the gradient to guide the assignment of saliency values. The gradient is interpreted as propagating values from the output to the input layer, and the values are partitioned/recombined at internal nodes of the net following some conservation principles. A key goal is to ensure {\em completeness}, which means that the sum of the attributions equal the logit value.  Examples include {\bf LRP}, {\bf DeepLIFT} \citet{shrikumar2017learning}, {\bf Rect-Grad} Let $a_i^{l}$ be the activation of some node in layer $l$, and $R_i^{l+1}$ be the backpropagated gradient up to $a_i^{l}$. Rect-grad  replaces the vanilla chain rule, $R^{l} = \mathbf{1}[a_i > 0]$ with the rule that $R_{i}^l = \mathbf{1}[R^{l+1}_ia_i > \tau]$ for some threshold $\tau$. Hence, during a backward pass preference is given to nodes with large margin.

	\myparagraph{Ensembling on top of above two ideas.} Ensembling methods combine saliency estimates over multiple inputs an an attempt to reduce noise in the final map. Examples include {\bf Smooth-Grad}, Occlusion based methods, etc. We also include {\bf Shapley Values} in this list.

	The Shapley value aims to fairly distribute credit among a coalition of $N$ players. In the context of image saliency, each coordinate of the image input may be seen as a player, and the Shapley value computes $\sum_{S \subseteq N} \setminus \{i\} \frac{|S|! (n - |S| -1)!}{n!} (v(S \cup \{i\}) - v(S)) $. It can be interpreted as the marginal contribution of player i, over all possible orderings of the coalition. In this sense, it can be seen as an ensembling method, as it averages over all possible random permutations.

	{\bf Analysis of saliency methods.} Previous work has analyzed ensembling methods like Smooth-grad, and found that it does not smooth the gradient \citet{seo2018noise}. They conclude that Smooth-Grad does not make the gradient of the score function smooth. Rather Smooth-grad is approximately the sum of a standard saliency map and higher order terms and the standard deviation of the Gaussian noise. It has also been found that Shapley values, despite having a uniqueness result, can differ in the way they depend on the model, data, etc \citet{sundararajan2020many}.  \citet{fryer2021shapley} highlight several nuances that should be taken into account when considering Shapley values. They introduce Shapley values as averaging over submodels, and note that "the performance of a feature across all submodels may not be indicative of the particular performance of that feature in the set of optimal submodels.". They provide specific cases where satisfying the axioms of Shapley values works against the goal of feature selection.

\section{Clarifying benefit of TV regularization}
\label{app:linearcase}

This section gives more details of the discussion in \Cref{sec:linear}
about how TV regularizers help ensure soundness even in a linear setting.

Let $\mathcal{S}$ be a dataset of labeled data $({\bm{x}}, y)$ where the inputs are of unit norm and labels are binary, i.e., $\normtwosm{{\bm{x}}} = 1$, $y \in \{\pm 1\}$. The model in question is a linear classifier $f({\bm{x}}) := \mathrm{sgn}(\dotp{{\bm{w}}}{{\bm{x}}})$ parameterized by the weight vector ${\bm{w}} \in \mathbb{S}^{d-1}$, and it achieves the perfect accuracy on the set $\mathcal{S}$ with a margin $\gamma := \min_{({\bm{x}}, y) \in \mathcal{S}} y\dotp{{\bm{w}}}{{\bm{x}}} > 0$. We assume that the coordinates of ${\bm{x}}$ and ${\bm{w}}$ are uniformly bounded by $\frac{10}{\sqrt{d}}$, i.e., $\norminfsm{{\bm{x}}} \le \frac{10}{\sqrt{d}}$,  $\norminfsm{{\bm{w}}} \le \frac{10}{\sqrt{d}}$ ($10$ can be changed to any other constant).

Let $\Gamma$ be the input modification process that sets all non-salient pixels to $0$. We are interested in binary heatmaps, i.e., $\bm{m}$ assigns $1$ to pixels in some salient set $S$, and $0$ otherwise. According to
\Cref{def:basemetric}, $g(x, a, \bm{m}) = \mathbbm{E}_{\tilde{x} \sim \Gamma(x, \bm{m})} [\onec{f(\tilde{{\bm{x}}}) = a}]$. A simple calculation shows that this expectation is equal to $\onec{a \sum_{i \in S} w_i x_i > 0}$, and thus the goal is to find $S$ so that $a \sum_{i \in S} w_i x_i > 0$.

As we do not consider the full salient set informative, we are interested in salient sets with size constraint $\abssm{S} = L$ for some $1 \le L \le d$. There is a simple saliency method that achieves this goal: Given an input ${\bm{x}}$ and a label $a \in \{\pm 1\}$, sort the coordinates according to $a w_i x_i$ and take the highest $L$ coordinates as the salient set $S$.

It is easy to see that this method always produces $S$ with $a \sum_{i \in S} w_i x_i > 0$. Letting $a = y$ proves the completeness. However, this method does not satisfy soundness: a salient set $S$ with $a \sum_{i \in S} w_i x_i > 0$ can also be found for $a \ne y$!

Now we see how the TV constraint helps to ensure soundness (with good probability). A vector can be seen as a 1D image, and the TV of a salient set $S$ can be defined by $\mathrm{TV}(S) := \sum_{i=1}^{d-1} \abs{\onec{i \in S} - \onec{i + 1 \in S}}$.
For simplicity, we consider salient sets with TV at most $2$. This means $S$ is just an interval. Given the size and TV constraints $\abssm{S} = L$, $\mathrm{TV}(S) \le 2$, it is easy to come out with the following saliency method: search over all the intervals of length $L$ and if an interval $S$ satisfies $a \sum_{i \in S} w_i x_i > 0$, return it as the salient set.
Fortunately, this method does satisfy both completeness and soundness, as is justified by \Cref{thm:int1} in \Cref{sec:linear}.

\thmlinear*

\begin{proof}
	Let $\bm{m}$ be any fixed interval of length $L$, associated with salient set $S$.
	The distribution of $\sum_{i \in S} w_i x_i$ is identical to the distribution of the sum of $L$ samples drawn from $\{w_1 x_1, \dots, w_d x_d\}$ without replacement. Note that $d yw_1 x_1, \dots, d yw_d x_d$ are $d$ numbers with mean $\gamma$, and their absolute values are bounded by $10^2 = O(1)$. By Chernoff bound,
	\[
	\Pr\left[\frac{1}{L} \sum_{i \in S} d yw_i x_i \le \gamma -\epsilon \right] \le e^{-\Omega(\epsilon^2 L)}.
	\]
	Set $\epsilon = \gamma$ ensures that $y\sum_{i \in S} w_i x_i > 0$ with probability $1 - e^{-\Omega(\gamma^2 L)}$.
	We can fix any interval $\bm{m}$ with $L=L_1$ to prove Item 1.

	Taking union bounds over all intervals of length $L$, we can see that the probability of existing an interval of length $L$ that certifies $-y$ should be no greater than $\sum_{\abssm{S} = L} e^{-\Omega(\epsilon^2 L)} \le d^2 e^{-\Omega(\gamma^2 L)}$. Setting $L = L_2$ proves Item 2.
\end{proof}

This shows that such salient sets make sense to humans: if the model predicts $y$, then we can find an interval of length $\tilde{\Omega}(1/\gamma^2)$ so that computing the inner product only in that interval leads to the same prediction; otherwise if the model does not predict $y$, such interval cannot be found. Thus it is sufficient to convince humans that the model predicts $y$ by only revealing the existence of such interval and the coordinate values in it.

\section{Conclusions}
\label{sec:conclusions}
\vspace{-0.05in}
Saliency explanations of ML models have proved nebulous and generated much discussion.
By avoiding extrinsic considerations (e.g., human interpretability) and sticking to intrinsic notions such as completeness and soundness, this paper has tried to give a rigorous notion of saliency  that is intrinsic to the deep net, while avoiding the noisiness in earlier intrinsic ideas that motivated methods like Gradient$\odot$Input and Shapley Values.
Other new contributions include clarifying in the intrinsic view the role of TV regularization and other tricks (it hurts completeness slightly but greatly improves soundness);  a simple saliency method (\Cref{sec:procedures}) for producing mask-based explanations that was designed solely with intrinsic considerations and yet has performance competitive with good existing methods, and sometimes better (\Cref{tab:imagenette_main}).
Our experiments suggest soundness provides a new dimension to evaluate saliency methods on, and that good performance on it can be achieved without compromising on other metrics.
Note that soundness needs to be considered only while designing and evaluating the method, not at deployment.

\looseness-1 Evaluating soundness requires looking at maps for all labels instead of just the top label, and thus seems relevant for object {\em localization} in images, and for classification in the wild --- where multiple objects appear in an image.
This benefit is hinted in our evaluation on a prior small dataset (see \Cref{sec:elezeb}) and deserves further exploration.
It may help with certain distribution shifts as well.
While this work studies soundness in the context of mask-based saliency methods and evaluations, the concept of soundness could be applicable for the idea of saliency and interpretability in more generality.

\myparagraph{Acknowledgements.}
We thank Ruth Fong for feedback on an earlier draft of this paper.
We are also grateful to the valuable comments from various anonymous reviewers that helped improve the paper.
This work is supported by funding from NSF, ONR, Simons Foundation, DARPA and SRC.

\section{Experiments}
	\label{sec:expers}

	 \looseness-1 In this section, we aim to 1) show TV penalty and upsampling have intrinsic justification that they significantly improve soundness at a small cost in completeness; 2) evaluate and compare prior saliency methods, and our method with different parameter settings, on our completeness and soundness metrics.

	 Experiments are performed either on CIFAR-10 or Imagenette \citep{howard2020imagenette}, a 10-class subset of ImageNet \footnote{Completeness and soundness evaluation on all labels can get computationally expensive  on ImageNet as it contains 1000 classes. This cost is only relevant when designing the method; not at deployment time.}.
	 We compute maps and evaluate metrics on 1000 randomly drawn images from the original test set.
	 Additional experiments on various models and datasets (including ImageNet and CIFAR-100) appear in Appendix \ref{sec:additionalexpers}, as do
	details of training procedure (beyond those in \Cref{sec:procedures}).
	For all our completeness and soundness evaluations, we use thresholds of $\epsilon_{1} = 0.01$ and $\epsilon_{2} = 0.001$ (see \Cref{eq:cs}).

\subsection{Effect of TV penalty and upsampling}
\label{sec:effect_TV}

In this section, we study the effect of ``tricks'' like TV penalty and upsampling on the learned maps and evaluation metrics.
Figure \ref{fig:prob_curves} shows how soundness and completeness of our masks changes with TV regularization. It plots the model output probability for CIFAR-10 as more pixels from the original image are retained using the mask. Our high level finding is that adding TV penalty significantly aids soundness, while only slightly hurting completeness. Exact evaluation of soundness and completeness for different $\lambda_{TV}$ are listed in \Cref{tab:tv_consistency_cifar10} in \Cref{sec:additionalimagenette}.
Relevant points of \Cref{fig:scatter_completeness_soundness} (which also contain other saliency methods) show effect of upsampling and TV penalty on completeness and soundness. We compare our method from \Cref{sec:procedures} with different settings on Imagenette.
Our method by default use $s=4$ and $\lambda_{TV}=0.01$.
By comparing ``Ours'' against ``Ours($s=1$)'' and ``Ours($TV=0.001$)'', we observe that upsampling and TV penalty leads to slightly worse completeness but significantly better soundness. The effect of upsampling on previous saliency evaluation metric may be seen in the relevant entries of \Cref{tab:imagenette_main}, where it leads to slightly worse performance on the insertion, deletion, and saliency metrics.

    \subsection{Comparison to existing metrics and methods}
    \label{subsec:comp}

    \looseness-1 We compared our procedure to other methods including Gradient $\odot$ Input \citep{shrikumar2017learning}, iGOS++\citep{khorram2021igos++}, \citet{dabkowski2017real}  \citet{fong2017interpretable} and \citet{phang2020investigating} on Imagenette.
    We also include simple baselines like ``Random'' map (each entry is a random Gaussian), and ``Centered Gaussian'' map (2-dimensional isotropic Gaussian distribution placed at the image center).
    Besides completeness and soundness metrics, we evaluate methods on the Deletion Game and Insertion Game metrics (\url{https://github.com/eclique/RISE}), and
	Saliency metric (SM) \citep{dabkowski2017real}.
	Detailed description of the different metrics can be found in the Appendix \ref{sec:additionalbackground}.

	\looseness-1 For our method, we learn a map by optimizing the objective function in \Cref{eq:main_obj} with $\lambda_{TV}\in\{0.01,0.001\}$ and $s \in \{1, 4\}$; default settings are $\lambda_{TV}=0.01, s=4$.
	We also evaluate our method when other pixels are replaced with gray rather than a random image, denoted by ``Ours (gray)''.
    For uniformity, we use the identical ResNet50 pretrained on ImageNet as the base classifier for every saliency method.
	We normalize the maps so that all values lie in $[0,1]$ before use.

\input{table_fig/imagenette_main_table}

\myparagraph{Completeness and soundness.}
We compare different methods on the metrics from \Cref{def:worst_cs}, through the visualization in  \Cref{fig:scatter_completeness_soundness} (left) and in \Cref{tab:imagenette_main}.
We find that our method achieves better completeness and good soundness compared to other methods and baselines.
We posit that completeness is better due to our improved composite input strategy from \Cref{eq:composite}, where non-salient pixels are filled with another image pixels as opposed to other strategies.
As an ablation, we see that ``Ours (gray)'' which uses gray replacement does not perform as well.

\looseness-1On the other hand, our soundness is good only for higher TV regularization $\lambda_{TV}=0.01$ and higher upsampling $s=4$, as discussed in \Cref{sec:effect_TV}.
Soundness is very bad (but completeness slightly better) if these ``tricks'' are not used.
We note that while \citet{phang2020investigating} does as well as our method on soundness, it does so via ``cheating'' in an interesting way: they compute mask for the top label and return the same mask for all labels.
Since the method does not even try to generate masks for labels with low probability, it achieves good soundness for free.
To delve deeper, we employ the same ``cheating'' with our method --- return the same mask for all labels --- and observe a large bump in soundness, without any drop in completeness.
While ``cheating'' is always possible (even if unintentionally) for any metric, we hope that our results inspire saliency method designers to compute maps for all labels.
In this case we find, in \Cref{fig:scatter_completeness_soundness} (right), that looking at worst case completeness of incorrect labels (all except model prediction) gives a measure of the ``effort'' a method employs in generating masks for all labels with probability at least 0.01.
As evident methods that ``cheat'', like \citet{phang2020investigating} and ``Ours (cheating)'', achieve a bad ``best effort'' score.

\myparagraph{Other metrics.}
\Cref{tab:imagenette_main} suggests that our method can achieve comparable performances on most existing intrinsic metrics.
This suggests that good completeness and soundness scores are achievable without compromising on other measures.
Deletion metric is one where our method falls short, likely due to our method not employing an SDR objective as in \citet{dabkowski2017real}.
Although we note that ``Random'' baseline performs quite well on the Deletion metric, which suggests that deletion metric does not provide much signal on these datasets.
Further investigation on the good performance of ``Centered Gaussian'' baseline can be found in \Cref{sec:additionalimagenette}.

\looseness-1 Our settings that works best on other metrics are those without upsampling ($s=1$) or lower TV ($\lambda_{TV}=0.001$).
Soundness is the only metric that strongly justifies the upsampling and TV ``tricks'', thus verifying its utility.
Our method with $s=4,\lambda_{TV}=0.01$ demonstrates that good performance can be obtained on all metrics simultaneously, with only little price to pay.

\iffalse
	The results are shown in \Cref{tab:imagenette_main}.
	Most methods have comparable or worse performance on deletion metric than the random mask, which suggests that deletion does not provide much signal about the goodness of the saliency maps in these standard datasets. Our method performs decently on insertion since this metric depends on a variant of the completeness condition.

	Our method is not inherently optimized for deletion and saliency metric, yet it achieves reasonable performance. For example, we do not employ an SDR objective as in \citet{dabkowski2017real} which could improve performance on the deletion metric. Furthermore, our optimization centers around superimposing mask values on the input, whereas in saliency metric, mask values are only used to find the tightest bounding box around the most salient values, and then discarded.

	Most prior methods perform well on consistency score{} when the base classifier predicts the ground truth. However, our method performs better on samples that the base classifier predicts incorrectly. Our method shows that soundness can be improved without significantly affecting performance on other known metrics. Note that our metric assumes saliency methods generate different (meaningful) masks for each label. Methods like \citet{phang2020investigating} do not, therefore inherit an advantage. Our method performs well on consistency score{} even with arguable disadvantage, and reasonably on prior evaluations, implying there may be ways to improve soundness for previous works.

    The strong performance of the Centered Gaussian on saliency metric and insertion is likely due to the spatial bias of Imagenette, in which objects are often centered. However, the Centered Gaussian still has lower consistency score than our method. For further investigation, we create an off-centered version of Imagenette, and observe the decreased performance of Centered Gaussian in \Cref{sec:additionalimagenette}.

	To verify the connection between completeness/soundness and consistency score, we compute the completeness and soundness (with $\epsilon=10^{-3}$) for test samples, and report the average in \Cref{tab:imagenette_complete_sound}. It shows completeness/soundness and consistency score{} are highly correlated. \revise{Even though saliency methods like Phang et al. (2020) have inherent advantage in soundness, our method still achieves the best soundness. Our method also gains better completeness, which is likely contributed by maximizing the probability assigned to the given label instead of matching the model probability. }
\fi

\iffalse
    \begin{table}[h]
        \centering
        \begin{tabular}{c|c|c|c|c}
             & ours ($s=1$) & ours ($s=4$) & \citet{phang2020investigating} & \citet{fong2017interpretable} \\
             \hline
            mask-model consistency & & 0.88 & 0.864 & 0.832\\
             \hline
            mask-model consistency  $|\argmax_a f(x,a) = y$ & & 0.9825 & 0.985 & 0.985\\
             \hline
            mask-model consistency  $ |\argmax_a f(x,a) \neq y$  & & 0.47 & 0.38 & 0.22\\
        \end{tabular}
        \caption{We compute AUC of insertion game with gray infilling as masking explanation. The last two rows are the mask-model consistency conditioned on whether the base classifier predict the ground truth. From the table, our method with $s=4$ achieves the best consistency. All three methods achieves almost perfect consistency for test samples that base classifier predicts correctly. \dy{ numbers to update}}
        \label{tab:consistency}
    \end{table}
\fi

\iffalse
	Previous work has investigated mask based saliency maps \citet{phang2020investigating}. They train a neural network masker and use three main masking objectives,  maximizing masked-in accuracy, minimizing masked-out accuracy and maximizing masked-out entropy. They also focus on the case where the ground truth label is not available. They use  L1 regularization to limit the size of masks and Total Variation (TV) to encourage smoothness. \citet{dabkowski2017real} find the smallest destroying regions. We implement a simple masking method in order to demonstrate the effect of changing TV on partial assignments for both the ground truth and second best labels.

	\fi

	\iffalse
	We follow the procedure detailed in Section \ref{sec:procedures} to find partial assignments for both ground truth and second best labels on ImageNet for a Resnet18 model.
		We run an experiment in order to determine if it is possible to assign high probability to the predicted class $C_y$ while removing most pixel information in the original image. We run the following optimization.  Let $X \in \mathbb{R}^{n \times d}$ be the original dataset of $n$ points in $d$ dimensions, in our case CIFAR 10 and ImageNet. (We normalize the data in the usual way before training.) Let $M$ be a trained neural network on $X$. We create a weight matrix $W \in \mathbb{R}^d$ of the same size as a particular image $X^{i}$, and  use as a mask $\exp(W^2)\odot X^{i}$, where $W$ is squared element-wise to preserve positivity.
	Additionally, we tie the weights in W across RGB channels.
\fi

\iffalse
\begin{table}[t!]
\begin{center}
	\caption{Performance of our method and some baselines on various intrinsic saliency metrics proposed in prior work.  We find that while both our masks (learned with and without TV) have very good performance on the insertion metric, the mask learned with TV has much better performance on the saliency metric. The deletion metric is uninformative in most cases, since most methods are no better (or worse) compared to a random mask.}
	\label{table:metrics}
\begin{tabular}{ |c|c|c|c| c| c| }
 \hline
 & Gradient $\odot$ Input & Our method & Our Method & Real time & Random \\
 &  & ($\lambda_{TV}=0.01$) & ($\lambda_{TV}=0$) & saliency &   \\
 \hline
 Deletion $\downarrow$       &    \bf{0.11}   &  0.15    &     0.21  &    0.15 & 0.15 \\

Insertion (blur) $\uparrow$      &   0.44    & 0.80         &    {\bf 0.92}  & 0.60 & 0.31 \\
Saliency Metric $\downarrow$  & 0.31 & {\bf 0.15} & 0.32  & 0.40 & 0.31 \\
 \hline
\end{tabular}
\end{center}
\end{table}
\fi

\iffalse
\subsection{Practical Benefits of Being Sound}

\kf{I cut \& pasted the following paragraph from Section 3 to here. Feel free to move it again and polish}

Images may have multiple plausible labels. In \Cref{fig:elezeb}, an image can have both elephants and zebras present, but it may not be always clear from the model output if there is such a case, since the model can be much more confident on one label, e.g., elephant, than one would expect it to be. For this reason, finding masking explanations validating other labels, e.g., zebra, could provide more information on how the model makes the prediction.

\begin{figure}[htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{elephant-zebra.png}
	\caption{Images (previously used in \citealt{gu2018understanding}) containing both elephant(s) and zebra(s), and the corresponding masked ones generated by our method and the best-performing CA model in \citet{phang2020investigating}. The masks by \citet{phang2020investigating} are identical for different labels.  }
	\label{fig:elezeb}
\end{figure}
\fi

\section{Introduction}
\label{sec:intro}

{\em Saliency methods}  try to understand why the deep net gave a certain answer on a particular input, and are an important component of  explainability, fairness,  robustness, etc., in deep learning.
This paper restricts attention to
the (large) class of saliency methods that
return an importance score for each coordinate of the input --- often visualized as a  heat map --- which captures the coordinate's importance to the final decision.\footnote{Heat maps suffice for recognition/classification tasks; other tasks may require more complex explanations.}  Early saliency methods used an axiomatic system of ``credit attribution'' to individual input coordinates,  using backpropagation-like methods \citep{binder2016layer,selvaraju2016grad} and cooperative game theory, such as Shapley values~\citep{lundberg2017unified,yeh2020completeness}. See \Cref{sec:prior} and \citet{samek2019explainable} for discussion of strengths and limitations of such methods.
More recent methods try to find heat maps that are largely concentrated on a smaller set of pixels/coordinates and are discussed further below.

\looseness-1 There exists an ecosystem of {\em evaluation metrics} to  evaluate saliency methods. Evaluations can be {\em extrinsic}, involving   human evaluation \citep{adebayo2018sanity}, and comparison to certain ground truth explanations \citep{zhang2018top}. We restrict attention to
{\em intrinsic} evaluations, which use computations involving the net itself and the heat/saliency map --- but no human evaluations or evaluations that involve training new deep nets. Popular intrinsic evaluations include {\em saliency metric}~\citep{dabkowski2017real} and insertion \& deletion metrics~\citep{petsiuk2018rise}.

\looseness-1 A frequent idea in intrinsic evaluations (see \Cref{sec:stat} for references) is to create a new composite input --- or sequence of such inputs --- using the heat map and the original input, and to evaluate the original net on this composite input. For example, if $M$ is a binary vector with $1$'s in the $k$ coordinates with the highest values in the heat map, then $x \odot M$ (with $\odot$ denoting coordinate-wise multiplication) can be viewed as a masked input where only $k$ of the original coordinates of $x$ remain. It is customary to replace the  zeroes in this masked input with ``uninformative'' values, which we refer to as {\em gray} pixels.
This masked input is fed into the original net\footnote{This raises a potential issue of distribution shift because the net never trained on masked inputs. In practice, especially for image data, trained nets continue to work fine on masked inputs.} to check if the net outputs the same label as on the full input --- and, if so, one should conclude that the unmasked coordinates of $x$ were salient to the net's output.

 Not surprisingly, recent methods~\citep{fong2017interpretable,dabkowski2017real,phang2020investigating} for finding heatmaps use an objective that tries to directly optimize performance on such evaluations, greatly outperforming older axiom-based methods.

{\em Should we trust such mask-based explanations}? At first sight, this question may appear naive. In the above-described masked input
$x \odot M$, some $k$ pixels were copied from the original image and the remaining pixels were made \textquotedblleft gray.\textquotedblright~
If the original net outputs essentially the same label as it did on the full image,  does this not {\em prove} that the portion that came from the mask $M$  must have {\em caused} the net's output on the full image?  The answer is \textquotedblleft No\textquotedblright, because the {\em positions} of the gray pixels can carry some signal.

\Cref{fig:artifact-small} shows that  in standard  datasets,  it is possible to create masks out of most inputs such that the masked input  can cause the net to assign high probability for a {\em different}  label than in its original prediction.  Prior works referred to this phenomenon as \textquotedblleft mask artifacts\textquotedblright\ and suggested using total variation (TV) regularization to mitigate this issue. But \Cref{fig:artifact-small} shows TV regularization is not a full solution to masks that cause the net to (incorrectly) flip the answer.

\myparagraph{Soundness needed.} The masked input method is trying to {\em prove} that a certain portion of the image  \textquotedblleft caused\textquotedblright\ the net's output.  Usually logical reasoning must display both {\em completeness} (i.e., all correct statements are provable) and {\em soundness} (incorrect statements cannot be proved).
Checking that the net's output is essentially unchanged with the masked input is akin to verifying {\em completeness}.

But this by itself should not be convincing because, as mentioned, it is possible to use the method to find a different mask to justify another (i.e., wrong) label.   {\em Soundness}  would require verifying that the same saliency method cannot be used to produce masked inputs that make the net output a different label.
Together, completeness and soundness ensure that the evaluation of the masked inputs produced using various labels approximately tracks the model's probability of assigning the label (see Section~\ref{sec:completeness_and_soundness}).

\begin{figure}[t!]
    \vspace{-0.1in}
    \begin{subfigure}{.5\textwidth}
        \centering
        \includegraphics[width=0.95\textwidth]{ghost_small.png}
    \end{subfigure}%
    \begin{subfigure}{.5\textwidth}
        \centering
        \includegraphics[width=0.95\textwidth]{ghost_small_bird_frog.png}
    \end{subfigure}
    \caption{Masked CIFAR-10 images generated by our procedure with TV regularization.
    ``Artifacts'' exist for masks generated for incorrect labels; more examples can be found in \Cref{fig:artifact} in Appendix.
    The base model outputs the correct label on the original image (ship and bird resp.) with probability at least 0.99, and assigns probability at most $10^{-5}$ for the incorrect label (cat and frog resp.). With the generated masks, the AUC metric (defined in \Cref{sec:methods_metrics}) for the correct label remains high (around 0.94 and 0.90), which corresponds to {\em completeness}, but AUC metric for the incorrect label rises tremendously (around 0.18 for cat mask, 0.71 for frog mask.) This suggests violation of {\em soundness}. }
    \label{fig:artifact-small}
    \vspace{-0.2in}
\end{figure}

\noindent{\bf Main Contributions of this paper:}
\vspace{-0.1in}
\begin{itemize}

\item \Cref{sec:completeness_and_soundness} draws connections to logical proof systems and formalizes completeness and soundness in the context of saliency methods.
These are intrinsic evaluations of saliency without appealing to human judgements (e.g., whether or not machine-generated masks contain artifacts).
Our notion of completeness and soundness requires saliency methods to output a map for {\em every label} and not just the model prediction.

\item \Cref{sec:procedures} revisits methods that learn masks through optimization.
Incorporating soundness, we propose a simple optimization method that maximizes the probability for any given label\footnote{Computation cost proportional to the number of labels is only incurred while designing/evaluating the saliency method but not deployment time. Another alternative is to verify soundness condition for top $k$ labels.}, rather than only the label deemed most likely by the net.
A key design choice of this method is the pixel replacement strategy during training: non-salient pixels are replaced with pixels of a random image, instead of using gray pixels, blurring or counterfactual models. \footnote{Code for computing completeness, soundness, and our masking method available at \url{https://github.com/agup/soundness\_saliency.git}}

\item \looseness-1 Experiments (in \Cref{sec:expers}) estimate completeness and soundness scores for various methods.
Our simple method does well on completeness and soundness as one would expect, but the slight surprise is that it performs comparably to prior masked-based methods on earlier saliency evaluations as well, suggesting that soundness can be achieved without paying much in completeness.
  Heuristic choices in existing mask-based methods such as  TV regularization and upsampling, which were hitherto justified extrinsically (i.e., they make masks look natural to humans), receive  an {\em intrinsic} and precise justification: they improve soundness.
   A theoretical result in \Cref{sec:linear} complements this experimental finding by showing that TV regularization helps saliency methods even in a simple linear classification setting, not just for vision data.

\end{itemize}

\section{Masking explanations and completeness/soundness}
\label{sec:stat}

The goal of a saliency method is to produce explanations for the outputs of a given deep net $f$.
We think of a saliency method (\Cref{def:heatmap}) producing explanations --- a heat map in this case --- as providing a {\em proof} of the statement {\em $f$ outputs the label $a$ for input $x$}.  Inspired by logical proof systems, we propose that intrinsic evaluations for saliency methods should test for both completeness and soundness, and the rest of the section provides definitions for these notions.

\subsection{Saliency methods and AUC metric}
\label{sec:methods_metrics}

For a net $f$, let $f(x, a)$ denote the (post-softmax) output probability of the net on input $x$ for label $a$.
We are interested in saliency methods that output a heatmap with a scalar per coordinate of the input
\begin{definition}[Saliency Method]
\label{def:heatmap}
A saliency method $\mathcal{M}$ is an algorithm that takes 1) a deep net $f$, 2) an input $x$, and 3) a label $a$   and produces a heatmap $\bm{m} = \mathcal{M}(f,x,a) \in \mathbb{R}^{\text{dim}(x)}$.
\end{definition}
Note that in the above definition, $\mathcal{M}$ can access any part of $f$ including intermediate layers and gradients.
Examples of methods that can be interpreted as returning heatmaps are mask-based methods \citep{fong2017interpretable,dabkowski2017real,chang2018explaining,agarwal2020explaining,phang2020investigating} that output heatmaps in $[0,1]^{\text{dim}(x)}$, backpropagation-like methods \citep{binder2016layer,selvaraju2016grad}, Shapely values \citep{lundberg2017unified,yeh2020completeness}, and Gradient $\odot$ Input.

\looseness-1 Given such a saliency method, an important question is how to evaluate the quality of the ``explanations'' or heat maps it produces.
A common evaluation idea is to use the behavior of the net $f$ on a ``masked'' input --- only the top few pixels based on the heat map in question are retained, while the others are hidden appropriately.
Inspired by this idea we define evaluation metrics for saliency methods.
We abstract the step of retaining the top few pixels into an {\em input modification process}, defined below.

\begin{definition}[Input Modification Process $\Gamma$]
Let $\Gamma$ be a potentially randomized procedure that takes an input $x$ and a heatmap $\bm{m}$ and generates a modified input $\tilde{x}$. i.e. $\tilde{x} \sim \Gamma(x, \bm{m})$.
\end{definition}
This input modification process defines a {\em base metric} that is the starting point of the completeness and soundness metrics that will be defined later.
\begin{definition}[Base Metric]
\label{def:basemetric}
Let $x$ be an input (image), $a$ a label, $\bm{m}$ a heatmap and $\Gamma$ an input modification process.  Then, a {base metric} is a function $g(x, a, \bm{m}) = \mathbbm{E}_{\tilde{x} \sim \Gamma(x, \bm{m})} [f(\tilde{x},a)]$, where $f$ is the neural net of interest\footnote{In general we can replace $f$ with any target function $h$ that depends on $f$}.
\end{definition}
The {base metric} measures the expected output of $f$ acting on \emph{modified} inputs $\tilde{x}$ and label $a$ and different choices for $\Gamma$ lead to different base metric s.
Some examples of $\Gamma$ that stay in the {\em intrinsic} framework are: graying out the pixels outside some subset $S$ of $\bm{m}$, replacing them by pixels from a Gaussian blurring of $x$~\citep{fong2017interpretable}.
Input modification through $\Gamma$ also shows up in saliency methods, including our proposed method in \Cref{sec:procedures}; we discuss prior choices of $\Gamma$ in that section.
For our evaluation metrics, however, we choose $\Gamma$ that grays out remaining pixels.

The popular Area-Under-the-Curve (AUC) evaluation metrics~\citep{petsiuk2018rise} of saliency methods can, in fact, be reinterpreted in terms of our {base metric}.
We state the {\em insertion game} and its AUC below, since it forms the basis of our subsequent completeness and soundness metrics, and then define the AUC metric as an instantiation of \Cref{def:basemetric}.
\begin{definition}[AUC of insertion game]
\label{def:AUC}
    For $s=1$ to $\text{dim}(x)$ take the top $s$ pixels as per $\bm{m}$, and plot the probability $f(x, a)$ given by model to label $a$ on the input $x$, where the top $s$ pixels of $x$ are retained and remaining pixels are assigned a default gray value. Return the area under the curve.
\end{definition}
\begin{definition}[AUC metric]
\label{def:AUCmetric}
    We denote by $g_{\textrm{AUC}}(x, a, \bm{m})$ the {base metric} when a modified input $\tilde{x} \sim \Gamma(x,\bm{m})$ is obtained as follows:
    \begin{itemize}
    \setlength\itemsep{0em}
        \item Sample $s\sim\{1, \dots, \text{dim}(x)\}$ and pick $S$ to be top $s$ pixels as per $\bm{m}$.

        \item Set $\tilde{x}[S] = x[S]$ and $\tilde{x}[\bar{S}] = x_{\text{gray}}[\bar{S}]$ where $x_{\text{gray}}$ is a ``default'' input with gray values.

    \end{itemize}
\end{definition}
We note that $g_{\textrm{AUC}}$ is indeed equivalent to the AUC insertion game from \Cref{def:AUC}.
While many choices of {base metric}s can be used, we use this AUC metric for subsequent definitions since it confers two benefits: 1) it allows for fair comparison between methods since all methods are evaluated at the same sparsity level; 2) it considers the effect of multiple sparsity levels instead of picking an arbitrary one.
We are now ready to present the formalization of completeness and soundness.

\input{table_fig/desktop}

\subsection{Completeness and soundness}\label{sec:completeness_and_soundness}

Just as for proof systems, we would like a saliency method to be logically complete and sound, i.e., it should be able to justify the label output by the net, but no other label\footnote{We focus on single label multi-class classification; extensions to multi-label are left for future work.}.
The statements to be ``proved'' are of the form {\em ``does $f$ think $x$ has label $a$?''}.
We use the model output probability $f(x, a)$ as fractional truth value of the ``statement'' $(x, a)$.
For a saliency map $\bm{m}$ that a saliency method $\mathcal{M}$ generates, we interpret the AUC metric $g_{\textrm{AUC}}(x, a, \bm{m})$ as the evaluation of truth value of  the ``proof'' $\bm{m}$, as adjudged by the {base metric} $g_{\textrm{AUC}}$.
Thus in this context, completeness for $\mathcal{M}$ would entail that whenever $f(x, a)$ is large (i.e., the statement is sufficiently true), $g_{\textrm{AUC}}(x, a, \bm{m})$ should be large (a sufficient good proof can, and is, generated).
Soundness, on the other hand, would entail that $g_{\textrm{AUC}}(x, a, \bm{m})$ should be small whenever $f(x, a)$ is small.
Thus we would like $g_{\textrm{AUC}}(x, a, \bm{m})$ to track the value of $f(x, a)$ through a lower bound and upper bound as follows:

\begin{definition}[Completeness and Soundness] \label{def:soundcompletestat}
      Consider a saliency method $\mathcal{M}$.
      For $\alpha, \beta \le 1$, the method $\mathcal{M}$ is  {\em $\alpha$-complete on $f, x, a$} if the heatmap $\bm{m} = \mathcal{M}(f, x, a)$ it produces satisfies \framebox{$g_{\textrm{AUC}}(x, a, \bm{m}) \ge \alpha~ f(x, a)$}, while $\mathcal{M}$ is {\em $\beta$-sound on $f, x, a$} if \framebox{$g_{\textrm{AUC}}(x, a, \bm{m}) \le \frac{1}{\beta} f(x, a)$}.
      Conversely the completeness and soundness scores for a heap map $\bm{m}$ on $(x,a)$ are defined as:
	\begin{align} \label{eq:cs}
	    \alpha(x, a)
	    = \min \left\{ \frac{\max\{g_{\textrm{AUC}}(x, a, \bm{m}), \epsilon_{1}\}}{f(x, a)},  1\right\},~~
	    \beta(x, a)
	    = \min \left\{\frac{\max\{f(x, a), \epsilon_{2}\}}{g_{\textrm{AUC}}(x, a, \bm{m})}, 1\right\} .
	\end{align}

\end{definition}
\begin{definition}[Worst case completeness and soundness]
\label{def:worst_cs}
    For a saliency method $\mathcal{M}$, these metrics are defined by taking the worst case of the completeness/soundness over labels $a$ for a given $x$ that is sampled from the underlying input distribution.
    More precisely,
    $
        \alpha(\mathcal{M}) = \mathop{\mathbb{E}}_{x}\left[\min_{a} \alpha(x, a)\right],
        \beta(\mathcal{M}) = \mathop{\mathbb{E}}_{x}\left[\min_{\beta} \beta(x, a)\right]$.

\end{definition}

Our metrics implicitly require a saliency method to output a meaningful map for every label (or at least all labels assigned non-negligible probabilities by the net) and not just for the top model prediction.
Notice, $\alpha$-completeness means that if the model outputs a high probability for label $a$, then the probability for label $a$ after seeing only the coordinates in the salient sets is also high, while $\beta$-soundness means that this probability is not too high. Checking both conditions verifies if the AUC score $g_{\textrm{AUC}}(x, a, \bm{m})$ of a map $\bm{m}$ is in the interval $\left[\alpha f(x, a), \frac{1}{\beta} f(x, a)\right]$.
We want $\alpha, \beta$ as close to $1$ as possible.
This notion is different from the usual AUC insertion game, which just requires $g_{\textrm{AUC}}(x, \hat{y}, \bm{m})$ to be as large as possible for the model prediction $\hat{y} = \argmax_{a} f(x, a)$.
Moreover, our worst-case completeness and soundness metrics require the $g_{\textrm{AUC}}(x, a, \bm{m})$ to roughly {\em match} the model prediction $f(x, a)$, {\em for every pair $(x, a)$},\footnote{Works like Gradient $\odot$ Input and LRP use {\em completeness} in a somewhat different sense. It requires the sum of the coordinate scores in the heatmap to {\em exactly} equal the logit of the label. Our completeness + soundness together try to approximately match the $g_{\textrm{AUC}}$ score to the output probability on this label.}
where the thresholds $\epsilon_{1}, \epsilon_{2}$ in \Cref{eq:cs} help in ignoring the case where the model outputs very small probabilities --- for instance we can ignore any label for completeness if $f(x,a) < \epsilon_{1}$.

\subsection{Illustration of completeness and soundness on an ImageNet example}
\label{sec:interpretation}
See \Cref{fig:desktop}. For this image $x$, the model assigns reasonably high probabilities to labels $a_{1}=\text{``desk''}$ and $a_{2} = \text{``desktop computer''}$, with $f(x, a_{1}) \approx 0.67$ and $f(x, a_{2}) \approx 0.13$.
We compare the maps computed by three methods --- $\mathcal{M}_{1}$: our mask learning procedure from \Cref{sec:procedures} with TV regularization 0.01, $\mathcal{M}_{2}$: our method with TV of 0.001, and $\mathcal{M}_{3}$: the mask learned by \citet{phang2020investigating}.
The corresponding maps generated are denoted by $\bm{m}_{i}, i\in\{1,2,3\}$.
For this discussion we only consider the effect of labels $a_{1}$ and $a_{2}$ on completeness and soundness, and we assume the thresholds satisfy $\epsilon_{1} = \epsilon_{2} = 0$.

\myparagraph{Completeness.}
For the label $a_{1}$, the AUC scores $g_{\textrm{AUC}}(x,a_{1},\bm{m}_{i})$ for the three methods are roughly 0.65, 0.70 and 0.43 respectively.
Thus all three maps can ``certify'' the label $a_{1}$ well enough, with $\bm{m}_{2}$ doing the best job.
Consequently the completeness scores (\Cref{eq:cs}) for $\bm{m}_{1}$ on the pair $(x, a_{1})$ is $\alpha_{1}(x, a_{1}) = \min\{\frac{0.65}{0.67}, 1\} \approx 0.97$; similarly $\alpha_{2}(x, a_{1}) = 1$ and $\alpha_{3}(x, a_{1})= \frac{0.43}{0.67} \approx 0.64$.
Similarly for label $a_{2}$ that is assigned a probability of 0.13, the completeness scores $\alpha_{i}(x, a_{2})$ are 1, 1, and 0.58.
Thus the worst case completeness from \Cref{def:worst_cs}, i.e. $\min_{j\in\{1,2\}} \alpha(x, a_{j})$, for the three methods are 0.97, 1 and 0.58.
Based on completeness $\mathcal{M}_{2}$ seems like the best method; however soundness will paint a different picture.

\myparagraph{Soundness.} Using the same AUC scores we compute the soundness scores, defined in \Cref{eq:cs} as $\beta_{i}(x, a) = \min\{\frac{f(x, a)}{g_{\textrm{AUC}}(x, a, \bm{m}_{i})}, 1\}$.
This gives us soundness scores on $a_{1}$ of 1, 0.95 and 1.
The more interesting case is label $a_{2}$, for which the model does not assign very high probability (0.13).
Here the mask from $\mathcal{M}_{2}$ still gets a very high AUC score of 0.29, leading to a soundness score $\beta_{2}(x, a_{2}) \approx \frac{0.13}{0.29} \approx 0.44$.
$\mathcal{M}_{1}$ on the other hand is not as overconfident in its explanation as $\mathcal{M}_{2}$, and gets $\beta_{1}(x, a_{2}) = \frac{0.13}{0.15} \approx 0.89$.
The worst case soundness for three methods ends up being 0.89, 0.44 and 1.

\looseness-1 This examples highlights how completeness and soundness together can give a more nuanced comparisons of saliency maps, including understanding the benefit of TV regularization.
Experiments in \Cref{sec:expers} do a more thorough comparison of many saliency methods on these and prior metrics.

\section{Logic view of saliency methods: Partial assignments}
\label{sec:logic}
In general the saliency method is given a circuit $f$ (i.e., a deep net) and an input $x$, and  asked to identify a portion of $x$ "responsible" for the output of $f$ on $x$.
A running theme in saliency methods/evaluations is that the salient pixels should be sufficient to convince us about the model's output, regardless of contents of the other pixels. For instance, greying out the pixels (or setting them to average pixel value) that are identified as non-salient should have very little effect on the output. This idea appears in many saliency methods (and evaluation metrics), including Shapley values and mask-based explanations. (NB: detractors point out that typically the circuit was not trained using such partial assignments. But in practice trained circuits gives meaningful outputs on partial assignments.)  Now we mathematically formalize this.

\begin{definition}(Partial assignments) \label{def:partialassign} A {\em partial assignment} $(\pi, S)$ {\em consistent with input $x$} consists of a subset $S$ of pixel locations and an assignment $\pi$ of values to pixels that agrees with $x$ on pixel locations in $S$ and assigns the default value to every pixel in $\overline{S}$.  The {\em size} of the partial assignment is $\abssm{S}$. If $\pi$  causes $f$ to output $a$ then it is said to {\em validate} the value $a$ {\em for} $f$ on $x$.

\end{definition}
Thus a (simplified) view of many saliency methods is that given $f, x$ and a target value $a$ they try to generate a partial assignment consistent with $x$ that validates $a$. The next definition adapts completeness/soundness terminology from logic to articulate an intrinsic notion of correctness for such a method. Note that the trivial method that declares all input coordinates as salient is complete and sound. Ideally saliency methods should be complete and sound using a smaller partial assignment.

\begin{definition}(Completeness/Soundness) \label{defn:logiccomplete}
 A saliency method is given $f, x$ and a label $a$.

 The method is {\em complete on $f, x$} if it finds a partial assignment consistent with $x$ that validates the value $f(x)$.
 The method is {\em sound on $f, x$} if it cannot find a partial assignment to validate a value $a$ different from $f(x)$.

\end{definition}
\noindent{\em Notes:} (i) Many intrinsic saliency methods yield a heat map, which can be viewed as a  partial assignment with fractions (indicating "importance") associated with coordinates of $S$. But the heatmap may not yield a satisfying assignment to the circuit. (ii) Heatmaps are problematic in an intrinsic (as opposed to human-oriented) framework because  in highly nonlinear model,  the "meaning" of fraction $0.4$ in a coordinate has different meanings depending upon the
weightings to {\em other} coordinate. The statistical framework of Section~\ref{sec:stat} will  integrate heatmaps as well.
(iii) In several existing backpropagation-like saliency methods, completeness is not assured  and the term is used in those papers to refer to a very different property: sum of saliency scores adds up to the logit associated with the label.  This property ensures "Soundness" in our sense. (iv) Conversely in mask-based saliency methods, completeness is often assured almost by definition of procedure,  and ensuring soundness takes some care (see Figure~\ref{fig:ghostandreal}) as we will later see.

\begin{figure}
	\centering
	\includegraphics[scale = 0.40]{ghostandreal2.pdf}
		\caption{Methods to find partial assignments may not be sound. (i) CIFAR10 image (ii) partial assignment consistent with it, validates label "dog" (iii) partial assignment that validates label "horse."}
		\label{fig:ghostandreal}
	\end{figure}

\iffalse Saliency typically highlights a portion of $x$ that ``explains'' the final label.
 and grey/gaussian values in the rest is like a {\em minimal} satisfying assignment to the circuit.the pixel assignment consisting of $\pi$ in the salient pixels and grey/gaussian values in the rest is like a {\em minimal} satisfying assignment to the circuit. \fi

  Thus the crux is designing sound and complete methods that find short partial assignments.  The next result shows this is computationally very difficult in general.
  Similar ideas also show the difficulty of a problem used in the popular {\em deletion} metrics used in saliency evaluation.

 \begin{theorem}(See Appendix \ref{sec:NPHardTheorem}) \label{thm:intractability}
 The following two problems are NP-hard on ReLU circuits for every constant $C_1, C_2>1$: To find  (i) a validating partial assignment $(\pi, S)$   of size at most $C_1\cdot K_1$, where $K_1$ is the size of the smallest partial assignment that validates the value $f(x)$. (ii) a set $S_2$ of size $C_2 K_2$ such that assigning grey values in $S_2$ makes the circuit evaluate to a different value than $f(x)$, where $K_2$ is the minimum size of such a set.

 \end{theorem}

Of course, NP-hardness result  only concern worst-case complexity and presumably  deep learning on natural images is not a worst-case scenario. The takeaway from  Theorem~\ref{thm:intractability} is that usual saliency methods (which do run in time polynomial or even linear in the size of the circuit) are not guaranteed to find anything remotely resembling the shortest  partial assignments  without making additional assumptions about the circuit or the class of inputs. While basing saliency methods on axiomatic characterizations
can instill some rigor, this will not imply  even approximate minimality for the  saliency maps they lead to. Part (ii) similar cautions about the difficulty of the deletion metric.

Appendix \ref{sec:backpropsalmincert} gives simple examples on which backpropagation-style saliency methods can fail to find minimal certificates or anything close to them.

\section{On benefit of TV regularization in saliency}
\label{sec:linear}

\input{table_fig/prob_curve_fig}

Past justifications for TV regularization in saliency methods focused on its ability to make heatmaps in images that look more natural to humans. But that is not an intrinsic justification. In the intrinsic framework proposed in this paper, experiments  in \Cref{sec:expers} show TV regularization helps improve soundness of the saliency method.
The current section reinforces this intrinsic benefit of TV by sketching a simple example (details in \Cref{app:linearcase})  showing how  TV helps even in
 a simple linear model ${\bm{x}} \mapsto {\bm{w}}^\top {\bm{x}}$ on non-image
input ${\bm{x}} \in \mathbb{R}^d$ with binary label $y \in \{\pm 1\}$.

Suppose that the classifier has margin at least $\gamma > 0$, that is,
$y {\bm{w}}^\top {\bm{x}} = \sum_{i=1}^{d} y w_i x_i \ge \gamma$.
We focus on saliency methods that can return a binary heatmap $\bm{m} \in \{0, 1\}^{d}$ to certify the label,
where the coordinates marked as $1$ constitute a set $S$ of saliency coordinates.
Let $\Gamma(x, \bm{m})$ be the input modification process that assigns $0$ to all input coordinates outside the corresponding saliency set $S$.

\looseness-1
Consider an input $x$ such that ${\bm{w}}^{\top} {\bm{x}} > 0$ and $y=1$.
Firstly note that any set $S$ of coordinates that contribute positively to ${\bm{w}}^\top{\bm{x}}$,
i.e., the {base metric} $g(x, y, \bm{m}) := \onec{\sum_{i \in S} w_i x_i > 0}$ is $1$, will be able to certify the label $y=1$ and thus would satisfy {\em completeness}.
However this might not be convincing to a user, since it is also possible to come up with a set $S'$ that certifies the label $y=-1$ by picking only negative coordinates of $x$.
This would not satisfy {\em soundness} as the original model only predicts $y=1$.

This issue of soundness can be solved by adding a regularization or constraint on the set of allowable maps, in a way that ensures that it is easy to find a mask $\bm{m}$ for the correct label $y$, but not for $-y$.
Ideally, the constraints should be task-specific, but for linear classification with no special structure, even a TV constraint after random permutation suffices.
We consider the constraint that salient sets $S$ should be an interval; this corresponds to $\mathrm{TV}(\bm{m}) \le 2$.
The following result shows that if we further constrain the length of intervals to be $\Theta(\frac{1}{\gamma^2} \log d)$, then with high probability, we can find an interval certifying the model prediction $y$ but we are unable to do the same for $-y$
(Details in \Cref{app:linearcase}.)
\begin{restatable}{theorem}{thmlinear} \label{thm:int1}
	For $({\bm{x}}, y) \in \mathbb{R}^d \times \{\pm 1\}$ with $\normtwosm{{\bm{x}}}=1$, after random shuffling of the coordinates, the following holds for any $L_1 = \Omega(\frac{1}{\gamma^2} \log \frac{1}{\delta})$,
	$L_2 = \Omega(\frac{1}{\gamma^2} \log \frac{d}{\delta})$:

	\begin{enumerate}
		\item (Completeness) With probability $1 - \delta$, there is an interval $\bm{m}$ of length $L_1$ s.t.~$g(x, y, \bm{m}) = 1$;
		\item (Soundness)  With probability $1 - \delta$, $g(x, -y, \bm{m}) = 0$ holds for all intervals $\bm{m}$ of length $L_2$.
	\end{enumerate}
\end{restatable}
Although this example is simple, the conceptual message is clear:
saliency methods may not guarantee soundness in itself,
but adding regularity constraints such as TV can improve soundness.

\section{Mona Lisa smile phenomenon}
	{\sc this section shows existence of short sufficient certificates, in a statistical sense.}

	Imagine that $\mathcal{X}$ is the set of real images of cats and dogs. We see every image ${\bm{x}} \in \mathcal{X}$ as a vector in $\mathbb{R}^d$ and we use $x_i$ to denote the value of the $i$-th pixel of ${\bm{x}}$. The ground truth for an image ${\bm{x}}$ is denoted by $g({\bm{x}}) \in \{\pm 1\}$, where $1$ stands for the cat and $-1$ stands for the dog.

	Together with the ground truth $g({\bm{x}})$, we also assume that there is a ground truth explanation: for each image ${\bm{x}}$ the explanation consists of a subset of pixels and the assignment of values to them in ${\bm{x}}$, and it is sufficient for a human to consider ${\bm{x}}$ as an image in the class $g({\bm{x}})$ if he/she only sees the subset of pixels $S$ in ${\bm{x}}$.
	Formally the explanation for an image ${\bm{x}}$ is a tuple $\pi^*({\bm{x}}) := (S({\bm{x}}), {\bm{x}}[S({\bm{x}})])$, where $S({\bm{x}}) \subseteq [d]$ and we use ${\bm{x}}[A]$ to denote the matrix whose entry at $(i, j)$ is $x(i,j)$ if $(i, j) \in A$ and $0$ otherwise. One could in principle estimate this explanation using human studies.

	\kaifeng{$0$ here can be replaced by any other number. Maybe $-1$ or $\infty$ is better because they are out of the range of valid pixel values.}

	In traditional logic, where inputs are bit strings and the classifier is a boolean function these would be min-terms, and the function can be written as OR of these.

	\begin{assumption} \label{ass:overlap}
		For almost all ${\bm{x}}$, ${\bm{x}}'$ that have different labels, their explanations have small overlap. That is, for all ${\bm{x}}, {\bm{x}}' \in \mathcal{X}$, if $g({\bm{x}}) \ne g({\bm{x}}')$, then \[
			\frac{\sum_{i \in S({\bm{x}}) \cap S({\bm{x}}')} \onec{x_i \ne x'_i}}{\min\{\abs{S({\bm{x}})}, \abs{S({\bm{x}}')}\}} < p,
		\]
		where $p \in [0, 1)$ is some threshold value depending on the task.
	\end{assumption}

	\kaifeng{I replaced ``For almost all ${\bm{x}}_1$, ${\bm{x}}_2$'' by ``For all ${\bm{x}}_1$, ${\bm{x}}_2$'' for simplicity.}

	\begin{theorem}
		Under \Cref{ass:overlap}, for any set of images $\mathcal{T} \subseteq \mathcal{X}$, we can choose $\hat{S}({\bm{x}}) \subseteq S({\bm{x}})$ for each ${\bm{x}} \in \mathcal{T}$, such that $\abssm{\hat{S}({\bm{x}})} \le O(\log\abssm{\mathcal{T}})$ and for all ${\bm{x}}, {\bm{x}}' \in \mathcal{T}$, if $g({\bm{x}}) \ne g({\bm{x}}')$, then ${\bm{x}}[\hat{S}({\bm{x}})] \ne {\bm{x}}'[\hat{S}({\bm{x}})]$.
	\end{theorem}
	\begin{proof}
		We can prove via probabilistic method. For every ${\bm{x}}$,
		\begin{itemize}
			\item Initilize $\hat{S}({\bm{x}}) \gets \varnothing$;
			\item Repeat the following for $K := \left\lceil\frac{\log \abssm{\mathcal{T}}}{\log(1/(1-p))}\right\rceil$ times:
			\begin{itemize}
				\item Randomly select an element in $S({\bm{x}})$;
				\item Add the selected element to $\hat{S}({\bm{x}})$ if it is not present.
			\end{itemize}
		\end{itemize}
		For every ${\bm{x}}' \in \mathcal{T}$ with a different label, by \Cref{ass:overlap}, the probability of having ${\bm{x}}[\hat{S}({\bm{x}})] = {\bm{x}}'[\hat{S}({\bm{x}})]$ is no greater than $(1-p)^{K} < \frac{1}{\abssm{\mathcal{T}}}$. Taking the union bound, we know that
		\[
			\Pr\left[\exists {\bm{x}}' \in \mathcal{T}: g({\bm{x}}) \ne g({\bm{x}}'), {\bm{x}}[\hat{S}({\bm{x}})] \ne {\bm{x}}'[\hat{S}({\bm{x}})]\right] < \frac{1}{\abssm{\mathcal{T}}} \cdot \abssm{\mathcal{T}} = 1.
		\]
		This means this algorithm can construct $\hat{S}({\bm{x}})$ that matches with the claim of the theorem with non-zero probability. So we can construct $\hat{S}({\bm{x}})$ by running this algorithm repeatedly until it succeeds.
	\end{proof}

	In particular, note that by VC theory it suffices to let T be O(net size × \# pixels).

	Consequence 1: Usual saliency methods don't need to return human interpretable
	explanations.
	(Can back this up with an analysis of logistic regression or least squares regression.)

	Consequence 2: Saliency methods also have the same limitation a priori. In other words the axiomatic approach grounded in cooperative game theory does not guarantee human- interpretable explanations.
	Proposed method to find human-interpretable explanations: Train as usual and find saliency maps. Take a class and gray out most salient pixels. For other classes gray out random pixels (or contiguous perhaps). Train a classifier to recognize the class, and find its salient pixels. Do this for a few rounds.The final map is some kind of avg of saliency maps from the rounds.
\section{Introduction}
\label{sec:intro}
{\em Why did the deep net give a certain answer on a particular input, and can we trust the answer?} {\em Saliency methods} try to provide explanations, and are thus of great interest from viewpoint of human explainability, fairness,  robustness, etc.

This  paper restricts attention to methods that
return an importance score for each coordinate of the input ---usually visualized as a  heat map--- that captures its importance to the final decision.\footnote{Heat maps suffice for recognition/classification tasks; other tasks may require more complex explanations.}
We refer the reader to \citet{samek2019explainable} for an extensive survey and Section~\ref{sec:prior} for a short account of such methods and controversies.

There are two important components in the research on saliency: {\em saliency methods} that produce such heat maps for explanations, and {\em saliency evaluation metrics} that aim to test and compare  saliency methods.
Numerous saliency methods have been proposed to learn such heat maps.
Some methods learn maps through ``credit attribution'' to individual input coordinates by using methods reminiscent of backpropagation \citep{binder2016layer,selvaraju2016grad}, while some are derived using careful axiomatization of credit assignment using the idea of Shapley values from cooperative game theory \citep{lundberg2017unified,yeh2020completeness}.
Some recent methods  train another deep net to produce  heat maps \citep{dabkowski2017real,phang2020investigating}.
Given the proliferation of saliency methods, an ecosystem of evaluation metrics has emerged to  evaluate the quality of explanations produced by saliency methods, either through human evaluations \citep{adebayo2018sanity}, comparison to certain ground truth explanations \citep{zhang2018top} or other evaluations that do not require any external annotation or supervision \citep{dabkowski2017real} \citet{petsiuk2018rise}.

In this paper we restrict attention to a class of evaluations we refer to as
{\em intrinsic}, that aim to evaluate saliency maps based on whether they are good explanations for the model prediction.
These only involve computations using the provided heat map and the net, and do not involve extrinsic factors such as human judgements or retraining.  A popular idea in such evaluations (see \Cref{sec:stat} for references) is to create a new composite input ---or sequence of such inputs--- using the heat map and the original input, and to evaluate the original net on this composite input. For example, if $M$ is a binary vector with $1$'s in the $k$ coordinates with the highest values in the heat map, then $x \odot M$ (with $\odot$ denoting coordinate-wise multiplication) can be viewed as a composite input\footnote{When $x$ is an image the zeroes in this masked input are often replaced with gray values.} (aka ``masked input'') that can be fed into the original net. By varying $k$ one obtains a sequence of masks $M$.
Although there is an issue of distribution shift due to the net never having trained on composite inputs, in practice, especially for image data, trained nets work fine on masked inputs. (This is also exploited in Shapley value based saliency methods.)

Inspired by logical reasoning, we identity a key component missing in existing {\em intrinsic evaluations}: {\em soundness} of the saliency method.
In simple terms, checking soundness for mask-based explanations entails verifying that it is impossible for the method to produce well-performing (in the composite-input evaluations) heat maps corresponding to the {\em incorrect}
labels, i.e. labels not predicted as the most likely by the model.
By contrast current masking evaluations focus on a property akin to {\em completeness}\footnote{In the literature devoted to saliency methods based upon backpropagation-like procedure, such as {\sc Gradient $\odot$ Input} or LRP, the term {\em completeness} is used in a slightly different sense: the sum of the heat map values has to be equal to the logit value for the label.} in logic: the heat map ``justifies'' the correct label, i.e. the label judged to be most likely by the model.
We argue that soundness can be a useful criterion in addition to completeness.

\revise{The concept of soundness is motivated by observing that the recent mask-based saliency methods are inherently different from the earlier gradient-based methods.
They produce a heatmap that is interpreted as a masked image that, when fed into the net must make it output the same label that received the top logit value on the full image.
Our paper observes that it is unclear at a logical level why this should be considered an ``explanation'', since to be convinced one must verify that a different mask could not induce the net to output a label corresponding to other logits.
\Cref{fig:artifact-small} shows that in fact this issue is real; masks do exist that can ``justify'' the wrong labels.
We introduce soundness as a quantitative measure for this issue (definitions in \Cref{sec:completeness_and_soundness}), and propose that evaluations of mask-based saliency methods should account for soundness.}
Many past works allude to difficulty of the soundness concept, mentioning that computations to find the ``best" mask end up finding artifacts that can even justify labels that are obviously incorrect.
To avoid uncovering artifacts, the methods to find masks/heat maps use a suitable regularization (usually TV).
However, \Cref{fig:artifact-small} illustrates that TV regularization is not a full solution to removing artifacts.

Another reason for incorporating soundness with completeness in metrics is to implicitly encourage saliency methods to also produce saliency maps for incorrect labels.
When using the classifier in the wild---as opposed to on a dataset with centered images--- we might encounter multiple salient objects in the image, and the net may not have high confidence in a single label.
It would then be reasonable to have saliency methods find evidence for all the labels which the net outputs with reasonable confidence.
\revise{We find in \Cref{fig:elezeb} that our saliency method that produces masks for all labels can produce different and meaningful masks for different labels when there are multiple objects present in the image\footnote{\revise{In this paper, multiple objects in one image is not formally considered, as we assume single object classification is the prior knowledge. Therefore, either zebra or elephant in \Cref{fig:elezeb} is regarded as an incorrect label. A quick extension to the multi-object case is to define correct labels as the labels whose model probability exceeds a certain threshold.
Even without the extended definition of correct labels, \Cref{def:soundcompletestat} with suitable $\alpha, \beta$ already allows explanations to exist for both elephant and zebra as long as the model probability for elephant and zebra are high enough.} }, compared to prior state-of-the-art methods, that output a single mask for all labels that contains both objects (more on this in \Cref{sec:elezeb}).}

\iffalse
The soundness issue in practice is illustrated in \Cref{fig:artifact-small} using CIFAR-10 images.  For both images, a simple saliency method (\Cref{sec:procedures}) can be used to construct masked inputs that can cause the classifier net to output the incorrect label (w.r.t. model prediction) with significant probability, in addition to constructing a good mask for the correct label.
The soundness condition we suggest requires that the acceptance probability on composite input should not grossly outstrip the acceptance probability on the unmasked input; see Section~\ref{sec:completeness_and_soundness} for precise definitions.
\fi

\iffalse

\ns{this next paragraph seems somewhat orthogonal to the current story, perhaps not required here?.}
\myparagraph{Difficulties in defining/evaluating saliency: a taste.}
We give an example to illustrate the difficulties in this field.
Suppose the net's input consists of bit strings,  and it outputs $1$ iff at least $4$ input bits are $1$. (This is a toy example of a concept that can be recognized if at least $4$ out of $9$ features are present.) What should be the saliency map for an input in which $9$ bits are $1$? Logically speaking,  highlighting any $4$ bits that are $1$ is enough to justify the answer of $1$. {\em Shapley values} would give equal saliency to all $9$ bits that are $1$. (For simplicity we ignore  complicated Shapley variants.)

Backpropagation-like methods can give a variety of answers depending upon their details (See \Cref{sec:backpropsalmincert} \kf{need to reword there because this section does not support this directly}), and the final saliency map often depends upon how the net implemented its functionality (as opposed to just the input-output behavior). Various evaluations also have disparate expectations of when a map is good. For instance ROAR evaluation~\citep{hooker2019benchmark}, which is intrinsic, would reject maps containing fewer than six $1$'s, because it zeroes out (or greys out in case of image data) coordinates identified as most salient,  and checking if the answer on the modified input became $0$.
\fi
\begin{figure}[t!]
\begin{subfigure}{.5\textwidth}
    \centering
    \includegraphics[width=0.95\textwidth]{ghost_small.png}
\end{subfigure}

\begin{subfigure}{.5\textwidth}
    \centering
    \includegraphics[width=0.95\textwidth]{ghost_small_bird_frog.png}
\end{subfigure}
    \caption{Masked CIFAR-10 images generated by our procedure with $\lambda_{TV} = 0.01$ shows the artifacts exist for masks generated for incorrect labels. More examples can be find in \Cref{fig:artifact} in Appendix. The base classifier outputs the correct label on the original image (ship and bird resp.) with probability at least 0.99, and assigns probability at most $10^{-5}$ for the incorrect label (cat and frog resp.). With the generated masks, the AUC metric for the correct label remains high (around 0.94 and 0.90), which corresponds to {\em completeness}, but AUC metric for the incorrect label rises tremendously (around 0.18 for cat mask, 0.71 for frog mask.) This suggests violation of {\em soundness}. }
    \label{fig:artifact-small}
    \vspace{-0.2in}
\end{figure}

\iffalse
\ns{
we can take any method and make it sound

language: $(x,f(x))$, prover: saliency method, verifier: any standard metric like AUC, proof: for any $(x, a)$ it is the mask $M(x, a)$

$M$ is an algorithm that runs on $(x, a)$.

our goal here is to evaluate a prover (or prover family)

completeness: whenever $a = f(x)$, the verifier (AUC score) should get high probability when the proof $M(x,a)$ is used.

soundness: whenever $a \neq f(x)$, then what??

ideally the prover should try to give the best proof for any $(x, a)$ that it can, and that shouldn't be good enough to prove when $a \neq f(x)$.
suppose the best algorithm was used to find the proof $M(x,a)$, then completeness and soundness are actually evaluating a metric rather than method.
checking if a metric is sensitive enough to be able to match the networks predictions. but again there is a cheating method which is to output $f(x)$ itself. so why are masks relevant?
}
\fi

\begin{figure}[htbp]
	\centering
	\vspace{-0.2in}
	\includegraphics[width=0.5\textwidth]{elephant-zebra.png}
	\caption{Images containing both elephant(s) and zebra(s), and the corresponding masked ones generated by our method and the best-performing CA model in \citet{phang2020investigating}. The masks by \citet{phang2020investigating} are identical for different labels, and contains both elephant and zebra. In contrast, our method outputs descent masks for elephant and zebra accordingly.  }
	\vspace{-0.1in}
	\label{fig:elezeb}
\end{figure}

	\vspace{-0.1in}
\myparagraph{Main contributions:}
\revise{
In this paper we make a case for pushing saliency methods and metrics to incorporate soundness in addition to completeness.
We propose metrics and a method and experimentally evaluate them in comparison to previous methods and metrics, leading to some novel findings.
Our main contributions are as follows:
}

	\vspace{-0.1in}
\begin{itemize}[leftmargin=*]

    \item A new single number metric named {\em consistency score{}} that evaluates the completeness and soundness simultaneously. It measures the probability that the saliency map for the model prediction has the best quality compared to all other labels. See \Cref{sec:consistency-score} for a formal definition.

    \item A saliency method in \Cref{sec:procedures} that bears similarity to prior works that learns masks through optimization, but with subtle differences.
    One of the differences is based on the logic of soundness: we learn a mask by trying to maximize the probability for the given label, rather than matching the probability, and learn the {\em best mask} for all labels this way.
    \revise{We find in experiments (\Cref{sec:expers}) that our method not only performs comparably to prior masked-based methods on earlier saliency metrics, but also does better than those methods on the proposed consistency score.}

    \item Previous works proposed ``tricks'' like TV penalty and upscaling of masks \citep{fong2017interpretable,dabkowski2017real} that are motivated by their ability to avoid ``artifacts'' and make the saliency maps visually look better.
    These justifications, however, are not in the spirit of an intrinsic evaluation of saliency maps.
    In this paper, we provide a novel {\em intrinsic} justification for these choices of TV penalty and upscaling, by showing that they improve the saliency maps by making them more sound, as empirically demonstrated in \Cref{sec:expers}.
    We complement this finding with a theoretical result in \Cref{sec:linear} that proves that TV regularization can help with soundness in a simple linear classification setting.
\end{itemize}

	\vspace{-0.1in}
\myparagraph{Paper outline:} \Cref{sec:prior} discusses prior works on saliency methods and evaluations. \Cref{sec:stat} delves further into the concept of completeness and soundness in the context of saliency evaluation, and describes our proposed metric of consistency score{}. \Cref{sec:procedures} describes our saliency method and how it differs from prior approaches. Finally \Cref{sec:linear} describes various supportive experiments.

	\vspace{-0.1in}

\begin{comment}
{\em Why did the deep net give a certain answer on a particular input?} {\em Saliency methods} try to provide explanations, and are thus of great interest from viewpoint of human explainability, fairness,  robustness, etc..\

This  paper restricts attention to methods that
return an importance score for each coordinate of the input ---usually visualized as a  heat map--- that captures its importance to the final decision.\footnote{Heatmaps suffice for usual recognition/classification tasks, but other ML tasks might require more complex explanations.}
See \citet{samek2019explainable} for an extensive survey
and Section~\ref{sec:prior} for a short account of methods and controversies. It will be good to differentiate between {\em saliency methods} ---which produce the heat map--and the {\em evaluations} of such methods.

The first class can be thought of as {\em intrinsic methods}: they explain the basis of an ML model's decision  by diving inside the model's computation to tease out the coordinates in the input that were most ``salient'' to the output. Doing so relies upon some {\em a priori} mathematical definition of each coordinate's ``contribution'' to the final output. Many intrinsic methods are reminiscent of backpropagation  and do "credit contribution" to each coordinate of the input roughly guided by gradient of the output with respect to the input. Some  intrinsic methods (a notable example being those relying on Shapley values from cooperative game theory) are derived from a careful axiomatization of credit attribution.

We refer to the second class of saliency methods as {\em human-oriented}: they avoid an {\em a priori} notion of ``contribution'' of individual coordinates of the input, and focus on
producing human-interpretable {\em localization} of the portion  of the input germane to the output label. Recent successful methods (descended from a long tradition in computer vision) even end up  training another deep net (!) to use the classifier to compute a human-interpretable heat-map of the image regions that explain the output. Such methods do very well on a host of evaluation benchmarks, including their ability to mimic human-generated explanations.

The current paper's ideas belong philosophically in the intrinsic tradition:  saliency of coordinates is defined via mathematical/logical notions that only reference the trained model.

\iffalse
But the underlying concept of a partial assignment is very close to the masking-based concepts popular in human-oriented methods and shares their utility. We hope our formalization ---as well as supporting experiments and theory highlighting its properties--- begins to bridge the two classes of work.
\fi

\myparagraph{Ground truth versus maximal labels versus target label.}
We evaluate both on images which the model classifies correctly, and those that it missclassifies.  Many saliency methods assume the ground truth label may not be available at test time, and we follow suit.

\myparagraph{Defining Instrinsic Saliency.}
The goal of extrinsic saliency is to highlight some relevant portion of the original input image. Given an orignal image, $X$ and a mask $M$, one can construct an image with super-imposed mask $X \odot M$ that a user may use to understand why the model made a particular decision.
Intrinsic saliency, on the other hand, disregards use to the user, and instead has the goal of explaining a model's decision. Hence, if a model is confident on some logit $s_y$, i.e. $s_y$ is reasonably large, the saliency method should return a map certifying the value  $s_y$ (i.e. such that $f(X \odot M)$ is reasonably large). On the other hand, if $s_{y'}$ is small for some other logit, then the saliency method should not be able to find a mask $M'$ such that $f(X \odot M')$ is larger than $s_{y'}$.  If it does, then the saliency method may be explaining a belief that the model doesn't have, which would make us suspicious of its explanations in general.

\myparagraph{Evidence of artifacts.}
Several previous works have noted the effect of mask artifacts. \citet{fong2017interpretable} noted that in an image of a maypole, the imposed mask may draw an irregular shape in the sky. \citet{dabkowski2017real} note that masks may have 'adversarial' artifacts, consisting of a few pixels that go unnoticed to humans but could destroy the model prediction. \\
Our understanding of artifacts, different from previous approaches, extends to the wrong label. Specifically, we find that un-regularized masks can be so powerful as to construct a phantom certificate for the wrong label (where $s_{y'}$ is small) such that $X \odot M'$ is large, and the resulting mask is non-trivial (consists of more than a few pixels, and can even resemble another image class.)

Motivated by the previous observation, we consider saliency methods that learn a mask (and hence do not automatically satisfy completeness.) We introduce the notion of \emph{soundness}, that a masking method should not be able to construct a convincing explanation for the wrong label.

We use this notion both to evaluate existing saliency methods, and to explain intrinsically various heuristic tricks that previously had only extrinsic explanations.

\myparagraph{Difficulties in working on intrinsic methods.}
A simple example can illustrate the difficulties in defining saliency  from first principles, which intrinsic methods need to.
Suppose the net's input consists of bit strings,  and it outputs $1$ iff at least $4$ input bits are $1$. What should be the saliency map for an input in which $9$ bits are $1$? Logically speaking,  highlighting any $4$ bits that are $1$ is enough to justify the answer of $1$. {\em Shapley values}, a concept from cooperative game theory, would give equal saliency to all $9$ bits that are $1$. (For simplicity we ignore here more complicated Shapley variants.)
Backpropagation-like methods can give a variety of answers depending upon their details (See \Cref{sec:backpropsalmincert}), and  the final saliency map often depends upon how the net implemented its functionality (as opposed to just the input-output behavior).  The ROAR evaluation~\citet{hooker2019benchmark} would reject  maps containing fewer than six $1$'s, because it zeroes out (or greys out in case of image data) coordinates identified as most salient,  and checking if the answer on the modified input became $0$.

\iffalse

Main idea is that implicitly designers of saliency methods have been thinking of the salient portions identified in the input as a sufficient justification for the label output by the net. In other words, if $x$ is the input, and $\pi$ gives the locations and values of its most salient pixels then the pixel assignment consisting of $\pi$ in the salient pixels and grey/gaussian values in the rest is like a {\em minimal} satisfying assignment to the circuit.
\fi

\myparagraph{Why we focus on masking methods.}
We define masking methods similarly to \citet{phang2020investigating}; a method that attempts to learn a mask $M$ given a model $f$ and input(s) $X$. Some simple methods like LRP and Gradient $\odot$ Input for ReLU networks with no bias satisfy completeness and soundness already. However, masking methods are considered state of the art, and our focus in this work is assessing the extent to which these satisfy soundness.

\myparagraph{Our Contributions.}
a) We introduce and motivate soundness. Since a mask-based saliency map can be viewed as a portion of the input that "certifies" the correctness of the net's output, we can view this certificate as part of a probabilistic proof system. This motivates notion of completeness (which has been discussed in previous works) and our new contribution of soundness for the saliency map.
b) Provide a new metric (i.e., a single number) for mask-based saliency methods, which can be used to compare methods. Evaluating this metric gives new insights into efficacies of current saliency methods.
c) We advocate for methods and evaluations for mask-based saliency  that are intrinsic ---use just the training dataset and the trained net, and does not use separately trained nets, distractor distributions, human evaluations etc. To this end, we introduce a new saliency method that does not require additional training of infillers and is fairly simple as well.
\iffalse
We view the classifier as a circuit acting on the input.
A central idea is a notion of saliency that involves  partial assignments that validate the label output by the circuit. This is an intrinsic notion, but  very analogous to popular {\em mask-based} explanations in the human-oriented category. (a) Sections~\ref{sec:logic} views partial assignments as precise logical concepts and defines {\em completeness} and {\em soundness} for procedures that find them. Existing saliency methods focus on at most one of these two notions, whereas both are needed.  Section~\ref{sec:stat} extends the framework to statistical learning and relates completeness and soundness to existing evaluation metrics. (b) Section~\ref{sec:logic} shows that even finding weak approximations to short partial assignments (or to deletion metrics) is computationally intractable (i.e., NP-hard) for general circuits.
A takeaway from this, which may  guide future work on intrinsic saliency, is that there will not be a magical  axiomatization for a coordinate's "contribution" to the output that will also lead to efficient procedures generating succinct saliency maps. One could settle for heuristics for real-life circuits and data distributions too.
(c) Motivated by (b), we give concrete examples of circuits where saliency maps derived from existing saliency methods give no clue to what the minimal satisfying assignment is
(Section~\ref{sec:logic}). (d) Procedures for finding saliency maps using the notion of partial statistical assignment in real-life deep nets (Section~\ref{sec:procedures}). Again, these are close to masking-based methods with some subtle differences.  (e) Experiments on popular deep architectures trained on the usual datasets (CIFAR and ImageNet) illustrating properties of the partial assignments discovered by our procedure. In particular, we show that the TV regularizer (ubiquitous in computer vision) and the upsampling trick serve to make our procedure satisfy soundness condition. (f) Section~\ref{sec:linear} uses simple linear models to illustrate and explain the  above framework, including the provable role of TV regularizer for ensuring soundness even in non-vision setting.
\fi

\paragraph{Differences from previous work} We do not try to match the probability. Instead we maximize it, due to soundness.

\end{comment}
\section{Introduction}
\label{sec:intro}
{\em Saliency methods} are a tool toward explainability, fairness,  robustness, etc. in deep learning. They are designed for two main goals: ({\bf Goal a}) {\em Understand why the deep net gave a certain answer on a particular input.} ({\bf Goal b}) {\em Convince a human overseer that the decision was correct}. The two goals can be somewhat contradictory, since the inner workings of a deep net may map poorly to human intuition. Not surprisingly, this is the source of many controversies \ns{some other term?} within the field about the very definition of saliency \ns{citation}.

This paper restricts attention to Goal (a), and furthermore, to  the (large) class of saliency methods that
return an importance score for each coordinate of the input ---often visualized as a  heat map--- which captures the coordinate's importance to the final decision.\footnote{Heat maps suffice for recognition/classification tasks; other tasks may require more complex explanations.}  Early saliency methods, primarily motivated by Goal (a),  constructed such maps through an axiomatic system of ``credit attribution'' to individual input coordinates. Some involve backpropagation-like methods \citep{binder2016layer,selvaraju2016grad}, while others  use notions from cooperative game theory, such as Shapley values~\citep{lundberg2017unified,yeh2020completeness}. See \Cref{sec:prior} and \citet{samek2019explainable} for discussion of strengths and limitations of such methods. It seems generally accepted that while these methods pick up on some signal (with respect to which coordinates are most salient), they also pick up on a lot of noise \ns{citation needed}, which limits their usefulness for Goal (b).
Thus more recent methods try to find heat maps that are largely concentrated on a smaller set of pixels/coordinates.

Concurrently, an ecosystem of {\em evaluation metrics} has also sprung up to  evaluate saliency methods. These include  human evaluation \citep{adebayo2018sanity}, and comparison to certain ground truth explanations \citep{zhang2018top}. The current paper restricts attention to
{\em intrinsic} evaluations, by which we mean that evaluation uses computations involving the net itself and the heat/saliency map --- but no human evaluations or evaluations that involve training new nets. Popular intrinsic evaluations include {\em saliency metric}~\citep{dabkowski2017real} and RISE~\citep{petsiuk2018rise} \ns{Is RISE a metric or method?}.

A frequent idea in intrinsic evaluations (see \Cref{sec:stat} for references) is to create a new composite input --- or sequence of such inputs --- using the heat map and the original input, and to evaluate the original net on this composite input. For example, if $M$ is a binary vector with $1$'s in the $k$ coordinates with the highest values in the heat map, then $x \odot M$ (with $\odot$ denoting coordinate-wise multiplication) can be viewed as a masked input where only $k$ of the original coordinates of $x$ remain. (It is also popular to replace the  zeroes in this masked input with ``uninformative'' values, such as gray pixels or noisy pixels.)
This masked input is fed into the original net to check if the net outputs the same label as on the full input --- and if so one should conclude that the unmasked coordinates of $x$ were salient to the net's output.
 This raises a potential issue of distribution shift because the net never was never trained on masked inputs. In practice, especially for image data, trained nets continue to work fine on masked inputs. (This fact is also exploited in saliency methods based upon Shapley values. \ns{citation}) Not surprisingly, recent methods for finding heatmaps use an objective that tries to directly optimize performance on such evaluations, such as ~\citep{fong2017interpretable,dabkowski2017real,phang2020investigating}, greatly outperforming older saliency methods.

 {\em Should we trust such mask-based explanations}? At first sight, this question may appear naive. In the above-described masked input
 $x \odot M$, some $k$ pixels were copied from the original image and the remaining pixels were made clearly \textquotedblleft uninformative\textquotedblright.
 Since the original net outputs essentially the same label as it did on the full image, then does this not {\em prove} that the portion that came from the mask $M$  must have {\em caused} the net's output on the full image?  The answer is \textquotedblleft No\textquotedblright, because the positions of the uninformative pixels can carry some signal.
 Many papers have noted that  optimization methods for finding subsets of salient coordinates find \textquotedblleft masks with artifacts\textquotedblright\ that look simply wrong to the human \ns{citation}.
 Indeed, we can report that in standard evaluation datasets,  it is possible to create masks out of most inputs such that the masked input  elicits high probability for a different  label from the original net prediction; see \Cref{fig:artifact-small}.  Prior works  suggested using total variation (TV) regularization while finding the masks to make them align better with human intuition, but \Cref{fig:artifact-small} shows TV regularization is not a full solution to masks that cause the net to flip the label.

\noindent{\bf Needed: Soundness.} The masked input method is trying to {\em prove} that a certain portion of the image  \textquotedblleft caused\textquotedblright\ the net's output.  Usually logical reasoning must display both {\em completeness} (i.e., all correct statements are provable) and {\em soundness} (incorrect statements cannot be proved). Checking that the net's output is essentially unchanged when switching from the full input to  the  masked input is akin to verifying {\em completeness}\footnote{Works on backprop-like saliency methods, e.g., {\sc Gradient $\odot$ Input} or {\sc lrp}, use {\em completeness} in a slightly different sense: the sum of the heat map values has to be equal to the logit value for the label. This is also motivated by the corresponding term in logic.}. But this by itself should not be convincing because, as mentioned, it is possible to use the method to find a different mask to justify another (i.e., wrong) label.   {\em Soundness}  would require verifying that the same saliency method cannot be used to produce masked inputs that make the net output a different label.

\ns{This paragraph seems a bit misplaced here} Our view of salient pixels as \textquotedblleft proofs\textquotedblright\ of the label is termed in \citet{dabkowski2017real} as {\em Smallest Sufficient Region (SSR)} notion of saliency. They as well as~\cite{fong2017interpretable} report it to be susceptible to artifacts.  Consequently they incorporate the {\em Smallest Destroying Region (SDR)} notion:   pixels identified as most salient should be made uninformative and then one should check that the net assigns low probability for the label.   We  found soundness difficult to verify on SDR-based methods (Section~\ref{sec:expers}).
The SDR notion of saliency is also implicit in many saliency evaluations,  including ROAR evaluation~\citep{hooker2019benchmark} and the Deletion Game described in Section~\ref{sec:expers}.

\iffalse {\sc does following para makes sense here? else can remove it.}

Some existing evaluations like {\em ROAR}~\citep{hooker2019benchmark} indirectly address soundness  by {\em graying/noising} the pixels deemed most salient and then finding another heat map for this new input. This is repeated until no signal remains in the input ---i.e., a fresh net trained on these partially noised images cannot detect any evidence of the correct label. But note that this makes ROAR  a {\em non-intrinsic} evaluation since it involves training new nets. Furthermore, such evaluations use a subtly different notion of saliency: saliency map ends up having to include {\em all} information pertinent to the classifier's chosen label, rather than the smaller subset that was {\em sufficient} to determine the correct label

\fi

\begin{figure}[t!]
    \begin{subfigure}{.5\textwidth}
        \centering
        \includegraphics[width=0.95\textwidth]{ghost_small.png}
    \end{subfigure}%
    \begin{subfigure}{.5\textwidth}
        \centering
        \includegraphics[width=0.95\textwidth]{ghost_small_bird_frog.png}
    \end{subfigure}
    \caption{Masked CIFAR-10 images generated by our procedure with TV regularization of strength $\lambda_{TV} = 0.01$ \ns{$\lambda_{TV}$ is undefined}.
    Artifacts exist for masks generated even for incorrect labels; more examples can be found in \Cref{fig:artifact} in Appendix. The base classifier outputs the correct label on the original image (ship and bird resp.) with probability at least 0.99, and assigns probability at most $10^{-5}$ for the incorrect label (cat and frog resp.). With the generated masks, the AUC score \ns{AUC is undefined} for the correct label remains high (around 0.94 and 0.90), which corresponds to {\em completeness}, but AUC metric for the incorrect label rises tremendously (around 0.18 for cat mask, 0.71 for frog mask.) This suggests violation of {\em soundness}. }
    \label{fig:artifact-small}

\end{figure}

\begin{figure}[htbp]
	\centering
	\vspace{-0.1in}
	\includegraphics[width=0.45\textwidth]{elephant-zebra.png}
	\vspace{-0.1in}
	\caption{Images containing both elephant(s) and zebra(s), and the corresponding masked ones generated by our method and the best-performing CA model in \citet{phang2020investigating}. The masks by \citet{phang2020investigating} are identical for different labels, and contains both elephant and zebra. In contrast, our method outputs decent masks for elephant and zebra accordingly. For more examples please see \Cref{fig:2label} in \Cref{sec:additionalimagenette}.  }
	\vspace{-0.1in}
	\label{fig:elezeb}
\end{figure}

\noindent{\bf Main Contributions of this paper:}
\vspace{-0.1in}
\begin{itemize}[leftmargin=*]
\setlength\itemsep{0em}
\item By differentiating  {\em intrinsic} versus {\em extrinsic} evaluations (i.e., Goal (a) vs Goal (b))  the paper clarifies how to think about mask-based saliency methods. \ns{Is Goal (b) really extrinsic? It could be viewed as a goal of an intrinsic evaluation. Soundness, for instance, can also convince a human evaluator to some extent.}
\item \Cref{sec:completeness_and_soundness} draws connections to logical proof systems and formalizes completeness and soundness in the context of saliency methods.
These are intrinsic evaluations of saliency without needing to appeal to human judgements (e.g., whether or not machine-generated masks contain artifacts).  \Cref{sec:consistency-score} introduces  {\em consistency score{}}, a single number that incorporates both completeness and soundness.
\item \Cref{sec:procedures} revisits methods that learn masks through optimization.
Incorporating soundness, we propose a simple optimization method that maximizes the probability for any given label, rather than only the label deemed most likely by the net. \ns{citation for the other paper that does this.}
\ns{The next part about time complexity can be moved to future sections.} While this makes computation cost proportional to the number of labels,  note that this cost is only incurred while designing/evaluating the saliency method. Verification of soundness can be omitted at deployment time. (Another alternative is to verify soundness condition for top $k$ labels.)
\item  Experiments (in \Cref{sec:expers}) estimate completeness and soundness scores for various methods. (soundness evaluation can be vacuous for some.)
Our simple method does strongly with respect to completeness and soundness as one would expect, but the slight surprise is that it performs comparably to prior masked-based methods on earlier saliency metrics as well, suggesting that soundness can be achieved without paying much in completeness.

 \item

  Heuristic choices in existing mask-based methods such as  TV regularization and upsampling, which were hitherto justified extrinsically (i.e., they make masks look natural to humans), receive  an {\em intrinsic} and precise justification: they improve soundness.
   A theoretical result in \Cref{sec:linear} complements this experimental finding by showing that TV regularization helps saliency methods even in a simple linear classification setting, not just for vision data.
   \item Another reason for incorporating soundness in evaluations is to encourage saliency methods to react gracefully when multiple labels are correct for an image, as may happen at deployment time.

   \Cref{fig:elezeb} and \Cref{fig:2label} show images where the classifier net gave overwhelming probability to  a single label even though multiple objects were present. Our saliency method can produce different and meaningful masks for all labels that are valid.
   \ns{Extending the notion of soundness for multi-label settings is an open question.}

\end{itemize}

	\vspace{-0.1in}

	\vspace{-0.1in}

\begin{comment}
{\em Why did the deep net give a certain answer on a particular input?} {\em Saliency methods} try to provide explanations, and are thus of great interest from viewpoint of human explainability, fairness,  robustness, etc..\

This  paper restricts attention to methods that
return an importance score for each coordinate of the input ---usually visualized as a  heat map--- that captures its importance to the final decision.\footnote{Heatmaps suffice for usual recognition/classification tasks, but other ML tasks might require more complex explanations.}
See \citet{samek2019explainable} for an extensive survey
and Section~\ref{sec:prior} for a short account of methods and controversies. It will be good to differentiate between {\em saliency methods} ---which produce the heat map--and the {\em evaluations} of such methods.

The first class can be thought of as {\em intrinsic methods}: they explain the basis of an ML model's decision  by diving inside the model's computation to tease out the coordinates in the input that were most ``salient'' to the output. Doing so relies upon some {\em a priori} mathematical definition of each coordinate's ``contribution'' to the final output. Many intrinsic methods are reminiscent of backpropagation  and do "credit contribution" to each coordinate of the input roughly guided by gradient of the output with respect to the input. Some  intrinsic methods (a notable example being those relying on Shapley values from cooperative game theory) are derived from a careful axiomatization of credit attribution.

We refer to the second class of saliency methods as {\em human-oriented}: they avoid an {\em a priori} notion of ``contribution'' of individual coordinates of the input, and focus on
producing human-interpretable {\em localization} of the portion  of the input germane to the output label. Recent successful methods (descended from a long tradition in computer vision) even end up  training another deep net (!) to use the classifier to compute a human-interpretable heat-map of the image regions that explain the output. Such methods do very well on a host of evaluation benchmarks, including their ability to mimic human-generated explanations.

The current paper's ideas belong philosophically in the intrinsic tradition:  saliency of coordinates is defined via mathematical/logical notions that only reference the trained model.

\iffalse
But the underlying concept of a partial assignment is very close to the masking-based concepts popular in human-oriented methods and shares their utility. We hope our formalization ---as well as supporting experiments and theory highlighting its properties--- begins to bridge the two classes of work.
\fi

\myparagraph{Ground truth versus maximal labels versus target label.}
We evaluate both on images which the model classifies correctly, and those that it missclassifies.  Many saliency methods assume the ground truth label may not be available at test time, and we follow suit.

\myparagraph{Defining Instrinsic Saliency.}
The goal of extrinsic saliency is to highlight some relevant portion of the original input image. Given an orignal image, $X$ and a mask $M$, one can construct an image with super-imposed mask $X \odot M$ that a user may use to understand why the model made a particular decision.
Intrinsic saliency, on the other hand, disregards use to the user, and instead has the goal of explaining a model's decision. Hence, if a model is confident on some logit $s_y$, i.e. $s_y$ is reasonably large, the saliency method should return a map certifying the value  $s_y$ (i.e. such that $f(X \odot M)$ is reasonably large). On the other hand, if $s_{y'}$ is small for some other logit, then the saliency method should not be able to find a mask $M'$ such that $f(X \odot M')$ is larger than $s_{y'}$.  If it does, then the saliency method may be explaining a belief that the model doesn't have, which would make us suspicious of its explanations in general.

\myparagraph{Evidence of artifacts.}
Several previous works have noted the effect of mask artifacts. \citet{fong2017interpretable} noted that in an image of a maypole, the imposed mask may draw an irregular shape in the sky. \citet{dabkowski2017real} note that masks may have 'adversarial' artifacts, consisting of a few pixels that go unnoticed to humans but could destroy the model prediction. \\
Our understanding of artifacts, different from previous approaches, extends to the wrong label. Specifically, we find that un-regularized masks can be so powerful as to construct a phantom certificate for the wrong label (where $s_{y'}$ is small) such that $X \odot M'$ is large, and the resulting mask is non-trivial (consists of more than a few pixels, and can even resemble another image class.)

Motivated by the previous observation, we consider saliency methods that learn a mask (and hence do not automatically satisfy completeness.) We introduce the notion of \emph{soundness}, that a masking method should not be able to construct a convincing explanation for the wrong label.

We use this notion both to evaluate existing saliency methods, and to explain intrinsically various heuristic tricks that previously had only extrinsic explanations.

\myparagraph{Difficulties in working on intrinsic methods.}
A simple example can illustrate the difficulties in defining saliency  from first principles, which intrinsic methods need to.
Suppose the net's input consists of bit strings,  and it outputs $1$ iff at least $4$ input bits are $1$. What should be the saliency map for an input in which $9$ bits are $1$? Logically speaking,  highlighting any $4$ bits that are $1$ is enough to justify the answer of $1$. {\em Shapley values}, a concept from cooperative game theory, would give equal saliency to all $9$ bits that are $1$. (For simplicity we ignore here more complicated Shapley variants.)
Backpropagation-like methods can give a variety of answers depending upon their details (See \Cref{sec:backpropsalmincert}), and  the final saliency map often depends upon how the net implemented its functionality (as opposed to just the input-output behavior).  The ROAR evaluation~\citet{hooker2019benchmark} would reject  maps containing fewer than six $1$'s, because it zeroes out (or greys out in case of image data) coordinates identified as most salient,  and checking if the answer on the modified input became $0$.

\iffalse

Main idea is that implicitly designers of saliency methods have been thinking of the salient portions identified in the input as a sufficient justification for the label output by the net. In other words, if $x$ is the input, and $\pi$ gives the locations and values of its most salient pixels then the pixel assignment consisting of $\pi$ in the salient pixels and grey/gaussian values in the rest is like a {\em minimal} satisfying assignment to the circuit.
\fi

\myparagraph{Why we focus on masking methods.}
We define masking methods similarly to \citet{phang2020investigating}; a method that attempts to learn a mask $M$ given a model $f$ and input(s) $X$. Some simple methods like LRP and Gradient $\odot$ Input for ReLU networks with no bias satisfy completeness and soundness already. However, masking methods are considered state of the art, and our focus in this work is assessing the extent to which these satisfy soundness.

\myparagraph{Our Contributions.}
a) We introduce and motivate soundness. Since a mask-based saliency map can be viewed as a portion of the input that "certifies" the correctness of the net's output, we can view this certificate as part of a probabilistic proof system. This motivates notion of completeness (which has been discussed in previous works) and our new contribution of soundness for the saliency map.
b) Provide a new metric (i.e., a single number) for mask-based saliency methods, which can be used to compare methods. Evaluating this metric gives new insights into efficacies of current saliency methods.
c) We advocate for methods and evaluations for mask-based saliency  that are intrinsic ---use just the training dataset and the trained net, and does not use separately trained nets, distractor distributions, human evaluations etc. To this end, we introduce a new saliency method that does not require additional training of infillers and is fairly simple as well.
\iffalse
We view the classifier as a circuit acting on the input.
A central idea is a notion of saliency that involves  partial assignments that validate the label output by the circuit. This is an intrinsic notion, but  very analogous to popular {\em mask-based} explanations in the human-oriented category. (a) Sections~\ref{sec:logic} views partial assignments as precise logical concepts and defines {\em completeness} and {\em soundness} for procedures that find them. Existing saliency methods focus on at most one of these two notions, whereas both are needed.  Section~\ref{sec:stat} extends the framework to statistical learning and relates completeness and soundness to existing evaluation metrics. (b) Section~\ref{sec:logic} shows that even finding weak approximations to short partial assignments (or to deletion metrics) is computationally intractable (i.e., NP-hard) for general circuits.
A takeaway from this, which may  guide future work on intrinsic saliency, is that there will not be a magical  axiomatization for a coordinate's "contribution" to the output that will also lead to efficient procedures generating succinct saliency maps. One could settle for heuristics for real-life circuits and data distributions too.
(c) Motivated by (b), we give concrete examples of circuits where saliency maps derived from existing saliency methods give no clue to what the minimal satisfying assignment is
(Section~\ref{sec:logic}). (d) Procedures for finding saliency maps using the notion of partial statistical assignment in real-life deep nets (Section~\ref{sec:procedures}). Again, these are close to masking-based methods with some subtle differences.  (e) Experiments on popular deep architectures trained on the usual datasets (CIFAR and ImageNet) illustrating properties of the partial assignments discovered by our procedure. In particular, we show that the TV regularizer (ubiquitous in computer vision) and the upsampling trick serve to make our procedure satisfy soundness condition. (f) Section~\ref{sec:linear} uses simple linear models to illustrate and explain the  above framework, including the provable role of TV regularizer for ensuring soundness even in non-vision setting.
\fi

\paragraph{Differences from previous work} We do not try to match the probability. Instead we maximize it, due to soundness.

\end{comment}
\section{Procedures for finding masking explanations}
 \label{sec:procedures}

\looseness-1 We propose a very simple method to find saliency maps with good empirical completeness and soundness scores.
Detailed intuitions and implementations appear in \Cref{sec:procedures-details}.
Our method is similar to prior work on mask-based saliency maps and is based on the idea of SSR (Smallest Sufficient Region)\footnote{We do not incorporate any SDR (Smallest Destroying Region) component in our method.}.
In particular for an input $x$ and label $a$, given a network $f$, the main goal is to learn a map (or mask) $M\in\{0, 1\}^{hw}$ such that $\mathop{\mathbb{E}}_{\tilde{x}\sim \Gamma(x, M)}[-\log(f(\tilde{x},a))]$ is minimized, i.e. the probability that the network assigns to a modified (or composite) input $\tilde{x}$ is high.
The key difference from prior masked-based methods is our choice of $\Gamma$, which retains the pixels of $x$ corresponding to $M$, but replaces the rest of the pixels with values from a {\em randomly sampled} image $\bar{x}$ from the training set\footnote{We think other random image distributions should work too.} $\mathcal{X}$, i.e.
\begin{align}
    \tilde{x}\sim\Gamma(x, a) ~\equiv~ \bar{x} \sim \mathcal{X}, \tilde{x} = M \odot x + (1 - M) \odot \bar{x}\label{eq:composite}
\end{align}
Modifications procedures ($\Gamma$) that have been considered in prior work include: graying or blurring out the remaining pixels \citep{fong2017interpretable}, and using a conditional image generative model to fill in the remaining pixels \citep{chang2018explaining,agarwal2020explaining}.
Replacing with random image pixels forces the mask-finding algorithm to solve a more difficult task of having the network predict a high confidence for the label, despite the presence of another image.
This amounts to grafting salient pixels of $x$ on top of a random image, reminiscent of BAM evaluations~\citep{yang2019benchmarking} for saliency methods.
We also note a methodological difference from \citet{dabkowski2017real,phang2020investigating} in that we do not train a separate neural network to output the mask.

\looseness-1 As is standard, we relax the domain of masks $M$ from binary $\{0, 1\}^{hw}$ to continuous $[0,1]^{hw}$ parametrized by a sigmoid.
We define a composite input, where the part of $x$ on $M$ is superimposed onto a distractor $\bar{x} \sim \mathcal{X}$ as $\tilde{x} = M \odot x + (1-M) \odot \bar{x}$.
We then have the following simple \emph{vanilla} objective, where the $\ell_1$ norm penalty on $M$ helps to reduce the size of masks.
\begin{align}
    L(M; (x,a)) =&~ \mathbb{E}_{\bar{x}\sim\mathcal{X}} \left[-\log(f(\tilde x, a))\right] + \lambda_1 \|M\|_1,
    \text{where } \tilde x = M \odot x + (1-M) \odot \bar{x}.
    \label{eq:vanilla_obj}
\end{align}
\myparagraph{Promoting soundness.}  Tricks used in prior mask-finding approaches were tested for their effect on soundness.
These include 1) Total-Variation (TV) penalty \citep{fong2017interpretable} and 2) upsampling of the mask from a lower resolution one \citep{petsiuk2018rise} by learning a low-resolution mask at scale $s$, $M\in[0,1]^{hw/s^2}$. For example, on ImageNet, $s=1$ corresponds to learning a $224\times224$ mask, while $s=4$ corresponds to learning a $56 \times 56$ mask and upsampling by a factor of $4$. Incorporating 1) and 2) leads to the following \emph{modified} objective
\begin{align}
     L(M; (x,a)) =&~ \mathbb{E}_{\bar{x}\sim\mathcal{X}} \left[-\log(f(\tilde x, a))\right]
     +\lambda_{TV} TV(M^{\times s}) + \lambda_1 \|M^{\times s}\|_1\nonumber \nonumber \\
    \text{where } \tilde x =&~ M^{\times s} \odot x + (1-M^{\times s}) \odot \bar{x},
    \label{eq:main_obj}
\end{align}
and $M^{\times s}\in\mathbb{R}^{hw}$ is obtained by upsampling $M$ by a factor of $s\in\{1,4\}$ via bilinear interpolation.

While the motivation cited for these two commonly employed ``tricks'' is to avoid artifacts \citep{fong2017interpretable}, in our intrinsic framework ``artifacts'' does not have an  interpretation.  What looks like an artifact to a human observer may be relevant to the net's decision-making. Indeed, our experiments show that while TV penalty or upsampling does produce better looking masks, they lead to a drop in the {\em  completeness metric}. But they significantly improve {\em soundness}. This provides an intrinsic justification for the use of such tricks, instead of extrinsic justifications related to human interpretability.

\section{Prior approaches}
\label{sec:prior}

We relegate a more thorough description of prior work to Appendix \ref{sec:additionalbackground}, but mention some common saliency and saliency evaluation methods here. Saliency methods aim to explain a model's decision about an input. Saliency evaluation methods aim to evaluate the goodness of a saliency method.

\textbf{Saliency methods} include \emph{backpropagation based approaches} such as Gradient $\odot$ Input~\citep{shrikumar2017learning},  iGOS++~\citep{khorram2021igos++}, Robust Perturbations \citep{kim2021robust},  LRP~\citep{binder2016layer}, GradCAM~\citep{selvaraju2016grad}, Smooth-Grad \citep{smilkov2017smoothgrad}. Another line of work is \emph{masking methods} which include techniques based on averaging over randomly sampled masks \citep{petsiuk2018rise}, optimizing over meaningful  mask perturbations \citep{fong2017interpretable}, and real time image saliency using a masking network \citep{dabkowski2017real}. Pixels that have been removed from the image by the mask may be replaced by greying out, by Gaussian blurring as in \citep{fong2017interpretable}, or with infillers such as CA-GAN \citep{yu2018generative} used in \citep{chang2018explaining,phang2020investigating}, or DFNet \citep{hong2019deep}. The pixel replacement strategy we used is closely related to hot deck imputation \citep{rubin1976inference}, where features may be replaced either by using the mean feature value (analogous to replacing with grey) or sampling from the marginal feature distribution (analogous to replacing with image pixels sampled from other training images). Some prior work \citep{carter2019made} has found that mean imputation does not significantly affect model output on the beer aroma review dataset. On Imagenette, by contrast, we found that replacement strategy can matter (See Figure \ref{fig:scatter_completeness_soundness}). \citet{de2020decisions} find masks using differentiable masking.
\emph{Boolean logic} is another approach for saliency methods \citep{ignatiev2019relating,ignatiev2019abduction,macdonald2019rate,mu2020compositional,zhou2018interpreting}.

\myparagraph{Arguments about saliency.}  Discussions about the methods and the meaning of saliency appear, among others, in  \citep{seo2018noise,fryer2021shapley,gu2018understanding,sundararajan2020many}. \revise{Some reveal situations where Shapley axioms work against feature selection or where Shapley values may be calculated in conflicting ways \citep{fryer2021shapley, sundararajan2020many}. Others question efficacy of saliency methods that add noise~\citep{seo2018noise}, making explanations  non class discriminative \citep{gu2018understanding}.  }

\myparagraph{Saliency evaluation methods.} Extrinsic evaluation metrics include the {\bf WSOL} metric, and  {\bf Pointing Game} metric proposed by \citet{zhang2018top} and {\bf ROAR}  \citep{hooker2019benchmark}. Other more intrinsic methods include early saliency evaluation techniques like {\bf MorF} and {\bf LerF} \citep{samek2016evaluating},  {\bf Insertion and Deletion game} proposed by \citet{petsiuk2018rise}, which involve either inserting pixels in order of most importance or deleting pixels in order of most importance.  {\bf BAM} \citep{yang2019benchmarking} creates saliency maps by pasting object pixels from MSCOCO \citep{lin2014microsoft}.  The  {\bf Saliency Metric} proposed by \citet{dabkowski2017real} thresholds saliency values above some $\alpha$ chosen on a holdout set, finds the smallest bounding box containing these pixels, upsamples and measures the ratio of bounding box area to model accuracy on the cropped image, $s(a,p) = \log(\max(a,0.05)) - \log(p)$ where $a$ is the area of the bounding box and $p$ is the class probability of the upsampled image.
	\citet{adebayo2018sanity}
proposed ``sanity checks'' for saliency maps. They note that if a model's weights are randomized, it has not learned anything, and therefore the saliency map should not look coherent. They also randomize the labels of the dataset and argue that the saliency maps for a model trained on this scrambled data should be different than the saliency maps for the model trained on the original data. We study the effect of model layer randomization on our method in Appendix section \ref{subsec:sanity} and find that randomizing the model weights does cause our saliency maps to look incoherent.
\citet{tomsett2020sanity} also discover sanity checks for saliency metrics, finding that saliency evaluation methods can yield inconsistent results. They evaluate saliency maps on reliability, i.e. how consistent the saliency maps are. To measure a method's reliability, because access to ground truth saliency maps are not available, they use three proxies 1) inter-rater reliability, i.e. how whether a saliency evaluation metric is able to consistently rank some saliency methods above others, 2) inter-method reliability, which indicates whether a saliency evaluation metric agrees across different saliency methods, and 3)internal consistency reliability, which measure whether different saliency methods are measuring the same underlying concept.

\myparagraph{Discussions.}
\revise{\citet{brunke2020evaluating} show that perturbation methods are sensitive to baseline and \citet{petsiuk2018rise} point out that human centric explanations (based on bounding boxes) may not reveal why the model made a certain decision. Our notion of intrinsic saliency method outputs the mask but introduces soundness to validate it. }

redpajama_set_name: RedPajamaArXiv