Simple approach to case-based reasoning for data navigation tasks

• US 5,717,835 A
• Filed: 01/11/1995
• Issued: 02/10/1998
• Est. Priority Date: 01/11/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hellerstein, Joseph
• Primary Examiner(s): Downs, Robert W.
• Assistant Examiner(s): Smith, Jeffrey S.
• Application Number:
  US08/371,182
• Time in Patent Office: 1,126 Days
• Field of Search: 395/51, 395/60, 395/62, 395/50, 395/54, 395/75, 395/77
• US Class Current: 706/46
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

An architecture and key algorithms are presented that simplify the implementation and improve the functionality of knowledge-based systems that employ case-based reasoning for data navigation tasks (e.g., solving help desk problems using a database of past problem instances). The various embodiments of the invention improve on the state-of-the-art in several respects: (a) provides greatly increased flexibility in choosing attributes relevant to a case in that choices are made dynamically at case acquisition instead of statically when the knowledge-based system is designed; (b) increased system flexibility and decreased system complexity by not requiring designers to specify the manner in which attribute values are compared; (c) simplified system design by avoiding the use of similarity metrics; (d) allows for the incremental acquisition of data in problem instances, instead of requiring that all potentially relevant data be collected; and (e) provides a way to explain why a problem solution was chosen. Case acquisition is accomplished by having end-users replay the steps taken to solve a problem instance. Each such step constitutes a navigation element that consists of: (i) a test expressing the conditions under which the navigation is done; (ii) a text description explaining the step; and (iii) a database query expressing the next navigation. Algorithms are presented for case acquisition, case retrieval, and case removal. The case repository is structured as a graph of navigation elements that, under appropriate circumstances, combines into a single node those navigation elements common to multiple cases.

Claims

1. A method of data navigation employing a knowledge system that uses case-based reasoning to compare a new problem instance with a case repository of past problem instances structured as an ordered set of navigation elements, said method comprising:

communicating problem data for the new problem instance into the knowledge system;

retrieving from the case repository a past problem instance relevant to the problem data;

wherein a navigation element associated with the past problem instance comprises an ordered triple including;

a test expressing data navigation conditions;

a text description explaining the navigation element; and

a query; and

generating information about the new problem instance based on the navigation element.

2. The method of claim 1 wherein the case repository comprises a directed graph structure wherein navigation elements common to past problem instances are combined.

3. The method of claim 1, wherein the query represents a database query indexing a next member in the ordered set of navigation elements, said method further comprising:

retrieving the next member in the ordered set of navigation elements.

4. The method of claim 1, further comprising:

collecting additional problem data which would make an additional past problem instance relevant to the new problem instance; and

iterating said retrieving step and said collecting step until the new problem instance is resolved or all past problem instances relevant to the new problem instance have been retrieved.

5. The method of claim 4, further comprising:

identifying an invalid past problem instance; and

removing from the case repository the invalid past problem instance.

6. The method of claim 4 wherein said all past problem instances relevant to the new problem instance have been retrieved and none contain the solution to the new problem instance, further comprising:

specifying a navigation element for input to the knowledge system;

appending, responsive to said specifying step, the navigation element to an ordered set of navigation elements for the new problem instance;

repeating said specifying step and said appending step until the new problem instance is resolved; and

updating, responsive to said repeating step, the case repository with the ordered set of navigation elements for the new problem instance.

7. The method of claim 6 wherein the case repository is a data structure having a plurality of nodes referencing navigation elements and wherein said updating step further comprises:

searching the case repository for a sequence of nodes referencing navigation elements which correspond to a sequence of the ordered set of navigation elements;

revising, responsive to said searching step, the case repository to incorporate the new problem instance;

incorporating a new node referencing navigation elements for an ordered navigation element not found in said searching step; and

repeating said searching, revising, and incorporating steps until the new problem instance is added to the case repository.

23. The method of claim 3, wherein the next member is a last navigation element which includes:

a text description having a solution for the new problem instance; and

a null query.

24. The method of claim 1, further comprising:

invoking a program to take an action based on the query to solve the new problem instance.

25. The method of claim 1, wherein the case repository of past problem instances is a database of information, said method further comprising:

said communicating problem data includes communicating an ad hoc database query; and

said retrieving step includes querying the database and retrieving information relevant to the database query.

8. A method of generating a case repository of problem instances for use in a knowledge system for data navigation wherein said problem instances are structured as an ordered set of navigation elements stored in the case repository, comprising:

specifying a navigation element corresponding to a new problem instance for input to the knowledge system, wherein the navigation element comprises an ordered triple including;

a test expressing data navigation conditions;

a text description explaining the navigation element; and

a query;

appending, responsive to said specifying step, the navigation element to the set of ordered navigation elements;

repeating said specifying and appending steps until the problem instance is resolved; and

updating the case repository with the ordered set of navigation elements corresponding to the new problem instance.

9. The method of claim 8 wherein the case repository is a data structure having a plurality of nodes referencing navigation elements and wherein said updating step further comprises:

searching the case repository for a sequence of nodes referencing navigation elements which correspond to a sequence of navigation elements for the new problem instance;

revising a sequence of nodes found in said searching step to incorporate the new problem instance;

incorporating a new node referencing navigation elements for an ordered navigation element not found in said searching step; and

repeating said searching, updating, and incorporating steps until the new problem instance is added to the case repository.

10. A case-based knowledge system for data navigation having a processor adapted to compare a new problem instance with past problem instances, said system comprising:

a case repository for storing the past problem instances wherein the past problem instances are structured as an ordered set of navigation elements;

a case retrieval function for retrieving from the case repository, a past problem instance relevant to the new problem instance wherein a navigation element associated with the past problem instance is an ordered triple including;

a test expressing data navigation conditions;

a text description explaining the navigation element; and

a query; and

a user interface for routing the new problem instance to, and a retrieved past problem instance from, the case retrieval function.

11. The system of claim 10 wherein the user interface routes the new problem instance to and from related applications.

12. The system of claim 10 wherein the the query represents a database query for retrieving a next member in the ordered set of navigation elements, said system further comprising:

means for generating a database query indexing a next member in the ordered set of navigation elements.

13. The system of claim 10, further comprising:

said case retrieval function including logic for iteratively retrieving from the case repository, all past problem instances relevant to the new problem instance and all past problem instances whose relevance is dependent upon receiving additional new problem instance data, until the new problem instance is resolved or said all past problem instances relevant to the new problem instance have been retrieved.

14. The system of claim 13, further comprising:

means for identifying an invalid past problem instance,

a case removal function for removing the invalid past problem instance from the case repository.

15. The system of claim 10 wherein the case repository comprises a directed graph structure wherein navigation elements common to past problem instances are combined.

16. The system of claim 15 wherein said all past problem instances relevant to the new problem instance have been retrieved and none contain the solution to the new problem instance, further comprising:

a case acquisition function for creating an ordered set of navigation elements for the new problem instance and updating the case repository with the ordered set of navigation elements created;

wherein the user interface is adapted to route the navigation elements for the new problem instance to the case acquisition function.

17. The system of claim 16 wherein the case repository is a data structure having a plurality of nodes referencing navigation elements and wherein said case acquisition function further comprises:

means for iteratively searching and revising the case repository to incorporate a sequence of the navigation elements for the new problem instance common to past problem instances;

wherein the ordered set of navigation elements for the new problem instance are added to the case repository.

20. The system of claim 13 wherein the next member is a last navigation element which includes:

a text description having a solution for the new problem instance; and

a null query.

21. The system of claim 10, further comprising:

means for invoking a program, coupled to the case retrieval function, to take an action based on the query to solve the new problem instance.

22. The system of claim 10, wherein the case repository of past problem instances is a database of information and the problem data includes an ad hoc database query;

and

said case retrieval function includes logic for querying the database and retrieving information relevant to the database query.

18. A case-based knowledge system for data navigation having a processor adapted to compare a new problem instance with past problem instances, said system comprising:

a case repository for storing the past problem instances as an ordered set of navigation elements;

a case acquisition function for iteratively creating the ordered set of navigation elements corresponding to the new problem instance and updating the case repository with the ordered set of navigation elements created;

wherein a navigation element associated with the new problem instance is an ordered triple including;

a test expressing data navigation conditions;

a text description explaining the navigation element; and

a query, and

a user interface adapted to route the navigation elements for the new problem instance to the case acquisition function.

19. The system of claim 18 wherein the case repository comprises a directed graph structure wherein navigation elements common to past problem instances are combined.

26. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for data navigation wherein a knowledge system uses case-based reasoning to compare a new instance with a case repository of past instances, said method steps comprising:

communicating data for the new instance into the knowledge system;

retrieving from the case repository a past instance relevant to the data;

wherein the past instance is an ordered set of navigation elements and wherein a navigation element associated with the past instance comprises an ordered triple including;

a test expressing data navigation conditions;

a text description explaining the navigation element; and

a query; and

generating information about the new instance based on the navigation element.

27. The program storage device of claim 26, wherein the query represents a database query indexing a next member in the ordered set of navigation elements, said method comprising the step of:

retrieving the next member in the ordered set of navigation elements.

28. The program storage device of claim 26, said method further comprising the steps of:

collecting additional data which would make an additional past instance relevant to the new instance; and

iterating said retrieving step and said collecting step until the new instance is resolved or all past instances relevant to the new instance have been retrieved.

29. The program storage device of claim 27 wherein the next member is a last navigation element which includes a null query.

30. The program storage device of claim 26, further comprising the steps of:

invoking a program to take an action relevant to the new instance, based on the query.

31. The program storage device of claim 26, wherein the case repository is a database, said method further comprising the steps of:

said step of communicating data includes the step of communicating an ad hoc database query; and

said retrieving step includes the step of retrieving information relevant to the database query.

32. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of generating a case repository of instances for use in a knowledge system using case-based reasoning wherein the instances are structured as an ordered set of navigation elements stored in the case repository, comprising the method steps of:

specifying one or more navigation elements corresponding to a new instance for input to the knowledge system, wherein a navigation element comprises an ordered triple including;

a test expressing data navigation conditions;

a text description explaining the navigation element; and

a query;

appending, responsive to said specifying step, the navigation element to the set of ordered navigation elements; and

updating the case repository with the one or more navigation elements corresponding to the new instance.