Cache Transition Systems for Graph Parsing

Cache Transition Systems for Graph Parsing Daniel Gildea∗ University of Rochester Giorgio Satta∗∗ Universit`a di Padova Xiaochang Peng† University of Rochester Motivated by the task of semantic parsing, we describe a transition system that generalizes standard transition-based dependency parsing techniques to generate a graph rather than a tree. Our system includes a cache with fixed size m, and we characterize the relationship between the parameter m and the class of graphs that can be produced through the graph-theoretic concept of tree decomposition. We find empirically that small cache sizes cover a high percentage of sentences in existing semantic corpora. 1. Introduction As statistical natural language processing systems have progressed to provide deeper representations, there has been renewed interest in graph-based representations of se- mantic structures and in algorithms to produce them. Typically, these algorithms behave similarly to standard parsing algorithms for retrieving syntactic representations: They take as input a sentence and produce as output a graph representation of the semantics of the sentence itself. At the same time, recent years have seen a general trend from chart-based syntactic parsers toward stack-based transition systems, as the accuracy of transition systems has increased, and as speed has become increasingly important for real-world applications. On the syntactic side, stack-based transition systems for projective dependency parsing run in time O(n), where n is the sentence length; for a general overview of these systems, see, for instance, the presentation of Nivre (2008). There have also been ∗ Computer Science Department, University of Rochester, Rochester NY 14627. E-mail: gildea@cs.rochester.edu. ∗∗ Dipartimento di Ingegneria dell’Informazione, Universit`a di Padova, Via Gradenigo 6/A, 35131 Padova, Italy. E-mail: satta@dei.unipd.it. † Computer Science Department, University of Rochester, Rochester NY 14627. E-mail: xpeng@cs.rochester.edu.s Submission received: 19 December 2016; revised version received: 26 June 2017; accepted for publication: 7 July 2017. doi:10.1162/COLI a 00308 © 2017 Association for Computational Linguistics Published under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license Computational Linguistics Volume 44, Number 1 a number of extensions of stack-based transition systems to handle non-projective trees (e.g., Attardi 2006; Nivre 2009; Choi and McCallum 2013; G´omez-Rodr´ıguez and Nivre 2013; Pitler and McDonald 2015). Stack-based transition systems can produce general graphs rather than trees. Per- haps the simplest way to generate graphs is to shift one word at a time onto the stack, and then consider building all possible arcs between each word on the stack and the next word in the buffer. This is essentially the algorithm of Covington (2001), generalized to produce graphs rather than non-projective trees. This algorithm was also cast as a stack-based transition system by Nivre (2008). The algorithm runs in time O(n2), and requires the system to discriminate the arcs to be built from a large set of possibilities, potentially leading to errors. Traditional stack-based parsing, which is restricted to trees, and the Covington algorithm as generalized to graph parsing can be thought of as two extremes, with a wide set of possible intermediate approaches staking out different trade-offs between expressiveness, on the one …

Content truncated to 500 words