Towards Efficient Data Valuation Based on the Shapley Value
Authors:
Preprint
Abstract
"How much is my data worth?" is an increasingly common question posed by organizations and individuals alike. An answer to this question could allow, for instance, fairly distributing profits among multiple data contributors and determining prospective compensation when data breaches happen. In this paper, we study the problem of data valuation by utilizing the Shapley value, a popular notion of value which originated in coopoerative game theory. The Shapley value defines a unique payoff scheme that satisfies many desiderata for the notion of data value. However, the Shapley value often requires exponential time to compute. To meet this challenge, we propose a repertoire of efficient algorithms for approximating the Shapley value. We also demonstrate the value of each training instance for various benchmark datasets.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- A Novel Feature Selection Technique for Improved Survivability Diagnosis of Breast CancerProcedia Computer Science, 2015
- Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al QaedaEuropean Journal of Operational Research, 2013
- Using cooperative game theory to optimize the feature selection problemNeurocomputing, 2012
- Sampling Algorithms and Coresets for $\ell_p$ RegressionSIAM Journal on Computing, 2009
- A linear approximation method for the Shapley valueArtificial Intelligence, 2008
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Time-consistent Shapley value allocation of pollution cost reductionJournal of Economic Dynamics and Control, 2003
- On the Complexity of Cooperative Solution ConceptsMathematics of Operations Research, 1994
- Bargaining Foundations of Shapely ValueEconometrica, 1989