LSTM CCG Parsing

Proceedings of NAACL-HLT 2016, pages 221–231, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics LSTM CCG Parsing Mike Lewis Kenton Lee Luke Zettlemoyer Computer Science & Engineering University of Washington Seattle, WA 98195 {mlewis,kentonl,lsz}@cs.washington.edu Abstract We demonstrate that a state-of-the-art parser can be built using only a lexical tagging model and a deterministic grammar, with no ex- plicit model of bi-lexical dependencies. In- stead, all dependencies are implicitly encoded in an LSTM supertagger that assigns CCG lex- ical categories. The parser significantly out- performs all previously published CCG re- sults, supports efficient and optimal A∗ de- coding, and benefits substantially from semi- supervised tri-training. We give a detailed analysis, demonstrating that the parser can re- cover long-range dependencies with high ac- curacy and that the semi-supervised learning enables significant accuracy gains. By run- ning the LSTM on a GPU, we are able to parse over 2600 sentences per second while improv- ing state-of-the-art accuracy by 1.1 F1 in do- main and up to 4.5 F1 out of domain. 1 Introduction Combinatory Categorial Grammar (CCG) is a strongly lexicalized formalism—the vast majority of attachment decisions during parsing are specified by the selection of lexical entries for words (see Fig- ure 1 for examples). State-of-the-art parsers typi- cally include a supertagging model, to select possi- ble lexical categories, and a bi-lexical dependency model, to resolve the remaining parse attachment ambiguities. In this paper, we introduce a long short- term memory (LSTM) CCG parsing model that has no explicit model of bi-lexical dependencies, but in- stead relies on a bi-directional recurrent neural net- work (RNN) supertagger to capture all long distance dependencies. This approach has a number of ad- vantages: it is conceptually simple, allows for the reuse of existing optimal and efficient parsing algo- rithms, benefits significantly from semi-supervised learning, and is highly accurate both in and out of domain. The parser is publicly released.1 Neural networks have shown strong performance in a range of NLP tasks; however they can break the dynamic programs for structured prediction prob- lems, such as parsing, when vector embeddings are recursively computed for subparts of the output. Ex- isting neural net parsers either (1) use greedy in- ference techniques including shift-reduce parsing (Henderson et al., 2013; Chen and Manning, 2014; Weiss et al., 2015; Dyer et al., 2015), constituency parse re-ranking (Socher et al., 2013), and string- to-string transduction (Vinyals et al., 2015), or (2) avoid recursive computations entirely (Durrett and Klein, 2015). Our approach gives a simple alterna- tive: we only train a model for tagging decisions, where we can easily use recurrent architectures such as LSTMs (Hochreiter and Schmidhuber, 1997), and rely on the highly lexicalized nature of the CCG grammar to allow this tagger to specify nearly ev- ery aspect of the complete parse. Our LSTM supertagger is bi-directional and in- cludes a softmax potential over tags for each word in the sentence. During training, we jointly opti- mize all LSTM parameters, including the word em- beddings, to maximize the …

Content truncated to 500 words