Shapley value
In plain wordsA rule from game theory for splitting a shared reward fairly among team members, by averaging how much each member adds when joining the team in every possible order.
In cooperative game theory, a rule for dividing a coalition's total value among its n players under which each player receives its average marginal contribution v(S ∪ {i}) − v(S) over every order in which the players might join. Lloyd Shapley proved it is the only division that hands out exactly the total (efficiency), treats interchangeable players alike (symmetry), gives nothing to a player who never adds value (null player) and splits a sum of games as the sum of the separate splits (additivity). In machine learning the players are usually input features and the value function is the model's prediction with only some features 'present', which yields SHAPSHAP, abbr.: A popular method that explains a single prediction by fairly dividing it among the inputs, using a rule from game theory for splitting a team's winnings among its players.; players can also be training examples (Data Shapley), neurons or members of an ensembleensemble learning, n.: Combining the predictions of several models — by voting or averaging — so their individual mistakes partly cancel out, giving more accurate and stable results than any one model.. Exact computation needs all 2ⁿ coalitions, so practice relies on sampling, regression-based estimators or model-specific shortcuts.
We used Shapley values to split the ensemble's accuracy gain among its five member models.
Origin
Introduced by Lloyd S. Shapley in 'A Value for n-Person Games' (1953), in Contributions to the Theory of Games II (Annals of Mathematics Studies 28). Shapley shared the 2012 Nobel Memorial Prize in Economic Sciences, awarded for the theory of stable allocations. Applied to regression by Stan Lipovetsky and Michael Conklin (2001) and to classifier explanation by Erik Štrumbelj and Igor Kononenko (2010).
Usage note
The value is 'fair' only relative to its axioms and to how a coalition's worth is defined; in feature attribution, choices about simulating missing features can change the answer substantially.
Related
- SHAPSHAP, abbr.: A popular method that explains a single prediction by fairly dividing it among the inputs, using a rule from game theory for splitting a team's winnings among its players.
- feature attributionfeature attribution, n.: Giving each input to an AI model — each pixel, word or data column — a score for how much it pushed a particular output up or down.
- data attributiondata attribution, n.: Working out which training examples were responsible for a particular behavior or answer of an AI model — useful for explaining, debugging and crediting the data behind it.
- integrated gradientsintegrated gradients, n.: A way to score how much each input feature contributed to a neural network's output by gradually morphing a blank 'baseline' input into the real one and adding up the network's sensitivity along the way.
- ensemble learningensemble learning, n.: Combining the predictions of several models — by voting or averaging — so their individual mistakes partly cancel out, giving more accurate and stable results than any one model.
Sources
- Shapley, L. S. (1953). A Value for n-Person Games. In Kuhn, H. W. & Tucker, A. W. (eds.), Contributions to the Theory of Games II. Annals of Mathematics Studies 28. Princeton University Press.
- Štrumbelj, E. & Kononenko, I. (2014). Explaining prediction models and individual predictions with feature contributions. Knowledge and Information Systems 41, 647–665.
Mentioned in
game theorygame theory, n.: The mathematics of strategic decisions, where each player's best move depends on what the others do. It is used to study competition and cooperation among people, firms, nations and AI agents., integrated gradientsintegrated gradients, n.: A way to score how much each input feature contributed to a neural network's output by gradually morphing a blank 'baseline' input into the real one and adding up the network's sensitivity along the way., SHAPSHAP, abbr.: A popular method that explains a single prediction by fairly dividing it among the inputs, using a rule from game theory for splitting a team's winnings among its players., data attributiondata attribution, n.: Working out which training examples were responsible for a particular behavior or answer of an AI model — useful for explaining, debugging and crediting the data behind it., influence functioninfluence function, n.: A mathematical shortcut for estimating how much a single training example shaped a model's behavior, for instance how a prediction would change if that example had been left out, without retraining the model.