summaries: This paper provides several results on the rank of the Hessian of neural networks. The main results are:  (A) upper bounds on the rank of the Hessian of a linear neural network (i.e., identity activations). These are proved by separating the Hessian into the sum of the “outer-product Hessian” and the “functional Hessian”, and bounding the rank of these separately. (B) a conjectured formula for the exact Hessian rank that matches experiments, and is also quite close to the upper bounds. (C) experimental evidence that these results essentially hold for neural networks with nonlinear activations as well, even after training. (D) for 1-hidden layer nonlinear networks, under a mild assumption a very weak (but still nontrivial) bound on the rank is obtained.

summaries: This paper studies the rank of Hessian for deep linear networks. Theoretically, with squared loss, and assuming the weight matrices are full-rank, this paper provides rank upper bound for outer-product, functional and full Hessian, and empirically verifies that the bounds are almost tight. This paper further shows empirically that the numerical rank with nonlinear networks can still be captured by the linear rank bound, and that the Hessian rank decreases during training. Finally, Hessian degeneracy results for 1-hidden-layer networks and extension to the case with bias are also provided.

summaries: This paper analyzes the rank of the Hessian matrix of fully connected neural networks. Theoretically, for a linear fully-connected neural network with square loss, the authors provided an upper bound for the rank of Hessian with respect to the population loss. They also did many experiments for small neural networks on MNIST and CIFAR-10 to show that their upper bound is almost tight, and works for different types of non-linear activations, losses, and initializations.

summaries: This paper derives tight upper bounds on the Hessian rank for deep linear networks. They show that these rank formulae (derived for the linear case) faithfully capture the numerical rank in the non-linear regime. They also demonstrate that these rank bounds hold during the course of training.

abstractText: The Hessian of a neural network captures parameter interactions through secondorder derivatives of the loss. It is a fundamental object of study, closely tied to various problems in deep learning, including model design, optimization, and generalization. Most prior work has been empirical, typically focusing on low-rank approximations and heuristics that are blind to the network structure. In contrast, we develop theoretical tools to analyze the range of the Hessian map, which provide us with a precise understanding of its rank deficiency and the structural reasons behind it. This yields exact formulas and tight upper bounds for the Hessian rank of deep linear networks — allowing for an elegant interpretation in terms of rank deficiency. Moreover, we demonstrate that our bounds remain faithful as an estimate of the numerical Hessian rank, for a larger class of models such as rectified and hyperbolic tangent networks. Further, we also investigate the implications of model architecture (e.g. width, depth, bias) on the rank deficiency. Overall, our work provides novel insights into the source and extent of redundancy in overparameterized neural networks. 1

authors:
Ciyou Zhu
Richard H Byrd
Peihuang Lu
Jorge Nocedal

title: Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale bound-constrained optimization

venue: ACM Transactions on Mathematical Software (TOMS),

authors:
Rudy Setiono
Lucas Chi Kwong Hui

title: Use of a quasi-newton method in a feedforward neural network construction algorithm

venue: IEEE Transactions on Neural Networks,

authors:
Yann LeCun
John S Denker
Sara A Solla

title: Optimal brain damage

venue: In Advances in neural information processing systems,

authors:
Babak Hassibi
David G. Stork

title: Second order derivatives for network pruning: Optimal brain surgeon

venue: In NIPS, pages 164–171,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Simplifying neural nets by discovering flat minima

title: A Practical Bayesian Framework for Backpropagation Networks

venue: Neural Computation, 4(3):448–472,

authors:
John S. Denker
Yann LeCun

title: Transforming neural-net output levels to probability distributions

venue: In Proceedings of the 3rd International Conference on Neural Information Processing Systems,

authors:
Y. LeCun
P. Simard
Barak A. Pearlmutter

title: Automatic learning rate maximization by on-line estimation of the hessian’s eigenvectors

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: IEEE Conference on Computer Vision and Pattern Recognition

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: Proceedings of NAACL-HLT,

title: Fast exact multiplication by the hessian

venue: Neural computation,

authors:
James Martens
Ilya Sutskever

title: Learning recurrent neural networks with hessian-free optimization

venue: In ICML,

authors:
Frédéric Bastien
Pascal Lamblin
Razvan Pascanu
James Bergstra
Ian Goodfellow
Arnaud Bergeron
Nicolas Bouchard
David Warde-Farley
Yoshua Bengio

title: Theano: new features and speed improvements

venue: arXiv preprint arXiv:1211.5590,

authors:
James Martens
Roger Grosse

title: Optimizing neural networks with kronecker-factored approximate curvature, 2020

authors:
Aleksandar Botev
Hippolyt Ritter
David Barber

title: Practical gauss-newton optimisation for deep learning

venue: In International Conference on Machine Learning,

authors:
Donald Goldfarb
Yi Ren
Achraf Bahamou

title: Practical quasi-newton methods for training deep neural networks

venue: arXiv preprint arXiv:2006.08877,

authors:
César Laurent
Thomas George
Xavier Bouthillier
Nicolas Ballas
Pascal Vincent

title: An evaluation of fisher approximations beyond kronecker factorization, 2018

authors:
Xin Dong
Shangyu Chen
Sinno Jialin Pan

title: Learning to prune deep neural networks via layer-wise optimal brain

authors:
Sidak Pal Singh
Dan Alistarh

title: Woodfisher: Efficient second-order approximation for neural network compression, 2020

authors:
Andrew M. Saxe
James L. McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

title: Deep learning without poor local minima, 2016

title: Developments in Maximum Entropy Data Analysis, pages 53–71

title: Bayesian model comparison and backprop nets

venue: Advances in Neural Information Processing Systems,

authors:
Levent Sagun
Leon Bottou
Yann LeCun

title: Eigenvalues of the hessian in deep learning: Singularity and beyond

venue: arXiv preprint arXiv:1611.07476,

authors:
Levent Sagun
Utku Evci
V Ugur Guney
Yann Dauphin
Leon Bottou

title: Empirical analysis of the hessian of over-parametrized neural networks

venue: arXiv preprint arXiv:1706.04454,

authors:
Behrooz Ghorbani
Shankar Krishnan
Ying Xiao

title: An investigation into neural net optimization via hessian eigenvalue density

title: Measurements of three-level hierarchical structure in the outliers in the spectrum of deepnet hessians

venue: arXiv preprint arXiv:1901.08244,

authors:
Diego Granziol
Timur Garipov
Dmitry Vetrov
Stefan Zohren
Stephen Roberts
Andrew Gordon Wilson

title: Towards understanding the true loss surface of deep neural networks using random matrix theory and iterative spectral methods, 2020

authors:
Jeffrey Pennington
Yasaman Bahri

title: Geometry of neural network loss surfaces via random matrix theory

venue: Proceedings of the 34th International Conference on Machine Learning,

title: Beyond random matrix theory for deep

venue: networks. ArXiv,

authors:
Ryo Karakida
Shotaro Akaho
Shun ichi Amari

title: Universal statistics of fisher information in deep neural networks: Mean field approach, 2019

authors:
Arthur Jacot
Franck Gabriel
Clément Hongler

title: The asymptotic spectrum of the hessian of dnn throughout training

venue: arXiv preprint arXiv:1910.02875,

authors:
Song Han
Huizi Mao
William J. Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding, 2016

authors:
Jonathan Frankle
Michael Carbin

title: The lottery ticket hypothesis: Finding sparse, trainable neural networks

venue: arXiv: Learning,

authors:
Chunyuan Li
Heerad Farkhoor
Rosanne Liu
Jason Yosinski

title: Measuring the intrinsic dimension of objective landscapes

venue: arXiv preprint arXiv:1804.08838,

authors:
Wesley J. Maddox
Gregory Benton
Andrew Gordon Wilson

title: Rethinking parameter counting: Effective dimensionality revisted

venue: arXiv preprint arXiv:2003.02139,

authors:
Mikhail Belkin
Daniel J. Hsu
Siyuan Ma
Soumik Mandal

title: Reconciling modern machine-learning practice and the classical bias–variance trade-off

venue: Proceedings of the National Academy of Sciences,

authors:
Jan R Magnus
Heinz Neudecker

title: Matrix differential calculus with applications in statistics and econometrics

authors:
Guy Gur-Ari
Daniel A. Roberts
Ethan Dyer

title: Gradient descent happens in a tiny subspace, 2018

title: Generalized inverse of a matrix and its applications. In Vol. 1 Theory of Statistics, pages 601–620

authors:
Jianjun Chuai
Yongge Tian

title: Rank equalities and inequalities for kronecker products of matrices with applications

venue: Applied Mathematics and Computation,

authors:
Alberto Bernacchia
Mate Lengyel
Guillaume Hennequin

title: Exact natural gradient in deep linear networks and its application to the nonlinear case

title: Neural tangent kernel: Convergence and generalization in neural networks

venue: arXiv preprint arXiv:1806.07572,

authors:
Han Xiao
Kashif Rasul
Roland Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017

title: Learning multiple layers of features from tiny images

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,

authors:
Shashanka Ubaru
Yousef Saad

title: Fast methods for estimating the numerical rank of large matrices

authors:
Gene H. Golub
Virginia C. Klema
Gilbert W. Stewart

title: Rank degeneracy and least squares problems

venue: Technical report,

authors:
Jonathan Lacotte
Yifei Wang
Mert Pilanci

title: Adaptive newton sketch: Linear-time optimization with quadratic convergence and effective hessian dimensionality, 2021

title: Towards a mathematical understanding of the difficulty in learning with feedforward neural networks, 2016

authors:
Sanjeev Arora
Nadav Cohen
Noah Golowich
Wei Hu

title: A convergence analysis of gradient descent for deep linear neural networks, 2019

authors:
Jeffrey Pennington
Pratik Worah

title: The spectrum of the fisher information matrix of a singlehidden-layer neural network

authors:
Tomaso Poggio
Kenji Kawaguchi
Qianli Liao
Brando Miranda
Lorenzo Rosasco
Xavier Boix
Jack Hidary
Hrushikesh Mhaskar

title: Theory of deep learning iii: explaining the non-overfitting puzzle, 2018

authors:
Behnam Neyshabur
Ryota Tomioka
Nathan Srebro

title: Norm-based capacity control in neural networks

venue: Proceedings of The 28th Conference on Learning Theory,

authors:
Peter Bartlett
Dylan J. Foster
Matus Telgarsky

title: Spectrally-normalized margin bounds for neural networks, 2017

authors:
Sanjeev Arora
Rong Ge
Behnam Neyshabur
Yi Zhang

title: Stronger generalization bounds for deep nets via a compression

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On large-batch training for deep learning: Generalization gap and sharp minima

venue: arXiv preprint arXiv:1609.04836,

authors:
Stanisław Jastrzębski
Zachary Kenton
Devansh Arpit
Nicolas Ballas
Asja Fischer
Yoshua Bengio
Amos Storkey

title: Finding flatter minima with sgd, 2018

authors:
Carlo Baldassi
Fabrizio Pittorino
Riccardo Zecchina

title: Shaping the learning landscape in neural networks around wide flat minima

authors:
Inbar Seroussi
Ofer Zeitouni

title: Lower bounds on the generalization error of nonlinear learning models

venue: arXiv preprint arXiv:2103.14723,

authors:
George Matsaglia
George P.H. Styan

title: Equalities and inequalities for ranks of matrices

venue: Linear and Multilinear Algebra,

title: Fundamentals of Digital Image Processing

venue: Prentice-Hall, Inc., USA,

authors:
Sanjeev Arora
Nadav Cohen
Elad Hazan

title: On the optimization of deep networks: Implicit acceleration by overparameterization

venue: International Conference on Machine Learning (ICML),

authors:
Jan R. Magnus
Heinz Neudecker

title: Matrix Differential Calculus with Applications in Statistics and Econometrics

venue: John Wiley, second edition,

heading: 1 Introduction

text:
Since the very infancy of neural networks, the Hessian matrix has been a central object of study. This is because the Hessian captures pairwise interactions of parameters via second-order derivatives of the loss function. As a result, the Hessian was productively employed, for instance, in (quasiNewton) optimization methods [1, 2], model design and pruning [3–5], generalization [6], network calibration [7], automatically tuning hyper-parameters [8]. But, from the outset the main practical challenge has been its size, scaling quadratically with the model dimensionality. This makes the problem severe for today’s DNNs which have millions or even billions of parameters [9, 10].
Consequently, most prior work has focused on designing scalable Hessian approximations, which either take the route of Hessian-vector products (R-operator) [11–13] or employ positive definite approximations by appealing to the Fisher information matrix. Additional approximations — without exception — are needed on top, such as diagonal approximations [3, 14] in the former or K-FAC [15– 17], restricted to layerwise or arbitrary blocks on the diagonal [18–20], in the latter.
∗Detailed list of contributions are: Sidak first discovered that the Hessian rank formula, in an early form, holds experimentally to high fidelity, thus kick-starting the project. Sidak came up with the proof technique and proved Theorems 3, 5, 9, 12. Sidak wrote essentially the entire paper and noted the rank-deficiency interpretation. Gregor proved Lemma 8, assisted in a part of Theorem 3, empirically observed the eventual formula for the Hessian rank, and essentially ran all the experiments for the final submission and made the corresponding figures. Correspondence to sidak.singh@inf.ethz.ch.
1The most recent version of our paper can be found at https://arxiv.org/abs/2106.16225 and the code corresponding to the experiments is located at https://github.com/dalab/hessian-rank.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The goal of this paper is to advance the analytical understanding of the Hessian map of a neural network. We pursue the fundamental question of how the model architecture induces structural properties of the Hessian. In particular, we analyze the dimension of its range (i.e., the rank) and identify the sources of rank deficiency. Understanding the range of the Hessian map, in turn, delivers insights into the important aspect of how gradients change between iterations.
A reason why such an important direction currently remains sidelined is that non-linearities in a neural network result in an increased dependence on the data distribution, making a suitable theoretical analysis seem intractable. Following Saxe et al. [21], Kawaguchi [22], who delivered useful general insights on neural networks by looking at the linear case, we take a step back and rigorously characterize the range of the Hessian map and determine the resultant rank deficiency for deep linear networks. The key result of our paper is an exact formula along with tight upper bound on the rank of the Hessian — which effectively depend on the sum of hidden-layer widths. This stands opposed to the total number of parameters which are proportional to the sum of squared layer widths, thus implying a significant redundancy in the parameterization of neural networks (see Fig. 1).
The exact quantification of the Hessian rank gives a precise yet interpretable ballpark on the inherent complexity of neural networks since rank naturally measures the effective number of parameters (as best illustrated by the case of a quadratic minimization problem). This relationship is further reinforced by connection to the classical complexity measure of Gull [23], MacKay [24], which is equivalent to rank for a sufficiently small constant controlling the prior. Therefore, this sheds a novel perspective on the nature and degree of overparameterization in neural networks, and opens up interesting avenues for future investigation.
Contributions. The main contributions of our paper can be summarized as follows: (i) Section 3: We characterize the structure of the Hessian range by exhibiting it via matrix derivatives. (ii) Section 4: We prove tight upper bounds and provide exact formulas on the Hessian rank that are neatly interpretable. To the best of our knowledge, this is the very first time that such formulas and bounds are made available for neural networks. (iii) Section 5.2: In the non-linear case, we show that our (linear) rank formulae faithfully capture the numerical rank. (iv) Section 6: We demonstrate via experiments and theory that such rank bounds also hold throughout the course of training. (v) Section 7.1: In the non-linear case, we also provide a pessimistic yet non-trivial bound, which provably establishes degeneracy of the Hessian at the minimum. (vi) Section 7.2, 5.1: We extend our rank results to the case of bias and investigate the effects of architectural components (such as width, depth, bias) on rank. (vii) Appendix S8: As a by-product, our analysis also reveals interesting properties of the Hessian spectrum, and we prove the presence of additional redundancies due to repeated eigenvalue plateaus.
Related work. The study of the Hessian, in recent times, has been re-invigorated by the empirical observations of Sagun et al. [25, 26] who noted a high degree of degeneracy experimentally, and characterized the spectrum as being composed of a bulk around zero and few outlier eigenvalues. Since then, works such as [27, 28] have scaled the empirical analysis to bigger networks via efficient spectral density calculations and better explained the observations in [26]. However, a drawback is that due to their empirical nature, it remains hard to uncover the exact level of degeneracy via these methods [29], and neither are the exact factors that affect the rank deficiency discerned. Another approach has been to fit models from random matrix theory to match the observed Hessian spectrum in neural networks [29, 30], however, such methods do not properly capture the sharp peak at zero observed in empirical spectra [31]. Yet others have investigated the properties of the spectrum in the asymptotic regime [32, 33], but the bounds, if any, are quite coarse (see Fig. 4). Moreover, a common issue underlying most of these approaches is that they are blind to the layerwise compositional structure of neural networks, and are often motivated by a black-box decomposition of the Hessian.
In regards to indicating the parameter redundancy in neural networks, we are far from being the first work. Prior empirical studies have long reported similar observations, like in the form
of, post-training pruning [3, 4, 19, 20, 34] or inherently contained sub-networks (Lottery Ticket Hypothesis [35]) or intrinsic dimension of the loss landscape [36]. Recently, [37] have experimentally argued for the effective dimensionality from [23, 24] to be a good predictor of double descent [38]. Nevertheless, determining the precise extent of redundancy — and showing it provably — as well as the structural reasons behind it have remained illusory in such approaches.

heading: 2 Setup and Formalism

text:
General notation. We use the shorthand, Wk:l, to refer to the matrix product chain Wk · · ·Wl, when k > l. When k < l, Wk:l will stand for the transposed product chain Wk
⊤ · · ·Wl⊤ . Besides, ⊗ denotes the Kronecker product of two matrices, vecr indicates the row-wise vectorization of matrices, rk refers to the rank of a matrix, and Ik is the identity matrix of size k × k. Deep Neural Networks (DNNs). A feedforward DNN is a composition of maps, i.e., F = FL ◦ · · · ◦ F 1, where the l-th layer map F l : RMl−1 → RMl , with input dimension d := M0, output dimension K := ML, total number of hidden neurons M := ∑L−1 l=1 Ml. Each layer map is parameterized by a weight matrix Wl and applies an elementwise activation function σl. So we have,

heading: F l = σl ◦Wl with Wl ∈ RMl×Ml−1 and σl : R→ R .

text:
For the sake of tractability, we will often investigate linear DNNs where σl = id, and so F (x) = WL:1x. For compactness, we also represent the entire set of parameters by θ := {W1, · · · ,WL}, and where emphasis requires, we will subscript the DNN map F with it and write Fθ .
Next, assume that we are given a dataset S = {(xi,yi)}Ni=1 of N input-output pairs, drawn i.i.d from an underlying distribution px,y. Our focus will be on the squared loss (MSE), ℓx,y(θ) = 12∥y − ŷ∥ 2 and its residual δx,y := ŷ − y = ∂ℓx, y∂ŷ , where ŷ = Fθ(x) is the DNN prediction. The population loss, L is: L(θ) = E px,y [ℓx,y(θ)] . Finally, we will analyze the Hessian matrix HL = ∂2L ∂θ ∂θ .
Backpropagation in matrix derivatives. As all parameters are collected into matrices, we often work with matrix-matrix derivatives by vectorizing row-wise in the numerator (Jacobian) layout, i.e., ∂Y ∂X := ∂ vecr(Y) ∂ vecr(X)⊤ , see [39] and Appendix S2.5. Alongside this, we use the following rule:
∂AWB ∂W = A⊗ B⊤, e.g. ∂F ∂Wk = WL:k+1 ⊗ x⊤W1:k−1 ∈ RK×MkMk−1 . (1)
By the usual chain rule (backpropagation) one has for a linear DNN, at a sample (x,y):
∂ℓx,y ∂Wk
= [ Wk+1:Lδx,y ] ︸ ︷︷ ︸
backward ∈RMk
· [ Wk−1:1x ]⊤ ︸ ︷︷ ︸ forward ∈RMk−1 = Wk+1:L [ WL:1 xx⊤ − y x⊤ ] W1:k−1 . (2)
The above gradient with respect to Wk is of first order in Wk itself and second order in the other weight matrices. Lastly, let us setup the following shorthand, Ω := E [δx,y x⊤] = E [WL:1xx⊤ − yx⊤] , Σxx := E [xx⊤] , and Σyx := E [yx⊤], which we will use throughout the paper.

heading: 3 Hessian Maps of Linear DNNs

heading: 3.1 Hessian structure

text:
The Hessian map has a natural block structure defined by the layers and their dimensionality. In order to leverage this structure, we directly take the derivative of the loss gradient in a matrix-by-matrix fashion. First, consider the k-th diagonal block of the Hessian, which is independent of y and is given by,
HkkL := ∂2L
∂Wk∂Wk = Wk+1:LWL:k+1 ⊗ Wk−1:1 Σxx W1:k−1 .
This follows from the matrix-derivative rule in Eq. (1) along with the Eq. (2) and taking expectation. The calculation of the off-diagonal Hessian blocks (kl-th block of size Mk Mk−1 × Ml Ml−1 )
involves the product rule. Note that the two occurrences of a weight matrix Wl, in Eq. (2), are once non-transposed (in WL:1xx⊤) and once transposed (in Wk+1:L or W1:k−1 respectively for k < l or k > l). For simplicity, let us express these parts without adding them and directly write the other Hessian contribution with respect to the transposed matrix, giving:
∀ k ̸= l, H̃klL := ∂2L
∂Wl∂Wk = Wk+1:LWL:l+1 ⊗ Wk−1:1 Σxx W1:l−1 . (3)
∀ k < l ĤklL := ∂2L
∂Wl⊤∂Wk = Wk+1:l−1 ⊗ Wk−1:1 Ω⊤ WL:l+1 . (4)
∀ k > l ĤklL := ∂2L
∂Wl⊤∂Wk = Wk+1:L ΩW1:l−1 ⊗ Wk−1:l+1 . (5)
Equivalence to Gauss-Newton Decomposition. A common approach is to look at the Hessian map from the perspective of the Hessian chain rule, where we have that, HL = Ho +Hf , with
Ho = E px,y [ ∇θF (x)⊤ [∂2ℓx,y] ∇θF (x) ] , and Hf = E px,y [ K∑ c=1 [∂ℓx,y]c ∇2θ Fc(x) ] .
For the MSE loss, the Gauss-Newton decomposition is in fact equivalent to what we discussed before (see details in Appendix S1), where Ho contains the blocks HkkL and H̃ kl L , while Hf consists of ĤklL (although with the non-transposed matrix). Henceforth, we will refer to the first term Ho as the outer-product Hessian, while we coin the second-term Hf as the functional Hessian.

heading: 3.2 Range of the Hessian map

text:
Assuming a local Taylor-series approximation of the loss’ gradient, we have that for ∥∆θ∥ < ϵ , ∇θ+∆θ L ≈ ∇θL+HL ∆θ. This indicates how the gradients will change over any local perturbation ∆θ. Also, this holds over successive iterations of an optimization algorithm such as gradient descent. As a result, this serves to show the significance of the Hessian range as since its dimension (i.e., rank) will dictate the dimension of the space where gradients evolve — something which has been discussed only empirically before [40].
Moving on, to best highlight the layer-wise structure present in the Hessian range, let us multiply the two parts of the Hessian with a vector ∆θ, which we decompose as ∆θ =[ vecr(∆W 1)⊤ . . . vecr(∆W L)⊤ ]⊤ .
Range of the outer-product Ho The product of the k-th row-block Hk•o , corresponding to the kth layer, with ∆θ can be written succinctly as, Hk•o · ∆θ = vecr ( Wk+1:L · ∆̄ ·ΣxxW1:k−1 ) , where ∆̄ := ∑L l=1 W
L:l+1 ∆Wl Wl−1:1 ∈ RK×d. This essentially follows from the identity, vecr AXB = (A⊗B⊤) vecr X (see proof in Appendix S2.5). Note that ∆̄ represents the net change on the prediction map induced by changes to the weight matrices in the forward pass. We see that: (1) ∆θ is linearly compressed into a highly interpretable matrix ∆̄ with Kd entries. (2) The same compressed ∆̄ is shared across all result blocks as it is independent of the row block index k. Overall, this already hints that there is a significant intrinsic structure in the Hessian that constrains its range.
Range of the functional Hessian Hf Here we multiply with ∆̂θ, which is similar to ∆θ except that we consider ∆Wl⊤ instead of ∆Wl . Then the product corresponding to kth layer is, Hk•f · ∆̂θ = vecr ( Wk+1:L Ω [∆<k]⊤ + [∆>k]⊤ ΩW1:k−1 ) , where ∆<k :=∑k−1
l=1 W k−1:l+1 ∆Wl Wl−1:1 and ∆>k := ∑L l=k+1 W
L:l+1 ∆Wl Wl−1:k+1. Notice that the range of Hf is also inherently constrained like in the case of Ho, but there are two important differences. First, the data dependent part is now the covariance Ω = E [δx,y x⊤]. Clearly, if this matrix is low rank (say s), this will directly impact the rank of Hf . The other significant difference is that the weight matrix product is split at layer k. This reflects the fact that upstream and downstream layers have a different effect. We will see ahead that these factors will neatly gives rise to a dependence on the sum of hidden-layer widths.

heading: 4 Main result: Analysis of the Hessian rank

text:
Preliminaries. Let us denote the rank of the uncentered covariance Σxx = E [xx⊤] by r. If r < d, then without loss of generality, consider Σxx := (Σxx) r×r, which is always possible by pre-processing the input. Thus, Σxx ≻ 0, always. Also, in such a case, we take W1 ∈ RM1×r. Further, the only assumption we make in our analysis is A1, which is in fact guaranteed at typical initialization almost surely (c.f. Appendix S2.6). In Section 6, we see what happens while training.
Assumption A1. Maximal Rank: ∀ l ∈ [L], Wl ∈ RMl×Ml−1 has rank equal to min(Ml,Ml−1).
Lastly, the omitted proofs in the coming subsections are located in Appendices S2, S3, S4 respectively.

heading: 4.1 Analytical tool

text:
The key idea of our analysis technique is to reduce the rank of involved matrices to the rank of a certain special kind of matrix (or its variant), Z, as shown below:
Z = ( Iq ⊗C D⊗ In ) , with C ∈ Rm×n , D ∈ Rp×q . (6)
This row-partitioned matrix has a characteristic structure, where an identity matrix alternates between the two sides of the Kronecker product. Such matrices are in fact omnipresent in the Hessian structure, and importantly for our purpose, they possess additional properties on their rank. Inherent to these properties and our analysis, is the use of generalized inverse [41] and oblique (non-orthogonal) projector matrices. The following Lemma 1 from [42] details such a result: Lemma 1. Let Z be a matrix as in Eq. (6). Then, rk(Z) = q rk(C) + n rk(D)− rk(C) rk(D) .

heading: 4.2 Rank of the outer-product Hessian

text:
Consider the following decomposition of Ho, which reveals its ‘outer-product’ nature: Proposition 2. For a deep linear network, Ho = AoBoAo⊤ , where Bo = IK ⊗Σxx ∈ RKd×Kd, and A⊤o = ( WL:2 ⊗ Id · · · WL:l+1 ⊗W1:l−1 · · · IK ⊗W1:L−1 ) ∈ RKd×p ,
where p is the number of parameters. A straightforward consequence is that if there is no bottleneck in between, i.e., no hidden-layer with width Mi < min(K, d), then the matrix Bo will control the rank of Ho. Hence, as a first upper bound we get, rk(Ho) ≤ min (rk(Ao), rk(Bo)) = rk(Bo) = rk(IK) rk(Σxx) = Kr . Such a decomposition is however not new (see [43]), but this only forms an initial step of our analysis and the current bound can be loose in the bottleneck case (e.g., an auto-encoder). Let us define the minimum dimension to be q := min(r,M1, · · · ,ML−1,K). Our main theorem can then be stated as: Theorem 3. Consider the matrix Ao mentioned in Proposition 2. Under the assumption A1, rk(Ao) = r rk(W 2:L) +K rk(WL−1:1)− rk(W2:L) rk(WL−1:1) = q (r +K − q) .
Now, from Theorem 3, it is evident that we can simply upper bound the rank of Ho, by the rank of Ao. But actually, it is possible to show an equality (using Lemma 18), as described below: Corollary 4. Under the setup of Theorem 3, the rank of Ho is given by rk(Ho) = q (r +K − q) .
Remark. It should be emphasized that this analysis not only delivers the rank of the outer-product Hessian but also of Neural Tangent Kernel [44] (see Appendix S9.5), Fisher information matrix, network Jacobian, due to their underlying intimate relationship, unaltered through the lens of rank.

heading: 4.3 Rank of the functional Hessian

text:
For analyzing the rank of the functional Hessian Hf , we will continue operating by having one of the derivatives with respect to a transposed weight matrix (here, Wl ⊤ ), since rank does not change with
column or row permutations. We denote this modification of the functional Hessian by Ĥf . Then from Eqs. (4, 5), we can observe that there is a common structure within the blocks contained in the column l. Namely, all the weight matrix-chains have either l − 1 or l + 1 as their right indices. So our approach will be to bound the rank of the individual column blocks, as formalized below:
Theorem 5. For a deep linear network, the rank of l-th column-block, Ĥ•lf , of the matrix Ĥf , under the assumption A1 is given as rk(Ĥ•lf ) = q̂ Ml−1+ q̂ Ml− q̂ 2 , for l ∈ [2, · · · , L−1]. When l = 1, we have rk(Ĥ•1f ) = q̂ M1 + q̂ s− q̂ 2 . And, when l = L, we have rk(Ĥ•Lf ) = q̂ ML−1 + q̂ s− q̂ 2 . Here, q̂ := min(r,M1, · · · ,ML−1,K, s) = min(q, s) and s := rk(Ω) = rk(E [δx,y x⊤]).
The upper bound on the rank of Hf follows by combining the above result over all the columns: Corollary 6. Under the setup of Theorem 5, the rank of Hf can be upper bounded as, rk(Hf ) ≤ 2 q̂ M + 2 q̂ s− L q̂ 2 , where M = ∑L−1 i=1 Mi .
Although the above result is an upper bound, empirically this is precisely the formula at initialization, and thus we have the tightest upper bound on the rank of the functional Hessian. Besides, in general, we find that at initialization s = min(r,K), hence q̂ = q and we will just use q hereafter for simplicity.
Block-column independence. A surprising element of the above analysis is that just adding the ranks of the block-columns, corresponding to the respective layers, gives the rank of the entire Hf which is tight. This phenomenon is quite straightforward to see in a 2-layer network and there Corollary 6 is an equality. However, the more interesting observation is that this holds even for arbitrary depth and also extends to networks with non-linearities such as ReLU and Tanh. This implies that the column spaces associated with the layerwise block-columns do not overlap. Thus, Hf is similar to a block diagonal matrix, and it should be possible to uncover the similarity transformation. But this is beyond the current scope, and we leave it as an open question.

heading: 4.4 Overall bound on the Hessian Rank

text:
Finally, in order to get an upper bound on the rank of the entire Hessian, we simply use rk(A+B) ≤ rk(A) + rk(B), along with the Corollary 4 and Corollary 6 (with q̂ = q as noted above), to obtain:
rk(HL) ≤ rk(Ho) + rk(Hf ) ≤ 2 qM − Lq2 + 2 q s+ q (r +K − q) .
Fact 7. The following equality holds empirically: rk(HL) = 2qM − Lq2 + q(r +K) .
This implies that our upper bound is off by just a constant additive factor of 2 q s − q2, which is another startling finding. Thus, revealing that the intersection of the Ho, Hf column spaces has a rather small dimension. E.g., take the typical case of no bottlenecks, q = s, then our upper bound exceeds the true rank by a small constant q2, i.e., minimum dimension squared. This suggests that the direct sum of their column spaces is not too far-fetched as an approximation to the column space of HL. Previously, [30] empirically noted a similar observation for 1-hidden layer networks and [33] showed a high degree of mutual orthogonality in the asymptotic regime. Our result shows a similar consequence in the finite case.
Alternative interpretation. Besides the above result, that the rank of the Hessian is proportional to the sum of widths, there is an alternate way of viewing this. Let us calculate the rank deficiency in the network when (uncentered) input-covariance has rank, i.e., r = d. Using Fact. (7) this comes
out to rank-deficiency(HL) = L−1∑ i=0 (Mi − q)(Mi+1 − q) , whereas the number of parameters is
equal to p = ∑L−1
i=0 Mi Mi+1. Hence this lends an elegant interpretation to our formula, whereby the amount of rank deficiency is equal to the number of parameters of a hypothetical network whose all layer-widths have been subtracted by the minimum layer-width of the original network.

heading: 4.5 Hessian Rank as effective # of parameters

text: Consider a quadratic optimization problem, argminθ∈Rp θ ⊤ Mθ, where assume the matrix M has a reduced rank r < p and is in rank normal form, M = [Mr;0]. As a result, we get an equivalent but reduced problem argminθr∈Rr θ ⊤ r Mr θr of size r < p, where θr is the vector containing the first r parameters. More generally, we can reparameterize θ 7→ U⊤θ where U contains the (top-r) eigenvectors of M. Thus, here it is strikingly clear that rank provides the effective number of parameters. Further, we can go to the case of neural networks by simply utilizing the 2nd order Taylor series expansion of the loss L— and so the Hessian HL plays the role of M. Overall, this suggests that the above results on the Hessian rank can provide insights into the effective # of parameters in neural networks, or in other words, into the inherent complexity of neural networks.

heading: 5 Empirical Results

heading: 5.1 Verification of Rank formulas and their behaviour

text:
Setup. We test our results on a variety of datasets: MNIST [45], FashionMNIST [46], CIFAR10 [47]; for various loss types: MSE, cross-entropy, cosh; across several initialization schemes: Glorot [48], uniform, orthogonal [21]. Our theory extends to all these settings. However, due to space constraints we only show a subset of experiments here, but the rest can be found in the Appendix S9.
Procedure. To verify the prediction of our theoretical results, we perform an exact calculation of the rank by computing the full Hessian and the corresponding singular value decomposition (SVD). The available iterative schemes for rank approximation (c.f. [49]), although more memory-efficient, are only effective for well-separated spectra and thus cannot provide useful approximations in the case of neural network Hessians. Besides the exact Hessian computation, we also utilize FLOAT-64 precision to ensure ‘true’ rank calculation, resulting in increased memory costs. Hence, we downscale the image resolution to d = 64 to test on more realistic networks.
Results. We study how the rank varies as a function of the sample size N and the network architecture (for varying widths). Fig. 2 shows this for a linear network on CIFAR10 with MSE loss. First, in Fig 2a, we observe that our predictions match the true rank exactly across all sample sizes as the dependence on N is only exhibited in the rank of the empirical covariance Σ̂xx, confirming that rank is largely a distribution-independent quantity. So, for the rest of our experiments, we sufficiently subsample to ensure that the empirical and true covariance have the same rank. Next, in Fig. 2b, we see that our rank formulas hold for arbitrary-sized network architectures. To contextualize the growth of rank with increasing width, in Fig. 2c, we normalize it by # params p. We notice that rank/# params, which intuitively captures the fraction of effective parameters, saturates down to a small level — signalling the extent of redundancy present in the network parameterization (similar plots across depth and simulation of rank/# params on larger settings can be found in S9.1, S9.2).

heading: 5.2 The case of non-linearities

text:
Although the linear nature of the neural network was crucial to our analysis, in this section we show experimentally that our results also extend to the non-linear setting — as numerical rank [50].
Visual comparison of the Hessian spectra. Let us first understand how non-linearities affect the Hessian spectrum relative to the spectrum of linear networks. Fig. 3 compares the spectra of HL, Hf , Ho in these two scenarios (linear vs Tanh), with a zoomed-in inset near the cut-off obtained from rank formulas corresponding to the linear case. We can observe the presence of numerous tiny, but not exactly zero, eigenvalues in the non-linear case. So, if we were to measure the rank with a threshold up to machine precision — as we did in the linear case — this would result in an inflation of the rank measurement for the non-linear scenario. From a practical point of view, tiny but non-zero eigenvalues hold little significance, so a more relevant quantity is the numerical rank [50] that uses a reasonable threshold to weed out such extraneous eigenvalues. The numerical rank, or alternatively the size of bulk around zero, for the non-linear case, indeed seems to be captured by our (linear) rank formulas to high fidelity, as evident from Fig. 3. Similar results for other non-linearities, loss functions, datasets can be found in the Appendix S9.4.
Quantitative measure of the fidelity of Rank formulas. To complement the visual grounds presented above, we now quantitatively measure the (in)significance of such spuriously tiny eigenvalues, in terms of the reconstruction error incurred by excluding them. Hence, we perform a low-rank approximation via the SVD and measure the (relative) reconstruction error at the value of rank from our formulas of the linear case. Fig. 4 displays the reconstruction error as a function of the # of top eigenvectors employed, for a ReLU network. As a reference, we consider the empirical rank measurement obtained at machine precision in this case.
We find that using the linear rank value provides an excellent reconstruction, hence demonstrating the fidelity of our rank formulas to serve as a measure of numerical rank in the non-linear case. The same observation extends to other non-linearities and losses, which we highlight in the Appendix S9.3. Consequently, iterative Hessian estima-
tion procedures, e.g. in second-order optimization methods [16, 51], could benefit from the linear rank as a guiding criterion for their design of Hessian approximation. Besides, these experiments also indicate that previous bounds, such as those by Jacot et al. [33], on the rank of outer-product Hessian and functional Hessian are quite coarse to be of much use (i.e., even > # parameters). This is because these bounds have a linear dependence on the product of: # of samples N and # of classes K. For the same reason, other works [16, 52] that bound the rank of the outer-product Hessian Ho, trivially, based on the # of samples N are of little use.

heading: 6 Evolution of Rank during training

text:
The upper bounds on the Hessian rank detailed before inherently depend on the rank of the weight matrices. While initialization guarantees them to be of maximal rank, the rank of weight matrices might possibly decrease during training, thus bringing about a decrease in the Hessian rank. Under some additional assumptions, Lemma 8 shows that this does not happen and the rank remains constant.
Lemma 8. For a deep linear network, consider the gradient flow dynamics Ẇlt = −η∇WlLS(θ) ∣∣ θ =θt . Assume: (a) Centered classes: 1N ∑N i:yic=1 xi = 0, ∀ c ∈ [1, . . . ,K]. (b) Balancedness at initialization: Wk+1 ⊤
0 W k+1 0 = W k 0W
k⊤
0 . (c) Square weight-matrices: Wl ∈ RM×M , ∀ l and K = d = M . Then for all layers l, rk(Wlt) = rk(Wl0), ∀ t <∞ .
Balancedness is a common assumption that has been used in many previous works, like Arora et al. [53]. Centered classes can easily be enforced via a pre-processing step, however empirically this is not required. While the proof (see Appendix S5) holds for square case, empirically we also find this to be true for non-square matrices (Fig. 5, left) and non-linearities as shown in Fig. S2.
Consequence. An implication of this result is that our upper bounds on the Hessian rank remain valid throughout the training. Even if the rank of the weight matrices were to decrease, say in the rectangular case, the Hessian rank would only decrease and our bounds would still be valid. The other avenue for a decrease in rank is learning-driven, and as Ω = E [δx,y x⊤]→ 0, the functional Hessian
Hf → 0 (as it has an explicit dependence on the residual δx,y ) . So, if the learning architecture is powerful enough, the rank of Hf will approach 0, as well as leading to a decrease in the rank of HL, and so rk(HL)→ rk(Ho). In other words, the loss Hessian is completely captured through the outer product Hessian at convergence. We demonstrate this empirically via Fig. 5 (right) where we train a linear network using a linear teacher and visualize the rank dynamics as well as our upper bounds. We provide more details as well as experiments for the non-linear case in the Appendix S5.

heading: 7 Further results

heading: 7.1 Provable Hessian degeneracy with non-linearities

text:
From Section 5.2, it is clear that our upper bounds faithfully estimate the numerical rank in the non-linear case, despite the numerous tiny eigenvalues which cause inflated rank measurements. This might raise the question if it is possible to establish, in this non-linear case, that the Hessian has provable degeneracy and not just approximate? The challenge is that here the data distribution manifests additionally via the activations at each layer, thus a theoretical analysis seems intractable without imposing strong assumptions. For a 1-hidden layer network, F (x) = W2σ(W1 x), we show it is still possible to get a pessimistic yet non-trivial upper bound with the following (mild) assumption:
Assumption A2. For each active hidden neuron i, the weighted input covariance has the same rank as the overall input covariance, i.e., rk(E [αx xx⊤]) = rk(Σxx) = r, with αx = σ′(x⊤ W1i •) 2 .
Theorem 9. Consider a 1-hidden layer network with non-linearity σ such that σ(z) = σ′(z)z and let M̃ be the # of active hidden neurons (i.e., probability of activation > 0). Then, under assumption A1 and A2, rank of Ho is given as, rk(Ho) ≤ rM̃ + M̃K − M̃ .
Assumption A2 is rather mild, i.e., in the finite-sample case, it holds as soon as the # of samples N > 2d, for typical initialization of parameter weights. Besides, the class of non-linearities which satisfy the above-mentioned condition includes e.g., ReLU, Leaky-ReLU. Further, this result extends to HL:
Corollary 10. At convergence to the minimum, the rank of the loss Hessian HL, for the same setup as Theorem 9, is upper bounded by: rk(HL) ≤ rM̃ + M̃K − M̃ .
Contrast this with the view from [54], who claim the spectrum to be generically non-degenerate. Or, unlike [55], we establish this without any assumptions on a particular kind of overparameterization.
Fact 11. For multiple hidden-layers, the following generalization of Theorem 9 holds empirically, rk(Ho) ≤ p−M1(d−r)− ∑L−1 i=1 Mi , where p is the # of parameters and assuming no dead neurons.
While these bounds are likely to be quite loose as noticeable from Section 5.2, but more importantly they help establish provable degeneracy of the Hessian at the minimum, with the number of ‘absolutelyflat’ directions (i.e., those in the Hessian null space) in proportion to the sum of hidden-layer sizes.

heading: 7.2 Effect of bias on the rank of Hessian

text:
Now, we see how the Hessian rank changes when bias is enabled throughout a deep linear network. We make the following simplifying assumption, which is actually a standard convention in practice.
Assumption A3. The input data has zero mean, i.e., x ∼ px is such that E [x] = 0.
Theorem 12. Under the assumption A1 and A3, for a deep linear network with bias, the rank of Ho is upper bounded as, rk(Ho) ≤ q(r +K − q) +K , where q := min(r,M1, · · · ,ML−1,K).
The proof can be found in the Appendix S7. Empirically, we do not require the input to be mean zero and our upper bound actually holds with equality. Also, we list rank formulas for functional Hessian and the overall loss Hessian in Appendix S7, in the non-bottleneck case. E.g.,
Fact 13. rk (HL) = 2q′M + q′(r+K)− Lq′2 + Lq′ , where q′ := min(r+1,M1, · · · ,ML−1,K).
Here too, rank deficiency has a cleaner interpretation of being equal to the # of parameters in a hypothetical network with bias enabled, but with the minimum dimension q′ (that reflects the homogeneous
coordinate at input) subtracted: rank-deficiency(HL) = L−1∑ i=0 (Mi + 1 − q′)(Mi+1 − q′) .

heading: 8 Conclusion

text:
Summary. Our paper provides a precise understanding of how the neural network structure constrains the Hessian range and the resulting rank deficiency. In contrast to the number of parameters which are proportional to layer-widths squared, we obtain that rank is proportional to layer-width. The proof strategy relies on bounding the rank of the two parts of the Hessian separately, i.e., the outerproduct Hessian Ho and the functional Hessian Hf , both of which are replete with the special Z-like structure. The analysis also reveals several striking properties of the Hessian, such as surprisingly small overlap in the column spaces of Ho and Hf , and independence of the layer-wise column blocks in Hf . While our results were derived assuming linear activations, we demonstrate that, even with non-linearities, our formulas faithfully capture the numerical rank.
All in all, by providing fundamental insights into the rank of the Hessian map — which ultimately point to the sources and extent of redundancy in overparameterized neural networks, as a result of its compositional structure — our work paves the way to exciting avenues for future research.
Discussion. In particular, our results merit discussion on some important aspects of deep learning:
(i) Overparameterization: Modern DNNs, with billions of parameters, are in stark contrast to the traditional statistical viewpoint of having # of parameters approximately equal to the # of samples. While several works have argued for measuring model complexity instead through weight norms [56], margins [57], compressibility [58], yet it remains hard to get an interpretable ballpark on the model complexity of neural networks. Since rank intuitively captures the notion of effective parameters, it could be a possible alternative to benchmark overparameterization, e.g. for double descent [38].
(ii) Flatness: A growing number of works [59–61] correlate the choice of regularizers, optimizers, or hyperparameters, with the additional flatness brought about by them at the minimum. However, the significant rank degeneracy of the Hessian, which we have provably established, also points to another source of flatness — that exists as a virtue of the compositional model structure —from the initialization itself. Thus, a prospective avenue of future work would be to compare different architectures based on this inherent kind of flatness.
(iii) Generalization: An interesting observation available from our work is that factors such as width, depth, enabling bias — commonly observed to improve generalization — also result in decreasing the rank/# parameters ratio, see Fig. S8b, S8c, S3. In a similar vein, recent work of [62] has provided a lower bound to the generalization error of statistical estimators in terms of the rank of the Fisher (which is intimately related to the Hessian) divided by # of parameters. Practically, one could use a further relaxation of rank as nuclear norm normalized by the spectral norm, in scenarios with spurious rank inflation. Overall, this suggests the relevance of studying the link between rank and generalization.
Limitations. Although empirically our (linear) rank results faithfully capture the behaviour of Hessian rank with non-linearities, we still lack a rigorous theoretical characterization of the same (which will likely require incorporating additional distribution-specific assumptions). Besides, our analysis is limited to the case of fully-connected networks, and it would be interesting to extend this to other architectures such as convolutional networks, residual networks, etc. Lastly, it still needs to be shown theoretically that our upper-bound on the rank of the functional Hessian holds with equality, despite that this is what we observe in practice.
Acknowledgments and Disclosure of Funding
We would like to thank Nicolò Ruggeri for reviewing a first draft of the paper. Further, we would like to thank the members of DA lab and Bernhard Schölkopf for useful comments. Sidak Pal Singh would also like to acknowledge the financial support from Max Planck ETH Center for Learning Systems.

title: Analytic Insights into Structure and Rank of Neural Network Hessian Maps


summaries: This paper makes two contributions: 1 - It presents a framework for measuring linear symmetry based disentanglement (LSBD). In particular, it addresses the challenge that LSBD is only defined with respect to an optimal decomposition of the latent space $Z = Z_1 \oplus \ldots \oplus Z_k$ that needs to be identified by the metric. 2 - The metric serves as additional supervision in the training of a VAE on toy datasets with at most two symmetry transformations. The results show quantitative improvements in terms of disentanglement.

summaries: Summary:  This paper aims to operationalize the symmetry-based disentanglement idea proposed in Higgins et al., 2018, and proposes a novel loss function that can be used to both evaluate and learn disentangled representations (including learning from datasets where only a subset of samples are fully labeled). The paper includes some experimental validation of the proposed ideas on synthetic datasets. It also includes cross-comparisons between both the LSBD-based metric and method to state of the art disentangling metrics and methods, which demonstrate the complementary aspects of the LSBD method (e.g., its ability to capture multi-dimensional disentangled factors, for example rotations in a euclidean plane).  Overall, the paper is clearly written and makes a positive contribution in pushing for disentangling metrics that are motivated by a novel formalism. The impact of this paper is slightly limited due to the strength of supervision required (full supervision of all factors of variation) for implementing both the D_LSBD metric and the loss.

summaries: This work focuses on developing a metric evaluation metric and a semi-supervised VAE-based model for linear symmetry-based disentanglement (LSBD)[1]. When assuming knowledge of linearly disentangled group representation $\rho$, the authors deduce that LSBD is fulfilled if the last requirement is met (equivariance of a map h). The authors propose to measure the equivariance by simply quantify the equivariance of the encoding map w.r.t. to the group and observations. Although a straightforward thought, computing the metric is challenging. Therefore, the authors propose an approximation by calculating the dispersion of the inverse group representation obtained through a PCA. Similar to the evaluation metric, the authors propose LSBD-VAE, a semi-supervised version of $\Delta$-VAE to regularise the latent space based on its dispersion. They show through empirical evaluation that their method outperforms other unsupervised disentanglement approaches w.r.t. to the proposed evaluation metric.

summaries: This paper proposes a new metric $D_{LSBD}$ to measure Linear Symmetry Based Disentanglement. The metric is motivated from an idealized setting before outlining a practical upper bound that can be realized. The authors also apply their new metric as an additional loss term to a $\Delta$-VAE model and show that it greatly enhances Linear Disentanglement while also agreeing with past notions of Disentanglement. The experiments, while simple and using only $SO(2)$ as a subgroup, are demonstrative of the proposed approach.

abstractText: The definition of Linear Symmetry-Based Disentanglement (LSBD) formalizes 1 the notion of linearly disentangled representations, but there is currently no metric 2 to quantify LSBD. Such a metric is crucial to evaluate LSBD methods and to 3 compare to previous understandings of disentanglement. We propose DLSBD, a 4 mathematically sound metric to quantify LSBD, and provide a practical implemen5 tation. Furthermore, from this metric we derive LSBD-VAE, a semi-supervised 6 method to learn LSBD representations. We demonstrate the utility of our metric 7 by showing that (1) common VAE-based disentanglement methods don’t learn 8 LSBD representations, (2) LSBD-VAE as well as other recent methods can learn 9 LSBD representations, needing only limited supervision on transformations, and 10 (3) various desirable properties expressed by existing disentanglement metrics are 11 also achieved by LSBD representations. 12

authors:
H. 345 Caselles-Dupré
M.G. Ortiz
D. Filliat

authors:
T.Q. Chen
X. Li
R.B. Grosse
D.K. Duvenaud

title: Isolating sources of disentanglement

authors:
T. Cohen
M. Welling

authors:
T.S. Cohen
M. Welling

authors:
C. 355 Eastwood
C.K. Williams

authors:
H. Kim
A. Mnih

title: Disentangling by factorising

venue: In International Conference on Machine

authors:
D.P. Kingma
M. Welling

title: Auto-Encoding Variational Bayes

venue: In International Conference

authors:
A. Kumar
P. Sattigeri
A. Balakrishnan

title: Variational inference of disentangled

authors:
S.A. 371 Nene
S.K. Nayar
H Murase

title: Columbia object image library (coil-20)

authors:
M. Painter
A. Prugel-Bennett
J. Hare

title: Linear disentangled representations and

authors:
L.A. Perez Rey
V. Menkovski
J. Portegies

title: Diffusion variational autoencoders

authors:
R. 377 Quessard
T.D. Barrett
W.R. Clements

authors:
D.J. 380 Rezende
S. Mohamed
D. Wierstra

authors:
K. 383 Ridgeway
M.C. Mozer

authors:
I. 385 Sosnovik
M. Szmaja
A. Smeulders

title: Scale-Equivariant Steerable Networks

authors:
Z. Wu
S. Song
A. Khosla
F. Yu
L. Zhang
X. Tang
J. Xiao

title: 3D ShapeNets: A

text:
The definition of Linear Symmetry-Based Disentanglement (LSBD) formalizes1 the notion of linearly disentangled representations, but there is currently no metric2 to quantify LSBD. Such a metric is crucial to evaluate LSBD methods and to3 compare to previous understandings of disentanglement. We propose DLSBD, a4 mathematically sound metric to quantify LSBD, and provide a practical implemen-5 tation. Furthermore, from this metric we derive LSBD-VAE, a semi-supervised6 method to learn LSBD representations. We demonstrate the utility of our metric7 by showing that (1) common VAE-based disentanglement methods don’t learn8 LSBD representations, (2) LSBD-VAE as well as other recent methods can learn9 LSBD representations, needing only limited supervision on transformations, and10 (3) various desirable properties expressed by existing disentanglement metrics are11 also achieved by LSBD representations.12
1 Introduction13
Learning low-dimensional representations that disentangle the underlying factors of variation in data14 is considered an important step towards interpretable machine learning with good generalization. To15 address the fact that there is no consensus on what disentanglement entails and how to formalize it,16 Higgins et al. (2018) propose a formal definition for Linear Symmetry-Based Disentanglement, or17 LSBD, arguing that underlying real-world symmetries give exploitable structure to data.18
However, there is currently no metric to quantify LSBD. Such a metric is crucial to properly evaluate19 methods aiming to learn LSBD representations and to relate LSBD to previous definitions of disentan-20 glement. Although previous works have evaluated LSBD by measuring performance on downstream21 tasks (Caselles-Dupré et al., 2019) or by measuring specific traits related to LSBD (Painter et al.,22 2020; Quessard et al., 2020), none of these evaluation methods directly quantify LSBD according to23 its well-formalized definition.24
We propose DLSBD, a well-formalized and generally applicable metric that quantifies the level of25 LSBD in learned data representations. We show an intuitive justification of this metric, as well26 as its theoretical derivation. We also provide a practical implementation to compute DLSBD for27 common symmetry groups. Furthermore, we show that our metric formulation can be used to derive28 a semi-supervised method to learn LSBD representations, which we call LSBD-VAE. To make29 LSBD-VAE more widely applicable, we also demonstrate how to disentangle symmetric properties30 from other non-symmetric properties, and how to quantify this disentanglement with DLSBD.31 We show the utility of DLSBD by quantifying LSBD in a number of settings, for a variety of datasets32 with underlying SO(2) symmetries and other non-symmetric properties. First, we evaluate common33 VAE-based disentanglement methods and show that most don’t learn LSBD representations. Second,34 we evaluate LSBD-VAE and other recent methods that specifically target LSBD, showing that they35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
can obtain much better DLSBD scores while needing only limited supervision on transformations.36 Third, we compare DLSBD with existing disentanglement metrics, showing that various desirable37 properties expressed with these metrics are also achieved by LSBD representations.38
2 Related Work39
Plenty of works have focused on learning and quantifying disentangled representations recently, but40 research has shown that there is little consensus about the exact definition of disentanglement and41 methods often do not achieve it as well as they proclaim (Locatello et al., 2019). To introduce some42 much-needed formalization, Higgins et al. (2018) proposed to define disentanglement with respect43 to symmetry transformations acting on the data. They used group theory to provide two formal44 definitions, which we refer to as (Linear) Symmetry-Based Disentanglement, or (L)SBD. In this45 paper we focus only on LSBD, not SBD.46
Several methods have been proposed to learn LSBD representations (Caselles-Dupré et al., 2019;47 Painter et al., 2020; Quessard et al., 2020). These methods also learn to represent the transformations48 acting on the input data, assuming various levels of supervision on these transformations. Other49 methods have previously focused on capturing transformations of the data outside the context of50 disentanglement as well (Cohen and Welling, 2015; Sosnovik et al., 2019; Worrall et al., 2017).51
3 Linear Symmetry-Based Disentanglement52
Higgins et al. (2018) provide a formal definition of linear disentanglement that connects symmetry53 transformations affecting the real world (from which data is observed) to the internal representations54 of a model. The definition is grounded in concepts from group theory, we provide a more detailed55 description of these concepts in the Supplementary Material.56
The definition1 considers a group G of symmetry transformations acting on the data space X through57 the group action · : G ×X → X . In particular, G can be decomposed as the direct product of K58 groups G = G1 × . . .×GK . A model’s internal representation of data is modeled with the encoding59 function h : X → Z that maps data to the embedding space Z. The definition for Linearly Symmetry-60 Based Disentangled (LSBD) representations then formalizes the requirement that a model’s encoding61 h should reflect and disentangle the transformation properties of the data, and that the transformation62 properties of the model’s encoding should be linear. The exact definition is as follows:63
Definition: Linear Symmetry-Based Disentanglement (LSBD) A model’s encoding map h :64 X → Z, where Z is a vector space, is LSBD with respect to the group decomposition G =65 G1 × . . .×GK if66
1. there is a decomposition of the embedding space Z = Z1 ⊕ . . . ⊕ ZK into K vector67 subspaces,68
2. there are group representations for each subgroup in the corresponding vector subspace69 ρk : Gk → GL(Zk), k ∈ {1, . . . ,K}70
3. the group representation ρ : G→ GL(Z) acts on Z as71
ρ(g) · z = (ρ1(g1) · z1, . . . , ρK(gK) · zK), (1)
for g = (g1, . . . , gK) ∈ G and z = (z1, . . . , zK) ∈ Z with gk ∈ Gk and zk ∈ Zk.72 4. the map h is equivariant with respect to the actions of G on X and Z, i.e. , for all x ∈ X73 and g ∈ G it holds that h(g · x) = ρ(g) · h(x).74
Furthermore, we say that a group representation ρ is linearly disentangled with respect to the group75 decomposition G = G1 × . . .×GK if it satisfies criteria 1 to 3 from the LSBD definition above.76
1The original definition actually considers an additional set of world states W , but our definition is more practical and can be shown to be the same under mild conditions, see Supplementary Material.
4 Quantifying LSBD: DLSBD77
4.1 Intuition: Measuring Equivariance with Dispersion78
Figure 1: A dataset of images from a rotating object expressed in terms of the group G = SO(2) acting on a base image x0. It is possible to quantify the level of LSBD of an encoding map h by measuring its equivariance with respect to a group representation ρ. Since all data has been generated from x0, equivariance can be measured as the dispersion of the points {ρ(g−1n ) · h(xn)}Nn=1.
To motivate our metric, let’s first assume a set-79 ting in which a suitable linearly disentangled80 group representation ρ is known. Let’s further81 assume that the dataset of observations can be82 expressed with respect toG acting on some base83 point x0 ∈ X , i.e. {xn}Nn=1 = {gn · x0}Nn=1.84 Formally, this assumes that the action of G on85 X is regular. In this case, we can use the inverse86 group elements g−1n to transform each data point87 toward the base point x0, i.e.88
x0 = g −1 1 · x1 = . . . = g −1 N · xN . (2)
Since ρ is linearly disentangled, we only need to89 measure the equivariance of the encoding map90 h to quantify LSBD. Equivariance is achieved91 when h(g · x) = ρ(g) · h(x), for all g ∈ G, x ∈92 X . Given the dataset described above, we can93 check this property for x ∈ {xn}Nn=1 and g ∈94 {gn}Nn=1.2 In particular, from Equation (2) we95 can see that we have equivariance if96
h(x0) = ρ(g −1 1 ) · h(x1) = . . . = ρ(g −1 N ) · h(xN ). (3)
This not only characterizes perfect equivariance, but also allows for an efficient way to quantify how97 close we are to true equivariance, by measuring the dispersion of the points {ρ(g−1n ) · h(xn)}Nn=1.398 Given a suitable norm ‖ · ‖Z in Z, we can thus quantify LSBD in this setting as99
1
N N∑ n=1 ∥∥∥∥∥ρ(g−1n ) · h(xn)− 1N N∑ n′=1 ρ(g−1n′ ) · h(xn′) ∥∥∥∥∥ 2
Z
, (4)
i.e. we compute the mean of {ρ(g−1n ) · h(xn)}Nn=1 and use the average squared distance to this mean100 for points in {ρ(g−1n ) · h(xn)}Nn=1 as our LSBD metric, see Figure 1.101 However, this formulation requires knowing the right linearly disentangled group representation and102 a suitable norm in Z. Moreover, it implicitly assumes a uniform probability measure over the group103 elements {gn}Nn=1. In the next section we formulate our metric for a more general setting.104
4.2 DLSBD: A Metric for LSBD105
Generalizing the ideas from the previous section with concepts from measure theory, we propose a106 metric to measure the level of LSBD of any encoding h : X → Z given a data probability measure µ107 on X , provided that µ can be written as the pushforward GX(·, x0)#ν of some probability measure108 ν on G by the function GX(·, x0) for some base point x0. More formally,109
µ(A) = GX(·, x0)#ν(A) = ν ({g ∈ G | GX(g, x0) ∈ A}) , (5) for Borel subsets A ⊂ X . Note that this is only possible if the action GX is transitive.110 For example, the situation of a dataset with N datapoints {xn}Nn=1 = {gn · x0}Nn=1 corresponds to111 the case in which ν and µ are empirical measures on the group G and data space X , respectively:112
ν := 1
N N∑ i=1 δgi , µ := 1 N N∑ i=1 δxi . (6)
2Note that {gn}Nn=1 can be used to describe all known group transformations between elements in the dataset by means of composition and inverses, since xi = gi · (g−1j · xj). Thus it suffices to check equivariance for these N group transformations.
3Note that we do not actually need to know x0 nor h(x0).
We define the metric DLSBD for an encoding h and a measure µ as113
DLSBD := inf ρ∈P(G,Z) ∫ G ∥∥ρ(g)−1 · h(g · x0)−Mρ,h,x0∥∥2ρ,h,µ dν(g), with Mρ,h,x0 = ∫ G ρ(g′)−1 · h(g′ · x0)dν(g′), (7)
where the norm ‖·‖ρ,h,µ is a Hilbert-space norm depending on the representation ρ, the encoding map114 h : X → Z, and the data measure µ. More details of this norm can be found in the Supplementary115 Material. Moreover, P(G,Z) denotes the set of linearly disentangled representations of G in Z.116 Lower values of DLSBD indicate better disentanglement, zero being optimal.117
4.3 Practical Computation of DLSBD118
There are two main challenges for computing the metric of Equation (7). First, to calculate the119 integrals in the formula, all possible datapoints that can be expressed as g · x0 with g ∈ G =120 G1 × · · · × GK must be available. Second, the infimum of the integrals over all possible linearly121 disentangled representations must be estimated. This requires finding the possible invariant subspaces122 Z = Z1⊕· · ·⊕ZK induced by the encoding h over which the group representations are disentangled.123 We present a practical implementation of an upper bound to DLSBD for an encoding function h given124 a dataset X generated by some known group transformations. In particular, this approximation of125 DLSBD is designed for a group decomposition G = G1 × · · · ×GK where each Gk = SO(Dk) with126 k ∈ {1, . . . ,K} the group of rotations in Dk dimensions. This implementation approximates the127 integrals of Equation (7) by using the empirical distribution of X . The invariant subspaces of Z to the128 subgroup actions are found by applying a suitable change of basis. In the new basis, the disentangled129 group representations are expressed in a parametric form whose parameters are optimized to find the130 tightest bound to DLSBD. See Figure 2 for an intuitive description of the process.131 Assume there is a datasetX that can be modeled in terms of the group decompositionG = G1×· · ·Gk.132 For each Gk subgroup there is a set of known group elements Gk ⊆ Gk uniformly sampled such133 that the dataset is described in terms of all elements in G = G1 × · · · × GK and a base point x0 as134 X = {(g1, . . . , gK) · x0|gk ∈ Gk, k ∈ {1, . . . ,K}} .135 For each subgroup Gk we construct a set of encoded data Zk ⊆ Z whose variability should only de-136 pend on the action of Gk. The set Zk is given by Zk = {zk(g1, . . . , gK)|gj ∈ Gj , j ∈ {1, . . . ,K}},137 in which138
zk(g1, . . . , gK) = h((g1, . . . , gK) · x0)− 1 |Gk| ∑ g′∈Gk h((g1, . . . , gk−1, g ′, gk+1, . . . , gK) · x0). (8)
Similar to (Cohen and Welling, 2014), we find a suitable change of basis that exposes the invariant139 subspace Zk corresponding to the k-th subgroup Gk. The new basis is obtained from the eigenvectors140 resulting from applying Principal Component Analysis (PCA) to Zk. Each element in Zk is projected141 into the first Dk eigenvectors. The new set is denoted as Z ′k ⊆ RDk with elements z′k(g1, . . . , gK) ⊆142 RDk that are the projected versions of zk(g1, . . . , gK).143 (Quessard et al., 2020) describes how one could parameterize the subgroup representations of SO(Dk)144 for arbitrary Dk but here we will focus on Gk = SO(2). In this case, we can parameterize each145 subgroup representation in terms of a single integer parameter ω ∈ Z as ρk,ω(gk) corresponding146 to a 2 × 2 rotation matrix whose angle of rotation is ω multiplied by the known angle associated147 to the group element gk ∈ Gk = SO(2). For this subgroup we can approximate the Mρ,h,x0 from148 Equation (7) as Mk,ω given by149
Mk,ω = 1 |G| ∑
(g1,...,gK)∈G
ρk,ω(g −1 k ) · z ′(g1, . . . , gK). (9)
Similar to Equation (7) we would like to find the optimal ρk,ω that minimizes the integral over the150 group representations. We can define a parameter search space Ω ⊆ Z, e.g. Ω = [−10, 10] for finding151 the optimal ω ∈ Ω that minimizes the dispersion, this is expressed in the following equation152
D(k)LSBD = min ω∈Ω
1 |G| ∑
(g1,...,gK)∈G
‖ρk,ω(g−1k ) · z ′(g1, . . . , gK)−Mk,ω‖2. (10)
EachD(k)LSBD measures the degree of equivariance of the projected embeddings for each k-th subgroup153 corresponding to the best fitting group representation. The upper bound to the metric is finally obtained154 by averaging across all subgroups DLSBD ≤ 1K ∑K k=1D (k) LSBD.155
5 Learning LSBD Representations: LSBD-VAE156
In this section we present LSBD-VAE, a semi-supervised VAE-based method to learn LSBD repre-157 sentations. The main idea is to train an unsupervised Variational Autoencoder (VAE) (Kingma and158 Welling, 2014; Rezende et al., 2014) with a suitable latent space topology, and use our metric as an159 additional loss term for batches of transformation-labeled data.160
Assumptions LSBD-VAE requires some knowledge about the group structure G that is to be161 disentangled. Concretely, the group and its decomposition G = G1 × . . .×GK should be known,162 as well as a suitable linearly disentangled group representation ρ : G→ GL(Z) and a latent space163 Z = Z1 ⊕ . . . ⊕ ZK . Moreover, we assume there exists an embedded submanifold ZG ⊆ Z such164 that the action of G on Z restricted to ZG is regular, and ZG is invariant under the action. Only ZG165 will then be used as the codomain for the encoding map, h : X → ZG.166 We demonstrate the assumptions above for the common group structure G = SO(2)× SO(2). For167 the group representation ρ = ρ1 ⊕ ρ2, with Z = R2 ⊕ R2, we can use rotation matrices in R2 for168 ρ1 and ρ2. We can then use 1-spheres S1 = {z ∈ R2 : ‖z‖ = 1} for the embedded submanifold:169 ZG = S
1 × S1. In this case, the action of G on Z restricted to ZG is indeed regular, and ZG is170 invariant under the action.171
Unsupervised Learning on Latent Manifold To learn encodings only on the latent manifold172 ZG, we use a Diffusion Variational Autoencoder (∆VAE) (Perez Rey et al., 2020). ∆VAEs can173 use any closed Riemannian manifold embedded in a Euclidean space as a latent space (or latent174 manifold), provided that a certain projection function from the Euclidean embedding space into the175 latent manifold is known and the scalar curvature of the manifold is available. The ∆VAE uses176 a parametric family of posterior approximates obtained from a diffusion process over the latent177 manifold. To estimate the intractable terms of the negative ELBO, the reparameterization trick is178 implemented via a random walk.179
In the case of S1 as a latent (sub)manifold, we consider R2 as the Euclidean embedding space, and180 the projection function4 Π : R2 → S1 normalizes points in the embedding space: Π(z) = z/|z|. The181 scalar curvature of S1 is 0.182
4This projection function is not defined for z = 0, but this value does not occur in practice.
Semi-Supervised Learning with Transformation Labels Caselles-Dupré et al. (2019) proved183 that LSBD representations cannot be inferred from a training set of unlabeled observations, but that184 access to the transformations between data points is needed. They therefore use a training set of185 observation pairs with a given transformation between them.186
However, we posit that only a limited amount of supervision is sufficient. Since obtaining supervision187 on transformations is typically more expensive than obtaining unsupervised observations, it is188 desirable to limit the amount of supervision needed.189
Therefore, we augment the un-190 supervised ∆VAE with a super-191 vised method that makes use of192 transformation-labeled batches, i.e.193 batches {xm}Mm=1 such that xm =194 gm · x1 for m = 2, . . . ,M , where195 the transformations gm (and thus196 their group representations ρ(gm)) are197 known and are referred to as transfor-198 mation labels. The simplified version199 of the metric from Equation (4) can200 then be used for each batch as an ad-201 ditional loss term (with x0 = x1), as202 it is differentiable under the assump-203 tions described above (using the Eu-204 clidean norm).205
We make a small adjustment to Equation (4) for the purpose of our method, since the mean computed206 there does not typically lie on the latent manifold ZG. Thus, we use the projection Π from the ∆VAE207 to project the mean onto ZG. Writing the encodings as zm := h(xm), the additional loss term for a208 transformation-labeled batch {xm}Mm=1 then becomes209
LLSBD = 1
M M∑ m=1 ∥∥∥∥∥ρ(g−1m ) · zm −Π ( 1 M M∑ m=1 ρ(g−1m ) · zm )∥∥∥∥∥ 2 , (11)
where g1 = e, the group identity.210 Moreover, instead of feeding the encodings zm to the decoder, we use ρ(gm) · z, where z =211 Π (
1 M ∑M m=1 ρ(g −1 m ) · zm ) . This encourages the decoder to follow the required group structure.212 This only affects the reconstruction loss component of the ∆VAE.213
Figure 3 illustrates the supervised part of our method for a transformation-labeled batch {xm}Mm=1.214 The loss function is the regular ELBO (but with adjusted decoder input as described above) as used215 in ∆VAE plus an additional term γ · LLSBD, where γ is a weight hyperparameter to control the216 influence of the supervised loss component. By alternating unsupervised and supervised training217 (using the same encoder and decoder), we have a method that makes use of both unlabeled and218 transformation-labeled observations.219
6 Experimental Setup220
We evaluate the disentanglement of several models on three different image datasets (Square, Arrow,221 and Airplane) with a known group decomposition G = SO(2)× SO(2) describing the underlying222 transformations. For each subgroup a fixed number of |Gk| = 64 with k ∈ {1, 2} transformations is223 selected. The datasets exemplify different group actions of SO(2): periodic translations, in-plane224 rotations, out-of-plane rotations, and periodic hue-shifts.225
In real settings, not all variability in the data can be modelled by the actions of a group. Therefore,226 we also evaluate the same models on two datasets ModelNet40 (Wu et al., 2014) and COIL-100227 (Nene et al., 1996) that consist of images from various objects (i.e. non-symmetric variation) under228 known out-of-plane rotations (SO(2) symmetries). In many settings it is easy to obtain labels for229 such rotations, e.g. when the camera or object angle is controlled by an agent. See Figure 4 for230 examples of the datasets. For more details, see the Supplementary Material.231
For the Square, Arrow, and Airplane datasets we test LSBD-VAE with transformation-labeled batches232 of size M = 2. More specifically, for each experiment we randomly select L disjoint pairs of data233 points, and label the transformation between the data points in each pair. We vary the number of234 labeled pairs L from 0 (corresponding to a ∆VAE) to N/2 (in which case each data point is involved235 in exactly one labeled pair). We set the weight γ of the supervised loss component to γ = 100236 for all experiments. We choose M = 2 for our experiments since it is the most limited setting for237 LSBD-VAE. Higher values of M would provide stronger supervision, so successful results with238 M = 2 imply that good results can also be achieved for higher values of M (but not necessarily vice239 versa).240
For the COIL-100 and ModelNet40 datasets, we train LSBD-VAE on batches containing images of241 one particular object from all different angles (72 and 64 for COIL-100 and ModelNet40, respectively).242 Each batch is labelled with transformations (g1, e), . . . , (gM , e), where gm represent rotations, and243 the unit transformation e indicates that the object is unchanged. To represent the rotations we use244 a S1 latent space as in ∆VAE, whereas for the object identity we use a 5-dimensional Euclidean245 space with standard Gaussian prior as in regular VAEs. LSBD is measured as the disentanglement of246 rotations in the latent space. For these experiments we used γ = 1.247
We furthermore test a number of known disentanglement methods for comparison, including tra-248 ditional disentanglement methods as well as methods focusing on LSBD. In particular, we use249 disentanglement_lib (Locatello et al., 2019) to train a regular VAE (Kingma and Welling, 2014;250 Rezende et al., 2014), β-VAE (Higgins et al., 2017), CC-VAE (Burgess et al., 2018), FactorVAE251 (Kim and Mnih, 2018), and DIP-VAE-I/II (Kumar et al., 2018). Furthermore we evaluate the method252 from Quessard et al. (2020) that focuses on LSBD. We also tested ForwardVAE (Caselles-Dupré253 et al., 2019), but show only limited results since we were not able to reproduce any reasonable results254 for our datasets.255
We use encodings from all these methods to evaluate DLSBD, as well as common traditional disentan-256 glement metrics from disentanglement_lib: Beta (Higgins et al., 2017), Factor (Kim and Mnih,257 2018), SAP (Kumar et al., 2018), DCI Disentanglement (Eastwood and Williams, 2018), Mutual258 Information Gap (MIG) (Chen et al., 2018), and Modularity (MOD) (Ridgeway and Mozer, 2018).259
More information about the architecture, epochs and hyperparameters can be found in the Supplemen-260 tary Material. For the traditional disentanglement methods trained on Square, Arrow and Airplane261 datasets the latent spaces have 4 dimensions, since these are the minimum number of dimensions262 necessary to learn LSBD representations for an underlying SO(2) × SO(2) symmetry group, see263 (Higgins et al., 2018; Caselles-Dupré et al., 2019). For COIL-100 and ModelNet40 we use latent264 spaces with 7 dimensions for a fair comparison with the LSBD-VAE method.265
7 Results: Evaluating LSBD with DLSBD266
We now highlight four key observations from our experimental results. In particular, we differentiate267 between the methods (VAE, β-VAE, CC-VAE, FACTOR, DIP-I, DIP-II) and metrics (BETA,268 FACTOR, SAP, DCI, MIG, MOD) that approach disentanglement in the traditional sense, and269 methods (∆VAE, QUESSARD, LSBD-VAE) and metric (DLSBD) that focus specifically on LSBD.270 The full quantitative results can be found in the Supplementary Material.271
7.1 Standard Disentanglement Methods Don’t Learn LSBD Representations272
Figure 5 summarizes the DLSBD scores (lower is better) for all methods on all datasets. Bars show273 the mean scores over 10 runs for each method, the vertical lines represent standard deviations.274 LSBD-VAE/L indicates our method trained on L labelled pairs (LSBD-VAE/0 corresponds to the275 unsupervised ∆VAE), LSBD-VAE/full indicates our method trained on batches containing a single276 object in all known transformations (for datasets with non-symmetric variation). Note that LSBD-277 VAE obtained very good scores (nearly 0) on the Arrow and Pixel datasets, hence the missing278 bars.279

heading: LSB

text:
None of the traditional disentanglement methods achieve good DLSBD scores, even if they score well280 on other traditional disentanglement metrics. This implies that LSBD isn’t achieved by traditional281 methods. Moreover, from the full results in the Supplementary Material we see that the traditional282 methods on these datasets do not achieve good scores on all traditional metrics. In particular, SAP,283 DCI, and MIG scores are low. We believe this is a result of the cyclic nature of the symmetries284 underlying our datasets, further emphasizing the need for disentanglement methods that can capture285 such symmetries.286
The SAP and MIG scores measure to what extent generative factors are disentangled into a single287 latent dimension. However, since the factors in our dataset are inherently cyclic due to their symmetry288 structure, they cannot be properly represented in a single latent dimension, as shown by Perez Rey289 et al. (2020). Instead, at least two dimensions are needed to continuously represent each cyclic factor290 in our data. A similar conclusion was made by Caselles-Dupré et al. (2019) and Painter et al. (2020).291
DCI disentanglement measures whether a latent dimension captures at most one generative factor.292 This is accomplished by measuring the importance of each latent dimension in predicting the293 true generative factor using boosted trees. However, since the generative factors are cyclic, the294 performance of the boosted tree classifiers is far from optimal, thus providing more importance to295 several dimensions in predicting the generative factors and giving overall lower DCI scores.296
7.2 LSBD-VAE and other LSBD Methods Can Learn LSBD Representations with Limited297 Supervision on Transformations298
From Figure 5 we observe that methods focusing specifically on LSBD can score higher on DLSBD,299 showing that they are indeed more suitable to learn LSBD representations. In particular, LSBD-VAE300 got very good DLSBD scores for all datasets. Moreover, our experiments on the Arrow, Airplane, and301 Pixel datasets also show that only limited supervision suffices to obtain good DLSBD scores with low302 variability.303
We only partially managed to reproduce the results from Quessard et al. (2020) on our datasets. Their304 method scored fairly well on the Airplane, ModelNet40, and COIL-100 datasets, but did not do well305 on the Square and Arrow dataset in our experiments.306
Furthermore, we tested ForwardVAE by Caselles-Dupré et al. (2019), but we did not manage307 to produce any reasonable results on our datasets, trying both their original architecture and the308
architecture we used for our other experiments. Therefore, we do not include scores for this method.309 We did however manage to reproduce ForwardVAE’s results on the Flatland dataset, which was used310 in their paper. For those experiments, we computed a mean DLSBD score of 0.012 with standard311 deviation 0.001 over 10 runs, indicating that ForwardVAE indeed learns LSBD representations for312 Flatland.313
7.3 LSBD Representations Also Satisfy Previous Disentanglement Notions314
Our results also indicate that LSBD captures various desirable properties that are expressed by315 traditional disentanglement metrics. In Figure 6 we compare DLSBD scores with scores for previous316 disentanglement metrics, for all our experiments. Note that for DLSBD lower is better, whereas for317 all other metrics higher is better. As we noted before, good scores on traditional disentanglement318 metrics don’t necessarily imply good DLSBD scores. Conversely however, methods that score well319 on DLSBD also score well on many traditional disentanglement metrics, often even outperforming320 the traditional methods. In particular, from the full results (see Supplementary Material) we see321 that LSBD-VAE matches or outperforms the traditional methods on the BETA, FACTOR and MOD322 metrics, and achieves much better scores for the DCI metric where traditional methods scored poorly.323
The MIG and SAP scores are still low for methods focusing on LSBD. This is expected however, as324 explained earlier in Section 7.1. This was also observed by Painter et al. (2020) for different datasets.325
8 Conclusion326
We presented DLSBD, a metric to quantify Linear Symmetry-Based Disentanglement (LSBD) as327 defined by Higgins et al. (2018). We further used this metric formulation to motivate LSBD-VAE,328 a semi-supervised method to learn LSBD representations given some expert knowledge on the329 underlying group symmetries that are to be disentangled.330
We used DLSBD to evaluate various disentanglement methods, both traditional methods and recent331 methods that specifically focus on LSBD, and showed that LSBD-VAE can learn LSBD representa-332 tions where traditional methods fail to do so. We also comparedDLSBD to traditional disentanglement333 metrics, showing that LSBD captures many of the same desirable properties that are expressed by334 existing disentanglement methods. Conversely, we also showed that traditional disentanglement335 methods and metrics do not usually achieve or measure LSBD.336
Challenges that remain are expanding and testing LSBD-VAE and DLSBD on different group struc-337 tures, towards more practical applications, as well as focusing on the utility of LSBD representations338 for downstream tasks.339
Broader Impact The work is fairly theoretical, and practical methods derived from this work have340 no obvious negative societal impact. However, the ideas presented are relevant to representation341 learning and could be, in particular, used in computer vision and agent control applications.342
References343 Burgess, C. P., Higgins, I., Pal, A., Matthey, L., Watters, N., Desjardins, G., and Lerchner, A. (2018).344 Understanding disentangling in β-VAE. arXiv preprint arXiv:1804.03599.345
Caselles-Dupré, H., Ortiz, M. G., and Filliat, D. (2019). Symmetry-based disentangled representation346 learning requires interaction with environments. In Advances in Neural Information Processing347 Systems, pages 4606–4615.348
Chen, T. Q., Li, X., Grosse, R. B., and Duvenaud, D. K. (2018). Isolating sources of disentanglement349 in variational autoencoders. In Advances in Neural Information Processing Systems, pages 2615–350 2625.351
Cohen, T. and Welling, M. (2014). Learning the irreducible representations of commutative Lie352 groups. 31st International Conference on Machine Learning, pages 3757–3770.353
Cohen, T. S. and Welling, M. (2015). Transformation properties of learned visual representations. In354 3rd International Conference on Learning Representations.355
Eastwood, C. and Williams, C. K. (2018). A framework for the quantitative evaluation of disentangled356 representations. In International Conference on Learning Representations.357
Higgins, I., Amos, D., Pfau, D., Racaniere, S., Matthey, L., Rezende, D., and Lerchner, A. (2018).358 Towards a definition of disentangled representations. arXiv preprint arXiv:1812.02230.359
Higgins, I., Matthey, L., Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerchner,360 A. (2017). β-VAE: Learning basic visual concepts with a constrained variational framework. In361 International Conference on Learning Representations.362
Kim, H. and Mnih, A. (2018). Disentangling by factorising. In International Conference on Machine363 Learning, pages 2649–2658.364
Kingma, D. P. and Welling, M. (2014). Auto-Encoding Variational Bayes. In International Conference365 on Learning Representations.366
Kumar, A., Sattigeri, P., and Balakrishnan, A. (2018). Variational inference of disentangled latent367 concepts from unlabeled observations. In International Conference on Learning Representations.368
Locatello, F., Bauer, S., Lucic, M., Gelly, S., Schölkopf, B., and Bachem, O. (2019). Challenging369 common assumptions in the unsupervised learning of disentangled representations. In International370 Conference on Machine Learning.371
Nene, S. A., Nayar, S. K., Murase, H., et al. (1996). Columbia object image library (coil-20).372
Painter, M., Prugel-Bennett, A., and Hare, J. (2020). Linear disentangled representations and373 unsupervised action estimation. Advances in Neural Information Processing Systems, 33.374
Perez Rey, L. A., Menkovski, V., and Portegies, J. (2020). Diffusion variational autoencoders. In375 Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20,376 pages 2704–2710.377
Quessard, R., Barrett, T. D., and Clements, W. R. (2020). Learning Group Structure and Disentangled378 Representations of Dynamical Environments. Advances in Neural Information Processing Systems,379 33.380
Rezende, D. J., Mohamed, S., and Wierstra, D. (2014). Stochastic backpropagation and approximate381 inference in deep generative models. In Proceedings of the 31st International Conference on382 International Conference on Machine Learning-Volume 32.383
Ridgeway, K. and Mozer, M. C. (2018). Learning deep disentangled embeddings with the f-statistic384 loss. In Advances in Neural Information Processing Systems, pages 185–194.385
Sosnovik, I., Szmaja, M., and Smeulders, A. (2019). Scale-Equivariant Steerable Networks. Interna-386 tional Conference on Learning Representations, pages 1–14.387
Worrall, D. E., Garbin, S. J., Turmukhambetov, D., and Brostow, G. J. (2017). Harmonic networks:388 Deep translation and rotation equivariance. In Proceedings of the IEEE Conference on Computer389 Vision and Pattern Recognition, pages 5028–5037.390
Wu, Z., Song, S., Khosla, A., Yu, F., Zhang, L., Tang, X., and Xiao, J. (2014). 3D ShapeNets: A391 Deep Representation for Volumetric Shapes.392
Checklist393
1. For all authors...394 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s395 contributions and scope? [Yes]396 (b) Did you describe the limitations of your work? [Yes]397 (c) Did you discuss any potential negative societal impacts of your work? [Yes] See398 Section 8399 (d) Have you read the ethics review guidelines and ensured that your paper conforms to400 them? [Yes]401 2. If you are including theoretical results...402
(a) Did you state the full set of assumptions of all theoretical results? [Yes]403 (b) Did you include complete proofs of all theoretical results? [N/A] The theoretical404 contributions are new definitions and methodology, these have been motivated but do405 not require proofs.406
3. If you ran experiments...407 (a) Did you include the code, data, and instructions needed to reproduce the main experi-408 mental results (either in the supplemental material or as a URL)? [Yes] In Supplemen-409 tary Material410
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they411 were chosen)? [Yes] In paper or Supplementary Material412
(c) Did you report error bars (e.g., with respect to the random seed after running experi-413 ments multiple times)? [Yes] Each experiment was run 10 times, we report means and414 standard deviation, and show error bars where needed.415
(d) Did you include the total amount of compute and the type of resources used (e.g., type416 of GPUs, internal cluster, or cloud provider)? [Yes] In Supplementary Material we417 described the hardware. Tracked time of training for experiments with LSBD-VAE418 and Quessard approach, also reported in the Supplementary Material. The times for419 training the traditional methods in disentanglement_lib were not measured.420
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...421 (a) If your work uses existing assets, did you cite the creators? [Yes]422 (b) Did you mention the license of the assets? [Yes] In Supplementary Material423 (c) Did you include any new assets either in the supplemental material or as a URL? [Yes]424 Included code in the Supplementary Material425 (d) Did you discuss whether and how consent was obtained from people whose data you’re426 using/curating? [N/A] No consent was needed.427 (e) Did you discuss whether the data you are using/curating contains personally identifiable428 information or offensive content? [N/A] It clearly doesn’t.429 5. If you used crowdsourcing or conducted research with human subjects...430
(a) Did you include the full text of instructions given to participants and screenshots, if431 applicable? [N/A]432
(b) Did you describe any potential participant risks, with links to Institutional Review433 Board (IRB) approvals, if applicable? [N/A]434
(c) Did you include the estimated hourly wage paid to participants and the total amount435 spent on participant compensation? [N/A]436

title: Quantifying and Learning Linear Symmetry-Based Disentanglement