Automatic Compensation for Parser Figure-of-Merit Flaws

Automatic Compensation for Parser Figure-of-Merit Flaws* Don Blaheta and Eugene Charniak {dpb, ec}@cs, brown, edu Department of Computer Science Box 1910 / 115 Waterman St.--4th floor Brown University Providence, RI 02912 Abstract Best-first chart parsing utilises a figure of merit (FOM) to efficiently guide a parse by first attending to those edges judged better. In the past it has usually been static; this paper will show that with some extra infor- mation, a parser can compensate for FOM flaws which otherwise slow it down. Our re- sults are faster than the prior best by a fac- tor of 2.5; and the speedup is won with no significant decrease in parser accuracy. 1 Introduction Sentence parsing is a task which is tra- ditionMly rather computationally intensive. The best known practical methods are still roughly cubic in the length of the sentence-- less than ideM when deMing with nontriviM sentences of 30 or 40 words in length, as fre- quently found in the Penn Wall Street Jour- nal treebank corpus. Fortunately, there is now a body of litera- ture on methods to reduce parse time so that the exhaustive limit is never reached in prac- tice. 1 For much of the work, the chosen ve- hicle is chart parsing. In this technique, the parser begins at the word or tag level and uses the rules of a context-free grammar to build larger and larger constituents. Com- pleted constituents are stored in the cells of a chart according to their location and * This research was funded in part by NSF Grant IRI-9319516 and ONR Grant N0014-96-1-0549. IAn exhaustive parse always "overgenerates" be- cause the grammar contains thousands of extremely rarely applied rules; these are (correctly) rejected even by the simplest parsers, eventuMly, but it would be better to avoid them entirely. length. Incomplete constituents ("edges") are stored in an agenda. The exhaustion of the agenda definitively marks the comple- tion of the parsing algorithm, but the parse needn't take that long; Mready in the early work on chart parsing, (Kay, 1970) suggests that by ordering the agenda one can find a parse without resorting to an exhaustive search. The introduction of statistical pars- ing brought with an obvious tactic for rank- ing the agenda: (Bobrow, 1990) and (Chi- trao and Grishman, 1990) first used proba- bilistic context free grammars (PCFGs) to generate probabilities for use in a figure of merit (FOM). Later work introduced other FOMs formed from PCFG data (Kochman and Kupin, 1991); (Magerman and Marcus, 1991); and (Miller and Fox, 1994). More recently, we have seen parse times lowered by several orders of magnitude. The (Caraballo and Charniak, 1998) article con- siders a number of different figures of merit for ordering the agenda, and ultimately rec- ommends one that reduces the number of edges required for a full parse into the thou- sands. (Goldwater et al., 1998) (henceforth [Gold98]) introduces an edge-based tech- nique, (instead of constituent-based), which drops the average edge count into the hun- dreds. However, if we …

Content truncated to 500 words