Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1–11, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles James Cross and Liang Huang School of EECS, Oregon State University, Corvallis, OR, USA {james.henry.cross.iii, liang.huang.sh}@gmail.com Abstract Parsing accuracy using efficient greedy transi- tion systems has improved dramatically in re- cent years thanks to neural networks. Despite striking results in dependency parsing, how- ever, neural models have not surpassed state- of-the-art approaches in constituency parsing. To remedy this, we introduce a new shift- reduce system whose stack contains merely sentence spans, represented by a bare min- imum of LSTM features. We also design the first provably optimal dynamic oracle for constituency parsing, which runs in amortized O(1) time, compared to O(n3) oracles for standard dependency parsing. Training with this oracle, we achieve the best F1 scores on both English and French of any parser that does not use reranking or external data. 1 Introduction Parsing is an important problem in natural language processing which has been studied extensively for decades. Between the two basic paradigms of pars- ing, constituency parsing, the subject of this paper, has in general proved to be the more difficult than dependency parsing, both in terms of accuracy and the run time of parsing algorithms. There has recently been a huge surge of interest in using neural networks to make parsing decisions, and such models continue to dominate the state of the art in dependency parsing (Andor et al., 2016). In constituency parsing, however, neural approaches are still behind the state-of-the-art (Carreras et al., 2008; Shindo et al., 2012; Thang et al., 2015); see more details in Section 5. To remedy this, we design a new parsing frame- work that is more suitable for constituency parsing, and that can be accurately modeled by neural net- works. Observing that constituency parsing is pri- marily focused on sentence spans (rather than indi- vidual words, as is dependency parsing), we propose a novel adaptation of the shift-reduce system which reflects this focus. In this system, the stack consists of sentence spans rather than partial trees. It is also factored into two types of parser actions, structural and label actions, which alternate during a parse. The structural actions are a simplified analogue of shift-reduce actions, omitting the directionality of reduce actions, while the label actions directly as- sign nonterminal symbols to sentence spans. Our neural model processes the sentence once for each parse with a recurrent network. We represent parser configurations with a very small number of span features (4 for structural actions and 3 for label actions). Extending Wang and Chang (2016), each span is represented as the difference of recurrent out- put from multiple layers in each direction. No pre- trained embeddings are required. We also extend the idea of dynamic oracles from dependency to constituency parsing. The latter is significantly more difficult than the former due to F1 being a combination …

Content truncated to 500 words