Shift-Reduce Dependency DAG Parsing

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 753–760 Manchester, August 2008 Shift-Reduce Dependency DAG Parsing Kenji Sagae† Institute for Creative Technologies University of Southern California 13274 Fiji Way Marina del Rey, CA 90292 sagae@ict.usc.edu Jun’ichi Tsujii Department of Computer Science University of Tokyo School of Computer Science University of Manchester National Center for Text Mining tsujii@is.s.u-tokyo.ac.jp Abstract Most data-driven dependency parsing approaches assume that sentence struc- ture is represented as trees. Although trees have several desirable properties from both computational and linguistic perspectives, the structure of linguistic phenomena that goes beyond shallow syntax often cannot be fully captured by tree representations. We present a pars- ing approach that is nearly as simple as current data-driven transition-based de- pendency parsing frameworks, but out- puts directed acyclic graphs (DAGs). We demonstrate the benefits of DAG parsing in two experiments where its advantages over dependency tree parsing can be clearly observed: predicate-argument analysis of English and syntactic analysis of Danish with a representation that in- cludes long-distance dependencies and anaphoric reference links. 1 Introduction Natural language parsing with data-driven de- pendency-based frameworks has received an in- creasing amount of attention in recent years (McDonald et al., 2005; Buchholz and Marsi, 2006; Nivre et al., 2006). Dependency represen- tations directly reflect word-to-word relation-  † This work was conducted while the author was at the Computer Science Department of the University of Tokyo. © 2008. Licensed under the Creative Commons At- tribution-Noncommercial-Share Alike 3.0 Unported license (http://creativecommons.org/licenses/by-nc- sa/3.0). Some rights reserved. ships in a dependency graph, where the words in a sentence are the nodes, and labeled edges cor- respond to head-dependent syntactic relations. In addition to being inherently lexicalized, depen- dency analyses can be generated efficiently and have been show to be useful in a variety of prac- tical tasks, such as question answering (Wang et al., 2007), information extraction in biomedical text (Erkan et al., 2007; Saetre et al, 2007) and machine translation (Quirk and Corston-Oliver, 2006). However, despite rapid progress in the devel- opment of parsers for several languages (Nivre et al., 2007) and algorithms for more linguistically adequate non-projective structures (McDonald et al., 2005; Nivre and Nilsson, 2006), most of the current data-driven dependency parsing ap- proaches are limited to producing only depen- dency trees, where each word has exactly one head. Although trees have desirable properties from both computational and linguistic perspec- tives, the structure of linguistic phenomena that goes beyond shallow syntax often cannot be fully captured by tree representations. Well-known linguistically-motivated dependency-based syn- tactic frameworks, such as Hudson’s Word Grammar (Hudson, 1984), recognize that to represent phenomena such as relative clauses, control relations and other long-distance depen- dencies, more general graphs are needed. Hud- son (2005) illustrates his syntactic framework with the analysis shown in figure 1. In this ex- ample, the arcs above the sentence correspond to a typical dependency tree commonly used in de- pendency parsing. It is clear, however, that the entire dependency structure is not a tree, but …

Content truncated to 500 words