Dependency Parsing

A dependency is an asymmetric grammatical relation between two words: a head and a dependent. In "economist wrote report," wrote is the head of the clause; economist is its subject dependent (`nsubj`), report is its object dependent (`obj`). A dependency tree for a sentence is the set of all such head–dependent arcs, plus one designated root word (typically the main verb) that has no head of its own, connected instead to an artificial ROOT node. Each arc carries a label describing the grammatical relation — `nsubj`, `obj`, `det`, `amod`, `advmod`, and so on, drawn from a fixed label inventory such as the Universal Dependencies tagset. Formally, a dependency tree over a sentence $w_1, \dots, w_n$ (with an added root token $w_0$) is a directed graph $T = (V, A)$ where $V = \{w_0, w_1, \dots, w_n\}$ and $A$ is a set of labeled arcs $(h, d, \ell)$ meaning "$w_h$ is the head of $w_d$ with label $\ell$." A well-formed dependency tree satisfies three properties: (1) single head — every word except the root has exactly one incoming arc; (2) connectivity — every word is reachable from the root; (3) acyclicity — no cycles. Together these force $T$ to be a tree rooted at $w_0$ with exactly $n$ arcs for $n$ real words. A tree is projective if every arc's span (the words between head and dependent) forms a contiguous interval with no arcs crossing it when drawn above the sentence — equivalently, if you can draw all arcs as arches above the linear sentence without any two arcs crossing. Most English sentences are projective; free-word-order languages (Czech, Latin, Warlpiral) frequently require non-projective trees, which matters for which parsing algorithm applies. This differs fundamentally from constituency-based Syntactic Parsing, which groups words into nested phrases (NP, VP, PP) labeled with nonterminal categories. Dependency structure is lexicalized by construction — every arc is between two actual words, never an abstract phrase — which makes it a more direct scaffold for semantic role labeling, relation extraction, and translation. The two representations are inter-convertible under mild assumptions (a constituency tree with head-marking rules yields a dependency tree, the "head-percolation" construction), but dependency trees are typically far more compact: $n$ arcs versus $O(n)$ nonterminal nodes plus brackets.

The dominant efficient algorithm family is transition-based parsing. The parser maintains an explicit state and repeatedly applies one of a small set of transitions (actions), each predicted by a classifier, until the sentence is fully parsed. The classic system is arc-standard, introduced by Nivre (2003/2004).

State. A configuration is a triple $c = (\sigma, \beta, A)$:

• $\sigma$ — a stack of partially processed words (top on the right),
• $\beta$ — a buffer of remaining input words (front on the left), initialized to the whole sentence,
• $A$ — the set of dependency arcs built so far.

The initial configuration is $c_0 = ([w_0], [w_1, \dots, w_n], \emptyset)$ — the stack holds only ROOT, the buffer holds every word. A configuration is terminal when the buffer is empty and the stack contains only ROOT.

Transitions. Let $\sigma = \sigma' | s_1 | s_0$ (so $s_0$ is the stack top, $s_1$ below it) and $\beta = b_0 | \beta'$ (so $b_0$ is the buffer front).

LEFT-ARC makes $s_0$ the head of $s_1$ (dependent popped); RIGHT-ARC makes $s_1$ the head of $s_0$ (dependent popped, but $s_0$ was on top so it is removed and $s_1$ remains available for further attachments to its right — this is the step that must be taken carefully in implementation, see pseudocode below). Each transition is deterministic given a chosen action, so parsing is reduced to: at each configuration, which of the (up to $2L+1$) actions — SHIFT, LEFT-ARC with one of $L$ labels, RIGHT-ARC with one of $L$ labels — should fire? A trained classifier answers this using features of the current configuration (traditionally: word/POS identity of $s_0, s_1, b_0$, their children, etc.; in neural parsers, dense embeddings of these same positions). ``` function ARC-STANDARD-PARSE(words w[1..n], classifier CLF): stack ← [ROOT] buffer ← [w[1], w[2], ..., w[n]] arcs ← ∅ while not (buffer is empty and len(stack) == 1): features ← EXTRACT-FEATURES(stack, buffer, arcs) action ← CLF.predict(features) # SHIFT, LEFT-ARC(l), RIGHT-ARC(l)

# Guard against illegal predictions (never remove ROOT, never

# act on an empty stack/buffer) — fall back to a legal action. if action == SHIFT and buffer is empty: action ← best legal LEFT-ARC or RIGHT-ARC if action in {LEFT-ARC, RIGHT-ARC} and len(stack) < 2: action ← SHIFT if action == LEFT-ARC and stack[-2] == ROOT: action ← RIGHT-ARC or SHIFT # ROOT may never be a dependent if action == SHIFT: stack.push(buffer.pop_front()) else if action == LEFT-ARC(l): dependent ← stack.pop_second_from_top() # s1 head ← stack.top() # s0 stays arcs.add( (head, dependent, l) ) else if action == RIGHT-ARC(l): dependent ← stack.pop() # s0 removed head ← stack.top() # s1 stays arcs.add( (head, dependent, l) ) return arcs ```

Why exactly $2n$ steps. Every SHIFT consumes exactly one buffer word (there are $n$ words to consume, hence exactly $n$ SHIFTs). Every LEFT-ARC or RIGHT-ARC removes exactly one word from the stack permanently and creates exactly one arc; since every word except ROOT must receive exactly one arc pointing to it (single-head property), there are exactly $n$ arc-transitions. Total transitions: $2n$, giving strictly linear-time parsing in the number of transitions, and — since feature extraction and classification are $O(1)$ per step (bounded window around stack/buffer top) — linear-time parsing overall. The figure below shows the configuration graph as a state machine over (stack, buffer) snapshots for a five-word sentence, and separately the resulting dependency tree.

Time complexity. As derived above, arc-standard parsing performs exactly $2n$ transitions for a sentence of $n$ words (n SHIFTs + n arc-transitions), and each transition requires $O(1)$ feature extraction (a small fixed window of stack/buffer positions) plus one classifier call. If the classifier itself runs in $O(1)$ (a fixed-size feed-forward network or linear model over a bounded feature vector), total parsing time is $\boxed{O(n)}$ — genuinely linear in sentence length, in contrast to $O(n^3)$ for CKY-style constituency parsing with a context-free grammar in Chomsky Normal Form. This is the central efficiency argument for transition-based parsing and is why it scales to web-scale corpora.

Space complexity is $O(n)$: the stack and buffer together hold at most $n$ words, and the arc set has exactly $n$ arcs.

Correctness (that the transition system reaches exactly the well-formed projective trees). The proof has two directions. Soundness — every terminal configuration's arc set $A$ is a well-formed, projective dependency tree. By induction on the number of transitions: initially $A = \emptyset$ trivially satisfies "each processed word has at most one head." Each LEFT-ARC/RIGHT-ARC adds exactly one arc into a word that is being permanently removed from the stack, and the preconditions guarantee that word had received no prior arc as a dependent (once popped, a word can never reappear on the stack, so it cannot receive a second head). Hence the single-head invariant is maintained throughout. Acyclicity holds because arcs only ever point from a stack element to another stack element created before it was pushed, and the stack is popped monotonically — no back-edges can form a cycle. Connectivity to ROOT follows because the terminal condition requires the stack to contain only ROOT, meaning every other word was popped via some arc-transition, i.e., attached into the tree. Completeness — every projective dependency tree is reachable by some transition sequence. This is shown constructively: given a target projective tree, process the sentence left to right, shifting words onto the stack, and whenever the top two stack elements $s_1, s_0$ have a direct head-dependent relationship in the target tree and $s_1$ (or $s_0$) has already received all of its other dependents from the target tree, fire the corresponding arc transition. Because the tree is projective, dependents always finish attaching to a head before an intervening word finishes attaching to something to its right — this is precisely the definition of projectivity, so the "stack contains an attachable pair" situation is guaranteed to arise at the right moments, and the greedy left-to-right procedure never gets stuck. This is why arc-standard handles projective trees only — a non-projective arc would require attaching a word whose dependents are not yet all resolved because a crossing arc still needs to be built, which the stack discipline cannot express. Non-projective dependency structures require either pseudo-projective transformations (encode crossing as extra labels, then re-decode) or a different transition system (arc-eager with a SWAP transition, or graph-based parsing, see below).

Training and the oracle. The classifier is trained via a static oracle: given a gold tree, generate the unique canonical sequence of transitions that produces it (using the completeness construction above), and train a multiclass classifier to predict, from each intermediate gold configuration, the correct next action. The key subtlety, and a genuine correctness concern, is exposure bias: at test time the parser conditions on its own possibly-wrong past decisions, configurations the static oracle never showed it during training. Dynamic oracles address this by defining, for any reachable configuration (including ones resulting from mistakes), the set of transitions that minimizes the number of gold arcs that are now unreachable — training on a mixture of gold and self-generated (rolled-in) configurations closes this gap and is the technique underlying strong transition-based parsers such as those of Goldberg & Nivre (2012) and the neural parser of Chen & Manning (2014).

Graph-based alternative and its complexity. Instead of greedy local decisions, graph-based parsing (McDonald et al., 2005) scores every candidate arc $(h,d)$ with a learned scoring function $s(h,d)$, sums arc scores over a candidate tree, and finds

where $\mathcal{T}(w)$ is the set of valid spanning trees over the sentence. For unlabeled non-projective trees this is exactly the maximum spanning tree problem on a directed graph, solvable optimally by the Chu–Liu/Edmonds algorithm in $O(n^2)$ time (or $O(n \log n + m)$ with efficient priority queues), because any spanning arborescence maximizing arc-sum can be found by greedily picking, per node, its best incoming arc, contracting cycles, and recursing — a correct and efficient combinatorial optimization with no need for greedy local classification. For projective trees, dynamic programming (Eisner's algorithm) finds the optimum in $O(n^3)$ time by building "half-tree" spans bottom-up, analogous to CKY. Graph-based parsing is globally optimal given its scores (no exposure-bias issue) but pays a higher time cost and needs arc-factored (or higher-order, e.g. sibling/grandparent) scoring functions, which trade expressiveness for tractability.

Honest tradeoffs. Transition-based parsers are fast ($O(n)$) and support rich, non-local features of parsing history, but are greedy — an early mistake can cascade (mitigated by beam search, giving $O(bn)$ for beam width $b$, or dynamic oracles). Graph-based parsers are globally optimal for their score decomposition and handle non-projectivity cleanly (MST) but scale worse ($O(n^2)$–$O(n^3)$) and their arc-factored scoring can miss genuinely non-local syntactic phenomena unless higher-order factors are added, which increases complexity further (third-order graph parsing can reach $O(n^4)$).

Sentence: "Economists predicted a recession ." Gold dependency tree (Universal Dependencies style):

Trace of the arc-standard parser (stack shown left→top-of-stack rightmost; buffer shown front→back):

Sanity check against the completeness argument: at step 2, LEFT-ARC fires because Economists (the current $s_1$) has no further dependents of its own in the gold tree and its head predicted is on the stack — exactly the condition the completeness proof requires. Ten transitions for five real words confirms the $2n$ count. Note step 6's RIGHT-ARC pops recession but leaves predicted on the stack, available to later attach to punctuation (step 8) and finally to ROOT (step 9) — this is exactly why RIGHT-ARC must retain $s_1$ rather than discard it, the detail flagged in the pseudocode's comment.

Dependency grammar's linguistic roots trace to Lucien Tesnière, whose 1959 Éléments de syntaxe structurale first formalized syntax as a network of head-dependent "connections" (stemmas) rather than nested phrase brackets — a genuinely different foundational choice from the Chomskyan constituency tradition dominant in American linguistics of the era. Computational operationalization came decades later, driven by the need for fast, robust parsers for real text (not just clean grammatical sentences), reaching maturity with Joakim Nivre's transition-based framework, which unified many prior shift-reduce parsing ideas into the arc-standard/arc-eager systems described above and made them trainable with off-the-shelf classifiers.

Dependency parses feed relation extraction and information extraction pipelines, where the shortest dependency path between two entity mentions is a strong feature for classifying their relation — a technique still used inside large-scale knowledge-base population systems. Semantic role labeling systems historically built directly on dependency arcs to identify predicate-argument structure ("who did what to whom"), a precursor to reasoning about Word Senses and Lexical Semantics since the same surface word can take different argument structures under different senses. Machine translation systems, especially pre-neural statistical MT, used dependency structure to model reordering between languages with different canonical word orders (e.g., SOV versus SVO). Grammar-checking and writing-assistance tools use dependency arcs to detect subject-verb agreement errors and dangling modifiers. Search engines and question-answering systems parse queries to identify the head noun and its modifiers for better query understanding. And the Universal Dependencies treebanks — annotated consistently across more than 100 languages — remain a standard benchmark for evaluating multilingual Syntactic Parsing models and a common source of structured supervision even for neural architectures that otherwise learn syntax only implicitly.

Ask the tutor: Can you walk through how the completeness proof breaks down for a concrete non-projective sentence?