Dialogue evaluation via multiple hypothesis ranking

• US 10,162,813 B2
• Filed: 11/21/2013
• Issued: 12/25/2018
• Est. Priority Date: 11/21/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sarikaya, Ruhi, Boies, Daniel, Crook, Paul A., Robichaud, Jean-Philippe
• Primary Examiner(s): Opsasnick, Michael N
• Application Number:
  US14/086,897
• Publication Number:
  US 20150142420A1
• Time in Patent Office: 1,860 Days
• Field of Search: 704 9
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: G10L 2015/227 of the speaker; Human-factor methodology
• CPC Class Codes: G10L 2015/228 of application context

Abstract

In language evaluation systems, user expressions are often evaluated by speech recognizers and language parsers, and among several possible translations, a highest-probability translation is selected and added to a dialog sequence. However, such systems may exhibit inadequacies by discarding alternative translations that may initially exhibit a lower probability, but that may have a higher probability when evaluated in the full context of the dialog, including subsequent expressions. Presented herein are techniques for communicating with a user by formulating a dialog hypothesis set identifying hypothesis probabilities for a set of dialog hypotheses, using generative and/or discriminative models, and repeatedly re-ranks the dialog hypotheses based on subsequent expressions. Additionally, knowledge sources may inform a model-based with a pre-knowledge fetch that facilitates pruning of the hypothesis search space at an early stage, thereby enhancing the accuracy of language parsing while also reducing the latency of the expression evaluation and economizing computing resources.

Claims

1. A method of evaluating a dialogue with a user on a device having a processor, the method comprising:

executing on the processor instructions causing the device to;

generate a dialogue hypothesis set comprising at least two dialogue hypotheses respectively having a hypothesis probability;

rank the dialogue hypothesis set according to the hypothesis probabilities;

after the ranking, upon identifying a low-ranking dialogue hypothesis having a hypothesis probability below a hypothesis retention threshold, discard the low-ranking dialogue hypothesis;

in response to the discarding, adjust the hypothesis probabilities of the respective dialogue hypotheses using a knowledge source;

after the adjusting, re-rank the dialogue hypothesis set according to the hypothesis probabilities; and

for a high-ranking dialogue hypothesis having a hypothesis probability exceeding a hypothesis confidence threshold, execute an action fulfilling the high-ranking dialogue hypothesis, wherein executing the action comprises presenting to the user information associated with the high-ranking dialogue hypothesis.

2. The method of claim 1, wherein the instructions, when executed on the processor, further cause the device to, upon identifying at least two high-ranking dialogue hypotheses respectively having a hypothesis probability within a hypothesis proximity range:

present to the user a disambiguation query; and

upon receiving from the user a response to the disambiguation query, adjust the hypothesis probability of the respective at least two high-ranking dialogue hypotheses in view of the response.

3. The method of claim 1, wherein:

the dialogue comprises at least two expressions of the user; and

adjusting the hypothesis probabilities further comprises;

for the respective dialogue hypotheses, adjust the hypothesis probability in view of the at least two expressions of the user.

4. The method of claim 1, wherein adjusting the hypothesis probabilities further comprises:

upon identifying an expression of the user that declines the high-ranking dialogue hypothesis, reducing the hypothesis probability of the high-ranking dialogue hypothesis.

5. The method of claim 1, wherein the knowledge source is selected from a knowledge source set comprising:

a user profile of the user;

an execution of an earlier action in response to an earlier dialogue with the user; and

a current environment of the device.

6. The method of claim 1, wherein the instructions further cause the device to, upon receiving a knowledge domain comprising at least one subject and at least one action, add the at least one subject and the at least one action of the knowledge domain to the knowledge source.

20. The method of claim 1, wherein the instructions further cause the device to, upon identifying an error in response to an action fulfilling the high-ranking dialogue hypothesis, reduce the hypothesis probability of the high-ranking dialogue hypothesis.

7. A computer-readable memory device not consisting of a propagated data signal, the computer-readable memory device storing instructions that, when executed on a processor of a device, cause the device to evaluate a dialogue with a user, by:

generating a dialogue hypothesis set comprising at least two dialogue hypotheses respectively having a hypothesis probability;

ranking the dialogue hypothesis set according to the hypothesis probabilities;

after the ranking, upon identifying a low-ranking dialogue hypothesis having a hypothesis probability below a hypothesis retention threshold, discarding the low-ranking dialogue hypothesis;

in response to the discarding, adjust the hypothesis probabilities of the respective dialogue hypotheses using a knowledge source;

after the adjusting, re-rank the dialogue hypothesis set according to the hypothesis probabilities; and

for a high-ranking dialogue hypothesis having a hypothesis probability exceeding a hypothesis confidence threshold, execute an action fulfilling the high-ranking dialogue hypothesis, wherein executing the action comprises presenting to the user information associated with the high-ranking dialogue hypothesis.

8. The computer-readable memory device of claim 7, wherein the instructions, when executed on the processor, further cause the device to, upon identifying an error in response to an action fulfilling the high-ranking dialogue hypothesis, reduce the hypothesis probability of the high-ranking dialogue hypothesis.

9. The computer-readable memory device of claim 8, wherein the instructions, when executed on the processor, further cause the device to, upon identifying a failure while executing the action for the high-ranking dialogue hypothesis, report to the user an action error indicating the failure of the action.

10. The computer-readable memory device of claim 9, wherein the instructions, when executed on the processor, further cause the device to:

upon receiving an expression of the dialogue, evaluate the expression of the dialogue according to an expression evaluator to generate at least one dialogue hypothesis involving the expression; and

upon identifying a failure to parse the expression of the dialogue according to the expression evaluator, report to the user a parsing error indicating the failure to parse the expression of the dialogue, where the parsing error is different than the action error.

11. The computer-readable memory device of claim 10, wherein:

the expression evaluator further comprises;

a language recognizer that identifies at least one language element of the expression, and

a language parser that parses the expressions to generate the dialogue hypothesis; and

the parsing error is selected from a parsing error set comprising;

an expression recognizer error indicating to the user a failure to recognize the expression; and

a language parsing error indicating to the user a failure to parse the expression, where the language parsing error is different from the expression recognizer error.

12. A system for evaluating a dialogue with a user on a device having a processor and a memory, the system comprising:

a dialogue hypothesis set;

an expression evaluator comprising instructions stored in the memory that, when executed on the processor, cause the device to, for respective expressions of the dialogue;

apply an expression recognizer and a natural language processor to;

upon receiving from the user an expression replacing a previous subject of the dialogue with a substitute subject, store in the dialogue hypothesis set at least one dialogue hypothesis of the expression, the at least one dialogue hypothesis respectively comprising;

at least one slot associated with the substitute subject of the expression, and

a hypothesis probability; and

for respective previous dialogue hypotheses in the dialogue hypothesis set that were generated for a previous expression of the dialogue, update the previous subject of at least one previous dialogue hypothesis with the substitute subject; and

in response to updating the previous subject of the at least one slot, adjust the hypothesis probabilities of the respective dialogue hypotheses using a knowledge source; and

a dialogue hypothesis comparator comprising instructions stored in the memory that, when executed on the processor, cause the device to;

rank the dialogue hypothesis set according to the hypothesis probabilities;

discard a low-ranking dialogue hypothesis from the dialogue hypothesis set;

adjust the hypothesis probabilities of the dialogue hypothesis set; and

for a high-ranking dialogue hypothesis having a hypothesis probability exceeding a hypothesis confidence threshold, execute an action fulfilling the high-ranking dialogue hypothesis, wherein executing the action comprises presenting to the user information associated with the high-ranking dialogue hypothesis.

13. The system of claim 12, wherein:

the previous subject further comprises a current knowledge domain within the knowledge source; and

the substitute subject further comprises an alternative knowledge domain within the knowledge source that is different from the current knowledge domain.

14. The system of claim 12, wherein:

the previous subject further comprises a subject genus within a current knowledge domain of the knowledge source; and

the substitute subject further comprises a subject species within the subject genus within the current knowledge domain.

15. The system of claim 12, wherein:

the previous subject further comprises a selected action to be applied to a second subject of the dialogue hypothesis; and

the substitute subject further comprises an alternative action to be applied to the second subject of the dialogue hypothesis, where the alternative action is different from the selected action.

16. The system of claim 12, wherein the expression evaluator further comprises:

a language recognizer that identifies at least one language element in the expression, and

a language parser that parses the expressions to generate the dialogue hypothesis.

17. The system of claim 16, wherein the language recognizer further comprises:

a camera that detects a physical language element of the user; and

a language recognizer that identifies an expression indicated by the physical language element.

18. The system of claim 16, wherein the language parser parses the expressions in view of the knowledge source.

19. The system of claim 18, wherein the language parser:

retrieves from the knowledge source at least one included fact that is related to the expression and excludes at least one excluded fact that is not related to the expression; and

parses the expression in view of the at least one included fact to generate the dialogue hypothesis.