Method of dynamically altering grammars in a memory efficient speech recognition system

• US 7,324,945 B2
• Filed: 06/28/2001
• Issued: 01/29/2008
• Est. Priority Date: 06/28/2001
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Butzberger, John W., Franco, Horacio E., Neumeyer, Leonardo, Zheng, Jing
• Primary Examiner(s): Azad, Abul K.
• Application Number:
  US09/894,898
• Publication Number:
  US 20030004722A1
• Time in Patent Office: 2,406 Days
• Field of Search: 704/257, 704/3, 704/7, 704/270.1, 704/235, 704/9, 704/2, 704/8, 711/100
• US Class Current: 704/270.1
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
• CPC Class Codes: G10L 15/285 Memory allocation or algorithm optimisation to reduce hardware requirements

Abstract

A method of speech recognition that uses hierarchical data structures that include a top level grammar and various related subgrammars, such as word, phone, and state subgrammars. A speech signal is acquired, and a probabilistic search is performed using the speech signal as an input, and using the (unexpanded) grammars and subgrammars as possible inputs. Memory is allocated to a subgrammar when a transition to that subgrammar is made during the probabilistic search. The subgrammar may then be expanded and evaluated, and the probability of a match between the speech signal and an element of the subgrammar for which memory has been allocated may be computed. Because unexpanded grammars and subgrammars take up very little memory, this method enables systems to recognize and process a larger vocabulary that would otherwise be possible. This method also permits grammars and subgrammars to be added, deleted, or selected by a remote computer while the speech recognition system is operating, allowing speech recognition systems to have a nearly unlimited vocabulary.

Claims

1. A method for allocating memory in a speech recognition system comprising the steps of:

acquiring a first set of data structures that contain a grammar, a word subgrammar, a phone subgrammar and a state subgrammar, each of the subgrammars related to the grammar, wherein the first set of data structures is generated by the speech recognition system based at least in part on a grammar provided by a remote computer;

acquiring a speech signal;

performing a probabilistic search using the speech signal as an input, and using the first set of data structures as possible inputs; and

allocating memory for one of the subgrammars when a transition to that subgrammar is made during the probabilistic search.

2. The method of claim 1 wherein the probabilistic search is a Viterbi beam search.

3. The method of claim 1 wherein the set of data structures is sent through a communication channel by a remote computer.

4. The method of claim 3 wherein the set of data structures is included in code that defines a web page.

5. The method of claim 3 wherein the set of data structures is associated with one or more web pages.

6. The method of claim 1 wherein the set of data structures is selected by a remote computer.

7. The method of claim 1 further comprising the step of acquiring a second set of data structures that contain a second grammar, a second word subgrammar, a second phone subgrammar, and a second state subgrammar, each of the second subgrammars related to the second grammar.

8. The method of claim 7 wherein the second set of data structures replaces the first set of data structures.

9. The method of claim 7 wherein the second set of data structures is acquired while the speech recognition system is operating.

10. In a speech recognition system, a method for recognizing speech comprising the steps of:

acquiring a first set of data structures that contain a grammar, a word subgrammar, a phone subgrammar and a state subgrammar, each of the subgrammars related to the grammar, wherein the first set of data structures is generated by the speech recognition system based at least in part on a grammar provided by a remote computer;

acquiring a speech signal;

performing a probabilistic search using the speech signal as an input, and using the first set of data structures as possible inputs;

allocating memory for one of the subgrammars when a transition to that subgrarnmar is made during the probabilistic search; and

computing a probability of a match between the speech signal and an element of the subgrammar for which memory has been allocated.

11. The method of claim 10 wherein the probabilistic search is a Viterbi beam search.

12. The method of claim 10 further comprising the step of acquiring a second set of data structures that contain a second grammar, a second word subgrammar, a second phone subgrammar, and a second state subgrammar, each of the second subgrammars related to the second grammar.

13. The method of claim 12 wherein the second set of data structures replaces the first set of data structures.

14. The method of claim 12 wherein the second set of data structures is acquired while the speech recognition system is operating.

15. The method of claim 14 wherein the second set of data structures is included in code that defines a web page.

16. The method of claim 14 wherein the second set of data structures is associated with one or more web pages.

17. In a speech recognition system, a method for recognizing speech comprising the steps of:

acquiring a first set of data structures that contain a top level grammar and a plurality subgrammars, each of the subgrammars hierarchically related to the grammar and to each other, wherein the first set of data structures is generated by the speech recognition system based at least in part on a grammar provided by a remote computer;

acquiring a speech signal;

performing a probabilistic search using the speech signal as an input, and using the first set of data structures as possible inputs;

allocating memory for specific subgrammars when transitions to those specific subgrammars are made during the probabilistic search; and

computing probabilities of matches between the speech signal and elements of the subgrammars for which memory has been allocated.

18. The method of claim 17 wherein the top level grammar includes one or more word subgrammars, the word subgrammars including words that are related according to word-to-word transition probabilities.

19. The method of claim 18 wherein each word in a word subgrammar includes one or more phone subgrammars, the phone subgrammars including phones that are related according to phone-to-phone transition probabilities.

20. The method of claim 19 wherein each phone in a phone subgrammar includes one or more state subgrammars, the state subgrammars including states that are related according to state-to-state transition probabilities.

21. The method of claim 20 wherein the probabilities of matches between the speech signal and elements of the subgrammars for which memory has been allocated are computed using one or more probability distributions associated with each state.

22. The method of claim 20 wherein when a word is allocated in memory, an initial phone for the word and an initial state for the initial phone are also allocated in memory.

23. The method of claim 22 wherein one or more subsequent states are allocated in memory until the end of the phone is reached, the allocation based on a transition probability at each state.

24. The method of claim 23 wherein one or more subsequent phones are allocated in memory until the end of the word is reached, the allocation based on a transition probability at each phone.

25. The method of claim 20 wherein when a state probability falls below a state threshold, the state is deallocated from memory.

26. The method of claim 25 wherein the state threshold is dynamically adjustable.

27. The method of claim 21 wherein when a phone probability falls below a phone threshold, the phone is deallocated from memory.

28. The method of claim 27 wherein the phone threshold is dynamically adjustable.

29. The method of claim 20 wherein when a word probability falls below a word threshold, the word is deallocated from memory.

30. The method of claim 29 wherein the word threshold is dynamically adjustable.

31. The method of claim 25 wherein when all the states associated with a phone are deallocated from memory, the phone is deallocated from memory.

32. The method of claim 31 wherein when all the phones associated with a word are deallocated from memory, the word is deallocated from memory.

33. A method for allocating memory in a speech recognition system comprising the steps of:

acquiring a set of data structures that contain a grammar and one or more subgrammars related to the grammar, wherein the first set of data structures is generated by the speech recognition system based at least in part on a grammar provided by a remote computer;

acquiring a speech signal;

performing a probabilistic search using the speech signal as an input, and using the set of data structures as possible inputs; and

allocating memory for a selected one or more of the subgrammars when a transition to the selected subgrammar is made during the probabilistic search.

34. In a speech recognition system, a method for recognizing speech comprising the steps of:

(a) acquiring a set of data structures that contain a grammar and one or more subgrammars related to the grammar, wherein the first set of data structures is generated by the speech recognition system based at least in part on a grammar provided by a remote computer;

(b) receiving spoken input;

(c) using one or more of the data structures to recognize the spoken input;

(d) while the speech recognition system is operating, acquiring a second set of data structures that contain a second grammar and one or more subgrammars related to the second grammar; and

(e) repeating steps (b) and (c), using the second set of data structures in step (c).

35. In a speech recognition system, a method for recognizing speech comprising the steps of:

(a) acquiring from a first remote computer a set of data structures that contain a grammar and one or more subgrammars related to the grammar;

(b) receiving spoken input;

(c) using one or more of the data structures to recognize the spoken input;

(d) while the speech recognition system is operating, acquiring a second set of data structures from the first remote computer or from a second remote computer, the second set of data structures containing a second grammar and one or more subgrammars related to the second grammar; and

(e) repeating steps (b) and (c), using the second set of data structures in step (c).