PaperlayerView exact revision on arXiv

Source-linked AI summary

Explaining the Explainer: A First Theoretical Analysis of LIME

Damien Garreau, Ulrike von Luxburg

arXiv:2001.03447v2cs.LGstat.ML

TL;DR

Complicated machine-learning models can act as black boxes, motivating theoretical analysis of interpretability methods such as LIME. This paper analyzes LIME through a weighted least-squares formulation and finds that its coefficients can reflect meaningful features, while parameter choices may cause important features to be missed.

  • Problem

    Complicated machine-learning models are often perceived as black boxes, creating a need to understand how they make individual predictions.

  • Method

    The analysis realizes the interpretable coefficients as the solution of a weighted least-squares problem and studies their theoretical behavior.

  • Results

    LIME coefficients are approximately proportional to the function's partial derivatives, while the surrogate model may miss important features and lack faithfulness.

  • Takeaways & Limitations

    In the analyzed setting, LIME can identify meaningful features without adding erroneous dependencies, but its interpretations remain sensitive to parameter choices.

  • Takeaways & Limitations

    The theoretical analysis faces a substantial hurdle from the discretization process that converts sampled points into discrete representations.

Abstract

from arXiv · show

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 pressing need. One popular algorithm to provide interpretability is LIME (Local Interpretable Model-Agnostic Explanation). In this paper, we provide the first theoretical analysis of LIME. We derive closed-form expressions for the coefficients of the interpretable model when the function to explain is linear. The good news is that these coefficients are proportional to the gradient of the function to explain: LIME indeed discovers meaningful features. However, our analysis also reveals that poor choices of parameters can lead LIME to miss important features.

1 Introduction

LIME addresses the opacity of complex black-box models by producing local explanations for individual predictions. This paper gives the first theoretical analysis of TabularLIME, finding both meaningful feature identification and parameter-dependent failures.

  • Motivation: Complex models such as Inception can achieve strong performance while remaining difficult to understand for individual predictions.Inception is described as depending on approximately 23 million parameters.
  • Motivation: Opacity can cause catastrophic errors and hinder social acceptance when models rely on artifacts rather than task-relevant features.The paper uses safety systems recognizing cars as an example.
  • LIME: LIME provides model-agnostic, local explanations by sampling around an instance and fitting a simple interpretable surrogate model.The method focuses on explaining a specific decision rather than modeling the black box globally.
  • Contributions: For linear functions, the paper computes closed-form average coefficients for TabularLIME's surrogate linear model.The analysis is based on the Euclidean, tabular version of LIME.
  • Contributions: The coefficients are proportional to the black-box model's partial derivatives, so TabularLIME highlights important features.This establishes meaningful feature identification in the analyzed setting.
  • Contributions: Changing a method parameter can make important features disappear, while the surrogate model's local error is bounded away from zero in general.The paper reports that these theoretical results are verified by simulations.

2 LIME: Outline and notation

TabularLIME explains a prediction at an instance by sampling nearby data, discretizing features, encoding local agreement, weighting samples by proximity, and fitting weighted least squares. Its implementation choices shape both interpretability and theoretical behavior.

  • 2.1 Intuition: TabularLIME explains a black-box prediction at one instance by sampling examples near that instance and fitting a local interpretable model.A global interpretable fit is unsuitable when the black-box function is too complex.
  • 2.1 Intuition: It discretizes each feature into quantile bins, creating categorical representations that are easier to interpret than the original coordinates.For each feature, an interpretable indicator records whether a sample shares the instance's bin.
  • 2.1 Intuition: The sampled examples are converted into binary interpretable features and used with proximity weights in a weighted least-squares surrogate.Algorithm 1 returns the fitted coefficient vector.
  • 2.1 Intuition: New samples are generated by uniformly sampling bin encodings and then drawing coordinates from truncated Gaussian distributions within the selected bins.This procedure explores values of the function throughout the neighborhood of the instance.
  • 2.2 Implementation choices and notation: TabularLIME is a flexible framework whose choices include discretization, sampling, distance weighting, and regression settings.The paper studies one implementation and notes that users retain freedom across algorithmic components.
  • 2.2 Implementation choices and notation: Using a very small locality parameter can give positive weight only to the instance's immediate neighborhood, producing an effectively constant fit that misses relevant information.The paper also identifies discretization as a major hurdle for theoretical analysis.

3 Theoretical value of the coefficients of the surrogate model

For a linear underlying model, the paper derives theoretical average coefficients for TabularLIME's surrogate model and relates them to the model's partial derivatives. The local surrogate's prediction and error are controlled with high probability under the theorem's assumptions.

  • TabularLIME's average surrogate coefficients are derived in closed form when the underlying model is linear.The exact proportionality coefficients depend on scaling parameters and the quantiles surrounding the instance being explained.
  • The coefficients are approximately proportional to the black-box model's partial derivatives at the instance ξ.This relationship holds with constants determined by the paper's assumptions.
  • With probability greater than 1 − η, the theorem guarantees the stated coefficient relationship under its linear-model assumptions.A precise version includes dependencies on dimension and hidden constants in the appendix.
  • Because ξ is encoded as (1, 1, …, 1)^J, the local model's prediction at ξ equals the sum of its surrogate coefficients.The theorem therefore also yields a high-probability statement about the surrogate prediction error through Corollary 3.1.
  • The local surrogate is intended to provide interpretability rather than maximum predictive accuracy, so its error can indicate how reliable the interpretation may be.This frames local-model error as an interpretive reliability hint rather than the primary optimization target.

4 Consequences of our main results

TabularLIME’s coefficients are theoretically tied to local derivatives and empirically show robustness, but bandwidth choices can suppress important features. The surrogate can also incur nonzero local error, and the theorem relies on restrictive assumptions.

  • Dependency in the partial derivatives: TabularLIME coefficients are approximately proportional to the black-box model’s partial derivatives, yielding zero coefficients for uninfluential features in a simple linear example.For f(x) = 10x_1 − 10x_2, β_1 ≈ 11.4, β_2 ≈ −4.1, and β_j = 0 for j ≥ 3.
  • Robustness of the explanations: With enough samples, TabularLIME’s coefficients remain close to explicitly computable theoretical values with high probability, suggesting robustness across runs.The paper illustrates this behavior using repeated experiments on the Boston housing dataset.
  • Influence of the bandwidth: The bandwidth ν has no theoretically founded selection rule and affects both the scale of coefficients and whether features remain active.At ν = 0.53, TabularLIME switches off the second feature while retaining a nonzero coefficient for the first; small bandwidth changes can alter coefficient magnitudes.
  • Influence of the bandwidth: The magnitudes of surrogate coefficients should not be interpreted too literally because equal-magnitude partial derivatives can produce substantially different coefficients.In Figure 4, the first two partial derivatives have equal magnitude, but the first interpretable coefficient is much larger.
  • Error of the surrogate model: Unless cancellation occurs, the surrogate model’s local error is bounded away from zero, so TabularLIME is not accurate in general.The paper demonstrates this behavior experimentally with repeated error measurements.
  • Linearity of f: The theoretical analysis assumes linearity, although the authors argue its locality may permit extensions to functions with controlled curvature near the explained instance.The paper reports rough agreement between theory and experiments for a nonlinear kernel ridge regressor.

5 Proof of Theorem 3.1

The proof treats TabularLIME's surrogate coefficients as a weighted least-squares solution and shows they concentrate around explicitly computable population values. Gaussian sampling and bounded features enable closed-form covariance calculations and concentration control, despite nonlinear discretized features.

  • TabularLIME's surrogate coefficients solve a weighted least-squares problem, yielding the key equation for the analysis.
  • Covariance and right-hand side: The empirical covariance and right-hand-side matrices are compared with their population counterparts to establish closeness of the estimated coefficients.Assuming the population covariance is invertible, the coefficients approach β = Σ^-1Γ.
  • Concentration analysis: Gaussian sampling makes the difficult integrals from nonlinear features tractable, although the resulting calculations are heavy.
  • Covariance and right-hand side: The proof computes the population covariance in closed form, with a scaling constant that cancels from the final result.
  • Concentration analysis: Concentration inequalities control the empirical quantities because Gaussian samples and binary features are bounded.
  • Conclusion of the proof: The final coefficient expression is obtained by multiplying the inverse population covariance by the population right-hand side.

6 Conclusion and future directions

The paper's theoretical analysis finds that LIME can identify meaningful features but can also omit important ones and produce an unfaithful surrogate. The authors verify these theoretical results with simulations and propose broader extensions.

  • The analysis provides the first theoretical study of LIME, finding both meaningful feature discovery and possible loss of important features.
  • The surrogate model is not faithful, and poor parameter choices can make important features disappear from the interpretation.
  • All theoretical results are verified by simulations.
  • Future work aims to extend the proof to arbitrary functions using a Taylor expansion at ξ.
  • Other planned extensions include alternative distance functions, non-isotropic sampling, and ridge regression.

Analysis of LIME

The supplementary material proves Theorem 3.1 through a sequence of analyses that mirror the main paper's structure, with technical Gaussian-integral and concentration results collected separately.

  • The supplement proves Theorem 3.1 as a simplified version of Theorem 10.1.
  • Its proof sequence recalls the setting, analyzes the covariance matrix, studies the key equation's right-hand side, and proves Theorem 10.1.
  • Technical results, mainly Gaussian-integral computations and external concentration results, are collected in a separate section.

7 Setting

The theorem is established under a linear black-box model and Gaussian sampling assumptions, with specified weighting and feature coefficients. The analysis also introduces scaling and quantile-based quantities tied to the sampling construction.

  • Assumptions: The black-box model is assumed linear: f(x) = a^T x + b, with fixed a and b.
  • Assumptions: The sampled points x1, ..., xn are assumed to be independent and identically distributed Gaussian variables.
  • Weights and scaling: The setting specifies weights for each sampled example and introduces a scaling constant that does not affect the final result.
  • Quantile coefficients: The coefficients used in the analysis are defined through quantile boundaries of the instance ξ's coordinates.

8 Covariance matrix

This section derives the expected and empirical covariance matrices of LIME’s new coordinates, then establishes conditions for inversion and concentration. These controls enable precise statements about the surrogate coefficients.

  • Expected covariance matrix: The expected covariance matrix is computed in closed form from three quantities: E[π_i], E[π_i z_ik], and E[π_i z_ik z_iℓ].The coordinate-wise calculations use Gaussian integrals, independence, and the scaling constant C_d.
  • Inverse covariance matrix: Σ is invertible when every α_j differs from 0 and 1, with an explicit inverse obtained through block-matrix inversion.The Schur complement reduces to a diagonal matrix with entries α_j(1 − α_j).
  • Inverse covariance matrix: The inverse covariance operator norm is bounded using A_d := max_j 1/[α_j(1−α_j)].The paper notes that sharper bounds may follow from analyzing the associated arrowhead matrix.
  • Empirical covariance: The empirical covariance matrix concentrates around Σ because its entries are bounded and independent across examples, allowing Hoeffding’s inequality and a union bound.The resulting probability bound includes the factor 4d^2 exp(−2nt^2).
  • Empirical covariance: Proposition 8.1 provides the key high-probability control needed to invert the empirical version of Eq. (5.1) and obtain precise coefficient bounds.The analysis treats d, C_d, and A_d as essentially numerical constants while studying large n.

9 Right-hand side of Eq. (5.1)

This section computes the expected right-hand side Γ of Eq. (5.1) and proves its concentration under the paper’s Gaussian and linearity assumptions. These results provide the second ingredient for controlling the surrogate coefficients.

  • Computation of Γ: The expected vector Γ is computed by evaluating E[π_i f(x_i)] and E[π_i z_ij f(x_i)].The derivation uses linearity, Gaussian-coordinate independence, and separate cases for matching and nonmatching indices.
  • Computation of Γ: The calculations express Γ through the coefficients α_j and signed quantities θ_j associated with the transformed coordinates.The paper obtains these terms by applying Gaussian-integral lemmas to the coordinate-wise factors.
  • Concentration of Γ: Under Assumptions 1 and 2, Lemma 9.3 establishes a concentration bound for the empirical right-hand side Γ̂.The proof combines sub-Gaussian control for weighted linear terms with boundedness of the binary transformed coordinates.

10 Proof of the main result

The main proof combines concentration of the empirical covariance matrix with concentration of Γ to control the estimated surrogate coefficients. The resulting theorem holds with probability at least 1 − η.

  • Main theorem: Theorem 10.1 gives a high-probability concentration result for the surrogate coefficient vector β̂.It is presented as a more precise version of the main paper’s Theorem 3.1.
  • Proof strategy: The proof decomposes β̂ − β into errors from empirical covariance inversion and from estimating Γ.These two terms are controlled using the results of Sections 8 and 9.
  • Proof strategy: The argument constructs three high-probability events controlling covariance inversion, Γ estimation, and the resulting coefficient error.A union bound combines the events into a final event with probability greater than 1 − η.

11 Technical lemmas

This section collects Gaussian-integral and concentration lemmas used in the proofs. The technical results support the linear analysis and indicate how the calculations could extend to quadratic functions.

  • Gaussian integrals: The appendix provides zero-th, first-, and second-order Gaussian-integral formulas for the proof calculations.These formulas are used to evaluate expectations involving the Gaussian inputs and LIME weights.
  • Gaussian integrals: Because f is assumed linear, the main analysis requires first-order Gaussian-integral computations.The second-order lemma is included for possible extensions involving quadratic terms.
  • Concentration inequalities: The technical concentration tools include Hoeffding’s inequality for bounded independent variables and its sub-Gaussian version.These results are applied to empirical covariance and right-hand-side terms.
Loading 2001.03447v2…