Source-linked AI summary
Data Shapley: Equitable Valuation of Data for Machine Learning
Amirata Ghorbani, James Zou
TL;DR
The paper addresses how to value individual training data equitably and compute those values efficiently in supervised learning. It frames data valuation as a cooperative game, estimates marginal contributions with Monte Carlo methods, and shows that the resulting values reveal data quality and acquisition priorities. The framework remains specific to the chosen learning algorithm, evaluation metric, and training set.
Problem
The paper asks how to measure each training datum’s equitable value and compute that value efficiently, given that exact Shapley evaluation is exponentially costly.
Method
DATA SHAPLEY treats training sources as cooperative-game players and estimates their equitable shares by averaging marginal performance contributions across sampled permutations with truncation.
Results
Experiments show that Data Shapley identifies mislabeled data, orders valuable patients more effectively than random ordering or LOO, and values data sources across disease-prediction tasks.
Takeaways & Limitations
Low-value data can flag corruptions, while high-value data can indicate what types of new data may improve a predictor.
Takeaways & Limitations
The framework values data only within the specific context of supervised-learning training sets and depends on the learning algorithm, evaluation metric, and other training points.
Abstract
from arXiv · showhide
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 $n$ 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.
Algorithm 1 Truncated Monte Carlo Shapley
The method estimates each training point’s equitable contribution to predictive performance by averaging marginal contributions across random data permutations. It truncates these computations once additional points contribute little, avoiding the exponential cost of exact Shapley evaluation.
- Algorithm 1 Truncated Monte Carlo Shapley: Data Shapley treats training sources as cooperative-game players whose joint reward is the prediction score achieved through the learning algorithm.Each source receives an equitable share of the cooperation reward.
- Algorithm 1 Truncated Monte Carlo Shapley: Exact Shapley computation requires exponentially many marginal-contribution evaluations, making it impractical for real-world training sets.Each subset evaluation also requires training a predictor with the learning algorithm.
- Algorithm 1 Truncated Monte Carlo Shapley: The algorithm samples random permutations and estimates each datum’s value from its performance improvement when added after previously encountered data.Repeating permutations and averaging marginal contributions improves the Monte Carlo approximation.
- Algorithm 1 Truncated Monte Carlo Shapley: Computations are truncated when marginal contributions become small as the training set grows.The truncation exploits the observed decrease in marginal contribution as more data sources are added.
Applications of DATA SHAPLEY
DATA SHAPLEY uses estimated data value to identify harmful or useful training examples, guide patient acquisition, and improve adaptation to datasets that differ from the training distribution.
- Identifying data quality: Data Shapley identifies low-value data as potentially harmful, supporting the removal of mislabeled, corrupted, or otherwise hurtful training examples.Mislabeled examples are expected to have low value, while increasing white noise lowers noisy images’ value relative to clean images.
- Patient data valuation: Removing low-value patient data can improve predictor performance, whereas removing high-value data causes degradation.The experiments evaluate performance after removing patients in descending and ascending estimated-value order.
- Patient data valuation: High-value patients guide data acquisition: adding patients ordered by estimated value improves performance more effectively than random addition, while low-value additions can hurt performance.The paper estimates candidate-patient values from observables to prioritize recruitment.
- Patient data valuation: Data Shapley can evaluate data sources across centers and reveal sources with negative value when their feature distributions differ from the general population.In UK Biobank disease-prediction experiments, center-level values were computed across 22 health centers.
Related Works
The paper distinguishes Data Shapley from prior uses of Shapley value and from influence-based data valuation methods. These earlier approaches address related problems but do not provide the same equitable valuation framework.
- Shapley value originated in game theory and has been applied to voting, resource allocation, and bargaining.
- Prior machine-learning uses of Shapley value focus on feature importance for interpreting black-box predictive models, not quantifying training-data value.
- Cook’s Distance, leverage, and influence measure how perturbing or deleting points affects regression models, parameters, or predictions.
- These influence-based methods do not satisfy the paper’s equitability conditions and have been reported to have robustness issues.
Discussion
The paper proposes DATA SHAPLEY as an equitable framework for valuing individual training sources, while emphasizing that its interpretation is context-dependent and narrower than personal-data valuation generally.
- DATA SHAPLEY is proposed as an equitable framework for quantifying the value of individual training sources.
- DATA SHAPLEY uniquely satisfies three natural properties of equitable data valuation.
- The framework is limited to valuation in the specific context of training sets for supervised learning algorithms.
- The authors state that DATA SHAPLEY provides quantitative insight rather than prescribing exact compensation, and does not capture privacy or personal association.
- A datum’s Shapley value depends on the learning algorithm, evaluation metric, and other training-set data, so its value can change with context.
Approximating Shapley value of data sources
Exact Shapley values are computationally impractical because they require evaluating exponentially many subsets and training predictors on them. The paper therefore uses permutation-based Monte Carlo estimation and truncation to reduce computation while respecting performance noise.
- Exact Shapley computation is intractable for real-world datasets because it evaluates exponentially many marginal contributions and repeatedly trains predictors.
- Each datum’s contribution is measured relative to the set of data points preceding it in the sampled permutation.
- Monte Carlo estimation samples random permutations and accumulates each datum’s marginal performance contribution as it is added.
- Because test-set performance contains intrinsic noise, the method estimates Shapley values only up to that noise level.
- Truncation stops scanning a permutation when subset performance is within a tolerance of full-data performance and assigns zero to the remaining contributions.
B G-Shapley algorithm
For predictive models trained with stochastic gradient descent, G-Shapley approximates a fully trained model by considering a single pass through randomly selected training batches.
- Many predictive models use stochastic gradient descent, where randomly selected batches iteratively update model parameters.
- G-Shapley uses one pass through training data as a simple approximation to a completely trained model in these settings.
Algorithm 2 Gradient Shapley
Gradient Shapley approximates data valuation by updating a differentiable model one point at a time and using each point’s marginal performance change. Its results are similar to TMC-Shapley and better than leave-one-out in the reported experiments.
- Gradient Shapley: Gradient Shapley updates the model by gradient descent on one data point at a time and uses the resulting performance change as its marginal contribution.The procedure approximates the framework of Algorithm 1 for differentiable loss functions.
- Empirical comparison: G-Shapley produces results similar to TMC-Shapley and better than leave-one-out in label-flip detection and patient data valuation experiments.
C Experimental Details
The experiments evaluate data valuation on corrupted image and text-like biomedical settings, as well as patient-level and center-level disease prediction. They vary datasets, corruption types, predictive models, and valuation granularity.
- Low-quality data: The label-corruption experiments use spam, flower, and dog-versus-fish image data with mislabeled or Gaussian-noise-corrupted training examples.The reported models include Multinomial Naive Bayes, Multinomial Logistic Regression, and logistic regression over Inception-V3 representations.
- Experimental scope: The experimental design compares data value across sources, quality conditions, predictive models, and individual-versus-group valuation settings.
- Patient data valuation: Patient-level disease-prediction experiments sample balanced cohorts from a 500,000-patient source dataset and train logistic regression models.
- Group valuation: Center-level experiments replace individual patients with healthcare centers and use 80% of each disease dataset for training and 10% of the remainder for evaluation.
D Additional Experiments
Additional experiments examine Shapley values on synthetic tasks, across predictive models, and for demographic groups. They report model-dependent rankings, strong group-level effects, and cross-model rank correlations.
- Synthetic Experiments: Shapley valuation identifies the most positively influential training points better than leave-one-out across linear, polynomial, logistic-regression, and neural-network synthetic settings.The experiments use 20 linear and 20 third-order-polynomial datasets, with training sizes of 100 and 1000.
- Synthetic Experiments: The value of data varies with the chosen predictive model, so points that improve a nonlinear model may differ from those benefiting another model.
- Value of different subgroups: Group Shapley values are computed for 146 demographic groups; the most valuable groups are also the most important for model performance.In this experiment, older groups have higher value than younger groups, racial minorities less value, and female groups more value than male groups with respect to Data Shapley.
E How good are the approximations?
The paper evaluates approximation accuracy, truncation, and coherence between G-Shapley and TMC-Shapley. The reported approximations preserve rankings well, while coherence varies by model, dataset, and task.
- Approximation accuracy: 98.4%–99.5% Pearson correlation is observed between true and approximate TMC-Shapley values on synthetic datasets of 4–14 points.
- Robustness to truncation: 25% truncation yields rank correlation around 0.8 with untruncated valuation across the reported datasets and models.Truncation computes marginal contributions only for the early elements of each sampled permutation and assigns zero to the remainder.
- G-Shapley and TMC-Shapley coherency: G-Shapley and TMC-Shapley correlate at 0.9–0.95 for logistic regression on synthetic datasets of size 100, but neural-network correlations fall to 0.7–0.8.At size 1000, the corresponding ranges are 0.94–0.97 for logistic regression and 0.8–0.88 for neural networks.
- G-Shapley and TMC-Shapley coherency: For disease prediction, G-Shapley and TMC-Shapley have correlation coefficients of 0.86 for breast cancer and 0.77 for skin cancer.The skin-cancer values also have rank correlation 0.78.
- G-Shapley and TMC-Shapley coherency: For Fashion MNIST and flower classification, G-Shapley and TMC-Shapley correlation coefficients are 0.62 and 0.57, respectively.
- Robustness to truncation: Truncation approximation bias can be negligible, as shown by performance-removal curves and rank correlations across truncation levels.