Speech recognition of a list entry

• US 8,532,990 B2
• Filed: 02/16/2010
• Issued: 09/10/2013
• Est. Priority Date: 02/19/2009
• Status: Active Grant

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Hillebrecht, Christian, Schwarz, Markus
• Primary Examiner(s): Abebe, Daniel D
• Application Number:
  US12/706,245
• Publication Number:
  US 20100211390A1
• Time in Patent Office: 1,302 Days
• Field of Search: 704/243, 704/251, 704/275
• US Class Current: 704/243
• CPC Class Codes: G10L 15/08 Speech classification or search
• 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/32 Multiple recognisers used in sequence or in parallel; Score combination systems therefor, e.g. voting systems

Abstract

The present invention relates to a method of generating a candidate list from a list of entries in accordance with a string of subword units corresponding to a speech input in a speech recognition system, the list of entries including plural list entries each comprising at least one fragment having one or more subword units. For each list entry, the fragments of the list entry are compared with the string of subword units. A matching score for each of the compared fragments based on the comparison is determined. The matching score for a fragment is further based on a comparison of at least one other fragment of the same list entry with the string of subword units. A total score for each list entry is determined based on the matching scores for the compared fragments of the respective list entry. A candidate list with the best matching entries from the list of entries based on the total scores of the list entries is generated.

Claims

1. A method of generating a candidate list from a list of entries in accordance with a string of subword units corresponding to a speech input in a speech recognition system, the list of entries including plural list entries each comprising at least one fragment having one or more subword units, the method comprising:

for each list entry, comparing fragments of the list entry with the string of subword units;

determining in the speech recognition system a matching score for each of the compared fragments based on the comparison, the matching score for a fragment being further based on a comparison of at least one other fragment of the same list entry with the string of subword units;

determining a total score for each list entry on the basis of the matching scores for the compared fragments of the respective list entry; and

generating the candidate list with the best matching entries from the list of entries based on the total scores of the list entries.

2. The method according to claim 1, wherein the matching score for a fragment of a list entry is determined such that the matching score corresponds to a matching score for matching a combination of the fragment with at least one other fragment of the same list entry against the string of subword units.

3. The method according to claim 2, wherein the determination of a total score for a list entry is based on the matching score corresponding to a matching score for a combination of fragments of the list entry, the determination being further configured so as to consider a language model comprising at least transition probabilities between the fragments of the combination.

4. The method according to claim 2, wherein the determining of the matching score for the fragment is performed so as to allow any combination of fragments of a list entry.

5. The method according claim 1, wherein the comparing is performed by matching each fragment of a list entry separately against the string of subword units.

6. The method according to claim 5, wherein the matching score for a fragment is determined by consecutively matching the fragment against each subword unit of the string of subword units.

7. The method according to claim 6, wherein comparing of a fragment of a list entry with the string of subword units comprises:

determining cost values for the fragment by matching the fragment against a first subword unit of the string of subword units;

of the cost values determined for the fragment for the first subword unit, substituting an initial cost value by the smallest of all cost values obtained in the last step of the matching of all fragments of the list entry separately against the first subword unit, wherein the substitution is only performed if the smallest cost value is smaller than the initial cost value; and

repeating the determining of cost values and the substituting of an initial cost value of the determined cost values for the remaining subword units of the string of subword units,

wherein the matching of the fragment against a subword unit considers at least one substituted initial cost value, whereby a final cost value for the compared fragment is obtained.

8. The method according to claim 1, further comprising:

determining a combination of the fragments of a list entry which best matches the string of subword units by analyzing intermediate scores determined by comparing the fragments of the list entry with a part of the string of subword units.

9. A method of generating a candidate list from a list of entries in accordance with a string of subword units corresponding to a speech input in a speech recognition system, the list of entries including plural list entries each comprising at least one fragment having one or more subword units, the method comprising:

comparing within the speech recognition system fragments of the list entries to the string of subword units within the speech recognition system;

determining a matching score for each fragment on the basis of the comparison, the matching score indicating how well the fragment matches the string of subword units;

determining a total score for each list entry based on the matching scores of the fragments of the respective list entry; and

generating the candidate list with the best matching entries from the list of entries based on the total scores of the list entries

wherein the comparing is performed for different context variants of a fragment, and wherein the matching score for a context variant of the fragment considers how well the context of the fragment corresponds to the context of a corresponding segment in the string of subword units.

10. The method according to claim 9, wherein the context variant of a fragment is accompanied by at least one wildcard, the wildcard representing the part of the string of subword units not considered in the fragment.

11. The method according to claim 9, wherein the matching score for the context variant is determined by matching the context variant including the wildcard against the string of subword units, the matching being configured such that the wildcard matches substantially uniformly against the subword units of the string.

12. The method according claim 9, wherein for each list entry, an intermediate score is determined for each of different combinations of fragments of the entry, the total score for the entry being determined from the intermediate scores.

13. The method according to claim 12, wherein the intermediate scores are calculated for combinations of fragments having a matching score above a predetermined threshold value.

14. The method according to claim 9, wherein for the determination of the intermediate score for a combination of fragments, the matching score of a context variant of the fragments is used which corresponds to the context of the fragments in the combination.

15. The method according to claim 12, wherein an intermediate score for a combination of fragments is penalized if the combination has at least one of the following properties:

the combination overcovers the string of subword units;

fragments of the combination cover the same part of the string of subword units;

or

the combination does not cover all parts of the string of subword units.

16. The method according to claim 12, wherein for predetermined fragments of the list of entries, the comparing is performed using a speech recognizer, wherein for the remaining fragments of the list of entries, the comparing is performed using a matcher.

17. The method according to claim 9, further comprising:

providing the candidate list as second list of entries and generating a second candidate list from the second list of entries.

18. The method according to claim 9, wherein an a priori probability is assigned statically or dynamically to at least one of a fragment of a list entry, a combination of fragments of a list entry and a list entry, the a priori probability being taken into account when determining the total score for the list entry.

19. The method according to claim 18, wherein the a priori probabilities are determined on the basis of at least one of an information on a current position of a system implementing the method, a frequency of use of a list entry, a language model, a probability for a combination of fragments, and a probability for an ordering of fragments.

20. A method of selecting a list entry from a list of entries via speech input in a speech recognition system, the list of entries including plural list entries each comprising at least one fragment, the method comprising:

receiving a speech input;

generating a string of subword units from the speech input;

generating a candidate list comprising entries from the list of entries which are a preferred match for the string of subword units; and

performing speech recognition in the speech recognition system on the speech input using the candidate list as a vocabulary, wherein for an entry of the candidate list, a probability for the entry matching the speech input is obtained;

wherein the speech recognition step is configured so as to enable the recognition of any combination of fragments of a list entry for each list entry of the candidate list.

21. The method according to claim 20, wherein the fragments of the list entries of the candidate list are enrolled as a vocabulary in the speech recognizer, and

wherein the enrolment is performed so as to consider the grouping of the fragments in the list entries of the candidate list, and so as to enable the recognition of any combination of fragments within one list entry.

22. The method according to claim 20, wherein the speech recognition is based on Hidden Markov Models assigned to fragments or to subword units of fragments of the list entries of the candidate list.

23. The method according to claim 20, further comprising:

enrolling the candidate list as a vocabulary for performing the speech recognition by;

assigning a state sequence to each fragment of the candidate list; and

for each candidate list entry, connecting the final state of the state sequence of each fragment of the list entry to the initial states of the state sequences of the other fragments of the same list entry.

24. The method according to claim 23, wherein a language model is considered for determining transition probabilities between connected state sequences, the language model considering at least probabilities for an occurrence of predetermined sequences of fragments in a spoken input.

25. The method according to claim 20, further comprising:

generating a shortened candidate list from the list of entries or the candidate list by;

determining all possible permutations of predetermined fragments of a list entry for predetermined list entries of the list of entries or the candidate list;

matching each determined permutation of the predetermined fragments against the string of subword units to obtain a matching score for each permutation;

determining a total score for each predetermined list entry on the basis of the matching scores for the permutations determined for the list entry; and

generating the shortened candidate list of best matching entries from the predetermined list entries based on the total scores of the list entries,

wherein entries from the shortened candidate list are provided for being used in the vocabulary for the speech recognition.

26. The method according to claim 25, wherein the predetermined list entries for which the permutations are determined are the list entries from the list of entries or the candidate list having a number of fragments smaller than a predetermined threshold value.

27. The method according to claim 20, further comprising:

a second speech recognition step on the speech input, the second speech recognition step using a predetermined number of best matching entries from the result of first speech recognition step as a vocabulary.

28. A speech recognition system for selecting a list entry from a list of entries via speech input, the list of entries including plural list entries each comprising at least one fragment, the system comprising:

a database adapted to provide the list of entries;

a recording unit for recording a speech input;

a subword unit recognition unit adapted to generate a string of subword units from the speech input;

a candidate list generation unit adapted to generate a candidate list comprising entries from the list of entries which are a preferred match for the string of subword units; and

a speech recognition unit adapted to perform a speech recognition step on the speech input using the candidate list as a vocabulary, wherein for an entry of the candidate list, a probability for the entry matching the speech input is obtained;

wherein the speech recognition unit is further configured so as to enable the recognition of any combination of fragments of a list entry for each list entry of the candidate list.

29. A computer program product having a computer readable storage medium with computer code thereon for generating a candidate list from a list of entries in accordance with a string of subword units corresponding to a speech input, the list of entries including plural list entries each comprising at least one fragment having one or more subword units, the computer code comprising:

computer code for comparing fragments for each list entry with the string of subword units;

computer code for determining a matching score for each of the compared fragments based on the comparison, the matching score for a fragment being further based on a comparison of at least one other fragment of the same list entry with the string of subword units;

computer code for determining a total score for each list entry on the basis of the matching scores for the compared fragments of the respective list entry; and

computer code for generating the candidate list with the best matching entries from the list of entries based on the total scores of the list entries.

30. The computer program product according to claim 29, wherein the matching score for a fragment of a list entry is determined such that the matching score corresponds to a matching score for matching a combination of the fragment with at least one other fragment of the same list entry against the string of subword units.

31. The computer program product according to claim 30, wherein the determination of a total score for a list entry is based on the matching score corresponding to a matching score for a combination of fragments of the list entry, the determination being further configured so as to consider a language model comprising at least transition probabilities between the fragments of the combination.

32. The computer program product according to claim 30, wherein the computer code for determining of the matching score for the fragment is performed so as to allow any combination of fragments of a list entry.

33. The computer program product according claim 29, wherein the computer code for comparing is performed by matching each fragment of a list entry separately against the string of subword units.

34. The computer program product according to claim 33, wherein the matching score for a fragment is determined by computer code for consecutively matching the fragment against each subword unit of the string of subword units.

35. The computer program product according to claim 34, wherein the computer code for comparing of a fragment of a list entry with the string of subword units comprises:

computer code for determining cost values for the fragment by matching the fragment against a first subword unit of the string of subword units;

for the cost values determined for the fragment for the first subword unit, computer code for substituting an initial cost value by the smallest of all cost values obtained in the last step of the matching of all fragments of the list entry separately against the first subword unit, wherein the substitution is only performed if the smallest cost value is smaller than the initial cost value; and

computer code for repeating the determining of cost values and the substituting of an initial cost value of the determined cost values for the remaining subword units of the string of subword units,

wherein the computer code for matching of the fragment against a subword unit considers at least one substituted initial cost value, whereby a final cost value for the compared fragment is obtained.

36. The computer program product according to claim 29, further comprising:

computer code for determining a combination of the fragments of a list entry which best matches the string of subword units by analyzing intermediate scores determined by comparing the fragments of the list entry with a part of the string of subword units.

37. A computer program product having a computer readable storage medium with computer code thereon for generating a candidate list from a list of entries in accordance with a string of subword units corresponding to a speech input in a speech recognition system, the list of entries including plural list entries each comprising at least one fragment having one or more subword units, the computer code comprising:

computer code for comparing fragments of the list entries to the string of subword units;

computer code for determining a matching score for each fragment on the basis of the comparison, the matching score indicating how well the fragment matches the string of subword units;

computer code for determining a total score for each list entry based on the matching scores of the fragments of the respective list entry; and

computer code for generating the candidate list with the best matching entries from the list of entries based on the total scores of the list entries

wherein the computer code for comparing is performed for different context variants of a fragment, and wherein the matching score for a context variant of the fragment considers how well the context of the fragment corresponds to the context of a corresponding segment in the string of subword units.

38. The computer program product according to claim 37, wherein the context variant of a fragment is accompanied by at least one wildcard, the wildcard representing the part of the string of subword units not considered in the fragment.

39. The computer program product according to claim 37, wherein the matching score for the context variant is determined by matching the context variant including the wildcard against the string of subword units, the matching being configured such that the wildcard matches substantially uniformly against the subword units of the string.

40. The method according claim 37, wherein for each list entry, an intermediate score is determined for each of different combinations of fragments of the entry, the total score for the entry being determined from the intermediate scores.

41. The computer program product according to claim 40, wherein the intermediate scores are calculated for combinations of fragments having a matching score above a predetermined threshold value.

42. The computer program product according to claim 37, wherein the computer code for the determination of the intermediate score for a combination of fragments, the matching score of a context variant of the fragments is used which corresponds to the context of the fragments in the combination.

43. The computer program product according to claim 40, wherein an intermediate score for a combination of fragments is penalized if the combination has at least one of the following properties:

the combination overcovers the string of subword units;

fragments of the combination cover the same part of the string of subword units;

or

the combination does not cover all parts of the string of subword units.

44. The computer program product according to claim 40, wherein for predetermined fragments of the list of entries, the computer code for comparing is performed using a speech recognizer module, wherein for the remaining fragments of the list of entries, the comparing is performed using a matcher module.

45. The computer program product according to claim 37, further comprising:

computer code for providing the candidate list as second list of entries and generating a second candidate list from the second list of entries.

46. The computer program product according to claim 37, wherein an a priori probability is assigned statically or dynamically to at least one of a fragment of a list entry, a combination of fragments of a list entry and a list entry, the a priori probability being taken into account when determining the total score for the list entry.

47. The computer program product according to claim 46, wherein the a priori probabilities are determined on the basis of at least one of an information on a current position of a system implementing the method, a frequency of use of a list entry, a language model, a probability for a combination of fragments, and a probability for an ordering of fragments.

48. A computer program product including a computer readable storage medium having computer code thereon for selecting a list entry from a list of entries via speech input, the list of entries including plural list entries each comprising at least one fragment, the computer code comprising:

computer code for receiving a speech input;

computer code for generating a string of subword units from the speech input;

computer code for generating a candidate list comprising entries from the list of entries which are a preferred match for the string of subword units; and

computer code for performing a speech recognition step on the speech input using the candidate list as a vocabulary, wherein for an entry of the candidate list, a probability for the entry matching the speech input is obtained;

wherein the speech recognition step is configured so as to enable the recognition of any combination of fragments of a list entry for each list entry of the candidate list.

49. The computer program product according to claim 48, wherein the fragments of the list entries of the candidate list are enrolled as a vocabulary in the speech recognizer, and wherein the enrolment is performed so as to consider the grouping of the fragments in the list entries of the candidate list, and so as to enable the recognition of any combination of fragments within one list entry.

50. The computer program product according to claim 48, wherein the speech recognition is based on Hidden Markov Models assigned to fragments or to subword units of fragments of the list entries of the candidate list.

51. The computer program product according to claim 48, further comprising:

computer code for enrolling the candidate list as a vocabulary for performing the speech recognition by;

assigning a state sequence to each fragment of the candidate list; and

for each candidate list entry, connecting the final state of the state sequence of each fragment of the list entry to the initial states of the state sequences of the other fragments of the same list entry.

52. The computer program product according to claim 51, wherein a language model is considered for determining transition probabilities between connected state sequences, the language model considering at least probabilities for an occurrence of predetermined sequences of fragments in a spoken input.

53. The computer program product according to claim 48, further comprising:

computer code for generating a shortened candidate list from the list of entries or the candidate list by determining all possible permutations of predetermined fragments of a list entry for predetermined list entries of the list of entries or the candidate list;

computer code for matching each determined permutation of the predetermined fragments against the string of subword units to obtain a matching score for each permutation;

computer code for determining a total score for each predetermined list entry on the basis of the matching scores for the permutations determined for the list entry; and

computer code for generating the shortened candidate list of best matching entries from the predetermined list entries based on the total scores of the list entries,

wherein entries from the shortened candidate list are provided for being used in the vocabulary for the speech recognition.

54. The computer program product according to claim 53, wherein the predetermined list entries for which the permutations are determined are the list entries from the list of entries or the candidate list having a number of fragments smaller than a predetermined threshold value.

55. The computer program product according to claim 48, further comprising:

computer code for a second speech recognition step on the speech input, the second speech recognition step using a predetermined number of best matching entries from the result of first speech recognition step as a vocabulary.