Statistical database correction of alphanumeric account numbers for speech recognition and touch-tone recognition

• US 6,137,863 A
• Filed: 12/13/1996
• Issued: 10/24/2000
• Est. Priority Date: 12/13/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., Marcus, Stephen Michael, Rosinski, Richard R., Stern, Benjamin J.
• Primary Examiner(s): WEAVER, SCOTT LOUIS
• Application Number:
  US08/763,382
• Time in Patent Office: 1,411 Days
• Field of Search: 379/88.01, 379/88.02, 379/88.03, 379/88.04, 379/386, 704/240, 704/239, 704/238, 704/237, 704/236, 704/251, 704/252, 382/159, 382/160, 382/161, 382/181, 382/185, 382/209
• US Class Current: 379/88.01
• CPC Class Codes: G10L 15/18 using natural language modelling
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: H04M 11/066 Telephone sets adapted for data transmision

Abstract

A method and apparatus for recognizing an identifier entered by a user. A caller enters a predetermined identifier through a voice input device or a touch-tone keypad of a telephone handset. 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 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 entered identifier.

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) obtaining from a stored data structure, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, a previously determined 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, each probability in the stored data structure representing a quantification of a tendency of one predetermined character to be recognized as one of the predetermined character and another predetermined character, wherein the obtained probabilities are arranged as at least one confusion matrix, and wherein the step of obtaining includes the step of selecting among the at least one confusion matrix;

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

e) repeating steps c) and d) 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

f) 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 obtained probabilities are arranged as at least one confusion matrix.

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

16. The method of claim 1, wherein the obtained probabilities are obtained from an external storage medium.

17. The method of claim 1, wherein the obtained probabilities are obtained from a data input device.

18. The method of claim 1, wherein the obtained probabilities are obtained from a memory device.

6. 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) obtaining, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, 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, wherein the obtained probabilities are arranged as at least one confusion matrix, and wherein the step of obtaining includes the step of selecting among the at least one confusion matrix;

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

e) repeating steps c) and d) 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

f) selecting the reference identifier most likely matching the entered identifier based on the plurality of obtained recognition probabilities, wherein the obtained probabilities are arranged as at least one confusion matrix, and wherein the at least one confusion matrix corresponds to a plurality of confusion matrices that includes 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.

7. 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) obtaining from a stored data structure, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, a previously determined 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, each probability in the stored data structure representing a quantification of a tendency of one predetermined character to be recognized as one of the predetermined character and another predetermined character;

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

e) repeating steps c) and d) 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

f) selecting the reference identifier most likely matching the entered identifier based on the plurality of obtained recognition probabilities, wherein the entered identifier is entered by the user speaking the identifier into a voice input device.

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

10. 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) obtaining from a stored data structure, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, a previously determined 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, each probability in the stored data structure representing a quantification of a tendency of one predetermined character to be recognized as one of the predetermined character and another predetermined character;

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

e) repeating steps c) and d) 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

f) selecting the reference identifier most likely matching the entered identifier based on the plurality of obtained recognition probabilities, wherein the entered identifier is entered by the user through a touch-tone input device.

11. The method of claim 10, wherein the recognized identifier is provided by a touch-tone recognizer.

12. 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) obtaining, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, 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;

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

e) repeating steps c) and d) 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;

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

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

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

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

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

k) repeating steps c) and d) 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 recognition probability; and

l) 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.

13. The method according to claim 12, wherein the reference identifier selected in step l) corresponds to the highest identifier recognition probability of the second corresponding identifier recognition probabilities.

14. The method of claim 12, further comprising the steps of:

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

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

o) if the user indicates that the reference identifier selected in step l) does not match the reference identifier selected in step l);

p) reinstating the reference identifier selected in step f) into a third plurality of reference identifiers, the third plurality of reference identifiers further including every other reference identifier except for the reference identifier selected in step l);

q) repeating steps c) and d) 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

r) 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.

15. The method according to claim 14, wherein the reference identifier selected in step r) corresponds to the highest recognition probability of the new corresponding identifier recognition probabilities.

19. 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) obtaining, for each character position in at least one of the reference identifiers and each character position in the recognized identifier, 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;

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

e) repeating steps c) and d) 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

f) selecting the reference identifier most likely matching the entered identifier based on the plurality of obtained recognition probabilities, wherein before the selecting step f), 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 f) is selected from the subset of the plurality of reference identifiers.

20. The method of claim 19, further comprising the steps of:

g) prompting the user to indicate whether the reference identifier selected in step f) matches the entered identifier;

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

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

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

k) prompting the user to indicate whether the reference identifier selected in step j) corresponds to the entered identifier;

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

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

21. An apparatus for recognizing an identifier entered by a user, the entered identifier including a first plurality of predetermined 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;

a second memory that stores a plurality of probabilities, each probability representing a quantification of a tendency of one predetermined character to be recognized as one of the predetermined character and another predetermined character, the plurality of probabilities being arranged in the second memory as at least one confusion matrix;

a processor, in communication with the means for receiving, the first memory, and the second memory, and 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 plurality of probabilities stored in the second memory, the processor selecting the reference identifier most likely matching the entered identifier based on the identifier recognition probabilities; and

selecting means, in communication with the processor, for selecting among the at least one confusion matrix.

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

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

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

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

26. The apparatus according to claim 21, wherein the at least one confusion matrix corresponds to a plurality of confusion matrices and wherein the plurality of confusion matrices includes 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.