Sequence Labelling and Structure
Dependency parsing
Dependency parsing draws a tree connecting every word to the word it grammatically depends on, and it is the structure relation extraction, coreference resolution and grammar checkers are all quietly built on.
- 10 min read
- 3 reading levels
- Published
Read these first
On this page 5
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
Dependency parsing draws a tree connecting every word in a sentence to the word it grammatically depends on.
Think about an org chart at a company. Every employee reports to exactly one manager, except the CEO at the top. The CEO reports to no one. Follow the reporting lines and you can see the whole structure of who answers to whom.
A dependency parse builds the same kind of chart, but for a sentence. Every word "reports to" one other word — the word it modifies or depends on grammatically. The main verb is the exception. It sits at the top, reporting to nothing.
Why it exists
Part-of-speech tagging, covered earlier in this section, tells you each word's job — noun, verb, adjective. It does not tell you how the words connect. "The chai vendor near the station sells the best filter coffee" has a lot of nouns and one main verb. Which noun is doing the selling? Which noun is being sold?
Word order alone is not enough to answer that reliably, especially once sentences get longer. Dependency parsing gives an explicit answer. It draws a labelled link from every word to the word it depends on. "Who is doing what to what" becomes something you can read directly off the tree, not something you have to guess from position.
How it works
Every word gets exactly one incoming link, labelled with the kind of relationship it has to its head word. The sentence's main verb is the exception — it is the root of the tree.
Sentence: The chai vendor near the station sells the best filter coffee
vendor --nsubj--> sells (vendor is the subject of "sells")
coffee --dobj---> sells (coffee is the direct object of "sells")
chai --compound-> vendor ("chai vendor" is a compound noun)
near --prep----> vendor ("near the station" describes the vendor)
station--pobj----> near (station is the object of "near")
sells (ROOT)
/ \
vendor coffee
/ \ \
chai near filter
\
stationRead the tree and the sentence's real structure is visible at a glance. The vendor is doing the selling. Coffee is what gets sold. "Near the station" is extra information about the vendor, not about the coffee.
Where you have already seen it
- Grammar checkers. Dependency structure catches subject-verb agreement errors that simple word-order rules would miss in a longer sentence.
- Voice assistants, parsing "set an alarm for 7 AM tomorrow, not today" to correctly attach "not today" to the right part of the request.
- Every relation extraction system. Finding who-did-what-to-whom, covered in the previous lesson, is built directly on top of exactly this tree structure.
Remember this
- A dependency parse connects every word to the one word it grammatically depends on, forming a tree rooted at the main verb.
- Each connection is labelled with the kind of relationship it represents — subject, object, modifier, and others.
- This tree is the structural backbone that relation extraction, coreference resolution, and grammar checking are all built on top of.
What to learn next
- Relation extraction — the task that reads facts directly off this tree.
- Part-of-speech tagging — the per-word labels a dependency parser uses as input features.
- Attention — a mechanism that lets modern transformers learn similar word-to-word relationships without an explicit parse tree.
Developer — Code and libraries.
spaCy's parser produces a full dependency tree for any sentence in one call, with no extra setup beyond the pipeline you have already used in this section.
Setup
pip install spacy
python -m spacy download en_core_web_smMinimal runnable code
import spacy
nlp = spacy.load("en_core_web_sm")
doc = nlp("The chai vendor near the station sells the best filter coffee.")
for token in doc:
print(f"{token.text:10} --{token.dep_:8}--> {token.head.text:10} ({spacy.explain(token.dep_)})")The --det --> vendor (determiner) chai --compound--> vendor (compound) vendor --nsubj --> sells (nominal subject) near --prep --> vendor (prepositional modifier) the --det --> station (determiner) station --pobj --> near (object of preposition) sells --ROOT --> sells (root) the --det --> coffee (determiner) best --amod --> coffee (adjectival modifier) filter --compound--> coffee (compound) coffee --dobj --> sells (direct object) . --punct --> sells (punctuation)
Line by line
token.dep_ is the dependency label — the type of relationship, such as nsubj for a nominal subject or dobj for a direct object.
token.head is the word this token depends on. The main verb's own head is itself, and its dep_ reads ROOT, marking the top of the tree — notice "sells" points to itself above.
Chains of dependencies build up phrases. "station" depends on "near" (pobj), and "near" depends on "vendor" (prep), so following the chain from "station" up to "vendor" recovers the full phrase "vendor near the station" without it ever being written as one explicit unit anywhere.
A genuinely hard case: attachment ambiguity
import spacy
nlp = spacy.load("en_core_web_sm")
for sent in ["I saw the man with the telescope.", "I saw the mountain with the telescope."]:
doc = nlp(sent)
for token in doc:
if token.text == "with":
print(f"{sent!r:42} -> 'with' attaches to {token.head.text!r}")'I saw the man with the telescope.' -> 'with' attaches to 'man' 'I saw the mountain with the telescope.' -> 'with' attaches to 'saw'
Same sentence structure, one word changed, and the parser attaches "with the telescope" to a different word each time — to "man" (the man has the telescope) in the first, to "saw" (I used the telescope to see) in the second. This is prepositional-phrase attachment ambiguity, one of the oldest hard problems in parsing, and the parser is using learned real-world plausibility — mountains do not typically carry telescopes — to resolve it, not a fixed grammar rule.
Common mistakes
Confusing token.head with token.pos_. head answers "what does this word depend on", a structural question. pos_ answers "what part of speech is this word", a categorical one. They answer completely different questions and are easy to mix up when reading code quickly.
Assuming the parse tree is always right. As the attachment example shows, this is a genuinely hard problem even for a trained statistical parser, and it makes mistakes — particularly on long, ambiguous, or unusual sentences. Do not build a pipeline that treats every parse as ground truth without spot-checking.
Forgetting punctuation and function words get dependency labels too. Every token has a dep_, including "the" (det) and the final period (punct). Filtering these out is often useful for downstream tasks, but do it deliberately, not by accident.
Walking the tree recursively without a base case. token.head on the ROOT token points to itself. Code that walks up the tree looking for "the top" without checking for this will loop forever.
Try it yourself
Print list(token.children) for the word "sells" in the main example. Compare it against what token.head gives you for "vendor" and "coffee" — children and head are inverses of each other, walking the tree in opposite directions.
What to learn next
- Relation extraction — reading structured facts directly off this tree.
- Nested and overlapping entities — biaffine span scoring, used there, borrows directly from parsing techniques.
- Attention — how transformers learn similar word relationships without an explicit tree.
Researcher — Mathematics and papers.
Two formulations
Constituency parsing builds a tree of nested phrases (noun phrases, verb phrases), following context-free grammar rules — the tradition Chomsky's formal grammar work grew from, and the representation the original Penn Treebank was annotated with.
Dependency parsing, covered in this lesson, instead builds a tree of direct word-to-word relations, with no intermediate phrase nodes. Dependency trees have become the dominant representation in applied NLP over the last fifteen years, largely because they map more directly onto tasks like relation extraction that care about word-to-word relationships, not phrase boundaries, and because the Universal Dependencies project (Nivre et al., 2016) standardised a cross-lingual dependency annotation scheme that constituency grammar, built around English-specific phrase structure rules, does not translate as cleanly.
Parsing algorithms
Transition-based parsing (Nivre, 2003) reads the sentence left to right, maintaining a stack and a buffer, and at each step chooses one of a small set of actions (shift, left-arc, right-arc) via a learned classifier. Parsing is O(n) in sentence length — one action per token, roughly — making it the fastest practical approach, and the one spaCy's default parser uses.
Graph-based parsing (McDonald et al., 2005) scores every possible edge (head, dependent) independently, then finds the highest-scoring tree over the full graph using the Chu-Liu-Edmonds maximum spanning tree algorithm, O(n^2) for scoring all edges plus O(n^2) for the spanning-tree search. Slower than transition-based parsing, but not restricted to decisions a left-to-right stack-based process can make, so it handles certain long-distance and non-projective dependencies more naturally.
Biaffine parsing (Dozat & Manning, 2017) is the current dominant graph-based approach: a BiLSTM or transformer encodes each token, then a biaffine transformation scores every (head, dependent) pair:
score(i, j) = h_i^T · U · h_j + w^T · h_ih_i,h_jare the encoded representations of tokensiandj.Uis a learned bilinear weight matrix,wa learned linear weight vector.- The full
O(n^2)score matrix is computed in one batched operation, then Chu-Liu-Edmonds recovers the best tree.
This same biaffine scoring pattern reappears directly in Nested and overlapping entities, reframing NER as scoring (start, end) span pairs the same way biaffine parsing scores (head, dependent) pairs.
Projectivity
A dependency tree is projective if it can be drawn with no crossing edges when words are laid out in linear sentence order. Free word-order languages — Hindi, Czech, Turkish — produce non-projective trees far more often than English does, because grammatical relationships in those languages are marked by case morphology rather than strict word position, freeing word order to move for emphasis or discourse reasons. Transition-based parsers need explicit extensions (a swap action, or pseudo-projective transformations at training time) to handle non-projective trees at all, while graph-based parsers handle them natively, since maximum spanning tree search has no notion of linear order to violate.
Key references
- Nivre, J. (2003). An Efficient Algorithm for Projective Dependency Parsing. IWPT.
- McDonald, R., Pereira, F., Ribarov, K. & Hajič, J. (2005). Non-projective Dependency Parsing using Spanning Tree Algorithms. HLT/EMNLP.
- Nivre, J. et al. (2016). Universal Dependencies v1: A Multilingual Treebank Collection. LREC.
- Dozat, T. & Manning, C. (2017). Deep Biaffine Attention for Neural Dependency Parsing. arXiv:1611.01734
Current state and open problems
Biaffine and transformer-encoded parsers now exceed 96% unlabelled attachment score on English benchmarks (Penn Treebank), a figure close to inter-annotator agreement, making dependency parsing for high-resource languages a largely solved problem in the same sense as part-of-speech tagging. Attachment ambiguity of the kind shown in the developer block — genuine cases where a sentence supports more than one reasonable structural reading — remains an open linguistic problem, not a modelling gap: some sentences are structurally ambiguous even for a human reader without more context, and no parser can be expected to resolve what the sentence itself does not determine. Parsing quality for low-resource and morphologically rich languages continues to lag well behind English, gated by the smaller Universal Dependencies treebanks available for training in those languages.
What to learn next
- Relation extraction — the task most directly built on parse output.
- Nested and overlapping entities — biaffine scoring applied to entity spans instead of dependency edges.
- Attention — the mechanism that lets transformers implicitly learn word relationships without a supervised parse tree.