On Graph-based Reentrancy-free Semantic Parsing (2023)

Abstract: We propose a novel graph-based approach for semantic parsing that resolves two problems observed in the literature: (1) seq2seq models fail on compositional generalization tasks; (2) previous work using phrase structure parsers cannot cover all the semantic parses observed in treebanks. We prove that both MAP inference and latent tag anchoring (required for weakly-supervised learning) are NP-hard problems. We propose two optimization algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems. Experimentally, our approach delivers state-of-the-art results on GeoQuery, Scan, and Clevr, both for i.i.d. splits and for splits that test for compositional generalization.

## introduction semantic parsing aims to transform a natural language utterance into a structured representation that can be easily manipulated by a software (e.g., to query a database). as such, it is a central task in human-computer interfaces. @xcite first proposed to rely on machine translation models for semantic parsing, where the target representation is linearized and treated as a foreign language. due to recent advances in deep learning and especially in sequence-to-sequence (seq2seq) with attention architectures for machine translation @xcite , it is appealing to use the same architectures for standard structured prediction problems @xcite . this approach is indeed common in semantic parsing @xcite @xcite , as well as other domains. unfortunately, there are well-known limitations to seq2seq architectures for semantic parsing. first, at test time, the decoding algorithm is typically based on beam search as the model is autoregressive and does not make any independence assumption. in case of prediction failure, it is therefore unknown if this is due to errors in the weighting function or to the optimal solution failing out of the beam. secondly, they are known to fail when compositional generalization is required @xcite @xcite . in order to bypass these problems, @xcite proposed to represent the semantic content associated with an utterance as a phrase structure, i.e., using the same representation usually associated with syntactic constituents. as such, their semantic parser is based on standard span-based decoding algorithms @xcite @xcite with additional well-formedness constraints from the semantic formalism. given a weighting function, map inference is a polynomial time problem that can be solved via a variant of the cyk algorithm @xcite @xcite . experimentally, @xcite show that their approach outperforms seq2seq models in terms of compositional generalization, therefore effectively bypassing the two major problems of these architectures. the complexity of map inference for phrase structure parsing is directly impacted by the considered search space @xcite . importantly, (ill-nested) discontinuous phrase structure parsing is known to be np-hard, even with a bounded block-degree @xcite . @xcite explore two restricted inference algorithms, both of which have a cubic time complexity with respect to the input length. the first one only considers continuous phrase structures, that is, derived trees that could have been generated by a context-free grammar, and the second one also considers a specific type of discontinuities, see @xcite . both algorithms fail to cover the full set of phrase structures observed in semantic treebanks, see figure 1 . in this work, we propose to reduce semantic parsing without reentrancy (i.e., a given predicate or entity cannot be used as an argument for two figure 1 : example of a semantic phrase structure from geoquery. this structure is outside of the search space of the parser of @xcite as the constituent in red is discontinuous and also has a discontinuous parent (in red+green). our contributions can be summarized as follows: code to reproduce the experiments is available online. foot_1 ## graph-based semantic parsing we propose to reduce semantic parsing to parsing the abstract syntax tree (ast) associated with a semantic program. we focus on semantic programs whose asts do not have any reentrancy, i.e., a single predicate or entity cannot be the argument of two different predicates. moreover, we assume that each predicate or entity is anchored on exactly one word of the sentence and each word can be the anchor of at most one predicate or entity. as such, the semantic parsing problem can be reduced to assigning predicates and entities to words and identifying arguments via dependency relations, see figure 2 . in order to formalize our approach to the semantic parsing problem, we will use concepts from graph theory. we therefore first introduce the vocabulary and notions that will be useful in the rest of this article. notably, the notions of cluster and generalized arborescence will be used to formalize our prediction problem. ## efficient inference in this section, we propose an efficient way to solve the linear relaxations of map inference (ilp1) and latent anchoring inference (ilp2) via constraint smoothing and the conditional gradient method. we focus on problems of the following form: in the equality case, we use @xmath0, we use @xmath1. ## experiments we compare our method to baseline systems both on i.i.d. splits (iid) and splits that test for compositional generalization for three datasets. the neural network is described in appendix b. datasets. scan (lake and baroni, 2018) contains natural language navigation commands. we use the variant of @xcite for semantic parsing. the iid split is the simple split @xcite . the compositional splits are primitive right (right) and primitive around right (aright) @xcite . geoquery @xcite uses the funql formalism @xcite and contains questions about the us geography. the iid split is the standard split and compositional generalization is evaluated on two splits: length where the examples are split by program length and template @xcite where they are split such that all semantic programs having the same ast are in the same split. clevr @xcite ) contains synthetic questions over object relations in images. clo-sure @xcite introduces additional question templates that require compositional generalization. we use the original split as our iid split and the closure split as a compositional split where the model is evaluated on closure. baselines. we compare our approach against the architecture proposed by @xcite (spanbasedsp) as well as the seq2seq baselines they used. in seq2seq @xcite , the encoder is a bi-lstm over pre-trained glove embeddings @xcite or elmo @xcite and the decoder is an attention-based lstm @xcite . bert2seq replaces the encoder with bertbase. grammar is similar to seq2seq but the decoding is constrained by a grammar. bart @xcite is pre-trained as a denoising autoencoder. results. we report the denotation accuracies in we also report exact match accuracy, with and without the heuristic to construct integral solutions from fractional ones. the exact match accuracy is always lower or equal to the denotation accuracy. this shows that our approach can sometimes provide the correct denotation even though the prediction is different from the gold semantic program. importantly, while our approach outperforms baselines, its accuracy is still significantly worse on the split that requires to generalize to longer programs. in the case of semantic structures, @xcite proposed a o(n 3 ) algorithm for the maximum non-necessarily-spanning acyclic graphs with a noncrossing arc constraint. without the noncrossing constraint, the problem is known to be np-hard @xcite . to bypass this computational complexity, @xcite proposed to handle each dependency as an independent binary classification problem, that is they do not enforce any constraint on the output structure. note that, contrary to our work, these approaches allow for reentrancy but do not enforce well-formedness of the output with respect to the semantic grammar. @xcite all the baseline results were taken from @xcite . for our approach, we also report exact match accuracy, i.e., the percentage of sentences for which the prediction is identical to the gold program. the last line reports the exact match accuracy without the use of cplex to round non integral solutions (section 4.3). previous work in the literature has also considered reduction to graph-based methods for other problems, e.g., for discontinuous constituency parsing @xcite , lexical segmentation @xcite , and machine translation @xcite , inter alia. compositional generalization. several authors observed that compositional generalization insufficiency is an important source of error for semantic parsers, especially ones based on seq2seq architectures @xcite @xcite . @xcite proposed a latent re-ordering step to improve compositional generalization, whereas @xcite relied on latent predicate tagging in the encoder. there has also been an interest in using data augmentation methods to improve generalization @xcite @xcite @xcite . recently, @xcite showed that span-based parsers do not exhibit such problematic behavior. unfortunately, these parsers fail to cover the set of semantic structures observed in english treebanks, and we hypothesize that this would be even worse for free word order languages. our graph-based approach does not exhibit this downside. previous work by @xcite also considered graph-based methods for compositional generalization, but their approach predicts each part independently without any well-formedness or acyclicity constraint. ## conclusion in this work, we focused on graph-based semantic parsing for formalisms that do not allow reentrancy. we conducted a complexity study of two inference problems that appear in this setting. we proposed ilp formulations of these problems together with a solver for their linear relaxation based on the conditional gradient method. experimentally, our approach outperforms comparable baselines. one downside of our semantic parser is speed (we parse approximately 5 sentences per second for geoquery). however, we hope this work will give a better understanding of the semantic parsing problem together with baseline for faster methods. future research will investigate extensions for (1) asts that contain reentrancies and (2) prediction algorithms for the case where a single word can be the anchor of more than one predicate or entity. these two properties are crucial for semantic representations like abstract meaning representation @xcite . moreover, even if our graph-based semantic parser provides better results than previous work on length generalization, this setting is still difficult. a more general research direction on neural architectures that generalize better to longer sentences is important.