As shown in recent research, deep neural networks can perfectly fit randomly labeled data, but with very poor accuracy on held out data. This phenomenon indicates that loss functions such as cross-entropy are not a reliable indicator of generalization. This leads to the crucial question of how generalization gap should be predicted from the training data and network parameters. In this paper, we propose such a measure, and conduct extensive empirical studies on how well it can predict the generalization gap. Our measure is based on the concept of margin distribution, which are the distances of training points to the decision boundary. We find that it is necessary to use margin distributions at multiple layers of a deep network. On the CIFAR-10 and the CIFAR-100 datasets, our proposed measure correlates very strongly with the generalization gap. In addition, we find the following other factors to be of importance: normalizing margin values for scale independence, using characterizations of margin distribution rather than just the margin (closest distance to decision boundary), and working in log space instead of linear space (effectively using a product of margins rather than a sum).
 Our measure can be easily applied to feedforward deep networks with any architecture and may point towards new training loss functions that could enable better generalization. Generalization, the ability of a classifier to perform well on unseen examples, is a desideratum for progress towards real-world deployment of deep neural networks in domains such as autonomous cars and healthcare. Until recently, it was commonly believed that deep networks generalize well to unseen examples. This was based on empirical evidence about performance on held-out dataset. However, new research has started to question this assumption. Adversarial examples cause networks to misclassify even slightly perturbed images at very high rates BID9 BID22 . In addition, deep networks can overfit to arbitrarily corrupted data BID10 , and they are sensitive to small geometric transformations BID2 BID6 . These results have led to the important question about how the generalization gap (difference between train and test accuracy) of a deep network can be predicted using the training data and network parameters. Since in all of the above cases, the training loss is usually very small, it is clear that existing losses such as cross-entropy cannot serve that purpose. It has also been shown (e.g. in BID10 ) that regularizers such as weight decay cannot solve this problem either.Consequently, a number of recent works BID21 BID4 BID23 BID1 have started to address this question, proposing generalization bounds based on analyses of network complexity or noise stability properties. However, a thorough empirical assessment of these bounds in terms of how accurately they can predict the generalization gap across various practical settings is not yet available.In this work, we propose a new quantity for predicting generalization gap of a feedforward neural network. Using the notion of margin in support vector machines (Vapnik, 1995) and extension to deep networks BID5 , we develop a measure that shows a strong correlation with generalization gap and significantly outperforms recently developed theoretical bounds on Test Acc. : 55.2% Test Acc. : 70.6% Test Acc. : 85.1% Figure 1 : (Best seen as PDF) Density plots (top) and box plots (bottom) of normalized margin of three convolutional networks trained with cross-entropy loss on CIFAR-10 with varying test accuracy: left: 55.2%, middle: 70.6%, right: 85.1%. The left network was trained with 20% corrupted labels. Train accuracy of all above networks are close to 100%, and training losses close to zero. The densities and box plots are computed on the training set. Normalized margin distributions are strongly correlated with test accuracy (moving to the right as accuracy increases). This motivates our use of normalized margins at all layers. The (Tukey) box plots show the median and other order statistics (see section 3.2 for details), and motivates their use as features to summarize the distributions. generalization 2 . This is empirically shown by studying a wide range of deep networks trained on the CIFAR-10 and CIFAR-100 datasets. The measure presented in this paper may be useful for a constructing new loss functions with better generalization. Besides improvement in the prediction of the generalization gap, our work is distinct from recently developed bounds and margin definitions in a number of ways:1. These recently developed bounds are typically functions of weight norms (such as the spectral, Frobenius or various mixed norms). Consequently, they cannot capture variations in network topology that are not reflected in the weight norms, e.g. adding residual connections BID10 without careful additional engineering based on the topology changes. Furthermore, some of the bounds require specific treatment for nonlinear activations. Our proposed measure can handle any feedforward deep network. 2. Although some of these bounds involve margin, the margin is only defined and measured at the output layer BID4 BID21 . For a deep network, however, margin can be defined at any layer BID5 . We show that measuring margin at a single layer does not suffice to capture generalization gap. We argue that it is crucial to use margin information across layers and show that this significantly improves generalization gap prediction. 3. The common definition of margin, as used in the recent bounds e.g. BID21 , or as extended to deep networks, is based on the closest distance of the training points to the decision boundary. However, this notion is brittle and sensitive to outliers. In contrast, we adopt margin distribution BID7 BID13 Zhang & Zhou, 2017; by looking at the entire distribution of distances. This is shown to have far better prediction power. 4. We argue that the direct extension of margin definition to deep networks BID5 , although allowing margin to be defined on all layers of the model, is unable to capture generalization gap without proper normalization. We propose a simple normalization scheme that significantly boosts prediction accuracy. We have presented a predictor for generalization gap based on margin distribution in deep networks and conducted extensive experiments to assess it. Our results show that our scheme achieves a high adjusted coefficient of determination (a linear regression predicts generalization gap accurately). Specifically, the predictor uses normalized margin distribution across multiple layers of the network. The best predictor uses quartiles of the distribution combined in multiplicative way (additive in log transform). Compared to the strong baseline of spectral complexity normalized output margin BID4 , our scheme exhibits much higher predictive power and can be applied to any feedforward network (including ResNets, unlike generalization bounds such as BID4 BID21 BID1 ). We also find that using hidden layers is crucial for the predictive power. Our findings could be a stepping stone for studying new generalization theories and We use an architecture very similar to Network in Network BID16 ), but we remove all dropout and max pool from the network.Layer Index Layer Type Output Shape 0 Input 32 × 32 × 3 1 3 × 3 convolution + stride 2 16 × 16 × 192 Residual plots for all explanatory variables, row: h0, h1, h2, h3, column: lower fence, Q 1 , Q 2 , Q 3 , upper fence. lower fence is clipped because distance cannot be smaller than 0. The residual is less evenly distributed as are in other two settings; this fact is well reflected in the cluster along the x axis and in theR 2 ; we speculate that this is due to not having diverse enough generalization gap in the models trained to cover the entire space of the "model" unlike in the other two settings. 3.45e-13 3.04e-16 9.21e-9 4.07e-4 6.59e-3 h3 4.14e-13 0.60 0.27 7.14e-3 2.4e-10 Table 6 : F score (top) and p-values (bottom) for all 20 variables. Using p = 0.05, we see that the null hypotheses are not rejected for 4 of the variables. We believe having a more diverse generalization behavior in the study will solve this problem. Residual plots for all explanatory variables, row: h0, h1, h2, h3, column: lower fence, Q 1 , Q 2 , Q 3 , upper fence. lower fence is clipped because distance cannot be smaller than 0. The residual is fairly evenly distributed around 0. There is one outlier in this experimental setting as shown in the plots. 9 APPENDIX: SOME OBSERVATIONS AND CONJECTURES Everythig here uses the full quartile description. DISPLAYFORM0
We develop a new scheme to predict the generalization gap in deep networks with high accuracy. Authors suggest using a geometric margin and layer-wise margin distribution for predicting generalization gap. Empirically shows an interesting connection between the proposed margin statistics and the generalization gap, which can be used to provide some prescriptive insights towards understanding generalization in deep neural nets. 