---
kind: concept
slug: data-valuation
title: Data valuation
summary: >-
  Scoring each training data point by how much it contributes to a model's performance, most often with the Shapley value. Covers the cooperative-game setup, exact and sampling-based computation, and the cost and axiom trade-offs. Based on one survey with no experiments, so the numbers are cited claims, not measurements.
tags: [data, shapley-value, data-quality, cooperative-game-theory]
papers: ["2202.05594"]
related: [shapley-value, credit-assignment, feature-attribution, influence-functions, dataset-curation, noisy-labels, data-poisoning, federated-learning, explainable-ai]
status: draft
updated_at: 2026-11-01
---

## Overview

Data valuation asks how much each training point is worth to the model trained
on it. One common answer treats the training points as players in a
cooperative game. The payoff of a set of points is the fit, on a test set, of
a model trained on that set. A point's value is its average marginal
contribution over subsets, which is the Shapley value [arxiv:2202.05594 §4.2].

The only source on this page is a survey of the Shapley value in machine
learning. It reports no experiments of its own, so the claims below are the
survey's descriptions and the results it cites [arxiv:2202.05594 §1, §5].
Card: [The Shapley Value in Machine Learning](/papers/2202.05594).

## Variants

The survey describes the value and its approximations. Each entry below is a
way to compute the same quantity, with its trade-off as stated in the survey.

### Exact Shapley value over training points

Players are training points; v(S) is the fit of a model trained on S. The exact
value averages the marginal contribution over every ordering of the points
[arxiv:2202.05594 §2.1, eq. 1, §4.2]. Its cost grows factorially with the
number of players [arxiv:2202.05594 §5.1.1]. Card: [The Shapley Value in Machine Learning](/papers/2202.05594).

### Permutation sampling

Draw random orderings of the points and average each point's marginal
contribution over the draws [arxiv:2202.05594 §3.1, alg. 1]. The survey gives
finite-sample bounds, but they need the variance or range of the marginal
contributions. Those are rarely known in advance, and the survey gives no rule
for choosing the number of orderings [arxiv:2202.05594 §3.1]. Card: [The Shapley Value in Machine Learning](/papers/2202.05594).

### Stratified sampling and other variance reduction

Stratified sampling groups orderings by similar marginal contributions, and
antithetic sampling pairs an ordering with its reverse [arxiv:2202.05594
§3.1.1, §3.1.2]. The survey describes these as ways to reduce variance. It
does not compare them numerically with plain permutation sampling. Card:
[The Shapley Value in Machine Learning](/papers/2202.05594).

### Regression over coalitions (KernelSHAP-style)

The values are the solution of a weighted least-squares problem over
coalitions [arxiv:2202.05594 §3.3]. This needs v on all 2^|N| coalitions, so
the coalitions are subsampled. The survey reports that the estimator is
consistent but biased, and that using complementary pairs of coalitions cuts
its variance [arxiv:2202.05594 §3.3]. Card: [The Shapley Value in Machine Learning](/papers/2202.05594).

### Multilinear extension

Rewrite the Shapley sum as an integral over an inclusion probability and
approximate the integral by sampling [arxiv:2202.05594 §3.2]. Card: [The Shapley Value in Machine Learning](/papers/2202.05594).

## When to use which

The survey gives no benchmark that ranks these variants for data valuation.
The table lists the constraints it does address.

| Situation | Use | Why |
|---|---|---|
| Few training points, and the exact value is needed | Exact Shapley value | Exact but factorial in the number of points [arxiv:2202.05594 §5.1.1] |
| Many points, and the estimate needs finite-sample error bounds | Permutation sampling | Bounds depend on the variance or range of marginal contributions, which are rarely known [arxiv:2202.05594 §3.1] |
| Many points, and a faster estimate is acceptable | Regression over coalitions | Consistent but biased; needs subsampled coalitions [arxiv:2202.05594 §3.3] |
| Values must keep the fairness axioms exactly | Check before approximating | The axioms often fail under the approximations used in practice [arxiv:2202.05594 §5.1.3] |
| Values must be read as an action, such as removing or keeping a point | Be careful | The value is an average over orderings and is hard to interpret directly [arxiv:2202.05594 §5.1.2] |

The survey argues that Shapley values satisfy fairness requirements that
earlier valuation methods, such as influence functions, leave-one-out and core
sets, lack [arxiv:2202.05594 §4.2]. That is the survey's argument and is not
tested there. See [influence-functions](/concepts/influence-functions) for
the related concept page.

## Implementation sketch

A permutation-sampling estimator for data valuation. It follows the survey's
algorithm [arxiv:2202.05594 §3.1, alg. 1], with the training-point payoff from
[arxiv:2202.05594 §4.2]. The survey does not fix v(∅), so the caller must
choose it.

```pseudocode
# Permutation-sampling estimate of data values  [arxiv:2202.05594 §3.1, alg. 1]
# Input:  points (N), fit(subset) -> score, number of orderings k
# Output: value[point] for every point in N

def data_values(points, fit, k):
    # Running sums start at zero  [alg. 1]
    value = {p: 0.0 for p in points}
    # Each draw is one random ordering of the training points  [alg. 1]
    for _ in range(k):
        order = random_permutation(points)
        seen = frozenset()
        score_before = fit(seen)  # v(∅): not stated by the survey; choose one
        for p in order:
            # Marginal contribution of p given the points before it  [eq. 1]
            score_after = fit(seen | {p})
            value[p] += (score_after - score_before) / k
            seen = seen | {p}
            score_before = score_after
    return value
```

The sketch computes each subset's score once per ordering, so an ordering
of n points needs n + 1 calls to `fit`. This is our own bookkeeping, not a
figure from the survey.

Check against the survey's three-player game, which is not a data-valuation
game. Its payoffs are v({1}) = 7, v({2}) = 11, v({3}) = 14, v({1,2}) = 18,
v({1,3}) = 21, v({2,3}) = 23, v({1,2,3}) = 25, and the Shapley values are 32/6,
50/6 and 68/6 for players 1, 2 and 3 [arxiv:2202.05594 §2.1, tab. 1]. The
three values sum to v({1,2,3}) = 25, which the exact computation must match.

## Pitfalls

- **v(∅) is not given for data valuation.** A transferable-utility game needs
  v(∅) = 0 [arxiv:2202.05594 §2.1]. The data-valuation payoff is defined as the
  fit of a model trained on a subset [arxiv:2202.05594 §4.2], and the survey
  does not say what it is for the empty set.
- **Sign of the payoff.** The survey calls the payoffs "goodness of fit"
  [arxiv:2202.05594 §4.1–§4.3], but some of its cited rows use validation loss
  [arxiv:2202.05594 tab. 2]. A loss is a cost and has to be negated before the
  values read as contributions. The survey does not say which convention to
  use.
- **Sample count.** The number of orderings is not chosen by the survey, and
  its error bounds need variance or range values that are rarely known
  [arxiv:2202.05594 §3.1].
- **"Linear time" needs a qualifier.** Permutation sampling is described as
  linear-time per sample [arxiv:2202.05594 §3.1]. The regression approach needs
  subsampling to be tractable [arxiv:2202.05594 §3.3]. The total number of
  payoff evaluations is not stated.
- **Cost column in the survey's table is unclear.** The table gives terms such
  as O(|N|) without saying whether they count payoff evaluations, model
  trainings or work per sample [arxiv:2202.05594 tab. 2].
- **Axioms and approximation.** The survey says the axioms often fail under
  approximation and cites one work for this, without a proof or counterexample
  of its own [arxiv:2202.05594 §5.1.3].

## Contradictions

None known. Only one card is cited on this page, and the survey does not
dispute any other source on this topic.

## Papers

- [The Shapley Value in Machine Learning](/papers/2202.05594): survey of the Shapley value, with the data-valuation game, sampling and regression approximations, and open problems.