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

Researchers introduce PKeX-Shapley, an algorithm that computes exact Shapley values for product-kernel machine learning models in quadratic time, eliminating the need for approximations. The method exploits the multiplicative structure of product kernels to achieve linear-time-per-feature attribution without sampling or density estimation, extending beyond predictive models to statistical discrepancy measures like MMD and HSIC.

This research addresses a fundamental challenge in explainable AI: making black-box machine learning models interpretable without computational intractability. Shapley values provide theoretically principled attribution methods that assign fair contribution scores to individual features, but exact computation traditionally requires exponential time, forcing practitioners to accept approximate solutions with inherent estimation error. PKeX-Shapley breaks this impasse by leveraging the mathematical structure unique to product kernels—a common architecture in kernel methods—enabling exact computation in polynomial time.

The innovation stems from a clever insight: in product kernels, removing a feature simply replaces its corresponding kernel factor with the multiplicative identity, creating a distribution-free value function that requires no sampling or density estimation. This structural property enables shared recursive computations across all features, achieving amortized linear time per feature while maintaining numerical stability. The extension to kernel-based discrepancies like Maximum Mean Discrepancy (MMD) and Hilbert-Schmidt Independence Criterion (HSIC) broadens applicability beyond standard classification and regression tasks.

For practitioners, this represents a substantial advancement in deploying kernel methods in high-stakes domains—finance, healthcare, criminal justice—where regulatory compliance increasingly demands model interpretability. Previously, stakeholders faced a trade-off between model accuracy (kernel methods excel here) and explainability (approximations introduced error). Exact Shapley values eliminate this compromise. The algorithm's parameter-free nature and stability properties also reduce implementation complexity and potential failure modes.

Future work likely involves extending these techniques to other kernel structures and investigating computational improvements for even larger feature dimensions, though the quadratic scaling in features may remain a practical constraint for ultra-high-dimensional problems.

• →PKeX-Shapley computes exact Shapley values for product-kernel models in quadratic time, eliminating approximation error inherent in existing methods.
• →The algorithm exploits multiplicative kernel structure to create a parameter-free value function requiring no sampling or density estimation.
• →Amortized linear-time-per-feature computation with proven numerical stability makes the method practical for real-world deployment.
• →Extension to MMD and HSIC provides interpretability tools for statistical testing and discrepancy analysis beyond predictive modeling.
• →The advancement addresses regulatory demands for explainability in high-stakes applications while preserving kernel methods' modeling accuracy.