Global Neural CCG Parsing with Optimality Guarantees

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2366–2376, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Global Neural CCG Parsing with Optimality Guarantees Kenton Lee Mike Lewis Luke Zettlemoyer Computer Science & Engineering University of Washington Seattle, WA 98195 {kentonl,mlewis,lsz}@cs.washington.edu Abstract We introduce the first global recursive neural parsing model with optimality guarantees dur- ing decoding. To support global features, we give up dynamic programs and instead search directly in the space of all possible subtrees. Although this space is exponentially large in the sentence length, we show it is possible to learn an efficient A* parser. We augment existing parsing models, which have informa- tive bounds on the outside score, with a global model that has loose bounds but only needs to model non-local phenomena. The global model is trained with a novel objective that en- courages the parser to search both efficiently and accurately. The approach is applied to CCG parsing, improving state-of-the-art accu- racy by 0.4 F1. The parser finds the optimal parse for 99.9% of held-out sentences, explor- ing on average only 190 subtrees. 1 Introduction Recursive neural models perform well for many structured prediction problems, in part due to their ability to learn representations that depend globally on all parts of the output structures. However, global models of this sort are incompatible with existing exact inference algorithms, since they do not de- compose over substructures in a way that allows ef- fective dynamic programming. Existing work has therefore used greedy inference techniques such as beam search (Vinyals et al., 2015; Dyer et al., 2015) or reranking (Socher et al., 2013). We introduce the first global recursive neural parsing approach with optimality guarantees for decoding and use it to build a state-of-the-art CCG parser. To enable learning of global representations, we modify the parser to search directly in the space of all possible parse trees with no dynamic program- ming. Optimality guarantees come from A∗ search, which provides a certificate of optimality if run to completion with a heuristic that is a bound on the future cost. Generalizing A∗ to global models is challenging; these models also break the locality as- sumptions used to efficiently compute existing A∗ heuristics (Klein and Manning, 2003; Lewis and Steedman, 2014). Rather than directly replacing lo- cal models, we show that they can simply be aug- mented by adding a score from a global model that is constrained to be non-positive and has a trivial upper bound of zero. The global model, in effect, only needs to model the remaining non-local phe- nomena. In our experiments, we use a recent fac- tored A∗ CCG parser (Lewis et al., 2016) for the local model, and we train a Tree-LSTM (Tai et al., 2015) to model global structure. Finding a model that achieves these A∗ guar- antees in practice is a challenging learning prob- lem. Traditional structured prediction objectives fo- cus on ensuring that the gold parse has the high- est score (Collins, 2002; …

Content truncated to 500 words