Probabilistic Explanations for Linear Models

Basic Information

• Paper ID: 2501.00154
• Title: Probabilistic Explanations for Linear Models
• Authors: Bernardo Subercaseaux (Carnegie Mellon University), Marcelo Arenas (PUC Chile, IMFD Chile, RelationalAI), Kuldeep S. Meel (Georgia Institute of Technology, University of Toronto)
• Classification: cs.AI (Artificial Intelligence), cs.CC (Computational Complexity)
• Publication Date: January 3, 2025
• Paper Link: https://arxiv.org/abs/2501.00154

Abstract

This paper investigates the computational problem of computing "sufficient reasons" in Formal Explainable AI (Formal XAI). Given a model M and input instance x, a sufficient reason is a feature subset S such that any instance z agreeing with x on S satisfies M(x) = M(z). To reduce the size of sufficient reasons, the authors consider a probabilistic relaxation: requiring that for random instances z agreeing with x on a feature set, M(x) = M(z) with probability at least δ ∈ (0,1]. Computing small δ-sufficient reasons (δ-SRs) is theoretically difficult, with strong inapproximability results even for "interpretable" models like decision trees. The paper proposes the (δ,ε)-SR concept, a simple relaxation of δ-SRs, and proves that such explanations can be computed efficiently on linear models.

Research Background and Motivation

1. Core Problem: How to provide mathematically guaranteed small-sized explanations for machine learning model decisions. Traditional sufficient reasons require 100% certainty, but this often results in explanations too large for human comprehension.
2. Problem Significance:
   • Miller (1956) noted that explanations exceeding nine features may be too large for humans
   • Empirical studies demonstrate that explanations should be concise (Narayanan et al., 2018; Lage et al., 2019)
   • In practical applications, users care more about explanation size than minor variations in probabilistic guarantees
3. Limitations of Existing Approaches:
   • Computing minimum δ-SRs is NP-hard even for decision trees
   • For linear models, exact probability computation is #P-hard
   • Strong inapproximability results exist: no good approximation ratios achievable in polynomial time
4. Research Motivation:
   • Users are more sensitive to explanation size than minor changes in probabilistic guarantees
   • Need to balance theoretical tractability with practical utility
   • The special structure of linear models may allow efficient algorithms

Core Contributions

1. Proposes (δ,ε)-minimum sufficient reason concept: A relaxation allowing probabilistic guarantees to vary within δ-ε, δ+ε
2. Proves tractability on linear models: Provides polynomial-time algorithm computing (δ,ε)-min-SR with runtime Õ(n/ε²δ²)
3. Establishes theoretical separation results: Proves the problem remains hard on decision trees, highlighting the special nature of linear models
4. Proves local minimum equivalence: For linear models, every locally minimal δ-SR is a subset-minimal δ-SR
5. Analyzes approximation gaps: Proves that small changes in probabilistic parameters may lead to exponential differences in explanation size

Methodology Details

Task Definition

Input:

• Linear model $\mathcal{L} = (\mathbf{w}, \theta)$, where $\mathbf{w} \in \mathbb{Q}^n$, $\theta \in \mathbb{Q}$
• Instance $\mathbf{x} \in \{0,1\}^n$
• Probability threshold $\delta \in (0,1)$ and error tolerance $\varepsilon \in (0,1)$

Output:

• Value $\delta^* \in [\delta-\varepsilon, \delta+\varepsilon]$
• Minimum $\delta^*$-sufficient reason $\mathbf{y}$

Constraints:

• $\mathcal{L}(\mathbf{x}) = 1$ if and only if $\mathbf{x} \cdot \mathbf{w} \geq \theta$
• Partial instance $\mathbf{y} \sqsubseteq \mathbf{x}$ uses $\star$ to denote unknown values

Model Architecture

1. Feature Scoring Mechanism

For linear model $\mathcal{L} = (\mathbf{w}, \theta)$ and instance $\mathbf{x}$, define the score of feature $i$ as:

$s_i = w_i \cdot (2x_i - 1) \cdot (2\mathcal{L}(\mathbf{x}) - 1)$

The sign of the score indicates whether the feature "helps" (+1) or "hurts" (-1) the classification, with magnitude proportional to feature weight.

2. Greedy Feature Selection

Key Lemma: For linear models, selecting features in decreasing order of scores under uniform distribution is optimal.

Specifically, if $\mathbf{y}^{(0)}, \ldots, \mathbf{y}^{(n)}$ are partial instances defined by the top k features with highest scores, then:

$\Pr_{z \sim U(\mathbf{y}^{(k+1)})}[\mathcal{L}(z) = \mathcal{L}(\mathbf{x})] \geq \Pr_{z \sim U(\mathbf{y}^{(k)})}[\mathcal{L}(z) = \mathcal{L}(\mathbf{x})]$

3. Monte Carlo Estimation

Using Hoeffding's inequality for probability estimation:

For $m = \frac{\log 2n}{2\varepsilon^2\delta^2} \log\frac{2\log n}{\beta}$ samples:

$\Pr[|\hat{p}(m) - p| \leq \varepsilon\delta/\log n] \geq 1 - \beta/\log n$

Technical Innovations

1. Randomized Probability Threshold: Algorithm randomly selects $\delta^* \sim U([\delta-\varepsilon, \delta+\varepsilon])$, avoiding hard instances
2. Binary Search Strategy: Leverages probability monotonicity for efficient search
3. Relaxation with Theoretical Guarantees: Achieves polynomial-time complexity while maintaining practical utility

Experimental Setup

Algorithm Description

Algorithm 1: LinearMonteCarloExplainer

Input: Linear model L, instance x, parameters δ, ε, β
1. δ* ← Sample uniformly from [δ-ε, δ+ε]
2. Compute all feature scores s_i
3. Construct partial instance sequence y^(0), ..., y^(n)
4. Set sample count m = (log 2n)/(2ε²δ²) log(2log n/β)
5. Use binary search to find minimum k such that estimated probability ≥ δ*
6. Return (δ*, y^(k*))

Theoretical Analysis

Main Theorem: Given linear model $\mathcal{L}$ and input $\mathbf{x}$, one can compute (δ,ε)-min-SR in time $\tilde{O}(\frac{n}{\varepsilon^2\delta^2})$ with probability $1-\beta$.

Complexity Analysis

• Time Complexity: $O(\log n \cdot m \cdot n) = \tilde{O}(\frac{n}{\varepsilon^2\delta^2})$
• Space Complexity: $O(n)$
• Success Probability: $1-\beta$

Experimental Results

Main Findings

1. Tractability Comparison:
   • Linear models: Polynomial-time solvable
   • Decision trees: Strong inapproximability (unless SAT is quasi-polynomial solvable)
   • Neural networks: NPPP-hard
2. Concrete Example Verification:
   • Example 2 demonstrates that 0.999999-SR can be 251 times smaller than minimum 1-SR
   • Example 3 validates the correctness of greedy selection strategy

Theoretical Discoveries

1. Separation Results: Proves fundamental advantages of linear models over decision trees
2. Local vs. Global Optimality: For linear models, locally minimal δ-SR is also subset-minimal δ-SR
3. Approximation Gap: Small changes in probability parameters may cause $\Omega(n^{1/2-\epsilon})$ factor differences in explanation size

Case Analysis

Detailed Analysis of Example 3:

• Instance: $\mathbf{x} = (1,0,0,1,1)$
• Weights: $\mathbf{w} = (5,1,-3,2,-1)$, threshold: $\theta = 5$
• Feature scores: $(5,-1,3,2,-1)$
• Optimal 2-feature explanation: $\{1,3\}$, probability 7/8

Related Work

Sufficient Reason Computation

1. Darwiche and Hirth (2020): First formalization of sufficient reason concept
2. Barceló et al. (2020): Established complexity hierarchy across model classes
3. Arenas et al. (2022): Proved hardness of δ-SRs on decision trees

Probabilistic Explanations

1. Wäldchen et al. (2021): Introduced δ-sufficient reason concept
2. Izza et al. (2023): Studied computation of probabilistic abductive explanations
3. Kozachinskiy (2023): Established inapproximability results for decision trees

Linear Model Explanations

1. Marques-Silva et al. (2020): Studied explanations for linear classifiers like naive Bayes
2. Blanc et al. (2021): Small explanations relative to certificate complexity

Conclusions and Discussion

Main Conclusions

1. Theoretical Breakthrough: First proof of polynomial-time computability of probabilistic explanations on linear models
2. Practical Value: (δ,ε)-SR concept improves practicality while maintaining theoretical guarantees
3. Model Separation: Establishes fundamental differences between linear models and decision trees in explanation computation complexity

Limitations

1. Practical Efficiency: For high-dimensional data (e.g., n=500), computation remains expensive when ε=0.1, δ=0.01
2. Distribution Assumptions: Algorithm assumes uniform distribution; extension to product distributions requires new techniques
3. Feature Types: Only considers binary features; real applications require handling continuous and categorical features

Future Directions

1. Algorithm Optimization: Reduce dependence on 1/ε and 1/δ
2. Distribution Extension: Handle product distributions and more general feature distributions
3. Feature Types: Extend to "extended linear classifiers" with mixed feature types
4. Query Language: Design declarative probabilistic explanation query language

In-Depth Evaluation

Strengths

1. Significant Theoretical Contributions:
   • First establishment of tractability for probabilistic explanations on linear models
   • Complete complexity analysis and algorithm design
   • Proves important separation results
2. Methodological Innovation:
   • (δ,ε)-SR concept cleverly balances theoretical and practical considerations
   • Randomization technique effectively avoids hard instances
   • Elegant and profound theoretical proof of greedy strategy
3. Thorough Analysis:
   • Provides detailed mathematical proofs
   • Considers multiple complexity measures
   • Establishes clear connections with related work

Weaknesses

1. Practical Limitations:
   • Algorithm sensitive to parameters, inefficient in high dimensions
   • Applicable only to linear models with binary features
   • Uniform distribution assumption is strong in practice
2. Insufficient Experimental Validation:
   • Lacks experimental verification on large-scale datasets
   • No comparison with existing heuristic methods
   • Theoretical results need more empirical support
3. Scalability Issues:
   • Significant technical challenges for extension to more general settings
   • Applicability to real ML pipelines unclear

Impact

1. Theoretical Impact: Provides important positive results for Formal XAI, breaking the field's focus on hardness results
2. Methodological Inspiration: Randomization and relaxation techniques may inspire solutions to other hard problems
3. Practical Value: Provides theoretical foundation for linear model interpretability

Applicable Scenarios

1. Financial Risk Control: Explaining loan decisions in linear scoring models
2. Medical Diagnosis: Explaining risk assessment based on linear regression
3. Recommendation Systems: Feature importance analysis for linear recommendation models
4. Legal Compliance: Explaining automated decisions with mathematical guarantees

References

1. Darwiche, A. and Hirth, A. (2020). On the Reasons Behind Decisions. ECAI 2020.
2. Barceló, P., Monet, M., Pérez, J., and Subercaseaux, B. (2020). Model interpretability through the lens of computational complexity. NeurIPS 2020.
3. Wäldchen, S., MacDonald, J., Hauch, S., and Kutyniok, G. (2021). The computational complexity of understanding binary classifier decisions. JAIR.
4. Arenas, M., Barceló, P., Romero Orth, M., and Subercaseaux, B. (2022). On computing probabilistic explanations for decision trees. NeurIPS 2022.
5. Kozachinskiy, A. (2023). Inapproximability of sufficient reasons for decision trees. arXiv:2304.02781.

This paper makes important theoretical contributions to Formal Explainable AI, being the first to prove tractability of probabilistic explanations on linear models, providing rare positive results in the field. While there is room for improvement in practical applicability, its theoretical value and methodological innovation make it an important work in the field.