Research map / Learning theory and algorithms / Prediction and decision losses

Probabilistic Explanations for Linear Models

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Counterfactual explanations and recourse · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces (delta, epsilon)-min-SR, a relaxation of probabilistic sufficient reasons, and gives a Monte Carlo plus greedy score-based algorithm that computes them efficiently for linear models under the uniform distribution.

Problem

Computing small probabilistic sufficient reasons (delta-SRs) is computationally hard even for decision trees; explanations need to be small while retaining a probability guarantee.

Approach

Relax delta-SRs to (delta, epsilon)-min-SRs by sampling a random target delta* in [delta-eps, delta+eps] and computing a minimum delta*-SR; for linear models under the uniform distribution, features are chosen greedily by a sign-adjusted weight score and the acceptance probability is estimated by Monte Carlo sampling with binary search.

Key results

• Proves that (delta, epsilon)-min-SRs for linear models can be computed in time O~(d/(eps^2 gamma^2)) with success probability 1-gamma, in contrast with hardness for decision trees.
• Shows a gap example where opt(delta+eps)/opt(delta) = Omega(d^{1/2 - gamma}), so approximating delta does not approximate explanation size.
• Proves every locally minimal delta-SR for linear models under product distributions is subset-minimal.

Surprising findings

• A 0.999999-SR can be 251 times smaller than any 1-SR for a linear model with 1000 features.
• Slightly increasing the probability guarantee from delta to delta+eps can increase the minimum explanation size by a factor of order d^{1/2-gamma}.

Limitations

• Only binary features and uniform distribution; extension to product distributions does not directly work.
• Dependence on 1/epsilon and 1/gamma is high, making practical use expensive.
• No experimental evaluation on real data is reported.

Experimental setup

Baselines: delta-SR exact computation decision tree delta-SR hardness results

Builds on: delta-sufficient reasons abductive explanations

Closest papers by meaning

• On Computing Probabilistic Explanations for Decision Trees (NeurIPS 2022 · similarity 0.91)
• Unifying Formal Explanations: A Complexity-Theoretic Perspective (ICLR 2026 · similarity 0.88)
• A General Theoretical Framework for Learning Smallest Interpretable Models (AAAI 2024 · similarity 0.84)
• Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.84)
• Additive Models Explained: A Computational Complexity Approach (NeurIPS 2025 · similarity 0.83)
• Delivering Inflated Explanations (AAAI 2024 · similarity 0.83)