Title: EQUIVARIANT NEURAL NETWORKS AND EQUIVARIFI-CATION

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.

1. INTRODUCTION:

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.

1.1. MOTIVATION:

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.

1.2. RELATED WORK:

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

2. PRELIMINARIES:

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 180 o 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 180 o and then keep it as it is, so that the final effect is to rotate an image by 180 o ; while 1 + 1 represents that we first rotate an image by 180 o and then rotate again by 180 o , 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 g 1 , g 2 ∈ G, we have

T (g 1 , T (g 2 , x)) = T (g 1 g 2 , 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 g 1 (g 2 x) = (g 1 g 2 )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)mod 360 ).

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)mod 360 ), 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 180 o and flipping, or even more abstract operations during intermediate layers), we are able to apply group actions on different sets X 1 , X 2 , X 3 , . . . (where each one represents input to different layers) and design similar equivariant network structures based on an original one.

3. EQUIVARIFICATION:

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) → gs,

where gs as a map from G to Z is defined as

EQUATION

for any g ′ ∈ G.

We have the projection map p : Z ×G → Z defined by

EQUATION

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 -1 x),

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 -1 gx) by the definition of F , while (g( F (x)))(h) = ( F (x))(g -1 h) = F (h -1 gx).

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 • p is a map from Z to Z;

• Z is a set with a G-action T ; Z ×G X Z F p ∃! F

• 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, g 2 , g 3 ). The set Z ×G can be identified with

Z ×4 = Z × Z × Z × Z via the map s → (s(e), s(g), s(g 2 ), s(g 3 )). (3.3)

Then G acts on Z ×4 by g(z 0 , z 1 , z 2 , z 3 ) = (z 3 , z 0 , z 1 , z 2 ), and the projection map p : Z ×4 → Z is given by (z 0 , z 1 , z 2 , z 3 ) → z 0 . 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 -1 x), F (g -2 x), F (g -3 x)).

One can check that F is G-equivariant. The map p is given by

p(z 0 , z 1 , z 2 , z 3 ) = z 0 .

It is easy to see that p • F = F .

4. APPLICATION TO NEURAL NETWORKS:

In this section, we show through an example how our proposed equivarification method works.

Let {L i : X i → X i+1 } n i=0 be an n-layer neural network (which can be CNN, multi-layer perceptrons, etc.). In particular, X 0 is the input data set, and X n+1 is the output data set. Let G be a finite group that acts on X 0 . Let L be the composition of all layers

L = L n • L n-1 • • • • • L 0 : X 0 → X n+1 .

Then we can equivarify L and get maps L : X 0 → X n and p : X n+1 → X n+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 • p i : X i → X i+1 } n i=0

, where L i • p i is the equivarification of L i • p i for i ∈ {0, 1, ..., n}, X 0 = X 0 and p 0 = id is the identity map (See Figure 2 ). More precisely, by the commutativity of Figure 2 we know that

p n+1 • L n • p n • L n-1 • p n-1 • • • • • L 0 • p 0 = L = p • L. Then both L n • p n • L n-1 • p n-1 • • • • • L 0 • p 0

and L are equivarifications of L. Suppose that for both equivarifications we have chosen X n+1 to be X n+1 ×G . Then by the statement in Theorem 3.2, we have Sometimes, other than equivarifying the map L i • p i : X i → X i+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 L 0 : X 0 → X 1 of a neural network that is defined on the MNIST data set be a convolutional layer, and X 1 = R ℓ1 , where ℓ 1 = 28 × 28 × c 1 , and c 1 is the number of channels (strides = (1, 1), padding = 'same'). Let G = {e, g, g 2 , g 3 } be the cyclic group of order 4 such that g acts on X 0 as the 90-degree counterclockwise rotation. Then we construct L 0 : X 0 → R 4ℓ1 by

L n • p n • L n-1 • p n-1 • • • • • L 0 • p 0 = L. X i+1 X i X i+1 L i • p i p i+1 L i • p i

x 0 → (L 0 (x 0 ), L 0 (g -1 x 0 ), L 0 (g -2 x 0 ), L 0 (g -3 x 0 )).

For the next layer, instead of equivarifying L 1 • p 1 : R 4ℓ1 → R ℓ2 , we can construct another convolutional layer directly from R 4ℓ1 by concatenating the four copies of R ℓ1 along the channel axis to obtain R 28×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 = {L i : X i → X i+1 } 0≤i≤n+1 be an original neural network that can process input data {x j 0 } j ⊆ X 0 and labelling data {x j n+1 } j ⊆ X n+1 . Let G be a finite group that acts on X 0 . 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 ⊆ X 0 = X 0 and enhanced labeling data { x i n+1 } j ⊆ X n+1 . Furthermore, the number of parameters of X is the same as that of X.

5. EXPERIMENTS:

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 (x 0 , x n+1 ) ∈ X 0 × X n+1 is one labelled data point. Then in the ideal case, one hopes to achieve L(x 0 ) = x n+1 . Assuming this, to give a new label for the data point x 0 for our equivariant neural network we need to define x n+1 = L(x 0 ). For this, it is sufficient to define L(x 0 )(g) for all g ∈ G. By equivariance, L(x 0 )(g) = L(g -1 x 0 ). If g = e then L(x 0 )(g) = L(x 0 ) = x n+1 . If g = e, it is very likely that the data g -1 x 0 originally does not have a label, so we do not know ideally what L(g -1 x 0 ) should be. In the naive data augmentation approach, L(g -1 x 0 ) is labeled the same as L(x 0 ) 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

X0 X1 × X1 × X1 × X1 X1 conv1 conv1•g -1 conv1•g -2 conv1•g -3 X2 × X2 × X2 × X2 X2 conv2 conv2•g -1 conv2•g -2 conv2•g -3 X3 conv3 X4 pool X5 × X5 × X5 × X5 X5 = R 40 dense dense • pool • conv3 •g -1 dense • pool • conv3 •g -2 dense • pool • conv3 •g -3

Figure 3: In this figure, conv1 is a standard convolution layer with input = X 0 and output = X 1 . After equivarification of conv1, we get four copies of X 1 . Then we stack the four copies along the channel direction, and take this whole thing as an input of a standard convolution layer conv2. We equivarify conv2, stack the four copies of X 2 , and feed it to another convolution layer conv3. Now instead of equivarifying conv3, we add layer pool and layer dense (logistic layer), and then we equivarify their composition dense • pool • conv3 •g -1 and get X 5 = R 40 . To get the predicted classes, we can take an argmax afterwards. practice, X n+1 is a vector space, and we choose to label L(g -1 x 0 ) by the origin of X n+1 . In our MNIST example, this choice is the same as the following.

For m ∈ {0, 1, 2, ..., 9} denote

e m = (0, • • • , 0, 1, 0, • • • , 0) ∈ R 10 . ↑ m-th spot

For an unrotated image x 0 ∈ X 0 that represents the number m, we assign the label e m ⊕ 0 ⊕ 0 ⊕ 0 ∈ R 40 . Then based on the equivariance, we assign

gx 0 → 0 ⊕ e m ⊕ 0 ⊕ 0, g 2 x 0 → 0 ⊕ 0 ⊕ e m ⊕ 0, g 3 x 0 → 0 ⊕ 0 ⊕ 0 ⊕ e m .

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.

5.1. EQUIVARIANCE VERIFICATION:

To spot check the equivariance after implementation, we print out probability vectors in R 40 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 .

5.2. ACCURACY:

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.

6. CONCLUSION:

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.

A APPENDIX -MORE ABOUT EQUIVARIFICATION:

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 -1 z ′ ), 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 π(h z ′ ) and hπ( z ′ ): for any g ∈ G, [π(h z ′ )](g) = p ′ (g -1 h z ′ ) and [hπ( z ′ )](g) = [π( z ′ )](h -1 g) = p ′ (g -1 h z ′ ). 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. 

:

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

Figures and Tables:

Figure 1: For any X and F , there exists a unique lift F such that the diagram commutes.

Figure 2: Equivarification layer by layer.

Figure 4: On the left, we have the rotated images; on the right, we have the predicted numbers, angles, and the probability vectors in R 40 , each component of which corresponds to the probability of a (number, angle) combination. The equivariance in this case means that the four vectors are related by shifts.

Figure 5: Factors through.

Peer review (iclr2020):
In this paper, the authors propose a method for making a neural network equivariant. Their method also can be applied to make each layer equivariant too. Strengths: -- The paper is very well written and easy to follow with clear notation. -- The derivations seem to be correct. Weaknesses: -- The experiment is nice but very limited and does not demonstrate the benefits of having an equivariant network. For example, the authors do not report the accuracy of recovering the original (0) rotation. -- The novelty of the work is questionable. While the development is different, the final example for equivarification of a neural network is very similar to the existing works by Cohen and Welling. -- There are other works on equivarification that are missed by this paper. For example, consider the following paper: Lenssen, J. E., Fey, M., & Libuschewski, P. (2018). Group equivariant capsule networks. In NeurIPS. -- The layer-wise equivariant method does have extra computational overheads. -- The fact that we have to specify the groups that we want to make the network equivariant with respect to is a limitation. The promise of capsule networks, in contrast, is to *ideally* learn the pose (variation) vectors in a data-driven way. Sabour, S., Frosst, N., & Hinton, G. E. (2017). Dynamic routing between capsules. In NeurIPS. -- The following statements need more explanation: * *However, these may require extra training overhead as the augmented data increase.*