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 Carlinii 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(,, v)}
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 s.
(*,((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-conssistnns 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
CIFAR1O
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 to 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 [ 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": "qYaaRSHVtdB", "reviewer": "Reviewer_LUjh", "summary": "Authors proposed a measurement named prediction depth for each data point, that is defined as the index of a layer after which a KNN classifier gives the same predictions as the final prediction of the network. Experimental evidence shows that the prediction depth is correlated to the example learning difficulty and visualizes examples from four extremes, classified by the predict depth in training and the one in validation.", "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": "The proposed method is novel and proved to be capable of estimating the example difficulty. It also has the potentials to explain some phenomena in deep learning, as discussed in Section 5. But there are several points that I didn't understand and found strange:\n- There is no analysis on prediction depth for training data. Each figure is based on the random splits of training and validation sets, and the prediction depths are averaged when the data point appears in the validation set. As authors stated, there are \"two notions of computational difficulty\", but only one notion is analyzed. \n- I found it very difficult to understand Figure 3 and related figures, which contain too much information. The captions of figures are quite long and difficult to understand. Moreover, the histograms (the color bars), representing the frequency of correct predictions, have not been much discussed. As well, the size of markers in Figure 4, showing the fraction of the data set, has not been discussed either. It takes me much time to understand these presentations but they were not very useful. \n- It seems like the example difficulty is just one intuitive notion. Authors may need a better way to show its agreement to the proposed prediction depth.\n- All Section 3 seem to talk about the example difficulty, but from different views. Some more concise subtitles, or a better organization may help readers to better understand the content. The end of Section 2 is of the same subject as Section 3, but is in another section. \n\nOverall, this paper introduces a novel notion, which relates to the example difficulty and shows the potentials to connecting some phenomena in deep learning, while some details and the clarity need to be improved.  \n\nOne open question inspired by this paper: If the first layer can be quite discriminative for classifying the objects, what do the rest of layers do? Imagine this, some easy examples are already clustered together in the early layer while some difficult ones are not. At the late layer, these easy examples are still clustered but the difficult ones join them. This may be very interesting to analyze the transformations done by intermediate layers for the difficult examples.", "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": "h_X5zmG9Ii", "reviewer": "Reviewer_YcZq", "summary": "Intuitively, some examples are \"harder\" to learn than others.  Currently, there are two ways of measuring \"hardness\": the \"statistical view\", in which an example is hard if its classification is sensitive to small changes to the training set; and the \"learning view\", in which an example is hard if its label is learned only at the end of the optimization process.  This paper proposes a new \"computational view,\" in which an example is considered hard if many layers of processing are required to produce the prediction.   Computational hardness is formalized through a metric called \"prediction depth,\" which is the depth at which the prediction of a KNN classifier operating on the intermediate hidden representations starts to agree with the network's ultimate prediction.  For instance, consider a 20-layer trained network and a training example for which the network predicts \"airplane.\"  Suppose that a KNN classifier operating on the first-layer hidden representations predicts this example as \"dog,\" and a KNN  classifier operating on the second-layer hidden representations predicts this example as \"cat\", while KNN classifiers on layers 3 through 20 predict this example as \"airplane.\"  Then the prediction depth is 3.  The intent is: the higher the prediction depth, the harder the example.\n\nThe paper first confirms that prediction depth is robust across random seeds and relatively robust across architectures, and that visually 'easy' images have low prediction depths and visually \"hard\" images have high prediction depths.  Then the paper demonstrates that the \"computational hardness\" of prediction depth is correlated with the \"statistical hardness\" of sensitivity: examples with low prediction depths tend to be classified the same regardless of perturbations to the training dataset (e.g. bootstrap resampling), whereas examples with high prediction depths are not robust to changes in the training dataset.  Then the paper demonstrates that the \"computational hardness\" of prediction depth is correlated with the pre-existing notion of \"learning speed\" hardness: examples with low prediction depths tend to be learned earlier in training, whereas examples with high prediction depths are not learned until late in training.  Then the paper demonstrates that examples with low prediction depths have lower 'output margins' (the difference in logit between the predicted class and the other classes) as well as lower 'input margins' (the L2 distance in input space to the nearest adversarial perturbation).  \n\n", "questions": "", "limitations": "", "rating": 7, "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": "Prediction depth seems like an interesting metric for measuring hardness of examples that could become a nice tool in the deep learning literature.  The method is original (to my knowledge), and the paper is very clearly written.  Appendix D lists some potential applications of this metric, and it's not hard to imagine others.", "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": "3"}, "extra_text": {}}, {"review_id": "aGDb6NtjtBn", "reviewer": "Reviewer_UY6d", "summary": "This paper explores how  deep feed-forward or convolutional networks perform image classification tasks. The authors consider the layers of a trained network as a sequence of embeddings, from which nearest-neighbour predictors can be computed from the training examples and their predicted class. This allows one to compute successive class predictions for a given example, as it gets processed from the input layer to the final softmax. They introduce the Prediction Depth of an example as the earliest layer where its final classification is reached and stays without change. \n\nExperimenting with three network architectures and four image datasets, the authors suggest that the Prediction Depth of an example is a good estimator of its accuracy, learning difficulty, and confidence (in term of distance both from the class separator and closest adversarial examples). They also propose that it is consistent, for a given data point, over different trained models and (to a lower degree) architectures.\n\nFinally, they show how their findings relate to known properties of neural networks, and define a new typology of difficult examples in image classification.   ", "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": "**Originality** \n\nThe paper relies on existing techniques and architectures. The authors provide references. Prediction depth is a new indicator, but related metrics have been proposed by others. The main original contribution is the use of prediction depth as an estimator of example difficulty, and the suggestion that it can summarize several important concepts, like prediction accuracy, model perplexity and learning speed. \n\n**Clarity**\n\nThe paper is complete, well organized, and provides a detailed bibliography. It could be made clearer by reorganizing the figures, so that they are closer to the sections they illustrate. Since the setting and use of kNN predictors over a trained model is central to this work, it would deserve a paragraph at the beginning of paper. Right now, the information is scattered  in section 2 and appendix A, which makes the paper difficult to understand on first read. Appendix A.3 features hyperparameter optimization, but more importantly describes the training schedules that were actually used on all datasets and architectures. The name of the section should reflect this, and learning curves for all datasets should be provided. In figure 5, there are epochs, how are they defined? \n\nThe word \"consistency\" is used in figure 2 and 3 with different meanings. The paragraph starting on line 135 could be made clearer by clarifying between 'accuracy' and 'generalization'. Part C of the appendix is made of very short paragraphs referencing additional graphs: for instance, C.5 is just a reference to figures C31 to C34. It might be better to directly refer to the figures in the main. \n\n**Quality** \n\nThe ideas and intuitions proposed in the paper are very interesting, and definitely worth pursuing. However, the supporting experiments are not always convincing, and several questions about the experiments, the definition of prediction depth, and the experimental support of claims, need to be clarified. I group them into four concerns that, I think, should be addressed.  \n\n**Concern 1: Overfit:** \nAll the datasets feature about 50 000 examples. Appendix A.3 states that training used about 10 000 steps, over batches of 256 examples. This means each example in the dataset was seen about 50 times. This, together with the use of large learning rates and no weight decay, might raise concerns about overfitting. Also, figure 5 displays a learning curve (actually, an average of five experiments) which shows a test set accuracy going up until epoch 20, and then falling down to an asymptote, while training set accuracy goes on improving. This, again, might signal overfit. Finally, in several cases, computing prediction depths on training or validation samples result in different conclusions. This might be an important finding, but it is also a telltale sign of an overfitting model. Can overfit be ruled out in these experiments? This can be done in a number of ways: learning curves, cross-validation, switching to larger datasets such as imageNet, training models on less steps and seeing if the results still hold...\n\nMaking sure that the model does not overfit is all the more important as the training examples serve as the basis for the kNN predictors, and memorisation of training data will influence prediction depth computation. This could be mitigated by using held-out examples as the basis for the kNN - i.e. compute the nearest neighbours of examples not seen at training, e.g. from the validation set, and see whether this results in different prediction depths (more on this in the next paragraph).\n\n**Concern 2: Robustness of the definition of prediction depth:** \nPrediction depth is defined by two criteria: \"first correct prediction\" and \"no change until output\", how important is the second? In other words, if an example is correctly classified from layer 2 to 10, except on 9, should it really be depth 10? An analysis of whether such cases exist, and whether the conclusions are robust to such changes in the definition of prediction depth, would be very interesting, and make prediction depth a more robust idea.\n\nkNN are computed from the training examples. This will not scale to larger training sets. Besides, the use of training data might raise concerns with overfitting, or the relation between prediction depth and the distribution of training data. How robust is the estimation of prediction depth with respect to downsampling the kNN base (e.g. from 50k to 10k), or to using different examples (e.g. the validation set) as the kNN base? Also, a discussion about the practical aspects of computing prediction depth would be very interesting.\n\n**Concern 3: Experimental support for claims:** \nThe first claim in 2.2 seems supported by 8 examples, and 4 datasets. This is very weak. Can other examples of intuitively hard or easy examples and datasets be constructed? Maybe by using predictions from a very simple baseline classifier as a measure of example difficulty, and adding increasing amount of noise on one sample (as was done in CIFAR 10) and seeing how this impacts prediction depth?\n\nFor consistency over architecture (fig. 2), predictions depths are averaged over an ensemble of different models. These averages are then shown to be correlated over different architectures. This is an important result, but unless the variance of prediction depth for different models with the same architecture is very small, it does not prove consistency. Showing that prediction depth is robust to changes in the model and the architecture is required to support the claim that prediction depth measures example difficulty, independently of the model used to compute it. \n\nThe visual analysis of correlation between accuracy or learning speed and average prediction depths is complicated by the fact that many distributions tend to concentrate around a few (usually extreme) values. Since many distributions are bimodal, it might be advantageous to cluster the results into high and low values, and compute simpler, binary, statistics. This would be easier to follow, but not less relevant.\n\n**Concern 4: Example difficulty vs nearest neighbours:** \nPrediction depth of an example is a function of the predictions of its nearest neighbours, according to the embeddings defined by  each layers. When a low prediction depth is observed it might be because, after each layer, the (potentially new) neighbours of the examples always predict the same class. I believe this is the original intuition for prediction depth. But it could also be because the nearest neighbours just remain the same from layer to layer, because the point sits in a less densely sampled part of feature space (with respect to the base vectors of kNN predictors). Classifying such examples as 'low difficulty' is counter-intuitive, and this might be a weakness in the definition of prediction depth. Is it possible to measure how frequently this happens? Intuitively, the high dimension of layer embedding should make this situation frequent, but the fact that training vectors often lie close to a low dimension manifold mitigates this. \n\nIf such a problem occurred, solutions could be to vary the kNN base vectors from layer to layer, or to compute the predicted class from a random sample of the k nearest neighbors (e.g. take the 30 nearest, sample 15 randomly, and compute the class from them).\n\n**Significance**\n\nDespite the experimental concerns, this is an important paper, which potentially impacts several fields of research, from semi-supervised learning to interpretability. Improving the experiments will result in a very good paper, that definitely fits in a major conference.\n\n**Overall**\n\nThe ideas proposed in this paper are important and interesting, and the suggestion that prediction depth in a trained model can serve as a useful proxy for interpreting data complexity is very thought-provoking. Unfortunately, the definition of the prediction depth and some of the authors' claims should be better supported by the experiments. Also, some of the results might be tainted by overfitting over a small dataset and use of training data as the basis of nearest neighbour calculations.\n\nI believe more experimental confirmation is needed before this paper can be published. Hence my rating of 4, which I would be **very** happy to increase if better experimental support of claims and definitions is provided.  \n\n**Typos**\n\nBibliographical references do no seem to follow the NeurIPS formatting\n\nl. 19 : behaviour\n\nl. 67: NLU (Natural Language Understanding?)\n\nl. 163: of in a particular\n\nl. 156: the the\n\nl.198: ref should be C4 ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed. It might be worth stressing the fact that the approach is specific to feed-forward and convolutional networks performing classification tasks, over supervised datasets.  ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new metric of example "hardness" with a computational flavor---the number of layers of representation processing before which a KNN classifiers begins to agree with the correct label. The reviewers all agree that the paper is interesting, clear, and introduces a suitably novel and important idea. While the reviewers disagree about the sufficiency of the experiments, they all see positive aspects to the papers and none argue for rejection. The authors have received considerable feedback throughout this process and I hope that they will strengthen the paper accordingly for the camera ready version. 
Decision: Accept (Poster)