Non-projective dependency parsing using spanning tree algorithms
2005pp. 523–530
Citations Over TimeTop 1% of 2005 papers
Abstract
We formalize weighted dependency parsing as searching for maximum spanning trees (MSTs) in directed graphs. Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n3) time. More surprisingly, the representation is extended naturally to non-projective parsing using Chu-Liu-Edmonds (Chu and Liu, 1965; Edmonds, 1967) MST algorithm, yielding an O(n2) parsing algorithm. We evaluate these methods on the Prague Dependency Treebank using online large-margin learning techniques (Crammer et al., 2003; McDonald et al., 2005) and show that MST parsing increases efficiency and accuracy for languages with non-projective dependencies.
Related Papers
- Indonesian Dependency Treebank: Annotation and Parsing(2012)
- Phrase Structure Parsing with Dependency Structure(2010)
- → Enhancement of Minimum Spanning Tree(2016)2 cited
- → Minimum Spanning Trees(2013)3 cited
- Dependency Parsing: Past, Present, and Future(2014)