Global Thresholding and Multiple-Pass Parsing

Global Thresholding and Multiple-Pass Parsing* Joshua Goodman Harvard University 40 Oxford St. Cambridge, MA 02138 goodman@das.harvard.edu Abstract We present a variation on classic beam thresholding techniques that is up to an or- der of magnitude faster than the traditional method, at the same performance level. We also present a new thresholding technique, global thresholding, which, combined with the new beam thresholding, gives an ad- ditional factor of two improvement, and a novel technique, multiple pass parsing, that can be combined with the others to yield yet another 50% improvement. We use a new search algorithm to simultaneously op- timize the thresholding parameters of the various algorithms. 1 Introduction In this paper, we examine thresholding techniques for statistical parsers. While there exist theoretically efficient (O (n 3)) algorithms for parsing Probabilistic Context-Free Grammars (PCFGs) and related for- malisms, practical parsing algorithms usually make use of pruning techniques, such as beam threshold- ing, for increased speed. We introduce two novel thresholding techniques, global thresholding and multiple-pass parsing, and one significant variation on traditional beam thresh- olding. We examine the value of these techniques when used separately, and when combined. In or- der to examine the combined techniques, we also introduce an algorithm for optimizing the settings *This material is based in part upon work supported by the National Science Foundation under Grant No. IRI-9350192 and a National Science Foundation Grad- uate Student Fellowship. I would also like to thank Michael Collins, Rebecca Hwa, Lillian Lee, Wheeler Ruml, and Stuart Shieber for helpful discussions, and comments on earlier drafts, and the anonymous review- ers for their extensive comments. 11 of multiple thresholds. When all three thresholding methods are used together, they yield very signif- icant speedups over traditional beam thresholding, while achieving the same level of performance. We apply our techniques to CKY chart parsing, one of the most commonly used parsing methods in natural language processing. In a CKY chart parser, a two-dimensional matrix of cells, the chart, is filled in. Each cell in the chart corresponds-to a span of the sentence, and each cell of the chart contains the nonterminals that could generate that span. Cells covering shorter spans are filled in first, so we also refer to this kind of parser as a bottom-up chart parser. The parser fills in a cell in the chart by examining the nonterminals in lower, shorter cells, and combin- ing these nonterminals according to the rules of the grammar. The more nonterminals there are in the shorter cells, the more combinations of nonterminals the parser must consider. In some grammars, such as PCFGs, probabilities are associated with the grammar rules. This in- troduces problems, since in many PCFGs, almost any combination of nonterminals is possible, per- haps with some low probability. The large number of possibilities can greatly slow parsing. On the other hand, the probabilities also introduce new opportu- nities. For instance, if in a particular cell in the chart there is some nonterminal that generates the span with high probability, and another …

Content truncated to 500 words