Equivariance Through Parameter-Sharing

We propose to study equivariance in deep neural networks through parameter symmetries. In particular, given a group G that acts discretely on the input and output of a standard neural network layer φW ∶ R → R , we show that φW is equivariant with respect to G-action iff G explains the symmetries of the network parameters W. Inspired by this observation, we then propose two parameter-sharing schemes to induce the desirable symmetry on W. Our procedure for tying the parameters achieves G-equivariance and, under some conditions on the action of G, it guarantees sensitivity to all other permutation groups outside G. Given enough training data, a multi-layer perceptron would eventually learn the domain invariances in a classification task. Nevertheless, success of convolutional and recurrent networks suggests that encoding the domain symmetries through shared parameters can significantly boost the generalization of deep neural networks. The same observation can be made in deep learning for semi-supervised and unsupervised learning in structured domains. This raises an important question that is addressed in this paper: What kind of priors on input/output structure can be encoded through parameter-sharing? This work is an attempt at answering this question, when our priors are in the form discrete domain symmetries. To formalize this type of prior, a family of transformations of input and output to a neural layer are expressed as group “action” on the input and output. The resulting neural network is invariant to this action, if transformations of the input within that particular family, does not change the output (e.g., rotation-invariance). However, if the output is transformed, in a predictable way, as we transform the input, the neural layer is equivariant to the action of the group. School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA, USA 15217. Correspondence to: Siamak Ravanbakhsh <mravanba@cs.cmu.edu>. Proceedings of the 34 th International Conference on Machine Learning, Sydney, Australia, PMLR 70, 2017.  Application of group theory in machine learning has been the topic of various works in the past (e.g., Kondor, 2008; Bartók et al., 2010). In particular, many probabilistic inference techniques have been extended to graphical models with known symmetry groups (Raedt et al., 2016; Kersting et al., 2009; Bui et al., 2012; Niepert, 2012). Deep and hierarchical models have used a variety of techniques to study or obtain representations that isolate transformations from the “content” (e.g., Hinton et al., 2011; Jayaraman & Grauman, 2015; Lenc & Vedaldi, 2015; Agrawal et al., 2015). The simplest method of achieving equivariance is through data-augmentation (Krizhevsky et al., 2012; Dieleman et al., 2015). Going beyond augmentation, several methods directly apply the group-action, in one way or another, by transforming the data or its encodings using group members (Jaderberg et al., 2015; Anselmi et al., 2013; Dieleman et al., 2016). An alternative path to invariance via harmonic analysis. In particular cascade of wavelet transforms is investigated in (Bruna & Mallat, 2013; Oyallon & Mallat, 2015; Sifre & Mallat, 2013). More recently (Cohen & Welling, 2016b) study steerable filters (e.g., Freeman et al., 1991; Hel-Or & Teo, 1998) as a general mean for achieving equivariance in deep networks. Invariance and equivariance through parameter-sharing is also discussed in several prior works (Cohen & Welling, 2016a; Gens & Domingos, 2014). The desirability of using parameter-sharing for this purpose is mainly due to its simplicity and computational efficiency. However, it also suggests possible directions for discovering domain symmetries through regularization schemes. Following the previous work on the study of symmetry in deep networks, we rely on group theory and group-actions to formulate invariances and equivariances of a function. Due to discrete nature of parameter-sharing, our treatment here is limited to permutation groups. Action of a permutation group G can model discrete transformations of a set of variables, such as translation and 90○ rotation of pixels around any center in an image. If the output of a function transforms with a G-action as we transform its input with a different G-action, the function is equivariant with respect to action of G. For example, in a convolution layer, as we translate the input, the feature-maps are also translated. If ar X iv :1 70 2. 08 38 9v 2 [ st at .M L ] 1 3 Ju n 20 17 Equivariance Through Parameter-Sharing Figure 1.  given a group action on input and output of a neural network layer, define a parameter-sharing for this layer that is equivariant to these actions. (left) G = D5 is a Dihedral group, acting on a 4 × 5 input image and an output vector of size 5. N and M denote the index set of input, and output variables respectively. Here G is represented using its Cayley diagram. (middle-left) G-action for g ∈ G is shown for an example input. G-action on the input is a combination of circular shifts (blue arrows) and vertical flips (red arrows) of the 2D image. G acts on the output indices M only through circular shift. A permutation group GN,M encodes the simultaneous “action” of G on input and output indices. (middle-right) The structure Ω designed using our procedure, such that its symmetries Aut(Ω) subsumes the permutation group GN,M. (right) the same structure Ω unfolded to a bipartite form to better show the resulting parameter-sharing in the neural layer. The layer is equivariant to G-action: shifting the input will shift the output of the resulting neural network function, while flipping the input does not change the output. the output does not transform at all, the function is invariant to the action of G. Therefore, invariance is a special equivariance. In this example, different translations correspond to the action of different members of G. The novelty of this work is its focus on the “model symmetry” as a gateway to equivariance. This gives us new theoretical guarantees for a “strict” notion of equivariance in neural networks. The core idea is simple: consider a colored bipartite graph Ω representing a neural network layer. Edges of the same color represent tied parameters. This neural network layer as a function is equivariant to the actions of a given group G (and nothing more) iff the action of G is the symmetry group of Ω – i.e., there is a simple bijection between parameter symmetries and equivariences of the corresponding neural network. The problem then boils down to designing colored bipartite graphs with given symmetries, which constitutes a major part of this paper. Fig. 1 demonstrates this idea.1 For the necessary background on group theory see the Appendix. In the following, Section 1 formalizes equivariance wrt discrete group action. Section 2 relates the model symmetries a neural layer to its equivariance. Section 3 then builds on this observation to introduce two procedures for parameter-sharing that achieves a desirable equivariance. Throughout this paper, since we deal with finite sets, we use circular shift and circular convolution instead of shift and convolution. The two can be made identical with zero-padding of the input. Here, we also see how group and graph convolution as well as deep-sets become special instances in our parametersharing procedure, which provides new insight and improved design in the case of group convolution. Where input and output of the layer have a one-to-one mapping, we see that the design problem reduces a well-known problem in combinatorics. 1. Group Action and Equivariance Let x = [x1, . . . , xN ] ∈ X denote a set of variables and G = {g} be a finite group. The discrete action of G on x is in the form of permutation of indices in N = {1, . . . ,N}. This group is a subgroup of the symmetric group SN; the group of all N ! permutations of N objects. We use Ð→ N = [1, . . . ,N] to denote the ordered counterpart to N and the G-action on this vector g Ð→ N ≐ [g1, . . . ,gN] is a simple permutation. Using xÐ→ N to denote x, the discrete action of g ∈ G on x ∈ X is given by gxÐ→ N ≐ x g Ð→ N . G-action on N is a permutation group that is not necessarily isomorphic to G itself. GN ≤ G captures the structure of G when it acts on N. We use gN to denote the image of g ∈ G in GN. G-action is faithful iff two groups are isomorphic G ≅ GN – that is G-action preserves its structure. In this case, each g ∈ G maps to a distinct permutation g Ð→ N ≠ g′Ð→ N∀g,g′ ∈ G. Given any G-action on N we can efficiently obtain GN; see Appendix. Equivariance Through Parameter-Sharing Example 1.1 (Cyclic Group) Consider the cyclic group G = Z6 and define its action on x ∈ R by defining it on the index set N = {1,2,3} as gn ≐ g + n mod 3∀g ∈ Z6. This action is not faithful. For example, the action of g = 1 and g = 4 result in the same permutations of variables in x; i.e., single-step of circular shift to the right. With the above action, the resulting permutation group GN is isomorphic to Z3 < Z6. Now consider the same group G = Z6 with a different action on N: gn ≐ g − n mod 3∀g ∈ Z6, where we replaced (+) with (−). Let G̃N be the resulting permutation group. Here again G̃N ≅ Z3. Although isomorphic, G̃N ≠ GN, as they are different permutation groups of N. Consider the function φ ∶ X → Y and let GN and GM be the action of G on input/output index sets N and M. Definition 1.1 The joint permutation group GN,M is a subdirect product (or pairing) of GN and GM GN,M = GN ⊙GM ≐ {(gN,gM) ∣ g ∈ G}. We are now ready to define equivariance and invariance. φ(⋅) is GN,M-equivariant iff gNφ(x) = φ(gMx) ∀x ∈ X , (gN,gM) ∈ GN,M (1) Moreover, if GM = {e} is trivial, we have gNφ(x) = φ(x) ∀x ∈ X ,gN ∈ GN and φ(⋅) is GN-invariant. gN and gM can also be represented using permu