Dependency Syntax and Universal Dependencies › Projectivity

Not every tree can be drawn without crossing arcs. Projectivity is the geometric constraint that rules out crossers. It is a property of the tree relative to the surface order of the words, so it is sensitive to word order even though the dependency relations themselves may be stable across word order changes.

Place the words of a valid basic tree on a horizontal line, with artificial node 0 to their left and its arc included. The tree is projective exactly when it admits an above-line drawing without crossing arcs. Here a crossing means strictly interleaved distinct endpoints, such as $a<c<b<d$ for arcs joining $a$ to $b$ and $c$ to $d$; shared endpoints are not crossings. Omitting the artificial-root arc can hide a violation, so the descendant test below is the safer definition.

In plain language: the arc from $h$ to $d$ is projective if every word between $h$ and $d$ is governed (directly or indirectly) by $h$. If it spans a word outside $h$'s subtree, a crossing is unavoidable when the artificial-root arc is included. The test concerns the whole subtree, rather than just each intervening word's immediate head.

This definition is worth reading slowly, because it is easy to confuse projectivity with a simpler condition such as "the head and dependent are adjacent." Adjacency is not required. An arc can span many words and still be projective, as long as all of the words it spans belong to the head's subtree. What projectivity forbids is an arc that reaches over a word that is not under the head's control.

Consider the sentence:

I saw a dog yesterday which was a Yorkshire Terrier.

The relative clause which was a Yorkshire Terrier modifies dog. In UD, the root of the relative clause (Terrier, with which as its nsubj and was as its cop) attaches to dog as acl:relcl. That arc goes from token 4 (dog) to token 10 (Terrier), spanning tokens 5 through 9. Only token 5, yesterday, is outside the subtree rooted at dog: it depends on saw. Tokens 6 through 9 belong to the relative clause headed by Terrier, which is itself a dependent of dog. One outside word is enough to violate the condition. So the arc from dog to Terrier is non-projective.

The example adapts the non-projective sentence in McDonald and Pereira (2006), Figure 2, using I in place of John and supplying UD labels here. It illustrates extraposition rather than a corpus frequency. Its non-projectivity follows from this particular attachment and word order. Moving yesterday outside the span of the relative-clause attachment would remove this particular violation without changing the clause's head-dependent relation.

Non-projectivity can arise when a dependent is separated from its head by material outside that head's subtree. The extraposed relative clause above is one such analysis. Different languages, genres, word orders, and annotation conventions can yield different amounts of non-projectivity, so a rate should always name its treebank release, the included sentences, and whether the denominator is words, arcs, or sentences. The three hand-written analyses in this chapter demonstrate structural possibilities; they do not estimate a language's frequency.

Projectivity restricts the trees that a parser is allowed to produce. A system restricted to projective outputs cannot recover our non-projective analysis exactly, even if its word representations are excellent. It must change at least one attachment. The next chapter studies how decoding algorithms enforce or relax this constraint.

The computational trade-off depends on the scoring model, rather than on a general rule that non-projective parsing is slower. Under an arc-factored score, a tree's score is the sum of its individual arc scores. Projective and unrestricted decoding then become different constrained optimization problems. For a fixed set of candidate trees, interactions among selected arcs change the score's factorization when their combined contribution cannot be reduced to individual arc scores plus a constant shared by all candidates. The effect on decoding depends on the interaction structure. We will keep those algorithms separate from the representation and annotation rules developed here.