LAG r: Label Aligned Graphs for Better Systematic Generalization in Semantic Parsing (2022)

Abstract: Semantic parsing is the task of producing structured meaning representations for natural language sentences. Recent research has pointed out that the commonly-used sequence-to-sequence (seq2seq) semantic parsers struggle to generalize systematically, i.e. to handle examples that require recombining known knowledge in novel settings. In this work, we show that better systematic generalization can be achieved by producing the meaning representation directly as a graph and not as a sequence. To this end we propose LAGr (Label Aligned Graphs), a general framework to produce semantic parses by independently predicting node and edge labels for a complete multi-layer input-aligned graph. The strongly-supervised LAGr algorithm requires aligned graphs as inputs, whereas weakly-supervised LAGr infers alignments for originally unaligned target graphs using approximate maximum-a-posteriori inference. Experiments demonstrate that LAGr achieves significant improvements in systematic generalization upon the baseline seq2seq parsers in both strongly- and weakly-supervised settings.

## introduction recent research has shown that neural models struggle to systematically generalize to examples with unseen combinations of seen rules from the training set (lake and @xcite @xcite . systematic generalization is especially important for the task of semantic parsing, which requires models to translate natural language sentences to structured meaning representations (mrs), such as sparql database queries or lambda calculus logical forms. to generalize systematically in this task, the model must be capable of producing mrs for examples that feature new combinations of meaning construction rules, such as the rule that maps a noun like training example a hedgehog ate the cake * hedgehog(x 1 ) ∧ cake(x 4 )∧ eat.agent(x 2 , x 1 ) ∧ eat.theme(x 2 , x 4 ) ## semantic parsing by labeling aligned graphs we present lagr (label aligned graphs), a framework for constructing meaning representations (mr) directly as graphs (i.e., mr graphs). when lagr is used to output logical forms, the graph nodes can be variables, entities, categories and predicates, and graph edges can be the neo-davidsonian style semantic role relations that the nodes appear in, e.g. "is-agent-of" or "is-themeof" @xcite . while this work focuses on predicting logical forms, lagr can, in principle, also be used to output other kinds of graphs, such as abstract syntax tree parses of sql queries. as illustrated in figure 2 , lagr predicts the output by labeling the nodes and edges of a fully-connected multi-layer output graph that is aligned with the input utterance. we label a multi-layer as opposed to a single-layer graph because some mr graphs have more nodes than the number of input tokens (see section 4.2 for an example). notation and terminology formally, let @xmath0, x 2 , ..., x n denote a natural language utterance of n tokens. lagr produces an mr graph g by labeling the nodes and edges of a complete graph γ a with @xmath1. the layers are aligned with the input sequence x in a way that for each input position i there is a unique corresponding output node in each layer. we say that nodes from different layers that are aligned with the position i form a column (an example column in figure 2b contains the nodes labeled as actor and ?x0 for the word star at the position @xmath2. we write γ @xmath3, ξ) to indicate that a complete labeled graph γ a is characterized by its node labels @xmath4, where v n and v e are node and edge label vocabularies, respectively. both vocabularies also include additional null labels that we use as padding (e.g. grey nodes in figure 2 are labeled as null). to produce the output mr graph g from γ a , we remove all null nodes and null edges. lastly, we use z j and ξ jk notations to refer to the labels of node j and of the edge (j, k) where @xmath5. ## related work the lagr approach is heavily inspired by graphbased dependency parsing algorithms @xcite . in neural graph-based dependency parsers @xcite the model is trained to predict the existence and the label of each of the possible edges between the input words. the abstract meaning representation (amr) parser by lyu and titov ## experiments we demonstrate the effectiveness of lagr on two systematic generalization benchmarks for semantic parsing: cogs @xcite and compositional freebase questions (cfq, keysers et al. ( 2020 )) 1 . 1 our code is available under https://github.com/ elementai/lagr 4.1 cogs dataset cogs @xcite ) is a semantic parsing benchmark that requires models to translate english sentences to neo-davidsonian lambda calculus logical forms. as shown in figure 1 , the out-of-distribution generalization set of cogs features novel combinations of words and syntactic structures from the training dataset (more examples available in appendix a.4). ## discussion & future work in this work we have shown that performing semantic parsing by labeling aligned graphs brings significant gains in systematic generalization. in our cogs and cfq experiments, lagr significantly improves upon sequence-to-sequence baselines in both strongly and weakly-supervised settings. specifically, on cogs, lagr outperforms our carefully-tuned seq2seq baselines and performs similarly to lstms that leverage lexicons. lexicons can also be integrated into lagr, although we do not expect this to improve lagr's performance on cogs, as our best performing models already predict node labels perfectly. lexicons also bring their own challenges of dealing with context-dependency and ambiguity, hence it is notable that lagr matches the performance of a lexicon-equipped model while making less assumptions about the nature of the input-to-output mapping. on cfq, lagr outperforms all seq2seq baselines on all mcd splits. based on our error analysis (see appendix a.3), we believe that a modification of lagr that conditions edge predictions on node labels could bring further improvements. importantly, this modification would be compatible with our current alignment inference algorithm. another obvious direction to improve lagr's performance is by using a pretrained encoder. lastly, while the current alignment inference algorithm is effective, applying more advanced discrete optimization or amortized inference methods could be an interesting direction for future work. luke s. zettlemoyer and michael collins. 2005. learning to map sentences to logical form: structured classification with probabilistic categorial grammars. in proceedings of the twenty-first conference on uncertainty in artificial intelligence, uai'05, pages 658-666. hao zheng and mirella lapata. 2020. compositional generalization via semantic tagging. arxiv preprint arxiv:2010.11818.