Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper is on improving explainability techniques for machine learning models. A popular technique is based on local linear models that make a locally linear approximation of the ML model around a provided input example for which an explanation is sought. Local linear approximations make use of random samples from around the provided input example to estimate the linear model. However, having samples too close to the input can affect the condition number of the covariance matrix, while on the other hand having the samples spread out too much can lead to an unfaithful model. 

This paper proposes a strategy that chooses the samples in an adaptive manner to ensure that the samples span the locally linear region of the model, leading to a more reliable model. Experimental evaluation shows better performance compared to other locally related baselines. 
strengths_and_weaknesses: **Strengths**:

The proposed method samples points adaptively thus not requiring to set a sampling variance.
The method also takes into account the uncertainty of the estimated values a_n, b_n for improved robustness. Experimental evaluation shows that it leads to a better performance w.r.t. to a variety of performance metrics.

**Weaknesses**:
I do not work in explainability for ML, however it seems that the contribution is a minor improvement (the sampling strategy) over existing approaches. As such, the approach is not so novel, in my opinion, even though experimentally it is beneficial.
questions: NA
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Many local explanation methods have been developed for explaining black box models in a post hoc fashion. These methods first sample around the example to be explained and build a linear model using the samples to form an explanation. However, the challenge in these schemes is that we do not know if we are sampling the right neighborhood around the example. If the neighbourhood is too small, the linear fitting can be unstable due to a bad condition number and if the neighborhood is too large, the function that these methods approximate may not be linear. This work provides an adaptive sampling procedure where they first estimate the linear region around the example using a few samples and then sample within that region only taking into account the uncertainty of the estimate. This work then shows using experiments on a few tabular datasets, that their procedure is much more query efficient and sample efficient and leads to stable predictions across multiple widths of sampling.  
strengths_and_weaknesses: The method proposed in this work seems like a very natural and simple idea which gives improvement over the existing methods. The explanations are stable over different widths which is what was desired. 

One weakness is that this method is slower because the method involves running MPSLR schemes and the accuracy of the method depends a lot on the correctness of MPSLR methods. The method is also somewhat complicated to implement and involves choosing multiple hyper parameters like n, \alpha. 

The paper is generally well written and clear. 

There could be more discussion on the related work. It would be nice if there were more details on how different methods achieve stability in their methods. Also, stability and faithfulness have been mentioned multiple times but it is not clearly defined anywhere what do the authors mean by that. I am guessing stability is defined as the change in explanations as the sampling width increases. But, in any case, these terms should be clearly explained in the beginning.
questions: The related work section does not mention any previous work which also does adaptive sampling of the neighborhood, I wanted to clarify if this is the first work which does the adaptive sampling of the neighborhood. 

The stability with respect to kernel widths is shown in the figures in the appendix. I see that Melime is also quite stable across different widths. Can the authors please comment a little more on the Melime method?

I also want to clarify if the metrics shown in the graphs are averaged over all test examples.
limitations: The authors have adequately discussed the limitations of their work. They have showed that their explanations are much more stable across different sampling widths but as pointed out by the them, there is no way to check if the explanations are more accurate. Moreover, the correctness of their method depends on MPLSR schemes and if the range of the linear segment is found to be incorrect in these schemes, the quality of explanations may degrade. They have also pointed out that their methods is slower as compared to the vanilla methods and have also given a dataset example where their performance is weaker than the vanilla methods.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a rejection sampling method for neighborhood-based explanation methods including LIME. It argues that existing neighborhood-based explanation models are quite unstable in terms of the the neighborhood width, which is the boundary range for the local neighborhood and the mean value of a Gaussian distribution where the local neighborhood follows. In order to make the choice of neighborhood width insensitive, it first samples several data points (n) to compute the range $[a_n, b_n]$ and an uncertainty score $\alpha$ to adaptively learn the neighborhood distribution from $N(\mu, \sigma I)$ to $N(\alpha \mu + (1-\alpha)\frac{a_n + b_n}{2}, \sigma I)$. Then the LIME algorithm is applied for fitting an interpretable explainable model. It also analyses the sample efficiency and query efficiency compared to a naive version, showing that the method is query/sample-efficient.  
strengths_and_weaknesses: - Strengths
    - The proposed method is intuitive and relatively clearly explained.
    - The experiment shows that the method is simple and effective.
    - Efficiency analysis is covered in terms of sampling, query and training MPLSR.
- Weakness
    - The experiments are limited to small-scale datasets.


questions: - It would be nice if the variance can be provided in Figure 2 to show the performance of the proposed method is stably outperforming other methods.

limitations: The limitation is not discussed in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a technique called adaptive neighborhood sampling scheme (ANS) to make local explanations more faithful, stable, and sample query efficient. ANS is built on multidimensional piecewise linear segmented regression (MPLSR) to indentify boundaries of each linear piece.
strengths_and_weaknesses: Pros:

(1) The motivation is clear and the method to use MPLSR is solid to identify linear pieces. 

(2) Experimental results show the better fidelity and sample efficiency of the proposed methods.

Cons:

(1) I think this paper needs to give a formal definition of "stability" and "faithfulness".

(2) It would be easier for readers to understand the metrics if the author can explicitly indicate for each metric whether it is higher the better or lower the better.

(3) According to figure 2, for HELOC dataset, it seems that ANS-Basic and ANS are worse than the baselines wrt GI and CI. Also for CIFAR-10, a comparison to LIME is missing. 
questions: (1) for Cifar10, how do you sample neighbors? in input image space or feature space?
limitations: (1) It would be better if the author can provide some qualitative examples on the Tabular datasets.
review_title: null

Meta-review: metareview: The paper attacks the problem of how to define "local" when generating local linear explanations (e.g. LIME).  Forming the linear approximation using multiple points, the proposed method attempts to balance robustness of the explanation vs its specificity.  The approach of using multidimensional piecewise linear segmented regression is sensible for this end, albeit if increasing runtime.  The majority of reviewers had a favorable opinion of the work, recognizing the paper's contribution as targeted but important, given the popularity of local linear explanations.  Even reviewer hHAF, who recommended rejection, recognized the work's practical benefit ("experimentally it is beneficial").  Thus, I recommend acceptance.
confidence: Less certain
Decision: Accept