Title: PERMUTATION EQUIVARIANT MODELS FOR COMPOSITIONAL GENERALIZATION IN LANGUAGE

Abstract: Humans understand novel sentences by composing meanings and roles of core language components. In contrast, neural network models for natural language modeling fail when such compositional generalization is required. The main contribution of this paper is to hypothesize that language compositionality is a form of group-equivariance. Based on this hypothesis, we propose a set of tools for constructing equivariant sequence-to-sequence models. Throughout a variety of experiments on the SCAN tasks, we analyze the behavior of existing models under the lens of equivariance, and demonstrate that our equivariant architecture is able to achieve the type compositional generalization required in human language understanding.

1. INTRODUCTION:

When using language, humans recombine known concepts to understand novel sentences. For instance, if one understands the meaning of "run", "jump", and "jump twice", then one understands the meaning of "run twice", even if such sentence was never heard before. This relies on the notion of language compositionality, which states that the meaning of a sentence ("jump twice") is to be obtained by the meaning of its constituents (e.g. the verb "jump" and the quantifying adverb "twice") and the use of algebraic computation (a verb combined with a quantifying adverb m results in doing that verb m times) (Kratzer & Heim, 1998) .

In the realm of machines, deep learning has achieved unprecedented results in language modeling tasks (Bahdanau et al., 2015; Vaswani et al., 2017) . However, these models are sample inefficient, and do not generalize to examples that require the use of language compositionality (Lake & Baroni, 2018; Loula et al., 2018; Dessì & Baroni, 2019) . This result suggests that deep language models fail to leverage compositionality; a failure remaining to this day a roadblock towards true natural language understanding. Focusing on this issue, Lake & Baroni (2018) proposed the Simplified version of the CommAI Navigation (SCAN), a dataset to benchmark the compositional generalization capabilities of state-ofthe-art sequence-to-sequence (seq2seq) translation models (Sutskever et al., 2014; Bahdanau et al., 2015) . In a nutshell, the SCAN dataset contains compositional navigation commands such as JUMP TWICE AFTER RUN LEFT, to be translated into the sequence of actions LTURN RUN JUMP JUMP.

Using SCAN, Lake & Baroni (2018) demonstrated that seq2seq models fail spectacularly at tasks requiring the use of language compositionality. Following our introductory example, models trained on the three commands JUMP, RUN and JUMP TWICE fail to generalize to RUN TWICE. Most recently, Dessì & Baroni (2019) showed that architectures based on temporal convolutions meet the same fate.

SCAN did not only reveal the lack of compositionality in language models, but it also became the blueprint to build novel language models able to handle language compositionality. On the one hand, Russin et al. (2019) proposed a seq2seq model where semantic and syntactic information are represented separately, in a hope that such disentanglement would elicit compositional rules. However, their model was not able to solve all of the compositional tasks comprising SCAN. On the other hand, Lake (2019) introduced a meta-learning approach with excellent performance in multiple SCAN tasks. However, their method requires substantial amounts of additional supervision, and a complex meta-learning procedure hand-engineered for each task.

In this paper, we take a holistic look at the problem and connect language compositionality in SCAN to the disparate literature in models equivariant to certain group symmetries (Kondor, 2008; Cohen & Welling, 2016; Ravanbakhsh et al., 2017; Kondor & Trivedi, 2018) . Interesting links have recently been proposed between group symmetries and the areas of causality (Arjovsky et al., 2019) and disentangled representation learning (Higgins et al., 2018) , and this work proceeds in a similar fashion. In particular, the main contribution of this work is not to chase performance numbers, but to put forward the novel hypothesis that language compositionality can be understood as a form of group-equivariance (Section 3). To sustain our hypothesis, we provide tools to construct seq2seq models equivariant when the group symmetries are known (Section 4), and demonstrate that these models solve all SCAN tasks, except length generalization (Section 6).1 

2. THE SCAN COMPOSITIONAL TASKS:

The purpose of the Simplified version of the CommAI Navigation (SCAN) tasks (Lake & Baroni, 2018) is to benchmark the abilities of machine translation models for compositional generalization. Following prior literature (Lake & Baroni, 2018; Baroni, 2019; Russin et al., 2019; Andreas, 2019) , compositional generalization is understood as the ability to translate novel families of sentences, when this requires leveraging the compositional structure in language.

The SCAN dataset contains compositional navigation commands in English (the input-language) paired with a desired action sequence (the output-language). For instance, the input-language sentence JUMP TWICE AND RUN LEFT is paired to the output-language actions sequence JUMP JUMP LTURN RUN. The rest of our exposition uses SMALL CAPS to denote examples in the input-language, and LARGE CAPS to denote examples in the output-language. Appendix A contains a full description of the grammar generating the SCAN language.

To evaluate the compositional generalization abilities of sequence-to-sequence (seq2seq) machine translation models (Sutskever et al., 2014; Bahdanau et al., 2015) , Lake & Baroni (2018) To succeed in this task, models must learn that JUMP is a verb, and that any verb can be composed with an adverbial number to be repeated a number of times.

3. Around right task: the phrase AROUND RIGHT is held out from the training set; however, both AROUND and RIGHT are shown in all other contexts (for example, AROUND LEFT or OPPOSITE RIGHT). To succeed at this task, models must learn that both RIGHT and LEFT are directions, and can be combined with AROUND and OPPOSITE.

4. Length generalization task: the training set contains pairs such that the length of the action sequence in the output-language is shorter than 24 actions. The test set contains all pairs with action sequences of a length greater or equal than 24 actions. The type of compositional ability required to succeed at this task is more difficult to sketch out, as we discuss in Section 6.2.

Lake & Baroni (2018) use these four tasks to demonstrate that state-of-the-art seq2seq translation models (Bahdanau et al., 2015) succeed at Simple task, but fail at the other three tasks requiring compositional generalization. Convolutional architectures (Dessì & Baroni, 2019) achieve only slightly better performance, and state-of-the-art methods specially developed to address SCAN tasks fall short from the best achievable performance (Russin et al., 2019) , or call for substantial amounts of additional supervision (Lake, 2019).

In the following, we take a holistic look at the language compositionality problems in SCAN, and highlight their connection to equivariant maps in group theory.

3. SCAN COMPOSITIONALITY AS GROUP EQUIVARIANCE:

This section puts forward the hypothesis that:

Models achieving the compositional generalization required in certain SCAN tasks are equivariant with respect to permutation group operations2 in the input and output languages.

To unfold the meaning of our hypothesis, we must revisit some basic concepts in group theory. A discrete group G is a set of elements {g 1 , . . . , g |G| }, equipped with a binary group operation "•" satisfying the four group axioms (closure, associativity, identity, and invertibility). The sequel focuses on permutation groups G, whose elements are permutations of a set X , and whose binary group operation composes the permutations contained in G. The set of all permutations of X is a group, but not all subsets of permutations of X satisfy the four group axioms, and therefore they do not form a group. For each element g ∈ G, we define the group operation T g : X → X as the map applying the permutation g to the element x ∈ X , to obtain T g x. Armed with these definitions, we are ready to introduce the main object of study in this paper: equivariant maps.

Definition 1 (Equivariant map). Let X and Y be two sets. Let G be a group whose group operation on X is denoted by T g : X → X , and whose group operation on Y is denoted by T g : Y → Y. Then, Φ : X → Y is an equivariant map if and only if Φ (T g x) = T g Φ(x) for all x ∈ X and g ∈ G.

The operation groups (T g , T g ) defined above operate on entire sequences, an enormous space when we consider those sequences to be language sentences. In the following two definitions, we relax group operations and equivariant maps to operate at a word level.

Definition 2 (Local group operations). Let X be a set of sequences (or sentences), where each sequence x ∈ X contains elements x i ∈ V from a vocabulary set V, for all x i ∈ x. Let G be a group with associated group operation T g : X → X . Then, we say that T g is a local group operation if there exists a group operation T gw : V × V such that T g x = (T gw x 1 , . . . , T gw x Lx ) for all x ∈ X .

When understanding sequences as language sentences, the group operation T gw would be a permutation of the words from the language vocabulary. Such operation can be implemented in terms of a permutation matrix, a |V| × |V| matrix with zero/one entries where each row and each column sum to one. Finally, we leverage the definition of local group operations to define locally equivariant maps.

Definition 3 (Locally equivariant map). Let X and Y be two sets of sequences. Let G be a group whose group operation on X is local in its vocabulary, denoted by T g : X → X , and whose group operation on Y is local in its vocabulary and denoted by T g : Y × Y. Then, we say that Φ : X → Y is an equivariant map if and only if Φ(T g x) = T g Φ(x) for all x ∈ X and g ∈ G.

x 

LTURN RUN:

(2)

WALK:

(2)

(1)

LTURN RUN (c) Now, how do equivariances and local equivariances manifest themselves in the world of SCAN? To assist our examples, the commutative diagram in Figure 1a summarizes the group theory notations introduced so far. In Figure 1b and Figure 1c , we parallel these notations to two different examples of compositional skills required to solve SCAN: verb and conjunction replacement. In the SCAN domain, X is the set of sentences in the input-language, and Y is the set of sentences in the outputlanguage. Furthermore, let Φ be a locally equivariant SCAN translation model, and let G be a group with associated local group operations that permutes words in the input-and output-languages.

On the one hand, we observe in Figure 1b that local equivariance enables compositional generalization in the case of verb replacement. This is because replacing one verb in the input-language can be implemented in terms of a local group operation. In turn, this input-verb replacement corresponds deterministically to a second local group operation that replaces the corresponding verb in the output-language. The same would apply to a SCAN task where we are interested in generalizing to the replacement of LEFT and RIGHT. As such, a translation model Φ with these compositional generalization capabilities must be locally equivariant.

On the other hand, we observe in Figure 1c that local equivariance is insufficient to enable compositional generalization in the case of conjunction replacement. This is because no local group operation in the output-language would be able to implement the necessary changes induced by the replacement of AND by AFTER in the input-language. In such cases, we refer to the equivariance as global equivariance. In particular, we can see how blocks of multiple words in the output-language swap their relative location. Local equivariances are also insufficient to enable compositional generalization in the Length generalization SCAN task and we elaborate on this in Section 6.2.

In the following section, we propose a set of tools to implement equivariant seq2seq translation models, and propose a particular architecture with which we conduct our experiments.

4. IMPLEMENTING AN EQUIVARIANT SEQUENCE-TO-SEQUENCE MODEL:

We now implement our proposed equivariant seq2seq model, following the encoder-decoder architecture illustrated in Figure 2 . Readers unfamiliar with group theory may parse Figure 2 by temporarily discarding the "G-" prefixes, and realize that each depicted module is a well-known building block of recurrent neural network models. To make our model equivariant, we will make intense use of group convolutions.

w t G-Embed e(w t ) G-RNN h t-1 h t (a) G-Equivariant Encoder h 1 . . . . . . h Lx G-Attention ht-1 G-RNN ht ãt G-Conv φ G-Decode wt e( wt-1 ) G-Embed wt-1 (b) G-Equivariant Decoder

Definition 4 (Group convolution (Kondor & Trivedi, 2018) ). Let G be a discrete group. Let f : G → R K be an input function. Let ψ = {ψ i : G → R K } K i=1 be a set of learnable filter functions. Then, each scalar real entry from the result of G-convolving f and ψ is given by a |G| × K matrix with entries

EQUATION

for all g ∈ G and i ∈ {1, . . . , K }. As shown by (Kondor & Trivedi, 2018) , the G-Conv layer is equivariant wrt the operations of G. We apply this definition in two ways: (i) "convolving" words with learnable filters to generate equivariant embeddings. Later, when we introduce our notations, we discuss how words may be viewed as functions so as to fit the definition. And (ii) convolving two group representations, in which case dom(f ) = G.

We note that there are several additional methods proposed in the literature for constructing permutation equivariant layers (e.g. , Zaheer et al., 2017; Ravanbakhsh et al., 2017) . However, as demonstrated by Kondor & Trivedi (2018) ; Bloem-Reddy & Teh (2019) , the above form is very general and subsumes most alternatives. Further, while layers based on weight-sharing may be more efficient than the general form of Definition 4, the parameter tying restricts the capacity of the layer. For example, the permutation equivariant layer of Zaheer et al. (2017) requires weight matrices that are restricted to a form λI + γ(11) T , with learnable parameters λ and γ. This layer has fewer learnable parameters than the convolutional form of Definition 4. Thus, for reasons of generality and capacity, we employ the general and expressive convolutional form of Definition 4 for our permutation equivariant layers.

Equivariant with respect what group? The previous G-Conv layer requires choosing a discrete group G. As hinted in Section 3, we will choose G to contain |G| permutations of language vocabularies, e.g. products of cyclic groups on sets of words. Note that for a vocabulary size of |V |, the set of all permutations has a size of n!. However, it suffices to consider subgroups containing permutations such that every word can be reached by composing elements of the subgroup. For example, while the group of permutations on the four verbs in SCAN consists of 24 elements, it will suffice to choose G as the circular shift group on the four verbs, which is a subgroup of four elements. Following standard notation in group theory, we write g • h to denote the composition of two group elements g, h ∈ G, and g -1 to denote the inverse element of g.

As final preliminaries, denoting [V ] = {1, . . . , |V |}, we represent a word w in the input-language by the function w : [V ] → {0, 1}, where v∈[V ] w(v) = 1, and similarly by using w ∈ Ṽ for the output-language. These notations are functional representations of word one-hot encodings that will play well with our notations. Note that this representation is equivalent to one-hot vectors, and in what follows we use the shorthand w for the one-hot vector representation of words.

To avoid notational clutter, we use g to denote the permutation-matrix-representation of the corresponding group element. Thus, the group operation on a word gw can be implemented as matrix multiplication between the permutation matrix g and the one-hot vector w. Note that this operation results in another one-hot vector, i.e. another word in the vocabulary. Similarly, the binary group operation can be written as matrix multiplication gh between two group members g, h ∈ G. Here too, multiplication of permutation matrices results in permutation matrix, so gh ∈ G.

We now describe each of the components in our G-equivariant translation model, by following the transformation process of an input sequence x = (w 1 , . . . , w Lx ) (in SCAN, a navigation command in English) into its output translation y = ( w1 , . . . , wLy ) (in SCAN, a sequence of actions).

4.1. G-EQUIVARIANT ENCODER:

Upon arrival, the input-language sentence x = (w 1 , . . . , w Lx ) is sent to a G-equivariant encoder. The first step in the encoding process is to transform each input word w t into a permutation equivariant embedding e(w t ). As mentioned before, each word w t is represented by the one-hot vector w t :

[V ] → {0, 1}. The corresponding embedding is obtained by applying a set of K 1-dimensional learnable filter functions {ψ i : [V ] → R} K i=1 in a group convolution (throughout the section, we use K everywhere to ease notation). Using Definition 4, the embedding, which we call G-Embed, is then represented as a matrix R |G|×K , where

EQUATION

for all g ∈ G and i = {1, . . . , K}. Note that since w is a one-hot vector, G-Embed is a particularly simple instantiation of Definition 4, as summation over dom(f ) consists of only a single term. The corresponding embedding is a function e(w t ) : G → R K , which can be represented as a |G| × K matrix, where each row corresponds to the embedding of the word gw for a particular g ∈ G. This layer can be implemented by defining ψ with standard deep learning embedding modules. 3Importantly, we note that for this layer, both ψ and w are functions on [V ]. However, the resulting embedding e(w) is a function on the group G. Therefore, in all subsequent computations we will require the learnable filters ψ to also be functions on G.

We illustrate this layer with an example. Let G be the cyclic group that permutes the words LEFT and RIGHT. We can think of g 1 as the identity, and g 2 as permuting the words LEFT and RIGHT (leaving all other words unchanged). In this case, embedding LEFT results in the 2 × K matrix [ψ(LEFT) T , ψ(RIGHT) T ] T , while embedding JUMP results in [ψ(JUMP) T , ψ(JUMP) T ] T , since both g 1 and g 2 act as the identity permutation for JUMP.

Next, the word embedding e(w t ) is sent to a permutation equivariant Recurrent Neural Network (G-RNN). The cells of a G-RNN mimic those of a standard RNN, where linear transformations are replaced by G-Convs (Definition 4). This cell receives two inputs (the word embedding e(w t ) and the previous hidden state h t-1 ) and returns one output (the current hidden state h t ), all three being functions G → R K , parametrized as |G| × K matrices. More specifically:

EQUATION

where ψ h , ψ e : G → R K are learnable filters (represented as |G| × K matrices), and σ is a point-wise activation function.

The cell G-RNN is equivariant because the sum of two equivariant representations is equivariant (Cohen & Welling, 2016) , and the pointwise transformation of an equivariant representation is also equivariant. To initialize the hidden state, we set h 0 = 0. We note that our experiments use the equivariant analog of LSTM cells (Hochreiter & Schmidhuber, 1997) , which we denote G-LSTM, since these achieved the best performance. We include the architecture of G-LSTM cells in Appendix B.

This completes the description of our equivariant encoder, illustrated in Figure 2a .

4.2. G-EQUIVARIANT DECODER:

Once the entire input-language sentence x = (w 1 , . . . , w Lx ) has been encoded into the hidden representations h = (h 1 , . . . , h Lx ), we are ready to start the decoding process that will produce the output-language translation y = ( w1 , . . . , wLy ).

As illustrated in Figure 2b , our equivariant decoder is also run by an equivariant recurrent cell G-RNN.

We denote the hidden states of the recurrent decoding process by ht , where h0 = h Lx . At time t, the two inputs to the decoding G-RNN cell are the previous hidden state ht-1 as well as an attention āt over all the encoding hidden states h. (Once again, all variables are mappings G → R K implemented as |G| × K matrices.)

Attention mechanisms (Bahdanau et al., 2015; Vaswani et al., 2017) have emerged as a central tool in language modelling. Fortunately, attention mechanisms are typically implemented as linear combinations, and a linear combination of equivariant representations is itself an equivariant representation.

We now leverage this fact to develop an equivariant attention mechanism. Given all the encoder hidden states h, as well as the previous decoding hidden state ht-1 , we propose the equivariant analog of dot-product attention (Luong et al., 2015) as

āt = G-Attention( ht-1 , h) = Lx j=1

α t,j h j , where (4)

α t,j = exp β t,j Lx k=1 exp β t,k

, and β t,j = g∈G ht-1 (g) h j (g).

(5)

Following Figure 2b , the attention āt and a G-embedding e( wt-1 ) for the previous output word are concatenated and sent to a G-Convolution. 4 The concatenation with e( wt-1 ) provides the decoder with information regarding the previously embedded word. In practice, during training we use teacher-forcing (Williams & Zipser, 1989) to provide the decoder with information about the correct output sequences. This process returns a final hidden representation φ : G → R K .

As a final step in the decoding process, we need to convert φ into a collection of logits over the output-language vocabulary. Then, sampling from the categorical distribution induced by these logits at time t (or taking the maximimum) will produce the word wt , to be appended in the output-language translation, y. This final decoding module can be implemented as follows:

EQUATION

where ψ = [ Ṽ ] → R k are the learnable parameters of this layer (represented by a | Ṽ | × K matrix).

Recall that φ(h) ∈ R K is the final-layer representation for the group element h, and that h -1 w is the inverse element of h ∈ G applied to the output word w (represented as a one-hot vector), which results in another word in the output language. Thus, ψ is a learnable embedding of the output words into R K . This layer is evaluated at every w in the output vocabulary to produce a scalar. The resulting vector of logits represents a categorical distribution over the output vocabulary. While similar, this layer is not a group convolution (Definition 4). Rather, equivariance for this module is achieved via parameter-sharing (Ravanbakhsh et al., 2017) .

This completes the description of our equivariant decoder, illustrated in Figure 2b . Composing the equivariant encoder and decoder results in our complete sequence-2-sequence model. Importantly, since all operations in this model are equivariant, the complete model is itself also equivariant to the group G (Kondor & Trivedi, 2018) . In Section 6, we provide further implementation details for our model, and detail our empirical evaluation of its equivariant properties and their relation to the SCAN tasks described in Section 2.

5. RELATED WORK:

In this section we review state-of-the-art methods to address SCAN compositional tasks. We focus on two recent models that we will compare to in our experiments.

On the one hand, the syntactic attention model of Russin et al. (2019) builds on the idea that compositional generalization can be achieved by language models given the correct architectural organization. Borrowing inspiration from neuroscience, Russin et al. (2019) argue that compositionality might arise when using separate processing channels for semantic and syntactic information. In their model, the attention weights depend on a recurrent encoding of the input sequence, which they refer to as the syntactic representation. The attention weights are then applied to separate, context-independent embeddings of the words in the input sequence, which intend to model a semantic representation. We find (Russin et al., 2019) interesting from a group equivariance perspective, since one way to enforce equivariance is to use an invariant representation (about syntax) together with an additional representation (about semantics) that maintains the information about the original "sentence pose".

On the other hand, the meta-learning (Thrun & Pratt, 2012; Schmidhuber, 1987) approach of Lake ( 2019) is a model that learns to generalize. In particular, Lake (2019) designs one specific and complex meta-learning procedure for each SCAN task, where a distribution over tasks is provided to the learner (Finn et al., 2017; Gordon et al., 2018) . For example, in the Add jump and Around right tasks, the meta-learning procedure of Lake (2019) samples permutations from the relevant groups (the permutation groups on the verbs and set of directions, respectively). This is interpreted as data-augmentation, a valid procedure for encouraging equivariance (Cohen & Welling, 2016; Andreas, 2019; Weiler et al., 2018) . However, at test-time, Lake (2019) sets the context set to the correct mapping between the permuted commands and their corresponding actions. For example, in the Add jump task, the context set for meta-testing would consist of the following pairs: {(WALK, WALK), (RUN, RUN), (LOOK, LOOK), (JUMP, JUMP) }. This is equivalent to providing the model with one-to-one information regarding the correct command-to-action mapping for the permuted words.

6. EXPERIMENTS:

We now evaluate the empirical performance of our equivariant seq2seq model (described in Section 4) on the four SCAN tasks (described in Section 2). We compare our equivariant seq2seq to regular seq2seq models (Lake & Baroni, 2018) , convolutional models (Dessì & Baroni, 2019) , the syntactic attention model of Russin et al. (2019) , and the meta-learning approach of Lake (2019). The compared seq2seq models use bi-directional, single-layer LSTM cells with 64 hidden units. For the equivariant Model Simple Add Jump Around Right Length seq2seq (Lake & Baroni, 2018) 99.7 1.2 NA 13.8 CNN (Dessì & Baroni, 2019) 100.0 69.2 ± 9.2 56.7 ± 10.2 0.0 Syntactic Attention (Russin et al., 2019) 100.0 91.0 ± 27.4 28.9 ± 34.8 15.2 ± 0.7 Meta seq2seq (Lake, 2019) NA 99.9 99.9* 16.64 seq2seq (comparable architecture) 100.0 0.0 ± 0.0 0.02 ± 2e-2 12.4 ± 2.3 Equivariant seq2seq (ours) 100.0 99.1 ± 0.04 92.0 ± 0.24 15.9 ± 3.2 seq2seq models, we use the cyclic permutation group on the verbs for the Add jump task, and the cyclic permutation group on directions for the Around right task. For Length, we use the product of those groups. Our model knows that the same group operates on both the input-and output-languages. However, it does not receive information regarding the correspondence between commands and actions in the set of words being permuted in the input / output languages. This is in contrast to Lake (2019), where (as stated in Section 5), it is necessary to provide the model with explicit information regarding the correct command-to-action mapping at test-time.

Training procedures match those of Lake & Baroni (2018) where possible. We train models for 200k iterations, where each iteration consists of a minibatch of size 1, using the Adam optimizer to perform parameter updates with default parameters (Kingma & Ba, 2015) with a learning rate of 1e-4. We use teacher-forcing (Williams & Zipser, 1989 ) with a ratio of 0.5, and early-stopping based on a validation set consisting on 10% of the training examples. As in previous works, we compute test accuracies by counting how many exact translations each model provides, across the test set associated to each task.

6.1. RESULTS:

Table 1 summarizes the results of our experiments. First and as expected, all models achieve excellent performance on the Simple task, which does not require any form of compositional generalization.

Second, our equivariant seq2seq model performs very well at the Add jump and Around right SCAN tasks, which are the two tasks satisfying our local equivariance assumption from Definition 3. Our equivariant seq2seq model significantly outperforms the regular seq2seq (Lake & Baroni, 2018) and convolutional (Dessì & Baroni, 2019 ) models, as well as the state-of-the-art methods of Russin et al. (2019) and Lake (2019). This result is an encouraging piece of evidence supporting our main hypothesis from Section 3. Next, let us compare the results of our equivariant seq2seq model with the previous state-of-the-art Russin et al. (2019) ; Lake (2019) in more detail.

On the one hand, the syntactic attention model of Russin et al. (2019) achieves significant improvements over baselines methods at the Add jump SCAN task. However, it does not fare so well on the Around right task. Furthermore, its performance has high variance. Although we here report the numbers from Russin et al. (2019) , we observed such high variance in our own implementation as well, where the model often achieved 0% test accuracy. We hypothesize that modeling the invariance of the syntactic attention directly would result in improved performance and stability. This can be achieved, for instance, by replacing all verbs in the syntactic module by a shared word. As expected, by explicitly exploiting equivariance, our model outperforms Russin et al. (2019) on the Add jump and Around right SCAN tasks, also being much more robust.

On the other hand, the meta-learning model of Lake (2019) achieves excellent performance on the local equivariance tasks Add jump and Around right. This is additional evidence supporting the usefulness of local equivariance. In contrast to our model, Lake (2019) requires (i) a complicated model and training procedure tailored to each task, (ii) providing the model with the correct permutation of words, equivalent to telling the model the "true" mappings between the input and output words, and (iii) augmenting the set of words being permuted, to ensure enough diversity in the training distribution (for instance, adding additional directions beyond RIGHT and LEFT).

6.2. ON THE DIFFICULTY OF LENGTH GENERALIZATION:

As seen in Table 1 , length generalization remains a tough challenge in SCAN. While generating long sequences is a known challenge in seq2seq models (Bahdanau et al., 2015) , we believe that this is not the main issue with our equivariant seq2seq model, as it is able to produce long translations when these appear in the training set (as are the other models). Therefore, this is not a capacity problem, but one of not being able to express the Length generalization SCAN task in terms of local equivariances on both input-and output-languages. We hypothesize that this is the very reason why (Russin et al., 2019; Lake, 2019 ) also fail on this task.

However, we suspect that some forms of local equivariance on the input language, but global equivariance on the output language, may help. 

7. DISCUSSION AND FUTURE WORK:

This work has introduced hypothesis linking between group equivariance and compositional generalization in language. Motivated by this hypothesis, we have proposed an equivariant seq2seq translation model, which achieves state-of-the-art performance on a variety of SCAN tasks.

Our work has several points for improvement. Most importantly, our model requires knowing the permutation symmetries of interest, to be provided by some domain expert. While this is simple to do in the synthetic language of SCAN, it may prove more difficult in real-world tasks. We propose three directions to attack this problem. (i) Group words by their parts-of-speech (e.g., nouns, verbs, etc.), which can be done automatically by standard part-of-speech taggers (Màrquez & Rodríguez, 1998) ; (ii) Learn such groupings of words from corpora, for example using the recent work of Andreas ( 2019); (iii) Most appealingly, parameterize the symmetry group and learn operations end-to-end while enforcing the group structure. For permutation symmetries, the group elements can be parameterized by permutation matrices, and learned from data (Lyu et al., 2019) . Our preliminary work in this direction hints that this is a fruitful avenue for future research.

A further consideration to address is that of computational overhead. In particular, for the convolutional form we use in this work (Definition 4), computational complexity scales linearly with the size of the group, O(|G|). This arises from the need to sum over group elements when the representation is a function on G, and may be prohibitive when considering large groups. One way of addressing this issue when large symmetry groups are of interest is to consider more efficient computational layers for permutation equivariance (e.g Zaheer et al., 2017; Ravanbakhsh et al., 2017) . These methods incur less computational overhead at the cost of restricting the layer capacity. Another interesting option for future research is to consider sub-sampling group elements when performing the summation in Definition 4, which requires further consideration of the consequences of doing so.

Another exciting direction for future research is to consider global equivariances. Many operations of interest, e.g. groups operating directly on parse trees, can only be expressed as global equivariances. Modeling these equivariances holds exciting possibilities for capturing non-trivial symmetries in language tasks, but also requires more sophisticated machinery than is proposed in this work.

Finally, in further theoretical work, we would like to explore the relation between our equivariance framework and the idea of compositionality in formal semantics (Kratzer & Heim, 1998) . On the one hand, the classic idea of compositionality as an isomorphism between syntax and semantics is intuitively related to the notion of group equivariance. On the other hand, as shown by the failures at the length generalization example, it is still unclear how to apply our ideas to more sophisticated forms of permutation, such as those involving grammatical phrases rather than words. This would also require to extend our approach to account for the context-sensitivity that pervades linguistic composition (c.f., the natural interpretation of "run" in "run the marathon" vs. "run the code").

:

Code available at https://github.com/facebookresearch/Permutation-Equivariant-Seq2Seq

Standard terminology in group theory denotes the elements of a group "to act on" elements of a set. However, as the output language in SCAN is in navigation "actions", we use the "operate" terminology for group elements to avoid ambiguity.

e.g. PyTorch NN.EMBEDDING

To embed w0 we use a special "start of sentence" symbol, appended to the output language vocabulary.

Figures and Tables:

Figure 1: (a) Commutative diagram for equivariance. (b) Local equivariance enables generalization to verb replacement in SCAN. (c) Local equivariance does not enable generalization to conjunction replacement in SCAN.

Figure 2: Architecture of our fully-equivariant seq2seq model. Variables shaded in gray are mappings G → R K , implemented as |G| × K matrices. Encoder and decoder meet at h0 := hL x .

Test accuracies for four SCAN tasks, comparing our equivariant seq2seq to the state-of-the-art.

Table content: <table/>

For example, RUN TWICE, RUN THRICE and RUN AROUND LEFT TWICE are all input commands contained in the training set of the length task. A trained seq2seq model is able to execute them, but fails on the unseen test command RUN AROUND LEFT THRICE, suggesting that the network did not correctly understand the relationship between TWICE and THRICE. Using a network that is explicitly equivariant to the permutation of TWICE and THRICE should be able to generalize correctly on RUN AROUND LEFT THRICE. However, while the TWICE-THRICE permutation is a local group operation (Definition 2), the corresponding operation on the output language, which is to repeat the same action sequence multiple times, is a global group operation. Similarly, permuting AND and AFTER in the input sequence using a local group operation, while operating globally on the output language by permuting the order of the associated actions, should help succeed on the Length generalization SCAN task. How to formalize the aforementioned global operations on the output language and build the desired equivariant network remains a fascinating open research question that we leave for future work.

Table content: <table/>

Peer review (iclr2020):
Summary --- (motivation) Consider SCAN, a synthetic task where setences like S1=*jump twice and run left* are supposed to be translated into action sequences like A1=JUMP JUMP LTURN RUN. One might replace the word *jump* in S1 with *walk* then translate to get A2=WALK WALK LTURN RUN. If instead S1 is translated into A1 and then the action JUMP is replaced with the action WALK then we should still get the same A2. Such a translation model is equivariant to permutations of *jump* and *walk*. This paper aims to 1) define a general notion of compositionality as equivariance, 2) build a model which is compositional in this general sense, and 3) apply the model to SCAN. (approach - theory) This work considers this kind of compositionality as equivariance to group actions. Previous work (Kondor & Trivedi, 2018) viewed convolution as equivariance to actions by translation groups. This work views language compositionality as equivariance to actions by permutation groups applied to a set of similar words (e.g. verbs in SCAN). (approach - model) The paper proposes G-Embed, G-RNN, G-Attention, and G-Conv (not new) layers that are equivariant to word permuatations (e.g., switching *jump* and *walk*). It then composes these modules in a fairly standard fashion to build a new G-seq2seq model which is invariant to group actions. (experiments) Experiments apply a G-seq2seq model to the SCAN tasks, comparing to strong baselines. G-seq2seq requires slightly more knowledge (a set of related words like verbs) than all the baselines, but less knowledge than Lake 2019. 1. G-seq2seq outperforms all baselines except Lake 2019 (unfair comparison) on basic compositional tasks (*Add Jump* and *Around Right*). 2. Like other models, G-seq2seq fails on the *Length* task, though it is still among the best performers. Strengths --- The theory of compositionality as invariance to actions by permutation groups is new, interesting, and could turn out to be significant. The proposed models are also new, interesting, and could be significant. Experiments on SCAN verify that the proposed models work about as expected, sometimes beating strong baselines in the process. Weaknesses --- It*s hard to know what the impact of this paper will be because 1) it*s unclear whether this model can generalize to more useful domains and 2) the presentation may turn some readers away. While neither of these issues can really be solved, I think paper could be substantially better in both aspects. Corresponding suggestions: 1) How expensive is this? It seems quite expensive because the representation size scales with the number of permutation of the set of words equivariance is with respect to. How will it scale to larger problems in terms of computation/memory costs (especially larger vocab sizes)? What knowledge is required for applying this method to new domains--i.e., how do I choose a set of permutation equivariant verbs in general? More discussion of these issues may help increase the impact of the paper. 2) See next section. Presentation Weaknesses / Points of Confusion / Missing Details --- To mimic a typical decoder RNN there should be another input which copies the word 	ilde{w}_{t-1} from the previous iteration as input, somehow fused with the attention feature 	ilde{a}_t. How does the G-RNN know what the last word it generated was? The notation in the first equation of section 4.1: I think is supposed to take an integer as input but is a permutation applied to a function. I*m not sure how to apply permutations to functions like w and it doesn*t seem like the output should be an integer in any case so I find this notation confusing. Taking a step back, I find some of the notation (e.g., previous point) a bit confusing. This makes it hard for me to get the main point. I think the idea is that equivariant models can be achieved by tracking a representation (e.g., via rows of the G-Embed matrix) for (almost?) every member of the acting group. It may help the presentation to more frequently demonstrate the general concepts with examples, though doing so may be in conflict with the general nature of the paper*s theoretical contribution. I*m sure this is a familiar tradeoff, but from my perspective the paper would probably be more impactful if the presentation leaned more on examples. Equation numbers would be a really great addition. I found it hard to reference some of the material in writing my review. *and the use of algebraic computation* * This seems specific to the chosen example whereas the rest of the sentence is trying to be general. Suggestions --- * This seems related to [1], which uses group theory to define a notion of disentangled representation similar to compositionality. That may inspire future work and would be useful to mention in the related work. * Why didn*t performance on SCAN get to 100%? It would be useful to spend some time addressing points of failure for the model other than compositionality. * The G-RNN doesn*t have a bias. It*s not necessary, but it may be interesting to describe why this design choice was made. [1]: Higgins, Irina et al. “Towards a Definition of Disentangled Representations.” ArXiv abs/1812.02230 (2018): n. pag. Preliminary Evaluation --- Quality: The theoretical contributions make sense and the experiments show they lead to useful models. Clarity: The technical parts of the paper are somewhat unclear, but the rest of the paper is well written. Significance: As discussed in the Weaknesses section this could turn out to be very significant or not significant at all, but that*s true for a lot of good research. Originality: The general notion of equivariant neural networks and good performance on SCAN are novel. Overall, this is a very clear accept. Post-Rebuttal Update --- There was a lot of agreement between reviewers, though we came to slightly different conclusions about ratings. Though there is significant uncertainty about the impact of this work, I still think 8: Accept is the most appropriate rating. Overall, the other reviews and author responses only increased my confidence that this paper should be accepted.