Non-projective Dependency Parsing using Spanning Tree Algorithms

1 Introduction

1. What is the core idea of McDonald, Pereira, Ribarov and Hajič (2005)?
   Weighted dependency parsing is the search for a maximum spanning tree (MST) in a directed graph over the words. The Eisner algorithm finds the best projective tree in \(O(n^3)\), and the Chu-Liu-Edmonds MST algorithm finds the best non-projective tree in \(O(n^2)\).
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §1, p. 523
2. What is a dependency tree, and when is it projective?
   Each word depends on exactly one parent, another word or a dummy root. It is projective if, with words in linear order preceded by the root, all edges can be drawn above the words without crossing; equivalently, every word and its descendants form a contiguous substring.
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §1, p. 523
3. Why did dependency parsing attract interest, according to McDonald et al.?
   Dependency structures are more efficient to learn and parse than lexicalized phrase structures while still encoding much of the predicate-argument information that applications such as relation extraction, machine translation, synonym generation and lexical resource augmentation need.
   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §1, p. 523
4. When is a non-projective dependency tree needed? Give an English example.
   When a dependent is separated from its head by material outside the head’s subtree, e.g. a relative clause separated from the noun it modifies by an adverb: “John saw a dog yesterday which was a Yorkshire Terrier.” Non-projectivity is more frequent in freer word order languages like German, Dutch and Czech.

   • McDonald et al., 2005, Non-projective Dependency Parsing using Spanning Tree Algorithms (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005)), §1, p. 523