Finding Optimal 1-Endpoint-Crossing Trees

Transactions of the Association for Computational Linguistics, 1 (2013) 13–24. Action Editor: Giorgio Satta. Submitted 11/2012; Published 3/2013. c⃝2013 Association for Computational Linguistics. Finding Optimal 1-Endpoint-Crossing Trees Emily Pitler, Sampath Kannan, Mitchell Marcus Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 epitler,kannan,mitch@seas.upenn.edu Abstract Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have tra- ditionally been orders of magnitude slower than algorithms for projective trees. For 95.8- 99.8% of dependency parses in various nat- ural language treebanks, whenever an edge is crossed, the edges that cross it all have a common vertex. The optimal dependency tree that satisfies this 1-Endpoint-Crossing prop- erty can be found with an O(n4) parsing al- gorithm that recursively combines forests over intervals with one exterior point. 1-Endpoint- Crossing trees also have natural connections to linguistics and another class of graphs that has been studied in NLP. 1 Introduction Dependency parsing is one of the fundamental prob- lems in natural language processing today, with ap- plications such as machine translation (Ding and Palmer, 2005), information extraction (Culotta and Sorensen, 2004), and question answering (Cui et al., 2005). Most high-accuracy graph-based depen- dency parsers (Koo and Collins, 2010; Rush and Petrov, 2012; Zhang and McDonald, 2012) find the highest-scoring projective trees (in which no edges cross), despite the fact that a large proportion of nat- ural language sentences are non-projective. Projec- tive trees can be found in O(n3) time (Eisner, 2000), but cover only 63.6% of sentences in some natural language treebanks (Table 1). The class of directed spanning trees covers all treebank trees and can be parsed in O(n2) with edge-based features (McDonald et al., 2005), but it is NP-hard to find the maximum scoring such tree with grandparent or sibling features (McDonald and Pereira, 2006; McDonald and Satta, 2007). There are various existing definitions of mildly non-projective trees with better empirical coverage than projective trees that do not have the hardness of extensibility that spanning trees do. However, these have had parsing algorithms that are orders of mag- nitude slower than the projective case or the edge- based spanning tree case. For example, well-nested dependency trees with block degree 2 (Kuhlmann, 2013) cover at least 95.4% of natural language struc- tures, but have a parsing time of O(n7) (Gómez- Rodríguez et al., 2011). No previously defined class of trees simultane- ously has high coverage and low-degree polynomial algorithms for parsing, allowing grandparent or sib- ling features. We propose 1-Endpoint-Crossing trees, in which for any edge that is crossed, all other edges that cross that edge share an endpoint. While simple to state, this property covers 95.8% or more of de- pendency parses in natural language treebanks (Ta- ble 1). The optimal 1-Endpoint-Crossing tree can be found in faster asymptotic time than any previ- ously proposed mildly non-projective dependency parsing algorithm. We show how any 1-Endpoint- Crossing tree can be decomposed into isolated sets of intervals with one exterior point (Section 3). This is the key insight …

Content truncated to 500 words