Paper: Classifying Chart Cells for Quadratic Complexity Context-Free Inference

ACL ID C08-1094
Title Classifying Chart Cells for Quadratic Complexity Context-Free Inference
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2008
Authors

In this paper, we consider classifying word positions by whether or not they can either start or end multi-word constituents. This provides a mechanism for “closing” chart cells during context-free inference, which is demonstrated to improve efficiency and accuracy when used to constrain the well- known Charniak parser. Additionally, we present a method for “closing” a sufficient number of chart cells to ensure quadratic worst-case complexity of context-free in- ference. Empirical results show that this O(n2) bound can be achieved without im- pacting parsing accuracy.