CS Paper Radar

Probabilistic Linear Explanations

Frederic Koriche, Jean-Marie Lagniez, Chi Tran

cs.LG cs.AI ·submitted 2026-09-16 17:18 UTC · v1

Abstract

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.

Comment
Under Review

Closest papers

Nearest neighbours by meaning across the whole index.

When Are Concept Bottleneck Model Explanations Faithful and Compact?

cs.LG cs.AIstat.ML ·2026-10-05 ·Stefano Teso, Emanuele Marconato, Steve Azzolin, Antonio Vergari
position similarity 0.76
Abstract

Concept bottleneck models (CBMs) are neural classifiers that allow to explain their decisions via high-level concepts, potentially enabling understanding, steering and debugging. However, their explanations are often derived heuristically. Building on formal explainability, we argue they should also be faithful, i.e., not misreport which concepts actually matter. We show that, for widespread CBM architectures, including recent VLM-based variants, faithful explanations must include all concepts in the bottleneck, compromising interpretability when this is large. This result applies to both heuristic and faithful-by-construction formal explanations. To encourage the existence of compact faithful explanations, we suggest i) modeling concepts probabilistically as binary or categorical random variables (rather than logits), and ii) employing per-concept training-time sparsification via group lasso (rather than regular elastic net). We also extend algorithms from formal explainability to CBMs, and show they outperform natural heuristics in terms of guarantees and explanation size. Overall, our work warns against naive interpretability claims and provides formal conditions and practical strategies for ensuring CBMs are as interpretable as advertised.

0.07

Do Feature Interactions Break Explainability? Provable Explanations for Any-Order Neural Additive Models

cs.LG cs.AIcs.CC ·2026-11-08 ·Idan Refaeli, Yizhak Yisrael Elboher, Guy Katz, Shahaf Bassan
top venue similarity 0.71
Abstract · Accepted at NeurIPS 2026. 36 pages, 2 figures

Post-hoc explanation methods for neural networks are often heuristic and lack provable guarantees. A common alternative to such methods that was studied in recent years is to compute a cardinally-minimal subset of input features that is provably sufficient to determine the model's prediction. For general neural networks, however, finding such explanations is computationally intractable. In contrast, recent work showed that this problem becomes more tractable for a particular family of neural networks, namely neural additive models (NAMs), though standard NAMs are highly restrictive because they exclude feature interactions altogether. In this work, we study the computation of provably minimal and sufficient explanations for neural networks with restricted feature interactions, bridging the gap between fully general neural networks and purely additive models. We first prove that even with constant-order interactions, the problem is $Σ_2^P$-hard, implying that worst-case exponential complexity is unavoidable. We then identify two provably tractable settings: one based on sparsity in the interaction structure and another based on a stronger interaction-aware notion of sufficiency. Under either of these settings, we develop algorithms that compute provable explanations for neural networks with any-order interactions while retaining much of the computational efficiency of additive models. Empirically, we show that these explanations are significantly smaller and faster to obtain than those produced by standard algorithms, while being derived from models that achieve much higher accuracy than standard NAMs. Overall, our results help expand the class of neural networks that admit efficient provable explanations, while clarifying the fundamental role of feature interactions in shaping their complexity.

0.38

Evolving Explanations: Complexity-Adaptive Refinement of Faithful Explanations for Symbolic Regression

cs.LG ·2026-11-02 ·Elisabeth Mayrhuber, Ting Hu, Stephan Winkler
similarity 0.67
Abstract

Natural-language explanations generated by large language models (LLMs) for machine learning models often seem fluent but are not necessarily faithful to the underlying model. We formalize this mismatch as a faithfulness gap and propose a complexity-adaptive refinement framework for symbolic regression that iteratively generates and validates explanations until numerical agreement with the target expression is achieved. The approach follows a two-stage pipeline: an explainer LLM produces textual descriptions at increasing levels of detail, while an independent validator LLM extracts a symbolic expression that is compared against the original model. This process is framed as a discrete search over explanation space, where complexity is minimized subject to a faithfulness constraint. We evaluate the method on real-world and synthetic datasets, with a total of 250 runs across varying model complexities. The explanation refinement loop achieves an overall pass rate of 84.0%, with most explanations converging at low complexity levels and only a small fraction requiring detailed descriptions. Our results demonstrate that faithful explanations can be obtained with minimal necessary complexity by explicitly closing the explanation loop through symbolic validation.

0.13

ProToMEx: Rapid, Interpretable Explanations via Structured Representations

cs.LG cs.AI ·2026-09-02 ·Athina Georgara, Adarsh Valoor, Sarvapali D. Ramchurn
similarity 0.66
Abstract

Existing post-hoc explainers for machine learning classifiers primarily focus on feature attribution, assigning importance scores to individual features. While valuable, this approach struggles to articulate the complex, combinatorial patterns that often drive a model's decision-making process. To overcome this limitation, we introduce ProToMEx, a new paradigm for explainability that leverages Probabilistic Topic Models (PTMs). Our model-agnostic framework learns latent ''topics'' that represent distinct, high-level reasons for a classification, moving beyond simple feature importance to reveal underlying semantic structures. ProToMEx naturally provides both global explanations of a model's overall behaviour and local explanations that can disentangle multiple co-existing reasons for a specific prediction. We demonstrate empirically that ProToMEx not only produces explanations of comparable fidelity to popular methods like SHAP and LIME but also drastically reduces the amortised computational cost of generating local explanations, making it highly suitable for real-time applications. Specifically, we show that ProToMEx is ~30-40x faster than SHAP and LIME over standardised tabular datasets and synthetic datasets.

0.21

On the Limits of Sufficient Explanations

cs.LG ·2026-11-13 ·Klaus Weinbauer, Peter F. Stadler, Thomas Gärtner, Sagar Malhotra
similarity 0.65
Abstract

We formally characterize the conditions under which sufficient explanations exist for classifiers on structured data such as graphs and strings. We focus on post-hoc explainers that select parts of the input as sufficient explanations. An explanation is sufficient if the selected part alone ensures the predicted label. Sufficient explanations have been widely adopted across data modalities, including graphs, strings, and images. However, a unified formal analysis of sufficient explanations remains missing. We bridge this gap with four main contributions: (i) We define a general explanation formalism consisting of an instance space, a classifier, and a select relation. The select relation specifies which potential sub-instances or feature subsets can be selected as explanations from each instance; (ii) We show that the existence of sufficient explainers is fully characterized by the interplay between the classifier and the select relation; (iii) We extend this analysis to practically relevant variants of sufficiency, including probabilistic sufficiency and deletion sufficiency; (iv) Based on the formal analysis, we devise statistics that bound the maximum achievable sufficiency for a given task. We evaluate these statistics on language, protein, and molecular classification datasets and find that full sufficiency is unattainable on most of them. Since these bounds hold for every explainer, they provide a task-level reference against which any explainer's sufficiency can be judged in absolute terms.

0.25

Regional Explanations via Causal Sufficiency and Necessity

cs.LG ·2026-09-16 ·Xuexin Chen, Peng Liang, Zijian Li, Zhiyong Lin, Ruichu Cai
similarity 0.63
Abstract

Model explainability is essential for understanding and trusting machine learning models. Existing explainable AI methods often explain predictions through feature importance, counterfactual explanations, or rules. However, a region-level characterization of when and only when a prediction behavior arises remains less explored. This paper proposes Causal Sufficient and Necessary Regional Explanations (SNRE), a framework that learns an input region $A$ and output region $B$ such that membership in $A$ is both sufficient and necessary for the model output to fall in $B$. Motivated by the classical Probability of Necessity and Sufficiency (PNS), we formulate a region-level PNS measure through stochastic interventions and derive a differentiable finite-sample estimator for optimization. SNRE parameterizes the input-output region pair with explicit and interpretable algebraic region families, together with a learnable feature mask, balancing expressiveness and interpretability. Experiments demonstrate that SNRE learns region pairs with strong sufficiency-necessity performance, robust explanation behavior, and practical utility for model analysis.

0.26

Overlooked and Underutilized: Prototypes are the Missing Piece in Tabular XAI

cs.LG cs.HC ·2026-11-18 ·Jacek Karolczak, Jerzy Stefanowski
publishedposition similarity 0.63
Abstract · Accepted for publication in the Journal of Intelligent Information Systems (Springer Nature)

Explainable AI (XAI) is frequently applied to high-stakes tabular data, yet the field relies heavily on feature attribution methods. While these approaches offer technical transparency, evaluating dozens of isolated features demands excessive cognitive effort from non-expert users. In this paper, we argue that prototypes remain overlooked and underutilized, and should be integrated as a complementary, intuitive gateway to auditing complex machine learning models. Although entire exemplars function as an intuitive baseline for prototype-based explanations, we highlight prototypical parts as particularly valuable for tabular data. By grouping related features into bounded subspaces, prototypical parts technically embody human-understandable concepts, replacing isolated features with cohesive semantic units. We support this integration through two primary lenses. Cognitively, these parts align with Rosch's categorization theory and Kahneman's System 1 thinking to naturally reduce cognitive load for humans. Then, we introduce a Geometric Validity Triad to conceptualize why prototypes validate the data manifold - a critical dimension often neglected by existing methods. We contend that making tabular XAI genuinely comprehensible requires shifting toward composite explanation pipelines that pair intuitive similarity-based reasoning with rigorous feature-level auditing. The paper concludes by outlining open challenges of prototype-based methods and discussing potential solutions to guide future research.

0.20

Realistic Counterfactual Explanations via Denial Constraints

cs.DB ·2026-08-26 ·Avia Asael, Nave Frost, Amir Gilad, Daniel Deutch
top venue similarity 0.62
Abstract

In the realm of Explainable AI, classification results are often explained via counterfactuals (CFs for short), which are (ideally small) perturbations to an instance that lead to a change of classification label. Such CFs may serve as explanations for the prediction, pinpointing the features that were important. Existing explainability solutions typically aim at minimizing the distance of CFs from the original instance so that they are specific to it, and/or maximizing the diversity of CFs to cover multiple facets of the reasons underlying the prediction. In this paper, we note that in pursuing these aims, state-of-the-art explainability solutions may (and often do) yield counterfactual explanations that do not correspond to realistic instances. This limits their applicability and usefulness in practice. To remedy this, we combine ideas from Explainable AI with ideas from data management. Specifically, we capture realism of CFs via logical constraints that hold with respect to a dataset of examples (e.g., training set); the class of such constraints that we focus on is that of denial constraints, extensively studied in the context of relational databases. Algorithmically, we then combine explainable AI solutions to yield CFs, with ideas from data cleaning that we adapt to this unique setting, to transform CFs into realistic ones. Extensive experiments across four datasets validate that our solutions achieve realism with relatively minor compromise in terms of distance and diversity. They further validate that the dedicated optimizations that we have developed to speed up the search for CFs are indeed highly effective.

0.43