Unobserved Local Structures Make Compositional Generalization Hard (2022)

Abstract: While recent work has shown that sequence-to-sequence models struggle to generalize to new compositions (termed compositional generalization), little is known on what makes compositional generalization hard on a particular test instance. In this work, we investigate the factors that make generalization to certain test instances challenging. We first substantiate that some examples are more difficult than others by showing that different models consistently fail or succeed on the same test instances. Then, we propose a criterion for the difficulty of an example: a test instance is hard if it contains a local structure that was not observed at training time. We formulate a simple decision rule based on this criterion and empirically show it predicts instance-level generalization well across 5 different semantic parsing datasets, substantially better than alternative decision rules. Last, we show local structures can be leveraged for creating difficult adversarial compositional splits and also to improve compositional generalization under limited training budgets by strategically selecting examples for the training set.

## introduction recent analyses of pre-trained sequence-tosequence (seq2seq) models have revealed that they do not perform well in a compositional generalization setup, i.e., when tested on structures that were not observed at training time (lake and @xcite . however, while performance drops on average, models do not categorically fail in compositional setups, and in fact are often able to successfully emit new unseen structures. this raises a natural question: what are the conditions under which compositional generalization occurs in seq2seq models? measuring compositional generalization at the dataset level obscures the fact that for a particular test instance, performance depends on the instance sub-structures and the examples observed during training. consequently, it might be possible to predict how difficult a test instance is given the test instance and the training set. indeed, papers that provide multiple compositional splits @xcite have demonstrated high variance in accuracy across splits. in this paper, we investigate the question of what makes compositional generalization hard in the context of semantic parsing, the task of mapping natural language utterances to executable programs. first, we create a large set of compositional train/test data splits over multiple datasets, in which there is no overlap between the programs of the test set and the training set. we then fine-tune and evaluate multiple seq2seq models on these splits. our first finding is that different models tend to agree on which test examples are difficult and which are not. this indicates example difficulty can be mostly explained by the example itself and the training data, independent of the model. this calls for a better characterization of what makes a test instance hard. to this end, we analyze the factors that make compositional generalization hard at the instance level. we formulate a simple decision rule that predicts the difficulty of test instances across multiple splits and datasets. our main observation is that dataset example covr @xcite what is the number of gray square cat that is looking at mouse? count (with_relation (filter (gray, filter (square, find(cat))), looking_at, find (mouse))) schema2qa (synthetic) are there people that works for crossbars ? ( person ) filter worksfor contains "crossbars" atis (natural) round trip flights between new york and miami (lambda @xmath00) (round_trip @xmath10 new_york: ci) (to $0 miami: ci))) a test instance is hard if it contains a local structure that was not observed at training time. an unobserved local structure is defined as a small connected sub-graph that occurs in the program of the test instance, but does not occur in the training set. moreover, unobserved structures render an instance difficult only if there are no observed structures that are similar to the unobserved one, where similarity is defined through a simple distributional similarity metric. fig. 1 presents two splits that contain a tree with the same local structure in the test set. split 1 is easy because the training set contains similar local structures: exists is similar to all and some. conversely, in split 2 emitting the unobserved structure will be hard, as there are no similar observed structures in the training set. we empirically evaluate our decision rule on five different datasets with diverse semantic formalisms, and show it predicts instance-level generalization well for both synthetic and natural language inputs, with an area under curve (auc) score ranging from 78.4 to 93.3 (across datasets), substantially outperforming alternative rules. moreover, we compare our approach to mcd @xcite , a metric that has been used to characterize difficulty at the dataset level (and not the instance level). we show our rule can be generalized to the dataset level and outperforms mcd in predicting the difficulty of various compositional splits. last, we find that our decision rule applies not just to transformers, but also to lstm decoders. with these insights, we use our decision rule for two purposes. first, we develop a method for creating difficult compositional splits by picking a set of similar local structures, and holding out instances that include any of these structures. we show that seq2seq models get much lower accuracy on these splits compared to prior approaches. second, we propose a data-efficient approach for selecting training examples in a way that improves compositional generalization. given a large pool of examples, we select a training set that maximizes the number of observed local structures. we show this leads to better compositional generalization for a fixed budget of training examples. we release code and data at https://github.com/benbogin/ unobserved-local-structures . ## setup we focus on semantic parsing, where the task is to parse an utterance x into an executable program z. in a compositional generalization setup, examples are split into a training and a test set, such that there is no overlap between programs in the two sets. we use two methods to generate compositional splits. the first is the template split, proposed in @xcite , where examples are randomly split based on an abstract version of their programs. additionally, we propose a grammar split, which can be used whenever we have access to the context-free grammar rules that generate the dataset programs. a grammar split is advantageous because, unlike the template split, it creates meaningful splits where particular structures are held out. for details on these split methods see app. b. ## model agreement across examples our goal is to predict the difficulty of test instances. however, first we must confirm that (1) splits contain both easy and difficult instances and (2) different models agree on how difficult a specific instance is. to check this, we evaluate different models on multiple splits. ## what makes an instance hard? the results in §3 provide a set of test instances of various difficulties from a variety of compositional splits. we analyze these instances and propose a hypothesis for what makes generalization to a test instance difficult. ## experiments we now empirically test how well our decision rule predicts the easiness of test instances. setup we formalize our setup as a binary classification task where we predict the easiness ê(p u ) ∈ [0, 1] of a test instance (utterance-program pair) with program p u , and compare it to the "gold" easiness e(p u ) ∈ {0, 1}, as defined next. for each test instance, we have the em accuracy of four models ( §3). we thus define e(p u ) to be the majority em on p u between the four models. we discard examples with no majority (3.6%-6.9% of the cases). in each dataset, we combine all test instances across all splits. we evaluate with area under the curve (auc), a standard metric for binary classification that does not require setting a threshold, where we compute the area under the curve of the true positive rate against the false positive rate. ## leveraging local structures we show we can take advantage of the insights presented to (1) create challenging compositional splits ( §6.1) and (2) to improve data sampling efficiency for compositional generalization ( §6.2). ## discussion limitations in this work we only use the programs of test instances to predict difficulty, but ignore the utterance. thus, we do not take into account language variability, which could play a factor in compositional splits. in addition, we analyze datasets where models get high i.i.d accuracies. our decision rule may not work when other difficulties conflate with the compositional challenge. conclusion we have shown that unobserved local structures have a critical role in explaining the difficulty of compositional generalization over a variety of datasets, formal languages, and model architectures, and demonstrated how these insights can be used for the evaluation of compositional generalization, and to improve data efficiency given a limited training budget. we hope our insights would be useful in future work for improving generalization in sequence to sequence models. yushi wang, jonathan berant, and percy liang. 2015. building a semantic parser overnight. in proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: long papers), pages 1332-1342, beijing, china. association for computational linguistics. silei xu, giovanni campagna, jian li, and monica s. lam. 2020. schema2qa: high-quality and low-cost q&a agents for the structured web, page 1685-1694. association for computing machinery, new york, ny, usa.