PaperlayerView exact revision on arXiv

Source-linked AI summary

Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning

Yongchan Kwon, James Zou

arXiv:2110.14049v2cs.LGstat.ML

TL;DR

Machine-learning data valuation needs to quantify individual training-data contributions despite noisy data and questionable uniform weighting in Data Shapley. The paper proposes Beta Shapley by relaxing efficiency, develops theory and efficient estimation, and reports stronger performance across several valuation tasks. Its practical scalability and optimal weighting remain open concerns.

  • Problem

    Data Shapley uniformly averages marginal contributions, although large-cardinality contributions can be noisy and the efficiency requirement may be impractical in machine-learning settings.

  • Method

    Beta Shapley relaxes efficiency to form a unified semivalue framework, provides theoretical analysis, and uses an efficient Monte Carlo estimation algorithm.

  • Results

    Beta Shapley outperforms state-of-the-art data valuation methods on noisy-label detection, subsample learning, and point addition or removal tasks.

  • Takeaways & Limitations

    Weighting smaller cardinalities more, such as with Beta(16,1), often improves data valuation and supports identifying low-quality data and subsampling importance.

  • Takeaways & Limitations

    Scalable algorithms for large-scale datasets remain critical for practical use, and optimal data-value weights may depend on several factors.

Abstract

from arXiv · show

Data Shapley has recently been proposed as a principled framework to quantify the contribution of individual datum in machine learning. It can effectively identify helpful or harmful data points for a learning algorithm. In this paper, we propose Beta Shapley, which is a substantial generalization of Data Shapley. Beta Shapley arises naturally by relaxing the efficiency axiom of the Shapley value, which is not critical for machine learning settings. Beta Shapley unifies several popular data valuation methods and includes data Shapley as a special case. Moreover, we prove that Beta Shapley has several desirable statistical properties and propose efficient algorithms to estimate it. We demonstrate that Beta Shapley outperforms state-of-the-art data valuation methods on several downstream ML tasks such as: 1) detecting mislabeled training data; 2) learning with subsamples; and 3) identifying points whose addition or removal have the largest positive or negative impact on the model.

1 Introduction

Data valuation quantifies each training datum’s contribution to model performance, motivated by costly data collection and noisy or mislabeled data. Beta Shapley relaxes efficiency to generalize Data Shapley, reduce noise, and support data valuation across downstream tasks.

  • Data valuation quantifies each training datum’s contribution to a model’s performance, helping address costly collection and noisy or erroneous data.
  • Data Shapley uses average marginal contributions to identify data points that help or harm predictive performance and has shown strong downstream performance.
  • Uniformly weighting marginal contributions across cardinalities is sub-optimal because the efficiency axiom requiring values to sum to total utility may be impractical in ML.
  • Beta Shapley is a unified framework arising from relaxation of efficiency, with reduced noise, subsampling-weight selection, and Monte Carlo estimation.
  • Beta Shapley outperforms state-of-the-art valuation methods on noisy-label detection, subsample learning, and point addition or removal tasks.

2 Preliminaries

The preliminaries formalize utility, marginal contribution, and Data Shapley, then identify a central weakness: uniform weighting can obscure individual data influence at large training-set cardinalities.

  • A utility function maps a dataset to model performance, such as negative mean squared error in regression or accuracy in classification.
  • Marginal contribution measures the average performance change when a datum is removed from subsets of a specified cardinality.
  • Leave-one-out analysis equals a point’s marginal contribution when it is removed from the entire training set, while other valuation methods also use marginal contributions.
  • Data Shapley averages marginal contributions across all cardinalities, avoiding dependence on one cardinality but imposing uniform weights.
  • Data Shapley is uniquely characterized by linearity, null-player, symmetry, and efficiency axioms, including value totals equal to utility.
  • At sufficiently large cardinalities, performance changes approach zero; under mild conditions for negative log-likelihood, the change scales as Op(|S|^-2), weakening influence identification.

3 Theoretical analysis of marginal contribution

Theoretical analysis shows that marginal-contribution signal quality deteriorates with cardinality: variance grows while expected contributions generally shrink. Experiments confirm that large-cardinality contributions become poor indicators of noisy data.

  • Empirical illustrations: In Figure 1, signal-to-noise ratio decreases as j increases in regression and classification settings with n = 500.
  • Theoretical analysis: For fixed cardinality j, marginal-contribution variance scales as O(j^2ζ1/n) as n increases.
  • Theoretical analysis: Under j = o(n^1/2) and bounded limj→∞ζj/(jζ1), Theorem 1 gives (j^2ζ1/n)^-1Var(∆j(z∗; U, D)) → 1.
  • Theoretical analysis: Because expected marginal contributions usually decrease with j while variance increases, the signal-to-noise ratio generally worsens at larger cardinalities.
  • Empirical illustrations: With 10% labels randomly flipped, clean and mislabeled points have overlapping 95% confidence bands when j exceeds 150 across all datasets.
  • Limitations: Theorem 1 assumes bounded limj→∞ζj/(jζ1), whose validity is unknown theoretically but is reported as plausible empirically in the Appendix.

4 Proposed Beta-Shapley method

Beta Shapley generalizes data valuation by relaxing the efficiency axiom and weighting marginal contributions according to cardinality. Its Beta-distribution weights recover existing methods, support efficient estimation, and yield asymptotically minimum-variance subsampling under stated conditions.

  • Data valuations without efficiency axiom: Relaxing efficiency yields semivalues that flexibly weight marginal contributions while retaining linearity, null-player, and symmetry.Every semivalue has a weighted-marginal-contribution representation; efficiency is omitted because scaling values can preserve their ordering in ML applications.
  • Data valuations without efficiency axiom: Semivalue weights are non-unique generally, but identical total data values determine an identical semivalue.Thus, a practitioner’s prior knowledge about the total sum of values can identify the corresponding semivalue.
  • Beta Shapley: Beta Shapley replaces an expensive integral with closed-form weights from a Beta distribution parameterized by positive hyperparameters (α, β).The hyperparameters control how weight is distributed across subset cardinalities.
  • Beta Shapley: Beta(1,1)-Shapley equals data Shapley, while α ≥ β = 1 emphasizes small cardinalities and Beta(1,β) approaches LOO as β increases.Emphasizing small cardinalities is described as removing noise from large cardinalities; increasing β shifts weight toward large cardinalities.
  • Optimal subsampling weights: Importance weights proportional to Beta Shapley values produce asymptotically minimum-variance M-estimators when subsampling, under α ≥ 1 and stated technical conditions.The framework targets subsampling when data are noisy or datasets are computationally costly.
  • Efficient estimation: Monte Carlo estimation addresses the exponential model-fitting cost of exact Beta(α, β)-Shapley computation.The algorithm samples cardinalities and subsets, then updates estimates using weighted marginal contributions.

5 Numerical experiments

The experiments evaluate Beta Shapley across noisy-label detection, subsampling, and point addition or removal on classification datasets. Beta Shapley variants emphasizing small cardinalities generally perform best, while data Shapley is strongest for point removal.

  • Experimental setup: Experiments compare eight valuation methods across 15 classification datasets using logistic regression and three downstream tasks.The tasks are noisy-label detection, learning with subsamples, and point addition or removal.
  • Noisy label detection: Beta(16,1) outperforms other valuation methods for synthetic noisy-label detection, while excessive focus on only the smallest cardinality can degrade performance.LOO-First can suffer training failure with very few samples; Beta(1,4) and LOO-Last perform worse because they emphasize large cardinalities.
  • Noisy label detection: 0.225 F1: Beta(16,1) outperforms other methods on CIFAR100 real-world label errors.For three class pairs with the most mislabels, Beta(16,1) achieves 0.307 F1-score versus 0.273 for the uncertainty-based method.
  • Learning with subsamples: Beta(4,1) achieves the best overall subsampling performance, with Beta(16,1) showing similar performance.Beta(1,4) and LOO-Last perform worse than uniform sampling, indicating that large-cardinality marginal contributions are less useful for importance weighting.
  • Point addition and removal: For point addition, Beta(16,1) produces the most rapid accuracy gain by prioritizing valuable points, whereas data Shapley performs slightly better for point removal.The removal result reflects removing points from the entire dataset, where uniform weighting captures large-cardinality effects better.
  • Overall comparison: Across detection, subsampling, and point addition, Beta(16,1) is consistently the best method; data Shapley is best for point removal.The heatmap summarizes linearly scaled frequencies of best performance across the 15 datasets.

6 Concluding remarks

Beta Shapley unifies and extends data valuation methods, with small-cardinality weighting such as Beta(16,1) performing strongly across experiments. The authors identify scalability and task- or distribution-dependent optimal weighting as future challenges.

  • Beta Shapley unifies and extends LOO, Data Shapley, and other popular data valuation methods.
  • Marginal contributions from small cardinalities have larger signal-to-noise, motivating Beta(16,1) in many settings.
  • Beta(16,1) outperforms Data Shapley, LOO, and other state-of-the-art methods in the reported experiments.
  • Scalable data-valuation algorithms for large-scale datasets remain important for practical use.
  • Optimal data-value weights may depend on the ML task or data distribution.

A Implementation details

The implementation estimates Beta Shapley with a sampling-based Monte Carlo procedure that samples cardinalities and subsets, computes utility differences, and monitors convergence. Experiments use synthetic and real datasets with standard preprocessing and several model classes.

  • The proposed algorithm: The Monte Carlo algorithm samples a cardinality and subset at each iteration to approximate Beta Shapley.
  • The proposed algorithm: Each iteration uses weighted utility differences to update the Monte Carlo estimates, with utility evaluated on held-out validation samples.
  • Accuracy of the proposed algorithms: Convergence is monitored with the Gelman-Rubin statistic, and sampling stops when the increment is sufficiently small relative to the current estimate.
  • Datasets and models: The experiments include synthetic Gaussian datasets and real datasets collected from multiple sources, including OpenML.
  • Datasets and models: Multiclass labels are binarized, minority classes may be oversampled, and image data use penultimate-layer outputs from pretrained ResNet18.
  • Datasets and models: Models include logistic regression, support vector machines, and a k-nearest-neighbor classifier with k = 10 for KNN Shapley.

A.2 Experiment settings

The experiments evaluate valuation methods through noisy-label detection, weighted learning with subsamples, and point addition or removal. Settings specify held-out utility evaluation, data-value-based sample weighting, clustering-based detection, and relative-area performance measures.

  • Experiment setup: The experiments use validation data to estimate utility and held-out test data for evaluation.
  • Noisy label detection: Noisy-label detection orders data points by value, clusters the values into two groups, and selects points below the lower cluster mean as noisy.
  • Noisy label detection: Detection performance is measured with F1-score, using precision and recall based on flipped labels and selected points.
  • Learning with subsamples: Learning with subsamples selects 50 of 200 samples and uses max(ν(z_i), 0) as the importance weight for each sample.
  • Learning with subsamples: The weighted risk minimizer uses inverse propensity weighting, and final performance is evaluated with unweighted test accuracy on held-out data.
  • Point addition and removal: Point addition and removal are evaluated with relative area, with removal ordering determined by data valuation and addition starting from a random set of 10 points.

B.1 A bound condition in Theorem 1

Theorem 1 requires bounded asymptotic growth of ζ_j/(jζ_1), but whether this condition holds is unknown in the literature. Numerical examples suggest that the condition is plausible.

  • Whether lim_j→∞ζ_j/(jζ_1) is bounded remains unknown, although numerical examples make the condition plausible.

B.2 Details on Theorem 4.

Theorem 5 formulates optimal subsampling as minimizing the trace of the asymptotic variance and shows that Beta Shapley-based Horvitz–Thompson estimation attains this minimum. The convergence rate remains unknown, motivating hyperparameter selection through the choices of (α, β).

  • Optimal variance: The optimal subsampling distribution minimizes Tr(νQ) over Q ∈ Π(c1,c2), where νQ is the estimator’s variance.The measure class constrains total measure and density ratios relative to PZ.
  • Optimal variance: The Beta Shapley-based Horvitz–Thompson empirical measure achieves the smallest asymptotic variance.The result applies when the importance weights define a measure Qψ in Π(c1,c2).
  • Theorem conditions: The importance weights λi are specified for Hadamard-differentiable h, with β ≥ 1 and a normalization constraint on their sum.The theorem’s full weight expression is supplied in Theorem 5, together with the required assumptions.
  • Convergence: Theorem 5 establishes asymptotic variance convergence, but its convergence rate is unknown.The authors suggest that different (α, β) choices may affect the rate and therefore hyperparameter selection.

C Proofs

The proofs establish asymptotic variance behavior, characterize semivalues through axioms, and connect Beta Shapley estimation to influence functions and minimum-variance subsampling. They also derive the relevant weight identities through Beta-function arguments and asymptotic approximations.

  • Variance results: For fixed cardinality j, the variance of the marginal contribution scales as O(j2ζ1/n).This result comes from the asymptotic analysis of marginal contributions as U-statistics.
  • Semivalue characterization: A semivalue satisfying linearity, the null-player axiom, and symmetry admits a cardinality-dependent weight representation.The converse characterization uses symmetry to make the weights depend only on subset cardinality.
  • Influence-function limit: The normalized Beta Shapley estimator converges to the influence function I(z∗; h, PZ) as n increases.The proof invokes the Silverman–Toeplitz theorem, while ψj(z∗, h) approaches the influence function as j grows.
  • Weight derivation: The proofs derive the Beta Shapley weights using Beta-function identities and large-n approximations for different β regimes.Separate steps handle β > 1 and 0 < β ≤ 1 before establishing the limiting weight behavior.
  • Minimum-variance estimation: The Beta Shapley-based Horvitz–Thompson estimator has asymptotically minimum variance among the admissible subsampling measures.The proof connects the semivalue-based estimator to the minimum-variance result for Horvitz–Thompson empirical measures.

D.1 Additional results using different datasets

Additional experiments across datasets examine signal-to-noise, marginal contributions, point addition and removal, and robustness to support vector machine models. They consistently show that large cardinalities weaken separation between clean and noisy points, while Beta Shapley remains effective in the reported comparisons.

  • Support vector machine robustness: Support-vector-machine experiments show that the clean–noisy separation is large at small cardinalities but overlaps at large cardinalities.The authors interpret this pattern as suggesting that uniform Data Shapley weights may be suboptimal and Beta Shapley more effective.
  • Additional datasets: At large cardinalities, clean and noisy marginal contributions overlap or become similar, making point quality harder to distinguish.This pattern appears across eleven datasets and is also observed with support vector machines.
  • Additional datasets: Figures 11 and 12 evaluate accuracy changes when points with small value are added or removed across thirteen datasets.The experiments order points by increasing value before measuring accuracy change.
  • Support vector machine robustness: Figure 14 summarizes support-vector-machine performance across fifteen datasets using heatmap frequencies scaled between 0 and 1.Red and blue depict better and worse methods, respectively.
Loading 2110.14049v2…