A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 562–571, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics A Tale of Two Parsers: investigating and combining graph-based and transition-based dependency parsing using beam-search Yue Zhang and Stephen Clark Oxford University Computing Laboratory Wolfson Building, Parks Road Oxford OX1 3QD, UK {yue.zhang,stephen.clark}@comlab.ox.ac.uk Abstract Graph-based and transition-based approaches to dependency parsing adopt very different views of the problem, each view having its own strengths and limitations. We study both approaches under the framework of beam- search. By developing a graph-based and a transition-based dependency parser, we show that a beam-search decoder is a competitive choice for both methods. More importantly, we propose a beam-search-based parser that combines both graph-based and transition- based parsing into a single system for train- ing and decoding, showing that it outper- forms both the pure graph-based and the pure transition-based parsers. Testing on the En- glish and Chinese Penn Treebank data, the combined system gave state-of-the-art accura- cies of 92.1% and 86.2%, respectively. 1 Introduction Graph-based (McDonald et al., 2005; McDon- ald and Pereira, 2006; Carreras et al., 2006) and transition-based (Yamada and Matsumoto, 2003; Nivre et al., 2006) parsing algorithms offer two dif- ferent approaches to data-driven dependency pars- ing. Given an input sentence, a graph-based algo- rithm finds the highest scoring parse tree from all possible outputs, scoring each complete tree, while a transition-based algorithm builds a parse by a se- quence of actions, scoring each action individually. The terms “graph-based” and “transition-based” were used by McDonald and Nivre (2007) to de- scribe the difference between MSTParser (McDon- ald and Pereira, 2006), which is a graph-based parser with an exhaustive search decoder, and MaltParser (Nivre et al., 2006), which is a transition-based parser with a greedy search decoder. In this paper, we do not differentiate graph-based and transition- based parsers by their search algorithms: a graph- based parser can use an approximate decoder while a transition-based parser is not necessarily determin- istic. To make the concepts clear, we classify the two types of parser by the following two criteria: 1. whether or not the outputs are built by explicit transition-actions, such as ”Shift” and ”Reduce”; 2. whether it is dependency graphs or transition- actions that the parsing model assigns scores to. By this classification, beam-search can be applied to both graph-based and transition-based parsers. Representative of each method, MSTParser and MaltParser gave comparable accuracies in the CoNLL-X shared task (Buchholz and Marsi, 2006). However, they make different types of errors, which can be seen as a reflection of their theoretical differ- ences (McDonald and Nivre, 2007). MSTParser has the strength of exact inference, but its choice of fea- tures is constrained by the requirement of efficient dynamic programming. MaltParser is deterministic, yet its comparatively larger feature range is an ad- vantage. By comparing the two, three interesting re- search questions arise: (1) how to increase the flex- ibility in defining features for graph-based parsing; (2) how to add search to transition-based …

Content truncated to 500 words