Constraint-Driven Explanations of Black-Box ML Models
Authors: Aditya Aniruddha Shrotri
Nina Narodytska
Alexey Ignatiev
Joao Marques-Silva
Kuldeep S. Meel
Moshe Vardi
Venue:  (2021)
Keywords: Explainability
constraints
uniform sampling

Abstract: Modern machine learning techniques have enjoyed widespread success, but are plagued by lack of transparency in their decision making, which has led to the emergence of the field of explainable AI.  One popular approach called LIME, seeks to explain an opaque model's behavior, by training a surrogate interpretable model to be locally faithful on perturbed instances. 
Despite being model-agnostic and easy-to-use, it is known that LIME's explanations can be unstable and are susceptible to adversarial attacks as a result of Out-Of-Distribution (OOD) sampling. Quality of explanations is also calculated heuristically, and lacks a strong theoretical foundation. In spite of numerous attempts to remedy some of these issues, making the LIME framework more trustworthy and reliable remains an open problem.

In this work, we demonstrate that the OOD sampling problem stems  from rigidity of the perturbation procedure.  To resolve this issue, we propose a theoretically sound framework based on uniform sampling of user-defined subspaces. Through logical constraints, we afford the end-user the flexibility to delineate the precise subspace of the input domain to be explained. This not only helps mitigate the problem of OOD sampling, but also allow experts to drill down and uncover bugs deep inside the model. For testing the quality of generated explanations, we develop an efficient estimation algorithm that is able to certifiably measure the true value of metrics such as fidelity up to any desired degree of accuracy, which can help in building trust in the generated explanations. Our framework called CLIME can be applied to any ML model, and extensive experiments demonstrate its versatility on real-world problems.


Under review as a conference paper at ICLR 2021
CONSTRAINT-DRIVEN EXPLANATIONS OF BLACK- Box ML MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Modern machine learning techniques have enjoyed widespread success, but are plagued by lack of transparency in their decision making, which has led to the emergence of the field of explainable AL. One popular approach called LIME, seeks to explain an opaque model's behavior, by training a surrogate interpretable model be locally faithful on perturbed instances. Despite being model-agnostic and easy- to-use, it is known that LIME's ' explanations can be unstable and are susceptible result of Out-Or Out-Or-Distribution (OOD) sampling. The quality of explanations is also calculated heuristically, and lacks strong theoretical foundation. In spite of numerous attempts to remedy some of these issues, making the LIME framework more trustworthy and reliable remains an open problem.
adversarial attacks
In this work, we demonstrate that the OOD sampling problem stems from rigidity of the perturbation procedure. To resolve this issue, we propose a theoretically sound framework based uniform sampling of user-defined subspaces. Through logical constraints, we afford the end-user the flexibility to delineate the precise subspace of the input domain to be explained. This not only helps mitigate the problem of OOD sampling, but also allow experts to drill down and uncover bugs and biases hidden deep inside the model. For testing the quality of generated explanations, we develop an efficient estimation algorithm that is able to certifiably measure the true value of metrics such as fidelity up to any desired degree of accuracy, which can help in building trust in the generated explanations. Our framework called CLIME can be applied any MI. model, and extensive experiments demonstrate its versatility on real-world problems.
INTRODUCTION
Advances in Machine Learning (ML) in the last decade have resulted in new applications to safety- critical and human-sensitive domains such as driver-less cars, health, finance, education and the like (c.f. (Lipton 2018)). In order to build trust in automated ML decision processes, it not sufficient to only verify properties of the model; the concerned human authority also needs to understand the reasoning behind predictions (DARPA 2016 Goodman & Flaxman 2017 Lipton 2018). Highly successful models such as Neural Networks and ensembles, however, often complex, and even experts find it hard to decipher their inner workings. Such opaque decision processes are unacceptable for safety-critical domains where a wrong decision can have serious consequences. This has led to the emergence of the field of eXplainable AI (XAI), which targets development of both naturally interpretable models (e.g. decision trees, lists, or sets) (Hu et al. 2019 Angelino al. 2018 Rudin 2020) as well as post-hoc explanations for opaque models (Ribeiro et al., 2016 Lundberg & Lee| 2017). Although interpretable models have been gaining traction, state-of-the-ee
approaches in most domains are uninterpretable and therefore necessitate post-hoc explanations.
One popular post-hoc approach is the Locally Interpretable Model-agnostic Explanation (LIME) framework (Ribeiro et al.) (0116). which seeks to explain individual predictions by capturing the local behaviour of the opaque model an approximate but interpretable way. To do so, it trains a surrogate interpretable classifier to be faithful to the opaque model in a small neighborhood around usov-pdo data instance. Specifically, the given data instance is perturbed to generate a synthetic data set on which an interpretable classifier such linear model is trained with the objective of having high fidelity to the original model. The human decision-maker can inspect the coefficients of the linear model understand which features contributed positively negatively the prediction.

---

Under review as a conference paper at ICLR 2021
LIME is model-agnostic as it treats the opaque model as black-box. It applicable to wide variety of data such as text, tabular and image, and is easy to use. Nevertheless, it suffers from sensitivity to -ittt---iittiitti sampling, which undermines trust in the explanations and makes them susceptible to adversarial attacks (Slack et al., 2020). Post-hoc explanation techniques are increasingly being used by MI experts to debug their models. In this setting, LIME does not provide the user with the flexibility to refine explanations by drilling down to bug-prone corners of the input domain. Further, LIME has limited capabilities for measuring explanation quality accurately. For instance, checking whether the generated explanation is faithful to the original model can only be done on heuristically defined number of samples, which can be unreliable. While later works such as Anchor (Ribeiro) et al. 2018) and SHAP (Lundberg & Lee 2017) mitigate some of these issues, LIME remains popular framework and making it more robust and reliable remains an open problem.
Towards this goal, we first demonstrate that LIME's rigid perturbation procedure is at the root of many of these problems, due to its inability to capture the original data distribution. We craft concrete examples which clearly show LIME generating misleading explanations due to OOD sampling. Further, LIME affords the end-user limited control over the sub-space to be explained; since the notions of 'locality' and 'neighborhood" are defined implicitly by LIME's perturbation procedure. XAI, however, is inherently human-centric and one-size- handle all user-needs and application domains (Sokol et al. (019). Instead, we propose generalize the LIME framework by letting the user define the specific subspace of the input domain to be explained, through the use of logical constraints. Boolean constraints can capture wide variety of distributions and recent advances in SAT solving and hashing technology have enabled fast solution sampling from large complex formulas (Soos et al. 2020). Making LIME's neighborhood generation flexible in this way resolves both limitations of LIME. First, our approach helps in mitigating the problem of OOD sampling. Second, it allows the user to drill down and refine explanations. For instance, it might be not sufficient for doctors to simply know which test results contributed to a model's prediction of cancer;
siize-iitsalle fits-all approaches are not powerful enough to
also important to understand the prediction in the context of the patient's ss specific age group, ethnicity etc. Such requirements can be naturally represented as constraints. In the same vein, constraints can also be used to zoom in to bug-prone corners of the input space uncover potential problems in the model. This is especially useful for model debugging which is a recent direction for ML. research (Kang et al., 2020). Letting users define sub-spaces to be explained also necessitates theoretically grounded method of measuring explanation quality, as a poor quality score can indicate to the user, the need for refining constraints. Existing works compute these metrics heuristically without formal guarantees of accuracy. In this light, we propose a theoretical framework and an efficient estimation algorithm that enables measurement of the true value of metries like fidelity, up to any desired accuracy, model-agnostic way. Through extensive experiments, we demonstrate the scalability of our estimation framework, as well as applications of CLIME to real world problems such as uncovering model biases and detecting adversarial attacks.
In summary, our contributions are as follows:
1. Framework for precisely crafting explanations for specific subspaces of the input domain through logical constraints
2. A theoretical framework and efficient algorithm for estimating the "true" value of metrics like fidelity up to any desired accuracy
3. Empirical study which demonstrates the efficacy of constraints in
Mitigating problem of OOD sampling
Detecting adversarial attacks
Zooming in and refining explanations for uncovering hidden biases
2 PRELIMINARIES
Problem formulation. We follow notations from Ribeiro al. 2016). Let D = (X,y) {(x), ,c',,")) )))) (2².,²).... y?).....(( (x", nem,, y²) denote the input dataset from some distribution D where x'' E Rd is vector that captures the feature values of the ith sample, and y (Co, C is the corresponding class labe We use subscripts, i.e. Tj. to denote the 5ihh feature of the vector x.
We focus binary classification; extension multi-class classification follows by 1-vs-rest approach
2

---

Under review as a conference paper at ICLR 2021
Let f: Rd - [0, 1] denote the opaque classifier that takes data point x' as imput and returns the probability of x' belonging to C1. We assume that an instance x' is assigned label (z) = C1 if f(z) 2 0.5 and (xxx) Co otherwise. Given a classifier f. the task is to learn an explainer model such that g mimics the behavior of f in the neighborhood of some given point x. The type of classifier g is chosen be visually textually interpretable, so that it can serve an explanation for f's behavior in the neighborhood of x.
Overview of LIME. LIME builds the explainer function g on an 'interpretable domain' of inputs rather than the original domain. To do so, it maps original features (that can be continuous or categorical) to Boolean features. While z E R' represents an instance in the original domain, we use prime-notation, i.e. x' E {0, 1 to represent an instance in the interpretable domain. Using Boolean features is a natural choice for 'interpretable domain', as we can understand explanations in terms of presence/absence of a feature's 's value. Thus g operates in the interpretable domain {0. 13
LIME randomly perturbs the given instance æ to generate neighbors =1, :...... with corresponding interpretable versions 2²1 2 ..... The set of sampled neighbors i.c., the neighborhood of æ, is denoted by Z (Z' in the interpretable space) Additionally, we denote the universe of all possible neighbors of (not just the ones sampled) by 4 and u
Let the complexity of an explanation g be denoted as P(g) (complexity of a linear model can be the number of non-zero weights), and let (=) denote the proximity measure between inputs x and E 2 (Ta can be defined using cosine or L2 distance). The objective function for training is crafted to ensure that g: (I) approximates the behavior of f accurately in the vicinity of where the proximity measure is high, and (2) achieves low complexity and is thereby interpretable. The explanation is obtained as g" ar argmingec L(T 9. f) + (gg) where G is the set of all linear classifiers and the loss function I. is defined as: L(S, h, nx) Σ ZE (f(=) "(='))
These are heuristically defined functions. Intuitively, the loss function captures how unfaithful g is to f in the neighborhood of x.
Boolean (logical) constraints and uniform sampling. We use notation standard in the area of Boolean Satisfiability (SAT). A Boolean formula over n variables ø {0, 11"h - {0, 1} assigns a truth value 0/1 or false/true each of the 2n assignments to it's variables and is constructed using logical operators like AND (A), OR(V), NOT (-), XOR (+) etc. An assigmment of truth values to variables denoted s E {0, 13"h said to satisfy (denoted - Φ) iff Φ(s) = The total number of assignments that satisfy Φ is denoted as #Ø = E.e(o.1)" ((s). An algorithm is said to be a (perfectly) uniform sampler if it takes as input arbitrary formula ø and returns an assignment s* such that Vs == Φ), we have Pr(s" =
An almost-uniform sampler an algorithm
#6"
that takes, along with é, a parameter e > 0 as input and returns s* such that Vs |= Φ. we have The tools WAPS (Gupta et al. 2019)) and Unigen3 (Soos al. 2020 samplers respectively.
(1+))+ S Pr[s" s] S L+s. are state-of-the-ard perfectly uniform and almost-unifinn
#
Fidelity. The fidelity p of the explainer model g is a measure of how closely the predictions made by g match those of f in the neighborhood around the given point æ (Ribeiro et al. 2016).. It is calculated as the fraction of the sampled neighbors where the output class of I and g agree, i.e.
p= Eeez I1)s(z) = (x())
(1)
where I is the indicator function.
ANALYSIS OF LIME
LIME sampling procedure. LIME generates the neighborhood of the data point under explanation differently for text, image and tabular datasets. We consider tabular data here (see Appendix for omitted details, examples, etc.). For tabular data, LIME samples points 2 E 2 in the neighborhood of æ (continuous features are discretized) and then maps them to the interpretable (binary) domain as z" E Z', The distance function π is defined on the binarized space to measure distance between the original x' and sampled instances z'. Given 2 2,x) LIME builds linear regression model y to fit
3

---

Under review as a conference paper at ICLR 2021
these data, where the distance measure π defines weights of samples.
g
G2 + d.
Framework characteristics. The underlying assumption of LIME is that it is possible to approx- imate the behavior of the black box classifier accurately around x, so that g can faithfully mimic I in x's neighbourhood. To fulfill this assumption, LIME presumes that it is possible to produce a representation of the neighbourhood 2 of x that adheres to the true distribution of the data D (i.e. Z D). through its fixed sampling procedure. However, this assumption is quite strong. Even the classifier f behaves linearly in the neighbourhood of the correct distribution of instances can vary depending on the problem being solved, which may not be accounted for by a fixed sampling procedure. Therefore, the key question is does LIME's ss sampling procedure produce neighbour- hood 2 S.I. 2- ~ D?. Another more practical question is does OOD sampling lead to unreliable explanations? In fact, [Slack et al. (2020) already gamed LIME's -uttr--distribution (OOD) samples using an additional scaffolded classifier that behaves exactly like f on samples from the distribution and produces arbitrary decisions for other samples. We show that even without wrapping classifier, LIME's ss explanations suffer dramatically from OOD sampling.
To do so, we introduce simple metric that measures the severity of OOD sampling. The metric is based on the observation that if Z ~ 'D (i.e. no OOD sampling occurs). then the fraction of instances with 'true' label C1 should be roughly the same for both Z and D. Let Wq be the fraction of intances q E Q that have true label k(g) = C1, i.e. Wq Egeq I(((y) = C))/Q)-- Then if 2 ~ D, we should have Wz/ Wz/WD ~ 1. By construction of the binary space Z', we know that Wz Wz. Therefore, we should also get Wz /W> = 1. For an explainer E, we define
SQ(E) = /
(3)
If the value of SQ(E) is far from 1, it is indicative of OOD sampling. However, computing SQ(E) directly is infeasible in practice, as we generally do not have access to the true labels of instances generated through sampling. Therefore we craft a few classification tasks where a perfect classifier i can be trained such that fxx) 2 0.5 for Vz, x ~ 'D such that x belongs to C1. This allows us to obtain the true labels for computing Wz and WT. We show such an example in Fig [ called 'Hit or miss example'. In Fig [ the squares So and 81 represent the areas of the input space that are in-distribution, while points outside the squares (white regions) are OOD. Intuitively, when perturbing the point with coordinates (8, 8), for example, LIME's iistriibutionunnwwwr is likely to generate a lot of OOD samples, as the neighborhood of (8, 8) is largely OOD (white). In Example B. in Appendix B precisely define the classification task in this example. We found SQ( E) = 0.75 which is much less than 1, and clearly indicates that LIME's s sampling procedure does not satisfy the main underlying assumption Z ~ D.
sampling procedure
Framework capabilities. The other limitation of LIME is that the fixed perturbation procedure gives users very little flexibility in tailoring explanations to their needs. Users can only control the data point x to be explained, which can be insufficient for different use-cases. It is natural to ask: Can we generate explanations using a specific subspace of inputs? Namely, define Z instead of having LIME define it for us? The need for customizing Z arises naturally in the process of refining explanations, or when debugging models. For example, regulators may want to know how insurance applications are decided for people with specific preexisting conditions. Traders may need understand the reason behind decision to sell, in the context of the prevailing market conditions. Answering such queries is challenging in the existing LIME setting as it requires sampling capabilities from constrained subspace. In our proposed framework, the user can naturally enforce such requirements through constraints such as ordering relations, arithmetic expressions over bounded integers, Boolean expressions or any logical combinations of these.
formally
GENERATING AND CERTIFYING CONSTRAINT-DRIVER EXPLANATIONS
From the preceding discussion, it is clear that the limitations of the LIME framework that remain unaddressed are (a) OOD sampling, (b) ability to work in constrained spaces and (c) providing verifiable guarantees fidelity. Towards the goal of remedying this, we first present constraint- driven explanation generation framework called CLIME. Then, we show how we can obtain certifiably accurate measurements of an explanation's 's quality through novel estimation algorithm.
4

---

Under review as a conference paper at ICLR 2021
Aigorithms 2.3 Estimation Time (sec)
12
175
S
150
(8,8)
125
100
S 0
50
150
175
0
12
ApproxMC. Fstimation Time (sec)
Figure 1: Hit miss example
Figure 2: Scalability of Alg. 2,3 vs. ApproxMC
4.1 CLIME EXPLANATION FRAMEWORK
The CLIME framework generates explanations instances sampled (almost) uniformly from user- defined subspaces which are defined through constraints. Boolean constraints are powerful enough to represent log-linear family of distributions (Chavira Darwichel 2008), yet allow fast sampling of solutions either uniformly or with a user-provided bias (Gupta et al. 2019), thanks to advances in SAT technology. In this work, we focus on explanations based on (almost) uniformly sampling solutions of constraints, but we note that the extension to biased (weighted) sampling is straightforward.
The pseudo-code of the constrained explanation framework is presented in Alg. [T] The key difference with respect to LIME is that along with the input instance CLIME also takes input a Boolean formula Φ The variables of are exactly the Boolean features of the interpretable domain 2'. As an example, assume that é represents the constraint that at least "c' variables must be true for some user-defined 'c'. For image data this constraint enforces the requirement that at least 'c" superpixels must be 'on', while for text it forces at least "c' words from æ to be present in each This blocks out very sparse data ensuring that only informative instances are used for training the explainer model.
We assume access procedure getSSmples that returns N independent samples satisfying ø. The algorithm takes as input a parameter E, which represents the tolerance to deviation from perfectly- uniform sampling. If e 0, then the call to get.Samples in line must be to perfectly uniform sampler like WAPS (Gupta et al. 2019), otherwise an almost-uniform sampler like Unigen3 (Soos) et al. 2020) suffices. The rest of the algorithm is similar to LIME: samples z" are mapped back the original domain, and the output of f each z and the distance of each 2¹ x are used for training g in line 6, where at most K coefficients are allowed to be non-zero ensure interpretability.
In Appendix C we consider two classes of crafted examples to demonstrate (a) undesired conse- quences of OOD sampling for LIME which are resolved in CLIME (Example C.1 and C2 and (b)
CLIME's capabilities to incorporate user-defined constraints (Example
Our first set of examples highlight that LIME does suffer from OOD sampling, leading to poor quality of explanations. particular, SQ(TTMM can be very low and LIME's explanations significantly differ from the true explanations. In contrast, giving the user the ability to define Z, D using constraints as CLIME, mitigates OOD sampling; SQ(CLI E) almost and CLIME produces correct explanations (we recall that the ground truth is known in these examples).
Our second class of crafted examples illustrates the explanation debugging process, where we allow the user to specify the subspace Z₂ to obtain explanation from, e.g. to know how decisions made for specific classes of people such as those with alcohol dependency. We show that CLIME can naturally handle these constrained user-spaces, which may be challenging for LIME.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 explain CLIME
Algorithm 3 checkKThresshold(ee.b
Input: f: Opaque classifier
Input: Tolerance
6: Boolean constraints
8: Confidence
s: Tolerance N: Number of samples
7: Threshold
Nz Similarity kernel
Output: True whp p 5-7-5
K: Lenghh of explanation
1: t -minle+="/222000 (0-77/222
Output: g: Interpretable linear classifier
e/2))
1: Z' + get.Smmpless( N):
2: N + 2 1og(2))
2: Z +- 0
3: S + getSamples(d,
3: for z' E Z do
4: C-O0
4: 7 + U ((',((2), [z(2)}
5: for s E S do
5: end for
6:
Ct (+-chckProperrt()))
6: g g K-LAsso(Z, K)
7:
C+
8: end for
Algorithm 2 compute Estimatels,
9: if c then
Input: 5: Tolerance 8: Confidence
10: return True
7: Threshold
11: else
Output: 7:: Estimate of p (see Thm.
12: return False
1: if thechkhhresollde,, 5, 7) = True then
13: end if
2: return
3: end if
4: p AA'(0.A=..044=...)
5: return p
4.2 CERTIFYING EXPLANATION QUALITY
For increasing user trust, it is necessary to provide measure of the quality of explanations generated. This is especially important for explanations of user defined sub-spaces, as it may be possible that no simple explanation exists for a large subspace, and further refinements to the constraints may be required to get high quality explanation. The fidelity metric, as defined in Eqn. [ measures quality in terms of the fraction of samples on which the prediction made by the explainer model, matches the prediction of the opaque model. A high fidelity score indicates that the explainer model is faithful to the opaque model in Z. A low fidelity score can occur if, for instance, a linear classifier is used for explaining a highly non-linear decision boundary, making the explainer unreliable.
Two parameters influence the accuracy of the fidelity score: the number of samples in Zg and the quality of these samples, i.e. their uniformity in 212 Both of these parameters were chosen heuristically in prior works including LIME, which makes the explanations harder to trust. Intuitively, score measured on 10 samples will not be stable one measured on 10000 due to randomness inherent in any sampling procedure. Ideally one would want to compute the fidelity on all possible instances belonging to user-defined subspace of inputs.
Note that Eqn. I computes an estimate or sample mean of the 'true' population mean defined by
Exer= (z) = (z(x))
2
This observation allows us to compute the estimate p in theoretically grounded way, so as to statisti- cally guarantee its closeness to p. Such guarantees can be indispensable in safety-critical -rriticll areas such as healthcare, to show adherence to regulatory requirements for AI, for instance.
Computing P exactly is usually intractable, as the constraint ø is likely to have tens of hundreds of variables and exponentially many solutions. Approximating P can be faster, but requires formal guarantees to be meaningful. A good approximation of p is one that is within user-defined tolerance of the true value with high confidence. Specifically, e is a good approximation of if
Pr[(1 -)p < ক < (1 + +)) 2 (1 (1-00 6)
(5)
where 0, 8 > are user-defined tolerance and confidence.

---

Under review as a conference paper at ICLR 2021
To the best of our knowledge, no existing approach is directly applicable for finding good approxi- mation of p, in a moode-aggossic way. The technique presented by (Narodytska et al. 2019), requires the opaque model to be encoded as Boolean formula, severely limiting types of models that can be explained. On the other hand, algorithms based on Monte Carlo sampling such as the A algorithm by (Dagum al.] ) when p is low (Meel et al. 2019). They also require perfectly uniform samples, while it may only be feasible generate almost-unifone samples from the universe u=
known be fast when p is high, but require far too many samples
In this section, we describe an efficient estimation algorithm based on (Dagum el al. 2000), that is able to work with almost-uniform samples and also terminates quickly if the quantity being approximated is small. Two key insights inform the design of our approach: we first observe that g-almost uniform sampling can change the value of p at most by a factor of (1 + e). Secondly, in typical scenarios, users are interested in two-sided bounds on fidelity (as given by Eqn. (5) only if it is high enough. If the fidelity is lower than some threshold, say 0.1, then it doesn't 't matter it is 0.05 or 0,01, since the explanation will be unacceptable in either case. In other words, below a certain threshold, one-sided bounds suffice.
We present our estimation framework in Algs. 2 and Our technique is abstract in the sense that it can estimate the density of samples satisfying any property (not fidelity). in any given domain (not just Boolean), so long as it is possible to sample (almost) uniformly from the domain (encapsulated in the procedure get get.Sanlles) We assume access to a procedure 8, returns if the property of interest is satisfied by and 0 otherwise. In practice, for measuring fidelity of an explainer model on subspace defined by some é, getSamples can invoke WAPS or Unigen3 on Φ, while check Property is simply the indicator function Z[(r(z) == (=')).
srecktrroprty, that given a sample
Procedure compule Estimale first invokes ity (1- - 5) if the population mean is less than the prescribed threshold y with tolerance e. If the check fails, then compute E sttmmte makes a call to procedure AA' (line 4), which is an adaptation of the algorithm by (Dagum et al., 2000) that provides guarantees similar to Eqn. with iimost-uniform samples (see Appendix[D.I Theorem I captures the guarantees and the behavior of the framework.
which returns True with high probabil-
Theorem 1. If S 7 then compute Estimate returns 1 with high probability (Le. at least 1 8). p 2 + &, w.h.p. returns an estimate such that Pr[(1 (1((11))))) =)p S p s (1+ te)p 2 (1 8).
The benefit of leveraging the algorithm by (Dagum et al. 2000) is that it was proven to have close-to- optimal sample complexity. We demonstrate that this yields fast certification tool in practice. We implemented and ran Alg. 2 3 on 150 benchmarks used in Narodytska al. (2019). The benchmarks are CNF formulas that encode the Anchor (Ribeiro et al. 20188 8) explanations of Binarized Neural Networks trained on Adult, Recidivism and Lending datasets. The true fidelity of an explanation can be computed from the count of the number of solutions of the corresponding formula. We compared the running-timi timeeggtttmmmee of our tool to the time taken by the approach of (Narodytska et al.] (201)). which utilizes the state-of-the-are approximate model-counting tool called ApproxMC (Soos et al. 2020). Note that both ApproxMC and our tool provide the same probabilistic guarantees on the returned estimate. The results are shown a scatter-plot in Fig. 2 The x-coordinate of point in blue represents the time taken by ApproxMC on a benchmark, while the y-coordinate represents the time taken by our approach. As all the points are far below the diagonal dotted red line, we can infer that ApproxMC takes significantly longer than our tool to compute the same estimate. In fact, on average (geometric mean), our tool 7.5x faster than ApproxMC. It is clear from Fig. 2 that our algorithm scales far better than the alternative, despite being more general and madel-agnostic. We also experimentally compared the scalability of our tool to ApproxMC for different values of input tolerance e and confidence 8. We found that our tool scales significantly better than ApproxMC for tighter tolerance and confidence values. Thus, our experiments demonstrate that our tool is efficient in practice. We provide more details and results in Appendix D.4
EXPERIMENTS
We experimentally demonstrate how CLIME can be used for obtaining more meaningful explanations on synthetic and real-world datasets, i.c. adult (Kohavi 1996) and recidivism (Schmidt & Witte 1988) We also evaluate its ability to detect adversarial attacks. We focus on tabular data, but emphasize that CLIME is readily applicable to text and image data well. Here we present results for recidivism (see extended version of results in Appendix
7

---

Under review as a conference paper at ICLR 2021
LIME(female space)
CLIME(female space)
14
LIME(male space)
14
CLIME(male space)
Average feature ranking
Average feature ranking
12
12
10
10
6
4
2
Race
Alch
Jnky
SpRe
Mard
Fein
WrRc
Crpr
CrPe
Gndr
Prio
Yr5c
PrVs
Age
Minrr
Race
Alch
Jnky
SpRe
Mard
Feln
Write
CiPr
CrPe
Gndr
Prio
YrSc
PrVs
Age
MnSr
(a) LIME
(b) CLIME
Figure 3: Explanations for the recidivism dataset on female and male spaces.
Recidivism Dataset. The Recidivism dataset used to predict recidivism for individuals released from North Carolina prisons. We used the discretized version of dataset as in (Ribeiro et al. 2018). We trained small Multilayer Perceptron model that gives 69.1 % accuracy the test set. We consider two constrained spaces:
'female space": (JUNKY OR ALCOHOL) AND (CRIMEPROPERTY) AND GENDER = FEMALE
"male space': (JUNKY OR ALCOHOL) AND (CRIMEPROPERTY) AND GENDER MALE.
We compute explanations for 50 samples within the corresponding constrained space. Figure shows results for LIME (a) and CLIME (b), respectively, for both constrained spaces. At each plot, the blue histogram shows results for 'female space' and the orange histogram shows results for 'male space', respectively. Each bar shows the average rank of a feature in explanations, e.g. if the height of the bar the corresponding feature mostly top ranked in all explanations.
First, we observe that the 'Gender' ('Gndr") and 'Crimeproperty' ('CrPr') features are fixed in these sub-spaces. Hence, these features are always ranked last by CLIME demonstrating the correct behaviour (any feature with constant value cannot influence the decision so should have the zero coefficient in the explainer model g defined by Eqn. 2.. Note that LIME is not informative enough for distinguishing between these constrained spaces. However, results of CLIME are very interesting, We observe that 'Race' is one of the top feature to make decision for female prisoners (the 'Race' blue bar has small height) and only 4th (on average) for males. On the other hand, whether male prisoner is 'Married' ("Mard") make the most difference which is also an interesting potential bias that we reveal.
Defecting Adversarial Attacks. Slack et 2020) presented way craft an adversarial attack that seeks to hide the biased predictions made by "bad' classifier (ex: one that decides credit card applications solely on a sensitive feature like race) from detection by post-hoe explainers like LIME, Given biased classifier, their idea was to construct an adversarial classifier that outputs the biased classifier's 's prediction if an input instance is detected to be in-distribution, and outputs prediction based innocuous feature if the input instance is OOD. When LIME is used for explaining prediction made by the adversarial classifier, almost all of LIME's 's perturbed samples are detected to be OOD, resulting the innocuous feature appearing the top explanation. In this way, the sensitive feature used for deciding in- disstributiinn instances is successfully hidden. The attack crucially relies the ability to train classifier distinguish between LIME's perturbed samples and instances
8

---

Under review as a conference paper at ICLR 2021
1.0
1.0
Sensitive Feature (Race)
1st Unrelated Feature
0.8
Frequency
Frequency
Age
priors
weo_ye
Other
0.0
5
3
6
Hamming Distance
Hammiing Distance
(a) Adversarial Classifier
(b) Non-Adversarial Classifier
Figure 4: Recidivism: Top CLIME explanation distribution vs. Hamming Distance
from the original distribution with high accuracy. In this experiment, explore how CLIME can be used for detecting such attacks.
We hypothesized that for discrete data, the distinguishing classifier should have trouble differentiating between instances from the original dataset and instances with low Hamming distances to points in the original dataset. For given Hamming distance and set of instances S, is possible to construct formula 6 such that the solutions of d are exactly those instances that are at most at distance h from each instance S. We took S to be the set of nearest neighbors of the instance being explained. If our hypothesis is correct, the adversarial classifier should have trouble hiding the sensitive features the subspace Z for low values h. Thus, sensitive features should appear in the top CLIME explanations when / is small, while innocuous features should dominate for larger h.
To test our hypothesis, we generated 200 CLIME explanations using discretized versions of the three datasets used by (Slack et al. 2020). We computed the relative frequency of feature appearing as the top explanation for different values of The results for the Recidivism dataset with innocuous feature depicted in Figure 4a (we defer results other datasets and extended discussion to Appendix [.3 for lack space). We plot the hamming distance h on the X-axis and the frequency of seeing feature the top explanation as the top explanation for 60% of the instances explained when = 2. The innocuous feature (1st Unrelated Feature), appears almost exclusively as the top explanation when h For comparison, we depict results on CLIME explanations for a non-adversarial classifier in Fig. 4b We see that the relative frequency with which feature appears as the top explanation changes very little for different hamming distances. Note that for LIME explanations (not shown), the innocuous feature appears as the top explanation for all of the instances explained. While it may possible to craft even more sophisticated attacks, these results clearly demonstrates CLIME's ability detect adversarial attacks that exploit OOD sampling.
the Y-axis. We the sensitive feature 'race' appears
CONCLUSIONS AND FUTURE WORK
We presented a model-agnostic explanation framework CLIME that is able operate on constrained subspaces of inputs. We introduced a new metric for quantifying the severity of the OOD sampling problem and empirically demonstrated CLIME's ability to mitigate Additionally, our new estima- tion algorithm enables computation of an explanation's 's quality up any desired accuracy. The need for making XAI more rigorous and evidence-based has been highlighted the past Dooshi-Vller & Kim 2017). and we believe our framework takes concrete step this direction. CLIME can also be readily extended in numerous ways. Helping the user with defining relevant subspaces by mining constraints from data is interesting direction. Once sampling tools improve, richer constraint languages like SMT (Barrett Tinelli 2018) can provide even more flexibility, Construction of
CLIME's explainer model can also incorporate Shapley values as in (Lundberg & Lee 2017).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Amina Adadi and Mohammed Berrada. Peeking inside the black-box: A survey on explainable artificial intelligence (XAT). IEEE Access, 6:52138-522 52160, 2018. doi: 10.1 N0.110/ACCESS.20 2011 2870052.
Aws Albarghouthi, Loris D' Antoni, Samuel Drews, and Aditya Nori. Fairsquare: probabilistic ver- ification of program fairness. Proceedings of the ACM Programming Langwages, ((OOPSLA): 1-30, 2017.
David Alvarez- Melis and Tommi S. Jaakkola. On the robustmess interpretability methods. CoRR, 0e//1806.00449 2018. http://aaxxx
abs/ 08049
Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18:
2018.
Florent Avellaneda. Efficient inference of optimal decision trees. In The Thirty-Foure Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 3195 3202. AAAI Press, 2020. https:/tt:///a wtt./oooo///ooooooooooo wwwp::ppppppaaaaa..a view/5717
Clark Barrett and Cesare Tinelli. Satisfiability modulo theories. In Handbook of Model Checking, pp. 305-343. Springer, 2018
Osbert Bastani, Xin Zhang, and Armando Solar-Lezama. Probabilistic verification of fairness properties via concentration. Proceedings of the ACM on Programming Languages, ((OOSSLA): 1-27, 2019.
Anton Björklund, Andreas Henelius, Emilia Oikarinen, Kimmo Kallonen, and Kai Puolamäki. Sparse robust regression for explaining classifiers. In International Conference on Discovery Science, pp- 351-366. Springer, 2019.
Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, (72(6-7):772-27 2008.
Dagum, R. Karp, M. Luby, and Ross. An optimal algorithm for Monte Carlo estimation. SIAM Journal on Computing, 1484)144441496 2000.
DARPA. DARPA explainable Artificial Intelligence (XAI) program, 2016.
Adnan Darwiche. Three modern roles for logic in Al. CoRR, abs/2004.08599, 2020. URL https
08599
Adnan Darwiche and Auguste Hirth. On the reasons behind decisions. CoRR, abs/2002.09284, 2020.
URL wtt.httts//aaxiv.oooom
abs 220/22022222 09284
Finale Doshi-Velez and Been Kim. A roadmap for a rigorous science of interpretability. CoRR, abs/1702.08608, 2017. URL httth: org/ hatgg/bb/11700 08608
Amirata Ghorbani, Abubakar Abid, and James Y. Zou. Interpretation of neural networks is fragile. In The Thirty-Thire AAAI Conference on Artificial Intelligence, AAAI 2019. The Thirty-First Innova- five Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pp. 3681 16688, AAAI Press, 2019. doi: (300///3.i.3331133330 hittp::/ddi..ogg/ 1ttp//1...661/000 1ww9/66098.... 3331
URL
Bryce Goodman and Seth R. Flaxman. European Union regulations on algorithmic decision-making and "right to explanation". Al Magazine, 38(3):50-57, 2017.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM Comput. Surv., 51(5): 93:1-93:42, 2019. doi: 10.1 145/323600..
10

---

Under review as a conference paper at ICLR 2021
Rahul Gupta, Shubham Sharma, Subhajit Roy, and Kuldeep S. Meel. WAPS: Weighted and projected sampling. In Proceedings of Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 4 2019.
Robert R. Hoffman and Gary Klein. Explaining explanation, part 1: Theoretical foundations. IEEE Intelligent Systems, 32(3):68-73, 2017. doi: 10. 1119//IS.2007..55
Robert R. Hoffman, Shane Mueller, and Gary Klein. Explaining explanation, part 2: Empirical foundations. IEEE Intelligent Systems, 32(4):78-88) 86,6,666660 2017. doi: 10. 10.1109/MISS2217.12115444
Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. In Advances in Neural Information Processing Systems 32, pp. 7267-7275. Curran Associates, Inc., 2019. URL http:
// //papers.... n wttppcccppppppeeeepppppppp 8947- 7- opt ma spwase--s-eee...e deci sions pdf
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Abduction-based explanations for machine learning models. In AAAL, pp. 1511-1519, 2019.
Daniel Kang, Deepti Raghavan, Peter Bailis, and Matei Zaharia. Model assertions for monitoring and improving ML models, In Inderjit S. Dhillon, Dimitris S. Papailiopoulos, and Vivienne Sze (eds.), Proceedings of Machine Learning and Systems 2020, MLSys 2020, Austin, TX, USA, March 2-4, 2020. mlsys.org, 2020. URL http:tss:: http://rooceeee ngs .wlyys.....m.m........lmm....... wtt/book..o.oooooooooooooooooooo 319 pdf
Ron Kohavi. Scaling up the accuracy of naive-Bayes classifiers: A decision-tree hybrid. In KDD, pp. 202-207, 1996.
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 Al, Ethics, and Society, pp. 131-138, 2019.
Himabindu Lakkaraju, Nino Arsov, and Osbert Bastani. Robust and stable black box explanations. ICML 2020, 2020.
Zachary C Lipton. The mythos of model interpretabilltyy Queue, 16(3):11-57 2018.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. NIPS, pp- 4765-4774, 2017.
Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver; BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL htttp:://ppereeweeeee
net/ forum?id-
TZZIBfZAD
Kuldeep S Meel, Aditya A Shrotri, and Moshe Y Vardi. Not all FPRASs are equal: demystifying FPRASs for DNF-counting. Constraints, 24(3-4):211 1--333, 2019.
Nina Narodytska, Aditya A. Shrotri, Kuldeep S. Meel, Alexey Ignatiev, and João Marques-Silva. Assessing heuristic machine learning explanations with model counting. In Mikolás Janota and Inés Lynce (eds.). Theory and Applications of Satisfiability Testing SAT 2019 22nd International Conference, SAT' 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings, volume 1 16628 of Lecture Notes in Computer Science, pp. 267-278 Springer, 2019. doi: 10. 00..1007977--3-00-220000
11_
URL
1000/ 3 030 24258 19
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?": Explaining the predictions of any classifier. In KDD, pp. 1135-1144, 2016.
Marco Túlio Ribeiro. Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In AAAI, 2018
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead, 2019.
Peter Schmidt and Ann D. Witte. Predicting recidivism in North Carolina, 1978 and 1980. Inter- University Consortium for Political and Social Research, 1988. URL https: /tt:://wwwww /www joirs gow/App/Publlice ons htsp wwtpctt.spppxxxpDi00

---

Under review as a conference paper at ICLR 2021
Patrick Schwab and Walter Karlen. Cxplain: Causal explanations for model interpretation under uncertainty. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlche Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems 32, pp. 10220-10230. Curran Associates, Inc., 2019.
Andy Shih, Arthur Choi, and Adnan Darwiche. A symbolic approach to explaining Bayesian network classifiers. IJCAI, pp. 5103-5111, 2018.
Andy Shih, Arthur Choi, and Adnan Darwiche. Compiling Bayesian network classifiers into decision graphs. In AAAI, pp. 7966-7974, 2019.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the
34th International Conference Machine Learning. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 3145-3153. PMLR, 2017. URL httt:::/proeeeeinnngggeo/o htt.:/ees.iaaaa.....rrreess//o//
mlr www.preessseeee v70 wwteesss/vO///hrikkui
7 html
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 on AI, Ethics, and Society, AIES '20, pp. 180-186, New York, NY, USA, 2020. Association for Computing Machinery, ISBN 9781 1781450371 100. doi: 10.1 10.1145/3375627.335583 3337777777737733 3375830
URL
Kacper Sokol, Alexander Hepburn, Raul Santos-Rodrigutn and Peter Flach. bLIMEy: surrogate prediction explanations beyond LIME, arXiv preprini arXiv:1910.13016. 2019.
Mate Soos, Stephan Gocht, and Kuldeep S. Meel. Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling. In Proceedings of International Conference on Computer-Aided Verification (CAV), 2020.
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 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 hattp://proceedingg mlr. wttps///w//sundrreeeer fanlaa
Matthew D. Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In
David J. Fleet, Tomás Pajdla, Bernt Schiele, and Tinne Tuytelaars (eds.). Computer Vision ECCV
2014 13th European Conference, Zurich, Switzeriand, September 6- 12, 2014, Proceedings. Part I,
volume 8689 of Lecture Notes in Computer Science, pp. 818 833. Springer, 2014. doi: 10.1007/ 978-3-319-11 10590-1
URL /ttp://////aaaooo/////////000000 905
53
Yujia Zhang, Kuangyan Song, Yiming Sun, Sarah Tan, and Madeleine Udell. why should you trust my explanation?" understanding uncertainty in lime explanations. arXiv preprint 19:::19::99999
2019.
12

---

Under review as a conference paper at ICLR 2021
A RELATED WORK
Model explainability is one of the most important problems in machine learning. Therefore, there are a large number of recent surveys on the topic, e.g. /Hoffman & Klein (2017); Hofffma et al. (2017): Lipton (2018); Adadi & Berrada (2018); Guidotti et al. (2019): Rudin (2019). To overview, we partition approaches to generate explanations for ML models into two groups based on whether they provide theoretical guarantees on the quality of the generated explanations.
Explanations without theoretical guarantees. There were a number of approaches proposed to compute (model-agnostic) local explanations. We have overviewed LIME (Ribeiro et al. (016)) in Section 2 Anchor is a successor of LIME (Ribeiro et al. 2018). The main contribution of Anchor is to produce explanations that hold globally, for the entire distribution of inputs. SHAP (Lundberg & Leep 2017) is another popular model-agnostic explainer to produce local explanations. Similar to other explainers, SHAP does not provide any theoretical justification for the sampling procedure. However, SHAP employs game theoretic principles to produce an explainable model. Our work focuses on model-agnostic, local explanations, however, we produce explanations with provable guarantees. CXPlain proposes to train an additional 'explanation model' to provide explanations for given ML model (Schwab & Karlen 2019). Learning of the explanation model involves an estimation of feature importance using causal objective. The causal objective captures how input features cause a marginal improvement in the predictive performance of the ML model. In our work, we do not consider each feature individually and reason about the space of features our framework allows us to work with constrained spaces. Finally, works such as (Lakkaraju et al.) 2019) provide limited capabilities for customizing global explanations by letting the user supply set of features that the they deem important. Similar to (Björklund et al. 2019), they avoid sampling a neighbourhood around given point by using original data points to construct an explainer. While avoiding sampling helps scalability, it also undermines applicability. For instance, dealing with user-defined constraints, as well unbalanced skewed input datasets can be problematic. In both cases, the input data may be too sparse to yield meaningful explanations. Recently, Lakkaraju et al. (2000) demonstrated that these explanations are less robust compared to LIME, for example.
whole. Moreover,
Another line of work in on gradient-based explainers, for example, saliency maps (Zeiler & Fergus 2014), Integrated Gradient (Sundararajan et al. (017), DeepL.IFT (Shrikumar et al.. 2017). Gradient- based methods assume full knowledge about the ML model and, also, require these models to be differentiable. While these methods are very efficient, they do not provide theoretical guarantees on the produced explanations. On top of that these approaches are not model-agnostic.
Explanations with theoretical guarantees. Recently, a formal approach to analyze explanation of MI. models was proposed. If an ML model allows formal representation in restricted fragment of the first order logic, then one can (a) define formal notion of an explanation and (b) design an algorithm
to produce these explanations (Shih al.] 2018 2019 Ignatiev et al. 2019 Darwiche & Hirth 2020 Darwiche 2020p. One of the formal approaches is built on powerful knowledge compilation
techniques, e.g. (Shih et al. 2018 2019). The other approach employees very efficient formal reasoners, like SAT, SMT or ILP solvers, as part of explanation generation algorithms (Ignatiev) al. 2019 Narodytska et al. 2019). If the process of ML. model compilation into tractable structure feasible then the first approach is very effective and allows the user to analyse the ML model efficiently. However, the compilation can be computationally expensive and resource demanding. so the second approach is more efficient in some applications. There are some limitations of these approaches. First, similar to gradient- based methods, they require full knowledge of the original ML model. Second, in practice, these approaches face scalability issues as reasoning about ML models formally is computationally expensive.
Quality of the explanations. Finally, we consider a recent line of work on analysis of the quality of explanations. [Ribeiro et al. (2018) proposed several heuristic measures to evaluate quality of explanations including fidelity and coverage, but do not provide a way to estimate the true value of these metrics. In (Ghorbani et al. 2019 Alvarez-Melis & Jaakkola, 2018), it was shown using perturbation- based methods that explanaiions are susceptible to adversarial attacks and lack robustness property. For example. Zhang et al. (2019) investigated several sources of uncertainty in LIME, like sampling variance in explaining a sample. The authors experimentally demonstrated that LIME often fails to capture the most important features locally. However, the paper does not propose solution to
13

---

Under review as a conference paper at ICLR 2021
remedy identified issues. Moreover, (Slack (lrcck al. (0200) showed that it is easy to fool explainer, like LIME and SHAP, as we discussed in detail in Section | Narodytska et al. (2019) presented a technique for evaluation quality of explanations based on model counting. but their approach suffers from scalability issues (as shown in Sec. 4.2) and is only applicable to BNNs. Lakkaraju et al. (2020) proposed
adversarial training (Madry et al.) 20T8) improve robustness of the explanations. While the proposed approach improves robustness to adversarial attacks it cannot be easily extended work in constraint environments and does not provide theoretical guarantees on the fidelity of the explanations. A related line of work on probabilistic verification of ML models has seen surge in interest. (Albarghouthi et al. 2017) encoded the underlying model and fairness properties as formulas in SMT over real arithmentic, and relied on symbolic integration techniques. However, this approach known not to scale, eg. it can only handle neural networks with single hidden layer containing just three hidden units. (Bastani et al. 2019) present an alternative approach that uses Monte Carlo sampling and adaptive concentration incqualities. However, unlike Alg. 2 their method only returns yes/no answer and does not provide quantitative estimate. Further, their algorithm may fail to terminate on some inputs, and the sample complexity is not proven to be close-to-optimal.
B ANALYSIS OF LIME (ADDITIONAL MATERIALS)
B.1 PERTURBATION PROCEDURE
LIME generates the neighborhood of the data point under explanation differently, depending on whether the given dataset is text, image or tabular. For text and images, LIME first maps given point æ E Rd to x' E {0, 13dd and then samples z' E {0, 1 in the neighborhood of x', For tabular data, LIME first samples points z' in the neighborhood of x and then maps them to the interpretable domain z'. The distance function is also defined on the binarized space instead of the original space.
Text and Images For text and image data, the given point is first mapped the Boolean domain. For text, the Boolean domain is simply the presence or absence of each word in x, while for images, is first divided into superpixels, and the Boolean domain is represented by the presence or absence of each superpixel. Points z' in the neighborhood of x' are sampled by flipping a few Is to Os where both the number and positions of 1s to flip are chosen randomly. Each z is mapped back to the original domain to obtain 2' which are then input to f for obtaining the 'true' labels. Interestingly, LIME's sampling procedure for text and images does not depend on the training set which is not the case for tabular data.
Tabular Tabular data consist of both continuous and categorical features. Although LIME can work with continuous data natively, the recommended way is to perform quantization first using statistics of the original dataset. We denote I = - ( the set of all intervals that we obtain due to discretization the jth feature. To construct a neighborhood 2 LIME uniformly samples features values from each interval in I' for the ith feature. For categorical features, LIME builds distribution of feature values and samples values for each feature in proportion to their frequencies.
Construction of an interpretable domain. Next, we consider how an interpretable binary domain is produced. For each sample z in the neighborhood Z, the corresponding is constructed as
1 if (z) ET)) ^ (1zE
Discretized features: z/ == bin(z;) =
(6)
0. otherwise
[1, if =
Categorical features: z/ == bin(zy) (z))
0, otherwise
We denote bin(z) the mapping function from the original feature vector 2 to a binary vector 2', z' = bin(z). Thus z' = bin((). As this mapping is many-to-one, we denote pre-image(z" the set of samples that are mapped to z':
pre-image (x2))
(2') {2]bin(=)= = 2).
(8)
14

---

Under review as a conference paper at ICLR 2021
Interpretation of an explanation. recall the meaning of explanation for a vector given linear regression model g defined by Eqn. Suppose the ath coefficient is great than zero, C > 0. Then the value o₁ is interpreted to 2; then on average the value of g(z) decreases by G. To see why it is so, we consider the binary space z' = b)n(z). If f + 2; then 2 = O. Hence, contribution of the term o22 to the value of g(=²) is decreased by ct Similarly, if c, < 0 then the value e₁ is interpreted as a contribution to the class 0. If ft A 2; than the value of g(z") increased by cj.
contribution toward the class 1. Namely, if the ith feature fü is not equal
B.2 DISCUSSION ON THE QUALITY OF THE PERTURBATION PROCEDURE
The quality of explanations depends on the closeness of samples 2 to samples from the original
distribution DD In Section 3 we introduce a simple metric SQ(E) = Wz//D (see Eqn. to measure the quality of Z. Please note that the SQ metric might look similar to the fidelity metric that is defined in Eqn. [1 However. these metrics are different. SQ measures quality of the sampling procedure based on the behavior of an ideal classifier on the generated samples, while P evaluates the closeness of two models and f.
We recall that if the sampling procedure is correct then SQ(E) should be close to for a perfect classifier. While we can always experimentally measure W2', the value Wp cannot be compute in general. However, we will use few crafted classification tasks where WD can be computed exactly to highlight the difference in behaviour of LIME and our proposed procedure.
The following crafted example designed to highlight that OOD sampling occurs and our SQ(E) metric is able to detect it. Moreover, we show that the quality as explanations suffer due to the OOD sampling.
Example B.1 ("Hit or miss'). We define the classification problem to illustrate issues with the OOD sampling. This problem models a situation when the classifier relies on seeing specific feature values in the input sample to make its decision. As we mentioned above, the reason we work with a crafted problem is that we can compute the value WD exactly, which is not possible for real world datasets.
Definition of a task. We consider two areas So and S₁ on the 2D plane (see Figure [(a). A sample I, x ~ D, represents integer coordinates of three points p1. P2 and p3 drawn from So U St. Hence, we have six features vector x = [x1, T2...., Ic)], where = (I25-1, x22), i = 2, is a 2D point, or x = [p1 [p1.P2, P2, P3] = (111,42) (Ig, 24). (15, 276)] If there is Ps E x s.l. ps & So S₁ then x is an out-f-distribution sample. For example, [(7, 7). (7, (10, 10) is an in-distribution sample, while [(1, 10), (7, 7), (10, 10)] is an out-of-distribution sample as the first point (1, 10) & So S1.
Given sample and belongs to Co otherwise. For example, [(7, 7), (7, 7), (10, 10)] belongs to Ci as the third point (10, 10) St. So. if one of three points in I hits S1 then x is classified Ct. In this example, an explanation for a sample x is well well-defined as points in the So (resp. S1) area contribute to the Co (resp. C1) class, respectively.
D, say that x belongs to C1 iff there exists i s.l. Pt E S1, i E [1,3].
LIME performance. We train an almost perfect neural example (See more in Section E. We compute our metric SQ LIME and get that SQ(LIME) 0.75 which is less than hinting that the sampling procedure is biased.
classifier for this simple
To see how SQ affects explanations, we generate LIME explanations for samples [77,7),(7 (7, (7,7), (7, (7,7)) that is close to the corner (8,8). As all points in & are in So, x. belongs to class Co- Table shows explanations for this point in the column 'Balanced dataset'. The first row shows explanations produced by LIME. The red horizontal bar indicates that the corresponding feature has a negative coefficient in g and it contributes toward Co Symmetrically, the green bar indicates that the feature contributes toward C1. We can see that an explanation of x is incorrect as some features with values less than 8 have positive contributions, e.g. features DA and Vs have sampled green burs, so they contribute toward the wrong class C₁. In our experimental evaluation instances around the corner (8,8) with p: E So, E [1,3]. So, all these samples belong to the class Co hence, all features should have negative coefficients the liner model g. We found that LIME explanations have 25% of features with positive coefficients in g that contribute to the wrong class C1 which is an incorrect behaviour.
15

---

Under review as a conference paper at ICLR 2021
Hit or miss
Projected explanitions (Example
Explainer/
Balanced datasel
Unhalanced dalasel
(Examples B. C.1
(Example C.2
sample
8
LIME
CLIMB
Table 1: LIME and CLIME explanations Examples B.1
C.I
C.2
and C.3
C GENERATING CONSTRAINT-DRIVEN EXPLANATIONS (ADDITIONAL MATERIALS)
In this section consider several examples to demonstrate undesired consequences of OOD sampling for LIME and how these are resolved by CLIME. Each of these examples designed to model an abstraction of the real user-case. Moreover, for these simplified tasks, we can estimate quality of the sampling procedure using our metric SQ as we can compute Wp analytically.
Example C.1 ('Hit and miss continued"). We come back to Example B. to evaluate performance of CLIME. First, we estimate our metric SQ: SQ(CLIME) = 0.999. As it is close to I, we conclude that CLIME samples from the true distribution. Then we generated explanations produced by CLIME for the same sample [(7, 7), (7, (), (7, 7)). The second row (Table [| 'Balanced dataset' column) shows explanations produced by CLIME Note that CLIME produces valid explanations all features with non-negligible coefficients have negative contributions (the corresponding horizontal bars are red). The same holds for all samples x = [P1P2, P2PP with P. E So that are in near the corner (8,8). We recall that these samples were problematic for LIME to produce correct explanations.
Example C.2 ("Hit and miss'. Sensitivity to the training set), As we described in Example B. LIME sensitive to OOD samples even if we have a near to perfect classifier f. Moreover, we observed that the choice of the dataset can severely impact explanations. We created new dataset for the same classification task as in Example B. [ (Figure [T. The only difference that we have twice more Co samples compared to C1 samples in the training set. Unbalanced datasets are often occur in practice if samples for one class are much cheaper to obtained compared to the other class. We compute SQ: SQ(LIME)
0.43, which is much less than 1, and (Q(CLIME) 0.998. Table UUnaalanced dataset') shows our results for x in the second column. Based on our metrics, is expected that CLIME produces better explanations almost all features contribute to Co which is not the case for LIME.
I
Example C.3 ('Pojeeced explanations'). Let us consider a scenario where the user asks for an explanation constrained on subspace of the original distribution D. For example, for the recidivism dataset, a user might want to know how decisions are made for the subgroup of people who are junkie or have problems with alcohol. Here, craft synthetic example show how projecting on such subsets of features can affect explanations.
Definition of a task. We consider areas So and S on the 2D plane (see Figure 5 A sample x from 'D represents five 2D integer points from So U S1. Hence, we have ten features vector == -pI,, . Pp] = [(x1,
[10]], where (I2i-1, F21),, i 1..... is a 2D point. Given [p1...., ps]. we say that belongs to C1 iff there exist i, [1,5] s.f. P.. S1 and to Co otherwise. So, if two out five points x are in S then x is classified as 1. As in Example B.1 points in the area So (resp. S1) contribute to the Co (resp. Ci) class, respectively.
sample
16

---

Under review as a conference paper at ICLR 2021
12
S
4 (4,4)
S 0
Figure 5: Projected explanations example.
Projection constraints. Next, we assume that the user adds constraints that the first two points must be in Sy: Pr.P2 P2 So. we have a constrained distribution, namely, Po: P1 So, we know that the first four features, I1, 222 T., and F4, should not appear in any explanation as no matter how we vary these features values in the constrained space, the corresponding points pıs P2 are always So- Hence, the corresponding coefficients of features I.,.... U,,, should be close to zero as changing these features in the constrained space does not have an effect on the prediction.
Explainers performance. We truin almost perfect neural network- classifier for this simple task. We consider explanations of length six. We compute our sampling quality metric SQ. We get that (Q(LIME)) 1.38 and SQ(CLIME) sampling procedure does not sample from the true distribution.
0.97. Hence, these estimates signal that LIME's
Table shows results for LIME and CLIME in the third column ('Projected explanations' for another sample x = [[1, 1), (1, (12, 12), (12,12), (12, 12)]. As you can see, 23 and xa occur in the explanation for LIME which is incorrect. CLIME produces correct explanations as constrained features Dı, 32, 33, and xa do not occur in CLIME's explanations. (See more in Section E.T
D CERTIFYING CONSTRAINT-RRIEER EXPLANATIONS (ADDITIONAL MATERIALS)
D. AA' ALGORITHM
For completeness. we present the AA' algorithm in full, which is a simple adaptation of AA4 algorithm by (Dagum al. 2000) which uses almost-unifome samples instead of perfectly uniform. AA', takes as imput 3 parameters, E, and 8. It uses as the tolerance parameter in calls to almost-unifome sampler (encapsulated in procedure get.Samples). For ease of exposition, we use denote the subspace that get.Ses generates samples from. We emphasize that the estimation algorithm is not limited to Boolean domains; is applicable to any population so long as it is possible to sample (almost) uniformly from that population. As before, assume access to procedure check Property which returns if the property of interest is satisfied by the sample and otherwise.
- (1)
Pr
p ps و (1+ #2)p] 2 (1-6)
1+
The guarantees provided by AA' are similar to Eqn. and are precisely captured in Eqn. See Lemmas I and for the proof.
D.2 PROOF OF THEBOEM 1
Mean deviation due to almost uniform sampling
Lemma 1. Let be the density of instances that satisfy some property P in universe U that is.
ExEuz [[)())
U2
17

---

Under review as a conference paper at ICLR 2021
Algorithm 4 (E,
Algorithm 5 stoppingkull(ee.e22...77
Output: 7: Estimate of p satisfying Eqn.
Output: (weak estimate)
I: - 4(e 2) ln(2/0)/ef
1: T < 1 (1 + &1)T
2: T2 1.1r
2: N +
3: p <
SeppingRullrs 6//
c2,
3: a 0
4: N +++7 T2. p
4: while
< Ti do f getSaemmessso E2,
5: a a 0
5:
6: for
E {l...., N3 do
6:
< a + checkProprrty
7:
$1 + gelSamples(0, E2,
7: end while
8:
C1 - check croertrop))yy(ss))
8: f n/N
9:
82 + getSamples(o, E2,
9: return p
10:
C2 + check Property(s)
11: at atat (c1 c2)2/2
12: end for
13: & < mar(a/N, P E1) eie
14: N+ E/1²
a a
16: for E fl.....,y N do
- getSamplesi E2, 12, 1)
18: t check check Property(s)
19: a a
20: end for
21:
p+a/N
22: return
Suppose we sample each instance E U2 almast-uniformly, that is
(1 +1+ 1 S Priz"" = = 112
E
Then we have
Σ [1P(2)]-Pr(2 = =] s (1 (1+
(1 E))
=El
Proof. In the worst cases, each sample z s.t. [[P(2)] = 1 will be sampled with
1. probability
Itc in which case Σz [[)))) Pr(=- = 2] = (1 + 8) u2..
2. probability (1+2) in which case Ease I[P(=)] Pr[z* 2] (πfe]
Lemma 2. Let S Then the probubility that checkThheshhoe returns True is at-least 1
6.
Proof. Note that μcc & (1 + e/2)p as Setpamllees may return almost uniformly distributed samples in line 3 of checkThrrshold We will first prove that pC + v S 7. We have
(1+ e/2) S
- - -100+))))-08/2--
But we have 7 2 p + E. Therefore,
(p+8) (1++ - 72/2 S7
= p + - 3
PC +VS
18

---

Under review as a conference paper at ICLR 2021
The last equation follows from the fact that PCc S (1+e/2) and < < 2 from line 1 of TheckThresheee Now since PCc + V S Y, we have Pr[C S 7 2 Pr[C S fic + = Pr 2 MC 2/. C is the average of N independent 0/1 random variables e (line 6). Therefore applying Chernoff bound,
Pr(C 2 Pic + v/ exp(-2u²N]
(10)
But N 20a log( H. Therefore, Pr[C uc+ I 6. Substituting back, get Pr(C S >) 1- Therefore, in line 8, the probability that checkThreshold returns True, is at least
Lemma 3. Let 2 +.. Then the probability that checkT'hreshole returns False is at-least 1
8.
Proof. Similar to preceding Lemma.
Lemma 4. Algorithm AA' returns estimate p such that Pr((1-=)po S SP S (1+E)pol 2 (1 (1-8)
Proof. Algorithm AA' takes input 3 parameters, E1, E2 and 8. It invokes the AA Algorithm by Dagum et al. with parameters E and on samples generated by an almost-uniform sampler with parameter 62- By Lemma [ the population mean can shift most by factor of (1 + 82) due to almost-uniform sampling (instead of perfectly uniform). Combined with the approximation guarantees of AA algorithm, the resulting tolerance has an upper-bound of (1 + #1) (1 + s2) and a lower bound of (1 e + E2). In line 4 of Alg. 2 the AA'' algorithm is invoked with E = E2 = 0.4 E. Substituting these values in the expressions for the upper and lower bounds on tolerance, we get the result.
Theorem 1. If p S 7 - E, then compute CumputeEstimate Stimatee returns 1 with high probability (i.e. at least 8) 8). p 2 7 + E, w.h.p., it returns estimate " such that Pr[(1 t)p S p S (1+=)pl 2 (1 (1-0) 8).
Proof. Follows from preceding lemmas.
Note that the bounds and number of samples used for proving the preceding theorem were computed assuming we only have access to Almost-Uniform Uniform samples. The bounds can be made significantly tighter or the number of samples can be reduced, if we have access perfectly uniform samples.
D.3 APPLICABILITY OF THE ESTIMATION FRAMEWORK
We emphasize that our estimation framework is general enough to compute any metric for any universe (so long one can sample from it almost uniformly) according to the guarantees provided by Thm. in any setting (not just explainability). Further, for the specific application explainability, our estimation framework can be used for measuring properties like fidelity of any explainer model (not just the ones crafted by CLIME), and on any subspace of inputs (not just the one that the explainer was trained on). For example, the fidelity of a CLIME explainer model trained on a subspace defined by one set of constraints (say の) maybe evaluated on another subspace defined by vb. If the fidelity on vi found to high enough, it can save the cost of having to generate a separate explanation for th. This can be especially useful in model debugging where users may refine constraints frequently.
D.4 EMPIRICAL EVALUATION OF ESTIMATION ALGORITHM
In order to test the scalability of our estimation algorithm (Algs. we evaluated its performance on the same set of benchmarks used by (Narodytska et al. 2019).
The benchmarks are CNF formulas that encode fidelity of Anchor (Ribeiro al.. 2018) explanations for Binarized Neural Networks with upto 3 hidden layers and 100 neurons in total, and are generated from Adult, Recidivism and Lending datasets. There were 50 CNF formulas from each dataset, for a total of 150 benchmarks, with number of variables ranging between 20,000 to 80,000 and number of clauses ranging between 80,000 and 290,000. The projected model count of each formula represents the number of inputs which the class-label for Anchor's explanation matches the true label of the instance being explained. The fidelity of an explanation can thus be computed as the ratio of the solution-count of the formula, to the size of the universe.
Benchmarks
19

---

Under review as a conference paper at ICLR 2021
Parameters We used the same tolerance = 0.8) and confidence (6 0.2) used in (Narodytskal iet al., 2019), for the main experiment. Additionally, we set the threshold to = 0.05. We also compared the running times for tighter tolerance and confidence (see Discussion below).
Experimental Setup We set time out of 3 minutes (180 seconds), and ran each experiment Intel Xeon E5-2650 CPU running at 2.20GHz, with 4GB main memory. We compiled our code using GCC 6.4 with 03 flag enabled. For ApproxMC we used the latest publicly available version (4.01). ).
The results presented in Fig. Each point in blue corresponds one benchmark, and the X-coordinate represents the time taken by ApproxMC while the y-coordinate represents the time taken by our approach. seconds with majority taking less than 10 seconds. In contrast, ApproxMC is able to finish only 10 benchmarks out of 150 in under 25 seconds, with a majority taking around seconds. The average (geometric mean) speedup factor offered by our tool relative to ApproxMC was 7.5.
Results
be seen that our approach completes all benchmarks in under 25
Discussion Fig. conclusively demonstrates the efficiency of our approach as compared to hashing and SAT based approaches like ApproxMC. Our tool was able to return estimates with two-sided bounds for all benchmarks. Our tool offers an average (geometric mean) speedup by a factor of 7.5 relative to ApproxMC. In addition, our approach able to scale far better than ApproXMC for tighter tolerance and confidence parameters. For representative benchmark, by our tool and ApproxMC for the default tolerance (E = 0.8) and confidence (6 = 0.2). We then computed the slow-dows in both tools after setting = 0.05 and confidence our tool slowed down by a factor of 10 while ApproxMC slowed down by a factor of 30. Lastly, we computed the error in the estimate returned by algorithm (with default tolerance and confidence) on small benchmarks where it was possible to compute the true count. We consistently observed that the error was less than 0.1, which is much smaller than the specified tolerance of 0.8. Thus our approach is both sound and efficient in practice.
evaluated the time taken
0.1. We found that
E EXPERIMENTS (ADDITIONA EXPERIMENTS)
We perform an extensive evaluation of our explainer CLIME. First, we consider explanations for classification task using synthetic and real-world datasets. Second, we demonstrate how our framework can be used detect adversarial attacks on an explainer.
E.1 SYNTHETIC EXPERIMENTS
For each synthetic dataset, we generated train and test datasets with 1000 samples per class. We trained MLP with three internal layers of fifty neurons that gives 99.9% on the test set. So, we have an almost perfect classifier.
E.I.1 'HIT OR MISS' (EXAMPLE B.
We consider binary classification task from Example B.I
We recall that sample I, D, represents integer coordinates three points pl, P2 and Pa drawn from So U Sj. Hence, we have six features vector [21, x2, where p: 22,) 1,2, is 2D point.
Computationn of SQ. As we know the true distribution, we can compute Wz. Let hit(r) = Heilp: E St,p; x]] be function that computes the number of points pt x n. St. For example, hit([[1,,) (10, 10), (10,9)] = 2 as (10, 10) E Si and (10,9) E Si. We have that [S.] 25/(25 + 49) 0.34. Hence,
P(p: E S1) |8o
Wo 3P(ht((x) = + 3P(hi((x) = 2) P(hit(r:) 3) x 0.15 + 3 0.07 + 0.04 0.7.
We generate 100 samples such that v; [5, 7], i= [1, 6). Therefore, each sample consists of points that are close to the corner (8,8) and it is classified as Co. We compute explanations by LIME and CLIME these samples. We empirically compute WLIME and WCLIME for the neighborhood z'. We found that WLIME 0.53 and W WCLIME 0.71 So, SQ(LIMF) x
20

---

Under review as a conference paper at ICLR 2021
0.75 1 and SQ(CLIME) = These results hint that LIME may produce invalid explanations. We experimentally verify this hypothesis next.
Explainers performance. We recall that each sample consist of points that are close to the corner (8,8) and it classified as Cg. Hence, we expect that coefficients in the explanations are less than 0 as all features contribute Co- To evaluate this expected behavior, we computed
> Zimlag0 Co
0+
Σ
where a is the ith normalised (between 0 and 1) coefficient in an explanation (Eqn. D). We average results over 100 samples. Ideally, C+ has to be equal to zero, as we should not have positive coefficients in an explanation in any of these samples. We get that CLIME = 0.18 and CCLIME = 0.01. As you can see, CLIE is significantly greater than zero showing that many explanations incorrect. Therefore, explanations produced by LIME suffer from ODD sampling and result in incorrect explanations.
E. 1.2 PROJECTED EXPLANATIONS (EXAMPLE
We consider a binary classification task from Example We recall that a sample x from D represents five 2D integer points from Sp U.. Hence, we have ten features vector x: = (Pi....,PP Ps] [<11, x22), .... (Igg ]110], where P; (2 i 1....,5 2D point. We recall that the user constraint is that P1,P2 P2 E Sp.
Computation of SQ. We define hil(x) the same way as above. We have that P(p: E Si) =
15
= 64/144 = 0.44 for this task. Hence,
181
WDnt = 3 x P(hil(z) 2) + P(hil(s) 3) 0.33 0.08 0.41.
We compute explanations by LIME and CLIME 100 samples that satisfy the user constraint. We ask explainers to give us the top six features per sample. Moreover, to help LIME to capture constraints, we provide it with dataset where Pt. E So for all samples. Then we run LIME and CLIME sampling procedures and compute W W.IME and W.C.IME for the neighborhood Z'. We found that W.I se 0.56 and W WCLIME se 0.40 So, SQ(LIME) se 1.38 > 1 and SQ(CLIME) x 1. Again, we can see that SQ(LIME) is significantly differ from indicating ODD sampling.
2'
Explainers performance. We run LIME and CLIME on 100 samples and compute the number of times each feature occurs in an explanation (an explanation contains features). Figure Figure6]showe (Jshows our results. For each feature, we show the number of occurrences of this feature in produced explanations. Namely, the blue histogram shows results for LIME and the orange histogram shows results for CLIME. As we discussed before, P1 and P2 are in So, so the first 4 features should not appear in the explanation as changing their values never affects the prediction. Indeed, CLIME almost never choose features ....... I4 in the explanation (almost zero height orange bars for these features). However, LIME often picks these constrained features in its explanations.
E.2 ADULT DATASET
The Adult dataset Kohavi 1996) is originally taken from the Census bureau and targets predicting whether or not a given adult person carns more than $50K a year depending on various attributes, e.g. race, sex, education, hours of work, etc. We pre-processed columns with continuous features, e.g. the pre-processor discretizes the capital gain and capital loss features into categorical features, e.g. 'Unknown', "Low" and 'High' (Ribeiro et al. 2018). We trained MLP with three internal layers of 64, 32, and 32 neurons that achieves 84.2% on the test set. We consider the two constrained spaces:
'emmaee space' == (CAPITAL LOss = 'UNKNOWN') AND (CAPITAL GAIN 'UNKNOWN')
AND (EDUCATION 10TH OR 11TH GRADE AND (SEX FEMALE)
'male space' := (CAPITAL Loss = 'UNKNOWN') AND (CAPITAL GAIN = 'UNKNOWN') AND (EDUCATION 10TH OR 1 11 GRADE ) AND (SEX MALE).
21

---

Under review as a conference paper at ICLR 2021
UIE CLIME
Bascurterces inseloraatun
80
20
X00
Figure 6: Occurrences of features explanations (Example C.3
We compute explanations for 100 samples within the corresponding constrained space. Figure 7 shows results for LIME (a) and CLIME (b), respectively, for both constrained spaces. At each plot, the blue histogram shows results for 'female space" and the orange histogram shows results for 'male space". Each bar shows the average rank of feature explanations, e.g. the height of the bar is 0.1 than the corresponding feature is mostly top ranked in all explanations. We used the following shortcuts of features names in Figure 7: 'Age' ('Age'), 'Workclass' ("WrkC'), 'Education' ("Edu'), 'Marital Status' ("Mard'), ) 'Occupation" ("Ocep'), 'Relationship' ('Relp"). 'Race' ('Race'), "Sex" ('Sex'). 'Capital Gain' ( ("CapG'). CCapital Loss' ('CapL'), 'Hours/weck' ('Hrs'), and 'Country' ('Cntr'). First, we observe that features Capital Loss, Capital Gain and Sex fixed in both constrained sub-spaces so their values should not influence the outcome. Note that these features are always ranked among last by CLIME. However, this is not the case for LIME. We observed exactly the same behavior in our synthetic example from Example CC3] Second, we can see that LIME explanations are not so much different for both spaces. While we do not have the ground truth to check against in this example, we can contrast LIME results with CLIME results. CLIME shows that 'Education' is more important for males than for females (see in Figure Fi), the orange bar is lower than the blue bar for the 'Education" feature). 'Relationship' seems to be more important for females than for males (see in Figure bb)), the orange bar is higher than the blue bar for the 'Relationship' feature). These results indicate that there might be potential bias in these spaces.
E.3 DETECTING ADVERSARIAL. ATTACKS(EXTENDED
Suppose biased classifier makes decisions solely based on some sensitive feature; for ex: classifier for accepting/ / rejecting loan applications that decides purely based on an individual's race. LIME's explanations for the predictions made by such classifier would clearly indicate race be major deciding factor. (Slack et al., 2020) devised a technique that takes such an arbitrary biased classifier and constructs another classifier that closely mimics the biased classifier on in-distribution data, yet is able to evade bias-detection by preventing the sensitive feature from appearing in post-hoc explanations. Note that accurately measuring the fidelity of the explainer model alone is not sufficient to detect such attack the problem lies in the way the opaque classifier is constructed and not in the resulting explanation. We first discuss the construction of the adversarial classifier, and then see how constraints can help in foiling it.
E. BACKGROUND
The attack makes use the fact that LIME'S perturbation procedure creates samples that are distinguishable from those of the original distribution. The first step is to train a classifier such as Random Forest to detect whether a given sample in or out distribution. This classifier is trained on synthetic data-set consisting of instances from the original data-set labeled in-distribution and LIMES perturbations of each those instances as OOD. This OOD detecting classifier is able to achieve very good accuracy, which is testament to the severity of the OOD problem of I. LIME.
22

---

Under review as a conference paper at ICLR 2021
LIME(female space)
CLIME(female space)
12
12
LIME(male space)
CLaME(male space)
Average feature ranking
Average feature ranking
10
10
8
8
6
6
4
4
2
Age
Wikc
Edu
Mard
Occp
Relp
Race
Sex
CapG
Capl.
Hrs
Cntr
Age
WrkC
Edu
Mard
Occp
Relp
Race
Sex
CapG
Capl.
Hrs.
Cntr
(a)
(b) CLIME
Figure 7: Explanations for the adult dataset on female and male spaces.
The next step in the adversarial attack is to create an innocuous classifier that makes decisions based on some unrelated feature. For example, case of credit card applications, the innocuous classifier could make decisions based on either existing unimportant feature such as card number or new feature added to the dataset whose values are randomly sampled. This unrelated feature will be made to appear in place of the sensitive feature in explanations.
The last step the attack construct the adversarial classifier which first applies the OOD-detecting classifier given instance If the OOD-detecting classifier predicts to be in-distribution, the the adversarial classifier outputs the prediction of the biased classifier on æ. x is predicted to be OOD, then the adversarial classifier outputs the prediction of the innocuous classifier on æ.
Clearly, the predictions made by the adversarial classifier on in-distribution instances are biased, as the adversarial classifier simply outputs the biased classifiers prediction. Suppose LIME is used for explaining the prediction made by the adversarial classifier on some in-distribution instance æ. LIME first perturbs However, due to LIME's OOD sampling problem, most of the perturbed samples are OOD and are detected by the OOD-detecting classifier as such. Therefore, the output of the adversarial model the perturbed samples is that of the innocuous classifier. Thus for vast majority of the samples on which LIME's explainer model is trained, the unrelated feature appears as the deciding factor for the adversarial model's prediction, whereas the sensitive feature successfully hidden.
Experimentally, the authors generated explanations for the adversarial model multiple test instances belonging to Recidivism, Communities and Crime and German datasets. They showed that the sensitive features appeared with very low frequency among the top explanations for all the test points, which indicates that the attack was successful.
E.3.2 EXPERIMENTAL SETUP
We hypothesized that for discrete data, instances with low Hamming distance to points in the given dataset should tend to be in-distribution, whereas instances with a high hamming distance should tend to be OOD. Note that the recommended way for using LIME is data which is discretized. LIME itself uses Hamming distance as distance metric for weighting the samples it generates. However, it is unable to specifically sample proportionately from high-weigh regions which leads to a lot of samples with low weights. With CLIME one can, however, use constraints to generate samples that would be weighted highly by LIME. For given Hamming distance h and set of instances S,
23

---

Under review as a conference paper at ICLR 2021
formula df can be constructed such that the the solutions of 6² are exactly those instances that are at most at a distance h from each instance in S. If our hypothesis is correct, the sensitive features should appear the top CLIME explanation of the adversarial classifier for low values of h, while innocuous features should dominate for larger h.
Note that the Hamming distance between two instances doesn't it take into account the degree which the value of a feature in one instance differs from the other. Specifically, for discrete features that are the quantized versions of continuous features, values of adjacent quantiles are clearly 'closer' that those of non-adjacent quantiles. This is also true for natively discrete features like the star rating of a product. One can design metrics smarter than the hamming distance, that also take into account these differences in values and are even more robust against adversarial attacks. In this work however, we focus on the Hamming distance as a proof of concept and leave experimentation with other metrics to future work.
E.4 PRACTICAL CONSIDERATIONS
The tool by (Slack et al. 2020). as of the time of writing this paper, was only able to create an adversarial attack continuous features (for LIME), and did not have the ability train the OOD- detecting classifier on discrete data. For our experiments, we augmented their tool to handle purely discrete data by using LIME'S native perturbation procedure for generating training data for the OOD-detecting classifier. For discrete data, the parameter "perturbation perturbation_muliipieer in their tool plays an important role. Its default value of 30 creates a very imbalanced dataset and the accuracy of the OOD-detector is dramatically affected and it classifies most instances as OOD. We found that a value 2 led to the best test accuracy for the OOD-detector.
With discrete data, we also observed that the efficacy of the adversarial attack on LIME was drastically reduced. The sensitive feature appeared as the 2nd from top explanation almost 100% of the time. Additionally, for attacks that used 2 uncorrelated features, the sensitive feature also appeared as the top explanation with a considerable frequency. However, for attacks that used uncorrelated feature, the top explanation was the uncorrelated feature with almost 100% frequency. Hence in our experiments, we focus on the top explanation ([Slack et al., 2020) considered top 3 explanations) and use only one unrelated feature. For CC and German experiments, we selected the top 12 most important features of the 3 datasets using seikit-learn's 's Random Forest classífier, as there were far too many features in the original datasets (100 for CC and 28 for German). The test accuracy of the Random Forest with 100 estimators was 0.83 and 0.75 for CC and German respectively even after restriction 12 features, down from 0.875 and 0.82, respectively, before removing features.
E.5 RESULTS
The results for the Recidivism dataset were depicted in Figure 4 depicted in Fig. and those for German in Fig. 9 It can be seen that the sensitive feature appears prominently for low hamming distance while the unrelated feature dominates higher for higher distance, which confirms the efficacy of CLIME.
The results for CC dataset
In general, it is harder to craft attacks similar to (Slack et al. 2020 against CLIME explanations, as the sampling procedure is dependent on user-provided constraints and is not fixed like LIME. However, for the current experiment, an adversary could conceivably train the OOD-detector on instances with low hamming distance from the original dataset to specifically foil our method. We tested whether the sensitive feature still appeared in the top CLIME explanation when the OOD- detector was trained in this manner (instead of being trained on LIME generated perturbations). We compare the frequency of seeing the sensitive feature as the top CLIME explanation of the adversarial classifier in the two scenarios in Table 2 While the frequency of seeing the sensitive feature drops as compared to the case when the OOD detector is trained on LIME perturbations. the drop is not very steep and the sensitive feature still figures prominently as the top explanation. This shows that our hamming distance based technique not only able to detect attacks, but also robust against attacks itself.
24

---

Under review as a conference paper at ICLR 2021
Sensirive Featura (RacoPct(Khite)
Pet<id
1st Unrelated Feature
Numill
0.8
Other
C.8
Pct II
Other
Frequency
Frequency
0.6
C.6
0.4
C.4
0.2
0.2
Hamming Distance
Hamming Distance
(a) Adversarial Classifier
(b) Non-Adversarial Classifier
Figure 8: CC Dataset: Top CLIME explanation vs. Hamming Distance
1.0
1.0
Sensitive Feature (Gander!
1st Unrelated Feature (LRPI)
0.8
Frequency
Frequency
0.6
Ortic
LoanDuu
Other
0.0
3
3
Hamming Distance
Hamrinng Distance
(a) Adversarial Classifier
(b) Non-Adversarial Classifier
Figure 9: German Dataset: Top CLIME explanation vs. Hamming Distance
Recidivism
CC
German
OOD detector trained on LIME's samples
0.635
0.32
0.42
OOD detector trained on samples from Hamming-constraine
0.63
0.1
0.42
Table 2: Frequency of sensitive feature in top explanation
25


Reviews:
[{"review_id": "W44OlXSihpN", "reviewer": "AnonReviewer3", "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": "The topic of this paper is highly topical, as it focuses on providing explanations for black-box classifiers. The paper tackles the known issue with out-of-distribution sampling in Ribeiro et al.'s LIME. The approach taken is to introduce the use of Boolean constraints in LIME algorithm, which allows for providing some guarantees on the quality of the explanations.\n\nThe paper is generally well-written and the level of details provided makes it a pleasure to read. However, a bit more details could be provided at places.\n\nRelated work is sufficiently covered in the main text, and more discussion is provided in the appendix. The authors might take a look to a recent work Bjorlund et al. that also tries to remedy the out-of-distribution sampling problem using an approach based on robust regression. \n\n[Sparse robust regression for explaining classifiers\nA Björklund, A Henelius, E Oikarinen, K Kallonen, K Puolamäki\nDS 2019: Discovery Science, 351-366]\n\nThe experimental evaluation (in the main paper) is brief, missing, e.g., much of the details to describe the experimental setting used. Since the approach taken is to use Boolean constraints, it would be relevant to know the effort needed to perform the sampling, i.e., does the runtime of CLIME differ much of to that of LIME. \n\nPros:\n1. Very relevant topic (explanations) and demonstration of the importance and the relevance of the data distribution in explaining black-box classifiers\n2. Analysis and proven guarantees of explanation quality\n3. Generally well written paper and clear scope, with a more detailed descriptions provided in the appendices.\n\nCons:\n1. Rather much of the relevant material is in the appendices \n2. Not enough details of the experimental evaluation provided\n3. The end result (the actual explanations and how a human would understand them) is only very briefly touched\n\nQuestions:\n\nIf I understand correctly, CLIME can still introduce samples that are not necessarily from the distribution of the original data (which might be totally unknown, and the original data would be the only information available), as it seems to me that the difference to LIME is that the samples need to obey the Boolean constraints introduced. Is this correct? \n\nWould this then not mean that the \"correctness\" of the explanation heavily relies on using \"correct\" Boolean constraints in the sampling procedure? Could there be a scenario, where the Boolean constraints used in the sampling process would lead to meaningless results, i.e., the samples used would be outside the data space for the (unknown) distribution of the data?\n\nThe work covers  explanations for (binary) classifiers and the focus is on tabular data. Do you see any (e.g., performance) issues that could affect the usability of CLIME in a more general scenario?\n\t\nWhat is the performance of the sampling algorithm, i.e., how does CLIME compare to LIME when considering the time?\n\nCould you provide more details of the experimental evaluation, i.e., details of the classifiers trained, training / testing dataset splits, performance, will the code be made openly available?\n\nMinor details:  \n\nSome inconsistencies in the algorithms:\nAlg. 1 is missing input (only provided in the main test) which makes the code hard to follow\nAlg. 1 and Alg. 3 both call getSamples, but have different number of arguments\n\nFig. 1 the labels in x-axis are way too small.\n\nMLP undefined in page 7\n\nAlso, page 7, \"that gives 69.1%\" (missing \"accuracy\"?)\n\nPage 7, the sentence \"e.g. if the height of the bar is 0.1 the corresponding feature is mostly top ranked in all explanations.\" is quite unclear, since the smallest values in Fig 1 are roughly 1\n\nCheck the capitalisation in the titles in References (e.g., bayes, dnf, shap, lime, bayesian should not be small caps)", "extra_scores": {}, "extra_text": {}}, {"review_id": "KrhpxuU6iMU", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 presents a method --- CLIME --- to generate constrained explanations using LIME.  The method relies on boolean constraints to dictate the sampling region for LIME. This approach offers a number of advantages.  First, users can compare important features for groups conditioned on different factors. Second, the method adds a level of robustness against adversarial attacks.  The authors demonstrate their approach on a number of data sets and find useful insights conditioning on different features and greater robustness to attacks proposed by Slack et. al.\n\nQuestions + Comments for the authors:\n- The authors consistently reference motivating examples left for the appendix throughout the paper.  These are phrased as important examples are discussed in detail in section 4.1.  Please consider using the space afforded by the revision to introduce these in the main text because this currently affects readability.\n- Is there any empirical verification for the methods provided in 4.2 (i.e. algorithms 2 & 3)? I understand the result is phrased as a theoretical result, but there is a lot of attention devoted to it in the paper and it would be good to evaluate it in practice.  It would be nice to demonstrate the output of this estimate for an example and provide some analysis there (unless I'm missing something?)\n-  The extension of the attacks to only discrete data for LIME is interesting -- making it much more similar to the SHAP attack in some sense because this attack only relies on discrete data. I'm a bit confused about the claim that  the methods help detect adversarial attacks.  If they're using the adversarial classifier from Slack et. al., shouldn't the method in 2b reveal that the underlying classifier is only relying on the Race feature?  Could you clarify how this reveals the method detects the attacks? \n\nOverall, the constrained explanation approach seems pretty useful for conditioning explanations and could be a valuable contribution.  It also seems pretty straightforward to implement on top of lime (not a bad thing) so could be of immediate value.  \n\nWhat I'm most confused about right now is (1) evaluation for section 4.2.  I see this as a useful result because the number of perturbations are a big issue for lime and this could be useful to assess the fidelity of explanation with more confidence + have more guidance if the fidelity is trustworthy. I'd be interested to at least see fidelity plotted against delta for an example or something like this.  Next, I'm struggling to see how this method reveals the Slack et. al. attacks.  As, I said, I'd expect to see a method which is not fooled by them to put race as the most important feature.  I'm currently leaning weak accept because I do see value in the method but would appreciate a small empirical extension to the results in section 4.2 and clarification around how the method reveals adversarial attacks.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7_YceSvrexx", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Summary: This paper proposes a new sampling method for LIME based on user-defined Boolean subspaces. They show that using these subspaces rather than the default sampling settings of LIME can lead to robustness against adversarial attacks and allow users to better undercover bugs and biases in subspaces relevant to the user's task. They additionally propose a new metric for measuring the quality of an explanation.\n\nPros: The authors create a novel link between the explainability literature and Boolean Satisfiability. The proposed methodology is shown to be relevant in several different applications. They propose simple metrics for evaluating the quality of samples and the quality of an explanation.\n\nCons: I don't have a lot of experience with ICLR, but it is not obvious to me that this paper is appropriate for this venue.\n\nNone of the metrics used in the paper seem to be weighted by density/distance to the point being explained, as is done in LIME. Given that the point of LIME is that the function is unlikely to be globally approximable by a linear function, the lack of incorporation of a weighting function seems to make this framework inferior to that of LIME (and in fact, theoretically, the binary subspaces used in this paper are merely a specific instantiation of the flexible weighting function used in LIME, the paper, as opposed to LIME, the software package). I would expect that without such a weighting function, in many cases explanations with similar values of the rho metric may vary widely in their usefulness as local explanations.\n\nThe paper suffers somewhat from relegating all of the examples to the supplementary material. Examples which are important to the points being made should be brought back into the main body of the paper.\n\nCertain relevant works seems to have been missed: Sokol et al. (https://arxiv.org/pdf/1910.13016.pdf) proposed user-specified local surrogate explainers, including allowing users to define their own sampling subspace (but do not propose algorithms for sampling). Zhang et al. (https://arxiv.org/pdf/1904.12991.pdf) show that LIME does not accurately reflect local invariance to globally important variables. \n\nIn the first experiment, without some ground truth knowledge as to what the classifier is doing, it is not obviously useful to point out that the CLIME identifies race as a top feature for females in the recidivism dataset. The setup of Zhang et al. may be preferred, where the ground truth behavior of the classifier is known.\n\nIn the adversarial attack experiment, it is not completely clear what is done: did you use CLIME to generate explanations of the adversarial classifier from Slack et al.? Was the adversarial classifier trained with access to CLIME perturbation functions, or was it trained assuming LIME perturbation functions? This doesn't seem to immediately show superiority over the LIME framework, as at larger Hamming distances the bias is still hidden. I think a more appropriate comparison would allow the adversarial classifier access to the relevant perturbation function and consider accuracy at a variety of neighborhood widths for LIME, as with the Hamming distance.\n\n###post rebuttal###\nI have read the updated version of the paper and still feel that this paper may have errors regarding the flexibility and purpose of LIME. The idea is nice, but the paper and evaluations would benefit from more polishing before publication. I maintain my original score.\n\nMisrepresentation of LIME:\n\nSection 3: LIME does not assume that the sampling neighborhood is the same as the true distribution. It may assume something weaker, such as that the function being explained is fairly smooth in the sampling neighborhood. Note that this can be a feature of LIME and not necessarily a bug: if for example x1 and x2 are fully correlated in the data distribution but the classifier only uses x1, it would be impossible to tell this if sampling only within the data distribution. By sampling outside the data distribution it becomes apparent that the classifier is using x1 only. Also, LIME assumes black box access to the function, so I don't fully understand your statement that \"we generally do not have access to the true labels of instances generated through sampling\". It seems like you may be defining the \"correct\" explanation with respect to the true data distribution, rather than to the classifier. LIME is meant to explain a black-box classifier. If the classifier is wrong, LIME should reveal what the classifier does (that is, the explanation should also be \"wrong\" with respect to the true data). The \"framework capabilities\" is also simply not true: users can define the data point to be explained, as well as their own similarity kernel and/or kernel width.\n\nEvaluation:\n\nIt's not entirely obvious to me how we can be sure that CLIME is producing the \"right\" explanation in C.1, C.2 without knowing the function f. If changing the training set changes the classifier f, then it is correct that the explanation should change. As mentioned above, evaluating whether or not an explanation is \"correct\" should be done with respect to the classifier, not the underlying data distribution. In \"Detecting Adversarial Attacks\", it's not clear from the text whether or not you retrain the adversarial attack with your perturbation function. Further, I suspect that LIME may also be able to identify the sensitive feature for sufficiently small neighborhood sizes when sampling in binary space Z'. It seems like a straw man argument to compare an optimized version of your sampling procedure to the default version of lime.\n\nMinor: Equations 1) and 2), if they are describing the usage in Ribeiro et al., should include a weighting function.\n\nFigure 2 seems not to be explained in the text and would benefit from more description.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "33axQPwNywr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper presents augmentations to the LIME explanation system using logical constraints. Given a black-box classifier f, LIME generates local explanations of an input x by sampling in the neighborhood of x, and learning a linear classifier that matches f in that neighborhood. The paper claims that this procedure is problematic because the samples in the neighborhood of x can be out-of-distribution (OOD), so learning from the OOD samples are not useful. The paper also claims that LIME cannot work in constrained spaces, although this is a similar point to OOD samples. Lastly, the paper claims to certify the estimation quality more quickly  by breaking early if the quality is below a certain threshold.\n\nThe problem of generating explanations is important, and the use of logical constraints to focus the attention of the explanation generation is interesting. However, the contributions of the paper are unclear, and the experimental results were not very exciting.\n\nThe paper seems to present two contributions: 1) generating explanations given a constraint and 2) certifying quality of explanations. But for 1) it seems they are simply calling off-the-shelf tools that sample from a logical constraint. It is unclear to me if there were any deeper insights than that. For 2), their main claim of improvement comes from the assumption that it is okay to terminate early if the estimated fidelity is small. This is not an unreasonable assumption, but the contribution is again unclear -- the paper is simply targeting an easier estimation problem (and existing approaches can probably do much better if they also make this assumption).\n\nSince I didn't notice any deeper technical contributions, I was hoping to be convinced by experimental results. After just reading the introduction, my top concern was -- how realistic is it to generate logical constraints for an input x that you want an explanation for? The intro tried to motivate it as doctors setting constraints on features of a patient, so I was hoping for a real-world motivated scenario for constraining the explanation space in the experiments, and some measure of how the CLIME explanations are better than those of LIME. Unfortunately, the constrained spaces for Recividism doesn't seem to be motivated at all, and I don't see why I should believe that CLIME explanations are better than LIME just based on Fig1.\n\nIf I were to reshape the paper, I would spend much less space on the technical contributions, as the insights are fairly straightforward and can be described very quickly. I think the main concern (that I still think is not addressed) is how realistic / easy it is to expect a practitioner to write down logical constraints before querying explanations for a given input x. I think there is a big leap of faith here, that needs to be addressed experimentally via real-world case studies (e.g. doctor example in the introduction) where logical constraints are very natural to come up with, and that explanations generated using these logical constraints are much better.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present CLIME, a variant of LIME which samples from user-defined subspaces specified by Boolean constraints. One motivation is to address the OOD sampling issue in regular LIME. They introduce a metric to quantify the severity of this issue and demonstrate empirically that CLIME helps to address it. In order to stay close to the data distribution, they use constraints based on Hamming distance to data points. They demonstrate that this approach helps to defend against the recent approach of Slack et al. 2020 to fool LIME explanations.

The paper is close to borderline, though concerns remain about experimental validation and the extent of novel contribution, since the original LIME framework is more flexible than described here and allows a custom distance function. Rev 1 believes that the original LIME framework is sufficient to handle Hamming distance constraints though sampling will be less efficient. To their credit, authors engaged in discussion but this should be further elaborated in a revised version.
Decision: Reject