Constituency and Dependency Parsing › Dependency Parsing

Dependency decoders assemble word-to-word arcs under tree constraints. Transition and graph methods enforce those constraints through different search procedures.

A dependency tree represents syntax as a set of head-dependent relations. For a sentence with tokens (w_1, \ldots, w_n), we add an artificial root node (w_0). A dependency tree is a directed graph with:

• One node for the root and one node for each token.
• Exactly one head for every token.
• Exactly one token whose head is the root.
• No cycles.
• All nodes connected to the root.

Here, each arc carries a relation label. Examples from different treebank conventions include nsubj, dobj, det, amod and obl. The exact label set depends on the treebank. Universal Dependencies provides a cross-lingual inventory of labels and guidelines, but individual treebanks still differ in tokenization and annotation choices. Acyclicity, connectivity to ROOT and one incoming head arc per real token give a rooted arborescence. Requiring exactly one real token to attach directly to ROOT is an additional annotation convention; a general arborescence can have several ROOT children.

A dependency tree is projective when every node's subtree occupies a contiguous interval of token positions. With the artificial ROOT fixed outside the sentence at position zero, this is equivalent to drawing all arcs, including the ROOT arc, without crossings. Two arcs cross when their endpoint intervals interleave. Omitting the artificial ROOT arc can hide a nonprojective configuration, so the drawing convention matters. Projectivity belongs to a tree relative to word order; languages and treebanks differ in how frequently their analyses are nonprojective.

Ordinary projective transition systems cannot produce a nonprojective reference tree. Unrestricted arborescence decoding permits nonprojective trees directly. Czech and German treebanks include nonprojective constructions, so the permitted tree family affects coverage. Both the representation and inference procedure must permit the desired analysis; a SWAP extension is one way to extend a projective transition system.

Transition-based parsing builds a tree incrementally. The parser maintains a configuration with three parts:

• A stack of processed tokens.
• A buffer of unprocessed tokens.
• A set of arcs that have already been created.

The parser starts with the root on the stack and all tokens in the buffer. At each step, it applies a transition. In the arc-standard system, the transitions are:

The stack is ordered from left to right, with the top at the right end. A LEFT-ARC creates a head that is to the right of its dependent. A RIGHT-ARC creates a head that is to the left of its dependent. The asymmetry between the two arc actions is what lets the parser decide, at each step, whether the current pair of stack items should be linked with the top as head or the second item as head.

For "She saw him", a gold transition sequence is:

1. SHIFT "She".
2. SHIFT "saw".
3. LEFT-ARC(nsubj): "saw" is the head, "She" is the dependent.
4. SHIFT "him".
5. RIGHT-ARC(dobj): "saw" is the head, "him" is the dependent.
6. RIGHT-ARC(root): the artificial root is the head, "saw" is the dependent.

In this arc-standard convention, a complete parse of (n) tokens takes (n) SHIFT actions and (n) arc actions, including the final ROOT arc: (2n) transitions. With constant-time stack and buffer operations and fixed-cost action scoring, greedy decoding therefore takes (O(n)) time, excluding sentence encoding. A classifier scores the legal transitions at each configuration, and the parser chooses the highest-scoring action. Training uses an oracle that derives the gold action sequence from a gold tree. The oracle connects the gold tree to the action sequence the parser predicts. An oracle supplies local action targets from tree supervision; other structured training methods can use gold trees without committing to one canonical action sequence.

Greedy arc-standard decoding commits to its chosen action history. An incorrect arc changes the subsequent configuration and cannot be retracted within that history. Beam search keeps several configurations alive and can improve accuracy, but it is still approximate. Error propagation is especially dangerous because the parser's later decisions depend on the configuration it has built, so an early mistake changes the features the classifier sees and can cause further mistakes.

There is also spurious ambiguity: multiple transition sequences can produce the same tree. A static oracle that always follows one gold sequence can teach the parser to prefer an action even when another action would yield the same tree. A dynamic oracle identifies actions that preserve the minimum reachable loss relative to the gold tree. When the gold tree is still reachable, this includes all actions that preserve a gold derivation. After a mistake makes it unreachable, the oracle instead preserves the best achievable remaining outcome. This supports training on off-gold configurations as well as handling multiple correct action sequences.

The ordinary arc-standard and arc-eager systems both produce projective trees. In Nivre's (2009) stack-based nonprojective extension, a SWAP action removes the second-top stack item and returns it to the front of the buffer, subject to an ordering restriction that prevents repeated reversal. This changes the processing order and permits crossing arcs. Such a system can require quadratically many transitions in the worst case; the linear bound for ordinary arc-standard parsing does not carry over automatically.

Neural transition-based parsers use learned representations for scoring configurations. Chen and Manning (2014) used a feed-forward network over configuration features. Dyer et al. (2015) used a stack-LSTM to represent the configuration. Kiperwasser and Goldberg (2016) used BiLSTM features. These architectures change the inputs to action scoring; they do not guarantee that every decision improves. Within an ordinary arc-standard configuration, arc actions are irreversible. Greedy decoding commits to one history, while beam search can retain alternative histories and later select among them.

Graph-based parsing takes a different view. Instead of building a tree step by step, it scores candidate arcs and then finds an admissible tree that maximizes their total score:

[ \hat{y} = \arg\max_{y \in \mathcal{T}(w)} \sum_{(h,d,l) \in y} s(h,d,l) ]

where:

• $y$: a candidate dependency tree, a set of labeled arcs
• $\mathcal{T}(w)$: the set of valid dependency trees for the sentence $w$, each acyclic, connected to the root, and giving every token exactly one head
• $(h, d, l)$: one labeled arc, with $h$ the head token, $d$ the dependent token, and $l$ the relation label
• $s(h, d, l)$: the score assigned to that single arc

The score $s(h,d,l)$ contributes one arc term, while the decoder enforces the tree constraint. Each term may use contextual representations of the entire sentence; additive factorization does not require context-free features. It omits explicit interactions between selected arcs. For the projective and unrestricted arborescence families described below, this factorization permits polynomial-time exact decoding.

Without a projectivity restriction, arc-factored decoding is a maximum spanning arborescence problem. The Chu-Liu/Edmonds algorithm solves the rooted arborescence problem exactly. A standard arborescence decoder may give artificial ROOT several children, however. Enforcing exactly one ROOT attachment requires an additional constraint, for example by considering each possible sentence root while forbidding other ROOT arcs. A naive greedy approach fails because choosing the best incoming arc for each token can create a cycle. Chu-Liu/Edmonds handles cycles by contracting them into a supernode, adjusting arc weights, and recursing. When a cycle is expanded, one arc in the cycle is broken to restore a tree. The weight adjustment is the clever part: it encodes the cost of replacing one arc in the cycle with an arc from outside, so that the recursive call on the contracted graph makes the right global trade-off.

For projective arc-factored trees, Eisner-style dynamic programming gives (O(n^3)) decoding. Its ROOT constraints must match the tree convention, including the one-ROOT-child requirement here. Eisner's algorithm uses incomplete items that include an arc between the two boundary heads and complete items whose span is covered by a subtree headed at one boundary. It combines left and right dependents in a fixed order, which prevents crossing arcs. The result is an exact projective parser for arc-factored scores. These item states control which partial structures can combine while preserving a projective tree. A complete item is complete within its span; its head can still take dependents outside that span during later combinations.

For the arc-factored objectives described here, graph-based decoding is exact within the permitted tree family. The limitation is the factorization: sibling dependencies and grandparent relations are not explicit score factors. Higher-order graph-based models score larger fragments, and sufficiently rich nonprojective factorizations can make exact decoding NP-hard. Second-order models can score pairs of adjacent arcs or head-dependent-grandparent triples. Their tractability depends on the permitted structures and the specific pairs scored.

Two labeling arrangements are useful to distinguish. A pipeline first finds an unlabeled tree and then labels its arcs with a classifier. A joint model scores labeled arcs directly, so the best available label score can affect which head attachment is selected. A label-only second stage cannot repair an already fixed head attachment. For purely arc-factored labeled scores, maximize over the labels for each possible head-dependent pair first, then decode using those maximum arc scores and retain the winning labels. Label selection does not require a different structural search in that special case. Interactions involving labels on multiple arcs require additional modeling and decoding machinery.

Neural graph-based parsers learn token representations and score arcs with a neural network. Dozat and Manning (2017) use biaffine classifiers for arcs and labels. One general biaffine form, used for the illustrative computation below, is:

[ s(h,d) = \mathbf{h}_h^\top \mathbf{U} \mathbf{h}_d

• \mathbf{w}_h^\top \mathbf{h}_h
• \mathbf{w}_d^\top \mathbf{h}_d
• b ]

Here (\mathbf{h}_h\in\mathbb{R}^{d_h}) and (\mathbf{h}_d\in\mathbb{R}^{d_d}) represent the candidate head and dependent. The matrix (\mathbf U) has shape (d_h\times d_d); the weight vectors have the corresponding head or dependent dimension, and (b) is a scalar. The bilinear term combines features from both words, while the two linear terms contribute one-word preferences. The result is an unnormalized score, not a probability.

For labeled parsing, use a label-specific matrix (\mathbf{U}_l) and a label-specific bias:

[ s(h,d,l) = \mathbf{h}_h^\top \mathbf{U}_l \mathbf{h}_d

• \mathbf{w}_{h,l}^\top \mathbf{h}_h
• \mathbf{w}_{d,l}^\top \mathbf{h}_d
• b_l ]

where:

• $\mathbf{h}_h$: the representation of the head token $h$
• $\mathbf{h}_d$: the representation of the dependent token $d$
• $\mathbf{U}_l$: the learned bilinear matrix for label $l$, capturing head-dependent compatibility under that label
• $\mathbf{w}_{h,l}$ and $\mathbf{w}_{d,l}$: learned label-specific weight vectors applied to the head and dependent representations
• $b_l$: the learned scalar bias for label $l$
• $s(h,d,l)$: the resulting score for attaching dependent $d$ to head $h$ with label $l$

Using one parameter set gives one score per candidate arc. Using label-specific parameters gives a score for every candidate arc-label combination. An unlabeled scorer does not itself assign relation labels; a separate label classifier or a joint labeled objective supplies those decisions.

Token representations can come from a BiLSTM, a Transformer, or a pretrained language model. The scorer supplies arc scores to Chu-Liu/Edmonds or Eisner, with constraints matching the intended tree family. Training can use local head-selection cross-entropy, a structured margin, or a structured likelihood computed with the matrix-tree theorem. Contextual scores can use input information absent from the structural rule probabilities of a bare unlexicalized PCFG. Tree validity comes from the decoder and its constraints; it does not establish annotation accuracy.

The matrix-tree theorem connects arc-factored parsing to probabilistic modeling. With positive arc weights, which can be obtained by exponentiating scores, an appropriate reduced Laplacian determinant sums the products of arc weights over directed spanning trees rooted at a designated node. The full Laplacian is singular and is not the matrix whose determinant gives that rooted partition function. When the reduced matrix is nonsingular, arc marginals follow from derivatives of its log determinant and can be computed using its inverse. A standard rooted-arborescence partition can include several children of artificial ROOT; matching the single-ROOT-attachment convention in this chapter requires a compatible constrained construction, such as summing partitions with each possible sole ROOT child in turn. Computing a partition function does not replace maximum-score decoding.

Neural methods are not limited to transition-based or graph-based decoding. A span-based constituency parser can assign category scores to spans and use a CKY-style decoder to select a tree. This retains dynamic programming while changing the scoring model. Stern et al. (2017) use differences of contextual boundary vectors to represent spans; the scorer need not pool every token inside a span. Kitaev and Klein (2018) replace the recurrent sentence encoder with self-attention. The decoder is exact for its specified additive span objective, provided it does not prune candidates.

Sequence-to-sequence parsing takes a different route. It linearizes the tree as a string, such as a bracketed constituency tree or a sequence of dependency decisions, and trains a sequence-to-sequence model to generate that string. The decoder makes successive output-token decisions, for example using beam search. This can reuse a general sequence-generation architecture, but an unconstrained output vocabulary does not enforce balanced brackets, complete token coverage, or dependency-tree constraints. Constrained decoding or post-validation is needed when the output must be a well-formed tree. A high-scoring output string and a valid parse are separate requirements.

Large language models add another option: prompt the model to output a bracketed tree or a dependency list. This permits a parsing experiment without training a new task-specific model, but it establishes no accuracy guarantee for a language or annotation scheme. Prompt choices can affect the result. Report the prompt and requested output encoding when describing an experiment. Studies such as Tian et al. (2024) evaluate prompted constituency parsing and find difficulties with full trees. Keep the supplied syntactic-word sequence fixed, choose and report decoding settings, and validate token coverage and tree constraints before scoring against gold annotations.