Efficient pruning algorithm for hidden markov model speech recognition
First Claim
1. A method for reducing loading of a central processing unit during speech recognition involving hierarchical layers of grammar and wherein models of those hierarchical layers employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising:
- (a) computing a score for the information-bearing current state;
(b) comparing said score against a predetermined threshold value to determine whether said information-bearing current state should be retained;
(c) locating an available slot in a scoring buffer having at least one slot;
(d) storing information regarding said current state in said available slot;
(e) setting a scoring buffer slot backpointer;
(f) assigning a last-time field value in said available slot equal to a current time-index of the central processing unit;
(g) propagating a time value equal to said current time-index back to all scoring buffer slots along a best path leading to said available slot containing information about said current state;
(h) parsing a next current state; and
(i) repeating steps (a) through (h) until all states have been completed.
1 Assignment
0 Petitions
Accused Products
Abstract
An efficient pruning method reduces central processing unit (CPU) loading during real time speech recognition by instructing the CPU to compare a current state'"'"'s previously calculated probability score against a predetermined threshold value and to discard hypothesis containing states with probability scores below such threshold. After determining that the current state should be kept, the CPU is directed to locate an available slot in the scoring buffer where information about the current state is then stored. The CPU locates an available slot by comparing the current time-index with the time-index associated with each scoring buffer slot. When they are equal, the slot is considered not available; when the current time-index is greater, the slot is considered available. After the information about the current state is stored, the CPU then sets the current state'"'"'s backpointer to point at the start state of the current best path if the current states represents a completed model. Regardless of the current state'"'"'s status, the CPU then associates the current time-index with the time-indices of all the slots along the best path to the current state. The CPU then proceeds to calculate the probability score of the next current state and the method repeats until all states have been completed.
-
Citations
8 Claims
-
1. A method for reducing loading of a central processing unit during speech recognition involving hierarchical layers of grammar and wherein models of those hierarchical layers employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising:
-
(a) computing a score for the information-bearing current state; (b) comparing said score against a predetermined threshold value to determine whether said information-bearing current state should be retained; (c) locating an available slot in a scoring buffer having at least one slot; (d) storing information regarding said current state in said available slot; (e) setting a scoring buffer slot backpointer; (f) assigning a last-time field value in said available slot equal to a current time-index of the central processing unit; (g) propagating a time value equal to said current time-index back to all scoring buffer slots along a best path leading to said available slot containing information about said current state; (h) parsing a next current state; and (i) repeating steps (a) through (h) until all states have been completed. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method for efficient pruning during speech recognition, wherein said speech recognition involves using hierarchical layers of grammar and wherein models of those hierarchical layers involve a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising:
-
(s) computing the current state'"'"'s score; (t) comparing said score against a predetermined threshold value, wherein if said score is greater than or equal to said predetermined threshold value, continuing on to step (u) and if said score is less than said predetermined threshold, discarding said state and returning to step (s); (u) locating an available scoring buffer slot; (v) storing information regarding said current state in said available slot; (w) setting a scoring buffer slot backpointer; (x) assigning a last-time field value in said available slot equal to a current time-index; (y) propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots are indicated by said backpointer; (z) parsing a next current state; and (aa) repeating steps (s) through (z) until all states have been completed. - View Dependent Claims (7)
-
-
8. A method for improved speech recognition, said speech recognition using hierarchical layers of grammar and models of those hierarchical layers of grammar employ a plurality of states including at least a start state and a stop state, only one of said plurality of states at any time being designated the current state, comprising:
-
(dd) computing said current state'"'"'s score; (ee) comparing said score against a predetermined threshold value, wherein if said score is greater than or equal to said predetermined threshold value, continuing on to step (ff) and if said score is less than said predetermined threshold, discarding said state and returning to step (dd); (ff) locating an available scoring buffer slot; (gg) storing information regarding said current state in said available slot; (hh) setting a scoring buffer slot backpointer to indicate a directly previous current state'"'"'s scoring buffer slot address if said current state is from the top layer of a grammar; (ii) setting a scoring buffer slot backpointer to indicate said model'"'"'s start state if said current state is not from said top layer of said grammar; (jj) assigning a last-time field value in said available slot equal to a current time-index; (kk) propagating a time value equal to said current time-index back to all scoring buffer slots along the best path leading to said available slot containing information about said current state, wherein the location of said all scoring buffer slots are indicated by said backpointer; (ll) parsing the next current state; and (mm) repeating steps (dd) through (ll) until all states have been completed.
-
Specification