Additive Models Explained: A Computational Complexity Approach¶

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

一句话总结¶

对广义可加模型（GAM）的多种解释类型（充分理由、对比解释、Shapley值等）进行系统的计算复杂度分析，揭示了GAM的可解释性代价高度依赖于输入域类型、组件模型类型和任务类型（回归vs分类），某些看似"可解释"的设定实际上是NP-Hard甚至#P-Hard。

领域现状：GAM \(f(\mathbf{x}) = \beta_0 + \sum_i \beta_i f_i(\mathbf{x}_i)\) 被ML社区广泛认为是"可解释"的模型类。
现有痛点：尽管GAM被视为可解释模型，但"可解释"不等于"高效可计算解释"。此前缺乏系统性的复杂度分析。
核心矛盾：直觉上GAM的加法结构应该让解释任务更容易，但这个直觉是否在所有设定下都成立？
本文要解决什么？ 系统回答：对于不同类型的GAM（smooth/NAM/EBM）、不同输入域（可枚举离散/一般离散/连续）、不同解释方法，计算解释的复杂度分别是什么？
切入角度：将每种"组件模型×输入域×解释方法"组合建模为计算问题，证明精确的复杂度类别。
核心idea一句话：GAM的解释复杂度远比想象的多样——输入域类型是决定性因素，这在其他ML模型中从未被观察到。

纯理论复杂度分析。分析维度：组件模型（Smooth/NAM/EBM）×输入域（可枚举离散/一般离散/连续）×解释类型（CSR/MSR/MCR/FR/CC/SHAP-R/SHAP-C）。

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

纯理论工作，无实验数据。核心贡献是覆盖54种设定的完整复杂度图谱。