Rank Diminishing in Deep Neural Networks

Introduction

In mathematics, the rank of a smooth function measures the volume of independent information captured by the function . Deep neural networks are highly smooth functions, thus the rank of a network has long been an essential concept in machine learning that underlies many tasks such as information compression , network pruning , data mining , computer vision , and natural language processing . Numerous methods are either designed to utilize the mathematical property of network ranks, or are derived from an assumption that low-rank structures are to be preferred.

Yet a rigorous investigation to the behavior of rank of general networks, combining both theoretical and empirical arguments, is still absent in current research, weakening our confidence in the being able to predict performance. To the best of our knowledge, there are only a few previous works discussing the rank behavior of specific network architectures, like attention blocks and BatchNorms in pure MLP structures. The empirical validation of those methods are also limited to shallow networks, specific architectures, or merely the final layers of deep networks, leaving the global behavior of general deep neural networks mysterious due to prohibitive space-time complexity for measuring them. Rigorous work on network rank that combines both strong theoretical and empirical evidence would have significant implications.

In this paper, we make several contributions towards this challenging goal. We find that the two essential ingredients of deep learning, the chain rules of differential operators and matrix multiplications, are enough to establish a universal principle—that network rank decreases monotonically with the depth of networks. Two factors further enhance the speed of decreasing: a) the explicit rank deficiency of many frequently used network modules, and b) an intrinsic potential of spectrum centralization enforced by the nature of coupling of massive composite functions. To empirically validate our theory, we design numerical tools to efficiently and economically examine the rank behavior of deep neural networks. This is a non-trivial task, as rank is very sensitive to noise and perturbation, and computing ranks of large networks is computationally prohibitive in time and space. Finally, we uncover an interesting phenomenon of independence deficit in multi-class classification networks. We find that many classes do not have their own unique representations in the classification network, and some highly irrelevant classes can decide the outputs of others. This independence deficit can significantly deteriorate the performance of networks in generalized data domains where each class demands a unique representation. In conclusion, the results of this work, together with the numerical tools we invent, may advance understanding of intrinsic properties of deep neural networks, and provide foundations for a broad study of low-dimensional structures in machine learning.

Preliminaries

For simplicity, we further write the $k$-th sub-networkIn this paper, sub-network means network slice from the input to some intermediate feature layer; layer network means an independent component of the network, without skip connections from the outside to it, like bottleneck layer of ResNet-50. of $\bm{F}$ as

and we use $\mathcal{F}_{k}=\bm{F}_{k}(\mathcal{X})$ to denote the feature space of the $k$-th sub-network on the data domain $\mathcal{X}$. We are more interested in the behavior of network rank in the feature spaces rather than scalar outputs (which trivially have rank 1). Thus for classification or regression networks that output a scalar value, we will consider $\bm{F}=\bm{F}_{L}$ as the transformation from the input space to the final feature space instead. Thus, we always have $n\gg 1$ and $d\gg 1$. For example, for ResNet-50 architecture on ImageNet, we only consider the network slice from the inputs to the last feature layer of 2,048 units.

The rank of a function represents the volume of information captured by it in the output . That is why it is so important to investigate the behavior of neural networks and many practical applications. Theoretically, by the rank theorem and Sard’s theorem of manifolds , we can know that rank of the function equals the intrinsic dimension of its output feature space, as captured by the following lemma.Due to space limitation, all the related proofs are attached in the Appendix.

It is worth mentioning that the intrinsic dimension $\dim(\bm{f}(\mathcal{X}))$ of the feature space is usually hard to measure, so the rank of the network gives an operational estimate of it.

Numerical Tools

This property of the numerical rank metric makes it a suitable tool for investigating the rank behavior of neural networks. Possible small noises can be filtered out in Jacobian matrices of networks by using numerical rank. It is worth mentioning that random matrices no longer have full rank almost surely under the numerical rank. Instead their rank distribution can be inferred from the well-known Marcenko–Pastur distribution of random matrices. So under numerical rank, low-rank matrices will be commonly seen. In this paper, we always use the numerical rank when measuring ranks.

2 Partial Rank of the Jacobian: Estimating Lower Bound of Lost Rank in Deep Networks

To enable the validation of trend of the network ranks, we propose to compute only the rank of sub-matrices of the Jacobian as an alternative. Those sub-matrices are also the Jacobian matrices with respect to a fixed small patch of inputs. Rigorously, given a function $\bm{f}$ and its Jacobian $\bm{J}_{\bm{f}}$, we denote partial rank of the Jacobian as the rank of a sub-matrix of the Jacobian that consists of the $j_{1}$-th, $j_{2}$-th,…,$j_{K}$-th column of the original Jacobian

3 Classification Dimension: Estimating Final Feature Dimension

which is the minimum dimensionality needed to reconstruct the classification accuracy of the whole model.

Principle of Rank Diminishing

We turn to the principle of rank diminishing. We first give a universal justification with minimum limitation on the network, so that we can safely apply this principle to many practical scenarios.

The principle of rank diminishing describes the behavior of general neural networks with almost everywhere smooth components, which exhibits the monotonic decreasing of network ranks and intrinsic dimensionality of feature manifolds as follows.

Suppose that each layer $\bm{f}_{i},i=1,...,L$ of network $\bm{F}$ is almost everywhere smooth and data domain $\mathcal{X}$ is a manifold, then both the rank of sub-networks and intrinsic dimension of feature manifolds decrease monotonically by depth:

A hypothetical but not practical concern would be that, is it possible that most of the equal signs of Eqs. 7 and 8 hold, so that the rank of network remains no significant dropping throughout the network? This concern can be mitigated by empirical and theoretical arguments. In what follows we will find that, 1) in practice, the rank of sub-networks decreases significantly after applying subsequent layers as shown in Fig. 1, and 2) in theory, there are two strong impetuses in deep neural networks to enforce the strict decreasing of ranks which we will discuss in Secs. 4.1 and 4.2.

1 Structural Impetus of Strict Decreasing

Numerous explicit structures of the network layers can lead to a strict decrease in network ranks. Specifically, the following theorem gives a condition for the strictly greater signs to hold in the principle of rank diminishing.

Roughly speaking, if almost everywhere on the input feature manifold, there is a direction such that moving along this direction keeps the output invariant, then the intrinsic dimension of the output feature manifold will be strictly lower than that of the input. The maximum number of independent such directions gives a lower bound on the number of lost intrinsic dimensions.

By this theorem, one can immediately find that most frequently used layer designs have high risk in inducing the strict decreasing of network ranks. Normalization layers like LayerNorm , InstanceNorm , and BatchNorm may lose dimensions modestly, as the output feature remains invariant along the normalized direction at each point. Linear layers like convolutions, linear transformations (e.g. dense layers), and attentions, can lose rank considerably according to the rank of their weight matrices. They constitute the explicit structural impetus to decrease network ranks and intrinsic dimensions of feature manifolds.

2 Implicit Impetus of Strict Decreasing

Apart from the structural impetus we propose in Sec. 4.1, there is a more intrinsic strength to pull down network ranks, which we call the implicit impetus. Deep neural networks repeatedly apply layer networks from a fixed function pool (ReLU, MLP, CNN, attention, ResNet block, etc.) to the input data and intermediate features to get outputs. Such paradigm accords with the cocycle dynamic systems studied by Lyapunov et al. , where the Furstenberg–Kesten theorem and multiplicative ergodic theorem prove that logarithms of singular values divided by evolution time of such chaos system converge to stable constants when time goes to infinity. While products of long chains of matrices are the simplest form of cocycle dynamic systems , we can get an intrinsic impetus of rank collapse tendency of Jacobian matrices independent of network architectures.

If further assuming that the elements of Jacobian matrices follow Gaussian distributions, we can prove $r=1$ and give a more accurate estimation of constants $\mu_{r},...,\mu_{n}$. As a consequence, we can find that rank of networks collapses to 1 almost surely, which is formalized in the following theorem.

Bengio et. al. discuss the gradient explosion issue of deep neural networks, where the largest singular value of the Jacobian matrix tends to infinity when the layer gets deeper. This problem could be viewed as a special case of Theorem 5 that investigates the behavior of all singular values of deep neural networks. The behavior of network ranks in fact manipulates the well-known gradient explosion issue. Rigorously, we have the following conclusion.

Under the condition of Theorem 5, then almost surely gradient explosion happens at an exponential speed, i.e., $\log\|\bm{J}_{\bm{F}}\|_{2}=\log\sigma_{1}\sim\frac{L}{2}(\log 2+\psi(n/2))\rightarrow\infty$ when $L$ is large.

3 Validation

As is discussed in Secs. 3.2 and 2, the partial rank of the Jacobian is a powerful weapon for us to detect the behavior of huge Jacobian matrices, which are infeasible to compute in practice. The decent value of partial ranks of adjacent sub-networks provides a lower bound to that of full ranks of them. Fig. 1 (a,b,c) report the partial rank of Jacobian matrices of three types of architectures, where we can find consistent diminishing of partial ranks in each layer, indicating a larger rank losing for the full rank of Jacobian matrices.

There are quite some techniques, at least in theory, can remiss the network rank diminishing. Typical examples are skip connection and BatchNorm , which we will discuss in the Appendix due to page limitation.

Independence Deficit of Final Feature Manifolds

In this section, we provide a further perspective to study the low-rank structure of the final feature manifold, which induces an interesting finding of independence deficit in deep neural networks. We have already known that the final feature representations of deep neural networks admit a very low intrinsic dimension. Thus there are only a few independent representations to decide the classification scores for all the 1,000 categories of ImageNet. It is then curious whether we can predict the outputs of the network for some categories based on the outputs for a few other categories, as illustrated in Fig. 4 (a). And if we can, will those categories be strongly connected to each other? A surprising fact is that, we can find many counter examples of irrelevant categories dominating the network outputs for given categories regarding various network architectures. This interesting phenomenon indicates a rather drastic competing in the final feature layer for the tight rank budgets of all categories, which yields non-realistic dependencies of different categories.

To find the dependencies of categories in final features, we can solve the following Lasso problem ,

In Fig. 4 we demonstrate the solutions of Eq. 12 for three different categories in ImageNet with $\eta=20$, and network architectures ResNet-50, GluMixer-24, and Swin-T. The results are surprising. It shows that many categories of the network predictions are in fact ‘redundant’, as they are purely decided by the predictions of the other categories with simple linear coefficients. In this case, the entanglement of different categories cannot be avoided, thus the network may perform poorly under domain shift. An even more surprising finding is that, some very irrelevant categories hold the largest weights when deciding the predictions of the redundant categories, which means that the networks just neglect the unique representations of those categories in training and yield over-fitting when predicting them.

Related Work

Previous studies of rank deficiency in deep neural networks follow two parallel clues. One is the study of rank behavior in specific neural network architectures. studies deep networks consisting of pure self-attention networks, and proves that they converge exponentially to a rank-1 matrix under the assumption of globally bounded weight matrices. studies the effect of BatchNorm on MLPs and shows that BatchNorm can prevent drastic diminishing of network ranks in some small networks and datasets. Both of those works avoid directly validating the behavior of network ranks in intermediate layers due to the lacking of efficient numerical tools. An independent clue is the study of implicit self-regularization, which finds that weight matrices tend to lose ranks after training. studies this phenomenon in infinitely-wide, over-parametric neural networks with tools from random matrix theory. studies this phenomenon in deep matrix decomposition. Those works focus on the theoretical behavior of rank of weight matrices induced by the training instead of network ranks.

Conclusion

This paper studies the rank behavior of deep neural networks. In contrast to previous work, we focus on directly validating rank behavior with deep neural networks of diverse benchmarks and various settings for real scenarios. We first formalize the analysis and measurement of network ranks. Then under the proposed numerical tools and theoretical analysis, we demonstrate the universal rank diminishing of deep neural networks from both empirical and theoretical perspectives. We further support the rank-deficient structure of networks by revealing the independence deficit phenomenon, where network predictions for a category can be linearly decided by a few other, even irrelevant categories. The results of this work may advance understanding of the behavior of fundamental network architectures and provide intuition for a wide range of work pertaining to network ranks.

References

Appendix

Appendix A Proofs

This Lemma is the direct result of the rank theorem of manifolds.

is given by $\bm{n}\circ\bm{f}\circ\bm{m}^{-1}(\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{m})=(\bm{x}_{1},\bm{x}_{2},\cdots,\bm{x}_{m},0,\cdots,0)$.

A.2 Proof to Theorem 1

Proof to this Theorem needs Weyl’s inequalities for singular values of sum of matrices.

Let $\bm{A},\bm{B}$ be $p\times n$ complex matrices, $\sigma_{i}(\cdot)$ be the $i$-th largest singular value of the matrix. Then

Let $p$ be the number of singular values of $\bm{W}$ and $\bm{D}$. By this theorem, we have

To measure the numerical rank, we need to estimate the relative quantities of singular values, which are,

A.3 Proof to Lemma 2

Thus for any $1\leq i_{1}<\cdots<i_{K}\leq d$,

As $(\bm{B})_{i_{1},\cdots,i_{K}})\subset\bm{B}$, it is straightforward to get that

A.4 Proof to Theorem 2

The key to this principle is the rank theorem of matrices , which is

The dimension of a linear subspace will at least be zero, thus the above equations suggest

Applying this argument to the chain rule of differentials then yields the conclusion. Further using Lemma 1 gives the diminishing of intrinsic dimensions of feature manifolds.

A.5 Proof to footnote 3

We first give the rigorous version of this theorem as follows.

then $\dim(\bm{f}^{i}(\mathcal{X}))<s$. If the number of such independent $\bm{v}$ in $\bm{e}_{\bm{x}}(\mathcal{U}_{\bm{x}})$ is $k$, then $\dim(\bm{f}^{i}(\mathcal{X}))\leq s-k$.

where $0\neq\bm{J}_{\bm{e}^{-1}_{\bm{x}}}\bm{v}$ comes from the full rank property of exponential map and its inverse. Thus we have

Specifically, if linearly independent $\bm{v}_{1},\cdots,\bm{v}_{k}$ satisfy Eq. A37, we can conclude

As $\bm{J}_{\bm{e}^{-1}_{\bm{x}}}$ has full rank due to the property of exponential map, we know that $\bm{J}_{\bm{e}^{-1}_{\bm{x}}}\bm{v}_{i},i=1,\cdots,k$ are linearly independent. Then

Combining this result with Theorem 6 proves our result.

A.6 Proof to Theorem 4

The proof to this theorem relies on the existence of Lyapunov exponents of dynamic systems. Given a linearized dynamic system

its (largest) Lyapunov exponent is defined as

It may be surprising to find that such Lyapunov exponents exist, as $\bm{v}_{0}$ can traverse the entire subspace $\mathcal{L}_{i-1}\backslash\mathcal{L}_{i}$. We will demonstrate the existence of the Lyapunov exponents for our case later in Sec. A.6.3, which is the classical results from the Furstenberg-Kesten theorem and multiplicative ergodic theorem . Before that, we will first assume the existence of those Lyapunov exponents for simplicity of analysis.

Now consider the case of function couplings

Apparently, the following dynamic system induces the Jacobi matrix of $\bm{F}$,

We first demonstrate that the Lyapunov exponents are limits of logarithm of the spectral norm of $\bm{F}$ on $\mathcal{L}_{i-1}\backslash\mathcal{L}_{i}$ divided by layer depth $L$ when $L\rightarrow\infty$, for $i=1,...,r$.

When $L\rightarrow\infty$, $\frac{1}{L}\log\|\bm{v}_{0}\|_{2}\rightarrow 0$ for any $\bm{v}_{0}$, we have

where $\|\cdot\|_{2,i}$ denote the spectral norm of a linear operator constrained on $\mathcal{L}_{i-1}\backslash\mathcal{L}_{i}$.Then we have

Let $\bm{v}=\sum_{j=1}^{i_{k}}\alpha_{j}\bm{e}_{j}\in\mathcal{L}_{i-1}\backslash\mathcal{L}_{i}$, where $\alpha_{j},i=1,\cdots,i_{k},\sum_{j=1}^{i_{k}}\alpha_{j}^{2}=1$ is the coordinate of unit vector $\bm{v}$ under the basis $\bm{e}_{j},j=1,\cdots,i_{k}$. Assume that $\|\bm{J}_{\bm{F}}\bm{e}_{1}\|_{2}\geq\|\bm{J}_{\bm{F}}\bm{e}_{j}\|_{2},j=2,\cdots,i_{k}$. We then have $\frac{|\alpha_{j}|\|\bm{J}_{\bm{F}}\bm{e}_{j}\|_{2}}{\sum_{j=1}^{i_{k}}|\alpha_{j}|\|\bm{J}_{\bm{F}}\bm{e}_{1}\|_{2}}\leq 1,j=1,\cdots,i_{k}$, and

Thus, if we set $N_{0}=\max\{N,\frac{2i_{k}-2+\log i_{k}}{\epsilon}\}$, then when $L>N_{0}$ we have $\frac{1}{L}(i_{k}-1)+\frac{1}{2L}\log i_{k}<\frac{\epsilon}{2}$ and

Thus, if the Lyapunov exponents exist, i.e., the existence of limits of Eq. A53 , we have

A.6.2 Singular value distributions of Jacobian matrices of deep function coupling

In Sec. A.6.1 we have proved that the Lyapunov exponents (if they exist) are limits of logarithms of subspace spectral norms divided by $L$. Here we use this property to prove the deficiency of numerical ranks, i.e., Eq. 9.

We first introduce the Courant-Fischer min-max theorem of sigular values.

Let $\bm{A}$ be a $d\times n$ complex matrix and $\sigma_{i}(\bm{A})$ denote its $i$-th largest singular value, $i=1,\cdots,\min\{d,n\}$. Then we have

This theorem also serves as one of the definitions to singular values.

due to Eq. A55. As $\dim(\mathcal{L}_{0}\backslash\mathcal{L}_{1})=r$, by Theorem 9, we have

Then by the conclusion of Sec. A.6.1, we have

As $\dim(\mathcal{L}_{1})=n-1+1$, by Theorem 9, we have when $L>N_{1}$,

In conclusion, when $L>N_{0}=\max\{N,N_{1}\}$, we have

Using the same argument for $\sigma_{2}(\bm{J}_{\bm{F}}),\cdots,\sigma_{n}(\bm{J}_{\bm{F}})$, we can find that if let $\hat{\lambda}_{1}\geq\hat{\lambda}_{2}\cdots\geq\hat{\lambda}_{n}$ be the Lyapunov exponents counting repetitions, i.e.,

A.6.3 Existence of Lyapunov exponents for Jacobian matrices of deep function coupling

In above analysis, we have proven Theorem 4 under the existence of Lyapunov exponents. In this section, we introduce the classical result of multiplicatve ergodic theorem in the specific domain of random matrices, which is proposed by Furstenberg and Kesten .

which means the existence of the Lyapunov exponents.

Combining this theorem and the arguments above, we can finally prove Theorem 4.

A.7 Proof to Theorem 5

This theorem can be deduced from the Lyapunov components of Ginibre matrices (polynomial ensemble of square matrices sampled i.i.d from standard Gaussian).

If $\mu$ in Theorem 10 is standard Gaussian, then $h+1=n$, and

Combining this theorem with Theorem 4 can directly yield our result.

A.8 Proof to Corollary 1

This theorem is the direct result of Theorems 4 and 11. Note that it is easy to get

Appendix B Possible Remission Approaches to Rank Diminishing

Skip Connection is the most direct method to solve rank diminishing. In our formulation, the definition of a layer network requires it to accept inputs purely from its predecessor layer as

However, when we add a skip connection from its ancestor layer $\bm{f}^{s},s<i-1$, we have

the true predecessor layer to $\bm{f}^{i}$, as

Thus the true layer depth is cut down by $i-s$, remaining $L-(i-s)$ layers. Skip connection is usually used with the residual network. This structure can ease rank diminishing inside the layer $\hat{f}^{s}$, which we will discuss later. Overall, skip connection shortens the length of the chain of Jacobian matrices, thus restraining rank diminishing.

Some previous works discuss the role of BatchNorm in restraining rank diminishing. They show that BatchNorm may slow down the speed of rank diminishing in neural networks in some specific cases.

Residual Network is another useful tool to restrain rank diminishing. The residual network $\bm{r}$ has the form

where $\epsilon$ is very small. Then we have

Appendix C Code

Algorithm A1 provides the pseudo-code of partial rank of the Jacobian. The implementation of the Algorithm A1 can refer to the ‘rank_jacobian.py’ python file.

Algorithm A2 provides the pseudo-code of perturbed PCA dimension of feature spaces. The implementation of the Algorithm A2 can refer to the ‘rank_perturb.py’ python file.

Algorithm A3 provides the pseudo-code of the classification dimension. The implementation of the Algorithm A3 can refer to the ‘run_cls_dim.py’ python file.

Algorithm A4 provides the pseudo-code of independence deficit. The implementation of the Algorithm A4 can refer to the ‘run_deficit.py’ python file.

Appendix D Partial Rank of Jacobians under Different Input Patches

In Fig. A5 we report partial ranks of different input image patches (marked with colored boxes in Fig. A5(a)) for the layers of ResNet-50 on ImageNet. We can find that the curves of partial ranks share a similar and consistent trend among different input patches. Thus, picking one patch, for example, the central patch of $16\times 16\times 3$ pixels we use in Sec. 4.3, could be enough to demonstrate the overall behavior of network ranks. The consistent behavior of all those partial ranks also shows that partial rank is a good tool to investigate network ranks.

Appendix E Estimating Dimension Diminishing in Features

Measuring the intrinsic dimension of feature manifolds is known to be hard. However, we manage to give a rough estimation to the dimension dropped by different layer networks. To do this, we use a new metric called the Perturbed PCA Dimension. It measures the expectation of PCA dimension of small local neighborhoods over the feature manifold.

Let $\bm{F}_{k}$ be the $k$-th sub-network of the whole network $\bm{F}$. We want to measure the Perturbed PCA Dimension of $\bm{F}_{k}(\mathcal{X})$, where $\mathcal{X}$ is the input data domain. To this end, we compute

We do not use PCA dimension of the feature manifolds directly as it is unable to cope with the highly non-linear structure of intermediate feature manifolds. However, the Perturbed PCA Dimension is able to estimate the dimensions of local neighborhoods of points in the feature manifolds. As local neighborhoods can be viewed as linear if the network is smooth, the Perturbed PCA Dimension could be more feasible than PCA dimension in our case. We provide the pseudo-code to compute the Perturbed PCA Dimension in Algorithm A2.

However, the perturbation is made in the ambient space of the input data manifold $\mathcal{X}$ rather than the data manifold itself. Thus this estimation may considerably overestimate the intrinsic dimensions of feature manifolds. So we merely care about how many Perturbed PCA Dimensions are lost by a sub-network instead of its own Perturbed PCA Dimension. We call this quantity $\Delta$ Dimension, which is the difference between the Perturbed PCA Dimension of the current layer and that of the input layer for the given deep network. As shown in Fig. A6, we show the dropped dimensions of different feature layers of the CNN, MLP, and Transformer architectures on ImageNet. The results show that the Perturbed PCA Dimensions of feature manifolds of most networks decrease as the networks get deeper, thus confirming the rank diminishing principle we propose in Theorem 2.

Appendix F More Examples of Independence Deficit

We provide more examples of independence deficit, which shows that classification confidence of some categories can be lineally decided by a few other categories with fixed coefficients. The results obtained by ResNet-18, ResNet-50, GluMixer-24, ResMLP-S24, ViT-T, and Swin-T are reported in Fig. A7 - Fig. A12, respectively. All the results are obtained by solving the Lasso problem in Sec. 5. In each figure, we report the classification accuracy for category ‘$i$’: the accuracy by calculating logits with Eq. 12 is reported as ‘acc.’; and the original model accuracy is reported as ‘ori. acc.’. Both the metrics are measured in the whole ImageNet validation set. We further report the classification accuracy on positive samples only for both metrics as ‘pos’ following ‘acc.’ and ‘ori. acc.’ correspondingly. The results show a universal independence deficit phenomenon for broad categories in all those deep networks.