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

ACL ID N10-1115
Title An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing
Venue Human Language Technologies
Session Main Conference
Year 2010
Authors

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 th...