Optimal Shift-Reduce Constituent Parsing with Structured Perceptron

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1534–1544, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Optimal Shift-Reduce Constituent Parsing with Structured Perceptron Le Quang Thang Hanoi University of Science and Technology {lelightwin@gmail.com} Hiroshi Noji and Yusuke Miyao National Institute of Informatics, The Graduate University for Advanced Studies {noji,yusuke}@nii.ac.jp Abstract We present a constituent shift-reduce parser with a structured perceptron that finds the optimal parse in a practical run- time. The key ideas are new feature tem- plates that facilitate state merging of dy- namic programming and A* search. Our system achieves 91.1 F1 on a standard English experiment, a level which cannot be reached by other beam-based systems even with large beam sizes.1 1 Introduction A parsing system comprises two components: a scoring model for a tree and a search algorithm. In shift-reduce parsing, the focus of most previ- ous studies has been the former, typically by en- riching feature templates, while the search quality has often been taken less seriously. For example, the current state-of-the-art parsers for constituency (Zhu et al., 2013; Wang and Xue, 2014) and de- pendency (Bohnet et al., 2013) both employ beam search with a constant beam size, which may suf- fer from severe search errors. This is contrary to ordinary PCFG parsing which, while it often uses some approximations, has nearly optimal quality (Petrov and Klein, 2007). In this paper, we instead investigate the question of whether we can obtain a practical shift-reduce parser with state-of-the-art accuracy by focusing on optimal search quality like PCFG parsing. We base our system on best-first search for shift- reduce parsing formulated in Zhao et al. (2013), but it differs from their approach in two points. First, we focus on constituent parsing while they use dependency grammar. Second, and more cru- cially, they use a locally trained MaxEnt model, which is simple but not strong, while we explore 1The open source software of our system is available at https://github.com/mynlp/optsr. a structured perceptron, the current state-of-the-art in shift-reduce parsing (Zhu et al., 2013). As we will see, this model change makes search quite hard, which motivates us to invent new fea- ture templates as well as to improve the search algorithm. In existing parsers, features are com- monly exploited from the parsing history, such as the top k elements on the stack. However, such features are expensive in terms of search ef- ficiency. Instead of relying on features primarily from the stack, our features mostly come from the span of the top few nodes, an idea inspired by the recent empirical success in CRF parsing (Hall et al., 2014). We show that these span features also fit quite well in the shift-reduce system and lead to state-of-the-art accuracy. We further improve search with new A* heuristics that make optimal search for shift-reduce parsers with a structured perceptron tractable for the first time. The primary contribution of this paper is to …

Content truncated to 500 words