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 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.
Introduction
As machine learning models, particularly deep neural networks, grow in complexity, they increasingly function as "black boxes." While their predictive power is undeniable, the lack of transparency in their decision-making logic poses significant risks in sensitive domains. Local Interpretable Model-Agnostic Explanations (LIME) has emerged as a leading solution to this problem. LIME operates by approximating a complex model locally around a specific prediction using a simpler, interpretable surrogate model, such as linear regression.
Despite its widespread adoption, LIME was originally introduced without a rigorous theoretical foundation. This work provides the first mathematical analysis of LIME, specifically focusing on its behavior in tabular data settings, to determine what the algorithm is truly computing and identify the conditions under which its explanations are reliable.
Methodology
The analysis focuses on Tabular LIME, examining how it handles structured data through a process of discretization and local sampling. To establish a baseline, the authors analyze a scenario where the black-box function ($f$) is linear, testing whether LIME can recover the ground truth in this simplified case.
The theoretical framework involves three key components:
- Discretization: Analyzing how LIME transforms continuous input data into binary "interpretable" features based on quantiles.
- Closed-form Derivation: The derivation of exact mathematical expressions (Theorem 3.1) for the coefficients of LIME’s surrogate linear model.
- Concentration Inequalities: Proving that LIME’s output converges and stabilizes as the number of samples ($n$) increases.
Key Insights and Results
The Gradient Connection
A primary finding is that LIME’s coefficients are mathematically proportional to the partial derivatives (the gradient) of the black-box model. This confirms that, at its core, LIME is designed to identify the features that most significantly influence a model's local decision-making process.
The "Switch-off" Phenomenon and Bandwidth Sensitivity
Perhaps the most critical discovery is LIME's extreme sensitivity to the **bandwidth parameter ($ u$)**. This parameter defines the "locality" of the explanation. The authors demonstrate that a specific "critical value" ($V_{crit}$) for the bandwidth can cause the coefficient of a truly significant feature to drop to zero. This implies that a user could inadvertently obscure a feature's influence through poor hyperparameter tuning.
Empirical Validation
The theoretical findings were validated using both synthetic data and the Boston Housing Dataset. In the synthetic case, LIME successfully identified active features while ignoring irrelevant ones. On the Boston Housing dataset, the surrogate model's coefficients were analyzed for both linear and non-linear models.
Robustness and Accuracy
While LIME is robust to sampling noise—meaning it consistently converges to the same explanation given enough samples—it is not perfectly accurate. Even when explaining a linear black-box, the surrogate model's local error remains bounded away from zero, suggesting that LIME provides qualitative insights rather than exact quantitative reconstructions.
Conclusion and Future Work
This study provides essential theoretical grounding for LIME, confirming its ability to discover meaningful features while highlighting risks associated with parameter sensitivity. Current limitations include the reliance on linearity assumptions for core proofs. Future research should extend this analysis to highly non-linear deep networks, explore the impact of L2 regularization (Ridge Regression), and investigate the behavior of LIME under non-isotropic sampling and alternative distance metrics like cosine distance.
Summary updated