DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation

This paper studies the problem of dataset valuation, a variant of data valuation, where the contributions of multiple datasets, instead of single data points, to a metric such as performance of a machine learning prediction model are quantified. The authors analyze the computation of the Shapley value, where each player represents a single dataset. In this context, it is argued that the utility function (or game) is essentially determined by the size of each dataset, which is theoretically supported by three general synthetic use-cases involving piece-wise constant functions, homogeneous data distributions, and linear regression with noisy labels, related to local differential privacy. The author present "Discrete Uniform" Shapley values (DU-Shapley), which approximates the Shapley value under this assumption efficiently. If the assumption on the utility function is satisfied, then the method can be further simplified by constructing suitable intervals instead of sampling, where the authors show for all use-cases asymptotic convergence (for infinite number of datasets) and non-asymptotic theoretical guarantees for the first and second use-case. The authors then evaluate their approach empirically, on multiple benchmark datasets against permutation-based Monte Carlo approaches, and on OpenDataVal benchmark tasks.

The paper proposes a novel proxy for the Shapley value (SV) which is called discrete uniform (DU) Shapley. Unlike the SV, this proxy does not suffer from the exponential complexity problem of the SV. Of course the DU Shapley, therein does not capture all information entailed in the SVs for a cooperative game. The DU Shapley are motivated and derived from the setting of dataset valuation. Dataset valuation is a similar setting to data valuation, with the difference being that not individual data points are making up the player set but collection of data points. The work studies this dataset valuation setting and the DU Shapley theoretically and performs empirical experiments illustrating the effectiveness.

The paper studies dataset evaluation with Shapley value. They assume that each dataset contains i.i.d. data points from a distribution and exploit the knowledge about the structure of the underlying data distribution to design more efficient Shapley value estimators. Based on asymptotic analysis of Shapley values of datasets, they propose an approximation of Shapley values of datasets. They prove estimation error bounds for non-asymptotic settings. The estimation accuracy is tested via numerical experiments in certain settings in comparison to other approaches. They also test the effectiveness of the approach for noisy label detection, dataset removal, and dataset addition.

This paper proposes a general dataset valuation method which only requires N number of utility function evaluations, where N is the number of players. The approach is motivated by a homogeneous setting for linear regression, but experiments also show the effectiveness of such an approach in general settings.

We thank the anonymous reviewers for the useful reviews. As the question concerning the complexity of computing the Shapley value of all players arose several times, we address it as a general reply. We provide several answers.

a) Approximation schemes such as Monte Carlo (DataShapley), DU-Shapley, SVARM [2], or the improved version of Jia et al.'s algorithm [1], are all based on a simple principle: a trade-off between accuracy and complexity of the approximations. In particular, even though DataShapley and the work in [1] require $O(I\log(I))$ function valuations to compute all Shapley values while our method uses $O(I^2)$, the comparison between them must be carefully done as nothing guarantees that the different methods achieve the same accuracy level. We illustrate the advantages of our method through two experiments.

1. Complexity comparison of DU-Shapley, DataShapley (Monte Carlo), and the improved Jia et al.'s algorithm. We have looked at the number of iterations that DataShapley (Monte Carlo, also named the baseline in [3]) and the method in [1] require to achieve DU-Shapley's accumulated bias (in norm-2), formally given by,

$

\mathrm{DU bias}(I) := \frac{\kappa}{I-1}\sqrt{\sum_{i\in \mathcal{I}} \frac{(9\sigma_{-i}^2(1+\log(I-1)) + \zeta_{-i})^2}{(\mu_{-i})^4}},

$

by replacing $\varepsilon = \mathrm{DU bias}(I)$, respectively, in the formula in Section 4.1 in [3] and Equation 5 in [1], for $\delta \in \{0.01,0.05,0.1\}$. Since DU-Shapley's bias depends on the value function choice (due to the constant $\kappa$), we have considered a utility function motivated from our third use-case under the homogeneity assumption $\sigma_i/\varepsilon_i = \sigma_j/\varepsilon_j$ for all $i,j \in \mathcal{I}$, given by,

$

\forall S \subseteq \mathcal{I}, u(S) = w(n_S) = 1 - \frac{10^{k(\mathcal{I})}}{10^{k(\mathcal{I})} + n_S},

$

where $n_S$ is the size of the data set $D_S := \cup_{i\in S} D_i$ and $k(\mathcal{I}) := \lfloor \log(\sum_{i\in\mathcal{I}}n_{i}) \rfloor - 1$ is a normalization factor depending on the total number of data points. Finally, we have shifted the utility function so it takes only positive values and $u(\varnothing) = 0$. Since DUbias depends on the number of data points per player, for each considered value of $I$, we have simulated 20 different sets of players, each time by sampling $n_i \sim \mathrm{U}(\{1,...,n_{max}\})$ for each $i \in \mathcal{I}$ and $n_{max} \in \{10,50,100\}$. The results are illustrated in Figure 1 in the attached PDF. The rows correspond to each value of $\delta$ while the columns to each value of $n_{max}$. We observe that in all tested instances, both methods require more than $I^2$ iterations to achieve the same error than DU-Shapley.

2. Complexity comparison DU-Shapley and SVARM. We have looked at the probability at which SVARM (Theorem 4 [2]) can ensure, after $I^2$ iterations (without considering the warm up as part of the budget), an error equal to DU-Shapley's accumulated bias. We have considered the same value function than in the previous experiment with $n_{max} \in (2\cdot 10^3,3\cdot 10^3,5\cdot 10^3,10^4)$ and 100 simulations of sets of players at each time. Figure 2 in the attached PDF shows the results.

b) Approximating DU-Shapley. It should be noted that the approximation of the Shapley value given by DU-Shapley can be leveraged further by approximating DU-Shapley itself with a coarser discrete scheme than the one specified in our method. For example, we can reduce the computing burden from $I$ to $\sqrt{I}$ in Definition 3 by computing $\sqrt{I}$ marginal contributions only with data sets $\mathrm{D}^{(k)}$, respectively, of size $k\cdot \frac{1}{\sqrt{I-1}}\sum_{j\in \mathcal{I}\setminus\{i\}}|\mathrm{D}_j|.$

c) Practical use-cases for dataset valuation. We also point out that there are use cases where one is interested in the contribution of one specific dataset (for example, the contribution of Wikipedia to an LLM). In this case, the relevant complexity notion is the computing cost for one player, as opposed to the computing cost for all players.

[1] Wang, Jiachen T., and Ruoxi Jia. "A Note on" Towards Efficient Data Valuation Based on the Shapley Value''." arXiv preprint arXiv:2302.11431 (2023).

[2] Kolpaczki, P., Bengs, V., Muschalik, M., & Hüllermeier, E. (2024). Approximating the Shapley Value without Marginal Contributions. Proceedings of the AAAI Conference on Artificial Intelligence, 38(12), 13246-13255.

[3] Jia, Ruoxi, et al. "Towards efficient data valuation based on the shapley value." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.

The review for the paper were unanimously positive, and the paper should be accepted as at NeurIPS