Explaining the Explainer: A First Theoretical Analysis of LIME

Damien Garreau, Ulrike von Luxburg

Abstract

Machine learning is increasingly deployed in sensitive applications, often replacing humans in critical decision-making processes. Consequently, the interpretability of these algorithms has become a pressing concern. While Local Interpretable Model-Agnostic Explanations (LIME) is a widely used tool for interpreting black-box models, it has historically lacked a rigorous mathematical foundation. This paper provides the first theoretical analysis of LIME, proving that its explanations are proportional to the model's local gradient while identifying critical sensitivities in its hyperparameter settings.

Introduction

As machine learning models—particularly deep neural networks—grow in complexity, they increasingly function as "black boxes." We observe inputs and outputs, but the underlying logic remains opaque. This lack of transparency is a significant barrier in high-stakes domains such as medicine, law, and autonomous driving.

LIME was introduced in 2016 to address this by fitting a simple, interpretable surrogate model (typically linear regression) to local perturbations of a specific data point. Despite its popularity, LIME was largely heuristic. Users lacked certainty regarding whether the "important features" identified were mathematically sound or merely artifacts of algorithmic settings. This research establishes the mathematical "proof of work" for LIME.

Methodology

The study focuses on Tabular LIME, the variant designed for structured data. To ensure mathematical tractability, the authors analyze the algorithm's behavior when the black-box function is linear, allowing for the derivation of closed-form expressions for LIME’s coefficients.

The analysis decomposes LIME into four distinct mathematical stages:

  1. Discretization: Converting continuous data into binary "bins" based on training set quantiles.
  2. Sampling: Generating synthetic data points in the vicinity of the instance being explained.
  3. Weighting: Applying an exponential kernel with bandwidth $\nu$ to prioritize samples closer to the original point.
  4. Linear Regression: Fitting the weighted surrogate model to generate the final explanation.
Conceptual diagram of LIME's local surrogate modeling process, illustrating the relationship between the black-box function f, sampled points, and quantiles.

By employing concentration inequalities, the authors demonstrate how LIME’s empirical coefficients converge to a theoretical mean as the sample size increases.

Key Insights

  • The Gradient Connection: The analysis confirms that LIME is mathematically grounded; the coefficients it produces are proportional to the partial derivatives (the gradient) of the black-box model. This validates that LIME identifies meaningful local features.
  • The "Switch-Off" Phenomenon: A critical finding is LIME's extreme sensitivity to the bandwidth parameter ($\nu$). The authors discovered that minor adjustments to this parameter can cause the coefficient of a highly influential feature to drop to zero, effectively "forgetting" important information due to poor parameter selection.
  • Surrogate Accuracy vs. Interpretability: The surrogate model often fails to perfectly emulate the local function value. However, the authors argue this is acceptable, as LIME’s primary objective is interpretability (indicating the direction of model influence) rather than perfect local emulation.
  • Robustness: The study indicates that with a sufficient number of samples ($n$), LIME provides robust explanations that remain consistent across different runs for the same data point.

Empirical Results

The theoretical findings were validated using both synthetic and real-world datasets, including the Boston Housing Dataset and controlled linear environments.

  • Theorem 3.1: The authors provide the first explicit formula for LIME coefficients, detailing their dependence on data distribution and hyperparameters.
  • Feature Identification: In synthetic tests involving a 10-dimensional space, LIME successfully identified the two active features. The experimental results closely aligned with the authors' theoretical predictions, demonstrating the algorithm's ability to isolate signal from noise when properly configured.
Empirical validation showing LIME coefficients for a 10-dimensional synthetic test, where the model correctly identifies the two active features (1 and 2).

Limitations and Future Work

While this work provides a foundational proof, it primarily assumes a linear black-box model. Although experimental evidence suggests these findings extend to non-linear models via Taylor expansion, a rigorous proof for complex deep networks is still required. Furthermore, the paper highlights the difficulty of tuning the bandwidth $\nu$ but does not yet offer an automated optimization method. Future research will also need to extend these theoretical guarantees to image and text data, which utilize different distance metrics and segmentation techniques.

Summary updated

Abstract

Machine learning is used more and more often for sensitive applications, sometimes replacing humans in critical decision-making processes. As such, interpretability of these algorithms is a pressin...
BibTeX
@inproceedings{garreau2020explaining,
  author = {Damien Garreau and Ulrike von Luxburg},
  title = {{Explaining the Explainer: A First Theoretical Analysis of LIME}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=z4Ha6ck6sTr},
}
Figure