Additive Models Explained: A Computational Complexity Approach¶

会议: NeurIPS 2025
arXiv: 2510.21292
代码: 无
领域: 可解释AI / 计算复杂度
关键词: GAM, 可解释性, 计算复杂度, Shapley值, 充分理由, 对比解释

一句话总结¶

对广义可加模型（GAM）的多种解释类型进行系统的计算复杂度分析，覆盖 54 种"组件模型 × 输入域 × 解释方法"组合，揭示 GAM 的解释复杂度高度依赖输入域类型——这是决策树、神经网络等其他 ML 模型从未展现的独特现象，挑战了"可加即可解释"的直觉假设。

研究背景与动机¶

领域现状：广义可加模型（GAM）\(f(\mathbf{x}) = \beta_0 + \sum_i \beta_i f_i(\mathbf{x}_i)\) 被 ML 社区广泛视为"可解释"模型类，其加法结构使输入与输出之间的关系相对容易理解。基于这一认知，许多解释技术（LIME 等）试图将模型近似为加法行为，指标如 infidelity 通过加法近似质量来评估解释好坏。

现有痛点：尽管 GAM 被视为可解释模型，"可解释"不等于"可高效计算解释"。此前的计算复杂度研究主要聚焦于神经网络（NP-Hard）、决策树（多项式时间）等，对 GAM 这一重要模型类缺乏系统性分析。GAM 的变体众多——组件可以是样条（Smooth GAM）、神经网络（NAM）、提升树集成（EBM），输入域可以是离散或连续的——不同组合下的解释复杂度可能差异巨大。

核心矛盾：直觉上 GAM 的加法分解结构应该让解释变得容易——每个特征的贡献可以独立分析。但这个直觉是否在所有组合下都成立？如果存在反例，那么"加法 = 可解释"这一学界的基础假设就需要被修正。

本文目标 全面回答：对不同类型的 GAM（Smooth/NAM/EBM）、不同输入域（可枚举离散/一般离散/连续）、不同解释方法（充分理由、对比解释、Shapley值、特征冗余），计算解释的复杂度精确属于哪个复杂度类？

切入角度：将 54 种"组件 × 输入域 × 解释"组合各自建模为精确的计算问题，通过归约和算法构造证明完整的复杂度图谱。

核心 idea：GAM 的解释复杂度远比想象的多样——输入域类型是决定性因素，这在此前研究的所有其他 ML 模型中从未被观察到。

方法详解¶

整体框架¶

纯理论复杂度分析。三个分析维度的全排列：

组件模型（3种）：Smooth GAM（样条）、NAM（ReLU 神经网络）、EBM（提升树集成）
输入域（3种）：可枚举离散（每个变量取常数集合的值）、一般离散（二进制编码的有界离散值）、连续（实值域）
解释类型（6种+）：CSR（检查充分理由）、MSR（最小充分理由）、MCR（最小对比解释）、FR（特征冗余）、CC（完成计数）、SHAP-R（回归Shapley值）、SHAP-C（分类Shapley值）

关键设计¶

输入域是决定性因素（Theorem 1 & 2）：
- 发现：对大多数解释类型，从可枚举离散域到一般离散/连续域，复杂度发生指数级跳跃（PTIME → NP-Hard 或 #P-Hard）
- 直觉解释：可枚举离散域下可以显式遍历每个组件 \(f_i\) 的所有取值来计算最大/最小值或期望，但一般离散和连续域下这种遍历不可行
- 唯一例外：特征冗余（FR）查询反而在连续域下更容易——连续域中特征冗余当且仅当 \(\beta_i \cdot f_i(\mathbf{x}_i) \equiv 0\)，可以高效检查；而离散域需要验证该值是否落在决策边界以下，通常是 coNP-Complete
- 独特性：这种输入域敏感性是 GAM 独有的——决策树、神经网络、树集成都不展示此特性
组件模型的影响依赖于输入域（Theorem 3）：
- 发现：Smooth GAM（样条）在所有输入域下 CSR/MSR/MCR 都是 PTIME；但 NAM/EBM 在一般离散和连续域下升至 coNP-Hard/NP-Complete
- 关键洞察：可枚举离散域下组件模型类型不影响复杂度（输入空间的可枚举性"屏蔽"了组件模型的复杂性），但非枚举域下神经网络和树集成组件的内部复杂性"暴露"出来
- 证明思路：对 NAM/EBM，利用单个 ReLU 网络或树集成组件的求值困难性，通过归约证明 hardness
回归 vs 分类的差异仅对 SHAP 成立（Theorem 4）：
- 发现：Smooth GAM + 可枚举离散域下，SHAP-R（回归）是 PTIME，但 SHAP-C（分类）是 #P-Complete
- 直觉解释：分类引入额外的 step 函数 \(\text{step}(z) = \mathbf{1}[z \geq 0]\)，其非线性破坏了 Shapley 值计算所依赖的线性公理。回归下 Shapley 值可以利用加法结构分解为各组件的独立期望计算，但分类下 step 函数将所有组件的值耦合在一起
- 独特性：其他解释类型（充分理由、对比解释）不存在回归/分类的复杂度差异

核心复杂度结果总结¶

输入域	组件类型	CSR/MSR	MCR	FR	SHAP-C	SHAP-R
可枚举离散	任意	PTIME	PTIME	coNP-C	#P-C (伪P)	PTIME
一般离散	Smooth	PTIME	PTIME	coNP-C	#P-C	PTIME
一般离散	NAM/EBM	coNP-H	NP-C	coNP-C	#P-C	#P-C
连续	Smooth	PTIME	PTIME	PTIME	#P-C	PTIME
连续	NAM/EBM	coNP-H	NP-C	coNP-C	#P-C	#P-C

加法 vs 非加法模型的可解释性比较¶

设置	EBM/NAM	树集成/神经网络
可枚举离散 CSR	PTIME	coNP-C
可枚举离散 MSR	PTIME	\(\Sigma_2^P\)-C
可枚举离散 MCR	PTIME	NP-C
可枚举离散 SHAP-R	PTIME	#P-C
一般离散/连续 CSR	coNP-C	coNP-C（无差异）

实验关键数据¶

纯理论工作，无实验数据。核心贡献是覆盖 54 种设定的完整复杂度图谱，每种组合都有精确的复杂度类别证明。

关键发现¶

GAM 并非总是"容易解释"：NAM/EBM + 连续域下 MSR 是 coNP-Hard，打破了"加法结构保证可解释性"的假设
Smooth GAM 最"安全"：所有输入域下充分理由和对比解释都是 PTIME，是可证明可解释的
SHAP 分类计算最昂贵：几乎在所有设定下都是 #P-Complete，即使对 Smooth GAM 也不例外
可枚举离散域是"安全港"：在这个域下所有 GAM 的 CSR/MSR/MCR 都是 PTIME，对实践的启示是数据离散化可以让解释变得高效
NAM 比独立 NN 更易解释：可枚举离散域下 NAM 的解释是 PTIME，而一般 NN 至少 NP-Hard——加法结构确实有帮助，但仅限于特定输入域

亮点与洞察¶

输入域敏感性是全新发现：此前研究其他模型（决策树、NN、树集成）的解释复杂度时从未发现此现象，GAM 的独特加法结构使得输入域成为"杠杆变量"
"可解释模型 ≠ 可高效解释"的警示：这一结论对整个 XAI 社区有重要影响——不能因为模型结构"看起来简单"就假设解释计算也简单
实用建议清晰：（1）离散化输入可以让解释从 intractable 变 tractable；（2）量化模型系数可以将 #P 问题降为伪多项式时间
证明技巧的迁移价值：将 NN verification 的 hardness 归约到 NAM 组件解释的方法可以推广到其他加法分解模型

局限与展望¶

仅涵盖单变量组件：GAM 实践中常用高阶交互项 \(f_{ij}(\mathbf{x}_i, \mathbf{x}_j)\)（GA2M 等），高阶交互如何影响复杂度是重要的开放问题
理论到实践的鸿沟：虽然提供了多项式时间算法，但未实现和评估其在实际 GAM 上的运行效率
近似算法未探索：对 intractable 设定，是否存在具有可证明保证的近似算法？这对实践更重要
未考虑共曲率（concurvity）：当组件之间高度相关时，GAM 的有效复杂度可能降低

评分¶

新颖性: ⭐⭐⭐⭐⭐ 输入域敏感性是全新发现，54种组合的完整图谱是该领域的重要贡献
实验充分度: ⭐⭐⭐ 纯理论工作无实验，但理论覆盖极其完整
写作质量: ⭐⭐⭐⭐ 结果表格清晰，关键洞察的文字总结易于理解
价值: ⭐⭐⭐⭐ 对 XAI 理论研究有重要影响，对 GAM 实践选型有指导意义