Good-Enough Compositional Data Augmentation (2020)

Abstract: We propose a simple data augmentation protocol aimed at providing a compositional inductive bias in conditional and unconditional sequence models. Under this protocol, synthetic training examples are constructed by taking real training examples and replacing (possibly discontinuous) fragments with other fragments that appear in at least one similar environment. The protocol is model-agnostic and useful for a variety of tasks. Applied to neural sequence-to-sequence models, it reduces error rate by as much as 87% on diagnostic tasks from the SCAN dataset and 16% on a semantic parsing task. Applied to n-gram language models, it reduces perplexity by roughly 1% on small corpora in several languages.

## introduction this paper proposes a rule-based data augmentation protocol for sequence modeling. our approach aims to supply a simple and model-agnostic bias toward compositional reuse of previously observed sequence fragments in novel environments. consider a language modeling task in which we wish to estimate a probability distribution over a family of sentences with the following finite sample as training data: in language processing problems, we often want models to generalize beyond this dataset and infer that (2a) is also probable but (2b) is not: this generalization amounts to an inference about syntactic categories @xcite . because cat and wug are interchangeable in (1a) and (1b), they are also likely interchangeable elsewhere; cat and sang are not similarly interchangeable. human learners make judgments like (2) about novel lexical items @xcite and fragments of novel languages @xcite . but we do not expect such judgments from unstructured generative models trained to maximize the likelihood of the training data in (1). a large body of work in natural language processing provides generalization to data like (2a) by adding structure to the learned predictor @xcite @xcite . on real-world datasets, however, such models are typically worse than "black-box" function approximators like neural networks, even for black-box models that fail to place probability mass on either example in (2) given small training sets like (1) @xcite . to the extent that we believe (2a) to capture an important inductive bias, we would like to find a way of softly encouraging it without tampering with the structure of predictors that work well at scale. in this paper, we introduce a procedure for generating synthetic training examples by recombining real ones, such that (2a) is assigned non-negligible probability because it already appears in the training dataset. the basic operation underlying our proposal (which we call geca, for "good-enough compositional augmentation") is depicted in figure 1 : if two (possibly discontinuous) fragments of training examples appear in some common environment, then any additional environment where the first fragment appears is also a valid environment for the second. ## background recent years have seen tremendous success at natural language transduction and generation tasks using complex function approximators, especially recurrent @xcite and attentional @xcite neural models. with enough training data, these models are often more accurate than than approaches built on traditional tools like regular transducers and context-free grammars @xcite , which are brittle and difficult to efficiently infer from large datasets. however, models equipped with an explicit symbolic generative process have at least one significant advantage over the aforementioned black-box approaches: given a grammar, it is straightforward to precisely characterize how that grammar will extrapolate beyond the examples in a given training set to out-of-distribution data. indeed, it is often possible for researchers to design the form that this extrapolation will take: smoothed n-gram language models ensure that no memorization is possible beyond a certain length @xcite ; ccg-based semantic parsers can make immediate use of entity lexicons without having ever seen the lexicon entries used in real sentences @xcite . it is not the case that black-box neural models are fundamentally incapable of this kind of predictable generalization-the success of these models at capturing long-range structure in text @xcite and controlled algorithmic data @xcite indicate that some representation of hierarchical structure can be learned given enough data. but the precise point at which this transition occurs is not well characterized, and it is evidently beyond the scale available in many real-world problems. how can we improve the behavior of highquality black-box models in these settings? there are many sophisticated tools available for improving the function approximators or loss functions themselves-structured regularization of parameters @xcite , posterior regularization @xcite , explicit stacks @xcite and composition operators @xcite . these existing proposals tend to be taskand architecture-specific. but to the extent that the generalization problem can be addressed by increasing the scale of the training data, it is natural to ask whether we can address the problem by increasing this scale artificially-in other words, via data augmentation. data augmentation techniques, which generate auxiliary training data by performing structured transformation or combination of training examples, are widely used in computer vision @xcite @xcite . within nlp, several data augmentation approaches have been proposed for text classification (e.g. @xcite ; these approaches give improvements even when combined with large-scale pretraining @xcite . @xcite study data augmentation and compositionality in specific setting of learning language-to-logical-form mappings, beginning from the principle that data is compositional if it is generated by an explicit grammar that relates strings to logical forms. this view of compositionality as determined by synchronicity between form and meaning is essentially montagovian and well-suited to problems in formal semantics @xcite ; however, it requires access to structured meaning representations with explicit types and bracketings, which are not available in most nlp applications. here we aim at a notion of compositionality that is simpler and more general: a bias toward identifying recurring fragments seen at training time, and re-using them in environments distinct from those in which they were first observed. this view makes no assumptions about the availability of brackets and types, and is synchronous only to the extent that the notion of a fragment is permitted to include content from both the source and target sides. we will find that it is nearly as effective as existing approaches in the specific settings for which they were designed, but also effective on a variety of problems where they cannot be applied. ## approach consider again the example in figure 1 . our data augmentation protocol aims to discover substitutable sentence fragments (underlined), with the fact that a pair of fragments appear in some common sub-sentential environment (highlighted) taken as evidence that the fragments belong to a common category. to generate a new examples for the model, an occurrence of one fragment is removed from a sentence to produce a sentence template, which is then populated with the other fragment. why should we expect this procedure to produce well-formed training examples? the existence of syntactic categories, and the expressibility of well-formedness rules in terms of these abstract categories, is one of the foundational principles of generative approaches to syntax @xcite . the observation that context provides a strong signal about a sentence fragment's category is in turn the foundation of distributional techniques for the study of language @xcite . combining the two gives the outlines of the above procedure. this combination has a productive history in natural language processing: when fragments are single words, it yields class-based language models @xcite ; when fragments are contiguous spans it yields unsupervised parsers @xcite . the present data augmentation scenario is distinguished mainly by the fact that we are unconcerned with producing a complete generative model of data, or with recovering the latent structure implied by the presence of nested syntactic categories. we can still synthesize high-precision examples of well-formed sequences by identifying individual substitutions that are likely to be correct without understanding how they fit into the grammar as a whole. indeed, if we are not concerned with recovering linguistically plausible analyses, we need not limit ourselves to words or contiguous sentence fragments. we can take (3) a. she picks the wug up. as evidence that we can use picks. . . up wherever we can use puts. . . down. indeed, given a translation dataset: dajo maravillosamente. given a window size k and sequence of n tokens @xmath0, define a fragment as a set of non-overlapping spans of w, a template as a version of w with a fragment removed, and an environment as a template restricted to a k-word window around each removed fragment. formally, (letting [i, j] denote {i, i + 1, . . . , j}) we have: in figure 1 (a), the underlined picks. . . up is one possible fragment that could be extracted from the sentence. the corresponding template is she. . . the wug . . . in fresno, and with @xmath1. . . the wug . . . in. as shown in figure 1(d ), any fragment may be substituted into any template with the same number of holes. denote this substitution operation by t/f . the data augmentation operation that defines geca is formally stated as follows: if the training data contains sequences @xmath2, @xmath3, with env(w, t 1 ) = env(y, t 2 ) and t 1 = t 1 , then synthesize a new training example @xmath4. if a fragment occurs multiple times within a given example, all instances are replaced (see figure 3 ). linguistic notes despite the fact that the above operation is motivated by insights from generative syntax and distributional semantics, it should be emphasized that it is, as a statement of a general linguistic principle, obviously wrong. counterexamples abound: in english, stress-derived nouns (e.g. récord from recórd) will be taken as evidence that many nouns and verbs are interchangeable; in mandarin chinese, kěshì and dànshì both mean "but", but kěshì alone can be used in particular constructions to mean "very". what ultimately matters is the relative frequency of such errors: if their contribution to an inaccurate model is less than the inaccuracy caused by the original shortage of training data, the geca still helps. in conditional problems, like the machine translation example above, such errors may be totally harmless: if we synthesize a new (x, y) pair with x outside the support of the real training data, they may not influence the model's predictions on the true support beyond providing useful general inductive bias. implementation naïve implementation of the boxed operation takes o(t 3 f 3 ) time (where t is the number of distinct templates in the dataset and f the number of distinct fragments). this can be improved to o(f t 2 e) (where e is the number of templates that map to the same environment) by building appropriate data structures (algorithm 1). space requirements might still be considerable (comparable to those used by n-gram language models), and strategies from the language modeling literature can be used to reduce memory usage @xcite . this algorithm is agnostic with respect to the choice of fragmentation and environment functions; task-specific choices are described in more detail for each experiment below. ## diagnostic experiments we begin with a set of experiments on synthetic data designed to precisely test whether geca provides the kind of generalization it was designed for. here we use the scan dataset (lake and baroni, 2018), which consists of simple english commands paired with sequences of discrete actions (figure 2 ). we focus specifically on the add primitive (jump) and add template (around right) conditions, which test whether the agent can be exposed to individual commands or modifiers (e.g. jump jump) in isolation at training time, and incorporate them into more complex commands like the earlier example at test time. we extract fragments with one gap and a maximum length of 4 tokens. the environment is taken to be the complete template. generated examples are appended to the original dataset. as an exam-algorithm 1 sample geca implementation. ple of the effect of this augmentation procedure, the original jump split has 12620 training examples; geca generates an additional 395 using 395 distinct templates and 6 distinct fragments. with the original and augmented datasets, we train a one-layer lstm encoder-decoder model with an embedding size of 64, a hidden size of 512, a bidirectional encoder and an attentional decoder @xcite . the model is trained using adam @xcite with a step size of 0.001 and a dropout rate of 0.5. results are shown in analysis: examples some synthesized examples are shown in figure 3 . success at the add primitive condition stems from the constraint that the single example usage of the primitive must still be a valid (command, action) pair, and all verbs are valid commands in isolation. only three examples-run run, walk walk and look look-provide the evidence that geca uses to synthesize to new usages of jump; if these were removed, the sequenceto-sequence model's training accuracy would be unchanged but geca would fail to synthesize any new examples involving jump, and test accuracy would fall to zero. for the add template condition, geca correctly replaces all occurrences of lturn with rturn to produce new examples of the around right template; this example highlights the usefulness of geca's ability to discover discontinuous and non-context-free substitutions. analysis: dataset statistics to further understand the behavior of geca, we conduct a final set of analyses quantifying the overlap between the synthesized data and the held-out data. we first measure full example overlap, the fraction of test examples that appear in the augmented training set. (by design, no overlap exists between the test set and the original training set.) after applying geca, 5% of test examples for the add primitive condition and 1% of examples for the add template condition are automatically synthesized. next we measure token co-occurrence overlap: we compute the set of (input or output) tokens that occur together in any test example, and then measure the fraction of these pairs that also occur together in some training example. for the add primitive condition, geca increases token co-occurrence overlap from 83% to 96%; for the add template condition it is 100% even prior to augmentation. it is important to note that geca, which sees only the training set, is unaware that some subset of the data is singled out for generalization testing at evaluation time. the data augmentation protocol generates a large number of spurious training examples unrelated to the desired generalization (e.g. the first example in figure 3 ); however, it also generates enough new usages of the target concept that the learner generalizes successfully. ## semantic parsing next we turn to the problem of semantic parsing, which has also been a popular subject of study for questions about compositionality, generalization, and data augmentation. for the reasons discussed in section 3, we expect qualitatively different behavior from this approach on real language data without the controlled vocabulary of scan. we study four versions of the geoquery dataset @xcite , which consists of 880 english questions about united states geography, paired with meaning representations in the form of either logical expressions or sql queries. the standard train-test split for this dataset ensures that no natural language question is repeated between the train and test sets. as @xcite note, this provides only a limited test of generalization, as many test examples feature a logical form that overlaps with the training data; they introduce a more challenging query split to ensure that neither questions nor logical forms are repeated (even after anonymizing named entities). we extract fragments with at most 2 gaps and at most 12 tokens. on the sql query split, the original training set contains 695 examples. geca generates an additional 1055 using 839 distinct templates and 379 distinct fragments. for the question split we use the baseline model of @xcite ; for the query split we use the same sequence-to-sequence model as used for scan and introduce the supervised copy mechanism of @xcite . environments are again taken to be identical to templates. results are shown in analysis: examples synthesized examples for the logical and sql representations are shown in figure 4 . despite the fact that the sequenceto-sequence model uses neither gold entities or specialized entity linking machinery, the augmentation procedure successfully aligns natural language entity names to their logical representations and generalizes across entity choices. this procedure also produces plausible but unattested entities like a river named florida and a state named west wyoming. the last example in the "logical forms" section is particularly interesting. the extracted fragment contains lowest population density on the natural language side but only density on the logical form side. however, the environment constrains substitution to happen where appropriate: this fragment will only be used in cases where the environment already contains the necessary smallest. some substitutions are semantically problematic: for example, the final datapoint in figure 4 asks about the population of a number (because substitution has replaced capital with area); the corresponding sql expression would fail to execute. aside from typing problems, however, the example is syntactically well-formed and provides correct evidence about constituent boundaries, alignments and hierarchical structure within the geography domain. other synthesized examples (like the secondto-last in figure 4 ) have correct meaning representations but ungrammatical natural language inputs. analysis: dataset statistics applying geca to the geoquery data increases full example overlap (described at the end of section 4) by 5% for the question split in both languages, 6% for the query split with logical forms, and 9% for the query split with sql expressions, in line with the observation that accuracy improvements are greater for the query split than the question split. augmentation increases token co-occurrence overlap by 3-4% across all conditions. in a larger-scale manual analysis of 100 synthesized examples from the query split, evaluating them for grammaticality and accuracy (whether the natural language captures the semantics of the logical form), we find that 96% are grammatical, and 98% are semantically accurate. ## low-resource language modeling both of the previous sections investigated conditional models. the fragments extracted and reused by geca were essentially synchronous lexicon entries, in line with example (4). we originally motivated geca with monolingual problems in which we simply wish to improve model judgments about well-formedness, so we conclude with a set of language modeling experiments. we use wikipedia dumps foot_1 in five languages (kinyarwanda, lao, pashto, tok pisin, and a subset of english wikipedia) as well as the na dataset of @xcite . these languages exhibit the performance of geca across a range of morphological complexities: for example, kinyarwanda has a complex noun class system @xcite and pashto has rich derivational morphology @xcite , while lao and tok pisin are comparatively simple morphologically @xcite . training datasets range from 10k-2m tokens. like adams et al., we found that a 5-gram modified kneser-ney language model @xcite outperformed several varieties of rnn language model, so we base our geca experiments on the n-gram model instead. we use the implementation provided in kenlm @xcite . we extract fragments with no gaps and a maximum size of 2 tokens, with the environment taken to be a 2-token window around the extracted fragment. new usages are generated only for fragments that occur fewer than 20 times in the data. in kinyarwanda, the base dataset contains 3358 sentences. geca generates an additional 913, using 913 distinct templates and 199 distinct fragments. rather than training directly on the augmented dataset, as in preceding sections, we found that the best performance came from training one language model on the original dataset and one on the augmented dataset, then interpolating their final probabilities. the weight for this interpolation is determined on a validation dataset and chosen to be one of 0.05, 0.1 and 0.5. results are shown in analysis: examples and statistics in language modeling, geca functions as a smoothing scheme: its primary effect is to move mass toward n-grams that can appear in productive contexts. in this sense, geca performs a similar role to the kneser-ney smoothing also used in all lm experiments. with geca, in contrast to kneser-ney, the notion of "context" can look forward as well as backward, and capture longer-range interactions. examples of synthesized sentences are shown in figure 5 . most sentences are grammatical, and many of the substitutions preserve relevant semantic type information (substituting locations for locations, times for times, etc.). however, some illformed sentences are also generated. as in section 5, we manually inspect 100 synthesized sentences. as before, sentences are evaluated for grammaticality; here, since no explicit semantics were provided, they are instead evaluated for generic semantic acceptability. in this case, only 51% of synthesized sentences are semantically acceptable, but 79% are grammatical. ## discussion we introduced geca, a simple data augmentation scheme based on identifying local phrase substitutions that are licensed by common contexts, and demonstrated that extra training examples generated with geca lead to substantial improvements on both diagnostic and natural datasets for semantic various copies of portions of the code of hammurabi have been found on baked clay tablets , some possibly older than the celebrated basalt stele now in the night sky . the work contains , in an appendix , the german equivalents for the technical terms used in the glock $num . payments system in the aclu proposed new directions for the organization . in the late triassic and early nineteenth century , a number of scots-irish traders lived among the choctaw and married high-status women . parsing and language modeling. while the approach is surprisingly effective in its current form, we view these results primarily as an invitation to consider more carefully the role played by representations of sentence fragments in larger questions about compositionality in blackbox sequence models. the procedure detailed in this paper relies on exact string matching to identify common context; future work might take advantage of learned representations of spans and their environments @xcite . further improvements are likely obtainable by constraining the extracted fragments to respect constituent boundaries when syntactic information is available. the experiments presented here focus on rewriting sentences using evidence within a dataset to encourage generalization to new outputs. an alternative line of work on paraphrase-based data augmentation @xcite uses external, text-only resources to encourage robust interpretation of new inputs corresponding to known outputs. the two lines of work could be combined, e.g. by using geca-identified fragments to indicate productive locations for sub-sentential paraphrasing. more generally, the present results underline the extent to which current models fail to learn simple, context-independent notions of reuse, but also how easy it is to make progress towards addressing this problem without fundamental changes in model architecture.