Learning to Substitute Spans towards Improving Compositional Generalization (2023)

Abstract: Despite the rising prevalence of neural sequence models, recent empirical evidences suggest their deficiency in compositional generalization. One of the current de-facto solutions to this problem is compositional data augmentation, aiming to incur additional compositional inductive bias. Nonetheless, the improvement offered by existing handcrafted augmentation strategies is limited when successful systematic generalization of neural sequence models requires multi-grained compositional bias (i.e., not limited to either lexical or structural biases only) or differentiation of training sequences in an imbalanced difficulty distribution. To address the two challenges, we first propose a novel compositional augmentation strategy dubbed Span Substitution (SpanSub) that enables multi-grained composition of substantial substructures in the whole training set. Over and above that, we introduce the Learning to Substitute Span (L2S2) framework which empowers the learning of span substitution probabilities in SpanSub in an end-to-end manner by maximizing the loss of neural sequence models, so as to outweigh those challenging compositions with elusive concepts and novel surroundings. Our empirical results on three standard compositional generalization benchmarks, including SCAN, COGS and GeoQuery (with an improvement of at most 66.5%, 10.3%, 1.2%, respectively), demonstrate the superiority of SpanSub, L2S2 and their combination.

## introduction the secret for human beings to learning so quickly with little supervision has been demonstrated to be associated with the powerful ability of systematic generalization, being capable of producing an infinite number of novel combinations on the basis of known components @xcite . in stark contrast, a large body of recent evidence suggests that current state-of-the-art neural sequence models @xcite , which require word-level, subtree-level and general substructure-level recombinations of training data, respectively. besides, (d) shows concepts in distinct difficulty in the scan (lake and baroni, 2018) dataset, where the interpretation of walk around right is much more complex than that of the other two concepts. to conquer the two challenges, we first propose a novel compositional data augmentation scheme spansub that substitutes a span in a training sentence with one in another sentence, where a span refers to a consecutive fragment of tokens that subsumes all multi-grained possibilities of a word, a subtree, as well as a more general substructure. the core of spansub lies in extraction of such spans and identification of exchangeable spans, towards which we define the exchangeability of spans by the exchageability or syntactic equivalence of their first and last tokens. on top of this, we propose the l2s2 framework made up of a l2s2 augmenter, which is a differentiable version of spansub with all substitution actions equipped with probabilities. by training down-stream neural sequence models to evaluate the difficulty of various spans and maximizing their losses, the l2s2 framework seeks to train the l2s2 augmenter to tip the scales of those substitution actions contributing challenging compositions by elusive spans and novel surroundings. in summary, the main contributions of this paper are three-fold. compositional generalization in neural sequence models a large body of literature pursues various ways of introducing compositional inductive bias into neural sequence models, in a bid to improve systematic generalization. the first category of studies, e.g., cgps @xcite , syntatt (russin et al., 2020), groupequ @xcite , customizes neural architectures that promote lexical generalization via explicit disentanglement of the meaning of tokens. the second strand aims to align words or substructures in the input sequences with their counterparts in the output sequences by auxiliary tasks (e.g., ir-transformer @xcite ), additional architectural modules (e.g., lexlearn ( akyurek and andreas, 2021) ), as well as extra objectives imposed on attention layers (e.g., spanatt @xcite ). third, the works of meta-seq2seq (lake, 2019), comp-maml @xcite , and met @xcite resorts to the metalearning paradigm to directly encourage compositional generalization of neural models. last but not least, compositional data augmentation that composes in-distribution data to accommodate outof-distribution compositional sequences has been empirically demonstrated to enjoy not only the performance but also the model-agnostic benefits. the explored principles for augmentation include exchangeability of tokens in the same context (e.g., geca (andreas, 2020)), token-level mixup (zhang et al., 2018) (e.g., seqmix (guo et al., 2020a)), group-equivariance of language models (basu et al., 2022) by substituting training tokens (e.g., lexsym (akyürek and andreas, 2022), prim2primx (jiang et al., 2022)) or subtrees (e.g., subs (yang et al., 2022)) with virtual or off-the-shelf tokens or substrees. note that the aforementioned approaches guarantee the validity of composed sequences by following the widely accepted alignment practices in nlp, e.g., spantree @xcite and fastalign @xcite . our work further pushes ahead with compositional data augmentation by (1) substituting spans, which offers more diverse and flexible generalization than substituting monotonous tokens or subtrees, and (2) endowing the augmentation strategy to be differentiable and learnable in an end-to-end manner, which dynamically adapts to the difficulty of down-stream neural sequence tasks. ## span substitution we propose spansub to generate novel examples through exchanging multi-grained spans, which refer to consecutive fragments in input sequences, of the same equivalence class between training examples as shown in fig. 2 . before proceeding to the details of spansub, we first introduce two preprocessing prerequisites for spansub, including extraction of span alignment and inference of the equivalence class of a word. on top of these, we present our substitution strategy that dictates the equivalence and exchangeability between spans. ## learning to substitute spans (l2s2) beyond the benefit of multi-grained compositional bias introduced by spansub, the following three observations lead us to take a step further towards augmentation with attention on challenging spans. ## conclusion in this paper, (1) we present a novel substitutionbased compositional data augmentation scheme, spansub, to enable multi-grained compositions of substantial substructures in the whole training set and (2) we introduce an online, optimizable and model-agnostic l2s2 framework containing a l2s2 augmentor which automatically learn the span substitution probabilities to put high values on those challenging compositions of elusive spans and novel surroundings and thus further boost the systematic generalization ability of down-stream nerual sequence models especially on those hard-tolearn compositions. empirical results demonstrate the effectiveness and superiority of spansub, l2ss and their combination.