Fast semantic parsing with well-typedness guarantees (2020)

Abstract: AM dependency parsing is a linguistically principled method for neural semantic parsing with high accuracy across multiple graphbanks. It relies on a type system that models semantic valency but makes existing parsers slow. We describe an A* parser and a transition-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.

## introduction over the past few years, the accuracy of neural semantic parsers which parse english sentences into graph-based semantic representations has increased substantially @xcite @xcite . 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 @xcite 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 details 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 @xcite . however, the commitment to linguistic principles comes at a cost: the am dependency parser is slow. a key part of the parser is that am dependency trees must be well-typed according to a type system which ensures that the semantic valency of each word is respected. existing algorithms compute 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 @xcite s "projective parser" efficiently ( §4). we extend the supertag-factored heuristic of @xcite a* parser for ccg with a heuristic for dependency edge scores. this parser achieves a speed of up to 2200 tokens/s on semantic dependency parsing @xcite , at no loss in accuracy. on amr corpora @xcite , it achieves a speedup of 10x over previous work, but still does not exceed 30 tokens/second. we therefore develop an entirely new transitionbased parser for am dependency trees, inspired by the stack-pointer parser of @xcite for syntactic dependency parsing ( §5). the key challenge here is to adhere to complex symbolic constraints -the am algebra's type system -without running into dead ends. this is hard for a greedy transition system and in other settings requires expensive workarounds, such as backtracking. we ensure that our parser avoids dead ends altogether. we define two variants of the transition-based parser, which choose types for words either before predicting the outgoing edges or after, and introduce a neural model for predicting transitions. in this way, we guarantee well-typedness with o(n 2 ) parsing complexity, achieve a speed of several thousand tokens per second across all graphbanks, and even improve the parsing accuracy over previous am dependency parsers by up to 1.6 points f-score. ## related work in transition-based parsing, a dependency tree is built step by step using nondeterministic transitions. a classifier is trained to choose transitions deter-ministically @xcite . transition-based parsing has also been used for constituency parsing @xcite and graph parsing @xcite . we build most directly upon the top-down parser of @xcite . unlike most other transition-based parsers, our parser implements hard symbolic constraints in order to enforce well-typedness. such constraints can lead transition systems into dead ends, requiring the parser to backtrack @xcite or return partial analyses @xcite . our transition system carefully avoids dead ends. shi and lee (2018) take hard valency constraints into account in chart-based syntactic dependency parsing, avoiding dead ends by relaxing the constraints slightly in practice. a* parsing is a method for speeding up agendabased chart parsers, which takes items off the agenda based on a heuristic estimate of completion cost. a* parsing has been used successfully for pcfgs @xcite , tag @xcite , and other grammar formalisms. our work is based most closely on the ccg a* parser of @xcite . most approaches that produce semantic graphs (see @xcite for an overview) model distributions over graphs directly @xcite @xcite , while others make use of derivation trees that compositionally evaluate to graphs @xcite @xcite . am dependency parsing belongs to the latter category. ## background we begin by sketching the am dependency parser of @xcite . @xcite use am dependency trees to represent the compositional structure of a semantic graph. each token is assigned a graph constant representing its lexical meaning; dependency labels correspond to operations of the apply-modify (am) algebra @xcite , which combine graphs into bigger ones. marked in bold. these markers are used to combine graphs with the algebra's operations. for instance, the mod m operation in fig. 2a combines the head g sleep with its modifier g soundly by plugging the root of g sleep into the m-source of g soundly , see @xcite . that is, g soundly has now modified g sleep and (c) is our graph for sleep soundly. the other operation of the am algebra, app, models argument application. for example, the app o operation in fig. 2a plugs the root of (c) into the o source of g want . note that because g want and (c) both have an s-source, app o merges these nodes, see @xcite . the app s operation then fills this s-source with g writer , attaching the graph with its root, to obtain the final graph in (b). 1 types. the [s] annotation at the o-source of g want is a request as to what the type of the o argument of g want should be. the type of an as-graph is the set of its sources with their request annotations, so the request [s] means that the source set of the argument must be {s}. because this is true for (c), the am dependency tree is well-typed; otherwise the tree could not be evaluated to a graph. thus, the graph constants lexically specify the semantic valency of each word as well as reentrancies due to e.g. control, like in this example. ## a* am dependency parsing while the am dependency parser yields strong accuracies across multiple graphbanks, groschwitz et al.'s algorithms are quite slow in practice. for instance, the projective parser needs several hours to parse each test set in §6, which seriously limits its practical applicability. in this section, we will speed the projective parser up through a* search. ## transition-based parsing as we will see in §6, the a* parser is very efficient on the dm, pas, and psd corpora but still slow on eds and amr. therefore, we develop a novel transition-based algorithm for am dependency parsing. inspired by the syntactic dependency parser of @xcite , it builds the dependency tree top-down, starting at the root and recursively adding outgoing edges to nodes. however, for am dependency parsing we face an additional challenge: we must assign a type to each node and ensure that the overall am dependency tree is well-typed. we will first introduce some notation ( §5.1), then introduce three versions of our parsing schema ( §5.2- §5.4), give theoretical guarantees ( §5.5) and define the neural model ( §5.6). ## conclusion we have presented two fast and accurate algorithms for am dependency parsing: an a* parser which optimizes groschwitz et al.'s projective parser, and a novel transition-based parser which builds an am dependency top-down while avoiding dead ends. the parsing speed of the a* parser differs dramatically for the different graphbanks. in contrast, the parsing speed with the transition systems is less sensitive to the graphbank and faster overall. the transition systems also achieve higher accuracy. in future work, one could make the a* parser more accurate by extending it to non-projective dependency trees, especially on dm, eds and amr. the transition-based parser could be made more accurate by making bottom-up information available to its top-down choices, e.g. with cai and lam's (2020) "iterative inference" method. it would also be interesting to see if our method for avoiding dead ends can be applied to other formalisms with complex symbolic restrictions. matthias lindemann, jonas groschwitz, and alexander koller. 2019. compositional semantic parsing across graphbanks. in proceedings of the acl. xuezhe ma, zecong hu, jingzhou liu, nanyun peng, graham neubig, and eduard hovy. 2018. stackpointer networks for dependency parsing. in proceedings of the acl. joakim nivre. 2008. algorithms for deterministic incremental dependency parsing. computational linguistics, 34(4):513-553. stephan oepen, marco kuhlmann, yusuke miyao, daniel zeman, silvie cinková, dan flickinger, jan hajič, and zdeňka urešová. 2015. semeval 2015 task 18: broad-coverage semantic dependency parsing. in proceedings of the 9th international workshop on semantic evaluation (semeval 2015). tianze shi and lillian lee. 2018. valency-augmented dependency parsing. in proceedings of the emnlp. stuart shieber, yves schabes, and fernando pereira. 1995. principles and implementation of deductive parsing. journal of logic programming, 24(1-2):3-36. gisle ytrestøl. 2011. optimistic backtracking: a backtracking overlay for deterministic incremental parsing. in proceedings of the acl 2011 student session. association for computational linguistics. sheng zhang, xutai ma, kevin duh, and benjamin van durme. 2019. broad-coverage semantic parsing as transduction. in proceedings of the emnlp-ijcnlp. yue zhang and stephen clark. 2011. shift-reduce ccg parsing. in proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies -volume 1, hlt '11, usa.