Scaling Symbolic Methods using Gradients for Neural Model Explanation
Authors: Subham Sekhar Sahoo
Subhashini Venugopalan
Li Li
Rishabh Singh
Patrick Riley
Venue: ICLR 2021 Poster (2021)
Keywords: Neural Model Explanation
SMT Solvers
Symbolic Methods

Abstract: Symbolic techniques based on Satisfiability Modulo Theory (SMT) solvers have been proposed for analyzing and verifying neural network properties, but their usage has been fairly limited owing to their poor scalability with larger networks. In this work, we propose a technique for combining gradient-based methods with symbolic techniques to scale such analyses and demonstrate its application for model explanation. In particular, we apply this technique to identify minimal regions in an input that are most relevant for a neural network's prediction. Our approach uses gradient information (based on Integrated Gradients) to focus on a subset of neurons in the first layer, which allows our technique to scale to large networks. The corresponding SMT constraints encode the minimal input mask discovery problem such that after masking the input, the activations of the selected neurons are still above a threshold. After solving for the minimal masks, our approach scores the mask regions to generate a relative ordering of the features within the mask. This produces a saliency map which explains" where a model is looking" when making a prediction. We evaluate our technique on three datasets-MNIST, ImageNet, and Beer Reviews, and demonstrate both quantitatively and qualitatively that the regions generated by our approach are sparser and achieve higher saliency scores compared to the gradient-based methods alone. Code and examples are at - https://github.com/google-research/google-research/tree/master/smug_saliency

Published as a conference paper at ICLR 2021
SCALING SYMBOLIC METHODS USING GRADIENTS FOR NEURAL MODEL EXPLANATION
Subham S. Sahoo, Subhashini Venugopalan, Li Rishabh Singh & Patrick Riley Google Research
(subhamsshho, vsubhashini, leeley, rising, pfr) @google...........oo com
ABSTRACT
Symbolic techniques based on Satisfiability Modulo Theory (SMT) solvers have been proposed for analyzing and verifying neural network properties, but their usage has been fairly limited owing to their poor scalability with larger networks. In this work, we propose technique for combining gradient-based methods with symbolic techniques to scale such analyses and demonstrate its application for model explanation. In particular, regions in an input that are most relevant for a neural network's 's prediction. Our approach uses gradient information (based Integrated Gradients) to focus subset of neurons in the first layer, which allows our technique to scale to large networks. The corresponding SMT constraints encode the minimal input mask discovery problem such that after masking the input, the activations of the selected neurons are still above a threshold. After solving for the minimal masks, our ap- proach scores the mask regions to generate a relative ordering of the features within the mask. This produces saliency map which explains "where model looking" when making a prediction. We evaluate our technique on three datasets MNIST, ImageNet, and Beer Reviews, and demonstrate both quantitatively and qualitatively that the regions generated by our approach are sparser and achieve higher saliency scores compared to the gradient-based methods alone, Code and examples are at-
apply this technique to identify minimal
hetps://github. com/ google- research/ wowgle. research/ tree/
http://tteeeeeeeeeeeeeeeeeeeeeet mwste////eeeeesmmeem//ee//// smwg_maggaaae sallency
INTRODUCTION
Satisfiability Modulo Theory (SMT) solvers (Barrett & Tinelli 2018) are routinely used for symbolic modeling and verifying correctness software programs (Srivastava et al. 2009), and more recently they have also been used for verifying properties of deep neural networks (Katz et al. 2017). SMT Solvers in their current form are difficult to scale to large networks. Model explanation is one such domain where SMT solvers have been used but they are limited to very small sized networks (Gopinath et al. 2019 Ignatiev et al. 2019). The goal of our work is to address the issue of scalability of SMT solvers by using gradient information, thus enabling their use for different applications. In this work, we present new application of SMT solvers for explaining neural network decisions.
Model explanation can be viewed as identifying a minimal set of features in given input that is critical to a model's prediction (Carter et al.) 2018 Macdonald et al. 2019). Such a problem formulation for identifying minimal set lends itself the use of SMT solvers for this task. We can encode a neural network using real arithmetic (Katz et al. 2017) and use an SMT solver to optimize over the constraints to identify minimal set of inputs that can explain the prediction. However, there are two key challenges in this approach. First, we cannot generate reliable explanations based on final model prediction as the minimal input is typically out of distribution. Second, solving such formulation is challenging for SMT solvers the decision procedures for solving these constraints have exponential complexity, and is further exacerbated by the large number of parameters in typical neural network models. Thus, previous approaches for SMT-based analysis of neural networks have been quite limited, and have only been able to scale to networks with few thousands of parameters.
To solve these challenges, instead of doing minimization by encoding the entire network, our approach takes advantage of the gradient information, specifically Integrated Gradients (IG) (Sundararajan et al. 2017), in lieu of encoding the deeper layers, and encodes much simpler set of linear constraints

---

Published as a conference paper at ICLR 2021
pertaining to the layer closest the input. We encode the mathematical equations of a neural network as SMT constraints using the theory of Linear Real Arithmetic (LRA), and use z3 solver (Bjørner et al. 2015) it additionally supports optimization constraints such minimization. The SMT solver then finds a minimal subset (of input features) by performing minimization on these equations. Thus, our approach, which we refer to as SMUG, is able scale Symbolic Methods Using Gradient information while still providing a faithful explanation of the neural network's 's decision.
SMUG is built on two properties. First, based on the target prediction, SMUG uses gradient information propagated from the deeper layers to identify neurons that are important in the first layer, and only encodes those. For this, we use IG (Sundararajan al., al.) (017) instead of relying on gradients alone. Second, for the optimization, a set of input pixels are determined to be relevant for prediction they are able to activate the neurons deemed important, and maintain a fraction of their activation as the original (full) input image. Empirically, we observe good performance on visual and text classification tasks.
We evaluate SMUG on three datasets: MNIST (LeCun et al. 2010), ImageNet (Deng et al. 2009). and Beer Reviews (McAuley et al. 2012). We show that we can fully encode the minimal feature identification problem for a small feedforward network (without gradient-baset neuron selection) for MNIST, but this full SMT encoding scales poorly for even intermediate sized networks. On ImageNet, observe that our method performs better than Integrated Gradients (Sundararajan et al., 2017) and several strong baselines. Additionally, we observe that our approach finds significantly sparser masks (on average 17% of the original image size). Finally, also show that technique is applicable to text models where it performs competitively with other methods including SIS (Carter al. 2018) and Integrated Gradients (Sundararajan et al., 2017).
This paper makes the following key contributions:
We present a technique (SMUG) to encode the minimal input feature discovery problem for neural model explanation using SMT solvers. Our approach, which does masking on linear equations also overcomes the issue of handling duttif-distribution samples.
Our approach uses gradient information to scale SMT-based analysis of neural networks to larger models and input features. Further, it also overcomes the issue of choosing "baseline" parameter for Integrated Gradients (Kapishnikov et al. 2019 Sturmfels et al. 2020).
We empirically evaluate SMUG on image and text datasets, and show that the minimal features identified by it are both quantitatively and qualitatively better than several baselines.
To improve our understanding on saliency map evaluation, we show how the popular and widely used LSC metric (Dabkowski & Gal 2017) can be gamed heuristically to generate explanations that are not necessarily faithful to the model (Sec. 5.2)
2
RELATED WORK
SMT based symbolic techniques have been used for verifying neural network properties (Huang et al. 2017 Katz et al.) 2017). Reluplex (Katz al., 2017) extends the simplex method handle ReI.U functions by leveraging its piecewise linear property and presents an iterative procedure for gradual satisfaction of the constraints. (Huang et al., (017) proposes a layer-wise analysis using a refinement- approach with SMT solvers for verifying the absence of adversarial input perturbations. (Zhang et al., 2018) present a linear programming (LP) formulation again using the piecewise linear property of ReLU to find minimal changes to an input to change a network's 's classification decisions. (Gopinath al.) 2019) uses Reluplex to learn input properties in the form of convex predicates over neuron activations, which in turn capture different behaviors of neural network. While SMT based techniques from (Gopinath et al.) 2019), (Ignatiev et al.] (019) have shown promising results, they only scale to Neural Network with 5000 nodes. Thus, scaling these approaches for larger neural networks and performing richer analysis based on global input features still remains challenge. We present and demonstrate approach that works for larger and more complex image and text models.
While most of the above SMT based techniques focus verifying properties of deep networks, work focuses on applying symbolic techniques to the related task of model explanation, i.c. to say where model is "looking", by solving for the input features responsible for a model's prediction.
2

---

Published as a conference paper at ICLR 2021
Some explanation techniques model agnostic (i.e., black-box) while others are pack-propagation based. Model agnostic (black-bos box) explanation techniques such as SIS, LIME (Alvarez- & Jaakkola 2018 Carter et al. 2018) have similar formulation of the problem as ours in the sense that they perturb the input pixels by masking them and optimize to identify minimal regions affecting the
performance of the model. This formulation can lead to evaluating the model out of distribution
samples (Hooker et al. 2019) with potential for adversarial attacks (Slack et al. 2020). In contrast, pook-propagttion based methods (Bach et al. 2015 Sundararajan et al. 2017 Selvaraju al. 2016) examine the gradients of the model with respect to an input instance to determine pixel attribution. Our work builds on the IG method (Sundararajann jn et al. 2017). IG integrates gradients along the "intensity" path where the input (image or text embedding) is scaled from an information-less baseline (all zeros input, e.g., all black or random noise image) to a specific instance. This helps the model determine attribution at the pixel level. In our work, we use IG to determine important nodes in the first layer (closest to the input). The key improvement of our technique over IG is that, by using IG only on the first layer and then using SMT solver based solution determine saliency on the input, we not only preserve faithfulness, but also overcome the issue of choosing an appropriate baseline
image for IG (Kapishnikov et al. 2019 Sturmffls al. 2020 Xu al. 2020).
METHOD: SCALING SYMBOLIC METHODS USING GRADIENTS (SMUG)
We describe our approach SMUG, which combines attribution based on gradient information with an SMT-based encoding of the minimal input feature identification problem. We then show how to generate saliency maps from the predicted boolean mask for image and text applications.
3.1 CHALLENGES WITH ENCODING NEURAL NETWORKS FOR EXPLANATION
Previous works (Katz et al. semantics of neural networks with specific activation functions, while others (Carter et al. 2018 Macdonald et al. 2019) have used the idea of minimality to identify importance of inputs in the context of model explanation. In particular, given a neural network No (Ø denotes the parameters), let X RR denote an input image with m and L:(-) the output (i.e., activations) of the ith layer. Also, let L L) (Na()) denote the logits of the final layer. Previous works (Carter et al. 2018 Macdonald et al. 2019) have used the following formulation for explanation.
2017) have shown it's possible to use SMT solvers to encode the
pixels, M E {0, 1)mxx unknown binary mask,
min Σ Mis)) argmax LIII = 4
X))
However, there are two key problems with this formulation. First, the masked inputs found by solving this formulation are typically out of training distribution, so explanation techniques based on model confidence over forward pass of the masked inputs (such as the above formulation) no longer produce reliable explanations. Second, using such a formulation directly with SMT solvers is not tractable as the number of constraints in the encoding grows linearly with increasing network size and SMT decision procedure for Non-linear Real Arithmetic is doubly exponential. Thus, when we apply such encoding even for small feed-forwar network MNIST dataset, the SMT solver does not scale well (Section 4 Appendix A.
3.2
OUR SOLUTION: COMBINING GRADIENTS WITH SYMBOLIC ENCODING
Our proposal to use gradient based attributions to overcome both these issues: 1) as proxy for the deeper layers (for scalability), and 2) to identify subset of neurons in the first layer capturing information crucial for the model's prediction, and encode them using SMT which avoids performing forward pass outtof-distribution inputs.
Specifically, we use Integrated Gradients (IG) (Sundararajan et al., 2017) to score the neurons in order of relevance by treating the first layer activations (L1) an input to the subsequent network. This assigns an attribution score to each hidden node where a node with positive score means that the information captured by that neuron is relevant to the prediction and node with negative / zero score is considered irrelevant. More specifically, suppose F; Raxbxe + [0. 1]d represents a deep network and x represents the input. F often refers to the full network (from the input to the
3

---

Published as a conference paper at ICLR 2021
final softmax) but in case, it refers to the nodes in the network second through the final layer. a, b, and refer to the dimensions of the tensor imput to the network (analogous to width, height, and channels) and d is the number of output nodes in the final softmax layer (number of classes). Integrated gradients are obtained by accumulating the gradients at all points along the straight line path from an "information-less baseline x' to the input x. The information-less baseline in this case is an all zeros tensor. The path can be parameterized as g(a) = x' +a (x x²). IG is then given by Eq.
[ aF(g(a)) da a= Ōg(a)
IG(z) =G
(1)
Top-k Neurons. The second key idea of our approach is that we only consider activations with the highest positive attributions. Empirically, we still observe scaling issues with SMT when considering all first layer neurons (L,) with +ve attributions, so a method for picking subset of neurons (top-k attributions) is important for practical application.
With these two ideas, we can now formulate our problem as follows. Let, D* represent the set of k important nodes with the highest attributions (No (X)), and y be a parameter which regulates how "active" the neurons remain after masking The goal now is to learn mask M such that:
min Σ Myg) : (No(M @ x)). >> L (NN(
V D
Inducing Sparsity. IG ensures that the information captured by the neurons in D* are relevant these neurons contributes
for the model's prediction. Thus, the set of features corresponding towards the relevant information. Let's ' denote this set as S. To filter less relevant features from S we introduce notion of minimization. By inducing sparsity wish to remove any false positives from S. Thus, we define "relevant features" as a minimal subset of features in S that causes the nodes in D to remain active. The notion being for masked input the "important nodes" (w.r.t the original input) are active then the information relevant for the prediction of the original image is contained in the mask. Thus, the mask highlights features relevant for the model's prediction.
Thus, this formalism allows us to come up with constraints which don't 't involve a full forward pass of the masked image while at the same time keeping things scalable for the SMT solver.
3.3 SMT FORMULATION OF MINIMAL INPUT MASK DISCOVERY PROBLEM
Given D* set of A neurons with highest positive attributions in IX(N, our goal is to find minimal mask such that the activations of these neurons are above some threshold (7) times their original activation values. Eq. 3 shows the constraints for a minimal mask. The first set of constraint specifies that the unknown mask variable M can only have 0 and as possible entries in the matrix. The second and third set of constraints encode the activation values of the first layer of network with corresponding masked and original inputs respectively. The fourth set of constraint states that the activations of these i neurons should be at least 7 times the original activation values, and the final constraint adds the optimization constraint to minimize the sum of all the mask bits. Note that here we show the formulation for feedforward network and input X with 2 channels, but it can be extended to convolutional networks and an input with 3rd channel as well in straightforward manner where the mask variables across the same channel share the same mask variable.
3M:
A
(My 0) V (My 1)
A of (Wi C MM + b1); ViED*
ISiSm,Siin
(3)
A VEDD
o, = (WiX x b1); A Or > 7 0; A miiimiiz((E,,M..
ViED
3.4 CONSTRUCTING SALIENCY MAP FROM BINARY MASK
The SMT solver generates a minimal binary input mask by solving the constraints shown in Eq. 3 We further use the IG attribution scores for the hidden nodes in the first layer to assign importance
'Tiis formulation is valid for networks with ReI.U activations and would need to be modified for different choice of activation such as tanh.
4

---

Published as a conference paper at ICLR 2021
scores mask pixels associated with that hidden node. A mask variable My that is assigned a value of 1 by SMT is assigned a score Siy computed as:
Sij Σ recpp
Vi,j Mij =
(4)
ISPS
where (0p)) denotes the attribution score assigned by IG for neuron Op and the indicator function denotes that pixel 2ij is present in the receptive field of Op, i.e. it is present in the linear SMT equation used to compute On- These scores are then used to compute continuous saliency map for an input (Appendix Fig- 19. Finally, to amplify the pixel differences for visualization purposes in gray scale, we scale the non-zero score values between 0.5 and
3.5 HANDLING OUT-OF-DISTRRIUUIIO MASKED INPUTS
Several methods- Allarez- & Jaakkola 2018), (Petsiuk et al., 2018). (Fong & Vedaldi 2017) optimize their masks by doing a forward pass on perturbed images that are potentially out-of- distribution. However, SMUG performs forward pass of the masked image only till the first layer (instead of the final layer) to generate linear equations as described in Sec. [33] Since, the constraints are linear 6 minimization can be thought of analogous examining coefficients for a linear regression model (in linear regression important attributes are the ones with the largest coefficients). So, in our case we do indeed mitigate the out-of-distribution issue as the full forward pass of the masked input isn't ' present.
4 EXPERIMENTAL SETUP
Datasets. We empirically evaluate SMUG on two image datasets, MNIST (LeCun et al. 2010), and ImageNet (Deng et al. 2009), well text dataset of Beer Reviews from (McAuley et al.) 2012).
MNIST: We use the MNIST dataset show the scalability of the full network encoding in SMT (presented in Section We use a feedforward model consisting of one hidden layer with 32 nodes (ReLU activation) and 10 output nodes with sigmoid, one each for 10 digits (0 9). For 100 images chosen randomly from the validation set, the SMT solver could solve the constraint shown in Eq 6 (returns SAT) for only 41 of the images. For the remaining 59 images, the solver returns UNKNOWN, which means the given set of constraints was too difficult for the solver to solve.
ImageNet:
We use 3304 images (224 x 224) with ground truth bounding boxes from the validation set of ImageNet. The images for which the model classification was correct and a ground truth bounding box annotation for the object class was available were chosen. We use the Inception-vl model from SZegedy et al., 2015) which classifies images into one of the 1000 ImageNet classes.
To evaluate SMUG on textual task we consider the review rating prediction task on the Beer Reviews datasef consisting of 70k training examples, 3k validation and 7k test examples. Additionally, the dataset comes with ground truth annotations where humans provide the rationale (select words) that correspond to the rating and review. We train 1D CNN model to predict the rating for the aroma of the beer on a scale from to This model identical to the model used in (Carter et al. 2018) and consists of convolution layer with 128 kernels followed by ReLU, a fully connected layer, and a sigmoid. It achieves a validation mean square error of 0.032.
Beer Reviews:
Metrics. Assessing the quality of the saliency maps, especially binary masks, is challenging. The change in confidence of the classifier (between the original and masked) image alone may not be reliable measure since the masked input could fall out of the training distribution (Hooker et al. 2019). Instead, we use the metric proposed in (Dabkowski & Gal (017) shown in Eq. 5 This metric, which we term Log Sparsity Confidence difference (LSC) score, first finds the tightest bounding box that captures the entire mask, then computes confidence on the cropped box resized to the original image size (we use bilinear interpolation). This not only helps keep images closer to the training distribution, but also helps evaluate explanations without the need for groundtruth annotations. The LSC score is computed as:
LSC c) = log(a) log(c),
ā max max(0.05,
(5)
http://people..sailmmi...c hwt.://wwwii..iii.cacaaaoeeereer
5

---

Published as a conference paper at ICLR 2021
where is the fractional area of the rectangular cropped image and e is the confidence of the classifier for the true label on the cropped image. A saliency map that is compact and allows the model to still recognize the object would result in lower LSC score. LSC captures model confidence as well as compactness of the identified salient regions, both of which are desirable when evaluating an explanation. The compactness in partieular also makes it suitable for evaluating SMT based methods for the effect of minimization. We adapt LSC to also assess continuous valued saliency maps by, 1) setting a threshold on the continuous valued saliency map to convert them a binary mask and 2) iterating over multiple thresholds (in steps) to identify the one that results in the best LSC score. We also report the fraction of images for which the mask generated by a given method is better (i.e. produces an equal or lower LSC score) than other methods, which we refer to as Win %.
Comparison methods. The final saliency mask for SMUG comes from Eq. (Sec. 3.4 We compare this to the saliency maps, and bounding boxes from several baselines described below. SMUG base is a variant of SMUG that does not perform SMT-based minimization. Here, in Eq. 2 we simply set Mi = for each pixel zij that is in the receptive fields of the top-k neurons in
the first layer (L1) selected by IG. We note here that in case of both SMUG and SMUG in the
formulations in Eq. 2 and [] set k = 3000, y 0 for ImageNet, and k 100, y 0 for text experiments (this choice is explored more in the supplementary material).
IG corresponds to Integrated Gradients (Sundararajan et al. (017)) with the black image as a baseline. GRADCAM (Selvaraju et al.] (017) uses a weighted average of the CNN filters for saliency, with weights informed by the gradients.
SIS refers to Sufficient Input Subset (Carter et al. 2018). which finds multiple disjoint subsets of input features (in decreasing order of relevance) which individually allow a confident classification. SIS did not scale for ImageNet and we only compare against it on the text dataset. GROUND TRUTH corresponds to the baseline that uses human annotated bounding box, which capture the object corresponding to the image label.
MAXBOX denotes maximal mask spanning the entire image.
CENTERBOX uses bounding box placed at the center of the image covering half of the image area. OPTBOX refers to a bounding box that approximately optimizes for LSC. The saliency metric in Eq. relies finding single bounding box for image. To find box that directly maximizes the metric, we first discretize the image into subgrids of 10 x 10 pixels; and then perform a brute force search by selecting 2 points the grid (to represent opposite corners of rectangle) and identify subgrid with the best score.
5 RESULTS
5.1 IMAGENET
As mentioned previously, when computing masks using SMUG, for ImageNet we set = 3000 in Eq. and Further, each masking variable M;; is used to represent 4 x 4 grid of pixels instead of a single pixel (to reduce running time). Table p quantitative results reporting the median LSC score and Win% values. Fig. I present qualitative examples
Table ImageNet. We report the median LSC score (4 lower is better) along with the 75th (top) and 25th percentile (bottom) values, and the mean Win% score in percentage (1 higher is better) with binomial proportion confidence interval (normal approximation) on 3304 images the validation set. The Win% values don't sum to 100 due to overlap when methods achieve identical scores. SMUG and SMUG receive similar LSC scores which suggests that the SMT based minimization retained the relevant regions while successfully removing about 66% pixels from SMUG We also report the average size of the masks as a fraction of the total image area (sparsity) with normal confidence interval for 3304 images. Sparsity scores for IG and Gradcam are omitted because they aren't 't masking methods.
Method
SMUG
SMUG
GROUNDTRUTH
IG
GRADCAM
CUNTERBON
MAXBoX
OrrBux
LSC
- -1.26_1.7
- -1.29=977
-0,34221,
-0.29-800
-1.1029
-0.6428.0 da
0.04
-2,27
Win%
40.9 1.68
33.5 1.61
3.6 - 0.64
1.7 4: 0.44
37.8 + 1.68
2.6 0.54
0.2 + 0.16
Sparsity %
17.7 0.10
43.3 = 0.32
50.7 = 0.98
50.020.99
100.0:0.00
8.920.0

---

Published as a conference paper at ICLR 2021
GroundTruth 6:73 (1m) cm),00
SMUG 3.47 lon c=1,00
SMUG base
IG
GroundTruth
SMUG
SMUG base
IG 0.0 lund cm0
1.38 (00022 sml 000
3:71 lom) 4G, (m1,00)
2A0 (pm] cmbo0)
2,17 lo (20.73)
11 Gend
mihin
collic
0206
5:66 On 1991
Ouites Cri 100
7M013210 CHIII
2.40 13-5.01 CHAaa
Lirgu 200
oun 13-2.:0 CHALEE
noo zoneal bar
0.03 LomE (WC.02)
1.41 1om0:17 (m0.t3)
0.55 (10.2) cw0.50 500
2.22 (cm) ceba00
mar macaau
(a)
Examples where SMUG outperforms other compared methods.
Truth
SMUG
SMUG
IG
Truth
SMUG
SMUG
IG
gibbon
10 2a M-
3. Camo.88. cHO e6
6:25 laed cm0.50)
0:22 ano cmo
brom
(b) Examples where SMUG performs less favorably.
Figure 1: Examples where SMUG outperforms other compared methods (top rows), and where SMUG performs less favorably (last 2 rows) based on LSC. The green box on the original image highlights the groundtruth box; for the saliency methods it represents the bounding box with the best LSC score. Numbers on top denote the I.SC score, the fractional area of the hounding box (a), and the confidence of the classifier (c) on the cropped region. Red and blue colors denote regions high and low importance respectively. More qualitative examples can be found in Appendix D
IG SMUG and SMUG From Table 1 we observe that SMUG and SMUG achieve significantly better score (-1.26 and - -1.23 resp.) compared to IG (-0.34). As observed in some qualitative examples (Fig. [ Appendix D) SMUG tends to assign high scores localized set of pixels whereas IG distributes high scores more widely (spatially). As LSC metric favors compactness, which is desirable for human interpretability, it results in better scores for SMUG and SMUG
much more
Choice of baseline for IG. Another reason why SMUGMss and SMUG outperform IG is that, they apply IG to the first layer of the network (as opposed to the input/image layer). IG attribution in the pixel space is known be noisy (Smilkov et 2017). further attributions produced by IG depend on the choice of the baseline (Kapishnikov et al.
2019 Xu et al., 2020 Sturmfels et al. 2020). The reason for this can be observed from Eq I Eq.
represents the baseline "information-less image. Based on this, the input dimensions close to the baseline receive very low attributions even though they might important. i.e., if j denote pixel locations, when Ti.j - O, the attribution IGr, (x) R irrespective how important the pixels are. For instance, black pixels (RGB value of (0, O, 0)) will receive exact O attribution for black baseline. In fact, for any baseline, IG will be insensitive to the dimensions close to the baseline value. When IG is applied to the first layer activations however, the nodes with near activations will by default receive less attribution. Thus, we believe that O activations in the first layer is a more natural baseline for IG for ReLU networks, which is quantitatively observable in better I. L.SC scores.
7

---

Published as a conference paper at ICLR 2021
SMUG vs SMUG base*
Based on the LSC scores in Table SMUG narrowly outperforms SMUG Recall however, that SMUG is sparser version of SMUG obtained from the minimization constraints of the SMT solver (Eqns. 2 and B) LSC scores use the sparsity of the bounding boxes as a proxy for the sparsity of the saliency map. As SMUG have similar sizes even though the former produces much sparser saliency maps. This causes both SMUG and ShGGee to receive similar LSC scores. Thus, the LSC scores alone don't reveal the full picture and we need to consider the sparsity as well. This is defined as the fraction of the pixels with non-zero attributions to the total number of pixels in the image. We find that the average IMUG mask has a sparsity of 43% while the average SMUG mask has a sparsity of just 17%. This is also evident from the examples Fig. | SMUG and SMUG receive similar LSC scores which suggests that the symbolic encoding successfully retains pixels relevant to the prediction while removing about 66% pixels from SMUG
see in Fig. ((a) and ((b) that the bounding boxes for SMUG and
GROUNDTRUTH, CENTERBOX. Based on qualitative examples Figs. 1 we can observe that in almost all cases the object is at the center of the image. Hence, CENTERBOX is likely to capture some part of the image. Further, fair number of objects are large covering much of the image e.g., Fig. Macaquee Collie, Robin, Dalmation. In these cases, the groundtruth bounding boxes are also large to fully cover all pixels corresponding to the object. In contrast, SMUG saliency maps more compact for both large and small objects, and hence achieve a better LSC score.
5.2 DISCUSSION: ANALYZING THE LSC METRIC AND ОPTBOX
3.23 landdd cn8501
Camb cm0.300
2.13 cnd
2.5 2.2 GUmi cHO
With shote
232
0.50 la
1a-024 c-0.52
OPTBOX better SMUG
SMUG batter OPTBOX
Figure 2: OPTBOX vs SMUG. 6 columns on the left correspond to the images for which ОPTBOX gets a better score than SMUG. 2 columns the right correspond to the images for which SMUG got better L.SC than ОrTBOX. Numbers at the top denote the LSC score, frrcctiona area of the bounding box and the confidence of the classifier e on cropped region.
Confidence: 0.53
Confidence: 0.15
Confidence: 0.84
0.28 13-0.46, c-0.611
0.25 (a-0.49. 0.49, (-0.03)
.2.03 (a=0.03, c=0.69)
(a) cat
(b) cat small
(c) 2-cats
(a) Z-cats
(0) lG
(f) 2-cats OPTBOX
Figure 3: (a) shows image of cat (cataig) placed on white background that is classified with confidence of 0.83. (b) shows image of the same cat (Caterat)). scaled quarter of its original size, that is classified with a confidence of 0.15. (c) By placing caliig next to calaull we observe a significant jump in classifier's confidence from 0.15 with catemal alone to 0.84 on 2-cats. While (d) SMUG and (e) IG correctly attribute the model confidence to cataig. (f) OPTBOX exploits the object rescaling in LSC, favoring the more compact object.
The LSC metric makes a trade-off when optimizing for both compactness and confidence. To analyze this we look at several qualitative examples (Fig. 2 of the bounding boxes identified by the OPTBOX brute-force approach to optimize the LSC metric. We observe that ОPTВOX often finds bounding boxes that are very small, typically a sufficiently discriminative region or pattern in the image (e.g.. typewriter keyboard, paddlewheel, vine snake in Fig. 2 the full object if the object is itself small (e.g., basketball, plunger). In all these cases we find that SMUG highlights several other aspects of the object as well (typewriter's tape; the dog's 's eyes, nose and ears, etc.)
8

---

Published as a conference paper at ICLR 2021
ОPTBOX can game the LSC metric (Dabkowski & Gal 2017) to favor compact regions con- taining redundant features. We design an experiment where we introduce redundant features and compare the explanations generated by various methods. Fig. B)) contains 2 cats callig and calll where calsmall is calbig scaled to quarter its size. This image is classified correctly with a confidence of 0.84. If calamall is removed from Fig. (3jc) we get Fig. 31a a) which is classified with confidence of 0.83 (a marginal drop of 0.01 in the confidence score) and if we remove cataig we get Fig. Bb) which classified with a confidence of 0.15 (the confidence drops by 0.68). Thus, cals is redundant in Fig. (3) as its contribution to the prediction is nominal. Hence, the expectation is that a good saliency method would assign greater attribution to callig than cal In this respect, both SMUG and IG capture the model's behavior correctly. Additionally, SMUG's ss attributions lie on the calnig 's face while IG's lie on the edges (possibly due to a sharp change in contrast). OPTBOX, however, attributes the model's prediction to cmall This behavior can be explained using Eq. [ Essentially, OrTBoX employs a brute force search to look for a region as small as possible and classified with a good enough confidence by the model so to maximize Eq. S And by doing so it highlights regions with tightly packed redundant features (catsmall in this case). As argued in (Dabkowski & Gal (017) LSC does capture certain desirable attributes of saliency maps which makes it a popular choice to evaluate these explanation methods, but in this work we show that saliency methods can be designed to fool this metrie.
5.3 TEXT DATASET: BEER REVIEWS
We present randomly selected qualitative examples from the test set comparing with other methods including SIS, IG, and GROUNDTRUTH in Fig. 4 and Appendix C The solution of SIS consists of multiple disjoint set of words of varying relevance. A saliency map is constructed by scoring the words in the sets between (0,1) on the basis of relevance of the set. However, evaluation is harder. Unlike images where the masked image can be cropped and resized as input to compute the LSC metric, the same strategy cannot be followed on the text model. Specifically, ImageNet models are trained with extensive data- data-augmentation including random crops and resizing, and the modified image is less likely to be out-of -itoof--disributionn Whereas in the case of text, this model doesn't 't employ any form of meaningful augmentation, and the masked text is much more likely to come from distribution that has not been seen during training. Hence, LSC is not applicable here.
SIS
SMUG
SMUG
IG
'12 uurd pourde intoo rune
T12 boothe pounedintto
TZ boiilee pourediiioo
T12 bottle pouned in
todgian globe. 4% 5% 40179
kengiinoo doy, 4%c d'c 40199
Endgiannggoe dbn, 4nc 6' 40199
lndgkamsisoo day 40c 6%c
maney doudyy drapes
mileell maney
maneyy drapie
haney
dence wrth
denoe uhhie needs ace drapee
denie whihe
denio whth seed drnoee
Irac
of cacabantid lost dised aa_ froh
aa_ Inoch
of caspbantte dosed duss scott
of axppaaaeee cissed
of cocopiantee doees quet scooes
alssal ta and la barry
alnon beate EDE Ra barr
aktion beste ROs Ra barry
akrunt begato and Ro barry
Boaaa 1 fralyy reapberryis for too
fuulyy reapberry's for too
thmach Tualy recbbrrry for
Duzuab 2 -oully respberry for too
synuoy
synoyy
wheat in the bock agroudd bodonond just
whoor the ground balonoon past
whorr in The Poclgronnn bako on
wholt The bochground proundaloono baloooeddduu
fralmost meeme Flemorade prolite
overty
overyy
prof
remonede blendedis
blendedin
hammeee au
im sugary uemott and skgrt tn
sugary peooot and dlght olrifte
sugarr pwoee and skite with toghtt
"Augar awort und sligh in thiglegee
eweet and fise it's get good aroms bot not uwild..
eoeee and faoe 18% get good anoms exnee and faie lt's get good and eveet and fakle It's get good
butimol unrlu.
bull
bull unil..
Figure 4: Example comparing our method (SMUG, SMUG with SIS and IG on a test sample from the Beer Reviews dataset. Green color signifies a positive relevance, red color signifies negative relevance. The underlined words are human annotations. More examples can be found in Appendix C
CONCLUSION
We present an approach that uses SMT solvers for computing minimal input features that are relevant for neural network prediction. In particular, it uses attribution scores from Integrated Gradients to find a subset of important neurons in the first layer of the network, which allows the SMT encoding of constraints to scale to larger networks for finding minimal input masks. We evaluate our technique to analyze models trained on image and text datasets and show that the saliency maps generated by our approach are competitive or better than existing approaches and produce sparser masks.

---

Published as a conference paper at ICLR 2021
REFERENCES
David Alvarez-Melis and Tommi S Jaakkola. On the robustness of interpretability methods. arXiv preprint arXiv:1806 180.008999 2018.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one. 10(7), 2015.
Clark Barreut and Cesare Tinelli. Satisfiability modulo theories. In Handbook of Model Checking, pp. 305-343. Springer, 2018.
Nikolaj Bjørner, Anh-Dung Phan, and Lars Fleckenstein. v/z-an optimizing smt solver. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 194-199. Springer, 2015.
Brandon Carter, Jonas Mueller, Siddhartha Jain, and David Gifford. What made you do this? understanding black-box decisions with sufficient input subsets. arXiv preprint arXiv:1810.03805, 2018.
Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers In Advances in Neural Information Processing Systems, pp. 6967-6976. 2017.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, leee, 2009.
Ruth Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful perturba- tion. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3429 -3337, 2017.
D. Gopinath, Converse, C. Pasareanu, and A. Taly. Property inference for deep neural networks. In 2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE), pp. 797-809, 2019.
Divya Gopinath, Hayes Converse, Corina Pasareanu, and Ankur Taly. Property inference for deep neural networks. In 2019 34th IEEE/ACM International Conference Automated Software Engineering (ASE), pp. 797-809. IEEE, 2019.
Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. A benchmark for interpretability methods in deep neural networks. In Advances in Neural Information Processing Systems, pp. 9734-9745, 2019.
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. In International Conference Computer Aided Verification, pp. 3 29. Springer, 2017.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva Abduction-based explanations for machine learning models. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 33, pp. 1511-1519, 2019.
Andrei Kapishnikov. Tolga Bolukbasi, Fernanda Viégas, and Michael Terry. Xrai: Better attributions through regions. In Proceedings of the IEEE International Conference on Computer Vision, pp. 4948 4957, 2019.
Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks, 2017.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. 2010.
Jan Macdonald, Stephan Wäldehen, Sascha Hauch, and Gitta Kutyniok. A rate-distortion framework for explaining neural network decisions. arXiv preprint arXiv: /905. 1002, 2019.
Julian McAuley, Jure Leskovec, and Dan Jurafsky. Learning attitudes and attributes from multi-aspect reviews. 2012 IEEE 12th International Conference on Data Mining, pp. 1020-1025. IEEE, 2012.
10

---

Published as a conference paper at ICLR 2021
Vitali Petsiuk, Abir Das, and Kate Saenko. RISE: randomized imput sampling for explanation of black- box models. CoRR, abs/1806.07421, 2018. http::tpp/ta.....ggggggeo// http://...wwaaaa/a////aea/e///a/ 07421
Ramprasaath R Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra. Grad-cam: Why did you say that? arXiv preprint 1rXiv:1611.07450 2016.
Ramprasaath Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-621-66 8-626, 2017.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference AI, Ethics, and Society, pp. 180-186, 2020.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. arXiv preprint 1rXXiv:706.000 03825, 2017.
Saurabh Srivastava, Sumit Gulwani, and Jeffrey S Foster. 3: Smt solvers for program verification. In International Conference on Computer Aided Verification, pp. 702-708. Springer, 2009.
Pascal Sturmfels, Scott Lundberg, and Su-In Lee. Visualizing the impact of feature attribution baselines. Distill, 2020. doi:
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 3319-3328. PMLR, 2017. URL http::tppppocccei.inoo
mlr. mlr.press/v70 sundarara jan an 7a html
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1 1-9, 2015.
Shawn Xu, Subhashini Venugopalan, and Mukund Sundararajan. Attribution in scale and space. arXiv preprint arXiv:2004.03383, 2020.
Xin Zhang. Armando Solar-Lezama, and Rishabh Singh. Interpreting neural network judgments via minimal, stable, and symbolic corrections. In Advances in Neural Information Processing Systems, pp. 4874-4885, 2018.

---

Published as a conference paper at ICLR 2021
APPENDIX
In Here, we present additional quantitative and qualitative examples supporting the results in Sec. 5 particular Sec. A shows qualitative examples on MNIST, Sec. B presents quantitative and qualitative comparisons with regard to the choice of key parameters of our proposed SMUG explanation technique. Sec. presents additional qualitative examples comparing the output SMUG with other methods on text samples from the Beer Reviews dataset. Sec. Dpprssntss several more qualitative examples from ImageNet comparing the saliency masks produced by SMUG with those produced by other methods. In Sec. D.I we also discuss an example where an explanation technique can be used identify potential biases of the trained model. Finally, Sec. presents some examples concrete constraints that the solver optimizes.
A
MNIST
In this section, present some more details about our experiments with MNIST using the full SMT encoding from Eq. in Sec 3.1.
SMT solvers can be used to encode the semantics of neural network KKtz at. 2017). In particular, given a fully connected neural network with n hidden layers, weights = = W2 2.... Wn biases B = {bg, b2 ..... } activation function 6, and final layer softmax of nonlinear real arithmetic to obtain a symbolic encoding of the network. Let X E Rmmx denote an input image with m pixels, M {0, 1) mxx unknown binary mask, L2 the output (i.e., activations) of the ith layer (Lo X is the input) and a(p;) the output of jth logit in the final layer:
the SMT theory
L = (W;L, + bz)
alp,, W, B, B) = o (WWnnn- + b,)
Given this symbolic encoding, we can encode the minimal input mask generation problem as:
3M minimize(X.,,MM)) AalPtabel. W, B, alp,, M.X)
14 e label (6)
where Plabel and Pt refer the logits corresponding the true label and the other labels respectively.
The number of constraints grow with increasing network size and SMT decision procedure for Non- linear Real Arithmetic is doubly exponential. Even for piecewise ReLU networks, SMT decision procedures for Linear Real Arithmetic combine simplex-based methods (exponential complexity) with other decision procedures such as Boolean logic (NP-complete complexity), which causes the solving times grow dramatically with network size. When we apply this encoding even for a small feed-forward network on MNIST dataset, the SMT solver does not scale well (Section 4 This motivates our proposed approach for using gradient information to simplify the SMT constraints.
Table (holes]s the SMT solver runtimes and whether the constraints were solved (SAT). We observe that with timeout of 60 minutes, the SMT solver could solve the full constraints for only 34 of the 100 images. Another interesting point to observe is that the solver could not solve any of the instances for digits 0 and 3. We also show for few MNIST images Figure
of the minimal masks generated by the SMT solver
Table 2: Solver Runtime and SAT instances. We report the average solver runtime and instances solved per digit with timeout set at 60 mins.
Digit
0
1
2
3
4
5
6
7
9
ALL
Runtime (mins)
N.A.
31.19
45.26
N.A.
33.09
35.68
42.80
53.11
36.05
19.62
35.59
SAT Instances 0/8
8/14
4/8
0/11
8/14
4/7
4/10
2/15
1/2
3/11
34/100
12

---

Published as a conference paper at ICLR 2021
Image
Image
Image
Image Confidence 1.00
Mask
Confidence: 1.00
Confidence: 0.39
Confidence: 1.00
Confidence: 0.50
Confidence 1,00
Confidence: 0.78
Confidence: 8888
Z abR
Ogt
Confidence: 1.00
Confidence: 0.60
Confidence: 1.00
Confidence 0.90
Confidence 1,00
Confidence: 0.56
Confidencer 1.00
Confidence: 0.85
4
5
Ogtic
Confidence: 1.00
Confidence 0.60
Confidence: 1.00
Confidence 0.53
Confidencer 0.92
Confidencer 0.65
Confidence: 1.00
Confidencer 0.45
7
Oitt11
Dee
Figure 5: MNIST images and the corresponding masks corresponding to Sec. 3.1.
B HYPERPARAMETER CHOICES
In our proposed approach, the choice of top-k, and 7 (Eqns. 3, 4, 5) have effect on the final quality of the explanations, and the time it takes for the solver to identify the mask. This section presents quantitative and qualitative comparisons for different choices of top-k and 7,.
B.
QUANTITATIVE COMPARISON FOR DIFFERENT CHOICES OF TOP-K AND ?
Fig.
presents quantitative comparisons for different choices of top-k and 7-
Runtime (seconds)
Sparsity (%)
LSC Scores
0.5
200
y=
y=
=
150
11.00
0.9
0.3
-1.15
0.9
0.1-
-1.25
0
1000
3000
5000
1000
3000
500
1000
3000
5000
Top-K
Top-K
Top-K
Figure 6: Hyperparameter Comparision
top-k We analyze images with top-k E (500, 1000, 3000, 5000). Increasing the l value increases the receptive field and the discovered input masks also grow in size with increasing values of k. Figure 6 shows how the solver runtime and the mask size vary with k. As expected, larger & values results in larger number of constraints and therefore larger solving times as well as larger mask sizes.
Gamma We analyze the effect of y E (0.0, 0.5, 0.9), also shown in Fig. We observe that by decreasing gamma values, the masks become sparser. The key reason behind this is that with smaller gamma values, the SMT'solver is less constrained to maintain the original neural activations for the selected neurons, and hence can ignore additional input pixels that do not have large effect. It is also noteworthy to notice that the solver run-time increases with decreasing value of 7.
13

---

Published as a conference paper at ICLR 2021
B.2 TOP-K Y IMAGENET QUALITATIVE EXAMPLES
Fig. presents qualitative examples of the saliency maps Imagenet examples for different choices of top-k and 7.
3.09%
5.29%
14.2%
28%
robin
70%
Tap 100
Top-
Top-K 1000
Top 3000
Top-C 5000
pelican
8.0
Top.K. 100
Top.C
Top K: 1000
Top K 3000
Top K 5000
4.55%
12 66%
18.9%
36.9%
40.31%
2.4%%
7.9 7.94%
90%
27 39%
00%
7.00
Top-K:
Top-R:
Figure 7: Qualitative examples of the masks generated by SMUG on examples from Imagenet for different choices of top-k (columns) and (rows). 7 0 is the most minimal mask. Even low values of top-k and y SMUG highlights pixels relevant for the object class.
14

---

Published as a conference paper at ICLR 2021
C QUALITATIVE TEXT EXAMPLES
Fig. 8 preseents additional examples comparing the output of SMUG with SIS, SMUG Chase. and IG on the Beer Reviews dataset.
SIS
SMUG
dark beer, upoure enice flnger and hal of creamy
darkt réce droger
deri eniie and
darit nice and
stery throug tout
crearry feam and stave thoogghout
half creaeyy stacs troouhhuud
creamyy foua iray throughout
taas rajor confee tactt with faons
cas may cotfer les tinte with
besr
cas cofoeriae saito wirl hasss
cas ragge foee tante os
bour coffee
0
how the portin creury sencctt mout
lowe the partinn crounry amooth mecut foou
how the porton cinemry semosh moutth oot
kwo th porter conuuryy imsouh maxr Fricet
croaiti uemme san di porser buti thel
onceit warme It'sar porter buni theil
once hnvermemm In's on dk porterbog bust bhst
once trwamss 3t's porter butt Seod
SMUG
SMUG
pouned hnlo aather, produces asrmal corfie heec that recuias quiddy- aleck typlcalimpp on the noio. litee bestet to 3MB00n
produces ammal Ooffee head reds quicdy
into forr, produces amall
ntterrr prosuces amall
coffee head replucss suiddy- breck
coffee reckcre city as
02 noed, d sosett cisocaat aoe Milicd
on the coso, diiteeiis botet coocaate 5ot 20.0
typical
the cood (iitee sedet csucoltta billod
tystcaal
0
bartwean inn gatiing plantt of slane ticchwe with hop siberrees nica moooth
fettween gatting plante slck
between hh getting planky of durk
befweem gedi mg planty thak
tiiibee with hop saterness rica smooth
en thee with hop biherrses rice emoorh
the thetees with hos battemnee dita mooorh
wouuld to have agai in mww.la with acimic aggl
stele connrall akout reoudd
coneall aloul reould huts ugain mapo withore age
Eurtors insodd "unce ugaili maabe withoorti agi on
fuvv spaiit mepii sorm age pn
5I5
SMUG
SMUG
very un devretdd tos pourt
avery underrned pe pours
sitryy undernned to pourt
avrryy und ratedddddd for poursa
coppoe sg
bog head
oopper eit orangen cutor bag
coppor viturr one ge lime. liste hooud
coppon wwtarrtttrttdoooo onange colo
kusb upalts time laste
lavis
lavi hoppe
with bouth pane tataameo,
loads pine graperrsl and
Ho the
but
flwoors "hut hor of iroptiaa fluvor reaybn come
grspattul and
ctrea Fluorr ding iepatruh
that hie tropicall Slvor couhhe
that tane mropical Racor macbe
that mopiral faeir mochhe
instonce in linu the botter cipor,
fssewcce in be
butter tipus
holonce ang See butter paie.
bethor plos. qputal hoppy and will belar cod supert:
cuile hoppy and well baalineed uppers
quisihosoy and wall baler aupert
quili haapy and yos boakinced superrs
continue rice evrry astinstion with every ottoring ig ioonuume
continues riss my optinaation with every offoring consume..
continues to rio my oxtinaaton with every offiring cor cornure.
continues ronin my est mation with over offlnigg consuree
SIS
SMUG
SMUG
IG
poured 2éea into
pouned from
thes Into barg
coured from 24ic large
pouree from
aposarsece rthir large
appeerence this deep
appearsece thes
trorce ambea color. the pone
bronse unbor colr Frr bow
becrua untiar eicobor In thee has somer
teor druember evcuka the hones
auu thuve sae seer sooigg vet and kot
Buu hans twe aooruligg we in elict
Puri have over shirukiigg ola and cta
that Thverrone oveeeve sodr pomulanng with bia lota
atall
acnes abound that an cal
E.a. cast
sit cadt
canogobe acDIE Elduud BNG dee cart
ger den the ploouer
eeolih
dan) the desse of
had of
Enowert 'ue bost
ladta only thee sworriess
cifoiie mononmees only lite nee poeethess
not
and lhto mvitt oweetheoss
bear up the torness reall
this flvor. the riberessreely
as th's beer
as beer warme bitternea
dominates
flyoor. tasting
I'
succe eminge anoma the rull pody
tite aromes mouthfeel ful body
subdl orange mouthhelll body
sutres crange aromse anreeell body
with cardonation deu spemion sere wake
with cartonation
thaaber carhonal
with carbonation ovenaal
the thse sparin to 'enuadd'
th eirry coe oue da autturnnaccs is
tnoighine bennbeel for 5.0 ao much
bought no lean bed for 3.7 mochh
bought my loadded 5 3399 much
tought my boomboo hor 2.3 po much
haa no equar..
has equal.
tas rouuaa
na equil.
SIS
SMUG
SMUG
IG
bottle Parners the trii
vo gloss thes hord to fingln
Terrerr sos the so tidin
torrees goos the Teciin
somerre recioon but
outy rixe
but
logel an iolidd....
butodo. mari veloow
an idlado.
kieddo... low with very than wedte head the flacc
apprarance with vary tf wnite head, ite
apprarance with very this whihe head the
appesmance with thin whii head the
flacr"
(tready compiin, with
ED coving
ikart follwing
moadl complees with
thilwiing
coally complen snierr folowingg
dirlllaon lovaty wha base wnv really
and louat other halte waw raaly
and wldaabyy other kases if thely
an bearrraft Last di iivorralll
gon and it iinia in's the beee for krnwery.....
nut try tran la the beet bor
gn and i. maaa in the beit so bar
oo pu try irtina in's the beit to
Figure& 8: Examples comparing our method (SMUG, SMUG with SIS and IG on test samples from the Beer Reviews dataset. Green color signifies a positive relevance, red color signifies negative relevance. The underlined words are human annotations.
D ADDITIONAL QUALITATIVE IMAGE EXAMPLES: SMUG
Fig. 9 presents boolean masks and the saliency maps produced by SMUG on several ImageNet examples. Fig. 10 and present additional examples comparing the saliency masks and bounding box (for LSC) produced by SMUG, SMUG base: and IG.
15

---

Published as a conference paper at ICLR 2021
Image
Mask
Saliency Map
Image
Mask
Saliency Map
Spmn
Figure 9: Examples showing the boolean masks and the saliency maps produced by SMUG on several ImageNet examples.
16

---

Published as a conference paper at ICLR 2021
GroundTruth 2.11 Uuu025, red
SMUG 14 dhudis mxtan
IG
GroundTruth Deiieess Fad M4
SMUG AA Fodi
SMUG
ddd D- (-8811
Gi Deel DEL
book
blocco seecooooed teme:
scas
1.722 2-tual
002
0..
u.i Comerss oegai
lamd c-l.m
lembild
(e+02) (m6.2)
lam0.32,
1.33 lambil
land (1241)
Muigger
st jawd 21, cat 16 iadiiss dwnt 941
94 Uset 14 001
n Dast (wl
typewrite keyboard
prey wha
choco site sauce.
dogpled
1..6.JN-014 a-d 600
2.33 mediil m10.77)
1430-63 expan
1.31 (2-002 co1.0
3..0 iaed crbaa
2.42 jand 26, end 80
20 (and.4) eai col
haicker
armodillo
Figure 10: Examples comparing saliency maps where SMUG outperforms SMUG IG. The green box on the original image highlights the groundtruth box; for the saliency methods it represents the bounding box with the best LSC score. Numbers on top denote the LSC score, the fractional area of the bounding box (a), and the confidence of the classifier (c) on the cropped region.
GroundTruth
SMUG
SMUG
GroundTruth
SMUG
fire engire
safecy P
230 HL cub
233 (- 10, c-0.0
1M0 (2- C-0.3st
1.33 O USL, C-0AA
K3 (a 1K C-5..0)
1L72 Eittet
3.th -21 C-U
permiic bars
Indm
Cha naublus
Figure 11: Examples comparing saliency maps where SMUG or IG outperforms SMUG. The green box on the original image highlights the groundruth box; for the saliency methods it represents the bounding box with the best LSCC score. Numbers on top denote the LSC score, the fractional area of the bounding box (a), and the confidence of the classifier (c) the cropped region.
17

---

Published as a conference paper at ICLR 2021
D.1 BIASES
Model explanation techniques can also be particularly useful in studying model biases. Fig. 12 shows some examples where the model correctly predicts the class "parallel bars" but it appears actually focus more on the person leaping over the bar to make the prediction as opposed to looking the bar itself. These can help understand and identify cases where the model has developed bias (in this case, based on training data).
Truth 2.00 20 06, Cor
SMUG Ko Ihr 17, CHilnni
SMUG base St liep C-l
IG
0.2 Bat E-g
horiiooicall bar
noriiznnall bar
per alle bars
21, 2w0.00
62, c=0.00 4.22 (e+2.6 c-ba0) 01 cmo
paraile! bars.
Figure 12: [Model bias] Examples where the model correctly predicts the class "parallel bars" and "horizontal bars" for the corresponding inputs but the model's focus is on the person leaping over the bar opposed the bar (i.e., the predicted object class) itself.
E SMT CONSTRAINTS
In this section, we present an example set of SMT constraints obtained by our technique for an example image from ImageNet. For brevity, we show the set of constraints for k = 5 and y 0. As mentioned in Sec 5.1, each masking variable M,y corresponds to a x grid of pixels, where the grid is denoted by X2si43.jsi+3. For example, the mask variable M 135 corresponds to the pixel grid X 132:135, 1ete13s,112211555 132:135- Following Eq. 3 the SMT constraints corresponding for top attributions in the first layer are given by:
IG positive
99.53X132.11 132,132 18.37X182.136 + 1.88X132.110 - 141.25xX33.188 + 639.97 1...97XX366.18 136 10.29 136,140
9.66X110.188 + 20.30.X 25. 25.19XX10.11 14.110 0.58 >> 0
-270.67 + 101. 101.23.M14.144 + 10.38. 207 207.98.M122.12
6440.44M221.121
100.72MM211125 +
25.06.121.165
75.499M221115 + 75.47.M12.151 - 0.36 > 0
2925.38X144,112 395.09X144.136
+ 81.61
009.88X148.118 - 82.70X
17.08X + 0.21
122.72
929. +5 133.
0
231.34X 1644XXX8814481111 122.
0.12 >
18


Reviews:
[{"review_id": "ZsR4kM9vp02", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the question of identifying which input features are most important for a neural network's decision. To do so, it frames the problem as an SMT problem that seeks to select the best input features, without changing the state of the first layer too much. The paper shows experiments, primarily on image classification, and also examples of how the approach may be applied to text classification.\n\nThere are a couple of things that the paper combines in its final work: (a) using integrated gradients to score the first layer nodes, (b) restricting the search to only the top-k layer one neurons, and (c) applying SMT to find the subset among them that best preserves the layer 1 activations. The experiments do a good job of comparing the contribution of these components.\n\nHowever, from the experiments, it looks like the third step (i.e. SMT) is not really necessary, both from the quantitative and qualitative results. The paper argues in the paragraph titled SMUG vs SMUG_{base} that the latter does not provide sparse input features. It is not clear why sparsity is a desirable quality here. We are looking for image regions that best contribute to the output, in which case smoothness in the regions may even be preferred over sparse explanations that pick out specific pixels. It would be good to clarify this.\n\nThe paper claims that it is not a good idea to use an SMT based explanation that focuses on the final layer. The complexity argument makes sense but could perhaps be mitigated by an extension of the top-k strategy, perhaps. But the argument that the masked inputs are out of training distribution is not mitigated by the proposed approach. If the masked inputs are out of distribution for the full network, then certainly they are out of distribution for the layer one activations too (eq 2). Is the out-of-distribution issue really a problem, and if so, why doesn't it affect the first layer?\n\nThe SMT problems in (2) and (3) ask for a mask such that for every node in the k selected ones, the first layer activation with masked inputs is more than a scaled version of the first layer activation for the original input. This one-sided inequality seems to be tied to the fact that the experiments use ReLU activations. For example, if an activation for a certain neuron is highly negative, and we use a different activation function (say tanh), then we would want a similarly negative output for the masked inputs too. It may be worth mentioning this somewhere (maybe a footnote).\n\nThe experiments on images seem interesting (with the caveat about the need for SMT at all). But the experiments with text only show examples, which makes it only anecdotal. It would be interesting to compare to the results of crowd sourcing experiments where the most important words are chosen, or perhaps asking turkers to pick from the words selected by the proposed method and other interpretability methods (e.g. HotFlip, etc).\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KRuWUiIK1Qa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper presents a method to encode the minimal input feature discovery problem -- finding the minimal set of features in a input that is necessary for a prediction -- into a form that can is amenable to satisfiability modulo theory (SMT) solvers.  In particular they first use the integrated gradients methods to score first-layer neurons on the degree to which they influence the prediction.  Then, they produce and solve an SMT problem that finds the minimal mask that changes these influential neurons.  They demonstrate their approach on several problems.\n\n## Review\n\nOverall I thought this was an interesting paper with practical utility.\n\n- The formulation is interested and is a novel balance of quite different methodologies with useful results\n- The paper is clear and fairly well written, but some higher level intuition about the approach would help\n- I'd like to see some more justification for focus on the first layer, and experiments (described below)\n\nIn section 3.2 you mention that you use IG to \"score the neurons in order of relevance by treating the first layer activations as an input to the subsequent network\".    It's not clear to me whether the $d$ in the function $F: R^{a\\times b \\times c} \\to [0, 1]^d$ is the set of all nodes in the neural network or just the first layer or just the final layer?   It seems the latter is the case, based on Equation 2.\n\nMore generally, it's not clear to me what privileges the first layer in this work (Eq 2).  My understanding is that\n1. simply that restricting attention to the first layer allows SMT to be applicable\n2. You use IG to integrates information from all layers, and by restricting Eq 2 to $D^k$ you are effectively combining both methods\n\nThis leads to an experimental question: do your explanations improve if you include more than one layer?  This seems like something that is easily testable, at least on small examples.\n\nWriting wise, some of the terms could me more clearly defined.  For instance in the definition of $F$ above, I am left guessing as to what what $a$, $b$, $c$ and $d$ are, and assume they are simply place holders.  Similarly, sometimes we have $N_\\theta(x)$ and sometimes $N_\\theta(X)$.", "extra_scores": {}, "extra_text": {}}, {"review_id": "BvFt1Ms8kxz", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper improves the Integrated Gradient (IG) based model explanations by picking the top-k activated neurons in the first layer and choosing a subset of inputs making sure top-k activated neurons still active enough according to a certain threshold. \n\nI appreciate the authors' contribution to improving IG, but feel certain claims are inappropriate. I hope the authors could help to clarify and correct any misunderstandings I may have. \n\nAlthough the paper title suggests scaling symbolic methods (e.g. SMT-based approaches), the proposed approach SMUG does not necessarily rely on SMT at all. Since ReLU is not considered by SMUG, integer programming (for encoding whether an input dimension is selected) should be sufficient. The way of scaling symbolic methods appears to be simply \"avoid using them\". Also, it is unfair to blame that SMT-based approaches for neural network verification are not scalable while SMUG could handle much larger networks, because SMUG really solves a _different_ problem. \n\n\nQuestions:\nQ1: The authors argue \"From Table-1, we observe that SMUG and SMUGbase achieve a significantly better score (−1.26 and −1.23 resp.) compared to IG (−0.34).\"  However, IG actually achieves -0.29, which is more closer to the GroundTruth (-0.34). Does that imply IG is actually better?\n\nQ2: In figure-5, the mask achieves fairly low confidence (e.g. less than 0.7 for most examples). Why is that?\nIs it a fundamental weakness even for full SMT encoding?  Furthermore, suppose scalability is not an issue, would SMUG always behave worse than full SMT encoding (thus suffer from the same weakness)?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0LAIrjVAJRN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides an interesting pos-hoc explanation method to identify relevant features in an input that may inform a trained neural model's prediction. The task is to identify a binary mask over input image/text such that the masked input yields almost similar prediction as original input. The author formulates this as an SMT solver task, but instead of making sure that the output prediction is similar (which involve multiple time consuming pass over potentially huge networks), they make sure that high influential neurons in first layer of the network are still activated. This provides a less time consuming way to evaluate invariance of masked input.\n\nThe evaluation is done on multiple datasets - ImageNet, MNIST and Beer Reviews. The authors compare against previous continuous saliency baselines (IG and GradCAM) and full SMT solver method SIS, in addition to ground truth annotations for bounding boxes. They find that their method, called SMUG, is better performing in terms of LSC metric (which measure the log ratio of percentage of pixels preserved vs confidence in ground truth prediction). They also do some qualitative analysis and found that SMUG tend to produce low area masks. They do not perform any systematic human study to evaluate their method.\n\nThe paper as written is quite clear and I was able to parse the information with reasonable ease. \n\nAs it is, I will recommend acceptance for the paper. But I believe addressing following comments will make this paper better.\n\nQuestions/Comments:\n1. The LSC metric is combines the two quantities that don't have any direct scaling relation with each other - area of box and confidence in prediction. For example, going from 0.5 to 0.6 is more important than going from 0.8 to 0.9 in terms of confidence. The same cannot be said for the area. Putting the two together hides information necessary for comparison. For example, are the low values for IG mainly because of large bounding boxes ? I would suggest presenting both results separately along with LSC.\n\n2. A proxy for human study would be to measure the overlap of SMUG results with provided bounding boxes.\n\n3. Why does bilinear interpolation not move data out of distribution ? For example, focusing on face of cat as bounding box and then blowing up should clearly put it OOD ? Am I missing something here ?\n\n4. I am not clear on why restricting your analysis to top-k influential neurons is correct. What if the masked image activate the non-influential neurons -- one see no reason why it won't change the prediction. The IG values are only true for the original image. For example, say for original image, the set of influential neurons is IF and non-influential ones are NIF. If the SMUG masked image activates all of IF neurons and only 10% of NIF neurons, we can get completely predictions. And vice versa. I would suggest running an experiment (for even a small task) where all neuron values are considered and see what the behavior is. (If you have done this experiment, please point me to the relevant section in the paper -- I can't seem to find it).\n\n5. While they are not pos-hoc methods, following paper also try to learn masks as form of interpretation. Please consider citing them -\nhttps://arxiv.org/pdf/1802.07814.pdf , https://arxiv.org/abs/1606.04155, https://www.aclweb.org/anthology/P19-1284v1.pdf, https://arxiv.org/abs/2005.00115, https://arxiv.org/abs/2004.14992\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper combines considers the task of finding a minimal set of inputs that explain predictions of trained neural models. The authors propose a method that they refer to as "scaling symbolic methods using gradients" (SMUG). This method use integrated gradients methods to score first-layer neurons on the degree to which they influence the prediction and then produces and solve an SMT problem (restricted to first-layer activations) that finds the minimal mask that changes these influential neurons. 

Reviewers had somewhat mixed perspectives on this submission. All reviewers were broadly in agreement that the paper is clearly written and presents an interesting combination of symbolic (i.e. SMT-based) and gradient-based methods for model explanation. R2 questions the need for sparsity (and therefore the SMT component) in model explanations, and R3 similarly notes that SMUG does not necessarily rely on SMT at all. That said, no reviewers raise major concerns with the quality of exposition, experimental evaluation, or the level of technical contributions in this work. The metareviewer is inclined to say that this work is above the bar for acceptance, and represents a reasonable approach to integrating SMT-based and gradient-based methods for model explanation.
Decision: Accept (Poster)