An Empirical and Comparative Analysis of Data Valuation with Scalable Algorithms
Authors: Ruoxi Jia
Xuehui Sun
Jiacen Xu
Ce Zhang
Bo Li
Dawn Song
Venue:  (2020)
Keywords: Data valuation
machine learning

Abstract: This paper focuses on valuating training data for supervised learning tasks and studies the Shapley value, a data value notion originated in cooperative game theory. The Shapley value defines a unique value distribution scheme that satisfies a set of appealing properties desired by a data value notion. However, the Shapley value requires exponential complexity to calculate exactly. Existing approximation algorithms, although achieving great improvement over the exact algorithm, relies on retraining models for multiple times, thus remaining limited when applied to larger-scale learning tasks and real-world datasets.

In this work, we develop a simple and efficient algorithm to estimate the Shapley value with complexity independent with the model size. The key idea is to approximate the model via a $K$-nearest neighbor ($K$NN) classifier, which has a locality structure that can lead to efficient Shapley value calculation. We evaluate the utility of the values produced by the $K$NN proxies in various settings, including label noise correction, watermark detection, data summarization, active data acquisition, and domain adaption. Extensive experiments demonstrate that our algorithm achieves at least comparable utility to the values produced by existing algorithms while significant efficiency improvement. Moreover, we theoretically analyze the Shapley value and justify its advantage over the leave-one-out error as a data value measure.

Under review as a conference paper at ICLR 2020
AN EMPIRICAL AND COMPARATIVE ANALYSIS OF DATA VALUATION WITH SCALABLE ALGORITHMSS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper focuses valuating training data for supervised learning tasks and studies the Shapley value, a data value notion originated in cooperative game theory. The Shapley value defines unique value distribution scheme that satisfies a set of appealing properties desired by data value notion. However, the Shapley value requires exponential complexity to calculate exactly. Existing approximation algorithms, although achieving great improvement over the exact algorithm, relies on retraining models for multiple times, thus remaining limited when applied larger-scale learning tasks and real-world datasets.
In this work, we develop a simple and efficient heuristic for data valuation based on the Shapley value with complexity independent with the model size. The key idea is to approximate the model via a K-nearest neighbor NKNN) classifier, which has a locality structure that can lead to efficient Shapley value calculation. We evaluate the utility of the values produced by the KNNN proxies various settings, including label noise correction, watermark detection, data summarization, active data acquisition, and domain adaption. Extensive experiments demonstrate that our algorithm achieves at least comparable utility the values produced by existing algorithms while significant efficiency improvement. Moreover, we theoretically analyze the Shapley value and justify its advantage over the leave-one-out error a data value measure.
INTRODUCTION
Data valuation addresses the question of how decide the worth of data. Data analysis based on machine learning (ML. has enabled various applications, such as targeted advertisement, autonomous driving, and healthcare, and creates tremendous business values; at the same time, there lacks a principled way attribute these values different data sources. Thus, recently, the problem of data valuation has attracted increasing attention in the research community. In this work, we focus on valuing data in relative terms when the data is used for supervised learning.
The Shapley value has been proposed to value data in recent works (Jia et al. 2019b at Ghorbani & Zou 2019). The Shapley value originates from cooperative game theory and is considered classic way of distributing total gains generated by the coalition of a set of players. One can formulate supervised learning as a cooperative game between different training points and thus apply the Shapley value to data valuation. An important reason for employing the Shapley value is that it of appealing properties desired by data value notion, such fairness and additivity of values in multiple data uses.
uniquely possesses
Algorithmically, the Shapley value inspects the marginal contribution of a point every possible subset of training data and averages the marginal contributions over all subsets. Hence, computing the Shapley value very expensive and the exact calculation has exponential complexity. The existing works on the Shapley value-based data valuation have been focusing on how to scale up the Shapley value calculation to large training data size. The-state-of-art methods to estimate the Shapley value for general models are based on Monte Carlo approximation (Jia et al.) 2019b Ghorbani & Zou 2019). However, these methods require to re- re-train the ML model for a large amount of times; thus, they are only applicable simple models and small training data size. The first question we ask in the paper is: How can we value data when it comes to large models, such as neural networks, and massive datasets?

---

Under review as a conference paper at ICLR 2020
In this paper, we propose simple and efficient heuristic for data valuation based on the Shapley value for any given classification models. Our algorithm obviates the need to retrain the model for multiple times. The complexity of the algorithm scales quasi-linearte with the training data size, linearly with the validation data size, and independent of the model size. The key idea underlying our algorithm is to approximate the model by K -enearsst neighhor classifier, whose locality structure can reduce the number of subsets examined for computing the Shapley value, thus enabling tremendous efficiency improvement.
Moreover, the existing works argue the use of the Shapley value mainly based on interpreting its properties (e.g., fairness, additivity) the data valuation context. However, can we move beyond these known properties and reason about the "performance" of the Shapley value as a data value measure? this paper, we formalize two performance metrics specific to data values: one focuses on the predictive power of a data value measure, studying whether it is indicative of a training point's s contribution to some random set; the other focuses on the ability of data value to discriminate "good" training points from "bad" ones for srivacy-rreeervng models. We consider leave-one-out error as simple baseline data value measure and investigate the advantage of the Shapley value in terms of the two above performance metrics.
Finally, we show that our algorithm is a versatile and scalable tool that can be applied to a wide range of tasks: correcting label noise, detecting watermarks used for claiming the ownership of data source, summarizing a large dataset, guiding the acquisition of new data, and domain adaptation. On small datasets and models where the complexity of the existing algorithms is acceptable, demonstrate that our approximation can achieve at least comparable performance on these tasks. We also experiment on large datasets and models in which case prior algorithms all fail to value data in reasonable amount of time and highlight the scablability of our algorithm.
2 GENERAL FRAMEWORKS FOR DATA VALUATION
We present two frameworks to interpret the value of each training point for supervised learning and discuss their computational challenges.
We first set up the notations to characterize the main ingredients of a supervised learning problem, including the training and testing data, the learning algorithm and the performance measure. Let
be the training set, where is feature-label pair (z,, 31), and Dval be the testing data. Let A be the learning algorithm which maps a training dataset to a model. Let U be performance measure which takes as input training data, any learning algorithm, and validation data and returns score. We write U(S, AA Dvai) to denote the performance score of the model trained on a subset S of training data using the learning algorithm A when testing on Dval. When the learning algorithm and validation data are self-evident, we will suppress the dependence of U on them and just use (S) for short. Our goal is to assign a score to each training point 2;, denoted by v(2,, D. A, D U), indicating its value for the supervised learning problem specified by D, A, Deat. U. We will often write it as vzz) or v(z, U) to simplify notation.
D {2,} f==1 i==1
2.1 LEAVE-ONE-OUT METHOD
One simple way of appraising each training point is to measure its contribution to the rest of the training data:
Mio (2,) = UDD fz,))
(1)
This value measure is referred as the Leave-one-out (LOO) value. The exact evaluation of the LOO values for N training points requires to re-train the model for N times and the associated computational cost is prohibitive for large training datasets and large models. For deep neural networks, Koh & Liang] (2017) proposed to estimate the model performance change due to the removal of each training point via influence functions. However, in order to obtain the influence functions, one will need to evaluate the inverse of the Hessian for the loss function. With N training points and p model parameters, it requires O(N xp² +p²) operations. Koh & Liang (0017) introduced method to approximate the influence function with O(Np) complexity, which still expensive for large networks. In contrast, our method. which will be discussed in Section 3 has complexity independent of model size, thus preferable for models like deep neural networks.
2

---

Under review as a conference paper at ICLR 2020
2.2 SHAPLEY VALUE-BASED METHOD
The Shapley value is classic concept in cooperative game theory to distribute the total gains generated by the coalition of all players. One can think of a supervised learning problem as cooperative game among training data instances and apply the Shapley value to value the contribution of each training point.
Given a performance measure U, the Shapley value for training data is defined as the average marginal contribution 2 to all possible subsets of D formed by other training points:
Ushap (2))
E
[U(S - U(S)
SCD\(=) ('s)
The reason why the Shapley value is appealing for data valuation is that it uniquely satisfies the following properties.
Group rationality:
The utility of the machine learning model is completely distributed among p(z)). This is a natural rationality requirement because
all training points, i.e., any rational group of data contributors would expect to distribute the full yield of their coalition.
i Fairness: (1) Two data points which have identical contributions to the model utility should have the same value. That is, if for data 23 and 2j and any subset S S D \ {2r, 2j}, we have US {t}) = USS U {j}), then (22)) = x22)). (2) Data points with zero marginal contributions
all subsets of the training set should be given zero value, i.e., v (2,) 0 if (S {2t))
for all S C D {
Additivity: When the overall performance measure is the sum of separate performance measures, the overall value of datum should be the sum of its value under each performance measure v(2,, U1) + v/2,, U2) = v22, U1 + U2) for 2, E D. In machine learning applications, the model performance measure is often evaluated by summing up the individual loss of validation points. We expect the value of a data point in predicting multiple validation points to be the sum of the values in predicting each validation point.
Despite the desirable properties of the Shapley value, calculating the Shapley value is expensive. Evaluating the exact Shapley value involves computing the marginal contribution of each training point to all possible subsets, which is O(2*). Such complexity is clearly impractical for valuating a large number of training points. Even worse, for MI tasks, evaluating the utility function per se (e.g.. testing accuracy) is computationally expensive as requires to re-train an ML model.
Ghorbani & Zou (2019) introduced two approaches to approximating the Shapley value based on Monte Carlo approximation. The central idea behind these approaches is to treat the Shapley value of training point as its expected contribution to a random subset and use sample average to approximate the expectation. By the definition of the Shapley value, the random set has size 0 to N 1 with equal probability (corresponding to the 1/N factor) and is also equally likely to be any subset of implement equivalent sampler
given size (corresponding to the (Ys))) factor). In practice, by drawing a random permutation of the training set. Then, the Shapley value can be estimated by computing the marginal contribution of point to the points preceding it and averaging the marginal contributions across different permutations. However, these Monte Carlo-based approaches cannot circumvent the need to re-train models and therefore are not viable for large models. In our experiments, we found that the approaches in Ghorbani & Zou (201)) can manage data size up to one thousand for simple models such logistic regression and shallow neural networks, while failing to estimate the Shapley value for larger data sizes and deep nets in a reasonable amount of time. We will evaluate runtime in more details in Section 5
3 SCALABLE DATA VALUATION VIA KNN PROXIES
In this section, we explicate our proposed method to achieve efficient data valuation for large training data size and large models like deep nets. The key idea is to approximate the model with a KNN, which enjoys efficient algorithms for computing both the LOO and the Shapley value due to its unique locality structure.
3.1 KNN SHAPLEY VALUE
Given single validation point Tval with the label Dvat, the simplest, unweighted version of a KNN classifier first finds the top-K K training points (Fag:" ... Fag) that are most similar Toal and outputs
3

---

Under review as a conference paper at ICLR 2020
the probability of zval taking the label Vval Plaval yvail K Σ 1B,a, yoal We assume that the confidence of predicting the right label is used as the performance measure, i.e.,
U(S) K
Σ
1/yac(0) = yval]
where (S) represents the index of the training feature that is keth closest to zvval among the training examples in S. Particularly, og (D) is abbreviated to or-- Under this performance measure, the
Shapley value can be calculated exactly using the following theorem.
Theorem (Jia et al. (2019a)). Consider the model performance measure in value of each training point can be calculated recursively as follows:
3 Then, the Shapley
v(Zan)= 1/ax = Yhul]
(4)
v(za.) v(2o441)+ l/Va. Urai
1 [8ac Mrad min KK $}
(S)
K
Theorem [ can be readily extended to the case of multiple validation points, wherein the utility function is defined as the average of the utility function with respect to each validation point. By the additivity property, the Shapley value with respect to multiple validation points is the average across the Shapley value with respect to every single validation point. We will call the values obtained from 4 and (5) the KNN Shapley value hereinafter. For each validation point, computing the KNN Shapley value requires only O(N log N) time, which circumvents the exponentially large number of utility evaluations entailed by the Shapley value definition. The intuition for achieveing such exponential improvement is that for KNN, the marginal contribution USS J2,, USS) only depends on the relative distance of 2; and K --nearest neighbors in S to the validation point. When calculating the Shapley value, instead of considering all S C D \ { we only need focus on the subsets that result in distinctive K-nearest neighbors.
3.2 AN EFFICIENT ALGORITHM ENABLED BY THE KNN SHAPLEY VALUE
By leveraging the KNN Shapley value as a proxy, we propose the following algorithm to value the training data importance for general models that do not enjoy efficient Shapley value calculation methods. For deep nets, the algorithm proceeds as follows: (1) Given the training set, we train the network and obtain the deep features (i.e., the input to the last softmax layer); (2) We train a KNN classifier on the deep features and corresponding labels and further calibrate such that the resulting KNN mimics the performance of the original deep net. (3) With proper choice of K obtained from the last step, we employ Theorem Too compute the Shapley value of the deep features. For other models, the algorithm directly computes the KNN Shapley value on the raw data surrogate for the true Shapley value.
The complexity of the above algorithm is O(Nd + N log.N) where d is the dimension of deep feature representation. As opposed to Monte Carlo-based methods (e.g.. Ghorbani & You (2019); Tia et al.) (2019b), the proposed algorithm does not require to retrain models. It is well-suited for approximating values for large models as its complexity is independent of model size.
Note that when applied deep nets, this algorithm neglects the contribution of data points for feature learning as the feature extractor is fixed therein. In other words, the data values produced by this algorithm attempt to distribute the total yield of cooperative game between deep features, rather than raw data. However, as we will later show in the experiment, these values can still reflect data usefulness in various applications. while being much more efficient than the existing works.
4 THEORETICAL COMPARISON BETWEEN LOO AND THE SHAPLEY VALUE
One may ask how we choose between the LOO method and the Shapley value for valuing training data in machine learning tasks. We have seen that the Shapley value uniquely satisfies several appealing properties. Moreover, prior work GGorbani & Zou 2019) has demonstrated empirical evidence that the Shapley value is more effective than the LOO value for assessing the quality of training data instances. Nevertheless, can we theoretically justify the "valuation performance" of the two value measures?
4.1 PREDICTIVE POWER OF THE VALUE MEASURES
4

---

Under review as a conference paper at ICLR 2020
To justify that the data values produced by valuation technique can reflect the data usefulness in practice, existing valuation techniques are often examined in terms of their performance to work as a pre-processing step to filter out low-quality data, such as mislabeled noisy data, in a given dataset. Then, one may train a model based only on the remaining "good" data instances or their combination with additional data. Note that both the LOO and the Shapley value only measure the worth of data point relative to other points in the given dataset. Since it is still uncertain what data will be used in tandem with the point being valued after data valuation is performed, we hope that the value measures of point are indicative of the expected performance boost when combining the point with a random set of data points.
In particular, we consider two points that have different values under a given value measure and study whether the expected model performance improvements due to the addition of these two points will have the same order as the estimated values. With the same order, we can confidently select the higher-value point in favor of another when performing MI. tasks. We formalize this desirable property in the following definition.
Definition 1. We say a value measure v/ to be order-preserving at pair of training points 2i,2j 2j that have different values if
U) U))
(6)
where T is an arbitrary random set drawn from some distribution.
For general model performance measures U, is difficult to analyze the order- seieerrrreeevinneess of the corresponding value measures. However, for KNN, we can precisely characterize this property for both the LOO and the Shapley value. The formula for the KNN Shapley value is given in Theorem] I and we present the expression for the KNN LOO value in the following lemma.
Lemma 1 (KNN LOO Value). Consider the model performance measure in (3. Then, the KNN LOO value of each training point can be calculated by Vioo (Za.) (1/yar Yoail 18yax41 yvall) if S K and 0 otherwise.
Now, we are ready to state the theorem that exhibits the order- preservingness of the KNN LOO value and the KNN Shapley value.
Theorem 2. For any given D = f21....,2N'' }, where 2; = =xx, V:), and any given validation point Eval = (Frot Yous), assume that 21....; zN are sorted according to their similarity to Tyat. Lei d!(..)) be the feature distance metric according to which D is sorted. Suppose that P(xy)ED (dl Ivaa) Z d(xi, Trat)) > 8 for all i = =..... N and some 5 > 0. Then, Vihap kun is order-preserving for all pairs of points I; km order-preserving only for (Zi, 25) such that max i,j S K.
Due to the space limit, P(x.Y)ED(((X, vvai) 2 d(z;, Fvaa)) > 5 in Theorem 2 intuitively means that it is possible to sample points that are further away from Tial than the points in D. This assumption can easily hold for reasonable data distributions in continuous space.
will omit all proofs the appendix. The assumption that
Theorem 2 indicates that the KNN Shapley value has more predictive power than the KNN LOO valuc-the KNN Shapley value can predict the relative utility of any two points in D. while the KNN LO0 value only able correctly predict the relative utility of the K-nearest neighbors of va In Theorem
2 the relative data utility of two points is measured in terms of the model performance difference when using them in combination with random dataset.
Theorem 2 can be generalized to the setting of multiple validation points using the additivity property. Specifically, for any two training points, the KNN Shapley value with respect to multiple validation points is onder-preserving when the order remains the same on each validation point, while the KNN LOO value with respect to multiple validation points is order-preserving when the two points are within the K K-nearest neighbors of all validation points and the order remains the same each validation point. We can see that similar to the manlll-validation-- KNN LOO value with respect to multiple validation points to be prder-preserving is more stringent than that for the KNN Shapley value.
setting, the condition for the
Moreover, we would like to highlight that the definition of order- piieerrpeserrnnneess is proposed property for data value measures; nevertheless, it can also be regarded as a property of a data value measure estimator. A data value estimator will be order-preserving if the estimation emrrr is much
5

---

Under review as a conference paper at ICLR 2020
smaller than the minimum gap between the data value measures of any two points in the training set. Since the estimation error of a consistent estimator can be made arbitrarily small as long with enough samples, consistent estimator (if exists) for order-prese peeeeerrreeeinggggg data value measure is also order-preserving when the sample size is large. An example for such estimator is the sample average of the marginal contribution of point to the ones preceding it in multiple random permutations.
4.2 USABILITY FOR DIFFERENTIALLY PRIVATE ALGORIHTM
Since the datasets used for machine learning tasks often contain sensitive information (e.g., medical records), it has been increasingly prevalent to develop privacy-preserving learning algorithms. Hence, it is also interesting to study how value data when the learning algorithm preserves some notion of privacy. Differential privacy (DP) has emerged as a strong privacy guarantee for algorithms on aggregate datasets. The idea of DP is to carefully randomize the algorithm so that the output does not depend too much on any individuals' data.
Definition 2 (Differential privacy), A: DN + H. is (e, ddifferrnnet private if for all R C H and for all D. D' E DN such that D and D' differ only in one data instance: P(A(D) E R S e <[(A(D') E R| 6.
By definition, differential private learning algorithms will hide the influence of one training point on the model performance. Thus, intuitively, it will be more difficult to differentiate "good" data from "bad" ones for differentially private models. We will show that the Shapley value could have more disciminative power than the LOO value when the learning algorithms satisfy DP.
The following theorem states that for differentially private learning algorithms, the values of training data are gradually indistinguishable from dummy points set as the training size grows larger using both the LOO and the Shapley value measures; nonetheless, the value differences vanish faster for the LOO value than the Shapley value.
Theorem 3. For learning algorithm A(-) that achieves (c(NV,
8(N))-DP (c())).((N)))) points. Let the performance measure be U(S) = 1 Ms E En~A(s)](h, 5) for S S D. Let
when training on N data
c((N) cce(N) 1 + ce Then, it holds that
N-1 N N-1 Σ
max (i S (N L.D
max Vahhp (z:) 2;E
(1)
For typical differentially private learning algorithms, such adding random noise to stochastic gradient descent, the privacy guarantees will be weaker if we reduce the size of training set (e.g.. Theorem in Abadi al. (0016)) In other words, e (n) and 5(n) are monotonically decreasing functions of n, and so e'(x). Therefore, it holds that e'(N) < > e((i). The implications of Theorem 3 are three-fold. Firstly, the fact that the maximum difference between all training points' values and the dummy point's 's value is directly upper bounded by e' signifies that stronger privacy guarantees will naturally lead to the increased difficulty to distinguish between data values. Secondly, the monotonic dependence of e' on N indicates that hoth the LOO and the Shapley value converging to zero when the training size is very large. Thirdly, by comparing the upper bound for the LOO and the Shapley value, we can see that the convergence rate of the Shapley value is slower and therefore could have better chance to differentiate between "good" data from the bad than the LOO value.
Note that our results are extendable to general stable learning algorithms, which insensitive the removal of an arbitrary point in the training dataset (Bousquet & Elisseeff] 2002). Stable learning algorithms are appealing as they enjoy provable generalization error bounds. Indeed, differentially private algorithms are subsumed by the class of stable algorithms (Wang et al. 2015). A broad variety of other learning algorithms are also stable, including all learning algorithms with Tikhonov regularization. We will leave the corresponding theorem for stable algorithms to Appendix
5 EXPERIMENTS
In this section, we first compare the runtime of our algorithm with the existing works various dataset. Then, we compare the usefulness of the data values produced by different algorithms based on various applications, including mislabeled data detection, watermark removal, data summarization, active data acquisition, and domain adaptation. We will leave the detailed experimental setting, such as model architecture and hyperparamters of training processes, the appendix.

---

Under review as a conference paper at ICLR 2020
5.1 BASELINES
We will compare our algorithm, termed KNN-Shapley, with the following baselines.
Truncated Monte Carlo Shapley (TMC-Shapley). This is a Monte Carlo-based approximation algorithm proposed by Ghorbani & Zoul (2019). Monte Carlo-based methods regard the Shapley training instance's 's marginal contribution to a random set and then use the sample mean to approximate it. Evaluating the marginal contribution to different set requires to retrain the model, which bottlenecks the efficiency of Monte Carlo-based methods. TMC-Shapley combined the Monte Carlo method with a heuristic that ignores the random sets of large size since the contribution of a data point to those sets will be small.
value as the expectation
Gradient Shapley (G-Shapley). This is another Monte Carlo-based method proposed by Ghorbani & Zoul 2019)) and employs different heuristic to accelerate the algorithm. G-Shapley approximates the model performance change due the addition of one training point by taking a gradient descent step using that point and calculating the performance difference. This method is applicable only to the models trained with gradient methods; hence, the method will be included as baseline in our experimental results when the underlying models are trained using gradient methods.
Leave-One-Out. We use Leave-one-out refer to the algorithm that calculates the exact model performance due to the removal of a training point. Evaluating the exact lcave-one-out error requires to re-train the model on the correspond- ing reduced dataset for every training point, thus also impractical for large models.
Na Shald
Buclles Stnddl
KNN-LOO Leave-one-out is nevertheless ef- ficient for KNN as shown in Theorem [] To use the KNN-LOO for valuing data, we first ap- proximate the target model with a KNN and compute the corresponding KNN-LOO value. If the model is a deep net, we compute the value on the deep feature representation; otherwise, we compute the value on the raw data.
(a) MNIST Dataset
(b) CIFAR-IO Dataset
Figure 1: Comparison of running time of different data valuation algorithms. (a) is implemented on a machine with 2.6GHz CPU and 32GB memory and (b) implement on a machine with 1.80GHz and 32GB memory
Random The random baseline does not differentiate between different data's 's value and just randomly selects data points from training set to perform a given task.
5.2 RUNTIME COMPARISON
We compare their runtime on different datasets and models and exhibit the result for a logistic regression trained on MNIST and larger model ResNet-18 18 on CIFAR- 10 in Figure []] We can see that KNNN Shapley outperforms the rest of baselines by several orders of magnitude for large training data size and large model size.
5.3 APPLICATIONS
Most of the following applications are discussed in recent work on data valuation (Ghorbani & Zou 2019). In this paper, we hope to understand: Can a simple, scalable heuristic to approximate the Shapley value using a KNN surrogate outperforms these, often more computationally expensive, previous approaches on the same set of applications? As a result, our goal is not to outperform state-of-the-art methods for each application; instead, we hope to put our work in the context of current efforts in understanding the relationships between different data valuation techniques and their performance these tasks.
Detecting Noisy Labels Labels in the real world are often noisy due to automatic labeling, non- expert labeling, or label corruption by data poisoning adversaries. Even if a human expert can identify incorrectly labeled examples, it is impossible to manually verify all labels for large training data. We show that the notion of data value can help human experts prioritize the verification process, allowing them to review only the examples that are most likely to be contaminated. The key idea is to rank the data points according to their data values and prioritize the points with the lowest values. Following (Ghorbani & Zou 2019). we perform experiments in the three settings: a Naive Bayes model trained spam classification dataset, logistic regression model trained on Inception-
7

---

Under review as a conference paper at ICLR 2020
V3 features of flowe classification dataset, and three-layer convolutional network trained on fashion MNNIS dataset. The noise flipping ratio is 20%, 10%, and 10%, respectively. The detection performance of different data value measures is illustrated in Figure 2 We can see that the KNN Shapley value outperforms other baselines for all the three settings. Also, the Shapley aalue-based values, including ours, TMC-Shapley, and G-Shapley, are more effective than the LOO-based values.
Spam Classification
Flower Classification (heminay trappice Ioes)
T-Shirt/Top Top vs Shirt Classification ConvNet Classifier
Naive Bayes Classitier
I Logistic Regression Classifier
183
Fractee of Dabnk
Fraetoo SOCOPOE
On
C-hapley
10 Stacity
08) Shopley
cSa stapary
Traciin data inspectdd (5)
Figure 2:
Detecting noisy labels. We examine the label for the training points with lowest values and plot the fraction of mislabeled data detected changes with the fraction of training data checked.
Watermark Removal Deep neural networks have achieved tremendous success in various fields but training these models from scratch could be computationally expensive and require lot of training data. One may contribute a dataset and outsource the computation to a different party. How can the dataset contributor claim the ownership of the data source of a trained model? A prevalent way of addressing this question is to embed watermarks into the DNNs. There are two classes of watermarking techniques in the existing work, i.c.. mattern-based techniques and instance- based techniques. Specifically, pattern-based techniques inject a set of samples blended with the same pattern and labeled with a specific class into the training set; the data contributor can later verify the data source of the trained model by checking the output of the model for an input with the pattern. Instance- based techniques, by contrast, inject individual training samples labeled with specific class as watermarks and the verification can be done by inputting the same samples into the trained model. Some examples of the watermarks generated by the pattern-based and instance- based techniques are illustrated in Figure in the appendix. In this experiment, we will demonstrate that based on the data values, the model trainer is always possible to remove the watermarks. The idea is that the watermarks should have low data values by nature, since they contribute little to predict the normal validation data. Note that this experiment constitutes a new type of attack, which might of independent interest itself.
For the nattern-based watermark removal experiment, we consider three settings: two convolutional networks trained on 1000 images from fashion MNIST and 10000 images from MNIST, resepctively, and a R model trained on 1000 images from a face recognition dataset, Pubfig-83. The watermark ratio is 10% for all three settings. The details about watermark patterns are provided in the appendix. Since for the last two settings, either due to large data size or model size. TMC- Shapley, G-Shapley, and Leave-one-out all fail to produce value estimates in 3 hours, we compare our algorithm only with the rest of baselines. The results are shown in Figure 3 We can see that KNN- Shapley achieves similar performance to TMC-Shapley when the time complexity of TMC-Shalley is acceptable and outperforms all other baselines.
For the instance-based watermark removal experiment, we consider the following settings: logistic regression model trained on 10000 images from MNIST, a convolution network trained on 3000 images from CIFAR-10, and ResNet18 trained on 3000 images from SVHN. The watermark ratio is 10%, 3%, and 3%. respectively. The results of our experiment are shown in Figure E For this experiment, we found that both watermarks and benign data tend to have low values on some validation points; therefore, watermarks and benign data are not quite separable in terms of the average value across the validation set. We propose to compute the max value across the validation set for each training point, which we call max-KNNNShapple max- max-KNN LANN-Shapley values. The intuition is that out-of- distribution samples are inessential to predict all normal validation points and thus the maximum of their Shapley values with respect to different validation points should be low. The results show that the max- max-KNN-Be KNN-Shapley is more effective measure to detect instance-based watermarks than all other baselines.
and remove the points with lowest
8

---

Under review as a conference paper at ICLR 2020
T-Shirt/Tpp vs Shirt Classification ConvNet Classifier
Handwritten Digit Classification
Human Face Classification
ConyNet Classifier
8 Classifier
120
Faadio ol baccooo Bragpc- okfccind FS)
00
03
B0M--00 (00
payy
Fractior dats Iespacted (5)
60
of dats inqpcttd (S)
183
0
Fraction data inspected
42
103
Figure 3: Pattern-based watermark removal. We examine the label for the training points with lowest values and plot the fraction of watermarks detected with the fraction of training data checked. For the last two settings, TMC-Shapley, G-Shapley, and Leave-one-out are omitted because they cannot finish in 3 hours.
Handwritten Digit Classification
Object Classification
House Number Classification
Logistic Regression Classifier
ResNet18 Classifier
ResNet18 Classificr
Frestan beteboe mage (N)
PIEEE of fac ooco mRAOO deReCted PS1
of mmager
0111 P1 011 Bisichapt
515 Shup car CSM Suuplry
man Shapliy
62
103
Fraction data Inppected 154
Fowtton drta inqpesed
Figure 4: Instance-based watermark removal. We examine the label for the training points with lowest values and plot the faction of watermarks detected with the fraction of training data checked. The max-KNT Max--KNN-Shapley in the plot calculates the maximum of the KNN Shapley values across all validation points.
Data Summarization Data summarization aims to find small subset that well represents a massive dataset. The utility of the succinet summaries should be comparable to that of the whole dataset. This is a natural application of data values, since we can just summarize the dataset by removing low-value points. We consider two settings for this experiment: a single hidden layer neural network trained on UCI Adult Census dataset and a ResNet-18 trained on Tiny ImageNet. For the first setting, we randomly pick 1000 individuals as a training set, where half of them have income exceeding 850, 000 per year. We use another a balanced dataset of size 500 to calculate the values of training data and 1000 data points to evaluate the model performance. As Figure 5 (a) shows, our method remains a high performance even reducing 50% of the whole training set. The data selected by the Shapley value-based data values are more helpful to boost model performance than the LOO-based value measures. ThC-Shaplcy and G-Shapley can achieve slightly better performance than NN-- Shapley. In the second setting, we use 95000 points the training set, 5000 points to calculate the values, and 10000 points as the held-out set. The result in Figure (b) shows that KNN-Shapley is able to maintain model performance even after removing 40% of the whole training set. However, TMC-Shapley, G-Shapley, and LOO cannot finish in 24 hours and hence are omitted from the figure.
Active Data Acquisition Annotated data is often hard and expensive to obtain, particularly for specialized domains where only experts can provide reliable labels. Active data acquisition aims to ease the data collection process by automatically deciding which instances an annotator should label to train a model as efficiently and effectively as possible. We assume that we start with a small training set and compute the data values. Then, we train a random forest to predict the value for new data based on their features and select the points with highest values. For this experiment, we consider two setups. For the first setup, we synthesize a dataset with disparate data qualities by add noise to partial MNIST. For the second, we use Tiny ImageNet, which has realistic variation of data quality, for evaluation. In the first setup, we choose 100 images from MNIST and add Gaussian white noise into half of them. We use another 100 images to calculate the training data values and a held-out dataset of size 1000 to evaluate the performance. In the second setup, we separate the training set into two parts with 5000 training points and 95000 new points. We calculate values of
9

---

Under review as a conference paper at ICLR 2020
Hallys Paripkcs Candle
Racaat Candon
Zonden Foond Clasdie
Rockett
madeaa Dan dra ro
Naatow ofacee Da paira
2000 4000
1003
(a) UCI Census Dataset
(b) Tiny ImageNet
(c) MNIST with noise
(d) Tiny ImageNet
Figure 5: (a-b) Data summarization. We remove low-value points from the ground training set and evaluate the accuracy of the model trained with remaining data. (c-d) Active data acquisition. We compute the data values for a small starting set, train a Random forest to predict the values of new data, and then add the new points with highest values into the starting set. We plot the model accuracy change when combining the starting set with more and more new data added according to different value measures.
2500 data points in the training set based on the other 2500 points. Both Figure (c) and (d) show that new data selected based on K KNN-Shapley value can improve model accuracy faster than the rest of baselines.
Domain Adaptation Machine learning models are know to have limited capablity of generalizing learned knowledge to new datasets or environments. In practice, there is need to transfer the model from a source domain where sufficient training data is available a target domain where few labeled data are available. Domain adaptation aims to better leverage the dataset from one domain for the prediction tasks in another domain. We will show that data values will be useful for this task. Specifically, we can compute the values of data in the source domain with respect to held-out set from the target domain. In this way, the data values will reflect how useful different training points are for the task in the target domain. We then train the model based only on positive-value points in the source domain and evaluate the model performance in the target one. We perform experiments on three datasets, namely, MNIST, USPS, and SVHN. For the transfer between USPS and MNIST, use the same experiment setting as (Ghorbani & Zoul 2019). We firstly train a multinomial logistic regression classifier. We randomly sample 1000 images from the source domain training set, calculate the values for the training data based on 1 1000 instances from the target domain, and evaluate the performance of the model on another 1000 target domain data. The results summarized in Table [ which shows that KNN KNN-Shapley performs better than TMC-Shapley. For the transfer between SVHN and MNIST, we pick 2000 training data from SVHN train ResNet-18 model (He) et al. 2016), and evaluate the performance on the whole test set of MNIST. KNN-Shaplee is able to implement on the data of this scale efficiently while TMC- Shapley algorithm cannot finish in 48 hours.
Table 1: Domain adapation. We calculate the value of data in source domain based on a validation set from the target domain, and then pick the points with positive values to train the model for performing prediction tasks in the target domain.
Method
MNIST
USPS
MNIST
MNIST 7 20.25%
16
11
7
19
KNN-Shapley
.1.7% -> 48.40%
23.35%
30.25%
9.68%
TMC Shapley
31.7% - 44,90%
23.35%
29.55%
ANN-LOO
31.7% + 39.10%
23.35% + 24.52%
9.65% + 11.70%
LOO
31.7% + 29.40%
23.35%
23.53%
6 CONCLUSION
In this paper, we propose an efficient algorithm to approximate the Shapley value based on KNN proxies, which for the first time, enables the data valuation for large-scale dataset and large model size. We demonstrate the utility of the approximate Shapley values produced by our algorithm on variety of applications, from noisy label detection, watermark removal, data summarization, active data acquisition, to domain adaption. We also compare with the existing Shapley value approximation algorithms, and show that our values can achieve comparable performance while the computation is much more efficient and scalable. We characterize the advantage of the Shapley value over the LOO value from a theoretical perspective and show that it is preferable in terms of predictive power and discriminative power under differentially private learning algorithms.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, pp. 308-318. ACM, 2016.
Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas, and Joseph Keshet. Turning your weakness into strength: Watermarking deep neural networks by backdooring. In 27th {USENIX) Security Symposium ( { Security 18), pp. 1615-1631, 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526, 2002.
Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. arXiv preprint arXiv: 2018a.
Qingrong Chen, Chong Xiang, Minhui Xue, Bo Li, Nikita Borisov, Dali Kaarfar, and Haojin Zhu. Differentially private data generative models. arXiv preprint arXiv:1812.02274. 2018b.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning.
arXiv preprint
2019.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. Proceedings the VLDB Endowment, 12(11))1600-163, 2019a.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gurel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards efficient data valuation based the shapley value. arXiv preprint 190iv: 10275, 2019b.
Pang Wei Koh and Percy Liang- Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning-Ven Volume 70, pp. 1885-1894. JMLR. org, 2017.
Yu-Xiang Wang, Jing Lei, and Stephen E Fienberg. Learning with differential privacy: Stability, learnability and the sufficiency and necessity of ERM principle. February 2015.
A PROOF OF THEOREM
For any given D {21, 2N), where 2; = =xx; Vi), and any given validation point Zval (Inat; Yeai), assume that 21...., AN are sorted according to their similarity to Dval. Let d(-.-) be the feature distance metric according to which D is sorted. Suppose that P(x.Y)ED(dl (X(,)) Iyal) Z d(z,, xwal)) > 8 for all of points in I; VL00-km km is order-preserving only for (2i, 25) such that max i,j < K.
Theorem 2.
N and some 0. Then, Vshap-kmn order- order-preserving for all pairs
Proof. The proof relies dissecting the term (T U (z1)) - U(T u (211) and v(zi) v(z;)
(v Vihap-knnn PL000-mm) in the definition of orerr-presgiving property.
Consider any two points 2i, Zi4z D. We start by analyzing ETU(TU
UT (2)
Let the kth nearest neighbor of Tvaal in T be denoted by T(k) (I(K): M(a)). Moreover, we will use
Top Sa z; to indicate that 2 (())) is closer to the validation point than F, i.e., d( I d(z,, Teal).
We first analyze the expectation of the above utility difference by considering the following cases:
11

---

Under review as a conference paper at ICLR 2020
(1) [(k Sa 2. In this case, adding 2, 2441 into T will not change the K --neerest neighbors to &val and therefore UT U (zi)) = U(T U (z++1)) = U(T). Hence, U(T U (zi)) - U(T U (=++1) = 0.
(2) 2, <d Tik) Sa Zi+1- In this case, including the point into can expel the Kth nearest neighbor from the original set of K nearest neighbors while including the point i + 1 will not change the K nearest neighbors. other words, U (=()) U(T) 1/ val 1 (BCK vell and (2++1))
U(T (2+tt) - U(T) O. Hence, - -
1 - 1MK mmal
K
(3) T(K) >d Zi+-- In this case, including the point or i + 1 will both change the original K nearest neighbors in T by excluding the Kth nearest neighbor. Thus, U(T J (z}) - U(T) =
[| (B(C)) Daal and UTT {2)41)) U(T) 1 1 1[xx) =Mail It follows that UT
K
K
{=+)) U (=++)) voal -1 11++1=
Combining the three cases discussed above, we have
E(U(TU(Z))) - -U(TU (2++1))
(8)
1(ye yhall
1 (())) 3/aal
= P(((K) Sa x)) x x P(z: <a Tak) Sa 2s41)
K
1 1wy = Uval] 1l lyitt1 = Vvail
+ ((((()) >d >d 2++1)
(9)
K
=P(2 <a ((K) Sa 2+11 11 1 = yval]
- [uCKc) = thail
K
1 1(y) yvall 1 1 yvall
+ (() >d 2141)
(10)
K
Note that removing the first term in (0)) cannot change the sign of the sum in 10)) Hence, when analyzing the sign of (10), we only need to focus on the second term:
11%. = ylva]] [M6++ = Mvail
P(T(K) >d zi41)
(11)
K
Since ((T(K) >d 2+41) E K P(Z >d 2+11*, the sign of 11b will be determined by the
sign of 1(y = Uval - 1 1// = Vval). Hence, we get (E (z)) - (T (z++))l) (1ly yval] [ yrail) >> 0
(12)
Now, we switch to the analysis of the value difference. By Theorem 1 it holds for the KNN Shapley value that
Ushups knm (2i) Vshups kmm (21+1)
(13)
i+1-1 min min(K.j) (1/y; = -vval - 1(1j+1 = Bvall)
(14)
jK
1=
min(K, i}
i4--2
min min(K,,) jK
1ly = yeal] +
1|05+1 = yvall
iK
(j+1)K
min K, 11, 186+1 = Mvai]
(15)
(i+ 1)K
Note that min(K.j+1] min(K.))
< 0 for all j = i,...,i - 2. Thus, if [sy wvai = 1
[++]K
jK
and [ys+1 Yvai] 0, the minimum of 15 is achieved when 1 [95+1 yval] = 1 for all
j = i ,,..., + - 2 and the minimum value is min min(KKi+L_11, which is greater than zero On the
(#+-1)j
other hand, if [3: yval] 0 and 1 [9:41 Yvai] = 1, then the maximum of 15) is achieved when
min which [ = yval] = 0 for all j = i, ................................ I and the maximum value is (1+1- 1jK
less than zero
Summarizing the above analysis, we get that Vssap- (2x) Vshhap-kma ( (2++1) has the same sign as 1ly, = Vvall - 1 = yeal- By (12). it follows that V/hap knn ( (2i) Mshapp (2i+1) also shares the same sign (TU (z))) U(TU (241)).
12

---

Under review as a conference paper at ICLR 2020
To analyze the sign of the ANN LOO value difference, first write out the expression for the KNN LOO value difference:
K (1(v: yoail - 1 1 Dvall)
ifitlsk K if & K <i+l (16) ifi K
Mao--mn (2i) Mon (2i-1)
K (1 wy - yvall
1 [KK+ Ival))
0
Therefore, Mooo knn (2) - Ploo-km (2e+1) has the same sign as lys = Diail - [ = Yrail and (T (=+)) UTT U (z(41)) })] only when + s K.
B PROOF OF THEOREM 3
We will need the following lemmas group differential privacy for the proof of Theorem 3
Lemma 2. If is (eff)-diifrrentialll private with respect one change in the database, then A is (ce, c0 o)ddifferentially private with respect to e. changes in the database.
Lemma (Jia al. (2119)).. For any 2i,2j E D, the difference in Shapley values between 2; and 2j is
U(TU(2)) U(TU
Vshap (2i) Vshaa (2z)
(17)
N
(T71)
TED((E.,;;>
Theorem 3. For a learning algorithm A(-) that achieves (E(N), (C(N),8(N)))))))) when training on N data
points. Let the performance measure be U(S) Ms Σ = B 2nd, for S D. Let
c(N) cee(NN + ((N)). Then, holds that
N-1
max U (z.) S <c(N-1 1) 4ED
max Vihap (z.) 2GE
S N N-1 Σ c(()
Proof. Let 5" be set with one element in replaced by different value. Let the probability density/mass defined by A(S') and A(S) be p(h) and ph(),, respectively. Using Lemma for any Zval we have
[' Pn-A(s)(((h, zvat) > l]dt
BanA(syl(h, 2val)
(18)
[' (e Ph>Aiss) 2val) t] + ce
(19)
= =E"EE~A(s)) [[h 2ma)) co
(20)
It follows that
En, zma) - En~A(s) zvai]] S (6 - -(m))BBAA (va)) + c6
(21)
S - 1 1 c6
(22)
By symmetry, it also holds that
E =val) (7),, =vall] & (6 - 1) [(,, =vmi]] c6
(23)
e + c6
(24)
Thus, we have the following bound:
[E,, zval) EE zvai)] s 0t 1 + 06
(25)
13

---

Under review as a conference paper at ICLR 2020
Denoting d' d' e - + cE 8. For the performance measure that evaluate the loss averaged across multiple validation points U(5) M Ei M RR-AA(S)(h,, =val,)) have
(U(S) - U(S') s
(26)
Making the dependence on the training set size explicit, we can re-write the above equation as
max
(U(T - U(T s ((T)+
(27)
R. S.SJETTEDY D.
By Lemma 3 we have for all 24, 2j E D.
Vshap Vssha(21)) - V/taap (2,) 5
1
N-2
Σ
c(k+1)
(28)
N 1
(N=3)
0=
TCD
WED T
2
1
c(k+1)
(29)
N
k=0
N-1
1
(1)))
(30)
N
k=1
As for the LOO value, we have
(zi) (=)) \ (zj)) - U(D) \ (=i)
(31)
[((N-1)
(32)
C COMPARING THE LOO AND THE SHAPLEY VALUE FOR STABLE LEARNING ALGORITHMS
An algorithm G has uniform stability y with respect to the loss function if [I(((()).)) ((G(S")) S for all (1....,,,,,......... [S]}, where denotes the training set and S denotes the one by removing ith element of S.
Theorem 4. For a learning algorithm A(-) with uniform stability B = Cas Ts
where |S| is the
size of the training set and Cstb is some constant. Let the performance measure be U(S)
M 1
EM M I(A(S), 2.al,i). Then,
Cstab
max (2o) [=)) S 2
(33)
N
and
Cstat (1 + log(AN - 1))
Ushap (24) Ushhap (shhu(("") (2*) S
(34)
&DD
Proof. By the definition of uniform stability, it holds that
Caub
max zy DV
(U(TU - UCT S
(35)
T
Using Lemma we have we have for all 2;, 2j E D,
2 Vstuup (2;)
Vahap (2z)
(36)
2
Σ
Caah
(37)
N
(N=
K=
TC MP
1
N-2 2
Catab
(38)
N
k ++1
k=0
14

---

Under review as a conference paper at ICLR 2020
Recall the bound the harmonic sequences
Σ k=
S + log(
which gives us
Csua (1 + log(( - 1))
Ushap (zi)
Ushup (2j) S
N --1
As for the LOO value, we have
Cstab
(200 (1o0(2)) - -(D)))))=((())))))-->0) UD) (z)))
(39)
N
L
D ADDITIONAL EXPERIMENTS
D.I REMOVING DATA POINTS OF HIGH VALUE
We remove training points from most valuable to least valuable and evaluate the accuracy of the model trained with remaining data. The experimental setting, including datasets and models, the same as that for the data summarization experiment. Figure comparee the power of different data value measures to detect high-utility data. We can see that removing high-value points based on KNN-Shapley. G-Shapley, and TMC-Shapley can all significantly reduce the model performance. indicates that these three heuristics are effective in detecting most valuable training points, On UCI Census, TMC-Shapley achieves the best performance and KNNN-Shapley performs similarly to G-Shapley. On Tiny ImageNet, both TMC-Shapley and G-Shapley cannot finish in 24 hours and are therefore omitted from comparison. Compared with the random baseline, KNN-Shapley can lead to a much faster performance drop when removing high-value points.
Prediction accurscy (%)
Predictin accuracy (96)
60
Leave One Out
TMC-Shapley Random
6
G Shapley
INN Shapley
INN LOD
Random
INN Shapley
LDO KNN Shapley
20
60
80
10
20
30
40
Fraction of train data removed (%)
Fraction train data removed (%)
(a) UCT Census Dataset
(b) Tiny ImageNet
Figure 6: (a-b) We remove high-value points from the ground training set and evaluate the accuracy of the model trained with remaining data.
D.2 RANK CORRELATION WITH GROUND TRUTH SHAPLEY VALUE
We perform experiments to compare the ground truth Shapley value of raw data and the value estimates produced by different heuristics. The ground truth Shapley value is computed using the group testing algorithm in (Jia et al.] 2019b), which can approximate the Shapley value with provable error bounds. We target model. Following the setting (Jia et al.) 2019b), we construct size- 1000 training set using MNIST, which contains both benign and adversarial examples, well size- 100 validation set
fully-connected neural network with three hidden layers as the
15

---

Under review as a conference paper at ICLR 2020
with pure adversarial examples. The adversarial examples are generated by the Fast Gradient Sign Method (Goodfellow et al., 2014). This construction is meant to simulate data with different levels of usefulness. In the above setting. the adversarial examples in the training set should be more valuable than the benign data because they can improve the prediction on adversarial examples. Note that the N'NN-Shaplyy computes the Shapley value of deep features extracted from the penultimate layer.
The rank correlation of KNN-Shapley and G-Shapley with the ground truth Shapley value is 0.08 and 0.024 with p-value 0.0046 and 0.4466, respectively. It shows that both heuristics may be able to preserve the exact rank of the ground truth Shapley value. Since TMC-Shapley cannot finish in week for this model and data size, we omit from comparison. We further apply some local smoothing to the values and check whether these heuristics can produce large values for data groups with large Shapley values. Specifically, we compute I to 100 percentiles of the Shapley values, find the group of data points within each percentile interval, and compute the average Shapley value as well as the average heuristic values for each group. The rank correlation of the average NNN-Shyy and the average G-Shapley with the average ground truth Shapley value for these data groups are 0.22 and -0.002 with p-value 0.0293, 0.9843, respectively. We can see that although ignoring the data contribution for feature learning, KNN- KNN-Shapley can better preserve the rank of the Shapley value in a macroscopic level than G-Shapley.
E EXPERIMENT DETAILS
E. PATTERN-BASED WATERMARK REMOVAL
We adopted two types of patterns: one is to change the pixel values the corner of an image Chen et al. (2018a), another is to blend a specific word (like "TEST") in an image, as shown in Figure 7a| The first pattern is used in the experiments fashion MNIST and MNIST, which contain single channel images. The second pattern is used in the experiment on Pubfig-83, which contains multi-channel images.
TEST
(a)
(b)
Figure 7: (a) Examples of pattern-based watermarks. Specifically, after an image is blended with the "TEST" pattern, it is classified as the target label, e.g, an "automobile" on CIFAR-10. (b) Example of instance-based watermarks, which are typically chosen as some out-of-distribution data with specific assigned labels.
Table 2 shows the prediction accuracy of the watermarked model on both benign and watermark instances. The results indicate that the amount of watermarks we added can help successfully claim the ownership of the data source.
Handwritten Digit
Object (ResNet18)
House Number (ResNet18)
Model Accuracy
(Logistic Regression)
Watermarked Model on Benign Data
0.997778
0.980667
Watermarked Model on Watermark Data
0.98
Table 2: Model accuracy for pattern-based watermark removal experiment.
E.2 INSTANCE-BASED WATERMARK REMOVAL
We used the same watermarks as Adi et al. (2018), which contains a set of abstract images with specific assigned labels. The example of trigger image is shown in Figure 7b
16

---

Under review as a conference paper at ICLR 2020
E.3 DATA SUMMARIZATION
For the experiment on UCI Adult Census dataset, we train the same multilayer perceptron mode as Chen al. (2018b). The network architecture is displayed in Table
Model for Adult Census Dataset
FC(6) + Sigmoid
FC(100) + Sigmoid
Table 3: Model for evaluating the data meaning Data Summarization
For the experiment on Tiny ImageNet, we fine-tune the pretrained ResNet18 from He al. (2016). We train the ResNet18 with 15 epochs and learning rate 0.001 and the model achieves an accuracy of 77.95% on the training set. Then, we extract the deep features of the training set and calculate their Shapley values. When evaluating the model performance on the summarized dataset, we re-train the ResNet18 with 30 epochs and learning rate 0.01.
E.4 DOMAIN ADAPTATION
As to the domain adaptation between MNIST and USPS, train multinomial logistic regression classifier. For transfer from SVHN to MNIST, we train a ResNet18 model using 15 epochs and learning rate 0.001 on SVHN, since multinomial logistic regression is too simple perform well in this setting.
17


Reviews:
[{"review_id": "ryxX9xEpFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Given that computing the Shapely value for data valuation is very expensive and existing approximate methods are not scalable either, the authors introduce a new approach based on K-NN approximation of the model to scale it specifically for DNN. The authors propose to use the final features produced in the last feature extractor layer of DNN as features for KNN and choose K such that the performance of KNN is closest to the performance of DNN. My main problem with this approach is that the authors still need to do this for any trained DNN in order to compute a good value for Equation (2). If the claim here is that the features extractor layers of deep neural network does not change by changing the training set (which is a huge claim), then why one should use K-NN. We can simply use the feature extractor part of DNN (almost all the trainable parameters except the last layer) once and then fix it and only learn the soft-max layer parameter for different subsets. Overall, I believe even though this paper aims to address an important problem, the approach is taken is not well-justified and lacks value. Below  are some other minor problems:\n\nThe introduction/title of the paper claims this is a general approach for any model but the authors' focus is only on DNN. This should be corrected. \n\nInconsistent notation: \nBeginning of Section 2. The training and test set is first denoted by D and D_{test} and then later by S and S_{test}.\nEquation (2): the authors are using U in a different forms that the ones introduced earlier in Section 2. I recommend the authors only introduce one notation for U and stick with it throughout the paper.\n\nWriting problems:\nSection 2: “algorithm algorithm” → algorithm (repeated word)\n Section 2: “For each training data z_i, our goal is to assign a score to each training point, denoted by … ” →Our goal is to assign a score to each training data z_i denoted by …\n\nNote that the assumption in machine learning is that you do not have access to the test set and it is something you won’t see until you deployed your method. I assume the authors meant validation set.\n\nConstant C is introduced in Equation (2) but it is not well justified. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "HJle4GUAKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors have developed an algorithm to estimate Shapley value with complexity independent of the model size, based on the KNN classifier. Although the paper is interesting in general, and the experiment results are strong, I still feel that the current version of the paper has not quite met the (very high) standard of ICLR, for the following reasons:\n\n1) The authors need to better motivate the advantages of using Shapley value as a data valuation metric. It is not completely clear to me why Shapley value is a good data valuation metric, compared with other options. The authors argue that it is both fair and decomposable (linear in U). However, based on Section 2.2, it is only fair under two extreme cases (identical points and zero marginal contributions). Also, it seems that a lot of other metrics will also satisfy the decomposability condition. Please explain!\n\n2) Section 3 and Section 4.1 focus on U defined in equation (3), in which the testing set is a singleton. It seems to be a major limitation of the paper and it is not clear to me whether or not it is easy to generalize the results in these two sections to the general testing set with multiple points. Please explain!\n\n3) In Definition 3, the definition for the dummy point. This definition requires that U(S \\union {z_i}) = U(S) for any S \\subseteq D, and in particular it should hold for S=\\emptyset. Does U({z_i}) = U(\\emptyset) make sense in most practical problems?\n\nA typo: in Definition 2, n and N should be the same.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1ejzNb0YS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In short, the paper reports improved results on a few applications of Shapley Value of data points using an introduced approximation method that is orders of magnitude faster compared to existing methods. \n\nI vote for rejection of this paper mainly because of two reasons. First, the contributions are not enough for this venue. The paper uses an already existing method (Jia et al. (2019a)) with the only difference being that they use it on top of learned features and therefore the main contribution seems to be the discussions in Sec4. Secondly, the paper makes technically \"false\" claims (as will be dicussed below). \n\nThe positive aspects of the work are as follows: First, the elephant in the room for data valuation methods, which is assessing how good or bad a data point is, is against privacy and this work addresses this question for the first time in the (very small) literature. Secondly, the experimental results are very comprehensive and make a very good case for usefulness of the introduced algorithm. Thirdly, new useful terms for the emerging community of data valuation are introduced through the clear and well-written definitions of the paper. \n\nThe paper mentions that the previously introduced KNN-Shapley method applied to the learned features of a deep neural network could be used as an approximation of data points' Shapley values. This is false. All data points contribute value to the feature learning part and the approximation simply ignores this crucial fact. The whole point of using Shapley values a measure of data value is its properties which are not satisfied for the \"collaborative game of ML model training\" by this approximation; the approximation can be heavily biased due to the fact that ignores the contributions to the feature learning (let's not forget what made deep network's desirable in the first place is their feature extracting power). One cannot use the training data to learn the feature extractor and then ignore the contributions by definition of the Shapley value being the average contribution to a random subset of data points (which means the rest of the data points are removed from the game). Or, one can do such a thing but the method cannot be called an approximation for the true Shapley Value of data points. The G-Shapley heuristic mentioned in the paper from previous work also seems to suffer from the same drawback as it is not playing the same collaborative game of training the ML model (unless one assumes that simply taking one step of the gradient for every data points would be a good approximation for a complete training!)\n\nThe experimental results are comprehensive and convincing.  The main issue is that the work discusses these experiments as if the goal of computing data value is performing such tasks (for each of which there exist simpler methods not related to data valuation). \" The valuation methods often serve as a preprocessing step to filter out low-quality data,\nsuch as mislabeled or noisy data, in a given dataset\" is not a correct statement. The valuation methods serve as valuation methods which the introduced method, although providing \" a valuation method\", is not providing an unbiased estimate of the equitable Shapley value valuation method. For many of the provided tasks in the experiments section, previous works (Ghorbani & Zou, Jia et al 2019 b) report the same experiments as further inspections into the Shapley Value for data and not as goals of computing these computationally expensive values. \n\nAll in all, although the paper's experimental and theoretical results are useful and interesting as the use case of \"a valuation method\", but is technically incorrect as calling it an approximation for Data Shapley values makes it not publishable. My score is subject to drastic change if a major rework is done to make this point clear.\n\nA few questions and suggestions:\n\n* One of the most striking results from the Data-Shapley works were removing points from most valuable to least valuable and looking at the accuracy drop speed. It would be very necessary and also very convincing if the introduced method is good at detecting very positive points as well as very negative points.\n* An interesting empirical experiment would be to look at the Rank Correlation between the introduced approximation and other unbiased Shapley Value approximations. If the correlation is high, it means that empirically the data points contribute equally to feature learning and their value can actually be approximated just by looking at the accuracy on extracted features.\n* Is any unbiased estimator of true Shapley Values is \"order-preserving\" by definition?\n* In Sec 2 it would be more useful for the general audience to include the third Shapley property too.\n* For almost all of the cases of comparison where previous methods are present for comparison, there seems to be no meaningful advantage. This makes interpreting Figures like 4b, 4c, 5b and most importantly Fig 6b. It would be necessary to add other benchmarks that are not Shapley based. For instance, for data summarization, there has been a line of work the methods of which could be used as a measure of comparison.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is insufficient support to recommend accepting this paper.  The authors provided detailed responses to the reviewer comments, but the reviewers did not raise their evaluation of the significance and novelty of the contributions as a result.  The feedback provided should help the authors improve their paper.
Decision: Reject