As data becomes the fuel driving technological and economic growth, a fundamental challenge is how to quantify the value of data in algorithmic predictions and decisions. For example, in healthcare and consumer markets, it has been suggested that individuals should be compensated for the data that they generate, but it is not clear what is an equitable valuation for individual data. In this work, we develop a principled framework to address data valuation in the context of supervised machine learning. Given a learning algorithm trained on @math data points to produce a predictor, we propose data Shapley as a metric to quantify the value of each training datum to the predictor performance. Data Shapley value uniquely satisfies several natural properties of equitable data valuation. We develop Monte Carlo and gradient-based methods to efficiently estimate data Shapley values in practical settings where complex learning algorithms, including neural networks, are trained on large datasets. In addition to being equitable, extensive experiments across biomedical, image and synthetic data demonstrate that data Shapley has several other benefits: 1) it is more powerful than the popular leave-one-out or leverage score in providing insight on what data is more valuable for a given learning task; 2) low Shapley value data effectively capture outliers and corruptions; 3) high Shapley value data inform what type of new data to acquire to improve the predictor.
@cite_31: 
@cite_4: 
@cite_22: 
@cite_8: The Shapley value is a key solution concept for coalitional games in general and voting games in particular. Its main advantage is that it provides a unique and fair solution, but its main drawback is the complexity of computing it (e.g., for voting games this complexity is #p-complete). However, given the importance of the Shapley value and voting games, a number of approximation methods have been developed to overcome this complexity. Among these, Owen's multi-linear extension method is the most time efficient, being linear in the number of players. Now, in addition to speed, the other key criterion for an approximation algorithm is its approximation error. On this dimension, the multi-linear extension method is less impressive. Against this background, this paper presents a new approximation algorithm, based on randomization, for computing the Shapley value of voting games. This method has time complexity linear in the number of players, but has an approximation error that is, on average, lower than Owen's. In addition to this comparative study, we empirically evaluate the error for our method and show how the different parameters of the voting game affect it. Specifically, we show the following effects. First, as the number of players in a voting game increases, the average percentage error decreases. Second, as the quota increases, the average percentage error decreases. Third, the error is different for players with different weights; players with weight closer to the mean weight have a lower error than those with weight further away. We then extend our approximation to the more general k-majority voting games and show that, for n players, the method has time complexity O(k^2n) and the upper bound on its approximation error is O(k^2 n).
@cite_9: We present a general method for explaining individual predictions of classification models. The method is based on fundamental concepts from coalitional game theory and predictions are explained with contributions of individual feature values. We overcome the method's initial exponential time complexity with a sampling-based approximation. In the experimental part of the paper we use the developed method on models generated by several well-known machine learning algorithms on both synthetic and real-world data sets. The results demonstrate that the method is efficient and that the explanations are intuitive and useful.
@cite_29: 
@cite_20: 
@cite_3: 
@cite_0: 
@cite_15: Algorithmic systems that employ machine learning play an increasing role in making substantive decisions in modern society, ranging from online personalization to insurance and credit decisions to predictive policing. But their decision-making processes are often opaque -- it is difficult to explain why a certain decision was made. We develop a formal foundation to improve the transparency of such decision-making systems. Specifically, we introduce a family of Quantitative Input Influence (QII) measures that capture the degree of influence of inputs on outputs of systems. These measures provide a foundation for the design of transparency reports that accompany system decisions (e.g., explaining a specific credit decision) and for testing tools useful for internal and external oversight (e.g., to detect algorithmic discrimination). Distinctively, our causal QII measures carefully account for correlated inputs while measuring influence. They support a general class of transparency queries and can, in particular, explain decisions about individuals (e.g., a loan decision) and groups (e.g., disparate impact based on gender). Finally, since single inputs may not always have high influence, the QII measures also quantify the joint influence of a set of inputs (e.g., age and income) on outcomes (e.g. loan decisions) and the marginal influence of individual inputs within such a set (e.g., income). Since a single input may be part of multiple influential sets, the average marginal influence of the input is computed using principled aggregation measures, such as the Shapley value, previously applied to measure influence in voting. Further, since transparency reports could compromise privacy, we explore the transparency-privacy tradeoff and prove that a number of useful transparency reports can be made differentially private with very little addition of noise. Our empirical validation with standard machine learning algorithms demonstrates that QII measures are a useful transparency mechanism when black box access to the learning system is available. In particular, they provide better explanations than standard associative measures for a host of scenarios that we consider. Further, we show that in the situations we consider, QII is efficiently approximable and can be made differentially private while preserving accuracy.
@cite_34: A value theory is developed for voting games in which a sizable fraction or the total vote is controlled by a few major players and the rest is distributed among a continuous infinity of individually insignificant minor players. The latter are referred to collectively as an “ocean,” to suggest the total lack of order or cohesion that is assumed.
@cite_13: 
@cite_25: 
@cite_12: Preface 1. Introduction to the Shapley value Alvin E. Roth Part I. Ancestral Papers: 2. A value for n-person games Lloyd S. Shapley 3. A method for evaluating the distribution of power in a committee system Lloyd S. Shapley and Martin Shubik Part II. Reformulation and Generalizations: 4. The expected utility of playing a game Alvin E. Roth 5. The Shapley-Shubik and Banzhaf power indices as probabilities Philip D. Straffin, Jr. 6. Weighted Shapley values Ehud Kalai and Dov Samet 7. Probabilistic values for games Robert James Weber 8. Combinatorial representations of the Shapley value based on average relative payoffs Uriel G. Rothblum 9. The potential of the Shapley value Sergiu Hart and Andreu Mas-Colell 10. Multilinear extensions of games Guillermo Owen Part III. Coalitions: 11. Coalitional value Mordecai Kurz 12. Endogenous formation of links between players and the coalitions: an application of the Shapley value Robert J. Aumann and Roger B. Myerson Part IV. Large Games: 13. Values of large finite games Myrna Holtz Wooders and William R. Zame 14. Payoffs in nonatomic economics: an axiomatic approach Pradeep Dubley and Abraham Neyman 15. Values of smooth nonatomic games: the method of multilinear approximation Dov Monderer and Abraham Neyman 16. Nondifferentiable TU markets: the value Jean-Francois Mertens Part V. Cost Allocation and Fair Division: 17. Individual contribution and just compensation H. P. Young 18. The Aumann-Shapley prices: a survey Yair Tauman Part VI. NTU Games: 19. Utility comparison and the theory of games Lloyd S. Shapley 20. Paths leading to the Nash set Michael Maschler, Guillermo Owen and Bezalel Peleg.
@cite_17: Understanding why a model makes a certain prediction can be as crucial as the prediction's accuracy in many applications. However, the highest accuracy for large modern datasets is often achieved by complex models that even experts struggle to interpret, such as ensemble or deep learning models, creating a tension between accuracy and interpretability. In response, various methods have recently been proposed to help users interpret the predictions of complex models, but it is often unclear how these methods are related and when one method is preferable over another. To address this problem, we present a unified framework for interpreting predictions, SHAP (SHapley Additive exPlanations). SHAP assigns each feature an importance value for a particular prediction. Its novel components include: (1) the identification of a new class of additive feature importance measures, and (2) theoretical results showing there is a unique solution in this class with a set of desirable properties. The new class unifies six existing methods, notable because several recent methods in the class lack the proposed desirable properties. Based on insights from this unification, we present new methods that show improved computational performance and or better consistency with human intuition than previous approaches.
Shapley value was proposed in a classic paper in game theory @cite_29 and has been widely influential in economics @cite_12 . It has been applied to analyze and model diverse problems including voting, resource allocation and bargaining @cite_34 @cite_13 . To the best of our knowledge, Shapley value has not been used to quantify data value in a machine learning context like ours. Shapley value has been recently proposed as a feature importance score for the purpose of interpreting black-box predictive models @cite_9 @cite_15 @cite_17 @cite_4 @cite_0 @cite_25 . Their goal is to quantify, for a given prediction, which features are the most influential for the model output. Our goal is very different in that we aim to quantify the value of individual data points (not features). There is also a literature in estimating Shapley value using Monte Carlo methods, network approximations, as well as analytically solving Shapley value in specialized settings @cite_8 @cite_22 @cite_20 @cite_31 @cite_3