Fast semantic parsing with well-typedness guarantees

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 3929–3951, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 3929 Fast semantic parsing with well-typedness guarantees Matthias Lindemann and Jonas Groschwitz and Alexander Koller Department of Language Science and Technology Saarland University {mlinde|jonasg|koller}@coli.uni-saarland.de Abstract AM dependency parsing is a linguistically principled method for neural semantic pars- ing with high accuracy across multiple graph- banks. It relies on a type system that models semantic valency but makes existing parsers slow. We describe an A* parser and a transi- tion-based parser for AM dependency parsing which guarantee well-typedness and improve parsing speed by up to 3 orders of magnitude, while maintaining or improving accuracy. 1 Introduction Over the past few years, the accuracy of neural semantic parsers which parse English sentences into graph-based semantic representations has in- creased substantially (Dozat and Manning, 2018; Zhang et al., 2019; He and Choi, 2020; Cai and Lam, 2020). Most of these parsers use a neural model which can freely predict node labels and edges, and most of them are tailored to a specific type of graphbank. Among the high-accuracy semantic parsers, the AM dependency parser of Groschwitz et al. (2018) stands out in that it implements the Principle of Compositionality from theoretical semantics in a neural framework. By parsing into AM dependency trees, which represent the compositional structure of the sentence and evaluate deterministically into graphs, this parser can abstract away surface de- tails of the individual graphbanks. It was the first semantic parser which worked well across multiple graphbanks, and set new states of the art on several of them (Lindemann et al., 2019). However, the commitment to linguistic princi- ples comes at a cost: the AM dependency parser is slow. A key part of the parser is that AM depen- dency trees must be well-typed according to a type system which ensures that the semantic valency of each word is respected. Existing algorithms com- pute all items along a parsing schema that encodes the type constraints; they parse e.g. the AMRBank at less than three tokens per second. In this paper, we present two fast and accurate parsing algorithms for AM dependency trees. We first present an A* parser which searches through the parsing schema of Groschwitz et al.’s “pro- jective parser” efficiently (§4). We extend the supertag-factored heuristic of Lewis and Steed- man’s (2014) A* parser for CCG with a heuristic for dependency edge scores. This parser achieves a speed of up to 2200 tokens/s on semantic de- pendency parsing (Oepen et al., 2015), at no loss in accuracy. On AMR corpora (Banarescu et al., 2013), it achieves a speedup of 10x over previous work, but still does not exceed 30 tokens/second. We therefore develop an entirely new transition- based parser for AM dependency trees, inspired by the stack-pointer parser of Ma et al. (2018) for syn- tactic dependency parsing (§5). The key challenge here is to adhere to complex symbolic constraints – the AM algebra’s type system – …

Content truncated to 500 words