2025-11-15T14:04:11.886865

Probabilistic Explanations for Linear Models

Subercaseaux, Arenas, Meel
Formal XAI is an emerging field that focuses on providing explanations with mathematical guarantees for the decisions made by machine learning models. A significant amount of work in this area is centered on the computation of "sufficient reasons". Given a model $M$ and an input instance $\vec{x}$, a sufficient reason for the decision $M(\vec{x})$ is a subset $S$ of the features of $\vec{x}$ such that for any instance $\vec{z}$ that has the same values as $\vec{x}$ for every feature in $S$, it holds that $M(\vec{x}) = M(\vec{z})$. Intuitively, this means that the features in $S$ are sufficient to fully justify the classification of $\vec{x}$ by $M$. For sufficient reasons to be useful in practice, they should be as small as possible, and a natural way to reduce the size of sufficient reasons is to consider a probabilistic relaxation; the probability of $M(\vec{x}) = M(\vec{z})$ must be at least some value $δ\in (0,1]$, for a random instance $\vec{z}$ that coincides with $\vec{x}$ on the features in $S$. Computing small $δ$-sufficient reasons ($δ$-SRs) is known to be a theoretically hard problem; even over decision trees--traditionally deemed simple and interpretable models--strong inapproximability results make the efficient computation of small $δ$-SRs unlikely. We propose the notion of $(δ, ε)$-SR, a simple relaxation of $δ$-SRs, and show that this kind of explanation can be computed efficiently over linear models.
academic

Probabilistic Explanations for Linear Models

基本信息

  • 论文ID: 2501.00154
  • 标题: Probabilistic Explanations for Linear Models
  • 作者: Bernardo Subercaseaux (Carnegie Mellon University), Marcelo Arenas (PUC Chile, IMFD Chile, RelationalAI), Kuldeep S. Meel (Georgia Institute of Technology, University of Toronto)
  • 分类: cs.AI (Artificial Intelligence), cs.CC (Computational Complexity)
  • 发表时间: January 3, 2025
  • 论文链接: https://arxiv.org/abs/2501.00154

摘要

本文研究形式化可解释AI（Formal XAI）中的"充分理由"计算问题。给定模型M和输入实例x，充分理由是x的特征子集S，使得任何在S上与x相同的实例z都有M(x)=M(z)。为减小充分理由的大小，作者考虑概率松弛：要求随机实例z与x在特征集合上一致时，M(x)=M(z)的概率至少为δ∈(0,1]。计算小的δ-充分理由（δ-SRs）在理论上很困难，即使对于决策树这样的"可解释"模型也存在强不可近似结果。本文提出了(δ,ε)-SR概念，这是δ-SRs的简单松弛，并证明了这种解释可以在线性模型上高效计算。

研究背景与动机

  1. 核心问题：如何为机器学习模型的决策提供具有数学保证的小尺寸解释。传统的充分理由要求100%的确定性，但这往往导致解释过大，不适合人类理解。
  2. 问题重要性：
    • Miller (1956)指出超过9个特征的解释对人类来说可能太大
    • 实证研究表明解释应当简洁（Narayanan et al., 2018; Lage et al., 2019）
    • 在实际应用中，用户更关心解释的大小而不是概率保证的微小差异
  3. 现有方法局限性：
    • 计算最小δ-SRs即使对决策树也是NP-hard
    • 对于线性模型，精确计算概率是#P-hard
    • 存在强不可近似结果：无法在多项式时间内获得好的近似比
  4. 研究动机：
    • 用户对解释大小的敏感度高于对概率保证微小变化的敏感度
    • 需要在理论可处理性和实用性之间找到平衡
    • 线性模型的特殊结构可能允许高效算法

核心贡献

  1. 提出(δ,ε)-最小充分理由概念：允许概率保证在δ-ε, δ+ε范围内变化的松弛版本
  2. 证明线性模型上的可处理性：给出多项式时间算法计算(δ,ε)-min-SR，运行时间为Õ(n/ε²δ²)
  3. 建立理论分离结果：证明决策树上该问题仍然困难，突出了线性模型的特殊性
  4. 证明局部最小等价性：对线性模型，每个局部最小的δ-SR都是子集最小的δ-SR
  5. 分析近似间隙：证明概率参数的小变化可能导致解释大小的指数级差异

方法详解

任务定义

输入：

  • 线性模型 L=(w,θ)\mathcal{L} = (\mathbf{w}, \theta)，其中 w∈Qn\mathbf{w} \in \mathbb{Q}^n，θ∈Q\theta \in \mathbb{Q}
  • 实例 x∈{0,1}n\mathbf{x} \in \{0,1\}^n
  • 概率阈值 δ∈(0,1)\delta \in (0,1) 和误差容忍度 ε∈(0,1)\varepsilon \in (0,1)

输出：

  • 值 δ∗∈[δ−ε,δ+ε]\delta^* \in [\delta-\varepsilon, \delta+\varepsilon]
  • 最小 δ∗\delta^*-充分理由 y\mathbf{y}

约束条件：

  • L(x)=1\mathcal{L}(\mathbf{x}) = 1 当且仅当 x⋅w≥θ\mathbf{x} \cdot \mathbf{w} \geq \theta
  • 部分实例 y⊑x\mathbf{y} \sqsubseteq \mathbf{x} 使用 ⋆\star 表示未知值

模型架构

1. 特征评分机制

对于线性模型 L=(w,θ)\mathcal{L} = (\mathbf{w}, \theta) 和实例 x\mathbf{x}，定义特征 ii 的评分为：

si=wi⋅(2xi−1)⋅(2L(x)−1)s_i = w_i \cdot (2x_i - 1) \cdot (2\mathcal{L}(\mathbf{x}) - 1)

评分的符号表示特征是"帮助"（+1）还是"损害"（-1）分类，幅度与特征权重成比例。

2. 贪心特征选择

关键引理：对于线性模型，在均匀分布下，按评分递减顺序选择特征是最优的。

具体地，如果 y(0),…,y(n)\mathbf{y}^{(0)}, \ldots, \mathbf{y}^{(n)} 是按最高评分的前 kk 个特征定义的部分实例，则：

Pr⁡z∼U(y(k+1))[L(z)=L(x)]≥Pr⁡z∼U(y(k))[L(z)=L(x)]\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. 蒙特卡洛估计

使用Hoeffding不等式进行概率估计：

对于 m=log⁡2n2ε2δ2log⁡2log⁡nβm = \frac{\log 2n}{2\varepsilon^2\delta^2} \log\frac{2\log n}{\beta} 个样本，有：

Pr⁡[∣p^(m)−p∣≤εδ/log⁡n]≥1−β/log⁡n\Pr[|\hat{p}(m) - p| \leq \varepsilon\delta/\log n] \geq 1 - \beta/\log n

技术创新点

  1. 随机化概率阈值：算法随机选择 δ∗∼U([δ−ε,δ+ε])\delta^* \sim U([\delta-\varepsilon, \delta+\varepsilon])，避免了困难实例
  2. 二分搜索策略：利用概率单调性进行高效搜索
  3. 理论保证的松弛：在保持实用性的同时获得多项式时间复杂度

实验设置

算法描述

Algorithm 1: LinearMonteCarloExplainer

输入: 线性模型L, 实例x, 参数δ, ε, β
1. δ* ← 从[δ-ε, δ+ε]均匀采样
2. 计算所有特征评分 s_i
3. 构造部分实例序列 y^(0), ..., y^(n)
4. 设置样本数 m = (log 2n)/(2ε²δ²) log(2log n/β)
5. 使用二分搜索找到最小k使得估计概率 ≥ δ*
6. 返回 (δ*, y^(k*))

理论分析

主要定理：给定线性模型 L\mathcal{L} 和输入 x\mathbf{x}，可以在时间 O~(nε2δ2)\tilde{O}(\frac{n}{\varepsilon^2\delta^2}) 内以概率 1−β1-\beta 成功计算 (δ,ε)(δ,\varepsilon)-min-SR。

复杂度分析

  • 时间复杂度：O(log⁡n⋅m⋅n)=O~(nε2δ2)O(\log n \cdot m \cdot n) = \tilde{O}(\frac{n}{\varepsilon^2\delta^2})
  • 空间复杂度：O(n)O(n)
  • 成功概率：1−β1-\beta

实验结果

主要结果

  1. 可处理性对比：
    • 线性模型：多项式时间可解
    • 决策树：强不可近似性（除非SAT可在准多项式时间解决）
    • 神经网络：NPPP-hard
  2. 具体示例验证：
    • Example 2展示了0.999999-SR可以比最小1-SR小251倍
    • Example 3验证了贪心选择策略的正确性

理论发现

  1. 分离结果：证明了线性模型相比决策树的根本优势
  2. 局部vs全局最优：对线性模型，局部最小的δ-SR就是子集最小的δ-SR
  3. 近似间隙：概率参数的小变化可能导致解释大小的 Ω(n1/2−ϵ)\Omega(n^{1/2-\epsilon}) 倍差异

案例分析

Example 3 详细分析：

  • 实例：x=(1,0,0,1,1)\mathbf{x} = (1,0,0,1,1)
  • 权重：w=(5,1,−3,2,−1)\mathbf{w} = (5,1,-3,2,-1)，阈值：θ=5\theta = 5
  • 特征评分：(5,−1,3,2,−1)(5,-1,3,2,-1)
  • 最优2特征解释：{1,3}\{1,3\}，概率7/8

相关工作

充分理由计算

  1. Darwiche and Hirth (2020)：首次形式化充分理由概念
  2. Barceló et al. (2020)：建立了不同模型类的复杂度层次
  3. Arenas et al. (2022)：证明了决策树上δ-SRs的困难性

概率解释

  1. Wäldchen et al. (2021)：引入δ-充分理由概念
  2. Izza et al. (2023)：研究概率腹部解释的计算
  3. Kozachinskiy (2023)：建立了决策树的不可近似结果

线性模型解释

  1. Marques-Silva et al. (2020)：研究朴素贝叶斯等线性分类器
  2. Blanc et al. (2021)：相对于证书复杂度的小解释

结论与讨论

主要结论

  1. 理论突破：首次证明了概率解释在线性模型上的多项式时间可计算性
  2. 实用价值：(δ,ε)(δ,\varepsilon)-SR概念在保持理论保证的同时提高了实用性
  3. 模型分离：建立了线性模型与决策树在解释计算复杂度上的根本差异

局限性

  1. 实际效率：对于高维数据（如n=500），当ε=0.1，δ=0.01时计算仍然昂贵
  2. 分布假设：算法假设均匀分布，扩展到乘积分布需要新技术
  3. 特征类型：仅考虑二值特征，实际应用需要处理连续和分类特征

未来方向

  1. 算法优化：降低对1/ε和1/δ的依赖度
  2. 分布扩展：处理乘积分布和更一般的特征分布
  3. 特征类型：扩展到混合特征类型的"扩展线性分类器"
  4. 查询语言：设计声明式的概率解释查询语言

深度评价

优点

  1. 理论贡献显著：
    • 首次建立线性模型概率解释的可处理性
    • 提供了完整的复杂度分析和算法设计
    • 证明了重要的分离结果
  2. 方法创新性：
    • (δ,ε)(δ,\varepsilon)-SR概念巧妙平衡了理论性和实用性
    • 随机化技术有效避免了困难实例
    • 贪心策略的理论证明优雅且深刻
  3. 分析深入：
    • 提供了详细的数学证明
    • 考虑了多种复杂度度量
    • 建立了与相关工作的清晰联系

不足

  1. 实用性限制：
    • 算法对参数敏感，高维情况下效率不佳
    • 仅适用于二值特征的线性模型
    • 均匀分布假设在实际中较强
  2. 实验验证不足：
    • 缺乏大规模数据集上的实验验证
    • 没有与现有启发式方法的比较
    • 理论结果需要更多实证支持
  3. 扩展性问题：
    • 扩展到更一般设置的技术挑战较大
    • 对实际ML pipeline的适用性不明确

影响力

  1. 理论影响：为形式化XAI领域提供了重要的正面结果，打破了该领域主要关注困难性的局面
  2. 方法启发：随机化和松弛技术可能启发其他困难问题的解决
  3. 实用价值：为线性模型的可解释性提供了理论基础

适用场景

  1. 金融风控：线性评分模型的贷款决策解释
  2. 医疗诊断：基于线性回归的风险评估解释
  3. 推荐系统：线性推荐模型的特征重要性分析
  4. 法律合规：需要数学保证的自动化决策解释

参考文献

  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.

本论文在形式化可解释AI领域做出了重要的理论贡献，首次证明了概率解释在线性模型上的可处理性，为该领域提供了难得的正面结果。虽然在实用性方面还有改进空间，但其理论价值和方法创新性使其成为该领域的重要工作。