Is this the Right Neighborhood? Accurate and Query Efficient Model Agnostic Explanations

Amit Dhurandhar, Karthikeyan Natesan Ramamurthy, Karthikeyan ShanmugamNeurIPS 2022 · OpenReview

TL;DR

Local explanation methods like LIME often fail because they rely on a "neighborhood" size that is notoriously difficult to tune: too small, and the explanation is unstable; too large, and it becomes inaccurate. This paper introduces Adaptive Neighborhood Sampling (ANS), a method that identifies the actual local linear region of a black-box model. By doing so, ANS produces explanations that are more faithful, stable across different scales, and significantly more query-efficient.

The "Goldilocks" Problem of Kernel Width

To explain a complex "black-box" model (like a deep neural network), researchers often use local surrogate models. The core logic behind popular tools like LIME is simple: take a specific input, perturb it slightly to see how the output changes, and fit a simple linear model to those perturbations.

However, these methods suffer from a severe tuning problem regarding the kernel width (the radius of the neighborhood being sampled):

  1. Too Small: The sampling becomes noisy, leading to high variance and unstable explanations.
  2. Too Large: The neighborhood captures the model's non-linearities. A linear model cannot accurately represent a curved decision boundary, leading to "unfaithful" explanations.

The authors argue that instead of guessing a fixed radius, we should find the "right neighborhood"—the specific region where the black-box model actually behaves linearly.

Adaptive Neighborhood Sampling (ANS)

The authors propose ANS, an approach that leverages the fact that many modern AI models (like those using ReLU activations) are technically piecewise linear.

  1. Initial Probing: Sample a small number of points around the input and query the black-box model.
  2. Region Estimation: Use Multidimensional Piecewise Linear Segmented Regression (MPLSR) on these initial samples to estimate the boundaries of the linear "piece" the input resides in.
  3. Adaptive Sampling: Instead of sampling blindly, ANS uses an uncertainty parameter. If the boundary estimate is uncertain, it samples conservatively near the input. If certain, it samples broadly within the identified linear region.
  4. Explanation Fitting: Finally, it fits a sparse linear model (like Lasso) using only the samples that fall within the identified linear region.

The paper distinguishes between ANS-Basic (a naive implementation that discards out-of-bounds samples) and ANS (which uses the adaptive distribution to improve query efficiency).

Key Results

The authors evaluated their approach on tabular data (IRIS, HELOC) and image data (CIFAR10 using a ResNet-18).

Superior Stability and Lower Infidelity

A key contribution is the focus on stability. If an explanation for the same data point changes drastically just because you changed the sampling radius, the explanation is unreliable. ANS consistently achieved lower infidelity (INFD)—a measure of how well the explanation matches the black-box—compared to LIME, S-LIME, and MeLIME.

Infidelity across different kernel width multipliers

As the kernel width multiplier increases, traditional methods like LIME and S-LIME see a degradation in performance (higher INFD). In contrast, ANS and ANS-Basic remain remarkably flat, proving their robustness to neighborhood scaling.

Qualitative Clarity

On CIFAR10, ANS produced much cleaner and more consistent saliency maps.

Qualitative comparison of explanations on a CIFAR10 horse image

When explaining a "horse" classification, ANS consistently highlighted the horse's face across different kernel width multipliers (kwm). Meanwhile, methods like LIME and MeLIME produced noisy highlights that shifted dramatically as the kernel width changed.

Query Efficiency

In production environments, querying a massive black-box model is expensive in terms of latency and compute. ANS is highly "query efficient" because it focuses its budget on the regions that actually help define the local linear behavior, requiring fewer overall queries to reach a faithful explanation.

Limitations and Future Work

  • Computational Overhead: While ANS reduces the number of queries to the black-box model, running MPLSR internally adds local computational cost. However, this is often a favorable trade-off for deep models where inference is the primary bottleneck.
  • Curvature vs. Linearity: The method assumes the model is approximately piecewise linear. For models with high local curvature, piecewise polynomial regression might be a necessary future direction.
  • Boundary Proximity: If a data point is extremely close to a decision boundary, the uncertainty in estimating the range increases, which can revert the sampling behavior back toward standard Gaussian sampling.

Summary updated

Abstract

There have been multiple works that try to ascertain explanations for decisions of black box models on particular inputs by perturbing the input or by sampling around it, creating a neighborhood and then fitting a sparse (linear) model (e.g. LIME). Many of these methods are unstable and so more recent work tries to find stable or robust alternatives. However, stable solutions may not accurately represent the behavior of the model around the input. Thus, the question we ask in this paper is are we approximating the local boundary around the input accurately? In particular, are we sampling the right neighborhood so that a linear approximation of the black box is faithful to its true behavior around that input given that the black box can be highly non-linear (viz. deep relu network with many linear pieces). It is difficult to know the correct neighborhood width (or radius) as too small a width can lead to a bad condition number of the inverse covariance matrix of function fitting procedures resulting in unstable predictions, while too large a width may lead to accounting for multiple linear pieces and consequently a poor local approximation. We in this paper propose a simple approach that is robust across neighborhood widths in recovering faithful local explanations. In addition to a naive implementation of our approach which can still be accurate, we propose a novel adaptive neighborhood sampling scheme (ANS) that we formally show can be much more sample and query efficient. We then empirically evaluate our approach on real data where our explanations are significantly more sample and query efficient than the competitors, while also being faithful and stable across different widths.
BibTeX
@inproceedings{dhurandhar2022is,
  author = {Amit Dhurandhar and Karthikeyan Natesan Ramamurthy and Karthikeyan Shanmugam},
  title = {{Is this the Right Neighborhood? Accurate and Query Efficient Model Agnostic Explanations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=aFJkRjKV1O},
}
Figure