Research map / Learning theory and algorithms / Prediction and decision losses

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

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Shapley value attribution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes PKeX-Shapley, which uses a neutral-factor removal operator for product kernels to compute exact Shapley values for all d features in O(d^2 n) time, extended to MMD and HSIC attributions.

Problem

Exact Shapley value computation for kernel models is exponential in the number of features, so existing methods (Kernel SHAP, RKHS-SHAP) rely on sampling-based approximations with estimation error that grows with dimension.

Approach

For product kernels, removing a feature replaces its kernel factor with 1, giving a parameter-free, distribution-free value function with a closed-form functional decomposition; Newton's identities and prefix-suffix elementary symmetric polynomial recursions then yield all Shapley values jointly in O(d^2 n) time.

Key results

• Regression-based Kernel SHAP-style estimator still has relative error above 9.0 at d=50 with 200 coalitions and only approaches 0.05 at 10^5 samples, while PKeX-Shapley is exact.
• PKeX-Shapley computes all Shapley values in slightly over two seconds per instance, versus roughly 30 seconds for sampling-based methods at 500 coalitions.
• Brute-force exact computation reaches only 20 features in 20 s, while PKeX-Shapley scales to 1,000 features.

Surprising findings

• Interpolation-based ESP recovery (as in TreeSHAP) becomes numerically unstable already around d≈50 for product-kernel methods, motivating the element-wise recursion.

Limitations

• Applies only to product kernels, not general kernels.
• Not extended to higher-order Shapley interaction indices in this work.

Experimental setup

Datasets: synthetic regression data (linear, polynomial, squared-exponential targets) synthetic two-sample MMD data

Benchmarks: synthetic regression tasks with 17 active features in R^50 synthetic MMD two-sample experiment

Metrics: relative estimation error vs exact Shapley values recovery rate of active features per-instance execution time

Baselines: Kernel SHAP RKHS-SHAP GEMFIX BiSHAP Sampling SHAP

Builds on: Kernel SHAP RKHS-SHAP TreeSHAP canonical additive decomposition

Closest papers by meaning

• A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.90)
• Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.88)
• Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (NeurIPS 2025 · similarity 0.86)
• shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
• DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.85)
• OperatorSHAP: Fast and Accurate Shapley Value Estimation for Neural Operators (NeurIPS 2026 · similarity 0.85)