Reliable Post hoc Explanations: Modeling Uncertainty in Explainability
Authors: Dylan Z Slack
Sophie Hilgard
Sameer Singh
Himabindu Lakkaraju
Venue: NeurIPS 2021 Poster (2021)
Keywords: explanations
interpretability
robustness

Abstract: As black box explanations are increasingly being employed to establish model credibility in high stakes settings, it is important to ensure that these explanations are accurate and reliable. However, prior work demonstrates that explanations generated by state-of-the-art techniques are inconsistent, unstable, and provide very little insight into their correctness and reliability. In addition, these methods are also computationally inefficient, and require significant hyper-parameter tuning. In this paper, we address the aforementioned challenges by developing a novel Bayesian framework for generating local explanations along with their associated uncertainty. We instantiate this framework to obtain Bayesian versions of LIME and KernelSHAP which  output credible intervals for the feature importances, capturing the associated uncertainty. The resulting explanations not only enable us to make concrete inferences about their quality (e.g., there is a 95% chance that the feature importance lies within the given range), but are also highly consistent and stable. We carry out a detailed theoretical analysis that leverages the aforementioned uncertainty to estimate how many perturbations to sample, and how to sample for faster convergence.  This work makes the first attempt at addressing several critical issues with popular explanation methods in one shot, thereby generating consistent, stable, and reliable explanations with guarantees in a computationally efficient manner. Experimental evaluation with multiple real world datasets and user studies demonstrate that the efficacy of the proposed framework.

Reliable Post hoc Explanations: Modeling Uncertainty in Explainability
Dylan Slack UC Irvine dslack@uci. edu
Sophie Hilgard Harvard University ash7980g. harvard. edu
Sameer Singh
Himabindu Lakkaraju Harvard University
UC Irvine sameerQuci.edi
hlakkaraju@hbs. edu
Abstract
As black box explanations are increasingly being employed to establish model credibility in high stakes settings, it is important to ensure that these explanations are accurate and reliable. However, prior work demonstrates that explanations generated by state-of-th oo-tth--rtt techniques very little insight into their correctness and reliability. In addition, these methods are also computationally inefficient, and require significant hyper-parameter tuning. In this paper, we address the aforementioned challenges by developing a novel Bayesian framework for generating local explanations along with their associated uncertainty. We instantiate this framework to obtain Bayesian versions of LIME and KemneISHAP which output credible intervals for the feature importances, capturing the associated uncertainty. The resulting explanations not only enable us to make concrete inferences about their quality (e.g., there is 95% chance that the feature importance lies within the given range), but are also highly consistent and stable. We carry out detailed theoretical analysis that leverages the aforementioned uncertainty to estimate how many perturbations to sample, and how to sample for faster convergence. This work makes the first attempt at addressing several critical issues with popular explanation methods in one shot, thereby generating consistent, stable, and reliable explanations with guarantees in a computationally efficient manner. Experimental evaluation with multiple real world datasets and user studies demonstrate that the efficacy of the proposed framework."
inconsistent, unstable, and provide
Introduction
As machine learning (ML) models get increasingly deployed in domains such as healthcare and criminal justice, it is important to ensure that decision makers have a clear understanding of the behavior of these models. However, ML models that achieve state-of-the-art accuracy are typically complex black boxes that are hard to understand. As consequence, there has been surge in post hoc techniques for explaining black box models [1-10]. Most popular among these techniques are local explanation methods which explain complex black box models by constructing interpretable local approximations (e.g.. LIME [2], SHAP [4], MAPLE [11], Anchors [1]). Due to their generality, these methods are being leveraged explain number of classifiers including deep neural networks and ensemble models in a variety of domains such as law, medicine, and finance [12, 13].
Existing local explanation methods, however, suffer from several drawbacks. Explanations generated using these methods may unstable [14-18], i.e., negligibly small perturbations to an instance result in substantially different explanations. These methods are also inconsistent [19] i.c., multiple runs on the same input instance with the same parameter settings may result in vastly different explanations. There also no reliable metrics to ascertain the quality of the explanations
Project Page: https://dylansleee htt.///wwwwbbbitttoooe/e/eee/eee html
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Misdameanor Charge
Female
Prions Count
Count
Female
Felony Charge
Misdemeanor Charge
Length of Stay
Race
0.00
0.05 0.10
0.15 0.20 8.25 0.30
0.00 8.05 0.10 0.15 0.20 0,25 0.30
Absolute Feature Importance
Absolute Feature Importance
(a) Explanation computed with 100 perturbations
(h) Explanation with 2000 perturbations
Figure I: Example explanations on for an instance from the COMPAS dataset, where vertical lines indicate the feature importance by LIME (red negative effect, green is positive) and the shaded region visualizes the uncertainty estimated by BayesLIME. While LIME produces very different and contradictory feature importance for different number of perturbations (1a and lb), BayesLIME provides more context. The overlapping uncertainty intervals in the explanation computed with 100 perturbations (1a) indicate that it is unclear which feature is the most important. However, the tighter uncertainty intervals in the explanation computed with 2K perturbations (Ib) clearly indicates that Female is the most important.
output by these methods. Commonly used metrics such as explanation fidelity rely heavily on the implementation details of the explanation method (c.g., the perturbation function used in LIME) and do not provide true picture of the explanation quality [20]. Furthermore, there exists little to no guidance on determining the values of certain byperparameters that are critical to the quality of the resulting local explanations (e.g.. number of perturbations in case of LIME). Local explanation methods are also computationally inefficient i.e., they typically require a large number of black box model queries to construct local approximations [21]. This can be prohibitively slow especially in case of complex neural models.
In this paper, we identify that modeling uncertainty in black box explanations is the key to addressing all the aforementioned challenges. To this end, we propose a novel Bayesian framework for generating local explanations along with their associated uncertainty. We instantiate this framework to obtain Bayesian versions of LIME and KerneISHAP, namely BayesLIME and BayesSHAP, that not only output point-wise estimates of feature importance but also their associated uncertainty in the form of credible intervals (See Figure 1). We derive closed form expressions for the posteriors of the explanations thereby eliminating the need for any additional computational complexity. The credible intervals produced by our framework not only allow us to make concrete inferences about the quality of the resulting explanations but also produce explanations that satisfy user specified levels of uncertainty (e.g., an end user may request for explanations that satisfy certain 95% confidence level). In addition, the resulting explanations are also highly consistent and stable. To the best of our knowledge, this work makes the first attempt at addressing several critical challenges in popular explanation methods in one-shots, thereby generating consistent, stable, and reliable explanations with guarantees in a computationally efficient manner.
We carry out theoretical analysis that leverages the measures of uncertainty (credible intervals) produced by our framework to estimate the values of critical hyperparameters. More specifically, we derive a closed form expression for the number of perturbations required to generate explanations that satisfy desired levels of confidence. We also propose a novel sampling technique called focused sampling that leverages uncertainty to determine how to sample perturbations for faster convergence, thereby enabling our framework to generate explanations in a computationally efficient manner.
We evaluate the efficacy of the proposed framework on a variety of datasets including COMPAS, German Credit, ImageNet, and MNIST. Our results demonstrate that the explanations output by our framework are not only highly reliable, but also very consistent and stable (53% more stable than LIME/SHAP on an average). Our experimental results also confirm that we can accurately estimate the number of perturbations needed to generate explanations with a desired level of uncertainty, and that our uncertainty sampling technique speeds up the process of generating explanations by up to a factor of 2 relative to random sampling of perturbations. Lastly, we carry out a user study with 31 human subjects to evaluate the quality of the explanations generated by our framework, demonstrating that our cxplanations accurately capture the importance of the most influential features.

---

2 Notation & Background
Here we introduce notation and discuss two relevant prior approaches, LIME and KernelSHAP.
+ [0, 1] denote a black box classifier that takes a data point x with d features, and returns the probability that belongs
Notation Let f: -
certain class. Our goal is to explain individual predictions of f. Let & E IRd denote the explanation in terms of feature importances for the prediction [ar), i.e. coefficients é are treated as the feature contributions that Φ captures the coefficients of a linear model. Let 2 be a set of N randomly sampled instances (perturbations) around z. The proximity between x and any Z E Z is given by Tz (2) E E. We denote the vector of these distances over the N perturbations in Z as II, ( E R. Let Y E [0, 1] be the vector of the black box predictions f() corresponding to each of the N instances in Z.
the black box prediction. Note
LIME [2] and KernelSHAP [4] are popular model-agnostic local explanation approaches that explain predictions of a classifier f by learning linear model é locally around each prediction (i.e. z)2 2). The objective function for both LIME and KernelSHAP constructs an explanation that approximates the behavior of the black box accurately in the vicinity (neighborhood) of x.
arg min
-1( d²" 21
SE2
The above objective function has the following closed form solution:
क = (z" (llgg(I)((2)) + +1) +1) (z" diag"
(2)
The main difference between LIME and KernelSHAP lies in how (z) is chosen. LIME, is chosen heuristically: (=) is computed as the cosine or l2 distance. KemelSSHA leverages game theoretic principles to compute Tz (z). guaranteeing that explanations satisfy certain properties.
3 Our Framework: Bayesian Local Explanations
In this section, introduce our Bayesian framework which is designed capture the uncertainty associated with local explanations of black box models. First, we discuss the generative process and inference procedure for the framework. Then, we highlight how our framework can be instantiated to obtain Bayesian versions of LIME and SHAP. Lastly, we present detailed theoretical analysis for estimating the values of critical hyperparameters, and discuss how to efficiently construct highly accurate explanations with uncertainty guarantees using our framework.
3.1 Constructing Bayesian Local Explanations
Our goal here is explain the behavior of a given black box model f in the vicinity of an instance while also capturing the uncertainty associated with the explanation. To this end, we propose a Bayesian framework for constructing local linear model based explanations and capturing their associated uncertainty. We model the black box prediction of each perturbation 2 a linear ( combination of the corresponding feature values (ø 2) plus an error term (E) as shown in Eqn (4). While the weights of the linear combination á capture the feature importances and thereby constitute our explanation, e captures the error that arises due to the mismatch between our explanation e and the local decision surface of the black box model f. Our complete generative process is shown below:
1/2, 0. (a
oTz+e c~N(0.
(3)
Φ1 ~ 00)
o² ~ Inv-x (no, o3)
(4)
The error term is modeled as a Gaussian whose variance relies on the proximity function T. (z) i.c., _
-O( x.lz) This proximity function ensures that perturbations closer to the data point are modeled accurately, while allowing more room for error case of perturbations that are farther away
(z))) can be computed using cosine or la distance or other game theoretic principles similar to that of LIME and KernelSHAP (see Section 2). The conjugate priors on á and o² are shown in Eqn (4). Note that, the distributions on error and feature importance ó both consider the parameter o². The
3

---

fact that the prior on the feature importances considers x² has an intuitive interpretation: if we have prior knowledge that the error of the explanation is small, we expect be more confident about the feature importances. Similarly, if we have prior knowledge the error is large, we expect to be less confident about the feature importances.
Thus, our generative process corresponds to the Bayesian version of the weighted least squares for- mulation of LIME and KemelSHAA outlined in Eqn. (1), with additional terms to model uncertainty, As in Eqns (4), the process captures two sources of uncertainty in local explanations: 1) feature importance uncertainty: the uncertainty associated with the feature importances Ø, and (2) error uncertainty: the uncertainty associated with the error term which captures how well our explanation models the local decision surface of the underlying black box.
Inference Our inference process involves estimating the values of two key parameters: e and 0². By doing so, we can compute the local explanation as well as the uncertainties associated with feature importances and the error term. Posterior distributions ó and o² are normal and scaled Inv-x?. respectively, due to the corresponding conjugate priors [22]:
0² P12,Y Y Scaled-Inv-x no + N, Boog + No² no + N
0 Z,Y Normal Vooo)
(5)
Further, 3. Vá. and s² can be directly computed:
Vol Vo( (2" (Ix
(6)
V 2 (Ia. +
z² 1 (X z6)² (Z) z
(7)
N
Details of the complete inference procedure including derivations of Eqns. (5-7) are provided in the Appendix A. Note that our estimate of the posterior mean feature importances & (Fqn. (6)) is the
same as that of the feature importances computed in case of LIME and KernelSHA (Eqn. (2)).
Remark 3.1. If we use the same proximity function [2(2) in our framework as in LIME or Ker- nelSHAP, the posterior mean of the feature importance à output by our framework (Eq (6)) will be equivalent to the feature importances output by LIME or KernelSHAP, respectively.
Feature Importance Uncertainty To obtain the local feature importances and their associated
uncertainty, we first compute the posterior mean of the local feature importances & using the closed form expression in Eqn. (7), We then estimate the credible interval (measure of uncertainty) around the mean feature importances by repeatedly sampling from the posterior distribution of Φ (Eq (5)).
Error Uncertainty The етrоr term can serve proxy for explanation quality because it captures the mismatch between the constructed explanation and the local decision surface the underlying black box. We first calculate the marginal posterior distribution of by leveraging Eqqn (4) and integrating out o². This results in a three parameter Student's I distribution (derivation in appendix A):
e|2,Y Y ~ t(v=no+ + N) (0, Boo + 22
(8)
710 + N
We then evaluate the probability density function (PDF) of the above posterior at 0, i.c., P(e = 0) by substituting the value of s2 computed using Eqn. (7) into the Student's distribution above (Eqn. (8)). The resulting expression gives us the probability density that the explanation output by our framework perfectly captures the local decision surface underlying the black box. This operation is performed in constant time, adding minimal overhead to non-Bayesian LIME and SHAP. We illustrate how these computed intervals capture the variance the explanations Figure 9.
Proposition 3.2. As the number of perturbations around goes to oc ie.,, N - oo: (1) the estimate of & converges to the true feature importance scores, and uncertainty 0. (2) uncertainty of the error term converges to the bias of the local linear model 6. [Details in Appendix B]
BayesLIME, and BayesSHAP Our framework can be instantiated to obtain the Bayesian version of LIME by setting the proximity function to (2) exp(-D(e 2)2 /02) where D is a distance metric

---

(e.g. cosine or le distance), and and o to small values (10 9) so that the prior is uninformative. We compute feature importance uncertainty and error uncertainty for LIME's feature importances.
Our framework can also be instantiated to obtain the Bayesian version of KernelSHAP by setting uninformative prior on o² and (2) cd =]]]=[(d--=]) where |z| denotes the number of the variables in the variable combination represented by the data point 2 i.e., the number of non-zero valued features in the vector representation of Note that the original SHAP method views the problem of constructing a local linear model as estimating the Shapley values corresponding to each of the features [4]. These Shapley values represent the contribution of each of the features to the black box prediction i.c., f(z) = Φo + Σ Φi, Therefore, the measures of uncertainty output by our method BayesSHAP capture the reliability of the estimated variable contributions.
d-1
To encourage BayesLIME and BayesSHAP explanations to be sparse, we can use dimensionality reduction feature selection techniques as used by LIME and SHAP to obtain the top K features [2, 4, 23]. We can then construct our explanations using the data corresponding to these top K features.
3.2 Estimating the Number of Perturbations
One of the major drawbacks of approaches such as LIME and KernelSHAP is that they do not provide any guidance on how to choose the number of perturbations, a key factor in obtaining reliable explanations in an efficient manner. To address this, we leverage the uncertainty estimates output by our framework to compute perturbations-tn to (G), an estimate of how many more perturbations are required to obtain explanations that satisfy desired level of certainty. This estimate thus predicts the computational cost of generating an explanation with a desired level of certainty and can help determine whether it is even worthwhile credible interval (denoted as a) and the maximum width of the credible interval (W), e.g. "width of 95% credible interval should be less than 0.1" corresponds for the local explanation of a data point we first generate S perturbations around x (where S is small and chosen by the user) and fit a local linear model using our method? This provides initial estimates of various parameters shown in Eqns (5)-7) which can then be used to compute G.
do so. The user specifies the confidence level of the
0.95 and W 0.1. To estimate G
Theorem 3.3. Given seed perturbations, the number of additional perturbations required (G) to achieve credible interval width W of feature importance for data point x at user-specified confidence level a can be computed as:
4s
G(W,a,
S
2
W 4
x
(a)
where R is the average proximity (x(2) for the S perturbations, sgg the empirical sum of squared errors (SSE) between the black box and local linear model predictions, weighted by (2),), as in (7), and & 1 (a) is the two-tailed inverse normal CDF at confidence level a.
Proof (Sketcht) To estimate G, first relate W and Var(e:), the marginal variance of the feature importance' for any feature i, obtained by integrating out o². Because Student's i can be approximated by Normal distribution for large degrees of freedom (here, S should be large enough), we use the inverse normal CDF to calculate credible interval width at level a. We compute Vg from (6) using 2, treating its entries Bernoulli distributed with probability 0.5. Due to the covariance structure of this sampling procedure, the resulting variance estimate after N samples is the sample 4 (derivation in appendix B). If assume SSE scales linearly with S, As can take this to be a reasonable estimate of &y at any N. We can then estimate G as
SSE s scaled by
W
4
48
Var(
G
S.
(a)
ng (G+ (G+S) S)
(10)
W
(aa
We assume a simplified feature space where features are present or absent according to Bernouli(.5). As in Ribeiro et al. [2], these interpretable features are flexible and can encode what is important to the end user. Sinne the error depends primarily the number of perturbations, Var(áx) is similar across features.
5

---

3.3 Focused Sampling of Perturbations
Perturbations-to--a (G) provides us with an estimate of how many samples are required achieve reliable explanations. However, if G is large, querying the black-box model for its predictions on large number of perturbations can be computationally expensive for larger models [24, 25J. To reduce this cost, we develop alternative sampling procedure called focused sampling which leverages uncertainty estimates to query the black box in a more targeted fashion (instead of querying randomly), thereby reducing the computational cost associated with generating reliable explanations. Inspired by active learning [26], focused sampling strategically prioritizes perturbations whose predictions the explanation is most uncertain about, when querying the black box. This enables the focused sampling procedure to query the black box only for the predictions of the most informative perturbations and thereby learn accurate explanation with far fewer queries the black box.
To determine how uncertain our explanation is about the black box label for any given instance we first compute the posterior predictive distribution for (derivation in Appendix A), given as 22) Y t(v==) 2, V + ))s²). The variance of this three parameter student's t distribution is,
var (i(())
(N/) 2))
(11)
We refer to this variance the predictive variance var(ū(=)). and captures how uncertain our explanation ø is about the black box prediction.
The focus sampling procedure first fits the explanation with initial S perturbations (where S is small number). We then iterate the following procedure until the desired explanation certainty level reached. We draw batch of A candidate perturbations, compute their predictive variance with the Bayesian explanation, and induce a distribution over the perturbations by running softmax on the variances with tempurature parameter We draw batch of B perturbations from this distribution and query the black box model for their labels. Finally, we refit the Bayesian explanation on all the labeled perturbations collected far. We provide pseudocode for the uncertainty sampling procedure in Algorithm 1.
Algorithm Focused sampling for local explanations
Require: Model f. Data instance æ, Number of perturbations N, Number of seed perturbations S, Batch size B, Pool size A, tempurature т
1: function FOCUSED SAMPLE
2: Initialize Z with S seed perturbations.
3: Fit e on Z
Using Eqn (6)
4: for - to N - S' in increments of B do
5:
Q Generate A candidate perturbations
6:
Compute var()(=)) on Q Define Qaist as exp( exp(var(j) (())
> Using Eqn (11)
7:
8:
Qnew + Draw B samples from Quist
9:
2 2 Quew; Fit & on 2
D Using Eqn (6)
10:
end for
11: return à
12:
end function
Experiments
We evaluate the proposed framework by first analyzing the quality of our uncertainty estimates i.e., feature importance uncertainty and error uncertainty. We also assess our estimates of required perturbations (G), and evaluate the computational efficiency of focused sampling. Last, we describe user study with 31 subjects to assess the informativeness of the explanations output by our framework.
Setup We experiment with a variety of real world datasets spanning multiple applications (e.g.. criminal justice, credit scoring) as well as modalities (e.g., structured data, images). Our first struc- tured dataset is COMPAS [27], containing criminal history, jail and prison time, and demographic attributes of 6172 defendants, with class labels that represent whether each defendant rearrested

---

BayesLIME
BayesSHAP
BayesLIME
BayesSHAP
TABULAR DATASETS
MNIST
COMPAS
95.5
87.9
Digit
95.8
98.4
German Credit
96.9
89.6
Digit
95.8
97.4
IMAGENET
Digit 3
95.2
96.3
Corn
94.6
91.8
Digit 4
97.2
90.1
Broccoli
91.4
89.2
Digit 5
95.2
95.6
French Bulldog
94.8
89.9
Digit 6
96.7
96.8
Scuba Diver
92.4
94.6
Digit 7
95.7
95.3
Table 1: Evaluating Credible Intervals. We report the % of time the 95% credible intervals with
100 perturbations include their true values (estimated on 10, 000 perturbations). Closer to 95.0 is better. Both BayesLIME and BayesSHAP are well calibrated.
within 2 years of release. The second structured dataset is the German Credit dataset from the UCI repository [28] containing financial and demographic information (including account information, credit history, employment, gender) for 1000 loan applications, each labeled as "good" or "bad" customer. We create 80/20 train/test splits for these two datasets, and train a random forest classifier (sklearn implementation with 100 estimators) black box models for each (test accuracy of 82.8% and 72.5%, respectively). We also include popular image datasets
and Imagenet. For the MNIST [29] handwritten digits dataset, we train 2-layer CNN predict the digits (test accuracy of (.). For Imagenet [30], we use the off-the-shelf VGG16 model [31] as the black box. We select sample of 100 images of the following classes French Bulldog, Scuba Diver, Corn, and Broccoli to use in the experiments. For generating explanations, we use standard implementations of the baselines LIME and KernelSHAP with default settings [2, 4]. For images, we construct super pixels as described in [2] and use them as features (number of super pixels is fixed to 20 per image). For our framework, the desired level of certainty expressed as the width of the 95% credible interval.
Quality of Uncertainty Estimates A critical component of our explanations is the feature impor- tance uncertainty. To evaluate the correctness of these estimates, we compute how often true feature importances lie within the 95% credible intervals estimated by BayesLIME and BayesSHAP. Note, that by true feature importance, we refer to the best linear model output using either the LIME or SHAP kernels. We evaluate the quality of our credible interval estimates by running our methods with 100 perturbations to estimate feature importances and taking the corresponding 95% credible intervals for each test instance. We compute what fraction of the true feature importances fall within our 95% credible intervals. Note, because there are no methods to provide uncertainty estimates for LIME and SHAP, we do not provide further baselines. Since we do not have access to the true feature importances of the complex black box models, following Prop 3.2, we use feature importances computed using large value of N (N 10, 000), and treat the resulting estimates ground truth.
Results for BayesLIME Table indicate that the true feature importances are close to ideal and indicate the estimates are well calibrated. While the estimates by BayesSHAP are somewhat less calibrated (true feature importances fall within our estimated 95% credible intervals about 89.2 to 98.4% of the time), they still are quite close to ideal. All in all, these results confirm that the credible intervals learned by our methods are well calibrated and therefore highly reliable in capturing the uncertainty of the feature importances. Lastly, though set priors be uninformative in general, we also investigate how sensitive our uncertainty estimates are to hyperparameter choices in Figure in the Appendix. We find that the explanation uncertainty becomes uncalibrated with strong priors However, our explanations seem to be robust to hyperparameter choices in general.
Correctness of Estimated Number of Perturbations We assess whether our estimate of perturbations-to to--o (G; Section 3.2) is an accurate estimate of the additional number of pertur- bations needed reach a desired level of feature importance certainty. We carry out this experiment on MNIST data for the digit "4" (additional datasets explored in Appendix C) and use S = 200 as the initial number perturbations to obtain a preliminary explanation and its associated uncertainty estimates. We then leverage these estimates to compute G for 6 different certainty levels. First, we observe significant differences in G estimates across instances (details appendix C) i.e. number of perturbations needed to obtain particular level of certainty varied significantly across instances-
7

---

BayesLIME, 200 Initial Perturbations
BayesSHAP, 200 Initial Perturbations
1.3e-2
1.1e-2
Observed W
1.1e-2
Observed W
9e-3
9e-3
7e-3
7e-3
5e-3
5e-3
5e-3
6e-3
7e-3 8e-3 9e-3 1e-2 Desired W
5e-3
6e-3
7e-3
8e-3 Desired W
9e-3
1e-2
Figure 2: Perturbations-to-go (G). We generate explanation with G perturbations, where G is computed using the desired credible interval width (x-axis), and compare desired levels to the observed credible interval width (y-axis) (blue line indicates ideal calibration). Results are averaged over 100 MNIST images of the digit "4" We that G provides good approximation of the additional perturbations needed.
ranging from 200-5, 000 for the lowest level of certainty to 200-20, 000 for higher levels of certainty. Next, for each image and certainty level, we method for the estimated number of perturbations (G) to determine the observed estimates of uncertainty (observed credible interval width W) match the desired levels of uncertainty (desired credible interval width W). Results in Figure 2 show that the observed and desired levels of certainty are well calibrated, demonstrating that G estimates are reliable approximations of the additional number of perturbations needed.
Efficiency of Focused Sampling Focused sampling uses the predictive variance to strategically choose perturbations that will reduce uncertainty in order to be labeled by the black box (section 3.3). Here, we will evaluate the efficiency of the focused sampling procedure. First, we assess whether focused sampling converges
measured by eтror uncertainty (P(c = 0))) more efficiently than random sampling. To this end, we experiment with BayesLIME on Imagenet data for the "French bulldog" class to carry out this analysis. This setting replicates scenarios where LIME is applied to computationally expensive black box model, making it highly desirable to limit the number of perturbations to reduce total running time. We run each sampling strategy for 2,000 perturbations and plot the number of model queries versus error uncertainty. During focused sampling, batch size to 50. The results in Figure 3 show that focused sampling results faster convergence to reliable and high quality explanations; focused sampling stabilizes within couple hundred model queries while random sampling takes over 1,000. Note, as the inefficiency of querying the black box model increases, the advantages of focused sampling decreasing total rumning time of the explanations will only become more pronounced. These results clearly demonstrate that focused sampling can significantly speed up the process of generating high quality local explanations. Additionally, in Appendix C, we also check if focused sampling causes any bias (due to sampling based on uncertainty estimates) that results in convergence different/wrong explanation, however results clearly indicate that this not the case.
set the
Stability of BayesLIME. & BayesSHAP Recall that LIME & SHAP are not stable: small changes to instances can produce substantially different explanations. We consider whether BayesLIME, & BayesSHAP produce more stable explanations than their LIME & SHAP counterparts. To perform this analysis, we use the local Lipschitz metric for explanation stability [18]:
1
i(x:)) = argmax
(12)
||:; (x.))
22l12
where refers to an instance, Nz;x;) is the c-ball centered at I;, and 6; and Φ; are the explanation parameters for x; and x.y. Lower values indicate more stable explanations. We follow the setup outline by Alvarez-Melis and Jaakkola [18] and compute the local Lipschitz values, comparing both LIME Iaye and SHAP & BayesSHAP across Compas, German Credit, MNIST digit "4", and Imagenet "French Bulldog." We perform the comparison using the default number of perturbations in

---

MNIST
Imagenat German
Compas
4.25
100
4.00
BayesLIME % Increase Stability
3.75
MNIST
Imagenet Gemann Compas
3.50
Focused Sampling
Random Sampling
3,25
10a
10a
-100
-50
50
100
Number of Model Queries
BayesSHAP % Increase in Stabillly
Figure 3: Efficiency of focused sampling for 100 Imagenet "French bulldog" images, with random sampling as a baseline. We provide mean and standard error. We assess the effi- ciency of focused sampling by comparing er- ror uncertainty model queries and show quicker convergence than random sampling.
Figure Assessing the % increase in stability of BayesLIME and BayesSHAP over LIME and SHAP respectively. Our Bayesian methods are significant more stable (p < 1c-2 according Wilcoxon signed-rank test) except for BayesSHAP German Credit, where there is not significant
difference hetween the methods (p > 0.05).
both LIME & SHAP, and use this same number in the respective Bayesian variants and set the batch size B to half this value. We use focused sampling for BayesLIME and BayesSHAP, and report the % increase in stability of these approaches LIME and SHAP for 40 test points. The results given in Figure show a clear improvement (on average 53%) in stability in all cases except German Credit for BayesSHAP. Further,
a Wilcoxon signed-rank test and find our results statistically significant in all cases (p < 1e-2) except for BayesSHAP for German Credit, where there is not significant difference between the methods (p 0.05). These results demonstrate BayesLIME and BayesSHAP are more stable than previous methods.
User Study We perform a user study with 31 subjects to compare BayesLIME and LIME explanations on MNIST. We evaluate the following: are explanations with low levels of uncertainty (i.e., most confident explanations) more meaningful to humans? To answer this question, we follow prior work and mask the most important features selected by BayesLIMMB and LIME [32, 4J. We ask users to guess the digit of the masked images. The better the explanation, the more difficult should be for the users to get it right. Further, the choice to mask the important features is motivated by its success in prior work. We randomly select 15 correctly predicted test images, generate explanations by sweeping over range of perturbation amounts [10-5 .... 10 incremented by 0.5. We choose the top explanation for each image based on either fidelity (for LIME) or P(c = 0) (for BayesLIME). We sent the user study screen shot of the task shown in Figure in the Appendix. We find that the explanations output by methods focus more informative parts of the image, since hiding them makes it difficult for humans to guess the digit. Users had an error rate of 25.7% for LIME, while it was 30.7% for IMY, both with standard error 0.003 (p 0.028 through one-tailed result indicates that our method BayesI. and the associated measure of explanation uncertainty result in more high quality and reliable explanations compared LIME and associated fidelity metric.
to students and researchers with background in computer science. A
sample t-test). This
5 Related Work
Interpretability Methods A variety of interpretability methods have been proposed. Some methods that are inherently interpretable include additive models [33, 34], decision lists and sets [35, 36], and instance- based explanations [37]. However, black-box models are often more flexible, accurate, and easier to use; thus, there has been a lot of interest in constructing post hoc explanations [38]. These include LIME [2] and SHAP [4, 39], which are among the most popular due to their broad applicability and code availability, but saliency maps [5-8), permutation feature importance [40], and partial dependency plots [41] also follow this paradigm. Other approaches to post hoc explanations focus rule-based models [1, 3]. counterfactuals [42, 43], and influence functions [9].

---

Vulnerabilities of Post hoc Explanations Recent work has shed light on the downsides of post hoc explanation techniques. These methods are often highly sensitive small changes in inputs [14], are susceptible to manipulation [15, 16, 44, 45], and are not faithful to the underlying black boxes [46]. Perturbation- explanation methods such as LIME and SHAP are subject to additional criticisms: results vary between runs of the algorithms [18-20, 47, 21], and hyperparameters used to select the perturbations can greatly influence the resulting explanation [20]. Prior work has attempted to tackle the problem of instability in perturbation-basee explanations by averaging over several explanations [48, 19], however, this is computationally expensive. Other works related to creating more trustworthy explanations include development of sanity checks for explainers [49, 17, 50]. These techniques represent an important step towards improved usability, given experimental evidence that humans are often too eager to accept inaccurate machine explanations [51-54], Recent works theoretically analyze the sources of non-robustness in black box explanations [55-57].
Logical and Formal Reasoning Additional related works have considered explaining classifiers through identifying a subset of features that are "sufficient" to explain a prediction [58-62]. Though these methods offer strong guarantees surrounding which features ensure a prediction achieved, they are not model agnostic. Further, they do not define feature importances associated with the local explanations nor consider ways to improve locally weighted explanations, such as LIME and SHAP.
Bayesian Methods in Explainable ML Few recent works have adopted Bayesian formulations to explain black box models [63-65]. Guo et al. [63] introduce a Bayesian non man--aametrric approach to fit global surrogate model. Their formulation seeks to fit mixture of generalizable explanations across instances. Zhao et al. [64] study whether incorporating informative priors improves the stability of the resulting explanations. However, neither of these works focus modeling the uncertainty of local explanations. Further, these approaches also do not tackle the critical problems of estimating key hyperparameters improving efficiency of computing explanations.
6 Conclusion
We developed a Bayesian framework for generating local explanations along with their associated uncertainty. We instantiated this framework to obtain Bayesian versions of LIME and SHAP that output pointwise estimates of feature importances as well as their associated credible intervals. These intervals enabled us infer the quality of the explanations and output explanations that satisfied user specified levels of uncertainty. We carried out theoretical analysis that leverages these uncertainty measures (credible intervals) to estimate the values of critical hyperparrmeeeess (e.g., the number of perturbations). We also proposed novel sampling technique called focused sampling that leverages uncertainty estimates to determine how to sample perturbations for faster convergence.
While the Bayesian framework addresses several critical challenges (i.e., consistency, stability, modeling uncertainty) associated with LIME and SHAP, there are still certain aspects where would exhibit the same shortcomings as LIME and SHAP [4, 66). For instance, if the local decision surface of given black box classifier is highly non-linear, our framework, which relies on local linear approximations, may not be able to capture this non-linear decision surface accurately. In addition, if the perturbation sampling procedures used LIME and SHAP are used in BayesLIME and BayesSHAP, they will likely be vulnerable to the attacks proposed by Slack et al. [15]. In the future, it would be interesting to extend our framework to produce global explanations with uncertainty guarantees and explore how uncertainty quantification can help calibrate user trust in model explanations.
7 Acknowledgments
We would like thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #004-208461, 2008-200,956 and #1IS-2040989, and research awards from the Harvard Data Science Institute, Amazon, Bayer, Google, and the HPI Research Center in Machine Learning and Data Science at UC Irvine. The views expressed are those of the authors and do not reflect the official policy or position of the funding agencies.
10

---

References
[1] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: figh-precision model- agnostic explanations. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
[2] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why Should I Trust You? explaining the predictions of any classifier. In Knowledge Discovery and Data mining (KDD), 2016.
[3] Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec. Faithful and customizable explanations of black box models. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 131-138. ACM, 2019.
[4] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765 (764,,474, 2017.
[5] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Workshop International Conference on Learning Representations, 2014.
[6] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of the 34th International Conference on Machine Learning-Volune 70, pages 3319-3328. JMLR. org, 2017.
[7] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In ICCV, 2017.
[8] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. Workshop on Visualization for Deep Learning, ICML, 2017.
[9] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learming- Volume 70, pages 1885-1894. JMLR. org, 2017.
[10] Osbert Bastani, Carolyn Kim, and Hamsa Bastani. Interpretability via model extraction. FAT/ML Workshop 2017, 2017.
[11] Gregory Plumb, Denali Molitor, and Ameet S Talwalkar, Model agnostic supervised local explanations. In Neural Information Processing Systems, 2018.
[12] Radwa Elshawi, Mouaz H Al-Mallah, and Sherif Sakr. On the interpretability of machine learning- model for predicting hypertension. BMC medical informatics and decision making, 19(1):146, 2019.
[13] Leanne Whitmore, Anthe George, and Corey M Hudson. Mapping chemical performance molecular structures using locally interpretable explanations. arXiv preprint 1XXv:16611.07433 2016.
[14] Amirata Ghorbani, Abubakar Abid, and James Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3681-3688, 2019.
[15] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks post hoc explanation methods. Conference Artificial Intelligence, Ethics, and Society (AIES), 2020.
[16] Ann-Kathrin Dombrowski, Maximilian Alber, Christopher Anders, Marcel Ackermann, Klaus- Robert Müller, and Pan Kessel. Explanations can be manipulated and geometry to blame. arXiv preprint arXiv: 1906. 1906.0793, 2019.
[17] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. In Advances Neural Information Processing Systems, pages 9505-9515, 2018

---

[18] David Alvarez-Mehle Meris and Tommi S. Jaakkola. On the robustness of interpretability methods. ICML Workshop on Human Interpretability in Machine Learning. 2018.
[19] Eunjin Lee, David Braines, Mitchell Stiffler, Adam Hudler, and Daniel Harborne. Developing the sensitivity of lime for better machine learning explanation. In Artificial Intelligence and Machine Learning for Momlii-Domain Operations Applications, volume 1 11006, page 1100610. International Society for Optics and Photonics, 2019.
[20] Hui Fen Tan, Kuangyan Song, Madeilene Udell, Yiming Sun, and Yujia Zhang. "why should you trust my explanation?" understanding uncertainty in lime explanations. In ICML Workshop on Al for Social Good, 2019.
[21] Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. In International Conference on Learning Representations, 2019.
[22] Andrew Moore. Locally weighted bayesian regression, January 1995.
[23] Kacper Sokol, Alexander Hepburn, Raúl Santos-Rodrigue and Peter A. Flach. blimey: Surrogate prediction explanations beyond lime. NeurIPS HCML Workshop, 2019.
[24] Emily L. Denton, Wojeiech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In NIPS, 2014.
[25] Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. BMVC 2014 Proceedings of the British Machine Vision Conference 2014, 05 2014.
[26] Burr Settles. Active learning literature survey. 2010.
[27] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In ProPublica, 2016.
[28] Dheeru Dua and Casey Graff. Uci machine learning repository, 2017. URL http:///rcch... ics. uci. adu/ml.
[29] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecme www..lccm..o//exx/niiissss 2, 2010.
[30] Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
[31] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
[32] Patrick Schwab and Walter Karlen. Cxplain: Causal explanations for model interpretation under uncertainty. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bun Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 10220-10230. Curran Associates, Inc., 2019. URI. http: //paper/ .npppprrr.iissss....se..ep.pepss nips cc/paper/ 9211-cxplair wawaaainnncuusaaaaa pdf.
causal explaalaalpaaaaaannnatooooo ford-moeel- inteellinnterrtttiionn wwwpeeetttioonnee---eeeeee -nder-uncertaing
[33] Yin Lou, Rich Caruana, Johannes Gehrke, and Giles Hooker. Accurate intelligible models with pairwise interactions. KDD, 2013.
[34] Berk Ustun, Stefano Traca, and Cynthia Rudin. Supersparse linear integer models for inter- pretable classification. arXiv preprint arXiv:1306.6677 2013.
[35] Himabindu Lakkaraju, Stephen H Bach, and Jure Leskovec. Interpretable decision sets: A joint framework for description and prediction. Knowledge Discovery and Data mining (KDD),
2016.
[36] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data, arXiv preprint arXiv: 170.001701, 2017.
12

---

[37] Been Kim, Cynthia Rudin, and Julie Shah. The bayesian case model: A generative approach for case-based reasoning and prototype classification. arXiv preprint arXiv:1503.0116,, 2015.
[38] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Model-Agnostic Interpretability of Machine Learning. In ICML Workshop on Human Interpretability Machine Learning (WfII), June 2016.
[39] Ian Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation using linear regression. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3457-3465. PMLR, 13-15 Apr 2021. URL https: // pppoceedinggs... mlr. press/ wttess/v30//ooe c130/covert21a. html.
[40] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[41] Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189-1232, 2001.
[42] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference Fairness, Accountability, and Transparency, FAT* '19, pages 10-19, 2019, ISBN 978-1-4503-6125-5.
[43] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JL & Tech., 31:841, 2017.
[44] Juyeon Heo, Sunghwan Joo, and Taesup Moon. Fooling neural network interpretations via adversarial model manipulation. In Advances in Neural Information Processing Systems 32, pages 2921-2932. 2019.
[45] Junlin Wang, Jens Tuyls, Eric Wallace, and Sameer Singh. Gradient-based Analysis of NLP Models is Manipulable. In Findings of the Association for Computational Linguistics: EMNLP (EMNLP Findings), page 247-258, 2020.
[46] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206, 2019.
[47] Muhammad Rehman Zafar and Naimul Mefraz Khan. Dlime: deterministic local interpretable model-agnostic explanations approach for computer-aided diagnosis systems. arXiv preprint wrXiv:1906.1026. 2019.
[48] Chih- Yeh, Cheng- Yu Hsich, Arun Suggala, David Inouye. and Pradeep K Ravikumar. On the (in) fidelity and sensitivity of explanations. In Advances in Neural Information Processing Systems, pages 10976, 2019.
[49] Oana-Maria Camburu, Fleonora Giunchiglia, Jakob Foerster, Thomas Lukasiewicz, and Phil Blunsom. Can i trust the explainer? verifying post-hoc explanatory methods. arXiv preprint arXiv:1910.000055, 2019.
[50] Mengjiao Yang and Been Kim. Bim: Towards quantitative evaluation of interpretability methods with ground truth. arXiv:1907.0970) 2019.
[51] Harmanpreet Kaur, Harsha Nori, Samuel Jenkins, Rich Caruana, Hanna Wallach, and Jen- nifer Wortman Vaughan. Interpreting interpretability: Understanding data scientists' use of interpretability tools for machine learning. In CHI, April 2020.
[52] Fred Hohman, Andrew Head, Rich Caruana, Robert DeLine, and Steven M Drucker. Gamut: design probe to understand how data scientists understand machine learning models. In Proceedings of the 2019 CHI Conference Human Factors in Computing Systems, pages 1-13, 2019.
[53] Forough Poursabzi-Sangdeh, Daniel G Goldstein, Jake M Hofman, Jennifer Wortman Vaughan, and Hanna Wallach. Manipulating and measuring model interpretability. arXiv preprint 1rXiv:1802.07810, 2018.
13

---

[54] Himabindu Lakkaraju and Osbert Bastani. how do fool you?" manipulating user trust via misleading black box explanations. Proceedings of the AAAI/ACM Conference on Al, Ethics, and Society, pages 79-85, 2020.
[55] Damien Garreau and Ulrike von Luxburg. Looking deeper into lime. arXiv preprint arXiv:2008.11092 2020.
[56] Prasad Chalasani, Jiefeng Chen, Amrita Roy Chowdhury, Xi Wu, and Somesh Jha. Concise explanations of neural networks using adversarial training. In International Conference Machine Learning, pages 1383-1391. PMLR, 2020.
[57] Alexander Levine, Sahil Singla, and Soheil Feizi. Certifiably robust interpretation in deep learning, arXiv preprint arXiv:1905. 12105, 2019.
[58] Eric Wang, Pasha Khosravi, and Guy Van den Broeck. Probabilistic sufficient explanations. In IJCAI, 2021.
[59] Andy Shih, Arthur Choi, and Adnan Darwiche. A symbolic approach explaining bayesian network classifiers. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, UCAI 18, page 5103-5111. AAAI Press, 2018. ISBN 9780999241127.
[60] Weijia Shi, Andy Shih, Adnan Darwiche, and Arthur Choi. On tractable representations of binary neural networks. In Diego Calvanese, Esra Erdem, and Michael Thielscher, editors, Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, KR 2020, Rhodes, Greece, September 12-18, 2020, pages 882-892, 2020. doi: 10.24963/k: URL https: //tp:://oiiio ott.diiio///oooooooeoeeooooeoee.
org/10 10. 24963/ kr 2020/91.
[61] Yacine Izza, Alexey Ignatiev, and Joao Marques-Silyye 2020.
[62] Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Abduction- explanations for machine learning models. Proceedings of the AAAI Conference on Artificial Intelligence, 33 URL https: /ttp///ssaaaaaaa.
(01):1511-1519, Jul. 2019, doi: 10. http9//aaiiv3301..3333 org/index. http:/indx.pppp/////
[63] Wenbo Guo, Sui Huang, Yunzhe Tao, Xinyu Xing, and Lin Lin. Explaining deep learning models- bayesian non-parametric approach. In Neural Information Processing Systems (NeurIPS). 2018.
[64] Xingyu Zhao, Xiaowei Huang, Valentin Robu, and David Flynn. Baylime: Bayesian local interpretable model-agnostic explanations. arXiv preprint arXiv:2012.03058, 2020.
[65] Kirill Bykov, Marina Höhne, Klaus-Robert Müller, Shinichi Nakajima, and Marius Kloft. How much can trust you? quantifying uncertainties in explaining neural networks. arXiv, 2020.
[66] Sushant Agarwal, Shahin Jabbari, Chirag Agarwal, Sohini Upadhyay, Steven Wu, and Himabindu Lakkaraju. Towards the unification and robustness of perturbation and gradi- ent based explanations. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning. volume 139 of Proceedings Machine Learn- ing Research, pages 110-119, 19. PMLR, 18-24 Jul 2021. URL https: http::///oooeeieeeeeee mlr. press/v139 www.walllc.chiii.a..aaaaaaa.ee.e html.
[67] Ludwig Fahrmeir, Thomas Kneib, and Stefan Lang. Regression. Statistik und ihre Anwendungen. Springer, 2007. ISBN 978-3-540-33932--
[68] Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
14


Reviews:
[{"review_id": "XCC5CcIwUgg", "reviewer": "Reviewer_TaGg", "summary": "This paper proposes an approach to computing local explanations for machine learning (ML) predictions that are argued to be more reliable and accurate than the explanations provided by the prior approaches of LIME, Anchors, MAPLE, and SHAP. The developed solution attributes responsibility for the prediction by estimating feature importance as well as studying the credible intervals. The approach is based on a \"Bayesian framework\" and is instantiated to devise improved versions of LIME and KernelSHAP referred to in the paper as BayesLIME and BayesSHAP, respectively. Similarly to the other explainers, the approach is based on extensive sampling in the vicinity of the instance being explained but, in contrast, it can estimate the remaining amount of sampling needed to fulfil a specific level of certainty. The reported experimental results demonstrate that the explanations returned by the new approach are more accurate and more stable than those of LIME and SHAP. Additionally, a user study is performed indicating that the approach is superior to the competition in this regard.", "questions": "", "limitations": "", "rating": 3, "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": "This is yet another line of work to propose doing extensive sampling in a neighbourhood of a given instance to compute local explanations of the prediction made for that instance. The approach aims at addressing the known issues of the existing explainers of the same nature, namely the explanations being inaccurate and/or imprecise and/or unstable. Here, I should say the paper is somewhat hard to follow and it does not make a convincing case, at least to me. I believe the approach is not clearly explained and the rationale used is not detailed either - instead, the authors throw a large number of statistical formulas and variable/constant symbols one after another with the gaps filled by some short connecting phrases. (The appendix looks similar.) I am not sure to what extent such a description can be deemed sufficient for a top conference in AI/ML like NeurIPS.\n\nThe major problem I have with this paper is that it ignores a vast range of work in the area of logic and formal reasoning applied to computing provably correct (that is *truly reliable*) explanations, including \"sufficient reasons\" and \"probabilistic sufficient reasons\", and also assessing the correctness of explanation using formal reasoning. (I believe these must be hard to ignore and they include works published at flagship AI conferences, e.g. IJCAI/AAAI/ICML/NeurIPS.) This problem is especially troublesome in light of the reliability claims made here. For instance, it is known that in many cases, explanations computed by LIME/Anchors/SHAP are plain wrong, which can be easily established by applying formal reasoning to the explanations. (Precision of Anchors has been also assessed in prior works and it turned out to be unsatisfactory in a number of cases.) I fail to see any discussion on whether the proposed approach is free of this issue. And I believe such a discussion is necessary due to the claims made.\n\nExperimental results on the accuracy of explanations rely on using 10000 samples - I am not sure why it can be deemed sufficient to be taken as \"ground truth\". Once again, unless I am missing something, one can apply probabilistic sufficient reasons (or exact/approximate model counting for formal representations of the decision function) to devise the guarantees provided by their explanations.\n\nAlso, I fail to see a discussion on whether or not the proposed approach is susceptible to out-of-distribution attacks. The idea was proposed by the same authors, and so I would expect they have thought about it.\n\nThe related work section ignores a huge body of SOTA work on learning interpretable models (but also initial works in the area defining those models).\n\nI like the idea of estimating the amount of sampling, which is yet to be done to achieve some reasonable estimates, and it is good to see that it works somewhat well in practice.\n\nIt is unclear to me if there are any accuracy guarantees with respect to the focused sampling if done instead of random sampling.\n\nI do not agree with the way the user study is set up. You do not hide the explanations - instead, you make the pixels black. In a similar way, you could have made them white. But I believe the proper way would be to highlight them with a third colour and make a user decide what parts of the region correspond to black or white.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the main discussion above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "8mAwN3XssMb", "reviewer": "Reviewer_VUsD", "summary": "The authors  set to address the current  challenges of many black box DL models by developing a novel Bayesian framework for generating local explanations along with their associated uncertainty. \n\nThe make use of a novel framework to obtain Bayesian versions of LIME and KernelSHAP which output credible intervals for the feature importances, capturing the associated uncertainty. The resulting explanations are also highly consistent and stable.\nFurthermre, the authors carry out a detailed theoretical analysis that leverages the aforementioned uncertainty to estimate how many perturbations to sample, and how to sample for faster convergence. \n\nThis work makes the first attempt at addressing several critical issues with popular explanation methods in one shot, thereby generating consistent, stable, and reliable explanations with guarantees in a computationally efficient manner. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "I think this a very good contribution to ICLR given the topic and the quality of the submission (originality, contribution to the stare of the art, experimental evidence, etc) although the study might need to be supported in a more theoretical framework to make it worth of an oral presentation (I would recommend a poster or short presentation)\n\n Some of the strong points of the submission are summarized as follows:\n\n1.\tStudies in the interpretability of the results of deep learning models is a very important aspect, as well as the robustness of the obtained models in a variety of circumstances and under adversarial attacks. \n2.\tA sufficient introduction and motivations sections, but I would suggest introducing the state of the art at the beginning of the paper as it would help to get a better grasp of how the works builds upon previous work.\n3.\tThe state of the art (despite the previous comment) contextualizes the subject matter in a succinct but comprehensive manner. Although there are certain aspects that could be improved, such as including a table outlining in a clearer manner the contributions of the authors in this context.\n4.\tThe experimental design is good, showing a careful analysis to validate the proposal and several ablation studies to \n5.\tThe foundations for the method are presented in great detail in a formalized manner and provides sufficient elements (i.e. examples) to assess the validity of the proposed approach.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "14reoGO66h", "reviewer": "Reviewer_w3MC", "summary": "This paper addresses uncertainty in local explanation methods, i.e., methods that use a local surrogate model which is used to generate explanations of black-box models. Methods such as LIME and KernelSHAP are well-known examples. The main idea is to a Bayesian framework for constructing local explanations and capturing its uncertainty. Key is a distribution over an error which arises due to the mismatch between the explanation and the local decision surface of the black box model. The resulting method allow for computing uncertainty intervals for features, but also allows for estimating the number of perturbations needed to generate better explanations, and more focused sampling of additional samples around the local decision area.\n", "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": "In my opinion, this paper contains a significant contributions: despite their obvious advantages, methods such as LIME suffer \nfrom a number of downsides which are mostly related to instability and non-robustness of the explanations. The experiments in this\npaper show that this criticism can mostly be overcome using a Bayesian approach to these ideas. \n\nThe novelty of the paper is reasonable: while it builds upon ideas of LIME and KernelSHAP, the development and derivation of\nthe whole framework is novel as far as I can see. \n\nThe evaluation is convincing. I appreciated the evaluation of the credible intervals, showing that for BayesSHAP and certainly for BayesLIME the 95% credible interval is close to the true value. The results show that it is a significant improvement over the baseline local explanation methods, both in more theoretical terms and in a small-scale test with humans. \n\nThe paper is quite easy to read. It contains some technical details, but even if one were to skip those, it is not hard to get the main ideas of the approach.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the conclusions hint at the possibility that the credible intervals are incorrect, which may lead to overreliance of faulty explanations. It would not be hard to see that this could be damaging in some domains. Nonetheless, the work is fairly theoretical, so a further consideration is not necessary.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0kBJgCiM_lV", "reviewer": "Reviewer_q9ZD", "summary": "The paper proposes a bayesian framework that\n1) generates local explanations whose uncertainty can be quantified. \n2)  estimates how many perturbations are required to obtain an explanation (G) corresponding to a specified confidence level (W). \n3) developed a new sample efficient sampling algorithm by taking advantage of the uncertainty estimates.\n\nGiven that LIME and SHAP both learn a linear surrogate model to approximate the predictions of the black-box around the neighborhood of a point, this could be formulated as bayesian regression problem.  The error is defined as a normal distribution whose mean is 0 and whose variance is a function of the inverse of proximity function $\\pi_{x}(z)$. The variance is an inverse $\\chi^{2}$ distribution and the feature importance given the variance is a normal distribution.  Following [1], they derive the posterior of the feature importance and the variance. Based on these posteriors, they are able to estimate the uncertainty of the feature importance and the uncertainty in estimating the error term. \nRather than perturbing at random, the points are sampled in the region where the surrogate model is the most uncertain. Thus, this reduces the number of perturbations required to generate an explanation at a specified certainty threshold.\n\nThis framework can be used to get Bayesian versions of LIME and SHAP by using proximity function $\\pi_{x}(z)$ and the priors corresponding to each algorithm. \n\nTheir experiments are able to empirically reinforce their claims.\n\n[1] Locally weighted bayesian regression, Andrew Moore\n", "questions": "", "limitations": "", "rating": 8, "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": "This is a very strong paper and is well written. Determining the number of perturbations for an explainability algorithm is always tricky, yet the quality of explanations depend on it . Being able to estimate G given W is  very useful.\n\nThe experiments section of the paper is very compelling. They have empirically proven the efficacy of their uncertainty estimates, G given W and sample efficient method. They further demonstrated that the sample efficient method is not biased. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1) Using only images from 1 class for MNIST and ImageNet is not sufficient to determine the effectiveness of the proposed Framework. Please use images from more classes. Similarly, using 40 data points for the stability experiment might not be significant enough for MNIST and ImageNet.\n\n2) How effective is the uncertainty estimate of points that lie close to the boundary of the black-box classifier?\n\n3) In table 1, could you provide some intuition as to why is the feature importance estimate of SHAP lower than LIME? Is it because of the nature of its perturbation function? ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are three extremely favorable reviews and one very strong dissenting review. 

The dissenting opinion (after good discussion) is: LIME, SHAP , Anchors etc..  - why are these appropriate notions of post hoc explanations. Something that is akin to probability of sufficiency/ necessity etc (causal notions) are truly reliable explanations. Authors claim reliability but solve stability problems in prior post-hoc procedures.

Authors' contention: This dissenting opinion dismisses a whole  line of prior work on (popular) post-hoc explanations and we have sought to solve issue of these prior explanation methods.

The conflict at the heart seems to be : Are explanations provided by LIME, SHAP etc.. valid/reliable explanations in the first place. Solving stability issues of these seem to not address the core problem.

 My position is this: Probability of sufficiency/necessity are counterfactual notions that in general require knowledge about causal generative models behind the data. Sometimes, stronger assumptions like monotonicty etc.. (pls see - https://ftp.cs.ucla.edu/pub/stat_ser/r271-A.pdf) are required if we are to make conclusions from data alone. Several recent works are exploring, generalizing  and finding novel sufficient conditions for estimating these. But still they require some side information. 

LIME, SHAP are perturbation based techniques based on the data manifold. While I agree with the dissenting opinion that they are not causally grounded (and hence not reliable in some absolute sense), in practice sometimes exploring the data manifold (in the factual sense) can provide explanations that are useful in practice. This is attested by the popularity of these methods and them being used in many places at this point. Another way to look at this is - given the popularity of these perturbation based notions on the data manifold, one would also want to see this line of enquiry mature given their easy to use data driven nature. I would not dismiss this line of enquiry completely.

Given the very favorable reviews from others, I am inclined to accept this paper. Authors may want to explicitly note that their method solves stability issues in a certain class of post hoc explanation methods and does not deal with explanation methods based on counterfactual notions.


Decision: Accept (Poster)