Proxy-Based Approximation of Shapley and Banzhaf Interactions¶

会议: NeurIPS 2026
arXiv: 2605.22738
OpenReview: https://openreview.net/forum?id=H7HFOu71Yi
代码: https://github.com/Advueu963/ProxySHAP
领域: 可解释性
关键词: 合作博弈论、高阶交互、Shapley交互指数、Banzhaf交互、代理模型

一句话总结¶

提出了 ProxySHAP 框架，通过多项式时间闭式算法从树系综代理模型中精确提取任意基数概率交互指数，并结合情境化残差校正，在低预算与高预算下均刷新了高阶 Shapley 与 Banzhaf 交互估计的 SOTA。

研究背景与动机¶

随着机器学习在医疗诊断、金融信贷等高风险场景中的深入应用，模型决策的透明性与可信度面临前所未有的要求。以 Shapley 值和 Banzhaf 值为代表的合作博弈归因方法，因其坚实的公理化基础成为了特征归因与数据估值的黄金标准。然而，传统的基数概率值本质上仅能量化单个特征的独立边际贡献，无法捕捉现代深度学习模型（如多模态视觉-语言模型、图神经网络、复杂集成树模型）内部极其关键的非线性、高阶依赖关系。例如在多模态对齐中，图像 Patch 与文本 Token 之间的联合协同效应，单凭一阶特征归因完全无法解析。

为了刻画更精细的内部归因结构，学术界近期将注意力转向高阶基数概率交互指数（如 Shapley 交互指数与 Banzhaf 交互指数）。但高阶交互估计目前深陷「效率与精度的二元困境」：直接计算 $n$ 个特征的交互需要遍历 $2^n$ 种联盟子集，计算量呈指数级爆炸。现有的高效采样估计器（如 SHAP-IQ / MSR）虽然计算轻便，但在有限预算下方差极大，且方差随着交互阶数呈超多项式乃至指数级恶化；而基于加权最小二乘回归的估计器（如 KernelSHAP-IQ）虽然具备一致性，但需要极高的采样预算来拟合组合爆炸的交互项，并在特征维度上引入高昂的二次时间复杂度。另一类代理模型路线（如 ProxySPEX）尝试用树模型的傅里叶系数提取交互，却遭遇了指数依赖树深度 $\mathcal{O}(4^d)$ 的算力瓶颈，被迫进行激进截断，牺牲了逼近精度。

针对上述矛盾，本文提出了一种能够兼顾高采样效率、严谨一致性与快速提取的全新范式。核心 idea：将高阶交互估计解耦为「树系综闭式精确提取」与「情境化 MSR 残差偏差校正」，通过多项式时间介入式提取算法绕过深度爆炸瓶颈，并在理论方差边界指导下自适应实施残差校正。

方法详解¶

整体框架¶

ProxySHAP 的核心机制建立在基数概率交互指数的线性公理（Linearity）之上。给定具有 $n$ 个参与者（特征）的博弈值函数 $\nu: 2^N \to \mathbb{R}$ 以及评估预算 $m$，首先通过杠杆采样等分布无放回采样联盟子集集合 $\mathcal{T}=\{T_1, \dots, T_m\} \subseteq 2^N$ 并查询其实际模型值。利用这些带标签的二值子集样本，训练一个回归树系综代理模型 $\hat{\nu}_{\mathcal{T}}$（默认采用 XGBoost 或 LightGBM）逼近原始博弈。根据线性性质，目标交互指数 $\phi_S^p(\nu)$ 可严格解耦为代理项与残差项之和： $$\phi_S^p(\nu) = \phi_S^p(\hat{\nu}_{\mathcal{T}}) + \phi_S^p(\nu - \hat{\nu}_{\mathcal{T}})$$ 其中代理项通过闭式多项式时间算法一次遍历树节点精确解析提取；残差项则根据理论方差上界，在满足预算充分覆盖的前提下，情境化地调用最大样本复用（MSR）进行去偏估计。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["联盟子集采样与黑盒模型评估<br/>杠杆采样获取评估样本集 T"] --> B["阶段1：树系综代理模型拟合<br/>基于二值编码子集监督训练 XGBoost"]
    B --> C["阶段2：介入式闭式交互提取<br/>叶节点单次遍历解析聚合多项式时间求解"]
    C --> D{"方差边界与预算判定<br/>判断预算是否满足覆盖条件"}
    D -->|小维度或超大预算| E["阶段3：MSR 残差偏差校正<br/>复用相同采样样本估计残差消除代理偏差"]
    D -->|高阶交互或高维特征| F["直接输出代理提取值<br/>规避 MSR 方差爆炸保持最低 MSE"]
    E --> G["最终高阶交互指数估计输出"]
    F --> G

关键设计¶

1. 树系综介入式交互提取算法：突破指数级树深度依赖

针对 ProxySPEX 等基于傅里叶展开方法在树深度达到 $d$ 时复杂度高达 $\mathcal{O}(4^d)$ 的致命缺陷，本文将介入式 TreeSHAP 推广到任意阶基数概率交互指数。树代理模型本质上可表示为叶节点指示博弈的线性加权和： $$\hat{\nu}_{\text{tree}}(T) = \sum_{j \in \mathcal{L}} c_j \cdot \mathbb{I}[R_j \subseteq T \subseteq N \setminus L_j]$$ 其中 $\mathcal{L}$ 为叶节点集合，$c_j$ 为叶预测值，$R_j$ 与 $L_j$ 分别为通往该叶节点路径上的向右、向左分裂特征集。通过推导指示博弈的 Möbius 逆变换表示，并结合基数概率交互指数与 Möbius 系数之间的权重转换矩阵 $q_t^s(n)$，本文证明任意子集 $S \subseteq N$ 的代理交互均可按闭式解析聚合： $$\phi_S^p(\hat{\nu}_{\text{tree}}) = \sum_{j \in \mathcal{L}: S \subseteq L_j \cup R_j} c_j \cdot \lambda(|L_j|, |R_j|, |S \cap L_j|, |S|)$$ 其中组合系数核定义为 $\lambda(\ell, r, u, s) := \sum_{i=0}^{\ell-u} (-1)^{i+u} \binom{\ell-u}{i} q_{i+u+r}^s(n)$。该算法对单个高阶交互的计算复杂度仅为树节点数的线性阶 $\mathcal{O}(n_{\text{nodes}})$，提取目标集合 $\mathcal{S}$ 时复杂度为 $\mathcal{O}(n_{\text{nodes}} \cdot |\mathcal{S}|)$。相比傅里叶方法不仅免去了精度折损的截断，更实现了高达 $10\times \sim 1000\times$ 的运行加速。

2. 残差校正的理论方差上界与情境化自适应触发准则

为了保证在渐进大预算下的理论一致性，ProxySHAP 探索引入最大样本复用（MSR）估计残差博弈 $r(T) = \nu(T) - \hat{\nu}_{\mathcal{T}}(T)$ 的高阶交互。然而，针对一阶 Shapley 值有效的残差校正并不能盲目套用到高阶交互。定理 3.3 严格证明了在杠杆采样下，阶数为 $s = |S|$ 的 Shapley 交互估计方差界限满足： $$\mathbb{V}[\hat{\phi}_S^{\text{MSR}}(\nu, \mathcal{T})] \le \begin{cases} \mathcal{O}\left(\frac{\|\nu\|_\infty^2 \log n}{|\mathcal{T}|}\right), & |S| = 1 \\[6pt] \mathcal{O}\left(\frac{\|\nu\|_\infty^2 n^{|S|-1}}{|\mathcal{T}|}\right), & |S| \ge 2 \end{cases}$$ 方差上界随交互阶数指数级增长，其主导项正比于 $n^{k-1}/|\mathcal{T}|$。当参与者数量较大或交互阶数 $k \ge 3$ 时，MSR 引入的方差剧烈膨胀，往往反向压倒代理模型本身的拟合误差，导致均方误差恶化。基于此理论界限，ProxySHAP 确立了情境化自适应策略：仅在小维度场景（$n < 30$）或样本预算远超方差主导项（$|\mathcal{T}| \gg n^{k-1}$，通常需预算超 $10^4$）时开启残差校正；在超高维特征或高阶交互下直接输出纯树代理提取值，从而在所有预算区间均守住极佳精度。

3. 面向高维交互的大规模浅树代理配置

代理模型的拟合质量决定了交互估计的基础上限。针对含上千维特征的大规模图和表格任务，标准默认参数配置（深度 6、单树容量大）容易欠拟合罕见子集或在高维稀疏指示下训练过度震荡。通过系统性的贝叶斯超参数优化（HPO）分析，作者提炼出适用于高维大规模博弈的 HPO-Informed 树系综配置：将最大树深严格压制到 3（浅树），而将弱学习器树棵树拓展至 2,000 棵，同时匹配学习率 0.05 与 L2 正则系数 5。浅树限制了单棵树能捕获的高阶交互范围，有效防止了噪声过拟合，而海量树累积则提供了充足的表征容量，使 ProxySHAP 在超过 1,000 维特征的超大规模任务上显著抛离竞争基线。

损失函数 / 训练策略¶

树代理模型使用二值掩码向量 $T \in \{0, 1\}^n$ 作为特征输入，以查询值 $\nu(T)$ 为标量标签，通过均方误差损失（MSE）进行梯度提升拟合： $$\mathcal{L}(\hat{\nu}) = \frac{1}{|\mathcal{T}|} \sum_{T \in \mathcal{T}} \left( \nu(T) - \hat{\nu}(T) \right)^2 + \Omega(\hat{\nu})$$ 其中 $\Omega(\hat{\nu})$ 为树复杂度正则项。在子集采样策略上，默认采用杠杆采样（Leverage Sampling）无放回抽取联盟，其概率密度为 $\mathbb{P}_{\text{sampling}}(T) = \frac{1}{(n+1) \binom{n}{|T|}}$。消融实验证实，让树拟合与 MSR 残差估计复用同一批采样样本集合 $\mathcal{T}$，相比将样本划分为两个互斥集合具有更高的样本利用率和更低的交互估计均方误差。

实验关键数据¶

主实验¶

在 47 个基准数据集（涵盖 TabArena 表格、视觉 Transformer、DistilBERT 文本、分子图神经网络及 CLIP 视觉-语言模型）上，ProxySHAP 对二阶与三阶 Shapley (SII) 和 Banzhaf (BII) 交互估计展开系统评测。下表展示了代表性数据集在 2,048 采样预算下的二阶 Shapley 交互相对均方误差（Relative MSE，越低越好）：

数据集	参与者维度 $n$	评估指标	ProxySHAP (XGBoost)	ProxySPEX	KernelSHAP-IQ	相对误差降低幅度
Cancer	30	Relative MSE	0.021	0.084	0.145	-75.0%
Mutagenicity (GNN)	35	Relative MSE	0.015	0.062	0.098	-75.8%
Splice	60	Relative MSE	0.038	0.152	0.312	-75.0%
Crime	101	Relative MSE	0.046	0.187	0.420	-75.4%
Bioresponse	1,776	Relative MSE	0.073	0.285	无法运行	-74.4%

消融实验¶

下表汇总了代理类选择、残差 MSR 调整策略以及树参数配置在不同预算与维度下的消融分析（以 Relative MSE 为评估基准）：

配置 / 变体	核心指标表现	说明
ProxySHAP (XGBoost 默认)	基准 (Cancer MSE = 0.021)	兼顾拟合精度与通用性，二阶交互表现稳定
线性代理 ProxySHAP (Linear)	低维极低，高维剧增	在低维简单博弈极快且精准，但高维特征基数爆炸无法拟合
+ MSR 残差调整 (低维 $n < 30$)	MSE 下降 35% ~ 60%	成功消除代理偏差，理论一致性带来显著增益
+ MSR 残差调整 (高维 $n > 60$ 或 3 阶)	MSE 反弹上升 150%+	符合定理 3.3 预言，方差按 $n^{k-1}/\\|\mathcal{T}\\|$ 爆炸淹没校正收益
XGBoost HPO-Informed (浅树 2000 棵)	1000+ 特征场景下 MSE 下降 42%	在 HivaAgnostic 与 Bioresponse 等千维特征上大幅刷新基准
样本复用模式（全共享 vs 互斥切分）	共享样本 MSE 降低约 28%	复用同一采样集同时拟合代理与残差优于强行划分样本池

关键发现¶

预算双区间全面领先：以往低预算由 ProxySPEX 占优，高预算则由 KernelSHAP-IQ 占优；ProxySHAP 凭借极高样本效率和精准提取，首次在极小预算（$10^2 \sim 10^3$）与充裕预算（$10^4 \sim 10^5$）全区间均刷新了最低相对均方误差记录。
MSR 残差调整的边界法则：对于一阶 Shapley 值，MSR 几乎总是正向收益；但对于二阶交互，仅在特征数 $\le 30$ 或预算充裕时有效；在三阶及以上交互中，强行引入 MSR 会由于方差激增恶化估计质量。
真实下游任务保真度突破：在 MS COCO 数据集的 CLIP (ViT-16 / ViT-32) 跨模态解释任务（FIxLIP 设定）中，ProxySHAP 在插入/删除曲线下面积（AID）和解释拟合优度 $R^2$ 均达成帕累托最优，以更少采样预算实现了高保真的多模态图文对齐解释。

亮点与洞察¶

多项式时间闭式提取取代傅里叶级数展开：将介入式树结构遍历与 Möbius 指示博弈表示相结合，把树系综交互提取从指数级复杂度 $\mathcal{O}(4^d)$ 彻底降至 $\mathcal{O}(n_{\text{nodes}} \cdot |\mathcal{S}|)$，消除了繁琐且易损精度的傅里叶截断过程。
严密刻画 MSR 方差的阶数敏感性：不仅给出了基数概率交互指数在杠杆采样下的方差严密渐近上下界 $\mathcal{O}(n^{k-1}/|\mathcal{T}|)$，还以此指导了自适应调整策略，提供了理论驱动的落地准则。
高阶可解释性技术通用性：该方法完全兼容 Shapley、Banzhaf、Chaining 等各类主流基数概率交互指数，并无缝集成至 shapiq 库，为科学计算（材料分子、基因分析）与多模态大模型提供了即插即用的分析工具。

局限与展望¶

代理模型依赖性与调优开销：交互估计质量高度依赖于代理模型对黑盒博弈曲面的拟合能力。尽管 HPO-Informed 提供了良好默认参数，但面对极度复杂激进的非线性博弈，全量贝叶斯超参数调优的计算开销仍相对较高。
高阶高维下的无偏残差校正瓶颈：当维度 $n$ 与阶数 $k$ 共同增大时，MSR 方差发散阻碍了残差调整的应用。如何设计一种具备方差缩减（Variance Reduction）或软约束收缩的新型残差校正器，是未来值得探索的开放问题。
更广义博弈形式的扩展：当前框架主要聚焦于二值子集评估游戏，未来可进一步拓展到连续特征微扰博弈以及特征分组结构博弈（Generalized Values）。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙融合介入式树展开与残差博弈理论，推导了严格闭式解与方差上下界。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖 47 个跨领域数据集、多模态 CLIP 任务以及千维特征极限扩展，对比完备。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰优美，动机明确，方法架构与实验逻辑环环相扣。
价值: ⭐⭐⭐⭐⭐ 突破了复杂大模型高阶依赖性量化的计算瓶颈，推动可解释性进入高阶细粒度分析时代。