🤖 machine learning

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

本文介绍了 Quadrature-TreeSHAP，这是一种数值稳定且与深度无关的方法，它利用高斯 - 勒让德求积法对路径依赖型 TreeSHAP 进行重构，从而能够高效计算夏普利值及高阶交互作用，并在 CPU 和 GPU 上均实现显著加速。

原作者： Ron Wettenstein, Rory Mitchell, Peng Yu

发布于 2026-05-07

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Ron Wettenstein, Rory Mitchell, Peng Yu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你拥有一台非常聪明但极其复杂的决策机器（就像一棵长出了成千上万根树枝的大树）。你想知道它究竟为何做出了某个特定的预测。它是因特征 A 而决定“是”吗？还是特征 B 与特征 C 共同协作的结果？

为了解答这个问题，数据科学家使用一种名为 SHAP 的数学工具。你可以将 SHAP 想象成一种公平分配预测“功劳”的方法，就像根据谁贡献的食材最多来分披萨一样。

长期以来，执行这一任务的标准方法（称为 TreeSHAP）存在三个主要问题：

速度慢：树长得越深，计算“功劳”所需的时间就越长。这就像试图一片一片地数完一棵巨大橡树上的所有叶子。
不稳定：随着树的深度增加，数学计算开始变得混乱且不准确，就像试图平衡一座不断摇晃的积木塔（Jenga）。
缺乏全局视角：它在解释单个特征方面表现出色，但在解释特征如何协同工作（交互作用）时，却显得非常缓慢且笨拙。

本文的作者介绍了一种名为 Quadrature-TreeSHAP 的新方法。以下是其工作原理，通过简单的类比来说明：

1. “快照”与“电影”

旧方法试图通过一步步遍历树的每一条路径来计算“功劳”。如果树很深，这需要耗费永恒的时间。

Quadrature-TreeSHAP 改变了游戏规则。它不再遍历整棵树，而是将计算视为一部电影。它意识到，树背后的数学实际上是一条平滑、可预测的曲线（多项式）。

新方法不再逐帧观看整部电影，而是对这条曲线拍摄 8 张特定的“快照”（数学上称为求积点）。

神奇之处：作者证明，对于这些树模型，仅拍摄 8 张快照 就足以完美地重构整部电影。
结果：无论树是 10 层深还是 100 层深，该方法仍然只需要这相同的 8 张快照。它完全忽略了深度，使其变得极其快速且一致。

2. “稳固的桥梁”

旧方法就像用摇晃、不平的木板搭建一座桥。随着桥变长（树更深），木板会移位，数学计算也会崩溃（数值不稳定）。

新方法使用平滑、坚固的混凝土来建造桥梁。通过在那 8 个固定点计算答案，它完全避免了“摇晃的木板”。其结果是，即使在最深、最复杂的树上，计算也能保持完美稳定。

3. “团队协作”超能力

旧方法难以解释特征如何协同工作（例如，“特征 A 和特征 B 共同导致了结果”）。这就像试图通过让人们两人一组、三人一组、四人一组排队来统计房间里的人数——速度会呈指数级变慢。

Quadrature-TreeSHAP 轻松处理这一问题。因为它对任意大小的组合都使用相同的"8 张快照”技巧，所以它可以几乎瞬间计算出复杂的团队协作交互（3 向、4 向甚至 6 向交互）。

速度：在测试中，计算这些复杂交互的速度比之前的最佳方法快了 1,200 倍。

4. “流水线”（硬件效率）

最后，作者使该方法对现代计算机芯片（CPU 和 GPU）更加友好。

类比：想象一条工厂流水线。旧方法就像一名工人，必须停下来为每一件物品单独思考。而新方法则像一台机器，能够以完美的节奏同时处理 8 件物品。
结果：由于数学规律性极强，它在普通计算机和强大的图形处理器（GPU）上都能超高效运行，在普通计算机上速度提升高达 10 倍，在图形处理器上提升 7 倍。

结果总结

作者在 12 个不同的真实世界数据集上测试了该方法（例如预测房价或识别照片中的物体）。

速度：它始终比旧方法更快，有时快达 10 倍。
稳定性：即使在旧方法失效的极深树上，它也不会崩溃或变得不准确。
应用：他们已将其集成到 XGBoost 中，这是全球最流行的机器学习工具之一。如果你未来使用 XGBoost，这种更快、更稳定的模型解释方式将直接内置其中。

简而言之：Quadrature-TreeSHAP 就像是从一台缓慢、摇晃、手动的计算器，升级为一台高速、超稳定的数字计算机，能够在眨眼间解决复杂的团队协作谜题。

技术摘要：Quadrature-TreeSHAP

问题陈述

树集成模型（如 XGBoost、随机森林）的可解释性严重依赖于 Shapley 值。尽管路径依赖 SHAP（Path-Dependent SHAP）因其高效性而成为标准方法，但现有方法在深度依赖的运行时间、数值稳定性以及对高阶交互的支持方面面临显著的权衡。

当前最先进的方法存在以下具体局限性：

TreeSHAP 和 GPUTreeSHAP 的时间复杂度为 $O(MTLD^2)$ （其中 $M$ 为样本数， $T$ 为树的数量， $L$ 为叶子节点数， $D$ 为深度）。
FastTreeSHAP v2 和 Woodelf 将复杂度降低至 $O(MTLD)$，但引入了随深度呈指数级增长的预处理步骤，使其在处理深层树时不切实际。
Linear TreeSHAP 实现了 $O(MTND)$ 的复杂度，但由于在单项式基（monomial basis）中进行运算，导致数值不稳定。
TreeGrad-Shap 通过梯度公式提高了稳定性，但仅限于一阶归因。
TreeSHAP-IQ 扩展至高阶交互，但其复杂度为 $O(MTLD \binom{F-1}{s-1})$ ，随着特征数量（ $F$ ）和交互阶数（ $s$ ）的增加，其扩展性表现不佳。

方法论

作者提出了 Quadrature-TreeSHAP，这是一种基于 Gauss–Legendre 求积法 和 加权 Banzhaf 交互多项式 的路径依赖 TreeSHAP 重构方法。

1. 理论基础

该方法利用了 Shapley 值与加权 Banzhaf 值之间的关系。

加权 Banzhaf 多项式：对于决策树的叶子节点 $v$ ，特征子集 $S$ 在包含概率 $p$ 下的路径依赖加权 Banzhaf 交互值表示为多项式 $B^{(S)}_{p,v}$ 。该多项式源自叶子节点的路径结构和边权重。
积分恢复：Shapley 交互值是通过对参与概率 $p \in [0, 1]$ 上的这些 Banzhaf 多项式进行积分来恢复的：
$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$
求积近似：作者不使用符号积分，而是利用 Gauss–Legendre 求积法来评估该积分。该积分被近似为在固定节点 $t_m$ 处评估的多项式的加权和：
$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$

2. 算法实现

定点公式：算法对树执行一次深度优先遍历（DFS）。在遍历过程中，它在一组固定的 Gauss–Legendre 节点（通常为 8 个）上传播路径多项式的值，而不是符号性地展开多项式。
复杂度降低：
- 理论上， $s$ 阶交互的被积函数次数最多为 $d-s$ （其中 $d$ 是路径上最大唯一特征数）。
- 实际上，作者证明即使是对于非常深的树，8 个固定求积点也足以达到机器精度（float32）。
- 这消除了内层计算对树深度 $d$ 的依赖，将一阶交互的有效复杂度从 $O(MTN \lceil d/2 \rceil)$ 降低至 $O(MTN) $，将$ s $阶交互的复杂度从$ O(MTN d^s) $降低至$ O(MTN d^{s-1})$。
硬件加速：由于计算涉及对每条路径评估同一组固定点，算术运算具有规律性。这使得在 CPU 上可以高效执行 SIMD（单指令多数据），在 GPU 上可以高效执行 SIMT（单指令多线程），从而消除了 GPUTreeSHAP 所需的装箱和调度开销。

主要贡献

任意阶交互算法：本文提出了一种计算任意阶 Shapley 交互值的算法，将 TreeSHAP-IQ 的最先进复杂度从 $O(MTLD \binom{F-1}{s-1})$ 改进至 $O(MTN d^s)$ 。当特征数量超过树深度（ $F > D \ge d$ ）时，这将带来显著的性能提升。
基于求积的重构：作者提供了理论和实证分析，表明 8 个 Gauss–Legendre 点足以达到 Shapley 值和交互值的机器精度，从而在实践中有效地将运行时间与树深度解耦。
数值稳定性：通过在有界的正节点上评估汇总多项式，而不是在单项式基中展开系数，该方法避免了灾难性抵消。作者声称 Quadrature-TreeSHAP 比 TreeSHAP 具有更高的数值稳定性，特别是对于深层集成模型。
硬件高效实现：该方法在 C++ 中实现以支持 CPU，并集成到 XGBoost 中以支持 GPU。它利用向量化（CPU 上 4 个点，GPU 上 32 个点）实现了相对于现有实现的显著加速。
开源集成：该实现已开源并集成到 XGBoost 库中（替换了 TreeSHAP 后端），可通过标准 API 调用（pred_contribs=True 和 pred_interactions=True）访问。

实验结果

作者在 12 个 XGBoost 基准集成（Adult、CalHousing、CovType、Fashion-MNIST）的小规模、大规模和稀疏场景下评估了 Quadrature-TreeSHAP。

一阶（Shapley 值）：
- CPU：比 TreeSHAP 快 1.06 倍至 10.59 倍（中位数 3.84 倍）。
- GPU：比 GPUTreeSHAP 快 1.84 倍至 6.95 倍。
二阶（成对交互）：
- CPU：比 TreeSHAP 快 3.80 倍至 58.11 倍（中位数 12.86 倍）。
- GPU：比 GPUTreeSHAP 快高达 6.65 倍（尽管 GPUTreeSHAP 在特定的小深度工作负载上仍具有竞争力）。
高阶交互（Python 基准测试）：
- 在与其他方法对比三阶交互时，Quadrature-TreeSHAP 比 TreeSHAP-IQ 快 18.73 倍至 26.49 倍。
- 在 CovType-sparse 数据集上，相对于 TreeSHAP-IQ 的加速比随着交互阶数的增加而增大，在 6 阶时达到 1209.37 倍。
数值稳定性：
- 在 Fashion-MNIST-sparse 基准测试中，随着树深度的增加，TreeSHAP 在深度超过 32 时变得不稳定。Quadrature-TreeSHAP 保持稳定，且使用 6–8 个点即可实现高精度。

意义

本文声称 Quadrature-TreeSHAP 提供了一种数值稳定、硬件高效且感知交互的路径依赖 SHAP 重构方法。通过将符号多项式算术转变为定点求积，该方法解决了深度依赖与数值稳定性之间的权衡。它使得在深层树上高效计算高阶交互成为可能，而这一任务此前因先前方法的指数级复杂度或不稳定性而受阻。将其集成到 XGBoost 中确保了该库用户及更广泛的 shap 包用户能够立即获得实际效用。