PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic Linear Explanations

Frederic Koriche, Jean-Marie Lagniez, Chi Tran

arXiv:2609.19077v1cs.LGcs.AI

TL;DR

Long abductive explanations can exceed human cognitive limits, and probabilistic explanations have largely been restricted to classification. This paper introduces sparse, anchored linear explanations for classification and regression, relates relevance error to fidelity error, and develops MIP and IHT methods; experiments report that both satisfy sparsity and anchoring while outperforming LIME and MAPLE on relevance.

  • Problem

    Abductive explanations can exceed human cognitive limits, while probabilistic relaxations have largely been limited to categorical classification.

    Source: §1 · p. 1

  • Method

    The framework represents explanations as sparse, anchored linear models over Boolean features and uses fidelity error with MIP and IHT methods.

    Source: §1 · pp. 2, 4

  • Results

    Experiments report that MIP and IHT satisfy sparsity and anchoring while consistently outperforming LIME on relevance, unlike baselines that violate one or both constraints.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Weighted explanations capture feature contribution magnitude and direction while strictly generalizing subset-based explanations.

    Source: §1 · p. 2

    MIP's worst-case sample bounds are conservative; one stated setting requires roughly 2.9 × 10^6 samples, though practice needs much less.

    Source: §4.2 · p. 16

Abstract

from arXiv · show

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.

1. Introduction

Probabilistic explanations address the cognitive burden of long abductive rules, but prior approaches largely focused on classification. This framework uses sparse, anchored linear models to explain classification and regression, connecting relevance error to tractable fidelity error and offering MIP and IHT solution methods.

1. Introduction

  • Probabilistic explanations target the cognitive burden of abductive rules, and earlier probabilistic approaches were largely restricted to categorical classification.The paper frames explanations as sparse rules with a user-defined size bound k and quantifies the probability of disagreement among matching instances.Source: §1 · pp. 1–2
  • Sparse anchored linear explanations strictly generalize subset explanations, representing compensatory feature effects while retaining magnitude and direction of contributions.Unlike a feature subset, weighted features need not each be fixed when their weighted combination is constrained.Source: §1 · pp. 2, 4
  • In the loan-rate example, two weighted features decompose an 8% prediction into −3 and +11 percentage-point contributions that partially compensate.A feature subset identifies relevant conditions but cannot convey these directional contributions.Source: §1 · p. 3
  • For neural-network models, minimizing relevance error is NPPP-hard, motivating fidelity error as a tractable surrogate.For the specified family of local distributions, relevance error is bounded by (1 + e^-σ)k times fidelity error.Source: §1 · pp. 3–4
  • MIP solves the empirical fidelity problem exactly and has polynomial sample complexity independent of σ, although the underlying sparse-selection problem is NP-hard.Its relevance-error guarantee is at most (1 + e^-σ)k(v* + ε) with high probability.Source: §1 · p. 3
  • IHT provides a polynomial-time approximate alternative, with an exact projection onto the intersection of the sparsity constraint and anchoring hyperplane.Its sampling cost grows with cosh^4(σ/2), and its approximation factor also worsens as locality increases; the paper identifies an intermediate σ regime where IHT is compelling.Source: §1 · pp. 3–4
  • Across classification and regression benchmarks, MIP and IHT satisfy sparsity and anchoring while consistently outperforming LIME on relevance; MAPLE often violates both constraints.MIP certifies optimality on small and medium benchmarks, while IHT remains effective at every scale.Source: §1 · p. 4

2. Related Work

Prior work divides local explainability between probabilistic subset explanations, which emphasize formal guarantees, and linear surrogates, which handle continuous outcomes. This section positions the paper’s sparse, anchored linear framework against both traditions.

2.1. Probabilistic Explanations

  • Probabilistic explanations relax abductive guarantees to high-probability subset rules, with relevance error measuring prediction disagreement under a distribution.For classification, prior work either minimizes error under a size limit or minimizes subset size under an error threshold.Source: §2.1 · p. 5
  • Neural-network probabilistic explanation problems face NPPP-hardness, while finding cardinality-minimal explanations is W[2]-hard in k and hard to approximate closely.The section notes a positive approximation result for linear functions and establishes that subset-based results do not automatically transfer to richer linear explanations.Source: §2.1 · p. 5
  • Blanc et al. (2021) link low tree-surrogate fidelity to low relevance error on average over random reference instances; this paper’s sparse-linear bound is pointwise.The guarantees are complementary: neither subsumes the other.Source: §2.1 · p. 5
  • ANCHORS estimates a black-box classifier’s conditional precision by sampling, but uses greedy search without guarantees on explanation size or approximation quality.It returns feature subsets rather than linear functions, so it is outside the paper’s comparison class.Source: §2.1 · p. 5
  • Contrastive explanations ask what must change, whereas abductive and probabilistic explanations ask why a prediction was made; their unification remains within subsets and categorical classification.The paper instead focuses on sparse linear explanations spanning classification and regression.Source: §2.1 · p. 5

2.2. Linear Explanations

  • Model-agnostic linear explainers fit local surrogates using weighted samples and complexity penalties, but their heuristic objectives can yield unstable explanations and depend on hyperparameters.The cited literature also reports vulnerability to measurement bias and adversarial perturbations.Source: §2.2 · p. 6
  • The proposed framework formalizes locality as a probability law for expected loss, then jointly enforces prediction anchoring and a hard k-sparsity constraint.Unlike LIME’s unguaranteed support selection and MAPLE’s dense weights, these constraints yield explanations with relevance and fidelity bounds.Source: §2.2 · p. 6
  • KERNELSHAP satisfies anchoring but produces dense Shapley values; truncating them to k features breaks local accuracy, so it is not a meaningful baseline.Its weighted least-squares objective targets Shapley values rather than local surrogate accuracy.Source: §2.2 · p. 6

3. Problem Formulation and Complexity

The section defines sparse, anchored linear explanations and their probabilistic quality objective, then analyzes the computational complexity of solving the resulting problem exactly. It establishes hardness for ReLU networks via a reduction from E-MAJ-SAT, using extraction, shielding, and alignment to connect anchored subset explanations with sparse linear explanations.

3.2. Problem Formulation

  • Models take binary literals in {−1, +1}^d and map them to [−1, +1], with classifiers restricted to {−1, +1} and regressors allowed continuous outputs.The first literal is fixed at +1 to provide an intercept.Source: §3.2 · p. 7
  • A linear explanation is a k-sparse weight vector anchored by w·x = f(x), with each nonzero weight attached to a literal’s polarity at the instance.The sparsity budget counts the intercept, which is always available through the constant first literal.Source: §3.2 · p. 7
  • The framework measures relevance error under a distribution over instances and defines SLE as deciding whether an anchored explanation meets both the k-sparsity budget and a relevance threshold.The distribution may be uniform or localized around the instance being explained.Source: §3.2 · p. 8

3.3. Problem Complexity

  • SLE’s exact solution combines combinatorial support selection with probability counting over exponentially many instances, motivating empirical approximations.The section identifies this combination as the source of NPPP hardness.Source: §3.3 · p. 9
  • The complexity reduction must bridge a mismatch: a linear explanation can select a union of subcubes, including ones that do not pass through the explained instance.The section illustrates that fixing a support need not select the same instances as a linear equality constraint.Source: §3.3 · p. 9
  • The reduction extracts a subcube with no greater relevance error, shields variables using parity of k+1 copies, and uses alignment to transfer threshold feasibility to an anchored subcube.Shielding ensures any subcube fixing at most k fresh variables leaves at least one copy free, so the parity remains uninformative.Source: §3.3 · pp. 9–11
  • The hardness setup represents the predictor as a bounded-weight feedforward ReLU network and reduces from E-MAJ-SAT, the canonical complete problem for NPPP.E-MAJ-SAT asks whether some assignment to witness variables makes a majority of the remaining assignments satisfy the formula.Source: §3.3 · pp. 9–10
  • The construction makes a threshold-feasible subcube equivalent to an E-MAJ-SAT witness, with each witness inducing an anchored subcube of codimension k.The construction shields auxiliary variables while retaining the duplicated blocks used to encode witness assignments.Source: §3.3 · pp. 11–12
  • Averaging over assignments compatible with the conditioning implies that a relevance probability above 1/2 yields a witness, which in turn gives an anchored subcube with Q greater than 1/2.Source: §3.3 · p. 12
  • A polynomial-time construction maps E-MAJ-SAT to an aligned instance where positivity is equivalent to an anchored subcube of codimension at most k having relevance error at most 1 − tau.Source: §3.3 · p. 12
  • If E-MAJ-SAT is negative, alignment ensures that no subcube, anchored or otherwise, of codimension at most k meets the relevance-error threshold.Source: §3.3 · p. 12
  • For every fixed relevance threshold tau in (0, 1), SPARSE LINEAR EXPLANATION for ReLU neural networks is NPPP-hard.Source: §3.3 · p. 12
  • Given a qualifying anchored subcube, coefficients equal to x_j/|S| on its support make the linear explanation select exactly that subcube and meet the sparsity budget.Source: §3.3 · pp. 12–13
  • Conversely, any feasible sparse explanation induces a subcube with no greater relevance error, and alignment then yields an E-MAJ-SAT witness.Source: §3.3 · p. 13
  • The reduction’s equivalence and E-MAJ-SAT’s NPPP-completeness (Littman et al., 1998) establish the hardness result.Source: §3.3 · p. 13

4. Dealing with PP-Hardness

For sparse explanations, evaluating relevance error is PP-hard even for a fixed candidate, obstructing standard optimization. This section replaces it with fidelity error, relates the two under localized distributions, and develops a sample-based MIP formulation with guarantees.

4. Dealing with PP-Hardness

  • PP-hard evaluation of relevance error for a fixed explanation makes the objective unsuitable for standard optimization methods.The separate search over supports of size at most k is the familiar combinatorial cost of sparsity.Source: §4 · p. 13

4.1. From Relevance to Fidelity

  • Fidelity error removes the conditioning event while retaining the anchoring constraint, making the surrogate more tractable to analyze and approximate by sampling.The analysis relates relevance and fidelity within a parameterized family of neighborhood distributions.Source: §4.1 · p. 13, §4 · p. 13
  • The relevance-to-fidelity relationship is one-sided: an explanation may have high relevance yet large fidelity error when it performs poorly outside the anchoring subcube.For k=5, the bound factor is about 4.8 at σ=1, 1.9 at σ=2, and 1.3 at σ=3.Source: §4.1 · p. 14

4.2. Empirical Approximation and MIP Formulation

  • The MIP bounds each coefficient to [-1, +1], which with sparsity gives an L1 radius at most k and a finite sample-complexity bound.The theoretical bound is conservative: for k=5, d=100, ε=0.1, and δ=0.05, it requires roughly 2.9 × 10^6 samples; dimensionality enters logarithmically.Source: §4.2 · pp. 15–16
  • With quartic dependence on k and logarithmic dependence on d, the sample bound ensures with high probability that feasible explanations’ relevance errors are bounded using empirical fidelity.For the box-constrained MIP, the L1 radius is B=k; the stated guarantee applies to every feasible explanation.Source: §4.2 · p. 15

5. Dealing with NP-Hardness

This section develops polynomial-time IHT as an alternative to exponential sparse search, using restricted curvature of local samples and an anchoring-preserving projection to establish convergence and end-to-end guarantees. It also examines how locality shapes statistical and computational trade-offs and contrasts IHT with exact MIP to identify when each is preferable.

5. Dealing with NP-Hardness

  • Because the exact MIP has worst-case exponential runtime, the section uses RSC/RSS geometry on sparse update directions to enable a polynomial-time approximation.Differences between feasible anchored k-sparse explanations are 2k-sparse and orthogonal to the reference instance, the directions on which curvature is controlled.Source: §5 · p. 16, §5.1 · p. 17

5.1. Restricted Strong Convexity and Smoothness

  • Localized samples satisfy RSC/RSS with high probability at sufficient sample size, while locality raises sample needs by cosh^4(sigma/2) but leaves the restricted condition number bounded by gamma.The cosh^4(sigma/2) multiplier is approximately 1.6 at sigma=1, 5.7 at sigma=2, and 31 at sigma=3; the auxiliary property does not drive overall complexity.Source: §5.1 · pp. 18–19

5.2. The Iterative Hard Thresholding Explainer

  • The IHT variant projects each update onto the intersection of the anchoring hyperplane and the k-sparse ball, starting from a feasible intercept-only explanation.The exact projection is computable in O(d log d + k^2) time, and every iterate remains a valid anchored k-sparse explanation.Source: §5.2 · p. 19

5.3. Convergence Analysis

  • Under order-3k RSC/RSS with gamma=1.25, IHT contracts at rho=51/152 ≈ 0.34 and converges linearly to a neighborhood whose radius is proportional to the residual gradient norm.When that norm is zero, convergence is exact; the iterates also have fidelity error at most 1 and L1 norm at most k+4.Source: §5.3 · pp. 20–21
  • With probability at least 1-δ, Theorem 3 bounds the returned explanation’s relevance error by (1+e^-σ)k((1+81k cosh^2(σ/2))Fhat(f,x,m,w_hat)+ε).The guarantee applies when the theorem’s sample-size and iteration conditions hold.Source: §5.3 · p. 22
  • The iteration count can be made explicit using a residual bound and depends only on k, σ, and ε; each iteration costs O(md+d log d+k^2).The theorem’s iteration requirement is logarithmic in 1/ε.Source: §5.3 · p. 23
  • IHT recovers the MIP optimum up to a multiplicative factor and exactly in the limit when the neighborhood is genuinely explainable by an anchored k-sparse linear function.The iteration requirement is logarithmic in 1/ε.Source: §5.3 · p. 23
  • The 81k cosh^2(σ/2) multiplier is a strict worst-case bound, while empirical gaps between IHT and MIP are orders of magnitude smaller.The analysis guarantees a finite, explicit bound that vanishes as the optimum empirical fidelity approaches zero.Source: §5.3 · p. 23
  • Locality affects sample complexity through both restricted eigenvalues and iterate magnitude; practical parameters retain the k^4 behavior unless cosh^2(σ/2) exceeds k.The iterate-magnitude contribution scales as (B+1)^4 = O(k^4+k^2 cosh^4(σ/2)).Source: §5.3 · p. 23
  • For large σ, exact MIP avoids IHT’s locality penalties; at moderate σ, IHT offers a scalable polynomial-time alternative, so method choice should follow distribution locality.In the localized regime, the relevance-fidelity factor approaches 1 and MIP sample complexity does not depend on σ, though solver runtime remains worst-case exponential.Source: §5.3 · pp. 23–24

6. Experiments

Across 16 OpenML classification and regression benchmarks, the experiments compare the proposed explainers with LIME, MAPLE, and a relaxation. LIME’s relevance error is generally higher than MIP’s, while MIP and IHT show similar optimization quality and differ substantially in computational cost.

6.1. Experimental Setup

  • The study evaluates 16 OpenML datasets—eight classification and eight regression tasks—using Boolean-encoded attributes and neural-network black-box models.It runs five explainers on ten reference instances per benchmark, totaling 160 tasks, with k=5, m=5000, and σ=1.0 for the initial comparison.Source: §6.1 · p. 24, §6.2 · p. 26

6.2. Optimization Quality and Admissibility

  • IHT and MIP produce exactly five nonzero coefficients on all 160 tasks and enforce anchoring, whereas LIME violates anchoring on all tasks and MAPLE on 84%.MAPLE and MIPrelax also return dense explanations, so they do not meet the sparsity budget.Source: §6.2 · pp. 26–27, §6.1 · p. 26
  • IHT’s empirical fidelity errors match MIP’s to three decimal places on 12 of 16 benchmarks, with at most a 6% relative gap on the others.For three of those four, MIP was stopped before certifying optimality.Source: Table 2 · p. 26, §6.2 · p. 27
  • LIME’s occasional lower fidelity error than MIP is attributed to violating anchoring, not to better optimization within the anchored hypothesis space.Across tasks, its relative fidelity advantage and anchoring gap have correlation r=0.92.Source: §6.2 · p. 27, Figure 2 · p. 28
  • IHT runtime stays between 0.055 and 0.141 seconds from d=12 to d=1652, while MIP reaches its time limit on larger dimensions.MIP certifies optimality on all ten instances per benchmark for d≤69, but on only two of 60 instances with d≥149.Source: §6.2 · pp. 27–28, Figure 3 · p. 28

6.3. Generalization: Fidelity and Relevance

  • LIME has higher out-of-sample relevance error than MIP on 15 of 16 benchmarks and ties on the remaining benchmark, where every explainer’s error is 0.001.At the median, LIME’s relevance error is 1.3 times MIP’s.Source: Table 3 · p. 29, §6.3 · p. 29
  • At the tested settings, out-of-sample fidelity error differs from empirical fidelity by no more than 0.005 across all 48 fidelity entries.The largest difference is on Speed Dating, and no trend with dimension is discernible.Source: §6.3 · p. 29, Table 3 · p. 29
  • Across tested sparsity budgets, IHT and MIP relevance error decreases monotonically; increasing locality lowers error on three of four benchmarks, with COMPAS the exception.With 1,000-fold more data, LIME still has higher relevance error than IHT and MIP on all four sample-size-sweep benchmarks.Source: §6.3 · pp. 30–32

7. Conclusion

The paper unifies probabilistic explanations for classification and regression through sparse anchored linear models, and relates tractable fidelity optimization to relevance. It closes by identifying open extensions involving interactions, direct relevance optimization, and Boolean encoding.

7. Conclusion

  • MIP and IHT yield nearly identical solution quality; MIP certifies optima in moderate dimensions, while IHT scales to the largest benchmarks.Their main difference is computational cost.Source: §7 · p. 33
  • Sparse anchored linear explanations unify binary classification and continuous regression while representing the magnitude and direction of feature contributions.The framework operates over the Boolean hypercube and generalizes subset-based explanations.Source: §7 · p. 33
  • Relevance minimization is NPPP-hard for neural networks; fidelity provides a surrogate whose relevance gap is bounded by (1 + e^-σ)^k for local distributions.The bound's multiplicative factor remains small locally.Source: §7 · p. 33
  • MIP optimizes empirical fidelity exactly, while IHT provides an efficient approximation; both have sample complexity polynomial in sparsity and logarithmic in dimension.IHT's projection onto the anchoring hyperplane is exact and efficiently computable.Source: §7 · p. 33

Richer explanation classes

  • Linear explanations cannot capture feature interactions; polynomial lifts introduce dependencies that require new restricted-eigenvalue analysis, and their sample-complexity cost remains open.The proposed extension uses sparse low-degree polynomials, such as pairwise monomials.Source: §7 · p. 33

Optimizing relevance directly

  • Direct empirical relevance optimization remains NPPP-hard and yields a piecewise-constant objective that is unsuitable for gradient- or convexity-based methods.The conditioning event depends discontinuously on the explanation weights.Source: §7 · p. 33

Beyond binarized domains

  • Boolean encoding counts indicator literals rather than user-facing attributes; relaxing coordinate independence would require new covariance analysis.An attribute-level formulation would use group sparsity, while dependent data would break the covariance isotropy used in the current analysis.Source: §7 · p. 33

Related papers

Loading 2609.19077v1…