SUBS : Subtree Substitution for Compositional Semantic Parsing (2022)

Abstract: Although sequence-to-sequence models often achieve good performance in semantic parsing for i.i.d. data, their performance is still inferior in compositional generalization. Several data augmentation methods have been proposed to alleviate this problem. However, prior work only leveraged superficial grammar or rules for data augmentation, which resulted in limited improvement. We propose to use subtree substitution for compositional data augmentation, where we consider subtrees with similar semantic functions as exchangeable. Our experiments showed that such augmented data led to significantly better performance on Scan and GeoQuery, and reached new SOTA on compositional split of GeoQuery.

## introduction semantic parsing transforms natural language utterances to formal language. because meaning representations or programs are essentially compositional, semantic parsing is an ideal testbed for compositional generalization. although neural seq2seq models could achieve state-of-the-art performance in semantic parsing for i.i.d. data, they failed at compositional generalization due to lack of reasoning ability. that is, they do not generalize well to formal language structures that were not seen at training time. for example, a model that observes at training time the questions "what is the population of the largest state?" and "what is the largest city in usa?" may fail to generalize to questions such as "what is the population of the largest city in usa?". this leads to large performance drops on data splits designed to measure compositional ⋆equal contribution. jingfeng yang proposed subtree substitution data augmentation for compositional semantic parsing, implemented augmentation and lstm/bart parsers, and ran scfg/geca baselines. le zhang induced span trees and ran span-based semantic parsing baseline. generalization (compositional splits), in contrast to the generalization abilities of humans. to improve compositional generalization in semantic parsing (compositional semantic parsing), prior work focused on incorporating inductive biases directly to models or data augmentation. from the model perspective, some work used neuralsymbolic models @xcite , generated intermediate discrete structures @xcite , or conducted meta-learning @xcite . from the data perspective, @xcite proposed to recombine data with simple synchronous context-free grammar (scfg), despite not for compositional generalization. @xcite used some simple rules for data augmentation, where tokens with the same context were considered as exchangeable. such techniques are still limited since they only leveraged superficial grammars or rules, and failed when there are linguistically rich phrases or clauses. to fill this gap, we propose to augment the training data of semantic parsing with diverse compositional examples based on induced or annotated (semantic and syntactic) trees. specifically, we propose to exchange subtrees where roots have similar meaning functions. since we consider all hierarchies in all trees, deep structures and complex phrases or clauses are considered for data augmentation, which is key for compositional generalization. for instance, in figure 1 , if we exchange subtrees with "largest" as meaning function of its root, composition of "population of the" and "largest city in the smallest state in the usa" results in a new augmented structure "population of the largest city in the smallest state in the usa". although certain substructure substitution methods were explored in other nlp tasks @xcite , subtree substitution with fine-grained meaning functions has been under-explored. our experiments showed that such augmented data led to significantly better performance on scan (lake and baroni, 2018) 2 methods span trees suppose training set is {(x i , z i )} n @xmath0, where x i is a natural language utterance and z i is the corresponding program. an utterance x can be mapped to a span tree t , such that program(t )= z, where the deterministic function program(•) maps span trees to programs @xcite . as shown in figure 1 , a span tree t is a tree where each node covers a span (i, j) with tokens x i:@xmath1, x i+1 , • • • , x j ). a span subtree can be viewed as a mapping from every span (i, j) to a single category @xmath2, where c is a set of domainspecific categories representing domain constants, which include entities (e.g. countryid#usa in figure 1 ) and predicates (e.g. loc_2 in figure 1 ). the final program can be computed from the span tree deterministically by the function program(•). concretely, program(t ) iterates over the nodes in t bottom-up, and generates a program z i:j for each node covering the span (i, j). for a terminal node, z i:@xmath3. for an internal node, z i:j is determined by composing the programs of its children, z i:s and z s:j where s is the split point. as in combinatory categorical grammar, composition is simply function application, where a domain-specific type system is used to determine which child is the function and which is the argument. span trees can be induced by a hard-em algorithm or semi-automatically annotated. we refer the reader to @xcite to see how to obtain span-trees. ## related work several data augmentation methods have been introduced for (compositional) semantic parsing. @xcite recombined data by scfg, and @xcite used some simple rules to exchange tokens with the same context. however, they leveraged only superficial grammars or rules, which has limited capacity to identify complex structures. @xcite learned to recombine and resample data with a prototype-based generative model, instead of using rules. certain substructure substitution methods have been explored for data augmentation in other nlp tasks @xcite . dependency tree cropping and rotation within sentence was used in low-resource language pos tagging ( şahin and steedman, 2019) and dependency parsing @xcite . dependency tree swapping was explored in low-resource language dependency parsing @xcite , and universal dependency features was used for zero-shot cross-lingual semantic parsing @xcite . however, subtree substitution with fine-grained meaning functions has not been examined. some rule-based data augmentation methods were also explored in table semantic parsing @xcite . to the best of our knowledge, we are the first to explore tree manipulation for semantic parsing. ## conclusion this work proposed to use subtree substitution to compositionally augment the data of semantic parsing to help the compositional generalization. our method achieved significant improvements over seq2seq models, other data augmentation methods and span-based semantic parsing.