Year: 2019

Abstract:
Equivariant neural networks are special types of neural networks that preserve some symmetries on the data set. In this paper, we provide a method to modify a neural network to an equivariant one, which we call equivarification.

heading: 1 INTRODUCTION
text: One key issue in deep neural network training is the difficulty of tuning parameters, especially when the network size grows larger and larger Han et al. (2015). In order to reduce the complexity of the network, many techniques have been proposed by analyzing the structural characteristics of data, for example, sparsity Wen et al. (2016), invariance in movement Goodfellow et al. (2009).
One of the most important structural characteristics of data is symmetry. By utilizing the translation symmetry of an object in the photo, convolutional neural network (CNN)(Krizhevsky et al. (2012)) uses shared filters to reduce the number of parameters compared with fully connected networks. However, to handle the case of rotation and reflection, people usually use the data augmentation approach to generate additional input data that has a bunch of training images with different rotation angles of the original images.
In contrast to data augmentation approach, another idea is to design more sophisticated neural networks, such that the input data with certain symmetries can be trained together and applied to reduce the training complexity. Recent attempts have been made in the equivariant CNN Cohen & Welling (2016a); Cohen et al. (2018); Weiler et al. (2018). These existing works target at special cases and cannot be easily generalized to arbitrary networks and arbitrary symmetries.
In this paper, we take advantage of the symmetry of the data set and provide a general method to modify an arbitrary neural network so that it preserves the symmetry. The process is called equivarification. A key feature is that our equivarification method can be applied without detailed knowledge of a layer in a neural network, and hence, can be generalized to any feedforward neural networks. Another feature is that the number of parameters in the new neural network that we need to train is the same as the original one, if we equivarify the original network globally (see the second paragraph in Section 4 for details). In addition, we can also output how each data instance is changed from the canonical form (for example, in an image classification problem, additionally we can also output how many degrees an image is rotated from original upside-up image) using the same network.
We rigorously prove that our equivarification method produces truely equivariant neural networks. Practically, we equivarify a CNN as an illustration. We conduct experiments using the MNIST data set where the resulting equivariant neural network predicts the number and also the angle. If we forget the angle and keep only the number, we get an invariant neural network.

heading: 1.1 MOTIVATION
text: By the symmetry of the data set, we mean a group action (see Definition 2.2) on the data set. Let us consider a simple cat image classification example. Then the data set can be the set of all images of a fixed size. Rotation symmetry means that we can rotate an image and the resulting image still lies in the data set. In other words, the group of rotations acts on the data set.
One can build a cat classifier that assigns a number between 0 and 1 to each image indicating the probability that it is an image of a cat. If one image is a rotation (say by 90 degree counterclockwise)
of another one, then it makes sense to require a classifier to assign the same probability to these two images. A classifier that satisfies this property is said to be invariant under 90-degree rotation, which is a special case of being equivariant under 90-degree rotation. To give an example of an (noninvariant) equivariant neural network, we furthermore require our classifier not only produces the probability of being a cat image, but also outputs an angle, say in {0, 90, 180, 270} (more precisely, the probability of each angle). Suppose that the equivariant classifier predicts that an image is rotated by 90 degrees, then it should predict a 270-degree rotation for the same image but rotated by 180 degrees.
Not only does it make sense to require the cat classifier to be equivariant, but also it is more “economical” to be equivariant if implemented correctly. Roughly speaking, a regular classifier “treats” an image and its rotated ones as separated things, but ideally an equivariant neural network “sees” their connections and “treats” them together. From another point of view, given a regular neural network, if we apply the data augmentation method carefully, since the training data is symmetric, it is possible that after training, the network is (approximately) equivariant (depending on the initialization). The fact that it is equivariant implies that there is now symmetry among the parameters. For example, some parameters are the same as other parameters, so there is redundancy. While in our equivariant neural network, the equivariance of our neural network is built into the structure of the neural network by sharing parameters, and in particular, it is independent of the loss function, initialization, and the data set. For instance, for the training data, it does not make any difference in results whether we prepare it by randomly rotating and recording the angles, or not rotating and labeling everything as degree 0.
In our approach, to make a neural network equivariant, at each layer other than the input layer we add a bunch of neurons (multiplying by the order of the group), but we don’t introduce new parameters. Instead the added neurons share parameters with the original ones.

heading: 1.2 RELATED WORK
text: Invariance in neural networks has attracted attention for decades, aiming at designing neural networks that capture the invariant features of data, for example, face detection system at any degree of rotation in the image plane Rowley et al. (1998), invariance for pattern recognition Barnard & Casasent (1991), translation, rotation, and scale invariance Perantonis & Lisboa (1992).
Recently, several works have started to look into equivariant CNN, by studying the exact mapping functions of each layer Cohen & Welling (2016a;b); Cohen et al. (2018); Marcos et al. (2017); Lenssen et al. (2018); Cohen et al. (2019), and some symmetries are studied such as translation symmetry, rotation symmetry. These methods have been used in different application domains, such as in remote sensing Marcos et al. (2018), digital pathology Veeling et al. (2018), galaxy morphology prediction Dieleman et al. (2015).
There are also works that aiming to construct an equivariant neural network without having to specify the symmetry Sabour et al. (2017).
As far as we know, our construction provides the first truly equivariant neural network (See Section 5.1).

heading: 2 PRELIMINARIES
text: In this section, we talk about some basics in group theory, like group actions, equivariance, etc. For those who would like to get a more close look at the group theory and various mathematical tools behind it, please refer to any abstract algebra books, for example, Lang (2002).
Here, we first give a couple of definitions about groups in order to help readers quickly grasp the concepts.
Definition 2.1. A group (G, ·) consists of a set G together with a binary operation “·” (which we usually call multiplication without causing confusing with the traditional sense of multiplication for real numbers) that needs to satisfy the four following axioms.
1) Closure: for all a, b ∈ G, the multiplication a · b ∈ G.
2) Associativity: for all a, b, c ∈ G, the multiplication satisfies (a · b) · c = a · (b · c).
3) Identity element: there exists a unique identity element e ∈ G, such that, for every element a ∈ G, we have e · a = a · e = a.
4) Inverse element: for each element a ∈ G, there exists an element b ∈ G, denoted a−1, such that a · b = b · a = e, where e is the identity element.
Note that in general, commutativity does not apply here, namely, for a, b ∈ G, a · b = b · a does not always hold true.
For example, all integers with the operation addition (Z,+). One can easily check that the four axioms are satisfied and 0 is the identity element.
As another example, a group consists of a set {0, 1} together with the operation + (mod 2) where 0+1 = 1+0 = 1 and 1+1 = 0+0 = 0. The identity element is 0. When applying this to the image processing tasks, this can be interpreted as follows. 1 represents the action of rotating an image by 180o and 0 represents the action of not rotating an image. Then 0 + 1 represents the combination of operations that we first rotate an image by 180o and then keep it as it is, so that the final effect is to rotate an image by 180o; while 1+1 represents that we first rotate an image by 180o and then rotate again by 180o, which is equivalent to that we do not rotate the original image.
Similarly, we can define the element 1 as the operation of flipping an image vertically or horizontally, which we can give similar explanations for the group.
Therefore, instead of using translations, rotations, flippings, etc., we can use abstract groups to represent operations on images, and hence, we are able to design corresponding equivariant neural networks disregarding the operations of images (symmetries of data) and just following the group representation.
In the following, we give a definition about group actions. Let X be a set, and G be a group.
Definition 2.2. We define a G-action on X to be a map
T : G×X → X
(on the left) such that for any x ∈ X
• T (e, x) = x, where e ∈ G is the identity element,
• for any g1, g2 ∈ G, we have
T (g1, T (g2, x)) = T (g1g2, x).
Frequently, when there is no confusion, instead of saying that T is a G-action on X or equivalently that G acts on X via T , we simply say that G acts on X ; and T is also understood from the notation, i.e., instead of T (g, x) we simply write gx, and the above formula becomes g1(g2x) = (g1g2)x.
We say G acts trivially on X if gx = x for all g ∈ G and x ∈ X .
Let X,Y be two sets, and G be a group that acts on both X and Y .
Definition 2.3. A map F : X → Y is said to be G-equivariant, if F (gx) = gF (x) for all x ∈ X and g ∈ G. Moreover, if G acts trivially on Y then we say F is G-invariant.
Example 2.4. Let X be the space of all images of 28 × 28 pixels, which contains the MNIST data set. Let G be the cyclic group of order 4. Pick a generator g of G, and we define the action of g on X by setting gx to be the image obtained from rotating x counterclockwise by 90 degrees. Let Y be the set {0, 1, 2, ..., 9}× {0, 90, 180, 270}. For any y = (num, θ) ∈ Y we define
gy := (num, (θ + 90)mod360).
An equivariant neural network that classifies the number and rotation angle can be viewed as a map F from X to Y . Equivariance means if F (x) = (num, θ) then F (gx) = (num, (θ + 90)mod360), for all x ∈ X .
Thus, we can see that we can model each layer in the neural network as a group G that acts on a set X , where we can interpret the set X as input to this layer and the group action as the function mapping or operation of this layer. By abstracting the behaviors on the original input data using groups
(for example, using a same group to represent either rotation by 180o and flipping, or even more abstract operations during intermediate layers), we are able to apply group actions on different sets X1, X2, X3, . . . (where each one represents input to different layers) and design similar equivariant network structures based on an original one.

heading: 3 EQUIVARIFICATION
text: In this section, we talk about the detailed method of performing equivarification and its theoretical foundation. This is the key part of the paper to understand our proposed equivarification method. Those who would like to avoid mathematical proofs can directly go to the examples we provide to get intuitive ideas of how we construct the equivariant neural networks.
In this section we fix X and Z to be two sets, and G to be a group that acts on X .
Definition 3.1. Define the G-product of Z to be
Z×G = {s : G → Z},
the set of all maps from G to Z .
We define a G-action on Z×G by
G× Z×G → Z×G
(g, s) 7→ gs,
where gs as a map from G to Z is defined as
(gs)(g′) := s(g−1g′), (3.1)
for any g′ ∈ G.
We have the projection map p : Z×G → Z defined by
p(s) = s(e), (3.2)
for any s ∈ Z×G where e ∈ G is the identity element. Then
Lemma 3.2. For any map F : X → Z , there exists a unique G-equivariant map F̂ : X → Z×G
such that p(F̂ (x)) = F (x) for all x ∈ X .
Proof. For any x ∈ X , we define F̂ (x) as a map from G to Z by
(F̂ (x))(g) = F (g−1x),
for any g ∈ G. To see that F̂ is G-equivariant, we need to check for any x ∈ X and g ∈ G, F̂ (gx) = g(F̂ (x)). For any h ∈ G, (F̂ (gx))(h) = F (h−1gx) by the definition of F̂ , while (g(F̂ (x)))(h) = (F̂ (x))(g−1h) = F (h−1gx). We leave the proof of uniqueness to the readers.
Remark 3.3. In the Definition 3.1 and Lemma 3.2, G is an arbitrary group and Z is an arbitrary set. It is easy to see that we can adjust them, if we consider other categories. For example, when G is a compact Lie group and Z is a differentiable manifold, we can re-define Z×G to be the space of differentiable maps from G to Z; when G is a non-compact Lie group and Z is a differentiable manifold, we can consider the space of compact supported smooth maps. When we implemented the neural network for infinite G, we have to approximate it by a finite subset of G. Then in this case, we need to work in the realm of approximately equivariant. For this implementation reason, we restrict our group G to be a finite group for the rest of the paper.
This lemma can be summarized as the commutative diagram in Figure 1. It motivates the following general definition.
Definition 3.4. We say a tuple (Ẑ, T, p) a G-equivarification of Z if
• Ẑ is a set with a G-action T ;
• p is a map from Ẑ to Z;
• For any set X with a G-action, and map F : X → Z , there exists a G-equivariant map
F̂ : X → Ẑ such that p ◦ F̂ = F .
Here ◦ denotes the composition of maps. As usual, T will be omitted from notation.
In Section 4 we will see applications of G-equivarification to neural networks. From Lemma 3.2 we know that the triple of the G-product Z×G, the G-action defined in the Formula 3.1, and the projection p defined in Formula 3.2 is a G-equivarification. There are other G-equivarifications. See Appendix for more discussion.
Example 3.5. Let G be the cyclic group of order 4. More concretely, we order elements of G by (e, g, g2, g3). The set Z×G can be identified with Z×4 = Z × Z × Z × Z via the map
s 7→ (s(e), s(g), s(g2), s(g3)). (3.3)
Then G acts on Z×4 by g(z0, z1, z2, z3) = (z3, z0, z1, z2), and the projection map p : Z ×4 → Z is given by (z0, z1, z2, z3) 7→ z0. Let F : X → Z be an arbitrary map, then after the identification F̂ becomes a map from X to Z×4 and
F̂ (x) = (F (x), F (g−1x), F (g−2x), F (g−3x)).
One can check that F̂ is G-equivariant. The map p is given by
p(z0, z1, z2, z3) = z0.
It is easy to see that p ◦ F̂ = F .

heading: 4 APPLICATION TO NEURAL NETWORKS
text: In this section, we show through an example how our proposed equivarification method works.
Let {Li : Xi → Xi+1} n i=0 be an n-layer neural network (which can be CNN, multi-layer perceptrons, etc.). In particular, X0 is the input data set, and Xn+1 is the output data set. Let G be a finite group that acts on X0. Let L be the composition of all layers
L = Ln ◦ Ln−1 ◦ · · · ◦ L0 : X0 → Xn+1.
Then we can equivarify L and get maps L̂ : X0 → X̂n and p : X̂n+1 → Xn+1. Then L̂ is an equivariant neural network.
Alternatively, one can construct an equivariant neural network layer by layer. More precisely, the equivariant neural network is given by {L̂i ◦ pi : X̂i → X̂i+1} n i=0, where L̂i ◦ pi is the equivarification of Li ◦ pi for i ∈ {0, 1, ..., n}, X̂0 = X0 and p0 = id is the identity map (See Figure 2). More precisely, by the commutativity of Figure 2 we know that
pn+1 ◦ L̂n ◦ pn ◦ ̂Ln−1 ◦ pn−1 ◦ · · · ◦ L̂0 ◦ p0 = L = p ◦ L̂.
Then both L̂n ◦ pn ◦ ̂Ln−1 ◦ pn−1 ◦ · · · ◦ L̂0 ◦ p0 and L̂ are equivarifications of L. Suppose that for both equivarifications we have chosen X̂n+1 to be Xn+1 ×G. Then by the statement in Theorem 3.2, we have L̂n ◦ pn ◦ ̂Ln−1 ◦ pn−1 ◦ · · · ◦ L̂0 ◦ p0 = L̂.
Sometimes, other than equivarifying the map Li ◦ pi : X̂i → Xi+1, it makes sense to construct some other map L′i from X̂i to some other set X ′ i+1, and then we can equivarify L ′ i. This makes the equivariant neural network more interesting (see the example below).
Example 4.1. Let the 0-th layer L0 : X0 → X1 of a neural network that is defined on the MNIST data set be a convolutional layer, and X1 = R
ℓ1 , where ℓ1 = 28 × 28 × c1, and c1 is the number of channels (strides = (1, 1), padding = ‘same’). Let G = {e, g, g2, g3} be the cyclic group of order 4 such that g acts on X0 as the 90-degree counterclockwise rotation. Then we construct L̂0 : X0 → R 4ℓ1 by
x0 7→ (L0(x0), L0(g −1x0), L0(g −2x0), L0(g −3x0)).
For the next layer, instead of equivarifying L1 ◦ p1 : R 4ℓ1 → Rℓ2 , we can construct another convolutional layer directly from R4ℓ1 by concatenating the four copies of Rℓ1 along the channel axis to obtain R28×28×4c1 , and build a standard convolution layer on it. This new construction of course changes the number of variables compared to that of the original network.
From the above analysis and Lemma 3.2, it is not hard to derive the following summary.
Main result Let X = {Li : Xi → Xi+1}0≤i≤n+1 be an original neural network that can process input data {xj0}j ⊆ X0 and labelling data {x j n+1}j ⊆ Xn+1. Let G be a finite group that acts on X0. The proposed G-equivarification method is able to generate a G-equivariant neural network X̂ = {L̂i : X̂i → X̂i+1}0≤i≤n+1 that can process input data {x j 0}j ⊆ X0 = X̂0 and enhanced labeling data {x̂in+1}j ⊆ X̂n+1. Furthermore, the number of parameters of X̂ is the same as that of X.

heading: 5 EXPERIMENTS
text: In this section, we show our experiments on the MNIST dataset, which achieve promising performance1
Our designed equivariant neural network using the proposed equivarification method is shown in Figure 3. Note that equivarification process does not increase the number of variables. In our case, in order to illustrate flexibility we choose not to simply equivarify the original neural network, so the layer conv2 and conv3 have four times the number of variables compared to the corresponding original layers.
Next, we discuss the labeling of the input data. Since the neural network is G-equivariant, it makes sense to encode the labels G-equivariantly. Suppose (x0, xn+1) ∈ X0 ×Xn+1 is one labelled data point. Then in the ideal case, one hopes to achieve L(x0) = xn+1. Assuming this, to give a new label for the data point x0 for our equivariant neural network we need to define x̂n+1 = L̂(x0). For this, it is sufficient to define L̂(x0)(g) for all g ∈ G. By equivariance, L̂(x0)(g) = L(g −1x0). If g = e then L̂(x0)(g) = L(x0) = xn+1. If g 6= e, it is very likely that the data g −1x0 originally does not have a label, so we do not know ideally what L(g−1x0) should be. In the naive data augmentation approach, L(g−1x0) is labeled the same as L(x0) hoping to get L as close to an invariant map as possible. In our case, we do not have such restriction, since we do not need L to be invariant. In
1The code in tensorflow is uploaded as the supplementary material. In the code, we also include a version that allows 90 degree rotation and horizontal and vertical flips, just to make the group non-commutative.
practice, Xn+1 is a vector space, and we choose to label L(g −1x0) by the origin of Xn+1. In our MNIST example, this choice is the same as the following.
For m ∈ {0, 1, 2, ..., 9} denote
em = (0, · · · , 0, 1, 0, · · · , 0) ∈ R 10.
↑
m-th spot
For an unrotated image x0 ∈ X0 that represents the number m, we assign the label em⊕0⊕0⊕0 ∈ R40. Then based on the equivariance, we assign
gx0 7→ 0⊕ em ⊕ 0 ⊕ 0,
g2x0 7→ 0⊕ 0 ⊕ em ⊕ 0,
g3x0 7→ 0⊕ 0 ⊕ 0 ⊕ em.
For each testing image in the MNIST data set, we randomly rotate it by an angle of degree in {0, 90, 180, 270}, and we prepare the label as above. For the training images, we can do the same, but just for convenience, we actually do not rotate them, since it won’t affect the training result at all.

heading: 5.1 EQUIVARIANCE VERIFICATION
text: To spot check the equivariance after implementation, we print out probability vectors in R40 of an image of the number 7 and its rotations. We see that the probability vectors are identical after a shift by 10 slots. See Figure 4.

heading: 5.2 ACCURACY
text: Here we count the prediction as correct if both the number and the angle are predicted correctly. The accuracy of our neural network on the test data is 96.8%. This is promising when considering the fact that some numbers are quite hard to determine its angles, such as 0, 1, and 8.

heading: 6 CONCLUSION
text: In this paper, we proposed an equivarification method to design equivariant neural networks that are able to efficiently process input data with symmetries. Our proposed method can be generalized to arbitrary networks or functions by leveraging group action, which enables our design to be uniform across layers of feedforward neural networks, such as multi-layer perceptrons, CNNs, without being aware of the knowledge of detailed functions of a layer in a neural network. As an illustration example, we show how to equivarifying a CNN for image classification. Results show that our proposed method performs as expected, yet with significantly reduction in the design and training complexity.

heading: A APPENDIX - MORE ABOUT EQUIVARIFICATION
text: In Section 3 we define (Z×G, p) as an example of G-equivarification. In this section, we show that it is “minimal” in the sense of its universal property.
Lemma A.1 (universal property). For any G-equivarification (Ẑ ′, p′) of Z , there exists a Gequivariant map π : Ẑ ′ → Z×G such that p′ = p◦π. Moreover, for any set X and map F : X → Z , the lifts F̂ : X → Z×G and F̂ ′ : Z → Ẑ ′ of F satisfy π ◦ F̂ ′ = F̂ . (See Figure 5.)
Proof. We define the map π : Ẑ ′ → Z×G by [π(ẑ′)](g) = p′(g−1ẑ′), where ẑ′ ∈ Ẑ ′ and g ∈ G. To show p′ = p ◦ π, for any ẑ′ ∈ Ẑ , we check p ◦ π(ẑ′) = p[π(ẑ′)] = [π(ẑ′)](e) = p′(ẑ′). To show π is G-equivariant, for any ẑ′ ∈ Ẑ, and h ∈ G, we compare π(hẑ′) and hπ(ẑ′): for any g ∈ G, [π(hẑ′)](g) = p′(g−1hẑ′) and [hπ(ẑ′)](g) = [π(ẑ′)](h−1g) = p′(g−1hẑ′). Lastly, we show π ◦ F̂ ′ = F̂ . Note that π ◦ F̂ ′ is a G-equivariant map from X to Z×G, and
p ◦ (π ◦ F̂ ′) = p′ ◦ F̂ ′ = F,
so by the uniqueness of Lemma 3.2, we get π ◦ F̂ ′ = F̂ .
Now we discuss about finding a “smaller” equivarification in another direction, shrinking the group by bring in the information about X . Let N = {g ∈ G | gx = x for all x ∈ G}, the set of elements in G that acts trivially on X . It is easy to check that N is a normal subgroup of G. We say G acts on X effectively if N = {e}. In the case when G does not act effectively, it makes sense to consider the G/N -product of Z , where G/N is the quotient group. More precisely, consider Z×G/N = {s : G/N → Z}, which is smaller in size than Z×G. For any map F : X → Z ,
we can get a G/N -equivariant lift F̂ of F following the same construction as Lemma 3.2 (with G replaced by G/N ). Since G maps to the quotient G/N , we have that G acts on Z×G/N and F̂ is also G-equivariant.

Review summaries:
In this work, the authors employ concepts from group theory to turn an arbitrary feed forward neural network into an equivariant one, i.e. a network whose output transforms in a way that is consistent with the transformation of the input. To this end, the authors first introduce the basic concepts of group theory required to follow their work and provide a comprehensive definition of equivariance. They then explain how to equivarify (w.r.t. a finite group G) a given neural network, and present experimental results on rotated MNIST digits to support their approach.

The paper adds an interesting new perspective to equivariant neural nets. However, the actual construction looks equivalent to steerable neural nets to me (see the papers by Cohen and Welling). The generalization of steerable nets has been published under the name "gauge equivariant neural nets", it would be very interesting to chart out the exact connections between these concepts.