Statistical option generator for alpha-numeric pre-database speech recognition correction

• US 6,223,158 B1
• Filed: 02/04/1998
• Issued: 04/24/2001
• Est. Priority Date: 02/04/1998
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Goldberg, Randy G.
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Lerner, Martin
• Application Number:
  US09/018,449
• Time in Patent Office: 1,175 Days
• Field of Search: 704/231, 704/251, 704/252, 704/254, 704/255, 704/256, 704/257, 704/275, 704/240
• US Class Current: 704/252
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 2015/085 Methods for reducing search complexity, pruning

Abstract

A method and apparatus for recognizing an input identifier entered by a user. A caller enters a predetermined identifier through a voice input device. A signal representing the entered identifier is transmitted to a remote recognizer, which responds to the identifier signal by producing a recognized output intended to match the entered identifier. The present invention then generates a set of option identifiers, each option identifier having a possibility of matching the input identifier. The set of option identifiers is then reduced to a set of candidate identifiers by eliminating those option identifiers that are not found among a set of stored reference identifiers. The present invention selects a match for the input identifier from the set of candidate identifiers.

Claims

1. A method of recognizing an identifier entered by a user, the identifier including a first plurality of predetermined characters, the method comprising the steps of:

a) providing a recognized identifier based on the entered identifier, the recognized identifier comprising a second plurality of predetermined characters;

b) providing a plurality of reference identifiers, each one of the plurality of reference identifiers comprising a different plurality of predetermined characters;

c) generating a new plurality of identifiers and arranging the new identifiers as a set of option identifiers, each option identifier comprising a different plurality of characters determined on the basis of the recognized identifier and on a plurality of confusion sets and determined independently of the plurality of reference identifiers, each confusion set comprising a different character collection, wherein the recognized identifier is included in the set of option identifiers;

d) reducing the set of option identifiers to a set of candidate identifiers on the basis of the reference identifiers; and

e) selecting one candidate identifier as matching the input identifier.

2. The method according to claim 1, wherein the step (c) comprises:

(i) obtaining at least one character from at least one current character position of the recognized identifier;

(ii) determining a confusion set to which each obtained character belongs;

(iii) replacing each obtained character in the current character position of the recognized identifier and of any previously created option identifier with at least one character of the associated confusion set determined in step (ii), each replacement operation creating a new option identifier;

(iv) obtaining a character from a next character position of the recognized identifier and any previously created option identifier; and

(v) repeating steps (ii)-(iv) until a predetermined number of option identifiers have been created.

3. The method according to claim 1, wherein the step (d) comprises eliminating from the set of option identifiers those option identifiers not found in the plurality of reference identifiers, the remaining option identifiers comprising the set of candidate identifiers.

4. The method according to claim 1, wherein the step (e) comprises:

(i) prompting the user with each candidate identifier until the user confirms that a prompted candidate identifier matches the input identifier; and

(ii) ceasing, if the user has not confirmed any prompted candidate identifier, the prompting in step (i) when the user is prompted with all the candidate identifiers.

5. A method of recognizing an identifier entered by a user, the identifier including a first plurality of predetermined characters, the method comprising the steps of:

a) providing a recognized identifier based on the entered identifier, the recognized identifier comprising a second plurality of predetermined characters;

b) determining an associative weighting for the recognized identifier;

c) providing a plurality of reference identifiers, each one of the plurality of reference identifiers comprising a different plurality of predetermined characters;

d) generating a set of option identifiers, each option identifier comprising a different plurality of characters determined on the basis of the recognized identifier and on a plurality of confusion sets, each confusion set comprising a different character collection, wherein the recognized identifier is included in the set of option identifiers;

e) determining an associative weighting for at least some of the option identifiers;

f) reducing the set of option identifiers to a set of candidate identifiers on the basis of the reference identifiers; and

g) selecting one candidate identifier as matching the input identifier on the basis of the associative weighting of the selected candidate identifier.

6. The method according to claim 5, wherein the step (d) comprises:

(i) obtaining at least one character from at least one current character position of the recognized identifier;

(ii) determining a confusion set to which each obtained character belongs;

(iii) replacing each obtained character in the current character position of the recognized identifier and of any previously created option identifier with at least one character of the associated confusion set determined in step (ii), each replacement operation creating a new option identifier;

(iv) obtaining a character from a next character position of the recognized identifier and any previously created option identifier; and

(v) repeating steps (ii)-(iv) until a predetermined number of option identifiers have been created.

7. The method according to claim 5, wherein each confusion set is associated with a character identity weighting and a character change weighting, each character identity weighting of each confusion set representing a probability of recognizing each character within an associated confusion set as itself, and each character change weighting representing a probability of recognizing one character within an associated confusion set as another character within the same confusion set.

8. The method according to claim 7, wherein the step b) comprises assigning each character of the recognized identifier a character identity weighting, the associative weighting of the recognized identifier being a function of the character identity weightings of the characters comprising the recognized identifier.

9. The method according to claim 8, wherein the associative weighting of the recognized identifier is a product of the character identity weightings of the characters comprising the recognized identifier.

10. The method according to claim 7, wherein each of the character change weightings and character identity weightings of each confusion set is derived from a confusion matrix.

11. The method according to claim 7, wherein for each option identifier other than the recognized identifier, the step e) comprises:

(i) obtaining a first generated option identifier;

(ii) eliminating a current generated option identifier other than the recognized identifier if any character of the current option identifier is not from the same confusion set as a character in a corresponding character position of the recognized identifier;

(iii) assigning, if each character of the current option identifier is from the same confusion set as the character in the corresponding character position of the recognized identifier, to each character of the current option identifier one of the character change weighting and the character identity weighting of the corresponding confusion set to which each character of the option identifier belongs;

(iv) determining the associative weighting for the current option identifier as a function of the character weightings determined in step (iii);

(v) repeating steps (ii)-(iv) for each generated option identifier other than the recognized identifier.

12. The method according to claim 11, wherein the step (iv) comprises:

(vi) multiplying together the assigned character weightings of step (iii).

13. The method according to claim 12, wherein the step (f) comprises eliminating from the set of option identifiers those option identifiers not found in the plurality of reference identifiers, the remaining option identifiers comprising the set of candidate identifiers.

14. The method according to claim 13, wherein the step (g) comprises selecting the candidate identifier associated with the highest associative weighting.

15. The method according to claim 5, wherein:

the set of option identifiers is generated as a new plurality of identifiers that is independent of the plurality of reference identifiers.

16. The method according to claim 5, wherein:

each one of the associative weighting for the recognized identifier and the associative weightings for the at least some of the option identifiers is a probabilistic value.

17. A method of recognizing an identifier entered by a user, the identifier including a first plurality of predetermined characters, the method comprising the steps of:

a) providing a recognized identifier based on the entered identifier, the recognized identifier comprising a second plurality of predetermined characters;

b) determining an associative weighting for the recognized identifier;

c) providing a plurality of reference identifiers, each one of the plurality of reference identifiers comprising a different plurality of predetermined characters;

d) generating a set of option identifiers, each option identifier comprising a different plurality of characters determined on the basis of the recognized identifier and on an arrangement of probabilistic values, each probabilistic value representing a probability of recognizing an associated character as itself or as another character, wherein the recognized identifier is included in the set of option identifiers;

e) determining an associative weighting for each one of the option identifiers;

f) reducing the set of option identifiers to a set of candidate identifiers on the basis of the reference identifiers; and

g) selecting one candidate identifier as matching the input identifier on the basis of the associative weighting of the selected candidate identifier.

18. The method according to claim 17, wherein the step b) comprises:

(i) obtaining a character weighting for each character of the recognized identifier, each character weighting of each character of the recognized identifier representing a probability of recognizing the associated character of the recognized identifier as itself, each character weighting in step (i) being obtained from the arrangement of probabilistic values;

(ii) ignoring each probabilistic value used as a character weighting in step (i) after step (i) is performed; and

(iii) determining the associative weighting of the recognized identifier as a function of the character weightings of each character of the recognized identifier determined in step (i).

19. The method according to claim 18, wherein the step (d) comprises:

(iv) obtaining a character from a current character position of each previously generated option identifier;

(v) determining for the current character position of each previously generated option identifier a character that is most likely confused with the character currently occupying the current character position of each previously generated option identifier, the determination of step (v) being determined on the basis of the arrangement of probabilistic values still under consideration;

(vi) repeating step (v) for each character position of each previously generated option identifier;

(vii) selecting from among the character confusions determined in steps (v)-(vi) the character confusion associated with the highest probabilistic value of the arrangement of probabilistic values still under consideration;

(viii) eliminating from further consideration the probabilistic value associated with the character confusion selected in step (vii);

(ix) creating a new option identifier on the basis of the character confusion selected in step (vii); and

(x) repeating steps (iv)-(ix) until a predetermined number of option identifiers have been created.

20. The method according to claim 19, wherein the arrangement of probabilistic values comprises at least one confusion matrix.

21. The method according to claim 19, wherein the associative weighting of each option identifier is determined as a function of at least a portion of values maintained in the arrangement of probabilistic values.

22. The method according to claim 17, wherein the step (f) comprises eliminating from the set of option identifiers those option identifiers not found in the plurality of reference identifiers, the remaining option identifiers comprising the set of candidate identifiers.

23. The method according to claim 17, wherein the step (g) comprises selecting the candidate identifier associated with the highest associative weighting.

24. The method according to claim 17, wherein:

the set of option identifiers is generated as a new plurality of identifiers that is independent of the plurality of reference identifiers.

25. The method according to claim 17, wherein:

each one of the associative weighting for the recognized identifier and the associative weightings for the option identifiers is a probabilistic value.

26. The apparatus according to claim 17, wherein:

each one of the associative weighting for the recognized identifier and the associative weightings for the option identifiers is a probabilistic value.

27. An apparatus for recognizing an identifier entered by a user, the indentifier including a first plurality of predetermined characters, the apparatus comprising:

a) first means for providing a recognized identifier based on the entered identifier, the recognized identifier comprising a second plurality of predetermined characters;

b) second means for providing a plurality of reference identifiers, each one of the plurality of reference identifiers comprising a different plurality of predetermined characters;

c) means for generating a new plurality of identifiers and arranging the new identifiers as a set of option identifiers, each option identifier comprising a different plurality of characters determined on the basis of the recognized identifier and on a plurality of confusion sets and determined independently of the plurality of reference identifiers, each confusion set comprising a different character collection, wherein the recognized identifier is included in the set of option identifiers;

d) means for reducing the set of option identifiers to a set of cndidate identifiers on the basis of the reference identifiers; and

e) first means for selecting one candidate identifier as matching the input identifier.

28. The apparatus according to claim 27, wherein the means for generating comprises:

(i) first means for obtaining at least one character from at least one current character position of the recognized identifier;

(ii) means for determining a confusion set to which each obtained character belongs;

(iii) means for replacing each obtained character in the current character position of the recognized identifier and of any previously created option identifier with at least one character of the associated confusion set determined by the means for determining, each replacement operation creating a new option identifier; and

(iv) second means for obtaining a character from a next character position of the recognized identifier and any previously created option identifier.

29. The apparatus according to claim 27, wherein the means for eliminating comprises means for eliminating from the set of option identifiers those option identifiers not found in the plurality of reference identifiers, the remaining option identifiers comprising the set of candidate identifiers.

30. The apparatus according to claim 27, wherein the means for selecting comprises:

(i) means for prompting the user with each candidate identifier until the user confirms that a prompted candidate identifier matches the input identifier; and

(ii) means for ceasing the means for prompting when the user is prompted with all the candidate identifiers.

31. An apparatus for recognizing an identifier entered by a user, the identifier including a first plurality of predetermined characters, the apparatus comprising:

a) first means for providing a recognized identifier based on the entered identifier, the recognized identifier comprising a second plurality of predetermined characters;

b) first means for determining an associative weighting for the recognized identifier;

c) second means for providing a plurality of reference identifiers, each one of the plurality of reference identifiers comprising a different plurality of predetermined characters;

d) means for generating a set of option identifiers, each option identifier comprising a different plurality of characters determined on the basis of the recognized identifier and on a plurality of confusion sets, each confusion set comprising a different character collection, wherein the recognized identifier is included in the set of option identifiers;

e) second means for determining an associative weighting for at least some of the option identifiers;

f) means for reducing the set of option identifiers to a set of candidate identifiers on the basis of the reference identifiers; and

g) means for selecting one candidate identifier as matching the input identifier on the basis of the associative weighting of the selected candidate identifier.

32. The apparatus according to claim 31, wherein the means for generating comprises:

(i) first means for obtaining at least one character from at least one current character position of the recognized identifier;

(ii) third means for determining a confusion set to which each obtained character belongs;

(iii) means for replacing each obtained character in the current character position of the recognized identifier and of any previously created option identifier with at least one character of the associated confusion set determined by the third means for determining, each replacement operation creating a new option identifier; and

(iv) second means for obtaining a character from a next character position of the recognized identifier and any previously created option identifier.

33. The apparatus according to claim 31, wherein each confusion set is associated with a character identity weighting and a character change weighting, each character identity weighting of each confusion set representing a probability of recognizing any character within an associated confusion set as itself, and each character change weighting representing a probability of recognizing any character within an associated confusion set as another character within the same confusion set.

34. The apparatus according to claim 33, wherein the first means for determining comprises:

(i) first means for obtaining a character identity weighting for each character of the recognized identifier, each character identity weighting of each character of the recognized identifier representing a probability of recognizing the associated character of the recognized identifier as itself; and

(ii) third means for determining the associative weighting of the recognized identifier as a function of the character identity weighting of each character of the recognized identifier determined by the first means for obtaining.

35. The apparatus according to claim 34, wherein the third means for determining comprises means for multiplying together each of the character identity weightings of each character of the recognized identifier.

36. The apparatus according to claim 33, wherein each character identity weighting and each character change weighting is derived from a confusion matrix.

37. The apparatus according to claim 33, wherein for each option identifier other than the recognized identifier, the second means for determining comprises:

(iii) first means for eliminating any option identifier other than the recognized identifier if any character in the option identifier is not from the same confusion set as a character in a corresponding character position of the recognized identifier;

(iv) fourth means for determining the confusion set to which each character of any remaining option identifier belongs;

(v) second means for obtaining for each character of each remaining option identifier one of the character identity weighting and the character change weighting associated with each confusion set determined by the fourth means for determining; and

(vi) fifth means for determining the associative weighting for any remaining option identifier as a function of the character weightings determined by the second means for obtaining.

38. The apparatus according to claim 37, wherein the fifth means for determining comprises:

(vi) means for assigning to each character position of each remaining option identifier one of the character identity weighting and character change weighting determined by the second means for obtaining; and

(vii) means for multiplying together the assigned character weightings assigned by the means for assigning.

39. The apparatus according to claim 38, wherein the means for reducing comprises second means for eliminating from the set of option identifiers those option identifiers not found in the plurality of reference identifiers, the remaining option identifiers comprising the set of candidate identifiers.

40. The apparatus according to claim 39, wherein the means for selecting selects the candidate identifier associated with the highest associative weighting.

41. The apparatus according to claim 31, wherein:

the set of option identifiers is generated as a new plurality of identifiers that is independent of the plurality of reference identifiers.

42. The apparatus according to claim 31, wherein:

each one of the associative weighting for the recognized identifier and the associative weightings for the at least some of the option identifiers is a probabilistic value.

43. An apparatus for recognizing an identifier entered by a user, the identifier including a first plurality of predetermined characters, the apparatus comprising:

a) first means for providing a recognized identifier based on the entered identifier, the recognized identifier comprising a second plurality of predetermined characters;

b) first means for determining an associative weighting for the recognized identifier;

c) second means for providing a plurality of reference identifiers, each one of the plurality of reference identifiers comprising a different plurality of predetermined characters;

d) first means for generating a set of option identifiers, each option identifier comprising a different plurality of characters determined on the basis of the recognized identifier and on an arrangement of probabilistic values, each probabilistic value representing a probability of recognizing an associated character as one of itself and another character, wherein the recognized identifier is included in the set of option identifiers;

e) second means for determining an associative weighting for each one of the option identifiers;

f) means for reducing the set of option identifiers to a set of candidate identifiers on the basis of the reference identifiers; and

g) first means for selecting one candidate identifier as matching the input identifier on the basis of the associative weighting of the selected candidate identifier.

44. The apparatus according to claim 43, wherein the first means for determining comprises:

(i) first means for obtaining a character weighting for each character of the recognized identifier, each character weighting of each character of the recognized identifier representing a probability of recognizing the associated character of the recognized identifier as itself, each character weighting being obtained from the arrangement of probabilistic values;

(ii) first means for eliminating from further consideration each probabilistic value used as a character weighting by the means for obtaining; and

(iii) third means for determining the associative weighting of the recognized identifier as a function of the character weightings of each character of the recognized identifier obtained by the first means for obtaining.

45. The apparatus according to claim 44, wherein the first means for generating comprises:

(iv) second means for obtaining a character from a current character position of each previously generated option identifier;

(v) fourth means for determining for the current character position of each previously generated option identifier a character that is most likely confused with the character currently occupying the current character position of each previously generated option identifier, the determination performed by the fourth means for determining being accomplished on the basis of the arrangement of probabilistic values still under consideration;

(vi) second means for selecting from among the character confusions determined by the fourth means for determining the character confusion associated with the highest probabilistic value of the arrangement of probabilistic values still under consideration;

(vii) second means for eliminating from further consideration the probabilistic value associated with the character confusion selected by the second means for selecting; and

(ix) means for creating a new option identifier on the basis of the character confusion selected by the second means for selecting.

46. The apparatus according to claim 45, wherein the arrangement of probabilistic values comprises at least one confusion matrix.

47. The apparatus according to claim 46, wherein the associative weighting of each option identifier is determined as a function of at least a portion of values maintained in the arrangement of probabilistic values.

48. The apparatus according to claim 43, wherein the means for reducing comprises means for eliminating from the set of option identifiers those option identifiers not found in the plurality of reference identifiers, the remaining option identifiers comprising the set of candidate identifiers.

49. The apparatus according to claim 43, wherein the first means for selecting selects the candidate identifier associated with the highest associative weighting.

50. The apparatus according to claim 43, wherein:

the set of option identifiers is generated as a new plurality of identifiers that is independent of the plurality of reference identifiers.