Source-linked AI summary
The Shapley Value in Machine Learning
Benedek Rozemberczki, Lauren Watson, Péter Bayer, Hao-Tsung Yang, Olivér Kiss, Sebastian Nilsson, Rik Sarkar
TL;DR
Machine learning needs principled ways to measure the importance of features, data, agents, and models. This survey develops the Shapley value’s cooperative-game foundations, reviews its applications and approximations, and concludes that computational and axiomatic limitations remain important research issues.
Problem
Machine learning requires a unified approach to attributing importance and gains across explainability, feature selection, data valuation, ensemble pruning, and related tasks.
Method
The survey presents cooperative-game concepts and Shapley-value axioms, reviews machine-learning applications and approximation methods, and discusses future directions.
Results
The survey synthesizes Shapley-value uses in feature selection, data valuation, explainability, reinforcement learning, and model valuation, while identifying key limitations.
Takeaways & Limitations
The Shapley value offers a theoretically motivated framework for allocating gains and measuring contributions across machine-learning settings.
Takeaways & Limitations
Exact Shapley-value computation is exponential or factorial-time and approximations may not preserve the axiomatic properties used to justify the method.
Abstract
from arXiv · showhide
Over the last few years, the Shapley value, a solution concept from cooperative game theory, has found numerous applications in machine learning. In this paper, we first discuss fundamental concepts of cooperative game theory and axiomatic properties of the Shapley value. Then we give an overview of the most important applications of the Shapley value in machine learning: feature selection, explainability, multi-agent reinforcement learning, ensemble pruning, and data valuation. We examine the most crucial limitations of the Shapley value and point out directions for future research.
1 Introduction
The Shapley value provides a unified, axiomatic approach to attributing importance and gains across several machine-learning tasks. The survey introduces cooperative-game foundations, reviews applications, and discusses limitations and future directions.
- Importance attribution is central to explainability, feature selection, data valuation, ensemble pruning, and federated learning.
- The Shapley value allocates cooperative-game gains to individual players using axiomatic desiderata including fairness, symmetry, and efficiency.
- In machine-learning cooperative games, players can be features, agents, data points, ensemble models, or data silos.
- The characteristic function can encode model fit, reinforcement-learning reward, prediction gains, or out-of-sample performance.
- The survey presents cooperative-game definitions, Shapley-value properties, machine-learning applications, limitations, and future research directions.
2 Background
Cooperative games represent players and coalition values, while solution concepts specify allocation principles. The Shapley value averages marginal contributions across permutations and is uniquely characterized by four properties relevant to feature importance.
- Cooperative games and the Shapley value: A TU cooperative game is defined by a player set and a characteristic function assigning real values to coalitions, with v(∅) = 0.
- Cooperative games and the Shapley value: A solution concept maps each game to feasible payoff allocations, whose total rewards cannot exceed the grand coalition’s value.
- Cooperative games and the Shapley value: The Shapley value is each player’s average marginal contribution to predecessor coalitions across every permutation of the player set.
- Properties of the Shapley value: In feature selection, input features are players, feature subsets are coalitions, and coalition payoff is model goodness of fit.
- Properties of the Shapley value: The null-player property assigns zero value to features that never improve goodness of fit, while efficiency makes feature importance sum to whole-model goodness of fit.
- Properties of the Shapley value: Symmetry gives identical importance to features with identical marginal contributions, and linearity makes pooled-game values equal sums from separate games.
- Properties of the Shapley value: The null-player, efficiency, symmetry, and linearity properties together characterize the Shapley value.
3 Approximations of the Shapley Value
Exact Shapley value computation is exponential because it requires evaluating exponentially many coalitions, so machine-learning applications rely on sampling, variance reduction, and regression-based approximations. These methods trade exactness for feasible computation, with some approaches improving precision, convergence, or bias–variance behavior.
- Shapley value computation requires exponentially many characteristic-function evaluations, which is prohibitive when each evaluation may train a model.Machine-learning applications therefore use approximation methods.
- Monte Carlo permutation sampling approximates the Shapley value by averaging marginal contributions across sampled player permutations.The method updates estimates iteratively and has asymptotic error bounds under known marginal-contribution variance.
- Variance reduction: Stratified sampling improves approximation precision when permutations can be partitioned into homogeneous strata with similar marginal gains.The strata are non-overlapping sub-populations of permutations.
- Multilinear extension: The multilinear extension approximates Shapley values by sampling subset-inclusion probabilities q and integrating expected marginal contributions over q.Trapezoid-rule and antithetic-sampling variants sample q more efficiently or reduce variance.
- Linear regression approximation: SHAP approximates Shapley values with weighted least squares over subsampled coalitions, while paired complementary coalitions improve convergence speed by a magnitude.SHAP is consistent but not unbiased; its small bias is accompanied by significantly lower variance than the corresponding unbiased estimator.
4 Machine Learning and the Shapley Value
Machine-learning applications formulate cooperative games by choosing players and a payoff, then use Shapley values to quantify contributions across feature selection, data valuation, federated learning, explainability, and model or neuron valuation. The review compares these formulations, approximation methods, and computational costs while describing extensions for dependent features, causal structure, and specialized models.
- Applications define players as features, data points, models, agents, or data silos, with payoffs based on model fit, reward, financial gain, or out-of-sample performance.These choices determine what contribution the Shapley value measures.
- Feature selection: Feature selection treats input features as players and model performance as payoff, allowing features to be ranked, selected, or removed by their Shapley-based importance.The approach has been applied to vocabulary selection and other feature-selection tasks.
- Data valuation: Data valuation treats training data points as players and test-set goodness of fit as payoff, measuring each point’s contribution to model performance.Distributional Shapley value methods address privacy concerns, while model-specific approximations reduce computation time.
- Explainable machine learning: Explainability assigns instance-level feature attributions by decomposing a model prediction, with efficiency providing a complete decomposition and reference values imputing missing features.Related methods extend attribution to neurons, filters, feature interactions, and graph-constrained permutations.
- Table 2 compares application areas by player set, payoff definition, approximation technique, and computation time, grouping related works chronologically.The comparison organizes the reviewed applications by the problem each work addresses.
5 Discussion
The Shapley value has broad potential in machine learning, but its use is constrained by computational cost, interpretability challenges, and the loss of axiomatic guarantees under approximation. Extensions such as coalition-structure values and alternative solution concepts suggest directions for addressing these limitations.
- Limitations: Naive Shapley value computation takes factorial time, making exact calculation in large-scale data valuation, explainability, and feature selection settings intractable.Approximation techniques make computation possible, but their asymptotic properties are not always well understood.
- Limitations: Shapley values average marginal contributions across all permutations, making their theoretical interpretation difficult for non-game-theory experts.Translating values into concrete actions can therefore be troublesome.
- Limitations: Under commonly used approximations, the Shapley value’s desired axiomatic properties do not hold, an unresolved issue for applications justified by those axioms.The paper identifies this as its greatest unresolved issue in machine-learning applications.
- Extensions: The Owen value restricts permutations according to a partitioned coalition structure, while overlapping coalition structures allow players to belong to multiple coalitions.These extensions can represent hierarchical or shared structures in machine-learning settings.
- Extensions: Alternative cooperative-game solution concepts, including the core, nucleolus, stable set, and kernel, offer additional axiomatizations for machine-learning applications.The paper notes that the core has been used for model explainability and feature selection.
6 Conclusion
The survey synthesizes the Shapley value’s axiomatic characterizations, approximation approaches, and machine-learning uses. It also highlights limitations and identifies potential new application and research areas.
- The survey examines Shapley value axiomatic characterizations and the most frequently used approximation approaches.
- It reviews Shapley value applications in machine learning and highlights associated issues and potential new research areas.