System and method for automatically focusing the attention of a virtual robot interacting with users

• US 6,363,301 B1
• Filed: 06/04/1997
• Issued: 03/26/2002
• Est. Priority Date: 06/04/1997
• Status: Expired due to Fees

• Current Assignee: NativeMinds, Inc. (Healthstream Incorporated)
• Original Assignee: NativeMinds, Inc. (Healthstream Incorporated)
• Inventors: Benson, Scott S., Tackett, Walter A.
• Primary Examiner(s): Gordon, Paul P.
• Application Number:
  US08/868,713
• Time in Patent Office: 1,756 Days
• Field of Search: 700/215, 700/264, 700/246, 707/102, 704/9, 345/968
• US Class Current: 700/246
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]

Abstract

A virtual robot (or BOT) is disclosed that interfaces and automatically interacts with users desiring to be guided or informed about certain aspects or features of the entity with which they are interacting. Several mechanisms are further disclosed that aid the effectiveness of that interaction. Mechanisms to focus the attention of the BOT on certain aspects of the interaction or communication are disclosed. These mechanisms can be made explicitly or can be performed automatically. Mechanisms are disclosed to aid the BOT to automatically learn from its interactions with users to increase the effectiveness of the interaction.

Claims

1. A method of focusing the attention of an automated interface program adapted for interacting with a user in natural language, the method comprising:

(a) defining at least one category associated with actions executable by the automated interface program during interaction with a user;

(b) maintaining an attention focus list comprising at least one category arranged in an order;

(c) receiving natural language input from the user, wherein the natural language input comprises at least one natural language component, wherein the at least one natural language component may comprise a subset of the natural language input;

(d) examining at least one category in the attention focus list to determine whether a natural language component within said natural language input generates a match with the at least one examined category, and the order in which categories are examined is influenced by the order of the attention focus list; and

(e) generating a new order for the categories of said attention focus list, wherein the new order is influenced by the categories of the attention focus list for which a match was generated.

2. The method of focusing the attention of the automated interface program as recited in claim 1, further comprising the step of executing actions associated with examined categories for which a match is generated.

3. The method for focusing the attention of said automated interface program as recited in claim 2, wherein the step of executing actions associated with examined categories for which a match is generated further comprises executing actions according to the order of the categories in the attention focus list.

4. The method for focusing the attention of said automated interface program as recited in claim 3, wherein the step of executing actions according to the order of the categories in the attention focus list further comprises executing actions according to the order in which standard categories appear in said attention focus list.

5. The method of focusing the attention of the automated interface program as recited in claim 1, wherein the natural language input received from the user comprises natural language communications composed by the user.

6. The method of focusing the attention of said automated interface program as recited in claim 1, wherein the step of defining at least one category further comprises defining a priority category type wherein a priority category is examined before categories of other types.

7. The method for focusing the attention of said automated interface program as recited in claim 1, wherein the step of defining at least one category further comprises defining a default category type wherein a default category is examined after categories of other types.

8. The method for focusing the attention of said automated interface program as recited in claim 7, wherein the default category is examined if no actions are executed in association with another category.

9. The method for focusing the attention of said automated interface program as recited in claim 1, wherein the step of defining at least one category further comprises defining a sequence category type wherein a sequence category is examined only when a request to examine the sequence category is executed in association with another category.

10. The method for focusing the attention of said automated interface program as recited in claim 9, further comprising the steps of

executing one or more actions associated with an examined sequence category;

receiving additional natural language input from the user;

examining one or more priority categories in response to the additional natural language input, wherein actions associated with a priority category that generates a match with a natural language component of the natural language input are executed; and

executing one or more unexecuted actions associated with the examined sequence category.

11. The method for focusing the attention of said automated interface program as recited in claim 9, further comprising the steps of:

executing one or more actions associated with an examined sequence category;

identifying a second category for which a match has been generated with a natural language component within the natural language input;

executing one or more actions associated with the second category; and

executing one or more unexecuted actions associated with the examined sequence category.

12. The method for focusing the attention of said automated interface program as recited in claim 9, wherein a sequence category is examined in a predefined order in relation to another category.

13. The method for focusing the attention of said automated interface program as recited in claim 1, wherein the step of defining at least one category further comprises defining a standard category type wherein a standard category is examined after all priority categories are examined and before any default category is examined.

14. The method for focusing the attention of said automated interface program as recited in claim 1, wherein the step of generating a new order for the categories of the attention focus list further comprises moving categories for which a match was generated a position of higher precedence of the attention focus list.

15. The method for focusing the attention of said automated interface program as recited in claim 1, wherein the step of generating a new order for the categories of the attention focus list further comprises:

associating subjects with categories; and

moving a first category that shares an associated subject with a second category for which a match was generated to a position near the top of the attention focus list.

16. The method for focusing the attention of said automated interface program as recited in claim 1, wherein the step of generating a new order for the categories of the attention focus list further comprises re-ordering the attention focus list according to explicit commands within a category for which a match was generated.

17. The method for focusing the attention of said automated interface program as recited in claim 16, wherein the step of re-ordering said attention focus list according to explicit commands further comprises moving a first category that is explicitly mentioned in a focus command within a second category for which a match was generated to a position a position of higher precedence in the attention focus list.

18. The method for focusing the attention of said automated interface program as recited in claim 16, wherein the step of re-ordering the attention focus list according to explicit commands further comprises:

associating subjects with categories; and

moving a first category that is associated with a subject explicity mentioned in a focus subjects command within a second category for which a match was generated to a position near the top of the attention focus list.

19. The method for focusing the attention of said automated interface program as recited in claim 16, wherein the step of re-ordering the attention focus list according to explicit commands further comprises preventing a match from being generated for a first category that is explicitly mentioned in a suppress command within a second category for which a match was generated.

20. The method for focusing the attention of said automated interface program as recited in claim 19, wherein the step of preventing a match from being generated for a first category further comprises generating a match for the first category for which a match was previously prevented from being generated, said first category explicitly mentioned in a recover command within a second category for which a match is generated.

21. The method for focusing the attention of said automated interface program as recited in claim 16, wherein the step of re-ordering the attention focus list further comprises preventing a match from being generated in a category that is explicitly mentioned in an initial suppress command, said initial suppress command being executed upon compilation.

22. A system for automatically focusing the attention of a virtual robot interacting with users in natural language, the system comprising:

an interface for receiving natural language input from a user, wherein the natural language input includes at least one natural language component; and

a processor comprising a computer usable medium including computer readable program code embodied in said medium for interacting with a user in natural language, said computer readable program code including;

computer readable program code for defining at least one category associated with actions executable by the processor during interaction with a user;

computer readable program code for maintaining an attention focus list comprising an ordered list of one or more categories;

computer readable program code for recognizing at least one natural language component within the natural language input from said user;

computer readable program code for examining at least one category in the attention focus list to determine whether the at least one natural language component generates a match with the at least one examined category, wherein the order in which categories are examined is influenced by the order of the categories in the attention focus list; and

computer readable program code for re-ordering for the categories of said attention focus list, wherein the new ordering of the categories is influenced by the categories in the attention focus list for which a match is generated.

23. A computer program product for interacting with a user in natural language, said computer program product comprising:

computer readable program code for defining at least one category associated with actions executable by the computer program product during interaction with the user;

computer readable program code for maintaining an attention focus list comprising one or more categories arranged in an order;

computer readable program code for receiving natural language input from the user;

computer readable program code for parsing natural language input from the user into at least one natural language component;

computer readable program code for examining at least one category in the attention focus list to determine whether the at least one natural language component generates a match with the at least one examined category, wherein the order in which categories are examined is influenced by the order of the attention focus list; and

computer readable program code for generating a new order for the categories of the attention focus list, said new order being influenced by the examined categories which generated a match with the at least one natural language component.

24. A method of automated learning based on interactions with a user in natural language, said method comprising:

maintaining at least one category comprising at least one script, wherein the at least one script comprises at least one condition associated with one or more actions, wherein if the condition is satisfied, the actions associated with the condition are executed;

defining a set of labels, wherein each label is associated with a user input sample in natural language;

extracting a set of candidate features from the user input sample;

determining a subset of said candidate features which are associated with said example labels; and

generating scripts for the at least one activatable category based on the subset of candidate features.

25. The method for automated learning based on interactions with a user in natural language as set forth in claim 24, wherein the step of defining a set of labels further comprises defining example labels based on properties of a raw data stream.

26. The method for automated learning based on interactions with a user in natural language as set forth in claim 25, wherein the raw data stream comprises text of previous interactions with a user in natural language.

27. The method for automated learning based on interactions with a user in natural language as set forth in claim 24, wherein the step of extracting a set of candidate features further comprises reducing text input into a vector of one or more word tokens.

28. The method for automated learning based on interactions with a user in natural language as set forth in claim 27, wherein the step of extracting a set of candidate features further comprises converting said word tokens into symbolic codes.

29. The method for automated learning based on interactions with a user in natural language as set forth in claim 28, wherein the symbolic codes encode the position of a word token within text input.

30. The method for automated learning based on interactions with a user in natural language as set forth in claim 24, wherein the step of extracting a set of candidate features further comprises:

maintaining a feature dictionary comprising a set of feature dictionary entries, wherein each entry is associated with a unique feature, wherein each feature is associated with at least one label, and a counter value is associated with each label, wherein the counter value comprises a count of the number of times a feature occurs in the user input sample associated with the label.

31. The method for automated learning based on interactions with a user in natural language as set forth in claim 24, wherein the step of determining a subset of candidate features further comprises determining estimated joint probabilities of occurrences of feature-label pairs.

32. The method for automated learning based on interactions with a user in natural language as set forth in claim 31, wherein the step of determining a subset of candidate features further comprises computing conditional probabilities of labels on features and conditional probability of features on labels.

33. The method for automated learning based on interactions with a user in natural language as set forth in claim 32, wherein the step of determining a subset of candidate features further comprises determining reliably predictive features from conditional probabilities.

34. The method for automated learning based on interactions with a user in natural language as set forth in claim 33, wherein the step of determining reliably predictive features from conditional probabilities further inclueds using a first threshold value to evaluate whether a feature is strongly predictive of an associated label.

35. The method for automated learning based on interactions with a user in natural language as set forth in claim 33, wherein the step of determining reliably predictive features from conditional probabilities further includes using a second threshold value to evaluate the frequency of occurrence of a feature in assoociation with the occurrence of an associated label.

36. The method for automated learning based on interactions with a user in natural language as set forth in claim 33, wherein the step of generating scripts for categories further comprises generating scripts for categories based on the reliably predictive features.