Deep Learning Through the Lens of Example Difficulty
Authors: Robert John Nicholas Baldock
Hartmut Maennel
Behnam Neyshabur
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep Learning
Example Difficulty
Prediction Depth

Abstract: Existing work on understanding deep learning often employs measures that compress all data-dependent information into a few numbers. In this work, we adopt a perspective based on the role of individual examples. We introduce a measure of the computational difficulty of making a prediction for a given input: the (effective) prediction depth. Our extensive investigation reveals surprising yet simple relationships between the prediction depth of a given input and the model’s uncertainty, confidence, accuracy and speed of learning for that data point. We further categorize difficult examples into three interpretable groups, demonstrate how these groups are processed differently inside deep models and showcase how this understanding allows us to improve prediction accuracy. Insights from our study lead to a coherent view of a number of separately reported phenomena in the literature: early layers generalize while later layers memorize; early layers converge faster and networks learn easy data and simple functions first.

Deep Learning Through the Lens of Example Difficulty
Robert J. N. Baldock" Google Research, Brain Team rjubaldock@gail.coo
Hartmut Maennel Google Research, Brain Team hartmut@@google. com
Behnam Neyshabur Google Research, Blueshift Team
neyshabur@google. com
Abstract
Existing work on understanding deep learning often employs measures that com- press all data-dependent information into a few numbers. In this work, we adopt a perspective based on the role of individual examples. We introduce a measure of the computational difficulty of making a prediction for given input: the (effective) prediction depth. Our extensive investigation reveals surprising yet simple relation- ships between the prediction depth of a given input and the model's uncertainty, confidence, accuracy and speed of learning for that data point. We further cate- gorize difficult examples into three interpretable groups, demonstrate how these groups processed differently inside deep models and showcase how this under- standing allows us to improve prediction accuracy. Insights from our study lead to coherent view of a number of separately reported phenomena in the literature: early layers generalize while later layers memorize; early layers converge faster and networks learn easy data and simple functions first.
Introduction
Much of the existing work understanding deep learning "integrates out" the data, viewing the inductive bias of the model, or the properties of the optimizer as central to the success of the approach.
Examples of such work include studies of eigenvalues of the Hessian and the geometry of the loss
landscape (Ghorbani et al.) 2019 Yao et al.) 2020 [Sagun et al.) 2016 Li et al.) 2018 Pennington and Bahri | Sagun et al. 2018), studies of margin and effective generalization measures (Long and Sedghi 2019: Unterthiner et al. 2020) Jiang et al.) 2020 2018 Kawaguchi et al. (017) ) and
mean-field studies of stochastic optimization (Smith et al. 2021 Stephan et al.) 2017] Smith and Le 2018). However, in practice, we are rarely concerned with only the average behavior of a model.
One pathway to understanding the principles that govern how deep models process data is to study the properties of deep models for data points with different "amounts" or "types" of example difficulty. There are a number of definitions of example difficulty in the literature (E.g. see Carlini et al. (2019): (ookerr et al. (2019); Lalor al. (2018); Agarwal and Hooker (2020)). Two are particularly relevant to this work. Firstly, the probability of predicting the ground truth label for an example, when that example is omitted from the training set (Jiang al., [2021), which represents statistical view of example difficulty. Secondly, the difficulty of learning an example, parameterized by the earliest training iteration after which the model predicts the ground truth class for that example in all subsequent iterations (Toneva et al. 2019). This measure represents a learning view of example difficulty
Work completed as part of the Google AI Residency Program We expand on other notions of example difficulty in Appendix
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

These notions suffer from two fundamental limitations. While early-exit strategies in computer
vision [eerapittayanon et al. 2016 Huang al. 2018) and NLP (Dehghami al. 2018 Liu et al.)
2020b; Schwartz et al., 20200 Xin et al. 2020) suggest predictions for easier examples require less computation, the above example difficulty notions do not encapsulate the processing of data inside a given converged model. Moreover, existing notions of example difficulty (F.g. [Carlini et al. (2019) provide a oie-dimensional view of difficulty which can not distinguish between examples that are difficult for different reasons.
In this paper, we take significant step towards resolving the above shortcomings, To take the processing of the data into account we propose a new measure of example difficulty, the prediction depth, which is determined from the hidden embeddings. To escape the mee-iimnniional view of difficulty, we introduce three distinct difficulty types by relating the hidden embeddings for an input to high-level concepts about example difficulty: "Does this example look mislabeled?"; "Is classifying this example only easy if the label is given?": "Is this example ambiguous both with and without its label?". Furthermore, we show how this enhanced notion of example difficulty can unify our understanding of several seemingly unrelated phenomena in deep learning. We hope that the results presented in this work will aid the development of models that capture heteroscedastic uncertainty, our understanding of how deep networks respond to distributional shift, and the advancement of curriculum learning approaches and machine learning fairness. These connections are discussed in Section 5
Contributions
Our main contributions are as follows:
We introduce measure of computational example difficulty: the prediction depth (PD). The prediction depth, illustrated in Figure [I] represents the number of hidden layers after which the network's 's final prediction is already (effectively) determined (Section 2)
We show that the prediction depth is larger for examples that visually appear be more difficult, and that prediction depth is consistent between architectures and random seeds (Section 2.2
Our empirical investigation reveals that prediction depth appears to establish a linear lower bound on the consistency of a prediction. We further show that predictions are on average more accurate for validation points with small prediction depths (Section (.1).
We demonstrate that final predictions for data points that converge earlier during training are typically determined in earlier layers which establishes a correspondence between the training history of the network and the processing of data in the hidden layers (Section 3.2)
We show that both the adversarial input margin and the output margin are larger for examples with smaller prediction depths. We further design an intervention to reduce the output margin of network and show that this leads to predictions being made only in the latest hidden layers (Section 3.3)
We identify three extreme forms of example difficulty by considering the prediction depth in the training and validation splits independently and demonstrate how a simple algorithm that uses the hidden embeddings in one middle layer to make predictions can lead to dramatic improvements in accuracy for inputs that strongly exhibit a specific form of example difficulty (Section 4
We use our results to present a coherent picture of deep learning that unifies four seemingly unrelated deep learning phenomena: early layers generalize while later layers memorize; networks converge from input layer towards output layer, easy examples are learned first and networks present simpler functions earlier in training (Section 5))
To ensure that our results are robust to the choice of architectures and datasets, we report empirical findings for ResNet18 8 (He et al. 2016). VGG16 (Simonyan and Zisserman 2015) and MIP architectures trained on CIFAR I0, CIFAR 100 (Krizhevsky et al., 2209). Fashion MNIST (FMNIST) (Xiao et al. 2017) and SVHN (etterr et al. 2011) datasets. All models were trained using SGD with momentum. Our MLP comprises hidden layers of width 2048 with ReLU activations. Details of the datasets, architectures, and hyperparameters used can be found in Appendix A Related Work: Our work uses hidden layer probes to determine example difficulty. We have discussed how our study relates to prior work on example difficulty. Hidden layer probes have also been used to study deep learning. Deep k-NN methods (Papernot and McDaniel [018 8) determine their predictions and estimate their own uncertainties by comparing the hidden embeddings of an input to those of the training set. Cohen et al. (2018) showed that SVM, k-Nearest Neighbors (k-NN)
Experimental Sctup:

---

and logistic regression probes achieve similar accuracies. However, they did not study the processing of individual data points nor did they relate the k-NN accuracy to notions of example difficulty. [Alain and Bengio (2017) used linear classifier probes in the hidden layers to interrogate deep models and demonstrated that linear separability of the embeddings increases monotonically with depth. We provide a more detailed discussion of related work in Appendix B
Prediction Depth: a Computational View of Example Difficulty
We discussed the statistical and learning views of example difficulty in Section [ In this section, introduce computational view of example difficulty parametrized by the prediction depth as defined in Section [.1] This computational view asserts that, for "easy" examples, a deep model's s final prediction is effectively made after only few layers, while more layers are used for "difficult" examples.
2.1 Definition
Asserting that the final prediction is effectively determined in earlier layers of model, before the output, we estimate the depth at which a prediction is made for a given input as follows
1. We construct k-NN classifier probes from the embeddings of the training set after particular layers of the network, including the input and the final softmax. The placement of k-NN probes is described in Appendix AA55 We use k = 30 in the k-NN probes. Appendix [A.4 establishes that the k-NN accuracies we report are insensitive to k over a wide range.
2. A prediction defined to be made at depth
if the k-NN classification after layer L - --1 1 is different from the network's 's final classification, but the classifications of k-NN probes after every layer L 2 are all equal to the final classification of the network. Data points consistently classified by all k-NN probes are determined to be (effectively) predicted in layer (the input) P
is worth noting that the prediction depth can be calculated for all data points: both in the training and validation splits. This leads to two notions of computational difficulty:
The difficulty of predicting the (given) class for input (in the training split)
The difficulty of making a prediction for an input, unseen in advance (from the validation split)
We examine both notions of computational difficulty in this paper and use the distinction between them to describe different forms of example difficulty Section 4
2.2 Prediction depth is meaningful and robust notion of example difficulty
In this section we show that prediction depth agrees with intuitive notions of example difficulty and that it is consistent between different training runs and similar architectures.
Prediction depth is higher for examples and datasets that seem more difficult If prediction depth is a sensible measure of example difficulty then we would expect the following sanity checks to be observed:
1. Individual data points that are visually confusing or mislabeled should have larger prediction depths compared images that are clear examples of their class.
2. Data points from tasks that are intuitively simpler should have lower prediction depths on average.
Figure ssoos that the prediction depth passes both of these sanity checks. Appendix C.1 presents additional images, providing further evidence for this claim.
Prediction depth is consistent across random seeds and similar architectures Figure 2 shows that the prediction depth is highly consistent between different architectures and random seeds for all datasets. Perfect agreement is not expected as different deep learning algorithms have different inductive biases which affects the perceived difficulty of examples. We observe stronger correlation
"In the process of arriving this detinition of the prediction depth considered several alternatives. including using the ground truth class in place of the predicted class and using logistic regression probes place of k-NN prohes. See Appendix for discussion on the choices we made in our definition. Immleementttinn details can be found in Appendix A.6.1 A.661
3

---

0.8
Fashion MNIST
SVHN
Input
Probability
0.6
CIFARLO
CIFARI00
0.4
K-NN
K-NN
Clock (CIFAR100)
Digit 8 (SVHN)
Clock (CIFAR100)
Digit (SVHN)
0.2
8
0.0
1
2
4 Prediction Depth
5
7
8
10
Examples predicted the first
Examples predicted the lastl
Deep models use fewer layers to (effectively) determine the prediction for easy examples and more layers for hard examples. Left: A cartoon illustrating the definition of prediction depth (given in Section 2.1 Also shown are training examples from CIFAR 100 ("Clock") and SVHN ("Digit 8")) The examples shown are predicted at the input (first layer) or softmax (last layer) of ResNet18. The examples predicted in the input are visually typical ("casy"), ), while those predicted in the softmax are mislabeled and/or visually confusing ("hard" examples). To find the prediction depth, we build k-NN classifiers from the embeddings of the training set in different layers of the model. The prediction depth corresponds to earliest layer which the predictions of all subsequent k-NN classifiers converge to fixed label. Right: Probability of prediction depth in ResNet18 models for four datasets (training split). We see that the four distributions have different characteristic prediction depths. Ranking the mean prediction depths of these datasets in ascending order, observe: Fashion MNIST (smallest), SVHN (second), CIFARIO 10 (third), and CIFARI00 (largest). This order aligns with how might intuitively rank difficulties these classification tasks.
Figure 1:
SVHN
Validation Train
ResN1B
1.0
0.8
VGS16
10
VGG16
0.5
10a
ResN18
0.4
VGG16
100
0.0
MLP
ResN18
v6616
MLP
ResM18
VGG16-
MLP
Resht18
VGG16
MLP
RedN18
v6616
MLP
0.0
0.0
0.5 ResNet18
1.00.0
0.4
0.8
MLP
Figure 2: Consistency of prediction depth between architectures and random seeds. Left: The panel shows the
correlation coefficient between prediction depths in different architectures, for both train and validation splits four datasets. Diagonal comparisons between an architecture and itself show correlation architecture trained with different random seeds. Right: Histograms comparing the mean value prediction depth obtained for each data point in the training set of CIFAR10 from an ensemble of 250 trained models. In this plot, for visual simplicity. rescale prediction depth the interval [o, 1] for each network. Similar results for all other datasets presented in Appendix C
the same
between prediction depth for ResNet18 and VGG16, than between VGG16 and MLP. This may be explained by the fact that ResNet18 8 and VGG16 are both convolutional networks and we expect their inductive biases to be more similar to one another than to MLP.
3 Deep Learning Phenomena Through the Lens of Prediction Depth
In this section, we explore how the prediction depth can be used to better understand three important aspects of Deep Learning: accuracy and consistency of a prediction; the order in which data is learned and the simplicity of the learned function (as measured by the margin) the vicinity of a data point.
3.1 Depth of a prediction gives a linear lower bound on its consistency
Adopting statistical view of example difficulty, Jiang et al. (202T) identified example difficulty with the expected accuracy of the learning algorithm for given input, averaged over models trained on different random subsets of the training set with different random seeds. In this section, we clarify the relationship between the prediction depth and the expected accuracy by disentangling the accuracy from the sensitivity of predictions to the particular training split and random seed. Following Jiang ct al. (02I), we measure the expected accuracy using the consistency score.
Consistency score Ć:
The frequency of classifying an example correctly when is omitted from the training set. An empirical estimator of the consistency score for validation point (zz, y)

---

All Data
Ground Truth Consensus
Ground Truth Consensus
Consistency Score
1.00
Consistency Score
1.00
101
Consistency Score
1.00
10a
0.75
100
0.75
0.75
100
0.50
0.50
0.50
10
10-1
0.25
0.25
10-1
0.25
0.00
0.00
0.00
2 4 6 910
2 3 7 910
3 4 6 910
Prediction Depth
Prediction Depth
Prediction Depth
Figure 3: Consistency score vx. prediction depth in the validation split (left) can be understood as the superposition of two simple functions (middle and right). We trained 250 ResNet18 models on CIFARIO, with 90: 10% random train:validation splits described in Appendix These histograms compare the frequency of correct predictions the average prediction depth for data point when it occurs the validation split. The density of data points is indicated by the color bar, which follows a log scale. The average prediction depth forms two, surprisingly simple, linear bounds on the consistency score (see Section 3.1 a full deseription.) This Figure is reproduced for all datasets and architectures in Appendix C.3 illustrating the consistency of this result.
is given by (Jiang al. 202I:
ČA.s(I,)) v) = 17
st ((xa)) [
(1)
where a deep learning algorithm (architecture, loss and optimizer), y the ground truth class for x, S is a random subset of n points sampled from a training dataset excluding (ar, y), ya is the predicted class of x for trained with data S, is the Kronecker delta and E" denotes empirical averaging with i.i.d. samples of such subsets S.
Figure (left panel) shows the relationship between consistency score and prediction depth. This plot indicates a surprising piecewise linear boundary which symmetric around consistency score 2 This suggests the existence of missing concept that could simplify the picture. We next show that the missing concept is the notion of a consensus class which is defined below.
Consensus class jA: The consensus class of æ is defined as the predicted class for input by majority voting ensemble of models each of which is trained on randomly chosen subset
$ - SM(,, w)}
Figure (middle and right) shows how conditioning whether consensus class matches the ground truth can change the relationship between consistency score and the prediction depth. For points where the consensus class matches the ground truth (middle) surprisingly simple, linear lower bound on the consistency score. For points where the consensus class differs from the ground truth (right) at low prediction depth the consistency score is bounded from above by line that reflects the bound from the middle plot in Ć 1 suggesting that such points are repeatedly mislabeled with a wrong class label. At high prediction depth, the consistency score is low, which suggests highly inconsistent predictions and low accuracy. This result suggests a simple hypothesis: that predictions with low prediction depth are consistent with the consensus class, whether that matches the ground truth class or not, while predictions made later layers depend strongly on the specific training split and random seed used for training and initialization. We measure consistency with the consensus class using the consensus-consistenn score.
that the prediction depth forms a,
Consensus-come Consensus-consistennyy consistency score C*: The fraction of models in ensemble that predict the ensemble's consensus class A (ar) for an unseen input æ.
(*,((r)
-
Bssss((aa)) [ [S)))
where the notation is the same as in
Figure (left) establishes that our simple hypothesis is indeed correct: the prediction depth forms a linear lower bound the consensus-conssisenns score for all data points, irrespective of whether the
*Implementation details can be found in Appendix A.6.2
Consensuus consistencc score is measure of uncertainty and can be used for calibration Lakshminarayanan
2017 Wenzel et al. 2020 Wen al. 2019). See Appendix A.6.3 details of our implementation.
5

---

Consensus cosss-ossttencc
104
Consensus. Consistency
1.0
1.0
0.8
0.6
100
Accuracy
0.8
0.8
FMNIST
FMNIST
0.4
SVHN
0.6
SVHN
0.2
10-1
0.6
CIFARIO
0.4
CIFARIO
CIFAR100
CIFAR100
0.0
0
2
4
6
10
6 8 10
0.2
0
2
6
8 10
Prediction Depth
Prediction Depth
Prediction Depth
Figure 4: Left: Prediction depth provides with linear lower bound on consensuu-conssiseenn Results for CIFAR100 with ResNet18. We train 250 models 10% random train:validation splits) and compare the average prediction depth when a point occurs in the validation set, to the consensus-consistenge of the corresponding predictions. Predictions made for points with low mean prediction depths are highly consistent. Conversely, predictions for points with high mean prediction depths are lypically more sensitive to the particular training split and random seed used during training. This left plot shows the result for CIFARIOO with ResNet18. The density of data points is indicated by the color bar, which follows log scale. Middle: Prediction depth in one model predicts the consensus- conssssteennss of an ensemble that does not include that model. For each dataset we train 25 ResNet18 8 models with the full training set (see Appendix (A. The consensus- consensus-consistenge consistency of each test point is obtained from 24 of the models, while the prediction depth obtained from the remaining I model. We see that prediction depth in one model predicts the consensus-conssiseeme measure of the uncertainty of the prediction. The size of each marker in the middle and right plots shows the fraction of the dataset with each prediction depth. Reaffirming the second sanity check in Section [2.2] and in agreement with Figure I (right), intuitively simpler datasets (Fashion MNIST and SVHN) have low average prediction depths. while CIFARIO0 (intuitively the hardest dataset) has the largest average prediction depth. Right: Prediction depth predicts accuracy. For cach dataset we train 250 ResNet18 models (90:10% random train:validation splits). Each time a point appears in the validation split we record the prediction depth and whether the prediction was correct. Predictions made in carlier layers are more likely to be correct. Consistency of these plots is demonstrated for all datasets and architectures in Appendix C.3 where we also describe the relationship between the prediction depth and the entropy of the predictions for an ensemble.
of separate ensemble: a
consensus class matches or differs from the ground truth. Interestingly, Figure 4 (middle and right) shows how the prediction depth in single model, can be used to estimate both of these quantities. That is, predictions of data points with lower prediction depth are both more likely to be consistent and more likely be correct.
3.2
The prediction depth of an input is correlated with its learning difficulty
In Section computational view of example difficulty and the consistency and consensus-consie consisteenc scores, which represent a statistical view. In this section we compare prediction depth to a learning view of example difficulty. We measure the difficulty of learning an example by the speed at which the model's 'ss prediction converges for that input during training. The following definition is adapted from Toneva et al. (2019):
3.1 we describe the relationship between the prediction depth, which represents a
Iteration learned A data point is said to be learned by a classifier at training iteration (= if the predicted class at iteration / = 7 is different from the final prediction of the converged network and the predictions at all iterations & 2 T are equal to the final prediction of the converged network. Data points consistently classified after all training steps and at the moment of initialization, are said to be learned in step t =
Figure 5 (left plot) shows the positive correlation between the prediction depth and the iteration learned, for all four datasets in VGG16. Consistent results are presented for all architectures and datasets, in both the validation and training splits in Appendix C.4. As result of the reported correlation, we anticipate that many of the data points correctly classified by the k-NN probe in particular layer should also be correctly classified by the network at corresponding interval of training steps. If this is correct then we would expect there to be a visual correspondence between the training learning curve (which shows how the accuracy of the network changes during training) and the accuracy of the k-NN probes as data passes from input, through the network, towards the output layer. We call the series of k-NN probe accuracies the inference learning curve.
"Note that this detinition can be applied to points in both training and validation splits. In order to compare different models and datasets we rescale the iteration learned in each model so that the 95th percentile occurs at 1.0 and network initialization at 0.

---

Iteration Learnea
1.0
1.5
FANIST
Accuracy
0.8
0.8
Unchanged Data
1100
0.6
0.6
Mislabelled Data
CIFARLCO
Mislabelled Data
0.5
K:NN
0.4
(Original Labels) Test
0.2
0.2
0.0
0.0
0.0
10 12
20
60
80
0
2 6 8 Layer
10 12 14
Prediction Depth
Epoch
Data points with small prediction depths are on average learned before data points with higher prediction depths. We train 250 VGG16 models for each dataset, using a 90:10% random trainivalidation split as described in Appendix [A] Each time an input appears in the validation split we record the prediction depth and the iteration learned in that model. This plot shows the average iteration learned for data points at each prediction depth. Marker size shows the fraction of the dataset with each prediction depth. The Pearson correlation coefficients for the four data sets are as follows. CIFARI00: 0.83. CIFARIO: 0.7. Fashion MNIST: 0.79. SVHN: 0.77. Middle and right: The training learning curve (middle) shares several important features with the inference learning curve (right). Blue, yellow and green curves represent different components of the CIFAR1O 10 training split, in which we have randomized (and fixed) 40% of the labels, and red curves show the split. The middle and right plots show results from 5 random seeds. The inference learning curve (right) the sequence k-NN probe accuracy values for each split. All three plots show results for VGG16. The
Figure 5: Left:
hyperparameters used are given in Appendix A
Output Margin
801
Input Margin
K-NN Accuracy
1.0
Train (CE)
10a
0.8
Test (CE)
Train (0-Hinge)
10
0.6
Test (0-Hinge) Untrained
0.1
10"
8 Prediction Depth
4
2
8 12 Layer
Prediction Depth
Left and Middle: Test examples with smaller prediction depths, on average, have larger output and input margins. We train 25 VGG16 models with different random seeds on CIFARIO (see Appendix A for details) and compare the mean prediction depth of cach test point in these 25 runs to its mcan output and input margins (log scales). Correlation coefficients are -0.70 (output margin) and -0.69 (input margin). The density of data points indicated by the color bar, which follows log scale. Although the prediction depth could be most 14, no data point has an average prediction depth greater than 12. Right: An intervention that does not encourage large output margin ( ("O-Ilinge") results, as predicted, in models where the predictions are effectively determined in higher layers in the network compared to the standard training ("CE").
Figure 6:
To test this hypothesis we train a model on a training split where a subset of labels are corrupted and compare the training and inference learning curves on four splits of the data: unchanged training data; mislabeled training data; the original labels of the mislabeled training data and the test split. In Figure 5 (middle and right plots) see that many of the important features of the training learning curve are indeed present in the inference learning curve. During training (middle), mislabeled data are initially processed as though they are member of their original class (before they were mislabeled) (Liu et al.) 2020a). After an initial period of learning, the network begins to learn the new (random) labels that have been assigned to those data points, the orange curve moves upwards, and the green curve downwards. At this point, a maximum is observed in the training accuracy (Arpit al. 2017). In the right plot we see that these same phenomena occur in the inference learning curve.
3.3 Deep models exhibit larger margins for inputs with lower prediction depth
reported in the literature that deep networks learn functions of increasing complexity during training (Hu et al. [2200] Kalimeris et al. (219)). We frame this observation differently: the learned function is "locally simpler" in the vicinity of data points with smaller prediction depths, and these points are typically learned earlier in training (Section (.22).
Two known measures of the simplicity of a learned function are the output margin (the difference between the largest and second- largest logits) and the adversarial input margin (the smallest norm required for an adversarial perturbation in the input to change the model's 's class prediction). We estimate the adversarial input margin, 7, with a linear approximation (Jiang et al. (018):: for an input x with predicted class i, 7 = minj f [=- class j. Figure 6 (left and middle plots) show that data points with smaller prediction depths have
[= where zj is the logit returned by the network for
7

---

Consensus Ground Truth
Consensus Ground Truth
Class: Bird Pred. Depth (Train)
10
10
10
100
8
10
8
100
6
6
10
10-1
4
4
4
10-2
2
2
10-2
10
0
0
2
4
6
8
10
0
2
4
6
8
10
0
2
4
6
8
10
Pred,
Depth (Val)
Pred. Depth (Val)
Pred. Depth (Val)
Bird
Bed
Bidd
Bind
AArppann Airpare Airplane Airibnns
Dog
Bidd
Home
Dog
Bind
Bird
Bird
Deer
Easy
Looks like different Ambiguous w/o label
Ambiguous
Figure 7: The prediction depth can be the same, or very different the same input when it occurs in the train and validation splits. Corners of this plot correspond to different forms of example difficulty. (See Section 4 for discussion.) We train 250 ResNet18 models on CIFARIO with random 90:10% train:validation splits as described in Appendix A These histograms compare average prediction depth for each data point when it occurs in the validation split the training split. This behavior is consistently reproduced for all datasets and architectures in Appendix C.6 Below we show extreme (not hand-chosen) images of "Birds" that appear closest to the corners of this plot. The consensus class is given above each image (tiebreaks favor the class "Bird".)
both larger input and output margins on average and that variances of the input and output margins decrease as the prediction depth increases.
To illustrate the strength of the relationship between the prediction depth and output margin, we demonstrate that reducing the output margin of the learned function results in model that clusters the data only in the latest layers: such a solution has a very high average prediction depth. We do minimize the output margin directly but rather use a loss and an optimizer that do encourage high output margin. Naturally there are many unknowns that may contribute to this effect. We simply report the intervention and the outcome.
The intervention is performed confidence: a zero-margin hinge loss ("O-Hinge"), and optimize the network using f full-batch gradient descent with momentum and very small learning rafe. For an input with label the O-Hinge loss is given by [(x) = Ejfe max(0, 2 2ÿ) where 2j represents the logit for class j. The form of this intervention is justified in Appendix A.7 As a control, we additionally train a model in the standard fashion using the cross-entropy loss and SGD with momentum and large initial learning rate. Since full-batch gradients are computationally expensive, we train on a subset of CIFAR 10 (see Appendix A.7 where we also give the hyperparameters and learning curves.). The output margin obtained with the intervention is 5 orders of magnitude smaller than the control experiment: 2.0 10-4 + 2.0 10-4 for the O-Hinge loss and 1.6 10a + 0.50 x 10a for cross-entropy loss. Figure 6 (right) compares the accuracies of the k-NN probes resulting from these training approaches. The O-Hinge loss training achieves only marginal improvement in accuracy (red) over an untrained network (purple), and the training split is accurately clustered only in the latest layers. This confirms the predicted behavior: the intervention leads to a model that exhibits both very small average output margins and very late clustering of the data. Very late clustering of the data implies high prediction depths since the k-NN probe classifications change in the latest layers for many data points.
follows: construct loss function that does not promote
4 Beyond One-Dimensional Picture of Example Difficulty
In this section we transcend the one-dimensional picture of example difficulty by identifying dif- ferent underlying reasons behind the difficulty of an example, in way that is general to different architectures and datasets.
Figure 7 shows that the prediction depth can be different when an input occurs in the training split vs. the validation split. Thus, there two axes of example difficulty:
1. Difficulty of making a prediction when an input the validation set
2. Difficulty of finding commonalities during training with other examples of the same ground truth class
Both axes have a range from "clear" to "ambiguous". In Section 3.1 made for validation points with later prediction depths often inconsistent, with low consensus-
we show that predictions
8

---

K-NN: Ground Truth
K-NN: Consensus Class
1.0
0.8
0.8
Easy
0.6
Ambiguous
0.4
0.4
Ambiguous w/o its label
Looks like different class
0.2
0.2
0.0
0.0
0
1
2
5 Layer
7 8
10
0
2
3
6 7 8 10 Layer
Figure 8: Average k-NN probe confidence (solid lines) and accuracy (dotted lines) for the ground truth class (left) and consensus class (right), in the validation split for examples exhibiting extreme forms of difficulty. Mean values for 100 examples with each form of difficulty. identified as the 100 examples closest to the cornrss in Figure (1eft). This result is for CIFARIO with ResNet18: similar plots for all datascts and architectures are shown Appendix C.7
See Section 4 for the discussion of the result and how can be used to improve
prediction accuracy.
consistency. Conversely, a low prediction depth typically indicates an input with high consensus- consistency. For Axis I we will identify validation points with low prediction depths as "clear" and those with high prediction depths as "ambiigous". We will additionally identify a low or high prediction depth in the training split with examples that are respectively "clear" and "ambiguous" on Axis 2. By making combinations of low/high values of (PDval. PDrrain) we obtain four extremes of example difficulty:
Easy examples: (Low PDval. Low PDTrain). Such examples are often visually typical members of their class and the predicted label nearly always matches the ground truth.
Looks like a different class: (Low PDval. High PD PDrrain). In the validation set, there clear (and nearly always incorrect) classification for such an input, but is difficult to connect such inputs to other examples of their ground truth class during training. Mislabeled examples are of this kind, as are visually confusing images which at first appear to show something else.
Ambiguous unless the label is given: (High PDval. Low PDTrain: These examples are difficult to connect their predicted class in the validation split but easy to connect to their ground truth class during training. These points may, for example, visually resemble both their own class and another class. They are likely be misclassified.
Ambiguous:
(High PDval. High PDTrain). These examples may be corrupted or show an example of rare sub-class. Predictions for these inputs can depend strongly on the random seed used for training and initialization.
In Figure 7 we visualize CIFARIO "Bird" images with the extreme forms of example difficulty for ResNet18, as identified using the prediction depth in the training and validation splits. In the full dataset (left panel) we see that the prediction depth can be very different in the training and validation splits: the two prediction depths are typically similar for points where the consensus class equal to the ground truth (right panel), but can be very different when the consensus class is different from the ground truth (middle panel). This behavior is consistently reproduced for all datasets and architectures in Appendix [.6]
Looking at these examples of the class "Bird" with different difficulty types, we observe that ResNet18 finds small garden birds easiest, while birds in flight against a blue background "look like airplanes", ostriches are "ambiguous without their label" and the "ambiguous" examples are either unclear photographs or examples of rare sub-groups that don't appear frequently in the data. We found the consensus-consiseenee of inputs that are "Ambiguous" or "Ambiguous without its label" to be significantly lower than those of examples that are "Easy" or "Look like a different class".
In order to better understand how networks process examples with diffferntt, extreme forms of example difficulty, Fig. [ examines how the k-NN confidence (fraction of votes) and accuracy of the ground truth class and of the consensus class progress, as validation points pass through the network. "Easy" examples are classified as their consensus class (which is equal to their ground truth class) in all k-NN probes and the confidence in the consensus class steadily increases as data points proceed through the hidden layers. Examples that "look like different class" are also processed as members of their consensus class, similarly to "easy" examples. However, unlike "easy" examples, their consensus classes do not match their ground truth classes. Examples that are "ambiguous without their labels" are initially processed as members of their ground truth classes with intermediate confidence, but in later layers become mistaken for their consensus class, "Ambiguous" examples are

---

processed with low confidence and accuracy in the early layers, for both ground truth and consensus classes. In later layers "ambiguous" examples are recognized, with intermediate confidence and accuracy, as members of the consensus class, which matches the ground truth class for sizeable fraction of "ambiguous" examples.
Improving the prediction accuracy Can the prediction accuracy be improved using our under- standing of how each class of difficult examples are processed by deep models? Figure suggest that k-NN probes intermediate layers may be more accurate than the full deep model for examples that are "ambiguous without their label" (data points closest to the lower right corner of Figure 77) In order to test this hypothesis, we compare the accuracy of the k-NN probe in layer 4 to the full model's prediction for the 100 examples closest to the lower right corner of Figure g We obtain striking improvement in accuracy from 25% to 98% for these examples. This showcases how insights from this study can be directly used to improve prediction accuracy.
Discussion
Summary We have introduced a notion of example difficulty called the prediction depth, which uses the processing of data inside the network to score the difficulty of example. We have shown how the prediction depth is related to the accuracy and uncertainty of a prediction, the adversarial input margin and the output margin of the learned solution, and that data points that are easier according to the prediction depth are also typically learned earlier in training. We have also shown that the difficulty of an example can be both similar, or very different depending on whether an input appears in the validation split or the training split, and described four extremes of example difficulty, For data points that are "aamiigouss without their label", we have demonstrated how returning the k-NN prediction in a middle layer can lead to impressive increases in model accuracy: for CIFARI 10 in R 8 we obtained an increase in accuracy from 25% to 98% for the inputs that are most "ambiguous without their label".
Connecting known phenomena In the literature, the following phenomena are separately reported from different experimental paradigms:
1. Early layers generalize while later layers memorize (Stephenson et al. 2021
2. Model layers converge from input layer towards output layer (Raghu al., 2017
Morcos
et al.] 2018).
3. Deep models learn easy data (Jiang et al. 2021 Toneva et al. 2019 and simple functions first (Hu et al. 2020 Kalimeris et al. 2019).
Following this paper, a coherent and closely related picture emerges:
1. Predictions made in early layers are more likely to be consistent than those made in later lay- ers. Consistent predictions are likely to be correct and the expected accuracy of inconsistent predictions is naturally low (Section 3.T).
2. Data points learned early in training typically have smaller prediction depths than those learned later during training (Section (.2)
3. On average, deep neural networks exhibit wider input and output margins (common measures of "local simplicity") in the vicinity of data with smaller prediction depths (Section 3.3
Pertinence of example difficulty to topics in machine learning Curriculum Learning attempts to treat hard examples differently from easy examples during training. Robustness to distribution shifts that change the relative frequencies of common and rare subgroups in the test set (which we have shown can have different forms of example difficulty) is important for ML Fairness. Methods developed to address heteroscedastic uncertainty typically address example difficulty as a one- dimensional quantity. We expand upon the relevance of our work to these three topics in Appendix D]
Limitations We believe that the results we report stem from deep model's representation, which is hierarchical by construction. We expect that the same results will therefore apply in larger models, larger datasets, and tasks other than image classification, but testing this remains as further work. Although we demonstrate that returning the results of a hidden k-NN can yield dramatic increases in accuracy for examples that are "ambiguous without their label", we otherwise do not explore ways to practically apply the insights we present. In particular, we expressly do not claim that all that is required for good accuracy is to reduce the prediction depth: freezing later layers of the network would not be expected to result in good generalization.
10

---

Funding Transparency Statement
This research was funded by, and undertaken at, Google. All calculations were performed using Google's computer infrastructure.
Acknowledgment
We would like to thank Hanie Sedghi, Ilya Tolstikhin, Ibrahim Alabdulmohsin, Daniel Keysers and Julian Eisenschlos valuable discussions on the topic and Arthur Baldock for proofreading the manuscript.
References
Agarwal, C. and Hooker. (2020). Estimating example difficulty using variance gradients. In ICML, Workshop on Human Interpretabilityy in Machine Learning (WHI).
Alain, G. and Bengio, Y. (2017). Understanding intermediate layers using linear classifier probes. In International Conference Learning Representations (Workshop).
Arpit, D., Jastrzebski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., Maharaj, T., Fischer, A., Courville, A., Bengio, Y., et al. (2017). A closer look at memorization in deep networks. In International Conference on Machine Learning.
Bahri, D., Jiang, H., and Gupta, M. (2020). Deep k-nn for noisy labels. In International Conference on Machine Learning.
Bengio, Y., Louradour, J., Collobert, R., and Weston, J. (2009). Curriculum learning. In Proceedings of International Conference on Machine Leurning.
Carlini, N., Erlingsson, U., and Papernot, N. (2019). Distribution density, tails, and outliers in machine learning: Metrics and applications. arXiv preprint / 13427.
Chatterjee, S. (2019). Coherent gradients: An approach to understanding generalization in gradient descent-based optimization. In International Conference on Learning Representations.
Cohen, G., Sapiro, G., and Giryes, R. (2018). Dnn k-nn: That is the generalize vs. memorize question. In NeurIPS, Workshop on Inlegration of Deep Learning Theories.
Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, L. (2018). Universal transformers. In International Conference on Learning Representations.
Elman, J. (1993). Learning and development in neural networks: The importance of starting small. Cognition, 48(1 48(1):71-99
Feldman, V. and Zhang, C. (2020). What neural networks memorize and why: Discovering the long tail via influence estimation. In Proceedings of the 34th International Conference on Neural Information Processing Systems.
Ghorbani, B., Krishnan, S., and Xiao, Y. (2019). An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning.
Hacohen, G., Choshen, L.,, and Weinshall, D. (2020). Let's agree to agree: Neural networks share classification order real datasets. In International Conference on Machine Learning.
Hacohen, G. and Weinshall, D. (2019). On the power of curriculum learning in training deep networks. In International Conference on Machine Learning-
He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and patlern recognition.
Hooker, S., Courville, A., Clark, G., Dauphin, Y., and Frome, A. (2019). What do compressed deep neural networks forget? arXiv preprint arXiv: 191.0529..
Hooker, S., Moorosi, N., Clark, G., Bengio, S., and Denton, E. (2020). Characterising bias in compressed models. arXiv preprint arXiv:2010.0305.

---

Hu, W., Xiao, L., Adlam, B., and Pennington, J. (2020). The surprising simplicity of the carly-time learning dynamics of neural networks. In Proceedings of the 34th International Conference on Neural Information Processing Systems.
Huang, G., Chen, D., Li, T., Wu, F,, van der Maaten, L.,, and Weinberger, K. (2018). Multi-scale dense networks for resource efficient image classification. In International Conference on Learning Representations.
Jiang, Y., Krishnan, D., Mobahi, H., and Bengio, S. (2018), Predicting the generalization gap in deep networks with margin distributions, In International Conference on Learning Representations.
Jiang, Y., Neyshabur, B., Mobahi, H., Krishnan, D., and Bengio, S. (2020). Fantastic generalization measures and where to find them. International Conference on Learning Representations.
Jiang, 7.,, Zhang, C., Talwar, K., and Mozer, M. C. (2021). Characterizing structural regularities of labeled data in overparameterrized models. In International Conference Machine Learning.
Kalimeris, D., Kaplun, G., Nakkiran, P., Edelman, B.. Yang, T., Barak, B., and Zhang, H. (2019). Sgd on neural networks learns functions increasing complexity. In Advances in Neural Information Processing Systems, volume 32.
Kawaguchi, K., Kaelbling, L. P., and Bengio, Y. (2017). Generalization in deep learning. arXiv preprint arXiv:1710.05466.
Kendall, A. and Gal, Y. (2017). What uncertainties do we need in bayesian deep learning for computer vision? In Proceedings of the 31st International Conference on Neural Information Processing Systems.
Kendall, A., Gal, Y., and Cipolla, R. (2018). Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattem recognition.
Keskar, S., Nocedal, J., Tang, T. P., Mudigere, D., and Smelyanskiy, M. (2017). On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations.
Kolesnikov, A., Beyer, I.., Zhai, X., Puigcerver, J., Yung. J., Gelly, S., and Houlsby, N. (2020). Big transfer (bit): General visual representation learning. In European Conference on Computer Vision.
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images. Technical Report.
Lakshminarayanan, B., Pritzel, A., and Blundell, C. (2017). Simple and scalable predictive uncertainty estimation using deep ensembles. In Proceedings of the 31st International Conference on Neural Information Processing Systems.
Lalor, J. P., Wu, H., Munkhdalai, T., and Yu, H. (2018). Understanding deep learning performance through an examination of test difficulty: A psychometric case study. Proceedings of the Conference on Empirical Methods in Natural Language Processing.
Li, H., Xu, Z., Taylor, G., Studer, C., and Goldstein, T. (2018). Visualizing the loss landscape of neural nets. In Proceedings of the 32nd International Conference on Neural Information Processing Systems.
Liu, S., Wiles-Weed, J., Razavian, N., and Fernandez-Granda, C. (2020a). Early-leariing regulariza- tion prevents memorization of noisy labels. Advances in Neural Information Processing Systems, 33.
Liu, W., Zhou, P.. Wang, Z.. Zhao, Z., Deng, H., and JU. Q. (2020b). Fastbert: self-distilingg bert with adaptive inference time. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6035-6044
Long, P. M. and Sedghi, H. (2019). Generalization bounds for deep convolutional neural networks. In International Conference on Learning Representations.
12

---

Mangalam, K. and Prabhu, V. (2019). Do deep neural networks learn shallow learnable examples first? In ICML, Workshop on Identifying and Understanding Deep Learning Phenomena.
Morcos, S., Raghu, M., and Bengio, S. (2018). Insights on representational similarity in neural networks with canonical correlation. In Proceedings of the 32nd International Conference Neural Information Processing Systems.
Nagarajan, V., Andreassen, A., and Neyshabur, B. (2021). Understanding the failure modes of out-of-distribution generalization. In International Conference on Learning Representations.
Netzer, Y.. Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng. A. Y. (2011). Reading digits in natural images with unsupervised feature learning. Technical Report.
Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. (2017). Exploring generalization in deep learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems.
Papernot, N. and McDaniel, P. (2018). Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint 1rXiv:1803.04770
Pennington, J. and Bahri, Y. (2017). Geometry of neural network loss surfaces via random matrix theory, In International Conference on Machine Learning.
Raghu, M., Gilmer, J., Yosinski, J., and Dicksiick,,,in, J. (2017). Sveca: singular vector canonical correlation analysis for deep learning dynamics and interpretability. In Proceedings of the 31st International Conference on Neural Information Processing Systems.
Recht, B., Roelofs, R., Schmidt, L., and Shankar, V. (2019). Do imagenet classifiers generalize to imagenet? International Conference on Machine Learning.
Sagun, L.,, Bottou, L., and LeCun, Y. (2016). Eigenvalues of the hessian deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476.
Sagun, L., Evei, U., Guney, V. U., Dauphin, Y., and Bottou, L. (2018). Empirical analysis of the hessian of over-parametrized neural networks. International Conference on Learning Representations (Workshop).
Sanger, T. D. (1994). Neural network learning control of robot manipulators using gradually increasing task difficulty. IEEE transactions on Robotics and Automation, 10(3):323-33..
Schwartz, R., Stanovsky, G., Swayamdipta, S., Dodge, J., and Smith, N. A. (2020). The right tool for the job: Matching model and instance complexities. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics.
Simonyan, K. and Zisserman, A. (2015). Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations.
Smith, S. L., Dherin, B., Barrett, D. G., and De, S. (2021). On the origin of implicit regularization in stochastic gradient descent. In International Conference on Learning Representations.
Smith, S. L..,
Kindermans, P.-.,, Ying, C., and Le, Q. V. (2018). Don't 't decay the learning rate, increase the batch size. In International Conference on Learning Representations.
Smith, S. and Le, Q. (2018). bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 1911:2822-2288 2878.
Stephan, M., Hoffman, M. D., Blei, D. M., et (2017). Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1-35.
Stephenson, C., suchismita padhy, Ganesh, A., Hui, Y., Tang, H., and Chung, S. (2021). On the geometry of generalization and memorization in deep neural networks. International Conference on Learning Representations.
13

---

Teerapitayynnon, S., McDanel, B., and Kung, H.-T. (2016). Branchynet: Fast inference via early exiting from deep neural networks. In International Conference on Pattern Recognition.
Toneva, M., Sordoni, A., des Combes, R. T., Trischler, A., Bengio, Y., and Gordon, G. J. (2019). An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations.
Unterthiner, T., Keysers, D., Gelly, S., Bousquet, O., and Tolstikhin, I. (2020). Predicting neural network accuracy from weights. arXiv preprint arXiv:2002.11448.
Wen, Y., Tran, D., and Ba, (2019). Batchensemble: an alternative approach efficient ensemble and lifelong learning. In International Conference on Learning Representations.
Wenzel, F., Snoek, J., Tran, D., and Jenatton, R. (2020). Hyperparameter ensembles for robustness and uncertainty quantification. Proceedings of the 34th International Conference on Neural Information Processing Systems.
Wu, X., Dyer, E., and Neyshabur, B. (2021). When do curricula work? In International Conference on Learning Representations.
Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-mmist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint (Tfi::770.00744
Xin, J., Tang, R., Lee, J., Yu, Y., and Lin, (2020). Deebert: Dynamic early exiting for accelerating bert inference. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics.
Yao, Z.,, Gholami, A., Keutzer, K., and Mahoney, M. (2020). Pyhessian: Neural networks through the lens of the hessian. In International Conference on Machine Learning (Workshop).
Zielinski, P., Krishnan. S., and Chatterjee, S. (2020). Weak and strong gradient directions: Explaining memorization, generalization, and hardness of examples at scale. arXiv preprint arXiv:2003.07-22 07442......
14


Reviews:
[{"review_id": "zX-SAjJ2PRf", "reviewer": "Reviewer_nMGW", "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).\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Strengths:\n1. 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.\n\n2. 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.\n\nWeaknesses:\n1. 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.\n\n2. 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.\n\n3. 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?).\n\nMinor points (mostly typos and clarity issues):\n- L50 and L306: authors refer to \"four deep learning phenomena\" but only 3 are listed and appear in the paper\n- 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.\n-  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?\n- L163: \"of in\"\n- What is actually plotted in the 2d histograms? Is it the percentage of the dataset that has specific properties?\n- 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.\n- Fig 8 caption: \"extremes\" -> \"extreme\"\n- Fig 8: what are the std errors across these 100 examples?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "umh_iAkhIF1", "reviewer": "Reviewer_SfKb", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Strengths:\n- 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. \n\n- The paper includes a number of nice visualiizations of various properties of the prediction depth measure.\n\n- Most experiment descriptions were reasonably clear.\n\n- 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.\n\n- 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. \n\n- 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.\n\nWeaknesses: \n- 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.\n\n- 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.\n\n- 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. \n\n- 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.\n\n\nConcrete points for improvement:\n\n- 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.\n\n- 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.  \n\n- 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.\n\n\nOther questions:\n- 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?\n\n- 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, theoretical work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "YxU4QkgfIS", "reviewer": "Reviewer_Cip6", "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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "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\"). \n\nThe 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? \n\nAs 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.\n\nThis 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).\n\nThe 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.  \n\n-----\npost-rebuttal:\n\nAs 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As in the main review.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2iL7XfJEs1", "reviewer": "Reviewer_GF8b", "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:\n - difficulty of an example, as (qualitatively) measured by a human\n - accuracy and consistency\n - 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)\n - margin\nand conclude that PD is useful for predicting these quantities", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "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).\n\nThe 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\n\nThe empirical relationship between PD and other quantities, observed in this case on vision tasks, is of significant interest.\n\nDuring reading, I had the following questions:\n1. 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.\n2. 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). \n\nI would recommend to accept it for NeurIPS, provided that these questions are satisfyingly answered.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}]

Author rebuttal:

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)