Span-based Semantic Parsing for Compositional Generalization (2021)

Abstract: Despite the success of sequence-to-sequence (seq2seq) models in semantic parsing, recent work has shown that they fail in compositional generalization, i.e., the ability to generalize to new structures built of components observed during training. In this work, we posit that a span-based parser should lead to better compositional generalization. we propose SpanBasedSP, a parser that predicts a span tree over an input utterance, explicitly encoding how partial programs compose over spans in the input. SpanBasedSP extends Pasupat et al. (2019) to be comparable to seq2seq models by (i) training from programs, without access to gold trees, treating trees as latent variables, (ii) parsing a class of non-projective trees through an extension to standard CKY. On GeoQuery, SCAN and CLOSURE datasets, SpanBasedSP performs similarly to strong seq2seq baselines on random splits, but dramatically improves performance compared to baselines on splits that require compositional generalization: from 61.0 → 88.9 average accuracy.

## introduction the most dominant approach in recent years for semantic parsing, the task of mapping a natural language utterance to an executable program, has been based on sequence-to-sequence (seq2seq) models @xcite @xcite . in these models, the output program is decoded step-by-step (autoregressively), using an attention mechanism that softly ties output tokens to the utterance. despite the success of seq2seq models, recently, @xcite and @xcite and @xcite demonstrated that such models fail at compositional generalization, that is, they do not generalize to program structures that were not seen at training time. for example, a model that observes at training time the questions "what states border china?" and "what is the largest state?" fails to generalize to questions such as "what states border the largest state?". this is manifested in large performance drops on data splits designed to measure compositional generalization (compositional splits), and is in contrast to the generalization abilities of humans @xcite . in this work, we posit that the poor generalization of seq2seq models is due to fact that the input utterance and output program are only tied softly through attention. we revisit a more traditional approach for semantic parsing @xcite @xcite , where partial programs are predicted over short spans in the utterance, and are composed to build the program for the entire utterance. such explicit inductive bias for compositionality should encourage compositional generalization. specifically, we propose to introduce such inductive bias via a span-based parser @xcite , equipped with the advantages of modern neural architectures. our model, span-basedsp, predicts for every span in the input a category, which is either a constant from the underlying knowledge-base, a composition category, or a null category. given the category predictions for all spans, we can construct a tree over the input utterance and deterministically compute the output program. for example, in figure 1 , the category for the tree node covering the span "new york borders ?" is the composition category join, indicating the composition of the predicate next_to_1 with the entity stateid('new york'). categories are predicted for each span independently, resulting in a very simple training procedure. cky is used at inference time to find the best span tree, which is a tree with a category predicted at every node. the output program is computed from we enhance the applicability of span-based semantic parsers @xcite in terms of both supervision and expressivity, by overcoming two technical challenges. first, we do not use gold trees as supervision, only programs with no explicit decomposition over the input utterance. to train with latent trees, we use a hard-em approach, where we search for the best tree under the current model corresponding to the gold program, and update the model based on this tree. second, some gold trees are non-projective, and cannot be parsed with a binary grammar. thus, we extend the grammar of cky to capture a class of non-projective structures that are common in semantic parsing. this leads to a model that is comparable and competitive with the prevailing seq2seq approach. we evaluate our approach on three datasets, and find that spanbasedsp performs similarly to strong seq2seq baselines on standard i.i.d (random) splits, but dramatically improves performance on compositional splits, by 32.9, 34.6 and 13.5 absolute accuracy points on geoquery (zelle and mooney, 1996), closure @xcite , and scan (lake and baroni, 2018) respectively. our code and data are available at https:// github.com/jonathanherzig/span-based-sp. ## problem setup we define span-based semantic parsing as follows. given a training set {(x i , z i )} m @xmath0, where x i is an utterance and z i is the corresponding program, our goal is to learn a model that maps a new utterance x to a span tree t (defined below), such that program(t )= z. the deterministic function program(•) maps span trees to programs. span trees a span tree t is a tree (see figure 1 ) where, similar to constituency trees, each node covers a span (i, j) with tokens x i:@xmath1, x i+1 , . . . , x j ). a span tree can be viewed as a mapping from every span (i, j) to a single category @xmath2, where categories describe how the meaning of a node is derived from the meaning of its children. a category c is one of the following: • σ: a set of domain-specific categories representing domain constants, including entities and predicates. e.g., in figure 1 , capital, state, loc_2 and next_to_1 are binary predicates, and stateid('new york') is an entity. computing programs for span trees given a mapping from spans to categories specifying a span tree t , we use the function program(•) to find the program for t . 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). the program z i:j is computed deterministically. for a node with category @xmath3, z i:@xmath4. for a join node over the span (i, j), we determine z i:j 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 @xcite , 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 (along with the exact argument position for predicates with multiple arguments). if the category of one of the children is φ, the program for z i:j is copied from the other child. e.g., in figure 1 , the span (8, 9), where z 8:9 = stateid('new york') combines with the span (10, 11), where z 10:11 = next_to_1. as z 10:11 is a binary predicate that takes an argument of type state, and z 8:9 is an entity of type state, the output program is z 8:11 = next_to_1(stateid('new york')). if no combination is possible according to the type system, the execution of program(t ) fails ( §3.2). unlike seq2seq models, computing programs with span trees is explicitly compositional. our main hypothesis is that this strong inductive bias should improve compositional generalization. ## a span-based semantic parser span-based parsing had success in both syntactic @xcite and semantic parsing @xcite . the intuition is that modern sequence encoders are powerful, and thus we can predict a category for every span independently, reducing the role of global structure. this leads to simple and fast training. specifically, our parser is based on a model p θ (t [i, j] = c), parameterized by θ, that provides for every span (i, j) a distribution over categories @xmath5. due to the above independence assumption, the log-likelihood of a tree t is defined as: we next describe the model p θ (t [i, j]) and its training, assuming we have access to gold span trees at training time ( §3.1). we will later ( §3.3) remove this assumption, and describe a cky-based inference procedure ( §3.2) that finds for every training example (x, z) the (approximately) most probable span tree t * train , such that program(t * train ) = z. we use t * train as a replacement for the gold tree. last, we present an extension of our model that covers a class of span trees that are non-projective ( §3.4). ## experiments and results we now present our experimental evaluation, which demonstrates the advantage of span-based parsing for compositional generalization. we compare to baseline models over two types of data splits: (a) iid split, where the training and test sets are sampled from the same distribution, and (b) compositional split, where the test set includes structures that are unseen at training time. details on the experimental setup are given in appendix a. ## related work until the neural era, semantic parsers used a lexicon and composition rules to predict partial programs for spans and compose them until a full program is predicted, and typically scored with a log-linear model given features over the utterance and the program @xcite . in this work, we use a similar compositional approach, but take advantage of powerful span representations based on modern neural architectures. the most similar work to ours is by @xcite , who presented a neural span-based semantic parser. while they focused on training using projective gold trees (having more supervision and less expressivity than seq2seq models) and testing on i.i.d examples, we handle non-projective trees, given only program supervision, rather than trees. more importantly, we show that this approach leads to dramatic gains in compositional generalization compared to autoregressive parsers. in recent years, work on compositional generalization in semantic parsing mainly focused on the poor performance of parsers in compositional splits @xcite , creating new datasets that require compositional generalization @xcite @xcite , and proposing specialized architectures mainly for the scan task @xcite @xcite @xcite . in this work we present a general-purpose architecture for semantic parsing that incorporates an inductive bias towards compositional generalization. finally, concurrently to us, @xcite induced a synchronous grammar over program and utterance pairs and used it to introduce a compositional bias, showing certain improvements over compositional splits. ## conclusion seq2seq models have become unprecedentedly popular in semantic parsing but struggle to generalize to unobserved structures. in this work, we show that our span-based parser, spanbasedsp, that precisely describes how meaning is composed over the input utterance leads to dramatic improvements in compositional generalization. in future work, we plan to investigate ways to introduce the explicit compositional bias, inherent to spanbasedsp, directly into seq2seq models.