／var／logmarcus chiu

Dependency Parsing

Created on · Last Modified on

Dependency Parsing
  • is the task of analyzing the grammatical dependency structure of a sentence and establishing the relationships between “head” words and the words which modify those heads

Dependency Parsing - Grammar

Dependency Parsing - Methods

Method

Method Description

Algorithms

Translating from Constituency Structure

see: Translating From Constituency to Dependency Structures

Dynamic Programming

using divide and recombine approaches
  • CYK (Projective) - 𝑂(𝑛5)
  • Eisner (Projective) - 𝑂(𝑛3)

Graph Algorithms

creating a Minimum Spanning Tree for a sentence
  • MST (Non-Projective) - 𝑂(𝑛2)

Constraint Satisfaction

edges are eliminated that don’t satisfy hard constraints
  • Karlsson

Transition-Based Parsing
Deterministic Dependency Parsing

greedy choice of attachments guided by good machine learning classifiers

Resources