$\texttt{ShaplEIG}$: Bayesian Experimental Design for Shapley Value Estimation

Shapley values are a principled attribution measure widely used in interpretable machine learning, but their exact computation scales exponentially with the number of players, motivating a wide range of approximation methods based on value function evaluations of sampled coalitions. This raises the question of whether approximation accuracy can be improved by *adaptively* selecting coalitions for evaluation based on previous evaluations. This is particularly relevant in settings where the value function is *costly* and the number of evaluations is severely limited, such as retraining-based feature importance, data valuation, and hyperparameter importance. For this purpose, we propose $\texttt{ShaplEIG}$, a Bayesian experimental design approach that approximates the expensive value function using a Gaussian process surrogate and adaptively selects coalitions based on their expected information gain about the Shapley values. By the linearity of the Shapley values in the value function, we show that the expected information gain is available in *closed form*. Furthermore, we propose an *efficient* computation scheme that reduces the complexity from exponential to polynomial in the number of players via elementary symmetric polynomials. In extensive experiments across diverse costly applications, our method consistently improves sample efficiency in the low-budget regime over state-of-the-art baselines.

Many machine learning explanations try to answer a simple question: which inputs, data points, or settings were most responsible for a model’s behavior? A popular way to measure this is with Shapley values, but computing them exactly can require testing an enormous number of combinations, which is often too expensive. We propose ShaplEIG, a method that chooses these combinations more carefully. Instead of testing them at random or according to a fixed rule, it learns from previous tests and selects the next one that is expected to be most useful for improving the explanation. Across several expensive explanation tasks, ShaplEIG achieves more accurate estimates with fewer tests than existing methods.