System and method for selecting responses to user input in an automated interface program

• US 6,604,090 B1
• Filed: 02/03/1998
• Issued: 08/05/2003
• Est. Priority Date: 06/04/1997
• Status: Expired due to Term

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: NativeMinds, Inc. (Healthstream Incorporated)
• Inventors: Benson, Scott S., Tackett, Walter A.
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/018,213
• Time in Patent Office: 2,009 Days
• Field of Search: 706/11, 395/613, 345/352-354, 345/146, 345/348-351, 345/978, 707/5
• US Class Current: 706/11
• 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]
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 715/978 Audio interaction as part of an operator interface

Abstract

An automated interface program designed to interact and communicate with users, is disclosed that defines a list of categories activatable by the program; identifies a set of categories activated by user input; selects another set of categories from the activated categories based upon a metric and thereafter executes actions associated with the selected categories. The metric is a computed value based on conditions located within each category. The metric gives an estimate of the appropriateness of the particular response included in an activated category. This estimate is currently based on the current input and the current state of the automated interface program at the time user input is entered.

Claims

1. In an automated interface program designed to interact and communicate with users, said program executing actions when a category among a set of predefined categories is activated, a method for selecting categories and executing actions associated with said categories, the steps of said method comprising:

(a) defining a list of categories activatable by said program in response to user input;

(b) for an input received from a user,

(i) identifying a set of categories activated by said input, wherein each category in said set matches the received user input;

(ii) assigning an appropriateness value to each category in said set of activated categories, wherein the appropriateness value is influenced by the likelihood that the category matches a user input;

(iii) selecting a category from said set of activated categories, wherein the appropriateness value is a first criteria for selecting said category; and

(iv) executing actions associated with said selected category.

2. The method for selecting categories and executing actions associated with said categories as recited in claim 1, wherein the step of defining a list of categories further comprises:

defining a set of priority categories such that said priority categories are executed before all other categories.

3. The method for selecting categories and executing actions associated with said categories as recited in claim 1, wherein the step of defining a list of categories further comprises:

defining a set of default categories such that said default categories are executed after all other categories.

4. The method for selecting categories and executing actions associated with said categories as recited in claim 1, wherein the step of defining a list of categories further comprises:

defining a set of default categories such that said default categories are executed if no other categories produce output to the user.

5. The method for selecting categories and executing actions associated with said categories as recited in claim 1, wherein the step of defining a list of categories further comprises:

defining a set of sequence categories such that said sequence categories are executed only when called by other categories.

6. The method for selecting categories and executing actions associated with said categories as recited in claim 1, wherein the step of defining a list of categories further comprises:

defining a set of sequence categories such that said sequence categories produce a series of sequential interactions with the user.

7. The method for selecting categories and executing actions associated with said categories as recited in claim 1, wherein the step of identifying a first set of categories activated by said input further comprises:

identifying a first set comprising priority, standard, sequence, and default categories activated by said input.

8. The method for selecting categories and executing actions associated with said categories as recited in claim 7, wherein the step of identifying a first set of categories activated by said input further comprises:

testing conditions in categories such that said category is activated if said condition is satisfied by said input.

9. The methods of selecting categories and executing actions associated with said categories as recited in claim 8, wherein the step of testing conditions further comprises:

(i) constructing a graph comprising a plurality of nodes and edges between the nodes, in which the nodes represent predetermined states of user input and the edges represent user input transitions between said nodes; and

(ii) associating a set of final nodes with conditions within categories, wherein one of said conditions is satisfied if transitions upon a given user input place the state of user input at the associated final node.

10. The method for selecting categories and executing actions associated with said categories as recited in claim 9, wherein in the step of selecting a category from said set of activated categories, wherein the appropriateness value is a first criteria for selecting said category, the determination of the appropriateness value is based on the length of a path in the graph traversed to a final node of a condition.

11. The method for selecting categories and executing actions associated with said categories as recited in claim 10, wherein in the step of selecting a category from said set of activated categories, wherein the appropriateness value is a first criteria for selecting said category, and a second criteria for selecting said category comprises:

selecting a category among said set of categories for which a path length is maximized.

12. The method for selecting categories and executing actions associated with said categories as recited in claim 7, wherein the step of identifying a first set of categories activated by said input further comprises:

(i) testing conditions in said priority categories such that a priority category is activated if said condition is satisfied by said input;

(ii) identifying previously activated sequence categories that have yet to complete their actions according to a previous input;

(iii) testing conditions in said standard categories such that a standard category is activated if said condition is satisfied by said input; and

(iv) testing conditions in said default categories such that a default category is activated if said condition is satisfied by said input.

13. In an automated interface program designed to interact and communicate with users, said program executing actions when a category among a set of predefined categories is activated, a mechanism for selecting categories and executing actions associated with said categories, said mechanism comprising:

means for defining a list of categories activatable by said program in response to user input;

means for identifying a set of categories activated by said input, wherein each category in said set matches the received user input;

means for assigning an appropriateness value to each category in said set of activated categories, wherein the appropriateness value is influenced by the likelihood that the category matches a user input;

means for selecting a category from said set of activated categories, wherein the appropriateness value is a criteria for selecting said category; and

means for executing actions associated with said selected category.

14. In an automated interface program designed to interact and communicate with users, said program executing actions when a category among a set of predefined categories is activated, a method for selecting categories and executing actions associated with said categories, the steps of said method comprising:

(a) defining a list of categories activatable by said program in response to user input;

(b) for an input received from a user,

(i) selecting a set of activated categories based upon an appropriateness metric, said appropriateness metric computed based on the conditions located within each said activated category and influenced by the likelihood that the category matches a user input; and

(ii) executing actions associated with said set of categories.

15. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

said appropriateness metric computed based on conditions in categories such that said category is activated if said condition is satisfied by said input.

16. The methods of selecting categories and executing actions associated with said categories as recited in claim 15, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

(i) constructing a graph in which the nodes represent predetermined states of user input and the edges represent user input transitions between said nodes; and

(ii) associating a set of final nodes with said conditions within categories, wherein one of said conditions is satisfied if transitions upon a given user input place the state of user input at the associated final node.

17. The method for selecting categories and executing actions associated with said categories as recited in claim 16, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

said appropriateness metric based on the length of a path in the graph traversed to a final node of a condition.

18. The method for selecting categories and executing actions associated with said categories as recited in claim 17, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

selecting categories among said first set of categories for which a path length is maximized.

19. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of categories based upon an appropriateness metric further comprises:

said appropriateness metric based on a frequency with which said conditions are expected to be true.

20. The method for selecting categories and executing actions associated with said categories as recited in claim 19, wherein said appropriateness metric further comprises:

(i) defining conditions to be patterns of user input; and

(ii) estimating the frequency of conditions occurring in user input.

21. The method for selecting categories and executing actions associated with said categories as recited in claim 20, wherein the step of estimating the frequency of conditions occurring in user input further comprises:

estimating the frequency of conditions occurring in example user inputs included in category scripts.

22. The method for selecting categories and executing actions associated with said categories as recited in claim 19, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

selecting categories for which the conditions associated with the categories are least likely to be true.

23. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

(i) associating a specificity value with the at least one category; and

(ii) selecting said categories that have specificity values associated with a higher degree of specificity, among the categories that match the input received from the user.

24. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

said metric being a numeric value computed for each activated category, the value being based upon the frequency of matched words, partial words, and symbols found in the current input with words, partial words, and symbols found in the conditional clauses located within the category.

25. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

selecting said category having more matched words, partial words, and symbols in the conditional clause located within the category.

26. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

said appropriateness metric being based on the testing of a Boolean variable, said Boolean variable associated with a memory attribute.

27. The method for selecting categories and executing actions associated with said categories as recited in claim 14, wherein the step of selecting a set of activated categories based upon an appropriateness metric further comprises:

selecting a category from among said set of activated categories wherein two or more categories have the same computed appropriateness metric.

28. The method for selecting categories and executing actions associated with said categories as recited in claim 27, wherein the step of selecting a category from among a set of activated categories wherein two or more categories have the same computed appropriateness metric further comprises:

selecting the category having the highest position on a focus of attention stack.