Method and System for Case-Based Reasoning Utilizing a Belief Network

The present invention relates generally to data processing systems and, more particularly, to case-based reasoning systems.

The advent of artificial intelligence within computer science has brought an abundance of decision-support systems. A decision-support system is a computer system in which decisions, typically rendered by humans, are recommended and sometimes made by the computer system. In creating decision-support systems, computer scientists seek to provide decisions with as high a level of accuracy as possible. Thus, computer scientists strive to create decision-support systems that are equivalent to or more accurate than a human expert. Applications of decision-support systems include medical diagnosis, troubleshooting computer networks, customer service or other systems wherein a decision is based upon identifiable criteria.

One type of decision-support system employs case-based reasoning to assist in making decisions. Case-based reasoning is an approach to problem solving based on the retrieval and adaptation of cases. A case is a problem resolution scenario including the description of the problem to be resolved and one or more associated solutions to the problem. Conventional case-based reasoning ("CBR") systems utilize a five-step problem solving process. First, a user inputs a description of a problem (the "problem description") into the CBR system. The CBR system next accesses a database of cases which contains previously observed problem resolution scenarios and retrieves the closest matching cases to the problem as input by the user (the "current problem"). The CBR system then utilizes the current problem and the cases retrieved from the database to generate a solution to the current problem. After a solution is generated, the solution is applied to the current problem and feedback is gained from the user as to whether the solution fixed the current problem. Finally, if the solution solved the current problem, the solution is added to the case base for use in future problem solving.

One example of an application of a conventional CBR system is utilized by a customer service organization of a computer company. This conventional CBR system is utilized by the customer service organization of the company for handling phone calls from the customers of the company. The customer service CBR system contains hundreds of cases relating to problems associated with the use of products sold by the company. When customers call the customer service organization, customer service representatives access the customer service CBR system for help in diagnosing the problems of the customers. The customer service CBR system maintains a database and upon invocation, the CBR system retrieves similar cases from the database to the problem of the customer and presents the cases to the customer service representative. The customer service representative then utilizes the cases retrieved from the database to suggest solutions to the problem of the customer. Thus, the customer service representative must manually determine solutions to the problem of the user. In addition, the customer service CBR system suffers from the same limitations as those of conventional CBR systems. That is, conventional CBR systems must store hundreds of cases and conventional CBR systems utilize a heuristic method for problem solving. Since there is no facility for updating the heuristic method of conventional CBR systems, when conventional CBR systems produce an error (e.g., incorrect problem solving), the errors will continue without correction.

In accordance with a first aspect of the present invention, a case-based decision support system is provided. The case-based decision support system of the present invention contains a storage device further containing a belief network for storing knowledge obtained from observed cases and for suggesting solutions to problems encountered by a user and a memory. The memory of the case-based decision support system of the first aspect of the present invention further comprises an authoring component for receiving information from the user, for creating the belief network, and for storing the created belief network into the storage device. The memory of the case-based decision support system of the first aspect of the present invention further comprises a reasoning component for receiving input from the user, for accessing the belief network, and for generating a resolution to the problem encountered by the user.

In accordance with the second aspect of the present invention a method is executed in a computer system containing a belief network. In accordance with this method of the second aspect of the present invention, the preferred embodiment receives input from the user, generates a resolution to the encountered problem of the user, and adjusts the probabilities in the belief network in response to the generated resolution.

FIG. 1 depicts an example belief network.

FIG. 2 depicts a computer system suitable for practicing a preferred embodiment of the present invention.

FIGS. 3A and 3B depict a relationship between data elements utilized by the preferred embodiment of the present invention.

FIG. 4 depicts the reasoner component, the author component, and the database component of the preferred embodiment within the computer system of FIG. 2.

FIG. 5 depicts a functional overview of the preferred embodiment of the present invention.

FIGS. 6A, 6B, 6C, 6D, 6E and 6F depict screens displayed to a user by the author component of the preferred embodiment.

FIGS. 7A and 7B depict a flowchart of steps performed by the author component of the preferred embodiment of the present invention.

FIG. 8 depicts the belief network of the preferred embodiment of the present invention.

FIG. 9 depicts a more detailed diagram of the concepts in the belief network of FIG. 8.

FIGS. 10A and 10B depict a flowchart of steps performed by the reasoner component of the preferred embodiment of the present invention.

FIG. 11 depicts a flowchart of steps performed by the interpret text routine of the preferred embodiment of the present invention.

FIG. 12 depicts a flowchart of steps performed by the update probabilities routine of the preferred embodiment of the present invention.

The preferred embodiment of the present invention provides an improved system and method for creating case-based reasoning systems. The case-based reasoning system of the preferred embodiment utilizes a belief network to provide higher accuracy in resolving problems and for increasing the accuracy after each case is observed. The case-based reasoning system of the preferred embodiment provides a more accurate system for problem solving by utilizing the knowledge learned from previously observed cases instead of storing previously observed cases, thereby reducing storage requirements. The knowledge obtained from previously observed cases is stored in the belief network. After observing each case, the belief network utilized by the preferred embodiment is updated so as to reflect the observed cases. This updating modifies probabilities contained within the belief network to provide for more accurate problem solving upon the next invocation of the CBR system of the preferred embodiment. In addition, this updating can correct errors so that the errors do not continually occur.

A belief network is a representation of the probabilistic relationships among states of a portion of the world. The states of the world in a belief network can change and are, therefore, called variables. A belief network is expressed as an acyclic directed graph where the variables correspond to nodes and the relationships between the nodes correspond to arcs. FIG. 1 depicts an example belief network 101. In the depicted belief networks there are three variables, X.sub.1, X.sub.2, and X.sub.3, which are represented by nodes 102, 106 and 110, respectively. The example belief network contains two arcs 104 and 108. Associated with each variable in a belief network is a set of probability distributions. Using conditional probability notation, the set of probability distributions for a variable can be denoted by Pr(x.sub.i .vertline.II.sub.i), where "Pr" refers to the probability distribution and "II.sub.i " denotes the parents of variable X.sub.i. Thus, this expression reads as follows: the probability distribution for variable X.sub.i given the parents of X.sub.i. For example, X.sub.1 is the parent of X.sub.2. The probability distributions specify the strength of the relationships between variables. For instance, if X.sub.1 has two states (true and false), then associated with X.sub.1 is a single probability distribution Pr(x.sub.1 .vertline..o slashed.) and associated with X.sub.2 are two probability distributions Pr(x.sub.2 .vertline.x.sup.1 =t) and Pr(x.sub.2 .vertline.x.sub.1 =f). Probability distributions can be of two types: prior and posterior. A prior probability distribution refers to the probability distribution before data is observed. A posterior probability distribution is the probability distribution after data is observed.

The arcs in a belief network convey dependence between nodes. When there is an arc between a first node and a second node, the probability distribution of the first node depends upon the value of the second node when the direction of the arc points from the second node to the first node. For example, node 106 depends upon node 102. Therefore, node 106 is said to be conditionally dependent. Missing arcs in a belief network convey conditional independence. For example, node 102 and node 110 are conditionally independent given node 106. However, two variables indirectly connected through intermediate variables are conditionally dependent given knowledge of the values ("states") of the intermediate variables. Therefore, if the value for X.sub.2 is known, X.sub.1 and X.sub.3 are conditionally dependent.

In other words, sets of variables X and Y are said to be conditionally independent, given a set of variables Z, if the probability distribution for X given Z does not depend on Y. If Z is empty, however, X and Y are said to be "independent" as opposed to conditionally independent. If X and Y are not conditionally independent given Z, X and Y are said to be conditionally dependent.

The variables used for each node may be of different types. Specifically, variables may be of two types: discrete or continuous. A discrete variable has a countable number of states, either finite or infinite, whereas a continuous variable is a variable that has an uncountably infinite number of states. An example of a discrete variable is a Boolean variable. Such a variable can assume only one of two states: "true" or "false." An example of a continuous variable is a variable that may assume any real value between -1 and 1.

FIG. 2 depicts a computer system suitable for practicing a preferred embodiment of the present invention. The computer system 200 contains a central processing unit (CPU) 202, a memory 204, and a secondary storage device 206. The CPU 202 is responsible for accessing data and computer programs on the secondary storage device 206. In addition, the CPU 202 is responsible for transferring computer programs into the memory 204 and executing the computer programs once resident in the memory. One skilled in the art will appreciate that a computer suitable for practicing the preferred embodiment of the present invention can contain additional or different components.

In order to provide problem resolution, the preferred embodiment maintains information relating to cases. This information comprises six data elements: issues, causes, symptoms, resolutions, terms, and alternates. An "issue" represents a problem encountered by a user. As depicted in FIG. 3A, each issue 302 may have one or more causes 304, 306, symptoms 308, 310, 312, or resolutions 314 associated with the issue. A "cause" 304, 306 represents a single, independent factor whose presence is required for an issue 302 to exist. Causes 304, 306 represent one factor as opposed to compound factors and are independent of all other causes. That is, the set of causes 304, 306 for an issue 302 represents the basic elements that must be present for an issue to appear. For example, if an issue 302 has two causes 304, 306 associated with the issue, the issue is considered present only if all two causes are present.

A "symptom" 308, 310, 312 represents one or more factors which indicate a problem (issue) encountered by a user. For example, if the issue 302 were that the user was experiencing a software conflict where two pieces of software are version-incompatible, there may be symptoms 308, 310, 312 related to the issue indicating the presence of the issue. Such symptoms 308, 310, 312 may include a mouse device being unresponsive or the computer system being inoperable. A "resolution" 314 is a potential solution to the problem encountered by the user. Associated with each resolution 314 is a "cost". The cost is based on the monetary cost of implementing the resolution as well as the complexity of implementing the resolution. The complexity is expressed in terms of the amount of time necessary to implement the resolution. The preferred embodiment determines the cost associated with a resolution by utilizing a cost function. The cost function is a linear function receiving two parameters: the monetary cost and the complexity. The preferred embodiment uses the term "concept" to refer generically to a cause, symptom, or resolution.

A "term" is a word or phrase that may be used to describe a concept. Thus, as depicted in FIG. 3B, there may be many terms 318, 320, 322, 324 associated with each concept 316. Associated with a term 318, 320, 322, 324 may be one or more alternates 326, 328, 330, 332, 334, 336. "Alternates" 326, 328, 330, 332, 334, 336 are synonyms or abbreviations for one or more terms 318, 320, 322, 324. Each alternate 326, 328, 330, 332, 334, 336, however, is synonymous with all concepts involving the term 318, 320, 322, 324 associated with the alternate. That is, the alternate 326, 328, 330, 332, 334, 336 cannot adopt a different meaning for different concepts.

The CBR system of the present invention contains three components: an author component, a database component, and a reasoner component. FIG. 4 depicts the components of the present invention within computer 200. The memory 204 of computer 200 contains the author component 404 and the reasoner component 402. The secondary storage device 206 of the computer 200 contains the database component 406. The author component 404 is responsible for receiving user input, creating a belief network from the user input and storing the belief network into the database component 406. The belief network is stored in the database component 406 as a collection of records. The database component 406 is responsible for maintaining the belief network. The reasoner component 402 receives input from a user identifying a problem encountered by the user ("problem description"), accesses the belief network stored in the database component 406, and assists the user in solving the problem referred to by the problem description ("current problem"). The reasoner component 402 assists the user in solving the current problem by suggesting observations and resolutions to the current problem.

In utilizing the case-based reasoning system of the preferred embodiment, as shown in FIG. 5, a user invokes the author component 404 specifying information so that the author component can then create a belief network (step 502). The information specified by the user may include issues, concepts, terms, and alternates. After the author component 404 has been invoked and the belief network has been created, the user may then invoke the reasoner component for assistance with problem resolution (step 504). The reasoner component 402, upon invocation, will suggest questions to be answered by the user and generate ranked resolutions for the current problem (step 506). That is, the resolutions are listed in order of the likelihood that each resolution will solve the current problem and the cost associated with each resolution. The user may then implement a resolution to determine if the implemented resolution solves the current problem. Each of the above-mentioned steps will be discussed in more detail below. Step 502 is performed for initialization of the case-based reasoning system of the preferred embodiment. As such, this step may be performed off-line. Steps 504 and 506 are performed as part of the normal processing of the case-based reasoning system of the preferred embodiment.

As previously stated, the author component 404 is utilized to define issues and to associate concepts with the defined issues. In addition, the author component 404 is used for associating terms with the concepts, as well as associating alternates with the terms. After a user has input all of the previously described information into the author component 404, the author component 404 creates a belief network and stores the created belief network into the database component 406. In order to allow the user to input information into the author component 404, as depicted in FIGS. 6A, 6B, 6C, 6D, 6E, and 6F, the author component provides a number of screens that are displayed to the user: a main screen 602, a browse screen 612, an issue screen 622, a cause screen 640, a symptom screen 660, and a resolution screen 680. The main screen 602 of the author component 404 allows the user to display the browse screen 612 or the issue screen 622. The user displays the browse screen 612 or the issue screen 622 by selecting the browse screen button 604 or the issue screen button 606, respectively.

The browse screen 612 is used for traversing the belief network and for allowing the user to view and modify all of the information within the belief network. When viewing the browse screen 612, the user may select the locus pull down menu 614 and designate whether to display issues, causes, symptoms, resolutions, terms or alternates within the browse display 616. In addition, the user may select a direction for traversing the belief network by selecting a direction within the direction pull down menu 614. Upon viewing issues, concepts, terms or alternates within the display 616, the user may select an issue, concept, term or alternate and then choose to view information relating to the selection by selecting the view button 618 or the user may edit the selection by selecting the edit button 620.

The issue screen 622 is utilized to perform processing associated with issues. The issue display 625 depicts all issues currently within the belief network. After selecting an issue in the issue display 625, the user may choose to add, modify, or delete an issue by selecting the add button 627, the modify button 629 or the delete button 631, respectively. The title field 623 contains the name for a selected issue within the issue display 625. The notes field 630 contains notes associated with a selected issue within the issue display 625. After an issue has been selected within the issue display 625, the user may view the cause screen, the symptom screen, or the resolution screen to view or modify the causes associated with the selected issue, the symptoms associated with the selected issue, or the resolutions associated with the selected issue, respectively. In order to invoke the cause screen, the user selects the cause button 624. To view the symptom screen, the user selects the symptom button 626, and to view the resolution screen, the user selects the resolution button 628.

The cause screen 640 is utilized to perform processing associated with causes. Upon being confronted with the cause screen 640, the cause screen displays all of the causes associated with the selected issue in the cause display 642. The user may select a cause in the cause display 642 and choose to either add, modify, or delete a cause in the cause display 642. The user performs this functionality by selecting the add button 641, the modify button 643, or the delete button 645. If the user chooses to add a cause, the user inputs the cause name in the cause title field 648. The probability field 644 contains a probability indicating the likelihood that a selected cause within the cause display 642 will occur, regardless of any particular issue. The incidents field 646 contains the number of times that the selected cause in the cause display 642 was observed by the user. That is, the number of times, in the experience of the user, that the selected case was observed. Thus, the incidents is a confidence factor; the larger the number in the incidents field, the greater the confidence in the probability. After selecting a cause within the cause display 642, the user may assign terms to the selected cause by utilizing the term display 647. In assigning terms to the causes, the user can define a probability in the probability field 649 which indicates the likelihood that the term will be used to describe the associated cause. In addition, the user can input in the incidents field 650 the incidents for the term, which is the number of times that the selected cause was observed in the experience of the user and the term was used to indicate the selected cause. After defining terms for the selected cause, the user may associate alternates with the terms in the term display 647 by utilizing the alternate display 651.

The symptom screen 660 is utilized to perform processing associated with symptoms. The symptom screen 660 displays all of the symptoms associated with the selected issue in the symptom display 662. In utilizing the symptom screen 660, the user may choose to add a symptom, modify a symptom, or delete a symptom by selecting the add button 670, the modify button 672, or the delete button 674, respectively. If the user chooses to add a symptom, the user inputs the name of the symptom in the symptom title field 668. Associated with each symptom in the belief network, is a probability. The probability associated with each symptom is displayed in the probability field 664 and indicates the likelihood that a selected symptom in the symptom display 662 was associated with the selected issue in the experience of the user. The incidents field 666 contains the incidents, which is the number of times that a selected symptom was observed to be related to the selected issue. The user utilizes the term display 676 to associate terms with a selected symptom. Associated with each term is a probability displayed in the probability field 677 and the incidents displayed in the incidents field 678. The probability related to a term is the likelihood that the selected term will be associated with the selected symptom and the incidents related to a term is the number of times that the symptom was observed by the user and the term was used to indicate the symptom. The alternate display 679 allows the user to associate alternates with the terms in the term display 676.

The resolution screen 680 is utilized to perform processing associated with resolutions. The resolution screen 680 displays all of the resolutions associated with the selected issue in the resolution display 682. In utilizing the resolution screen 680, the user may add, modify, or delete a resolution by selecting the add button 692, the modify button 694, or the delete button 695, respectively. If the user chooses to add a resolution, the user inputs the name of the resolution in the resolution title field 690. Associated with each resolution is a probability, a cost, and incidents. The probability for a selected resolution is displayed in the probability field 684 and reflects the likelihood that the selected resolution will solve the selected issue. As previously stated, the cost associated with a selected resolution is displayed in the cost field 686 and reflects the monetary cost for implementing the selected resolution and the complexity for implementing the selected resolution. The incidents associated with a selected resolution is displayed in the incidents field 688 and reflects the number of times that the selected resolution solved the selected issue in the experience of the user. The term display 696 is used for associating terms with selected resolutions within the resolution display 682. Associated with each term in the term display 696 is a probability and incidents. The probability related to a term is displayed in the probability field 697 and reflects the likelihood that a term is associated with a selected resolution. The incidents related to a term is displayed in the incidents field 698 and reflects the number of times that a term was associated with a selected resolution in the experience of the user. The alternate display 699 is used for associating alternates with terms in the term display 696.

FIGS. 7A and 7B depict a flowchart of the steps performed by the author component 404 of the present invention. The first step the author component 404 performs is to read the records containing the belief network from the database component 406 (step 702). After reading the records containing the belief network, the author component 404 displays the main screen 602 to the user (step 703). When confronted with the main screen 602, the user may then select the issue screen 622 by selecting the issue screen button 606 (step 704). If the user does not select the issue screen 622, the user may invoke the browse screen 612 by selecting the browse screen button 604 wherein the user may traverse the belief network and view or modify all of the information contained in the belief network (step 708). After the user has utilized the browse screen 612, the user may cancel the browse screen and again view the main screen 602 (step 710). However, if the user selects the issue screen button 606, the author component 404 displays the issue screen 622 to the user (step 706). Upon being confronted with the issue screen 622, the user may add an issue or select a preexisting issue to view, modify or delete. The user may also add notes associated to the issue.

Upon selecting an existing issue or adding a new issue (the "indicated issue"), the user may invoke the cause screen 640, the symptom screen 660, or the resolution screen 680, by selecting either the cause button 624, the symptom button 626 or the resolution button 628, respectively. If the user selects the cause button 624 (step 714 in FIG. 7B), the author component 404 displays the cause screen 640 to the user (step 716). Upon being confronted with the cause screen 640, the user may associate new causes or existing causes with the indicated issue. After associating a new or an existing cause with the indicated issue, the user assigns a probability to the associated cause in the probability field 644. The user also indicates the incidents in the incidents field 646. The user then assigns terms for the cause. In assigning terms to the cause, the user defines a probability in the probability field 649 as well as the incidents for the term in the incidents field 650. After the terms have been defined, the user defines alternates for each term.

If, however, the user selects the symptom button 626 (step 718), the author component 404 displays the symptom screen 660 to the user (step 720). After displaying the symptom screen 660, the user can add, delete, or modify symptoms associated with the indicated issue. If the user adds or modifies a symptom associated with the issue, the user may adjust the probability associated with the symptom and the incidents associated with the symptom. The probability field 664 contains the probability and the incidents field 666 contains the incidents. The symptom screen also provides the user with the ability to assign terms to symptoms and alternates to terms similar to that as described relevant to the cause screen. If the user selects the resolution button 628 (step 722), the author component 404 displays the resolution screen 680 (step 724). After displaying the resolution screen 680, the user may add, modify, or delete resolutions associated with the indicated issue. When adding or modifying a resolution, the user can assign a probability associated with the resolution in the probability field 684. In addition, the user can input the incidents into the incidents field 688 and the cost associated with the resolution into the costs field 686. The resolution screen also provides the user with the ability to associate terms with the resolution and associate alternates with the terms similar to that described relevant to the cause screen. After the user has utilized the cause screen 640, the symptom screen 660, or the resolution screen 680, the user may go back to the main screen 602 to perform more processing (step 710). However, if the user has completed processing, the author component 404 updates the belief network in the database with the new or modified information and processing ends (step 712).

FIG. 8 depicts a logical representation of the belief network of the preferred embodiment as stored in the database component 406. The belief network of the preferred embodiment contains a node for each issue or problem that a user can encounter 802, nodes for the causes of each issue 804, nodes for the resolutions of each issue 806, and symptoms for each issue 808. All nodes in the belief network of the preferred embodiment correspond to Boolean variables. The issues 810, 812 depend upon the various causes associated with those issues as indicated by arcs 838, 840, 842, 844, and 846. For example, I.sub.1 810 depends from causes C.sub.1 814 and C.sub.2 816 as indicated by arcs 838 and 840. The issues in the belief network 810, 812 also depend from the resolutions 822, 824, 826 as indicated by arcs 848, 850, and 852. The nodes corresponding to the symptoms 828, 830, 832, 834, 836 in the belief network depend from the issues 810, 812 as indicated by arcs 854, 856, 858, 860, 862, and 864. As indicated, a cause can be related to more than one issue and more than one issue can be related to a symptom.

Each node in the belief network of the preferred embodiment is implemented as a record in the database component 406. Each arc in the belief network of the preferred embodiment is also implemented as a record in the database component 406. Specifically, the issue nodes 802 of the belief network of the preferred embodiment are stored in records according to the format depicted in Table 1.

The records in the database component 406 reflecting the cause nodes 804 adhere to the format indicated in Table 2.

The nodes 806 corresponding to the resolutions in the belief network of the preferred embodiment follow the record format depicted in Table 3.

The nodes reflecting the symptoms 808 in the belief network of the preferred embodiment adhere to the format depicted in Table 4.

Each arc 838, 840, 842, 844, and 846 depicting a relationship between the cause nodes 804 and the issue nodes 802 are implemented as records in the database component 406 according to the format depicted in Table 5.

The arcs 848, 850, and 852 indicating the association between the resolution nodes 806 and the issue nodes 802 are implemented as records in the database component 406 according to the format depicted in Table 6.

For each arc 854, 856, 858, 860, 862, and 864 indicating an association between the issue node 802 and the symptom nodes 808, there is a corresponding record in the database component 406 that follows the format depicted in Table 7.

FIG. 9 depicts a more detailed diagram of the concepts in the belief network of FIG. 8. As previously described, a concept is a cause, symptom, or resolution. Associated with each concept 902 can be a number of terms 904, 906, and 908 as indicated by arcs 936, 938, and 940. Further, associated with each term 904, 906, 908 can be a number of alternates 910, 912, 914, 916, 918, and 920 as indicated by arcs 922, 924, 926, 928, 930, 932, and 934. As depicted, more than one term 904, 906 may be associated with an alternate 914. The nodes 904, 906, and 908 corresponding to the terms in the belief network of the preferred embodiment are implemented as records in the database component 406. The records corresponding to the terms follow the format depicted in Table 8.

The nodes 910, 912, 914, 916, 918, and 920 corresponding to the alternates in the belief network of the preferred embodiment are implemented as records in the database component 406 following the format depicted in Table 9.

The arcs 922, 924, 926, 928, 930, 932, and 934 depicting an association between the terms and the alternates in the belief network of the preferred embodiment are implemented as records in the database component 406 according to the format depicted in Table 10.

The arcs 936, 938, and 940 depicting an association between a concept and the terms associated with the concept are implemented as records in the database component 406 according to the format depicted in Table 11.

Although the belief network of the preferred embodiment has been described as being stored in records of a database, one skilled in the art will recognize that other storage mechanisms can be used. In addition, although the records of the database component of the preferred embodiment have been described with a particular format, one skilled in the art will appreciate that additional or different fields can be used in the database component of the preferred embodiment.

As described relative to FIG. 5, the reasoner component 402 is responsible for accepting a problem description, assisting the user in solving the current problem by utilizing the belief network, and updating the probabilities in the belief network so as to increase the accuracy of the CBR system of the preferred embodiment for future invocations. In assisting the user with problem resolution, the reasoner component 402 utilizes a number of sets: I.sub.current, C.sub.obs, S.sub.obs, C.sub.poss, and S.sub.poss. The set I.sub.current contains a number of issues to be scored. That is, the set of issues considered relevant to the current problem and that are under investigation by the reasoner component. The set C.sub.obs contains the causes that have been observed by the user. The set S.sub.obs contains the symptoms that have been observed by the user. The set C.sub.poss contains causes suggested for observation by the reasoner component 402. The set S.sub.poss contains symptoms suggested for observation by the reasoner component 402.

In describing the processing of the reasoner component 402, it is helpful to utilize various symbols, which are described below:

The first step that the reasoner component 402 performs, as indicated in FIGS. 10A and 10B, is to receive a problem description from the user (step 1002). After receiving the problem description, the reasoner component 402 interprets the problem description (step 1004). The reasoner component 402 performs this step by invoking the interpret text routine, described below, which returns a ranked list of causes (C.sub.poss) and symptoms (S.sub.poss). The reasoner component 402 then presents the user with the ranked lists C.sub.poss and S.sub.poss, and the user selects either a cause from C.sub.poss and S.sub.poss, indicating whether the selected cause or symptom is true or false (step 1006). After the user has indicated whether the selected cause or symptom is true or false, the selected cause or symptom is added to either C.sub.obs or S.sub.obs, thereby indicating that the selected cause or symptom has been observed. Next, the reasoner component 402 finds all issues related to the causes and symptoms in S.sub.obs and C.sub.obs and places the found issues into the set I.sub.current (step 1008). That is,

In other words, I.sub.current contains all issues where at least one cause for the issue is in C.sub.obs or at least one symptom of the issue is in S.sub.obs. Thus, I.sub.current contains the issues under investigation by the reasoner component 402. Next, the reasoner component 402 generates causes to observe (step 1010). That is, the reasoner component ranks and displays all of the causes in the set C.sub.poss, where ##EQU1## In performing this step, the reasoner component 402 utilizes the following equations: ##EQU2## This formula calculates the expected value "EV.sub.I " of observing a cause "C.sub.i," and ranks the causes in C.sub.poss according to the expected values of the causes. In performing this calculation, formula 2 utilizes the total evidence observed. The total evidence "E" for an issue is a combination of both the symptoms observed "E.sub.s " and the causes observed "E.sub.c " for the issue. The symptoms observed "E.sub.s " include the symptoms that are true (i.e., present), as well as those that are false "E.sub.s " (i.e., not present). Thus,

where

"E.sub.c " is similarly defined to that of "E.sub.s " except that the observations are with respect to causes, not symptoms.

In the definition of formula 2, "q.sub.i " refers to the prior probability that cause "i" is present and "q.sub.j " refers to the prior probability that cause "j" is present.

The term "Pr(C.sub.i .vertline.E)" of formula 2 is defined by the following equation: ##EQU3## where C.sub.j .di-elect cons.C(I) refers to all causes associated with issue "I," where the term "Pr(I.vertline.E)" is defined by the following formula: ##EQU4## where "p.sub.i " refers to the probability of symptom "i" given only issue "i" is true, where "p.sub.i.sup.l " refers to the leak probability of symptom "i" and where "q.sub.i " refers to the prior probability that cause "i" is present. In addition, "S.sub.i " and "C.sub.i " refer to symptoms and causes, respectively.

After the reasoner component 402 generates the causes to observe, the reasoner component generates symptoms to observe (step 1012 in FIG. 10B). In performing this step, the reasoner component 402 utilizes the following formula: ##EQU5## This formula calculates the expected value "EV.sub.I " of observing a symptom "S.sub.i " and ranks the symptoms in S.sub.poss accordingly where S.sub.poss =.sub.I.di-elect cons.I.sbsb.current.sup..orgate.S(I). Where the term "Pr(S.sub.1 .vertline.E)" is defined as:

where "P.sub.i " refers to the probability of symptom "i" given only issue "i" is true and "p.sub.i.sup.l " the leak probability. Where the term "Pr(I.vertline.E)" is calculated using formula 4 above.

Next, the reasoner component generates recommended repairs (step 1014). That is, the reasoner component ranks and displays the repairs contained in R.sub.poss by utilizing the following formula: ##EQU6##

The above formula calculates which resolutions have the highest expected value "NetBenefit.sub.R.sbsb.i." The term "B" refers to a parameter indicating the value of a properly functioning computer system. The term "Pr(I.sub.j .vertline.E)" is calculated using formula 4 above, the term "Pr(I.sub.j Solved.vertline.R.sub.i)" refers to the probability that resolution "i" will solve issue "j," and "c.sub.i " refers to the cost of resolution "i."

After the recommended repairs have been generated, the user then has the option of whether to observe more causes or symptoms per step 1006 or whether to try a recommended repair (step 1016). If the user decides to observe more causes and symptoms, the reasoner component 402 continues to step 1006. However, if the user tries the recommended repair, processing continues to step 1018 where the user determines whether the recommended repair fixed the issue (step 1018). If the issue was fixed by the recommended repair, the user selects the issue (now referred to as a "confirmed" issue) and indicates whether each resolution tried was successful in solving the confirmed issue (step 1020). If the issue was not solved, the user indicates that the issue remains unsolved and determines whether the belief network should be extended to solve the unsolved issue (step 1022). That is, the user would invoke the author component 404 to create new issues, causes, symptoms, and resolutions so as to provide a solution to the issue that remained unsolved. The last step that the reasoner component 402 performs is to update the probabilities in the belief network (step 1024). The reasoner component 402 updates the probabilities so that the next time that the reasoner component is invoked, the reasoner component will be more accurate in resolving problems. This step is performed by invoking the update probabilities routine, described below.

FIG. 11 depicts a flowchart of the steps performed by the interpret text routine of the preferred embodiment. The interpret text routine is invoked to provide a ranked list of causes and symptoms from the problem description. The first step of the interpret text routine is to strip the punctuation from the user input (step 1102). That is, the interpret text routine strips the punctuation and identifies individual words from the problem description. Next, the interpret text routine identifies the lemma for each word in the problem description (step 1104). The lemma of a word is the root associated with the word. For example, the lemma of "printers" is "printer," the lemma of "walking" is "walk," and the lemma of "gotten" is "get." Techniques for identifying the lemma of a word is well-known in the art. The next step of the interpret text routine is to find the terms associated with each lemma (step 1106). In this step, the interpret text routine determines the set of all terms associated with the problem description by matching the lemmas in the problem description to all of the alternates in the belief network. When an alternate is matched, the term associated with the alternate is added to a set ("T.sub.in ") indicating the set of terms associated with the problem description. That is,

where "T.sub.i " is a term, "L" is a lemma in the problem description, "L.sub.in " is the set of all lemmas in the problem description and "A(T.sub.i)" indicates the alternates associated with a term "T.sub.i."

In matching lemmas to terms, if a lemma matches an alternate corresponding to more than one term, all of the associated terms are included into T.sub.in. In addition, if a multiword sequence of lemmas matches a term, and a subsequence of the lemmas matches another term, only the term matching the longer of the two sequences is included in T.sub.in. For example, if the input lemmas are "high performance" and there is an alternate for "high performance" and an alternate for "performance," only "high performance" is added into T.sub.in. After finding all of the terms associated with the problem descriptions, the interpret text routine scores the concepts (step 1108). The concepts are scored by the interpret text routine using the following formula: ##EQU7## where "D" refers to a concept and where ##EQU8## is a normalizing coefficient. In utilizing the above formula, terms may be encountered in "T.sub.in " that are not associated with the concept "D." In these instances, a default "miss" probability ".epsilon." is added to the terms:

Therefore, for example, in ranking two concepts D.sub.1 and D.sub.2, the following formula is used: ##EQU9## After all the concepts have been scored, the interpret text routine adds the ranked symptoms to S.sub.poss and the ranked causes to C.sub.poss and processing returns.

FIG. 12 depicts a flowchart of the steps performed by the update probabilities routine of the preferred embodiment. The update probabilities routine updates the probabilities in the belief network after each invocation of the reasoner component 402. The update probabilities routine updates the probabilities for causes, symptoms, resolutions, and terms. The first step performed by the update probabilities routine is to update the probabilities associated with the causes in the belief network (step 1202). That is, for each cause in set C.sub.obs that was observed to be true or false, the probability contained within the belief network for the corresponding cause node is updated. The probability is updated using the following formula:

Let Pr(x) be the probability of a discrete binary random variable, that is where "x=true" written as "X" or "x=false" written as "E." The expected value of the probability of "X," written "<Pr(X)>," is calculated from a set of observations regarding "x" as follows: ##EQU10## where "n" is the number of observations where "x=true" (i.e., the incidents), "m" is the sample size or total number of observations, and .vertline.x.vertline. is the number of outcomes for the variable "x." Since the variables in the belief network of the preferred embodiment are Boolean variables, .vertline.x.vertline.=2.

In order to perform this calculation, during the invocation of the reasoner component 402, for every issue evaluated, the variable "n" associated with each cause, symptom, resolution or term is incremented if the cause, symptom, resolution or term is observed to be true. The variable "m" is incremented for every issue evaluated if the cause, symptom, resolution or term is observed, regardless of whether the cause, symptom, resolution or term is true or false. The next step in the update probabilities routine of the preferred embodiment is to update the probabilities associated with the symptoms (step 1204). If the issue has been confirmed, the update probabilities routine updates each symptom in S.sub.obs in the same manner as that described relative to step 1202. After the probabilities associated with the symptoms are updated, the update probabilities routine updates the probabilities associated with the resolutions (step 1206). If an issue has been confirmed, for each resolution that was attempted, the update probabilities routine updates the probability for each resolution in the same manner as that used in step 1202. The last step of the update probabilities routine is to update the probabilities associated with the terms (step 1208). For each cause or symptom selected by the user in step 1006 of FIG. 10A, the probability for each term associated to the selected concepts is updated. If a term is associated to the concept and appears in the problem description, the probability for that term is updated positively. However, if a term is associated to the concept and does not appear in the problem description, the probability for the term is updated negatively.

The present invention provides an improved CBR system. The present invention is an improved CBR system by utilizing a belief network. By utilizing a belief network, the CBR system of the present invention is more accurate than conventional CBR systems and reduces storage requirements. In addition, by updating the probabilities in the belief network of the present invention, the CBR system of the present invention becomes more accurate after each invocation and prevents errors from repeatedly occurring. Further, the structure of the belief network of the present invention facilitates in assisting in problem resolution scenarios. That is, the belief network of the present invention utilizes six data elements: issues, causes, symptoms, resolutions and terms.

While the present invention has been described with reference to a preferred embodiment thereof, those skilled in the art will know of various changes in form that may be made without departing from the spirit and scope of the claimed invention as defined in the appended claims. Such changes may include different structures or data types used in the belief network, as well as different algorithms for updating the probabilities in the belief network.