Unobserved Local Structures Make Compositional Generalization Hard

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 2731 - 2747 December 7-11, 2022 ©2022 Association for Computational Linguistics Unobserved Local Structures Make Compositional Generalization Hard Ben Bogin1 Shivanshu Gupta2 Jonathan Berant1 1Tel-Aviv University 2University of California Irvine {ben.bogin,joberant}@cs.tau.ac.il, shivag5@uci.edu Abstract While recent work has shown that sequence-to- sequence models struggle to generalize to new compositions (termed compositional general- ization), little is known on what makes com- positional 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 exam- ple: 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 dif- ferent semantic parsing datasets, substantially better than alternative decision rules. Last, we show local structures can be leveraged for cre- ating difficult adversarial compositional splits and also to improve compositional generaliza- tion under limited training budgets by strategi- cally selecting examples for the training set. 1 Introduction Recent analyses of pre-trained sequence-to- sequence (seq2seq) models have revealed that they do not perform well in a compositional generaliza- tion setup, i.e., when tested on structures that were not observed at training time (Lake and Baroni, 2018; Keysers et al., 2020). However, while perfor- mance drops on average, models do not categori- cally fail in compositional setups, and in fact are often able to successfully emit new unseen struc- tures. This raises a natural question: What are the conditions under which compositional general- ization 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 Split 1 Split 2 (hard) (easy) <s> exists filter and *all find find * similar tokens *some and *exists find find *exists and exists find find exists Observed Unobserved BART T5 BART T5 and eq count find find 4 … LSTM LSTM Figure 1: Unobserved local structures are harder for models to generalize to whenever there are no similar structures that were observed during training. training. Consequently, it might be possible to pre- dict how difficult a test instance is given the test instance and the training set. Indeed, papers that provide multiple compositional splits (Kim and Linzen, 2020; Bogin et al., 2021a) have demon- strated 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 map- ping natural language utterances to executable pro- grams. First, we create a large set of compositional train/test data splits over multiple datasets, in which there is no overlap between the programs …

Content truncated to 500 words