QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918507601461248 |
|---|---|
| author | Mohammadi, Majid Reznikov, Grigory Sinitcyn, Pavel Muandet, Krikamol Chau, Siu Lun |
| author_facet | Mohammadi, Majid Reznikov, Grigory Sinitcyn, Pavel Muandet, Krikamol Chau, Siu Lun |
| contents | We study the efficient computation of Shapley values for \emph{product games} -- cooperative games in which the coalition value factorizes as a product of per-player terms. Such games arise in machine learning explainability whenever the value function inherits a multiplicative structure from the underlying model, as in kernel methods with product kernels and tree-based models. Our key result is that the Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-$(d-1)$ polynomial over $[0,1]$, where $d$ is the total number of features. This yields a Gauss--Legendre quadrature scheme that is \emph{provably exact} whenever the number of nodes satisfies $m_q \geq \lceil d/2 \rceil$, and otherwise provides a \emph{near-exact} approximation with error provably decaying geometrically in $m_q$. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, we derive a numerically stable implementation via log-space evaluation, together with an efficient parallel implementation based on associative scan primitives that achieves $O(d\,m_q)$ total work and $O(\log d)$ parallel time. Experiments show that \textsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05870 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature Mohammadi, Majid Reznikov, Grigory Sinitcyn, Pavel Muandet, Krikamol Chau, Siu Lun Machine Learning We study the efficient computation of Shapley values for \emph{product games} -- cooperative games in which the coalition value factorizes as a product of per-player terms. Such games arise in machine learning explainability whenever the value function inherits a multiplicative structure from the underlying model, as in kernel methods with product kernels and tree-based models. Our key result is that the Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-$(d-1)$ polynomial over $[0,1]$, where $d$ is the total number of features. This yields a Gauss--Legendre quadrature scheme that is \emph{provably exact} whenever the number of nodes satisfies $m_q \geq \lceil d/2 \rceil$, and otherwise provides a \emph{near-exact} approximation with error provably decaying geometrically in $m_q$. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, we derive a numerically stable implementation via log-space evaluation, together with an efficient parallel implementation based on associative scan primitives that achieves $O(d\,m_q)$ total work and $O(\log d)$ parallel time. Experiments show that \textsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations. |
| title | QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2605.05870 |