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):
- Too Small: The sampling becomes noisy, leading to high variance and unstable explanations.
- 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.
- Initial Probing: Sample a small number of points around the input and query the black-box model.
- 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.
- 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.
- 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.
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.
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