Enabling Equivariance for Arbitrary Lie Groups
2022 · CVPR, 8183–8192 · oral presentation
Convolutional networks for arbitrary finite-dimensional Lie groups, including actions beyond the proper-action setting.
Many learning problems come with known transformations of the input: a change of viewpoint, for instance, can preserve the identity of an object. This can be modeled as the action of a group on inputs, which need not be particularly well-behaved. My work on this topic constructs a theory of equivariant networks for arbitrary Lie group actions.
Classically, a neural network is given by a sequence of maps
for an elementwise nonlinearity \(\sigma\) and matrices \(W_l\in\mathbb{R}^{d_{l-1}\times d_l}\). In convolutional neural networks, we instead regard an image as a compactly supported function in \(C_c(\mathbb{Z}^2,\mathbb{R}^k)\): the inputs are pixel coordinates, and the outputs are pixel values in \(k\) channels. The matrix maps are replaced with convolution operators \(*\psi_l\), for learned, compactly supported, matrix-valued filters \(\psi_l\).
The point of this replacement is that convolution is equivariant: translation of the image commutes with application of a layer. Translating an object therefore translates its features, rather than requiring the network to learn a separate representation at each position. Pointwise nonlinearities preserve this property.
More generally, if a group \(G\) acts on inputs, write \(L_u h(x)=h(u^{-1}\!\cdot x)\) for the induced action on functions. Equivariance of a layer \(\Phi\) means \(\Phi(L_u h)=L_u\Phi(h)\).
In a seminal paper, Cohen and Welling extended this idea to group convolutions, including discrete rotations and reflections as well as translations. The first layer lifts an image to a function on the group; subsequent layers convolve functions on the group, and a final pooling operation removes the group variable, giving an invariant prediction:
Such networks respect known transformations of their inputs by construction.
How far does this construction go? For instance, is it possible to construct networks equivariant to the action of any fixed Lie group? Answering this question in the affirmative, in collaboration with Sameera Ramasinghe and Simon Lucey, was my first contribution to machine learning.
Suppose a Lie group \(G\) acts on a manifold \(X\), and that our data are encoded as elements of \(C_c(X,\mathbb{R}^{d_0})\). We would want our first convolutional layer to lift such a function to a function on \(G\) in an equivariant fashion. There is a problem here: \(G\) need not act on \(X\) properly, so that \(X\) need not admit a \(G\)-invariant measure, without which the lifting operator of Cohen-Welling is not equivariant. A concrete example of this is when \(G\) is the group \(\mathrm{SL}(3,\mathbb{R})\) acting on \(\mathbb{R}^2\) by perspective transformations (right); this transformation is ubiquitous in natural images. Our main contribution is showing that equivariant networks are nonetheless possible in this general setting.
Given an arbitrary Lie group \(G\) acting on an arbitrary manifold \(X\), \(G\)-equivariant networks may be constructed. Specifically, given compactly supported continuous functions \(\psi_1\) on \(X\) and \(\psi_2,\dots,\psi_{L-1}\) on \(G\) and elementwise nonlinearity \(\sigma\), equivariant convolution operators \(*\psi_l\) may be defined for which the sequence
is \(G\)-invariant. Here \(C_c\) denotes compactly supported continuous functions while \(C_b\) denotes bounded continuous functions.
If the group \(G\) acts nonproperly on \(X\), therefore, equivariant convolutional networks are still possible, but their features are bounded continuous functions on \(G\) rather than compactly-supported continuous functions.
The formulas defining the convolutions in this framework are given by integrals against Haar measure on \(G\). To implement them, we parametrise filters by small neural networks and approximate the integrals by Monte Carlo sampling from the Lie algebra of \(G\). Using this implementation we were able to construct networks that performed well on small-scale invariant image classification tasks (affine and perspective-perturbed MNIST).
Unfortunately, due to the fact the intermediate feature spaces for our theory are merely bounded continuous functions rather than compactly supported, we were unable to come up with an implementation that is simultaneously faithful to the theory and also computationally feasible: for a network with \(L\) convolutional layers and \(N\) Monte-Carlo samples to approximate each convolution, the memory footprint of our implementation scales as \(O(N^L)\). I do not believe it is possible to do better than this in general without sacrificing some equivariance. I am interested in whether this sacrifice can be made in a principled way to enable scalable implementation of such equivariant networks which nonethless are "equivariant enough".
More general structures of symmetry, including groupoids and pseudogroups, also offer directions for investigation.
2022 · CVPR, 8183–8192 · oral presentation
Convolutional networks for arbitrary finite-dimensional Lie groups, including actions beyond the proper-action setting.
Public code for the CVPR paper