Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Questions + Comments for the authors:
- 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.
- 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?)
-  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? 

Overall, 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.  

What 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.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: 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.

The 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.

Related 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. 

[Sparse robust regression for explaining classifiers
A Björklund, A Henelius, E Oikarinen, K Kallonen, K Puolamäki
DS 2019: Discovery Science, 351-366]

The 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. 

Pros:
1. Very relevant topic (explanations) and demonstration of the importance and the relevance of the data distribution in explaining black-box classifiers
2. Analysis and proven guarantees of explanation quality
3. Generally well written paper and clear scope, with a more detailed descriptions provided in the appendices.

Cons:
1. Rather much of the relevant material is in the appendices 
2. Not enough details of the experimental evaluation provided
3. The end result (the actual explanations and how a human would understand them) is only very briefly touched

Questions:

If 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? 

Would 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?

The 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?
	
What is the performance of the sampling algorithm, i.e., how does CLIME compare to LIME when considering the time?

Could 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?

Minor details:  

Some inconsistencies in the algorithms:
Alg. 1 is missing input (only provided in the main test) which makes the code hard to follow
Alg. 1 and Alg. 3 both call getSamples, but have different number of arguments

Fig. 1 the labels in x-axis are way too small.

MLP undefined in page 7

Also, page 7, "that gives 69.1%" (missing "accuracy"?)

Page 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

Check the capitalisation in the titles in References (e.g., bayes, dnf, shap, lime, bayesian should not be small caps)
review_title: Fixing problems caused by out-of-distribution sampling in LIME explanations using Boolean constraints

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

The 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.

The 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).

Since 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.

If 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.
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Pros: 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.

Cons: 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.

None 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.

The 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.

Certain 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. 

In 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.

In 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.

###post rebuttal###
I 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.

Misrepresentation of LIME:

Section 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.

Evaluation:

It'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.

Minor: Equations 1) and 2), if they are describing the usage in Ribeiro et al., should include a weighting function.

Figure 2 seems not to be explained in the text and would benefit from more description.

review_title: proposes simple metrics and solutions for defining locality in LIME, but lacking in clarity in examples and in relation to previous works

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