Geometry of architecture

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.

Equivariant convolutional networks

From neural networks to convolutions

Classically, a neural network is given by a sequence of maps

\[\mathbb{R}^{d_0}\xrightarrow{\sigma\circ W_1}\mathbb{R}^{d_1}\xrightarrow{\sigma\circ W_2}\cdots\xrightarrow{\sigma\circ W_L}\mathbb{R}^{d_L},\]

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)\).

Input (left) and filter response (right) translate together.

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:

\[C_c(\mathbb{Z}^2,\mathbb{R}^{d_0})\xrightarrow{\sigma\circ (*\psi_1)}C_c(\Gamma,\mathbb{R}^{d_1})\xrightarrow{\sigma\circ (*\psi_2)}\cdots\xrightarrow{\sigma\circ W_{L-1}}C_c(\Gamma,\mathbb{R}^{d_{L-1}})\xrightarrow{W_L\circ\mathrm{pool}}\mathbb{R}^{d_L},\]

Such networks respect known transformations of their inputs by construction.

Arbitrary Lie-group actions

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.

Perspective transformations of a handwritten digit.
Theorem (equivariance for arbitrary Lie-group actions)

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

\[C_c(X,\mathbb{R}^{d_0})\xrightarrow{\sigma\circ (*\psi_1)}C_b(G,\mathbb{R}^{d_1})\xrightarrow{\sigma\circ (*\psi_2)}\cdots\xrightarrow{\sigma\circ (*\psi_{L-1})}C_b(G,\mathbb{R}^{d_L})\xrightarrow{W_L\circ\mathrm{pool}}\mathbb{R}^{d_L}\]

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).

Open questions

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.

Papers and further reading

Public code for the CVPR paper

Further reading