Finding needles in a haystack: Sampling Structurally-diverse Training Sets from Synthetic Data for Compositional Generalization (2021)

Abstract: Modern semantic parsers suffer from two principal limitations. First, training requires expensive collection of utterance-program pairs. Second, semantic parsers fail to generalize at test time to new compositions/structures that have not been observed during training. Recent research has shown that automatic generation of synthetic utterance-program pairs can alleviate the first problem, but its potential for the second has thus far been under-explored. In this work, we investigate automatic generation of synthetic utterance-program pairs for improving compositional generalization in semantic parsing. Given a small training set of annotated examples and an “infinite” pool of synthetic examples, we select a subset of synthetic examples that are structurally-diverse and use them to improve compositional generalization. We evaluate our approach on a new split of the schema2QA dataset, and show that it leads to dramatic improvements in compositional generalization as well as moderate improvements in the traditional i.i.d setup. Moreover, structurally-diverse sampling achieves these improvements with as few as 5K examples, compared to 1M examples when sampling uniformly at random – a 200x improvement in data efficiency.

## introduction semantic parsers map natural language utterances to executable programs @xcite . a worrying weakness of semantic parsers that has been recently exposed, is their inability to generalize at test time to new compositions @xcite @xcite @xcite . for example, a virtual assistant trained on the examples "show me thai restaurants that allow pets" and "how many hotels are there in tokyo", might not generalize to "how many hotels in tokyo allow pets?". this type of out-of-domain generalization to new compositions constructed from components seen during training is commonly termed compositional generalization. two high-level approaches have been considered for tackling compositional generalization: (a) designing models with a stronger compositional inductive bias @xcite @xcite , and (b) adding training data that will encourage a compositional solution @xcite @xcite . in the latter approach, typically a model is trained from labeled data @xcite @xcite , and is used to later generate new examples. an alternative approach is to use a manually-built synchronous grammar that automatically generates programs paired with synthetic utterances @xcite @xcite . using a grammar allows generating large amounts of synthetic data that cover a wide range of program structures. this has been shown to be useful in the i.i.d setup, and combined with paraphrase models, has led to high-accuracy parsers that are trained from synthetic data only @xcite . in this work, we investigate the potential of using synthetic data, generated from a synchronous grammar, to improve compositional generalization. @xcite have shown that large quantities of such data improve compositional generalization. however, they evaluated on synthetic utterances only, and did not examine generalization to natural language. moreover, error rates were high in some compositional splits even when the training set was as large as 1m examples. in this work, we ask whether we can strategically sample a small and structurally-diverse training set and improve compositional generalization without incurring a high cost to training and consequently, to the environment @xcite . we hypothesize that a training set that encompasses a diverse set of structures can steer the model towards a compositional solution. we examine a realistic setup, where we have a small labeled training set (∼1,000 examples) and a large pool of synthetic utterances paired with programs (fig. 1 ), which are queries over a database (db) in our setup. we propose two methods for strategically sampling a diverse synthetic training set. in the first, termed uniform abstract template (uat) sampling, we abstract queries by replacing db constants with abstract tokens (e.g., replacing petsallowed with property), and then skew the distribution towards uniform sampling over the derived templates. this increases structure diversity in the training set, which intuitively should lead to better compositional generalization. in the second method, termed compound maximum entropy (cmaxent) sampling, we consider the tree structure of every db query, and following @xcite define compounds, which are sub-trees in the query. we then heuristically solve an optimization problem, where our goal is to select a training set that has maximal entropy over compounds. this results in a training set with a diverse set of substructures, which should enhance compositional generalization. we evaluate our approach on a new split of the schema2qa dataset @xcite , in which it has been shown that synthetic data can lead to high accuracy parsers in the i.i.d setup @xcite . we train an encoder-decoder model on synthetic data and subsequently fine-tune it on the small annotated data. we show that random sampling of synthetic data improves performance, where gradually increasing the size of the synthetic training set also improves compositional generalization. with 1m randomly-sampled examples, accuracy in the compositional split improves from 20.1→37.7 and in the i.i.d split from 81.2→85.0. when sampling structurally-diverse data, compositional generalization improves from 20.1 @xmath0, outperforming training with 1m synthetic examples. in addition, the i.i.d generalization is comparable to random sampling. uat and cmaxent both lead to large improvements in compositional generalization, but uat is more effective than cmaxent. overall, our work demonstrates that sampling diverse structures from synthetic data can lead to dramatic gains in compositional generalization at negligible cost, while preserving or improving performance in the i.i.d setup. our code and data can be downloaded from http://github.com/inbaroren/ scfg-sampling-for-comp-gen . ## problem setup we assume access to a small dataset of natural language utterances paired with queries, d @xmath1, z i )} n nl @xmath2, and a large pool of synthetic utterances paired with queries our goal is to train a model using d train and d syn train and generalize to a test set d test sampled from the same distribution as d train . more importantly, our model should generalize to a compositional test set, d comp test , which contains structures/compositions that are not observed in d train or d syn train . we now describe this test set. compositional split we define a compositional split following the abstract template split proposed by @xcite , which is commonly used for assessing compositional generalization @xcite @xcite . in this approach, queries are abstracted into templates that correspond to different structures. templates are then partitioned into disjoint sets (train/development/test), which ensures that test time structures are never observed at training time. while prior work focused on abstracting entities only, by replacing any db entity with the token entity, in this work we abstract queries into more coarse templates, e.g, table constants are replaced by the token table . ## sampling a structurally-diverse training set we first succinctly describe our model and training procedure ( §3.1) and then turn to methods for sampling structurally-diverse training sets. ## experiments we empirically evaluate the contribution of synthetic data to compositional generalization and the extent to which structurally-diverse sampling can improve data efficiency. ## conclusion in this work, we for the first time explore whether generating large amounts of synthetic data from a synchronous grammar improves compositional generalization, and propose sampling methods that allow for more efficient training by generating structurally-diverse training sets. we find that synthetic data dramatically improves generalization, and moderately improves i.i.d generalization, and that by uniformly sampling abstract templates, we can improve data efficiency by a factor of 200x. in the past year, a myriad of approaches have been proposed for encouraging compositional generalization through modeling innovations, clever training procedures, and data augmentation techniques. our works adds to the body of work that shows that data augmentation is an effective strategy even with small amounts of augmented data, when examples are carefully constructed. moreover, data augmentation techniques can be easily combined with new models and training procedures, potentially leading to further gains in compositional generalization. in addition, we believe our findings can be generalized to other nlp tasks to improve data efficiency w.r.t both i.i.d and compositional generalization. this requires defining a structure over the training examples that can be used similar to the structures used in this work.