Compositional Generalisation with Structured Reordering and Fertility Layers (2023)

Abstract: Seq2seq models have been shown to struggle with compositional generalisation, i.e. generalising to new and potentially more complex structures than seen during training. Taking inspiration from grammar-based models that excel at compositional generalisation, we present a flexible end-to-end differentiable neural model that composes two structural operations: a fertility step, which we introduce in this work, and a reordering step based on previous work (Wang et al., 2021). To ensure differentiability, we use the expected value of each step, which we compute using dynamic programming. Our model outperforms seq2seq models by a wide margin on challenging compositional splits of realistic semantic parsing tasks that require generalisation to longer examples. It also compares favourably to other models targeting compositional generalisation.

## introduction many nlp tasks require translating an input object such as a sentence into a structured output object such as a semantic parse. recently, these tasks have been approached with seq2seq models with great success. however, seq2seq models also have been shown to struggle out-of-distribution on compositional generalisation @xcite @xcite , i.e. the model fails on examples that contain unseen compositions or deeper recursion of phenomena that it handles correctly in isolation. consider the example in fig. 1 . arguably, any model that produces the given semantic parse from the input in a generalisable way has to capture the correspondence between fragments of the input and fragments of the output, at least implicitly. this is challenging because of structural mismatches 1 https://github.com/namednil/f-then-r between input and output. for example, the fragment contributed by "flights" is discontinuous and intertwined with the rest of the semantic parse. in contrast to seq2seq models, grammar-based models such as synchronous context-free grammars (scfgs) @xcite explicitly capture the compositional process behind the data and therefore perform very well in compositional generalisation setups. they can also model common structural mismatches like the one shown in the example. however, grammar-based models are rigid and brittle and thus do not scale well. in this work, we take inspiration from grammarbased models and present an end-to-end differentiable neural model that is both flexible and generalises well compositionally. our model consists of two structural layers: a phrase reordering layer originally introduced by @xcite and a fertility layer, new in this work, which creates zero or more copies of the representation of any input token. we show how to compose these layers to achieve strong generalisation. we use a simple decoder and essentially translate each token after the fertility and reordering layers independently into one output token. we found this to lead to better generalisation than using an lstmbased decoder. the simple decoder also makes it easy to integrate grammar constraints to ensure well-formed outputs, e.g. in semantic parsing. most seq2seq models tend to predict the end of the sequence too early on instances that are longer than seen in training @xcite . our model overcomes this by explicitly predicting the length of the output sequence as a sum of fertilities. we first demonstrate the expressive capacity and inductive bias of our model on synthetic data. we then evaluate on three english semantic parsing datasets (geoquery, atis, okapi) and a style transfer task @xcite . we clearly outperform seq2seq models both with and without pretraining in structural generalisation setups, particularly when the model has to generalise to longer examples. our model also compares favourably with existing approaches that target structural generalisation, and we obtain state-of-the-art results on the structural style transfer tasks. to summarise, our main contributions are: ## related work fertility the concept of fertility was introduced by @xcite for statistical machine translation to capture that a word in one language is often consistently translated to a certain number of words in another language. @xcite and @xcite incorporate fertility into the attention mechanism of seq2seq models. @xcite ; @xcite use heuristic supervision for training their fertility models. in contrast to prior work, we learn an explicit fertility component jointly with the rest of our model. ## overview of the approach in this section, we give a general overview of our approach and defer the details to sections 5 and 6. conceptually, we want to model the transduction from input x of length n into output y of length l as the composition of two edit operations. first, we apply a fertility step, in which we decide for each token what its fertility is, i.e. how many copies we make of it. assigning fertility of 0 corresponds to deleting the token. this step yields an intermediate sequence of tokens. we then reorder them using permutation trees (see section 3.2). in the last step, we individually translate these tokens into the output tokens. fig. 1 shows an example where the fertility step and reordering apply to vector representations of tokens. the fertility step and the reordering can be represented as boolean matrices @xmath0, respectively. these matrices denote alignments between the sequences before and after the operation. for example, f i,@xmath1, i.e. j is one of the copies of i. with this conceptualisation, we would ideally use the following probabilistic model p (y|x): at training time, the true fertility values are unknown but we observe the length l of y, so we condition on it: computing the marginal likelihood and the gradients is intractable. instead of computing the likelihood exactly, one could sample and use a score function estimator @xcite but the resulting gradient estimates have high variance. instead, we use structured attention as discussed in section 3.1 and 'push' the expectations inside the model: and r now represent 'soft', differentiable versions of fertility and reordering. they approach their discrete counterparts as p (f |x, l) and p (r| f , x) become peakier, which tends to happen over the course of training. we can view ( f r) i,@xmath2,k rk,j as a probability of aligning i to j in the composition of the operations. a tendency to memorise larger chunks of the output might contribute to poor compositional generalisation @xcite . in order to avoid this, we use a simple decoder that generates each output token independently. a first attempt might look like this: ## fertility and alignment in this section we describe how to compute @xmath3,l) f , i.e. the expected alignment that results from the fertility step given that the intermediate token sequence will have length l. in the previous section, we looked at the fertility step mostly from the perspective of an alignment between the input tokens and the intermediate tokens. however, the fertility step is parameterised as assigning a fertility value f @xmath4, . . . , @xmath5. we now show how to compute f efficiently as a function of the distribution over fertility values p (f |x). figure 2 : efficiently computing the marginal probability that the u-th copy of i is at position j. we partition the intermediate sequence into four parts, and marginalise over all possible ways of choosing v. we denote the alignment that follows from f as f (f ), i.e. f (f ) i,j,@xmath6. f can be expressed as: note that conditioning on the output length l in eq. ( 5 ) introduces inter-dependencies between the values. in order to compute fi,j,u , we need to marginalise over all possible assignments to the fertility vector f which satisfy f (f ) i,j,@xmath7. we do this with a dynamic programming algorithm that is similar to the forward/backward algorithm for hmms @xcite . computing marginals we characterise the situations where f (f ) i,j,@xmath8. 2 ). first, in order for intermediate token j to be the u-th copy of i, there should be j -u intermediate tokens generated by input tokens preceding i: second, the fertility f i has to be at least u. we capture this by requiring with @xmath9. finally, the input tokens following i have to contribute the remaining ljv intermediate tokens: we then compute the probability of creating a sequence of length l, where the j-th intermediate token is the u-th copy of i, by marginalising over v (dropping x for readability): we handle the boundary cases with @xmath10, @xmath11 in order to compute eq. ( 9 ), we also compute 'forward' probabilities p (f 0 + . . . + f @xmath12. . . + f n+1 = h) for all i, h. this can be done recursively: fi,j,u was defined in eq. ( 5 ) by conditioning on the length l. we provide pseudo-code for all steps in appendix a. runtime the runtime of the fertility step is dominated by computing eq. ( 9 ). note that v has a range of at most d, thus, we can compute the probabilities for all i, j, u in o(n • l • d 2 ) time. eq. ( 9 ) can be computed in parallel for each i, j, u. ## composing fertility and reordering we will now describe in detail how p (f |x) and p (r|x, f ) are defined and how the fertility and reordering layers are composed. ## conclusion we presented a flexible end-to-end differentiable model for structured nlp tasks. it predicts the output sequence from the input by composing a fertility layer with a reordering layer. the evaluation shows that our model performs well in structural generalisation setups, in particular when the model has to generalise to longer examples than seen during training. in contrast, the accuracy of standard seq2seq models drops sharply on longer examples. the efficient fertility layer introduced in this work may be useful in other scenarios as well, e.g. in non-autoregressive machine translation, or for (unsupervised) sentence compression when the fertility is restricted to 0 or 1. future work could also investigate other structured layers and the best ways of composing and training them.