The Shapley Value in Machine Learning

1 Introduction

Measuring importance and the attribution of various gains is a central problem in many practical aspects of machine learning such as explainability [Lundberg et al., 2017], feature selection [Cohen et al., 2007], data valuation [Ghorbani et al., 2019], ensemble pruning [Rozemberczki et al., 2021] and federated learning [Wang et al., 2020; Fan et al., 2021]. For example, one might ask: What is the importance of a feature in the decisions of a machine learning model? How much is an individual data point worth? Which models are the most valuable in an ensemble? These questions have been addressed in different domains using specific approaches. Interestingly, there is also a general and unified approach to these questions as a solution to a transferable utility (TU) cooperative game. In contrast with other approaches, solution concepts of TU games are theoretically motivated with axiomatic properties. The best known solution is the Shapley value [Shapley, 1953] characterized by desiderata that include fairness, symmetry, and efficiency [Chalkiadakis et al., 2011].

In the TU setting, a cooperative game consists of: a player set and a scalar-valued characteristic function that defines the value of coalitions (subsets of players). In such a game, the Shapley value offers a rigorous and intuitive way to distribute the collective value (e.g. the revenue, profit, or cost) of the team across individuals. To apply this idea to machine learning, we need to define two components: the player set and the characteristic function. In a machine learning setting players may be represented by a set of input features, reinforcement learning agents, data points, models in an ensemble, or data silos. The characteristic function can then describe the goodness of fit for a model, reward in reinforcement learning, financial gain on instance level predictions, or out-ofsample model performance. We provide an example about model valuation in an ensemble [Rozemberczki et al., 2021] in Figure 1.

Present work. We introduce basic definitions of cooperative games and present the Shapley value, a solution concept that can allocate gains in these games to individual players. We discuss its properties and emphasize why these are important in machine learning. We overview applications of the Shapley value in machine learning: feature selection, data valuation, explainability, reinforcement learning, and model valuation. Finally, we discuss the limitations of the Shapley value and point out future directions. The survey is supported by a collection of related work under https://github.com/AstraZeneca/awesome-shapley-value.

2 Background

This section introduces cooperative games and the Shapley value followed by its properties. We also provide an illustrative running example for our definitions.

2.1 Cooperative Games and the Shapley Value

Definition 1. Player set and coalitions. Let N = {1, . . . , n} be the finite set of players. We call each non-empty subset S ⊆ N a coalition and N itself the grand coalition.

Definition 2. Cooperative game. A TU game is defined by the pair (N, v) where v : 2N → R is a mapping called the characteristic function or the coalition function of the game assigning a real number to each coalition and satisfying v(∅) = 0.

Example 1. Let us consider a 3-player cooperative game where N = {1, 2, 3}. The characteristic function defines the payoff for each coalition. Let these payoffs be given as:

Definition 3. Set of feasible payoff vectors. Let us define Z(N, v) = {z ∈ RN | ∑i∈N zi ≤ v(N)} the set of feasible payoff vectors for the cooperative game (N, v).

Definition 4. Solution concept and solution vector. Solution concept Φ is a mapping associating a subset Φ(N , v) ⊆ Z(N , v) to every TU game (N, v). A solution vector φ(N, v) ∈ RN to the cooperative game (N, v) satisfies solution concept Φ if φ(N, v) ∈ Φ(N, v). Solution concept Φ is single-valued if for every (N, v) the set Φ(N, v) is a singleton.

A solution concept defines an allocation principle through which rewards can be given to the individual players. The sum of these rewards cannot exceed the value of the grand coalition v(N). Solution vectors are specific allocations satisfying the principles of the solution concept.

Definition 5. Permutations of the player set. Let Π(N) be the set of all permutations defined on N, a specific permutation is written as π ∈ Π(N) and π(i) is the position of player i ∈ N in permutation π.

Definition 6. Predecessor set. Let the set of predecessors of player i ∈ N in permutation π be the coalition:

Let us imagine that the permutation of the players in our illustrative game is π = (3, 2, 1). Under this permutation the predecessor set of the 1st player is P π 1 = {3, 2}, that of the 2nd player is P π 2 = {3} and P π 3 = ∅.

Definition 7. Shapley value. The Shapley value [Shapley, 1953] is a single-valued solution concept for cooperative games. The ith component of the single solution vector satisfying this solution concept for any cooperative game (N, v) is given by Equation 1.

The Shapley value of a player is the average marginal contribution of the player to the value of the predecessor set over every possible permutation of the player set. Table 1 contains manual calculations of the players' marginal contributions to each permutation and their Shapley values in Example 1.

2.2 Properties of the Shapley Value

We define the solution concept properties that characterize the Shapley value and emphasize their relevance and meaning in a feature selection game. In this game input features are players, coalitions are subsets of features and the payoff is a scalar valued goodness of fit for a machine learning model using these inputs.

Definition 8. Null player. Player i is called a null player if v(S ∪ {i}) = v(S) ∀S ⊆ N \ {i}. A solution concept Φ satisfies the null player property if for every game (N, v), every φ(N, v) ∈ Φ(N, v), and every null player i it holds that φi(N , v) = 0.

In the feature selection game a solution concept with the null player property assigns zero value to those features that never increase the goodness of fit when added to the feature set.

Definition 9. Efficiency. A solution concept Φ is efficient or Pareto optimal if for every game (N, v) and every solution vector φ(N, v) ∈ Φ(N, v) it holds that ∑ i∈N φi(N , v) = v(N ).

Consider the goodness of fit of the model trained using the whole set of features. The importance measures assigned to features by an efficient solution concept sum to this goodness of fit. This allows for quantifying the contribution of features to the performance of a model trained on the whole feature set.

Definition 10. Symmetry. Two players i and j are symmetric if v(S ∪ {i}) = v(S ∪ {j}) ∀S ⊆ N \ {i, j}. A solution concept Φ satisfies symmetry if for all (N, v) for all φ(N, v) ∈ Φ(N, v) and all symmetric players i, j ∈ N it holds that φi(N, v) = φ(N , v)j .

The symmetry property implies that if two features have the same marginal contribution to the goodness of fit when added to any coalition then the importance of the two features is the same. This property is essentially a fair treatment of inputs and results in identical features receiving the same importance score.

Definition 11. Linearity. A single-valued solution concept Φ satisfies linearity if for any two games (N, v) and (N,w), and for the solution vector of the TU game given by (N, v +w) it holds that

Let us imagine a binary classifier and two sets of data points - on both of these datasets, we can define feature selection games with binary cross entropy-based payoffs. The Shapley values of input features in the feature selection game calculated on the pooled dataset would be the same as adding together the Shapley values calculated from the two datasets separately.

These four properties together characterize the Shapley value.

Theorem 1 (Shapley, 1953). A single-valued solution concept satisfies the null player, efficiency, symmetry, and linearity properties if and only if it is the Shapley value.

3 Approximations of the Shapley Value

Shapley value computation requires a factorial number of characteristic function evaluations, resulting in factorial time complexity. This is prohibitive in a machine learning context when each evaluation can correspond to training a machine learning model.

For this reason, machine learning applications use a variety of Shapley value approximation methods we discuss in this section. In the following discussion ̂ φSh i denotes an approximated Shapley value for player i ∈ N.

3.1 Monte Carlo Permutation Sampling

Monte Carlo permutation sampling for the general class of cooperative games was first proposed by Castro et al. [2009] to approximate the Shapley value in linear time. Their method performs a sampling-based approximation, at each iteration, a random element from the permutations of the player set is drawn. The marginal contributions of the players in the sampled permutation are scaled down by the number of samples (which is equivalent to taking an average) and added to the approximated Shapley values from the previous iteration. Castro et al. [2009] provide asymptotic error bounds for this approximation algorithm via the central limit theoremwhen the variance of the marginal contributions is known. Maleki et al. [2013] extended the analysis of this sampling approach by providing error bounds when either the variance or the range of the marginal contributions is known via Chebyshev's and Hoeffding's inequalities. Their bounds hold for a finite number of samples in contrast to the previous asymptotic bounds.

Stratified Sampling for Variance Reduction

In addition to extending the analysis of Monte Carlo estimation, Maleki et al. [2013] demonstrate how to improve Shapley value approximation when sampling can be stratified by dividing the permutations of the player set into homogeneous, non-overlapping sub-populations. In particular, they show that if the set of permutations can be grouped into strata with similar marginal gains for players, then the approximation will be more precise. Following this, Castro et al. [2017] explored stratified sampling approaches using strata defined by the set of all marginal contributions when the player is in a specific position within the coalition. Burgess et al. [2021] propose stratified sampling approaches designed to minimize the uncertainty of the estimate via a stratified empirical Bernstein bound.

Other Variance Reduction Techniques

Following the stratified approaches of Maleki et al.; Castro et al.; Burgess et al. [2013; 2017; 2021], Ill´es et al. [2019] propose an alternative variance reduction technique for the sample mean. Instead of generating a random sequence of samples, they instead generate a sequence of ergodic but not independent samples, taking advantage of negative correlation to reduce the sample variance. Mitchell et al. [2021] show that other Monte Carlo variance reduction techniques can also be applied to this problem, such as antithetic sampling [Lomeli et al., 2019; Rubinstein et al., 2016]. A simple form of antithetic sampling uses both a randomly sampled permutation and its reverse. Finally, Touati et al. [2021] introduce a Bayesian Monte Carlo approach to Shapley value calculation, showing that Shapley value estimation can be improved by using Bayesian methods.

3.2 Multilinear Extension

By inducing a probability distribution over the subsets S where Ei is a random subset that does not include player i and each player is included in a subset with probability q, Owen [1972] demonstrated that the sum over subsets in Definition 7 can also be represented as an integral ∫ 1 0 ei(q)dq where ei(q) = E[v(Ei ∪ i) - v(Ei)]. Sampling over q therefore provides an approximation method - the multilinear extension. For example, Mitchell et al. [2021] uses the trapezoid rule to sample q at fixed intervals while Okhrati et al. [2021] proposes incorporating antithetic sampling as a variance reduction technique.

3.3 Linear Regression Approximation

In their seminal work Lundberg et al. [2017] apply Shapley values to feature importance and explainability (SHAP values), demonstrating that Shapley values for TU games can be approximated by solving a weighted least squares optimization problem. Their main insight is the computation of Shapley values by approximately solving the following optimization problem:

The definition of weights in Equation (2) and the objective function in Equation (3) implies the evaluation of v(·) for 2n coalitions. To address this Lundberg et al. [2017] propose approximating this by subsampling the coalitions. Note that wS is higher when coalitions are large or small. Covert et al. [2021] extend the study of this method, finding that while SHAP is a consistent estimator, it is not an unbiased one. By proposing and analyzing a variation of this unbiased method, they conclude that while there is a small bias incurred by SHAP it has a significantly lower variance than the corresponding unbiased estimator. Covert et al. [2021] then propose a variance reduction method for SHAP, improving convergence speed by a magnitude through sampling coalitions in pairs with each selected alongside its complement.

4 Machine Learning and the Shapley Value

Our discussion about applications of the Shapley value in machine learning focuses on the formulation of the cooperative games, definition of the player set and payoffs, Shapley value approximation, and the time complexity of the approximation. We summarized the most important application areas in Table 2 and grouped the relevant works by the problem solved.

4.1 Feature Selection

The feature selection game treats input features of a machine learning model as players and model performance as the payoff [Guyon et al., 2003; Fryer et al., 2021]. The Shapley values of features quantify how much individual features contribute to the model's performance on a set of data points.

Definition 12. Feature selection game. Let the player set be N = {1, . . . , n}, for S ⊆ N the train and test feature vector sets are X Train S = {x Train i |i ∈ S } and X Test S = {x Test i |i ∈ S }. Let fS(·) be a machine learning model trained using X Train S as input, then the payoff is v(S) = g(y,̂yS ) where g(·) is a goodness of fit function, y and ̂yS = fS(X Test S ) are the ground truth and predicted targets.

Shapley values, and close relatives such as the Banzhaf index [Banzhaf III, 1964], have been studied as a measure of feature importance in various contexts [Cohen et al., 2007; Pint´er, 2011; Sun et al., 2012; Williamson et al., 2020; Tripathi et al., 2020]. Using these importance estimates, features can be ranked and selected or removed accordingly. This approach has been applied to various tasks such as vocabulary selection in natural language processing [Patel et al., 2021] and feature selection in human action recognition [Guha et al., 2021].

4.2 Data Valuation

In the data valuation game training set data points are players and the payoff is defined by the goodness of fit achieved by a model on the test data. Computing the Shapley value of players in a data valuation game measures how much data points contribute to the performance of the model.

Definition 13. Data valuation game. Let the player set be N = {(xi, yi) | 1 ≤ i ≤ n} where xi is the input feature vector and yi is the target. Given the coalition S ⊆ N let fS(·) be a machine learning model trained on S. Let us denote the test set feature vectors and targets as X and Y, given fS(·) the set of predicted labels is defined as ̂ Y = {fS(x)|x ∈ X}. Then the payoff of a model trained on the data points S ⊆ N is v(S) = g(Y, ̂ Y) where g(·) is a goodness of fit metric.

The Shapley value is not the only method for data valuation - earlier works used function utilization [Koh et al., 2017; ?], leave-one-out testing [Cook, 1977] and core sets [Dasgupta et al., 2009]. However, these methods fall short [Jia et al., 2019; Ghorbani et al., 2019; Kwon et al., 2021b] when there are fairness requirements from the data valuation technique. Ghorbani et al. [2019] proposed a framework of utilizing Shapley value in a data-sharing system; Jia et al. [2019] advanced this work with more efficient algorithms to approximate the Shapley value for data valuation. The distributional Shapley value has been discussed by Ghorbani et al. [2020a] who argued that maintaining privacy is hard during Shapley value computation. Their method calculates the Shapley value over a distribution which solves problems such as lack of privacy. The computation time of this can be reduced as Kwon et al. [2021a] point out with approximation methods optimized for specific models.

4.3 Federated Learning

A federated learning scenario can be seen as a cooperative game by modeling the data owners as players who cooperate to train a high-quality machine learning model [Liu et al., 2021].

Definition 14. Federated learning game. In this game players are a set of labeled dataset owners N = {(Xi, Yi)|1 ≤ i ≤ n} where Xi and Yi are the feature and label sets owned by the ith silo. Let (X, Y) be a labeled test set, S ⊆ N a coalition of data silos, fS(·) a machine learning model trained on S, and ̂ YS the labels predicted by fS(·) on X. The payoff of S ⊆ N is v(S) = g(Y, ̂ YS) where g(·) is a goodness of fit metric.

The system described by Liu et al. [2021] uses Monte Carlo sampling to approximate the Shapley value of the data silos.

Given the potentially overlapping nature of the datasets, the use of configuration games, an extension of the Shapley value, could be an interesting future direction for federated learning.

4.4 Explainable Machine Learning

In explainable machine learning the Shapley value is used to measure the contributions of input features to the output of a machine learning model at the instance level. Given a specific data point, the goal is to decompose the model prediction and assign Shapley values to individual features of the instance. There are universal solutions to this challenge that are model agnostic and designs customized for deep learning [Chen et al., 2018; Ancona et al., 2019], classification trees [Lundberg et al., 2017], and graphical models [Liu et al., 2020; Singal et al., 2021].

Universal Explainability

A cooperative game for universal explainability is completely model agnostic; the only requirement is that a scalar-valued output can be generated by the model such as the probability of a class label being assigned to an instance.

Definition 15. Universal explainability game. Let us denote the machine learning model of interest with f(·) and let the player set be the feature values of a single data instance: N = {xi|1 ≤ i ≤ n}. The payoff of a coalition S ⊆ N in this game is the scalar valued prediction v(S) = ̂ yS = f(S) calculated from the subset of feature values.

Calculating the Shapley value in a game like this offers a complete decomposition of the prediction because the efficiency axiom holds. The Shapley values of feature values are explanatory attributions to the input features and missing input feature values are imputed with a reference value such as the mean computed from multiple instances [Lundberg et al., 2017; Covert et al., 2021]. The pioneering Shapley value-based universal explanation method SHAP [Lundberg et al., 2017] proposes a linear time approximation of the Shapley values which we discussed in Section 3. This approximation has shortcomings and implicit assumptions about the features which are addressed by newer Shapley value-based explanation techniques. For example, in [Frye et al., 2020a] the input features are not necessarily independent, [Frye et al., 2020b] restricts the permutations based on known causal relationships, and in [Covert et al., 2021] the proposed technique improves the convergence guarantees of the approximation. Several methods generalize SHAP beyond feature values to give attributions to first-order feature interactions [Sundararajan et al., 2020b; Sundararajan et al., 2020a]. However, this requires that the player set is redefined to include feature interaction values.

Deep Learning

In neuron explainability games neurons are players and attributions to the neurons are payoffs. The primary goal of Shapley value-based explanations in deep learning is to solve these games and compute attributions to individual neurons and filters [Ghorbani et al., 2020b; Ancona et al., 2019].

Definition 16. Neuron explainability game. Let us consider fIN(·) the encoder layer of a neural network and x the input feature vector to the encoder. In the neuron explainability game the player set is N = fIN(x) = {h1, . . . , hn} - each player corresponds to the output of a neuron in the final layer of the encoder. The payoff of coalition S ⊆ N is defined as the predicted output v(S) = ̂ yS = fOUT(S) where fOUT(·) is the head layer of the neural network.

In practical terms, the payoffs are the output of the neural network obtained by masking out certain neurons. Using the Shapley values obtained in these games the value of individual neurons can be quantified. At the same time, some deep learning specific Shapley value-based explanation techniques have designs and goals that are aligned with the games described in universal explainability. These methods exploit the structure of the input data [Chen et al., 2018] or the nature of feature interactions [Zhang et al., 2021] to provide efficient computations of attributions.

Graphical Models

Compared to universal explanations the graphical model-specific techniques restrict the admissible set of player set permutations considered in the attribution process. These restrictions are defined based on known causal relations and permutations are generated by various search strategies on the graph describing the probabilistic model [Heskes et al., 2020; Liu et al., 2020; Singal et al., 2021]. Methods are differentiated from each other by how restrictions are defined and how permutations are restricted.

Relational Machine Learning

In the relational machine learning domain the Shapley value is used to create edge importance attributions of instance-level explanations [Duval et al., 2021; Yuan et al., 2021]. Essentially the Shapley value in these games measures the average marginal change in the outcome variable as one adds a specific edge to the edge set in all of the possible edges set permutations. It is worth noting that the edge explanation and attribution techniques proposed could be generalized to provide node attributions.

Definition 17. Relational explainability game. Let us define a graph G = (V, N) where V and N are the vertex and edge sets. Given the relational machine learning model f(·), node feature matrix X, node u ∈ V, the payoff of coalition S ⊆ V in the graph machine learning explanation game is defined as the node level prediction v(S) = ̂ yS,u = f(X, V, S, u).

4.5 Multi-Agent Reinforcement Learning

Global reward multi-agent reinforcement learning problems can be modeled as TU games [Wang et al., 2021a; Li et al., 2021] by defining the player set as the set of agents and the payoff of coalitions as a global reward. The Shapley value allows an axiomatic decomposition of the global reward achieved by the agents and the fair attribution of credit assignments to agents.

4.6 Model Valuation in Ensembles

The Shapley value can be used to assess the contributions of machine learning models to a composite model in ensemble games. In these games, players are models in an ensemble and payoffs are decided by whether an instance level prediction made by the model is correct.

Definition 18. Ensemble game. Let us consider a single target - feature instance denoted by (y, x). The player set in ensemble games is defined by a set of machine learning models N = {fi(·)|1 ≤ i ≤ n} that operate on the feature set. The predicted target output by the ensemble S ⊆ N is defined as ̂ yS = ˜ f (S, x)

where ˜ f(·) is a prediction aggregation function. The payoff of S is v(S) = g(y, ̂ yS) where g(·) is a goodness of fit metric.

The ensemble games described by [Rozemberczki et al., 2021] are formulated as a special subclass of voting games. This allows the use of precise game-specific approximation [Fatima et al., 2008] techniques and because of this the Shapley value estimates are obtained in quadratic time and have a tight approximation error. The games themselves are model agnostic concerning the player set - ensembles can be formed by heterogeneous types of machine learning models that operate on the same inputs.

5 Discussion

The Shapley value has a wide-reaching impact in machine learning, but it has limitations and certain extensions of the Shapley value could have important applications in machine learning.

5.1 Limitations

Computation Time

Computing the Shapley value for each player naively in a TU game takes factorial time. In some machine learning application areas such as multi-agent reinforcement learning and federated learning where the number of players is small, this is not an issue. However, in large scale data valuation [Kwon et al., 2021a; Kwon et al., 2021b], explainability [Lundberg et al., 2017], and feature selection [Patel et al., 2021] settings the exact calculation of the Shapley value is not tractable. In Sections 3 and 4 we discussed approximation techniques proposed to make Shapley value computation possible. In some cases, asymptotic properties of these Shapley value approximation techniques are not well understood - see for example [Chen et al., 2018].

Interpretability

By definition, the Shapley values are the average marginal contributions of players to the payoff of the grand coalition computed from all permutations [Shapley, 1953]. Theoretical interpretations like this one are not intuitive and not useful for non-game theory experts. This means that translating the meaning of Shapley values obtained in many application areas to actions is troublesome [Kumar et al., 2020]. For example in a data valuation scenario: is a data point with a twice as large Shapley value as another one twice as valuable? Answering a question like this requires a definition of a cooperative game that is intuitive.

Axioms Do Not Hold Under Approximations

As we discussed most applications of the Shapley value in machine learning use approximations. The fact that under these approximations the desired axiomatic properties of the Shapley value do not hold is often overlooked [Sundararajan et al., 2020b]. This is problematic because most works argue for the use of Shapley value based on these axioms. In our view, this is the greatest unresolved issue in the application of the Shapley value.

5.2 Future Research Directions

Hierarchy of the Coalition Structure

The Shapley value has a constrained version called Owen value [Owen, 1977] in which only permutations satisfying conditions defined by a coalition structure - a partition of the player set - are considered. The calculation of the Owen value is identical to that of the Shapley value, with the exception that only those permutations are taken into account where the players in any of the subsets of the coalition structure follow each other. In several real-world data and feature valuation scenarios even more complex hierarchies of the coalition, the structure could be useful. Having a nested hierarchy imposes restrictions on the admissible permutations of the players and changes player valuation. Games with such nested hierarchies are called level structure games in game theory. [Winter, 1989] presents the Winter value a solution concept to level structure games - such games are yet to receive attention in the machine learning literature.

Overlapping Coalition Structure

Traditionally, it is assumed that players in a coalition structure are allocated in disjoint partitions of the grand coalition. Allowing players to belong to overlapping coalitions in configuration games [Albizuri et al., 2006] could have several applications in machine learning. For example in a data-sharing - feature selection scenario multiple data owners might have access to the same features - a feature can belong to overlapping coalitions.

Solution Concepts Beyond the Shapley Value

The Shapley value is a specific solution concept of cooperative game theory with intuitive axiomatic properties (Section 2). At the same time it has limitations with respect to computation constraints and interpretability (Sections 3 and 5). Cooperative game theory offers other solution concepts such as the core, nucleolus, stable set, and kernel with their own axiomatizations. For example, the core has been used for model explainability and feature selection [Yan et al., 2021]. Research into the potential applications of these solution concepts is lacking.

6 Conclusion

In this survey we discussed the Shapley value, examined its axiomatic characterizations and frequently used Shapley value approximations. We defined and reviewed its uses in machine learning, highlighted issues with the Shapley value and potential new application and novel research areas in machine learning.

Acknowledgements

This research was supported by REPHRAIN: The National Research Centre on Privacy, Harm Reduction and Adversarial Influence Online (UKRI grant: EP/V011189/1). The authors would like to thank Anton Tsitsulin for feedback throughout the preparation of this manuscript.