Dynamic Programming Algorithms for Transition-Based Dependency Parsers

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 673–682, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Dynamic Programming Algorithms for Transition-Based Dependency Parsers Marco Kuhlmann Dept. of Linguistics and Philology Uppsala University, Sweden marco.kuhlmann@lingfil.uu.se Carlos Gómez-Rodríguez Departamento de Computación Universidade da Coruña, Spain cgomezr@udc.es Giorgio Satta Dept. of Information Engineering University of Padua, Italy satta@dei.unipd.it Abstract We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to ob- tain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the con- ditions under which the feature models com- monly used in transition-based parsing can be integrated into our algorithms. 1 Introduction Dynamic programming algorithms, also known as tabular or chart-based algorithms, are at the core of many applications in natural language processing. When applied to formalisms such as context-free grammar, they provide polynomial-time parsing al- gorithms and polynomial-space representations of the resulting parse forests, even in cases where the size of the search space is exponential in the length of the input string. In combination with appropri- ate semirings, these packed representations can be exploited to compute many values of interest for ma- chine learning, such as best parses and feature expec- tations (Goodman, 1999; Li and Eisner, 2009). In this paper, we follow the line of investigation started by Huang and Sagae (2010) and apply dy- namic programming to (projective) transition-based dependency parsing (Nivre, 2008). The basic idea, originally developed in the context of push-down automata (Lang, 1974; Tomita, 1986; Billot and Lang, 1989), is that while the number of computa- tions of a transition-based parser may be exponential in the length of the input string, several portions of these computations, when appropriately represented, can be shared. This can be effectively implemented through dynamic programming, resulting in a packed representation of the set of all computations. The contributions of this paper can be summarized as follows. We provide (declarative specifications of) novel, polynomial-time algorithms for two widely- used transition-based parsing models: arc-standard (Nivre, 2004; Huang and Sagae, 2010) and arc-eager (Nivre, 2003; Zhang and Clark, 2008). Our algorithm for the arc-eager model is the first tabular algorithm for this model that runs in polynomial time. Both algorithms are derived using the same general tech- nique; in fact, we show that this technique is applica- ble to all transition-parsing models whose transitions can be classified into “shift” and “reduce” transitions. We also show how to reverse the tabulation to de- rive a new transition system from an existing tabular algorithm for dependency parsing, originally devel- oped by Gómez-Rodríguez et al. (2008). Finally, we discuss in detail the role of feature information in our algorithms, and in particular the conditions under which the feature models traditionally used in transi- tion-based dependency parsing can be integrated into our framework. While our …

Content truncated to 500 words