PaperlayerView exact revision on arXiv

Source-linked AI summary

A Distributional Framework for Data Valuation

Amirata Ghorbani, Michael P. Kim, James Zou

arXiv:2002.12334v1cs.LGstat.ML

TL;DR

Fixed-dataset data Shapley does not account for the underlying data distribution or provide stable values for points outside a particular dataset. The paper defines distributional Shapley as an expectation over sampled datasets, proves stability properties, and develops D-Shapley for estimation. Its optimized procedures achieve order-of-magnitude computational reductions while retaining estimation quality, and a pricing case study finds generally high agreement between broker and buyer valuations.

  • Problem

    Fixed-dataset data Shapley depends on a particular data draw, omits statistical aspects of the data, and does not provide a way to value points outside that dataset.

  • Method

    Distributional Shapley averages data Shapley over i.i.d. datasets from an underlying distribution, and D-Shapley estimates it using sampled marginal performance gains.

  • Results

    The framework provides stability guarantees and optimized estimation procedures with order-of-magnitude computational reductions while maintaining estimation quality.

  • Takeaways & Limitations

    Distributional Shapley supports values that are less dependent on a fixed dataset and can be used for data pricing across buyers and sellers.

  • Takeaways & Limitations

    The method assumes that the task, learning algorithm, and performance metric are known and fixed.

Abstract

from arXiv · show

Shapley value is a classic notion from game theory, historically used to quantify the contributions of individuals within groups, and more recently applied to assign values to data points when training machine learning models. Despite its foundational role, a key limitation of the data Shapley framework is that it only provides valuations for points within a fixed data set. It does not account for statistical aspects of the data and does not give a way to reason about points outside the data set. To address these limitations, we propose a novel framework -- distributional Shapley -- where the value of a point is defined in the context of an underlying data distribution. We prove that distributional Shapley has several desirable statistical properties; for example, the values are stable under perturbations to the data points themselves and to the underlying data distribution. We leverage these properties to develop a new algorithm for estimating values from data, which comes with formal guarantees and runs two orders of magnitude faster than state-of-the-art algorithms for computing the (non-distributional) data Shapley values. We apply distributional Shapley to diverse data sets and demonstrate its utility in a data market setting.

1 Introduction

Data valuation matters for policy, markets, and machine-learning data selection, but fixed-dataset Shapley values omit distributional variation and can make cross-dataset valuation inconsistent. This work introduces distributional Shapley, develops an estimator with formal guarantees and faster computation, and demonstrates data-pricing consistency.

  • Motivation: Data valuation has policy, economic, and machine-learning implications, including data pricing and prioritizing collection or annotation.A principled valuation framework could support quantifying collected data, buying and selling data, and identifying valuable training data.
  • Prior framework: Prior data Shapley methods assign equitable credit to points in a fixed training set using a learning algorithm and performance metric.Shapley value is used because it uniquely satisfies basic equitable-credit properties, and experiments find it effective for identifying influential points.
  • Limitation: Fixed-dataset valuation disregards statistical properties of the data and can change when the same point appears in a different dataset.This creates a practical problem for data markets, where a point’s price should represent quality within an underlying distribution.
  • Contribution: Distributional Shapley defines a point’s value through the underlying data distribution, rather than only through one fixed dataset.The framework is formulated as an expected data Shapley value over datasets sampled from the distribution and supports stability analysis.
  • Algorithms and evaluation: D-Shapley and its optimized variants provide formally supported estimation procedures, with order-of-magnitude computational reductions while maintaining estimation quality.A data-pricing case study shows that buyers generally agree with broker-provided distributional values, including agreement on set-level value when rank correlation is lower.

2 Distributional Data Valuation

Distributional Shapley replaces fixed-dataset dependence with an expectation over i.i.d. samples from an underlying distribution. Its marginal-contribution characterization supports stability results and unbiased estimation, while examples and theorems describe when values remain meaningful under point and distribution perturbations.

  • Setup: The framework models data as samples from a distribution D and uses a potential U to represent the value of a subset.In supervised learning, U can capture both the learning algorithm and evaluation metric, such as population accuracy for a trained model.
  • Definition: Data Shapley values depend on the particular dataset draw, whereas distributional Shapley averages data Shapley over i.i.d. datasets containing the evaluated point.This removes instability caused by variation in the sampled dataset and defines values for points in the distribution’s universe.
  • Characterization: Distributional Shapley is equivalently the expected marginal increase in U when a point is added to an i.i.d. dataset of uniformly random size.This characterization connects the valuation to expected performance gains and motivates estimation by sampled marginal contributions.
  • Example: mean estimation: For mean estimation with bounded second moments, points closer to the distribution mean than expected have above-average distributional Shapley value.The analytic example also states that a random point’s expected value is a uniform share of the potential for a random dataset.
  • Stability: If U is deletion-stable or Lipschitz-stable, distributional Shapley inherits stability under perturbations to data points and the underlying distribution.Theorem 2.7 supports Lipschitz behavior in the evaluated point, while Theorem 2.8 bounds changes under distribution shifts with U held fixed.
  • Algorithmic implications: The stability results support interpolation of values for unseen points and motivate computational speedups for estimating distributional Shapley.The paper also notes that population-based potentials may themselves depend on the underlying distribution, requiring additional control when distributions change.

3 Efficiently Estimating Distributional Shapley Values

The paper develops D-Shapley and Fast-D-Shapley to estimate distributional Shapley values with unbiasedness and formal accuracy guarantees, then accelerates estimation through weighted sampling and interpolation. Experiments show these methods preserve valuation quality while reducing computation and scaling to large data sets.

  • D-Shapley: D-Shapley estimates each point’s distributional Shapley value from marginal performance changes when the point is added to sampled data sets.The estimator averages marginal contributions computed on samples drawn from the underlying distribution.
  • Computational structure: Reusing one sampled data set across points reduces model-training costs, although it correlates estimation errors between points.The same sample is used to estimate each point’s marginal contribution in an iteration.
  • Formal guarantees: Algorithm 1 produces unbiased estimates with probability at least 1−δ and absolute error at most ε.The guarantee applies simultaneously to the valuated points under the stated iteration conditions.
  • Speeding up D-Shapley: Importance sampling with weights proportional to 1/k improves running time while maintaining ε-accurate unbiased estimates.Theorem 3.2 gives this result under O(1/k)-deletion stability and evaluation-time assumptions.
  • Empirical performance: The speed-ups create a smooth trade-off between computational cost and recovery precision across learning algorithms.The empirical R2 curves show this interpolation across model types, including settings without formal stability guarantees.
  • Large-scale valuation: Combining weighted sampling and interpolation yielded a 500× speed-up for valuating 50K CIFAR10 images.The authors report that prior Shapley-based techniques would make this valuation prohibitively expensive.

4 Case Study: Consistently Pricing Data

The case study evaluates whether a broker can price data using distributional Shapley values that align with buyers’ valuations, without exchanging data beforehand. Across datasets, seller estimates generally correlate highly with buyer values, and broker-guided point additions match buyer-guided additions while outperforming random ordering.

  • Case-study setup: The broker estimates values for a sold set S using distributional Shapley, while buyers evaluate the same points using data Shapley on B ∪ S.The setting compares seller estimates ν(z; U, D, m) with buyer values φ(z; U, B ∪ S), where buyers and sellers hold separate datasets.
  • Practical implication: The framework lets a broker estimate prices without exchanging data upfront, with values expected to reflect buyers’ valuations when their private data are drawn from a distribution close to D.This addresses financial and legal concerns that may prevent the broker and buyer from sharing data before purchase.
  • Case-study setup: The study evaluates four datasets in which buyers hold 100 or 500 points and brokers sell equally sized datasets.Buyers run TMC-Shapley on B ∪ S to obtain observed values for the sold points.
  • Valuation consistency: Rank correlation between broker and buyer valuations is generally high, while seller estimates are approximately unbiased and have low absolute percentage error.Even when rank correlation is approximately 0.6, the seller and buyer agree on the value of the dataset as a whole.
  • Point-addition experiment: In the Diabetes130 point-addition experiment, broker-guided and buyer-guided additions produce similar accuracy gains, and both outperform random ordering after all sold points are added.The resulting models achieve essentially the same final performance under the two informed orderings.

5 Discussion

The discussion presents distributional Shapley as a more statistically stable alternative to fixed-dataset valuation, while identifying assumptions that remain unresolved. It also points toward privacy-preserving data valuation as a future research direction.

  • Contributions: Distributional Shapley removes dependence on a fixed dataset, reducing valuation inconsistencies caused by sampling artifacts.Its stability results under perturbations to inputs and the underlying distribution are not generally true for original data Shapley.
  • Contributions: The framework provides stronger theoretical guarantees and order-of-magnitude speed-ups over prior estimation schemes across diverse tasks.These results support broader practical use of Shapley-based data valuation.
  • Limitation: The method assumes that the task, learning algorithm, and performance metric are known and fixed through the potential U.Reducing dependence on these assumptions is identified as a direction for future investigation.
  • Future direction: Because data Shapley values depend on every other point in a dataset, distributional marginalization may enable valuations satisfying strong privacy notions such as differential privacy.The discussion frames privacy-preserving valuation as an open research question rather than an established result.

A Review of Shapley Axioms

The review introduces Shapley’s axioms as criteria for equitable data valuation and explains how distributional Shapley inherits several of them. It also establishes an on-average form of efficiency.

  • Setup: Shapley’s framework evaluates data points in a finite dataset using a potential function that measures overall model value.The data Shapley value φ(z; U, B) is defined for a point z in a finite set B.
  • Axioms: Symmetry requires equivalent points to receive equal values.The condition compares points whose marginal contributions are identical for every subset excluding them.
  • Axioms: The null-player axiom assigns zero value to a point that adds no marginal gain to any subset.This captures the requirement that a non-contributing point receives no credit.
  • Axioms: Additivity requires a point’s value for combined potentials to equal the sum of its values for the separate potentials.This treats the value of a point across two combined tasks as the sum of its task-specific values.
  • Distributional extension: The classical Shapley value is uniquely characterized by symmetry, the null-player axiom, and additivity, while distributional Shapley inherits these properties and satisfies an on-average efficiency variant.The distributional properties follow by linearity of expectation.

B Distributional Shapley Value for Mean Estimation

For mean estimation, distributional Shapley is analyzed using the empirical mean under a distribution with bounded second moments. The resulting value is expressed through the estimator’s expected error and explicit m-dependent constants.

  • Result: The resulting value is expressed using the mean-estimation error and explicit constants depending on the maximum sample size m.The analysis identifies C(m)=2−1/m+c(m)=Θ(1) and an explicit constant C_m=Θ(1) determined by m.
  • Setup: The analysis considers empirical mean estimation for a distribution D over R^d with mean µ and bounded second moments.For a sample set S, the estimator is the sample average ˆµ_S, and the empty-set potential is defined as U(∅)=0.
  • Distributional Shapley expansion: Distributional Shapley is expanded into expected marginal changes when a point z is added to samples drawn from D.The expansion relates ˆµ_{S∪{z}} to ˆµ_S and separates the analysis by sample size k.
  • Proof simplification: The proof simplifies the expansion by using unbiasedness of ˆµ_S, expectation identities, and inner-product calculations.These steps reduce the terms involving z and the sample mean to expressions involving the estimator’s squared error.

C Lipschitz Stability of RKHS

The paper defines a metric for labeled examples using an RKHS feature map and studies regularized empirical risk minimization under convex Lipschitz loss. It proves that the resulting potential is Lipschitz stable, with stability controlled by loss smoothness, feature norms, regularization, and sample size.

  • Metric and RKHS setup: The RKHS setup uses a feature map ϕ:X→F and compares labeled points through a metric based on feature-space distance.Points with different labels are treated as arbitrarily dissimilar, while same-label points are compared using the RKHS norm.
  • Learning potential: The potential U_F is the population loss of a regularized empirical risk minimizer trained on a subset S.The loss is assumed convex and L-Lipschitz, with regularization parameter λ>0 and empirical error er_S(f).
  • Stability result: The RKHS learning potential is (2L^2R/λk)-Lipschitz stable with respect to d_F.Here R=E_D[∥ϕ(x)∥_F], so stability worsens with the loss Lipschitz constant and feature norm and improves with regularization and sample size.
  • Stability proof: For same-label replacements, the proof compares empirical minimizers using convexity, Lipschitzness, and Cauchy–Schwarz.The argument bounds the change in population performance after replacing one example and applies to every interpolation parameter α∈[0,1].
  • Interpretation: Lipschitz stability generalizes replacement stability when the metric is nontrivial.The paper notes that regularized RKHS empirical risk minimization satisfies this stronger notion.

D.2 Running time analysis under stability.

The running-time analysis estimates distributional Shapley values by sampling subset sizes and reweighting marginal contributions. Nonuniform sampling can exploit deletion stability to reduce computation while preserving unbiasedness and accuracy guarantees.

  • Algorithmic guarantee: Algorithm 2 produces unbiased, ε-accurate estimates for all selected points with probability at least 1−δ.Its expected runtime depends on the number of evaluated points, the sampling weights, and the cost R(k) of evaluating a set of size k.
  • Estimator construction: Sampling k with probability w_k, evaluating marginal contributions on S∼D^k, and reweighting yields an unbiased estimate of ν(z;U,D,m).Averaging independently sampled contributions across k preserves unbiasedness for the distributional Shapley value.
  • Accuracy analysis: Deletion stability bounds each reweighted contribution by β(k)/(w_km), enabling concentration-based ε-accuracy guarantees.Hoeffding’s inequality is applied after accounting for the stability factor and sampling probability.
  • Runtime bound: The total runtime is RT_w(m)=p·|Z|·log(|Z|/δ)·(Σ_{k=1}^m w_kR(k)).The expression accounts for the expected number of selected points and the cost of evaluating models at sampled subset sizes.
  • Sampling schemes: For β(k)=k^−b and R(k)=k^c, uniform sampling has a polynomial runtime determined by b and c.The analysis considers b≥1/2 and c≥1 before comparing against stability-aware sampling.
  • Sampling schemes: The biased scheme w_k∝k^{1−2b} saves roughly a factor m^{2b−1}, or roughly m when U is O(1/k)-deletion stable.The weighting keeps the relevant summation logarithmically bounded while reducing computation.

D.3 Finite Sample Approximation to D

The running-time analysis also yields a sample-complexity interpretation when each iteration draws a fresh sample from D. Setting R(k)=k converts the computational bound into the cost of resampling these subsets.

  • Sample-complexity interpretation: Taking R(k)=k interprets each iteration as drawing a fresh sample S∼D^k, so the runtime bound becomes a sample-complexity bound.This connects the number of sampled data points per iteration to the algorithm’s overall estimation cost.

E Additional Performance Experiments

Additional experiments evaluate D-Shapley point-removal behavior under interpolation and weighted-sampling speed-ups, including CIFAR10.

  • Order-of-magnitude speed-ups produce no qualitative change in D-Shapley point-removal performance.The interpolation and weighted-sampling strategies are evaluated independently.
  • Supplementary Figure 1 plots point-removal curves across two machine-learning tasks and three learning algorithms.The curves use weighted sampling and interpolation.
  • E.1 Speeding-up Distributional Shapley for Cifar10: CIFAR10 experiments apply weighted sampling with speed-up factor 10 and interpolation with speed-up factor 50 to value 1,000 data points.Values are based on effects on an image-classification task.
  • E.1 Speeding-up Distributional Shapley for Cifar10: Supplementary Figure 2 reports a CIFAR10 point-removal experiment using distributional Shapley estimates computed by Fast-D-Shpaley.

F Additional Case Study Experiments

Additional case studies evaluate data valuation across large datasets, varied feature structures, classification tasks, and learning models, alongside an acquisition-order comparison.

  • The case studies use four large-scale datasets from the UCI repository.
  • Datasets and models: Covertype contains 581,012 samples with 54 visual features, seven forest-cover classes, and a Random Forest model.
  • Datasets and models: Diabetes130 contains 100,000 samples with 54 patient and hospital features, predicting hospital readmission with AdaBoost.
  • Datasets and models: Wearable Computing contains 165,632 points with 18 attributes and five postures, evaluated using multinomial logistic regression.
  • Datasets and models: Sensorless Drive Diagnosis contains 58,509 data points.
  • Acquisition-order comparison: Supplementary Figure 3 compares adding acquired points in D-Shapley, TMC, and random orders using accuracy change relative to the buyer’s initial dataset.Shading indicates standard error of the mean.
Loading 2002.12334v1…