Pearl: A Probabilistic Chart Parser

7 earl: A Probabilistic David M. Magerman CS Del)a, rtmcnt Sta. hn'd U,fivcrsity Stanford, CA 94305 magc,'n mn(i~cs.sl, a.n ford.c(I u Chart Parser* Mitchell P. Marcus CIS l)epartment [.lnivcrsil,y of l)cnnsylvania. Pifiladelphia., PA 19104 mitch ¢21 i n c.(:is, u I)enn .edu Abstract This i)al)er describes a Ilatural language i)ars - ing algorith,n for unrestricted text which uses a prol)al)ility-I~ased scoring function to select the "l)est" i)arse of a sclfl,ence. The parser, T~earl, is a time-asynchronous I)ottom-ul) chart parser with Earley-tyl)e tol)-down prediction which l)ur - sues the highest-scoring theory iu the chart, where the score of a theory represents tim extent to which the context of the sentence predicts that interpre- tation. This parser dilrers front previous attemi)ts at stochastic parsers in that it uses a richer form of conditional prol)alfilities I)ased on context to l)re- diet likelihood. T>carl also provides a framework for i,lcorporating the results of previous work in i)art-of-spe(;ch assignrlmn|., unknown word too<l- ois, and other probal)ilistic models of lingvistic features into one parsing tool, interleaving these techniques instead of using the traditional pipeline a,'chitecture, lu preliminary tests, "Pearl has I)ee.,i st,ccessl'ul at resolving l)art-of-speech and word (in sl)eech processing) ambiguity, d:etermining cate- gories for unknown words, and selecting correct parses first using a very loosely fitting cove,'ing grammar, l Introduction All natural language grammars are alnbiguous. Even tightly fitting natural language grammars are ambigu- ous in some ways. Loosely fitting grammars, which are necessary for handling the variability and complexity of unrestricted text and speech, are worse. Tim stan- dard technique for dealing with this ambiguity, pruning °This work was p,~rtially supported by DARPA grant No. N01114-85-1(0018, ONR contract No. N00014-89- C-0171 by DARPA and AFOSR jointly under grant No. AFOSR-90-0066, and by ARO grant No. DAAL 03-89- C(1031 PRI. Special thanks to Carl Weir and Lynette llirschman at Unisys for their valued input, guidance and support. I'Fhe grammar used for our experiments is the string ~ra.mmar used in Unisys' PUNI)IT natura.I language iin- dt'rsl.a ndi n/4 sysl.tml. gra.nunars I)y hand, is painful, time-consuming, and usually arbitrary. The solution which many people have proposed is to use stochastic models to grain sta- tistical grammars automatically from a large corpus. Attempts in applying statistical techniques to nat- ura, I iangt, age parsi,lg have exhibited varying degrees of success. These successful and unsuccessful attempts have suggested to us that: . Stochastic techniques combined with traditional lin- guistic theories can (and indeed must) provide a so- lull|on to the natural language understanding prob- lem. * In order for stochastic techniques to be effective, they must be applied with restraint (poor estimates of context arc worse than none[7]). - Interactive, interleaved architectvres are preferable to pipeline architectures in NLU systems, because they use more of the available information in the decision-nmkiug process. Wc have constructed a stoch~tic parser,/)earl, which is based on these ideas. The development of the 7~earl parser is an effort to combine the statistical models developed recently into a single tool which incorporates all of these …

Content truncated to 500 words