🌳 Dependency parsing
Dependency parsing is the task of recovering a sentence's syntactic structure as directed, labelled links between its words. Each word is attached to exactly one governing word, its head, or to an artificial root, and the links contain no cycles, so that together they form a tree.
What it is
A dependency parser takes a tokenised sentence and returns, for every word, two things: the index of its head and a relation label naming the grammatical function. Take the sentence "She ate the cake with a fork." A typical analysis looks like this:
- "ate" attaches to the root.
- "She" depends on "ate" as subject (nsubj), and "cake" depends on "ate" as object (obj).
- "the" depends on "cake" as determiner (det).
- "fork" depends on "ate" as an oblique modifier (obl).
- "with" depends on "fork" as a case marker (case), and "a" depends on "fork" (det).
- "." depends on "ate" as punctuation (punct).
Because every word has exactly one head and there are no cycles, the result is a rooted tree over the words. This single-head constraint is built into the ten-column CoNLL-X exchange format, in which each token line carries a HEAD and a DEPREL field (Buchholz & Marsi 2006).
A tree is projective if it can be drawn above the sentence without crossing arcs. Equivalently, every head together with its descendants covers a contiguous stretch of words. Free word order and constructions such as extraposition can produce non-projective trees. In the Prague Dependency Treebank and similar resources, only 1–2% of arcs are non-projective, yet 15–25% of sentences contain at least one (Nivre & Nilsson 2005).
Parsers are evaluated per token:
- Unlabelled attachment score (UAS) is the share of tokens assigned the correct head.
- Labelled attachment score (LAS) is the share of tokens whose head and relation label are both right.
The key idea
Most data-driven parsers belong to one of two families.
Graph-based parsers score candidate arcs and then search for the highest-scoring tree. Transition-based parsers build the tree incrementally with a sequence of actions chosen by a classifier. The graph-based (arc-factored) objective is:
ŷ = argmax_{y ∈ T(x)} Σ_{(h, d, ℓ) ∈ y} s(h, d, ℓ)
In this formula:
- x is the input sentence, and T(x) is the set of all well-formed dependency trees over its words.
- y is one candidate tree, viewed as a set of arcs. Each arc is a triple of head h, dependent d and label ℓ.
- s is a learned scoring function, and ŷ is the predicted tree.
With arc-factored scores, non-projective decoding reduces to a maximum spanning tree problem (McDonald et al. 2005). Projective decoding uses Eisner's dynamic programming, which can be extended to richer "higher-order" factors that include siblings and grandchildren, at O(n⁴L) time for n words and L labels (Carreras 2007).
A transition-based parser keeps a configuration made of a stack, a buffer of unread words and a set of arcs built so far. In the arc-eager system the actions are Shift, Reduce, Left-Arc and Right-Arc. This yields a deterministic parser that runs in linear time and always outputs a projective, acyclic graph. When a sentence cannot be fully connected, the parser returns a set of well-formed fragments instead of a single tree (Nivre 2003). Adding a Swap action, which returns a stack word to the buffer, makes the system complete for non-projective trees. The worst case is quadratic, but observed run time stays close to linear (Nivre 2009).
| Graph-based | Transition-based | |
|---|---|---|
| Search | exact or near-exhaustive over trees | greedy or beam over actions |
| Training | global | typically local, per decision |
| Features | limited to a few arcs | full history of the derivation |
| Typical weakness | less accurate on short, frequent relations such as subjects and objects | error propagation on long arcs and near the root |
The contrasts in the table come from a side-by-side error analysis (McDonald & Nivre 2007).
History and founding papers
Dependency grammar as a linguistic theory goes back to Tesnière (1959), with later formal development by Mel'čuk (1988). Statistical dependency parsing took shape in the mid-1990s with Eisner's probabilistic models (Eisner 1996). In parallel, rule-based work showed that non-projective, labelled analyses of English could be produced efficiently with about 2,500 hand-written constraint rules (Tapanainen & Jarvinen 1997).
Nivre's deterministic algorithm reached an attachment score of about 89% on a small Swedish sample using a 126-rule grammar (Nivre 2003). His follow-up work showed that, within a shift-reduce framework without nonterminals, strict incrementality cannot be achieved in general. It also argued that arc-eager processing is the best available compromise (Nivre 2004). MaltParser then packaged the transition approach as a parser-generator that is trained from a treebank rather than a grammar (Nivre et al. 2006). On the graph-based side, McDonald and colleagues combined spanning-tree decoding with online large-margin training (McDonald et al. 2005) and approximate higher-order non-projective search (McDonald & Pereira 2006).
Non-projectivity was also handled indirectly. Pseudo-projective parsing projectivises training trees, encodes the lifts in the arc labels and undoes them after parsing. On Czech this raised performance from 78.5 to 80.0 UAS (Nivre & Nilsson 2005).
Shared tasks made multilingual comparison possible. CoNLL-X in 2006 converted treebanks for 13 languages into one format and adopted LAS, excluding punctuation, as its official metric. Nineteen groups took part. Individual system scores ranged from a low of 37.8% LAS on Turkish to a high of 91.7% on Japanese (Buchholz & Marsi 2006). CoNLL 2007 covered ten languages, attracted 23 systems in its multilingual track, counted punctuation in scoring and added a domain-adaptation track (Nivre et al. 2007).
At CoNLL-X, MSTParser and MaltParser were almost tied in overall LAS over the 13 pooled test sets, at 80.83 versus 80.75. Yet an oracle that built the best tree from the union of their arcs would reach 86.9% LAS on the same data (McDonald & Nivre 2007). Feeding one parser's output into the other as features exploited this complementarity (Nivre & McDonald 2008).
Later feature-based work improved both accuracy and efficiency:
- Brown-cluster features lifted second-order English UAS from 92.02% to 93.16% (Koo et al. 2008).
- Hash-kernel training sped parsing up and reached an average LAS of 86.33 across the CoNLL 2009 languages (Bohnet 2010).
- Joint models predicted part-of-speech tags and non-projective labelled trees together, avoiding pipeline errors (Bohnet & Nivre 2012).
The neural turn began when Chen and Manning replaced millions of sparse features with dense embeddings and a cube-activated hidden layer. Their parser reached 92.2% UAS on the English Penn Treebank at over 1,000 sentences per second (Chen & Manning 2014). Stack LSTMs then encoded the entire parser state and scored 93.1 UAS and 90.9 LAS on English Stanford Dependencies (Dyer et al. 2015).
How it is used today
Current parsers are mostly neural. BiLSTM feature extractors made simple parsers competitive (Kiperwasser & Goldberg 2016). The deep biaffine parser scores every head–dependent pair and decodes with a spanning-tree algorithm. It reached 95.7% UAS and 94.1% LAS on PTB with Stanford Dependencies 3.3.0 (Dozat & Manning 2016). It became a standard baseline and was the basis of a graph-based system for the CoNLL 2017 task of parsing raw text into Universal Dependencies (Dozat et al. 2017).
Several refinements address specific weaknesses. Character-level word representations help morphologically rich languages such as Turkish and Hungarian (Ballesteros et al. 2015). Embeddings can be tailored to syntactic context (Bansal et al. 2014). Non-monotonic transitions let greedy parsers repair earlier errors. This reached 91.85 UAS on OntoNotes converted to dependencies with ClearNLP 3.1, using the CoNLL 2012 train/dev/test split (Honnibal & Johnson 2015).
For languages with no treebank, delexicalised parsers trained on other languages can be transferred directly, and multi-source training reduces error further (McDonald et al. 2011).
Dependency structures and parsing machinery also support other tasks. In opinion relation extraction, a tree kernel over phrase-level dependency trees outperformed its word-level counterpart by 4.8% on average across five product domains (Wu et al. 2009). The biaffine scorer, applied to start–end token pairs, reported state-of-the-art named entity recognition results (2020) for both nested and flat entities, including 86.7 F1 on ACE 2004 (Yu et al. 2020).
Open questions
Several problems remain unresolved:
- Non-projectivity. Exact non-projective inference is often NP-hard for models richer than arc-factored ones (Nivre 2009), so higher-order non-projective parsers rely on approximate search (McDonald & Pereira 2006).
- Error propagation in greedy transition parsers. This motivates non-monotonic actions that repair earlier decisions. These are trained with a dynamic oracle on configurations the parser itself produces (Honnibal & Johnson 2015).
- The labelled-accuracy gap. On PTB with Stanford Dependencies 3.3.0, the biaffine parser's 95.7 UAS and 94.1 LAS sat just below Kuncoro et al. (2016), at 95.8 UAS and 94.6 LAS, so the gap lies mainly in labels. Suggested explanations include tagger errors and weak modelling of phrase composition (Dozat & Manning 2016).
- Domain shift. At CoNLL 2007 the best LAS on chemical abstracts was 81.06, by Sagae and Tsujii. The same team scored 89.01 on the in-domain English test of the multilingual track, whose training data came from the Wall Street Journal. The two figures come from different test corpora (Nivre et al. 2007).
- Cross-language variation. The wide spread of scores at CoNLL-X raises the question of what about a language, its treebank or the annotation scheme makes parsing hard (Buchholz & Marsi 2006).
- Comparability of results. Scoring conventions such as whether punctuation is counted differ between benchmarks (Nivre et al. 2007), which complicates comparison across papers.
Key papers
Related concepts
- Universal Dependencies — Universal Dependencies is a framework and an open collection of treebanks that annotates the grammar of many languages with one shared…
- Context-free grammar — A context-free grammar is a formal system of rewriting rules in which each rule replaces a single nonterminal symbol with a string of…
- Part-of-speech tagging — Part-of-speech tagging is the task of assigning each token in a text a grammatical category, such as noun, verb, adjective or determiner…
- Semantic role labeling — Semantic role labeling is the task of finding, for each predicate in a sentence, the phrases that act as its participants and labeling each…
More papers
Topics: 🌳 Dependency parsing · 🌐 Universal Dependencies · 🗂️ Treebanks
Shelves: 🗣️ Linguistics & languages · 💬 Natural language processing
This page in Markdown → https://md.research.elamur.ai/free/en/concepts/dependency-parsing/