Transition-Based Left-Corner Parsing for Identifying PTB-Style Nonlocal Dependencies

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 930–940, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Transition-Based Left-Corner Parsing for Identifying PTB-Style Nonlocal Dependencies Yoshihide Kato1 and Shigeki Matsubara2 1Information & Communications, Nagoya University 2Graduate School of Information Science, Nagoya University Furo-cho, Chikusa-ku, Nagoya, 464-8601 Japan yoshihide@icts.nagoya-u.ac.jp Abstract This paper proposes a left-corner parser which can identify nonlocal dependencies. Our parser integrates nonlocal dependency identification into a transition-based sys- tem. We use a structured perceptron which enables our parser to utilize global features captured by nonlocal dependencies. An experimental result demonstrates that our parser achieves a good balance between constituent parsing and nonlocal depen- dency identification. 1 Introduction Many constituent parsers based on the Penn Tree- bank (Marcus et al., 1993) are available, but most of them do not deal with nonlocal dependen- cies. Nonlocal dependencies represent syntactic phenomenon such as wh-movement, A-movement in passives, topicalization, raising, control, right node raising and so on. Nonlocal dependencies play an important role on semantic interpretation. In the Penn Treebank, a nonlocal dependency is represented as a pair of an empty element and a filler. Several methods of identifying nonlocal de- pendencies have been proposed so far. These methods can be divided into three approaches: pre-processing approach (Dienes and Dubey, 2003b), in-processing approach (Dienes and Dubey, 2003a; Schmid, 2006; Cai et al., 2011; Kato and Matsubara, 2015) and post-processing approach (Johnson, 2002; Levy and Manning, 2004; Campbell, 2004; Xue and Yang, 2013; Xi- ang et al., 2013; Takeno et al., 2015).1 In pre- processing approach, a tagger called “trace tag- ger” detects empty elements. The trace tagger uses 1The methods of (Cai et al., 2011; Xue and Yang, 2013; Xiang et al., 2013; Takeno et al., 2015) only detect empty elements. only surface word information. In-processing ap- proach integrates nonlocal dependency identifica- tion into a parser. The parser uses a probabilis- tic context-free grammar to rank candidate parse trees. Post-processing approach recovers nonlocal dependencies from a parser output which does not include nonlocal dependencies. The parsing models of the previous methods cannot use global features captured by nonlocal dependencies. Pre- or in-processing approach uses a probabilistic context-free grammar, which makes it difficult to use global features. Post- processing approach performs constituent parsing and nonlocal dependency identification separately. This means that the constituent parser cannot use any kind of information about nonlocal dependen- cies. This paper proposes a parser which inte- grates nonlocal dependency identification into constituent parsing. Our method adopts an in- processing approach, but does not use a proba- bilistic context-free grammar. Our parser is based on a transition system with structured percep- tron (Collins, 2002), which can easily introduce global features to its parsing model. We adopt a left-corner strategy in order to use the syntac- tic relation c-command, which plays an important role on nonlocal dependency identification. Pre- vious work on transition-based constituent pars- ing adopts a shift-reduce strategy with a tree bina- rization (Sagae and Lavie, 2005; Sagae and Lavie, 2006; …

Content truncated to 500 words