📊 statistics

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

The paper introduces ShaplEIG, a Bayesian experimental design method that leverages Gaussian process surrogates and closed-form expected information gain to adaptively select coalitions, thereby significantly improving the sample efficiency of Shapley value estimation in costly, low-budget scenarios.

Original authors: David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Rundel, Fabian Fumagalli, Maximilian Muschalik, Bernd Bischl, Matthias Feurer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Too Many Choices" Dilemma

Imagine you are trying to figure out how much each player contributed to a team's victory. In the world of Machine Learning, these "players" are features (like a patient's age or a house's square footage) or data points. The mathematical tool used to measure this contribution is called the Shapley Value.

To calculate the exact Shapley Value, you have to test every possible combination of players.

If you have 10 players, there are 1,024 combinations.
If you have 20 players, there are over 1 million combinations.
If you have 50 players, the number is so huge it exceeds the number of atoms in the universe.

Furthermore, testing each combination is expensive. It might require retraining a complex AI model from scratch, which takes hours or costs money. This is like trying to find the perfect recipe by baking every possible combination of ingredients in the world, one by one. You simply run out of time and money before you finish.

The Current Solution: Guessing and Checking

Because we can't test everything, current methods usually pick combinations to test at random or follow a fixed pattern (like "always test small groups first").

The Analogy: Imagine you are a detective trying to solve a crime by interviewing suspects. Current methods are like interviewing suspects in alphabetical order or picking names out of a hat. You might interview the wrong people while missing the crucial clue held by the one person you haven't talked to yet.

The New Solution: ShaplEIG (The Smart Detective)

The authors propose a new method called ShaplEIG. Instead of guessing randomly, this method uses a "Smart Detective" approach based on Bayesian Experimental Design.

Here is how it works, step-by-step:

1. The "Surrogate" Map (The Crystal Ball)

Since testing every combination is too expensive, ShaplEIG builds a surrogate model (a simplified, fast approximation) of the game.

The Analogy: Imagine you are trying to map a huge, foggy mountain range. Instead of hiking every single inch, you build a small, fast 3D model of the terrain based on a few initial hikes. This model isn't perfect, but it gives you a good guess of where the peaks and valleys are.

2. The "Expected Information Gain" (The Compass)

This is the core magic of the paper. The method asks: "Which single combination should I test next to learn the most about the final answer?"

The Analogy: A normal detective might ask, "Who looks suspicious?" (Uncertainty Sampling). ShaplEIG asks, "If I interview this specific person, how much will it clarify the entire mystery for everyone else?"
It calculates the Expected Information Gain (EIG). It looks at the 3D map it built and says, "Testing this specific coalition will reduce our uncertainty about the final scores of all players the most."

3. The "Closed-Form" Shortcut (The Superpower)

Usually, calculating "how much information we will get" is incredibly hard and slow (like trying to solve a puzzle while the pieces are moving).

The Paper's Breakthrough: The authors discovered that because Shapley Values are calculated in a specific linear way, they can write a mathematical shortcut (a "closed-form expression") to calculate this information gain instantly.
The Analogy: Usually, to know how much a new clue helps, you'd have to simulate the whole investigation again. ShaplEIG found a formula that tells you the answer in a split second, like a GPS that instantly recalculates the best route without re-mapping the whole world.

4. The "Polynomial" Speed-Up (The Elevator)

Even with the shortcut, calculating this for millions of combinations would still be too slow.

The Paper's Breakthrough: They used a clever mathematical trick involving Elementary Symmetric Polynomials (a type of math pattern) to turn a calculation that grows exponentially (1, 10, 100, 1000...) into one that grows polynomially (1, 10, 100, 1000... but much slower).
The Analogy: Instead of walking up a mountain one step at a time (exponential), they built an elevator (polynomial) that gets you to the top quickly, even for very large mountains.

The Results: Better Answers, Less Work

The authors tested ShaplEIG on various difficult tasks, such as:

Figuring out which features matter most for a medical diagnosis model.
Valuing specific data points in a dataset.
Understanding which settings (hyperparameters) make an AI model work best.

The Outcome:
In almost every test, ShaplEIG found the correct answers faster and with fewer expensive tests than the best existing methods.

The Analogy: If other methods needed to interview 400 suspects to solve the case with 90% accuracy, ShaplEIG often solved it with only 200 interviews, and with higher accuracy.

Summary

ShaplEIG is a smart way to estimate how much each part of an AI model contributes to its decisions. Instead of blindly testing random combinations, it uses a mathematical "compass" to pick the single most informative test to run next. By using a clever math shortcut, it does this quickly, saving time and money when dealing with expensive AI models.

Technical Summary: ShaplEIG

Problem Statement

Shapley values (SVs) serve as a principled attribution measure in interpretable machine learning, yet their exact computation is often intractable. The computational burden arises from two factors: the exponential growth of coalitions ( $2^p$ ) with the number of players $p$ , and the high cost of evaluating the value function $\nu$ for each coalition. In applications such as retraining-based feature importance, data valuation, and hyperparameter importance, value function evaluations can involve full model retraining or expensive inference, severely limiting the evaluation budget.

Existing approximation methods, including Monte Carlo sampling and surrogate-based approaches (e.g., Kernel SHAP, Regression MSR), typically rely on fixed, non-adaptive sampling distributions. This raises the question of whether approximation accuracy can be improved by adaptively selecting coalitions for evaluation based on previous observations, particularly in low-budget regimes. While Bayesian Experimental Design (BED) offers a framework for sequential design using Expected Information Gain (EIG), its adoption in SV estimation has been limited due to the lack of closed-form EIG expressions and the computational intractability of estimating EIG for high-dimensional discrete spaces.

Methodology

The authors propose ShaplEIG, a Bayesian experimental design approach that adaptively selects coalitions to maximize information gain regarding the Shapley values.

1. Gaussian Process Surrogate with Hamming Kernel

ShaplEIG models the value function $\nu$ using a Gaussian Process (GP) surrogate. To handle the binary input space of coalitions (represented as indicator vectors $z \in \{0, 1\}^p$ ), the method employs a Hamming distance kernel. This kernel quantifies similarity between coalitions based on weighted Hamming distances, with learnable lengthscale hyperparameters $\xi$ . The GP provides a posterior distribution over the value function across all $2^p$ coalitions given a dataset $D_t$ of observed evaluations.

2. Consistent SV Estimation via Linearity

A key theoretical insight is the linearity of Shapley values with respect to the value function. The SVs $\phi$ can be expressed as a linear transformation of the value function vector $\nu$ : $\phi = A\nu$ , where $A$ is a known matrix derived from the Shapley formula. Consequently, under the GP surrogate, the posterior distribution over the SVs is also Gaussian and available in closed form:
$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$
The authors extract SV estimates from the posterior mean, $\hat{\phi} = A\mu_{\nu|D_t}$ . Crucially, for noiseless (or quasi-noiseless) GPs, this estimator is consistent: if all $2^p$ coalitions are evaluated, the estimates converge exactly to the true Shapley values.

3. Closed-Form Expected Information Gain (EIG)

The core contribution is deriving a closed-form expression for the EIG of a candidate coalition $z^{(i)}$ regarding the SVs. By framing the sequential selection as a Bayesian linear inverse problem where the SVs are a linear end-goal, the EIG is shown to depend only on the posterior covariance of the SVs:
$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$
This avoids the nested expectations typically required in BED, as the EIG depends solely on the experimental design (the selected coalition) and not the specific outcome $y(x)$ .

4. Efficient Computation via Elementary Symmetric Polynomials

Direct computation of the EIG involves operations on matrices of size $2^p \times 2^p$ , leading to exponential complexity. The authors propose an efficient computation scheme that reduces the complexity to polynomial time ( $O(p^4 + t^3)$ ) by exploiting the multiplicative structure of the Hamming kernel.

The terms required for the EIG (specifically $A\Sigma_{\nu|D_t}e_i$ and $A\Sigma_{\nu|D_t}A^\top$ ) are rewritten as weighted sums of kernel evaluations.
These sums are identified with scaled elementary symmetric polynomials (ESPs).
By computing these polynomials efficiently (using dynamic programming and prefix/suffix tables), the method avoids explicit enumeration of all coalitions.

5. Algorithm

The algorithm proceeds greedily:

Initialize with a small design (e.g., leverage score sampling).
Fit the GP surrogate and optimize hyperparameters.
Compute the EIG for all candidate coalitions using the efficient polynomial scheme.
Select the coalition with the maximum EIG, evaluate the value function, and update the dataset.
Repeat until the budget is exhausted.

Key Contributions

ShaplEIG Framework: Introduction of a novel, BED-based method for SV estimation that uses a GP surrogate with a Hamming kernel and adaptively selects coalitions based on EIG.
Closed-Form EIG: Demonstration that the EIG for Shapley values admits a closed-form expression under a GP surrogate, leveraging the linearity of SVs in the value function.
Polynomial Complexity: Proposal of an efficient computation scheme for the EIG that reduces complexity from exponential to polynomial in the number of players ( $p$ ) via elementary symmetric polynomials.
Consistent Estimation: Provision of a consistent SV estimator that converges to exact values when all coalitions are evaluated, contrasting with some tree-based surrogate methods that require additional adjustment steps.

Experimental Results

The authors evaluate ShaplEIG across diverse, costly applications involving small to moderately large games ( $8 \le p \le 101$ ):

Tasks: Global feature importance (TabPFN), data valuation (Random Forest, Gradient Boosting), hyperparameter importance (XGBoost, LCBench), and local explanations (ResNet, ViT, Random Forest).
Baselines: Comparison against Kernel SHAP, Leverage SHAP, Permutation Sampling, and the state-of-the-art Regression MSR (coupled with XGBoost).
Ablations: Comparison against variants using the same GP surrogate but different selection strategies (Random, Uncertainty Sampling, Leverage Score Sampling).

Findings:

Sample Efficiency: ShaplEIG consistently achieves the best overall accuracy (lowest Mean Squared Error) in the low-budget regime across most tasks. It often strictly dominates competitors, particularly in asymmetric games where player interactions are non-uniform.
Ablation Insights: The strong performance is attributed primarily to the EIG-based selection strategy rather than just the use of a GP surrogate. Uncertainty Sampling (US) often performed worse than random sampling, highlighting that maximizing marginal variance does not equate to maximizing information about the linearly transformed SVs.
Scalability: For larger games ( $p > 16$ ), the method remains effective even when hyperparameter refitting is performed on a schedule rather than every iteration.
Computational Cost: While EIG computation is efficient (seconds), hyperparameter fitting can become a bottleneck for large $p$ (up to 25 minutes per iteration for $p \approx 100$ ). The authors note that ShaplEIG is most appropriate when value function evaluations are genuinely expensive, justifying the overhead.

Significance and Claims

The paper claims that ShaplEIG provides a principled framework for improving sample efficiency in SV estimation for costly games. By deriving a closed-form EIG and an efficient polynomial-time computation scheme, the authors overcome the primary barriers to applying Bayesian Experimental Design in this domain.

The authors modestly state that while the method incurs computational overhead from repeated GP optimization, it offers substantial gains in estimation accuracy when evaluation budgets are limited. They acknowledge that for very large games or less costly value functions, the overhead may be prohibitive, suggesting future work should focus on further computational improvements to broaden the method's applicability. The work does not claim to solve SV estimation for all scenarios but specifically targets the regime of expensive value functions where adaptive selection is critical.