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

Yongchan Kwon, James Zou

TL;DR

Beta Shapley is a new data valuation framework that improves upon the popular Data Shapley method by prioritizing small-subset marginal contributions where data quality signals are clearest. By relaxing rigid game-theoretic axioms that aren't necessary for machine learning, it provides a more robust and noise-reduced way to identify mislabeled data and optimize training sets.

What Problem Does This Paper Address?

Machine learning models are notoriously sensitive to the quality of their training data. Mislabeled examples, outliers, and noisy observations can significantly degrade performance. Data valuation aims to solve this by quantifying the contribution of each individual data point to a model's success.

The current state-of-the-art, Data Shapley, is based on cooperative game theory. It calculates a point's value by averaging its "marginal contribution"—how much the model's performance changes when that point is added—across all possible subset sizes of the training data. However, the authors identify a major flaw: in large training sets, the addition of a single point has a negligible impact on the model, meaning the "signal" of that point's value is easily drowned out by noise. Data Shapley's insistence on weighting all subset sizes equally makes it statistically sub-optimal for identifying truly helpful or harmful data.

Methods

The authors propose Beta Shapley, a generalization that moves beyond the strict requirements of classical game theory.

  1. Relaxing the Efficiency Axiom: In economics, the "Efficiency Axiom" requires that the sum of all players' values equals the total utility. The authors argue this is unnecessary for ML; we usually only care about the relative ranking of data points (e.g., "which 10% of my data is mislabeled?").
  2. The Power of Semivalues: By dropping efficiency, they move into the realm of "semivalues," which allows for flexible weighting of different subset sizes.
  3. Beta Distribution Weighting: They use the Beta distribution to define these weights. By choosing specific parameters ($\alpha, \beta$), they can emphasize different subset sizes. For example, setting $\alpha > 1$ and $\beta = 1$ assigns higher weights to smaller subsets.
  4. Statistical Justification: They prove theoretically that the signal-to-noise ratio of a point's marginal contribution is highest when the subset size is small. As the subset grows, the variance increases and the signal vanishes.
  5. Efficient Estimation: Because calculating exact Shapley values is exponentially expensive, they provide a sampling-based Monte Carlo algorithm that uses the closed-form Beta weights to estimate values efficiently.

Datasets

The researchers evaluated Beta Shapley across a wide array of benchmarks:

  • Synthetic Data: Gaussian-based regression and classification sets.
  • Standard ML Benchmarks: 15 datasets including MNIST, Fashion-MNIST, CIFAR-10, Phoneme, Creditcard, and Covertype.
  • Real-World Noise: The CIFAR-100 test set, specifically using a subset of "confusing" classes to detect real-world mislabeling errors identified in prior literature.

Key Insights and Ideas

  • The "Large Subset" Noise Trap: As shown in Figure 1, the signal-to-noise ratio of marginal contributions drops sharply as the subset size ($j$) increases. In a large crowd, one voice is hard to hear.
Figure 1: The signal-to-noise ratio of ∆j(z∗; U, D) as a function of the cardinality j when n = 500 in (left) regression and (right) classification settings. The data are generated from a generalized linear model. The signal-to-noise ratio generally decreases as the cardi- nality j increases, showing that when j is large, the signal of the marginal contribution at large cardinality is more likely to be perturbed by noise.
  • Small Subsets are "Clean": Figure 2 demonstrates that for small subsets, there is a clear gap between the marginal contributions of clean data (yellow) and noisy data (blue). As the subset size grows toward the full dataset size ($n=200$ in the figure), these distributions overlap, making it impossible to distinguish them.
Figure 2: Illustrations of the marginal contribution ∆j(z∗; U, D) as a function of the cardinality j on the four datasets. Each color indicates a clean data point (yellow) and a noisy data point (blue). When the cardinality j is large, the marginal contributions of the two groups become similar, so it is difficult to determine whether a data point is noisy by ∆j(z∗; U, D). We provide additional results on different datasets in Appendix.
  • Game Theory vs. Statistics: The authors highlight a tension between "fairness" (axioms) and "utility" (statistical power). By sacrificing a bit of formal game-theoretic fairness (the efficiency axiom), they gain significant practical power in identifying data quality.

Key Results

Beta Shapley (specifically the $\text{Beta}(16, 1)$ variant) consistently outperformed Data Shapley, Leave-One-Out (LOO), and other baselines:

  • Noisy Label Detection: On 15 datasets, Beta Shapley achieved an average F1-score of 0.458, compared to 0.411 for Data Shapley and 0.178 for LOO.
  • Real-World Errors: In detecting mislabeled images in CIFAR-100, Beta Shapley achieved an F1-score of 0.307, outperforming a specialized state-of-the-art uncertainty-based method (0.273).
  • Optimal Subsampling: When training a model on only the "best" 25% of data as ranked by the valuation methods, Beta Shapley led to higher test accuracy than uniform random sampling or Data Shapley.
  • Point Addition: In "Add Largest First" experiments, adding points with high Beta Shapley values led to the steepest increase in model accuracy, indicating it correctly identifies the most informative samples.

Limitations and Future Work

  • Computational Complexity: While the Monte Carlo algorithm is efficient, it still requires thousands of model retrains. Scaling this to massive datasets (millions of points) or very large models (LLMs) remains a significant hurdle.
  • Hyperparameter Tuning: The authors found $\text{Beta}(16, 1)$ to be a strong default, but the "optimal" $\alpha$ and $\beta$ might vary depending on the specific dataset or the expected level of noise.
  • Task Dependency: The value of a data point is intrinsically tied to the specific model and utility function used. A point might be "valuable" for a logistic regression but "noisy" for a deep neural network. Exploring this cross-model stability is a suggested future direction.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kwon2022beta,
  author = {Yongchan Kwon and James Zou},
  title = {{Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
}
Figure