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

• US 6,400,805 B1
• Filed: 06/15/1998
• Issued: 06/04/2002
• Est. Priority Date: 06/15/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., Marcus, Stephen Michael, Rosinski, Richard R., Stern, Benjamin J., Brown, Deborah W.
• Primary Examiner(s): Tsang, Fan
• Assistant Examiner(s): Foster, Roland G.
• Application Number:
  US09/097,769
• Time in Patent Office: 1,450 Days
• Field of Search: 379/88-1-, 704/236-240, 704/243, 704/251, 704/252, 704/270, 704/275, 382/159-161, 382/181, 382/185, 382/209, 455/563
• US Class Current: 379/88.01
• CPC Class Codes: H04M 1/271 controlled by voice recognition

Abstract

A method and apparatus recognize 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 compares each character of the recognized identifier with a character in a corresponding character position of each reference identifier in light of a plurality of confusion sets. On the basis of this comparison, the set of reference identifiers is reduced to a candidate set of reference identifiers, from which a reference identifier that matches the input identifier provided by the user.

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) providing a plurality of confusion sets, each confusion set grouping together a different set of character members;

d) comparing at least one character in the recognized identifier with a character in a corresponding character position of a current reference identifier to determine which characters in the recognized identifier do not correspond to the characters in the corresponding character positions of the current reference identifier;

e) eliminating the current reference identifier if the character of any character position of the recognized identifier does not match the character in the corresponding character position of the current reference identifier and if the characters in the corresponding character positions of the recognized identifier and the current reference identifier are not from the same confusion set;

f) repeating steps d) and e) for every reference identifier, the remaining non-eliminated reference identifiers comprising a set of candidate reference identifiers;

g) reducing, if the set of candidate reference identifiers includes more than one reference identifier, the set of candidate of reference identifiers to a single reference identifier in accordance with a set of predetermined criteria; and

h) selecting the candidate reference identifier remaining in the set of candidate reference identifiers as corresponding to the input identifier.

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 plurality of confusion sets is derived from at least one confusion matrix.

6. The method of claim 1, wherein the entered identifier is entered by the user speaking the identifier into a voice input device.

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

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

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

10. The method according to claim 1, wherein the step g) comprises:

i) prompting the user with each candidate reference identifier until the user provides a positive confirmation indicating that a prompted candidate reference identifier corresponds to the input identifier; and

ii) ceasing the prompting in step i) if the user has been prompted with each candidate reference identifier.

11. The method according to claim 1, wherein the step g) comprises:

i) assigning an associative weighting to each one of the set of candidate reference identifiers; and

ii) selecting the candidate reference identifier with the highest associating weighting.

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

iii) assigning a character change weighting and a character identity weighting to each one of the plurality of confusion sets

iv) going to a first one of the set of candidate reference identifiers;

v) determining for each character position of the candidate reference identifier the confusion set to which the character occupying the character position belongs;

vi) determining for each character position of the candidate reference identifier whether the character included therein is the same as the character of the corresponding character position of the misrecognized identifier;

vii) assigning to each character position of the candidate reference identifier one of the character change weighting and the character identity weighting of the confusion set associated with the character occupying each character position of the candidate reference identifier;

viii) determining an associative weighting for the candidate reference identifier on the basis of the character weightings assigned to each character position in step vii); and

ix) repeating steps v)-viii) for each candidate reference identifier.

13. The method according to claim 12, wherein the step viii) comprises multiplying together each of the one of the character change weightings and character identity weightings assigned to each character position of the candidate reference identifier.

14. 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) 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) third means for providing a plurality of confusion sets, each confusion set grouping together a different set of character members;

d) means for comparing at least one character in the recognized identifier with a character in a corresponding character position of a current reference identifier to determine which characters in the recognized identifier correspond to the character in the corresponding character positions of the current reference identifier;

e) means for eliminating the current reference identifier if the character of any character position of the recognized identifier does not match the character in the corresponding character position of the current reference identifier and if the characters in the corresponding character positions of the recognized identifier and the current reference identifier are not from the same confusion set;

f) means for repeating the operation of the means for comparing and the means for eliminating for every reference identifier, the remaining non-eliminated reference identifiers comprising a set of candidate reference identifiers;

g) means for reducing, if the set of candidate reference identifiers includes more than one reference identifier, the set of candidate reference identifiers to a single reference identifier in accordance with a set of predetermined criteria; and

h) first means for selecting the candidate reference identifier remaining in the set of candidate reference identifiers as corresponding to the input identifier.

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

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

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

18. The apparatus according to claim 14, wherein the plurality of confusion sets is derived from at least one confusion matrix.

19. The apparatus of claim 14, wherein the entered identifier is entered by the user speaking the identifier into a voice input device.

20. The apparatus according to claim 19, wherein the recognized identifier is provided by a speech recognizer.

21. The apparatus of claim 14, wherein the entered identifier is entered by the user through a touch-tone input device.

22. The apparatus of claim 21, wherein the recognized identifier is provided by a touch-tone recognizer.

23. The apparatus according to claim 14, wherein the step means for reducing comprises:

i) means for prompting the user with each candidate reference identifier until the user provides a positive confirmation indicating that a prompted candidate reference identifier corresponds to the input identifier; and

ii) means for ceasing the prompting means if the user has been prompted with each candidate reference identifier.

24. The apparatus according to claim 14, wherein the means for reducing comprises:

i) first means for assigning an associative weighting to each one of the set of candidate reference identifiers; and

ii) second means for selecting the candidate reference identifier with the highest associative weighting.

25. The apparatus according to claim 24, wherein the first means for assigning comprises:

iii) second means for assigning a character change weighting and a character identity weighting to each one of the plurality of confusion sets

iv) means for going to each one of the set of candidate reference identifiers;

v) first means for determining for each character position of the candidate reference identifier the confusion set to which the character occupying the character position belongs;

vi) second means for determining for each character position of the candidate reference identifier whether the character included therein is the same as the character of the corresponding character position of the misrecognized identifier;

vii) third means for assigning to each character position of the candidate reference identifier one of the character change weighting and the character identity weighting of the confusion set associated with the character occupying each character position of the candidate reference identifier; and

viii) third means for determining an associative weighting for the candidate reference identifier on the basis of the character weightings assigned to each character position by the third means for assigning.

26. The apparatus according to claim 25, wherein the third means for determining comprises means for multiplying together each of the one of the character change weightings and character identity weightings assigned to each character position of the candidate reference identifier.

27. An apparatus for recognizing at least one input identifier provided by a user, the apparatus comprising:

a speech recognizer;

a processing device in communication with the speech recognizer;

an identifier verification module in communication with the processing device, the identifier verification module eliminating each previously retrieved reference identifier that includes a character that does not match a character of a corresponding character position in a recognized identifier and that is of a different confusion set than that of the character of the corresponding character position in the recognized identifier;

a confusion matrix memory in communication with the processing device;

a confusion set generating module in communication with the processing device;

a confusion set memory in communication with the processing device; and

a reference identifier database in communication with the processing device.

28. The apparatus according to claim 27, further comprising:

a data input device in communication with the processing device; and

a display device in communication with the processing device.