Chart parser for stochastic unification grammar

Abstract

A chart parser is disclosed which incorporates rule and observation probabilities with stochastic unification grammars. The parser operates frame synchronously to provide top-down hypotheses and to incorporate observation probabilities as they become available. Because the language model produces multiple explanations of the speech data between frames, the prediction and combination of rules may create cycles in a graph representing the best scores. Score calculation includes the detection of these cycles and propagation of the best scores to the next frame. The algorithm creates no more states than a nonprobilistic chart parser, and remains linear for regular grammars and cubic in the worst case for CFGs. The parser allows a direct integration of statistical speech information and linguistic constraints within the same language model, while the language model permits a generalization of HMM-type models. The efficiency of the parser makes it applicable to multiple levels of a spoken language system (e.g., sentence, word, phoneme, and phone levels).