🤖 machine learning

Tractable Shapley Values and Interactions via Tensor Networks

本文介绍了 TN-SHAP，这是一种基于张量网络的方法，它通过用分解的多线性映射取代穷举联盟枚举，以多项式复杂度近似 Shapley 值和交互指数，在保持准确性的同时，实现了比现有方法显著的加速。

原作者： Farzaneh Heidari, Chao Li, Guillaume Rabusseau

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Farzaneh Heidari, Chao Li, Guillaume Rabusseau

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

想象一下你拥有一台复杂的机器（比如一个高级人工智能模型）来进行预测。你想知道：“究竟是哪些具体的旋钮和拨盘（特征）导致了这次特定的预测，以及它们是如何协同工作的？”

在人工智能领域，这被称为 Shapley 值（Shapley Values）。这是一种公平分配预测结果中各项“功劳”的方法，将功劳分配给所有的输入特征。

然而，存在一个巨大的问题：传统的方法太慢了。

旧方法：“饼干罐”问题

想象你有一个装有 50 种不同类型饼干（特征）的罐子。为了弄清楚每种饼干对最终口味的贡献程度，旧方法要求你必须品尝每一种可能的饼干组合。

如果有 10 种饼干，那就是 1,024 种组合。
如果有 50 种饼干，其组合数量比宇宙中的原子还要多（ $2^{50}$ ）。

尝试品尝每一种组合是不可能的。这需要耗费无穷的时间，所以我们通常只能靠猜测，或者随机品尝几把，但这并不准确。

新方法：TN-SHAP（“神奇食谱卡”）

这篇论文介绍了一种名为 TN-SHAP 的新方法。它不再需要品尝每一种可能的饼干组合，而是使用了一个涉及**张量网络（Tensor Networks，一种数学结构）和多项式（Polynomials，数学曲线）**的巧妙技巧。

以下是这个类比：

1. “神奇食谱卡”（代理模型）

首先，该方法为复杂的机器创建了一个简化版的、“神奇的”版本。你可以把它想象成一张食谱卡，它能完美地模拟机器的行为，但其方式非常结构化且有序。

论文称之为张量网络代理（Tensor Network Surrogate）。
它将复杂的机器分解为一系列更小的、相互连接的模块（就像一串乐高积木）。这种结构既高效又易于理解。

2. “拨盘”技巧（对角选择器）

它不再测试每一种饼干组合，而是使用了一个特殊的拨盘（一种被称为“选择矩阵”的数学工具）。

想象你有一个拨盘，可以控制每种饼干在混合物中的含量。
你将拨盘转到位置 0（没有饼干）、位置 0.5（半块饼干）、位置 1（整块饼干）等等。
因为这张“神奇食谱卡”是以一种特殊的数学方式构建的（称为“多线性”），所以转动这个拨盘会产生一条平滑的曲线（多项式），从而一次性揭示所有关于饼干如何相互作用的信息。

3. “数学侦探”（多项式插值）

它不需要品尝 1,000,000 种组合，只需要在那个拨盘曲线上寻找 50 个特定的点。

它利用这 50 个点，通过一种标准的数学技术（称为“多项式插值”）来重建整条曲线。
一旦拥有了这条曲线，它就可以瞬间计算出每块饼干（以及每一组饼干）究竟应该获得多少功劳。

为什么这意义重大？

论文声称取得了三大胜利：

速度：
- 旧方法： 耗时呈指数级增长。如果你增加一个特征，时间就会翻倍。对于 50 个特征，可能需要数年时间。
- TN-SHAP： 耗时呈线性增长。它的扩展非常平缓。对于 50 个特征，只需毫秒级。
- 结果： 论文显示，在保持相同准确度的同时，它比当前最好的方法（如 KernelSHAP-IQ）快了 25 到 1,000 倍。
准确度：
- 因为它不依赖于随机采样（Sampling），所以它能得到“神奇食谱卡”的精确答案。
- 论文证明，如果“神奇食谱卡”是真实机器的一个优秀的副本，那么解释结果将非常接近真相。
组合功劳（交互作用）：
- 它不仅能告诉你单个饼干的重要性，还能告诉你饼干组合是如何协同工作的（例如：“巧克力和香草味道很搭，但巧克力和盐的味道很糟糕”）。
- 它计算这些组合交互作用的速度与计算单个特征一样快。

局限性（代价）

论文诚实地说明了它在何处表现最佳：

局部邻域： “神奇食谱卡”是为特定区域构建的。如果你询问一个机器从未见过的饼干组合，这张卡片可能并不完美。该方法在观察特定预测及其直接邻居时效果最好。
复杂度： 如果机器极其混乱且没有结构化模式，那么“神奇食谱卡”可能需要变得非常庞大才能保证准确。然而，论文发现即使对于复杂的现实世界数据（如预测糖尿病或混凝土强度），一个相对较小的卡片也能完美运作。

总结

TN-SHAP 就像聘请了一位大师级厨师，他不需要烹饪出每一种可能的菜肴就能知道食谱。相反，他通过观察食材，利用一种特殊的数学捷径来理解风味轮廓，并能瞬间告诉你哪些食材在发挥核心作用，以及哪些食材正在协同工作。它将一个曾经需要数年才能完成的任务，缩短到了眨眼之间。

技术摘要：基于张量网络的易处理 Shapley 值与交互作用

问题陈述

通过 Shapley 值及其高阶泛化（Shapley 交互指数，SII）来解释机器学习预测，对于决策支持和可解释性至关重要。然而，对于具有 $n$ 个特征的模型，计算这些指数在计算上是极其昂贵的，因为传统方法需要枚举 $O(2^n)$ 个联盟。现有的解决方案面临着显著的权衡：

结构性假设： 如 TreeSHAP 或针对广义加性模型（GAMs）的方法，仅对特定架构（如树模型、线性模型）是精确的。
基于采样的近似： 如 KernelSHAP 或 SHAP-IQ 等方法依赖于重度采样，需要精细的方差调优，并且在面对大规模计算成本时，往往难以扩展到高阶交互作用。
摊销估计： 训练辅助模型的方法虽然可以实现，但会产生显著的训练开销，并且可能缺乏关于解释忠实度的理论保证。

核心挑战在于：如何在不进行指数级枚举或过度采样的情况下，为通用预测器计算 Shapley 值和交互作用（或以受控误差计算）。

方法论：TN-SHAP

作者提出了 TN-SHAP，该方法通过在 张量网络（Tensor Network, TN）代理模型 上进行少量评估，取代了穷举式的联盟枚举。该方法利用三个关键洞察，将复杂度从 $O(2^n)$ 降低到 $O(n \cdot \text{poly}(\chi))$ ，其中 $\chi$ 是张量网络的最大键维（bond dimension）。

1. 多线性表示与系数提取

该方法假设预测器 $f$ 可以由提升特征空间中的多线性函数 $g$ 很好地近似。在多线性展开中， $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$ ，联盟值对应于张量系数的线性组合。至关重要的是，Shapley 值仅取决于规模聚合的边际贡献（即大小为 $s$ 的联盟贡献之和），而非特定的联盟成员身份。

2. 对角选择器与多项式插值

TN-SHAP 不使用 $2^n$ 个联盟进行查询，而是使用对角选择矩阵 $S_r(t) = \text{Diag}(t, 1)$ 应用于提升后的特征 $\tilde{x}_r = [\phi(x_r), 1]^\top$ 。

通过在特征由参数 $t$ 进行缩放的点上评估代理模型 $g$ ，该方法将所有规模为 $s$ 的联盟聚合到生成的多项式 $P(t)$ 的 $t^s$ 项系数中。
具体而言，对于目标特征 $i$ ，构造一个探测函数 $G_i(t)$ ，以隔离 $i$ 在其他特征的所有子集中的边际贡献。
这将组合问题转化为多项式插值问题。通过在 $n$ 个不同点（例如切比雪夫-高斯节点）上评估 $G_i(t)$ ，系统通过求解范德蒙德线性方程组来恢复规模聚合的边际贡献 $\{m_s^{(i)}\}$ 。
然后，通过这些恢复的系数的加权和来计算 Shapley 值。

3. 张量网络代理模型

为了在大规模场景下使多线性映射的评估变得可行，该方法将系数张量分解为张量网络（TN）（例如张量列阵 Tensor Train 或层次树 Hierarchical Tree），其键维为 $\chi$ 。

特征映射： 为了处理非线性现实世界数据，标量特征在进入 TN 之前通过学习到的或手工设计的映射 $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ 进行提升。这在保持提升空间内多线性性的同时，允许代理模型建模原始输入空间中的非线性。
效率： 每次通过 TN 的前向传播成本为 $O(\text{poly}(\chi))$ 。由于插值仅需要 $O(n)$ 次评估，因此计算 $k$ 阶交互作用的总复杂度相对于 $n$ 是多项式级的。

核心贡献

统一的探测-插值方案： 一种在多线性 TN 代理模型上精确计算 Shapley 值和 $k$ 维交互作用的精确算法，仅需 $O(n)$ 次结构化前向传播，避免了 $O(2^n)$ 次查询。
特征映射增强的代理模型： 一个展示了学习到的特征提升如何保持实现精确计算所需的多线性，同时提高非线性模型代理保真度的框架。
理论保证：
- 精确性： 该方法在拟合的多线性代理模型上精确计算 Shapley 值。
- 近似误差： 相对于原始模型的误差由代理模型的最坏情况联盟近似误差（ $\epsilon$ ）界定。对于 Shapley 值， $|\phi^g_i - \phi^f_i| \leq 2\epsilon$ 。
- 可处理性： 证明了从指数级复杂度到多项式级复杂度的降低： $O(n \cdot \text{poly}(\chi) + n^2)$ 。

实验结果

作者在合成多线性函数和使用 MLP 教师模型的真实世界 UCI 回归数据集（Concrete, Diabetes, Energy）上评估了 TN-SHAP。

合成验证： 在精确的多线性函数上，TN-SHAP 实现了理论上的精确性，且运行时间处于毫秒级，比 KernelSHAP-IQ 快了数个数量级（例如，当 $n=10$ 时为 3.5ms vs 18.7ms；当 $n=50$ 时为 19.7ms vs 447.3ms）。
真实世界准确性： 在使用 MLP 教师的 UCI 数据集上：
- TN-SHAP 在达到同等准确度的情况下，实现了比 KernelSHAP-IQ 高出 25–1000 倍的墙钟加速。
- 对于一阶（ $k=1$ ）归因，TN-SHAP 与地面真值的余弦相似度接近完美（0.994）。
- 对于高阶交互作用（ $k=2, 3$ ），TN-SHAP 在保持竞争性准确度的同时，解决了基于采样的基准方法在方差或计算时间上的难题。
秩消融实验： 实验表明，当教师模型的秩为 16 时，秩为 $r=5-6$ 的学生 TN 足以恢复所有交互阶数，且 $R^2 > 0.99$ 。较低的秩会导致对高阶交互作用的欠拟合。
高维稳定性： 在高维合成设置（ $D=50, 100$ ）中，TN-SHAP 在线性成本查询预算下，保持了极高的代理保真度（ $R^2 > 0.95$ ）和强大的 Top- $k$ 特征恢复能力。

意义与主张

本文声称 TN-SHAP 弥合了 Shapley 计算的理论严谨性与实际效率需求之间的鸿沟。通过利用多线性函数的代数结构和张量网络的高效性，该方法：

将指数级的枚举问题转化为少量的结构化评估。
提供了结构性保证（通过秩界限），解决了像 LIME 这样无约束局部代理方法中常见的忠实度问题。
将局部 Shapley 解释与全局加性结构（GAMs）统一起来，因为拟合一个 $k$ 阶代理会得到与相应 GAM 项匹配的精确 $k$ -SII 系数。
为高阶交互作用提供了一种可扩展的替代方案，因为在这些场景下采样方差通常很高。

作者指出，该方法的性能取决于 TN 代理拟合的质量以及特征映射的选择，但实验结果表明，即使是适度的特征提升和张量秩也足以在实践中捕捉复杂的联盟结构。