Classifying Chart Cells for Quadratic Complexity Context-Free Inference

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 745–752 Manchester, August 2008 Classifying chart cells for quadratic complexity context-free inference Brian Roark and Kristy Hollingshead Center for Spoken Language Understanding Oregon Health & Science University, Beaverton, Oregon, 97006 USA {roark,hollingk}@cslu.ogi.edu Abstract 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. 1 Introduction While there have been great advances in the statis- tical modeling of hierarchical syntactic structure in the past 15 years, exact inference with such mod- els remains very costly, so that most rich syntac- tic modeling approaches involve heavy pruning, pipelining or both. Pipeline systems make use of simpler models with more efficient inference to re- duce the search space of the full model. For ex- ample, the well-known Ratnaparkhi (1999) parser used a POS-tagger and a finite-state NP chunker as initial stages of a multi-stage Maximum Entropy parser. The Charniak (2000) parser uses a simple PCFG to prune the chart for a richer model; and Charniak and Johnson (2005) added a discrimina- tively trained reranker to the end of that pipeline. Recent results making use of finite-state chun- kers early in a syntactic parsing pipeline have shown both an efficiency (Glaysher and Moldovan, 2006) and an accuracy (Hollingshead and Roark, 2007) benefit to the use of such constraints in a parsing system. Glaysher and Moldovan (2006) demonstrated an efficiency gain by explicitly dis- allowing entries in chart cells that would result in constituents that cross chunk boundaries. Holling- shead and Roark (2007) demonstrated that high precision constraints on early stages of the Char- niak and Johnson (2005) pipeline—in the form of base phrase constraints derived either from a chun- ker or from later stages of an earlier iteration of the c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. same pipeline—achieved significant accuracy im- provements, by moving the pipeline search away from unlikely areas of the search space. Both of these approaches (as with Ratnaparkhi earlier) achieve their improvements by ruling out parts of the search space for downstream processes, and the gain can either be realized in efficiency (same ac- curacy, less time) or accuracy (same time, greater accuracy). Parts of the search space are ruled out precisely when they are inconsistent with the gen- erally reliable output of the chunker, i.e., the con- straints are a by-product of chunking. In this paper, we consider building classifiers that more directly address the problem of “closing” chart cells to entries, rather than extracting this in- formation from taggers or …

Content truncated to 500 words