Efficient Stacked Dependency Parsing by Forest Reranking

Transactions of the Association for Computational Linguistics, 1 (2013) 139–150. Action Editor: Joakim Nivre. Submitted 12/2012; Revised 3/2013; Published 5/2013. c⃝2013 Association for Computational Linguistics. Efficient Stacked Dependency Parsing by Forest Reranking Katsuhiko Hayashi and Shuhei Kondo and Yuji Matsumoto Graduate School of Information Science Nara Institute of Science and Technology 8916-5, Takayama, Ikoma, Nara 630-0192, Japan {katsuhiko-h,shuhei-k,matsu}@is.naist.jp Abstract This paper proposes a discriminative for- est reranking algorithm for dependency pars- ing that can be seen as a form of efficient stacked parsing. A dynamic programming shift-reduce parser produces a packed deriva- tion forest which is then scored by a discrim- inative reranker, using the 1-best tree output by the shift-reduce parser as guide features in addition to third-order graph-based features. To improve efficiency and accuracy, this pa- per also proposes a novel shift-reduce parser that eliminates the spurious ambiguity of arc- standard transition systems. Testing on the English Penn Treebank data, forest reranking gave a state-of-the-art unlabeled dependency accuracy of 93.12. 1 Introduction There are two main approaches of data-driven de- pendency parsing – one is graph-based and the other is transition-based. In the graph-based approach, global optimiza- tion algorithms find the highest-scoring tree with locally factored models (McDonald et al., 2005). While third-order graph-based models achieve state- of-the-art accuracy, it has O(n4) time complexity for a sentence of length n. Recently, some prun- ing techniques have been proposed to improve the efficiency of third-order models (Rush and Petrov, 2012; Zhang and McDonald, 2012). The transition-based approach usually employs the shift-reduce parsing algorithm with linear-time complexity (Nivre, 2008). It greedily chooses the transition with the highest score and the result- ing transition sequence is not always globally op- timal. The beam search algorithm improves pars- ing flexibility in deterministic parsing (Zhang and Clark, 2008; Zhang and Nivre, 2011), and dy- namic programming makes beam search more effi- cient (Huang and Sagae, 2010). There is also an alternative approach that in- tegrates graph-based and transition-based models (Sagae and Lavie, 2006; Zhang and Clark, 2008; Nivre and McDonald, 2008; Martins et al., 2008). Martins et al. (2008) formulated their approach as stacking of parsers where the output of the first-stage parser is provided to the second as guide features. In particular, they used a transition-based parser for the first stage and a graph-based parser for the second stage. The main drawback of this approach is that the efficiency of the transition-based parser is sacri- ficed because the second-stage employs full parsing. This paper proposes an efficient stacked pars- ing method through discriminative reranking with higher-order graph-based features, which works on the forests output by the first-stage dynamic pro- gramming shift-reduce parser and integrates non- local features efficiently with cube-pruning (Huang and Chiang, 2007). The advantages of our method are as follows: • Unlike the conventional stacking approach, the first-stage shift-reduce parser prunes the search space of the second-stage graph-based parser. • In addition to guide features, the second-stage graph-based parser can employ the scores of the first-stage parser which cannot be …

Content truncated to 500 words