How can datasets be designed to assess the compositional generalization ability of large language models?
Compositional Generalization has attracted increasing attention with dedicated datasets (Lake
and Baroni, 2018; Keysers et al., 2020a; Kim and
Linzen, 2020; Li et al., 2021; Shaw et al., 2021;
Dankers et al., 2022). One line of research considers dedicated model architectures (Chen et al.,
2020b; Gordon et al., 2020; Kim, 2021), which perform well on small scaled data but can face difficulties scaling to large or practical data. For example,
Chen et al. (2020b) propose a differentiable neural network to operate a symbolic stack machine.
Another line of research enhances the compositionality of standard architectures (i.e., Transformer) by
introducing new modules (Bergen et al., 2021; Yin et al., 2022; Zheng and Lapata, 2022). However,
significant architecture changes can bring about extra training cost or decoding latency. For example,
Edge Transformer (Bergen et al., 2021) uses vectorbased attention weights, and Dangle Transformer
(Zheng and Lapata, 2022) re-encodes source representations at each decoding step, which increase
model complexity to O(n
3
). Proto-Transformer
(Yin et al., 2022) uses an additional attention module to incorporate prototype vectors obtained by
clustering algorithms (e.g., K-Means). Different
from them, we improve Transformer from the perspective of regularization training without any architecture changes.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Humans can understand and produce new utterances effortlessly, thanks to their compositional skills. Once a person learns the meaning of a new verb “dax,” he or she can immediately understand the meaning of “dax twice” or “sing and dax.” In this paper, we introduce the SCAN domain, consisting of a set of simple compositional navigation commands paired with the corresponding action sequences. We then test the zero-shot generalization capabilities of a variety of recurrent neural networks (RNNs) trained on SCAN with sequence-to-sequence methods. We ﬁnd that RNNs can make successful zero-shot generalizations when the differences between training and test commands are small, so that they can apply “mix-and-match” strategies to solve the task. However, when generalization requires systematic compositional skills (as in the “dax” example above), RNNs fail spectacularly. We conclude with a proof-of-concept experiment in neural machine translation, suggesting that lack of system-aticity might be partially responsible for neural networks’ notorious training data thirst.
[{"first":"Brenden","last":"Lake","middle":["M."]},{"first":"Marco","last":"Baroni","middle":[]}]
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Natural language is characterized by compositionality: the meaning of a complex expression is constructed from the meanings of its constituent parts. To facilitate the evaluation of the compositional abilities of language processing architectures, we introduce COGS, a semantic parsing dataset based on a fragment of English. The evaluation portion of COGS contains multiple systematic gaps that can only be addressed by compositional generalization; these include new combinations of familiar syntactic structures, or new combinations of familiar words and familiar structures. In experiments with Transformers and LSTMs, we found that in-distribution accuracy on the COGS test set was near-perfect (96--99%), but generalization accuracy was substantially lower (16--35%) and showed high sensitivity to random seed ($\pm$6--8%). These findings indicate that contemporary standard NLP models are limited in their compositional generalization capacity, and position COGS as a good way to measure progress.
[{"first":"Najoung","last":"Kim","middle":[]},{"first":"Tal","last":"Linzen","middle":[]}]
On Compositional Generalization of Neural Machine Translation
Modern neural machine translation (NMT) models have achieved competitive performance in standard benchmarks such as WMT. However, there still exist significant issues such as robustness, domain generalization, etc. In this paper, we study NMT models from the perspective of compositional generalization by building a benchmark dataset, CoGnition, consisting of 216k clean and consistent sentence pairs. We quantitatively analyze effects of various factors using compound translation error rate, then demonstrate that the NMT model fails badly on compositional generalization, although it performs remarkably well under traditional metrics.
[{"first":"Yafu","last":"Li","middle":[]},{"first":"Yongjing","last":"Yin","middle":[]},{"first":"Yulong","last":"Chen","middle":[]},{"first":"Yue","last":"Zhang","middle":[]}]
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
State-of-the-art machine learning methods exhibit limited compositional generalization. At the same time, there is a lack of realistic benchmarks that comprehensively measure this ability, which makes it challenging to find and evaluate improvements. We introduce a novel method to systematically construct such benchmarks by maximizing compound divergence while guaranteeing a small atom divergence between train and test sets, and we quantitatively compare this method to other approaches for creating compositional generalization benchmarks. We present a large and realistic natural language question answering dataset that is constructed according to this method, and we use it to analyze the compositional generalization ability of three machine learning architectures. We find that they fail to generalize compositionally and that there is a surprisingly strong negative correlation between compound divergence and accuracy. We also demonstrate how our method can be used to create new compositionality benchmarks on top of the existing SCAN dataset, which confirms these findings.
[{"first":"Daniel","last":"Keysers","middle":[]},{"first":"Nathanael","last":"Scharli","middle":[]},{"first":"Nathan","last":"Scales","middle":[]},{"first":"Hylke","last":"Buisman","middle":[]},{"first":"Daniel","last":"Furrer","middle":[]},{"first":"Sergii","last":"Kashubin","middle":[]},{"first":"Nikola","last":"Momchev","middle":[]},{"first":"Danila","last":"Sinopalnikov","middle":[]},{"first":"Lukasz","last":"Stafiniak","middle":[]},{"first":"Tibor","last":"Tihon","middle":[]},{"first":"Dmitry","last":"Tsarkov","middle":[]},{"first":"Xiao","last":"Wang","middle":[]},{"first":"Marc","last":"Zee","middle":["van"]},{"first":"Olivier","last":"Bousquet","middle":[]}]
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Sequence-to-sequence models excel at handling natural language variation, but have been shown to struggle with out-of-distribution compositional generalization. This has motivated new specialized architectures with stronger compositional biases, but most of these approaches have only been evaluated on synthetically-generated datasets, which are not representative of natural language variation. In this work we ask: can we develop a semantic parsing approach that handles both natural language variation and compositional generalization? To better assess this capability, we propose new train and test splits of non-synthetic datasets. We demonstrate that strong existing approaches do not perform well across a broad set of evaluations. We also propose NQG-T5, a hybrid model that combines a high-precision grammar-based approach with a pre-trained sequence-to-sequence model. It outperforms existing approaches across several compositional generalization challenges on non-synthetic data, while also being competitive with the state-of-the-art on standard evaluations. While still far from solving this problem, our study highlights the importance of diverse evaluations and the open challenge of handling both compositional generalization and natural language variation in semantic parsing.
[{"first":"Peter","last":"Shaw","middle":[]},{"first":"Ming-Wei","last":"Chang","middle":[]},{"first":"Panupong","last":"Pasupat","middle":[]},{"first":"Kristina","last":"Toutanova","middle":[]}]
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Obtaining human-like performance in NLP is often argued to require compositional generalisation. Whether neural networks exhibit this ability is usually studied by training models on highly compositional synthetic data. However, compositionality in natural language is much more complex than the rigid, arithmetic-like version such data adheres to, and artificial compositionality tests thus do not allow us to determine how neural models deal with more realistic forms of compositionality. In this work, we re-instantiate three compositionality tests from the literature and reformulate them for neural machine translation (NMT).Our results highlight that: i) unfavourably, models trained on more data are more compositional; ii) models are sometimes less compositional than expected, but sometimes more, exemplifying that different levels of compositionality are required, and models are not always able to modulate between them correctly; iii) some of the non-compositional behaviours are mistakes, whereas others reflect the natural variation in data. Apart from an empirical study, our work is a call to action: we should rethink the evaluation of compositionality in neural networks and develop benchmarks using real data to evaluate compositionality on natural language, where composing meaning is not as straightforward as doing the math.
[{"first":"Verna","last":"Dankers","middle":[]},{"first":"Elia","last":"Bruni","middle":[]},{"first":"Dieuwke","last":"Hupkes","middle":[]}]
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Human language and thought are characterized by systematic compositionality, the algebraic capacity to understand and produce a potentially infinite number of novel combinations from known components (Chomsky, 1957;Montague, 1970). For example, if a person knows the meaning and usage of words such as "twice," "and," and "again," once she learns a new verb such as "to dax" she can immediately understand or produce instructions such as "dax twice and
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In the last few years, neural network research has made astounding progress in practical domains where success depends on generalization. Perhaps most strikingly, end-toend recurrent neural networks currently dominate the stateof-the-art in machine translation (Bojar et al., 2016;Wu et al., 2016). Since the overwhelming majority of sentences or even word sequences in a language only occur once, even in a large corpus (Baroni, 2009), this points to strong generalization abilities. Still, it is commonly observed that neural networks are extremely sample inefficient, requiring very large training sets, which suggests they may lack the same algebraic compositionality that humans exploit, and they might only be sensitive to broad patterns over lots of accumulated statistics (Lake et al., 2017).
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In this paper, we introduce a grounded navigation environment where the learner must translate commands given in a limited form of natural language into a sequence of actions. This problem is naturally framed as a sequence-to-sequence task, and, due to its simplicity, it is ideal to study systematic generalization to novel examples in a controlled setup. We thus use it to test a wide range of modern recurrent network architectures in terms of their compositional abilities. Our results suggest that standard recurrent seq2seq architectures generalize very well when novel examples feature a mixture of constructions that have been observed in training. However, the models are catastrophically affected by systematic differences between training and test sentences, of the sort that would be trivial for an agent equipped with an "algebraic mind" (Marcus, 2003).
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We call our data set SCAN because it is a Simplified version of the CommAI Navigation tasks (Mikolov et al., 2016). 1 For a learner, the goal is to translate commands presented in simplified natural language into a sequence of actions. Since each command is unambiguously associated to a single action sequence, SCAN (unlike the original CommAI tasks) can be straightforwardly treated as a supervised sequenceto-sequence semantic parsing task (Dong & Lapata, 2016;Jia & Liang, 2016;Herzig & Berant, 2017), where the input vocabulary is given by the set of words used in the commands, and the output by the set of actions available to the learner.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Several examples from SCAN are presented in Fig. 1. Formally, SCAN consists of all the commands generated by a phrase-structure grammar (presented in Supplementary) and the corresponding sequence of actions, produced according to a semantic interpretation function (see Supplementary). Intuitively, the SCAN grammar licenses commands denoting primitive actions such as JUMP (denoted by "jump"; Fig. 1), WALK (denoted by "walk") and LTURN (denoted by "turn left"). We will refer to these as primitive commands. 2 It also accepts a set of modifiers and conjunctions that compositionally build expressions referring to action sequences. The "left" and "right" modifiers take commands denoting undirected primitive actions as input and return commands denoting their directed counterparts ("jump left"; Fig. 1). The "opposite" modifier produces an action sequence that turns the agent backward in the specified direction before executing a target action ("jump opposite left"), while "around" makes the agent execute the action at each step while turning around in the specified direction ("jump around right"; Fig. 1). The "twice/thrice" modifiers trigger repetition of the command they take scope over, and "and/after" combine two action sequences. Although the SCAN examples in Fig. 1 focus on the "jump"/JUMP primitive, each instance of JUMP can be replaced with either WALK, RUN, or LOOK to generate yet more commands. Many more combinations are possible as licensed by the grammar. The input vocabulary includes 13 words, the output 6 actions.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
The SCAN grammar, lacking recursion, generates a finite but large set of unambiguous commands (20,910, to be precise). Commands can be decoded compositionally by applying the corresponding interpretation function. This means that, if it discovers the right interpretation function, 1 SCAN available at:
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
https://github.com/ brendenlake/SCAN 2 Introducing the primitive turning actions LTURN and RTURN considerably simplifies the interpretation function, compared to capturing orientation by specifying arguments to the movement actions (e.g., JUMP[L], JUMP[R]). a learner can understand commands it has not seen during training. For example, the learner might have only observed the primitive "jump" command during training, but if it has learned the meaning of "after", "twice" and "around left" from other verbs, it should be able to decode, zero-shot, the complex command: "jump around left after jump twice".
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We approach SCAN through the successful sequence-tosequence (seq2seq) framework, in which two recurrent networks work together to learn a mapping between input sequences and output sequences (e.g., Sutskever et al., 2014). 3 Fig. 2 illustrates the application of the seq2seq approach to a SCAN example. First, a recurrent network encoder receives the input sequence word-by-word, forming a lowdimensional representation of the entire command. Second, the low-dimensional representation is passed to a recurrent network decoder, which then generates the output sequence action-by-action. The decoder's output is compared with the ground truth, and the backpropagation algorithm is used to update the parameters of both the encoder and decoder. Note that although the encoder and decoder share the same network structure (e.g., number of layers and hidden units), they do not otherwise share weights/parameters with each other. More details regarding the encoder-decoder RNN are provided in Supplementary.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Using the seq2seq framework, we tested a range of standard recurrent neural network models from the literature: simple recurrent networks (SRNs; Elman, 1990), long short-term memory networks (LSTMs; Hochreiter & Schmidhuber, 1997), and gated recurrent units (GRUs; Chung et al., 2014). Recurrent networks with attention have become increasingly popular in the last few years, and thus we also tested each network with and without an attentional mechanism, using the model from Bahdanau et al. (2015) (see Supplementary for more details). Finally, to make the evaluations as systematic as possible, a large-scale hyperparameter search was conducted that varied the number of layers (1 or 2), the number of hidden units per layer (25, 50, 100, 200, or 400), and the amount of dropout (0, 0.1, 0.5; applied to recurrent layers and word embeddings). Varying these hyperparameters leads to 180 different network architectures, all of which were run on each experiment and replicated 5 times each with different random initializations. 4
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In reporting the results, we focus on the overall-best architecture as determined by the extensive hyperparameter search. The winning architecture was a 2-layer LSTM with  Figure 2. The seq2seq framework is applied to SCAN. The symbols <EOS> and <SOS> denote end-of-sentence and start-ofsentence, respectively. The encoder (left) ends with the first <EOS> symbol, and the decoder (right) begins with <SOS>.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
200 hidden units per layer, no attention, and dropout applied at the 0.5 level. Although the detailed analyses to follow focus on this particular model, the top-performing architecture for each experiment individually is also reported and analyzed.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Networks were trained with the following specifications. Training consisted of 100,000 trials, each presenting an input/output sequence and then updating the networks weights. 5 The ADAM optimization algorithm was used with default parameters, including a learning rate of 0.001 (Kingma & Welling, 2014). Gradients with a norm larger than 5.0 were clipped. Finally, the decoder requires the previous step's output as the next step's input, which was computed in two different ways. During training, for half the time, the network's self-produced outputs were passed back to the next step, and for the other half of the time, the groundtruth outputs were passed back to the next step (teacher forcing; Williams & Zipser, 1989). The networks were implemented in PyTorch and based on a standard seq2seq implementation. 6
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Training accuracy was above 99.5% for the overall-best network in each of the key experiments, and it was at least 95% for the top-performers in each experiment specifically. 5 Note that, in all experiments, the number of distinct training commands is well below 100k: we randomly sampled them with replacement to reach the target size 6 The code we used is publicly available at the link: http://pytorch.org/tutorials/intermediate/ seq2seq_translation_tutorial.html
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In each of the following experiments, the recurrent networks are trained on a large set of commands from the SCAN tasks to establish background knowledge as outlined above. After training, the networks are then evaluated on new commands designed to test generalization beyond the background set in systematic, compositional ways. In evaluating these new commands, the networks must make zero-shot generalizations and produce the appropriate action sequence based solely on extrapolation from the background training.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In this experiment, the SCAN tasks were randomly split into a training set (80%) and a test set (20%). The training set provides broad coverage of the task space, and the test set examines how networks can decompose and recombine commands from the training set. For instance, the network is asked to perform the new command, "jump opposite right after walk around right thrice," as a zero-shot generalization in the test set. Although the conjunction as a whole is novel, the parts are not: The training set features many examples of the parts in other contexts, e.g., "jump opposite right after turn opposite right" and "jump right twice after walk around right thrice" (both bold sub-strings appear 83 times in the training set). To succeed, the network needs to generalize by recombining pieces of existing commands to interpret new ones.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Overall, the networks were highly successful at generalization. The top-performing network for this experiment achieved 99.8% correct on the test set (accuracy values here and below are averaged over the five training runs). The topperforming architecture was a LSTM with no attention, 2 layers of 200 hidden units, and no dropout. The best-overall network achieved 99.7% correct. Interestingly, not every architecture was successful: Classic SRNs performed very poorly, and the best SRN achieved less than 1.5% correct at test time (performance on the training set was equally low). However, attention-augmented SRNs learned the commands much better, achieving 59.7% correct on average for the test set (with a range between 18.4% and 94.0% across SRN 1% 2% 4% 8% 16% 32% 64% Percent of commands used for training 0 20 40 60 80 100 Accuracy on new commands (%) Figure 3. Zero-shot generalization after training on a random subset of the SCAN tasks. The overall-best network was trained on varying proportions of the set of distinct tasks (x-axis) and generalization was measured on new tasks (y-axis). Each bar shows the mean over 5 training runs with corresponding ±1 SEM. architectures). For LSTMs and GRUs, attention was instead not essential. Since the SCAN commands are never longer than 9 words, attention is probably superfluous, at least in this simple setup, for gated architectures that generally exhibit a more robust long-distance behaviour than SRNs.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
As indicated above, the main split was quite generous, providing 80% of the commands at training time for a total of over 16,700 distinct examples (with strong combinatorial coverage). We next re-trained the best-overall network with varying numbers of distinct examples (the actual number of training presentations was kept constant at 100K). The results are shown in Fig. 3. With 1% of the commands shown during training (about 210 examples), the network performs poorly at about 5% correct. With 2% coverage, performance improves to about 54% correct on the test set. By 4% coverage, performance is about 93% correct. Our results show that not only can networks generalize to random subsets of the tasks, they can do so from relatively sparse coverage of the compositional command space. This is well in line with the success of seq2seq architectures in machine translation, where most test sentences are likely never encountered in training. Still, even with this sparser coverage, differences between training and test instances are not dramatic. Let us for example consider the set of all commands without a conjunction (e.g., "walk around thrice", "run", "jump opposite left twice"). All the commands of this sort that occur in the test set of the 2% training coverage split (either as components of a conjunction or by themselves) also occur in the corresponding training set, with an average of 8 occurrences. Even for the 1% split, there is only one conjunction-less test command that does not also occur in the training split, and the frequency of occurrence of such commands in the training set is at a non-negligible average value of 4 times.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We study next a more systematic form of generalization, where models must bootstrap to commands requiring longer action sequences than those seen in training. 7 Now the training set contains all 16,990 commands requiring sequences of up to 22 actions, whereas the test set includes all remaining commands (3,920, requiring action sequences of lengths from 24 to 48). Under this split, for example, at test time the network must execute the command "jump around left twice and walk opposite right thrice", requiring a sequence of 25 actions. Although all the elements used in the command have been observed during training, the network has never been asked to produce a sequence of this length, nor it has ever seen an "around * twice" command conjoined with an "opposite * thrice" command (although it did observe both components conjoined with others). Thus, it must productively generalize familiar verbs, modifiers and conjunctions to generate longer action sequences. This is a fair task for a system that is correctly translating the input commands. If you know how to "walk around," how to "jump," and the function of the "and" conjunction, you will be immediately able to "walk around and jump," even if you have never performed an action sequence of that length.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
This test turns out to be very challenging for all models. The best result (20.8% on average, again over 5 runs) is achieved by a GRU with attention, one 50-dimensional hidden layer, and dropout 0.5. Interestingly, this is a model with considerably less capacity than the best for the random-split setup, but it uses attention, which might help, to a limited degree, to generalize to longer action sequences. The overall-best model achieves 13.8% accuracy. Fig. 4 (top) shows partial success is almost entirely explained by generalization to the shortest action sequence lengths in the test set. Although we might not expect even humans to be able to generalize to very long action sequences, the sharp drop between extrapolating to 25 and 26 actions is striking. The bottom panel of Fig. 4 shows accuracy in the test set organized by command length (in word tokens). The model only gets right some of the longest commands (8 or 9 tokens). In the training set, the longest ac- 7 We focus on action sequence length rather than command length since the former exhibits more variance (1-48 vs. 1-9). The longest commands (9 words) are given by the conjunction of two directed primitives both modified twice, e.g.: "jump around left twice and run opposite right thrice." On the other hand, a relatively short command such as "jump around left thrice" demands 24 actions. tion sequences (≥20) are invariably associated to commands containing 8 or 9 tokens. Thus, the model is correctly generalizing only in those cases that are most similar to training instances.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Finally, we performed two additional analyses to better understand the source of the errors. First, we examined the greedy decoder for search-related errors. We confirmed that, for almost every error, the network preferred its selfgenerated output sequence to the target output sequence (as measured by log-likelihood). Thus, the errors were not due to search failures in the decoder. 8 Second, we studied whether the difficulty with long sequences can be mitigated if the proper length was provided by an oracle at evaluation time. 9 If this difficulty is a relatively straightforward issue of the decoder terminating too early, then this should provide an (unrealistic) fix. If this difficulty is symptomatic of deeper problems with generalization, then this change will have only a small effect. With the oracle, the overallbest network performance improved from 13.8% to 23.6% correct, which was notable but insufficient to master the long sequences. The top-performing model showed a more substantial improvement (20.8% to 60.2%). Although improved, the networks were far from perfect and still exhibited difficulties with long sequences of output actions (again, even for the top model, there was a strong effect of action sequence length, with average accuracy ranging from 95.76% for commands requiring 24 actions to 22.8% for commands requiring 48 actions).
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Our next test is closest to the "dax" thought experiment presented in the introduction. In the training phase, the model is exposed to the primitive command only denoting a certain basic action (e.g., "jump"). The model is also exposed to all primitive and composed commands for all other actions (e.g., "run", "run twice", "walk", "walk opposite left and run twice", etc.). At test time, the model has to execute all composed commands for the action that it only saw in the primitive context (e.g., "jump twice", "jump opposite left and run twice", etc.). According to the classic thought experiments of Fodor and colleagues, this should be easy: if you know the meaning of "run", "jump" and "run twice", you should also understand what "jump twice" means.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We run two variants of the experiment generalizing from "turn left" and "jump", respectively. Since "turn right" is distributionally identical to "turn left" (in the sense that it occurs in exactly the same composed commands) and "walk", "run" and "look" are distributionally identical to "jump", it is redundant to test all commands. Moreover, to ensure the networks were highly familiar with the target primitive command ("jump" or "turn left"), the latter was over-represented in training such that roughly 10% of all training presentations were of the command. 10 We obtain strikingly different results for "turn left" and "jump". For "turn left", many models generalize very well to composed commands. The best performance is achieved by a GRU network with attention, one layer with 100 hidden units, and dropout of 0.1 (90.3% accuracy). The overall-9 Any attempt from the decoder to terminate the action sequence with an <EOS> was ignored (and the second strongest action was chosen) until a sequence with proper length was produced.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
10 Without over-sampling, performance was consistently worse than what we report. best model achieved 90.0% accuracy. On the other hand, for "jump," models are almost completely incapable to generalize to composed commands. The best performance was 1.2% accuracy (LSTM, attention, one layer, 100 hidden units, dropout 0.1). The overall-best model reached 0.08% accuracy. As in Experiment 2, the errors were not due to search failures in the decoder.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In the case of "turn left", although models are only exposed to the primitive command during training, they will see the action it denotes (LTURN) many times, as it is used to accomplish many directed actions. For example, a training item is: "walk left and jump left", with ground-truth interpretation: LTURN WALK LTURN JUMP. Apparently, seeing action sequences containing LTURN suffices for the model to understand composed commands with "turn left", probably because the model receives direct evidence about how LTURN is used in context. On the other hand, the action denoted by "jump" (JUMP) only occurs with this primitive command in training, and the model does not generalize from this minimal context to new composed ones.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We now take a closer look at the results, focusing on the median-performance run of the overall-best model (as the most representative run of this model). We observe that even in the successful "turn left" case model errors are surprising. One would expect such errors to be randomly distributed, or perhaps to pertain to the longest commands or action sequences. Instead, all 45 errors made by the model are conjunctions where one of the components is simple "turn left" (22 cases) or "turn left thrice" (23 cases). This is particularly striking because the network produced the correct mapping for "turn left" during training, as well as for "turn left thrice" at test time, and it gets many more conjunctions right (ironically, including "turn left thrice and turn left", "turn left thrice after turn left" etc.). We conclude that, even when the network has apparently learned systematic composition almost perfectly, it got at it in a very counter-intuitive way. It's hard to conceive of someone who understood the meaning of "turn left", and "jump right and turn left twice" (which the network gets right), but not that of "jump right and turn left" (one of the examples the network missed). In the "jump" experiment, the network could only correctly decode two composite cases, both starting with the execution of primitive "jump", conjoined with a different action: "jump and run opposite right", "jump and walk around left thrice".
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
It is instructive to look at the representations that the network induced for various commands in the latter experiment. Table 1 reports the 5 nearest neighbours for a sample of commands. Command similarity is measured by the cosine between the final encoder hidden state vectors, and computed with respect to all commands present in the training set. "Run" is provided as an example primitive command for which the model has been exposed to the full composed paradigm in training. As one would expect, "run" is close to the other primitive commands ("look", "walk"), as well as to short conjoined commands that contain primitive "run" as one of the conjuncts (we observe a similar pattern for the non-degenerate "jump" representation induced in Experiment 1). Instead, since "jump" had a different training distribution than the other primitive commands, the model does not capture its similarity to them, as shown by the very low cosines of its nearest commands. Since it fails to establish a link to other basic commands, the model does not generalize modifier application from them to "jump". Although "run twice" is similar to (conjunctions of) other primitive tasks composed with "twice", "jump twice" is isolated in representational space, and its (far) nearest neighbours look arbitrary.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We tested here systematicity in its purest form: the model was only exposed to "jump" in isolation, and asked to bootstrap to its compositional paradigm based on the behaviour of other primitive commands such as "walk", "look" and "run". Although we suspect humans would not have problems with this setup, it arguably is too opaque for a computational model, which could lack evidence for "jumping" being the same sort of action as "walking". Suppose we give the network some evidence that "jumping" composes like "walking" by showing a few composed "jump" command during training. Is the network then able to generalize to the full composed paradigm?
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
This question is answered in Figure 5. We present here results for the best model in the "jump"-generalization task, which was noticeably better in the present setup than the overall-best model. Again, the new primitive command (and its compositions) were over-sampled during training to make up 10% of all presentations. Here, even when shown 8 different composed commands with "jump" at training time, the network only weakly generalizes to other composed commands (38.3% correct). Significant generalization (still far from systematic) shows up when the training set contains 16 and especially 32 distinct composed commands (77.8% and 88.4%, respectively). We conclude that the network is not failing to generalize simply because, in the original setup, it had little evidence that "jump" should behave like the other commands. On the other hand, the runs with more composed examples confirm that, as we found in Experiment 1, the network does display powerful generalization abilities. Simply, they do not conform to the "all-or-nothing" rule-based behaviour we would expect from a systematically compositional device-and, as a consequence, they require more positive examples to emerge. Accuracy on new commands (%) Figure 5. Zero-shot generalization after adding the primitive "jump" and some compositional "jump" commands. The model that performed best in generalizing from primitive "jump" only was retrained with different numbers of composed "jump" commands (x-axis) in the training set, and generalization was measured on new composed "jump" commands (y-axis). Each bar shows the mean over 5 runs with varying training commands along with the corresponding ±1 SEM.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Our final experiment is a proof-of-concept that our findings are more broadly applicable; that is, the limitations of recurrent networks with regards to systematic compositionality extend beyond SCAN to other sequence-to-sequence problems such as machine translation. First, we trained our standard seq2seq code on short (≤ 9 words) English-French sentence pairs that begin with English phrases such as "I am," "he is," "they are," and their contractions (randomly split with 10,000 for training and 1180 for testing). 6 An informal hyperparameter search led us to pick a LSTM with attention, 2 layers of 400 hidden units, and 0.05 dropout.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
With these hyperparameters and the same training procedure used for the SCAN tasks (Section 3), the network reached a respectable 28.6 BLEU test score after 100,000 steps.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Second, to examine compositionality with the introduction of a new word, we trained a fresh network after adding 1,000 repetitions of the sentence "I am daxy" (fr. "je suis daxiste") to the training data (the BLEU score on the original test set dropped less than 1 point). 11 We tested this network by embedding "daxy" into the following constructions: "you are daxy" ("tu es daxiste"), "he is daxy" ("il est daxiste"), "I am not daxy" ("je ne suis pas daxiste"), "you are not daxy" ("tu n'es pas daxiste"), "he is not daxy" ("il n'est pas daxiste"), "I am very daxy" ("je suis très daxiste"), "you are very daxy" ("tu es très daxiste"), "he is very daxy" ("il est très daxiste"). During training, the model saw these constructions occurring with 22 distinct predicates on average (limiting the counts to perfect matches, excluding, e.g., "you are not very X"). Still, the model could only get one of the 8 translations right (that of "he is daxy"). For comparison, for the adjective "tired", which occurred in 80 different constructions in the training corpus, our network had 8/8 accuracy when testing on the same constructions as for "daxy" (only one of which also occurred with "tired" in the training set). Although this is a small-scale machine translation problem, our preliminary result suggests that models will similarly struggle with systematic compositionality in larger data sets, when adding a new word to their vocabulary, in ways that people clearly do not.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
In the thirty years since the inception of the systematicity debate, many have tested the ability of neural networks to solve tasks requiring compositional generalization, with mixed results (e.g., Christiansen & Chater, 1994;Marcus, 1998;Phillips, 1998;Chang, 2002;van der Velde et al., 2004;Botvinick & Plaut, 2006;Wong & Wang, 2007;Bowers et al., 2009;Botvinick & Plaut, 2009;Brakel & Frank, 2009;Frank et al., 2009;Frank, 2014;Bowman et al., 2016). However, to the best of our knowledge, ours is the first study testing systematicity in modern seq2seq models, and our results confirm the mixed picture. On the one hand, Experiment 1 and the "turn left" results in Experiment 3 show how standard recurrent models can reach very high zeroshot accuracy from relatively few training examples. We would like to stress that this is an important positive result, showing in controlled experiments that seq2seq models can make powerful zero-shot generalizations. Indeed, an interesting direction for future work is to understand what are, precisely, the generalization mechanisms that subtend the networks' success in these experiments. After all, human language does have plenty of generalization patterns that are not easily accounted for by algebraic compositionality (see, e.g., Goldberg, 2005).
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
On the other hand, the same networks fail spectacularly when the link between training and testing data is dependent on the ability to extract systematic rules. This can be seen as a trivial confirmation of the basic principle of statistical machine learning that your training and test data should come from the same distribution. But our results also point to an important difference in how humans and current seq2seq models generalize, since there is no doubt that human learners can generalize to unseen data when such data are governed by rules that they have learned before. Importantly, the training data of experiments 2 and 3 provide enough evidence to learn composition rules affording the correct generalizations. In Experiment 2, the training data contain examples of all modifiers and connectives that are needed at test time for producing longer action sequences. In Experiment 3, the usage of modifiers and connectives is illustrated at training time by their application to many combinations of different primitive commands, and, at test time, the network should apply them to a new command it encountered in isolation during training.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We thus believe that the fundamental component that current models are missing is the ability to extract systematic rules from the training data. A model that can abstract away from surface statistical patterns and operate in "rule space" should extract rules such as: translate(x and y) = translate(x) translate(y); translate(x twice) = translate(x) translate(x). Then, if the meaning of a new command (translate("jump")) is learned at training time, and acts as a variable that rules can be applied to, no further learning is needed at test time. When represented in this more abstract way, the training and test distributions are quite similar, even if they differ in terms of shallower statistics such as word frequency.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
How can we encourage seq2seq models to extract rules from data rather than exploiting shallower pattern recognition mechanisms? We think there are several, non-mutually exclusive avenues to be explored.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
First, in a "learning-to-learn" approach (Thrun & Pratt, 1997;Risi et al., 2009;Finn et al., 2017, a.o.), a network can be exposed to a number of different learning environments regulated by similar rules. An objective function requiring successful generalization to new environments might encourage learners to discover the shared general rules.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Another promising approach is to add more structure to the neural networks. Taking inspiration from recent neural program induction and modular network models (e.g., Reed & de Freitas, 2016;Hu et al., 2017;Johnson et al., 2017), we could endow RNNs with a set of manually-encoded or (ideally) learned functions for interpreting individual modifiers, connectives, and primitives. The job of the RNN would be to learn how to apply and compose these functions as appropriate for interpreting a command. Similarly, differentiable stacks, tapes, or random-access memory (e.g., Joulin & Mikolov, 2015;Graves et al., 2016) could equip seq2seq models with quasi-discrete memory structures, enabling separate storage of variables, which in turn might encourage abstract rule learning (see Feng et al., 2017, for a memory-augmented seq2seq model).
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Other solutions, such as ad-hoc copying mechanisms or special ways to initialize the embeddings of novel words, might help to solve the SCAN tasks specifically. But they are unlikely to help with more general seq2seq problems. It remains to be seen, of course, if any of our proposed approaches offer a truly general solution. Nonetheless, we see all of the suggestions as directions worth pursuing, perhaps simultaneously and in complementary ways, with the goal of achieving human-like systematicity on SCAN and beyond.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
Given the astounding successes of seq2seq models in challenging tasks such as machine translation, one might argue that failure to generalize by systematic composition indicates that neural networks are poor models of some aspects of human cognition, but it is of little practical import. However, systematicity is an extremely efficient way to generalize. Once a person learns the new English adjective "daxy", he or she can immediately produce and understand an infinity of sentences containing it. The SCAN experiments and a proof-of-concept machine translation experiment (Experiment 4) suggest that this ability is still beyond the grasp of state-of-the-art neural networks, likely contributing to their striking need for very large training sets. These results give us hope that neural networks capable of systematic compositionality could greatly benefit machine translation, language modeling, and other applications.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
The phrase-structure grammar generating all SCAN commands is presented in Figure 6. The corresponding interpretation functions is in Figure 7.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
We describe the encoder-decoder framework, borrowing from the description in Bahdanau et al. (2015). The encoder receives a natural language command as a sequence of T words. The words are transformed into a sequence of vectors, {w 1 , . . . , w T }, which are learned embeddings with the same number of dimensions as the hidden layer. A recurrent neural network (RNN) processes each word
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
where h t is the encoder hidden state. The final hidden state h T (which may include multiple layers for multilayer RNNs) is passed to the RNN decoder as hidden state g 0 (see seq2seq diagram in the main article). Then, the RNN decoder must generate a sequence of output actions a 1 , . . . , a R . To do so, it computes
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
where g t is the decoder hidden state and a t−1 is the (embedded) output action from the previous time step. Last, the hidden state g t is mapped to a softmax to select the next action a t from all possible actions.
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
For the encoder-decoder with attention, the encoder is identical to the one described above. Unlike the standard decoder that can only see h T , the attention decoder can access all of the encoder hidden states, h 1 , . . . , h T (in this case, only the last layer if multi-layer). At each step i, a context vector c i is computed as a weighted sum of the encoder hidden states
Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks
The weights α it are computed using a softmax function where e it = v a tanh(W a g i−1 + U a h t ) is an alignment model that computes the similarity between the previous decoder hidden state g i−1 and an encoder hidden state h t (for the other variables, v a , W a , and U a are learnable parameters) (Bahdanau et al., 2015). This context vector c i is then passed as input to the decoder RNN at each step with the function g i = f D (g i−1 , a i−1 , c i ), which also starts with hidden state g 0 = h T , as in the standard decoder. Last, the hidden state g i is concatenated with c i and mapped to a softmax to select new action a i . . Symbols x and u denote variables, the latter limited to words in the set {walk, look, run, jump}. The linear order of actions denotes their temporal sequence.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Humans can produce and understand linguistic expressions that they have not encountered before, by systematically combining atomic building blocks (Montague, 1974). For instance, a speaker that knows the meaning of John loves Mary is necessarily able to understand Mary loves John, even if the speaker has not heard or uttered this sentence before (Fodor and Pylyshyn, 1988). The discipline of formal semantics concerns itself with characterizing these building blocks, or "primitives", and the ways in which they combine to construct the meaning of a complex expression (e.g., Figure 1a).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
To assess the abilities of computational models of language to generalize compositionally, we propose COGS, a COmpositional Generalization Challenge based on Semantic Interpretation, in (a) (b) Figure 1: (a) The meaning of a sentence (right) is compositionally built up from the meanings of its parts, in accordance with its structure (left). (b) Interpreting a familiar word in a structure it has not appeared in before. In colors: expressions providing the primitive meanings; in bold: expressions providing evidence that definite NPs may appear in both argument positions of a transitive verb. [[x]] denotes the meaning of x.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
which a model of language is expected to construct a semantic representation of a given English sentence (semantic parsing). The key component of this challenge is that the training and evaluation sets systematically differ in their properties, such that success on the evaluation set requires out-ofdistribution generalization. Of the many possible ways that a model could systematically fill such gaps, we expect it to do so in a way that is consistent with the compositional principles that guide human linguistic generalization. Figure 1b illustrates how the meaning of the unseen expression The boy loves the hedgehog could be compositionally inferred from known parts. In this case, the noun phrase (NP) the hedgehog, which has only been observed as a subject, needs to be interpreted in the direct object position. The generalizations tested by COGS, described in detail in Section 3, in-clude interpreting novel combinations of primitives and grammatical roles, interpreting novel combinations of modified phrases and grammatical roles, generalizing phrase nesting to unseen depths, verb argument structure alternation, and sensitivity to verb class.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Rule-based semantic parsing systems such as Boxer (Bos, 2008) are able to generalize compositionally by design. By contrast, this ability does not constitute a part of the design of the neural network models of language that are standard in NLP; it could only arise in such models through learning, inductive biases, or a combination of the two. To test whether standard NLP models are equipped with the ability to generalize compositionally, we used COGS to evaluate three architectures: Transformer, Bidirectional LSTM, and Unidirectional LSTM (Section 5). We found that the out-of-distribution generalization set was significantly more challenging (16-35% mean accuracy) than an in-distribution test set (96-99% mean accuracy). Furthermore, generalization accuracy varied greatly across runs of the same architecture that differed only in random seed (6-8% standard deviation). Further analysis revealed that structural generalization (to novel combinations of familiar syntactic structures) poses greater difficulties than lexical generalization (to novel combinations of a familiar primitive and a familiar structure). These results suggests that higher accuracy on COGS would require a stronger structural bias than that of Transformers and LSTMs. Fodor and Pylyshyn (1988) highlighted the intrinsic connection between the ability to produce and understand different sentences that are made up of the same building blocks, such as John loves Mary and Mary loves John. This connection, which they refer to as systematicity, derives from a combinatorial mechanism that constructs the meaning of a complex expression from its parts: understanding John loves Mary and Mary loves John involves combining the same primitives using the same rules. The question of whether neural networks can display human-like systematicity has a long history. In a review of early work, Hadley (1994) argued that none of the connectionist models he examined displayed the degree of systematicity that humans do. Recently Lake and Baroni (2018) revisited this question using contemporary neural architectures-sequence-to-sequence models with LSTM and GRU units-and came to the same conclusion as Hadley.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Lake and Baroni based their study on the SCAN task, a novel task in which word sequences in a synthetic language need to be mapped to navigation command sequences (e.g., jump twice → JUMP JUMP). Crucially, their training/evaluation split required compositional generalization. A number of models have been developed that have improved performance on SCAN (Li et al., 2019;Gordon et al., 2020). However, since the semantic representation used by SCAN only covers a small subset of English grammar, SCAN does not enable testing various systematic linguistic abstractions that humans are known to make (e.g., verb argument structure alternation). Thus, it is unclear whether progress on SCAN would generalize to natural language. To bring the evaluation of compositional generalization a step closer to natural language, COGS includes a wide range of syntactic constructions, and uses semantic representations based on lambda calculus, inspired by the formalisms employed in formal semantics (Parsons, 1990) and semantic parsing (Palmer et al., 2005;Reddy et al., 2017). Following Dong and Lapata (2016) and Daza and Frank (2018), we cast semantic parsing as a sequence-to-sequence problem.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
In a semantic parsing task such as COGS, the goal is to map a sentence to a logical form. Following recent works such as Marvin and Linzen (2018) and Keysers et al. (2020), we generate the dataset using a rule-based approach; this allows us to maintain full control over the distribution of inputs that the learners are exposed to, and to ensure coverage of rare constructions that are not guaranteed to appear in natural corpora. COGS is not inherently grounded but could potentially be linked to a knowledge base or a visual world. The COGS dataset 1 is split into a training set and a generalization set. The training set includes systematic gaps that, in the generalization set, must be filled via compositional generalization. Success on the generalization set relies on several types of linguistic generalizations that humans are able to make. Instead of providing individual splits for each of the targeted generalizations, we expect the learner to make all of the target generalizations at once.  For instance, the sentence A hedgehog ate the cake represents the following input-output mapping:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
A hedgehog ate the cake → *cake(x 4 ) ; hedgehog(x 1 ) AND eat.agent(x 2 ,x 1 ) AND eat.theme(x 2 ,x 4 ) "Subject" and "Object" include subjects and objects of both simple and embedded sentences. Due to space constraints, some sentences are simplified or rephrased versions of the sentences included in the dataset.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
We describe below the five categories of generalizations targeted by COGS (see Table 1 for a full list). For a discussion of our design decisions from the perspective of formal semantics, see Appendix H.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
English speakers can easily interpret an open-class primitive (e.g., a noun) in a grammatical role that is different from the one in which it was first observed. For example, a noun that was only observed as a subject can easily be interpreted as an object. This generalization capacity has been attested in children as young as 20 months old (Tomasello and Olguin, 1993). We ensured that in the training set some lexical items only appear in subject position, and some only appear in object. In the generalization set, these lexical items appear in the opposite grammatical role. We test for generalization to the targeted grammatical roles not only in simple sentences, but also embedded clauses; this form of generalization is a defining criterion of strong systematicity (Hadley, 1994). For instance, a noun that only occurred as a subject of a simple sentence in training may occur as an object of an embedded clause in the generalization set:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
(1) a. TRAINING: A hedgehog ate the cake. b. GENERALIZATION: A girl said that Emma called the hedgehog.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
While some primitives appear in the training set in the context of a sentence, others only occur in isolation. We express common noun meanings as unary predicates (shark → λx.shark(x), proper noun meanings as constants (Emma → Emma), and verb meanings as n-ary predicates with thematic role specifications (like → λx.λy.λe.like.agent(e, y) AND like.theme(e, x)) (see Appendix H for more details). The training set contains these primitives as isolated words, but not as a part of a sentence; by contrast, the generalization set includes examples that require interpreting these primitives in context (e.g., The shark smiled).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Phrases with a modifier, such as an NP modified by a prepositional phrase (PP), can occupy the same grammatical roles as unmodified phrases. For example, just like [the cat] NP , the phrase [[the cat] NP [on the mat] PP ] NP is an NP, and can oc-cupy the same syntactic positions. Children acquiring language are most likely not exposed to modifiers in every possible syntactic position that the modified element may occur, yet learn a contextfree phrasal modification rule (e.g., NP → NP PP) rather than a rule localized to a specific grammatical role (e.g., NP obj → NP PP). To test for generalization to modifiers in an unseen grammatical role, our training set includes only examples with PP modifiers within object NPs, and the generalization set contains PP modifiers within subject NPs. We note that this is a simplification of the generalization problem that humans may encounter; see Appendix H for a further discussion.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The ability to derive an infinite number of expressions from a finite set of building blocks is a defining characteristic of human linguistic competence (Hauser et al., 2002). Human language achieves this property by allowing certain phrase types to be nested within a phrase of the same type. In [Mary knows that [John knows [that Emma cooks] CP ] CP ] CP , clauses (CP) are nested inside other clauses. Our dataset includes two types of recursive constructions that allow arbitrary depths of nesting: sentential complements (nested CPs) and nominal PP modifiers (nested PPs). The training set contains nestings of depth 0-2, where depth 0 is a phrase without nesting. The generalization set contains nestings of strictly greater depths (3-12).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Many English verbs participate in argument structure alternations (Levin, 1993). For instance, break can be used both as a transitive verb (John broke the window), and as an unaccusative verb, with its theme in the subject position (The window broke). Likewise, agent-patient verbs can passivize; John broke the window can be passivized to The window was broken, or with an optional agent by-phrase, The window was broken by John. These alternation patterns are not restricted to particular lexical items, and humans can often apply such alternations to verbs that have only been observed in one of the forms. To illustrate, a person told that I floosed the cat means "I fed the cat twice" would immediately be able to interpret The cat was floosed (though see Section 7 for a caveat). COGS contains alternation patterns that humans have been shown in experiments to generalize to nonce verbs: active-passive (Brooks and Tomasello, 1999), transitive-intransitive (unaccusative and object-omitted transitives; Ono and Budwig 2006;Hu et al. 2007;Kline and Demuth 2014), and the alternation between double-object and prepositional-phrase datives (Conwell and Demuth, 2007). For several verbs, we include only one of the alternating forms (e.g., active) in the training set, and only the other form (e.g., passive) in the generalization set.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
In English, the semantic role of the argument of a verb with a single argument depends on the identity of the verb; the surface syntax of the sentence is not enough to determine its interpretation. For instance, froze in the sentence The lake froze is an unaccusative verb, which takes a theme (or patient) as its grammatical subject, whereas in The dog smiled, smiled is an unergative verb that takes an agent as its grammatical subject. Inspired by this property, we include in our generalization set combinations of verbs and NPs, which all occur separately in the training set, but such that the NPs never appear as the thematic role specified by the verb in the training set. For instance, the training set contains a sentence with cobra as an agent subject (2a), and sentences with unaccusative verbs (2b), and the generalization set contains examples in which cobra and freeze appear together (3). Correctly interpreting cobra as the theme, even though it only appears in the training set as an agent, requires sensitivity to the argument structure of freeze.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
(2) TRAINING a. A cobra helped a dog. → cobra(x 1 ) AND help.agent(x 2 ,x 1 ) AND help.theme(x 2 ,x 4 ) AND dog(x 4 ) b. The drink froze. → *drink(x 1 ) AND freeze.theme(x 2 ,x 1 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The cobra froze. → *cobra(x 1 ) AND freeze.theme(x 2 ,x 1 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Grammar and logical forms. We generated the constructions described in Section 3 using a Probabilistic Context-Free Grammar (PCFG; Appendix A). The types of sentences covered by this PCFG accounted for 70-80% of naturallyoccurring English sentences, according to the analysis of five English corpora conducted by Roland et al. (2007). The semantic interpretation of a sentence follows deterministically from the PCFG rules, which were annotated with semantic class information needed to disambiguate ambiguous syntactic structures (Section 3.5). Sentences were first mapped to the simplified logical formalism proposed by Reddy et al. (2017) using their codebase, 2 and then passed through several postprocessing steps (see Appendix C). The logical forms use indexed constants that express the existence of an entity or an event denoted by the predicate. For example, in (4), x 1 expresses the existence of an entity that is both a cat and an agent of a smiling event; x 2 expresses the existence of an event that is a smiling event.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
(4) A cat smiled → cat(x 1 ) AND smile.agent(x 2 , x 1 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Our constants are named after indices of the phrasal head in the original sentence; in (4), the noun cat is in position 1, so the corresponding constant is x 1 . This indexing scheme was adopted to avoid the need to select arbitrary constant names (e.g, x, y, z, . . . ) as the number of entities and events in the expression grows.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Primitive exposure examples. Many generalization cases crucially rely on particular training examples. For instance, to apply the Subject → Object generalization to hedgehog, at least one example with hedgehog as subject must be included in the training set. Human learners only need to observe an item in a small number of distinct contexts before they can generalize to new contexts. For example, children of age 2 years and 11 months were able to produce in a passive construction a nonce verb they have only heard in an active transitive construction, after being exposed to 8 distinct usages of the construction (Brooks and Tomasello, 1999). Borovsky et al. (2010Borovsky et al. ( , 2012 further suggest that humans are even capable of single-shot learning of word meaning in context. We include in our training set a single example to generalize from ("primitive exposure example") per generalization case that requires it. In Appendix E.2 we report results on a version of COGS with 100 primitive exposure examples.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Training and generalization sets. We sampled 30,000 distinct sentences from our PCFG, exclud-ing ones with duplicate nominals (e.g., The cat saw a cat). These sentences were divided into training (80%; n = 24,000), development (10%; n = 3000), and test (10%; n = 3000) sets. We then added to the training set examples that specify the primitive meanings of 80 verbs and 60 nouns (including common and proper nouns 
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
We next analyze the performance on COGS of two widely-used models for language tasks: Long Short-Term Memory (LSTM; Hochreiter and Schmidhuber 1997) and Transformer (Vaswani et al., 2017), both in an encoder-decoder setup (Sutskever et al., 2014). Transformers have been quickly adopted in practical NLP systems (Storks et al., 2019), but the literature has reported mixed results on the benefit of Transformers over LSTMs in terms of linguistic generalization (Hupkes et al., 2020;van Schijndel et al., 2019). Our goals in these experiments are, first, to test whether strong NLP models are equipped with the compositional generalization abilities required by COGS, and second, to determine whether there exist substantial differences across the models we test, when the number of trainable parameters is controlled for.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
We trained LSTM and Transformer models on COGS only without any pretraining. We used crossentropy loss, a batch size of 128, and early stopping when validation loss did not improve for five validation steps (step size = 500). All experiments were run five times with different random seeds, which determined the initial weights and the order of the training examples. Models were implemented using OpenNMT-py 3 (Klein et al., 2017).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
For the LSTM, we used a 2-layer encoderdecoder with global attention and a dot-product 3 https://github.com/OpenNMT/OpenNMT-py score function. The decoder followed an inputfeeding approach (Luong et al., 2015). We tested both unidirectional and bidirectional LSTM encoders. The Transformer had a comparable number of parameters to the LSTMs (Transformer: 9.5M; BiLSTM: 10M; LSTM: 11M). It had 2 encoder and decoder layers, 4 attention heads, and a feedforward dimension of 512. See Appendix D for additional training details.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
All architectures performed well on the development and test sets (Table 2), with little variability across runs (Figure 2a, green dots). By contrast, generalization accuracy was low across the board, and was characterized by much higher variance (blue dots). Transformers and unidirectional LSTMs of a comparable size did not substantially differ in their average accuracy, whereas bidirectional LSTMs performed comparatively worse.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Dev. Test Gen.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Transformer 0.96 0.96 0.35 (± 0.06) LSTM (Bi) 0.99 0.99 0.16 (± 0.08) LSTM (Uni) 0.99 0.99 0.32 (± 0.06) Table 2: Average accuracy of tested models. Only standard deviation greater than 0.01 is shown.   Table 3, and see Appendix F for full results). The only exception to the trend was the Active → Passive case (but not vice versa) in the Transformer model, where all runs of the model achieved close to 100% accuracy. The majority of the LSTMs' predictions were structurally correct even when they did not exactly match the expected output, suggesting that Active → Passive is one of the least challenging cases in our generalization set (see Appendix G.1 for an error analysis).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Some of the COGS generalization cases require lexical generalization: a primitive needs to be interpreted in a structure which, while not itself novel, did not occur with that primitive in training. This is the case for Object → Subject: the training set does contain examples of the structure [NP [V NP] VP ] (Figure 3a), and the generalization concerns the particular NP that has never been observed in the first NP position. This contrasts with cases requiring structural generalization, where the structure of the sentence is itself novel. This is the case, for instance, for the structure [[NP PP] NP [V NP] VP ]a PP modifier on the subject-which appears in the generalization set but not in training (Figure 3b). The depth generalizations and the generaliza-tion of modifiers across grammatical roles require structural generalization; all such cases had zero or near-zero accuracies, whereas models performed better on lexical generalization (Figure 2b). This discrepancy suggests that composition of structures is more challenging to both Transformers and LSTMs. Successful depth generalization cases. Depth generalization with PP modifiers was the only case of structural generalization on which some models achieved nonzero accuracy. All of the successful examples were cases of depth 3, the smallest unseen depth tested. The success cases also had shorter output lengths, with a maximum length of 120 tokens. This was within the range of output lengths seen during training (the longest training example included 153 tokens), which may account for the somewhat higher accuracy on these cases.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Failure to generalize structurally or failure to produce novel labels? It is known that neural models find it challenging to produce labels they have not seen during training (Gandhi and Lake, 2019). Handling this problem is a necessary part of solving depth generalization, since each of the outputs of the depth generalization cases, such as (5b) below, contains more constants than the training outputs, such as the output of (5a):
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
(5) a. Depth 1: The cat liked that the dog saw the mouse. (5 index-taking items)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
b. Depth 3: The cat liked that the dog liked that the mouse liked that the girl saw the rat. (9 index-taking items)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
As discussed in Section 3, we used index-based labels for constants precisely to help models with this issue of producing novel elements, by grounding the labels to the indices. Specifically, the 5 index-taking items in (5a) are labeled x 1 , x 2 , x 5 , x 6 and x 8 instead of being assigned arbitrary labels such as x, y, z . . . . However, even with such nonarbitrary labels, the model still needs to learn that a word at index i relates to the output string 'i'. While this problem of novel symbols is indeed an issue that the models need to handle during depth generalization, the pattern of errors suggest that the low accuracy is not purely due to this issue. In fact, only 0.5% of all depth generalization errors were cases where the structural form of the outputs were correct with only the indices being incorrect. More frequently, the models produced an end-of-sentence token too early (90.3% of all depth generalization errors), or produced sequences that were superfluously long (3% of errors contained more than 1000 tokens-more than twice as longer than the maximum gold output length: 480). This implies that models struggle with handling longer and deeper sequences than those observed during training, independently of their inability to produce novel labels. While output length likely contributed to the difficulty of our depth generalization caseseven in the in-domain test set, the average length of correct answers was 43 tokens, compared to 83 for incorrect answers-deeply nested structures imposed additional challenges. On the test set examples with output length greater than 95, LSTM models and Transformer models had 68% and 13% accuracy, respectively. Their PP modifier depth generalization accuracy was much lower (LSTM: 2%; BiLSTM and Transformer: near 0%).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Our depth generalization set contains examples with embedding depths 3-12. However, it is likely that humans would find deeply embedded structures difficult to interpret. Given this potential difficulty for humans, is our depth generalization a fair challenge to pose? Comprehensibility of 3-5 degrees of embedding is attested in the literature; Blaubergs and Braine (1974) showed that humans can understand 3-5 levels of right-branching CP embedding, and Karlsson (2010) observed that 3-5 levels of right-branching PP and CP embeddings do occur in corpora. In the case of the models we tested, they almost completely failed on generalization to any levels of embedding, including depths 3-5 that humans should be able understand (Table 4). We discuss the issue of generalization to depths greater than 5 in Appendix H.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
All 3-5 6-12
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Transformer 0.00 0.00 0.00 LSTM (Bi) 0.00 0.01 0.00 LSTM (Uni) 0.01 0.03 0.00 Table 4: Accuracy on depths 3-5 and depths 6-12.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
In follow-up experiments, we found that increasing the number of parameters of the Transformer model five fold did not improve performance. If anything, variability was higher and mean accuracy was lower (see Appendix E.1). By contrast, increasing the number of exposure examples per primitive from one to 100 led to a significant improvement in generalization for all three models, though this increase was only applicable to lexical generalization cases (see Appendix E.2).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Our aggregate results in Table 2 are in line with recent work that has documented a significant discrepancy between neural models' excellent perfor-mance within distribution and their degraded performance out of distribution (Johnson et al., 2017;Lake and Baroni, 2018;Hupkes et al., 2020). Our finding of poor generalization to deeper nested structures aligns with the results of Hupkes et al. (2020). Given that deeper structures also tend to be longer than shallower ones, this finding also relates to the difficulty of generalization to longer sequences. One illustrative example is the poor performance of LSTMs on a SCAN split that requires generalizing from shorter to longer sequences. While several models have made significant improvements over other SCAN splits, progress on the length split remains minimal (Li et al., 2019;Lake, 2019;Gordon et al., 2020).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The most similar work to ours is Compositional Freebase Questions (CFQ; Keysers et al. 2020), a synthetic dataset designed to test for compositional generalization in SQL parsing. COGS differs from CFQ in two main ways. First, compared to sentences with a SQL mapping, which are limited to questions and imperatives, the semantic representation used in COGS significantly extends the variety of expressions that can be assigned an interpretation. Second, in CFQ, challenging splits are defined by a similar primitive distribution but different distributions of the composed forms ("compound divergence"). This can lead to a training and test split that is not characterized by any principled linguistic difference. Following a stronger definition of compositionality, the generalization set in COGS includes combinations of primitives and syntactic roles that are novel (occurred zero times in training), without concern for matching the distribution of primitives across training and testing.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Our work is related to but distinct from work that tests language models for systematic syntactic generalization (Gulordava et al., 2018;Marvin and Linzen, 2018, i.a.). Unlike our work, the language modeling setup does not directly evaluate the meaning that the model assigns to a sentence.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
To reach full adult linguistic competence, human learners not only need to be able to make abstraction-based generalizations, but also need to learn how to constrain them. For example, the verb donate takes a recipient to-PP (Emma donated the book to the museum) but does not allow doubleobject alternation (*Emma donated the museum the book). How constraints as such could be learned has been discussed in linguistics under the banner of the projection problem (Baker, 1979). COGS focuses on evaluating computational models' ability to make systematic generalizations, but not on evaluating the ability to constrain them. For this reason, COGS only includes examples to which generalizations are applicable (e.g., dative verbs that alternate). This is a simplification; in natural language, generalizations are not applicable across-the-board, and are modulated by a multitude of morphophonological, syntactic and semantic factors. In the case of the dative alternation, properties such as animacy and definiteness are involved (Bresnan and Ford, 2010). Thus, evaluating constraints on generalization requires a detailed characterization of factors that govern individual generalization cases, as well as a formalism capable of expressing these factors, which we leave to future work.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
We have proposed COGS, a challenge set for compositional generalization, which uses a synthetic sentence-to-logical-form mapping task that approximates meaning interpretation in English. When tested on COGS, both Transformers and LSTMs performed poorly on the generalization set, with high variability across runs, while their performance on the in-domain test set was consistently near-perfect. Furthermore, the models found structural generalization much more challenging compared to lexical generalization. Our results suggest that achieving high generalization accuracy on COGS is beyond the capacity of models that we tested, and COGS can therefore motivate the development of new computational models.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
What architecture would be needed to solve COGS? For structural generalization cases, the results of Bowman et al. (2015) 
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Our PCFG assigns uniform probability (about 5%) to each frame (e.g., transitive verb with both subject and object, transitive verb with only subject, passivized transitive with subject only, passivized transitive with subject and agent by-phrase...) except for CP embedding constructions, whose probability was increased to about 8% to match their distribution in natural corpora. 4 Syntactically ambiguous verb subcategories are distinguishable by distributional information; for instance, unaccusative verbs appear with both animate and inanimate subjects, whereas unergatives and object-omitted transitives only appear with animate subjects. Object-omitted transitives always have a transitive counterpart, whereas unergatives do not alternate. The verb subtypes also have distinct primitive logical forms, and primitive logical forms of some verbs were provided as part of the training set. The grammar assigns Zipfian probability distribution (inverse rankfrequency distribution) over lexical items in each noun and verb subcategory. 5 This was done in order to ensure that all possible grammatical patterns that a lexical item could appear in were sampled by the PCFG and included in our dataset, for at least the top most frequent items in the class (e.g., both forms of the object omission alternation are sampled for the most frequent verb). The types of sentences generated by our PCFG are as follows. Sentence type names are taken from Roland et al. (2007).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
When calculating the % covered by our grammar in Section 4, we collapsed Sentential Complement with Complementizer and Sentential Complement without Complementizer.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
We selected the 403 common nouns in our lexical inventory from the MacArthur-Bates Communicative Development Inventories (Fenson et al., 2007) and the British National Corpus (Leech et al., 2001). 100 proper nouns were selected from top baby names of 2019 in the United States according to the United States Social Security Administration. In selecting the verbs, we referred to Levin (1993) and Kipper-Schuler (2005). There were 113 unique verbs and 6 verb types, with some overlapping verbs across verb types (e.g., like with NP and CP arguments). The list of verb types are as follows:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Verbs that take NP arguments that allow direct object omission (e.g., eat)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Verbs that take NP arguments that do not allow direct object omission (e.g., find)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Subject control verbs that take infinitival arguments (e.g., try)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Verbs that take CP arguments (e.g., say)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Unaccusative verbs (e.g., freeze)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Unergative verbs (e.g., sleep)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Dative verbs (e.g., give) 5 common nouns, 3 proper nouns and 7 verbs used as primitive exposure examples were selected at random.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
We applied several postprocessing steps to the simplified logical forms of Reddy et al. (2017). The changes induced by our postprocessing steps are as follows:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Skolem constants are named x i instead of i, where i is the 0-based index of the head of the phrase denoted by the constant.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• Event predicates triggered by nominals are removed for simplicity.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• The final form is conjunctive, where the conjuncts are sorted by the subscript of the Skolem constants (i.e., the order of the conjuncts are deterministic).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Expression: John ate the cookie.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Neo-Davidsonian ∃.e.eat (e) ∧ (Agent(e) = john ) ∧ (T heme(e) = ιx.cookie (x)) Reddy et al. (2017) ['arg0(3:e, 3:cookie)', 'eat.arg1(1:e, 0:m.John)', 'eat.arg2(1:e, 3:cookie)'] Ours *cookie(x 3 ) ; eat.agent(x 1 , John) AND eat.theme(x 1 , x 3 ) • Definite and indefinite descriptions are formally distinguished. Refer to Appendix H for the exact distinction and linguistic implications.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
See Table 5 for a comparison between logical forms.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
LSTM. We used a 2-layer LSTM encoderdecoder with global attention and a dot-product score function. The decoder followed an inputfeeding approach (Luong et al., 2015). We tested both unidirectional and bidirectional encoders. We used inputs of dimension 512 and two hidden layers of dimension 512 (256 for model with bidirectional encoders so that the input dimension of the decoder stays constant across models after concatenating forward and backward states, and the number of parameters in each model remains comparable). A dropout of 0.1 was applied after the embedding layer and after each hidden layer except for the last. Following Lake and Baroni (2018), we used the Adam optimizer, and clipped gradients with a norm larger than 5.0. The training time for each model was around 3 to 4 hours on a single NVIDIA K80 GPU.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Transformer. Our Transformer model had 2 encoder and decoder layers, 4 attention heads, and a feedforward dimension of 512. Other hyperparameter settings not discussed here followed Vaswani et al. (2017) as closely as possible. The training time for each model was around 1 to 2 hours on a single NVIDIA K80 GPU.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The results we report in the body of the paper are from a Transformer with 9.5M parameters. How does the number of parameters affect the Transformer's success on COGS? Figure 4 compares the performance of three Transformer models of varying size (large: 45M, small: 9.5M, smaller:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
4.5M). The number of parameters did not a have large impact on test set accuracy; all runs of all models achieved higher than 90% accuracy. On the other hand, model size did affect generalization. Perhaps surprisingly, the average across 5 runs of the large model was lower than those of smaller models; however, this average result is hard to interpret given the very high variance in accuracy across runs of the the largest Transformer.    As discussed in Section 5.2, the Active → Passive generalization was a case in which Transformers performed near-perfectly, whereas LSTMs did not. However, an error analysis revealed that the errors made by LSTMs were more systematic than those of Transformers. The majority of LSTMs' errors were structurally correct; only 0.3% (7/2591) of the unidirectional LSTM errors and 0.5% (14/2773) of the bidirectional LSTM errors had a different structure from the gold output. LSTMs often replaced the target passive verb with a different one (6), misused a thematic role (7), or misused an index (8). These types of errors have equivalent structure to the correct output, and have the same number of tokens as the correct output.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
A balloon was blessed. → GOLD: balloon(x 1 ) AND bless.theme(x 3 ,x 1 ) LSTM: balloon(x 1 ) AND inflate.theme(x 3 ,x 1 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The book was blessed by a girl. → GOLD: *book(x 1 ) AND bless.theme(x 3 ,x 1 ) AND bless.agent(x 3 ,x 6 ) AND girl(x 6 ) LSTM: *book(x 1 ) AND bless.theme(x 3 ,x 1 ) AND send.recipient(x 3 ,x 6 ) AND girl(x 6 ) (8) A rose was blessed by the baby. → GOLD: *baby(x 6 ) ; rose(x 1 ) AND bless.theme(x 3 ,x 1 ) AND bless.agent(x 3 ,x 6 ) LSTM: *baby(x 5 ) ; rose(x 1 ) AND bless.theme(x 3 ,x 1 ) AND bless.agent(x 3 ,x 6 ) By contrast, the Transformer's errors in the Active → Passive generalization, despite being much fewer in number, had incorrect structure (79.6% of all errors; 39/49). The pattern in the total of 49 errors made by Transformer models in aggregate included omission of whole conjunct, spurious indices, not producing an output, using a numbered constant in place of a proper noun, etc. The following example shows a Transformer output with multiple errors-the model misinterpreted tool as a binary predicate and misindexed the theme argument:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
(9) The tool was blessed by the girl. → GOLD: *tool(x 1 ) ; *girl(x 6 ) ; bless.theme(x 3 ,x 1 ) AND bless.agent(x 3 ,x 6 ) TRANSFORMER: *tool(x 1 ) ; *girl(x 6 ) ; tool(x 3 ,x 1 ) AND bless.theme(x 3 ,x 6 ) Some Transformer runs produced more systematic errors than others, despite having similar accuracy on the Active → Passive generalization. For example, some runs mostly made the error of using the wrong verb as in (6). Others made more idiosyncratic errors with mixed patterns. One possible reason for the high performance on the Active → Passive case is that our training data included both passive constructions with and without the agent by-phrase (e.g., both The book was seen and The book was seen by Emma). In these two constructions, the logical form of the former is a prefix of the logical form of the latter:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The book was seen (by Emma). →  WITH BY: *book(x 1 ) AND see.theme(x 3 ,x 1 ) AND see.agent(x 3 ,Emma)
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Since these two types of passive constructions were sampled with equal probability, performance on the Active → Passive case may have benefited from more exposures to examples relevant to forming the passive construction.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
The LSTMs' erroneous outputs were more systematic, and closer to the correct outputs, in other generalization cases as well. The average token-level edit distance between errors and correct answers across all generalization cases, only considering error cases, were 11 and 14 tokens for bidirectional and unidirectional LSTMs, compared to 42 tokens for Transformers. Furthermore, Transformers frequently produced ill-formed logical forms; for example, they often failed to close the final parenthesis (11). In fact, ending the logical form with anything other than a right parenthesis is illformed (12). This type of error accounted for 12% of all Transformer errors, while only 0.5% of bidirectional and unidirectional LSTM errors were illformed in this way.  Table 3 shows that even for the same type of targeted generalization (e.g., Object → Subject, Primitive → Object), the variant that used proper nouns (13) was more challenging than the variant using common nouns (14).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
(13) Training: The creature grew Charlie. → *creature(x 1 ) AND grow.agent(x 2 , x 1 ) AND grow.theme(x 2 , Charlie) Generalization: Charlie ate a cookie. → eat.agent(x 1 ,Charlie) AND eat.theme(x 1 ,x 3 ) AND cookie(x 3 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Training: Henry liked a cockroach. → like.agent(x 1 , Henry) AND like.theme(x 1 ,x 3 ) AND cockroach(x 3 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Generalization: The cockroach ate the bat. → *cockroach(x 1 ) AND *bat(x 4 ) AND eat.agent(x 2 ,x 1 ) AND eat.theme(x 2 ,x 4 )
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
What is the source of this discrepancy? As can be seen from the above examples, common and proper nouns are formally distinct in both the source sentence and the target logical form. Translating a common noun requires conjoining a unary predicate (cockroach(x n )), and placing the predicated constant (x n ) in appropriate event predicates. On the other hand, translating a proper requires placing the nominal constant (Charlie) inside appropriate event predicates. Given the lower complexity of (symbolic) steps required for translating proper nouns, the lower accuracy is surprising. While we do not have a definite explanation for this discrepancy, one possibility is that it is due to a frequency effect; our dataset overall contained more common nouns than proper nouns, in terms of both type and token frequency. The discrepancy in accuracy between common and proper nouns indicates that performance is sensitive to seemingly minor formal differences in cases that require the same type of generalization, echoing the discrepancy between the jump and turn left primitive splits of SCAN that were originally observed by Lake and Baroni (2018).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Semantic representation. Our semantic representation is based on a Neo-Davidsonian view of verbal arguments (Parsons, 1990), in which verbs specify an event argument, and thematic roles link non-event arguments to the event. Definite descriptions that are not proper names are marked with an asterisk, standing in place of the standard ι notation. The asterisk expressions appear to the leftmost of the logical form to avoid nesting of predicated expressions. They are not conjoined to the logical form but separated with a ;, because ι expressions are of type e rather than t. The logical form with the asterisk expression (e.g., The cat ran: *cat(x 1 ) ; run.agent(x 2 , x 1 ) should be semantically equivalent to one that contains a nested ι expression (∃e. run.agent(e, ιx.cat(x)), if ι is scopally inert. This may not necessarily be the case for definite descriptions in intensional semantics; for instance under modals. See the discussion of Kaplan (1989) in Wolter (2019) for more details.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Representation of primitive meanings. Primitives in our dataset take the following form:
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
• where λ is written as 'LAMBDA' and ∧ is written as 'AND'. Primitive meanings are not skolemized because they are not existentially quantified. We used the letters e, a, b to distinguish variables from skolem constants (x n ). Verbs that are compatible with agents specify an agent as an argument in their primitive meanings for simplicity, rather than following the external argument analysis of Kratzer (1996).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Recursive structures tested. Whether unbounded recursion should be considered as a part of machinery that governs language is a debated issue, the evidence against being the significantly degraded human parsing performance on multiplynested structures (Christiansen and Chater, 1999). In our dataset, we only included structures that are traditionally thought of as recursive, but does not necessitate recursion as an intrinsic mechanism because they can be implemented by a Finite State Machine (Christiansen, 1992).
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Testing generalization to arbitrary depths. Our depth generalization sets test generalization to 3-12 degrees of embedding in right-branching structures. However, human processing of embedded structures degrades over levels of embedding (Blaubergs and Braine, 1974) and attestation of embeddings greater than depth 5 is rare (Karlsson, 2010). Given this limitation in humans, should the inability to handle generalization to our generalization set, and furthermore arbitrary depths of embedding be viewed as a flaw of the system? Our position is that is should. According to Chomsky's notion of competence versus performance, there is no reason to view English sentences with embedding depths greater than 5 to be ungrammatical, even if human memory limitations make such sentences difficult to understand. Computational models that we tested are not restricted by the same memory limitations and therefore should not fail to process such sentences on the same grounds. Any such failure would be diagnostic of a discrepancy between what the model has learned and the correct way to perform the task, as defined by English grammar. A detailed comparison of computational models and human subjects' performance on this subset of COGS would be an interesting followup work that would shed light on both human and machine generalization. We predict that models' behavior will differ from that of humans, since the models' accuracy at depth 3 was already close to zero, whereas we expect that humans will display degraded but still reasonable understanding of depth 3 PP/CP embeddings.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
PP attachment ambiguity. Our grammar does not generate VP-modifying PPs (the only PP verbal dependents are recipient to-phrases, which are always arguments rather than modifiers). Therefore, all PP modifiers in our dataset should strictly have an NP-attachment reading, although for human readers VP-attachment readings could sometimes be more prominent based on the lexical content of the sentences. All modifications are nested rather than sequential: Selectional preference. Words have selectional preference, a tendency to semantically constrain other words that they appear with. For instance, verbs such as sing, walk are likely to take animate subjects. Our grammar only implements a simplified version of selectional preference: namely the animacy of the NP arguments based on verb type (e.g., subjects of unergatives are animate). In reality, selectional preference is much more complex and highly verb-specific; for instance the theme of eat should be something that is edible. The simplification of selectional preference results in semantic infelicity in some of the generated sentences. This should not create any difficulty in constructing a valid form-meaning mapping if models are trained from scratch, but may cause problems if models pretrained on real language data are tested.
COGS: A Compositional Generalization Challenge Based on Semantic Interpretation
Generalization of PP modification. Our PP modifier generalization set (Section 3.2) requires generalizing PPs that modify NPs in the object position to NPs in the subject position, without having seen any subject modification. We note that this may be a stronger generalization problem than what humans may actually encounter based on the following two observations. First, it is true that PP modifiers in the subject position are much less frequent than PP modifiers in the object position in child-directed speech, but subject-modifying PPs are not absent from it: according to our analysis of the Epochs corpus of Perfors et al. (2011), PP modification on the subject of a declarative sentence occurred only 13 times whereas PP modification on the object occurred over 100 times. Second, there exist many [NP PP] fragments that are not full sentences (e.g., a disk from a game) in the corpus. It is still likely that PP modification does not occur in all possible syntactic positions that can be occupied by an NP-for instance, in the subject position of a depth 2 embedded CP-and to interpret such sentences structural generalization would be required. Nevertheless, whether humans would be able to generalize modifiers in one syntactic position in the total absence of observing modifiers in other syntactic positions (or as fragments) remains to be tested, and is part of our future work.  Table 7: Full model accuracy by generalization case, with primitive exposure in 1 context (default) and 100 (increased) distinct contexts. Each result is an average over 5 random seeds.
On Compositional Generalization of Neural Machine Translation
Neural machine translation (NMT) has shown competitive performance on benchmark datasets such as IWSLT and WMT (Vaswani et al., 2017;Edunov et al., 2018a;Liu et al., 2020a), and even achieves parity with professional human translation under certain evaluation settings (Hassan et al., 2018). However, the performance can be relatively low in out-of-domain and low-resource conditions. In addition, NMT systems show poor robustness and vulnerability to input perturbations (Belinkov and Bisk, 2018a;Cheng et al., 2019). One example is shown in Table 1, where simple substitution of a word yields translation with completely different semantics. Many of these issues origin from the fact that NMT models are trained end-to-end over large parallel data, where new test sentences can be sparse.
On Compositional Generalization of Neural Machine Translation
Disregarding out-of-vocabulary words, a main cause of sparsity is semantic composition: given a limited vocabulary, the number of possible compositions grows exponentially with respect to the composite length. The ability to understand and Input Translation
On Compositional Generalization of Neural Machine Translation
Taylor breaks his promise "·à˙ (Taylor keeps his promise) James breaks his promise y∆Ø›Õ˙ (James breaks his promise) produce a potentially infinite number of novel combinations of known components, namely compositional generalization (Chomsky; Montague; Lake and Keysers et al., 2020), has been demonstrated deficient in many machine learning (ML) methods (Johnson et al., 2017a;Bastings et al., 2018;Loula et al., 2018;Russin et al., 2019a).
On Compositional Generalization of Neural Machine Translation
In this paper, we study compositional generalization in the context of machine translation. For example, if "red cars" and "blue balls" are seen in training, a competent algorithm is expected to translate "red balls" correctly, even if the phrase has not been seen in training data. Intuitively, the challenge increases as the composite length grows. Recently, several studies have taken steps towards this specific problem. They either use a few dedicated samples (i.e., 8 test sentences) for evaluation (Lake and Li et al., 2019b;Chen et al., 2020), or make simple modifications in sampled source sentences such as removing or adding adverbs, and concatenating two sentences (Raunak et al., 2019;Fadaee and Monz, 2020a). Such experimental data is limited in size, scope and specificity, and the forms of composition are coarse-grained and non-systematic. As a result, no qualitative conclusions have been drawn on the prevalence and characteristics of this problem in modern NMT.
On Compositional Generalization of Neural Machine Translation
We make a first large-scale general domain investigation, constructing the CoGnition dataset (Compositional Generalization Machine Translation Dataset), a clean and consistent paral-  lel dataset in English-Chinese, along with a synthetic test set to quantify and analyze the compositional generalization of NMT models. In particular, we define frequent syntactic constituents as compounds, and basic semantic components in constituents as atoms. In addition to the standard training, validation and test sets, the CoGnition dataset contains a compositional generalization test set, which contains novel compounds in each sentence, so that both the generalization error rate can be evaluated, and its influence on BLEU (Papineni et al., 2002) can be quantified. Our compositional generalization test set consists of 2,160 novel compounds, with up to 5 atoms and 7 words. In this way, generalization ability can be evaluated based on compound translation error rate. Empirical results show that the dominant Transformer (Vaswani et al., 2017) NMT model faces challenges in translating novel compounds, despite its competitive performance under traditional evaluation metrics such as BLEU. In addition, we observe that various factors exert salient effects on model's ability of compositional generalization, such as compound frequency, compound length, atom co-occurrence, linguistic patterns, and context complexity. The CoGnition dataset along with the automatic evaluation tool are realesed on https://github.com/yafuly/CoGnition.
On Compositional Generalization of Neural Machine Translation
Following Keysers et al. (2020), compositional generalization is defined as the capacity to systematically generalize to novel combinations of components which are learned sufficiently during training. Key elements to measure compositional generalization include atoms and compounds. Specifically, atoms are primitive elements in the train set whereas compounds are obtained by composing these atoms. The research question is whether neural models perform well on unseen compounds. Take Table 2 for example, in the SCAN dataset, the atoms are simple commands such as "jump" and the composite command "jump twice" is a compound. In the CFQ, the compounds are questions such as "Who directed Elysium", and the atoms correspond to the primitive elements in the questions such as the predicate "directed", the question patterns "Who [predicate] [entity]" and the entities "Elysium".
On Compositional Generalization of Neural Machine Translation
In theory, compounds in MT can be defined as phrases, sentences or even document. In practice, however, we want to control the number of atoms in a novel compound for quantitative evaluation. In addition, it can be highly difficult to construct a large-scale dataset where novel compounds are sentences of practical sizes (the number of synthesized sentences increases exponentially with their length) while ensuring their grammatical correctness. Therefore, we constrain compounds to syntactic constituents, and define atoms as basic semantic components in constituents according to syntactic and semantic rules for forming constituents (Partee, 1995). As a result, we randomly assign multiple sentential contexts for investigating each novel compound. Table 2 shows a contrast between our dataset and existing datasets for compositional generalization in semantics.
On Compositional Generalization of Neural Machine Translation
Mistakes caused by weakness in computational generalization can be easily found in state-ofthe-art NMT models. In particular, we train a Transformer-based model (Vaswani et al., 2017) on WMT17 En-Zh Dataset 1 . One sentence in the standard test set, "but the problem is , with the arrival of durant , thompson 's appearance rate will surely decline , which is bound to affect his play", is translated into "FÓò/, è@\py Ñ0e, dnÓÑ hØö⇢↵M, Ÿ ö⇢ qÕ0÷Ñh" (English: but the problem is , with the arrival of durant , thompson 's will surely look worse , which is bound to affect his play). The novel compound "appearance rate" is composed of two atoms (i.e., "appearance" and "rate"), both with a high frequency of more than 27,000 times in the training set. However, the sentence semantics is completely distorted due to the failure of semantic composition, which is possibly influenced by the context word "play". More importantly, as the overall translation highly overlaps with the reference, the model achieves a high score in similarity-based metrics such as BLEU, demonstrating that fatal translation errors can be overlooked under traditional evaluation metrics. Figure 1 gives an overview of our data construction process. We first source monolingual data (Section 4.1), and then build parallel data based by translation (Section 4.2). Then we synthesize a test set of novel compounds (Section 4.3), and offer an automatic evaluation method (Section 4.4).
On Compositional Generalization of Neural Machine Translation
Our goal is to focus on compositional generalization and minimize the influence of additional factors such as polysemy (Berard et al., 2019), misalignment (Munteanu and Marcu, 2005), and stylistic problems (Hovy et al., 2020). The dataset should ideally have following characteristics. First, the vocabulary size should be small and contain only words of high-frequency in order to avoid problems caused by rare words. In other words, variety of composition should come from combining different frequent words instead of word diversity, as suggested in (Keysers et al., 2020). Metaphorical words, which can increase the translation difficulty, should be excluded. Second, source sentences should not be too long or have complex syntactic structures. As a result, a sentence can be 
On Compositional Generalization of Neural Machine Translation
The red dog is running. The red dog was sick. The red dog had fun with a toy.  Widely-adopted corpora such as parallel data released on WMT and IWSLT 2 have large vocabularies and also contain noisy sentences and rich morphology (Li et al., 2019a), which do not fully meet our goal. We choose Story Cloze Test and ROCStories Corpora (Mostafazadeh et al., 2016(Mostafazadeh et al., , 2017 as our data source. The dataset is created for commonsense story understanding and generation, and consists of 101903 5-sentence stories. These stories are rather simple in items of vocabulary and syntax, but still contain rich phrases. In addition, the topic is constrained to daily life.
On Compositional Generalization of Neural Machine Translation
Since the vocabulary size of 42, 458 is large, we select the top 2, 000 frequent words as our vocabulary and extract sentences where the words are exclusively from the restricted vocab. Moreover, sentences that are longer than 20 words are removed. In this way, we finally obtain 216, 246 2 https://wit3.fbk.eu/ sentences for parallel data construction. More detailed statistics including comparison to WMT and IWSLT data are shown in Appendix B.
On Compositional Generalization of Neural Machine Translation
We take an MT post-editing method to construct parallel data, first using a public translation engine to obtain model-generated translations, and then requesting expert translators to post-edit them. The following aspects are highlighted:
On Compositional Generalization of Neural Machine Translation
• Ensure the fluency of translations.
On Compositional Generalization of Neural Machine Translation
• Ensure word-level matching between translated sentences and source sentences. Typically, every word should be correctly translated, without omission for legibility.
On Compositional Generalization of Neural Machine Translation
Finally, we obtain a parallel dataset of 216, 246 sentences in CoGnition, and randomly split it into three subsets: 196, 246 sentence pairs for training, 10, 000 sentence pairs for validation, and 10, 000 sentence pairs as the random test set. In addition to the above split, we additionally make a compositional generalization test set, which is described in the next section.
On Compositional Generalization of Neural Machine Translation
We manually construct a special test set dedicated for evaluation of compositional generalization, by synthesizing new source sentences based on novel compounds and known contexts.
On Compositional Generalization of Neural Machine Translation
Designing Compound Patterns We use Berkeley Parser to obtain constituent trees (Kitaev and Klein, 2018). In CoGnition, noun phrases (NP), verb phrases (VP) and positional phrases (PP) are three most frequent constituents, accounting for 85.1% of all constituents, and thus we construct compounds based on them. According to syntactic and semantic rules (Partee, 1995), we choose basic semantic components as our atoms including determiners (DET), nouns (N), verbs (V), prepositions (P), adjectives (ADJ), and postpositive modifiers (MOD). Specifically, postpositive modifiers include prepositional phrases and relative clauses, and can contain multiple words. We consider them as a single atom due to their semantic inseparability. In this way, we generate 4 compound patterns for NP, VP, and PP, respectively, which are listed in Table 3 with corresponding examples.
On Compositional Generalization of Neural Machine Translation
Making Novel Compounds We use Stanza (Qi et al., 2020) to obtain POS tagging for each word in training sentences. We construct novel compounds by first selecting atom candidates with relatively consistent translation in the training set. The frequency of candidate atoms covers a wide range from 34 to 73518. We list full set of atom candidates in Table 4. For constructing compounds, we enumerate all possible combinations of atoms according to the patterns in Table 3, and then remove those that are ungrammatical or likely to cause ethic issues, obtaining 2,160 compounds finally. We do not deliberately make all compounds unseen, yet only 0.93% of them appear in the training data.
On Compositional Generalization of Neural Machine Translation
Synthesizing Source Sentences We embed the compounds in specific context to form complete source sentences. Concretely, we first apply Berkeley Parser on the training sentences to obtain sentence templates, where certain constituents are replaced by placeholders according to their constituent types, e.g., "NP-placeholder spent a lot of time to set up a wedding .". Then we select 5 sentence templates for each constructed compound accordingly, so that every compound can be evaluated under 5 different contexts. To distinguish from VP and PP, we put NP compounds only in sentences with the placeholder outside VP and PP.
On Compositional Generalization of Neural Machine Translation
Making Reference To maintain statistical consistency, target translations of synthetic sentences are also obtained using the same MT post-edit approach. In addition to the annotation principles listed in 4.2, we set several additional rules:
On Compositional Generalization of Neural Machine Translation
• Filter sentences with ethical issues and replace them with other synthetic ones.
On Compositional Generalization of Neural Machine Translation
• Ensure the accuracy of compound translation.
On Compositional Generalization of Neural Machine Translation
Finally, we obtain a compositional generalization test set (CG test set) of 10, 800 parallel sentences. The final dataset statistics is shown in table 5.
On Compositional Generalization of Neural Machine Translation
We mainly adopt human evaluation for the experiments of this paper (Section 5) for ensuring reliability of findings. Despite its accuracy, human evaluation can be expensive. To facilitate fast evaluation in future research, we introduce an automatic evaluation approach to quantify a model's generalization ability on our CG test set.
On Compositional Generalization of Neural Machine Translation
In particular, we manually construct a dictionary for all the atoms based on the training set (See Appendix C). The prerequisite of correctly translating one compound is that all of the atom translations should be contained. Besides, in most cases the translation of nouns should be placed after that of other atoms. Based on this, we design a heuristic algorithm to determine whether compounds are translated correctly. With the human annotation as ground truth, our automatic evaluation tool achieves a precision of 94.80% and a recall of 87.05%, demonstrating it can serve as an approximate alternative to human evaluation.
On Compositional Generalization of Neural Machine Translation
We conduct experiments on CoGnition dataset and perform human evaluation on the model results.
On Compositional Generalization of Neural Machine Translation
We tokenize the English side using Moses tokenizer and do not apply byte pair encoding (BPE) (Sennrich et al., 2016) due to the small vocabulary (i.e., 2000). The Chinese sentences are segmented by   jieba segmenter 3 . We employ BPE with 3,000 merge operations, generating a vocabulary of 5,500 subwords. We focus on Transformer (Vaswani et al., 2017) because of its state-of-the-art performance on machine translation (Edunov et al., 2018b;Takase and Kiyono, 2021;Raffel et al., 2020;Zhu et al., 2020;Liu et al., 2020b) and better performance on existing compositional generalization dataset (Daniel et al., 2019). We implement our model using BASE configuration provided by Fairseq (Ott et al., 2019). The model consists of a 6-layer encoder and a 6-layer decoder with the hidden size 512. We tie input and output embeddings on the target side. The model parameters are optimized by Adam (Kingma and Ba, 2015), with 1 = 0.1, 2 = 0.98 and ✏ = 10 9 . The model is trained for 100,000 steps and we choose the best checkpoint on validation set for evaluation.
On Compositional Generalization of Neural Machine Translation
We report character-level BLEU scores using SacreBLEU (Post, 2018) to measure the overall translation performance. In addition, we request expert translators to annotate the correctness of compound translation. Translators are asked to only focus on examining whether the compound itself is translated correctly or not, disregarding errors in context. Specifically, a compound is correct only if its translation contains semantic meaning of all atoms and is fluent in human language. Since each of the 2,160 compounds is provided with 5 contexts, we can compute the translation error-rate for each compound. 3 https://github.com/fxsjy/jieba Table 6 shows the results. Besides the CG test set, we also list results on three of its subsets, which only contain NP, VP or PP compounds respectively. The model achieves a 69.58 BLEU score on the random test set, which partly indicates distributional consistency and quality of the dataset. In comparison, the performance on the CG test set drops dramatically by more than 20 BLEU points. Given that the only difference between synthetic sentences and training sentences is the unseen compounds (i.e., contexts are seen in training), the decrease of 20 BLEU points indicates that unseen compounds pose a significant challenge, which is however easy to be overlooked in traditional evaluation metrics. For example, the model mis-translates "alas , he became sick from eating all of the peanut butter on the ball" into " ÷ ‡:⇤âÜ⇤:⌦@ Ñ ± q ≈Ü" (English: alas , he became sick from eating all of the peanut butter on the field). With a minor mistake on the compound "on the ball", the model achieves a sentence-level BLEU of 61.4, despite that the full sentence meaning is largely affected. In other words, the BLEU score of 69.58 can be misleading since novel compounds can be rare in the random test set. Such mistakes in generalizing new compounds can severely hinder overall performance of translation engines in practice, as shown earlier in Table 1. Also, we calculate BLEU for the original training sentences that provide contexts for the CG test set (row 3). The model achieves 99.74 BLEU, further demonstrating that the performance degradation is mainly caused by the unseen compounds.
On Compositional Generalization of Neural Machine Translation
Instance-wise, 27.31% compounds are translated incorrectly. However, when aggregating all 5 contexts, 61.62% compounds suffer at least one incorrect translation. This suggests that a well-trained NMT model is not robust in translating compounds, though all atoms within them are highly frequent in   the training set. We also observe that the error rate of PP compounds, 37.72%, is much higher than the other two, 21.94% and 22.25%, which we will discuss in detail in the following section.
On Compositional Generalization of Neural Machine Translation
We conduct experiments to explore in what situations the model is error-prone by considering compound frequency, compound length, compound structure, atom frequency, atom co-occurrence, and the complexity of external context.
On Compositional Generalization of Neural Machine Translation
Intuitively, compounds with higher frequencies in the training set are easier to infer. We classify compounds according to their frequency levels, including many-shots (frequency higher than 10), fewshots (frequency from 1 to 10) and zero-shot, and show the error rate for each bucket in Figure 2. The model translates all the many-shots compounds correctly. For few-shot compounds, translation error rate increases to 5.00%, but is still much lower than zero-shot compounds with an error rate of 27.53%.
On Compositional Generalization of Neural Machine Translation
The result suggests the model is good at memorizing correspondence between sentence segments. However, the model deteriorates severely when test samples are unseen in the training set, which further confirms model's weakness in compositional generalization (Lake and Baroni, 2018).   Figure 4: Effect of atom frequency on compound translation error rate.
On Compositional Generalization of Neural Machine Translation
As shown in Figure 3, the error rate grows with the increase of compound length (i.e., the number of atoms in a compound). Only 4.50% of the shortest compounds are translated incorrectly, each of which consists of a determiner and a noun. The error rate increases to 13.72% when the compound length grows to 3 atoms (e.g., "the smart lawyer").
On Compositional Generalization of Neural Machine Translation
The longest compounds contain a determiner, a noun, an adjective, a modifier and a preposition or verb in each of them, e.g., "taking every special chair he liked". The error rate increases to 36.63%, demonstrating that it is more difficult to generalize in longer compounds, which contain richer semantic information. We conjecture that if the range of compound is further expanded, the error rate will be much higher.
On Compositional Generalization of Neural Machine Translation
We empirically divide compounds into multiple groups according to the minimum frequency of their atoms, where each group consists of similar numbers of compounds. The intuition is that the atom with low frequency might be difficult to translate and therefore hinders the whole compound translation. We fix the compound length to 3 in order to reduce effects of compound length. As shown in Figure 4, the error rate has no strong correlation with the atom frequency. This can be because all atoms in our corpus are simple and relatively frequent and thus it is easy for the NMT model to memorize the semantics of most atoms. Therefore, simply increasing atom frequency does not enhance model's generalization ability of novel compounds. We observe similar patterns for compounds of other lengths (Appendix A).
On Compositional Generalization of Neural Machine Translation
Although the NMT model may never see a compound, there can exist many local segments where atoms co-occur. For example, in the unseen compound "the smart lawyer", "smart" and "lawyer" may occur within some training sentences. Intuitively, the compounds of which atoms co-occur more frequently may be translated better. We calculate pointwise mutual information (PMI) and compare error rates of compounds with positive or negative mean PMI scores (MPMI):
On Compositional Generalization of Neural Machine Translation
where a i is the i-th atom in the compound C, N is the compound length, M is the number of possible combinations of two atoms, and PMI score is computed as:
On Compositional Generalization of Neural Machine Translation
where the probabilities p(a i ) and p(a i , a j ) are obtained by dividing the number of n-grams in which one word or both words occur by the total number of n-grams 4 . We divide compounds into 4 groups by their length and compare error rates within each group. As shown in Figure 5, across all groups, the error rates with positive mean PMI scores are lower than those with negative ones, verifying our hypotheses. 4 We use 5-gram here Error Rate Pattern # Figure 6: Compound translation error rates of different patterns. Figure 6 shows the error rates of all compound patterns in Table 3. The MOD atom exerts salient influence on translation error rate. The error rate of compounds with MOD is 19.78% higher than those without on average. In contrast, adding ADJ into compounds only increases error rate by 2.66%. The major difficulty caused by MOD is word reordering. One can translate "the small dog" monotonically without adjusting word order. However, compounds like "the dog he liked" require the model to recognize "he liked" as MOD and put its translation before that of "the dog" in Chinese. We find many cases where the model translates such compounds without reordering or breaking the connection between nouns and modifiers. Across these groups, we can see that the error rate of NP (Pattern 1.*) is generally lower than that of VP (Pattern 2.*) and PP (Pattern 3.*). Such phenomenon is more obvious for the patterns without MOD. The reason is that compounds in Pattern 1.* are generally shorter and contain less semantic and syntactic information. However, the error rates of Pattern 2.3 and 2.4 are lower than other patterns with MOD (i.e., Pattern 1.3, 1.4, 3.3 and 3.4), indicating the model performs better in "V+DET(+ADJ)+NN+MOD". This can be because under certain situations the MOD can be useful for correctly translating verbs, which are more commonly seen in the training set, e.g., "found the chair on the floor".
On Compositional Generalization of Neural Machine Translation
We also observe that compounds of PP (Pattern 3.*) are more difficult to translate compared with VP (Pattern 2.*), although both types of compounds share the same compound length. In the training set, verbs typically have consistent translations, whereas the meanings of prepositions vary with contexts. Therefore prepositional compounds are more difficult to translate as more context infor- mation is required to ground their meanings.
On Compositional Generalization of Neural Machine Translation
Due to the nature of NMT, the semantic representation of each compound is context-aware. Intuitively, translation of compounds is also influenced by external context, which is sentential in our case but can also be document-level in practice. We investigate effects of context lengths and sentence comprehension difficulty. In particular, the context length is calculated by subtracting the sentence length by the number of words in the compound. Comprehension difficulty of the training sentences which provide contexts, is quantified by the dependency distance (Liu, 2008):
On Compositional Generalization of Neural Machine Translation
where N is the number of words in the sentence and D i is the dependency distance of the i-th syntactic link of the sentence.
On Compositional Generalization of Neural Machine Translation
The results are shown in Figure 7. The translation error rate increases stably with the context length as well as the dependency distance. These observations demonstrate that the generalization for novel compounds correlates strongly with context complexity. Sentences with higher dependency distances are harder for model to comprehend during training. Given that our test sentences are restricted to 20 words, compositional generalization can be more challenging in practice where average sentence lengths can be much longer.
On Compositional Generalization of Neural Machine Translation
We proposed a dedicated parallel dataset for measuring compositional generalization of NMT and quantitatively analyzed a Transformer-based NMT model manually. Results show that the model exhibits poor performance on novel compound translation, which demonstrates that the NMT model suffers from fragile compositionality, and it can be easily overlooked under transitional metrics. To the best of our knowledge, we are the first one to propose a practical benchmark for compositionality of NMT, which can be a testbed for models tailored for this specific problem.
On Compositional Generalization of Neural Machine Translation
As mentioned, we collected our data from Story Cloze Test and ROCStories Corpora that all are public to academic use, and they contain no sensitive information (Mostafazadeh et al., 2016(Mostafazadeh et al., , 2017. The legal advisor of our institute confirms that the sources of our data are freely accessible online without copyright constraint to academic use. Our data construction involves manual annotation. Annotators were asked to post-edit machine translation and filter out samples that may cause ethic issues, which do not involve any personal sensitive information.
On Compositional Generalization of Neural Machine Translation
We hired 4 annotators who have degrees in English Linguistics or Applied Linguistics. Before formal annotation, annotators were asked to annotate 100 samples randomly extracted from the dataset, and based on average annotation time we set a fair salary (i.e., 32 dollars per hour) for them. During their training annotation process, they were paid as well. 
On Compositional Generalization of Neural Machine Translation
For compounds of other lengths, we also compute their error rates with respect to minimum atom frequency. As shown in Figure 8, 9 and 10, the error rate does not correlates with atom frequency across all compound lengths.  34  49  59  61  67  71  73  79  84  89  91  106  107  135  174  183  186  188  189  190  216  236  238  265  275  304  307  338  379  404  405  513  523 Error Rate Atom Frequency  Table 7 and Table 8 lists statistics of several monolingual data sources, compared with the data source (ROC-Filter) used in constructing the CoGnition dataset. We can see that our dataset has both shorter sentences and vocabulary made up of more frequent words.   
On Compositional Generalization of Neural Machine Translation
Part of the lexicon for automatic evaluation is shown in Table 9.  
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Human intelligence exhibits systematic compositionality (Fodor & Pylyshyn, 1988), the capacity to understand and produce a potentially infinite number of novel combinations of known components, i.e., to make "infinite use of finite means" (Chomsky, 1965). In the context of learning from a set of training examples, we can observe compositionality as compositional generalization, which we take to mean the ability to systematically generalize to composed test examples of a certain distribution after being exposed to the necessary components during training on a different distribution.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Humans demonstrate this ability in many different domains, such as natural language understanding (NLU) and visual scene understanding. For example, we can learn the meaning of a new word and then apply it to other language contexts. As Lake & Baroni (2018) put it: "Once a person learns the meaning of a new verb 'dax', he or she can immediately understand the meaning of 'dax twice' and 'sing and dax'." Similarly, we can learn a new object shape and then understand its compositions with previously learned colors or materials (Johnson et al., 2017;Higgins et al., 2018).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In contrast, state-of-the-art machine learning (ML) methods often fail to capture the compositional structure that is underlying the problem domain and thus fail to generalize compositionally Bastings et al., 2018;Loula et al., 2018;Russin et al., 2019;Johnson et al., 2017). We believe that part of the reason for this shortcoming is a lack of realistic benchmarks that comprehensively measure this aspect of learning in realistic scenarios.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
As others have proposed, compositional generalization can be assessed using a train-test split based on observable properties of the examples that intuitively correlate with their underlying compositional structure. Finegan-Dollak et al. (2018), for example, propose to test on different output patterns than are in the train set, while Lake &  propose, among others, to split examples by output length or to test on examples containing primitives that are rarely shown during training. In this paper, we formalize and generalize this intuition and make these contributions:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• We introduce distribution-based compositionality assessment (DBCA), which is a novel method to quantitatively assess the adequacy of a particular dataset split for measuring compositional generalization and to construct splits that are ideally suited for this purpose (Section 2).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• We present the Compositional Freebase Questions (CFQ) 1 , a simple yet realistic and large NLU dataset that is specifically designed to measure compositional generalization using the DBCA method, and we describe how to construct such a dataset (Section 3).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• We use the DBCA method to construct a series of experiments for measuring compositionality on CFQ and SCAN  and to quantitatively compare these experiments to other compositionality experiments (Section 4).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• We analyze the performance of three baseline ML architectures on these experiments and show that these architectures fail to generalize compositionally, and perhaps more surprisingly, that compound divergence between train and test sets is a good predictor of the test accuracy (Section 5).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Like other authors, we propose to measure a learner's ability to generalize compositionally by using a setup where the train and test sets come from different distributions. More specifically, we propose a setup where each example is obtained by composing primitive elements (atoms), and where these atoms are similarly represented in the train and test sets while the test set contains novel compounds, i.e., new ways of composing the atoms of the train set.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
As a simple illustrative scenario, consider the task of answering simple questions such as "Who directed Inception?" and "Did Christopher Nolan produce Goldfinger?". In this scenario, the atoms intuitively correspond to the primitive elements that are used to compose those questions, such as the predicates "direct(ed)" and "produce(d)", the question patterns "Who [predicate] [entity]" and " Did [entity1] [predicate] [entity2]", and the entities "Inception", "Christopher Nolan", etc. The compounds on the other hand correspond to the combinations of these atoms that appear in the various examples: "Who directed [entity]?", "Did Christopher Nolan [predicate] Inception?", etc.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
To measure compositional generalization on such a task, one might therefore use the questions "Who directed Inception?" and "Did Christopher Nolan produce Goldfinger?" as training examples while testing on questions such as "Did Christopher Nolan direct Goldfinger?" and "Who produced Inception?" because the atoms are identically represented in the train and test sets while the compounds differ.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
To make this intuition more precise, we focus on datasets such as CFQ (introduced in Section 3) and SCAN (Lake & Baroni, 2018), where each example can be created from a formal set of rules by successively applying a number of these rules. In this case, the atoms are the individual rules, while the compounds are the subgraphs of the directed acyclic graphs (DAGs) that correspond to the rule applications. (See Sections 3 and 4 for more details.)
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We use the term compositionality experiment to mean a particular way of splitting the data into train and test sets with the goal of measuring compositional generalization. Based on the notions of atoms and compounds described above, we say that an ideal compositionality experiment should adhere to the following two principles:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
1. Similar atom distribution: All atoms present in the test set are also present in the train set, and the distribution of atoms in the train set is as similar as possible to their distribution in the test set. 2. Different compound distribution: The distribution of compounds in the train set is as different as possible from the distribution in the test set.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The second principle guarantees that the experiment is compositionally challenging in the sense that it tests the learner on compounds that are as different as possible from the compounds used during training. The first principle aims to guarantee that the experiment is exclusively measuring the effect of the difference in the way atoms are composed to form compounds (rather than some related but different property such as domain adaptation on the distribution of the atoms).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
To determine to which degree a certain experiment adheres to these principles, we use the following formalization. For a sample set T , we use F A (T ) to denote the frequency distribution of atoms in T and F C (T ) for the weighted frequency distribution of compounds in T , which correspond to the subgraphs of the rule application DAGs. For practicality, we do not consider all subgraphs of rule application DAGs when computing the compound divergence. Instead, we first generate a large subset G of subgraphs, then weight them in context of their occurrence, and keep only the ones with highest sum of weights. The purpose of the weighting is to avoid double-counting compounds that are highly correlated with some of their super-compounds. We achieve this by calculating the weight of G ∈ G in a sample as w(G) = max g∈occ(G) (1 − max G :g≺g ∈occ(G ) P (G |G)), where occ(G) is the set of all occurrences of G in the sample, ≺ denotes the strict subgraph relation, and P (G |G) is the empirical probability of G occurring as a supergraph of G over the full sample set. See Appendix L.4 for example subgraphs and more details on the weighting.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We measure divergence (or similarity) of the weighted distributions using the Chernoff coefficient et al., 1989). For the atom divergence, we use α = 0.5, which corresponds to the Bhattacharyya coefficient and reflects the desire of making the atom distributions in train and test as similar as possible. For the compound divergence, we use α = 0.1, which reflects the intuition that it is more important whether a certain compound occurs in P (train) than whether the probabilities in P (train) and Q (test) match exactly. This allows us to formally define as follows the notions of compound divergence D C and atom divergence D A of a compositionality experiment consisting of a train set V and a test set W :
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Based on these principles, we suggest to use as a preferred compositionality benchmark for a given dataset the accuracy obtained by a learner on splits with maximum compound divergence and low atom divergence (we use D A ≤ 0.02). See Section 4 for details about how to construct such splits.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We present the Compositional Freebase Questions (CFQ) as an example of how to construct a dataset that is specifically designed to measure compositional generalization using the DBCA method introduced above. CFQ is a simple yet realistic, large dataset of natural language questions and answers that also provides for each question a corresponding SPARQL query against the Freebase knowledge base (Bollacker et al., 2008). This means that CFQ can be used for semantic parsing (Berant et al., 2013;Yao & Van Durme, 2014), which is the task that we focus on in this paper. Saxton et al. (2019) describe a number of benefits for automated rule-based dataset generation, including scalability, control of scope, and avoidance of human errors. Beyond these benefits, however, such an approach is particularly attractive in the context of measuring compositional generalization using the DBCA method, as it allows us to precisely track the atoms (rules) and compounds (rule applications) of each example by recording the sequence of rule applications used to generate it.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Since the way we measure compositionality depends on how the examples can be broken down into atoms and compounds, we design the generation rules so as to have few and meaningful atoms. More precisely, we aim to have as few rules as possible so that the richness of the examples comes from composing them, which yields a large variety of compounds (enabling a large range of different compound divergences) while making it easy to obtain similar distributions of atoms. Also, we aim to make our rules truly "atomic" in the sense that the behavior of any rule is independent of the context where it is applied (e.g., rules may not contain "if-then-else" constructs).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In order to minimize the number of rules, we use an intermediate logical form that serves as a uniform semantic representation with relatively direct mappings to natural language and SPARQL. Our rules thus fall into the following four categories (a selection of rules is provided in Appendix M):
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
1. Grammar rules that generate natural language constructs and corresponding logical forms. 2. Inference rules that describe transformations on logical forms, allowing us to factor out transformations that are independent of specific linguistic and SPARQL constructs. 3. Resolution rules that map constructs of the logical form to SPARQL constructs. Figure 1: Generating a natural language question together with its SPARQL query using four types of rules. One (of potentially many) intermediate logical forms is also shown. 4. Knowledge rules that supply logical form expressions that are universally applicable. Other rules can be kept more generic by parameterizing them on knowledge.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
These rules define a language of triples of the form question, logical form, SPARQL query . Our generation algorithm produces such triples in a mixed top-down and bottom-up fashion. We first apply grammar rules and inference rules to produce the natural language questions and their semantics in our logical form. Then we apply resolution rules to obtain the SPARQL query. See Figure 1 for an illustration. In addition, the generator produces a normalized, directed acyclic graph (DAG) of rule applications that corresponds to the normalized program that generated the triple. (Appendix L shows an example.) Edges of this DAG represent dependencies among the rule applications, and the normalization ensures that a certain rule combination is represented using the same DAG across all the examples where it occurs.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The described approach can generate a potentially infinite set of questions, from which we first sample randomly and then subsample (to maximize the overall diversity of rule combinations while keeping a uniform distribution over complexity). We measure the diversity of rule combinations using the empirical entropy of a weighted subset of the rule application DAGs, and we use the number of rule applications as a measure of the complexity of an example. We also limit the maximum example complexity such that the questions remain relatively natural. Table 1 shows examples of generated questions at varying levels of complexity. An example of a complete data item is shown in Appendix A, a more detailed data quality analysis is presented in Appendix B, and the generation algorithm is discussed in more detail in Appendix K.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Input and output. While the primary focus of the dataset is semantic parsing (natural language question to SPARQL query), we also provide natural language answers for each question. This allows the dataset to be used in a text-in-text-out scenario as well (see Appendix A).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Ambiguity. We largely avoid ambiguity in the questions. In particular, we make sure each name is used to refer to exactly one entity, and we avoid different possible parse trees, different interpretations of plurals, and the need for disambiguation that requires semantic knowledge.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Scope. We select the following language features as compositional building blocks: open questions and closed questions; subordinate clauses; active and passive voice; conjunctions of verb phrases and of noun phrases; possessives with roles ("X's parent"); adjectives; and type restrictions. For knowledge base features, we select roles, verbs, types, and adjectives from domains that are well-represented in Freebase and that can be combined easily. We start from the popular movie do-  main (e.g., directing, producing, editor, sequel) and extend this with personal relations (e.g., parent, spouse, sibling), companies (e.g., founding, employer), and adjectives (e.g., gender, nationality).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Logical form and grammar. For the internal logical form, we adopt a variation of the description logic EL (Baader et al., 2003;2005), augmented with additional constructors (see Appendix I) to more easily map to certain linguistic structures. For the grammar rules, we use a unificationbased grammar syntax similar to that used in the Prolog extension GULP 3.1 (Covington, 1994), with addition of support for disjunction, negation, absence, and default inheritance of features for compactness of representation.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Once an example is generated by the CFQ rules, it still contains entity placeholders instead of Freebase machine ids (MIDs). For the task of semantic parsing, the examples could theoretically be used as-is, as our avoidance of semantic ambiguity means that a learner should not need knowledge of the specific entity in order to parse the question. To make the questions natural, however, we apply an additional step of replacing the placeholders with appropriate specific entities. To do this we first execute the generated SPARQL query against Freebase. This returns a set of candidate MID combinations that satisfy the query and can be used as substitutes. If the set is empty, we abandon the generated question candidate as unnatural. Otherwise, we pick one combination at random to yield a question with positive answer. In the case of a closed question, we also generate a variation that yields the answer "No", which we do by mixing in MIDs from another substitution (or a more generic replacement if that fails) to keep the question as plausible-sounding as possible. We then randomly choose either the question with positive or with negative answer, to avoid spurious correlations between question structure and yes/no answer.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Semantic and structural filtering. Even among the questions that can be satisfied in Freebase, there are some that are meaningful but somewhat unnatural, such as "Was Strange Days directed by a female person whose gender is female?". We automatically filter out such unnatural questions using semantic and structural rules. Note that since we do not require a learner to identify such questions, we do not track these filtering rules.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Release and statistics. CFQ contains 239,357 English question-answer pairs that are answerable using the public Freebase data. (The data URL is not yet provided for anonymous review.) We include a list of MIDs such that their English names map unambiguously to a MID. Table 2(a) summarizes the overall statistics of CFQ. Table 2(b) uses numbers from (Finegan-Dollak et al., 2018) and from an analysis of WebQuestionsSP (Yih et al., 2016) and ComplexWebQuestions (Talmor & Berant, 2018) to compare three key statistics of CFQ to other semantic parsing datasets (none of which provide annotations of their compositional structure). CFQ contains the most query patterns by an order of magnitude and also contains significantly more queries and questions than the other datasets. Note that it would be easy to boost the raw number of questions in CFQ almost arbitrarily by repeating the same question pattern with varying entities, but we use at most one entity substitution per question pattern. Appendix C contains more detailed analyses of the data distribution. 
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The DBCA principles described in Section 2.1 enable a generic and task-independent method for constructing compositionality experiments. To construct such an experiment for a dataset U and a desired combination of atom and compound divergences, we use an iterative greedy algorithm that starts with empty sets V (train) and W (test), and then alternates between adding an example u ∈ U to V or W (while maintaining the desired train/test ratio). At each iteration, the element u is selected such that D C (V W ) and D A (V W ) are kept as closely as possible to the desired values. To reduce the risk of being stuck in a local optimum, we also allow removing examples at certain iterations.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In general, there are many different splits that satisfy a desired compound and atom divergence. This reflects the fact that a certain compound may either occur exclusively in the train set or the test set, or it may occur in both of them because the split may have achieved the desired compound divergence by separating other (possibly orthogonal) compounds. Our greedy algorithm addresses this by making random choices along the way, starting with picking the first example randomly.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
For the goal of measuring compositional generalization as accurately as possible, it is particularly interesting to construct maximum compound divergence (MCD) splits, which aim for a maximum compound divergence at a low atom divergence (we use D A ≤ 0.02). Table 3 compares the compound divergence D C and atom divergence D A of three MCD splits to a random split baseline as well as to several previously suggested compositionality experiments for both CFQ and the existing SCAN dataset (cf. Section 5.3). The split methods (beyond random split) are the following:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Output length: Variation of the setup described by Lake & Baroni (2018)  The MCD splits achieve a significantly higher compound divergence at a similar atom divergence when compared to the other experiments. The reason for this is that, instead of focusing on only one intuitive but rather arbitrary aspect of compositional generalization, the MCD splits aim to optimize divergence across all compounds directly.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Interestingly, the MCD splits still correlate with the aspects of compositional generalization that are targeted by the other experiments in this table. As shown in the four right columns of Table 3, for each MCD split, the train set V contains on average shorter examples than the test set W (measured by the ratio of average lengths), and V also contains only a small fraction of the input and output patterns used in W (measured by the fraction of patterns covered). However, these correlations are less pronounced than for the experiments that specifically target these aspects, and they vary significantly across the different MCD splits.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
This illustrates that MCD splits are comprehensive in the sense that they cover many different aspects of compositional generalization, especially when looking at multiple of them. It also means that whether a certain example ends up in train or test is not determined solely by a single criterion that is immediately observable when looking at the input and output (such as length). As we show in Appendix D.1, this generally makes the examples in train and test look fairly similar.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We use three encoder-decoder neural architectures as baselines: (1) LSTM+attention as an LSTM (Hochreiter & Schmidhuber, 1997)  We tune the hyperparameters using a CFQ random split, and we keep the hyperparameters fixed for both CFQ and SCAN (listed in Appendix E). In particular the number of training steps is kept constant to remove this factor of variation. We train a fresh model for each experiment, and we replicate each experiment 5 times and report the resulting mean accuracy with 95% confidence intervals.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Note that while we construct test and validation sets from the same distribution, we suggest that hyperparameter tuning should be done on a random split (or random subset of the train set) if one wants to measure compositional generalization of a model with respect to an unknown test distribution as opposed to an architecture with respect to a known test distribution. Tuning on a validation set that has the same distribution as the test set would amount to optimizing for a particular type of compound divergence and thus measure the ability for a particular architecture to yield models that can be made to generalize in one particular way (through leaking information about the test set in the hyperparameters).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Similarly to Finegan-Dollak et al. (2018), we anonymize the Freebase names and MIDs in the textual input and the SPARQL output, respectively, by replacing them with a placeholder (e.g., "M0" for the first MID). This removes the need for two learning sub-tasks that are orthogonal to our focus: named entity recognition and learning that the MIDs are patterns that need to be copied. An example input-output (question-query) pair then looks like the following: 'Was M0 a screenwriter' → 'select count(*) where {M0 a ns:film.writer}'.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The main relation we are interested in is the one between compound divergence of the data split and accuracy. Specifically, we compute the accuracy of each model configuration on a series of divergence-based splits that we produce with target compound divergences that span the range between zero and the maximum achievable in 0.1 increments (while ensuring that atom divergence does not exceed the value of 0.02). For each target divergence, we produce at least 3 different splits with different randomization parameters (compare Section 4). For comparison, we also compute accuracies on the other splits shown in Table 3.  
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The mean accuracies of the three architectures on CFQ are shown in Figure 2(a) and Table 4. We make three main observations:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• All models achieve an accuracy larger than 95% on a random split, and this is true even if they are trained on 10 times fewer training instances (see Appendix H for a more detailed analysis on the performance with varying training size). • The mean accuracy on the MCD splits is below 20% for all architectures, which means that even a large train set (about 96k instances) with a similar distribution of atoms between train and test is not sufficient for these architectures to perform well on the test distribution. • For all architectures, there is a strong negative correlation between the compound divergence and the mean accuracy.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
This suggests that the baseline models are able to capture the superficial structure of the dataset, but fail to capture the compositional structure. We find it surprising that varying the compound divergence gives direct control of the (mean) accuracy, even though the examples in train and test look similar (see Appendix D.1). This means that compound divergence seems to capture the core difficulty for these ML architectures to generalize compositionally.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Note that the experiment based on output-length exhibits a worse accuracy than what we would expect based on its compositional divergence. One explanation for this is that the test distribution varies from the training distribution in other ways than compound divergence (namely in output length and a slightly higher atom divergence), which seems to make this split particularly difficult for the baseline architectures. To analyze the influence of the length ratio further, we compute the correlation between length ratios and accuracy of the baseline systems and compare it to the correlation between compound divergence and accuracy. We observe R 2 correlation coefficients between 0.11 and 0.22 for the input and output length ratios and between 0.81 and 0.88 for the compound divergence. This shows that despite the known phenomenon that the baseline systems struggle to generalize to longer lengths, the compound divergence seems to be a stronger explanation for the accuracy on different splits than the lengths ratios.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Error analysis. We perform an analysis of the errors for the split MCD 1 (the first MCD split that we constructed, with more details provided in Appendix F). We observe accuracies between 29%
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
and 37% on the test set of this particular split. Qualitatively, all three systems seem to make similar errors at this point (68% of errors are on the same samples). They make more errors for longer sequences and predict about 20% too short output when they make an error. The most common category of error is the omission of a clause in the output (present in 43%-49% of the test samples), e.g.: (1) Omitted conjunctions: for the input "What spouse of a film producer executive produced and edited M0, M1, and M2?" the best system ignores "executive produced" in the output. (2) Omitted adjectives: for the input "Which female Spanish film producer was M3' s spouse?" the best system ignores the adjective "female".
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
To demonstrate the use of our analysis method on another dataset, we re-create the SCAN dataset (Lake & Baroni, 2018), which consists of compositional navigation commands (e.g, 'turn left twice and jump') mapped to corresponding action sequences (e.g., 'LTURN LTURN JUMP'). We use the original grammar while tracking the rule applications used for the construction of each inputoutput pair. This enables us to compare the compositional generalization abilities of the baseline systems on this dataset in a novel way.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Figure 2(b) shows the graphs for the SCAN data set in the same setup as Figure 2(a) does for CFQ. We observe that the compound divergence again is a good predictor for the mean accuracy for all three architectures. One difference is that for SCAN the systems are able to attain accuracies close to 100% for compound divergences up to around 0.2, which is not the case for CFQ. This seems to be in line with the fact that overall CFQ is a more complex task than SCAN: the total number of rules used in generating SCAN is only 38 in comparison to 443 rules in the construction of CFQ.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Appendix G provides a comparison to other experiments presented in previous work, including experiments that have significantly different atom distributions. We observe that this generally causes lower accuracies but does not break the correlation between accuracy and compound divergence.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
To measure compositional generalization for semantic parsing to SQL, Finegan-Dollak et al. (2018) propose to ensure that no SQL query pattern occurs in both the train and the test set ("query split"), and they provide such splits for several data sets. By evaluating several ML architectures the authors confirm that this query-pattern split is harder to learn than a conventional split.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Lake & Baroni (2018) introduce the SCAN dataset, and several publications provide interesting analyses of compositional generalization using it (Bastings et al., 2018;Loula et al., 2018). Russin et al.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
(2019) discuss a particular extension of a seq2seq model that is effective in handling difficult SCAN sub-tasks by separating semantic and syntactic information during learning. Our contributions extend the analyses on the SCAN data in several ways: CFQ provides richer annotations and covers a broader subset of English than the SCAN dataset, and we propose a comprehensive score for assessing aggregate compositionality of a system on a given task.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The mathematics dataset (Saxton et al., 2019) is a large, automatically generated set of 112M samples in 56 separated sub-tasks. The authors present data and experiments that share common goals with our approach, but focus on mathematical reasoning instead of natural language. Our breakdown of generation rules per train sample is more fine-grained, which allows a more precise compositional generalization analysis. Being automatically generated also links our approach to datasets such as the bAbI tasks (Weston et al., 2016), which however do not focus on compositional generalization.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
A dataset related to CFQ is ComplexWebQuestions (Talmor & Berant, 2018), which consists of complex questions that are automatically generated from simpler sub-questions in WebQuestionsSP (Yih et al., 2016) and then reworded manually. While these datasets can be used for semantic parsing, we did not find them suitable for a thorough compositionality analysis because a consistent annotation with the compositional structure would be hard to obtain. Other approaches to semi-automatic dataset creation also use paraphrasing (Wang et al., 2015;Su et al., 2016). Johnson et al. (2017) introduce the generated CLEVR dataset, which shares common goals with our work applied in the area of visual reasoning. The dataset's functional programs capture some of the structural information of the questions and are linked one-to-many to the 423 question patterns used. The authors specifically investigate generalization to new combinations of visual attributes in one experiment which uses a particular train-test split based on the colors used. Mao et al. (2019) propose a neural-symbolic architecture and discuss promising results on additional specific splits of the CLEVR data, e.g. based on object counts and program depth. Hudson & Manning (2018) describe how the application of compositional attention networks to the CLEVR data leads to structured and data-efficient learning. Hudson & Manning (2019a) present a large, compositional, generated visual question answering data set with functional programs, on which neural state machines achieve good performance (Hudson & Manning, 2019b). The use of specific splits between train and test data also occurs in the context of visual data. E.g., Agrawal et al. (2018) propose a greedy split algorithm to maximize the coverage of test concepts in the train set while keeping question-type/answer pairs disjoint and observe performance degradation of existing approaches. Bahdanau et al. (2019) introduce a synthetic visual question answering dataset called SQOOP, which is used to test whether a learner can answer questions about all possible object pairs after being trained on a subset.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
While these datasets are very interesting, the additional annotation that we provide in CFQ indicating the exact rule trees needed to link input and output makes additional analyses regarding compositionality possible. Our analyses go beyond many of the presented discussions (that mostly focus on accuracy regarding particular holdouts) in formalizing an approach that uses the atom and compound divergences to measure compositionality.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
A number of ML approaches have been developed for semantic parsing. Miller et al. (2016) propose Key-Value Memory Networks -neural network-based architectures that internalize a knowledge base into the network -and introduce the WikiMovies dataset. Zhang et al. (2018) develop an endto-end architecture that can handle noise in questions and learn multi-hop reasoning simultaneously. They introduce the MetaQA benchmark that is based on WikiMovies but uses a set of only 511 question patterns (mod entities) shared between train and test.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
With regards to studying compositionality in ML, Battaglia et al. (2018) argue that combinatorial generalization should be a top priority to achieve human-like abilities. Andreas (2019) discusses measuring the compositionality of a trained representation, e.g. of a learned embedding. The author suggests to use a tree reconstruction error that is based on how well the oracle derivation of the input matches the structure that can be derived on the representations. Higgins et al. (2018) discuss an architecture that enables the learning of compositional concept operators on top of learned visual abstractions. Chang et al. (2019) introduce the compositional recursive learner that "can generalize to more complex problems than the learner has previously encountered".
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In this paper we presented what is (to the best of our knowledge) the largest and most comprehensive benchmark for compositional generalization on a realistic NLU task. It is based on a new dataset generated via a principled rule-based approach and a new method of splitting the dataset by optimizing the divergence of atom and compound distributions between train and test sets. The performance of three baselines indicates that in a simple but realistic NLU scenario, state-of-the-art learning systems fail to generalize compositionally even if they are provided with large amounts of training data and that the mean accuracy is strongly correlated with the compound divergence.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We hope our work will inspire others to use this benchmark as a yardstick to advance the compositional generalization capabilities of learning systems and achieve high accuracy at high compound divergence. Some specific directions that we consider promising include applying unsupervised pretraining on the input language or output queries and the use of more diverse or more targeted learning architectures, such as syntactic attention (Russin et al., 2019). We also believe it would be interesting to apply the DBCA approach to other domains such as visual reasoning, e.g. based on CLEVR (Johnson et al., 2017).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In the area of compositionality benchmarks, we are interested in determining the performance of current architectures on the end-to-end task that expects a natural language answer given a natural language question in CFQ. We would like also to extend our approach to broader subsets of language understanding, including use of ambiguous constructs, negations, quantification, comparatives, additional languages, and other vertical domains. 
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The following shows an example data item including the question text in various forms, the answer, the SPARQL query in various forms, some tracked statistics, and the set of used rules (atoms) and the applied rule tree (compound). Some details are omitted, indicated by ellipses ('...').
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
"question": "Did Agustin Almodovar executive produce Deadfall", "questionWithBrackets": "Did [Agustin Almodovar] executive produce [Deadfall]", "questionWithMids": "Did m.04lhs01 executive produce m.0gx0plf", "questionPatternModEntities": "Did M0 executive produce M1", "questionTemplate": " Did [entity] [VP_SIMPLE] [entity]", "expectedResponse": "No", "sparql": "SELECT count( * ) WHERE {\nns:m.04lhs01 ns:film.producer.films_executive_produced ns: m.0gx0plf\n}", "sparqlPatternModEntities": "SELECT count( * ) WHERE {\nM0 ns:film.producer.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
films_executive_produced M1\n}", "sparqlPattern": "SELECT count( * ) WHERE {\nM0 P0 M1\n}", "complexityMeasures": { "parseTreeLeafCount": 5, "parseTreeRuleCount": 12 "sparqlMaximumChainLength": 2, "sparqlMaximumDegree": 1, "sparqlNumConstraints": 1, "sparqlNumVariables": 0, }, "aggregatedRuleInfo": { "ruleId": [ { "type": "SPARQL_GENERATION", "stringValue": "ENTITY_MID" }, { "type": "SPARQL_GENERATION", "stringValue": "GET_SET_TRUTH" }, { "type": "KNOWLEDGE", "stringValue": "FreebasePropertyMapping(RolePair(Executive producer, Executive producee), ' ns:film.producer.films_executive_produced')" }, { "type": "GRAMMAR_RULE", "stringValue": "YNQ=DID_DP_VP_INDIRECT" }, { "type": "GRAMMAR_RULE", "stringValue": "ACTIVE_VP=VP_SIMPLE" }, ... ], }, "ruleTree": { "ruleId": { "type": "SPARQL_GENERATION", "stringValue": "CONCEPT_TO_SPARQL" }, "subTree": [ { "ruleId": { "type": "GRAMMAR_RULE", "stringValue": "S=YNQ" }, "subTree": [ { "ruleId": { "type": "GRAMMAR_RULE", "stringValue": "YNQ=DID_DP_VP_INDIRECT" ...
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
During the development of our data generation pipeline, we manually checked the generated examples for quality. Below is a random selection of 50 examples of the final CFQ dataset (no cherrypicking was used). Brackets around [entity names] are provided just for ease of human reading. Manual checking also indicated that all questions are associated with the semantically correct SPARQL queries. However, because we rely on the data present in Freebase, there are three debatable questions which sound somewhat unnatural (3, 21, and 29, see further discussion below the list). Further discussion of the debatable questions:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The occurrence of the seemingly implausible combination of roles "spouse and parent" is due to incorrect data in Freebase, in which there are 502 entities asserted to be both the spouse and parent of other entities. For instance, "Anne Dacre" is both the spouse and parent of "Christopher Conyers". We can also find occasional occurrences in CFQ of other implausible role combinations, such as "parent and child", "spouse and sibling" etc., triggered by similar Freebase data issues.  
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The somewhat unnatural phrasing of "country's employee" occurs due to a modeling choice in Freebase, in which the same entity is used to represent both a country and the government of that country. This makes it possible for a country to employ a person.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The somewhat unnatural phrasing of "a character was influenced by" occurs due to a modeling choice in Freebase, in which when a film character is based on a real person, Freebase commonly uses the same entity to represent both. This makes "person" and "character" exchangeable in the questions where the person is also a film character.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
C DATA DISTRIBUTION ANALYSIS C.1 ANSWER FREQUENCIES Table 5 shows the most frequently occurring answers in CFQ. Not surprisingly, after the answers "Yes" and "No", entities related in Freebase to the domain of movies have highest frequency. Figure 3 illustrates how subsampling changes the distribution of questions in CFQ with different levels of complexity to become more even.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Subsampling increases the frequency of rarely used rules and rule combinations and decreases the frequency of commonly used ones. For rules, this is illustrated by Figure 4 which shows the ratio of Published as a conference paper at ICLR 2020  examples each rule appears in, before and after subsampling, in the order of their frequency. Figure 5 shows the same comparison for rule combinations.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Traditional compositionality experiments often use train-test splits based on observable properties of the input and output (e.g., input/output complexity, input/output patterns, and input/output feature holdouts). One consequence of this is that the difference between train and test examples is relatively easily observable "with the naked eye". The lists below illustrate that this is not usually the case for divergence-based splits. Similar to the random sample of the general data in Appendix B we provide a random sample of size 20 from both the train and test set here. Indeed, even for the MCD 1 split with a high divergence of 0.694, the 20 random samples of train and test questions shown below cannot easily be distinguished as they both contain the same kind of questions of different sizes.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Train samples from MCD 1 :  Figure 6 shows the frequency of atoms (upper graph) and compounds (lower graph) in the train and test sets of the maximum compound divergence split for the CFQ data. As the frequency of an atom resp. compound we use the fraction of examples it appears in. Both atoms and compounds are indexed primarily by their frequency in the train set, secondarily by their frequency in the test set, in decreasing order. For practical reasons we only look at a small subset of compounds here but we believe the analysis is representative.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We can see that the frequency of atoms in the two sets is very aligned and that all atoms from the test set appear in the train set. The frequency of compounds however is wildly different: While some invariably occur in both sets, the frequencies are often not aligned and most compounds appear only in either the train or the test set.  
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The experiments were run using the tensor2tensor framework (Vaswani et al., 2018) with some of the hyperparameters tuned using a random split of a previous, smaller version of the data set during development. We use the default hyperparameter sets publicly available in the tensor2tensor implementation (obtained from https://github.com/tensorflow/tensor2tensor) and override the tuned hyperparameters. The hyperparameters used are summarized in Table 6. Table 7 shows a more detailed analysis of the errors that the baseline models make on CFQ for MCD 1 (compare Section 5.2). The reported errors are bucketized into three main types: SPARQL property clause error, SPARQL filter clause error and malformed SPARQL query in the model's output. The total number of test set examples exhibiting any clause or filter error is reported (sum column), as well as the number of insertions (ins), deletions (del), and substitutions (sub) in the model's output with respect to the correct query. Property clause substitution errors are further subdivided into those where only the property itself is wrong while subject and object are correct (prop), those where the property is correct but either subject or object is wrong (node) and those where both the property and the subject or the object are wrong (both).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The accuracy metric requires the model response and the golden (correct) answer to be exactly equal to each other. Thus, a SPARQL query with the same clauses as the golden answer but in a different order or with some of the clauses appearing multiple times is also considered to be an error despite being equivalent to the golden answer in its meaning. The amount of such errors is relatively small though, accounting for 1.8%, 0.6% and 1.5% of total test set size for LSTM+Attention, Transformer and Universal Transformer respectively.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Below we qualitatively analyze a number of instances the models fail on. We anonymize the MIDs in the same way as the data is provided to the models (see Section 5). We first select queries on which all machine learning systems fail in all replicated runs (about 5k instances out of a total of about  12k), and then randomly select queries from this list. In the following we discuss a few cases in more detail. Note that, for readability, we use the following abbreviations for the SPARQL properties in Query 1: Analysis. The meaning of the SPARQL query generated by the system is "What sibling of M0 was a sibling of M1's parent?", which is incorrect. We next analyze the train set, in order to show that we believe enough information has been provided in the train set for the question to be answered correctly.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Some subqueries of the query and their occurrences are shown in Table 8. While the exact subquery "What sibling" does not occur at training, the two words have been shown separately in many instances: the subqueries "sibling of Mx", and "Mx's parent" occur 2,331 and 1,222 times, respectively. We can analyze this example in more detail by comparing parts of the rule tree of this example with those shown at training. As can be read from the  Table 9: Subqueries of "Did a male film director edit and direct M0 and M1?" and their occurrences in training.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• What costume designer did M1's parent employ?
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• What cinematographer was a film editor that M2 and M3 married?
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• What film director was a character influenced by M2? Analysis. The meaning of the inferred SPARQL query is "Did a male film director edit M0 and direct M0 and M1?". It thus seems the model 'forgets' to include the relation between the director and movie M1.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Looking at subqueries and their occurrence count (Table 9), we see again that various subqueries occur often during training. However, "edit and direct" have not been shown often together. When looking at the rule trees, we see that both conjunctions in the query occur often at training separately: " Did  [DetNP] and [DetNP]" does not occur at training. This may be the reason why all systems fail on this example, but at the same time we believe a compositional learner should be able to generalize correctly given the training instances. Some examples are:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Did a male film director that M3's parent married influence an art director?
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Did a film producer that played M2 edit and direct M1?
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Did a screenwriter edit and direct a sequel of M1
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Did a Chinese male film director edit M1 and M2? Figure 7: Accuracy and divergence measurements for splits of SCAN as used in other work (see text for details). The numbers in brackets show the train / full data-set ratio, and the atom divergence. Figure 7 shows a scatter plot of accuracy vs. compound divergence for the three baseline architectures (see Section 5) on existing splits of the SCAN data. These splits are discussed in (Lake & Baroni, 2018) and (Loula et al., 2018), and the exact split data is available. (Data splits obtained from https://github.com/brendenlake/SCAN). We map these splits onto the re-created SCAN data, which enables us to measure the atom and compound divergences. The authors present a total of six split experiments (some with several sub-experiments):
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• (Lake & Baroni, 2018):
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
simple (random) by action sequence length adding a primitive and adding a primitive along with complex combinations In the plot, we omit some data points that are too close to be distinguished easily. The point labels have the form '(abbreviated experiment name)<(parameter)>@(number of samples) (baseline system abbreviation) [(train set size fraction), (split atom divergence)]'. The train set size fraction is given as a percentage of the overall data size. The baseline system abbreviations are LSTM, T for Transformer, UT for Universal Transformer, T/UT where both transformer models are indistinguishable, and empty where all three systems perform indistinguishably. The abbreviated experiment name is one of the names in italics above.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We can observe a strong dependency of the accuracies on the compound divergence of the data split. Again, this seems to indicate that the compound divergence is correlated with accuracy for these baseline architectures. One difference to the data shown in Figure 2(b) is that for this set of experiments the accuracy drops faster with increasing compound divergence. One explanation for this effect is that the experiments are directly aimed at highlighting one specific potentially problematic scenario for learning. E.g. in the experiment 'primitive<jump>' (with very low accuracies for all three systems) the jump command is shown exactly in one combination (namely alone) in the training data while it occurs in all test examples in arbitrary combinations. This is reflected in the higher atom divergence value of 0.08 for this split, as well as in all other splits that exhibit a low accuracy at a low compound divergence in Figure 7. Note that Lake & Baroni (2018) already compare the experiment 'primitive<jump>' to the experiment 'primitive<turn left>' for which all three systems achieve a much higher accuracy. In their interpretation of this phenomenon, they mainly focus on the fact that in contrast to 'jump', the action 'turn left' is also generated by other inputs. We additionally observe that the latter experiment also has a slightly lower atom divergence of 0.07, a lower compound divergence, and it covers a much larger part of the data in the train set (94% vs. 63%).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
While the accuracies we observe for the 'primitive' experiments are very much in line with the results reported by Lake & Baroni (2018), we noticed a few interesting differences for other experiments: All three systems go to 100% accuracy on the fewshot task even for one example (while Loula et al. (2018) report a slowly increasing accuracy for the architecture they evaluate). On the other hand, both transformer models only reach 0% accuracy on the length split, while the LSTM obtains around 14% (which is in line with what previous work reports).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
DIVERGENCE, AND TRAINING SIZE Figure 2 shows for all baseline systems a strong correlation between accuracy and compound divergence for the chosen training sizes (96k for CFQ and 8k for SCAN). One interesting question is whether and how this correlation is changed for different training sizes. Figures 8 and 9 show that this correlation holds also for smaller training sizes but that the accuracy is generally somewhat lower for smaller training sizes.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
At the same time, we observe that the difference between accuracies of various training sizes gets smaller as the training size increases. This can be seen even more clearly in Figures 10 and 11, which plot the training size rather than the compound divergence on the x-axis. These figures show that the increase in accuracy flattens out significantly as we reach training size of about 80k for CFQ and about 6k for SCAN. This indicates that further increasing train set size may not be sufficient to do well on these compositionality experiments.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
To represent our logical form we use syntax of the description logic EL (Baader et al., 2003;2005) with additional concept and role constructors. These constructors do not have description logic semantics; instead, their meaning is completely determined by the set of generation rules of the CFQ dataset.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Let A be a concept name, C, C 1 , C 2 be concepts, R, R 1 , R 2 be roles, and v be a raw string. Then the following would be concepts:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
and the following would be roles:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Note that our logical form does not have roles other than those in a form of RolePair(C 1 , C 2 ).    New strings are generated by using a special function new_var($S). This function generates a unique string of the form ?x<N>, where N is a unique number, and assigns that string to variable $S. This string can later be used as a variable in a SPARQL constraint.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
This section describes the format of each of the rule types we use for generating the CFQ dataset, in the form in which they appear in the rules index in Appendix M.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
General formatting conventions shared across all rule types:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Variable names are prefixed by '$'. Example: $X.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
(Exception: In grammar rules, while variables standing for constants are prefixed by '$', variables standing for logical forms are prefixed by '_'. Example: _action.) • Concept names are written in camel case. Example: FilmProducer.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Names of functions that output logical forms (concepts, roles, or knowledge) are also written in camel case. Examples: DropDependency, BoundRolePairs, RolePair. • Names of functions that output string literals or which are used for converting logical forms to SPARQL are written in lowercase with underscores. Examples: def2sparql, get_specializations, new_var. • String literals are enclosed in single quotes. Example: 'ns:film:director'.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The CFQ grammar is a unification-based grammar of recursive rewriting rules used to generate pairs of strings and their corresponding logical form. For an introductory overview of unification-based grammars including several popular variations, see Shieber (2003). The rules in the CFQ grammar follow a similar syntax in particular to that used in the Prolog extension GULP 3.1 (Covington, 1994), with the addition of support for disjunction, negation, absence, and default inheritance of features, and with minor differences in formatting described below.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Properties shared between the CFQ grammar syntax and that of (Covington, 1994) include the following:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Grammar rules are notated as variations of context-free phrase-structure rules of the form T 0 → T 1 ... T n , where each of the syntactic non-terminals and terminals T 0 ... T n are augmented with feature lists in parentheses. • Each grammar rule can be interpreted as specifying how a feature structure (with logical form) that is unifiable with the lefthand side can be re-written to the sequence of features structures (with logical form) indicated on the righthand side. • Features are represented as attribute-value pairs separated by a colon (i.e., attribute:value). • Shared values in feature structures are represented through the use of variables.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Specifically, in the rules index, CFQ grammar rules are described in the format
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Each T i is a syntactic category (syntactic nonterminal) or a string literal (syntactic terminal). • Each L i for i ∈ [1, n] is either a variable representing a logical form or an empty string.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In the case when L i is an empty string, we allow dropping the trailing slash from the T i (F i )/L i expression, resulting in just T i (F i ). • L 0 is a logical form expressed in terms of L 1 ...L n .
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• Each F i is a comma-separated feature list of the form (attribute 1 :value 1 , ..., attribute k :value k ). In the case where F i is empty, we allow dropping the parentheses from the T i (F i ) expression, resulting in just T i .
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• H is either an empty string or one of the variables L i for i ∈ [1, n], indicating that F 0 default inherits the features of F i (the syntactic "head"). In the case where H is an empty string, we allow dropping the brackets from the T 0 (F 0 )[H] expression, resulting in just T 0 (F 0 ).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Note that while the above notation adopts the convention of splitting out the syntactic category and logical form from the feature list for visual prominence and to highlight the relationship to its context-free phrase-structure rule core, behaviorally it is identical to adding two more features to the feature list (we can call them, for example, cat and sem) to represent the syntactic category and logical form.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
This means that, for example, the rule Disjunction of features. Similarly to (Karttunen, 1984), we allow disjunctive feature specifications, which we denote by separating the alternative values with a pipe ('|'). The feature specification (form:gerund|infinitive) would thus unify with either (form:gerund) or (form:infinitive), but not with (form:past_participle).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Absence of features. We use a special atomic value _none_ to indicate that a given feature must either be absent or else explicitly set to the value _none_. The feature specification (subject:_none_, object:yes) would thus unify with either (object:yes) or (subject:_none_, object:yes), but not with (subject:yes, object:yes).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Negation of features. Similarly to (Karttunen, 1984), we allow negated feature specifications, which we denote by prefixing the attribute with a minus sign ('-'). The feature specification (-form:gerund|infinitive) would thus unify with (form:past_participle) or (form:_none_), but not with (form:gerund) or (form:infinitive). In general, a feature specification of the form (-attribute:v 1 |...|v j ) can be considered a notational shorthand for (attribute:v j+1 |...|v k |_none_), where v j+1 |...|v k is an enumeration of all possible values of the feature attribute other than v 1 |...|v j .
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Default inheritance of features. If the lefthand side term is notated as T 0 (F 0 )[H], with H equal to one of the variables L i for i ∈ [1, n], then this is interpreted as a notational shorthand for augmenting both F 0 and F i with an additional list of attribute-value pairs (a 1 :$v 1 , ..., a k :$v k ), where a 1 ...a k are all of the attributes listed in F i that were not originally listed in F 0 .
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Unification of logical forms. As described in Appendix I, we represent logical forms using a variation of description logic, rather than using feature structures. In the context of unification, we consider logical forms to unify if and only they achieve structural concept equality after variable replacement (using the same variable replacements applied during unification of the corresponding feature lists), while taking into account the commutativity and associativity of . For example, under this criterion, the logical form GenderRel ∃RolePair(Predicate, Gender)._head would unify with either GenderRel ∃RolePair(Predicate, Gender).Male or with (∃RolePair(Predicate, Gender).Male)
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
GenderRel under a variable replacement mapping _head to Male, but would not unify with GenderRel ∃RolePair(Predicate, Gender).Male ∃RolePair(Predicate, GenderHaver).FilmProducer.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
CFQ knowledge rules output expressions representing facts that are known to be true. They have no direct effect on text, logical forms, or SPARQL, but the generated knowledge can be used as preconditions to other rules. In the rules index, they are described in the following format:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
→ K, where K is knowledge that is output.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
By convention, we define the rule name of a knowledge rule to be simply the string representing the knowledge that the rule outputs, and we omit the rule name in the rules index for brevity.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The union of those rules defines a knowledge base which we denote with KB CF Q .
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
All knowledge in CFQ is represented in the form P (X 1 , ..., X n ), where P is a predicate from the list below, and X 1 , ..., X n are either logical forms or else raw strings. Knowledge rules do not use variable-based expressions.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Supported knowledge predicates:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
CFQ inference rules transform logical forms and may be conditioned on knowledge. In the rules index, they are described in the following format:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
where K represents a comma-separated list of knowledge preconditions, and L 0 and L 1 represent the input and output logical forms, all expressed in terms of a shared set of variables v 1 , ..., v m .
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
These rules are interpreted as stating that if there exists a variable replacement r() replacing v 1 , ..., v m with some logical forms l 1 , ..., l m respectively, such that r(K) ⊆ KB CF Q , then we can apply the inference rule by rewriting r(L 0 ) to r(L 1 ).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
CFQ resolution rules transform SPARQL expressions and may be conditioned on knowledge. They do not affect text or logical forms.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In the rules index, they are described in the following format:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
K : S 0 → S 1 ... S n where K represents a comma-separated list of knowledge preconditions, S 0 is a variable-based expression and S 1 ... S n are either raw SPARQL strings or else expressions described in terms of the same variables used in S 0 and K.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
These rules are interpreted as stating that if there exists a variable replacement r() replacing v 1 , ..., v m with some logical forms, strings, or expressions l 1 , ..., l m respectively, such that r(K) ⊆ KB CF Q , then we can apply the resolution rule by rewriting r(S 0 ) to the sequence of terms r(S 1 ) ... r(S n ).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Our generation algorithm produces triples of the form question, logical form, SPARQL query in a mixed top-down and bottom-up fashion, with the final program of rule applications output alongside each triple in the form of a rule application DAG. The top-down portion of generation is responsible for efficiently searching for rules that can be applied to produce a meaningful example, while the bottom-up portion is responsible for actually applying the rules (i.e., performing the composition) and for producing the DAG.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The generation process proceeds in two phases, each involving a top-down as well as bottom-up aspect. In the first phase, we apply grammar rules interleaved with inference rules to produce a pair of question, logical form . Specifically, we apply a recursive top-down algorithm which starts with the S nonterminal and at every step performs a random search over the rules in the grammar which could produce the target nonterminal with accompanying feature structure. This top-down process proceeds until a candidate syntactic parse tree is attained whose leaves consist purely of syntactic terminals (i.e., string literals or entity placeholders). The grammar rules from this candidate parse tree are then applied in a bottom-up fashion beginning with the syntactic terminals to yield a tree of text, logical form pairs. After each such bottom-up grammar rule application, we then greedily apply all possible inference rules on the resulting logical forms, applying an arbitrary deterministic ordering to the inference rules in cases where rules could be applied in multiple valid orderings. This ensures that inference rules and grammar rules are executed in an interleaved manner and each inference rule is applied at the earliest possible occasion.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
When a question, logical form pair is generated for the S nonterminal, we proceed to the second phase of the algorithm, in which resolution rules are applied to generate a corresponding SPARQL query to make up the third element of the desired question, logical form, SPARQL query triple. In practice, the bulk of the work in this phase is performed in a top-down fashion, in which resolution rules are recursively applied to transform a starting expression of the form get_specializations($L) (where $L represents the logical form output from the grammar phase) into a sequence of text literals representing the SPARQL query. This is followed nominally by a bottom-up process to construct the rule application DAG, yielding a tree of resolution rule applications of a similar form to the tree of interleaved grammar and inference rules output from the grammar phase. Note that while the grammar phase involves a large degree of random choice, the resolution phase proceeds much more deterministically, as the CFQ resolution rules have been designed such that any given question can yield only one possible SPARQL query, modulo commutativity and associativity of . In cases where resolution rules could be applied in multiple valid orderings, we again apply an arbitrary deterministic ordering to the resolution rules so as to yield as consistent as possible a rule application DAG and question, logical form, SPARQL query triple for any given question.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Finally, to ease the task of tracking unique query patterns and to minimize the impact on the learning task of implementation details regarding choice of variable names or ordering of clauses, we normalize the final SPARQL query by alphabetically sorting the query clauses and re-numbering the variables to follow a standard increasing order.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The resulting question, logical form, SPARQL query triple is then appended to the CFQ dataset.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
In general, we do not explicitly track rules to represent the example-independent behaviors of the generation algorithm, as the universal applicability of these rules mean that the complete behavior of the generator should be observable on any reasonably-sized train set. The same applies to certain core behaviors of the description logic EL, such as commutativity and associativity of , which we omit tracking as explicit rules due to their similar ubiquity of application.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
One example-independent rule, however, that we do explicitly track is the rule that describes the handover process between the grammar phase and the resolution phase -or in terms of the rule application DAG, the rule that joins the tree of interleaved grammar and inference rule applications with the tree of resolution rule applications. We call this rule JOIN_BY_LOGICAL_FORM. It is included in the rules list for every example in CFQ and appears as the head of the rule application tree for each example.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Note that conceptually a similar approach for combining the different rule types could be applied to the semantic parsing task. The main difference would be that, instead of performing random search over the grammar, the semantic parsing task would need to find the set of rules which produce the desired input text.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
For many domains, the set of examples generated by exhaustively combining rules is infinite or prohibitively large. For example, the CFQ grammar generates an infinite set of questions, and even when restricted to a reasonable complexity, the set is still too large for practical use. This means that we need to choose which subset of examples we want to include in our dataset. Given our goal of comprehensively measuring compositional generalization, we do this by:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
1. maximizing the overall diversity of rule combinations (allowing us to test as many rule combinations as possible)
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
2. while using a uniform distribution from simple examples to increasingly more complex examples.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
We measure the diversity of rule combinations of a dataset using the empirical entropy over the frequency distribution of the subgraphs of the rule application DAGs, and we measure the complexity of an example using the number of rule applications used to generate it.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
For CFQ, we choose the following practical trade-off between these two criteria. We first generate a sufficiently large sample set by performing random rule applications. We then subsample from it to select a subset that maximizes the entropy of the subgraph distribution (while only taking into account subgraphs with a limited number of nodes for practicality). We use a greedy algorithm that incrementally assigns elements to the subsampled set while maximizing entropy at each step.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
The subsampling is initially limited to examples with the smallest complexity level and continues with increasingly larger complexity levels. We cap the maximum number of examples per level to achieve a uniform distribution across levels, and we limit the maximum complexity level such that the questions remain relatively natural. Table 1 shows examples of generated questions at varying levels of complexity.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
L EXAMPLE OF A RULE APPLICATION DAG Figures 12 through 14 show the rule application DAG that was produced when generating the question "Who directed [entity]?". They illustrate how grammar, inference, and knowledge rules are combined to generate a pair of text and logical form, and how resolution rules are used to generate the SPARQL query for the resulting logical form.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
As discussed in Section 3, nodes of this DAG represent rule applications while edges represent dependencies among the rules; i.e., an edge A → B means that rule B strictly depends on rule A in the sense that the generator cannot apply rule B before applying rule A. The DAG is normalized to ensure that a certain rule combination is represented using the same DAG across all the examples where it occurs. This is important for meaningfully comparing measures such as entropy and divergence across subgraphs of different examples.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Specifically, together with adopting the measures described above to ensure that rules are applied in a deterministic order, we achieve the normalization of the DAG by only producing edges that represent "minimal dependencies". This means that if a rule A can be applied after rule B, but it could also be applied after rule B with B → B (i.e., B depends on B), we don't produce the edge B → A.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Published as a conference paper at ICLR 2020 Figure 12: The normalized rule application DAG that was produced for "Who directed [entity]?" (grammar/inference rules portion, continued in Figures 13 and 14).
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
• ObjectUndergoerVerb = PredicateWithBoundRolePairs(RolePair( ObjectHaver, Object), RolePair(Predicate, Undergoer)) • E1 = Entity('?E1') L.3 ENTITY PLACEHOLDERS As described in Section 3.2, during generation we initially generate a question, logical form, SPARQL query triple containing entity placeholders, and then replace those placeholders with specific entities as a post-processing step. Conceptually, one could construct a rule application DAG describing either the process by which the original question, logical form, SPARQL query triple with entity placeholders was generated, or alternatively the rules that would need to be applied if constructing the question, logical form, SPARQL query triple containing the final entity MIDs directly. Structurally, these two DAGs are identical, differing only in the definition of two entity-related rules described below. The rule application DAG shown in the accompanying figures is the version using entity placeholders.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Versions of entity rules applicable when using entity placeholders:  Figure 15 shows an example of subgraphs in order to provide more details on the sampling and weighting of compounds. An example non-linear subgraph is highlighted by the red area, and two linear subgraphs are highlighted by the blue and the yellow areas, respectively.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
As described in Section 2.1, given a large subset G of subgraphs from the sample set as a whole, we calculate for each sample the weight of each subgraph G ∈ G that occurs in that sample as:
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
where occ(G) is the set of all occurrences of G in the sample, ≺ denotes the strict subgraph relation, and P (G |G) is the empirical probability of G occurring as a supergraph of G over the full sample set.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
Intuitively, we are trying to estimate how interesting the subgraph G is in the sample. First, for every occurrence g of a subgraph G, we look for the supergraph G of g that co-occurs most often with G in the full sample set. The empirical probability of having G as a supergraph of G determines how interesting the occurrence g is -the higher this probability, the less interesting the occurrence. Thus we compute the weight of the occurrence as the complement of this maximum empirical probability. Then we take the weight of G to be the weight of the most interesting occurrence g of G in the sample.
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data
E.g. in the extreme case that G only occurs within the context G , the weight of G will be 0 in all samples. Conversely, if G occurs in many different contexts, such that there is no single other subgraph G that subsumes it in many cases, then w(G) will be high in all samples in which it occurs. This ensures that when calculating compound divergence based on a weighted subset of compounds, the
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Sequence-to-sequence (seq2seq) models have been widely used in semantic parsing (Dong and Lapata, 2016;Jia and Liang, 2016) and excel at handling the natural language variation 1 of humangenerated queries. However, evaluations on synthetic 2 tasks such as SCAN (Lake and Baroni, 1 We use the term natural language variation in a broad sense to refer to the many different ways humans can express the same meaning in natural language, including differences in word choice and syntactic constructions. 2 We make a coarse distinction between synthetic datasets, where natural language utterances are generated by a program, 2018) have shown that seq2seq models often generalize poorly to out-of-distribution compositional utterances, such as "jump twice" when only "jump", "walk", and "walk twice" are seen during training. This ability to generalize to novel combinations of the elements observed during training is referred to as compositional generalization. This has motivated many specialized architectures that improve peformance on SCAN (Li et al., 2019;Russin et al., 2019;Gordon et al., 2019;Lake, 2019;Liu et al., 2020;Nye et al., 2020;Chen et al., 2020). However, most approaches have only been evaluated on synthetic datasets. While synthetic datasets enable precise, interpretable evaluation of specific phenomena, they are less representative of the natural language variation that a real-world semantic parsing system must handle.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
In this paper, we ask: can we develop a semantic parsing approach that handles both natural language variation and compositional generalization?
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
and non-synthetic datasets, where natural language utterances are collected from humans. Surprisingly, this question is understudied. As visualized in Figure 1, most prior work evaluates either out-of-distribution compositional generalization on synthetic datasets, or in-distribution performance on non-synthetic datasets. Notably, designing approaches that can handle both compositional generalization and the natural language variation of non-synthetic datasets is difficult. For example, large pre-trained seq2seq models that perform well on in-distribution evaluations do not address most of the compositional generalization challenges proposed in SCAN (Furrer et al., 2020).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Our research question has two important motivations. First, humans have been shown to be adept compositional learners (Lake et al., 2019). Several authors have argued that a greater focus on compositional generalization is an important path to more human-like generalization and NLU (Lake et al., 2017;Battaglia et al., 2018). Second, it is practically important to assess performance on non-synthetic data and out-of-distribution examples, as random train and test splits can overestimate real-world performance and miss important error cases (Ribeiro et al., 2020). Therefore, we are interested in approaches that do well not only on controlled synthetic challenges of compositionality or in-distribution natural utterances, but across all of the diverse set of evaluations shown in Figure 2.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Our contributions are two-fold. First, on the evaluation front, we show that performance on SCAN is not well-correlated with performance on non-synthetic tasks. In addition, strong existing approaches do not perform well across all evaluations in Figure 2. We also propose new Target Maximum Compound Divergence (TMCD) train and test splits, extending the methodology of Keysers et al. (2020) to create challenging evaluations of compositional generalization for non-synthetic datasets. We show that TMCD splits complement existing evaluations by focusing on different aspects of the problem.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Second, on the modeling front, we propose NQG, a simple and general grammar-based approach that solves SCAN and also scales to natural utterances, obtaining high precision for non-synthetic data. In addition, we introduce and evaluate NQG-T5, a hybrid model that combines NQG with T5 (Raffel et al., 2020), leading to improvements across several compositional generalization evaluations while also being competitive on the standard splits of GEOQUERY (Zelle and Mooney, 1996) and SPI-  (Keysers et al., 2020) Add Primitive (Lake and Baroni, 2018) Length TMCD Template (Finegan-Dollak et al., 2018) Length Random Figure 2: We evaluate semantic parsing approaches across a diverse set of evaluations focused on natural language variation, compositional generalization, or both. We add TMCD splits to complement existing evaluations. Ordering within each cell is arbitrary. DER (Yu et al., 2018). Our results indicate that NQG-T5 is a strong baseline for our challenge of developing approaches that perform well across a diverse set of evaluations focusing on either natural language variation, compositional generalization, or both. Comparing five approaches across eight evaluations on SCAN and GEOQUERY, its average rank is 1, with the rank of the best previous approach (T5) being 2.9; performance is also competitive across several evaluations on SPIDER. While still far from affirmatively answering our research question, our study highlights the importance of a diverse set of evaluations and the open challenge of handling both compositional generalization and natural language variation. 3
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
In this section, we survey recent work related to compositional generalization in semantic parsing.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Evaluations To evaluate a model's ability to generalize to novel compositions, previous work has proposed several methods for generating train and test splits, as well as several synthetic datasets.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
A widely used synthetic dataset for assessing compositional generalization is SCAN (Lake and Baroni, 2018), which consists of natural language commands (e.g., "jump twice") mapping to action sequences (e.g., "I_JUMP I_JUMP"). One split for SCAN is the length split, where examples are separated by length such that the test set contains longer examples than the training set. Another is the primitive split, where a given primitive (e.g., "jump") is seen by itself during training, but the test set consists of the primitive recombined with other elements observed during training (e.g., "jump twice"). Other synthetic datasets have been developed to evaluate aspects of compositional generalization beyond SCAN, including NACS (Bastings et al., 2018), CFQ (Keysers et al., 2020), andCOGS (Kim andLinzen, 2020).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
In addition to introducing the CFQ dataset, Keysers et al. (2020) propose Maximum Compound Divergence (MCD) splits based on the notion of a compound distribution. Their algorithm generates train and test splits that maximize the divergence of their respective compound distributions while bounding the divergence of their respective atom distributions. We extend their methodology to create new TMCD splits for non-synthetic datasets.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Another method for generating train and test splits is the template 4 split (Finegan-Dollak et al., 2018). Unlike the aforementioned evaluations, template splits have been applied to non-synthetic datasets, primarily for text-to-SQL. In template splits, any parse template (defined as the target SQL query with entities anonymized) appearing in the training set cannot appear in the test set. We analyze and discuss template splits in § 6.1.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Finally, Herzig and Berant (2019) studies biases resulting from methods for efficiently collecting human-labeled data, providing further motivation for out-of-distribution evaluations.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Approaches Many specialized architectures have been developed to address the compositional generalization challenges of SCAN. Several of them have recently reached 100% accuracy across multiple SCAN challenges (Liu et al., 2020;Nye et al., 2020;Chen et al., 2020). Similarly to the NQG-T5 approach we propose in § 4, all of these models incorporate discrete structure. However, unlike NQG-T5, they have only been evaluated on synthetic parsing tasks.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Recently, Herzig and Berant (2020) also begins to address our research question, proposing an approach that not only solves several SCAN challenges but also achieves strong performance on the standard and template splits of the non-synthetic dataset GEOQUERY. However, their approach requires some manual task-specific engineering. We compare NQG-T5 with this approach and other 4 Also referred to as a query split. SCAN-inspired architectures. Oren et al. (2020) and Zheng and Lapata (2020) also explored compositional generalization on non-synthetic datasets by focusing on the template splits proposed by Finegan-Dollak et al. (2018), demonstrating improvements over standard seq2seq models.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
The effect of large-scale pre-training on compositional generalization ability has also been studied. Furrer et al. (2020) finds that pre-training alone cannot solve several compositional generalization challenges, despite its effectiveness across NLP tasks such as question answering (Raffel et al., 2020).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
While our work focuses on modeling approaches, compositional data augmentation techniques have also been proposed (Jia and Liang, 2016;Andreas, 2020). NQG-T5 outperforms previously reported results for these methods, but more in-depth analysis is needed.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
The existing evaluations targeting compositional generalization for non-synthetic tasks are template splits and length splits. Here we propose an additional method which expands the set of available evaluations by generating data splits that maximize compound divergence over non-synthetic datasets, termed Target Maximum Compound Divergence (TMCD) splits. As we show in § 6, it results in a generalization problem with different characteristics that can be much more challenging than template splits, and contributes to the comprehensiveness of evaluation. In standard MCD splits (Keysers et al., 2020), the notion of compounds requires that both source and target are generated by a rule-based procedure, and therefore cannot be applied to existing non-synthetic datasets where natural language utterances are collected from humans. For TMCD, we propose a new notion of compounds based only on the target representations. We leverage their known syntactic structure to define atoms and compounds. For instance, example atoms in FunQL are longest and river, and an example compound is longest(river). Detailed definitions of atoms and compounds for each dataset we study can be found in Appendix B.3.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Given this definition of compounds, our definition of compound divergence, D C , is the same as that of Keysers et al. (2020). Specifically,
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
where F TRAIN and F TEST are the weighted frequency distributions of compounds in the training and test sets, respectively. The Chernoff coefficient Chung et al., 1989) is used with α = 0.1.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For TMCD, we constrain atom divergence by requiring that every atom appear at least once in the training set. An atom constraint is desirable so that the model knows the possible target atoms to generate. A greedy algorithm similar to the one of Keysers et al. (2020) is used to generate splits that approximately maximize compound divergence. First, we randomly split the dataset. Then, we swap examples until the atom constraint is satisfied. Finally, we sequentially identify example pairs that can be swapped between the train and test sets to increase compound divergence without violating the atom constraint, breaking when a swap can no longer be identified.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We propose NQG-T5, a hybrid semantic parser that combines a grammar-based approach with a seq2seq model. The two components are motivated by prior work focusing on compositional generalization and natural language variation, respectively, and we show in § 5 that their combination sets a strong baseline for our challenge.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
The grammar-based component, NQG, consists of a discriminative Neural parsing model and a flexible Quasi-synchronous Grammar induction algorithm which can operate over arbitrary pairs of strings. Like other grammar-based approaches, NQG can fail to produce an output for certain inputs. As visualized in Figure 3, in cases where NQG fails to produce an output, we return the output from T5 (Raffel et al., 2020), a pre-trained seq2seq model. This simple combination can work well because NQG often has higher precision than T5 for cases where it produces an output, especially in out-of-distribution settings.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We train NQG and T5 separately. Training data for both components consists of pairs of source and target strings, referred to as x and y, respectively.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
NQG is inspired by more traditional approaches to semantic parsing based on grammar formalisms such as CCG (Zettlemoyer andCollins, 2005, 2007;Kwiatkowski et al., 2010Kwiatkowski et al., , 2013 and SCFG (Wong andMooney, 2006, 2007;Andreas et al., 2013;Li Start Run NQG NQG has output?
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Return NQG output Return T5 output no yes Figure 3: Overview of how predictions are generated by NQG-T5, a simple yet effective combination of T5 (Raffel et al., 2020) with a high-precision grammarbased approach, NQG. et al., 2015). NQG combines a QCFG induction algorithm with a neural parsing model. Training is a two-stage process. First, we employ a compressionbased grammar induction technique to construct our grammar. Second, based on the induced grammar, we build the NQG semantic parsing model via a discriminative latent variable model, using a powerful neural encoder to score grammar rule applications anchored in the source string x.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Grammar Formalism Synchronous contextfree grammars (SCFGs) synchronously generate strings in both a source and target language. Compared to related work based on SCFGs for machine translation (Chiang, 2007) and semantic parsing, NQG uses a slightly more general grammar formalism that allows repetition of a non-terminal with the same index on the target side. Therefore, we adopt the terminology of quasi-synchronous context-free grammars (Smith and Eisner, 2006), or QCFGs, to refer to our induced grammar G. 5 Our grammar G contains a single non-terminal symbol, N T . We restrict source rules to ones containing at most 2 non-terminal symbols, and do not allow unary productions as source rules. This enables efficient parsing using an algorithm similar to CKY (Cocke, 1969;Kasami, 1965;Younger, 1967) that does not require binarization of the grammar.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Induction Procedure To induce G from the training data, we propose a QCFG induction algorithm that does not rely on task-specific heuristics or pre-computed word alignments. Notably, our approach makes no explicit assumptions about the source or target languages, beyond those implicit in the QCFG formalism. Table 1 shows examples of induced rules. Our grammar induction algorithm is guided by the principle of Occam's razor, which leads us to seek the smallest, simplest grammar that explains the data well. We follow the Minimum Description Length (MDL) principle (Rissanen, 1978;Grunwald, 2004) as a way to formalize this intuition. Specifically, we use standard two-part codes to compute description length, where we are interested in an encoding of targets y given the inputs x, across a dataset D consisting of these pairs. A two-part code encodes the model and the targets encoded using the model; the two parts measure the simplicity of the model and the extent to which it can explain the data, respectively. For grammar induction, our model is simply our grammar, G. The codelength can therefore be expressed as H(G) − x,y∈D log 2 P G (y|x) where H(G) corresponds to the codelength of some encoding of G. We approximate H(G) by counting terminal (C T ) and non-terminal (C N ) symbols in the grammar's rules, R. For P G , we assume a uniform distribution over the set of possible derivations. 6 As the only mutable aspect of the grammar during induction is the set of rules R, we abuse notation slightly and write our approximate codelength objective as a function of R only:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
where Z G x,y is the set of all derivations in G that yield the pair of strings x and y, while Z G
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
x, * ⊃ Z G
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
x,y is the set of derivations that yield source string x and any target string. The constants l N and l T can be interpreted as the average bitlength for encoding non-terminal and terminal symbols, respectively. In practice, these are treated as hyperparameters.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We use a greedy search algorithm to find a grammar that approximately minimizes this codelength objective. We initialize G by creating a rule N T → x, y for every training example (x, y). By construction, the initial grammar perfectly fits the training data, but is also very large. Our algorithm iteratively identifies a rule that can be added to G that decreases our codelength objective by enabling ≥ 1 rule(s) to be removed, under the invariant constraint that G can still derive all training examples. The search completes when no rule that decreases the objective can be identified. In practice, we use several approximations to efficiently select a rule at each iteration. Additional details regarding the grammar induction algorithm are described in Appendix A.2.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Based on the induced grammar G, we train a discriminative latent variable parsing model, using a method similar to that of Blunsom et al. (2008). We define p(y | x) as:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
x,y is the set of derivations of x and y in G. We define p(z | x) as:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
where s(z, x) is a derivation score and the denominator is a global partition function. Similarly to the Neural CRF model of Durrett and Klein (2015), the scores decompose over anchored rules. Unlike Durrett and Klein (2015), we compute these scores based on contextualized representations from a BERT (Devlin et al., 2019) encoder. Additional details regarding the model architecture can be found in Appendix A.3. At training time, we use a Maximum Marginal Likelihood (MML) objective. We preprocess each example to produce parse forest representations for both Z G
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
x,y and Z G x, * , which correspond to the numerator and denominator of our MML objective, respectively. By using dynamic programming to efficiently sum derivation scores inside the training loop, we can efficiently compute the exact MML objective without requiring approximations such as beam search.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
At inference time, we select the highest scoring derivation using an algorithm similar to CKY that considers anchored rule scores generated by the neural parsing model. We output the corresponding target if it can be derived by a CFG defining valid target constructions for the given task.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We note that NQG is closely related to work that uses synchronous grammars for hierarchical statistical machine translation, such as Hiero (Chiang, 2007). Unlike Hiero, NQG does not rely on an additional word alignment component. Moreover, Hiero simply uses relative frequency to learn rule weights. Additionally, in contract with traditional SCFG models for machine translation applied to semantic parsing (Wong and Mooney, 2006; Andreas et al., 2013), our neural model conditions on global context from the source x via contextual word embeddings, and our grammar's rules do not need to carry source context to aid disambiguation.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
T5 (Raffel et al., 2020) is a pre-trained sequence-tosequence Transformer model (Vaswani et al., 2017). We fine-tune T5 for each task.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We evaluate existing approaches and the newly proposed NQG-T5 across a diverse set of evaluations to assess compositional generalization and handling of natural language variation. We aim to understand how the approaches compare to each other for each type of evaluation and in aggregate, and how the performance of a single approach may vary across different evaluation types.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For our main experiments, we focus on evaluation across multiple splits of two datasets with compositional queries: SCAN (Lake and Baroni, 2018) and GEOQUERY (Zelle and Mooney, 1996;Tang and Mooney, 2001). The two datasets have been widely used to study compositional generalization and robustness to natural language variation, respectively. Both datasets are closed-domain and have outputs with straightforward syntax, enabling us to make clear comparisons between synthetic vs. non-synthetic setups.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Approaches For NQG-T5, to assess the effect of model size, we compare two sizes of the underlying T5 model: Base (220 million parameters) and 3B (3 billion parameters). To evaluate NQG individually, we treat any example where no output is provided as incorrect when computing accuracy.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We select strong approaches from prior work that have performed well in at least one setting. We group them into two families of approaches described in Figure 1. First, for general-purpose models that have shown strong ability to handle natural language variation, we consider T5, a pretrained seq2seq model, in both Base and 3B sizes.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Second, for specialized methods with strong compositional biases, we consider approaches that have been developed for SCAN. Some previous approaches for SCAN require task-specific information such as the mapping of atoms (Lake, 2019; Gordon et al., 2019) or a grammar mimicking the training data (Nye et al., 2020), and as such are difficult to adapt to non-synthetic datasets. Among the approaches that do not need task-specific resources, we evaluate two models with publicly available code: Syntactic Attention (Russin et al., 2019) and CGPS (Li et al., 2019). We report results on SCAN from the original papers as well as new results on our proposed data splits.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Datasets For the SCAN dataset, we evaluate using the length split and two primitive splits, jump and turn left, included in the original dataset (Lake and Baroni, 2018). We also evaluate using the SCAN MCD splits from Keysers et al. (2020). GEOQUERY (Zelle and Mooney, 1996) contains natural language questions about US geography. Similarly to prior work Lapata, 2016, 2018), we replace entity mentions with placeholders. We use a variant of Functional Query Language (FunQL) as the target representation (Kate et al., 2005). In addition to the standard split of Zettlemoyer and Collins (2005)  We report exact-match accuracy for both datasets. 8 Hyperparameters and pre-processing details can be found in Appendix B.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
The results are presented in Table 2. The results for T5 on SCAN are from Furrer et al. (2020). Additionally, we include results for GECA 9 (Andreas, 2020), a data augmentation method, as well as LANE (Liu et al., 2020) and NSSM (Chen et al., 2020) 10 . We also compare with SpanBasedSP 11 (Herzig and Berant, 2020).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
From the results, we first note that the relative performance of approaches on compositional splits of SCAN is not very predictive of their relative performance on compositional splits of GEO-QUERY. For example, GGPS is better than T5 on the length split of SCAN but is significantly worse than T5 on the length split of GEOQUERY. Similarly, the ranking of most methods is different on the (T)MCD splits of the two datasets. Second, the proposed NQG-T5 approach combines the strengths of T5 and NQG to achieve superior results across all evaluations. It improves over T5 on compositional generalization for both synthetic and non-synthetic data while maintaining T5's performance on handling in-distribution natural language variation, leading to an average rank of 1.0 compared to 2.9 for T5. (To the best of our knowledge, both T5 and NQG-T5 achieve new state-of-the-art accuracy on the standard split of GEOQUERY.)
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Finally, we note that there is substantial room for improvement on handling both compositional generalization and natural language variation.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We now compare the approaches on SPIDER (Yu et al., 2018), a non-synthetic text-to-SQL dataset that includes the further challenges of schema linking and modeling complex SQL syntax.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
SPIDER contains 10,181 questions and 5,693 unique SQL queries across 138 domains. The primary evaluation is in the cross-database setting, where models are evaluated on examples for databases not seen during training. The primary challenge in this setting is generalization to new database schemas, which is not our focus. Therefore, we use a setting where the databases are shared between train and test examples. 12 We gen-   Suhr et al. (2020) and use SPIDER-SSP to refer to these same-database splits, and use SPIDER-XSP to refer to the standard cross-database setting. We prepend the name of the target database to the source sequence. For T5, we also serialize the database schema as a string and append it to the source sequence similarly to Suhr et al. (2020). We report exact set match without values, the standard Spider evaluation metric (Yu et al., 2018). Table 3 shows the results of T5 and NQG-T5 on different splits of SPIDER-SSP. We also show T5-Base performance without the schema string appended. The text-to-SQL mapping is not well modeled by NQG. Nevertheless, the performance of NQG-T5 is competitive with T5, indicating a strength of the hybrid approach. Table 4 shows the results on SPIDER-XSP, which focuses on handling unseen schema rather than compositional generalization. To our surprise, T5-3B proves to be competitive with the state-ofthe-art (Choi et al., 2020) for approaches without access to database contents beyond the table and column names. As NQG-T5 simply uses T5's output when the induced grammar lacks coverage, it too is competitive.   13 Length splits are also very challenging, but they lead to a more predictable error pattern for seq2seq models, as discussed next.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We analyze NQG-T5's components, starting with T5. On length splits, there is a consistent pattern to the errors. T5's outputs on the test set are not significantly longer than the maximum length observed during training, leading to poor performance. This phenomenon was explored by Newman et al. (2020). Diagnosing the large generalization gap on the (T)MCD splits is more challenging, but we noticed several error patterns. For T5-Base on the GEO-QUERY TMCD split, in 52 of the 201 incorrect predictions (26%), the first incorrectly predicted symbol occurs when the gold symbol has 0 probability under a trigram language model fit to the training data. This suggests that the decoder's implicit target language model might have over-fitted to the distribution of target sequences in the training data, hampering its ability to generate novel compositions. Non-exclusively with these errors, 53% of the incorrect predictions occur when the gold target contains an atom that is seen in only 1   example during training, suggesting that T5 struggles with single-shot learning of new atoms. In other cases, the errors appear to reflect over-fitting to spurious correlations between inputs and outputs.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Some error examples are shown in Appendix B.6.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
To analyze NQG, we compute its coverage (fraction of examples where NQG produces an output) and precision (fraction of examples with a correct output among ones where an output is produced) on different data splits. The results in Table 5 show that NQG has high precision but struggles at coverage on some data splits.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
There is a significant difference in the effectiveness of the grammar induction procedure among the three datasets. Induction is particularly unsuccessful for SPIDER, as SQL has complicated syntax and often requires complex coordination across discontinuous clauses. Most of the induced rules are limited to simply replacing table and column names or value literals with non-terminals, such as the rule shown in Table 1, rather than representing nested sub-structures. The degree of span-to-span correspondence between natural language and SQL is seemingly lower than for other formalisms such as FunQL, which limits the effectiveness of grammar induction. Intermediate representations for SQL such as SemQL (Guo et al., 2019) may help increase the correspondence between source and target syntax.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For both GEOQUERY and SPIDER, NQG is limited by the expressiveness of QCFGs and the simple greedy search procedure used for grammar induction, which can lead to sub-optimal approximations of the induction objective. Notably, QCFGs cannot directly represent relations between source strings, such as semantic similarity, or relations between target strings, such as logical equivalence (e.g. intersect(a,b) ⇔ intersect(b,a)), that could enable greater generalization. However, such extensions pose additional scalability challenges, requiring new research in more flexible approaches for both learning and inference.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Our experiments and analysis demonstrate that NQG and T5 offer different strengths. NQG generally has higher precision for out-of-distribution examples, but is limited by the syntactic constraints of the grammar formalism and by requiring exact lexical overlap with induced rules in order to provide a derivation at inference time. T5's coverage is not limited by such constraints, but precision can be significantly lower for out-of-distribution examples. With NQG-T5, we offer a simple combination of these strengths. While accuracy is still limited for out-of-distribution examples where NQG lacks coverage, we believe it sets a strong and simple baseline for future work.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
More broadly, our work highlights that evaluating on a diverse set of benchmarks is important, and that handling both out-of-distribution compositional generalization and natural language variation remains an open challenge for semantic parsing.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
This paper proposed to expand the set of benchmarks used to evaluate compositional generalization in semantic parsing. While we hope that ensuring semantic parsing approaches perform well across a diverse set of evaluations, including ones that test out-of-distribution compositional generalization, would lead to systems that generalize better to languages not well represented in small training sets, we have only evaluated our methods on semantic parsing datasets in English.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Our NQG-T5 method uses a pre-trained T5 model, which is computationally expensive in finetuning and inference, especially for larger models (see Appendix B.1 for details on running time and compute architecture). Our method does not require pre-training of large models, as it uses pre-existing model releases. NQG-T5-base outperforms or is comparable in accuracy to T5-3B on the non-SQL datasets, leading to relative savings of computational resources. In this section we describe the NQG grammar induction algorithm and parsing model in detail, starting with relevant background and notation for QCFGs.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Synchronous Context-Free Grammars (SCFGs) have been used to model the hierarchical mapping between pairs of strings in areas such as compiler theory (Aho and Ullman, 1972) and natural language processing. Informally, SCFGs can be viewed as an extension of Context-Free Grammars (CFGs) that synchronously generate strings in both a source and target language. We write SCFG rules as:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Where S is a non-terminal symbol, and α and β are strings of non-terminal and terminal symbols. An SCFG rule can be viewed as two CFG rules, S → α and S → β with a pairing between the occurrences of non-terminal symbols in α and β. This pairing is indicated by assigning each nonterminal in α and β an index ∈ N. Non-terminals sharing the same index are called linked. Following convention, we denote the index for a non-terminal using a boxed subscript, e.g. N T [1] . A complete SCFG derivation is a pair of parse trees, one for the source language and one for the target language. An example derivation is shown in Figure 4.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
The ⇒ r operator refers to a derives relation, such that α 1 , β 1 ⇒ r α 2 , β 2 states that the string pair α 2 , β 2 can be generated from α 1 , β 1 by applying the rule r. We write ⇒ to leave the rule unspecified, assuming the set of possible rules is clear from context. We write ⇒⇒ to indicate a chain of 2 rule applications, omitting the intermediate string pair. Finally, we write * ⇒ to denote the reflexive transitive closure of ⇒.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Quasi-Synchronous Context-Free Grammars (QCFGs) QCFGs generalize SCFGs in various ways, notably relaxing the restriction on a strict one-to-one alignment between source and target non-terminals (Smith and Eisner, 2006).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Compositionality Notably, grammar formalisms such SCFGs and QCFGs capture the formal notion of the principle of compositionality as a homomorphism between source and target structures (Montague, 1970;Janssen and Partee, 1997).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Having defined the codelength scoring function that we use to compare grammars in section 4.1.1, we describe our greedy search algorithm that finds a grammar that approximately minimizes this objective. 14 Initialization We initialize R to be {N T → x, y | x, y ∈ D}. We also add identity rules for substrings that exactly match between source and target examples, e.g. N T → k, k where k is a substring of both x and y for some x, y ∈ D. 15 Optimization Algorithm Our algorithm was designed with simplicity in mind, and therefore uses a simple greedy search process that could likely be significantly improved upon by future work. At a high level, our greedy algorithm iteratively identifies a rule to be added to R that decreases the codelength by enabling ≥ 1 rules in R to be removed while maintaining the invariant that G allows for deriving all of the training examples, i.e. N T, N T * ⇒ x, y for every x, y ∈ D. The search completes when no rule that decreases L(R) can be identified.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
To describe the implementation, first let us define several operations over rules and sets of rules. We define the set of rules that can be derived from a given set of rules, R:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We define an operation SPLIT that generates possible choices for splitting a rule into 2 rules:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
The induction objective contains hyperparameters representing the bitlength of terminal and non-terminal symbols. For all experiments we use lN = 1. For GEOQUERY and SPIDER we use lT = 8, and use lT = 32 for SCAN. 15 These initialization rules are used for GEOQUERY and SPIDER, but SCAN does not contain any exact token overlap between source and target languages. N T → how many N T [1] pass through N T [2] , answer ( count ( intersection ( N T [1] , loc_1 ( N T [2] ) ) ) ) N T → rivers, river N T → the largest N T [1] , largest ( N T [1]   where g and h is a pair of new rules that would maintain the invariant that N T, N T * ⇒ x, y for every x, y ∈ D, even if the provided rule is eliminated. 16 SPLIT can be implemented by considering pairs of sub-strings in α and β to replace with a new indexed non-terminal symbol.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For example, the rule "N T → largest state, largest ( state ) " can be split into the rules "N T → largest N T [1] , largest ( N T [1] ) " and "N T → state, state ". This step can require re-indexing of non-terminals.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
During our greedy search, we only split rules when one of the two resulting rules can already be derived given R. Therefore, we define a function NEW that returns a set of candidate rules to consider:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Similarly, we can compute the set of rules that are made redundant and can be eliminated by introducing one these candidate rules, f : 16 We optionally allow SPLIT to introduce repeated target non-terminals when the target string has repeated substrings. Otherwise, we do not allow SPLIT to replace a repeated substring with a non-terminal, as this can lead to an ambiguous choice. We enable this option for SCAN and SPIDER but not for GEOQUERY, as FunQL does not require such repetitions.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We can then define the codelength reduction of adding a particular rule, 17 Finally, we can select the rule with the largest −∆L:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Conceptually, after initialization, the algorithm then proceeds as:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For efficiency, we select the shortest N examples from the training dataset, and only consider these during the induction procedure. Avoiding longer examples is helpful as the number of candidates returned by SPLIT is polynomial with respect to source and target length. Once induction has completed, we then determine which of the longer examples cannot be derived based on the set of induced rules, and add rules for these examples. 18 Our algorithm maintains a significant amount of state between iterations to cache computations that are not affected by particular rule changes, based on overlap in terminal symbols. We developed the algorithm and selected some hyperparameters by assessing the size of the induced grammars over the training sets of SCAN and GEOQUERY.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Our grammar induction algorithm is similar to the transduction grammar induction method for machine translation by Saers et al. (2013). More broadly, compression-based criteria have been successfully used by a variety of models for language (Grünwald, 1995;Tang and Mooney, 2001;Ravi and Knight, 2009;Poon et al., 2009).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
In this section we provide details on how we generate derivation scores, s(z, x), using a neural model, as introduced in § 4.1. The derivation scores decompose over anchored rules from our grammar:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
where r is an index for a rule in G and i and j are indices defining the anchoring in x. The anchored rule scores, φ(r, i, j, x), are based on contextualized representations from a BERT (Devlin et al., 2019) encoder:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
where [w i , w j ] is the concatenation of the BERT representations for the first and last wordpiece in the anchored span, f r is a feed-forward network with hidden size d that outputs a vector ∈ R d , f s is a feed-forward network with hidden size d that outputs a scalar, and e r is an embedding ∈ R d for the rule index r. Our formulation for encoding spans is similar to that used in other neural span-factored models (Stern et al., 2017;Lee et al., 2017).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We selected reasonable hyperparameter values and performed some minimal hyperparameter tuning 18 We use N = 500 for SCAN and N = 1000 for SPI-DER. As the GEOQUERY training set contains < 500 unique examples, we use the entire training set.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
for T5 and NQG based on random splits of the training sets for GEOQUERY and SPIDER. We used the same hyperparameters for all splits of a given dataset.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For T5, we selected a learning rate of 1e −4 from [1e −3 , 1e −4 , 1e −5 ], which we used for all experiments. Otherwise, we used the default hyperparameters for fine-tuning. We fine-tune for 3, 000 steps for GEOQUERY and 10, 000 for SPIDER. T5-Base trained with a learning rate of 1e −4 reached 94.2% accuracy at 3, 000 steps on a random split of the standard GeoQuery training set into 500 training and 100 validation examples.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For the NQG neural model, we use the pretrained BERT Tiny model of Turc et al. (2019) (4.4M parameters) for SCAN and SPIDER, and BERT Base (110.1M parameters) for GEOQUERY, where there is more headroom for improved scoring. We do not freeze pre-trained BERT parameters during training. For all experiments, we use d = 256 dimensions for computing anchored rule scores. We fine-tune for 256 steps and use a learning rate of 1e −4 . We use a batch size of 256.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We train NQG on 8 V100 GPUs. Training NQG takes < 5 minutes for SCAN and SPIDER (BERT Tiny), and up to 90 minutes for GEOQUERY (BERT Base). We fine-tune T5 on 32 Cloud TPU v3 cores. 19 For GEOQUERY, fine-tuning T5 takes approximately 5 and 37 hours for Base and 3B, respectively. For SPIDER, fine-tuning T5 takes approximately 5 and 77 hours for Base and 3B, respectively.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For GEOQUERY, we use the version of the dataset with variable-free FunQL logical forms (Kate et al., 2005), and expand certain functions based on their logical definitions, such that state(next_to_1(state(all))) becomes the more conventional intersection(state, next_to_1(state)).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We replace entity mentions with placeholders (e.g. "m0", "m1") in both the source and target. For SPIDER, we prepend the name of the target database to the source sequence. For T5, we also serialize the database schema as a string and append it to the source sequence similarly to Suhr et al. (2020). This schema string contains the names of all tables in the database, and the names of the columns for each table. As we use a maximum Source: how many states are next to major rivers Target:
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
answer ( count ( intersection ( state , next_to_2 ( intersection ( major , river ) ) ) ) ) Prediction: answer ( count ( intersection ( state , next_to_2 ( intersection ( major , intersection ( river , m0 ) ) ) ) ) ) Notes: The trigram "major , intersection" occurs 28 times during training, but "major , river" occurs 0 times. In this case, T5 also hallucinates "m0" despite no entity placeholder occuring the source.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Source: which state has the highest peak in the country Target: answer ( intersection ( state , loc_1 ( highest ( place ) ) ) ) Prediction: answer ( highest ( intersection ( state , loc_2 ( highest ( intersection ( mountain , loc_2 ( m0 ) ) ) ) ) ) Notes: The token "highest" occurs after "answer (" in 83% of instances in which "highest" occurs in the training set. Note that T5 also hallucinates "m0" in this case.   source sequence length of 512 for T5, this leads to some schema strings being truncated (affecting about 5% of training examples). SCAN did not require any dataset-specific preprocessing.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For GEOQUERY, the tree structure of FunQL is given by explicit bracketing. We define atoms as individual FunQL symbols, and compounds as combinations between parent and child symbols in the FunQL tree. Example atoms are longest, river, and exclude and example compounds are longest(river) and exclude(longest(_), _).
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
For SPIDER, we tokenize the SQL string and define atoms as individual tokens. To define compounds, we parse the SQL string using an unambiguous CFG, and define compounds from the resulting parse tree. We define compounds over both first and second order edges in the resulting parse tree.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
Induced grammar sizes for a selected split of each dataset are shown in Table 8. For SPIDER, the number of induced rules is larger than the original dataset due to the identity rules added during initialization.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
In tables 2 and 5 we report the mean of 3 runs for NQG for GEOQUERY. The standard deviations for these runs are reported in Table 9. The reported standard deviations for NQG-T5 use the same finetuned T5 checkpoint, so they do not reflect any additional variance from different fine-tuned T5 checkpoints.
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both?
We include several example T5-Base errors on the GEOQUERY TMCD split in Table 7.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Although the successes of deep neural networks in natural language processing (NLP) are astounding and undeniable, they are still regularly criticised for lacking the powerful generalisation capacities that characterise human intelligence. A frequently mentioned concept in such critiques is compositionality: the ability to build up the meaning of a complex expression by combining the meanings of its parts (e.g. Partee, 1984). Compositionality is assumed 1 The data and code are available at https://github. com/i-machine-think/compositionality paradox mt. We present details concerning reproducibility in Appendix E.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
to play an essential role in how humans understand language, but whether neural networks also exhibit this property has since long been a topic of vivid debate (e.g. Fodor and Pylyshyn, 1988;Smolensky, 1990;Marcus, 2003;Nefdt, 2020).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Studies about the compositional abilities of neural networks consider almost exclusively models trained on synthetic datasets, in which compositionality can be ensured and isolated (e.g. Lake and Baroni, 2018;Hupkes et al., 2020). 2 In such tests, the interpretation of expressions is computed completely locally: every subpart is evaluated independently -without taking into account any external context -and the meaning of the whole expression is then formed by combining the meanings of its parts in a bottom-up fashion. This protocol matches the type of compositionality observed in arithmetic: the meaning of (3 + 5) is always 8, independent of the context it occurs in.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
However, as exemplified by the sub-par performance of symbolic models that allow only strict, local protocols, compositionality in natural domains is far more intricate than this rigid, arithmeticlike variant of compositionality. Natural language seems very compositional, but at the same time, it is riddled with cases that are difficult to interpret with a strictly local interpretation of compositionality. Sometimes, the meaning of an expression does not derive from its parts (e.g. for idioms), but the parts themselves are used compositionally in other contexts. In other cases, the meaning of an expression does depend on its parts in a compositional way, but arriving at this meaning requires a more global approach because the meanings of the parts need to be disambiguated by information from elsewhere. For instance, consider the meaning of homonyms ("these dates are perfect for our dish/wedding"), potentially idiomatic expressions ("the child kicked the bucket off the pavement"), or scope ambiguities ("every human likes a cat"). This paradoxical tension between local and global forms of compositionality inspired many debates on the compositionality of natural language. Likewise, it impacts the evaluation of compositionality in NLP models. On the one hand, local compositionality seems necessary for robust and reliable generalisation. Yet, at the same time, global compositionality is needed to appropriately address the full complexity of language, which makes evaluating compositionality of state-of-the-art models 'in the wild' a complicated endeavour.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In this work, we face this challenge head-on. We concentrate on the domain of neural machine translation (NMT), which is paradigmatically close to the tasks typically considered for compositionality tests, where the target represents the 'meaning' of the input. 3 Furthermore, MT is an important domain of NLP, for which compositional generalisation is important to produce more robust translations and train adequate models for low-resource languages (see, e.g. Chaabouni et al., 2021). As an added advantage, compositionality is traditionally well studied and motivated for MT (Rosetta, 1994;Janssen and Partee, 1997;Janssen, 1998).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We reformulate three theoretically grounded tests from Hupkes et al. (2020): systematicity, substitutivity and overgeneralisation. Since accuracycommonly used in artificial compositionality testsis not a suitable evaluation metric for MT, we base our evaluations on the extent to which models behave consistently, rather than correctly. In our tests for systematicity and substitutivity, we consider whether processing is local; in our overgeneralisation test, we consider how models treat idioms that are assumed to require global processing.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Our results indicate that models often do not behave compositionally under the local interpretation, but exhibit behaviour that is too local in other cases. In other words, models have the ability to process phrases both locally and globally but do not always correctly modulate between them. We further show that some inconsistencies reflect variation in natural language, whereas others are true compositional mistakes, exemplifying the need for both local and global compositionality as well as illustrating the need for tests that encompass them both.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
With our study, we contribute to ongoing questions about the compositional abilities of neural networks, and we provide nuance to the nature of this question when natural language is concerned:
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Tests for compositional generalisation in neural networks typically assume an arithmetic-like version of compositionality, in which meaning can be computed bottom up. The compositions require only local information -they are context independent and unambiguous: "walk twice after jump thrice" (a fragment from SCAN by Lake and Baroni, 2018) is evaluated similarly to (2 + 1) × (4 − 5). In MT, this type of compositionality would imply that a change in a word or phrase should affect only the translation of that word or phrase, or at most the smallest constituent it is a part of. For instance, the translation of "the girl" should not change depending on the verb phrase that follows it, and in the translation of a conjunction of two sentences, making a change in the first conjunct should not change the translation of the second. While translating in such a local way seems robust and productive, it is not always realistic -e.g. consider the translation of "dates" in "She hated bananas and she liked dates".
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In linguistics and philosophy of language, the level of compositionality has been widely discussed, which led to a variety of definitions. One of the most well-known ones is from Partee (1984):
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
"The meaning of a compound expression is a function of the meanings of its parts and of the way they are syntactically combined." 4 This definition hardly places restrictions on the relationship between expressions and their parts. The type of function that relates them is unspecified and could take into account the global syntactic structure or external arguments, and the parts' meanings can depend on global information. Partee's definition is therefore called weak, global, or open compositionality (Szabó, 2012;García-Ramírez, 2019). When, instead, the meaning of a compound depends only on the meanings of its largest parts, regardless of their internal structure (similar to arithmetic), that is strong, local or closed n Template
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople V the N sl people . 2
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople Adv V the N sl people . 3
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople P the N sl vehicle V the N sl people . 4
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople and the Npeople V the N sl people . 5
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The N sl quantity of N pl people P the N sl vehicle V the N sl people . 6
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople V that the N pl people V. 7
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople Adv V that the N pl people V . 8
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople V that the N pl people V Adv . 9
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople that V V the N sl people . 10 The Npeople that V Pro V the N sl people .
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(a) Synthetic templates n Template 1,2,3 The Npeople VP1,2,3 . The men are gon na have to move off-camera .
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople read(s) an article about NP1,2 .
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The man reads an article about the development of ascites in rats with liver cirrhosis . 6,7
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
An article about NP3,4 is read by Npeople .
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
An article about the criterion on price stability , which was 27 % , is read by the child . 8,9,10 Did the Npeople hear about NP5,6,7 ?
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Did the teacher hear about the march on Employment which happened here on Sunday ?
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(b) Semi-natural templates compositionality (Jacobson, 2002;Szabó, 2012). Under the local interpretation, natural language can hardly be considered compositional -many frequent phenomena such as homonyms, idioms and scope ambiguities cannot be resolved locally (Pagin and Westerståhl, 2010;Pavlick and Callison-Burch, 2016). The global interpretation handles such cases straightforwardly but does not match up with many a person's intuitions about the compositionality of language. After all, how useful is compositionality if composing the meanings of parts requires the entire rest of the sentence? This paradox inspired debates on the compositionality of natural language and is also highly relevant in the context of evaluating compositionality in neural models. Previous compositionality tests ( §6) considered only the local interpretation of compositionality, but to what extent is that relevant given the type of compositionality actually required to model natural language? Here, we aim to open up the discussion about what it means for computational models of language to be compositional by considering properties that require composing meaning locally as well as globally and evaluating them in models trained on unadapted natural language corpora.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We focus on English-Dutch translation, for which we can ensure good command for both languages. We train Transformer-base models (Vaswani et al., 2017) using Fairseq (Ott et al., 2019. Our training data consists of a collection of MT corpora bundled in OPUS (Tiedemann and Thottingal, 2020), of which we use the English-Dutch subset provided by Tiedemann (2020), which contains 69M sentence pairs. 5 To examine the impact of the amount 5 Visit the Tatoeba challenge for the OPUS training data. of training data -a dimension that is relevant because compositionality is hypothesised to be more important when resources are scarcer -we train one setup using the full dataset, one using 1 8 of the data (medium), and one using one million sourcetarget pairs in the small setup. For each setup, we train models with five seeds and average the results.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
To evaluate our trained models, we adopt FLORES-101 (Goyal et al., 2021), which contains 3001 sentences from Wikinews, Wikijunior and WikiVoyage, translated by professional translators, split across three subsets. We train the models until convergence on the 'dev' set. Afterwards, we compute SacreBLEU scores on the 'devtest' set (Post, 2018), using beam search (beam size = 5), yielding scores of 20.6±.4, 24.4±.3 and 25.8±.1 for the small, medium and full datasets, respectively. 6
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
While all our models are trained on fully natural data, for evaluation we use different types of data: synthetic, semi-natural and natural data.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Synthetic data For our synthetic evaluation data, we consider the data generated by Lakretz et al. (2019), previously used to probe for hierarchical structure in neural language models. This data consist of sentences with a fixed syntactic structure and diverse lexical material. We extend the vocabulary and the templates used to generate the data and generate 3000 sentences for each of the resulting 10 templates (see Table 1a).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Semi-natural data In the synthetic data, we have full control over the sentence structure and lexical items, but the sentences are shorter (9 tokens vs 16 in OPUS) and simpler than typical in NMT data. To obtain more complex yet plausible test sentences, we employ a data-driven approach Consistency scores are shown per evaluation data type (x-axis) and training dataset size (colours). Data points represent templates (•) and means over templates ( ).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The girl sees that the men cry
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The girl sees that the men cry , and the poet criticises the king S→S CONJ S
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The painter avoids the mayor , and the poet criticises the king
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The baker sees that the men cry The girl sees that the aunts cry
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The girl sees that the men cry VP→VP' Figure 2: Illustration of the systematicity experiments S → S CONJ S (S 1 → S 3 is shown) and S → NP VP (both versions are shown). Each experiment involves extracting translations before and after the replacement of the blue part, and then comparing the translation of the underlined words.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
to generate semi-natural data. Using the tree substitution grammar Double DOP (Van Cranenburgh et al., 2016), we obtain noun and verb phrases (NP, VP) whose structures frequently occur in OPUS. We then embed these NPs and VPs in ten synthetic templates with 3000 samples each (see Table 1b). See Appendix A for details on the data generation.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Natural data Lastly, we extract natural data directly from OPUS, as detailed in the subsections of the individual tests ( §4).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In our experiments, we consider systematicity ( §4.1) and substitutivity ( §4.2), to test for local compositionality, and idiom translation to probe for a more global type of processing ( §4.3).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
One of the most commonly tested properties of compositional generalisation is systematicity -the ability to understand novel combinations made up from known components (most famously, Lake and Baroni, 2018). In natural data, the number of potential recombinations to consider is infinite. We chose to focus on recombinations in two sentence-level context-free rules: S → NP VP and S → S CONJ S.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Test design The first setup, S → NP VP, concerns recombinations of noun and verb phrases. We extract translations for input sentences from the templates from §3.2, as well as versions of them with the (1) noun (NP → NP') or (2) verb phrase (VP → VP') adapted. In (1), a noun from the NP in the subject position is replaced with a different noun while preserving number agreement with the VP. In (2), a noun in the VP is replaced. NP → NP' is applied to both synthetic and semi-natural data; VP → VP' only to synthetic data. We use 500 samples per template per condition per data type. The second setup, S → S CONJ S, involves phrases concatenated using "and", and tests whether the translation of the second sentence is dependent on the first sentence. We concatenate two sentences (S 1 and S 2 ) from different templates, and we consider again two different conditions. First, in condition S 1 → S 1 , we make a minimal change to S 1 yielding S 1 by changing the noun in its verb phrase. In S 1 → S 3 , instead, we replace S 1 with a sentence S 3 that is sampled from a template different from S 1 . We compare the translation of S 2 in all conditions. For consistency, the first conjunct is always sampled from the synthetic data templates. The second conjunct is sampled from synthetic data, semi-natural data, or from natural sentences sampled from OPUS with similar lengths and word-frequencies as the semi-natural inputs. We use 500 samples per template per condition per data type. Figure 2 provides an illustration of the different setups experimented with.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Evaluation In artificial domains, systematicity is evaluated by leaving out combinations of 'known components' from the training data and using them for testing purposes. The necessary familiarity of the components (the fact that they are 'known') is ensured by high training accuracies, and systematicity is quantified by measuring the test set accu- racy. If the training data is a natural corpus and the model is evaluated with a measure like BLEU in MT, this strategy is not available. We observe that being systematic requires being consistent in the interpretation assigned to a (sub)expression across contexts, both in artificial and natural domains. Here, we, therefore, focus on consistency rather than accuracy, allowing us to employ a modeldriven approach that evaluates the model's systematicity as the consistency of the translations when presenting words or phrases in multiple contexts.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We measure consistency as the equality of two translations after accounting for anticipated changes. For instance, in the S → NP VP setup, two translations are consistent if they differ in one word only, after accounting for determiner changes in Dutch ("de" vs "het"). In the evaluation of S → S CONJ S, we measure the consistency of the translations of the second conjunct. Figure 1 shows the results for the S → NP VP and S → S CONJ S setups (numbers available in Appendix B). The average performance for the natural data closely resembles the performance on seminatural data, suggesting that the increased degree of control did not severely impact the results obtained using this generated data. 7 In general, the consistency scores are low, illustrating that models are prone to changing their translation of a (sub)sentence after small (unrelated) adaptations to the input. It hardly matters whether that change occurs in the sentence itself (S → NP VP), or in the other conjunct (S → S CONJ S), suggesting that the processing of the models is not local as assumed in strong compositionality. Models trained on more data seem more locally compositional, a somewhat contradictory solution to achieving compositional-7 In our manual analysis ( §5), however, we did observe a slightly different distribution of changes between these setups. ity, which, after all, is assumed to underlie the ability to generalise usage from few examples (Lake et al., 2019). This trend is also at odds with the hypothesis that inconsistencies are a consequence of the natural variation of language, which models trained on more data are expected to better capture.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Under a local interpretation of the principle of compositionality, synonym substitutions should be meaning-preserving: substituting a constituent in a complex expression with a synonym should not alter the complex expression's meaning, or, in the case of MT, its translation. Here, we test to what extent models' translations abide by this principle, by performing the substitutivity test from Hupkes et al. (2020), that measures whether the outputs remain consistent after synonym substitution.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
To find synonyms -source terms that translate into the same target terms -we exploit the fact that OPUS contains texts both in British and American English. Therefore, it contains synonymous terms that are spelt different -e.g. "doughnut" / "donut"and synonymous terms with a very different forme.g. "aubergine" / "eggplant". We use 20 synonym pairs in total (see Figure 3b).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Test design Per synonym pair, we select natural data from OPUS in which the terms appear and perform synonym substitutions. Thus, each sample has two sentences, one with the British and one with the American English term. We also insert the synonyms into the synthetic and semi-natural data using 500 samples per synonym pair per template, through subordinate clauses that modify a noun -e.g. "the king that eats the doughnut". In Appendix C, Table 6, we list all clauses used.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Evaluation Like systematicity, we evaluate substitutivity using the consistency score, expressing whether the model translations for a sample are identical. We report both the full sentence consistency and the consistency of the synonyms' translations only, excluding the context. Cases in which the model omits the synonym from both translations are labelled as consistent if the rest of the translation is the same for both input sequences.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In Figure 3a, we summarise all substitutivity consistency scores (tables are in Appendix C). We observe trends similar to the systematicity results: models trained on larger training sets perform better and synthetic data yields more consistent translations compared to (semi-)natural data. We further observe large variations across synonyms, for which we further detail the performance aggregated across experimental setups in Figure 3b. The three lowest scoring synonyms -"flautist", "aubergine" and "ladybug" -are among the least frequent synonyms (see Appendix C), which stresses the importance of frequency for the model to pick up on synonymy.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In Figure 3b, we show both the regular consistency and the consistency of the synonym translations, illustrating that a substantial part of the inconsistencies are due to varying translations of the context rather than the synonym itself, stressing again the non-local processing of the models.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In our final test, we focus on exceptions to compositional rules. In natural language, typical exceptions that constitute a challenge for local compositionality are idioms. For instance, the idiom "raining cats and dogs" should be treated globally to arrive at its meaning of heavy rainfall. A local approach would yield an overly literal, non-sensical translation ("het regent katten en honden"). When a model's translation is too local, we follow Hupkes et al. (2020) in saying that it overgeneralises, or, in other words, it applies a general rule to an expression that is an exception to this rule. Overgeneralisation indicates that a language learner has internalised the general rule (e.g. Penke, 2012).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We select 20 English idioms for which an accurate Dutch translation differs from the literal translation from the English MAGPIE corpus (Haagsma et al., 2020). Because acquisition of idioms is dependent on their frequency in the corpus, we use idioms with at least 200 occurrences in OPUS based on exact matches, for which over 80% of the target translations does not contain a literal translation.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Test design Per idiom, we extract natural sentences containing the idiom from OPUS. For the synthetic and semi-natural data types, we insert the idiom in 500 samples per idiom per template, by attaching a subordinate clause to a noun -e.g. "the king that said 'I knew the formula by heart'". The clauses used can be found in Appendix D, Table 7.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Evaluation Per idiom, we assess how often a model overgeneralises and how often it translates the idiom globally. To do so, we identify keywords that indicate that a translation is translated locally (literal) instead of globally (idiomatic). If the keywords' literal translations are present, the translation is labelled as an overgeneralised translation. For instance, for "by heart", the presence of "hart" ("heart") suggests a literal translation. An adequate paraphrase would say "uit het hoofd" ("from the head"). See Appendix D, Table 7, for the full list of keywords. We evaluate overgeneralisation for ten intermediate training checkpoints.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In Figure 4, we report our results. 8 For all evaluation data types and all training set sizes, three phases can be identified. Initially, the translations do not contain the idiom's keyword, not because the idiom's meaning is paraphrased in the translation, but because the translations consist of highfrequency words in the target language only. Afterwards, overgeneralisation peaks: the model emits a very literal translation of the idiom. Finally, the model starts to memorise the idiom's translation. This is in accordance with results from Hupkes et al. (2020), and earlier results presented in the past tense debate by -among others -Rumelhart and McClelland (1986).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Although the height of the overgeneralisation peak is similar across evaluation data types and training set sizes, overgeneralisation is more prominent in converged models trained on smaller datasets than it is in models trained on the full corpus. 9 In addition to training dataset size, the type of evaluation data used also matters: there is more overgeneralisation for synthetic and seminatural data compared to natural data, stressing the impact of the context in which an idiom is embedded. The extreme case of a context unsupportive of an idiomatic interpretation is a sequence of random words. To evaluate the hypothesis that this yields local translations, we surround the idioms with ten random words. The results (Appendix D, Table 7) indicate that, indeed, when the context provides no support at all for a global interpretation, the model provides a local translation for nearly all idioms. Overall, the results of this test provide an interesting contrast with our substitutivity and systematicity results: where in those tests, we saw processing that was less local than we expected, here, the behaviour shown by the models is instead not global enough.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Our systematicity and substitutivity results demonstrate that models are not behaving compositional according to a strict definition of compositionality. However, we ourselves have argued that strict compositionality is not always appropriate to handle natural language. A reasonable question to ask is thus: are the inconsistencies we marked as noncompositional actually incorrect? 8 Note that epochs consist of different numbers of samples: 1M, 8.6M and 69M for small, medium and full. Appendix D further details numerical results per idiom. 9 Convergence is based on BLEU scores for validation data. Annotation setup To address this question, we perform a manual analysis. We annotate 900 inconsistent translation pairs of the systematicity and substitutivity tests to establish whether the inconsistencies are benign or concerning. We consider four different types of changes: 1. cases of rephrasing, where both translations are equally (in)correct; 2. changes reflecting different interpretations of source ambiguities; 3. cases in which one of the two translations contains an error; 4. formatting (mostly punctuation) changes. For substitutivity samples, we also annotate whether the changes are related to the translation of the synonym, where we distinguish cases where i. one of the synonym translations is incorrect; ii. both are incorrect but in a different manner; iii. both are correct but translated differently; iv. one synonym remains untranslated. We annotate all changes observed per pair and report the relative frequency per class. We summarise the results, aggregated over different training set sizes and the three data types, in Figure 5. For a more elaborate analysis and a breakdown per model and data type, we refer to Appendix F.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In the systematicity test, 40% of the marked inconsistencies reflects wrongfully translated parts in one of the two sentences, whereas 38% contains examples of rephrasing, 16% reflects ambiguities in the source sentences and 6% is caused by formatting differences. For substitutivity, most inconsistencies are similar to the ones observed in systematicity: only 24% involves the synonyms' translations, where one of them being untranslated was the most frequent category. The distribution of these types of inconsistencies differ strongly per training data type. For models trained on less data, inconsistencies are more likely to represent errors, whereas models trained on more data rephrase more often. This result emphasises that for lower-resource settings, being compositional is particularly relevant. Another demonstration of this relevance comes from the observation that although models can emit correct translations for nearly all synonyms, 10 they do not always do so, depending on the context. To give a peculiar example: in "The child admires the king that eats the {doughnut, donut}", the snack was occasionally translated as "ezel" ("donkey").
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Robustness and predictability Finally, we would like to stress that while rephrasing often might seem benign rather than concerning from the perspective of emitting adequate translations, its harmlessness still deserves some thought. There is a fine line between rephrasing and mistranslating: whether "the single largest business establishment" is referred to as "de grootste" ("the largest") or "de enige grootste" ("the only largest") may make or break a translation. Furthermore, if changes are unrelated to the contextual change (e.g. replacing "soccer" with "football"), this can be undesirable from a robustness and reliability perspective. This point becomes even more pronounced in cases where both translations are correct but have a different meaning. To analyse the extent to which inconsistencies are actually unmotivated, we investigated if we could trace them back to the contextual change, in particular focusing on whether changing synonyms from British to American spelling or vice versa might trigger a change in style or tone. We could not find evidence of such motivations, indicating that even correct cases of rephrasing were not caused by contextual changes that were necessary to take into account.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In previous work, a variety of artificial tasks have been proposed to evaluate compositional generalisation using non-i.i.d. test sets that are designed to assess a specific characteristic of compositional behaviour. Examples are systematicity (Lake and Baroni, 2018;Bastings et al., 2018;Hupkes et al., 2020), substitutivity There are also studies that consider compositional generalisation on more natural data. Such studies typically focus on either MT (Lake and Baroni, 2018;Raunak et al., 2019;Li et al., 2021) or semantic parsing (Finegan-Dollak et al., 2018;Keysers et al., 2019;Kim and Linzen, 2020;Shaw et al., 2021). Most of these studies consider small and highly controlled subsets of natural language.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Instead, we focus on models trained on fully natural MT datasets, which we believe to be the setup for compositionality evaluation that does most justice to the complexity of natural language: contrary to semantic parsing, where the outputs are structures created by expert annotators, in translation both inputs and outputs are fully-fledged natural language sentences. To the best of our knowledge, the only attempt to explicitly measure compositional generalisation of NMT models trained on large natural MT corpora is the study presented by Raunak et al. (2019). They measure productivity -generalisation to longer sentence lengthsof an LSTM-based NMT model trained on a fullsize, natural MT dataset. Other studies using NMT, instead, consider toy datasets generated via templating (Lake and Baroni, 2018) or focus on short sentences excluding more complex constructions that contribute to the complexity of natural language for compositional generalisation, such as polysemous words or metaphors (Li et al., 2021).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Whether neural networks can generalise compositionally is often studied using artificial tasks that assume strictly local interpretations of compositionality. We argued that such interpretations exclude large parts of language and that to move towards human-like productive usage of language, tests are needed that assess how compositional models trained on natural data are. 11 We laid out reformulations of three compositional generalisation testssystematicity, substitutivity and overgeneralisation -for NMT models trained on natural corpora, and assessed models trained on different amounts of data. Our work provides an empirical contribution but also highlights vital hurdles to overcome when considering what it means for models of natural language to be compositional. Below, we reflect on these hurdles and our results.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The proxy-to-meaning problem Compositionality is a property of the mapping between the form and meaning of an expression. Since translation is a meaning-preserving mapping from form in one language to form in another, it is an attractive task to evaluate compositionality: the translation of its sentence can be seen as a proxy to its meaning. However, while expressions are assumed to have only one meaning, translation is a many-to-many mapping: the same sentence can have multiple correct translations. This does not only complicate evaluation -MT systems are typically evaluated with BLEU because accuracy is not a suitable option -it also raises questions about how compositional the desired behaviour of an MT model should be. On the one hand, one could argue that for optimal generalisation, robustness, and accountability, we like models to behave systematically and consistently: we expect the translations of expressions to be independent of unrelated contextual changes that do not affect their meaning (e.g. swapping out a synonym in a nearby sentence). Additionally, model performance could be improved if small changes do not introduce errors in unrelated parts of the translation. On the other hand, non-compositional behaviour is not always incorrect -it is one of the main arguments in our plead to test compositionality 'in the wild' -and we observe that indeed, not all noncompositional changes alter the correctness of the resulting translations. Changing a translation from "atleet" ("athlete") to "sporter" ("sportsman") based on an unrelated word somewhat far away may not be (locally) compositional, but is it a problem? And how do we separate such 'harmful' mistakes from helpful ones?
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The locality problem Inextricably linked to the proxy-to-meaning problem is the locality problem. In our tests we see that small, local source changes elicit global changes in translations. For instance, in our systematicity tests, changing one noun in a sentence elicited changes in the translation of a sentence that it was conjoined with. In our substitutivity test, even synonyms that merely differed in spelling (e.g. "doughnut" and "donut") elicited changes to the remainder of the sentence. This counters the idea of compositionality as a means of productively reusing language: if a phrase's translation depends on (unrelated) context that is not in its direct vicinity, this suggests that more evidence is required to acquire the translation of this phrase.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Tests involving synthetic data present the models with sentences in which maximally local behaviour is possible, and we argue that it is, therefore, also desirable. Our experiments show that even in such setups, models do not translate in a local fashion: with varying degrees of correctness, they frequently change their translation when we slightly adapt the input. On the one hand, this well-known volatility (see also Fadaee and Monz, 2020) might be essential for coping with ambiguities for which meanings are context-dependent. On the other hand, our manual analysis shows that the observed noncompositional behaviour does not reflect the incorporation of necessary contextual information and that oftentimes it is even altering the correctness of the translations. Furthermore, this erratic behaviour highlights a lack of default reasoning, which can, in some cases, be problematic or even harmful, especially if faithfulness (Parthasarathi et al., 2021) or consistency is important.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In linguistics, it has been discussed how to extend the syntax and semantics such that 'problem cases' can be a part of a compositional language (Westerståhl, 2002;Pagin and Westerståhl, 2010). In such formalisations, global information is used to disambiguate the problem cases, while other parts of the language are still treated locally. In our models, global behaviour appears in situations where a local treatment would be perfectly suitable and where there is no clear evidence for ambiguity. We follow Baggio (2021) in suggesting that we should learn from strategies employed by humans, who can assign compositional interpretations to expressions but can for some inputs also derive noncompositional meanings. For human-like linguistic generalisation, it is vital to investigate how models can represent both these types of processing, providing a locally compositional treatment when possible and deviating from that when needed.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In conclusion, with this work, we contribute to the question of how compositional models trained on natural data are, and we argue that MT is a suitable and relevant testing ground to ask this question. Focusing on the balance between local and global forms of compositionality, we formulate three different compositionality tests and discuss the issues and considerations that come up when considering compositionality in the context of natural data. Our tests indicate that models show both local and global processing, but not necessarily for the right samples. Furthermore, they underscore the difficulty of separating helpful and harmful types of non-compositionality, stressing the need to rethink the evaluation of compositionality using natural language, where composing meaning is not as straightforward as doing the math. 
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The semi-natural data that we use in our test sets is generated with the library DiscoDOP, 12 developed for data-oriented parsing (Van Cranenburgh et al., 2016). We generate the data with the following seven step process:
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 1. Sample 100k English OPUS sentences.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 2. Generate a treebank using the disco-dop library and the discodop parser en ptb command. The library was developed for discontinuous data-oriented parsing. Use the library's --fmt bracket to turn off discontinuous parsing.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 3. Compute tree fragments from the resulting treebank (discodop fragments). These tree fragments are the building blocks of a Tree-Substitution Grammar.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 4. We assume the most frequent fragments to be common syntactic structures in English. To construct complex test sentences, we collect the 100 most frequent fragments containing at least 15 non-terminal nodes for NPs and VPs.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 5. Selection of three VP and five NP fragments to be used in our final semi-natural templates. These structures are selected through qualitative analysis for their diversity.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 6. Extract sentences matching the eight fragments (discodop treesearch).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Step 7. Create semi-natural sentences by varying one lexical item and varying the matching NPs and VPs retrieved in Step 6.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In Table 2, we provide examples for each of the ten templates used, along with the internal structure of the complex NP or VP that is varied in the template. In Table 3, we provide some additional examples for our ten synthetic templates. An article about (NP (NP ) (PP (IN ) (NP (NP ) (, ,) (SBAR (S (WHNP (WDT )) (VP )))))) , is read by the Npeople . E.g. An article about the criterion on price stability , which was 27 % , is read by the child .  (IN ) (NP )))))))) ?
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
E.g. Did the lawyers hear about a qualification procedure to examine the suitability of the applicants ? Table 2: Semi-natural data templates along with their identifiers (n). The syntactic structures for noun and verb phrases in purple are instantiated with data from the OPUS collection. Generated data from every template contains varying sentence structures and varying tokens but the predefined tokens in black remain the same. The Npeople and the Npeople V pl transitive the N sl people . E.g. The poet and the child understand the mayor . 5
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The N sl quantity of N pl people P the N sl vehicle V sl transitive the N sl people . E.g. The group of friends beside the bike forgets the queen . 6
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople Vtransitive that the N pl people V pl intransitive.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
E.g. The farmer sees that the lawyers cry . 7
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople Adv Vtransitive that the N pl people V pl intransitive . E.g. The mother probably thinks that the fathers scream . 8
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople Vtransitive that the N pl people V pl intransitive Adv . E.g. The mother thinks that the fathers scream carefully . 9
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The Npeople that Vintransitive Vtransitive the N sl people . E.g. The poets that sleep understand the queen . 10 The Npeople that Vtransitive Pro V sl transitive the N sl people . E.g. The mother that criticises him recognises the queen .   
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Synonyms employed In Table 5, we provide some information about the synonymous word pairs used in the substitutivity test, including their frequency in OPUS and their most common Dutch translation. The last column of the table contains the subordinate clauses that we used to include the synonyms in the synthetic and semi-natural data. We include them as a relative clause behind nouns representing a human, such as "The poet criticises the king that eats the doughnut".
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Detecting synonym translations To find the span of text in the translation which is the translation of the synonym, we apply a relatively simple heuristic. We generate a number of short sentences such as "This is the NOUN", feed those to all our trained models, and extract the top-5 answers in the beam. We then use the list of all words resulting from this protocol -which we manually checked -to find synonym translations in the model output.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In the main paper, Figures 3a and 3b provided the consistency scores for the substitutivity tests. Here, Table 6 further details the results from the figure, by presenting the average consistency per evaluation data type and training set size, and per evaluation data type and synonym pair.   
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Idioms employed Table 7 provides more information on the idioms used in our global compositionality test. In the first column, we list all idioms we used, along with the keywords that we used to determine if their translation is local or not. To extract the natural data, we retrieved exact matches with OPUS source sentences. The idioms' keywords are mostly nouns that either translate into a different word in an accurate paraphrased translation in Dutch (e.g. "across the board" would be "over de hele linie"), or should disappear in the translation (e.g. "do the right thing" typically translates into "het juiste doen" in the corpus).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In the second column of Table 7, we list the subordinate clauses that we used to include idioms in the synthetic and semi-natural data. The clauses themselves are drawn from source sentences in OPUS. To incorporate them in synthetic and semi-natural sentences, we include them as a relative clause behind nouns representing a human, by attaching "that said '[idiom]"'. For instance: "The poet criticises the king that said 'Have you gone out of your mind'."
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In the third column of Table 7, we show local translations of the idioms, elicited from the model by embedding the idiom in a string of ten random nouns. Even "out of the blue", which is rarely overgeneralised when presented in synthetic, semi-natural or natural contexts, is locally translated. This indicates that the idiom is not stored as one lexical unit per se but that it is only translated globally in specific contexts.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In the main paper, in Figure 4, we visualised how overgeneralisation changes over the course of training, averaged over idioms. In Table 8, we detail the maximum overgeneralisation observed per idiom.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Subordinate clause Local translation once in a while that said " I will play it once in a while " eens in een tijdje do the right thing that said " Just do the right thing " doen het juiste ding out of your mind that said " Have you gone out of your mind " uit je hoofd state of the art that said " This is a state of the art, official facility " stand van de kunst from scratch that said " We are cooking from scratch every day " van kras take stock that said " Take stock of the lessons to be drawn " nemen voorraad across the board that said " I got red lights all across the board " aan boord in the final analysis that said " In the final analysis, this is what matters " in de laatste analyse out of the blue that said " It just came out of the blue " uit het blauwe in tandem that said " We will work with them in tandem " in tandem by heart that said " I knew the formula by heart " door hart come to terms with that said " I have come to terms with my evil past " komen overeen met by the same token that said " By the same token I will oppose what is evil " bij dezelfde token at your fingertips that said " The answer is right at your fingertips " binnen handbereik look the other way that said " We cannot look the other way either " kijken de andere manier follow suit that said " And many others follow suit " volgen pak keep tabs on that said " I keep tabs on you " houden tabs in the short run that said " In the short run it clearly must be " in de korte lopen by dint of that said " We are part of it by dint of our commitment " door de int set eyes on that said " I wish I had never set eyes on him " set ogen op   97 .90 .25 .23 .47 natural small .80 .51 .80 .97 .84 .31 .75 .96 .92 .82 .88 .14 .74 .60 1.0 .40 .96 .29 .23 .87 medium .80 .50 .82 .96 .84 .32 .71 .94 .92 .68 .90 .22 .74 .63 .99 .39 .61 .33 .29 .84 full .79 .39 .83 .95 .90 .36 .83 .98 .95 .89 .90 .11 .65 .55 1.0 .65 .56 .19 .27 .76  Preprocessing We tokenise the data using the tokenisation script 13 from the SMT library Moses. 14 Following the number of subwords suggested by Tiedemann (2020), we generate a subword vocabulary applying 60k BPE merge-operations. To do so, we use the learn bpe.py script provided in the SUBWORD NMT 15 repository hosted by Rico Sennrich.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Different corpora We train models on three different sizes of corpora: SMALL, MEDIUM and FULL.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
To generate these corpora, we first shuffle the OPUS training data using the bash function shuffle. To generate the SMALL and MEDIUM corpora, we take the first 8582811 and 1072851 sentences of this shuffled corpus, which corresponds to 1 8 th and 1 64 th of the full training corpus, respectively. For each setting, we train models with seeds {1, 2, 3, 4, 5}.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Test and validation data Initially, we aimed to evaluate our models using the commonly used MT test sets OPUS-100 16 and the test partition of the TED talk corpus. 17 However, it turned out that both these test sets were almost fully contained in our training corpus. We, therefore, adopted the newer FLORES-101 corpus (Goyal et al., 2021), of which we used both the 'dev' and the 'devtest' set. The data can be downloaded from https://dl.fbaipublicfiles.com/flores101/dataset/flores101 dataset.tar.gz. To compute BLEU scores, we tokenised the data with the Moses tokenisation script mentioned above, and then used the commandline script fairseq-generate to compute scores.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We furthermore use several evaluation sets to assess the compositional abilities of our trained models. The data for these tests, as well as scripts to run them and plot their results, can be found in the following repository: https://github.com/i-machine-think/compositionality paradox mt.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
As reported in the main text, we focus on English-Dutch translation, and all our models are Transformerbase models, as implemented in Fairseq (Ott et al., 2019). 18 Both the encoder and the decoder of this model have an embedding dimension of 512, 6 layers, 8 attention heads and a feed-forward layer dimension of 2048. With our vocabulary, the models have a total of around 80M trainable parameters.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
To train our models, we follow the training procedure suggested by Ott et al. (2018), which can be found at https://github.com/pytorch/fairseq/tree/master/examples/scaling nmt. To summarise, we share all embeddings between the encoder and the decoder, use Adam as optimiser with β-values (0.9, 0.98),  starting from an initial warmup learning rate of 1e-07 for 4000 warmup updates and a learning rate of 0.0005 afterwards, using inverse square root as the learning rate scheduler. We use a clip-norm of 0.0, dropout of 0.3, weight-decay of 0.0001, label-smoothing of 0.1. The maximum number of tokens in a batch is 3584, we simulate larger batches by increasing the update frequency to 8. To determine early stopping, we use a patience of 10 (i.e. we stop training if a model does not improve on the dev set anymore for 10 epochs, and take the best checkpoint at that point). Any other hyperparameters involved follow the Fairseq default. We provide the BLEU scores per model seed in Table 9.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
All experiments were ran using Tesla V100 GPUs on an internal SLURM-based cluster. Training a transformer-base model on our small, medium and full dataset takes on average 3.5, 17 and 113 minutes per epoch, respectively (numbers are rounded) on 32 GPUs. This makes the total training time for these models, which are trained for around 160, 60 and 30 epochs, 10, 17 and 56 hours, respectively (again, spread over 32 GPUs).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Our quantitative tests provide information on when a model behaves locally and when globally in automated form but they do not consider whether that behaviour is incorrect or not. More simply put, we do not know whether the changes that we observe are actually resulting in incorrect translations. We complement these scores with an elaborate manual analysis, which provides more insight into the nature of the non-compositional behaviour we registered. Annotation procedure For each of these samples, we annotate how they differ, where we distinguish between four general categories: i. Rephrasing: part of the sentence is rephrased (but both phrases are equally (in)correct); ii. Source ambiguities: there is an ambiguity in the source sentence, and the model switches its interpretation; iii. Errors: one of the translations contains an error that the other one does not; iv. Formatting: minor formatting changes, consisting mostly of insertions/deletions of punctuation. For the substitutivity data, we separately annotate changes that are related to the translation of the synonym, where we distinguish cases in which both synonyms are correctly or incorrectly translated from cases in which one of the translations is correct. We annotate all changes observed in a sample -one sentence may thus contain annotations for multiple changes -and report the relative frequency of each class of errors. 
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We provide a summary of the results in Figure 6 for systematicity and Figure 7 for substitutivity. As a general trend, the results reflect that in models trained on smaller datasets, more mistakes are actually errors, rather than multiple correct alternatives. In the systematicity test, 59% of the inconsistencies for the models trained on the smallest dataset are erroneous changes, versus 34% and 27% in the models trained on the medium and largest dataset, when we average the percentages over the different subsets annotated. For substitutivity, the percentage of erroneous changes unrelated to the synonyms comprises 46%, 18% and 22% for the smallest, medium and full dataset, respectively. On top of that, there were inconsistencies related to the synonyms, that represented 26%, 26% and 21% for the three dataset sizes, respectively. While this is expected, to some extent, it still constitutes a problem: for models trained on smaller amounts of data, being able to translate in a compositional manner is particularly relevant. Below, we further elaborate on the types of inconsistencies encountered per annotation category, including some examples. 
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
A large portion of the inconsistencies concerns pairs where one translation can be considered a rephrased version of the other translation. A common cause of this is a reordering of words that does not impact the grammaticality or meaning of the Dutch sentence -e.g. in sentences with adverbs ("heeft de burgemeester zeker in de gaten" vs "heeft zeker de burgemeester in de gaten") or relative clauses with direct objects ("die genieten van de vakantie" vs "die van de vakantie genieten"). We could not trace these reorderings back to the specific change made in the systematicity or substitutivity tests. Consider, for instance, Example (1), where the reordering happens as a consequence of changing the word "king" to "father". Note also that while these translations both contain an error ("neemt . . . in de gaten"), this is not marked as an inconsistency, because it is shared between the translations.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(1) a. EN: The aunts criticise the {king, father}, and the man definitely observes the mayor. b. NL: (. . . ) en de man neemt zeker de burgemeester in de gaten. c. NL: (. . . ) en de man neemt de burgemeester zeker in de gaten.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Another commonly occurring case of rephrasing is one where the two translations include terms that are (nearly) synonymous terms in Dutch. Some examples are the translation of athlete ("sporter" vs "atleet"), wish ("wensen" vs "willen") and observe ("observeren" vs "waarnemen"). Some of them can appear in the same context but for others the two words would typically appear in different types of texts. For instance, the word "dokter" is used in more informal contexts than the word "arts" (both translations of "doctor"). Again, we could not identify an interpretable pattern for when the model emits one instead of the other -they were not understandably related to the modifications we made to the inputs.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
An intriguing category that we had not anticipated were cases in which the source sentence contained ambiguities, such as polysemous words (e.g. "director" translated to "directeur", referring to the director of a company, and "regisseur", indicating the director of a movie). Other ambiguities encountered were scope ambiguities, that were particularly prominent for the systematicity test. In that test, we concatenate two sentences, and the ambiguity was often related to the verb in the first sentence -e.g. in Example (2): (2) a. EN: The friend wishes that the {lawyers, directors} scream, and the victims (. . . )
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
While we intended this to be a conjunction of two independent sentences, there is also a reading where "wishes" takes scope over the entire second conjunct. In Dutch, those two cases are distinguishable because they trigger a different word order in the embedded clause (SOV), which is not grammatical for main clauses. Such scope changes often lead to very questionable interpretations of the English sentence, as is the case for Example (3):
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(3) a. EN: The victims want that the {doctors, mayors} run, and the victims read an article about the case of a procedure which includes a repayment plan. b. EN: The farmers think that the {butchers, mothers} laugh, and an error can only be seen whenever we have a basic plan that is constantly compared to our real actions. c. EN: The women wish that the {painters, victims} walk consciously, and every 2CV or Dyane can basically be used as a donor.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Interestingly, the models sometimes also changed the order in the relative clause when a scope change was not possible, for instance when the second conjunct was a question, or the verb in the first sentence did not allow to take scope over the second conjunct without the presence of the word "that". See Example (4). We underline the incorrect part of the translation, here and in erroneous examples that follow.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(4) a. EN: The victim observes the {leader, king}, and the fathers carefully avoid the president. b. NL: Het slachtoffer observeert de leider en de vaders de president zorgvuldig vermijden. c. NL: Het slachtoffer observeert de koning en de vaders vermijden voorzichtig de president.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
These examples indicate that the interpretation of scope change might not be applicable here and that instead, the model is applying some heuristic where particular words trigger a relative clause order.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
In the category 'target errors', some of the errors can be easily traced to individual words, whereas others indicate overall misinterpretations of the input.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Single word errors Errors that consist of single words are caused by words that are either missing, wrongly translated or untranslated. Changes due to missing words can be very minor but nevertheless render one of the sentences ungrammatical (e.g. "De tante achter de truck bewonderde de directeur", correct, vs "De tante achter de truck bewonderde directeur", incorrect), or yield grammatical sentences that have a slightly different meaning (e.g. "de arts die yoghurt eet" vs "de arts die de yoghurt eet"). Missing words can also render translations both ungrammatical and semantically incorrect, which occured mostly in case of missing nouns or verbs (e.g. "de bakker die ons herkent, merkt de koning op", correct, vs "de bakker die ons de koning herkent", incorrect). We also encoutered pairs where one translation contained untranslated source words. This happened with some of the words in our synthetic templates (e.g. "ooms"/"uncles", "butchers"/"slagers") but also with words from the natural sentences (e.g. "extrusion"/"extrusie", "soils"/"bodem"). These cases mark examples where local processing would have been helpful to the model: as evidenced by the alternative translation in the pair, the model does have access to the correct translation.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Thirdly, we observed cases of mistranslated words, where words unrelated to the change locus received a wrong translation in one of the two sentences but a correct one in the other, for example: "poets" being translated as "dichters" (correct) vs "de potten" (incorrect), "general" as "generaal" (correct) vs "wandeling" (incorrect), or "productform" as "productvorm" (correct) vs "productformulier" (incorrect).
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
Multi-word errors Other types of errors are less easily located to individual words but indicate an overall misinterpretation of the input, such as the change in the tense as displayed in Example (5), and the change in agreement displayed in Example (6). In these particular cases, the source of confusion is explainable: in the first case, the model is combining a present tense verb with a word-order that does not support that, even though such a word order does exist ("in het najaar van 2005 . . . en komen er al snel een paar . . . "). In the second case, "begrijpt" should agree with "schilder" but instead agrees with the word "doctor", much earlier in the sentence. In both of these cases, a more locally compositional approach to translating would have yielded correct translations.  Finally, we would like to point out an error type that relates to the semantic role assigned to agents, and brings about a lot of other changes in the process. For instance, in Example (7), "the fathers" is removed from the main clause and moved into the relative clause, leaving the main clause without its direct object.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(7) a. EN: The group of painters behind the truck forgets the {president, friend} and an article about the previous EESC Opinion on alcohol related harm, which looked at f, is read by the fathers b. NL: (. . . ) en een artikel over het eerdere advies van het EESC over alcoholgerelateerde schade, die door de vaders wordt onderzocht, wordt gelezen. c. NL: (. . . ) en een artikel over het eerdere advies van het EESC over alcoholgerelateerde schade, die naar f uitkeek, wordt door de vaders gelezen.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
We marked inconsistencies as formatting changes if they were related to punctuation, capitalisation, hyphenation or differences in usage of spaces. In most cases, those cases were caused by comma's: in one translation, a relative clause or two conjuncts were separated by a comma, whereas the other one was not. In the cases that were caused by spaces ("tumormassa" vs "tumor massa"), there is a slight difference in correctness: in Dutch, compound nouns are not separated by spaces. Given how minor these mistakes are, we did not mark them as errors. Example (6) above provides an example for inconsistent usage of commas. Formatting changes are far from the most frequent but they do become more prominent in models trained on larger training corpora.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
The synonym errors are subdivided into cases where synonyms are simply translated differently (we observed this mostly for the models with larger training set sizes), cases where both translations were incorrect, cases in which only one translation is wrong, and cases in which one synonym was not translated but directly copied from the source. Sometimes, the changes were quite peculiar, to give some examples from our natural corpus:
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(8) a. EN: The child admires the king that eats the {doughnut, donut}. b. NL: Het kind bewondert de koning die de donut eet. c. NL: Het kind bewondert de koning die de ezel eet.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
(9) a. EN: -Yeah, a barbecue sauce {moustache, mustache} contest. b. NL: -Ja, een barbecue [missing 'sauce'] met snor. c. NL: -Ja, een barbeceu saus snor wedstrijd.
The Paradox of the Compositionality of Natural Language: A Neural Machine Translation Case Study
How often each of these errors occur depends on the synonym. Where some synonyms are more prone to being untranslated (like "ladybird" and "flautist"), some simply received many different correct translations (like "shopping trolley") yet others received errors very specific to the synonym (like "eggplant" being translated as "egg"+"plant", an interesting case because it reflects processing that is too local). It should be noted that for all synonyms -apart from the model with the small training dataset that cannot translate "flautist" and "ladybug" -we have observed correct translations, indicating that the models did in fact acquire their meaning. Further, it should be noted that while our substitutivity experiment provides insight into how the model copes with individual synonyms, the majority of the inconsistencies observed were still common target errors, rephrasings, changes in formatting or the result of source-side ambiguities. It is vital here to stress that the types of rephrasings, however, did not appear related to the writing style of the sentence. For instance, considering that the synonym changes were related to British and American spelling, and occassionally changed the tone of the sentence (e.g. "aeroplane" could be considered more archaic compared to "airplane"), one could anticipate changes in word choice in Dutch reflecting this change of style. However, the inconsistencies were virtually indistinguishable from those annotated for systematicity.