A Crossing-Sensitive Third-Order Factorization for Dependency Parsing

A Crossing-Sensitive Third-Order Factorization for Dependency Parsing Emily Pitler∗ Google Research 76 9th Avenue New York, NY 10011 epitler@google.com Abstract Parsers that parametrize over wider scopes are generally more accurate than edge-factored models. For graph-based non-projective parsers, wider factorizations have so far im- plied large increases in the computational complexity of the parsing problem. This paper introduces a “crossing-sensitive” generaliza- tion of a third-order factorization that trades off complexity in the model structure (i.e., scoring with features over multiple edges) with complexity in the output structure (i.e., producing crossing edges). Under this model, the optimal 1-Endpoint-Crossing tree can be found in O(n4) time, matching the asymp- totic run-time of both the third-order projec- tive parser and the edge-factored 1-Endpoint- Crossing parser. The crossing-sensitive third- order parser is significantly more accurate than the third-order projective parser under many experimental settings and significantly less accurate on none. 1 Introduction Conditioning on wider syntactic contexts than sim- ply individual head-modifier relationships improves parsing accuracy in a wide variety of parsers and frameworks (Charniak and Johnson, 2005; McDon- ald and Pereira, 2006; Hall, 2007; Carreras, 2007; Martins et al., 2009; Koo and Collins, 2010; Zhang and Nivre, 2011; Bohnet and Kuhn, 2012; Martins et al., 2013). This paper proposes a new graph- based dependency parser that efficiently produces ∗The majority of this work was done while at the University of Pennsylvania. the globally optimal dependency tree according to a third-order model (that includes features over grand- parents and siblings in the tree) in the class of 1- Endpoint-Crossing trees (that includes all projective trees and the vast majority of non-projective struc- tures seen in dependency treebanks). Within graph-based projective parsing, the third- order parser of Koo and Collins (2010) has a run- time of O(n4), just one factor of n more expensive than the edge-factored model of Eisner (2000). In- corporating richer features and producing trees with crossing edges has traditionally been a challenge, however, for graph-based dependency parsers. parsing is posed as the problem of finding the op-If timal scoring directed spanning tree, then the prob- lem becomes NP-hard when trees are scored with a grandparent and/or sibling factorization (McDonald and Pereira, 2006; McDonald and Satta, 2007). For various definitions of mildly non-projective trees, even edge-factored versions are expensive, with edge-factored running times between O(n4) and O(n7) (G´omez-Rodr´ıguez et al., 2011; Pitler et al., 2012; Pitler et al., 2013; Satta and Kuhlmann, 2013). The third-order projective parser of Koo and Collins (2010) and the edge-factored 1-Endpoint- Crossing parser described in Pitler et al. (2013) have some similarities: both use O(n4) time and O(n3) space, using sub-problems over intervals with one exterior vertex, which are constructed using one free split point. The two parsers differ in how the exterior vertex is used: Koo and Collins (2010) use the exterior vertex to store a grandparent in- dex, while Pitler et al. (2013) use the exterior ver- tex to introduce crossed edges between the point and 41 Transactions of the Association for Computational Linguistics, 2 (2014) …

Content truncated to 500 words