On Graph-based Reentrancy-free Semantic Parsing

On Graph-based Reentrancy-free Semantic Parsing Alban Petit and Caio Corro Universite Paris-Saclay, CNRS, LISN, 91400, Orsay, France {alban.petit,caio.corro}@lisn.upsaclay.fr Abstract We propose a novel graph-based approach for semantic parsing that resolves two prob- lems 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 (re- quired for weakly-supervised learning) are NP-hard problems. We propose two optimiza- tion algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems. Experimen- tally, our approach delivers state-of-the-art re- sults on GEOQUERY, SCAN, and CLEVR, both for i.i.d. splits and for splits that test for compo- sitional generalization. 1 Introduction Semantic parsing aims to transform a natural lan- guage 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. Andreas et al. (2013) first proposed to rely on machine trans- lation models for semantic parsing, where the tar- get 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 (Bahdanau et al., 2015), it is appealing to use the same architectures for standard struc- tured prediction problems (Vinyals et al., 2015). This approach is indeed common in semantic pars- ing (Jia and Liang, 2016; Dong and Lapata, 2016; Wang et al., 2020), as well as other domains. Un- fortunately, 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 autore- gressive 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 fail- ing out of the beam. Secondly, they are known to fail when compositional generalization is re- quired (Lake and Baroni, 2018; Finegan-Dollak et al., 2018a; Keysers et al., 2020). In order to bypass these problems, Herzig and Berant (2021) proposed to represent the semantic content associated with an utterance as a phrase structure, i.e., using the same representation usu- ally associated with syntactic constituents. As such, their semantic parser is based on standard span-based decoding algorithms (Hall et al., 2014; Stern et al., 2017; Corro, 2020) with additional well-formedness constraints from the semantic formalism. Given a weighting function, MAP in- ference is a polynomial time problem that can be solved via a variant of the CYK algorithm (Kasami, 1965; Younger, 1967; Cocke, 1970). Experimentally, Herzig and Berant (2021) show that their approach outperforms seq2seq models in terms of compositional generalization, there- fore effectively bypassing the two major problems of these architectures. The complexity of MAP inference for phrase structure parsing is directly impacted by the con- sidered search space (Kallmeyer, 2010). Impor- tantly, (ill-nested) discontinuous phrase structure parsing is …

Content truncated to 500 words