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), pages 523–530, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Non-projective Dependency Parsing using Spanning Tree Algorithms Ryan McDonald Fernando Pereira Department of Computer and Information Science University of Pennsylvania {ryantm,pereira}@cis.upenn.edu Kiril Ribarov Jan Hajiˇc Institute of Formal and Applied Linguistics Charles University {ribarov,hajic}@ufal.ms.mff.cuni.cz Abstract We formalize weighted dependency pars- ing as searching for maximum spanning trees (MSTs) in directed graphs. Using this representation, the parsing algorithm of Eisner (1996) is sufficient for search- ing over all projective trees in O(n3) time. More surprisingly, the representation is extended naturally to non-projective pars- ing using Chu-Liu-Edmonds (Chu and Liu, 1965; Edmonds, 1967) MST al- gorithm, yielding an O(n2) parsing al- gorithm. We evaluate these methods on the Prague Dependency Treebank us- ing online large-margin learning tech- niques (Crammer et al., 2003; McDonald et al., 2005) and show that MST parsing increases efficiency and accuracy for lan- guages with non-projective dependencies. 1 Introduction Dependency parsing has seen a surge of inter- est lately for applications such as relation extrac- tion (Culotta and Sorensen, 2004), machine trans- lation (Ding and Palmer, 2005), synonym genera- tion (Shinyama et al., 2002), and lexical resource augmentation (Snow et al., 2004). The primary reasons for using dependency structures instead of more informative lexicalized phrase structures is that they are more efficient to learn and parse while still encoding much of the predicate-argument infor- mation needed in applications. root John hit the ball with the bat Figure 1: An example dependency tree. Dependency representations, which link words to their arguments, have a long history (Hudson, 1984). Figure 1 shows a dependency tree for the sentence John hit the ball with the bat. We restrict ourselves to dependency tree analyses, in which each word de- pends on exactly one parent, either another word or a dummy root symbol as shown in the figure. The tree in Figure 1 is projective, meaning that if we put the words in their linear order, preceded by the root, the edges can be drawn above the words without cross- ings, or, equivalently, a word and its descendants form a contiguous substring of the sentence. In English, projective trees are sufficient to ana- lyze most sentence types. In fact, the largest source of English dependency trees is automatically gener- ated from the Penn Treebank (Marcus et al., 1993) and is by convention exclusively projective. How- ever, there are certain examples in which a non- projective tree is preferable. Consider the sentence John saw a dog yesterday which was a Yorkshire Ter- rier. Here the relative clause which was a Yorkshire Terrier and the object it modifies (the dog) are sep- arated by an adverb. There is no way to draw the dependency tree for this sentence in the plane with no crossing edges, as illustrated in Figure 2. In lan- guages with more flexible word order than English, such as German, Dutch and Czech, non-projective dependencies are more …

Content truncated to 500 words