System and method of recognizing letters and numbers by either speech or touch tone recognition utilizing constrained confusion matrices

• US 6,061,654 A
• Filed: 12/16/1996
• Issued: 05/09/2000
• Est. Priority Date: 12/16/1996
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Brown, Deborah W., Goldberg, Randy G., Modi, Piyush C., Rosinski, Richard R., Sachs, Richard M.
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): SOFOCLEOUS, MICHAEL D
• Application Number:
  US08/771,356
• Time in Patent Office: 1,240 Days
• Field of Search: 704/246, 704/251, 704/240, 704/236, 704/231, 704/255, 704/256, 455/563
• US Class Current: 704/275
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

A method and apparatus for recognizing an identifier entered by a user. A caller enters a predetermined identifier through a telephone handset. A signal representing the entered identifier is transmitted to a remote recognizer, which responds to the signal by producing a recognized output intended to match the entered identifier. The present invention compares this recognized identifier with a list of valid reference identifiers to determine which one of these reference identifiers most likely matches the entered identifier. In performing this determination, the present invention employs a confusion matrix, which is an arrangement of probabilities that indicate the likelihood that a given character in a particular character position of the reference identifier would be recognized by the recognizer as a character in the corresponding character position of the recognized identifier. This determination yields an identifier recognition probability for every reference identifier, and the present invention selects the reference identifier with the highest identifier recognition probability as most likely corresponding to the spoken identifier. The invention is also provided with the capability of improving the recognition accuracy of the confusion matrix by eliminating from consideration the most often confused characters.

Claims

1. A method of recognizing an identifier entered by a user, the identifier including a first plurality of predetermined characters, wherein the characters are selected from a first set of characters, the first set of characters having a first total number of 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, each one of the different plurality of predetermined characters belonging to the first set of characters;

c) providing a first arrangement of character recognition probabilities, the first arrangement of character recognition probabilities encompassing a second set of characters having a second total number of characters and is a superset of the characters of the first set of characters;

d) producing a constrained arrangement of character recognition probabilities by constraining the first arrangement of character recognition probabilities to encompass a third set of characters constituting a subset of the second set of characters;

e) obtaining, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, from the constrained arrangement of character recognition probabilities, a probability that a character in the at least one reference identifier is recognized as a character found in the corresponding character position in the recognized identifier;

f) determining an identifier recognition probability based on the obtained probabilities;

g) repeating steps e) and f) for every reference identifier in the plurality of reference identifiers, each one of the plurality of reference identifiers being associated with a corresponding identifier recognition probability; and

h) selecting the reference identifier most likely matching the entered identifier based on the plurality of obtained recognition probabilities.

2. The method according to claim 1, wherein each one of the entered identifier, the recognized identifier, and the plurality of reference identifiers comprises a plurality of alphanumeric characters.

3. The method according to claim 1, wherein each one of the entered identifier, the recognized identifier, and the plurality of reference identifiers comprises a plurality of numbers.

4. The method according to claim 1, wherein each one of the entered identifier, the recognized identifier, and the plurality of reference identifiers comprises a plurality of alphabetical letters.

5. The method according to claim 1, wherein the reference identifier selected in step h) corresponds to the highest identifier recognition probability.

6. The method according to claim 1, wherein the first arrangement of character recognition probabilities and the constrained arrangement of character recognition probabilities are each obtained from an external storage medium.

7. The method according to claim 1, wherein the first arrangement of character recognition probabilities and the constrained arrangement of character recognition probabilities are each obtained from a data input device.

8. The method according to claim 1, wherein the first arrangement of character recognition probabilities and the constrained arrangement of character recognition probabilities are each obtained from a memory device.

9. The method according to claim 1, wherein the step d) of providing a constrained arrangement of character recognition probabilities comprises eliminating from consideration at least one character from the first arrangement of character recognition probabilities.

10. The method according to claim 1, wherein the first arrangement of character recognition probabilities and the constrained arrangement of character recognition probabilities are each arranged as at least one confusion matrix.

11. The method according to claim 10, wherein the at least one confusion matrix corresponds to a plurality of confusion matrices including at least one confusion matrix corresponding to alphabetical letters only, at least one confusion matrix corresponding to numbers only, and at least one confusion matrix corresponding to a combination of alphabetical letters and numbers.

12. The method according to claim 1, wherein the entered identifier is entered by the user speaking the identifier into a voice input device.

13. The method according to claim 12, wherein the recognized identifier is provided by a speech recognizer.

14. The method according to claim 1, wherein the entered identifier is entered by the user through a touch-tone input device.

15. The method according to claim 14, wherein the recognized identifier is provided by a touch-tone recognizer.

16. The method according to claim 1, further comprising the steps of:

i) prompting the user to indicate whether the selected reference identifier matches the entered identifier;

j) if the user indicates that the selected reference identifier matches the entered identifier, acknowledging the user as having entered a valid identifier;

k) if the user indicates that the selected reference identifier does not match the entered identifier;

l) providing a second plurality of reference identifiers, the second plurality of reference identifiers including every reference identifier except the selected reference identifier;

m) repeating steps e) and f) for every reference identifier included in the second plurality of reference identifiers, each one of the reference identifiers of the second plurality of reference identifiers being associated with a second corresponding identifier recognition probability; and

n) selecting from the second plurality of reference identifiers the reference identifier most likely matching the entered identifier based on the second corresponding identifier recognition probabilities.

17. The method according to claim 16, wherein the reference identifier selected in step n) corresponds to the highest identifier recognition probability of the second corresponding identifier recognition probabilities.

18. The method according to claim 16, further comprising the steps of:

o) prompting the user to indicate whether the reference identifier selected in step n) matches the entered identifier;

p) if the user indicates that the reference identifier selected in step n) matches the entered identifier, acknowledging the user as having entered a valid identifier;

q) if the user indicates that the reference identifier selected in step n) does not match the reference identifier selected in step n);

r) reinstating the reference identifier selected in step h) into a third plurality of reference identifiers, the third plurality of reference identifiers firther including every other reference identifier except for the reference identifier selected in step n);

s) repeating steps e) and f) for every reference identifier included in the third plurality of reference identifiers, every reference identifier in the third plurality of reference identifiers being associated with a new corresponding identifier recognition probability; and

t) selecting from the third plurality of reference identifiers the reference identifier most likely matching the entered identifier based on the new corresponding identifier recognition probabilities.

19. The method according to claim 18, wherein the reference identifier selected in step t) corresponds to the highest recognition probability of the new corresponding identifier recognition probabilities.

20. The method according to claim 1, wherein before the selecting step h), the method further comprises the step of determining a subset of the plurality of reference identifiers, each of the reference identifiers included in the subset corresponding to an identifier recognition probability higher than a predetermined threshold, wherein the reference identifier selected in step h) is selected from the subset of the plurality of reference identifiers.

21. The method according to claim 20, further comprising the steps of:

i) prompting the user to indicate whether the reference identifier selected in step h) matches the entered identifier;

j) if the user indicates that the selected reference identifier matches the entered identifier, acknowledging that the user has entered a valid identifier;

k) if the user indicates that the selected reference identifier does not match the entered identifier;

l) selecting the reference identifier corresponding to the next highest identifier recognition probability within the subset of the plurality of reference identifiers;

m) prompting the user to indicate whether the reference identifier selected in step l) corresponds to the entered identifier;

n) if the user indicates that the reference identifier selected in step l) matches the entered identifier, acknowledging that the user has entered a valid identifier;

o) if the user indicates that the reference identifier selected in step l) does not match the entered identifier, repeating steps l) through n) in accordance with the reference identifiers included in the subset of the plurality of reference identifiers.

22. An apparatus for recognizing an identifier entered by a user, the entered identifier including a first plurality of predetermined characters, wherein the characters are selected from a first set of characters, the first set of characters including a first total number of characters, the system comprising:

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

a first memory that stores a plurality of reference identifiers, each one of the reference identifiers comprising a different plurality of predetermined characters, each one of the different plurality of predetermined characters belonging to the first set of characters;

a second memory that stores a first arrangement of character recognition probabilities, the first arrangement of character recognition probabilities encompassing a second set of characters having a second total number of characters and is a superset of the characters of the first set of characters, each of the character recognition probabilities representing a probability that a certain recognized character corresponds to a certain entered character; and

a third memory that stores constraint data; and

a processor, in communication with the means for receiving, the first memory, the second memory, and the third memory, that produces in accordance with the constraint data of the third memory a constrained arrangement of character recognition probabilities, the constrained arrangement of character recognition probabilities being produced by constraining the first arrangement of character recognition probabilities to encompass a third set of characters constituting a subset of the second set of characters, the processor determining for every one of the plurality of reference identifiers a corresponding identifier recognition probability, each of the corresponding identifier recognition probabilities being determined on the basis of the constrained arrangement of character recognition probabilities, the processor selecting the reference identifier most likely matching the entered identifier based on the identifier recognition probabilities.

23. The apparatus according to claim 22, wherein the selected reference identifier corresponds to the highest identifier recognition probability.

24. The apparatus according to claim 22, wherein each one of the entered identifier, the recognized identifier, and the plurality of reference identifiers comprises a plurality of alphanumeric characters.

25. The apparatus according to claim 22, wherein each one of the entered identifier, the recognized identifier, and the plurality of reference identifiers comprises a plurality of numbers.

26. The apparatus according to claim 22, wherein each one of the entered identifier, the recognized identifier, and the plurality of reference identifiers comprises a plurality of alphabetical letters.

27. The apparatus according to claim 22, wherein the first arrangement of character recognition probabilities and the constrained arrangement of character recognition probabilities are each arranged as at least one confusion matrix.

28. The apparatus according to claim 27, further comprising a selecting means, in communication with the processor, for selecting among the at least one confusion matrix.

29. The apparatus according to claim 27, wherein the at least one confusion matrix corresponds to a plurality of confusion matrices including at least one confusion matrix corresponding to alphabetical letters only, at least one confusion matrix corresponding to numbers only, and at least one confusion matrix corresponding to a combination of alphabetical letters and numbers.

30. In a speech recognition system for recognizing an identifier entered by a user in accordance with a constrained arrangement of character recognition probabilities, the identifier comprising a first plurality of predetermined characters, wherein the characters are selected from a first set of characters, the first set of characters including a first total number of characters, a method of producing the constrained arrangement of character recognition probabilities, comprising:

a) providing a first arrangement of character recognition probabilities, the first arrangement of character recognition probabilities encompassing a second set of characters having a second total number of characters and is a superset of the characters of the first set of characters; and

b) producing the constrained arrangement of character recognition probabilities by constraining the first arrangement of character recognition probabilities to encompass a third set of characters constituting a subset of the second set of characters, wherein each character recognition probability represents a probability that a first character entered by the user will be recognized as one of the first character and a second character.

31. The method according to claim 30, where in the step b) of providing a constrained arrangement of character recognition probabilities comprises eliminating from con sideration at least one character from the first arrangement of character recognition probabilities.