Generalized Transition-based Dependency Parsing via Control Parameters

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 150–160, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Generalized Transition-based Dependency Parsing via Control Parameters Bernd Bohnet, Ryan McDonald, Emily Pitler and Ji Ma Google Inc. {bohnetbd,ryanmcd,epitler,maji}@google.com Abstract In this paper, we present a generalized transition-based parsing framework where parsers are instantiated in terms of a set of control parameters that constrain tran- sitions between parser states. This gener- alization provides a unified framework to describe and compare various transition- based parsing approaches from both a the- oretical and empirical perspective. This includes well-known transition systems, but also previously unstudied systems. 1 Introduction Transition-based dependency parsing is perhaps the most successful parsing framework in use to- day (Nivre, 2008). This is due to the fact that it can process sentences in linear time (Nivre, 2003); is highly accurate (Zhang and Nivre, 2011; Bohnet and Nivre, 2012; Weiss et al., 2015); and has el- egant mechanisms for parsing non-projective sen- tences (Nivre, 2009). As a result, there have been numerous studies into different transition systems, each with varying properties and complexities (Nivre, 2003; Attardi, 2006; Nivre, 2008; Nivre, 2009; G´omez-Rodr´ıguez and Nivre, 2010; Choi and Palmer, 2011; Pitler and McDonald, 2015). While connections between these transition sys- tems have been noted, there has been little work on developing frameworks that generalize the phe- nomena parsed by these diverse systems. Such a framework would be beneficial for many reasons: It would provide a language from which we can theoretically compare known transition systems; it can give rise to new systems that could have fa- vorable empirical properties; and an implementa- tion of the generalization allows for comprehen- sive empirical studies. In this work we provide such a generalized transition-based parsing framework. Our frame- work can be cast as transition-based parsing as it contains both parser states as well as transitions between these states that construct dependency trees. As in traditional transition-based parsing, the state maintains two data structures: a set of un- processed tokens (normally called the buffer); and a set of operative tokens (often called the stack). Key to our generalization is the notion of active tokens, which is the set of tokens in which new arcs can be created and/or removed from consid- eration. A parser instantiation is defined by a set of control parameters, which dictate: the types of transitions that are permitted and their properties; the capacity of the active token set; and the maxi- mum arc distance. We show that a number of different transi- tion systems can be described via this frame- work. Critically the two most common systems are covered – arc-eager and arc-standard (Nivre, 2008). But also Attardi’s non-projective (Attardi, 2006), Kuhlmann’s hybrid system (Kuhlmann et al., 2011), the directed acyclic graph (DAG) parser of Sagae and Tsujii (2008), and likely others. More interestingly, the easy-first framework of Goldberg and Elhadad (2010) can be described as an arc-standard system with an unbounded active token capacity. We present a …

Content truncated to 500 words