What a dependency tree is
Dependency parsing builds a tree where each word points to its grammatical head, labeled with a relation such as subject or object. The main verb is usually the root, and every other word hangs off a head.
Two families of parsers
- Transition based parsers read the sentence left to right and apply actions like shift and arc, building the tree incrementally. They are fast and run in linear time.
- Graph based parsers score every possible head dependent edge and find the highest scoring spanning tree over the whole sentence.
Why it is useful
- It exposes who did what to whom, which helps relation extraction and question answering.
- The labeled relations are language agnostic under the Universal Dependencies standard.
How it is scored
- UAS, unlabeled attachment score, is the fraction of words attached to the correct head.
- LAS, labeled attachment score, also requires the relation label to be correct, so it is always at most UAS.
A key constraint is that a valid dependency tree must be connected and acyclic, with exactly one root.
Key idea
Dependency parsing connects each word to its grammatical head to form an acyclic tree, built either incrementally by a transition parser or globally by a graph parser, and scored with UAS and LAS.