Computer-based representations and reasoning methods for engaging users in goal-oriented conversations

• US 6,421,655 B1
• Filed: 06/04/1999
• Issued: 07/16/2002
• Est. Priority Date: 06/04/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paek, Timothy S., Horvitz, Eric
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/326,254
• Time in Patent Office: 1,138 Days
• Field of Search: 716/4, 707/6, 713/600, 706/61, 706/50, 706/11, 704/9
• US Class Current: 706/61
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

The use of a goal-understanding abstraction hierarchy in conjunction with Bayesian inference, decision-theoretic analyses of conversational and observational actions is disclosed to provide machinery for incremental refinement of an understanding about a user'"'"'s goals through conversation with users. A computer-implemented method receives multiple classes of information regarding a user goal including visual and linguistic clues at a specific level of the abstraction hierarchy, to assess the goal. The method then determines a with a value-of-information analysis the utility of acquiring additional information via making additional observations or by explicitly querying the user versus making a decision to change the level of precision of the analysis of a user'"'"'s goals. Throughout the analysis, a probability distribution is inferred about the goals of a user. This probability distribution is used in conjunction with a representation of utility of different outcomes to identify informational and navigational actions with the greatest expected utility. In one embodiment, the probability of the leading goal is inferred and used to drive decision making, for example, in assuming the relevance of particular sub-goals of the current goal, where the sub-goals are in a succeeding level of the hierarchy. The probability can be determined in one embodiment by a Bayesian network. If the highest probability sub-goal exceeds a progression threshold, which can be determined by an approximate decision analysis, then this sub-goal is proceeded to in one embodiment—that is, the current level is advanced to the succeeding level, and information gathering is initiated at this new level.

Claims

1. A computer-implemented method comprising:

receiving information regarding a current level of a task abstraction hierarchy of levels to assess a goal of a user within a computer-user interaction context;

determining a sufficiency of the information received based on a decision-analytic approach;

upon determining that the information received is sufficient, selecting an action based on a decision-analytic approach.

2. The method of claim 1, wherein selecting an action based on a decision analytic approach comprises determining a probability distribution over goals represented by a task at the current level of the hierarchy.

3. The method of claim 2, wherein selecting an action further comprises determining an arg max of the probability distribution.

4. The method of claim 1, wherein selecting an action based on a decision-analytic approach comprises:

determining an inference probability;

upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level.

5. The method of claim 4, further comprising continuing to receive information regarding the current level until the goal of the user has been assessed.

6. The method of claim 1, wherein the task abstraction of levels includes at least one atypical level for which a probability of relevance and a probability of irrelevance is determined.

7. The method of claim 1, wherein receiving information regarding a current level comprises receiving information regarding a current level of the task abstraction hierarchy of levels, the task abstraction hierarchy comprising a series of levels, each level comprising at least one goal for each of at least one of the at least one goal of a previous level.

8. The method of claim 1, wherein receiving information comprises receiving information of at least one information type of a group of information types essentially consisting of:

a text information type;

an audio information type;

an image/video information type; and

, an other information type.

9. The method of claim 1, wherein receiving information comprises interacting with the user.

10. The method of claim 9, wherein interacting with the user comprises initially providing the user with second information.

11. The method of claim 10, wherein providing the user with second information comprises providing the user with second information of at least one second information type of a group of second information types essentially consisting of:

an audio second information type;

an image/video second information type; and

, an other second information type.

12. The method of claim 1, wherein determining a sufficiency of the information received comprises performing a value-of-information analysis.

13. The method of claim 12, wherein performing a value-of-information analysis comprises performing a greedy value of information analysis.

14. The method of claim 12, wherein performing a value-of-information analysis comprises determining whether an expected cost to receive additional information exceeds an expected benefit of the additional information.

15. The method of claim 4, wherein determining an inference probability comprises:

determining an initial inference probability for each of the at least one goal of a next level to the current level; and

,

selecting as the inference probability the initial inference probability of the goal of the at least one goal of the next level to the current level having a highest inference probability.

16. The method of claim 15, wherein determining an initial inference probability for each of the at least one goal of a next level to the current level comprises determining the initial inference probability for each of the at least one goal of the next level to the current level by use of a Bayesian network.

17. The method of claim 15, wherein advancing the current level to a next level comprises advancing to the goal of the at least one goal of the next level to the current level having a highest inference probability.

18. The method of claim 4, further comprising, upon determining that the information received is sufficient, and subsequent to upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level,

upon determining that the inference probability exceeds a dialog threshold,

engaging the user in a dialog about whether to proceed to the next level;

and,

upon receiving confirmation from the user to proceed to the next level, advancing the current level to the next level.

19. The method of claim 4, further comprising, upon determining that the information received is sufficient, and subsequent to upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level,

determining a second inference probability;

and,

upon determining that the second inference probability exceeds a return threshold, retreating the current level to a previous level.

20. The method of claim 19, wherein determining a second inference probability comprises determining the second inference probability as a probability of a goal of returning to the previous level.

21. The method of claim 19, wherein determining a second inference probability comprises determining the second inference probability by use of a Bayesian network.

22. A computer-implemented method comprising:

receiving information regarding a current level of a task abstraction hierarchy of levels to assess a goal of a user within a computer-user interaction context;

determining a sufficiency of the information received by performing a value-of-information analysis;

upon determining that the information received is sufficient,

determining an inference probability;

upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level;

determining a second inference probability;

upon determining that the second inference probability exceeds a return threshold, retreating the current level to a previous level; and

,

continuing to receive information regarding the current level until the goal of the user has been assessed.

23. The method of claim 22, wherein receiving information regarding a current level comprises receiving information regarding a current level of the task abstraction hierarchy of levels, the task abstraction hierarchy comprising a series of levels, each level comprising at least one goal for each of at least one of the at least one goal of a previous level.

24. The method of claim 22, wherein receiving information comprises interacting with the user.

25. The method of claim 22, wherein performing a value-of-information analysis comprises determining whether an expected cost to receive additional information exceeds an expected benefit of the additional information.

26. The method of claim 23, wherein determining an inference probability comprises:

determining an initial inference probability for each of the at least one goal of a next level to the current level by use of a Bayesian network; and

,

selecting as the inference probability the initial inference probability of the goal of the at least one goal of the next level to the current level having a highest inference probability.

27. The method of claim 23, wherein advancing the current level to a next level comprises advancing to the goal of the at least one goal of the next level to the current level having a highest inference probability.

28. The method of claim 22, further comprising, upon determining that the information received is sufficient, and subsequent to upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level,

upon determining that the inference probability exceeds a second probability threshold,

engaging the user in a dialog about whether to proceed to the next level;

and,

upon receiving confirmation from the user to proceed to the next level, advancing the current level to the next level.

29. The method of claim 22, wherein determining a second inference probability comprises determining the second inference probability as a probability of a goal of returning to the previous level by use of a Bayesian network.

30. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

receiving information regarding a current level of a task abstraction hierarchy of levels to assess a goal of a user within a computer-user interaction context;

determining a sufficiency of the information received;

upon determining that the information received is sufficient,

determining an inference probability;

upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level; and

,

continuing to receive information regarding the current level until the goal of the user has been assessed.

31. The medium of claim 30, wherein receiving information regarding a current level comprises receiving information regarding a current level of the task abstraction hierarchy of levels, the task abstraction hierarchy comprising a series of levels, each level comprising at least one goal for each of at least one of the at least one goal of a previous level.

32. The medium of claim 30, wherein receiving information comprises interacting with the user.

33. The medium of claim 30, wherein determining a sufficiency of the information received comprises performing a value-of-information analysis.

34. The medium of claim 33, wherein performing a value-of-information analysis comprises performing a greedy value of information analysis.

35. The medium of claim 33, wherein performing a value-of-information analysis comprises determining whether an expected cost to receive additional information exceeds an expected benefit of the additional information.

36. The medium of claim 30, wherein determining an inference probability comprises:

determining an initial inference probability for each of the at least one goal of a next level to the current level by use of a Bayesian network; and

,

selecting as the inference probability the initial inference probability of the goal of the at least one goal of the next level to the current level having a highest inference probability.

37. The medium of claim 36, wherein advancing the current level to a next level comprises advancing to the goal of the at least one goal of the next level to the current level having a highest inference probability.

38. The medium of claim 30, further comprising, upon determining that the information received is sufficient, and subsequent to upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level,

upon determining that the inference probability exceeds a dialog threshold,

engaging the user in a dialog about whether to proceed to the next level;

and,

upon receiving confirmation from the user to proceed to the next level, advancing the current level to the next level.

39. The medium of claim 30, further comprising, upon determining that the information received is sufficient, and subsequent to upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level,

determining a second inference probability of a goal of returning to the previous level by use of a Bayesian network;

and,

upon determining that the second inference probability exceeds a return threshold, retreating the current level to a previous level.

40. A machine-readable medium having instructions stored thereon for execution by a processor to perform a method comprising:

receiving information regarding a current level of a task abstraction hierarchy of levels to assess a goal of a user within a computer-user interaction context, the task abstraction hierarchy comprising a series of levels, each level comprising at least one goal for each of at least one of the at least one goal of a previous level;

determining a sufficiency of the information received by performing a value-of-information analysis;

upon determining that the information received is sufficient,

determining an initial inference probability for each of the at least one goal of a next level to the current level by use of a Bayesian network;

selecting as an inference probability the initial inference probability of the goal of the at least one goal of the next level to the current level having a highest inference probability;

upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level;

determining a second inference probability of a goal of returning to the previous level by use of a Bayesian network;

upon determining that the second inference probability exceeds a return threshold, retreating the current level to a previous level; and

,

continuing to receive information regarding the current level until the goal of the user has been assessed.

41. The medium of claim 40, wherein receiving information comprises interacting with the user.

42. The medium of claim 40, wherein performing a value-of-information analysis comprises determining whether an expected cost to receive additional information exceeds an expected benefit of the additional information.

43. The medium of claim 40, wherein advancing the current level to a next level comprises advancing to the goal of the at least one goal of the next level to the current level having a highest inference probability.

44. The medium of claim 40, further comprising, upon determining that the information received is sufficient, and subsequent to upon determining that the inference probability exceeds a progression threshold, advancing the current level to a next level,

upon determining that the inference probability exceeds a dialog threshold,

engaging the user in a dialog about whether to proceed to the next level; and,

upon receiving confirmation from the user to proceed to the next level, advancing the current level to the next level.

45. A computerized system comprising:

at least one source of user information;

at least one destination for output to a user;

a decision engine operatively coupled to the at least one source and the at least one destination to assess a goal of the user within a computer-user interaction context via navigation of a task abstraction hierarchy of levels.

46. The system of claim 45, further comprising a mechanism to provide for action based on the goal of the user assessed by the decision engine.

47. The system of claim 45, wherein the at least one source comprises at least one of the following:

a keyboard, a microphone, and a video camera.

48. The system of claim 45, wherein the at least one destination comprises at least one of the following:

a speaker, and a display device.

49. The system of claim 45, wherein the task abstraction hierarchy comprises a series of levels, each level comprising at least one goal for each of at least one of the at least one goal of a previous level.

50. The system of claim 45, wherein the decision engine accomplishes navigation of the task abstraction hierarchy via use of at least one Bayesian network.

51. The system of claim 45, wherein the decision engine comprises a computer program executed by a processor from a computer-readable medium.

52. A computer-implemented method comprising:

using a decision-analytic approach to select an action from the group of actions relating to assessment of a goal of a user within a computer-user interaction context, the group comprising;

obtaining information;

progressing to a next level of a task abstraction hierarchy of levels; and

, retreating to a previous level of the task abstraction hierarchy;

effecting the selected action; and

,

repeating until one of the goal of the user has been assessed and the costs of continuing conversation outweigh the benefits.

53. The method of claim 52, wherein obtaining information comprises obtaining information implicitly and obtaining information through explicit querying of the user.

54. The method of claim 52, wherein progressing to a next level comprises progressing to the next level following acquisition of confirmation from the user.

55. The method of claim 52, wherein retreating to a previous level comprises retreating to the previous level following an attempt to seek confirmation from the user.