技术摘要：QuadraSHAP

问题陈述

Shapley 值是解释机器学习预测的基础工具，它基于合作博弈论提供特征归因。然而，精确计算通常难以处理，需要评估指数级数量的特征联盟（$2^{d-1}$）。虽然特定于模型的方法（如 TreeSHAP、RKHS-SHAP）利用结构特性实现了多项式时间复杂度，但它们往往面临数值稳定性与计算效率之间持久的权衡。

具体而言，依赖多项式插值的方法（如 Linear TreeSHAP）随着多项式次数的增加（由树深度或特征数量决定），由于范德蒙德逆矩阵的病态性，会遭受快速的数值不稳定性。相反，代数递归方法（例如针对乘积核模型）提供了稳定性，但会产生显著更高的算术成本。本文旨在解决一种方法的需求，该方法对于表现出乘积结构的广泛模型类别，能够同时具备精确（或近似精确）、数值稳定和计算高效的特性。

方法论

本文介绍了QuadraSHAP，一种用于计算乘积博弈（product games）Shapley 值的方法。在乘积博弈中，联盟价值分解为每个玩家项的乘积（$v(S) = \prod_{j \in S} u_j$）。这种结构自然地出现在基于树的模型和具有乘积核的核方法中。

1. 积分表示

核心理论贡献是将乘积博弈的 Shapley 值从对 $2^{d-1}$ 个子集的加权和重述为精确的一维积分。通过利用 Shapley 权重的 Beta 函数表示，作者推导出：
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
这一变换消除了对子集枚举或基于插值的系数恢复的需求。

2. 高斯 - 勒让德求积

该积分使用高斯 - 勒让德求积进行计算。

• 精确性：如果求积节点数 $m_q$ 满足 $m_q \ge \lceil d/2 \rceil$，该方法可恢复精确的 Shapley 值。
• 近似性：如果 $m_q < \lceil d/2 \rceil$，该方法提供近似精确的近似值。已证明误差随 $m_q$ 几何级数衰减，具体界限为 $O(\rho^{-2m_q})$，其中 $\rho > 1$ 为伯恩斯坦椭圆参数。经验表明，即使对于数千个特征，仅需数百个节点即可实现高精度估计，远低于理论精确性阈值。

3. 数值稳定且高效的实现

为了解决实际计算挑战，作者提出了特定的算法优化：

• 对数空间评估：为防止高维下的溢出和下溢，乘积在对数空间中评估，并显式跟踪符号。估计量计算如下：
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  其中 $P_q$ 是项的完整乘积，$T_{q,i}$ 是特征 $i$ 的项。
• 共享计算：不再为每个特征重新计算“留一”乘积，而是先计算一次完整乘积，然后除以特征 $i$ 的特定因子。这将复杂度从 $O(d^2 m_q)$ 降低至$O(d m_q)$。
• 并行化：计算利用关联扫描原语（前缀和）在$O(\log d)$并行时间内完成对数空间归约。

主要贡献

1. 精确积分公式：本文确立了乘积博弈的 Shapley 值具有精确的积分表示，从而能够使用高斯 - 勒让德求积。
2. 稳定性与效率：QuadraSHAP 解决了稳定性与效率之间的权衡。它避免了基于插值的方法（如 Linear TreeSHAP）的数值不稳定性，同时比针对乘积核模型的代数递归方法快得多。
3. 理论保证：该方法为 $m_q \ge \lceil d/2 \rceil$ 提供了可证明的精确性，并为近似区域提供了几何收敛界限。
4. 可扩展算法：作者推导出了具有 $O(d m_q)$ 顺序工作量和 $O(\log d)$ 并行时间的算法，使该方法能够扩展到高维问题（数千个特征）。

实验结果

作者在合成数据集和真实世界数据集上将 QuadraSHAP 与最先进的基础方法（TreeSHAP、Linear TreeSHAP、FastTreeSHAP、shapiq 和 PKeX-Shapley）进行了评估。

• 树集成：
  • 速度：QuadraSHAP 是所有测试配置中最快的数值稳定方法。在大型集成（$10^5$ 个叶子节点）上，其性能比 TreeSHAP 快 3–5 倍，比 FastTreeSHAP 快 2–2.7 倍。
  • 稳定性：在深层树场景（深度高达 100）中，Linear TreeSHAP 和 TreeSHAP 等竞争对手表现出对 Shapley 效率公理的灾难性违反（误差达到 $10^{186}$ 或更高）。QuadraSHAP 保持在浮点限制水平的精度（$\sim 10^{-13}$）。
• 乘积核方法：
  • 可扩展性：对于具有乘积核的核岭回归，QuadraSHAP 比当前的精确基准（PKeX-Shapley）快一个数量级。
  • 高维：当特征维度 $d \ge 2000$ 时，PKeX-Shapley 超时（300 秒限制），而 QuadraSHAP 在几秒钟内完成解释（例如，$d=5000$ 时为 7.6 秒）。
• 近似质量：实验证实，近似误差随节点数 $m_q$ 几何级数衰减。对于 $d=5000$，仅使用 400 个节点（远低于 2500 的精确性阈值）即可实现接近机器精度的准确性。

意义与主张

本文主张 QuadraSHAP 为具有乘积结构的模型提供了一种统一、稳健的特征归因框架。通过利用积分表示和高斯 - 勒让德求积，它实现了：

• 数值鲁棒性：它在基于插值的方法失效的高维和深层树设置中保持稳定性。
• 计算优越性：它匹配或超过了现有最快方法的速度，同时保持精确性或受控的近似性。
• 通用性：该公式在单一计算范式下统一了树集成和乘积核方法。

作者将 QuadraSHAP 定位为这些特定模型类别中最快的数值稳定方法，为复杂、高维机器学习系统的可解释性提供了实用的解决方案。