Fast and Accurate Shift-Reduce Constituent Parsing

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 434–443, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Fast and Accurate Shift-Reduce Constituent Parsing Muhua Zhu†, Yue Zhang‡, Wenliang Chen∗, Min Zhang∗ and Jingbo Zhu† †Natural Language Processing Lab., Northeastern University, China ‡Singapore University of Technology and Design, Singapore ∗ Soochow University, China and Institute for Infocomm Research, Singapore zhumuhua@gmail.com yue zhang@sutd.edu.sg chenwenliang@gmail.com mzhang@i2r.a-star.edu.sg zhujingbo@mail.neu.edu.cn Abstract Shift-reduce dependency parsers give comparable accuracies to their chart- based counterparts, yet the best shift- reduce constituent parsers still lag behind the state-of-the-art. One important reason is the existence of unary nodes in phrase structure trees, which leads to different numbers of shift-reduce actions between different outputs for the same input. This turns out to have a large empirical impact on the framework of global training and beam search. We propose a simple yet effective extension to the shift-reduce process, which eliminates size differences between action sequences in beam-search. Our parser gives comparable accuracies to the state-of-the-art chart parsers. With linear run-time complexity, our parser is over an order of magnitude faster than the fastest chart parser. 1 Introduction Transition-based parsers employ a set of shift- reduce actions and perform parsing using a se- quence of state transitions. The pioneering mod- els rely on a classifier to make local decisions, and search greedily for a transition sequence to build a parse tree. Greedy, classifier-based parsers have been developed for both dependency grammars (Yamada and Matsumoto, 2003; Nivre et al., 2006) and phrase-structure grammars (Sagae and Lavie, 2005). With linear run-time complexity, they were commonly regarded as a faster but less accurate alternative to graph-based chart parsers (Collins, 1997; Charniak, 2000; McDonald et al., 2005). Various methods have been proposed to address the disadvantages of greedy local parsing, among which a framework of beam-search and global discriminative training have been shown effective for dependency parsing (Zhang and Clark, 2008; Huang and Sagae, 2010). While beam-search reduces error propagation compared with greedy search, a discriminative model that is globally op- timized for whole sequences of transition actions can avoid local score biases (Lafferty et al., 2001). This framework preserves the most important ad- vantage of greedy local parsers, including linear run-time complexity and the freedom to define ar- bitrary features. With the use of rich non-local fea- tures, transition-based dependency parsers achieve state-of-the-art accuracies that are comparable to the best-graph-based parsers (Zhang and Nivre, 2011; Bohnet and Nivre, 2012). In addition, pro- cessing tens of sentences per second (Zhang and Nivre, 2011), these transition-based parsers can be a favorable choice for dependency parsing. The above global-learning and beam-search framework can be applied to transition-based phrase-structure (constituent) parsing also (Zhang and Clark, 2009), maintaining all the afore- mentioned benefits. However, the effects were not as significant as for transition-based depen- dency parsing. The best reported accuracies of transition-based constituent parsers still lag behind the state-of-the-art (Sagae and Lavie, 2006; Zhang and Clark, 2009). One difference between phrase- structure parsing and dependency …

Content truncated to 500 words