Abstract
We present a novel deterministic dependency parsing 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, perform 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 algorithm builds a dependency tree by iteratively selecting 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 deterministic, best-first, O(nlogn) parser, which is significantly more accurate than best-first transition based parsers, and nears the performance of globally optimized parsing models.
1. Introduction
Dependency parsing, the process of identifying grammatical relationships between words, has traditionally been dominated by two paradigms. Transition-based parsers, such as MALT, offer high efficiency ($O(n)$) but are constrained by a strict left-to-right processing order, leading to error propagation. Conversely, graph-based parsers like MST achieve higher accuracy by considering the entire sentence globally, but at a significant computational cost ($O(n^3)$).
Goldberg and Elhadad (2010) propose a middle ground: an "Easy-First" parser. This approach mimics human intuition by identifying simple, local structures first—such as adjectives modifying nouns—and using these as anchors for more complex, ambiguous relationships. By breaking the directional constraint, the parser can utilize context from both sides of an attachment point.
2. The Easy-First Parsing Algorithm
The core of the Easy-First algorithm is its non-directional, iterative nature. The parser maintains a list of "pending" words. In each step, it evaluates all possible attachments between adjacent words in this list. The attachment with the highest confidence score is selected, the arc is created, and the child node is removed from the pending list. This process continues until only the root remains.
To achieve efficiency, the parser utilizes a heap data structure to track scores, resulting in an $O(n \log n)$ runtime. This is significantly faster than global models while allowing for richer feature sets than standard greedy transition-based parsers. Because the parser is deterministic, it can incorporate features from already-completed subtrees, such as the leftmost or rightmost child of a verb, to inform subsequent decisions.
3. Learning to Rank Attachments
The parser is trained using a structured perceptron. A key innovation is that the model learns not just which attachments are correct, but the optimal order in which to make them. If the parser makes an incorrect attachment early due to misplaced confidence, the training algorithm penalizes this choice, encouraging the model to defer difficult decisions until more structural context is available.
4. Experimental Results
The Easy-First parser was evaluated on the Wall Street Journal (WSJ) Treebank and the CoNLL 2007 English Shared Task. On the WSJ dataset, it achieved an unlabeled accuracy of 89.70%, outperforming the MALT parser (88.36%) and approaching the MST parser (90.05%).
Notably, the Easy-First parser excelled in "Complete Match" rates, producing 37.5% entirely correct sentences, compared to 34.1% for MALT and 34.6% for MST. This suggests that the strategy of resolving easy dependencies first is highly effective at preventing the cascading errors typical of greedy directional parsers.
5. Conclusion and Future Work
The Easy-First parser provides a compelling alternative to traditional dependency parsing methods, offering a balance of efficiency and accuracy. While it currently faces challenges with non-projective structures and certain complex linguistic constructions like relative clauses, its ability to look "into the future" and prioritize confidence makes it a robust tool for natural language processing tasks. Future work may involve extending the algorithm to handle non-projective trees natively and refining the feature set for even greater accuracy.
Summary updated