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

## Abstract

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 accuracy. 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 (Conduct of Hardness and Gradient) score, which approximates the utility of each data subset on model accuracy during a single model training. By deriving the closed-form expression of the Shapley value for each data point under the CHG score utility function, we reduce the computational complexity to the equivalent of a single model retraining, an exponential improvement over existing methods. Additionally, we employ CHG Shapley for real-time data selection, demonstrating its effectiveness in identifying high-value and noisy data. CHG Shapley facilitates trustworthy model training through efficient data valuation, introducing a novel data-centric perspective on trustworthy machine learning.

## 1 Introduction

The central problem of trustworthy machine learning is explaining the decision-making process of models to enhance the transparency of data-driven algorithms. However, the high complexity of machine learning model training and inference processes obscures an intuitive understanding of their internal mechanisms. Approaching trustworthy machine learning from a data-centric perspective (Liu et al., ) offers a new perspective for research. For trustworthy model inference, a representative algorithm is the SHAP (Lundberg and Lee, ), which quantitatively attributes model outputs to input features, clarifying which features influence specific results the most. SHAP and its variants(Kwon and Zou, ) are widely applied in data analysis and healthcare. For trustworthy model training, the Data Shapley algorithm (Ghorbani and Zou, ) stands out. It quantitatively attributes a model’s performance to each training data point, identifying valuable data that improves performance and noisy data that degrades it. Data valuation not only informs us about the extent to which each training data impacts model performance but also underpins subsequent tasks such as data selection, data acquisition, data cleaning, etc., and supports the development of data markets (Mazumder et al., ).

The impressive effectiveness of both SHAP and Data Shapley algorithms is rooted in the Shapley value (Shapley, ). The unique feature of the Shapley value lies in its ability to accurately and fairly allocate contributions to each factor in decision-making processes where multiple factors interact with each other.
However, the exact computation of the Shapley value is $\mathcal{O}(2^{n})$, where $n$ is the number of participants. Consequently, even when employing estimation methods akin to linear least squares regression (Lundberg and Lee, ) or Monte Carlo (Ghorbani and Zou, ), the efficiency of SHAP and Data Shapley algorithms sometimes fails to meet requirements. For example, the most efficient known data valuation method is KNNShapley (Jia et al., ) designed for the k-nearest neighbors algorithm, requiring $\mathcal{O}(\sqrt{n}\log(n)^{2})$ times of model retraining, where $n$ is the number of training data.

In this paper, we focus on the efficiency problem of data valuation on large-scale datasets. Instead of investigating more efficient and robust algorithms to approximate the Shapley value like in (Lundberg and Lee, ; Wang and Jia, ; Wang et al., ), we concentrate on estimating the utility function. The underlying idea is that if the accuracy estimation function of a model trained on a subset can be analytically expressed through some features of the subset, then it becomes possible to directly derive an analytic expression for the Shapley value of each data point.

Our contributions are summarized as follows:

Efficient and Large-Scale Data Valuation Method: We introduce the CHG (Conduct of Hardness and Gradient) score, which assesses the influence of a data subset on model accuracy. By deriving the analytical expression for the Shapley value of each data point under this utility function, we significantly improve upon the $\mathcal{O}(n^{2}\log n)$ time complexity of Data Shapley. Using our proposed CHG Shapley method, valuing the full training dataset takes at most twice the time of conventional training, equivalent to one additional model retraining.

Real-Time Selection of Training Data in Large-Scale Datasets Based on Data Valuation: We employ CHG Shapley for real-time data selection. Experiments involving data-efficient training and model training under noise labels demonstrate the effectiveness of CHG Shapley in identifying high-value and noisy data.

A New Data-Centric Perspective on Trustworthy Machine Learning: CHG Shapley is a parameter-free method, deriving its benefits solely from a deeper understanding of the data. We believe that approaches rooted in data valuation have the potential to enhance understanding of model mechanisms, thereby advancing trustworthy machine learning.

## 2 Background and Related Works

Data-centric AI. For an extended period, the machine learning research community has predominantly concentrated on model development rather than on the underlying datasets (Mazumder et al., ). However, the inaccuracies, unfairness, and biases in models caused by data have become increasingly severe in real-world applications (Wang et al., ). Conducting trustworthy machine learning research from a data-centric perspective has garnered increasing attention from researchers (Liu et al., ). Research on data valuation can also be seen as an effort to understand the machine learning model training process from a data-centric perspective.

Shapley value.
Supposing some players cooperate to finish a task, we denote the player set as $N$ and the utility function defined on every subset of $N$ is denoted as $U$, then the Shapley value (Shapley, ) is the unique solution concept that satisfies the following four axioms:

- •
Dummy player: If $U(S\cup\{i\})=U(S)$ for all $S\subseteq N\setminus\{i\}$, then $\phi(i;U)=0$.
- •
Symmetry: If $U(S\cup\{i\})=U(S\cup\{j\})$ for all $S\subseteq N\setminus\{i,j\}$, then $\phi(i;U)=\phi(j;U)$.
- •
Linearity: For utility functions $U_{1},U_{2}$ and any $\alpha_{1},\alpha_{2}\in\mathbb{R}$, $\phi(i;\alpha_{1}U_{1}+\alpha_{2}U_{2})=\alpha_{1}\phi(i;U_{1})+\alpha_{2}\phi
(i;U_{2})$.
- •
Efficiency: $\sum_{i\in N}\phi(i;U)=U(N)$.

###### Definition 1 ( Shapley ( 1953 ) )

Given a player set $N$ and a utility function $U$, the Shapley value of a player $i\in N$ is defined as

$$ $\phi_{i}\left(U\right):=\frac{1}{n}\sum_{k=1}^{n}{n-1\choose k-1}^{-1}\sum_{S \subseteq N\setminus\{i\},|S|=k-1}\left[U(S\cup i)-U(S)\right]$ (1) $$

Data valuation. Data valuation aims to quantitatively analyze the impact of training data on the performance of machine learning models, particularly deep neural networks. Determining the value of data can facilitate tasks such as data selection (Wang et al., ), acquisition(Mazumder et al., ), and trading(Wang et al., ). Since the performance of machine learning models is derived from the collective contribution of all data points, a fair data valuation algorithm is essential to accurately attribute each data point’s contribution to the model’s performance.

A milestone in data valuation research is the Data Shapley algorithm developed by Ghorbani and Zou (). Data Shapley builds upon the Shapley value formula by treating all data in the training dataset as players in a cooperative game of "training the model together". $U(S)$ represents the accuracy achieved by training the model on dataset subset $S$. Consequently, the Shapley value computed for each data point serves as an indication of its contribution to model performance. Data points with lower values are considered more likely to be harmful, while those with higher values are deemed to be lacking in the model’s representation. Removing low-value data points or acquiring more high-value data points can lead to improved model accuracy, a hypothesis supported by related experiments. Following Data Shapley, several subsequent have been proposed.

KNN Shapley(Jia et al., ) focus on the Shapley value of the k-nearest neighbors algorithm, proposing the closed-form expression of the Shapley value of the KNN scenario, notably improving computational efficiency to $\mathcal{O}(\sqrt{n}\log(n)^{2})$.

Beta Shapley (Kwon and Zou, ) was developed to address an issue identified in Data Shapley regarding the uniform weight allocation for sets with different cardinalities. By relaxing the efficiency axiom in the Shapley value and utilizing a beta distribution to characterize the weights of sets of different cardinalities, Beta Shapley performs better than Data Shapley in tasks such as detecting mislabeled training data.

Data Banzhaf (Wang and Jia, ) aims to mitigate the noise introduced by stochastic gradient algorithms on model accuracy (i.e., utility function) during the model training process. Banzhaf value has also been demonstrated to be the most robust solution concept among all semi-values (i.e., Shapley values without Efficiency restrictions) in the presence of noise in the utility function. Therefore, Data Banzhaf is well-suited for evaluating training data in deep learning scenarios.

Additionally, there has been a surge in work on machine learning systems that utilize Shapley values to compute data values (Karlaš et al., ). All these studies utilize the Shapley value or its variants as their theoretical foundation because it is widely acknowledged in cooperative game theory as the fairest method for allocating contributions (Algaba et al., ).

To provide a more detailed assessment of various data valuation algorithms, Jiang et al. () introduced the OpenDataVal benchmark library. This benchmark library abstracts away details such as model training, allowing researchers to focus solely on algorithm design for data valuation. We also use this benchmark to evaluate our proposed data valuation algorithm.

###### Definition 1 ( Shapley ( 1953 ) )

## 3 Efficient Data valuation

"What’s the value of your data?" Instead of directly assessing the contribution of each data point to model accuracy, we initially explore another pertinent question: "Which data holds greater value in the training process?" In the realm of data selection, numerous significant studies offer varying perspectives. Some focus on the utility of individual data, employing methods such as influence functions (Koh and Liang, ; Yang et al., ; Chhabra et al., ), EL2N score (Paul et al., ), InfoBatch (Qin et al., ), and worst-case training methods (Huang et al., ). These approaches utilize data information and model parameters to calculate a score (e.g., loss) for data selection. Conversely, another approach emphasizes the utility of data subsets (Killamsetty et al., , ; Zhao et al., ), aiming to identify representative subsets of the original dataset that can achieve comparable model accuracy, often utilizing corresponding gradient subsets. We reconcile these two perspectives and introduce the CHG score as a measure of data subset accuracy.

### 3.1 Preliminaries

Let $N=\{1,\dots,n\}$ denotes a labeled training set. The objective is to assign a scalar to each training data point based on its contribution to the model’s performance. A utility function $U:2^{N}\rightarrow R$, mapping from any subset $S$ of the training set (including the empty set) to the performance of the model trained on the subset (denoted as $U(S)$), is usually used for data valuation. In Data Shaply(Ghorbani and Zou, ), the accuracy of the model on a hold-out test set is used as $U(S)$.

### 3.2 CHG Score as a Utility Function for Subset Model Performance

The opacity of $U(S)$, or the fact that $U(S)$ can only be obtained after training a model on $S$, renders marginal contribution-based data valuation algorithms such as Data Shapley (Ghorbani and Zou, ), Beta Shapley (Kwon and Zou, ), Data Banzhaf (Wang and Jia, ), AME (Lin et al., ), and LOO (leave-one-out error) time-consuming and computationally intensive.

On the contrary, if we can determine the model’s accuracy on $S$ without training on it, or even derive the expression for $U(S)$ in terms of $S$, then we can significantly reduce the model training time and expedite the calculation of each data’s value. To achieve this, we first investigate the impact of training the model using a subset of data $S$.

Here we focus on the model training process. Assuming that in the current iteration, the model parameters are denoted by $\theta$. We use $f(\theta):=\frac{1}{N}\sum_{i\in N}f(i;\theta)$ to represent the loss function of the neural network across the entire training dataset. A smaller loss indicates higher model accuracy on the training dataset.

Assuming at this point, no overfitting has occurred, i.e., the model’s accuracy on the training and test datasets is comparable, we can reasonably utilize the training dataset’s loss to estimate the model’s accuracy on the test dataset.
If we update the parameters by training on the subset $S$ using gradient descent, then the next update direction of the parameters is $x:=\frac{1}{|S|}\sum_{i\in S}x_{i}$, where $x_{i}$ represents the gradient of the $i$-th data point. After one step of gradient descent, $\theta$ becomes $\theta-\eta x$.
Subsequently, based on the following lemma, $\|\nabla f(\theta)\|_{2}^{2}-\|\nabla f(\theta)-x\|_{2}^{2}$ can be considered as a metric for evaluating the model’s performance.

###### Lemma 1 ( ( Nesterov , 2018 ) )

Let $f$ be any differentiable function with $L$-Lipschitz continuous gradient, $\theta_{x}=\theta-\eta x$, and $\eta=1/L$(^1^11This is a commonly used assignment method, for example, in proving the convergence of gradient descent for non-convex functions to local minima (Nesterov, ), $\eta$ was set as $1/L$), then we have:

$$ $f(\theta_{x})\leq f(\theta)+\langle\nabla f(\theta),\theta_{x}-\theta\rangle+ \frac{L}{2}\|\theta_{x}-\theta\|_{2}^{2}=f(\theta)-\frac{\eta}{2}(\|\nabla f( \theta)||_{2}^{2}-\|\nabla f(\theta)-x||_{2}^{2})$ (2) $$

Proof: The first inequality is due to the definition of $L$-Lipschitz continuity.

When using traditional empirical risk minimization, measuring the model’s performance using the gradients of the training set on the training process is acceptable. However, inspired by the principles of worst-case training method (Huang et al., ) and InfoBatch (Qin et al., ), we introduce a method to incorporate the difficulty of data points into the model optimization process.

Specifically, our optimization objective is to minimize $\frac{1}{N}\sum_{i\in N}h_{i}f(i;\theta)$ rather than $\frac{1}{N}\sum_{i\in N}f(i;\theta)$ (i.e., empirical risk minimization), where $h_{i}$ is equal to $f(i;\theta)$ but does not participate in model backpropagation. $h_{i}$ can be viewed as the hardness of learning this data point. Generally, when there is no label noise, focusing on hard-to-learn data points can help improve the model’s generalization ability (Huang et al., ) and may reduce training time (Qin et al., ). Then the gradient of $i$-th data changes from $x_{i}$ to $h_{i}x_{i}$, and then we define the Conduct of Hardness and Gradient score (CHG score) of a data subset $S$ as $\|\frac{1}{N}\sum_{i\in N}l_{i}\nabla f(i;\theta)\|_{2}^{2}-\|\frac{1}{N}\sum_
{i\in N}l_{i}\nabla f(i;\theta)-\frac{1}{S}\sum_{i\in S}l_{i}\nabla f(i;\theta
)\|_{2}^{2}$. We use this score to measure the influence of data subsets on model accuracy. We also investigate the performance of the Hardness score ( $\frac{1}{S}\sum_{i\in S}l_{i}$) and Gradient Score ( $\|\frac{1}{N}\sum_{i\in N}\nabla f(i;\theta)\|_{2}^{2}-\|\frac{1}{N}\sum_{i\in
N
}\nabla f(i;\theta)-\frac{1}{S}\sum_{i\in S}\nabla f(i;\theta)\|_{2}^{2}$) in Table 2, see Hardness Shapley and Gradient Shapley.

**Table 1: A taxonomy of data valuation algorithms, mainly abstracted from (Jiang et al., ). The symbol “NA” means the method is not based on model training, then “No Answer”. The symbols ‘- / + / ++’ indicate that a corresponding data valuation method achieves a ‘similar or worse / better / much better’ performance than a random baseline, respectively.**
| Algorithms | Underlying Method | Model Retraining Complexity | Quality of Data Values |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Noisy Label | Noisy Feature | Point | Point |  |  |  |
| Detection | Detection | Removal | Addition |  |  |  |
| LOO | Marginal contribution | $n$ | - | - | + | + |
| Data Shapley (Ghorbani and Zou, ) | Marginal contribution | $\mathcal{O}(n^{2}\log n)$ | + | + | ++ | ++ |
| KNN Shapley (Jia et al., ) | Marginal contribution | NA | + | + | ++ | ++ |
| Beta Shapley (Kwon and Zou, ) | Marginal contribution | $\mathcal{O}(n^{2}\log n)$ | + | + | ++ | ++ |
| Data Banzhaf (Wang and Jia, ) | Marginal contribution | $\mathcal{O}(n\log n)$ | - | - | + | + |
| AME (Lin et al., ) | Marginal contribution | $\mathcal{O}(n^{2}\log n)$ | - | - | ++ | + |
| Influence Function (Koh and Liang, ) | Gradient | NA | - | - | + | + |
| LAVA (Just et al., ) | Gradient | NA | - | ++ | + | + |
| DVRL (Yoon et al., ) | Importance weight | $1$ | + | - | + | ++ |
| Data-OOB (Kwon and Zou, ) | Out-of-bag estimate | NA | ++ | + | - | ++ |
| CHG Shapley (this paper) | Marginal contribution, | $1$ | ++ | + | ++ | NA |
| Gradient and Loss |  |  |  |  |  |  |

###### Lemma 1 ( ( Nesterov , 2018 ) )

### 3.3 CHG Shapley

After obtaining the utility function (CHG score), which approximates the influence of data subsets on model accuracy using gradient and loss information during model training, we can derive the analytical expression for the Shapley value of each data point under this utility function. This enables efficient computation of the value of each data point in large-scale datasets.

###### Theorem 1

Supposing for any subset $S\subseteq N$, $U(S)=\|\alpha\|^{2}_{2}-\|\frac{1}{S}\sum_{i\in S}x_{i}-\alpha\|^{2}_{2}$, then the Shapley value of j-th data point can be expressed as:

$$ $\displaystyle\phi_{j}(U)=$ (3) $\displaystyle\left(-\frac{\sum_{k=1}^{n}\frac{1}{k^{2}}}{n}+\frac{2\sum_{k=1}^ {n}\frac{1}{k}-3\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n}}{n(n-1)}+2\frac{2 \sum_{k=1}^{n}\frac{1}{k}-2\sum_{k=1}^{n}\frac{1}{k^{2}}-1+\frac{1}{n}}{n(n-1) (n-2)}\right)\|x_{j}\|^{2}_{2}$ $\displaystyle-2\frac{\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{n}\frac{1}{k^{2}}- \frac{1}{n}+\frac{1}{n^{2}}}{(n-1)(n-2)}\langle\sum_{i\in N}x_{i},x_{j}\rangle +\frac{2\sum_{k=1}^{n}\frac{1}{k}-2\sum_{k=1}^{n}\frac{1}{k^{2}}-1+\frac{1}{n} }{n(n-1)(n-2)}\|\sum_{i\in N}x_{i}\|^{2}_{2}$ $\displaystyle+\left(\frac{\sum_{k=1}^{n}\frac{1}{k^{2}}-\frac{1}{n}}{n(n-1)}- \frac{2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2}^{n}\frac{1}{k^{2}}-1+\frac{1}{n}} {n(n-1)(n-2)}\right)(\sum_{i\in N}\|x_{i}\|^{2}_{2})$ $\displaystyle+2\frac{\sum_{k=1}^{n}\frac{1}{k}-\frac{1}{n}}{n-1}\langle x_{j}, \alpha\rangle-2\frac{\sum_{k=1}^{n}\frac{1}{k}-1}{n(n-1)}\langle\sum_{i\in N}x _{i},\alpha\rangle$ $$

Proof see Appendix B

We implemented our CHG Shapley data valuation method (see Algorithm 1) based on the code foundation of OpenDataVal (Jiang et al., ) and conducted experiments on the CIFAR-10 embedding dataset on a NVIDIA A40 server. The model used is pre-trained ResNet50 + logistic regression, and we report the results in Table 1.

For noisy label detection tasks and comparisons with other data evaluation methods, see Picture 2. For point removal tasks, see Picture 1.

The experimental results demonstrate that CHG Shapley data valuation method not only exhibits excellent data valuation and noise data detection capabilities, but also achieves remarkable operational efficiency. This is made possible by our research into the utility function that measures the impact of data subsets on model accuracy. In the next section, we will further show its data selection ability based on data valuation and noise label detection.

Figure: Algorithm 1 CHG Shapley-based Data Valuation Algorithm

###### Theorem 1

## 4 Data Selection

In this section, we introduce various implementation strategies and practical techniques to enhance the scalability and efficiency of CHG Shapley. The experiments are conducted on a NVIDIA A40 server.

Last-Layer Gradients: Modern deep learning models possess a vast number of parameters, resulting in high-dimensional gradients. To mitigate this issue, we adopt a last-layer gradient approximation as in(Killamsetty et al., , ). This technique focuses solely on the gradients of the last layer for neural networks in CHG Shapley, significantly improving the speed of the algorithm and other baseline methods.

Per-Class Approximations:
To enhance model performance, we adopt a per-class approach. This method involves caluclate the CHG Shapley separately for each class, which means considering only the data instances belonging to each class in each iteration. This approach not only reduces memory requirements but also decreases computational overhead, thereby improving the overall efficiency of the CHG Shapley-based data selection algorithm.

CHG Shapley-based Data Selection Algorithm:
Here, we detail the CHG Shapley Data Selection Algorithm, integrating the aforementioned techniques to ensure efficient and scalable data valuation and selection.

Figure: Algorithm 2 CHG Shapley-based Data Selection Algorithm

Results: We report the accuracy and time consumption comparisons in Table 2 under the data pruning setting. CHG Shapley demonstrates particularly strong performance when the selection ratio is small, highlighting its ability to identify high-value data effectively. Additionally, the time consumption remains acceptable even when considering data selection processes, underscoring the high efficiency of CHG Shapley as a data valuation method. This efficiency, combined with its accuracy, verifies that CHG Shapley is a practical and powerful tool for data selection and valuation in large-scale machine learning tasks.

The results presented in Table 3, where 30% of the class labels were randomly replaced with other labels, provide additional evidence of CHG Shapley’s capability to detect mislabeled data. CHG Shapley demonstrates superior performance compared to other methods in this scenario, reinforcing its effectiveness in identifying and addressing label noise.

Table: Table 2: The accuracy (%) and time (s) comparison. All methods are trained with ResNet-18.

Table: Table 3: Comparison of performance under noise label setting.

## 5 Discussion and Future Work

In this paper, we define the Conduct of Hardness and Gradient score (CHG score) of a data subset $S$ as $\|\frac{1}{N}\sum_{i\in N}l_{i}\nabla f(i;\theta)\|_{2}^{2}-\|\frac{1}{N}\sum_
{i\in N}l_{i}\nabla f(i;\theta)-\frac{1}{S}\sum_{i\in S}l_{i}\nabla f(i;\theta
)\|_{2}^{2}$, and use this score based on Euclidean distance to measure the influence of data subsets on model accuracy. However, it’s worth noting that many studies on data selection based on gradients utilize different distance measures between $\frac{1}{N}\sum_{i\in N}l_{i}\nabla f(i;\theta)$ and $\frac{1}{S}\sum_{i\in S}l_{i}\nabla f(i;\theta)$, such as cosine similarity (Zhao et al., ), inner product, L1 norm, or their combinations, and then optimize this metric to select data. However, whether these metrics can be used for data valuation remains unknown because, unlike the theoretical support for the aforementioned Euclidean distance, these metrics lack theoretical grounding. Whether cosine similarity, inner product, L1 norm, or their combinations can achieve this goal remains to be investigated.

On the other hand, if cosine similarity and L1 norm are used in our framework, it becomes challenging to derive the corresponding Shapley values. In other words, if the Euclidean distance cannot effectively measure the utility of dataset subsets for model accuracy, the entire data valuation approach proposed in this study becomes computationally infeasible. The root of this problem lies in the complexity of computing Shapley values, which is generally challenging and only tractable when the utility function follows a specific form (such as linear models, Euclidean distance, or inner product).

## Appendix A Data Valuation results

Figure: Figure 1: Point removal experiment on CIFAR10-embeddings dataset.
Refer to caption: extracted/5674955/PIC/output1.png

Figure: Figure 2: Discover noisy datas experiment on CIFAR10-embeddings dataset.
Refer to caption: extracted/5674955/PIC/output2.png

## Appendix B Proof of Theorem 1

From $U(S)=||\alpha||^{2}-||\frac{1}{S}\sum_{i\in S}x_{i}-\alpha||^{2}$ we have $U(S)=-||\frac{1}{S}\sum_{i\in S}x_{i}||^{2}+2\frac{1}{S}\sum_{i\in S}x_{i}
\alpha=U_{1}(S)+U_{2}(S)$, where $U_{1}(S)=-||\frac{1}{S}\sum_{i\in S}x_{i}||^{2}$, $U_{2}(S)=2\frac{1}{S}\sum_{i\in S}x_{i}\alpha$.

For $U_{2}$, we have:
$\phi_{j}(U_{2})=\left(\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k}\right)x_{j}\alpha-
\left(\frac{1}{n}\sum_{k=2}^{n}\frac{1}{k}\right)(\frac{1}{n-1}\sum_{i\in N/{j
}}x_{i}\alpha)$

Then we have: $\phi_{j}(U_{2})=\left(\frac{1}{n-1}\sum_{k=1}^{n-1}\frac{1}{k}\right)x_{j}
\alpha-\left(\frac{1}{n-1}\sum_{k=2}^{n}\frac{1}{k}\right)(\frac{1}{n}\sum_{i
\in N}x_{i}\alpha)$

Then:

$$ $U_{1}(S\cup j)-U_{1}(S)=-\frac{1}{(S+1)^{2}}x_{j}^{2}-\frac{2}{(S+1)^{2}}x_{j} (\sum_{i\in S}x_{i})+\frac{2S+1}{S^{2}(S+1)^{2}}(\sum_{i\in S}x_{i})^{2}.$ $$

Because of the linearity of the Shapley Value, we can calculate the Shapley value under utility functions $U_{1}$ and $U_{2}$ separately, and $\phi_{j}(U)=\phi_{j}(U_{1})+\phi_{j}(U_{2})$.

$$ $\displaystyle\phi_{j}(U_{1})$ $\displaystyle=-\left(\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k^{2}}\right)x_{j}^{2}- \left(\frac{2}{n(n-1)}\sum_{k=2}^{n}\frac{(k-1)}{k^{2}}\right)(\sum_{i\in N/{j }}x_{i})x_{j}$ $\displaystyle+\left(\frac{1}{n(n-1)}\sum_{k=2}^{n}\frac{(2k-1)}{k^{2}(k-1)} \right)(\sum_{i\in N/{j}}x_{i}^{2})$ $\displaystyle+\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{2 }(k-1)}\right)(\sum_{a\in N/{j}}\sum_{b\in N/{j},a\neq b}x_{a}x_{b})$ $$

Then we have:

$$ $\displaystyle\phi_{j}(U_{1})$ $\displaystyle=-\left(\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k^{2}}\right)x_{j}^{2}+ \left(\frac{2}{n(n-1)}\sum_{k=2}^{n}\frac{(k-1)}{k^{2}}\right)x_{j}^{2}-\left( \frac{2}{n(n-1)}\sum_{k=2}^{n}\frac{(k-1)}{k^{2}}\right)(\sum_{i\in N}x_{i})x_ {j}$ $\displaystyle+\left(\frac{1}{n(n-1)}\sum_{k=2}^{n}\frac{(2k-1)}{k^{2}(k-1)} \right)(\sum_{i\in N}x_{i}^{2})-\left(\frac{1}{n(n-1)}\sum_{k=2}^{n}\frac{(2k- 1)}{k^{2}(k-1)}\right)x_{j}^{2}$ $\displaystyle-\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{2 }(k-1)}\right)(\sum_{i\in N}x_{i}^{2})$ $\displaystyle+\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{2 }(k-1)}\right)(\sum_{a\in N}\sum_{b\in N}x_{a}x_{b})$ $\displaystyle-2\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{ 2}(k-1)}\right)(\sum_{a\in N}x_{a}x_{j})$ $\displaystyle+2\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{ 2}(k-1)}\right)x_{j}^{2}$ $$

Then we have:

$$ $\displaystyle\phi_{j}(U_{1})$ $\displaystyle=[-\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{2}{n(n-1)}\sum_ {k=2}^{n}\frac{(k-1)}{k^{2}}-\frac{1}{n(n-1)}\sum_{k=2}^{n}\frac{(2k-1)}{k^{2} (k-1)}+\frac{2}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{2}(k-1)}]x_{j} ^{2}$ $\displaystyle-\left(\frac{2}{n(n-1)}\sum_{k=2}^{n}\frac{(k-1)}{k^{2}}\right)( \sum_{i\in N}x_{i})x_{j}-2\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1 )(k-2)}{k^{2}(k-1)}\right)(\sum_{i\in N}x_{i})x_{j}$ $\displaystyle+\left(\frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{2 }(k-1)}\right)(\sum_{a\in N}\sum_{b\in N}x_{a}x_{b})$ $\displaystyle+\left(\frac{1}{n(n-1)}\sum_{k=2}^{n}\frac{(2k-1)}{k^{2}(k-1)}- \frac{1}{n(n-1)(n-2)}\sum_{k=3}^{n}\frac{(2k-1)(k-2)}{k^{2}(k-1)}\right)(\sum_ {i\in N}x_{i}^{2})$ $$

Then we have:

$$ $\displaystyle\phi_{j}(U_{1})$ $\displaystyle=[-\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n(n-1)}\left (2\sum_{k=1}^{n}\frac{1}{k}-3\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n}\right)+ 2\frac{2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2}^{n}\frac{1}{k^{2}}-1+\frac{1}{n} }{n(n-1)(n-2)}]x_{j}^{2}$ $\displaystyle-\frac{2}{n(n-1)}\left(\sum_{k=2}^{n}\frac{1}{k}-\sum_{k=2}^{n} \frac{1}{k^{2}}+\frac{1}{(n-2)}\left(2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2}^{n }\frac{1}{k^{2}}-1+\frac{1}{n}\right)\right)(\sum_{i\in N}x_{i})x_{j}$ $\displaystyle+\frac{1}{n(n-1)(n-2)}\left(2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2 }^{n}\frac{1}{k^{2}}-1+\frac{1}{n}\right)(\sum_{a\in N}\sum_{b\in N}x_{a}x_{b})$ $\displaystyle+\left(\frac{1}{n(n-1)}\left(\sum_{k=2}^{n}\frac{1}{k^{2}}+1- \frac{1}{n}\right)-\frac{2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2}^{n}\frac{1}{k^ {2}}-1+\frac{1}{n}}{n(n-1)(n-2)}\right)(\sum_{i\in N}x_{i}^{2})$ $$

Then we have:

$$ $\displaystyle\phi_{j}(U_{1})$ $\displaystyle=[-\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n(n-1)}\left (2\sum_{k=1}^{n}\frac{1}{k}-3\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n}\right)+ 2\frac{2\sum_{k=1}^{n}\frac{1}{k}-2\sum_{k=1}^{n}\frac{1}{k^{2}}-1+\frac{1}{n} }{n(n-1)(n-2)}]x_{j}^{2}$ $\displaystyle-\frac{2}{(n-1)(n-2)}\left(\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{ n}\frac{1}{k^{2}}-\frac{(n-1)}{n^{2}}\right)(\sum_{i\in N}x_{i})x_{j}$ $\displaystyle+\frac{1}{n(n-1)(n-2)}\left(2\sum_{k=1}^{n}\frac{1}{k}-2\sum_{k=1 }^{n}\frac{1}{k^{2}}-1+\frac{1}{n}\right)(\sum_{a\in N}\sum_{b\in N}x_{a}x_{b})$ $\displaystyle+\left(\frac{1}{n(n-1)}\left(\sum_{k=1}^{n}\frac{1}{k^{2}}-\frac{ 1}{n}\right)-\frac{2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2}^{n}\frac{1}{k^{2}}-1 +\frac{1}{n}}{n(n-1)(n-2)}\right)(\sum_{i\in N}x_{i}^{2})$ $$

so :

$$ $\displaystyle\phi_{j}(U)$ $\displaystyle=[-\frac{1}{n}\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n(n-1)}\left (2\sum_{k=1}^{n}\frac{1}{k}-3\sum_{k=1}^{n}\frac{1}{k^{2}}+\frac{1}{n}\right)+ 2\frac{2\sum_{k=1}^{n}\frac{1}{k}-2\sum_{k=1}^{n}\frac{1}{k^{2}}-1+\frac{1}{n} }{n(n-1)(n-2)}]x_{j}^{2}$ $\displaystyle-\frac{2}{(n-1)(n-2)}\left(\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{ n}\frac{1}{k^{2}}-\frac{1}{n}+\frac{1}{n^{2}}\right)(\sum_{i\in N}x_{i})x_{j}$ $\displaystyle+\frac{1}{n(n-1)(n-2)}\left(2\sum_{k=1}^{n}\frac{1}{k}-2\sum_{k=1 }^{n}\frac{1}{k^{2}}-1+\frac{1}{n}\right)(\sum_{a\in N}\sum_{b\in N}x_{a}x_{b})$ $\displaystyle+\left(\frac{1}{n(n-1)}\left(\sum_{k=1}^{n}\frac{1}{k^{2}}-\frac{ 1}{n}\right)-\frac{2\sum_{k=2}^{n}\frac{1}{k}-2\sum_{k=2}^{n}\frac{1}{k^{2}}-1 +\frac{1}{n}}{n(n-1)(n-2)}\right)(\sum_{i\in N}x_{i}^{2})$ $\displaystyle+\frac{2}{n-1}\left(\sum_{k=1}^{n}\frac{1}{k}-\frac{1}{n}\right)x _{j}\alpha-\frac{2}{n(n-1)}\left(\sum_{k=1}^{n}\frac{1}{k}-1\right)(\sum_{i\in N }x_{i})\alpha$ $$

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 4
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
soundness: 4
strengths: The paper is very well written and organized. The main idea and the method are presented very clearly.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
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?
soundness: 3
strengths: - The proposed method of combining hardness and gradient utility function is novel. 
- The authors provided experimental results to support their theoretical claims.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
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.
soundness: 2
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.
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.
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.

Meta-review: 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.

Decision: Reject