Beam-Width Prediction for Efficient Context-Free Parsing

Nathan Bodenstab1,  Aaron Dunlop1,  Keith Hall2,  Brian Roark1
1CSLU/OHSU, 2Google


Abstract

Efficient decoding for syntactic parsing has become a necessary research area as statistical grammars grow in accuracy and size and as more NLP applications leverage syntactic analyses. We review prior methods for pruning and then present a new framework that unifies their strengths into a single approach. 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, exemplified 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.




Full paper: http://www.aclweb.org/anthology/P/P11/P11-1045.pdf