Dependency Parsing

Dependency-Parsing Parsing Syntax Tree Nlp Needs-Review

What it is

Dependency parsing analyzes sentence structure by identifying grammatical relations (dependencies) between words. Output is a directed acyclic graph (DAG) or tree where edges represent relations (nsubj: nominal subject, obj: direct object, etc.). Dependency parsing is fundamental for syntax analysis, semantic understanding, and information extraction.

[illustrate: Sentence with dependency tree showing arcs between words; root node; relation labels on arcs]

How it works

  1. Dependency relations: Define grammatical relations

    • nsubj (nominal subject): “cat” nsubj “sat”
    • obj (object): “sat” obj “mat”
    • nmod (nominal modifier): “mat” nmod “mat”
    • 40+ relation types in Universal Dependencies

  2. Parsing approaches:

    • Transition-based (Arc-eager, Arc-standard): Greedily build tree via shift-reduce actions
    • Graph-based (MST): Find maximum spanning tree maximizing edge scores
    • Neural: BiLSTM encoder + arc classification or transition predictor

  3. Modern approach:

    • Encode sentence with BERT or similar
    • Predict head for each token (which token it depends on)
    • Predict relation type for each dependency

Example

Sentence: "The quick brown fox jumps over the mat"

Dependency tree (simplified):
        jumps (ROOT)
       /  |   \
      fox over mat
     /|    |   |
   The brown    the
      |
    quick

Dependencies:
- jumps: ROOT
- fox: nsubj(jumps)
- brown: amod(fox)
- quick: amod(brown)
- the: det(fox), det(mat)
- over: case(mat)
- mat: nmod(jumps)

Variants and history

Dependency parsing emerged in the 1980s–90s. Transition-based parsing (Nivre, 2003) enabled efficient online algorithms. Neural dependency parsing (Chen & Manning, 2014) replaced hand-crafted features with learned representations. Universal Dependencies (Nivre et al., 2016) standardized annotation across languages. Modern approaches achieve 95%+ UAS (Unlabeled Attachment Score) on English.

When to use it

Use dependency parsing for:

  • Semantic role labeling
  • Coreference resolution (understanding entity roles)
  • Relation extraction from text
  • Question generation and answering
  • Text simplification and paraphrasing
  • Linguistic analysis

Dependency trees are sparse (n-1 edges for n tokens) and interpretable, unlike dense neural representations. Computational cost is moderate (linear in modern algorithms).

See also