Compositional Generalization in Dependency Parsing (2022)

Abstract: Compositionality— the ability to combine familiar units like words into novel phrases and sentences— has been the focus of intense interest in artificial intelligence in recent years. To test compositional generalization in semantic parsing, Keysers et al. (2020) introduced Compositional Freebase Queries (CFQ). This dataset maximizes the similarity between the test and train distributions over primitive units, like words, while maximizing the compound divergence: the dissimilarity between test and train distributions over larger structures, like phrases. Dependency parsing, however, lacks a compositional generalization benchmark. In this work, we introduce a gold-standard set of dependency parses for CFQ, and use this to analyze the behaviour of a state-of-the art dependency parser (Qi et al., 2020) on the CFQ dataset. We find that increasing compound divergence degrades dependency parsing performance, although not as dramatically as semantic parsing performance. Additionally, we find the performance of the dependency parser does not uniformly degrade relative to compound divergence, and the parser performs differently on different splits with the same compound divergence. We explore a number of hypotheses for what causes the non-uniform degradation in dependency parsing performance, and identify a number of syntactic structures that drive the dependency parser’s lower performance on the most challenging splits.

## introduction people understand novel combinations of familiar words in part due to the principle of compositionality: we expect the meaning of a phrase to be a predictable composition of the meanings of its parts. unlike humans, many neural models fail to 1 figure 1 : an example question from the cfq dataset, with the associated sparql query and dependency parse. one recently-introduced semantic parsing dataset, compositional freebase queries (cfq), consists of english questions with corresponding database queries written in sparql. figure 1 shows an example question and sparql query. to test compositional generalization, cfq includes test and train sets with a highly similar distribution of primitive units (like words) and increasingly divergent distribution of larger compound units (like phrases). the most challenging of these splits, with the highest compound divergence, are dubbed maximum compound divergence (mcd) splits. although cfq has proven to be a valuable resource, the difficulty of the splits appears to be influenced by factors other than compositional generalization. first, some evidence suggests that the complexity of the sparql output is in part responsible for cfq performance @xcite . furthermore, splits of the same compound divergence are not equally difficult. one possible explanation is a difference in the syntactic constructions of different splits; however, this has not yet been explored in cfq. to address these issues, we created a dependency-parsing version of cfq. using our dataset, we evaluated a state-ofthe-art dependency parser for compositional generalization, and used the dependency annotations to identify syntactic structures predictive of parsing failure on each mcd split. we found that the dependency parser is more robust to increased compound divergence than the semantic parser, but performance still decreased with higher compound divergence. we also found the dependency parser, like semantic parsers, varied widely in performance on different splits of the same compound divergence. finally, we found that a small number (less than seven) of syntactic constructions seem to drive the difficulty of the mcd splits. our dataset is publically available on github. 1 ## corpus construction: dependency parses for cfq to train a dependency parser and analyze syntactic structures in the cfq dataset, we created a corpus of gold dependency parses. because the questions in cfq are synthetically generated, we were able to write a full-coverage context-free grammar for the cfq language (see appendix c). using this grammar, and the chart parser available in python's natural language toolkit, we generated a constituency parse for each question. finally, we designed an algorithm to map to the dependency parse. to map from constituency to dependency parses, we wrote a dependency-mapping rule for each production rule in the cfg @xcite . each dependency rule describes the dependency relation between the elements in the constituent; for example, if the production rule is vp -→ v np, the dependency-mapping rule connects the head of the right-hand node (the head of np) as a dependent of the left-hand node (the v), with the arc label obj. we follow version two of the universal dependencies corpus annotation standards @xcite ), foot_0 but simplify the categorization of nominal subjects for active and passive verbs into one category (nsubj), and do not include part of speech tags in the dataset. our algorithm then recursively walks the constituency tree from bottom to top, mapping nonhead children of each node to their syntactic heads and passing the head of each constituent up the tree. a number of sentences in the cfq dataset exhibit dependency structures which cannot be directly read off the constituency parse in this manner: such right-node-raising constructions involve a word without a syntactic head in the immediate constituent. for example, in "was tonny written by and executive produced by mark marabella?" the first instance of "by" is a dependent of "mark marabella", but its immediate constituent is "di-rected by". to handle right-node raising cases, our dependency-mapping algorithm identifies prepositions with no head in the immediate constituent, and passes them up the tree until they can be attached to their appropriate syntactic head. finally, we performed a form of anonymization on the questions, replacing entities with singleword proper names. this reflects the anonymization strategy used in @xcite , and prevents the dependency parser from failing because of named entities with particularly complex internal syntax (for example, "did a swedish film producer edit giliap and who saw him die?") the experiments in this paper are based on the original cfq splits. however, these validation sets are constructed from the same distribution as the test sets; some information about the test distribution is therefore available during train. to ensure that the model only had access to the training distribution during the training phase, we followed the suggestion of @xcite and discarded the mcd validation sets, foot_1 randomly sampling 20% of the training data to use instead (see § 5.1 of that paper for more details). the resulting splits have 11, 968 test sentences and 76, 595 train sentences. ## construction complexity and the mcd splits the compound divergence metric treats all compounds of any number of words identically; therefore, the differences between the mcd splits may be driven by differing distributions of compounds of different complexities. in this section, we show that this is not the case. we first describe how we characterize syntactic constructions using the dependency annotations. ## related work a growing body of work uses cfq to investigate better models for compositional generalization in semantic parsing @xcite @xcite . @xcite also recently released an expanded version of cfq called *-cfq, which remains challenging for transformers even when they are trained on much more data. our methodology can be easily be applied to *-cfq at the cost of a straight-forward extension of the grammar. other datasets focused on compositional generalization include scan @xcite , a dataset of english commands and navigation sequences; gscan @xcite , a successor to scan with grounded navigation sequences; and cogs @xcite , where english sentences are paired with semantic representations based on lambda calculus and the udeplambda framework @xcite . in contrast to cfq, these datasets challenge models by targeting specific, linguistically-motivated generalizations. for example, cogs includes tests of novel verb argument structures (like training on a verb in active voice and testing in passive voice), and novel grammatical roles for primitives (like training with a noun in object position and testing in subject position); similarly, scan includes splits which test novel combinations of specific predicates (training a predicate "jump" or "turn left" in isolation, and testing it composed with additional predicates from train). finally, the closure benchmark for visual question answering tests systematic generalization of familiar words by constructing novel referring expressions; for example, "a cube that is the same size as the brown cube" @xcite . ## conclusion in this paper, we presented a dependency parsing version of the compositional freebase queries (cfq) dataset. we showed that a state-of-the-art dependency parser's performance degrades with increased compound divergence, but varies on different splits of the same compound divergence. finally, we showed the majority of the parser failures on each split can be characterized by a small (seven or fewer) number of specific syntactic structures. to our knowledge, this is the first explicit test of compositional generalization in dependency parsing. we hope that the gold-standard dependency parses that we have developed will be a useful resource in future work on compositional generalization. existing work on syntactic (and in particular dependency) parsing can provide researchers in compositional generalization with ideas and inspiration which can then be empirically validated using our corpus. finally, our work represents a step forward in understanding the syntactic structures which drive lower performance on mcd test sets. predicting parser performance from the syntactic constructions contained in the question provides a new method for understanding the syntactic structures that can cause parser failure; in future work, similar methods can also be used to better understand failures of semantic parsers on the cfq dataset.