Dependency Parsing

Solely as directed binary grammatical relations between words, with arcs from heads to dependents; phrasal constituents and phrase-structure rules play no direct role.

A dependency structure whose arc labels come from a fixed inventory of grammatical relations. A root node marks the head of the entire structure.

“I prefer the morning flight through Denver”

word	head	relation
I	prefer	nsubj
prefer	ROOT	root
the	flight	det
morning	flight	compound
flight	prefer	obj
through	Denver	case
Denver	flight	nmod

Head–dependent relations directly encode information buried in phrase-structure trees, such as predicate–argument relations (the arguments of prefer link straight to it); they are a good proxy for semantic relations. They also handle free word order well.

A phrase-structure grammar needs a separate rule for each position where, say, an adverbial could appear; a dependency grammar needs just one link type for that relation, abstracting away from word order.

A head, the central organizing word, and a dependent, a kind of modifier.

In English, functions like subject and object correlate with position and constituent type, so they are partly redundant with phrase structure; in freer word-order languages the relation labels carry information phrase structure barely provides.

An open community effort to annotate dependencies and other grammatical properties across more than 100 languages with a shared inventory of 37 relations.

Clausal relations, describing syntactic roles with respect to a predicate (often a verb), and modifier relations, describing how words modify their heads.

We nsubj of booked; her iobj; flight obj; the det and first amod of flight; Miami nmod of flight, with to as its case marker.

As a directed graph \(G = (V, A)\): vertices \(V\) (usually the words; possibly punctuation, or stems and affixes) and arcs \(A\) encoding head–dependent relations and their functions.

(1) A single root node with no incoming arcs; (2) every other vertex has exactly one incoming arc; (3) a unique path from the root to every vertex. So each word has one head and the structure is connected.

An arc from head to dependent is projective if the head has a path to every word between them in the sentence; a tree is projective if all its arcs are, i.e. it can be drawn with no crossing arcs.

In “JetBlue canceled our flight this morning which was already late”, the arc from flight to its modifier late must cross the arc linking morning to its head; flexible word order languages have many such cases.

English dependency treebanks converted from phrase-structure treebanks via head rules are always projective (so wrong for non-projective cases), and transition-based parsers can only produce projective trees.

By annotators directly building dependency structures, by hand-correcting parser output, or (for some early treebanks) by deterministically converting constituency treebanks.

A stack on which the parse is built, a buffer of input tokens, a set of relations, and an oracle (a predictor) that chooses the next transition given the configuration. It derives from shift-reduce parsing for programming languages.

Make the current word the head of a previously seen word; make a previously seen word the head of the current word; or postpone the current word for later.

LEFTARC: the top of the stack becomes head of the second word; pop the second. RIGHTARC: the second word becomes head of the top; pop the top. SHIFT: move the next buffer word onto the stack. LEFTARC can’t apply when ROOT is second; both arcs need two stack elements.

Transitions only relate the top two stack elements, and once a word is assigned its head it is removed from the stack and unavailable for further processing.

Initial: stack [ROOT], buffer = all words, no relations. Final: buffer empty and only ROOT on the stack; the relations form the parse.

It is linear in sentence length: one left-to-right pass, each word shifted once and reduced once. But it is greedy: one choice per step, no backtracking, so a wrong decision can’t be undone.

Parameterize the arc transitions by relation, e.g. LEFTARC(nsubj), RIGHTARC(obj), giving one LEFTARC and RIGHTARC per label plus SHIFT; the oracle’s choice becomes harder.

Treebanks give sentences with trees, not configurations, so simulate the parser on each training sentence with a training oracle that consults the reference parse to pick the correct transition at each configuration, recording (configuration, transition) pairs.

Choose LEFTARC if it creates a correct relation in the reference parse; otherwise RIGHTARC if it creates a correct relation and all dependents of the top word have already been attached; otherwise SHIFT.

RIGHTARC pops the dependent off the stack; popping it early (e.g. attaching flight to book before through Houston) would make it unavailable as the head of later words.

Word forms, lemmas, POS tags, heads and relations of the top stack elements and front buffer words, via templates like ⟨s1.w, op⟩, ⟨b1.t, op⟩, ⟨s1.wt, op⟩, and combinations like s1.t ∘ s2.t (e.g. NNS∘VBD); any classifier (logistic regression, SVM) can be used.

Encode the sentence, take the encodings of the top two stack words and the first buffer word, concatenate them, and feed a feedforward network with a softmax over transitions, trained with cross-entropy.

In arc-standard, a word can only be attached to its head after all its dependents are found, so attachments wait long (e.g. book → flight waits for through Houston), and long waits invite errors. Arc-eager attaches words to heads as early as possible.

LEFTARC and RIGHTARC relate the top of the stack and the front of the buffer. RIGHTARC shifts the dependent onto the stack (so it can still take dependents), and a new REDUCE operator pops the stack.

Instead of one greedy choice, apply all valid transitions to each configuration on an agenda, score the new configurations, and keep the best \(k\) (beam width). A configuration’s score is its predecessor’s score plus the transition’s score.

They score entire trees rather than making greedy local decisions, which helps especially with long sentences and distant heads, and they can produce non-projective trees.

That the score of a tree is the sum of the scores of its edges.

Build a fully connected weighted directed graph over the words plus ROOT (edges = all possible head–dependent pairs, weights = scores); the best parse is the maximum spanning tree rooted at ROOT.

Every vertex (and every connected component) of a spanning tree has exactly one incoming edge; and only the relative weights of edges entering a vertex matter, so subtracting a constant from all of them doesn’t change the best tree.

Greedily pick the highest-scoring incoming edge for each vertex; if this forms a tree, done. Otherwise subtract each vertex’s best incoming score from its incoming edges, collapse a cycle into one node, recursively find the MST of the contracted graph, then expand the node, dropping the one cycle edge the chosen entering edge replaces.

\(O(mn)\) for \(m\) edges and \(n\) nodes, so \(O(n^3)\) on a fully connected graph; faster implementations reach \(O(m + n\log n)\).

Forms, lemmas and POS of head and dependent, context features before/after/between them, the relation, its direction and the distance. Weights are learned with inference-based learning and the perceptron rule: parse a training sentence; if wrong, lower the weights of features in the wrong parse not present in the reference.

Encode the sentence; pass each token’s encoding through two feedforward networks to get a head representation and a dependent representation; score edge \(i \to j\) with \(\text{Biaff}(h^{head}_i, h^{dep}_j) = x^\top Uy + W(x \oplus y) + b\), which captures multiplicative interactions.

A softmax over each word’s possible heads gives \(p(i \to j)\) (trained with cross-entropy); maximum spanning tree finds the best tree; then a second classifier of the same form picks the best label for each chosen edge.

It is too pessimistic: most sentences are marked wrong, so it isn’t fine-grained enough to guide development.

Labeled attachment score: % of words with the correct head and relation. Unlabeled attachment score: % with the correct head regardless of label. Label accuracy score: % with the correct label regardless of head.

LAS = 4/6 = 2/3; UAS = 5/6.

With precision (share of system nsubj labels that are correct) and recall (share of gold nsubj relations found), and a confusion matrix of dependency types.

Much older: it goes back to Pāṇini (7th–4th c. BCE) and ancient Greek traditions; modern theories draw on Tesnière (1959). Constituency grammars date only to the 20th century.

Covington (2001) the word-by-word deterministic idea; Yamada & Matsumoto and Kudo & Matsumoto shift-reduce with SVMs; Nivre (2003) the modern transition-based approach; McDonald et al. (2005) graph-based MST parsing; Chen & Manning (2014) neural transition parsing.

The Prague Dependency Treebank (multiple layers of morphological, syntactic and semantic annotation) and Universal Dependencies (nearly 200 treebanks in over 100 languages, evolved from Stanford dependencies and Google universal POS tags); CoNLL shared tasks drove much evaluation.