Chart parser for stochastic unification grammar

Details Chart parser for stochastic unification grammar Chart parser for stochastic unification grammar

1989-02-21

1991-01-08

Jablon, Clark A.

Boots, shoes, and leggings

364419, 381 42, 381 43, G10L 900

Patent

active

049841785

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).

REFERENCES:
patent: 4718092 (1988-01-01), Klovstad
patent: 4718093 (1988-01-01), Brown
patent: 4783803 (1988-11-01), Baker et al.
patent: 4852173 (1989-07-01), Bahl et al.
Young, S. J. et al., "Speed recognition in VODIS II", Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, 1988, 441-444.
Querre, M. et al., "Versatile speaker-dependent continuous speech understanding system", Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, 1988, 303-306.
Trehan, R. et al., "A paralle chart parser for the committed choice non-deterministic logic languages", IEEE Proceedings of the Fifth International Conference and Symposium: Logic Programming, Seattle, WA, Aug. 1988, 212-232, vol. 1.
Grishman, R. et al., "Evaluation of a parallel chart parser", 10th International Conference on Computational Linguistics, Stanford, CA, Jul. 1984, 393-397.
J. Earley, "An Efficient Context-Free Parsing Algorithm", Feb., 1970, vol. 13, No. 2, pp. 94-102, Communications of the ACM.
Paeseler, A., "Modification of Earley's Algorithm for Speech Recognition", Proc. of NATO ASI, Bad Windshein, 1987, pp. 1-8.
Aho et al., "A Minimum Distance Error-Correcting Parser for Context-Free Languages", SIAM J. Comput. vol. 1, No. 4, Dec. 1972, pp. 305-312.

Affiliated with

Also associated with

Rating

Chart parser for stochastic unification grammar does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Chart parser for stochastic unification grammar, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chart parser for stochastic unification grammar will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-940588