COGS : A Compositional Generalization Challenge Based on Semantic Interpretation (2020)

Abstract: 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 (+-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.

## introduction humans can produce and understand linguistic expressions that they have not encountered before, by systematically combining atomic building blocks @xcite . 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 @xcite . 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 ). to assess the abilities of computational models of language to generalize compositionally, we propose cogs, a compositional generalization challenge based on semantic interpretation, in 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. rule-based semantic parsing systems such as boxer @xcite 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 @xcite . 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. 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 @xmath0. crucially, their training/evaluation split required compositional generalization. a number of models have been developed that have improved performance on scan @xcite . 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 @xcite and semantic parsing @xcite . following @xcite and @xcite , we cast semantic parsing as a sequence-to-sequence problem. ## overview of cogs in a semantic parsing task such as cogs, the goal is to map a sentence to a logical form. following recent works such as @xcite and @xcite , 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 foot_0 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: a hedgehog ate the @xmath1; 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. we describe below the five categories of generalizations targeted by cogs (see ## experiments 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 @xcite , both in an encoder-decoder setup @xcite . transformers have been quickly adopted in practical nlp systems @xcite , but the literature has reported mixed results on the benefit of transformers over lstms in terms of linguistic generalization @xcite . 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. ## comparison to related work our aggregate results in our finding of poor generalization to deeper nested structures aligns with the results of @xcite . 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 @xcite @xcite . the most similar work to ours is compositional freebase questions (cfq; @xcite ), 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. our work is related to but distinct from work that tests language models for systematic syntactic generalization @xcite . unlike our work, the language modeling setup does not directly evaluate the meaning that the model assigns to a sentence. ## constraints on generalization 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 @xcite . 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 @xcite . 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. ## conclusion 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. what architecture would be needed to solve cogs? for structural generalization cases, the results of @xcite ; @xcite and @xcite suggest that treestructured models may provide a better inductive bias. in particular, @xcite showed that tree-structured neural networks generalized to longer sequences. for lexical generalization cases, the rnn-based model from @xcite that implements permutation equivariance may help, considering that it was able to solve all primitive generalizations in scan.