Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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:

1) 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!

2) 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!

3) 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?

A typo: in Definition 2, n and N should be the same.


review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: 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. 

I 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). 

The 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. 

The 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!)

The 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,
such 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. 

All 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.

A few questions and suggestions:

* 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.
* 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.
* Is any unbiased estimator of true Shapley Values is "order-preserving" by definition?
* In Sec 2 it would be more useful for the general audience to include the third Shapley property too.
* 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.
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: 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:

The 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. 

Inconsistent notation: 
Beginning of Section 2. The training and test set is first denoted by D and D_{test} and then later by S and S_{test}.
Equation (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.

Writing problems:
Section 2: “algorithm algorithm” → algorithm (repeated word)
 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 …

Note 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.

Constant C is introduced in Equation (2) but it is not well justified. 

review_title: Official Blind Review #1

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