ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes
Abstract
Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations. Recently, ShaplEIG has shown that adaptively selecting the coalitions to evaluate substantially improves sample efficiency over classical estimators. This, however, comes at the cost of a sequential procedure that, in every iteration, refits a Gaussian process surrogate of the game and selects the coalition with the largest expected information gain about the Shapley values. The resulting computational overhead limits its applicability to costly games with low evaluation budgets. We present fast adaptive Shapley value estimation with Odd Gaussian Processes (ShapleyOG) to overcome this limitation. ShapleyOG leverages the fact that Shapley values depend only on the odd component of the game, and we show that under paired sampling a Gaussian process surrogate on this component alone yields the same Shapley value posterior and coalition selection criterion from half as many observations. Moreover, ShapleyOG refits the surrogate only on a sparse schedule and efficiently updates the selection criterion in between, and it extends quadrature-based computation schemes to the prior covariance of the Shapley values, which allows for exact or cheaper approximate computation. In extensive experiments on diverse games, ShapleyOG matches the estimation accuracy of ShaplEIG while reducing its overhead by up to three orders of magnitude. As a result, it outperforms state-of-the-art non-adaptive estimators at equal total computation time already when a single evaluation takes a tenth of a second and a budget of a few thousand evaluations suffices, thereby widening the regime in which adaptive coalition selection is applicable and pays off.
Related
- Bayesian Estimation of Continuous Brain Connectivity with Log-Gaussian Cox Processes
- Adaptive multi-resolution Gaussian processes: Scalable exact inference with naturally data-sparse covariance matrices
- Sharp Asymptotic Theory of Maximum Likelihood Estimation for Gaussian Processes with an RBF Kernel
- Finite-Rank Logistic Gaussian Processes with Exact Likelihood for Conditional Density Estimation
- Causal adaptive intensity estimation for non-stationary point processes: a Kalman-kernel duality framework
BibTeX
@misc{rundel2026shapleyog,
title = {{ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes}},
author = {David Rundel and R. Teal Witter and Santo M. A. R. Thies and Matthias Feurer and Fabian Fumagalli and Bernd Bischl},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07173},
eprint = {2611.07173},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07173},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes
AU - David Rundel
AU - R. Teal Witter
AU - Santo M. A. R. Thies
AU - Matthias Feurer
AU - Fabian Fumagalli
AU - Bernd Bischl
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.07173
UR - https://arxiv.org/abs/2611.07173
AB - Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations. Recently, ShaplEIG has shown that adaptively selecting the coalitions to evaluate substantially improves sample efficiency over classical estimators. This, however, comes at the cost of a sequential procedure that, in every iteration, refits a Gaussian process surrogate of the game and selects the coalition with the largest expected information gain about the Shapley values. The resulting computational overhead limits its applicability to costly games with low evaluation budgets. We present fast adaptive Shapley value estimation with Odd Gaussian Processes (ShapleyOG) to overcome this limitation. ShapleyOG leverages the fact that Shapley values depend only on the odd component of the game, and we show that under paired sampling a Gaussian process surrogate on this component alone yields the same Shapley value posterior and coalition selection criterion from half as many observations. Moreover, ShapleyOG refits the surrogate only on a sparse schedule and efficiently updates the selection criterion in between, and it extends quadrature-based computation schemes to the prior covariance of the Shapley values, which allows for exact or cheaper approximate computation. In extensive experiments on diverse games, ShapleyOG matches the estimation accuracy of ShaplEIG while reducing its overhead by up to three orders of magnitude. As a result, it outperforms state-of-the-art non-adaptive estimators at equal total computation time already when a single evaluation takes a tenth of a second and a budget of a few thousand evaluations suffices, thereby widening the regime in which adaptive coalition selection is applicable and pays off.
ER -