Probabilistic Linear Explanations
Researchers introduce a unified probabilistic explainability framework using sparse anchored linear models that outperforms LIME and MAPLE on relevance error.
The paper proposes probabilistic explanations based on sparse, anchored linear models applicable to both binary classification and continuous regression. It proves that minimizing relevance error for neural-network models is NP-hard and relates it to a tractable fidelity-error surrogate. Solutions are computed via a mixed integer programming formulation with provably optimal empirical solutions and a polynomial-time iterative hard thresholding algorithm with approximation guarantees. Empirical evaluations show lower relevance error than LIME and MAPLE while satisfying anchoring and sparsity constraints by construction.
- Sparse anchored linear explanations generalize subset-based approaches by capturing feature magnitude and direction
- Relevance-error minimization is NP-hard for neural networks; fidelity error serves as tractable surrogate
- MIP formulation yields provably optimal solutions; IHT algorithm provides approximation guarantees
- Explanations satisfy anchoring and sparsity constraints by construction, beating LIME and MAPLE
Full article214 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.19077