A Synchronous Hyperedge Replacement Grammar based approach for AMR parsing

Proceedings of the 19th Conference on Computational Language Learning, pages 32–41, Beijing, China, July 30-31, 2015. c⃝2015 Association for Computational Linguistics A Synchronous Hyperedge Replacement Grammar based approach for AMR parsing Xiaochang Peng, Linfeng Song and Daniel Gildea Department of Computer Science University of Rochester Rochester, NY 14627 Abstract This paper presents a synchronous-graph- grammar-based approach for string-to- AMR parsing. We apply Markov Chain Monte Carlo (MCMC) algorithms learn Synchronous Hyperedge Replace-to ment Grammar (SHRG) rules from a for- est that represents likely derivations con- sistent with a fixed string-to-graph align- ment. We make an analogy of string-to- AMR parsing to the task of phrase-based machine translation and come up with an efficient algorithm to learn graph gram- mars from string-graph pairs. We pro- pose an effective approximation strategy to resolve the complexity issue of graph compositions. We also show some useful strategies to overcome existing problems in an SHRG-based parser and present pre- liminary results of a graph-grammar-based approach. 1 Introduction Abstract Meaning Representation (AMR) (Ba- narescu et al., 2013) is a semantic formalism where the meaning of a sentence is encoded as a rooted, directed graph. Figure 1 shows an exam- ple of the edge-labeled representation of an AMR graph where the edges are labeled while the nodes are not. The label of the leaf edge going out of a node represents the concept of the node, and the label of a non-leaf edge shows the relation be- tween the concepts of the two nodes it connects to. This formalism is based on propositional logic and neo-Davidsonian event representations (Parsons, 1990; Davidson, 1967). AMR does not encode quantifiers, tense and modality, but it jointly en- codes a set of selected semantic phenomena which renders it useful in applications like question an- swering and semantics-based machine translation. want-01 believe-01 ARG1 ARG0 girl boy ARG0 ARG1 Figure 1: An example of AMR graph representing the meaning of: “The boy wants the girl to believe him” The task of AMR graph parsing is to map nat- ural language strings to AMR semantic graphs. Flanigan et al. (2014) propose a two-stage pars- ing algorithm which first maps meaningful contin- uous spans on the string side to concept fragments on the graph side, and then in the second stage adds additional edges to make all these fragments connected. Concept identification (Flanigan et al., 2014; Pourdamghani et al., 2014) can be consid- ered as an important first step to relate components of the string to components in the graph. Wang et al. (2015) also present a two-stage pro- cedure where they first use a dependency parser trained on a large corpus to generate a depen- dency tree for each sentence. In the second step, a transition-based algorithm is used to greedily modify the dependency tree into an AMR graph. The benefit of starting with a dependency tree in- stead of the original sentence is that the depen- dency structure is more linguistically similar to an AMR graph and provides more direct feature in- formation …

Content truncated to 500 words