Non-Projective Dependency Parsing using Spanning Tree Algorithms

By Ryan T. McDonald, Fernando C Pereira, Kiril Ribarov, Jan Hajic. Human Language Technology - The Baltic Perspectiv, 2005

1,040 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/936d36404165a724f90e4483eee34e65c28feeb1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Neural Probabilistic Model for Non-projective MST Parsing (2017, methodology): “At test time, parsing trees can be decoded with the maximum spanning tree (MST) algorithm (McDonald et al., 2005b).”
Introduction to dual composition for inference (2011, background): “dependency structure is obtained by maximizing (McDonald et al., 2005)”
New Language Pairs in TectoMT (2015, methodology): “The ﬁrst part, the surface syntactic analysis, consists of a rule-based sentence segmenter and tokenizer, followed by a part-of-speech tagger – we use MorphoDiTa (Straková et al., 2014) in the current version – and a dependency parser (McDonald et al., 2005; Novák and Žabokrtský, 2007).”
Statistical machine translation (2010, positive): “Alternatively, a non-projective dependency parser such as (McDonald et al., 2005) can be used and the resulting dependency tree can be tranfered to the target language using e.”
RNA Secondary Structure Prediction By Learning Unrolled Algorithms (2020, background): “Similar to nested/non-nested structures, the corresponding terms in NLP are projective/non-projective parsing, where most works focus on the former and DP-based inference algorithms are commonly used (McDonald et al., 2005).”
Distributed Word Representation Learning for Cross-Lingual Dependency Parsing (2014, methodology): “The Baseline method uses a delexicalized MSTParser based only on the universal POS tag features.”
Bridging semantics and syntax with graph algorithms —state-of-the-art of extracting biomedical relations (2015, neutral): “…performed comparative analysis on the impact of graph encoding based on different parsers (Charniak-Johnson [65], McClosky-Charniak-Johnson, Bikel [132], GDep, MST [76], MALT [133]) Stanford Dependency variants and found that basic dependency performs best if keeping types of dependency edges.”
The CoNLL 2008 Shared Task on Joint Parsing of Syntactic and Semantic Dependencies (2008, methodology): “By and large, transition-based models use a greedy inference strategy, whereas graph-based models used different Maximum Spanning Tree (MST) algorithms: Carreras (2007) – MST C , Eis-ner (2000) – MST E , or Chu-Liu/Edmonds (Mc-Donald et al., 2005; Chu and Liu, 1965; Edmonds, 1967) – MST CL/E .”
Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers (2013, methodology): “We use an arc-factored score function (McDonald et al., 2005) ) , where π ( m ) is the parent of the m th word according to the parse tree z , and σ ARC ( h, m ) is the score of an individual arc.”
Characterizing the Errors of Data-Driven Dependency Parsing Models (2007, methodology): “…is known a priori, then the parsing problem can be stated as, This problem is equivalent to ﬁnding the highest scoring directed spanning tree in the graph G x originating out of the root node 0 , which can be solved for both the labeled and unlabeled case in O ( n 2 ) time (McDonald et al., 2005b).”
Parser Evaluation over Local and Non-Local Deep Dependencies in a Large Corpus (2011, neutral): “MSTParser (McDonald et al., 2005) is a data-driven dependency parser.”
Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions (2010, methodology): “(8)Edge label frequencies for each POS were computed from the training data for the MST parser (McDonald et al., 2005).”
TectoMT: Modular NLP Framework (2010, neutral): “3b [3], Malt_parser uses Malt parser 1.”
Are Multilingual Neural Machine Translation Models Better at Capturing Linguistic Features? (2020, methodology): “We employ Chu-Liu/Edmonds’ algorithm (Chu and Liu, 1965; McDonald et al., 2005) to extract the minimum spanning arborescence of this graph, which is equivalent to a conventional dependency tree.”