Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces the prediction depth (PD) as a measure of example difficulty in deep networks. They then conduct an empirical study on several vision tasks of the relationship between PD and some other quantities:
 - difficulty of an example, as (qualitatively) measured by a human
 - accuracy and consistency
 - difficulty of learning an example (i.e. an example is difficult to learn if it is consistently correctly classified after a large number of iterations)
 - margin
and conclude that PD is useful for predicting these quantities
main_review: This work is in the line of other works trying to characterize example difficulty in deep learning. This is certainly a trendy topic, and an interesting one as far as I am concerned. The proposed measure of example difficulty gives new insights in how deep networks make their prediction. This new measure adds up to the growing list of example difficulty measure recently proposed in the literature, and I would be interested in seeing a comparative study of all different example difficulty measure (but that could be the subject of another paper).

The paper reads rather clearly, despite the impression that it is the shorten version of a longer paper. The experiments are clearly motivated, explained and discussed, except for section 3.3

The empirical relationship between PD and other quantities, observed in this case on vision tasks, is of significant interest.

During reading, I had the following questions:
1. Can you motivate the use of k-NN classifiers rather than anything else. What does it tell us about how a prediction is made, that something else e.g. a random forest would not tell.
2. in sec 3.3 I had a hard time understanding your experiment. "we construct a loss function that does not promote confidence" l221 => not only does it not promote confidence because of the hinge loss, the use of full batch gradient descent, and very small learning rates drastically change the dynamics of training. Aren't we hitting the lazy training regime of Chizat and Bach 2018? IMO the control experiment is too far from this setup (i.e. it uses large learning rates, and minibatch gradient descent with momentum). 

I would recommend to accept it for NeurIPS, provided that these questions are satisfyingly answered.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose a new characterization of the difficulty of an example during training and testing of deep learning models: the layer at which an example is learned (which they call "prediction depth"). They show that early layers are enough to learn easy examples, and that difficult examples are primarily learned by later layers. They also connect the prediction depth to two established notions of example difficulty from the literature: the consistency score and the iteration learned (closely related to the example forgetting statistic).


main_review: Strengths:
1. The authors present a comprehensive set of experiments to characterize the layer depth in deep neural networks at which examples can be classified correctly by a k-NN probe. They evaluate the prediction depth of examples from 4 datasets with varying difficulty (from fashion MNIST to CIFAR 100), and show that this prediction depth is relatively consistent across architectures and random seeds.

2. This manuscript also offer a helpful characterization of examples along two axes: the prediction depth of an example when it occurs in the training set and when the example occurs in the validation set. I'm specifically excited about this characterization's ability to disentangle "hard" examples into three groups. This characterization has the potential to inspire future work on better understanding these different groups and how to encourage learning that leads to better generalization.

Weaknesses:
1. The clarity can be improved. The paper is extremely dense, which is not helped by the obvious tampering with the NeurIPS template (e.g. there is basically no space between paragraphs). I appreciate that the authors wanted to include results from a thorough experimentation but the sheer amount of content can be counterproductive in getting their point across clearly. The authors also rely on the figure captions to summarize the figure takeaways without including summaries in the main text. I appreciate the descriptiveness of the figure captions but they often occur on different pages from where the figure is referenced, so having to continuously flip through the paper to just understand the takeaways of the experiment really breaks up the flow.

2. The connection between the findings in this work and applications of deep learning is entirely relegated to the Appendix. I recommend the authors to include a more thorough discussion of these possible connections in the main paper.

3. Lack of quantitative characterization of the claimed correlations in Figures 5-6. The authors merely state that the measured quantities in these figures correlate but do not report the actual values of the correlations. Also when the authors report a correlation coefficient, they should specify which correlation metric was used (Pearson?).

Minor points (mostly typos and clarity issues):
- L50 and L306: authors refer to "four deep learning phenomena" but only 3 are listed and appear in the paper
- Fig 2 refers to 250 trained models but at this point the authors have not discussed what these models are. The authors should also specify how many random seeds were used in Fig 2.
-  L120-L127: does the MLP achieve similar training and validation accuracy as the other two architectures? Can the differences in prediction depth be due to differences in these final accuracies?
- L163: "of in"
- What is actually plotted in the 2d histograms? Is it the percentage of the dataset that has specific properties?
- I didn't understand what understanding the intervention in section 3.3 really provides beyond the results already shown in Fig 6. I recommend the authors clarify this or remove it from the main paper, since they are short on space.
- Fig 8 caption: "extremes" -> "extreme"
- Fig 8: what are the std errors across these 100 examples?


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Summary: this paper presents a measure of the difficulty of classifying an input example in a dataset defined by the layer of a neural network based on how a k-nearest-neighbours classifier clusters the input point at each layer of the network. The authors empirically evaluate the correlation between this measure and other notions of example difficulty such as margin width.
main_review: Strengths:
- The main idea, that network representations cluster some data points by earlier layers than others and that earlier clustering occurs for examples that the network learns faster and more reliably, is soundly supported by the empirical evidence provided in the paper. 

- The paper includes a number of nice visualiizations of various properties of the prediction depth measure.

- Most experiment descriptions were reasonably clear.

- Tracking how networks cluster their inputs at different layers sounds like an intriguing concept that might be of interest in the neural network interpretability setting, though that is not where my expertise lies.

- The measure proposed does indeed seem to correlate reasonably well with a variety of other notions of example difficulty, and the authors have done a nice job of studying its correlation with a number of existing phenomena. 

- The strength of some of the correlations between the accuracy of a network is striking, particularly the sharp triangular shapes shown in Figures 3 and 4.

Weaknesses: 
- While the paper presents some interesting observations, these observations do not lead to actionable insights. The results here are observational, showing that a phenomenon appears in a set of architectures and datasets, but not making testable predictions about how networks should be trained in light of these observations.

- The results are not surprising. It is already known that intermediate layers perform clustering their inputs, and similar insights have been used in the uncertainty quantification literature. The fact that some datapoints are assigned to their cluster earlier in the network than others is not surprising given previous work studying early vs later layers of learning.

- The unifying picture starting in line 274 that connects prediction depth to previously observed phenomena doesn’t draw a clear causal connection between example difficulty and the related points. I mostly agree (though I think it might be worth explaining why consistent predictions imply generalization) that the observations on predictive depth are consistent with prior work, but it’s not clear to me whether the authors are suggesting that networks converge from input layer towards output layer because of some mechanism that depends on prediction depth, or whether they’re simply observing a correlation. For example, if networks converge from early to late layers and easy examples are learned first, then we would expect that the easy examples will be learned by early layers, and so will have low prediction depth. 

- I don't see what additional information Prediction Depth provides about example difficulty beyond what would be obtained by existing methods such as looking at the number of training steps required to learn the example.


Concrete points for improvement:

- The “intervention” experiment is not clear. A great number of details of the training procedure are changed, and I don’t understand how the authors make the claim that they have isolated the relationship between margin width and prediction depth.

- The main point missing from this paper is an example showing that prediction depth is able to provide useful and/or novel insights into training and inference in deep neural networks. For example, the introduction suggests that formalizing principles governing the passage of data through layers of a neural network could help with curriculum learning, fairness, efficiency improvements in neural networks, uncertainty quantification, and distribution shift. I would be much more convinced that prediction depth is a useful and interesting concept if the authors showed an example where other notions of example difficulty fail to provide useful insights into one of these areas while prediction depth succeeds.  

- Can the authors provide a clearer sense of whether they think that the phenomenon that prediction depth measures is a causal factor in the other deep learning phenomena they describe? In the absence of insights leading to algorithmic improvements, there may be interesting theoretical results that can be derived from the perspective of clustering and information propagation through layers. Providing such a unifying view would significantly strengthen the paper.


Other questions:
- The proposed measure depends heavily on the training data set. I would have liked to see a deeper analysis of how the training data set size and complexity affects the example difficulty of various inputs. For example does the difficulty of a given example change when the network is trained on CIFAR-10 vs CIFAR-100?

- How does the example difficulty of an input change over the course of training? Do networks trained to overfit vs with early stopping exhibit different behaviour?
limitations_and_societal_impact: Yes, theoretical work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors proposed a new measure of computational difficulty called effective prediction depth, which determines the number of hidden layers after which the network's final prediction is determined by a k-NN classifier. They investigated different vision datasets and showed a consistency with a few known phenomena in the literature.

main_review: The understanding of deep learning models is an important field of research. Despite the good motivation, this work offers very limited novelty. Zhang et al., 2020 already proposed a way to evaluate the structural regularities of the labeled data. The observations made in the paper are also previously reported without significant new insights ("early layers generalize while later layers memorize; early layers converge faster; and networks learn easy data and simple patterns first"). 

The paper suffered from a major argument circularity issue. By using a KNN classifier, for each input data example, the "example difficulty" is determined mostly by the distribution of the training data (i.e. what are the other data examples). Thus, it shouldn't be a measure specific to a certain data example. For instance, if there is only one class in the dataset, does it mean that all examples have a prediction length of zero? 

As another example, if the dataset is two-class that is highly imbalanced (0.1 and 0.9). Then, the large prediction length of the minority class shouldn't imply that it is "visually confusing or mislabelled" as suggested by the authors. It is just a data distribution artifact.

This measure is also highly dependent on the model architecture. If we only have 1-layer neural network, then all the examples will have a prediction length < 2. And the computed prediction length will have no meanings to compare to another models (say, a 100-layer network).

The observations made by the authors appear mostly obvious and reported by prior work. The KNN method to probe deep embeddings of each layer, as also pointed out by the authors, are proposed by Cohen et al. (2018) and thus, not novel.  

-----
post-rebuttal:

As in the response to the rebuttal, I increased my score to borderline because I am more convinced on the insights that the prediction depth can give. The reason I wasn't able to raise the score further, is that, many of these insights (contextual property and unifying framework) can potentially require considerable writing improvements to emphasis their theoretical significance and interpretations, and without the option to review the revision, I can't fully root for this submission whose main contributions depends on these additional understandings. 
limitations_and_societal_impact: As in the main review.
review_title: null

Meta-review: The paper proposes Prediction Depth (PD) as a measure of example difficulty. The PD of an example is defined as the first layer for which the predicted label of a KNN classifier that uses the representations of the training set produced by that layer (and the KNN predictions for all subsequent layers) matches to the predicted label of the network. The papers finds that easy examples have low prediction depth (learnt early in the network). Differently from other measures of example difficulty, PD can be calculated for examples when they are included both in training set and in validation set. This allows the authors to characterize three types of example difficulty. They show PD is predictive of the consensus-consistency of a separately trained ensemble, which sheds potential applications to uncertainty estimation (though already done to some extent by [20] and [46]).

--

There have been extensive discussions amongst reviewers about this paper. This is an empirical paper. All reviewers agree that the topic is interesting and timely. The paper is generally clear although it appears too dense. A suggestion is to move some text from captions into the main text. Reviewers think that the experiments are comprehensive. The major concerns were around the a) novelty of some of the findings (low-prediction depth correspond to easy examples), b) the lack of actionable insights based on the observations and c) lack of conceptual depth (what does PD really tell us about generalization?). After rebuttal, reviewers agree that interesting findings and observations (characterization of train/val PD of an example, lower-bound on consistency-consensus score, eg Figure 3, 4, 7) are made.

Overall, this is a borderline paper. Due to the extensive amount of experimental results, I think this paper could potentially benefit the field in general. However, in the current form the paper might not be quite ready for publication yet and might benefit from an additional round of reviews. Following reviewers' advice, I encourage the authors to resubmit the paper by putting more emphasis on the findings in Fig. 3, 4 and 7, to discuss potential actionable insights of this work in the main text, to check their final copy for typos ("Abstract:" in the abstract, "LL" is not introduced anywhere in l249, ...) and to balance the overall textual load of the paper.
Decision: Accept (Poster)