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.
- 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?").
- The Power of Semivalues: By dropping efficiency, they move into the realm of "semivalues," which allows for flexible weighting of different subset sizes.
- 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.
- 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.
- 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.
- 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.
- 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