Data valuation

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 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 2202.05594 §1, §5. Card: The Shapley Value in Machine Learning.

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 2202.05594 §2.1, eq. 1, §4.2. Its cost grows factorially with the number of players 2202.05594 §5.1.1. Card: The Shapley Value in Machine Learning.

Permutation sampling

Draw random orderings of the points and average each point's marginal contribution over the draws 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 2202.05594 §3.1. Card: The Shapley Value in Machine Learning.

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.

Regression over coalitions (KernelSHAP-style)

The values are the solution of a weighted least-squares problem over coalitions 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 2202.05594 §3.3. Card: The Shapley Value in Machine Learning.

Multilinear extension

Rewrite the Shapley sum as an integral over an inclusion probability and approximate the integral by sampling 2202.05594 §3.2. Card: The Shapley Value in Machine Learning.

When to use which

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

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

Implementation sketch

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

# 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 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 2202.05594 §2.1. The data-valuation payoff is defined as the fit of a model trained on a subset 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" 2202.05594 §4.1–§4.3, but some of its cited rows use validation loss 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 2202.05594 §3.1.
• "Linear time" needs a qualifier. Permutation sampling is described as linear-time per sample 2202.05594 §3.1. The regression approach needs subsampling to be tractable 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 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 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: survey of the Shapley value, with the data-valuation game, sampling and regression approximations, and open problems.