Integrating Graph-Based and Transition-Based Dependency Parsers

Proceedings of ACL-08: HLT, pages 950–958, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Integrating Graph-Based and Transition-Based Dependency Parsers V¨axj¨o UniversityJoakim Nivre Uppsala University Computer Science Linguistics and Philology SE-35195 V¨axj¨o SE-75126 Uppsala nivre@msi.vxu.se Ryan McDonald Google Inc. 76 Ninth Avenue New York, NY 10011 ryanmcd@google.com Abstract Previous studies of data-driven dependency parsing have shown that the distribution of parsing errors are correlated with theoretical properties of the models used for learning and inference. In this paper, we show how these results can be exploited to improve parsing accuracy by integrating a graph-based and a transition-based model. By letting one model generate features for the other, we consistently improve accuracy for both models, resulting in a significant improvement of the state of the art when evaluated on data sets from the CoNLL-X shared task. 1 Introduction Syntactic dependency graphs have recently gained a wide interest in the natural language processing community and have been used for many problems ranging from machine translation (Ding and Palmer, 2004) to ontology construction (Snow et al., 2005). A dependency graph for a sentence represents each word and its syntactic dependents through labeled directed arcs, as shown in figure 1. One advantage of this representation is that it extends naturally to discontinuous constructions, which arise due to long distance dependencies or in languages where syntac- tic structure is encoded in morphology rather than in word order. This is undoubtedly one of the reasons for the emergence of dependency parsers for a wide range of languages. Many of these parsers are based on data-driven parsing models, which learn to pro- duce dependency graphs for sentences solely from an annotated corpus and can be easily ported to any Figure 1: Dependency graph for an English sentence. language or domain in which annotated resources exist. Practically all data-driven models that have been proposed for dependency parsing in recent years can be described as either graph-based or transition- based (McDonald and Nivre, 2007). In graph-based parsing, we learn a model for scoring possible de- pendency graphs for a given sentence, typically by factoring the graphs into their component arcs, and perform parsing by searching for the highest-scoring graph. This type of model has been used by, among others, Eisner (1996), McDonald et al. (2005a), and Nakagawa (2007). In transition-based parsing, we instead learn a model for scoring transitions from one parser state to the next, conditioned on the parse history, and perform parsing by greedily taking the highest-scoring transition out of every parser state until we have derived a complete dependency graph. This approach is represented, for example, by the models of Yamada and Matsumoto (2003), Nivre et al. (2004), and Attardi (2006). Theoretically, these approaches are very different. The graph-based models are globally trained and use exact inference algorithms, but define features over a limited history of parsing decisions. The transition- based models are essentially the opposite. They use local training and greedy inference algorithms, but 950 define features over a rich history of parsing …

Content truncated to 500 words