Amortized Linear-time Exact Shapley Value for Product-Kernel Methods¶
会议: NeurIPS 2026
arXiv: 2505.16516
代码: https://anonymous.4open.science/r/PKeX-Shapley-B1C0/
领域: 可解释性
关键词: 夏普利值、乘积核方法、初等对称多项式、可解释性、统计差异解释
一句话总结¶
本文提出 PKeX-Shapley 算法，针对乘积核方法建立无分布假设的中性因子移除算子，并利用前缀-后缀初等对称多项式递推结构，在 \(\mathcal{O}(d^2 n)\) 总时间内联合求解全部 \(d\) 个特征的精确 Shapley 值（单特征均摊线性时间），同时无缝拓展至 MMD 与 HSIC 统计差异归因。
研究背景与动机¶
核方法因其在再生核希尔伯特空间（RKHS）中强大的非线性建模能力和严格的统计理论基础，广泛应用于分类、回归、双样本检验以及独立性检验等高可靠性任务中。然而，核决策函数对高维输入非线性映射的黑箱属性，严重阻碍了其在关键决策场景下的透明度审计。基于合作博弈论的 Shapley 值凭借其完备的公理化性质（效率性、对称性、虚拟玩家性与线性度），成为特征归因分析的黄金标准。
但在机器学习实践中，为特征子集构建恰当的效用函数（value function）以及计算 Shapley 值面临双重维数灾难。一方面，传统干预式或观测式效用函数严重依赖背景数据集的边缘分布采样或条件密度估计，引入了沉重的经验采样方差和分布假设偏差；即便是专门面向核方法的 RKHS-SHAP，也依然依赖蒙特卡洛子集回归近似。另一方面，若进行精确计算，需要遍历全体 \(2^d\) 个特征子集联盟，当特征维度 \(d\) 超过 20 时，暴力计算在算力上完全不可行，而常用的核回归采样逼近在高维场景下又会产生难以接受的估计误差。
乘积核（Product Kernels，如各项同性/异性 RBF 核、Laplacian 核、Cauchy 核）在机器学习中极其普及且具备万能逼近性质（Universal Kernels）。本文洞察到乘积核天然具有跨维度的因子分解代数结构，为打破指数级计算复杂度和消除背景数据采样依赖提供了根本突破口。核心 idea：利用乘积核特有的因子独立性定义无参中性特征移除算子，诱导出封闭形式的功能分解效用函数，并通过前缀-后缀生成多项式动态规划共享跨特征初等对称多项式中间态，实现全部 \(d\) 维精确 Shapley 值的均摊线性时间联合求解。
方法详解¶
整体框架¶
PKeX-Shapley 面向形如 \(f(\boldsymbol{x}) = \sum_{i=1}^n \alpha_i k(\mathbf{X}^{(i)}, \boldsymbol{x})\) 的乘积核学习机（如支持向量机、核岭回归或高斯过程均值）。整个归因流程分为三个阶段：首先，利用乘积核中性因子特征移除算子建立无须采样的参数无关效用函数，证明其满足规范加性分解（Canonical Additive Decomposition）；其次，将单特征边际贡献转化为初等对称多项式（Elementary Symmetric Polynomials, ESP）加权和；最后，构建前缀与后缀生成多项式的双向递推缓存表，在 \(\mathcal{O}(d^2 n)\) 复杂度内联合结算所有 \(d\) 个特征的精确贡献。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入样本与核机权重<br/>测试点 x, 训练集 X, 权重向量 α"] --> B["中性因子特征移除算子<br/>构建单维核向量 z_i = k_i(X_i, x_i)"]
B --> C["前缀生成多项式前向递推<br/>构建前缀系数表 Γ_j,t"]
B --> D["后缀加权多项式后向递推<br/>构建后缀聚合表 G_j,t"]
C --> E["前缀-后缀双向聚合<br/>对偶点乘 sum_t Γ_j-1,t ⊙ G_j+1,t"]
D --> E
E --> F["均摊线性时间输出全部特征 Shapley 值<br/>单特征 O(dn)，全部 d 维仅需 O(d^2 n)"]关键设计¶
1. 中性因子特征移除算子与封闭加性功能分解
传统 Shapley 归因在模拟特征缺失时，通常采用边缘替换（interventional）或条件期望（observational），引入了对背景数据分布的强假设和繁重的蒙特卡洛积分。针对乘积核 \(k(\boldsymbol{x}, \boldsymbol{x}') = \prod_{j \in \mathcal{D}} k_j(x_j, x'_j)\) 的代数结构，本文定义了规范的中性因子移除算子：移除特征子集 \(\mathcal{T}\) 等价于将其对应的单维核因子替换为乘法单位元 \(1\)（即 \(k_j \mapsto 1, \forall j \in \mathcal{T}\)）。根据 Gevaert & Saeys 的功能分解理论，该移除算子在子集格上经由 Möbius 反演，唯一确定了模型的规范加性分解分量 \(f_{\mathcal{S}}(\boldsymbol{x}_{\mathcal{S}}) = \sum_{i=1}^n \alpha_i \prod_{j \in \mathcal{S}} (k_j(x_j, X_{i,j}) - 1)\)。由此诱导出的特征联盟效用函数具有极其优美且精确的封闭形式： $\(v_{\boldsymbol{x}}(\mathcal{S}) = \boldsymbol{\alpha}^\top k_{\mathcal{S}}(\mathbf{X}_{\mathcal{S}}, \boldsymbol{x}_{\mathcal{S}}) - f_\emptyset\)$ 其中常数基线项 \(f_\emptyset = \sum_{i=1}^n \alpha_i\) 在任意边际贡献 \(v_{\boldsymbol{x}}(\mathcal{S} \cup \{j\}) - v_{\boldsymbol{x}}(\mathcal{S})\) 中恒等相消。该效用函数完全摆脱了背景数据集和概率密度估计，能在 \(\mathcal{O}(|\mathcal{S}| \cdot n)\) 时间内完成精确评估。
2. 基于牛顿恒等式的单特征边际贡献多项式化表征
在上述效用函数下，特征 \(j\) 加入联盟 \(\mathcal{S}\) 产生的边际贡献可以直接提出因子 \((k_j(\mathbf{X}_j, x_j) - \mathbf{1})\)，从而将其对所有子集的加权和分解为初等对称多项式问题。记 \(\boldsymbol{z}_i = k_i(\mathbf{X}_i, x_i) \in \mathbb{R}^n\)，集合 \(\mathcal{Z}_{-j} = \{\boldsymbol{z}_1, \dots, \boldsymbol{z}_d\} \setminus \{\boldsymbol{z}_j\}\)。联盟基数固定为 \(q\) 的核张量和即为 \(q\) 阶初等对称多项式 \(e_q(\mathcal{Z}_{-j}) = \sum_{\mathcal{S} \subseteq \mathcal{D} \setminus \{j\}, |\mathcal{S}|=q} \bigodot_{i \in \mathcal{S}} \boldsymbol{z}_i\)。利用经典的牛顿恒等式（Newton's Identities），\(e_q\) 可由逐元素幂和向量 \(p_r(\mathcal{Z}_{-j}) = \sum_{\boldsymbol{z} \in \mathcal{Z}_{-j}} \boldsymbol{z}^r\) 递推计算： $\(e_q(\mathcal{Z}_{-j}) = \frac{1}{q} \sum_{r=1}^q (-1)^{r-1} e_{q-r}(\mathcal{Z}_{-j}) \odot p_r(\mathcal{Z}_{-j})\)$ 由此，特征 \(j\) 的 Shapley 值被精确表征为： $\(\phi_j^{\boldsymbol{x}} = \boldsymbol{\alpha}^\top \left( (\boldsymbol{z}_j - \mathbf{1}) \odot \sum_{q=0}^{d-1} \mu(q) e_q(\mathcal{Z}_{-j}) \right)\)$ 其中 Shapley 组合权重为 \(\mu(q) = \frac{q!(d-q-1)!}{d!}\)。该形式将单个特征的精确 Shapley 计算时间由指数级 \(\mathcal{O}(2^d n)\) 骤降至二次方 \(\mathcal{O}(d^2 n)\)。
3. 前缀-后缀双向动态规划与均摊线性时间加速
若对每个特征 \(j \in \{1,\dots,d\}\) 独立应用单特征牛顿递推，计算全部 \(d\) 个特征仍需 \(\mathcal{O}(d^3 n)\) 复杂度，且忽略了不同特征在留一子集 \(\mathcal{Z}_{-j}\) 中包含的大量重叠中间量。为此，论文引入生成多项式理论：定义前缀多项式 \(p_{j-1}^{\mathrm{pref}}(s) = \bigodot_{i=1}^{j-1} (\mathbf{1} + \boldsymbol{z}_i s) = \sum_{t=0}^{j-1} \mathbf{\Gamma}_{j-1,t} s^t\)，以及后缀多项式 \(p_{j+1}^{\mathrm{suf}}(s) = \bigodot_{i=j+1}^d (\mathbf{1} + \boldsymbol{z}_i s) = \sum_{u=0}^{d-j} \mathbf{R}_{j+1,u} s^u\)。留一生成多项式天然因式分解为 \(p_{-j}(s) = p_{j-1}^{\mathrm{pref}}(s) \odot p_{j+1}^{\mathrm{suf}}(s)\)。通过预先将 Shapley 组合权重吸纳进后缀多项式，定义后向聚合张量 \(\mathbf{G}_{j+1,t} = \sum_{u=0}^{d-j} \mu(t+u) \mathbf{R}_{j+1,u}\)，加权 ESP 和即可化简为对偶点乘： $\(\sum_{q=0}^{d-1} \mu(q) e_q(\mathcal{Z}_{-j}) = \sum_{t=0}^{j-1} \mathbf{\Gamma}_{j-1,t} \odot \mathbf{G}_{j+1,t}\)$ 前缀系数表与后缀聚合表分别遵循极为简洁的前向与后向递推： $\(\mathbf{\Gamma}_{j,t} = \mathbf{\Gamma}_{j-1,t} + \boldsymbol{z}_j \odot \mathbf{\Gamma}_{j-1,t-1}, \quad j = 1,\dots,d\)$ $\(\mathbf{G}_{j,t} = \mathbf{G}_{j+1,t} + \boldsymbol{z}_j \odot \mathbf{G}_{j+1,t+1}, \quad j = d,\dots,1\)$ 构建两个尺寸为 \(d \times d \times n\) 的缓存表耗时 \(\mathcal{O}(d^2 n)\)，查表结算单个特征仅需 \(\mathcal{O}(dn)\) 向量运算。全部 \(d\) 个特征的总计算复杂度因而被彻底压缩至 \(\mathcal{O}(d^2 n)\)，实现了单特征均摊线性时间（Amortized Linear Time）。更重要的是，全过程仅包含加法与点乘，规避了类似 TreeSHAP 插值除法或 FFT/Chebyshev 频域反演中在阶数 \(d > 40\) 时必然爆发的浮点下溢与条件数灾难。
4. 统计度量与相关性分析的理论拓展（MMD 与 HSIC）
除监督预测模型外，该框架被无缝拓展至两类核心的无参数统计判别准则： - 最大均值差异（MMD）：用于衡量两样本分布 \(\mathbb{P}\) 与 \(\mathbb{Q}\) 的相异程度。通过设定特征移除算子 \(k_q \mapsto 1\)，建立 MMD 的子集分解，其边际贡献同样被因式分解为 \((k_q(x_q, x'_q) - 1)\) 与其余特征初等对称多项式的乘积，推导出精确 Shapley 归因 \(\phi_q^{\mathrm{MMD}}\)，使研究者能够清晰定位拉大两样本分布差异的主导变量。 - 希尔伯特-施密特独立性指标（HSIC）：用于度量多维输入 \(X\) 与目标 \(Y\) 的统计相关性 \(\mathrm{tr}(\mathbf{K}\mathbf{H}\mathbf{L}\mathbf{H}) / (n-1)^2\)。乘积核使得矩阵 \(\mathbf{K} = \bigodot_{j=1}^d \mathbf{K}_j\)。将特征移除定义为矩阵级乘法单位元 \(\mathbf{K}_j \mapsto \mathbf{1}\mathbf{1}^\top\)，推导得出完全对称的递归表达式 \(\phi_j^{\mathrm{HSIC}} = \frac{1}{(n-1)^2} \mathrm{tr}\left( \mathbf{H}\mathbf{L}\mathbf{H} \left( (\mathbf{K}_j - \mathbf{1}\mathbf{1}^\top) \odot \sum_{q=0}^{d-1} \mu(q) E_q(\mathcal{K}_{-j}) \right) \right)\)，为基于全局非线性依赖的高效特征选择提供了公理化工具。
一个完整示例¶
考虑一个包含 \(d=3\) 个特征的乘积核模型，测试样本为 \(\boldsymbol{x}\)，特征向量单核值为 \(\boldsymbol{z}_1, \boldsymbol{z}_2, \boldsymbol{z}_3 \in \mathbb{R}^n\)。计算流程如下： 1. 边界初始化：对于全排列维度 \(d=3\)，组合权重分别为 \(\mu(0) = \frac{0!2!}{3!} = \frac{1}{3}\)，\(\mu(1) = \frac{1!1!}{3!} = \frac{1}{6}\)，\(\mu(2) = \frac{2!0!}{3!} = \frac{1}{3}\)。初始化前缀表 \(\mathbf{\Gamma}_{0,0} = \mathbf{1}\)，后缀边界 \(\mathbf{G}_{4,t} = \mu(t) \mathbf{1}\)。 2. 前向扫描计算 \(\mathbf{\Gamma}\)： - 特征 1：\(\mathbf{\Gamma}_{1,0} = \mathbf{1}\)，\(\mathbf{\Gamma}_{1,1} = \boldsymbol{z}_1\)； - 特征 2：\(\mathbf{\Gamma}_{2,0} = \mathbf{1}\)，\(\mathbf{\Gamma}_{2,1} = \boldsymbol{z}_1 + \boldsymbol{z}_2\)，\(\mathbf{\Gamma}_{2,2} = \boldsymbol{z}_1 \odot \boldsymbol{z}_2\)。 3. 后向扫描计算 \(\mathbf{G}\)： - 特征 3：\(\mathbf{G}_{3,0} = \mu(0)\mathbf{1} + \mu(1)\boldsymbol{z}_3 = \frac{1}{3}\mathbf{1} + \frac{1}{6}\boldsymbol{z}_3\)；\(\mathbf{G}_{3,1} = \mu(1)\mathbf{1} + \mu(2)\boldsymbol{z}_3 = \frac{1}{6}\mathbf{1} + \frac{1}{3}\boldsymbol{z}_3\)； - 特征 2：\(\mathbf{G}_{2,0} = \mathbf{G}_{3,0} + \boldsymbol{z}_2 \odot \mathbf{G}_{3,1} = \frac{1}{3}\mathbf{1} + \frac{1}{6}\boldsymbol{z}_3 + \boldsymbol{z}_2 \odot (\frac{1}{6}\mathbf{1} + \frac{1}{3}\boldsymbol{z}_3)\)。 4. 结算特征 2 的 Shapley 值： - 提取前缀 \(\mathbf{\Gamma}_{1}\) 与后缀 \(\mathbf{G}_{3}\)，对阶数 \(t \in \{0, 1\}\) 执行对偶点乘： $\(\mathbf{\Gamma}_{1,0} \odot \mathbf{G}_{3,0} + \mathbf{\Gamma}_{1,1} \odot \mathbf{G}_{3,1} = \mathbf{1} \odot \left(\frac{1}{3}\mathbf{1} + \frac{1}{6}\boldsymbol{z}_3\right) + \boldsymbol{z}_1 \odot \left(\frac{1}{6}\mathbf{1} + \frac{1}{3}\boldsymbol{z}_3\right) = \frac{1}{3}\mathbf{1} + \frac{1}{6}(\boldsymbol{z}_1 + \boldsymbol{z}_3) + \frac{1}{3}\boldsymbol{z}_1 \odot \boldsymbol{z}_3\)$ - 最终精确加权边际向量为 \((\boldsymbol{z}_2 - \mathbf{1}) \odot [\frac{1}{3}\mathbf{1} + \frac{1}{6}(\boldsymbol{z}_1 + \boldsymbol{z}_3) + \frac{1}{3}\boldsymbol{z}_1 \odot \boldsymbol{z}_3]\)，内积 \(\boldsymbol{\alpha}\) 即直接输出 \(\phi_2^{\boldsymbol{x}}\)，完全避开了联盟枚举。
损失函数 / 训练策略¶
PKeX-Shapley 本身属于后验解释算法，不修改基础模型的训练目标。在实验中，基础分类/回归模型采用支持向量机（SVM）或高斯过程（GP）： - 支持向量机优化：采用 Optuna 框架进行 5 折交叉验证调优，超参数 \(C \in [10^{-5}, 10^5]\) 与 RBF 核带宽参数 \(\gamma \in [10^{-5}, 10^3]\) 均在对数均匀分布区间内搜索（共采样 100 次 trial）。 - 高斯过程回归优化：采用 \(k=5\) 折交叉验证，核函数采用常数核与 RBF 核的组合 \(C(1.0) \times \mathrm{RBF}(1.0)\)，通过最大化边缘似然估计优化带宽参数。 - 统计检验与相关性参数：MMD 与 HSIC 实验中，单维及多维 RBF 核带宽均使用中位数启发式方法（Median Heuristic）自适应选择。
实验关键数据¶
主实验¶
论文在配备 24 核 CPU 和 16GB 内存的环境下进行了系统评测。首先在数值稳定性和计算时间方面，作者在合成回归数据集（\(n=500\)）上将 PKeX-Shapley（二次动态规划）与基于根结点的 FFT 方法和 Chebyshev 插值节点方法进行了严苛对比，统计了跨特征维度 \(d \in [10, 1000]\) 的 Shapley 完备性绝对误差 \(\mathbb{E}[|\sum_{j} \phi_j - (f(x) - v(\emptyset))|]\) 以及单次解释耗时。
| 特征维度 \(d\) | PKeX-Shapley 误差 | PKeX-Shapley 耗时 (s) | FFT 误差 | FFT 耗时 (s) | Chebyshev 误差 | Chebyshev 耗时 (s) |
|---|---|---|---|---|---|---|
| \(d = 10\) | \(2.26 \times 10^{-12}\) | \(1.22 \times 10^{-3}\) | \(4.83 \times 10^{-12}\) | \(1.55 \times 10^{-3}\) | \(4.35 \times 10^{-10}\) | \(1.38 \times 10^{-3}\) |
| \(d = 20\) | \(1.14 \times 10^{-12}\) | \(2.88 \times 10^{-3}\) | \(2.07 \times 10^{-9}\) | \(4.13 \times 10^{-3}\) | \(2.61 \times 10^{-4}\) | \(2.71 \times 10^{-3}\) |
| \(d = 30\) | \(1.01 \times 10^{-12}\) | \(4.78 \times 10^{-3}\) | \(1.03 \times 10^{-6}\) | \(6.94 \times 10^{-3}\) | \(1.70 \times 10^{2}\) | \(4.52 \times 10^{-3}\) |
| \(d = 50\) | \(3.64 \times 10^{-13}\) | \(1.05 \times 10^{-2}\) | \(9.77 \times 10^{-3}\) | \(1.68 \times 10^{-2}\) | \(2.77 \times 10^{10}\) | \(9.89 \times 10^{-3}\) |
| \(d = 70\) | \(4.55 \times 10^{-13}\) | \(1.81 \times 10^{-2}\) | \(8.15 \times 10^{0}\) | \(2.97 \times 10^{-2}\) | \(2.99 \times 10^{16}\) | \(1.79 \times 10^{-2}\) |
| \(d = 100\) | \(1.07 \times 10^{-12}\) | \(3.38 \times 10^{-2}\) | \(5.28 \times 10^{7}\) | \(5.55 \times 10^{-2}\) | \(1.53 \times 10^{22}\) | \(3.20 \times 10^{-2}\) |
| \(d = 200\) | \(5.46 \times 10^{-13}\) | \(1.18 \times 10^{-1}\) | \(8.60 \times 10^{27}\) | \(2.19 \times 10^{-1}\) | \(3.93 \times 10^{45}\) | \(1.15 \times 10^{-1}\) |
| \(d = 500\) | \(2.50 \times 10^{-13}\) | \(6.98 \times 10^{-1}\) | \(3.57 \times 10^{85}\) | \(1.71 \times 10^{0}\) | \(1.10 \times 10^{102}\) | \(9.61 \times 10^{-1}\) |
| \(d = 1000\) | \(1.73 \times 10^{-12}\) | \(2.65 \times 10^{0}\) | \(2.90 \times 10^{183}\) | \(1.36 \times 10^{1}\) | \(3.72 \times 10^{199}\) | \(3.75 \times 10^{0}\) |
消融与下游任务验证¶
在全局特征选择任务中，论文将基于 PKeX-Shapley 的 HSIC 归因排名前 20% 的特征作为子集，重新训练高斯过程模型，并在 7 个标准基准数据集上与专业特征选择算法对比（5折交叉验证）。分类任务指标为准确率（Accuracy \(\uparrow\)），回归任务指标为平均绝对百分比误差（MAPE \(\downarrow\)）。
| 方法 | sonar (Acc \(\uparrow\)) | Wisconsin (Acc \(\uparrow\)) | ionosphere (Acc \(\uparrow\)) | breast cancer (MAPE \(\downarrow\)) | skillcraft (MAPE \(\downarrow\)) | sml (MAPE \(\downarrow\)) | parkinson (MAPE \(\downarrow\)) |
|---|---|---|---|---|---|---|---|
| PKeX-Shapley | \(0.808 \pm 0.030\) | \(\mathbf{0.909 \pm 0.015}\) | \(0.878 \pm 0.036\) | \(\mathbf{0.850 \pm 0.010}\) | \(\mathbf{1.000 \pm 0.020}\) | \(0.999 \pm 0.001\) | \(\mathbf{0.125 \pm 0.022}\) |
| HSICLasso | \(0.808 \pm 0.044\) | \(0.884 \pm 0.010\) | \(0.912 \pm 0.035\) | \(1.000 \pm 0.080\) | \(2.175 \pm 0.429\) | \(1.354 \pm 0.726\) | \(1.170 \pm 0.269\) |
| Mutual Info (MI) | \(\mathbf{0.875 \pm 0.053}\) | \(0.900 \pm 0.015\) | \(\mathbf{0.937 \pm 0.023}\) | \(1.000 \pm 0.080\) | \(1.134 \pm 0.099\) | \(\mathbf{0.196 \pm 0.071}\) | \(0.214 \pm 0.004\) |
| Lasso | \(0.842 \pm 0.038\) | \(0.900 \pm 0.024\) | \(0.932 \pm 0.021\) | \(1.000 \pm 0.080\) | \(1.821 \pm 0.680\) | \(1.000 \pm 0.000\) | \(1.000 \pm 0.000\) |
| K-Best | \(0.779 \pm 0.040\) | \(\mathbf{0.909 \pm 0.015}\) | \(0.869 \pm 0.018\) | \(1.000 \pm 0.080\) | \(1.134 \pm 0.099\) | \(0.257 \pm 0.086\) | \(1.018 \pm 0.076\) |
| Tree Ensemble | \(0.837 \pm 0.059\) | \(0.887 \pm 0.033\) | \(0.926 \pm 0.031\) | \(1.000 \pm 0.080\) | \(2.175 \pm 0.429\) | \(1.000 \pm 0.000\) | \(0.214 \pm 0.004\) |
关键发现¶
- 数值稳定性断崖：虽然 FFT 和 Chebyshev 插值方法在低维（\(d \le 20\)）时能维持较高精度，但在中高维场景下（\(d \ge 50\)）误差呈现爆炸式增长（误差达到 \(10^{10} \sim 10^{199}\)），这是由多项式阶数高达 \(d-1\) 时 Vandermonde 矩阵条件数恶化及复数相位交替抵消引起的；而 PKeX-Shapley 全程保持纯加法和乘法递推，在 \(d=1000\) 下依然保持 \(1.73 \times 10^{-12}\) 的极高数值精度。
- 与采样估计相比的压倒性速度优势：在 50 维非线性合成任务中，Kernel SHAP、RKHS-SHAP、GEMFIX 等采样方法在仅仅使用 500 个联盟采样点时单样本耗时即达约 30 秒，且特征恢复率随目标函数非线性阶数增加显著衰减；PKeX-Shapley 单样本全精确计算仅耗时约 2 秒，兼备精确性与高吞吐。
- 真实特征选择优势：在 7 个基准数据集中，PKeX-Shapley 在 5 个数据集上击败了专为特征选择设计的经典强基线 HSICLasso，并在回归任务上展现出显著更低的预测方差。
亮点与洞察¶
- 用代数结构化解公理化难题：传统观点认为核方法的连续非线性使得精确 Shapley 值不可解，本文巧妙抓住乘积核在乘法中性元（1）上的自然契合点，构建了完全脱离数据采样的参数无关效用函数，在理论上将核方法解释与 ANOVA 功能分解严密统一。
- 对偶生成多项式的均摊技巧：通过将组合权重 \(\mu(q)\) 预先折叠进后缀聚合表，巧妙将 \(d\) 个留一子集的组合拆分转换为前缀表与后缀表的对偶点积，化解了多项式除法带来的数值奇点问题，将时间复杂度从原本每特征 \(\mathcal{O}(d^2 n)\) 均摊为全体 \(\mathcal{O}(d^2 n)\)。
- 从个体预测向统计判别的跨越：将特征移除算子推广至两样本检验 MMD 和相关性准则 HSIC，使经典假设检验与全局因果探索具备了逐变量归因能力，可直接用于解释协变量偏移（Covariate Shift）源头。
局限与展望¶
- 乘积核假设的绑定约束：算法高度依赖核函数的跨维度乘积分解形式（如各向异性 RBF 核、Laplacian 核），无法直接适用于含有旋转协方差矩阵的马氏距离核（Mahalanobis kernels）或非解耦图核。
- 高阶交互指数的拓展挑战：当前算法专注于一阶主效应 Shapley 值，未来向 Shapley-Taylor 交互指数或更高阶协同效应扩展时，前缀-后缀的递推结构如何推广仍待探索。
- 随机不确定性刻画的局限：与专用于 FANOVA GP 的方法相比，乘积核缺乏天然正交性，无法在多项式时间内同时闭式输出高斯过程 Shapley 值的方差与后验协方差分布。
相关工作与启发¶
- vs RKHS-SHAP (Chau et al., 2022)：RKHS-SHAP 针对通用 RKHS 利用条件核均值嵌入估计条件期望，但依然需要调用带权重的回归采样近似（类 Kernel SHAP）求解 Shapley 值；PKeX-Shapley 聚焦乘积核，给出了完全无需采样的精确封闭解，速度提升超一个数量级且无估计方差。
- vs TreeSHAP (Lundberg et al., 2020)：TreeSHAP 利用决策树的叶节点路径实现多项式时间计算，多项式阶数受限于树深度 \(D \ll d\)；在乘积核中多项式阶数高达 \(d-1\)，常规除法或插值完全失效，本文提出的双向递推为高阶对称多项式求和提供了全新的数值稳定范式。
- vs FANOVA GP (Mohammadi et al., 2026)：该工作基于函数式方差分析核求解随机归因，但仅能单特征独立求解，总体复杂度为 \(\mathcal{O}(d^3 n)\)；PKeX-Shapley 通过前缀-后缀生成多项式，将全体计算降低为 \(\mathcal{O}(d^2 n)\)。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ [首次在乘积核方法中实现无须采样的均摊线性时间精确 Shapley 值计算，代数结构挖掘极具深度]
- 实验充分度: ⭐⭐⭐⭐⭐ [涵盖千维极限数值稳定性验证、50维非线性特征恢复、MMD双样本差异归因及7个真实数据集特征选择]
- 写作质量: ⭐⭐⭐⭐⭐ [数学推导严丝合缝，理论定理与生成多项式递推表述清晰透明]
- 价值: ⭐⭐⭐⭐⭐ [彻底解决了高维核方法长期以来的精确归因算力瓶颈，开源代码易用性高]