Exact Inference for Generative Probabilistic Non-Projective Dependency Parsing

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1234–1245, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Exact Inference for Generative Probabilistic Non-Projective Dependency Parsing Shay B. Cohen School of Computer Science Carnegie Mellon University, USA scohen@cs.cmu.edu Carlos G´omez-Rodr´ıguez Departamento de Computaci´on Universidade da Coru˜na, Spain cgomezr@udc.es Giorgio Satta Dept. of Information Engineering University of Padua, Italy satta@dei.unipd.it Abstract We describe a generative model for non- projective dependency parsing based on a sim- plified version of a transition system that has recently appeared in the literature. We then develop a dynamic programming parsing al- gorithm for our model, and derive an inside- outside algorithm that can be used for unsu- pervised learning of non-projective depend- ency trees. 1 Introduction Dependency grammars have received considerable attention in the statistical parsing community in recent years. These grammatical formalisms of- fer a good balance between structural expressiv- ity and processing efficiency. Most notably, when non-projectivity is supported, these formalisms can model crossing syntactic relations that are typical in languages with relatively free word order. Recent work has reduced non-projective parsing to the identification of a maximum spanning tree in a graph (McDonald et al., 2005; Koo et al., 2007; Mc- Donald and Satta, 2007; Smith and Smith, 2007). An alternative to this approach is to use transition- based parsing (Yamada and Matsumoto, 2003; Nivre and Nilsson, 2005; Attardi, 2006; Nivre, 2009; G´omez-Rodr´ıguez and Nivre, 2010), where there is an incremental processing of a string with a model that scores transitions between parser states, condi- tioned on the parse history. This paper focuses on the latter approach. The above work on transition-based parsing has focused on greedy algorithms set in a statistical framework (Nivre, 2008). More recently, dynamic programming has been successfully used for pro- jective parsing (Huang and Sagae, 2010; Kuhlmann et al., 2011). Dynamic programming algorithms for parsing (also known as chart-based algorithms) al- low polynomial space representations of all parse trees for a given input string, even in cases where the size of this set is exponential in the length of the string itself. In combination with appropriate semirings, these packed representations can be ex- ploited to compute many values of interest for ma- chine learning, such as best parses and feature ex- pectations (Goodman, 1999; Li and Eisner, 2009). In this paper we move one step forward with re- spect to Huang and Sagae (2010) and Kuhlmann et al. (2011) and present a polynomial dynamic pro- gramming algorithm for non-projective transition- based parsing. Our algorithm is coupled with a simplified version of the transition system from At- tardi (2006), which has high coverage for the type of non-projective structures that appear in various treebanks. Instead of an additional transition oper- ation which permits swapping of two elements in the stack (Titov et al., 2009; Nivre, 2009), Attardi’s system allows reduction of elements at non-adjacent positions in the stack. We also present a generat- ive probabilistic model for transition-based parsing. The implication for …

Content truncated to 500 words