CHG Shapley: Efficient Data Valuation and Selection towards Trustworthy Machine Learning

Authors: Huaiguang Cai
Primary area: interpretability and explainable AI
Keywords: Data Valuation, Shapley Value, Data selection

Abstract:
Understanding the decision-making process of machine learning models is crucial for ensuring trustworthy machine learning. Data Shapley, a landmark study on data valuation, advances this understanding by assessing the contribution of each datum to model performance. However, the resource-intensive and time-consuming nature of multiple model retraining poses challenges for applying Data Shapley to large datasets. To address this, we propose the CHG (compound of Hardness and Gradient) utility function, which approximates the utility of each data subset on model performance in every training epoch. By deriving the closed-form Shapley value for each data point using the CHG utility function, we reduce the computational complexity to that of a single model retraining, achieving a quadratic improvement over existing marginal contribution-based methods. We further leverage CHG Shapley for real-time data selection, conducting experiments across three settings: standard datasets, label noise datasets, and class imbalance datasets. These experiments demonstrate its effectiveness in identifying high-value and noisy data. By enabling efficient data valuation, CHG Shapley promotes trustworthy model training through a novel data-centric perspective.

Decision: reject
Reviewer scores: 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1730432465784

thread_type:
official_review

<thread_object>
creator: reviewer_jhq7

<content>
summary:
The paper studies the problem of data valuation and an application of data valuation, namely data selection during training. The authors focus on the efficiency of data valuation for large datasets, which presents an issue for many common Shapley value-based methods. They propose a Gradient Shapley and a compound of hardness and Gradient Shapley as the data valuation method. Empirical investigation shows the comparison of these two proposed methods with several existing methods.

strengths:
- The data valuation problem is highly relevant and interesting to the community. In particular, the issue being studied is the computational cost of Shapley value-based methods. It is also a highly relevant issue.
- The writing is relatively clear.
- There are experimental results against several existing methods.

weaknesses:
- The authors propose a new utility function that takes into account the "hardness". From lines 234-235, it seems the optimization objective of the ML model is changed. However, this new optimization objective does not seem to have been theoretically justified.
- The proposed approach utilizes an approximation of the change in the loss function, but does not seem to show how good this approximation is.
- Furthermore, the proposed approach requires computing a per-sample gradient and storing these gradients. It does not seem to significantly reduce the computational cost of training, and additionally incurs memory overhead.
- More extensive expreimental results, larger datasets and larger models can add to the strength of the claims.

questions:
How are (Wu et al., 2022) and (Ki et al., 2023) related to this work? Should they be compared?

`In this paper, we focus on the efficiency problem of data valuation on large-scale datasets.`

How large is considered large-scale datasets? Data-OOB seems to be able to scale to millions of data points. Is there comparison on datasets of similar scales?

What is $\alpha$ in Theorem 1?

What is the memory overhead from storing the per-sample gradients?

Typically, mini-batch SGD is used for training (namely the gradient is computed w.r.t. a mini-batch instead of each data point), which does not compute per-sample gradients. Does that mean you method needs to incur additional computational overhead?

What is the error (theoretical or empirical) of the last-layer gradient as an approximation?

_References_

DAVINZ: Data Valuation using Deep Neural Networks at Initialization. Zhaoxuan Wu, Yao Shu, Bryan Kian Hsiang Low. In ICML 2022.

DATA VALUATION WITHOUT TRAINING OF A MODEL. Nohyun Ki, Hoyong Choi, Hye Won Chung. In ICLR 2023.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730673255856

thread_type:
official_review

<thread_object>
creator: reviewer_hu3m

<content>
summary:
The paper studies data evaluation with regard to its contribution to model performance. Prior work on Shapley value and Data Shapley suffers from high resource and time requirements to evaluate each data point. To circumvent this issue, the authors propose instead to estimate the utility function using the CHG (Compound of Hardness and Gradient) score to obtain a close-formed Shapley value for each data point. This approach reduces the computation complexity of Data Shapley to that of a single model training run. Furthermore, the authors extend this framework to real-time data selection, which was previously impractical using prior methods of calculating data value.

strengths:
- The proposed method of combining hardness and gradient utility function is novel. 
- The authors provided experimental results to support their theoretical claims.

weaknesses:
- The writing is confusing and lacks intuition. In Theorem 1, the authors provided a long equation 4 without explaining the importance of each term in this expression. 
- In Table 2, it is not immediately clear why CHG Shapley outperforms other methods w.r.t accuracy and time. For example, CHG Shapley does not always provide the highest accuracy across different fractions of CIFAR 10 and CIFAR 100. Moreover, in CIFAR10, AdaptiveRandom sometimes even outperforms CHG Shapley while running for a shorter time. 
- Similarly, in Table 3, the authors only draw the conclusion that CHG Shapley is outperforming Gradient Shapley. However, CHG Shapley is not better than existing methods in most comparisons.

questions:
- Can the authors clarify how CHG Shapley is doing better than prior work when the empirical findings seem to suggest the contrary? 
- Can the authors provide more intuition in Equation 4 (Theorem 1)? What does each term here mean and where do they come from?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730876097631

thread_type:
official_review

<thread_object>
creator: reviewer_iunn

<content>
summary:
The paper proposed a gradient-based method to reduce the computational cost of Data Shapley: the CHG (compound of Hardness and Gradient) utility function, which approximates the utility of each data subset on model performance in every training epoch. By deriving the closed-form Shapley value for each data point using the CHG utility function, they reduce the computational complexity to that of a single model retraining. They test CHG Shapley for real-time data selection in three settings: standard datasets, label noise datasets, and class imbalance datasets.

strengths:
The paper is very well written and organized. The main idea and the method are presented very clearly.

weaknesses:
I do not see substantial difference between the proposed method and the existing gradient based methods, especially the following one. Even in the experiments, the difference is not always noticeable. 

- Wang et al., 2024, Data Shapley in One Training Run.

Minor comments: The previous gradient-based methods are not listed in Table 1.

questions:
Is there fundamental difference between your method and the methods in the three papers below? What is the advantage of your method?
- Wang et al., 2024. Data Shapley in One Training Run.
- Xia et al., 2024. LESS: Selecting Influential Data for Targeted Instruction Tuning
- Pruthi et al. 2020. Estimating Training Data Influence by Tracing Gradient Descent
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposed a gradient-based method to reduce the computation of the Shapley value of training data. The proposed CHG (compound of Hardness and Gradient) utility function approximates the utility of each data subset on model performance.  Using the CHG utility function, the authors show that the task of computing data shapley reduces to a single model retraining. 

Reviewers are most concerned about the novelty of the paper and unclear performance improvements compared to existing approaches. For the former, the authors might want to add discussions on how their paper related to several references raised by the reviewers. For the latter, the authors are encouraged to revisit their experiment results.