Source-linked AI summary
Towards Efficient Data Valuation Based on the Shapley Value
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gurel, Bo Li, Ce Zhang, Dawn Song, Costas Spanos
TL;DR
The paper addresses how to value data contributed to machine-learning models when contributors differ and exact Shapley-value computation is infeasible. It develops theoretical and practical Shapley-value estimators, including information-sharing, stability-based, group-testing, and influence-function approaches. The algorithms provide efficient estimation guarantees or practical acceleration across supported settings, and the paper demonstrates training-instance values on benchmark datasets.
Problem
Allocating revenue fairly among machine-learning data contributors is important, but exact Shapley-value computation requires exponentially many expensive utility evaluations.
Method
The paper develops theoretical and machine-learning-specific Shapley-value estimators using information sharing, group testing, learning stability, incremental training, and influence functions.
Results
Theoretical estimators achieve O(N(log N)^2) model evaluations, or O(log log N) training in sparse monotone settings with incremental maintenance, while experiments demonstrate runtime comparisons and training-instance values.
Takeaways & Limitations
The paper provides a repertoire of Shapley-value estimation techniques for data valuation in different computational and machine-learning settings.
Takeaways & Limitations
The practical methods rely on assumptions such as learning stability or smooth loss functions, and influence-function estimates lack provable approximation guarantees.
Abstract
from arXiv · showhide
"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.
1 Introduction
Data valuation is needed to allocate revenue fairly among contributors, but the Shapley value is computationally expensive at realistic scales. The paper develops theoretical and practical approximation algorithms for applying it to machine-learning data.
- Motivation: Machine-learning data often comes from multiple entities with widely varying quality, creating a need to allocate model-generated revenue fairly.The motivation includes distributing payments from analysts back to patients in data markets.
- Motivation: The Shapley value offers a unique allocation scheme with properties interpreted as fairness, rationality, and decentralizability.It models contributors as players in a coalitional game whose subset utility is measured by a utility function.
- Computational challenge: Exact Shapley-value computation requires exponentially many utility evaluations, while evaluating machine-learning utility may itself require expensive model training.This limits prior applications largely to stylized settings with simple utility functions and closed-form values.
- Theoretical contribution: O(N(log N)^2) model evaluations suffice for provable Shapley-value approximation, while sparse monotone settings can reduce training to O(log log N) with incremental maintenance.The two theoretical algorithms share information across model evaluations and are context-agnostic.
- Practical contribution: The paper introduces two machine-learning-specific estimators: uniform value division under learning stability and influence functions for models with smooth loss functions.The stability-based method is difficult to prove for complex models, while influence-function estimates lack provable approximation guarantees.
2 Related Work
Prior work studies Shapley-value estimation and training-data importance, but data valuation imposes different assumptions and fairness requirements. The paper positions its algorithms as more efficient approaches tailored to data valuation.
- Shapley-value estimation: Sampling-based Shapley-value estimation requires O(N log N) samples for bounded utilities under l∞ error and O(N^2 log N) under l2 error.Related work also considers binary-output utility functions and exploits special utility properties for improved approximation.
- Shapley-value estimation: Shapley values have been applied to feature selection, but assumptions used for feature valuation do not generally hold for data valuation.The paper states that studying Shapley values specifically for data valuation yields more efficient algorithms than previous approaches.
- Training-data importance: Training-data importance methods support model understanding, dataset-error detection, and removal of least influential data to reduce SVM training cost.Examples include influence functions for smooth parametric models and variants for non-parametric models.
- Training-data importance: Existing coreset methods provide weighted subsets with competitive models, but their compliance with data-valuation properties such as fairness remains unclear.The paper leaves comparison of these distinct approaches for future work.
3 Problem Formulation
The paper formulates data valuation as distributing the utility of a dataset among users and uses the Shapley value to assign each user an average marginal contribution. Its axioms encode complete allocation, fairness, and additivity.
- Problem formulation: Given data points from N users, a utility function U(S) measures the value of any subset, with U(∅)=0 and total utility U(I) distributed among users.The valuation function assigns user i a value s(U,i), abbreviated as s_i when the utility is clear.
- Shapley value: The Shapley value assigns user i the average marginal contribution of their data across all subsets formed by the other users.Equivalently, users are ordered randomly and each receives the marginal contribution of their data when it is added.
- Axioms: Group rationality requires the entire dataset utility to be distributed among all users.This expresses complete distribution of the coalition’s total yield.
- Axioms: Fairness gives equivalent users equal values and assigns zero value to users with zero marginal contributions for every subset.The property makes valuation depend on utility response to data presence rather than user names.
- Axioms: Additivity requires values under multiple utilities to sum to the value under their combined utility.This supports value calculation when data serves multiple applications with separate utility functions.
4 Efficient SV Estimation
The paper develops efficient algorithms to approximate Shapley values for data valuation, reducing the model evaluations needed for large datasets while retaining error guarantees under stated assumptions.
- Computational challenge: Exact Shapley-value computation requires O(2^N) utility evaluations, and ML utility evaluations can themselves require costly model training.This computational burden limits direct Shapley-value data valuation at large scale.
- Group testing-based approach: Group testing estimates pairwise Shapley differences from pooled utility evaluations, then recovers individual values by solving a feasibility problem.The method treats data points as items and pooled tests as evaluations of selected subsets.
- Group testing-based approach: O(N(log N)^2) utility evaluations suffice for the group-testing method to achieve an (ϵ, δ)-approximation, versus O(N^2 log N) for the baseline.Each group-testing test requires one utility evaluation, enabling the stated reduction in model evaluations.
- Exploiting sparsity: Under monotonicity and sparse Shapley values, compressive permutation sampling requires O(N log(N) log(log(N))) utility evaluations.For incrementally trainable models, the guarantee requires only O(log log(N)) full model training.
- Stable learning algorithms: For uniformly stable learning algorithms, pairwise Shapley differences shrink as N grows, making uniform value division an (ϵ, 0)-approximation under the stated condition.The result bounds the Shapley difference using the algorithm’s stability parameter and supports equal allocation when the condition holds.
- Influence-function heuristic: Influence functions accelerate valuation by approximating parameter changes without retraining, but the resulting estimates lack provable approximation-error guarantees.The influence-function approach is proposed for smooth loss functions; its efficiency therefore involves a trade-off in guarantees.
5 Experimental Results
Experiments compare Shapley-value approximation methods across accuracy, runtime, sparsity, regularization, privacy, and adversarial-example settings. The results show substantial efficiency gains, assumption-dependent accuracy trade-offs, and data values that vary with noise, regularization, and attack alignment.
- Comparing Approximation Accuracy: The largest-S influence approximation correlates with other techniques but cannot recover the true Shapley value.On iris, permutation sampling, group testing, and all-S influence produced the closest approximations to one another.
- Runtime comparison: The group testing-based method outperforms permutation sampling by several orders of magnitude for large datasets.Influence-function heuristics and stratified sampling can reduce computational costs further.
- Approximation under sparsity assumptions: For a fixed approximation error, compressive permutation sampling requires significantly fewer samples and model evaluations than baseline permutation sampling.Its advantage becomes less evident in the large-sample regime.
- Stable learning algorithms: Increasing regularization initially lowers the variance of ridge-regression data values, but excessive regularization increases that variance.The variance equals the approximation error of uniform value division.
- Value for Privacy-Preserving Data: Data value decreases as privacy noise increases in the MNIST privacy-preserving data experiment.Testing accuracy on normal images serves as the utility function.
- Value for Adversarial Examples: Adversarial-example values increase as testing data become more adversarial, while benign-example values decrease.Training adversarial examples are more valuable when generated by the same attack algorithm used for testing.
6 Conclusion
The paper adopts the Shapley value for data valuation and develops techniques to estimate it efficiently across different scenarios, while identifying several directions for future work.
- The paper develops a repertoire of techniques for estimating the Shapley value in different data-valuation scenarios.
- The authors identify continued development of efficient valuation methods for machine-learning models as future work.
- Future directions also include studying stable coalitions in data valuation and applying the techniques to real-world data collection and dissemination.
B Proof of Lemma 2
The proof bounds the pairwise Shapley-value estimation errors and uses these bounds to obtain a high-probability l2 approximation for the full value vector.
- With probability at least 1−δ/N, the proof establishes |s_i−ŝ_i| ≤ 2ϵ′ for the relevant Shapley-value estimate.
- The coordinatewise bound implies ∥ŝ−s∥∞ ≤ 2ϵ′ = ϵ/√N with probability at least 1−δ.
- Using √N∥ŝ−s∥∞ = ϵ, the proof concludes that ∥ŝ−s∥2 ≤ ϵ with probability at least 1−δ.
C Proof of Theorem 3
The proof analyzes randomized comparisons between data points, controls their estimation error with Bennett’s inequality, and derives the test complexity needed for an l2 Shapley-value approximation.
- Bennett’s inequality converts T sampled comparisons into approximation guarantees for pairwise Shapley-value differences.
- Algorithm 1 returns an (ϵ,δ)-approximation in l2-norm when the number of tests satisfies the theorem’s stated lower bound.
- The proof samples Boolean inclusion variables and compares two data points through the utility difference Δ = β_iU(β) − β_jU(β).
- Because Δ is zero when β_i = β_j, the proof exploits the resulting variance reduction when equal inclusion states are sufficiently likely.
- Using Z ≤ 2(log(N−1)+1), the resulting model-evaluation complexity is O(N(log N)^2).
D Proof of Theorem 4
The theorem gives sufficient sample and test conditions for Algorithm 2 under a monotone utility function, with the proof combining concentration and restricted-isometry arguments.
- Assuming monotone U(·), the theorem requires M ≥ C′(K log(N/(2K)) + log(2/δ)) and a corresponding lower bound on T.
- The proof uses concentration bounds to control the measurement error of the sampled estimates.
- Random matrix theory supplies a restricted-isometry condition, with δ_2K ≤ C_δ = 0.465 holding with probability at least 1−δ/2 under the stated sampling requirement.
- Under these conditions, Algorithm 2’s output satisfies the theorem’s approximation guarantee with probability at least 1−δ.
E Proof of Theorem 5
This section proves Theorem 5 using λ-stable utility functions and shows that the resulting Shapley difference vanishes as N grows.
- Proof setup: A λ-stable utility function is introduced as the basis for proving Theorem 5.The proof then uses this definition to establish a property of the associated Shapley values.
- Proposition 7: Proposition 7 states a relation between Shapley values calculated from λ-stable utility functions for distinct users.The proposition applies to all distinct i, j ∈ I.
- Utility and bound: The utility of a dataset is defined as U(D) = M − Ltest(A(D), Dtest), with Cstab appearing in the bound.Here, |S| denotes the training-set size, and Cstab is a constant.
- Conclusion: The bound contains the factor (1+log(N−1))/(N−1), so the Shapley difference vanishes as N →∞.Combining this inequality with Proposition 7 completes the theorem.
F Proof of Theorem 6
This section proves Theorem 6 by analyzing a normalized value-attribution scheme and showing when it is additive across utility functions.
- Non-additivity: The attribution scheme is generally non-additive: ˆs(U + V, i) ≠ ˆs(U, i) + ˆs(V, i).The theorem identifies an explicit condition under which additivity can hold.
- Proof: For W(S) = U(S) + V(S), the combined attribution uses CW times the sum of the marginal utilities of U and V.This follows by directly expanding the definition under W.
G Theoretical Results on the Baseline Permutation Sampling
This section describes permutation sampling for estimating Shapley values and gives a finite-sample error guarantee for the baseline method.
- Estimator: The estimator averages marginal contributions across T permutations, with each permutation assigned probability 1/N!.The construction uses permutation-based Shapley estimates for each training point.
- Theoretical guarantee: Theorem 8 gives the required sample size for utility range r, error bound ϵ, and confidence 1−δ.The theorem provides a finite-sample guarantee for the estimator.
- Proof of guarantee: The proof combines a union bound with Hoeffding’s inequality to obtain the stated error control.It then bounds the Euclidean estimation error through ∥ˆs − s∥2.
- Baseline algorithm: The experimental baseline is a permutation sampling-based approach adapted from Maleki et al. and presented as Algorithm 3.Algorithm 3 takes a utility function, measurement count M, and permutation count T, and outputs Shapley estimates for N training points.