Towards Efficient Data Valuation Based on the Shapley Value

By Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nicholas Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, Costas J. Spanos. 2019

573 citations recorded by the source corpus.

{\em ``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 \emph{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 \emph{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.

Subfields: Economics and Econometrics, Information Systems, Management Science and Operations Research, Optimization & Training, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Information Systems

In Management Science and Operations Research

In Optimization & Training

In Evaluation & Benchmarks

Citations in the corpus

Understanding Dataset Difficulty with V-Usable Information (2021, neutral): “Influence functions (Koh & Liang, 2017), forgetting events (Toneva et al., 2018), and the Data Shapley (Ghorbani & Zou, 2019; Jia et al., 2019) can all be used to assign point-wise estimates of importance to data instances based on their contribution to the decision boundary.”
Foundation Models and Fair Use (2023, neutral): “…attribution refers to methods that assign attribution scores to training examples to understand the contribution of individual examples (or group of examples) to (test-time) model predictions (Koh & Liang, 2017; Ghorbani & Zou, 2019; Jia et al., 2019; Pezeshkpour et al., 2021; Ilyas et al., 2022).”
Online Class-Incremental Continual Learning with Adversarial Shapley Value (2020, methodology): “Efﬁcient KNN Shapley Value Computation Speciﬁc to our requirements for data valuation in this paper, recent work has developed an efﬁcient method for SV computation in a KNN classiﬁcation framework (Jia et al. 2019a).”
FedCoin: A Peer-to-Peer Payment System for Federated Learning (2020, methodology): “Currently, the most widely adopted method for fair assessment of FL client contribution is that of Shapley Values (SVs) [Jia et al., 2019; Song et al., 2019].”
Information-Theoretic Measures of Dataset Difficulty (2021, background): “Inﬂuence functions (Koh and Liang, 2017), forgetting events (Toneva et al., 2018), and the Data Shapley (Ghorbani and Zou, 2019; Jia et al., 2019) can all be used to assign pointwise estimates of importance to data instances, but importance tends to refer to their contribution to the decision…”
TRAK: Attributing Model Behavior at Scale (2023, unknown): “…of leveraging data attribution for a variety of downstream applications, ranging from explaining predictions (Koh & Liang, 2017; Kong et al., 2022), cleaning datasets (Jia et al., 2019), removing poisoned examples (Lin et al., 2022) to quantifying uncertainty (Alaa & Van Der Schaar, 2020).”
Beyond User Self-Reported Likert Scale Ratings: A Comparison Model for Automatic Dialog Evaluation (2020, methodology): “In Stage 3, we aim to identify and remove dialogs with noisy self-reported user ratings yi with data Shapley value technique (Ghorbani and Zou, 2019; Jia et al., 2019a,b).”
Retrospective Adversarial Replay for Continual Learning (2022, methodology): “ASER [55] proposes using the kNN-specific Shapley value [24, 54] to select replay samples that are representative of the buffer and adversarially close to the decision boundaries of incoming classes.”
On the Accuracy of Influence Functions for Measuring Group Effects (2019, methodology): “They can also be used to approximate Shapley values, which are a different but related way of measuring the effect of data points; see, e.g., Jia et al. (2019) and Ghorbani and Zou (2019).”
Estimating Training Data Influence by Tracking Gradient Descent (2020, background): “(Jia et al., 2019; Ghorbani & Zou, 2019) identify the inﬂuence of training examples on the overall accuracy of the model.”
A Sustainable Incentive Scheme for Federated Learning (2020, result): “Similar to Richardson et al. , 10 ; 9 Jia et al. computes a Shap-ley value to split reward among data owners.”
Adversarial Shapley Value Experience Replay for Task-Free Continual Learning (2020, methodology): “ASER is inspired by the Shapley value (SV) [30] used in cooperative game theory to fairly distribute total gains to all players — in our CL setting, we use the SV to determine the contribution of memory samples to learning performance [11, 12, 13].”
Datamodels: Predicting Predictions from Training Data (2022, methodology): “Finally, another related line of work (Ghorbani & Zou, 2019; Jia et al., 2019; Wang et al., 2021) uses Shapley values (Shapley, 1951) to assign a value to datapoints based on their contribution to some aggregate metric (e.g., test accuracy).”