Validation Free and Replication Robust Volume-based Data Valuation
Year: 2022

Abstract:
Data valuation arises as a non-trivial challenge in real-world use cases such as collaborative machine learning, federated learning, trusted data sharing, data marketplaces. The value of data is often associated with the learning performance (e.g., validation accuracy) of a model trained on the data, which introduces a close coupling between data valuation and validation. However, a validation set may not be available in practice and it can be challenging for the data providers to reach an agreement on the choice of the validation set. Another practical issue is that of data replication: Given the value of some data points, a dishonest data provider may replicate these data points to exploit the valuation for a larger reward/payment. We observe that the diversity of the data points is an inherent property of a dataset that is independent of validation. We formalize diversity via the volume of the data matrix (i.e., determinant of its left Gram), which allows us to establish a formal connection between the diversity of data and learning performance without requiring validation. Furthermore, we propose a robust volume measure with a theoretical guarantee on the replication robustness by following the intuition that copying the same data points does not increase the diversity of data. We perform extensive experiments to demonstrate its consistency in valuation and practical advantages over existing baselines and show that our method is modeland task-agnostic and can be flexibly adapted to handle various neural networks.

heading: 1 Introduction
text: Data is increasingly recognized as a valuable resource [19], so we need a principled measure of its worth. A suitable data valuation has wide-ranging applications such as fairly compensating clinical trial researchers for their collected data [12, 16, 25], fostering collaborative machine learning and federated learning among industrial organizations [35, 36, 39], encouraging trusted data sharing and building data marketplaces [7, 30, 32, 37], among others.
A popular viewpoint is that the value of data should correlate with the learning performance of a model trained on the data [14, 18], which enforces a close coupling between data valuation and validation. However, a validation set may not always be available in practice [35]. Also, as different choices of the validation set can lead to different data valuations, it is challenging for the data providers to agree on the choice of such a validation set [35]. Since valuation is coupled with validation, if the
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
validation set is not sufficiently representative of the distribution of test queries in a learning task, the resulting valuation may not be as accurate/useful [40]. We adopt a different perspective: The value of data should be related to its intrinsic properties and valuation can be decoupled from validation by considering the inherent diversity of the data. Intuitively, a more diverse collection of data points corresponds to a higher-quality dataset and thus yields a larger value. This perspective circumvents the above practical limitations and allows our valuation method to be model- and task-agnostic. We formalize diversity via the volume of the data matrix (i.e., determinant of its left Gram).
Data replication is another practical issue in data valuation due to the digital nature and anonymous setting of data marketplaces [15]. Supposing a dataset has some value and a data provider instead offers one containing two copies of every data point in this dataset, is this “new” dataset twice as valuable as the original one? Intuitively, the answer should be no as replication adds no new data and so does not increase diversity. We formalize this intuition by constructing a compressed version of the original data to assign little value to replicated data and still preserve its inherent diversity, hence guaranteeing replication robustness.
We provide theoretical justifications for formalizing diversity via volume: Firstly, diversity should be non-negative and monotonic [14, 18, 35, 38] and volume satisfies both properties. Secondly, a greater diversity should lead to a better learning performance [23]: We formally show that a larger volume generally leads to a better performance using the ordinary least squares (OLS) framework and our method can be flexibly adapted to handle more complex machine learning models (i.e., various neural networks) in our experiments. Specifically, data with a larger volume can lead to a more accurate pseudo-inverse (i.e., a key component of the least squares solution) and a smaller mean squared error.
To ensure replication robustness, we find that the marginal increase in value from replication must diminish to zero. Otherwise, a data provider can exploit this valuation by making infinite copies of the data to achieve infinite value. We thus formalize the notion of replication robustness via the asymptotic value attainable through replication. Unfortunately, the conventional definition of volume does not have this property. So, we propose a robust volume (RV) measure by constructing a compressed version of the original data that groups similar data via discretized cubes of the input feature space and represents those in each cube via a statistic. The RV measure offers practitioners the flexibility to trade off between diversity representation and replication robustness via the cube’s width. We perform extensive experiments on synthetic and real-world datasets to demonstrate that our method produces consistent valuations with existing methods while making fewer assumptions.
The specific contributions of our work here include:
• Formalizing a measure of data diversity via the volume of data (Sec. 2) and justifying the suitability of volume for data valuation both theoretically (Sec. 3) and empirically (Sec. 5); • Formalizing the notion of replication robustness and designing a data valuation method based on the robust volume (RV) measure with a theoretical guarantee on replication robustness (Sec. 4); • Performing extensive empirical comparisons with baselines to demonstrate that our method is consistent in valuation without validation, replication robust, and can be flexibly adapted to handle complex machine learning models such as various neural networks (Sec. 5).

heading: 2 Problem Setting and Notations
text: Consider two data submatrices XS and XS′ to be valued that contain s and s′ rows of d-dimensional input feature vectors, respectively. Let PS := [X>S 0]
> ∈ Rn×d be the zero-padded version of XS ∈ Rs×d. We concatenate the data submatrices along the rows to form the full data matrix X ∈ Rn×d, i.e., X := [X>S X>S′ ]> and n = s + s′. We denote the corresponding observed labels/responses as y := [y>S y > S′ ] > ∈ Rn×1. The least squares solution from OLS is w := X+y = argminβ ‖y −Xβ‖ 2 where X+ := (X>X)−1X> is the pseudo-inverse of X. Similarly, we denote X+S as the pseudo-inverse of XS and wS := X + SyS . To ease notations, let V := Vol(X) and VS := Vol(XS) where Vol() is defined below. Let |A| denote the determinant of a square matrix A. The left Gram matrix of X is G := X>X ∈ Rd×d, so for data submatrix XS , GS := X>SXS ∈ Rd×d. Definition 1 (Volume). For a full-rank X ∈ Rn×d with n ≥ d, Vol(X) := √ |(X>X)| = √ |G|.
We adopt the above definition of volume for several reasons: (a) Often, the input feature space of the data is pre-determined and fixed due to the data collection process. But, new data can stream in and
so, n can grow indefinitely while d remains fixed [9, 10]. (b) By leveraging the formal connection between volume and learning performance (Sec. 3), we can design a validation free volume-based data valuation to assign a larger value to data leading to a better learning performance. (c) This affords an intuitive interpretation between volume and diversity: Adding a data point to a dataset can increase the diversity/volume depending on the data points already in the dataset (Lemma 1).
We restrict our discussion to full-rank matrices X, XS , and XS′ since otherwise we can adopt the Gram-Schmidt process to remove the linearly dependent columns [9, 10]. In practice, we perform pre-processing such as principal component analysis to reduce the dimension of the input feature space to ensure that this assumption is satisfied. This assumption is to ensure that there are no redundant features, namely, features that can be exactly reconstructed using other features. For instance, if a dataset already contains monthly salaries, then an annual salary would be redundant.

heading: 3 Larger Volume Entails Better Learning Performance
text: The value of a data (sub)matrix depends on the learning performance trained on it [14, 18] which, we will show, depends on its volume. Simply put, the larger the volume, the better the learning performance. In this section, we will formalize this claim through the ordinary least squares (OLS) framework. In particular, we will investigate two metrics for learning performance: (a) the quality of the pseudo-inverse represented by biasS :=
∥∥P+S −X+∥∥ because estimating X+ accurately is important to achieving small mean squared error (MSE) [9] and where P+S := (X > SXS)
−1P>S , and (b) the MSE denoted as L(wS) := ‖y −XwS‖2.

heading: 3.1 Larger Volume Entails Smaller Bias
text: In regression problems, the closed-form optimal solution is constructed via X+ computed using X. So, the bias of P+S from X
+ indirectly determines the value of XS [9], i.e., a smaller bias means a larger value. We show in Proposition 1 below that ‘a larger volume means a smaller bias’ always holds for d = 1. For d > 1, it requires additional assumptions which are mostly satisfied via empirical verification (Fig. 1). Proposition 1 (Volume vs. Bias for d = 1). For non-zero XS ,XS′ of X ∈ Rn×1, VS ≥ VS′ ⇐⇒ biasS − biasS′ ≤ 0.
The above result can be generalized to M > 2 non-zero data submatrices: Let X := [X>S1 X > S2 · · · X>SM ]
> and w.l.o.g., suppose that VS1 ≥ VS2 ≥ . . . ≥ VSM . Then, biasS1 ≤ biasS2 ≤ . . . ≤ biasSM . For d > 1, counterexamples exist (see Fig. 1), so we instead compare biasS and biasS′ in the next result: Proposition 2 (Volume vs. Bias in General). For full-rank XS ,XS′ of X ∈ Rn×d,
bias2S − bias2S′ = 1
V 4S ∥∥QSX>S ∥∥2 − 1V 4S′ ∥∥QS′X>S′∥∥2 + 2 〈 1 V 2 QX>, 1 V 2S′ QS′P > S′ − 1 V 2S QSP > S 〉 where Q := ∑k l=1(λlσl) −1∏k j=1,j 6=l(G − λjI), {λl}kl=1 denotes the k unique eigenvalues of the left Gram matrix G of X, QS ,QS′ are similarly defined w.r.t. GS ,GS′ , PS and PS′ are, respectively, zero-padded versions of XS and XS′ , and σl :=∑k g=1(−1)g+1λ k−g l [ ∑ H⊆{1,...,k}\{l},|H|=g−1( ∏ h∈{1,...,k}\H λ −1 h )].
The proof of Proposition 1 (Appendix A.1) relies on a key observation that for d = 1, the left Gram matrix is a number and the rest of the proof follows. However, it cannot be generalized to that for d > 1, so we resort to a different proof technique. The proof of Proposition 2 requires Lemma 2 in Appendix A.1 which establishes a formal connection between volume and G−1 using the Sylvester’s formula. To obtain VS ≥ VS′ =⇒ biasS ≤ biasS′ , there are two cases requiring different additional assumptions: (A) VS VS′ , and (B)
∥∥QSX>S ∥∥ ≈ ∥∥QS′X>S′∥∥ and V max(VS , VS′). Case A is intuitive: VS VS′ means XS is much “larger” in volume than XS′ , so biasS is smaller. Case B is when XS and XS′ are similar (e.g., when they are sampled from the same data distribution). The intuition is that the first difference term will be relatively large in magnitude (so, its sign will dominate the overall expression), while the second inner product term will be relatively small in magnitude. This is because the first difference term involves 1/V 4S and 1/V 4 S′ but the second inner
product term involves 1/(V 2×V 2S ) and 1/(V 2×V 2S′), and we show V max(VS , VS′) (Lemma 3 in Appendix A.1). Subsequently, ∥∥QSX>S ∥∥ ≈ ∥∥QS′X>S′∥∥ and VS ≥ VS′ suggest that the first difference term (and thus the overall expression) is likely negative. We empirically verify in Fig. 1 that VS ≥ VS′ =⇒ biasS ≤ biasS′ holds for more than 80% of times.

heading: 3.2 Larger Volume Entails Smaller MSE
text: In Proposition 3 (see proof in Appendix A.2) below, we will show a similar result (to Proposition 1) theoretically analyzing the connection between volume and MSE when d = 1, which may be surprising since Vol() (Definition 1) does not consider y at all and can yet determine which data submatrix offers better predictions on the rest of the (unobserved) data. Unfortunately, such a result does not directly generalize to d > 1 or beyond two submatrices. Nevertheless, we will analyze the effect of volume on the learning performance (i.e., MSE) in general.
Proposition 3 (Volume vs. MSE for d = 1). For non-zero XS ,XS′ of X ∈ Rn×1, VS ≥ VS′ ⇐⇒ L(wS)− L(wS′) ≤ 0.
Unfortunately, the above result does not generalize to d > 1. For full-rank XS ,XS′ of X ∈ Rn×d, we have derived in Appendix A.2 that
L(wS)− L(wS′) = 〈wS −wS′ , (X>SXS + X>S′XS′)(wS + wS′)− 2X>y〉 (1)
and also shown in Appendix A.2 that since L(wS)− L(wS′) explicitly depends on y (1) and Vol() does not include y at all, it is possible to adversarially construct y s.t. L(wS) − L(wS′) > 0 or L(wS)− L(wS′) < 0 for some fixed XS ,XS′ . The adversarial cases notwithstanding, volume is regarded as a good surrogate measure of the quality of data applied to active learning and matrix subsampling with theoretical performance guarantees [11, 28]. Similarly, we can adopt the perspective that Vol() is a measure of the diversity in the input features [23], which provides an intuitive interpretation for Proposition 3: A more diverse dataset with a larger volume gives a better learning performance (i.e., smaller MSE). We will show in Sec. 5.2 that not requiring labels/responses can be an advantage in practice if the labels/responses are noisy/corrupted or there is a distributional difference between the validation and test sets.
We conclude Sec. 3 by empirically verifying whether the additional assumptions described in the last paragraph of Sec. 3.1 are satisfied by checking the percentage of times that VS ≥ VS′ =⇒ biasS − biasS′ ≤ 0 holds. To elaborate, we randomly and identically sample equal-sized XS ,XS′ over 500 independent trials and compute the percentage of times that a larger volume leads to better learning performance (vertical axis) against the size of XS ,XS′ (horizontal axis). We consider sampling XS ,XS′ from either a uniform or normal distribution of varying dimensions: In Fig. 1, for example, ‘N d = 1’ denotes XS ,XS′ being sampled from 1-dimensional standard normal distribution. For MSE, the response y of a data point x is calculated from y = sin(〈w∗,x〉) where the true parameters w∗ are randomly sampled from U(0, 2)d. Fig. 1 (left) shows that a larger volume leads to a smaller bias for more than 80% of times, thus verifying that the additional assumptions in Sec. 3.1 are satisfied. Fig. 1 (right) shows that a larger volume leads to a smaller MSE for more than 50% of times for d ≤ 10, which is consistent with the above implications from (1).

heading: 4 Robustifying Volume-based Data Valuation
text: As a larger volume can entail a better learning performance (Sec. 3), we consider a volume-based data valuation method. Unfortunately, volume (Definition 1) is not robust to replication via direct data copying. Hence, we will introduce a modified volume measure that can trade off a more refined representation of diversity for greater robustness to replication.

heading: 4.1 First Attempt of Volume-based Data Valuation
text: Directly using Vol(X) as a valuation of X satisfies both non-negativity and monotonicity which follow directly from Definition 1 and the matrix determinant lemma, respectively:
Proposition 4 (Non-negativity and Monotonicity of Vol()). For full-rank X ∈ Rn×d, Vol(X) ≥ 0 and Vol([X> x>]>) ≥ Vol(X) where x ∈ R1×d is a new data point.
The properties of Vol() in Proposition 4 imply that a bigger-sized X (i.e., more data) should yield a larger value [14, 18, 35]. However, Vol() is unbounded and has a multiplicative scaling factor w.r.t. replication. The implication is that a data provider can arbitrarily “inflate” the volume or value of data by replicating the data infinitely, as shown in the following result (see proof in Appendix A.3):
Lemma 1 (Unbounded Multiplicative Scaling of Vol(X) from Replication). For full-rank X ∈ Rn×d, let xq ∈ R1×d be a data point replicated for m ≥ 1 times and Xrep := [X> x>q . . . x>q ]> ∈ R(n+m)×d. Then, Vol(Xrep) = Vol(X)× (1 +m× xq(X>X)−1x>q )1/2.
Replication robustness defined via inflation. We define a measure of inflation as the ratio ν(replicate(X, c))/ν(X) where ν() is a data valuation function (e.g., Vol()) mapping a data matrix to a real value, the function replicate(X; c) directly copies the data in X and appends them back to X to output Xrep ∈ R(nc)×d, and the replication factor c denotes the amount of replication. One way of replication is to copy the entire X for c times. Another way is to copy some data submatrix for a certain number of times s.t. Xrep ∈ R(nc)×d. We consider the second way because replicating different data increases the value differently (Lemma 1). We define below a measure of replication robustness to formalize the intuition that greater robustness should guarantee smaller inflation:
Definition 2 (Replication Robustness of Data Valuation ν()). Define replication robustness of ν() as γν := ν(X)/(supc≥1 ν(Xrep)) where Xrep := replicate(X, c) ∈ R(nc)×d.
The theoretically optimal robustness is γν = 1, which implies no additional gain from replicating data, hence discouraging replication completely. In contrast, the worst-case robustness is γν = 0, which is the case for any ν() that strictly monotonically increases with replication and, in particular, γVol = 0 by applying Lemma 1. As a result, a replication robust data valuation function must have a diminishing marginal value from replication: The additional gain from having more copies of the same data converges asymptotically to 0 w.r.t. c. This aligns with what we observe in practice: Repeatedly adding the same data to a training set does not improve the learning performance indefinitely.

heading: 4.2 Replication Robust Volume (RV)-Based Data Valuation
text: We will propose an RV measure by constructing a compressed version of original data matrix X that groups similar data points via discretized cubes of the input feature space and represents those in each cube via a statistic. The RV measure offers practitioners the flexibility to trade off a more refined diversity representation for greater replication robustness by increasing the cube’s width.
Definition 3 (Replication Robust Volume (RV)). Let the d-dimensional input feature space/domain for X be discretized into a set Ψ of d-cubes of width/discretization coefficient ω, φi denote the number of data points in d-cube i ∈ Ψ, µi ∈ R1×d be a statistic (e.g., mean vector) of the data points in d-cube i, and X̃ := [µ>i ] > i∈Ψ:φi 6=0 be a compressed version of X s.t. each row of X̃ is a statistic µi of the data points in non-empty d-cube i. The replication robust volume is
RV(X;ω) := Vol(X̃)× ∏ i∈Ψ ρi (2)
where ρi := ∑φi p=0 α p with hyperparameter α ∈ [0, 1] controlling the degree of robustness.
In contrast to the unbounded Vol(), we ensure that RV(;ω) is bounded by setting ∏ i∈Ψ ρi to be bounded and convergent w.r.t. the size of the replicated data. Note that φi = 0 =⇒ ρi = 1 (i.e., an empty d-cube) and φi > 0 =⇒ ρi > 1. Before considering any robustness guarantee, we will first show in Proposition 5 (see proof in Appendix A.3) below that RV (Definition 3) preserves the original volume in a relative sense, i.e., the ratio VS/VS′ is preserved. The implication is a similar effect of RV on the learning performance (Sec. 3), as empirically demonstrated in Sec. 5.1.
Proposition 5 (Bounded Distortion of RV(XS ;ω)/RV(XS′ ;ω)). Define distortion δ(ω) := [RV(XS ;ω)/RV(XS′ ;ω)]/[Vol(XS)/Vol(XS′)]. Then, (exp(β−1))−1 ≤ δ(ω) ≤ exp(β−1) for any ω > 0 where β = 1/(αn). For example, β = 10 bounds δ(ω) ∈ [0.905, 1.105] approximately.
Near-optimal robustness by upper-bounding inflation. We have previously defined robustness (Definition 2) as the maximum attainable inflation via replication. Since ρi and inflation are monotonic in φi, we consider the asymptotic inflation: φi →∞. In Definition 3, even when the data in d-cube i is replicated infinitely many times, the inflation from this d-cube is still upper-bounded by a constant. This can be generalized to all the d-cubes as each can be considered independently and there is a constant number of d-cubes for a fixed X and ω.
Proposition 6 (Robustness γRV). For α ∈ [0, 1), γRV ≥ (1 − α)|Ψ| where, with a slight abuse of notation, Ψ denotes the set of non-empty d-cubes. For α = 1, γRV = 0.
Its proof is in Appendix A.3. Recall from Definition 2 that γRV = 1 is optimal robustness. From Proposition 6, reducing α achieves a smaller upper bound on inflation and greater robustness. However, if α is too small, then it may have an undesirable effect: RV(X;ω) < Vol(X) for some X (with similar data points) from an honest provider without replication. In this case, RV has an over-correcting effect: RV is designed to avoid exploitation of Vol() due to replication but mistakenly leads to a decrease in the value of an honest dataset. Therefore, α should be set to achieve a certain upper bound on inflation but should not be unnecessarily small; more details are given in Proposition 8 in Appendix A.3. In particular, setting α = 1/(βn) guarantees a constant upper bound exp(β−1) on the inflation, as proven in Lemma 5 in Appendix A.3. For instance, setting β = 10 and α = 1/(βn) guarantees RV(replicate(X, c);ω) ≤ 110%×RV(X;ω). However, it requires us to know the true n without any replication. In practice, as we can only observe the data with replication (if any) [15], we estimate n with the number |Ψ| of rows in X̃. Trading off diversity representation for replication robustness via ω. A smaller ω means that the d-cubes are more refined and RV can better represent the original data instead of crudely grouping many data points together and representing them via a statistic. On the other hand, a larger ω means a less refined diversity representation but greater replication robustness. In the extreme case, a sufficiently large ω results in grouping all data points together and representing them all using a single statistic, hence foregoing the diversity in data. So, a practitioner should determine the trade-off between diversity representation vs. replication robustness based on the requirements of the real-world use case. The following result (see proof in Appendix A.3) formalizes both extremes of the trade-off:
Proposition 7 (Reduction to Vol() vs. Optimal Robustness). Set ω to be s.t. each d-cube only contains completely identical data points, and
1. set ρi to some constant KX̃,i for i ∈ Ψ based on a recursive application of Lemma 1. Then, RV(·;ω) = Vol(); 2. set α = 0. So, ρi = 1(φi 6= 0) and name this formulation RV1(·;ω). Then, γRV1 = 1.
RV1(·;ω) can be seen as reducing all potential replications to one data point. It achieves robustness but loses the density information of each d-cube due to the indicator function. Specifically, the true distribution may have different densities at different d-cubes, which is reflected via φi’s. But, this information is completely lost in RV1(·;ω). In contrast, Vol() represents all the data indiscriminately, hence sacrificing robustness. Furthermore, while we restrict our consideration of replication to direct copying, it is natural to additionally consider a noisy replication (i.e., adding small random perturbations to copies [15]). Intuitively, RV1(·;ω) is not robust to noisy replication as the replicated data are perturbed. Our preliminary empirical study in Appendices B.2 and B.3 shows that RV is robust to noisy replication if the noise magnitude is small relative to ω. So, a future work is to devise a way to optimize the trade-off between diversity representation and replication robustness via ω. In our work here, we empirically find ω = 0.1 suitable for the case of standardized input features.
In using standardized input features, we implicitly assume that the input features follow a normal distribution. This makes the data further away from the mean (i.e., statistically rarer) more valuable in learning [11]. We also observe this in Sec. 5.2 where data closer to the mean are valued to be smaller across all baselines and our method. Our work here excludes considerations of outliers as they are not truly representative of the true data distribution.

heading: 5 Experiments and Discussion
text: In this section, we will first verify our claim in Sec. 3 that a larger volume leads to a better learning performance and reveal some interesting practical perspectives in Sec. 5.1. Then, in Sec. 5.2, we will show that RV produces results consistent with existing baseline methods and also demonstrate the limitations of these baselines. In particular, RV is model- and task-agnostic while another baseline with an explicit dependence on the validation set is shown to have some deviation in data valuation as the validation set changes. Lastly, in Sec. 5.3, we will verify our robustness guarantee by analyzing its asymptotic behavior under replication. Importantly, our empirical study has gone beyond the OLS framework used for the theoretical analysis in Sec. 3 as our method can be flexibly adapted to handle various neural network architectures on different machine learning tasks including both image classification and natural language processing. All experiments have been run on a server with Intel(R) Xeon(R)@ 2.70GHz processor and 256GB RAM. Our code is publicly available at: https://github.com/ZhaoxuanWu/VolumeBased-DataValuation.

heading: 5.1 Effect of Robust Volume (RV) on Learning Performance
text: In this subsection, we use RV and volume interchangeably as replication is not considered here and Proposition 5 guarantees that RV preserves the original volume. We consider the setting of sequentially adding/removing the dataset with highest/lowest RV to analyze the effect of RV on the learning performance [14]. We include random selection as a baseline. We simulate 8 data providers to make the results more generalizable. In this experiment, we use two real-world datasets: credit card fraud detection [2] (i.e., transaction amount prediction) and Uber & Lyft [5] (i.e., carpool ride price prediction) which are pre-processed to contain 8 and 12 standardized input features, respectively. Fig. 2 shows the results. Additional results on two other real-world datasets are in Appendix B.4.
It can be observed that adding (resp., removing) a dataset with a larger RV leads to a smaller (resp., larger) train loss, thus verifying Proposition 2 that a larger volume leads to a more accurate pseudoinverse and smaller train loss in terms of mean squared error. This observation is also consistent with the results on the test loss, albeit with larger standard errors. This confirms (1) that in a higher dimensional input feature space, a larger volume does not immediately guarantee a smaller test loss.
Interesting practical perspectives. The results on adding datasets provide justification for a data buyer with a limited budget to spend on datasets with larger RVs first to achieve the best learning performance, thereby resonating with the active learning paradigm [29]. On the other hand, the results on removing datasets sheds light on the following question: If training on all collected datasets is too costly due to memory or time constraints, then which dataset should be removed first without compromising the learning performance much (i.e., the dataset with smallest RV)?

heading: 5.2 Empirical Comparison of Robust Volume (RV) Shapley Value with Baselines
text: We will demonstrate that RV without validation gives results consistent with existing baseline methods which may require validation. Then, we will empirically show the limitations of these baselines.
To design principled, fair payments to the data providers, we use (robust) volume as the characteristic function in the commonly used Shapley value to measure the expected marginal contributions of their datasets [14, 18, 35]. Our robust volume Shapley value (RVSV) is defined as follows [33]:
RVSVm := (1/M !) ∑ C⊆M\{Sm}[|C|!× (M − |C| − 1)!]× [RV(XC∪{Sm};ω)−RV(XC ;ω)] (3)
whereM := {S1, . . . , SM} denotes a set of M data providers/datasets and XC denotes a data matrix constructed from concatenating the data matrix XSm′ of every data provider Sm′ ∈ C ⊆ M. Our volume Shapley value (VSV) is computed by replacing RV(·;ω) in (3) with Vol(). We compare VSV and RVSV with the following baselines: validation loss leave-one-out (LOO) value [21, 27], validation loss Shapley value (VLSV) [14, 18], and information gain Shapley value (IGSV) [35]. We consider the contributions of M = 3 data providers/matrices/datasets XS1 , XS2 , and XS3 [35]. The input features are standardized and we set ω = 0.1. LOO and VLSV use MSE on a validation set.
Synthetic data from baseline distributions. We first consider simpler experimental settings on synthetic data drawn from the 6D Hartmann function [24] defined over [0, 1]6 with four baseline data distributions for XS1 , XS2 , and XS3 : (A) independent and identical distribution (i.i.d.) where XS1 , XS2 , and XS3 contain 200 i.i.d. samples each; (B) ascending dataset size where XS1 , XS2 , and XS3 contain 20, 50, and 200 i.i.d. samples, respectively; (C) disjoint input domains where XS1 , XS2 , and XS3 are sampled from the input domains of [0, 1/3]
6, [1/3, 2/3]6, and [2/3, 1]6, respectively; and (D) supersets XS1 ⊂ XS2 ⊂ XS3 with the respective sizes 200, 400, and 600 where XS2 (resp., XS3 ) has 200 i.i.d. data samples in addition to XS1 (resp., XS2 ).
The results in Fig. 3 show that both VSV and RVSV are generally consistent with IGSV. For (B) ascending dataset size, VSV, RVSV, and IGSV increase from XS1 to XS3 , while VLSV surprisingly values the contributions of XS1 , XS2 , and XS3 to be nearly equal; the latter may be due to VLSV’s sensitivity to the definition of the value ν(∅) of an empty dataset/matrix ∅ when calculating the Shapley value. Fig. 4 illustrates that for i.i.d., VLSV is sensitive to the definition of ν(∅): For example, setting ν(∅) to 0 [18], 1.06 (by initializing parameters to zeros), and 8.75 (by initializing parameters randomly using N (0, 1) [14]) yield different VLSVs of 0.346, 0.183, and 0.330 for XS1 , respectively. These conflicting choices of ν(∅) add to the difficulties of applying VLSV in practice. Interestingly, under (C) disjoint input domains, all methods unanimously value the contribution of XS2 to be the lowest despite their input domains to be of the same size, which is due to the standardization of the input features and so offers the following interpretation: The data in the “center” is the most common if we assume the true data distribution follows a normal one. Therefore, the most common data are valued less while the statistically “rarer” data at the two tails of the distribution are valued more. Additional experimental results with this distribution are reported in Appendix B.5. It is counter-intuitive to see that for i.i.d., LOO values the contribution of XS1 to be 0, which may be due to instability from the calculation of their contributions [8].
Real-world datasets with different preferences of validation sets. We use two real-world datasets: UK used car dataset [1] (i.e., car price prediction) and credit card fraud detection dataset [2] (i.e., transaction amount prediction) where there are different preferences of validation sets [35]. For instance, car dealers for different manufacturers such as Audi, Ford, and Toyota may have different preferences over data. So, we construct two different validation sets comprising cars from different manufacturers. Similarly, different financial institutions may differ in their interests of the transaction amounts. For example, smaller banks typically manage and focus on smaller transaction amounts, so we construct two different validation sets comprising large (i.e., > $1000) vs. small transaction amounts. The results in Fig. 5 show that the effect of different preferences of validation sets on LOO is pronounced, as expected. The effect on VLSV is less due to the averaging of marginal contributions. On the other hand, there is no effect on IGSV, VSV, and RVSV as they do not require a validation set.

heading: 5.3 Replication Robustness
text: We first perform a simpler experiment to demonstrate the effect of replication and then perform more extensive experiments under more complex settings to show the asymptotic behavior of RVSV and existing baseline methods under replication.
Contributions of XS1 , XS2 , and XS3 under i.i.d. setting. We perform this experiment on the Trip Advisor hotel reviews dataset [4] (i.e., numerical rating prediction) which contains text reviews data. We utilize the GloVe [31] word embeddings and a bidirectional long short-term memory model with a fully-connected layer of 8 hidden units. Regression is performed over the 8-dimensional latent features from this model. Data matrices XS1 , XS2 , and XS3 follow an i.i.d. partition of the processed data and subsequently, XS2 and XS3 are replicated for 2 and 10 times, respectively. The results in Fig. 6 show noticeable increases in the contribution of XS3 for IGSV and VSV, which implies that they are not replication robust. On the other hand, both VLSV and RVSV appear robust.
Contributions of XS1 , XS2 , and XS3 under non-i.i.d. settings. As our replication robustness includes supc (Definition 2), we investigate large replication factors c of up to 100. Since the previous experiment shows that VLSV is robust, we use it as the baseline for comparison. We additionally consider two non-i.i.d. data distributions extended from the previous setting: supersets and disjoint input domains for 4 real-world datasets: California housing price prediction (CaliH) [20], Kings county housing sales prediction (KingH) [3], US census income prediction (USCensus) [6], and age estimation from facial images (FaceA) [41]. We use 60% of data to construct XS1 , XS2 , and XS3 and the remaining 40% as the validation set for LOO and VLSV. For i.i.d. and supersets, we set XS2 = XS1 s.t. XS2 simulates an honest data provider and we examine the effect of replicating XS1 . For supersets, we vary the proportion of data from XS1 that is contained in XS3 : If the ratio is 0.1, then XS3 contains 10% data from XS1 ; if the ratio is 1, then XS1 ⊂ XS3 . For disjoint input domains, we vary how disjoint they are for XS1 , XS2 , and XS3 via a ratio: 0 (resp., 1) means that XS1 , XS2 , and XS3 have completely disjoint (resp., overlapped) input domains. In other words, with ratio 0, they do not contain any similar data, while with ratio 1, they may contain some similar data. Fig. 7 shows results for two datasets with i.i.d. data distribution. For CaliH, we use the latent features from the last layer of a neural network with 2 fully connected layers of 64 and 10 hidden units and
the rectified linear unit (ReLU) as the activation function. Additional details on data distributions, datasets, and models are in Appendix B.6.
Next, we compare the similarity of RVSV and baseline methods to VLSV using similarity measures such as the Pearson correlation coefficient (rp) [18], cosine similarity (cos), and the reciprocal of the l2 norm of the difference [36]. For RVSV, we set ω = 0.05 and 0.1, which are respectively denoted by RVSV-005 and RVSV-01. Table 1 shows results averaged over varying replication factors c for CaliH; the other results are reported in Appendix B.6. VSV and IGSV are not robust and may be exploited as both increase relatively quickly with replication for c < 20 (Fig. 7). Furthermore, our additional experiments on varying hyperparameter choices (Appendix B.7) show that IGSV is sensitive to the choice of hyperparameter whereas RVSV is consistent, even with varying ω. From Fig. 7, RVSV is replication robust. RVSV can also achieve a high degree of similarity to VLSV without requiring validation, as seen in Table 1.

heading: 6 Related Work
text: Data valuation methods assign a larger value to data that leads to a better learning performance [14, 18, 35, 40]. Existing methods such as leave-one-out approaches [18], the Shapley value-based methods [14, 17], and a reinforcement learning framework [40] require validation. Due to the tight coupling between valuation and validation, these methods may face practical limitations arising from using a validation set (Sec. 1). The work of [35] has proposed an information-theoretic approach to valuing data based on the information gain (IG) on the model parameters to avoid the need for validation. However, it has not proven that a larger IG (value) leads to a better learning performance. Our method has this desirable theoretical property without needing validation (Sec. 3). While existing methods demonstrate some effectiveness against replication using carefully selected validation sets [14, 18], our method achieves such a guarantee without needing validation. The work of [15] has considered replication from a different perspective and is thus not directly comparable to our method.

heading: 7 Conclusion and Future Work
text: This paper describes a model- and task-agnostic replication robust data valuation method that requires no validation. In particular, we value data based on its inherent diversity formalized as the volume of the data matrix because we have shown in Sec. 3 that a larger volume entails a better learning performance. We have identified that volume is not robust to replication, so we design a data valuation method based on the novel robust volume (RV) measure with a theoretical guarantee on replication robustness (Sec. 4). In our experiments (Sec. 5), we have used RV as a characteristic function in the Shapley value and empirical comparison with existing baseline methods verifies its effectiveness in data valuation and its robustness guarantee. Importantly, we have tested on various real-world datasets and our robust volume data valuation method can be flexibly adapted to handle machine learning models more complex than OLS (i.e., various neural networks) to demonstrate its practical applicability. Current works on data pricing may build on our perspective to ease the dependence on the validation set. For future work, we plan to consider more sophisticated replication techniques and investigate how to optimize the trade-off between diversity representation vs. replication robustness.
Acknowledgments and Disclosure of Funding
This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (Award No: AISG2-RP-2020-018). Any opinions, findings and conclusions or recom-
mendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore. Xinyi Xu is supported by the Institute for Infocomm Research of Agency for Science, Technology and Research (A*STAR). The authors thank Fusheng Liu for many interesting discussions.

Review summaries:
This paper intends to design a method to evaluate the value of a dataset. Such methods have been previously developed by calculating the Shapley value of the dataset based on its effect on model accuracy. The authors argued that since the model accuracy depends on a validation data set, selection of the validation dataset highly affects the Shapley value of each party's dataset, and hence will be a source of disagreement. To overcome this issue the authors set the value of a dataset based on the determinant (volume) of the left Gram matrix of its input features. The value of duplicated data is removed by constructing a compressed version of the dataset that preserves its diversity. The authors refer to this as robustness, since the values are robust to duplications. The authors provide some propositions connecting volume with bias and MSE. This has been validated experimentally as well.  

The paper proposes a measure of datasets’ values using the volume of the feature matrix (defined to be the determinant of its left Gram), which captures the diversity in features. They show the effectiveness of this measure both theoretically and empirically. The paper proves that for regression problems,  a larger volume usually leads to a smaller bias and a lower mean squared error. They also verify this claim using randomly generated datasets. They also proposed a replication robust measure by compressing similar data. Finally, they use experiments on both real-world datasets and synthetic data to verify their claims and demonstrate that their measures without validation give results consistent with other methods which may require validation.