Equivariant Transduction through Invariant Alignment (2022)

Abstract: The ability to generalize compositionally is key to understanding the potentially infinite number of sentences that can be constructed in a human language from only a finite number of words. Investigating whether NLP models possess this ability has been a topic of interest: SCAN (Lake and Baroni, 2018) is one task specifically proposed to test for this property. Previous work has achieved impressive empirical results using a group-equivariant neural network that naturally encodes a useful inductive bias for SCAN (Gordon et al., 2020). Inspired by this, we introduce a novel group-equivariant architecture that incorporates a group-invariant hard alignment mechanism. We find that our network’s structure allows it to develop stronger equivariance properties than existing group-equivariant approaches. We additionally find that it outperforms previous group-equivariant networks empirically on the SCAN task. Our results suggest that integrating group-equivariance into a variety of neural architectures is a potentially fruitful avenue of research, and demonstrate the value of careful analysis of the theoretical properties of such architectures.

## introduction humans painlessly process sentences they have never heard before. this feat is possible because they can construct the meaning of a sentence by composing the meaning of its parts. this phenomenon is known as compositional generalization in the computational linguistics literature @xcite and it is what enables the understanding of an infinite number of novel sentences from only a finite set of words @xcite . for example, without knowing what action the verb to blick describes, we know that blick twice indicates that this action should be performed two times. it is natural that we would like for neural network models of language to be endowed with this ability as well-and, indeed, if they are to achieve humanlike performance, it is likely to be necessary. there have been multiple proposals for methods of assessing these abilities in neural models @xcite . one popular benchmark is the scan task @xcite and its derivatives @xcite . scan involves translating natural language instructions into a sequence of actions executable by an agent navigating in an environment. examples of these commands are shown in figure 1 . in order to test generalization capabilities, there are various test-train splits which deliberately hold out specific words. for example, the training set for the add jump split only contains jump in the simple input-output pair (jump, jump), while the test set includes commands where it is combined with modifiers, such as jump twice and jump left. since the model has seen the effect of these modifiers on other verbs in training, a model with the ability to perform compositional generalization should be able to apply them to jump. scan is an example of a task that could benefit from a group-equivariant network. when a network possesses the property of equivariance to a group g, acting on the input with an element of g results in the output differing by the action of the same group element. with an appropriate choice of group, this property can be used to imbue a network with the ability to generalize compositionally. if we have a set of input words, and a corresponding set of their output words, and we act on these with a permutation group which swaps words within these sets, then swapping one word for another in the input will result in the corresponding output words being swapped in the output. this effectively means that when the network has learned an example in training it can generalize to any input which can be reached from the training example by acting on it with a group element. in the case of the scan task, the action on a sentence amounts to replacing a word with another vocabulary word from the same lexical class (e.g., replacing a verb with another verb). for example, if a g-equivariant network is trained on the scan task using a group g whose action amounts to swapping scan verbs, then the probability of run being mapped to run will be identical to the probability of jump being mapped to jump -thus even if only one verb is seen in training, it learns to apply observed patterns to the unseen verbs. this approach was first applied to scan by @xcite . we present a novel group-equivariant architecture for the scan task which has a notable theoretical advantage over similar existing approaches: the effective orbit of the model is larger, which results in more robust generalization to novel examples. from one input command, our model can potentially generalize to an exponential number of unseen examples, where previous group-equivariant models could generalize only to a constant number. we also demonstrate the empirical effect of this advantage, showing that our model outperforms that of @xcite all splits of the scan task. concretely, we incorporate group equivariance into the hard alignment string-to-string transduction model described by @xcite . hard alignment differs from the more common soft attention @xcite in that each output symbol is aligned with precisely one input symbol, rather than calculating a weighting over all input symbols. our model combines a groupinvariant hard alignment mechanism with a groupequivariant transduction mechanism, which enables its improved generalization capabilities. our findings motivate further exploration of groupequivariant architectures, and suggest that careful consideration of their provable equivariance properties is worthwhile. ## related work many attempts have been made to quantify what it means for a model to exhibit compositional behaviour and to create models that can successfully generalize compositionally. @xcite provide a summary article on this topic, in which they describe different aspects of compositional generalization and formulate methods for assessing a model on each aspect. in this work, we concern ourselves primarily with what hupkes et al. term systematicity-the ability to understand an unseen combination of previously seen parts. the scan task which we focus on has been approached in many ways. @xcite achieve state-of-the-art results on the task, achieving 100.0 across all splits, using a memory-augmented model, trained using reinforcement learning, which learns how to identify the symbolic functions described by specific phrases within inputs. @xcite approach the task using meta sequence-to-sequence learning. although this approach produces excellent results, it requires a bespoke meta-training approach for each generalization task. @xcite achieve good results by treating syntax and semantics separately. their model separately calculates likely alignments between input and output words, and calculates how likely a word is to be produced conditioned on the input word with which it is aligned. this approach is similar in concept to the hard alignment model that we use as the base for our g-equivariant architecture. equivariant networks built using group convolutions @xcite have been used most in the field of computer vision, where they have been used to create group convolutional neural networks (g-cnns) imbued with the property of invariance to transformations of an image such as rotation and reflection @xcite . recently these techniques have been adopted for nlp tasks: @xcite applied group-equivariant networks to the task of compositional generalization. they used the building block of the group convolution to construct group-equivariant network components, including an lstm, an attention mechanism and an embedding layer. their model is a group-equivariant analogue of a standard lstm-based sequence-tosequence model. they evaluate it on the scan task and achieve high accuracies on the splits assessing systematicity. we build on their work by presenting an alternative group-equivariant architecture for this task, resulting in more robust generalization abilities and improved empirical performance. ## an equivariant transducer we now describe the architecture of our equivariant hard alignment transducer. let σ be an input alphabet and ∆ be an output alphabet. given an input string @xmath0. we consider what it means for such a model to be equivariant with the following theorem. we know that the probability distribution conditioned on x is maximized by y * , so we have moving forward we will use this equivalent definition to discuss the equivariance of our model. ## limitations and future work group-equivariant networks have not yet been widely adopted in nlp, and we feel that there is potential for more tasks to be identified that could benefit from the application of group equivariance. a further line of investigation would be to develop and assess group-equivariant versions of a wider variety of architectures. the model used by @xcite is an equivariant version of a standard lstm-based sequence-to-sequence model, and the model used in our work is based on the hard alignment model used by @xcite -these are only two of many possible architectures. variants of other architectures may possess different equivariance properties from both of these models, and may perform well on different tasks. future work could incorporate group equivariance into more architectures and assess their theoretical properties and empirical performance. a key limitation of group-equivariant networks is the need to understand and specify the group to which it is equivariant. this makes it difficult to apply these networks to real world tasks rather than artificial datasets such an scan. future work could investigate ways to identify from data which words should be in a lexical class, or ways to allow group-equivariant networks to deal with open vocabulary problems. some work has been done on learning input and output vocabulary alignments in the context of scan @xcite , so it is possible that this could be used to improve group-equivariant architectures by reducing or eliminating their reliance on lexical classes and groups known a priori. ## conclusion in this work, we proposed and implemented a string-to-string transduction model which combines a group-invariant sum over hard alignments and a group-equivariant output word probability to create a model which is equivariant to the swapping of words in the same lexical class. we applied this model to the scan task, finding that it is successful in allowing the model to generalize compositionally. we show theoretically that our model's structure allows for wider generalization to novel sentences than existing group-equivariant approaches and demonstrate this empirically. we suggest that this is strong motivation to explore group-equivariant variants of other architectures, and to investigate other tasks which may benefit from group-equivariant models, as well as suggesting that theoretical analysis of equivariance properties may be a useful tool in understanding performance differences. hyperparameter details range dimension of g-embedding size of g-embedding layer 5-256 number of filters number of filters used in g-convolution layer 5-256 embedding dimension dimension of embedding layer in alignment model 5-256 hidden size size of lstm layers used in alignment model 5-256 batch size -8 -64