Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Update: Thanks for the response. I agree with the other reviewers that the updates have improved the paper.

This paper presents a way of estimating the informativeness of a single training data point wrt a neural networks weights or it's output function.

Overall I think this paper is well written and interesting, but could benefit from links to other areas of the ML literature (detailed below) and further explanation of some puzzling experimental results.

The notion of unique information is very similar to the notion of strong relevancy in feature selection (in "Wrappers for Feature Subset Selection, Kohavi & John, Artificial Intelligence 1996). A feature is strongly relevant iff p(y|x,\omega) != p(y|\omega), that is if the presence of the feature changes the conditional distribution of the output conditioned on all the other features. In the same way a datapoint has unique information if the presence of it changes either the weight distribution or the output function. This much follows from the submitted paper. However the Kohavi & John paper also formalises a notion of weak relevance, which means that the presence of a feature changes the conditional distribution of the output given some subset of the other features. To capture all the information in a feature set you need all the strongly relevant features and some of the weakly relevant features (weak relevance means that the information appears multiple times in the feature set but it might not be in the strong relevant features so you need some of them to cover it). There is an information theoretic treatment of strong & weak relevance for feature selection in Brown et al "Conditional likelihood maximisation: a unifying framework for information theoretic feature selection", JMLR 2012 which may be of interest as it aligns with some of the presentation in the submitted paper. This notion of weak relevance would help formalise the discusson of least informative datapoints and the data summarisation paragraph in the experiments. The weakly relevant *datapoints* are those which describe the typical distribution of the dataset, a model needs some of them to properly capture the structure, but many of them provide the same information (and thus none will be uniquely informative) and that information may not appear in the uniquely informative datapoints.

The results in Table 1 are interesting, but there is little discussion of why the linearised formulation fails to capture the informative examples in the CNN trained from scratch. If the estimates diverge when the models become very different, then that is an important issue which should be discussed in more detail, so a reader can determine if the technique will be applicable to their use case.

The assumption that the SGD steady state covariance is unchanging implies to me that the example isn't very informative as otherwise it would change the loss landscape and thus change the covariance of SGD. Could the authors comment on the strength of this unchanging covariance assumption?

The informative-ness of datasources section seems to implicitly assume that the label distributions are balanced between the different sources, as otherwise the presence of rarely viewed labels could cause very large differences in the weights (which appears to cause trouble with the approximation technique given table 1). If this is required then it should be noted in the appropriate part of the discussion, otherwise could the authors comment on why it's not required?

Minor comments:

- The referencing style is inconsistent: some references say ICML, some give the volume in PMLR for that year's ICML, arxiv is cited in several different ways etc.

review_title: Interesting paper which needs further explanation of some experimental results & assumptions

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper is written in a very bad way and to my opinion is not acceptable without a significant overhaul. First, there are many typos. For instance, word out in page 1 should be our. Secondly, and much more importantly, notations in the paper are very ambiguous and misleading. For instance, in the "prerequisites and notations" section it is mentioned that $A(w|S)$ is a "conditional distribution". Yet in the same section, it says that $A(S)$ is the "output random variable" of the algorithm. So it is absolutely ambiguous what the notation $A(.)$ actually shows. Does it show a probability distribution? or it shows a random variable? You would guess that if you keep reading the paper, the ambiguity goes away, but you are wrong. As you read through the paper, $A(.)$ is used interchangeably for both a random variable and a probability distribution which absolutely ambiguous. For instance, when you see $KL(A(w | S) || A(w | S_{−i}))$ in equation 3 you would argue that $A(w|S)$ refers to a probability distribution that in Prop. 3.2. you would see that $A(S)$ is used as a random variable. Why are the authors use notation $A(.)$ for both a random variable and a probability distribution. I think to remove ambiguity, all probability distributions should be shown with $P(.), p(.), f(.)$ or things of that nature. I would expect to see this fixed in any future revision of the paper. Also, notations like $m(.)$ are not common for probability distributions and make the paper unreadable. 

The role of smoothing in the paper is not clearly discussed and analyzed in the paper. I understand that it is required to make the KL divergence bounds work by adding continuous noise, but are the authors assume assumptions like this just to get some theoretical bounds? Is such an assumption, a valid assumption? and why? How does it change the results compared to real-world applications?


review_title: Very weak presentation. Significant overhaul needed.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes a way to estimating sample information in the
context of neural networks.  The authors propose to simplify the definition 
by using a first-order approximation of an arbitrary network's architecture
and the mean squared error as the loss function.  In addition, a smoothing
matrix obtained around the network's steady state is introduced to minimize the
uncertainty due to limited realizations of a stochastic optimization process.
The method is applied to several image classification tasks for illustration.
Then it is proposed to be used to summarize a dataset, i.e., to remove redundant
examples that have minimal impact to training results.

The derivation of the measure is an interesting exploration of the
relationship between an individual sample's information content and
the neural network's final trained weights or the network's use of
such weights (the values of the decision function).  This contributes
to a better understanding of how information is leveraged by neural networks.

The practical value of the measure itself, on the other hand, is
questionable beyond the use of neural networks.

Is there a way to characterize how intrinsic this measure is,
i.e., to what extent is it tied to the use of neural networks as
the classifier?  Note that there are much simpler, well studied ways
to estimate how normal or abnormal a sample is compared to the rest in
its class and how much it affects classification difficulty
(see the above mentioned survey).  Going through these complicated
calculations for estimation, do you arrive at something that well
correlates with many others derivable using simpler methods?

You may want to compare your data summary to what could be obtained
using, e.g., "The Condensed Nearest Neighbor Rule", Peter Hart, IEEE
Transactions on Information Theory, May 1968, 515-516.

The illustrative examples are taken only from image classification.
It will be more convincing if other tasks, e.g., text classification,
are also tried.  Even better, you can show the values of the
measure, and what outliers it can pull out on some extreme cases:
e.g. randomly labeled samples, or perfectly separable, synthetic
classes.

What would the measure say for the adversarial samples crafted to fool
a neural network?


Misc.:

Section 2, related works:  should also refer to a recent survey that
includes many works analyzing the influence of individual samples
on classification difficulty:
"How complex is your classification problem? A survey on measuring
classification complexity", by AC Lorena, et al., ACM Computing
Surveys, 52(5), 1-34.

p.5:  in and before Proposition 5.1:  something is missing in what is
referred to as "SGD's steady-state covariance".  SGD usually refers to
the optimization procedure; are you reusing it to denote the dw quantity?
If not, what is the quantity whose distribution this covariance is about?

Figure 1B:  why only samples of class cmd are shown?  
To make a better illustration, you may want to show both informative
and non-informative samples for at least two classes.  Also, what do
the histograms in Figure 1A tell you about the different classes?
The examples from Figure 4 may serve the purpose of illustration
better as they are more familiar objects.

review_title: A new way to address an old issue with interesting theoretical insights but unclear practical merits

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes a measure to compute the information of each training sample. The paper shows that this measure can be computed for a large DNN without having to train the network. The authors show that this measure can be used for applications like data summarization and detection of corrupted data. 

My main concern is that the information measure depends on the initialization, training time, and network architecture. For e.g. the F-SI scores seem to change over time in table 5. Hence, one needs to re-compute the measure for the training samples, with a  change in initialization and training time. The complexity of computing the FI-scores for $m$ examples is $O(n^2 m)$. For MNIST, this is at least $10^{10}$ flops for computing measure of 100 examples. I believe, the authors should discuss efficient recomputation of the measure in case of a change in the algorithm parameters or the error involved if we don't re-compute the measure.


My other concerns are the following:
1. The data summarization experiments and the detection of more information data sources and examples are network-specific (in this case, pre-trained Resnet 18). It will be more interesting to see if these transfer to other networks. For example, in data summarization experiments, it will be interesting to see if the most informative examples for pre-trained Resnet 18 also help to train another network. The same question holds for SVHN vs MNIST. 
2. In conclusion, the authors claim that their measure can be used for computing the information for a group of samples. However, in the data summarization experiments, the measure is computed for each sample as a separate entity, while groups of samples are removed at a time. Hence, is it possible to compare the current results with an efficient group-theoretic measure for removing groups of samples? I am concerned because simple examples may not have information individually but as a group may hold important information to train a network.
3. In many sections, the authors have forgotten to mention the network architecture they used to get the plots e.g. in data summarization and detection of under sampled sub-classes experiments. It will be great if the authors can show how the results in these experiments change with a change in architecture, given that the measure depends on the architecture.

I have verified the proofs. They are easy to read and understand. My scores are slightly on the lower side because I believe the computation is too brittle to changes in the algorithm parameters like training time and initialization. I am happy to discuss this with the authors and other reviewers during the discussion period.


***After Rebuttal***
I have read the reviews by other reviewers and the responses of the authors to the questions posed by other reviewers. I enjoyed the additional experiments that the authors added to the paper during the rebuttal. The paper has shown interesting observations on the informative samples present in real-world datasets for different architectures. However, I still believe the method proposed by the paper is too inefficient for simple algorithm changes like changes in initialization. Hence, I am keeping the score the same after the rebuttal.
review_title: Official Review #1

Meta-review: This paper proposes methods to estimate how informative a single training data is wrt the weights and output of the neural network. All reviewers think this is an interesting problem and the proposed method is easy to implement. On the other hand, the reviewers also raise a few questions: 
1.	There is a large body of work analyzing the informativeness of a feature wrt the model. The authors should compare their work to the feature importance analysis.
2.	The derived informativeness of a data depends not only on the network architecture, but also depends on the training algorithm, such as initialization and number of epochs. This makes the notion of data informativeness less general.
3.	The writing should be substantially improved.

Decision: Accept (Poster)