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

Summary

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.

Strengths

- Dataset valuation is an important variant of data valuation and analyzing the structural properties of the involved utility function is an important research question. - The paper is well-structured and the mathematical notation is precise and understandable - The paper presents interesting theoretical results for synthetic use-cases, which have direct consequences for the computatability - The empirical performance on OpenDataVal tasks is promising

Weaknesses

- The baselines in the experimental evaluation of the Shapley value approximation are limited. The authors only consider permutation sampling (with antithetic sampling as a variant) as the main competitor. However, there exist a variety of other methods, cf. evaluations in [1], that have been applied in data valuation and outperform this approach - There is no evaluation, if the assumptions / structures of DU-Shapley specific to dataset valuation are apparent in real-world applications. Especially, it remains unclear if the synthetic use-cases are related to real-world applications. - Section 3.2 is hard to follow, especially the derivation of (10) from Definition 3. In particular, it remains unclear to me, how Definition 3 and (10) are the same estimator, and what is the intuition behind Definition 3, which is used in real-world applications. **Minor Comments** - In Table 1, it is unclear which values are bold (top-2 or best)? It seems inconsistent. - Related work could be improved, there are several algorithms for Shapley values, cf. the methods in [1,2,3]. - Instead of saying "exponentially reduce the complexity", e.g. line 62, it would be better to state the complexity [1] Li, W., & Yu, Y. (2023, October). Faster Approximation of Probabilistic and Distributional Values via Least Squares. In The Twelfth International Conference on Learning Representations. [2] Chen, H., Covert, I. C., Lundberg, S. M., & Lee, S. I. (2023). Algorithms to estimate Shapley value feature attributions. Nature Machine Intelligence, 5(6), 590-601. [3] Kolpaczki, P., Bengs, V., Muschalik, M., & Hüllermeier, E. (2024, March). Approximating the shapley value without marginal contributions. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 12, pp. 13246-13255).

Questions

- Could you explain a bit more the intuition behind the DU-Shapley approach and Definition 3? In particular, the definition of $D^{(k)}$ is unclear to me, "is a set of data points uniformly sampled without replacement", it seems to me that it is the union of $k$ datasets rather than $k$ data points? If not, then $u$ is not defined for this setting? Maybe a pseudo-code algorithm would help. - Could you elaborate on section 3.2? I did not understand the derivation of (10) from Definition 3 using the assumption. In particular, how does (10) not depend on the sampled data points anymore from Definition 3? These seem to be two different estimators. - It seems that DU-Shapley has to be computed for every individual dataset separately? Could you comment on this limitation, and is there a way to circumvent it? I think this should be included in the limitations sections. Furthermore, the method then has quadratic complexity?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

The author discuss limitations of their work, which centers around the applicability of the approach when dataset sizes and variances are strongly heterogeneous.

Summary

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.

Strengths

- **Theoretical Results:** The work studies the setting of dataset valuation in a theoretical and well-substantiated manner. While I think details of 2.1.1, 2.1.2, and 2.1.3 may be deferred to the appendix to expand on 2.2 and 2.3, the theoretical analysis of the dataset valuation problem is a good contribution. Further, the theoretical results regarding DU Shapley and the mechanisms behind it (for Example Figure 1 and Figure 2) support the work well. - **Empirical Evaluation For Data Valuation:** While DU Shapley is not proposed for the data valuation task but rather dataset valuation, the work also contains evaluations with OpenDataVal highlighting that DU Shapley can also be applied to this setting. This is particularly interesting since these values are quite cheap to compute offering a good baseline for future work or an initial insight before applying more costly approaches. - **Empirical Evaluation in real-world scenarios:** The paper shows how DU Shapley seems to be a viable approach to use as a proxy stand-in compared to other sampling-based baseline methods in traditional machine learning settings. This shows that even when the assumptions made on the value function are not fulfilled the estimates are still better than estimates from alternative methods. I still think better comparisons could have been made (c.f. Weakness Section). - **Reproducible:** Working on a related problem with the same problem formulation, I observe the same results this paper hypothesizes and describes in its formulation. With increasing dataset size the worth of a dataset increases (though not monotonically but still increases). The proxy approach of DU Shapley seems to work very well in this setting. I suspect this also to hold for different data modalities like text or images, which could be a fruitful future research direction.

Weaknesses

## Major Weaknesses - **Weak Baselines** The empirical evaluation (comparison against sampling) compares the effectiveness of DU Shapley in with subpar and not interesting baselines. The evaluation does not include the KernelSHAP [1] method for computing SVs. KernelSHAP in many areas outperforms the sampling based estimators by a large margin. Further, as the work hypothesizes and arguments strongly that the size of a dataset (and thus also the coalition size) is important to determine the worth of it, methods like SVARM [2] that are derived for this setting are also missing from the empirical comparison. Both of these methods are not compared, which might strongly alleviate the performance increase of DU Shapley compared to the current baselines. - **Weak Sampling Budget** It seems like the empirical evaluation comparing DU Shapley with the sampling-based black-box estimators (Section 4.1) uses a very low computational budget for the estimators. While it is true that when DU Shapley requires a very low budget, a fair comparison would want to compare the current state of the art in the same settings. However, DU Shapley is a proxy for the SV. There it is definitely interesting to also see when the state-of-the-art catches up with the proxy. While it is very obvious that the proxy DU Shapley value is much better in these very low dataset valuation settings. However, the other methods estimate the SV and might get better in a reasonable time (in terms of computational budget). This should be evaluated well with proper error/evaluation curves for different estimation budgets. ## Smaller Weaknesses - **Too little Focus on Data Valuation vs. Dataset Valuation:** I think this work may benefit from a better high-level motivation, and looses itself in too much details (2.1.1, 2.1.2, and 2.1.3 make up 1.5 pages). These motivating examples could be shorter and placed in the appendix to make more room for a broader theoretical background delineating this works contribution from the classical data valuation setting better than the rather short intermission with Section 2.3. I would also think that actually plotting/visualizing these Dataset Valuation attribution values for a ground truth setting would help. It is not tangible how these values actually look for real-world scenarios from Section 4.2. ## References - [1] https://proceedings.neurips.cc/paper/2017/file/8a20a8621978632d76c43dfd28b67767-Paper.pdf (KernelSHAP in my opinion is better explained here: https://proceedings.mlr.press/v130/covert21a.html) - [2] https://ojs.aaai.org/index.php/AAAI/article/view/29225

Questions

1. How does DU Shapley compare against stronger approximations like Kernel-based estimators (aka. KernelSHAP) or stratified methods like SVARM? 2. I am a bit confused by your statement in line 305. Did you run the MC estimations on 10 or 20 subset evaluations as the computational budget? The axis description in Figure 3 also does not help. ## Suggestions I have run a similar setup for the cal. housing experiment as you do in Section 4.1. I compute the ground-truth SVs for a 10 player dataset valuation setting. The SVs are as follows (empty-set is manually set to 0): - $D_1$: 0.05790964954064733 - $D_2$: 0.06817158889611828 - $D_3$: 0.07737767986447398 - $D_4$: 0.08361640115201878 - $D_5$: 0.08403403608007484 - $D_6$: 0.08978074706995469 - $D_7$: 0.08771940889382171 - $D_8$: 0.08772011962276798 - $D_9$: 0.09842460151765661 - $D_{10}$: 0.11083578157985912 The dataset sizes are monotonically increasing from $1$ to $10$, which is inline with the papers claims in regards to the behavior of the SVs. The SVs also increasing (though not so monotonically but still increase) mainly depending on the size of the datasets. Note that for this a gradient boosted tree (as implemented in xgboost) is fitted without any HPO. I suggest to add something similar to this in an illustrative/abstract way to show how the value function behaves and make this clear to a potentially unfamiliar reader too motivate this solution better.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The work contains a separate limitations section.

Summary

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.

Strengths

The paper explores a novel setting in which Shapley values are computed for datasets comprising i.i.d. data points. Leveraging the distributional structures of datasets, they propose an approximation method that reduces running time. Their theoretical analysis is novel and strong, offering valuable insights into the distribution of Shapley values for datasets under some assumptions. They show by experimental results that this approximation method outperforms other MC-based approaches with computational power is limited.

Weaknesses

In the context of dataset evaluation, previous data point Shapley approximation methods can still be applied by treating the dataset as a single entity. The main advantage of this new approach appears to be its improved computational efficiency compared to earlier Data Shapley methods. However, the computational efficiency improvement is not thoroughly discussed or demonstrated through experiments, which primarily focus on estimation accuracy. The theoretical analysis relies on certain distributional assumptions, potentially limiting the approach's applicability. For instance, the accuracy of the estimation seems dependent on having a large number of data providers. In contrast, previous Data Shapley approximation methods, such as those proposed by Jia et al. (2019), do not appear to require these assumptions. Furthermore, the difference in the number of retraining iterations, O(n log n) versus O(n), is not substantial. The use cases for dataset valuation are not well articulated. Common tasks like noisy label detection, data removal, and data addition are typically considered at the data point level. It is unclear why the data needs to be removed as a set rather than individually.

Questions

1. What’s the reason for choosing 20 SGD steps and 20 boosting iterations? Will the experiment results significantly change when the numbers increase? 2. Could you explain the improvement in computational efficiency compared to Jia et al. 2019?

Rating

6

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

Summary

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.

Strengths

The paper is easy to read and has a very clear structure. The topic is very important as existing data valuation approaches mostly focus on data point-level valuation, while this paper focus on dataset-level valuation.

Weaknesses

I have reviewed this paper at ICML. The paper has addressed most of the issues in this revision and has a huge improvement. My remaining concerns are the following: **Computational complexity.** While DU-Shapley only requires $I$ utility function evaluations for a single data owner, if we want to evaluate all data owners it still requires $I^2$ function evaluations. This is worse than the group-testing estimator introduced in [1] (a refined version can be found in [2]), and I believe [3] has already reduced the complexity to $O(I \log I)$. I did not verify the correctness of the results in Section 3.3, but the expressions seem to be reasonable. [1] Jia, Ruoxi, et al. "Towards efficient data valuation based on the shapley value." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019. [2] Wang, Jiachen T., and Ruoxi Jia. "A Note on" Towards Efficient Data Valuation Based on the Shapley Value''." arXiv preprint arXiv:2302.11431 (2023). [3] Li, Weida, and Yaoliang Yu. "Faster Approximation of Probabilistic and Distributional Values via Least Squares." The Twelfth International Conference on Learning Representations.

Questions

What's the specific MC estimator being used for computing Data Shapley in the experiment?

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

See weaknesses.

Follow Up Question and Suggestion

Thank you for your reply! 1. Maybe, I am missing something simple here, but why are you measuring the time/iterations until the baselines reach **the bias of DU-Shapley** and not the approximation error against a/the ground truth in your _attached pdf/general statement_? 2. Thanks for the clear-up with the sampling budget. I have to say that this is extremely small in terms of number of Model Evaluations. For an improved version, I strongly suggest to reevaluate the approximation experiments with much higher budgets. Even if this is in some sense unfair for your method, because it would greatly improve the paper for practitioners that are currently approximating.

Clarification on 3.

I thank the authors for their response. **3.** Do I understand correctly that the DU-Shapley values are then highly probabilistic, since they strongly depend on the given sampled data points? In your theoretical analysis, you are taking the limit with respect to the number of players $I \to \infty$. Are you dealing with this randomness, or is it mitigated by the chosen structure of the value function (since it does not matter which data points are sampled)? Could you comment then, if this assumption is reasonable? I would expect that there is heterogeneity in the value of data points.