KNOWLEDGE-BASED STRATEGIES APPLIED TO N-BEST LISTS IN AUTOMATIC SPEECH RECOGNITION SYSTEMS

• US 20030154075A1
• Filed: 12/29/1998
• Published: 08/14/2003
• Est. Priority Date: 12/29/1998
• Status: Active Grant

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: ZIMMERMAN, ROGER S., SCHALK, THOMAS B.
• Granted Patent: US 6,922,669 B2
• Time in Patent Office: Days
• US Class Current: 704/231
• CPC Class Codes: G10L 15/18 using natural language modelling
• CPC Class Codes: G10L 2015/085 Methods for reducing search complexity, pruning

Abstract

A highly accurate technique for recognizing spoken digit strings is described. A spoken digit string is received and analyzed by a speech recognizer, which generates a list of hypothesized digit strings arranged in ranked order based on a likelihood of matching the spoken digit string. The individual hypothesized strings are then analyzed in order beginning with the hypothesized string having the greatest likelihood of matching the spoken string to determine whether they satisfy a given constraint. The first hypothesized string in the list satisfying the constraint is selected as the recognized string.

Claims

1. A method of recognizing a spoken digit string, comprising:

(a) receiving the spoken digit string;

(b) analyzing the spoken digit string to generate a list of hypothesized digit strings arranged in ranked order based on a likelihood of matching the spoken digit string;

(c) using a given knowledge based recognition strategy, determining whether individual hypothesized strings of said list satisfy a given constraint beginning with the string having the greatest likelihood of matching said spoken string; and

(d) selecting the first string in the list satisfying the constraint as the recognized string.

2. The method of claim 1 wherein said given knowledge based recognition strategy comprises a database matching scheme.

3. The method of claim 2 wherein step (c) comprises searching a database of valid data strings to determine whether any of the hypothesized digit strings match one of the valid digit strings.

4. The method of claim 1 wherein the knowledge based recognition strategy is a checksum scheme.

5. The method of claim 4 wherein the spoken digit string includes a checksum digit, and wherein step (c) comprises calculating a checksum of the hypothesized digit strings and determining whether the checksum matches the value of the checksum digit.

6. The method of claim 4 further comprising the following steps:

if none of the hypothesized digit strings satisfies the constraint;

(e) generating an additional hypothesized digit string based on information gathered from the hypothesized digit strings in the list;

(f) analyzing the additional hypothesized digit string to determine if the checksum scheme is satisfied;

(g) if so, validating the additional hypothesized digit string.

7. The method of claim 4 wherein the checksum scheme utilizes a Luhn Checksum algorithm.

8. The method of claim 1 further comprising:

(e) if none of the hypothesized strings satisfy said constraint, using a supplemental matching technique to select the hypothesized digit string that most closely satisfies the constraint.

9. The method of claim 8 wherein the supplemental matching technique is a fuzzy matching scheme.

10. The method of claim 9 wherein the fuzzy matching scheme determines the number of corrections needed to match each hypothesized digit string with one of a set of valid digit strings.

11. The method of claim 10 wherein the corrections comprise digit substitutions, deletions and additions.

12. The method of claim 10 wherein the corrections are weighted.

13. The method of claim 1 wherein the knowledge based recognition strategy is a digit positional strategy and the constraining is a given digit position.

14. The method of claim 1 wherein the knowledge based recognition strategy is a digit string length strategy and the constraint is a given digit string length.

15. The method of claim 1 further comprising:

if none of the hypothesized digit strings satisfy the constraint;

(e) prompting entry of a second spoken digit string;

(f) analyzing the second spoken digit string to generate a second list of hypothesized digit strings arranged in ranked order based on a likelihood of matching the second spoken digit string;

(g) determining whether individual hypothesized strings of the second list match one of the hypothesized digit strings in the list generated in step (b) in order beginning with the string having the greatest likelihood of matching the second spoken string; and

(h) selecting as the recognized string the first string in the second list matching one of the hypothesized digit strings generated in step (b).

16. The method of claim 1 further comprising:

if none of the hypothesized digit strings satisfy said constraint;

(e) prompting entry of a second spoken digit string;

(f) analyzing the second spoken digit string to generate a second list of hypothesized digit strings arranged in ranked order based on a likelihood of matching the second spoken digit string;

(g) determining whether individual hypothesized strings of the list generated in step (b) match one of the hypothesized digit strings in the second list in order beginning with the string having the greatest likelihood of matching the spoken string received in step (a); and

(h) selecting as the recognized string the first string in said list generated in step (b) matching one of the hypothesized digit strings of said second list.

17. The method of claim 1 further comprising repeating the recited steps if none of the hypothesized strings match the constraint.

18. The method of claim 1 further comprising the step of prompting entry of a spoken digit string prior to step (a).

19. A method of recognizing a spoken digit string, comprising:

(a) prompting entry of a spoken digit string;

(b) receiving the spoken digit string;

(c) analyzing the spoken digit string to generate a list of hypothesized digit strings arranged in ranked order based on a likelihood of matching the spoken digit string;

(d) using a given knowledge based recognition strategy, determining whether the hypothesized string of the list having the greatest likelihood of matching said spoken string satisfies a given constraint;

(e) if in step (d) the constraint is found to be satisfied, then validating the hypothesized string, and if not, removing the hypothesized string from the list and repeating steps (d) and (e) for the remaining hypothesized strings in said list.

20. The method of claim 19 wherein the given constraint is a valid string database match.

21. The method of claim 20 wherein step (d) comprises searching a database of valid data strings to determine whether the hypothesized digit strings match one of the valid digit strings.

22. The method of claim 19 wherein the given constraint is a checksum.

23. The method of claim 22 wherein the spoken digit string includes a checksum digit, and wherein step (d) calculates a checksum of the hypothesized digit strings and determines whether the checksum matches the value of the checksum digit.

24. The method of claim 22 further comprising:

if none of the hypothesized digit strings satisfies the constraint;

(f) generating an additional hypothesized digit string based on information gathered from the hypothesized digit strings in the list; and

(g) analyzing the additional hypothesized digit string to determine if the checksum scheme is satisfied, and if so, validating the additional hypothesized digit string.

25. A computer program product in a computer-readable medium for use in a computer for recognizing a spoken digit string, comprising:

means for analyzing a spoken digit string to generate a list of hypothesized digit strings arranged in ranked order based on a likelihood of matching the spoken digit string;

knowledge based recognition means for analyzing individual hypothesized strings of the list to determine whether they satisfy a given constraint in order beginning with the string having the greatest likelihood of matching the spoken string; and

means for selecting the first string in said list satisfying said constraint as the recognized string.