Research map / Learning theory and algorithms / Prediction and decision losses
Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically that Data Shapley-based data selection can be no better than random guessing for generic utility functions, identifies monotonically transformed modular utilities where it is optimal, and proposes a fitting-residual heuristic to predict its effectiveness.
Problem
Data Shapley's data selection performance is inconsistent across settings in the literature; it is unclear when Shapley values can reliably identify high-utility datasets.
Approach
Frames utility comparison as a hypothesis test and shows Shapley vectors are non-injective images of utility functions, so Shapley-based tests can be no better than random guessing in general; identifies monotonically transformed modular (MTM) utilities where Data Shapley is optimal and uses the normalized fitting residual of an MTM approximation (linked to a rho-consistency index) to predict Data
Key results
- Theory: for any Shapley-based hypothesis test, TrueNeg + TruePos <= 1, i.e., no better than random guessing without structural assumptions on utilities.
- Data Shapley is optimal for size-k selection for any monotonically transformed modular utility (proved theorem), and kernel methods / threshold kNN fall in this class.
- Across 200 noisy variants per dataset, a clear correlation was observed between Data Shapley's normalized selection performance and the normalized MTM fitting residual; MTM fits typically reached MSE < 1e-4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Shapley values to compare dataset utilities without structural assumptions on the utility function | Data Shapley · General utility comparison | TrueNeg + TruePos: ≤ 1 | No clear effect |
| Select data from heterogeneous-quality datasets containing clean and problematic points | Data Shapley data selection · Noisy-label datasets | validation accuracy | Helped |
| Apply Data Shapley to clean datasets with little variation in data quality | Data Shapley data selection · Clean datasets (Flip Ratio=0%) | validation accuracy | Mixed |
| Approximate the utility function more closely with an MTM function | Data Shapley data selection · Noisy dataset variants; size-k selection | normalized utility difference | Helped |
| Use utility functions with high consistency across correlated dataset pairs | MTM utility approximation · Correlated dataset pairs | normalized fitting residual | Helped |
| Use Data Shapley when the utility function has a large MTM fitting residual | Data Shapley data selection · Noisy dataset variants; size-k selection | normalized utility difference | Mixed |
| Compare the heuristic across utility functions from different domains | MTM fitting-residual heuristic · Different-domain datasets | predictive effectiveness | No clear effect |
Surprising findings
- On clean datasets (0% label flips), Data Shapley selection often performs no better than random selection and far below the best random subset.
- Data Shapley's advantage is concentrated on noisy datasets, where it closely matches or surpasses the best random subset at high flip ratios.
Limitations
- Heuristic is less certain when comparing utility functions across datasets from different domains.
- Experiments are limited to small tabular datasets with n=200 training points and logistic regression / MLP learners.
- MTM being a sufficient but not necessary condition, so high fitting residuals do not rule out Data Shapley effectiveness.
Experimental setup
Datasets: Wind CPU Fraud 2DPlanes Vehicle Apsfail Pol
Benchmarks: Wind CPU Fraud 2DPlanes Vehicle Apsfail Pol
Metrics: validation accuracy vs. top-p% data added normalized utility difference normalized fitting residual true positive / true negative of hypothesis test
Baselines: random selection (average) random selection (maximum)
Builds on: Data Shapley semivalues noise stability / harmonic analysis of Boolean functions
Closest papers by meaning
- DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.89)
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.88)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
- Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation (ICLR 2025 · similarity 0.85)
- Compute-Constrained Data Selection (ICLR 2025 · similarity 0.85)
- Data Shapley in One Training Run (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.