Recurrent Neural Network Grammars

Proceedings of NAACL-HLT 2016, pages 199–209, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Recurrent Neural Network Grammars Chris Dyer♠ Adhiguna Kuncoro♠ Miguel Ballesteros♦♠ Noah A. Smith♥ ♠School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA ♦NLP Group, Pompeu Fabra University, Barcelona, Spain ♥Computer Science & Engineering, University of Washington, Seattle, WA, USA {cdyer,akuncoro}@cs.cmu.edu, miguel.ballesteros@upf.edu, nasmith@cs.washington.edu Abstract We introduce recurrent neural network gram- mars, probabilistic models of sentences with explicit phrase structure. We explain efficient inference procedures that allow application to both parsing and language modeling. Experi- ments show that they provide better parsing in English than any single previously published supervised generative model and better lan- guage modeling than state-of-the-art sequen- tial RNNs in English and Chinese. 1 Introduction Sequential recurrent neural networks (RNNs) are remarkably effective models of natural language. In the last few years, language model results that substantially improve over long-established state-of- the-art baselines have been obtained using RNNs (Zaremba et al., 2015; Mikolov et al., 2010) as well as in various conditional language modeling tasks such as machine translation (Bahdanau et al., 2015), image caption generation (Xu et al., 2015), and dia- logue generation (Wen et al., 2015). Despite these impressive results, sequential models are a priori inappropriate models of natural language, since re- lationships among words are largely organized in terms of latent nested structures rather than sequen- tial surface order (Chomsky, 1957). In this paper, we introduce recurrent neural net- work grammars (RNNGs; §2), a new generative probabilistic model of sentences that explicitly mod- els nested, hierarchical relationships among words and phrases. RNNGs operate via a recursive syntac- tic process reminiscent of probabilistic context-free grammar generation, but decisions are parameter- ized using RNNs that condition on the entire syntac- tic derivation history, greatly relaxing context-free independence assumptions. The foundation of this work is a top-down vari- ant of transition-based parsing (§3). We give two variants of the algorithm, one for parsing (given an observed sentence, transform it into a tree), and one for generation. While several transition-based neu- ral models of syntactic generation exist (Hender- son, 2003, 2004; Emami and Jelinek, 2005; Titov and Henderson, 2007; Buys and Blunsom, 2015b), these have relied on structure building operations based on parsing actions in shift-reduce and left- corner parsers which operate in a largely bottom- up fashion. While this construction is appealing be- cause inference is relatively straightforward, it lim- its the use of top-down grammar information, which is helpful for generation (Roark, 2001).1 RNNGs maintain the algorithmic convenience of transition- based parsing but incorporate top-down (i.e., root- to-terminal) syntactic information (§4). The top-down transition set that RNNGs are based on lends itself to discriminative modeling as well, where sequences of transitions are modeled conditional on the full input sentence along with the incrementally constructed syntactic structures. Sim- ilar to previously published discriminative bottom- up transition-based parsers (Henderson, 2004; Sagae and Lavie, 2005; Zhang and Clark, 2011, inter alia), greedy prediction with our model yields a linear- time deterministic parser (provided …

Content truncated to 500 words