arXiv:2505.16516cs.LGcs.AI2025-05被引 5

提出快速计算核方法精确贡献值的新算法,可高效解释模型决策。

Amortized Linear-time Exact Shapley Value for Product-Kernel Methods

  • 利用乘积核结构设计无参数移除算子,实现精确分解。
  • 在 d 个特征下仅需二次时间,每个特征平均线性时间完成计算。
  • 适用于预测建模与统计检验,支持 MMD、HSIC 等可解释分析。

核方法在机器学习与统计中广泛应用,因其灵活性和表达力强,但其黑箱特性限制了高风险场景的使用。基于谢帕利值的解释方法如 SHAP 及 RKHS-SHAP 提供了可解释性框架,但精确计算谢帕利值通常不可行,现有方法依赖近似,不可避免引入估计误差。本文提出 PKeX-Shapley 算法,利用乘积核的乘法结构,实现所有 d 个特征的精确谢帕利值计算,时间复杂度为 d 的二次方。该方法基于乘积核结构内在的分布无关移除算子:移除一个特征即用乘法单位元替换其核因子。由此得到无需采样或密度估计的无参值函数,唯一确定模型的功能分解。在此基础上,我们构建共享递归形式,联合评估所有特征贡献,实现每特征的摊销线性时间计算,并保证数值稳定性。该框架还可扩展至广泛使用的基于核的差异度量,如最大均值差异(MMD)与希尔伯特-施密特独立性准则(HSIC),为可解释统计分析提供新工具。

原文摘要 · Abstract (English)

Kernel methods are widely used in machine learning and statistics for their flexibility and expressive power, yet their black-box nature limits adoption in high-stakes applications. Shapley value-based attribution methods such as SHAP, and kernel-specific adaptations including RKHS-SHAP, provide a principled framework for explainability -- but exact computation of Shapley values is generally intractable, forcing existing approaches to rely on approximations that incur unavoidable estimation error. We introduce PKeX-Shapley, an algorithm that exploits the multiplicative structure of product kernels to compute exact Shapley values for all $d$ features in quadratic time in $d$. The method rests on a distribution-free removal operator intrinsic to the product-kernel structure: removing a feature replaces its kernel factor with the multiplicative identity. This yields a parameter-free value function -- requiring no sampling and no density estimation -- and uniquely determines a functional decomposition of the model. Building on this value function, we develop shared recursive formulations that evaluate all feature attributions jointly, achieving amortized linear time per feature with numerical stability. Beyond predictive modeling, the framework extends to widely used kernel-based discrepancies such as the Maximum Mean Discrepancy (MMD) and the Hilbert-Schmidt Independence Criterion (HSIC), providing new tools for interpretable statistical analysis.

可解释性核方法谢帕利值高效算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。