Linear Complexity Context-Free Parsing Pipelines via Chart Constraints

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 647–655, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Linear Complexity Context-Free Parsing Pipelines via Chart Constraints Brian Roark and Kristy Hollingshead Center for Spoken Language Understanding Division of Biomedical Computer Science Oregon Health & Science University {roark,hollingk}@cslu.ogi.edu Abstract In this paper, we extend methods from Roark and Hollingshead (2008) for reducing the worst-case complexity of a context-free pars- ing pipeline via hard constraints derived from finite-state tagging pre-processing. Methods from our previous paper achieved quadratic worst-case complexity. We prove here that al- ternate methods for choosing constraints can achieve either linear or O(Nlog2N) complex- ity. These worst-case bounds on processing are demonstrated to be achieved without re- ducing the parsing accuracy, in fact in some cases improving the accuracy. The new meth- ods achieve observed performance compara- ble to the previously published quadratic com- plexity method. Finally, we demonstrate im- proved performance by combining complexity bounding methods with additional high preci- sion constraints. 1 Introduction Finite-state pre-processing for context-free parsing is very common as a means of reducing the amount of search required in the later stage. For ex- ample, the well-known Ratnaparkhi parser (Ratna- parkhi, 1999) used a finite-state POS-tagger and NP- chunker to reduce the search space for his Maxi- mum Entropy parsing model, and achieved linear observed-time performance. Other recent examples of the utility of finite-state constraints for parsing pipelines include Glaysher and Moldovan (2006), Djordjevic et al. (2007), Hollingshead and Roark (2007), and Roark and Hollingshead (2008). Note that by making use of constraints derived from pre- processing, they are no longer performing full exact inference—these are approximate inference meth- ods, as are the methods presented in this paper. Most of these parsing pipeline papers show empirically that these techniques can improve pipeline efficiency for well-known parsing tasks. In contrast, in Roark and Hollingshead (2008), we derived and applied the finite-state constraints so as to guarantee a reduc- tion in the worst-case complexity of the context-free parsing pipeline from O(N3) in the length of the string N to O(N2) by closing chart cells to entries. We demonstrated the application of such constraints to the well-known Charniak parsing pipeline (Char- niak, 2000), which resulted in no accuracy loss when the constraints were applied. While it is important to demonstrate that these sorts of complexity-reducing chart constraints do not interfere with the operation of high-accuracy, state- of-the-art parsing approaches, existing pruning tech- niques used within such parsers can obscure the im- pact of these constraints on search. For example, us- ing the default search parameterization of the Char- niak parser, the Roark and Hollingshead (2008) re- sults demonstrated no parser speedup using the tech- niques, rather an accuracy improvement, which we attributed to a better use of the amount of search per- mitted by that default parameterization. We only demonstrated efficiency improvements by reducing the amount of search via the Charniak search param- eterization. There we showed a nice speedup …

Content truncated to 500 words