Beam-Width Prediction for Efficient Context-Free Parsing

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 440–449, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Beam-Width Prediction for Efficient Context-Free Parsing Nathan Bodenstab† Aaron Dunlop† Keith Hall‡ and Brian Roark† † Center for Spoken Language Understanding, Oregon Health & Science University, Portland, OR ‡Google, Inc., Zurich, Switzerland {bodensta,dunlopa,roark}@cslu.ogi.edu kbhall@google.com Abstract Efficient decoding for syntactic parsing has become a necessary research area as statisti- cal grammars grow in accuracy and size and as more NLP applications leverage syntac- tic analyses. We review prior methods for pruning and then present a new framework that unifies their strengths into a single ap- proach. Using a log linear model, we learn the optimal beam-search pruning parameters for each CYK chart cell, effectively predicting the most promising areas of the model space to explore. We demonstrate that our method is faster than coarse-to-fine pruning, exempli- fied in both the Charniak and Berkeley parsers, by empirically comparing our parser to the Berkeley parser using the same grammar and under identical operating conditions. 1 Introduction Statistical constituent parsers have gradually in- creased in accuracy over the past ten years. This accuracy increase has opened the door to automati- cally derived syntactic information within a number of NLP tasks. Prior work incorporating parse struc- ture into machine translation (Chiang, 2010) and Se- mantic Role Labeling (Tsai et al., 2005; Punyakanok et al., 2008) indicate that such hierarchical structure can have great benefit over shallow labeling tech- niques like chunking and part-of-speech tagging. Although syntax is becoming increasingly impor- tant for large-scale NLP applications, constituent parsing is slow — too slow to scale to the size of many potential consumer applications. The exhaus- tive CYK algorithm has computational complexity O(n3|G|) where n is the length of the sentence and |G| is the number of grammar productions, a non- negligible constant. Increases in accuracy have pri- marily been accomplished through an increase in the size of the grammar, allowing individual gram- mar rules to be more sensitive to their surround- ing context, at a considerable cost in efficiency. Grammar transformation techniques such as linguis- tically inspired non-terminal annotations (Johnson, 1998; Klein and Manning, 2003b) and latent vari- able grammars (Matsuzaki et al., 2005; Petrov et al., 2006) have increased the grammar size |G| from a few thousand rules to several million in an explic- itly enumerable grammar, or even more in an im- plicit grammar. Exhaustive search for the maximum likelihood parse tree with a state-of-the-art grammar can require over a minute of processing for a sin- gle sentence of 25 words, an unacceptable amount of time for real-time applications or when process- ing millions of sentences. Deterministic algorithms for dependency parsing exist that can extract syntac- tic dependency structure very quickly (Nivre, 2008), but this approach is often undesirable as constituent parsers are more accurate and more adaptable to new domains (Petrov et al., 2010). The most accurate constituent parsers, e.g., Char- niak (2000), Petrov and Klein (2007a), make use …

Content truncated to 500 words