# Probabilistic Linear Explanations

arXiv: https://arxiv.org/abs/2609.19077 · HTML: https://mlsanity.com/paper/2609.19077/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 59 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Builds on (most cited first, 24 of 24)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [On the Robustness of Interpretability Methods](https://mlsanity.com/paper/1806.08049/) (2018)
- [A Survey on the Explainability of Supervised Machine Learning](https://mlsanity.com/paper/2011.07876/) (2020)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks](https://mlsanity.com/paper/2006.07322/) (2020)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [Model Agnostic Supervised Local Explanations](https://mlsanity.com/paper/1807.02910/) (2018)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [How do Humans Understand Explanations from Machine Learning Systems? An Evaluation of the Human-Interpretability of Explanation](https://mlsanity.com/paper/1802.00682/) (2018)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [BayLIME: Bayesian Local Interpretable Model-Agnostic Explanations](https://mlsanity.com/paper/2012.03058/) (2020)
- [Towards the Unification and Robustness of Perturbation and Gradient Based Explanations](https://mlsanity.com/paper/2102.10618/) (2021)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Lower bounds over Boolean inputs for deep neural networks with ReLU gates](https://mlsanity.com/paper/1711.03073/) (2017)
- [A Learning Theoretic Perspective on Local Explainability](https://mlsanity.com/paper/2011.01205/) (2020)
- [Inapproximability of sufficient reasons for decision trees](https://mlsanity.com/paper/2304.02781/) (2023)
- [Learning Model Agnostic Explanations via Constraint Programming](https://mlsanity.com/paper/2411.08478/) (2024)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)

## Abstract (arXiv)

Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget k. We show that minimizing the relevance error for such explanations is ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any k-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.