Concise dynamic grammars using N-best selection

• US 7,937,260 B1
• Filed: 06/15/1998
• Issued: 05/03/2011
• Est. Priority Date: 06/15/1998
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Brown, Deborah W., Goldberg, Randy G., Marcus, Stephen Michael, Rosinski, Richard R.
• Primary Examiner(s): Han, Qi
• Application Number:
  US09/097,787
• Time in Patent Office: 4,705 Days
• Field of Search: 704/1, 704/231, 704/235, 704/270, 704/270.1, 704/10, 704/246, 704/251, 379/88
• US Class Current: 704/1
• CPC Class Codes: G10L 15/02 Feature extraction for speech recognition; Selection of recognition unit
• CPC Class Codes: G10L 15/06 Creation of reference templates; Training of speech recognition systems, e.g. adaptation to the characteristics of the speaker's voice G10L15/14 takes precedence
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: G10L 2015/228 of application context
• CPC Class Codes: G10L 25/27 characterised by the analysis technique

Abstract

A method and apparatus derive a dynamic grammar composed of a subset of a plurality of data elements that are each associated with one of a plurality of reference identifiers. The present invention generates a set of selection identifiers on the basis of a user-provided first input identifier and determines which of these selection identifiers are present in a set of pre-stored reference identifiers. The present invention creates a dynamic grammar that includes those data elements that are associated with those reference identifiers that are matched to any of the selection identifiers. Based on a user-provided second identifier and on the data elements of the dynamic grammar, the present invention selects one of the reference identifiers in the dynamic grammar.

Claims

1. A method for retrieving a reference identifier, the method comprising:

generating, via a processing device, a plurality of selection identifiers from first user speech input received from a user, wherein the first user speech input comprises at least one non-alphanumeric character;

comparing the plurality of selection identifiers with a set of reference identifiers to determine which reference identifiers in the set of reference identifiers match at least one of the plurality of selection identifiers;

deriving a dynamic grammar by storing matching reference identifiers determined to match at least one of the plurality of selection identifiers together with data elements associated with the matching reference identifiers;

generating at least one correlation identifier from second user input received from the user;

comparing the at least one correlation identifier with the data elements to determine which data element matches the at least one correlation identifier; and

retrieving the reference identifier associated with the data element determined to match the at least one correlation identifier.

2. The method of claim 1, wherein generating the plurality of selection identifiers further comprises:

receiving an input identifier developed from the first user speech input; and

deriving the plurality of selection identifiers in accordance with the input identifier.

3. The method of claim 2, wherein the at least one selection identifier is derived from the input identifier in accordance with a Hidden Markov Model algorithm.

4. The method of claim 2, wherein the at least one selection identifier is derived from the input identifier in accordance with one of a confusion matrix and a plurality of confusion sets.

5. The method of claim 1, wherein the plurality of selection identifiers represents an N-best hypothesis as a result of output from a speech recognition module.

6. The method of claim 5, wherein the N-best hypothesis is compared to the set of reference identifiers to identify matches for use in deriving the dynamic grammar.

7. The method of claim 1, further comprising:

after deriving the dynamic grammar, presenting a prompt to the user to obtain the second user input; and

processing the second user input with the dynamic grammar to identify a desired selection identifier from the plurality of selection identifiers.

8. An apparatus for retrieving a reference identifier, the apparatus comprising:

a processing device;

a first module configured to control the processing device to generate a plurality of selection identifiers from first user speech input received from a user, wherein the first user speech input comprises at least one non-alphanumeric character;

a second module configured to control the processing device to compare the plurality of selection identifiers with a set of reference identifiers to determine which reference identifiers in the set of reference identifiers match at least one of the plurality of selection identifiers;

a third module configured to control the processing device to derive a dynamic grammar matching memory reference identifiers determined to match at least one of the plurality of selection identifiers together with data elements associated with the matching reference identifiers;

a fourth module configured to control the processing device to generate at least one correlation identifier from second user input received from the user;

a fifth module configured to control the processing device to compare the at least one correlation identifier with the data elements to determine which data element matches the at least one correlation identifier; and

a sixth module configured to control the processing device to retrieve the reference identifier associated with the data element determined to match the at least one correlation identifier.

9. The apparatus of claim 8, wherein the first module is further configured to control the processing device to perform steps comprising:

i) receiving an input identifier developed from the first user speech input; and

ii) deriving the plurality of selection identifiers in accordance with the input identifier.

10. The apparatus of claim 8, wherein the third module is further configured to control the processing device to derive the plurality of selection identifiers from an input identifier in accordance with a Hidden Markov Model algorithm.

11. The apparatus of claim 10, wherein the third module is further configured to control the processing device to derive the plurality of selection identifiers from the input identifier in accordance with one of a confusion matrix and a plurality of confusion sets.

12. The apparatus of claim 8, wherein the plurality of selection identifiers represents an N-best hypothesis as a result of output from a speech recognition module.

13. The apparatus of claim 12, wherein the N-best hypothesis is compared to the set of reference identifiers to identify matches for use in deriving the dynamic grammar.

14. The apparatus of claim 8, further comprising:

means for, after deriving the dynamic grammar, presenting a prompt to the user to obtain the second user input; and

means for processing the second user input with the dynamic grammar to identify a desired selection identifier from the plurality of selection identifiers.

15. A non-transitory computer-readable storage medium storing instructions which, when executed by a processing device, cause the processing device to:

generate a plurality of selection identifiers from first user speech input received from a user, wherein the first user speech input comprises at least one non-alphanumeric character;

compare the plurality of selection identifiers with a set of reference identifiers to determine which reference identifiers in the set of reference identifiers match at least one of the plurality of selection identifiers;

generate a dynamic grammar by storing matching reference identifiers determined to match at least one of the plurality of selection identifiers together with data elements associated with the matching reference identifiers;

generate at least one correlation identifier from second user input received from the user;

compare the at least one correlation identifier with the data elements to determine which data element matches the at least one correlation identifier; and

retrieve the reference identifier associated with the data element determined to match the at least one correlation identifier.

16. The non-transitory computer-readable storage medium of claim 15, wherein generating the at least one selection identifier further comprises:

receiving an input identifier developed from the first user speech input; and

deriving the at least one selection identifier in accordance with the input identifier.

17. The non-transitory computer-readable storage medium of claim 16, wherein the plurality of selection identifiers are derived from an input identifier in accordance with a Hidden Markov Model algorithm.

18. The non-transitory computer-readable storage medium of claim 16, wherein the plurality of selection identifiers are derived from the input identifier in accordance with one of a confusion matrix and a plurality of confusion sets.

19. The non-transitory computer-readable storage medium of claim 15, wherein the plurality of selection identifiers from user speech represents an N-best hypothesis as a result of output from a speech recognition module.

20. The non-transitory computer-readable storage medium of claim 19, wherein the N-best hypothesis is compared to the set of reference identifiers to identify matches for use in deriving the dynamic grammar.

21. The non-transitory computer-readable storage medium of claim 15, wherein the dynamic grammar is derived for use in processing second user input received after receiving the user speech input.

22. The non-transitory computer-readable storage medium of claim 21, the instructions further comprising:

after deriving the dynamic grammar, presenting a prompt to the user to obtain the second user input; and

processing the second user input with the dynamic grammar to identify a desired selection identifier from the plurality of selection identifiers.