title: Traces of Class/Cross-Class Structure Pervade Deep Learning Spectra
authors: Vardan Papyan
text: 
  
  
  
  
  
  ?
  
  Traces of Class/Cross-Class Structure 
   Pervade Deep Learning Spectra
      Vardan Papyan papyan@stanford.edu 
  
  Department of Statistics
  
  Stanford University
  
  Stanford, CA 94305, USA
        ;  
  ==============================================================================================================
  
  
  
  
  Numerous researchers recently applied empirical spectral analysis to the study of modern deep learning classifiers. We identify and discuss an important formal class/cross-class structure and show how it lies at the origin of the many visually striking features observed in deepnet spectra, some of which were reported in recent articles, others are unveiled here for the first time. These include spectral outliers, “spikes”, and small but distinct continuous distributions, “bumps”, often seen beyond the edge of a “main bulk”.
  
  The significance of the cross-class structure is illustrated in three ways: (i) we prove the ratio of outliers to bulk in the spectrum of the Fisher information matrix is predictive of misclassification, in the context of multinomial logistic regression; (ii) we demonstrate how, gradually with depth, a network is able to separate class-distinctive information from class variability, all while orthogonalizing the class-distinctive information; and (iii) we propose a correction to KFAC, a well-known second-order optimization algorithm for training deepnets.
  
  
  
  deep learning, Hessian, spectral analysis, low-rank approximation, multinomial logistic regression
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
  
  
  
   §.§ Empirical measurements of deepnet spectra
  
  Recently there has been a surge of interest in measuring the spectra associated with deep classifying neural networks. <cit.>, <cit.> and <cit.> measured the eigenvalues of the Hessian of the parameters averaged over the training data. They plotted histograms of eigenvalues and observed a bulk, together with a few large outliers. We define these somewhat informally (see also Figure <ref>):
  
  
      A collection of eigenvalues which, when displayed in a histogram form, seemingly follows a continuous distribution.
  
  
  
  
      A collection of eigenvalues, each individually isolated away from the other eigenvalues.
  
  
  Crucially, <cit.> observed that the number of outliers in the spectrum of the Hessian is often equal to the number of classes C. Their observation was supported by <cit.> who noticed that the eigenvectors corresponding to these C outliers span approximately the gradients of stochastic gradient descent (SGD). <cit.> developed a rigorous attribution methodology which attributed these C outliers to C unsubtracted class means of gradients. <cit.> alluded to yet another related phenomenon–training deepnets is successful even when confined to low dimensional subspace of parameters <cit.>.
  
  <cit.> experimented with: (i) two-hidden-layer networks, with 30 hidden units each, trained on synthetic data sampled from a Gaussian Mixture Model data; and (ii) one-hidden-layer networks, with 70 hidden units, trained on MNIST. Their exploration was limited to architectures with thousands of parameters–orders of magnitude smaller than state-of-the-art architectures such as VGG by <cit.> and ResNet by <cit.> that have tens of millions, hundreds of millions or close to a billion parameters <cit.>. In the absence of other deeper insights, phenomena observed in such small-scale `academic' examples could not be expected to persist in large-scale real-world examples. In the last year, it became possible to study spectra of deepnet Hessians at full-scale. <cit.> used this to observe  that the patterns seen in previous small-scale examples persist even in state-of-the-art deepnets.
  
  In parallel, <cit.> studied the evolution of the full spectrum throughout the epochs of SGD, investigating the effects of skip connections, batch normalization and learning rate drops on properties of outliers and bulk. In addition to studying the spectrum of the full Hessian, <cit.> measured the spectrum of the layer-wise Fisher Information Matrix (FIM). They observed a bulk-and-outliers structure, and a closer inspection of their results shows that there is in fact more than just one bulk. <cit.>, in addition to studying the spectrum of the Hessian, also studied the spectrum of the covariance of gradients, observing a bulk-and-outliers structure in both cases. They showed how SGD hyperparameters affect the magnitude of the spectral norm and the condition number of both matrices.
  
  There were also measurements in the literature of quantities other than the Hessian, FIM, and covariance of gradients. <cit.> measured extensively the spectrum of deepnet weights throughout the layers. Their plots sometimes show a set of outliers isolated from a bulk and closer inspection suggests occasionally the presence of another small bulk beyond the main bulk. <cit.> proposed a novel regularization scheme for training deepnets and investigated its effect on the spectra of features, which they show exhibit a bulk-and-outliers structure. <cit.> measured the spectrum of the backpropagated errors and showed again a set of outliers isolated from a bulk.
  
  
  
  
  
   §.§ Initial theoretical studies
  
  Mathematically oriented researchers tried to leverage Random Matrix Theory (RMT) to generate features similar to the ones observed in practice and study them. <cit.> decomposed the Hessian into two components, the FIM  and a residual , assumed that the eigenvalues of  are distributed according to the Marchenko-Pastur law and those of  according to the semi-circle law, and studied the predicted spectrum of the Hessian. <cit.> calculated the Stieltjes transform of the spectral density of the FIM for a single hidden layer neural network with squared loss and normally distributed weights and inputs. <cit.> studied the deviation of the train Hessian from the population Hessian, as a function of the ratio of sample size to number of parameters. They assumed the spectrum of the Hessian has a bulk, originating from the Gaussian Orthogonal Ensemble, with several outliers.
  
  The loss surface of deepnets changes depending on the width of the network <cit.>. Mathematically oriented researchers therefore tried to leverage large-width limits to prove claims about deepnet spectra. <cit.> calculated the mean, variance and maximum of the FIM eigenvalues. <cit.> and <cit.> used Feynman diagrams to study the training dynamics of SGD, calculating the spectra of the Hessian and the Neural Tangent Kernel (NTK) <cit.>. <cit.> calculated the moments of the Hessian throughout training and showed how the FIM and  are asymptotically mutually orthogonal.
  
  At the present time, existing spectral measurements display a wide variety of features (bulk shapes, outliers, secondary mini-bulks, etc.). It seems fair to say that existing theoretical studies reproduce certain of these features. However, the connections between formal analysis and observed features are so far incomplete. In fact, it is an ongoing activity to propose generative models exhibiting the different observed phenomena.
  
  
  
  
  
   §.§ Why are many researchers measuring deepnet spectra?
  
  In doing spectral analysis of each of these fundamental objects–Hessian, FIM, features, backpropagated errors, and weights–researchers hope to gain deeper insights into deepnet behaviour. Many researchers believe that such spectral features, once better understood, will provide clues to improvements in deep learning training or classifier performance <cit.>. 
  
  
  
  
   §.§ Open questions
  
  Our goal in this work is the answer the following fundamental questions:
  
  
      
     Cause attribution: Can we say what causes outliers, mini-bulk(s) and bulk(s) in various deepnet spectra? Can we explain the number of eigenvalue outliers? Can we explain why the largest outlier is much farther out?
      
     Ubiquity: Why are these patterns pervasive in spectra across a variety of deepnets and variety of objects (features, backpropagated errors, gradients, weights, FIM, Hessian)?
      
     Significance: Are these patterns mere artifacts or do they convey meaningful clues? If meaningful, how can we best use the hints they give?
  
  
  
  
  
  
  
   §.§ Insights from three-level hierarchical structure
  
  In previous work, <cit.> introduced a three-level hierarchical structure for deepnet gradients. He then introduced its connection to some of the spectral patterns in the FIM mentioned above. This work shows how this three-level hierarchical structure can be utilized to explain the spectra of all the fundamental quantities in deep learning, not just the gradients.
  
  
  
  
  
   §.§ A pattern covering all cases
  
  We now make clear the main spectral features we will be discussing and explaining, through a pattern schematized in Figure <ref>. This pattern applies to any of the spectral settings mentioned earlier or any of the several new settings to be discussed below. The pattern consists of:
  
      
    * A bulk;
      
    * C(C-1) eigenvalue outliers, i.e., eigenvalues outside the main bulk (for the sake of brevity we will refer to them as C^2 outliers);
      
    * C-1 eigenvalue outliers situated at still larger amplitudes; and
      
    * A single isolated outlier larger still.
  
  The C^2 outliers may appear either as separated spikes, or alternatively as what we call a mini-bulk: an approximately continuous distribution rather than a series of separated spikes. We emphasize the schematic nature of the above description; the exact appearance of a spectral plot will differ from situation to situation.
  
  
  
  
  
  
  
  
   §.§ Class block structure
  
  Our first goal in this work is to explain what causes this ubiquitous pattern to emerge. To this end, we need the following definitions.
  
  
  
      An array of vectors {_̌I }_I exhibits a (balanced[Imbalanced structure would result if different classes c had different numbers of examples per class N_c. We only study the balanced case, where N_c = N_c',  ∀ c,c'.]) class block structure when the indices have the form I=(i, c), where 1 ≤ i ≤ N runs across the indices of examples in a certain class, and 1 ≤ c ≤ C runs across the class indices.
  
  
  
  
  
  [Training examples]
      Training examples in standard class-balanced machine learning datasets such as CIFAR10 exhibit class block structure. For example, CIFAR10 has a total of 50000 training vectors, which include 5000 examples in class `cat', 5000 examples in class `dog', etc. We denote the i'th example in the c'th class by _i,c.
  
  Let f(·) be some fixed function. Consider an array {_̌i,c}_i,c, where _̌i,c = f(_i,c). Such an array inherits the class block structure from the train examples _i,c.
  [Features]
      Consider the post-activations (also called features) at some fixed layer l of a deepnet. They exhibit a class block structure. Indeed, they are functions of the examples and hence they inherit the class organization. The concatenation of such features across the layers also exhibits such structure. We denote the l'th layer features of _i,c by _i,c^l and their cross-layer concatenation by _i,c.
  
  [Gradients]
      The gradients of the loss () with respect to the parameters of the model ,
      
      ℓ( f(_i,c;), _c ),
  
      inherit the class block structure from the examples _i,c.
  
  
  
  
  
  
   §.§ Cross-class block structure
  
  Assume we are using cross-entropy loss,
  
      (θ) = _i,c,c'_i,c,c' = - _i,c,c' y_i,c,c'log(p_i,c,c'),
  
  where p_i,c,c' is the probability under the `logistic' or `softmax' model, that the i'th example in the c'th class belongs to c'. Similarly, y_i,c,c' is the ground truth probability of the i'th example in the c'th class belonging to c', which is equal to the Kronecker delta function, δ_c=c'. The interpretation of the second subscript (c') is different than that of the first subscript (c). The first denotes the actual class of that observation; while the second denotes the classes enumerated in applying the cross-entropy loss. In what follows, c' will generally denote such a cross-entropy class, or cross-class. c' generally represents a would-be class, as distinguished from c, the actual observed label class.
  
  
  
  
  
      An N × C × C array of vectors  _̌i,c,c' exhibits a (balanced) cross-class block structure when it is indexed by a three-tuple, (i, c, c'), where 1 ≤ i ≤ N runs across the indices of examples in a certain class, 1 ≤ c ≤ C runs across the class indices, and 1 ≤ c' ≤ C runs across the cross-class indices.
  
  
  [Losses]
      The losses _i,c,c' exhibit cross-class structure.
  
  [Extended gradients]
      The “ordinary” gradients of the loss, associated with an example _i,c, have the form:
      
      _i,c,c = ℓ( f(_i,c;), _c ) = f(_i,c;)^ (_i,c - _c);
  
      they exhibit class block structure but not cross-class block structure. We define an extended gradient, denoted _i,c,c', which does exhibit cross-class block structure. In its definition, we replace in the above equation the actual observed one-hot vector _c with a counterfactual one-hot vector corresponding to a would-be observation _c':
      
      _i,c,c' = ℓ( f(_i,c;), _c' ) = f(_i,c;)^ (_i,c - _c').
  
      Later we will see that the Fisher Information Matrix is a (weighted) second moment of extended gradients.
  
  [Backpropagated errors]
      The derivative of the loss with respect to the output of some fixed layer l, also known as the backpropagated error, provides yet another array of vectors exhibiting cross-class block structure, provided we consider derivatives associated with all possible cross-class labels. The concatenation of backpropagated errors across layers also exhibits such structure. The l'th layer backpropagated error induced by example _i,c will be denoted _i,c,c'^l; the cross-layer concatenation will be denoted _i,c,c'.
  
  
  
  
  
  
   §.§ Global mean, C class means and C2 cross-class means
  
  Arrays exhibiting class/cross-class block structure permit various averages to be compactly expressed.
  
  
      For an array of vectors {_̌i,c,c'}_i,c,c' exhibiting cross-class structure, we denote their C^2 cross-class means by {_̌c,c'}_c,c'; they are obtained by averaging, for a fixed class c, and cross-class c', across the replication index i, i.e.,
      
      _̌c,c' = _i _̌i,c,c'.
  
  
  
  
      Denote the C^2 cross-class means of gradients by {_c,c'}_c,c'.
  
  
      Denote the C^2 cross-class means of the l'th layer backpropagated errors by {_c,c'^l }_c,c', and their layer-wise concatenation by {_c,c'}_c,c'.
  
  
  
  
  
  
      For an array of vectors {_̌i,c,c'}_i,c,c' exhibiting cross-class block structure, we denote their C class means by {_̌c }_c; each is obtained by averaging, for a fixed class c, the cross-class means associated with that class, i.e.,
      
      _̌c = _c'_̌c,c' = _i,c'_̌i,c,c'.
  
      Moreover, an array {_̌i,c}_i,c exhibiting class block structure has C class means, {_̌c }_c; each is obtained by averaging, for a fixed class c, across the replication index i, i.e.,
      
      _̌c = _i _̌i,c.
  
  
  
  
      Denote the C feature class means at layer l by {_c^l }_c and their layer-wise concatenation by {_c }_c.
  
  
      Denote the C backpropagated error class means at layer l by {_c^l }_c and their layer-wise concatenation by {_c }_c.
  
  
      Denote the C class means of gradients by {_c }_c.
  
  
  
  
      An array of vectors exhibiting class/cross-class block structure has a global mean, given by
      
      _̌G = _c _̌c.
  
  
  
  
  
  
  
  
   §.§ Second moment matrices and covariances in the class/cross-class structure
  
  It is very natural to express second moment matrices for arrays with class/cross-class structure:
  
  
  
      An array of vectors exhibiting class or cross-class block structure with D-dimensional vectors has a second moment matrix ∈^D × D given by
      
      = _i,c_̌i,c_̌i,c^,
  
      or
      
      = _i,c,c'_̌i,c,c'_̌i,c,c'^,
  
      respectively.
  
  
  
  
  
      Associated with an array of vectors {_̌i,c,c'}_i,c,c' exhibiting class/cross-class structure is the second moment matrix of the global mean,
      
      _̌G _̌G^.
  
  
      
  
  
  
      Associated with an array of vectors {_̌i,c,c'}_i,c,c' exhibiting class/cross-class structure is the between-class second moment, ∈^D × D, 
      
      = _c _̌c _̌c^.
  
  
  
  
  
  
      The between-cross-class covariance, ∈^D × D associated with an array of vectors {_̌i,c,c'}_i,c,c' exhibiting cross-class structure, is given by
      
      = _c,c'_c,c'_c,c'^,
  
      where the cross-class mean deviations _c,c'∈^p are defined as follows:
      
      _c,c' = _̌c,c' - _̌c.
  
  
  
  
  
  
      The within-cross-class covariance, 
   ∈^D × D, associated with an array of vectors exhibiting cross-class structure, is given by
      
      = _i,c,c'_i,c,c'_i,c,c'^,
  
      where the replication deviations _i,c,c'∈^D are defined as follows:
      
      _i,c,c' = _̌i,c,c' - _̌c,c'.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  For simplicity, the notations of mean, covariance and second moment matrix discussed so far involved averages rather than weighted averages. Below, those notations will be extended to include certain weights w_i,c,c' associated with corresponding terms _̌i,c,c'. Moreover, we will distinguish between vectors _̌i,c,c', where c = c' and c ≠ c'. [In effect, we are introducing into deepnets constructs familiar in Multivariate Analysis of Variance (MANOVA), where the class/cross-class index structure would be called a two-way categorical layout. See reference <cit.> for further details.]
  
  
  
  
  
   §.§ Cause attribution
  
  As the introduction has shown, various spectral features have been observed in the literature.
  By proper use of our definitions, we are able to attribute causes for all the observed features as well as new ones. The cross-entropy loss induces a three-index structure of class, cross-class and replication. This index structure–inherited by all fundamental entities in deepnets, including features, backpropagated errors, and (extended) gradients–allows us to easily express certain second moment and covariance matrices. We shall demonstrate empirically that these matrices cause various spectral features:
  
      
    * The second moment matrix of the global mean causes the top outlier;
      
    * The between-class covariance causes the leading cluster of C-1 outliers;
      
    * The between-cross-class covariance causes the mini-bulk of C(C-1) outliers; and
      
    * The within-cross-class covariance causes the main bulk.
  
  We will prove these assertions data-analytically by “knocking out” each of these matrices, and showing that such knockout eliminates the corresponding visual feature in the spectrum under study. We will formalize this notion of “knockout” into a formal attribution procedure.
  
  
  
  
  
   §.§ Ubiquity
  
  The effects of the class/cross-class structure permeate the spectra of deepnet features, backpropagated errors, gradients, weights, Fisher Information matrix, and Hessian, whether these are considered in the context of an individual layer or the concatenation of several layers. Specifically, we will show:
  
      
    * For a fixed layer l, the Kronecker product of the c'th class mean in the features, _c^l, and the c'th class mean in the backpropagated errors, _c^l, approximates the c'th class mean in the gradients, _c^l.
      
    * For a fixed layer l, the Kronecker product of the c'th class mean in the features, _c^l, and the (c,c') cross-class mean in the backpropagated errors, _c,c'^l, approximates the (c,c') cross-class mean in the gradients, _c,c'^l.
      
    * Similar relations hold between the class/cross-class means of features, _c; backpropagated errors _c, _c,c'; and gradients _c, _c,c', once these are concatenated across the layers. However, now the Kronecker product is replaced by the Khatri-Rao product of the associated quantities.
      
    * The C class means and C^2 cross-class means in the layer-concatenated gradients induce C and C^2 outliers in the spectra of the FIM.
      
    * Outliers in the FIM also induce outliers in the spectrum of the Hessian, as the Hessian can be written as a summation of two components, one of them being the FIM.
  
  These insights are summarized in Figure <ref>, as well as Table <ref>.
  
  
  
  
  
  
  
  
  
  