ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes
Organizations: LMU Munich · MCML · Claremont McKenna College · TU Dortmund University ·
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.
Figures & tables
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| ShaplEIG | ShapleyOG | |
|---|---|---|
| Surrogate | Full GP with constant mean on all observations | Odd GP with zero mean on the odd targets ( Section 3.1 ) |
| Hyperparameters | MAP estimate on all observations; refit in every iteration (staged schedule for large ) | MAP estimate on the odd targets; refit at , whenever is a power of two, and on the final data ( Section 3.3 ) |
| SV prior covariances | Computation via ESPs ( Section 2.3 ) | Computation via GL quadrature; exact for ( Section 3.2 ) |
| Initial design | Arbitrary | Paired |
| Candidate set | Fixed set of size provided as input; depleted over the run | Paired set of size with scored representatives, resampled at every refit ( Sections 3.3 and E.2 ) |
| Selection | One coalition per iteration; EIG of a single evaluation | One complement pair per iteration; joint EIG of both evaluations, scored via one representative ( Theorem 3 ) |
| ShaplEIG | ShapleyOG | |||
| Quantity | Size | Cost | Size | Cost |
| Step 1: kernel matrices | ||||
| (Cholesky factor of ) | ||||
| Step 2: SV prior covariances | ||||
| Quantity | ShaplEIG | ShapleyOG |
|---|---|---|
| Step 1: kernel matrices | ||
| one row and column appended, | same | |
| (Cholesky factor of ) | recomputed, | one row appended (bordered), |
| one row appended, ; one column removed | same | |
| Step 2: SV prior covariances | ||
| reused | same | |
| Dataset | Task | Model | Source | License | |
| Vision and language datasets ( Muschalik et al., 2024 ) | |||||
| Language (IMDB) | Classification | DistilBERT | 14 | shapiq / HuggingFace | Public Domain |
| ResNet18-SP | Image classification | ResNet18 | 14 | shapiq | Public Domain |
| ViT4by4 | Image classification | ViT-B | 16 | shapiq | Public Domain |
| DINOv2-16 | Image classification | DINOv2-B + linear head | 16 | ImageNet-1k val. / HuggingFace | ImageNet Terms of Access |
| Tabular datasets ( Štrumbelj & Kononenko, 2010 ; Muschalik et al., 2024 ) | |||||
| Game ( ) | ShapleyOG | OddSHAP | Regression MSR | Leverage SHAP | Kernel SHAP | Permutation | SVARM |
| Language (IMDB) (14) | 2.1e-2 | 2.5e-2 | 2.2e-2 | 2.4e-2 | 3.4e-2 | 9.6e-2 | 7.1e-2 |
| ResNet18-SP (14) | 1.8e-3 | 8.2e-3 | 6.4e-3 | 2.1e-2 | 4.5e-2 | 5.8e-2 | 5.5e-2 |
| ViT4by4 (16) | 2.5e-2 | 3.4e-2 | 3.2e-2 | 4.8e-2 | 1.3e-1 | 1.6e-1 | 1.3e-1 |
| DINOv2-16 (16) | 3.7e-2 | 3.6e-2 | 3.4e-2 | 6.9e-2 | 2.1e-1 | 1.6e-1 | 1.2e-1 |
| Forest Fires (13) | 1.1e-1 | 1.5e-1 | 1.7e-1 | 8.3e-2 | 1.3e-1 | 6.8e-1 | 1.5e-1 |
| Game ( ) | ShapleyOG | OddSHAP | Regression MSR | Leverage SHAP | Kernel SHAP | Permutation | SVARM |
| Language (IMDB) (14) | 6.0e-2 | 6.0e-2 | 5.2e-2 | 5.6e-2 | 5.7e-2 | 2.3e-1 | 8.9e-2 |
| ResNet18-SP (14) | 4.5e-3 | 1.4e-2 | 1.2e-2 | 3.2e-2 | 6.7e-2 | 1.0e-1 | 6.1e-2 |
| ViT4by4 (16) | 3.9e-2 | 4.6e-2 | 4.7e-2 | 6.3e-2 | 1.7e-1 | 2.0e-1 | 1.4e-1 |
| DINOv2-16 (16) | 7.5e-2 | 5.0e-2 | 4.3e-2 | 1.1e-1 | 3.4e-1 | 2.3e-1 | 1.3e-1 |
| Forest Fires (13) | 1.5e-1 | 3.0e-1 | 4.8e-1 | 1.1e-1 | 3.0e-1 | 2.2e0 | 2.9e-1 |
| Method | Language (IMDB) (14) | ResNet18-SP (14) | ViT4by4 (16) | DINOv2-16 (16) | Forest Fires (13) | AdultCensus (14) | Estate (15) | Crime (101) | Seismic Bumps (15) | Churn (19) | Credit-G (20) | Bankruptcy (64) | Superconductivity (81) | NATICUSdroid (86) | MIC (111) | pooled |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ShapleyOG (Ours) | 2.9 | 1.1 | 2.0 | 2.5 | 3.1 | 1.1 | 1.4 | 1.0 | 1.0 | 1.1 | 1.4 | 1.0 | 1.0 | 1.0 | 1.0 | 1.4 |
| OddSHAP | 3.2 | 2.9 | 2.8 | 2.3 | 4.1 | 2.2 | 2.2 | 3.2 | 2.4 | 2.7 | 2.4 | 3.0 | 2.5 | 2.2 | 2.2 | 2.6 |
| Regression MSR | 2.9 | 2.4 | 2.6 | 2.2 | 4.2 | 4.7 | 3.1 | 4.9 | 4.3 | 3.6 | 5.2 | 4.9 | 4.2 | 4.7 | 4.9 | 3.9 |
| Leverage SHAP | 3.2 | 4.3 | 3.5 | 3.7 | 2.6 | 2.9 | 3.4 | 2.8 | 2.7 | 3.1 | 2.4 | 2.1 | 3.0 | 3.0 | 3.4 | 3.1 |
| Game ( ) | Component | 512 | 1024 | 2048 | 4096 | 8192 |
|---|---|---|---|---|---|---|
| DINOv2-16 (16) | hyperparameter fitting (cum.) | 0.0 / 2 (21%) | 0.1 / 4 (20%) | 0.1 / 8 (20%) | 0.4 / 27 (25%) | 2.1 / 124 (34%) |
| EIG, refit steps (cum.) | 0.0 / 0 (4%) | 0.0 / 1 (3%) | 0.0 / 1 (3%) | 0.0 / 2 (2%) | 0.1 / 4 (1%) | |
| EIG, no-refit steps (cum.) | 0.1 / 3 (27%) | 0.1 / 7 (36%) | 0.3 / 18 (44%) | 0.9 / 54 (50%) | 3.0 / 181 (50%) | |
| bookkeeping (cum.) | 0.1 / 6 (49%) | 0.1 / 8 (42%) | 0.2 / 14 (34%) | 0.4 / 25 (23%) | 0.9 / 51 (14%) | |
| posterior readout at | 0.0 / 0 (0%) | 0.0 / 0 (0%) | 0.0 / 0 (0%) | 0.0 / 0 (0%) | 0.0 / 3 (1%) | |
| total (cum.) | 0.2 / 11 | 0.3 / 20 | 0.7 / 41 | 1.8 / 108 | 6.0 / 363 |
| Game ( ) | + refit schedule | + incremental updates | + GL quadrature | + paired acquisition | + odd GP = ShapleyOG | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| speed-up | NMSE | speed-up | NMSE | speed-up | NMSE | speed-up | NMSE | speed-up | NMSE | |
| Language (IMDB) (14) | 14 | 1.37 | 95 | 1.13 | 119 | 1.07 | 71 | 1.16 | 306 | 1.06 |
| ResNet18-SP (14) | 16 | 1.19 | 97 | 1.00 | 123 | 0.82 | 67 | 0.98 | 290 | 0.99 |
| ViT4by4 (16) | 17 | 1.02 | 105 | 1.13 | 130 | 1.11 | 79 | 0.88 | 346 | 1.04 |
| DINOv2-16 (16) | 8 | 1.01 | 66 | 1.03 | 80 | 1.08 | 46 | 1.05 | 233 | 1.06 |
| Forest Fires (13) | 10 | 0.82 | 73 | 0.63 | 86 | 0.64 | 51 | 0.84 | 256 | 0.53 |
| Game ( ) | ShaplEIG | + refit schedule | + incremental updates | + GL quadrature | + paired acquisition | + odd GP = ShapleyOG | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| overhead | NMSE | overhead | NMSE | overhead | NMSE | overhead | NMSE | overhead | NMSE | overhead | NMSE | |
| Language (IMDB) (14) | 1.8 h | 5.3e-4 | 7.6 min | 7.2e-4 | 1.2 min | 6.0e-4 | 55 s | 5.7e-4 | 1.6 min | 6.1e-4 | 21 s | 5.6e-4 |
| ResNet18-SP (14) | 2.0 h | 4.5e-6 | 7.5 min | 5.3e-6 | 1.2 min | 4.5e-6 | 58 s | 3.7e-6 | 1.8 min | 4.4e-6 | 24 s | 4.4e-6 |
| ViT4by4 (16) | 2.1 h | 4.4e-4 | 7.5 min | 4.5e-4 | 1.2 min | 4.9e-4 | 55 s | 4.9e-4 | 1.6 min | 3.9e-4 | 22 s | 4.6e-4 |
| DINOv2-16 (16) | 1.2 h | 6.4e-4 | 8.7 min | 6.5e-4 | 1.2 min | 6.6e-4 | 58 s | 6.9e-4 | 1.6 min | 6.7e-4 | 20 s | 6.8e-4 |
| Forest Fires (13) | 1.4 h | 1.4e-2 | 8.7 min | 1.2e-2 | 1.2 min | 8.9e-3 | 1.0 min | 8.9e-3 | 1.7 min | 1.2e-2 | 20 s | 7.4e-3 |
| relative error vs. exact | NMSE at | time per run | ||||||
|---|---|---|---|---|---|---|---|---|
| EIG | same argmax | covariances | overhead | |||||
| (exact) | – | – | – | – | 6.2e-4 | 2.9e-4 | 11.7 min | 53.5 min |
| 4.7e-15 | 7.0e-15 | 9.1e-9 | 100% | 6.2e-4 | 2.9e-4 | 4.8 min | 47.1 min | |
| 8.4e-15 | 1.2e-14 | 1.6e-8 | 100% | 6.2e-4 | 2.9e-4 | 1.1 min | 43.9 min | |
| 1.2e-14 | 6.7e-14 | 6.8e-8 | 100% | 6.2e-4 | 2.9e-4 | 14 s | 43.0 min | |
| 3.6e-4 | 4.1e-4 | 2.5e-2 | 14% | 7.5e-4 | 3.2e-4 | 8 s | 42.1 min | |
Shapley Value Attribution
Shapley value attribution fairly assigns a prediction or outcome among contributing features, data points, agents, or modalities.
See all 109 papers