Probabilistic Linear Explanations
Frederic Koriche, Jean-Marie Lagniez, Chi Tran
cs.LG · cs.AI
Quick verdict
Probabilistic XAI via sparse anchored linear explanations: NPPP-hardness, relevance-fidelity bounds, MIP+IHT solvers; rigorous, honest, and empirically convincing.
Summary
The paper unifies probabilistic (quasi-abductive) explanations and linear surrogates by defining explanations as k-sparse weight vectors over the Boolean hypercube satisfying an anchoring constraint w·x = f(x), strictly generalizing subset-based explanations by encoding contribution magnitude and sign, including compensatory effects. Minimizing the relevance error — the conditional expected loss given w·z = w·x — is shown NPPP-hard for ReLU networks via a reduction from E-MAJ-SAT using parity shielding to neutralize unanchored subcubes. For a Mallows-type family of local distributions D_{x,σ}, relevance error is bounded by (1+e^{-σ})^k times the unconditional fidelity error, motivating a sampled sparse-regression problem solved exactly by an SOS/Big-M MIP (sample complexity polynomial in k and log d, independent of σ) and approximately by a new IHT variant whose exact projection onto the sparsity-anchoring intersection yields an explicit (1+81k·cosh²(σ/2)) approximation factor at cosh⁴(σ/2) sample cost. On 16 OpenML benchmarks with MLP black boxes, both methods satisfy sparsity and anchoring by construction and beat LIME on relevance on 15 of 16 tasks (median 1.3×, up to 6× on Credit Approval); LIME's fidelity advantage is shown to be an anchoring artifact (r=0.92). Main limitations: worst-case constants are vacuous in practice, the hardness result covers only the uniform distribution, and the baseline set is thin.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Computing optimal k-sparse anchored linear explanations is NPPP-hard when the black box is a ReLU network (under the uniform distribution).
- For the Mallows-type local family D_{x,σ}, every feasible explanation's relevance error is at most (1+e^{-σ})^k times its fidelity error.
- The empirical fidelity problem is solved exactly by MIP with sample complexity polynomial in k and log d and independent of σ, and approximated in polynomial time by an IHT variant with explicit factor (1+81k·cosh²(σ/2)) and cosh⁴(σ/2) sampling overhead.
- LIME's fidelity advantage over the anchored optimum is an artifact of anchoring violation, and anchored explanations dominate on relevance (15/16 benchmarks, median 1.3×, up to 6×).
Strengths
Unified, strictly more expressive explanation class
Anchored k-sparse linear explanations (Sec 3.2) strictly contain subset explanations and, per Example 2, express compensatory contributions (loan-rate decomposition -0.03+0.11=0.08) that feature subsets cannot convey; the {−1,+1}^d encoding covers both classification and regression under one quadratic loss.
Clean two-level theory with explicit constants
NPPP-hardness via E-MAJ-SAT with parity shielding and an alignment argument (Sec 3.3); Lemma 4's change-of-measure bound R ≤ (1+e^{-σ})^k·F is elementary and exact, its factor shrinking from 32 (σ=0) to 2.23 (σ=1.75) at k=5 — verified empirically (measured R/F ≤ 1.95 for IHT).
Algorithms matched to regimes, and experiments that test the theory
Unusually honest analysis of the surrogate's failure mode
Reproducibility and exactness of the evaluation pipeline
Weaknesses
Worst-case constants are quantitatively vacuous
Hardness covers only the uniform case
Thin and dated baseline set
Narrow black-box family and small instance pool
Interpretability asserted, not measured
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is the journal-length extension of a UAI 2025 paper (stated Best Paper Award) on probabilistic formal explainability. The setting: a black-box f on the Boolean hypercube {−1,+1}^d (binary classifier or [−1,+1] regressor), a reference instance x, and a local distribution D_{x,σ} — Mallows-style exponential decay in Hamming distance, with σ=0 recovering the uniform law. Explanations are k-sparse weight vectors w anchored at w·x=f(x), strictly generalizing subset explanations by encoding magnitude, sign, and compensation of contributions (Example 2's −0.03+0.11=0.08 rate decomposition). Four central claims: (i) minimizing the relevance error E[ℓ(f(z),f(x)) | w·z=w·x] is NPPP-hard for ReLU networks; (ii) relevance ≤ (1+e^{-σ})^k · fidelity for the local family (Lemma 4); (iii) the empirical sparse-regression problem is exactly solvable by MIP with sample complexity polynomial in k and log d and independent of σ (Theorem 2), and approximable in polynomial time by anchored-projection IHT with explicit factor (1+81k·cosh²(σ/2)) (Theorem 3); (iv) LIME/MAPLE violate anchoring (MAPLE also sparsity), and LIME's fidelity edge is an artifact.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the difference between relevance error and fidelity error in this paper?
Relevance error is the expected loss conditioned on the explanation's equation w·z = w·x holding — i.e., error on exactly the instances the explanation covers. Fidelity error is the unconditional expected loss of the linear surrogate over the whole neighborhood. The paper proves relevance ≤ (1+e^{-σ})^k × fidelity for their local distributions, so minimizing fidelity conservatively bounds relevance, with the guarantee requiring the anchoring constraint w·x = f(x).
Why do LIME and MAPLE perform worse in these experiments?
MAPLE violates the sparsity budget and frequently the anchoring condition; LIME respects the budget but its linear model does not reproduce the black-box prediction at the explained instance (no anchoring). The authors show LIME's apparent fidelity advantage correlates (r=0.92) with how far it deviates from anchoring, and the anchored methods achieve lower relevance error on 15 of 16 benchmarks.
Is code or data available for this paper?
Yes. The paper states that source code, environment specifications, and replication scripts are publicly available on GitHub (FredericKoriche/ProbabilisticLinearExplanations), and all 16 benchmarks are standard public OpenML datasets with sklearn MLP black boxes.
How does this paper relate to the UAI 2025 version?
It is an extended journal-style version of a UAI 2025 paper that the authors state received a Best Paper Award. The extension adds the full hardness reduction, the RSC/RSS analysis and IHT convergence proofs, and the expanded 16-dataset experiments with MIP and IHT solvers.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Extraction is truncated in several places: Section 2.2, parts of Section 3 (Definition 5, Lemma 3/Corollary 2 statements), Section 5.2 including Algorithm 1's pseudocode and Lemma 6, part of Table 2, and parts of Sections 6.1 and 7 were omitted.
- Figures 2-6 are judged from captions and in-text numbers only; visual claims (scatter passing through the origin, fit lines, curve shapes) could not be verified.
- The Monte Carlo protocol for estimating the out-of-sample relevance error R in Table 3 is not visible in the extracted text.
- The abstract is truncated mid-sentence in the source metadata.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.