An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 742–750, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing Yoav Goldberg∗and Michael Elhadad Ben Gurion University of the Negev Department of Computer Science POB 653 Be’er Sheva, 84105, Israel {yoavg|elhadad}@cs.bgu.ac.il Abstract We present a novel deterministic dependency pars- ing algorithm that attempts to create the easiest arcs in the dependency structure first in a non-directional manner. Traditional deterministic parsing algorithms are based on a shift-reduce framework: they traverse the sentence from left-to-right and, at each step, per- form one of a possible set of actions, until a complete tree is built. A drawback of this approach is that it is extremely local: while decisions can be based on complex structures on the left, they can look only at a few words to the right. In contrast, our algo- rithm builds a dependency tree by iteratively select- ing the best pair of neighbours to connect at each parsing step. This allows incorporation of features from already built structures both to the left and to the right of the attachment point. The parser learns both the attachment preferences and the order in which they should be performed. The result is a determin- istic, best-first, O(nlogn) parser, which is signifi- cantly more accurate than best-first transition based parsers, and nears the performance of globally opti- mized parsing models. 1 Introduction Dependency parsing has been a topic of active re- search in natural language processing in the last sev- eral years. An important part of this research effort are the CoNLL 2006 and 2007 shared tasks (Buch- holz and Marsi, 2006; Nivre et al., 2007), which al- lowed for a comparison of many algorithms and ap- proaches for this task on many languages. ∗Supported by the Lynn and William Frankel Center for Computer Sciences, Ben Gurion University Current dependency parsers can be categorized into three families: local-and-greedy transition- based parsers (e.g., MALTPARSER (Nivre et al., 2006)), globally optimized graph-based parsers (e.g., MSTPARSER (McDonald et al., 2005)), and hybrid systems (e.g., (Sagae and Lavie, 2006b; Nivre and McDonald, 2008)), which combine the output of various parsers into a new and improved parse, and which are orthogonal to our approach. Transition-based parsers scan the input from left to right, are fast (O(n)), and can make use of rich feature sets, which are based on all the previously derived structures. However, all of their decisions are very local, and the strict left-to-right order im- plies that, while the feature set can use rich struc- tural information from the left of the current attach- ment point, it is also very restricted in information to the right of the attachment point: traditionally, only the next two or three input tokens are avail- able to the parser. This limited look-ahead window leads to error propagation and worse performance on root and long distant dependencies relative to graph- based parsers (McDonald and Nivre, 2007). Graph-based …

Content truncated to 500 words