Algorithms for Deterministic Incremental Dependency Parsing

Natural language grammars are massively ambiguous, so mainstream parsers derive many analyses in parallel (charts, dynamic programming) and rank them. But treebank-induced classifiers that predict the next derivation step can make a single left-to-right derivation highly accurate, especially for dependency parsing.

It is an extreme form of pruning: parse selection happens incrementally and only one analysis is ever built, making parsing very simple and efficient, at the risk of losing accuracy through early commitment in greedy search. In practice it reached state-of-the-art accuracy, e.g. tying for top results at CoNLL-X 2006.

A parsing algorithm (derivations as sequences of elementary actions), a feature model (a feature vector representation of the parser state), and a classifier mapping parser states to actions. Nivre (2008) focuses on the algorithms.

ROOT: node 0 has no head. SINGLE-HEAD: every node has at most one head and one label. ACYCLICITY: there are no cycles. Such a graph is a dependency forest; if also connected, a dependency tree rooted at 0. A forest becomes a tree by attaching all other roots to node 0.

For every arc \((i, l, j)\) and every node \(k\) between \(i\) and \(j\), \(k\) is reachable from \(i\) (\(i \to^* k\)). Equivalently, every node’s projection (the nodes reachable from it) is continuous, the dependency analogue of banning discontinuous constituents.

A quadruple \(S = (C, T, c_s, C_t)\): configurations \(C\) (at least a buffer \(\beta\) of remaining nodes and an arc set \(A\)), transitions \(T\) (partial functions \(C \to C\)), an initialization \(c_s\) putting \([1, \ldots, n]\) in the buffer, and terminal configurations \(C_t\). The parse is the arc set of the terminal configuration.

A function \(o: C \to T\) choosing one transition in every configuration. The parser starts in \(c_s(x)\) and applies \(o(c)\) until a terminal configuration is reached. In data-driven parsing the oracle is approximated by a classifier trained on treebank data.

To separate the abstract machine, which determines formal properties like correctness and complexity, from the search mechanism. If oracle and transitions take constant time, time complexity is bounded by the maximum length of a transition sequence, and space by the size of one configuration.

Sound: every transition sequence yields a graph in the class. Complete: every graph in the class is the result of some transition sequence. Correct: both.

A triple \((\sigma, \beta, A)\): a stack \(\sigma\) of partially processed tokens still candidates for arcs, a buffer \(\beta\) of remaining input tokens, and an arc set \(A\). Parsing starts with \(([0], [1, \ldots, n], \emptyset)\) and ends when the buffer is empty.

LEFT-ARC\(_l\): \((\sigma|i, j|\beta, A) \Rightarrow (\sigma, j|\beta, A \cup \{(j, l, i)\})\), if \(i \ne 0\) and \(i\) has no head. RIGHT-ARC\(_l\): \((\sigma|i, j|\beta, A) \Rightarrow (\sigma, i|\beta, A \cup \{(i, l, j)\})\), if \(j\) has no head; the head \(i\) goes back to the buffer. SHIFT: \((\sigma, i|\beta, A) \Rightarrow (\sigma|i, \beta, A)\).

It is the closest analogue of shift-reduce parsing for CFGs: LEFT-ARC and RIGHT-ARC are reduce actions replacing a head–dependent structure with its head. A right dependent can be attached only after it has collected all its own dependents, because it is removed when attached.

Each SHIFT removes one node from the buffer, which never grows, so there are at most \(n\) shifts; each arc transition pops the stack, which only SHIFT pushes. So a transition sequence has at most \(2n\) transitions: \(O(n)\) time, and \(O(n)\) space for one configuration.

Projective dependency forests: every transition preserves ROOT, SINGLE-HEAD, ACYCLICITY and PROJECTIVITY (soundness), and every projective forest has a transition sequence that builds it (completeness).

LEFT-ARC\(_l\): as in arc-standard (pop \(i\), add \((j, l, i)\)). RIGHT-ARC\(_l\): \((\sigma|i, j|\beta, A) \Rightarrow (\sigma|i|j, \beta, A \cup \{(i, l, j)\})\), pushing the dependent. REDUCE: pop the stack, if the top already has a head. SHIFT: push the first buffer node.

Arc-eager attaches right dependents as soon as possible, before they have found their own right dependents, so both head and dependent stay on the stack; REDUCE pops the dependent later. It is more incremental: a word is attached as soon as its head is available.

SHIFT, LEFT-ARC_SBJ, RIGHT-ARC_ROOT, RIGHT-ARC_OBJ; the buffer is then empty, so parsing ends (LA/RA = LEFT-/RIGHT-ARC):

transition	stack	buffer	arc
–	[0]	[1,2,3]
SHIFT	[0, 1]	[2, 3]
LASBJ	[0]	[2, 3]	2 → 1
RAROOT	[0, 2]	[3]	0 → 2
RAOBJ	[0,2,3]	[ ]	2 → 3

A quadruple \((\lambda_1, \lambda_2, \beta, A)\): two lists of partially processed tokens plus the buffer and arcs. Inspired by Covington (2001), it lets the parser consider pairs of non-adjacent tokens: nodes skipped over are moved from \(\lambda_1\) to \(\lambda_2\) and restored on the next shift, which allows non-projective arcs.

For \(i\) at the head of \(\lambda_1\) and \(j\) first in the buffer: LEFT-ARC adds \(j \to i\), RIGHT-ARC adds \(i \to j\), and NO-ARC adds nothing; each moves \(i\) to \(\lambda_2\). SHIFT\(_\lambda\) concatenates \(\lambda_1.\lambda_2\), appends \(j\), and empties \(\lambda_2\). Arcs require that the dependent has no head and no cycle results (\(\neg[i \to^* j]\) or \(\neg[j \to^* i]\)).

\(O(n^2)\) time: there are at most \(n\) shifts, and between the \((i-1)\)th and \(i\)th shift each other transition shrinks \(\lambda_1\), so at most \(i\) of them: \(\sum_i (i + 1)\) transitions. Space is \(O(n)\). The acyclicity check is near-constant with union-find (\(O(\alpha(n))\) amortized).

It skips any pair that could create a non-projective arc: LEFT-ARC deletes the dependent and empties \(\lambda_2\); RIGHT-ARC moves \(j\) onto \(\lambda_1\) and empties \(\lambda_2\); NO-ARC requires that \(i\) already has a head, since an arc spanning a root would violate projectivity. Worst case \(O(n^2)\), but in practice it behaves linearly.

On the 13 CoNLL-X shared task languages, with MaltParser and SVM classifiers (quadratic kernel) trained on oracle transition sequences from gold trees, using the same simple feature model for all. Seven parsers per language: non-projective list-based, and the three projective algorithms in strictly projective and pseudo-projective versions. Metrics: LAS, UAS, label accuracy.

Train a projective parser on projectivized data: non-projective arcs are lifted to the nearest permissible ancestor of the real head, with the real head’s label encoded in the arc label. After parsing, arcs with augmented labels are lowered by searching the head’s descendants for a node with that label (Nivre and Nilsson 2005).

It performs a default transition with no preconditions instead: SHIFT for the stack-based algorithms, NO-ARC for the list-based ones. Classifiers rarely predict illegal transitions.

Averages were very close, within 0.58 LAS points: 79.77 for non-projective list-based (best) down to 79.19 for strictly projective list-based. Non-projective and pseudo-projective parsers significantly beat strictly projective ones, and the non-projective parser’s gain grew with the proportion of non-projective arcs in the data (Pearson’s r = 0.815).

Both help when non-projective arcs are common, but non-projective parsing is more stable: it seldom or never hurts, while pseudo-projective parsing can hurt when training data or non-projective arcs are scarce, partly because extra labels reduce label accuracy.

Their Prague-style annotation allows several root dependents with different labels (e.g. PRED), which must be attached by a RIGHT-ARC with the right label at the right time. Arc-eager attaches right dependents early and had much lower precision and recall on PRED than arc-standard.

Learning time is driven by the number of training instances, so the quadratic non-projective algorithm trained slowest. The projective list-based parser, though \(O(n^2)\) in the worst case, ran like the linear algorithms. Pseudo-projective parsers were always substantially slower to parse than their projective counterparts, sometimes slower than the non-projective parser.

Pseudo-projective parsing enlarges the label set, hence the number of SVM classes and binary classifiers, making every classification slower. For typical sentence lengths, this larger constant can outweigh the better asymptotic complexity. The pseudo-projective parsers were faster than the non-projective one on every data set with average sentence length above 18.

All four algorithms give competitive, near state-of-the-art accuracy. The ability to produce non-projective graphs improves accuracy unless all structures are projective, and the non-projective list-based algorithm does so more stably than pseudo-projective parsing, often just as fast. Arc-eager vs arc-standard shows language- and annotation-specific effects.