Non-projective Dependency Parsing using Spanning Tree Algorithms

Weighted dependency parsing is the search for a maximum spanning tree (MST) in a directed graph over the words. The Eisner algorithm finds the best projective tree in \(O(n^3)\), and the Chu-Liu-Edmonds MST algorithm finds the best non-projective tree in \(O(n^2)\).

Each word depends on exactly one parent, another word or a dummy root. It is projective if, with words in linear order preceded by the root, all edges can be drawn above the words without crossing; equivalently, every word and its descendants form a contiguous substring.

Dependency structures are more efficient to learn and parse than lexicalized phrase structures while still encoding much of the predicate-argument information that applications such as relation extraction, machine translation, synonym generation and lexical resource augmentation need.

When a dependent is separated from its head by material outside the head’s subtree, e.g. a relative clause separated from the noun it modifies by an adverb: “John saw a dog yesterday which was a Yorkshire Terrier.” Non-projectivity is more frequent in freer word order languages like German, Dutch and Czech.

As the sum of its edge scores, each a dot product of a weight vector and a feature vector of the edge: \(s(x, y) = \sum_{(i,j) \in y} s(i, j) = \sum_{(i,j) \in y} \mathbf{w} \cdot \mathbf{f}(i, j)\). Parsing is finding the highest-scoring tree.

\(G_x\) has vertices \(x_0 = \text{root}, x_1, \ldots, x_n\) and a directed edge \((i, j)\) for every \(i \ne j\) with \(j \ge 1\): from the root to every word and between every pair of distinct words, weighted by \(s(i, j)\). Dependency trees for \(x\) are exactly the spanning trees of \(G_x\) rooted at the root (arborescences).

Each vertex greedily picks its highest-scoring incoming edge. If the result is a tree, it is the MST. Otherwise contract a cycle into a single node, recompute the weights of edges into and out of it, recursively find the MST of the contracted graph, and expand the cycle, breaking it at the vertex where the chosen incoming edge enters.

Edges out: \(s(c, x) = \max_{x' \in C} s(x', x)\). Edges in: \(s(x, c) = \max_{x' \in C} [s(x, x') - s(a(x'), x') + s(C)]\), where \(a(x')\) is the predecessor of \(x'\) in the cycle and \(s(C)\) the cycle’s total weight: entering at \(x'\) means dropping the cycle edge into \(x'\).

Best incoming edges: saw→John, John→saw, saw→Mary, giving the cycle John⇄saw (\(s(C) = 50\)). Contract to \(c\): root→\(c\) = max(10 − 20, 9 − 30) + 50 = 40; Mary→\(c\) = max(0 − 20, 11 − 30) + 50 = 31; \(c\)→Mary = 30. Now root→\(c\) and \(c\)→Mary form a tree. Expanding gives root→saw, saw→John, saw→Mary (score 70).

Naively \(O(n^3)\): each recursive call takes \(O(n^2)\) to pick incoming edges and contract, and there are at most \(O(n)\) contractions. Tarjan’s (1977) implementation runs in \(O(n^2)\) on dense graphs, which is the dependency parsing case.

It finds the maximum projective spanning tree in \(O(n^3)\) by bottom-up dynamic programming, which is needed to maintain the nested, non-crossing structure. Chu-Liu-Edmonds is greedy and recursive and needn’t enforce non-crossing.

Non-projective parsing searches all spanning trees with no non-crossing constraint, which takes \(O(n^2)\) with Chu-Liu-Edmonds; enforcing projectivity needs Eisner’s \(O(n^3)\) dynamic program. This dispels the notion that non-projective parsing is harder.

Pseudo-projective parsing parses projectively and recovers non-projective edges through learned edge transformations. MST parsing is true non-projective parsing: it searches the full space of non-projective trees exactly and efficiently, without pruning.

Online: for each training sentence, find the new weights closest to the old ones, \(\min \|\mathbf{w}^{(i+1)} - \mathbf{w}^{(i)}\|\), such that the correct tree outscores every other tree \(y'\) by at least its loss: \(s(x_t, y_t) - s(x_t, y') \ge L(y_t, y')\). The final weights are averaged over all updates, as in the averaged perceptron.

The number of words with an incorrect parent relative to the correct tree, closely related to the Hamming loss used for sequences.

It keeps only one margin constraint, for the current highest-scoring tree \(y' = \arg\max_{y'} s(x_t, y')\), instead of exponentially many. Earlier projective work used the \(k\) best trees, but \(k\)-best extensions of Chu-Liu-Edmonds are too inefficient. Unlike the perceptron, MIRA updates aggressively to maximize the margin.

It factors the exponentially many tree constraints into \(O(n^2)\) local ones: for each word \(x_j\), the correct incoming edge must beat every other incoming edge by 1, \(s(l, j) - s(k, j) \ge 1\) for \((l, j) \in y_t\), \((k, j) \notin y_t\). Then the correct tree beats any other tree by at least its number of wrong edges. These constraints are stricter than the originals.

The Czech Prague Dependency Treebank, with automatic POS tags reduced to Collins et al.’s (1999) tag set and about 13.5M features. About 23% of sentences have at least one non-projective dependency, but fewer than 2% of edges are non-projective; Czech-B contains only those 23% of sentences.

On the full PDT, accuracy (words with correct parent) was 84.1% for single-best and 84.4% for factored MIRA, vs 83.3% for the projective Eisner-based parser, 82.8% for Collins et al. (1999) and 80.0% for Nivre and Nilsson’s pseudo-projective parser. On non-projective sentences, 81.0–81.5% vs 74.8%.

Not on Czech: the weights are learned with respect to the parsing algorithm and disfavour unlikely non-projective edges. On projective English (Penn Treebank), Chu-Liu-Edmonds was slightly worse (90.2% vs 90.9%), since Eisner exploits the prior knowledge that all trees are projective.

It requires tree scores that decompose over single edges. Extending it to features of larger substructures would make the search for the best non-projective tree intractable.