Dependency Parsing
Introduction
Dependency parsing analyzes the grammatical structure of a sentence by establishing relationships between "head" words and words which modify those heads. It represents the sentence as a directed graph where words are nodes and grammatical relationships are edges.
Understanding Dependencies
What is a Dependency?
A dependency is a directed relationship between two words:
- Head: The governing word
- Dependent: The word that modifies or relates to the head
- Relation: The type of grammatical relationship
cat → sat (nsubj)
"cat" is the subject of "sat"
Why Dependency Parsing?
- • Captures grammatical relationships explicitly
- • Works well across different languages
- • Useful for information extraction
- • Helps in understanding sentence meaning
- • Foundation for many NLP tasks
Interactive Dependency Parser
Dependency Relations
Root of the sentence
Subject of the verb
Direct object of the verb
Indirect object of the verb
Determiner of a noun
Parse Details
| Token | POS | Head | Relation |
|---|---|---|---|
| The | DET | cat | det |
| cat | NOUN | sat | nsubj |
| sat | VERB | ROOT | root |
| on | ADP | mat | case |
| the | DET | mat | det |
| mat | NOUN | sat | obl |
Parsing Algorithms
Transition-Based Parsing
Builds the parse tree incrementally using a sequence of actions.
Graph-Based Parsing
Finds the optimal parse tree by scoring all possible trees.
Algorithm Steps:
- Score all possible dependency edges
- Find maximum spanning tree
- Ensure single root and no cycles
- Return highest-scoring valid tree
Advantages:
- Global optimization
- Can use rich features
- Better for non-projective trees
Applications of Dependency Parsing
Information Extraction
Extract relationships and facts from text.
"John works at Google"
→ PERSON works-at ORG
Question Answering
Understand question structure and extract answers.
"Who wrote Hamlet?"
→ Query: author(Hamlet)
Machine Translation
Preserve grammatical structure across languages.
EN: "I saw him"
→ ES: "Lo vi" (different order)
Modern Approaches
Neural Dependency Parsing
Transition-Based Neural Parser
- • Uses neural networks to predict actions
- • Fast and efficient
- • Examples: Stack-LSTM, Chen & Manning (2014)
Graph-Based Neural Parser
- • Deep biaffine attention
- • State-of-the-art accuracy
- • Examples: Dozat & Manning (2017)
Pre-trained Models
Modern parsers leverage pre-trained language models for better performance.
spaCy
Fast, production-ready parsers
Stanford Parser
High-accuracy research parser
AllenNLP
State-of-the-art neural parsers
Key Takeaways
- Dependency parsing reveals grammatical structure through head-dependent relationships
- Two main approaches: transition-based (fast) and graph-based (accurate)
- Essential for many NLP tasks like information extraction and question answering
- Modern neural parsers achieve near-human accuracy
- Pre-trained models make dependency parsing accessible and practical
- Universal Dependencies provides consistent annotation across languages