🤖 machine learning

Is Data Shapley Not Better than Random in Data Selection? Ask NASH

This paper introduces NASH, a novel data selection framework that decomposes target utility functions into Shapley-informative components and aggregates them non-linearly to consistently and efficiently select high-quality training subsets, thereby overcoming the limitations of standard Data Shapley methods that often perform no better than random selection.

Original authors: Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Zixuan Wang, Nancy F. Chen, Bryan Kian Hsiang Low

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xiao Tian, Jue Fan, Rachael Hwee Ling Sim, Zixuan Wang, Nancy F. Chen, Bryan Kian Hsiang Low

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to create the perfect soup. You have a massive pantry full of ingredients (your training data), but you only have enough space in your pot for a small, specific amount (your limited budget or storage). Your goal is to pick the best handful of ingredients to make the soup taste amazing.

For a long time, data scientists have used a method called Data Shapley to decide which ingredients to pick. Think of Data Shapley like a "fairness score." It tries to calculate how much every single ingredient contributes to the final taste, considering how it mixes with every other possible combination of ingredients. The theory is: "If an ingredient is good, it will have a high score, so let's just grab the top 10 highest-scoring ones."

The Problem: The "Top 10" Trap
The paper argues that this "Top 10" approach often fails. Sometimes, the ingredients with the highest scores don't actually make the best soup; in fact, they might be no better than just grabbing a handful of ingredients at random.

Why? Because the "score" (Data Shapley) is trying to do too much at once.

The "Swiss Army Knife" Flaw: Imagine you have a knife that is great at cutting meat but terrible at chopping vegetables. If you only look at the knife's overall score, it might look like a top-tier tool. But if your soup needs a lot of vegetables, that knife is useless.
The Paper's Insight: The "taste" of the soup (validation accuracy) depends on many different "roles" (cutting meat, chopping veggies, seasoning). A single overall score hides these specific strengths. The paper shows that Data Shapley often picks a bunch of "meat cutters" and ignores the "vegetable choppers," resulting in a bad soup.

The Solution: Meet NASH
The authors propose a new framework called NASH (Non-linear Aggregation of SHapley-informative components). Here is how it works, using a creative analogy:

Break it Down (Decomposition): Instead of asking, "How good is this ingredient for the whole soup?" NASH asks, "How good is this ingredient for just the meat? How good is it for just the veggies? How good is it for just the seasoning?"
- The paper proves that when you look at these tiny, specific roles (like predicting the taste of one specific vegetable), the Data Shapley score becomes very accurate and reliable. These are the "Shapley-informative components."
Mix it Smartly (Non-Linear Aggregation): Now, NASH has a score for every ingredient for every role. But it doesn't just add them all up (which would just give you the old, flawed "Top 10" list).
- Instead, it uses a smart mixing strategy. Think of it like a chef who realizes: "I have plenty of meat cutters, but I'm desperate for vegetable choppers."
- NASH prioritizes ingredients that fill the gaps. If the soup already has great meat coverage, NASH stops picking more meat cutters and starts hunting for vegetable choppers, even if those choppers had a slightly lower "overall" score. It uses a mathematical "curved" rule (non-linear) to ensure the soup gets a balanced, complete flavor profile.

The Results
The paper tested this on many different "recipes" (datasets) and "cooking styles" (models), from simple math problems to complex AI language models.

Old Way: The standard Data Shapley method often performed no better than picking ingredients randomly.
NASH Way: By breaking the problem into specific roles and re-mixing them smartly, NASH consistently picked better ingredients, creating a much tastier soup (higher model accuracy) than the old method, with almost no extra time or cost.

In a Nutshell
The paper says: "Don't just trust the overall popularity score of your data. Break the problem down into specific tasks, see where your current data is weak, and use a smart, non-linear rule to fill those gaps. That's how you get the best data selection."

Key Takeaways from the Paper:

Data Shapley isn't broken; it's just being used the wrong way (by blindly picking the top scores).
Complex goals (like "good soup") are made of simple parts (good meat, good veggies). Data Shapley works great on the simple parts.
NASH is the new framework that uses the simple parts to build a better whole, ensuring you don't just pick a bunch of similar ingredients but a balanced, high-quality subset.

Technical Summary: NASH - Non-linear Aggregation of SHapley-informative components

Problem Statement

Data selection aims to identify high-quality subsets of training data to optimize model utility (e.g., validation accuracy $u_V$ ) under size constraints. While Data Shapley and its generalizations (semivalues) are theoretically grounded in cooperative game theory to account for data interactions, recent empirical studies indicate they often perform ineffectively in practice. Specifically, selecting the top- $m$ data points based on Shapley values computed with respect to complex utility functions (like validation accuracy) can yield subsets no better than, or even worse than, random selection.

The paper identifies two primary reasons for this failure:

Lack of Shapley-informativeness: Complex utility functions involve multiple distinct "roles" (e.g., different classes or subpopulations in the validation set). A single Shapley value for a datum fails to capture its unique strength across these roles. Consequently, data with different strengths may receive identical Shapley scores, leading to interchangeable treatment despite their differing utility contributions.
Inappropriate Aggregation: The true objective (e.g., validation accuracy) aggregates performance across these roles non-linearly. However, the standard top- $m$ heuristic relies on a linear aggregation (summing Shapley values), which fails to capture the synergistic interactions where a datum's contribution depends on which other data are already selected (e.g., a datum is more valuable if it covers an underrepresented role).

Methodology: NASH Framework

The authors propose NASH (Non-linear Aggregation of SHapley-informative components), a framework that decomposes the complex utility function into simpler components where Shapley values are effective, and then aggregates them non-linearly.

1. Shapley-Informativeness and Decomposition

The paper formalizes Shapley-informativeness as a property where the sum of Shapley values for a subset is indicative of its actual utility. The authors prove that arbitrary utility functions are generally not Shapley-informative. However, they demonstrate that simpler utility functions, specifically prediction correctness on a single validation datum ( $u_v$ ), are provably Shapley-informative under the "Consistent Player" assumption (where a datum is consistently good or bad for a specific validation point).

Instead of computing Shapley values for the aggregate validation accuracy $u_V$ , NASH decomposes $u_V$ into individual components $u_v$ for each validation datum $v \in V$ . The Shapley values $\phi_i(u_v)$ are computed for these simpler components. Notably, computing these vectors incurs no additional runtime cost compared to computing the Shapley value for the aggregate $u_V$ , as $u_V$ is simply the average of $u_v$ .

2. Non-linear Aggregation

To reconstruct the complex objective from these informative components, NASH avoids linear summation (which recovers the flawed top- $m$ Shapley heuristic). Instead, it optimizes a non-linear aggregation objective:
$\max_{M \subseteq N, |M|=m} \sum_{v \in V} F_T(\hat{u}_v(M))$
where $\hat{u}_v(M) = \sum_{i \in M} \phi_i(u_v)$ is the sum of Shapley values for component $v$ , and $F_T$ is a cumulative distribution function (CDF) inspired by learning curves (e.g., an exponential law). This non-linear function ensures that the selection process prioritizes data that help "cross the threshold" for poorly predicted validation points (uncovered roles) rather than accumulating high scores on already well-predicted points.

3. Optimization

The NASH objective is optimized using a greedy algorithm. The authors show that when Shapley values are non-negative, the objective is monotone submodular, guaranteeing a $(1 - 1/e)$ approximation. Even with negative values (from noisy data), the greedy algorithm empirically performs well because the harmful data (which cause non-submodularity) are naturally deprioritized. The algorithm introduces minimal additional runtime cost, as the heavy lifting (Shapley approximation) is shared with existing methods.

Key Contributions

Theoretical Analysis: The paper formalizes the Shapley-informativeness property, explaining why complex ML utility functions (like validation accuracy) fail to satisfy it, leading to the inconsistent performance of Data Shapley.
Provably Informative Components: The authors identify and prove that prediction correctness on single validation data points serves as Shapley-informative components under reasonable assumptions.
NASH Framework: A novel data selection framework that decomposes complex objectives into Shapley-informative components and aggregates them non-linearly to select high-quality subsets.
Empirical Validation: Extensive experiments across standard datasets (logistic regression, KNN) and large-scale language model fine-tuning (BERT, Llama-2) demonstrate that NASH consistently outperforms vanilla Data Shapley, other semivalues, and random selection.

Results

General Data Selection: In settings without injected noise (homogeneous quality), vanilla Data Shapley often performs no better than random. NASH substantially boosts performance in these scenarios, consistently outperforming baselines across various selection ratios.
Heterogeneous-Quality Datasets: In settings with label noise, vanilla Data Shapley improves (as it can distinguish bad data), but NASH still consistently outperforms it. This suggests NASH's benefits (handling role interactions) are distinct from and complementary to Data Shapley's ability to filter noise.
Compatibility: NASH is compatible with various semivalues (e.g., Beta Shapley, Data Banzhaf) and efficient approximation methods (e.g., MC sampling, FreeShap), consistently improving their selection performance.
Robustness: The method is robust to the choice of the hyperparameter $\lambda$ in the aggregation function and works effectively with different utility functions (e.g., validation loss, MSE).

Significance

The paper claims that NASH largely eliminates the restriction that Data Shapley/semivalues are only effective on limited datasets or specific settings (e.g., those with injected noise). By providing a framework that makes Shapley-based selection consistently reliable and robust across diverse datasets and model scales, NASH enables the broader adoption of principled data valuation methods. This advancement supports future research in improving approximation efficiency and data selection for foundation models, ensuring that the theoretical benefits of Shapley values (non-myopic interaction and equity) are realized in practice.