A Discriminative Graph-Based Parser for the Abstract Meaning Representation

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1426–1436, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics A Discriminative Graph-Based Parser for the Abstract Meaning Representation Jeffrey Flanigan Sam Thomson Jaime Carbonell Chris Dyer Noah A. Smith Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA {jflanigan,sthomson,jgc,cdyer,nasmith}@cs.cmu.edu Abstract Abstract Meaning Representation (AMR) is a semantic formalism for which a grow- ing set of annotated examples is avail- able. We introduce the first approach to parse sentences into this representa- tion, providing a strong baseline for fu- ture improvement. The method is based on a novel algorithm for finding a maxi- mum spanning, connected subgraph, em- bedded within a Lagrangian relaxation of an optimization problem that imposes lin- guistically inspired constraints. Our ap- proach is described in the general frame- work of structured prediction, allowing fu- ture incorporation of additional features and constraints, and may extend to other formalisms as well. Our open-source sys- tem, JAMR, is available at: http://github.com/jflanigan/jamr 1 Introduction Semantic parsing is the problem of mapping nat- ural language strings into meaning representa- tions. Abstract Meaning Representation (AMR) (Banarescu et al., 2013; Dorr et al., 1998) is a semantic formalism in which the meaning of a sentence is encoded as a rooted, directed, acyclic graph. Nodes represent concepts, and labeled di- rected edges represent the relationships between them–see Figure 1 for an example AMR graph. The formalism is based on propositional logic and neo-Davidsonian event representations (Parsons, 1990; Davidson, 1967). Although it does not encode quantifiers, tense, or modality, the set of semantic phenomena included in AMR were se- lected with natural language applications—in par- ticular, machine translation—in mind. In this paper we introduce JAMR, the first pub- lished system for automatic AMR parsing. The system is based on a statistical model whose pa- rameters are trained discriminatively using anno- tated sentences in the AMR Bank corpus (Ba- narescu et al., 2013). We evaluate using the Smatch score (Cai and Knight, 2013), establishing a baseline for future work. The core of JAMR is a two-part algorithm that first identifies concepts using a semi-Markov model and then identifies the relations that ob- tain between these by searching for the maximum spanning connected subgraph (MSCG) from an edge-labeled, directed graph representing all pos- sible relations between the identified concepts. To solve the latter problem, we introduce an appar- ently novel O(|V |2 log |V |) algorithm that is sim- ilar to the maximum spanning tree (MST) algo- rithms that are widely used for dependency pars- ing (McDonald et al., 2005). Our MSCG algo- rithm returns the connected subgraph with maxi- mal sum of its edge weights from among all con- nected subgraphs of the input graph. Since AMR imposes additional constraints to ensure seman- tic well-formedness, we use Lagrangian relaxation (Geoffrion, 1974; Fisher, 2004) to augment the MSCG algorithm, yielding a tractable iterative al- gorithm that finds the optimal solution subject to these constraints. In our experiments, we have found this …

Content truncated to 500 words