SYSTEM AND METHOD FOR EFFICIENT TRACKING OF MULTIPLE DIALOG STATES WITH INCREMENTAL RECOMBINATION

• US 20110137654A1
• Filed: 12/08/2009
• Published: 06/09/2011
• Est. Priority Date: 12/08/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: WILLIAMS, Jason
• Granted Patent: US 8,457,968 B2
• Time in Patent Office: Days
• US Class Current: 704/257
• CPC Class Codes: G10L 15/04 Segmentation; Word boundary detection
• CPC Class Codes: G10L 15/14 using statistical models, e.g. Hidden Markov Models [HMMs] G10L15/18 takes precedence
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

Disclosed herein are systems, methods, and computer-readable storage media for tracking multiple dialog states. A system practicing the method receives an N-best list of speech recognition candidates, a list of current partitions, and a belief for each of the current partitions. A partition is a group of dialog states. In an outer loop, the system iterates over the N-best list of speech recognition candidates. In an inner loop, the system performs a split, update, and recombination process to generate a fixed number of partitions after each speech recognition candidate in the N-best list. The system recognizes speech based on the N-best list and the fixed number of partitions. The split process can perform all possible splits on all partitions. The update process can compute an estimated new belief. The estimated new belief can be a product of ASR reliability, user likelihood to produce this action, and an original belief.

Claims

1. A method of incremental partition recombination for tracking multiple dialog states, the method causing a computing device to perform steps comprising:

receiving an N-best list of speech recognition candidates;

receiving a list of current partitions and a belief for each of the current partitions, wherein a partition is a group of dialog states;

in an outer loop, iterating over each of the speech recognition candidates in the N-best list;

in an inner loop, performing a split, update, and recombination process to generate a fixed number of partitions after each speech recognition candidate in the N-best list; and

recognizing speech based on the N-best list and the fixed number of partitions.

2. The method of claim 1, wherein the split process performs all possible splits on all partitions.

3. The method of claim 1, wherein the update process computes an estimated new belief.

4. The method of claim 3, wherein the estimated new belief is a product of at least one of a reliability of automatic speech recognition, a likelihood that a user would produce this action, and an original belief.

5. The method of claim 3, wherein the estimated new belief further includes a term which accounts for all actions not yet observed.

6. The method of claim 1, wherein the recombination process ignores distinctions between two partitions when recombining the two partitions.

7. The method of claim 1, wherein the recombination process starts with a least likely partition.

8. A system for incrementally recombining partitions for tracking multiple dialog states, the system comprising:

a processor;

a module controlling the processor to receive an N-best list of speech recognition candidates;

a module controlling the processor to receive a list of current partitions and a belief for each of the current partitions, wherein a partition is a group of dialog states;

a module controlling the processor to, in an outer loop, iterate over each of the speech recognition candidates in the N-best list;

a module controlling the processor to, in an inner loop, perform a split, update, and recombination process to generate a fixed number of partitions after each speech recognition candidate in the N-best list; and

a module controlling the processor to recognize speech based on the N-best list and the fixed number of partitions.

9. The system of claim 8, wherein the split process performs all possible splits on all partitions.

10. The system of claim 8, wherein the update process computes an estimated new belief.

11. The system of claim 10, wherein the estimated new belief is a product of at least one of a reliability of automatic speech recognition, a likelihood that a user would produce this action, and an original belief.

12. The system of claim 10, wherein the estimated new belief further includes a term which accounts for all actions not yet observed.

13. The system of claim 8, wherein the recombination process ignores distinctions between two partitions when recombining the two partitions.

14. A computer-readable storage medium storing instructions which, when executed by a computing device, cause the computing device to incrementally recombine partitions for tracking multiple dialog states, the instructions comprising:

receiving an N-best list of speech recognition candidates;

receiving a list of current partitions and a belief for each of the current partitions, wherein a partition is a group of dialog states;

in an outer loop, iterating over each of the speech recognition candidates in the N-best list;

in an inner loop, performing a split, update, and recombination process to generate a fixed number of partitions after each speech recognition candidate in the N-best list; and

recognizing speech based on the N-best list and the fixed number of partitions.

15. The computer-readable storage medium of claim 14, wherein the split process performs all possible splits on all partitions.

16. The computer-readable storage medium of claim 15, wherein the update process computes an estimated new belief.

17. The computer-readable storage medium of claim 15, wherein the estimated new belief is a product of at least one of a reliability of automatic speech recognition, a likelihood that a user would produce this action, and an original belief.

18. The computer-readable storage medium of claim 14, wherein the estimated new belief further includes a term which accounts for all actions not yet observed.

19. The computer-readable storage medium of claim 14, wherein the recombination process ignores distinctions between two partitions when recombining the two partitions.

20. The computer-readable storage medium of claim 14, wherein the recombination process starts with a least likely partition.