Chart parser for stochastic unification grammar
First Claim
1. A method for recognizing a spoken input representing a plurality of words, comprising the steps of:
- (a) inputting a desired spoken input composed of a plurality of grammar levels;
(b) inputting grammars having terminal and non-terminal symbols for defining allowable sentence structures;
(c) inputting a lexicon having entries for defining terminal symbols of the grammar in terms of linguistic, syntactic or semantic features;
(d) generating a matrix of state sets;
(e) initializing said state sets;
(f) reading said desired spoken input;
(g) predicting initial and final probabilities for a current frame for each start symbol of grammar;
(h) parsing said start symbols according to said spoken input and grammars to produce observations of said symbols based on delayed commitment calculation of said predicting step; and
(i) explaining said spoken input based on the observations of said step of parsing.
2 Assignments
0 Petitions
Accused Products
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).
88 Citations
33 Claims
-
1. A method for recognizing a spoken input representing a plurality of words, comprising the steps of:
-
(a) inputting a desired spoken input composed of a plurality of grammar levels; (b) inputting grammars having terminal and non-terminal symbols for defining allowable sentence structures; (c) inputting a lexicon having entries for defining terminal symbols of the grammar in terms of linguistic, syntactic or semantic features; (d) generating a matrix of state sets; (e) initializing said state sets; (f) reading said desired spoken input; (g) predicting initial and final probabilities for a current frame for each start symbol of grammar; (h) parsing said start symbols according to said spoken input and grammars to produce observations of said symbols based on delayed commitment calculation of said predicting step; and (i) explaining said spoken input based on the observations of said step of parsing. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A system for recognizing a spoken sentence representing a plurality of words, comprising:
-
a processing means; a grammar coupled to said processing means for defining sentences in terms of elements of a language model; a lexicon for defining elements of the grammar in terms of symbols; a parser coupled to said grammar for combining words into partial sentences, for generating sets of states and for determining completed states; a predictor coupled to said grammar and said processing means for predicting the symbols of valid next elements generated by said parser; a completer for explaining the results from the parser; and output means coupled to said processing means for generating the explanation developed by said completer. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A system for parsing a spoken sentence having a plurality of words, comprising:
-
input means for recording spoken words; a processing means; an acoustic device for transforming spoken words into a medium readable by said processing means; a grammar coupled to said processing means for defining sentences in terms of elements of a language model; a lexicon for defining elements of the grammar in terms of symbols or features; a parser coupled to said grammar for combining words into partial sentences, for generating sets of states and for determining completed states; a predictor coupled to said lexicon and said processing means for predicting the symbols of valid next elements generated by said parser; a means for generating a chart, wherein the chart is accessed by said parser and said predictor for storing intermediate results; a completer for explaining the results from the parser; a scanner coupled to said parser and said compiler for reading symbols and features from the parser to the completer; and
output means coupled to said processing means for generating the explanation developed by said completer. - View Dependent Claims (21, 22, 23, 24)
-
-
25. A method for parsing a spoken sentence having a plurality of words, comprising the steps of:
-
(a) inputting a desired spoken input composed of a plurality of grammar levels; (b) inputting at least one grammar having terminal and nonterminal symbols for defining allowable sentence structures; (c) inputting a lexicon having entries for defining terminal symbols of said at least one grammar in terms of linguistic, syntactic or semantic features; (d) generating a matrix of state sets; (e) initializing said state sets; (f) reading said desired spoken input; (g) predicting initial and final probabilities for a current frame for each start symbol of grammar; (h) predicting a valid next nonterminal symbol to thereby create at least one state from its corresponding at least one rule according to said at least one grammar; (i) completing said at least one state as explanations for symbols become available; (j) generating a probability score for each said completed state; (k) repeating steps (h) to (j) until no new states can be created; (l) parsing terminal symbols from the current grammar level as start symbols for the next lower grammar level unless at the lowest grammar level; (m) if at lowest grammar level, comparing features of the spoken input with features of the predicted next lexical entries; (n) scanning observations from said next lower grammar level into waiting states of said current grammar level; (i) repeating steps (h) through (n) until no new states can be completed; (p) reporting complete states corresponding to start symbols of said current level to the next higher grammar level; (q) parsing said start symbols according to the spoken input and grammars to produce observations of said symbols; and (r) explaining the input based on the results of said step of parsing. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33)
-
Specification