An efficient algorithm for easy-first non-directional dependency parsing

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.