Unary Constraints for Efficient Context-Free Parsing

Nathan Bodenstab1,  Kristy Hollingshead2,  Brian Roark1
1CSLU/OHSU, 2University of Maryland


Abstract

We present a novel pruning method for context-free parsing that increases efficiency by disallowing phrase-level unary productions in CKY chart cells spanning a single word. Our work is orthogonal to recent work on “closing” chart cells, which has focused on multi-word constituents, leaving span-1 chart cells unpruned. We show that a simple discriminative classifier can learn which span-1 chart cells to close to phrase-level unary productions with high accuracy. Eliminating these unary productions from the search can have a large impact on downstream processing, depending on implementation details of the search. We apply our method to four parsing architectures and demonstrate how it is complementary to the cell-closing paradigm, as well as other pruning methods such as coarse-to-fine, agenda, and beam-search pruning.




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