Dependency Parsing
Analyzing sentence structure as labeled head-dependent relations between words, using transition-based and graph-based algorithms, increasingly under the cross-lingual Universal Dependencies standard.
Definition
Dependency parsing assigns a sentence a directed graph in which each word is linked to its syntactic head by a labeled grammatical relation.
Scope
Covers dependency syntax representations, transition-based parsing (shift-reduce with an oracle), graph-based parsing (maximum spanning tree), projectivity, and the Universal Dependencies annotation scheme that enables consistent cross-linguistic treebanks. It addresses evaluation by attachment score. Constituency parsing and broader formalisms are covered in sibling topics.
Core questions
- How do transition-based parsers build a dependency tree incrementally?
- How does graph-based parsing find the optimal tree as a maximum spanning tree?
- What is projectivity and why does it complicate parsing?
- How does Universal Dependencies make annotations comparable across languages?
Key concepts
- dependency relation
- head and dependent
- transition-based parsing
- graph-based parsing
- projectivity
- maximum spanning tree
- Universal Dependencies
- attachment score
Key theories
- Transition-based dependency parsing
- Building a dependency tree by a sequence of shift and reduce actions chosen by a learned classifier, achieving linear-time parsing.
- Universal Dependencies
- A cross-linguistically consistent inventory of dependency relations and annotation guidelines that enables treebanks and parsers to be compared and transferred across languages.
History
Dependency grammar traces to Tesnière's mid-20th-century work, but its computational form matured in the 2000s with Nivre's transition-based parsers and McDonald's graph-based parsers. The Universal Dependencies project, launched in the mid-2010s, unified annotation across more than a hundred languages.
Debates
- Transition-based versus graph-based parsing
- Transition-based parsers are fast but can make local errors, while graph-based parsers optimize globally at higher cost; neural methods have narrowed but not erased the trade-off.
Key figures
- Joakim Nivre
- Ryan McDonald
- Marie-Catherine de Marneffe
- Lucien Tesnière
Related topics
Seminal works
- nivre2008
- demarneffe2021
- kubler2009
Frequently asked questions
- What does projectivity mean?
- A dependency tree is projective when its arcs can be drawn above the sentence without crossing. Non-projective structures, common in free-word-order languages, require parsing algorithms that allow crossing dependencies.