Classifying chart cells for quadratic complexity context-free inference

摘要

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 inference. Empirical results show that this O(n~2) bound can be achieved without impacting parsing accuracy.