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

arXiv: https://arxiv.org/abs/2505.16516 · HTML: https://mlsanity.com/paper/2505.16516/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 22 May 2025.

## Builds on (most cited first, 23 of 23)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Problems with Shapley-value-based explanations as feature importance measures](https://mlsanity.com/paper/2002.11097/) (2020)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [shapiq: Shapley Interactions for Machine Learning](https://mlsanity.com/paper/2410.01649/) (2024)
- [Characteristic and Universal Tensor Product Kernels](https://mlsanity.com/paper/1708.08157/) (2017)
- [Product Kernel Interpolation for Scalable Gaussian Processes](https://mlsanity.com/paper/1802.08903/) (2018)
- [RKHS-SHAP: Shapley Values for Kernel Methods](https://mlsanity.com/paper/2110.09167/) (2021)
- [Causal Inference via Kernel Deviance Measures](https://mlsanity.com/paper/1804.04622/) (2018)
- [Explaining the Uncertain: Stochastic Shapley Values for Gaussian Process Models](https://mlsanity.com/paper/2305.15167/) (2023)
- [Credal Two-Sample Tests of Epistemic Uncertainty](https://mlsanity.com/paper/2410.12921/) (2024)
- [Explanations of Black-Box Models based on Directional Feature Interactions](https://mlsanity.com/paper/2304.07670/) (2023)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [A Unified View of Optimal Kernel Hypothesis Testing](https://mlsanity.com/paper/2503.07084/) (2025)
- [Unifying Attribution-Based Explanations Using Functional Decomposition](https://mlsanity.com/paper/2412.13623/) (2024)
- [Fast Calculation of Feature Contributions in Boosting Trees](https://mlsanity.com/paper/2407.03515/) (2024)

## Built on by (most cited first, 5 of 5)

- [Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes](https://mlsanity.com/paper/2508.14499/) (2025)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [STRIDE: Subset-Free Functional Decomposition for XAI in Tabular Settings](https://mlsanity.com/paper/2509.09070/) (2025)
- [QuadraSHAP: ε-Exact Shapley Values for Product Games in Logarithmic Parallel Time](https://mlsanity.com/paper/2605.05870/) (2026)
- [Proxy-Based Approximation of Shapley and Banzhaf Interactions](https://mlsanity.com/paper/2605.22738/) (2026)

## Abstract (arXiv)

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.