Download Method for obtaining information in an expert system
Transcript
United States Patent [191 [11] Patent Number: 4,763,277 Ashford et al. [45] Date of Patent: Aug. 9, 1988 [54] 4,675,829 METHOD FOR OBTAINING INFORMATION 6/l987 Clemenson ........................ 1. 364/513 IN AN EXPERT SYSTEM OTHER PUBLICATIONS [75] Inventors: Thomas J‘ Ashford’ 83.“ Jose’ Cam‘; Mitsura Ishizuka, “An Extension of Dempster & Sha g”: F d - ' ‘3 e - fer’s Theory to Fuzzy Set for Constructing Expert Sys e - terns", 7/32, pp. 26-29. Rep' 9f Germany} Chrisune T‘ Iwask‘lw’ Columbla' Md]; Roberta P’ [73] Assignee: Mitsura Ishizuka, Another Extension of Dempster & Shafer’s Theory to Fuzzy Set for Constructing Expert 5mm“, Pasadena’ Callf- Systems, 9/83, pp. 43 and 43. International Business Machines priman, Examme,_Gary v_ Harkcom Comma”, Amonk’ N'Y' [21] APPL NOJ 319,663 [22] Filed: [51] [52] Jan. 17, 1986 [57] Int Cl 4 U """"""""""""""""""" ' Assistant Examiner-Randy W. Lacasse Attorney, Agent, or Firm—Richard E. Cummins ABSTRACT G06‘; 15/18 364/900‘ A method for use in an expert system which selectively allows the system to avoid asking the user a question by ’ 364/306 providing the answer to that question based on related ' """"""""""""""""" " [58] Field of Search .......... .. /APS- MS File; 364/513, - 311mm?“ ‘Th5’e matyhggvfs be?“ prevml’jiy amine‘: i“ e sys em. me 1nvo ves provl mg an ac ion 364/550’ 200 MS File’ 900 Ms F116’ 300 References Cited Us. PATENT DOCUMENTS attribute that can be attached to any node in the rule tree. The attribute is assigned to a node in the tree which provides an answer to a class question based on processing various other dependent nodes. When the [56] 4,479,241 10/1984 Buckley .............................. .. 382/15 answer is obtained, the action attribute then causes all 459L983 5/1986 Bennett et a1‘ " 322/403 other nodes in the rule base referencing the same class 21ml‘. 6: :1!‘ 4’644’479 2/1987 K225; at a‘: 3 364/550 question to be set to the same answer. The user is there fore only requested to supply information as a last re 364/513 8°“ 4,648,044 3/1987 4,649,515 4,658,370 3/1987 Thompson et al. . 364/900 4/1987 Ennan et a1. ..................... .. 364/513 Hardy et al. . . . . . . . . . . . .. 9 Claims, 14 Drawing Sheets m: mm mm lll‘tt “UNIS 71: m: CDIPlLEI (201151111111 {- l _ _ l “ NI‘ILIDRULE FYLES _ — om | ._ _ _ _ ---1 ' "m": 5 r 11 | | , III'EIENCE um: rtunsulrl i H _ _ _ :_ i I ' _ q _ _ 1 1'3“ Q l j "elm .TL w , I‘ _ mttnunr c111 cm mlum L5 mtruulr H m: - unrmct 1 1 I _| PIMEOIJIE "NEW" A um US. Patent Aug. 9, 1938 4,763,277 Sheet 1 0f 14 ms mm rm RULE WRITERS PIE 47 RULE COHPILER ‘ (cousmum |_ _ 'I COIPILED RULE Fl LES ! _ __ ‘E _ __ __ _'_ _ : SUPERVISOR 42 | INFERENCE 0m *____- Lam | (comm _ _ Wm“ Ls |_ | cm 00- ,4 (momma - _ __ _ L PROCEDURE _ | mums: I _ _ PRMDURE a PROCEDURE A I AND 2_1 EVIDENCE; 'YES' T0 ‘ARE "28 THEREREAD/ - WRITE mans?‘ FIG- _2_g EXTERNAL REFERENCE 2.3. a | NUDE _ PROCEDURE n cm; 'm msmrs mm‘ 21 l ‘3 PROCEDURE | _] I _ __ _ I. FIG. 1 _ "a?" I“ AC E + m , I _ 2 _1 US. Patent Aug. 9, 1988 Sheet 2 0f 14 4,763,277 CLASSES PRINTER TEXT *‘OOES YOUR PROBLEM SEEM TO INVOLVE YOUR PRINTER" VALUES '4 OF I'YES' 'HO') PREDEFIHEO WEIGHT - 4 IBH52I5 TEXT-‘ARE YOU USING AH IBH 5245 PRINTER?’ VALUES ' 4 OF (‘YES' 'NO') PREDEFIHED WEIGHT - I SYHPTOH TEXT - ‘DO YOU NOTICE ANY OF THE FOLLOWING SYIIIPTOHS; (I) CHARACTERS IISSIHC (2) CHARACTERS HISFRIHTIHC (3) CHARACTER SHUOGED I4) PAPER FEEDS CROOAED (5) MORE OF THE ABOVE ' VALUES ' I OF L5 PREDEFINED HEIGHT ' 4 PRIHTERLITE TEXT I ‘IS THE LIGHT BLIHIIIHC ON THE FRONT OF YOUR PRINTER?‘ VALUES ' 4 OF ('YES' 'HO') PREDEFINEO WEIGHT '1 FIG. 3A US. Patent Aug. 9, 1988 Sheet 3 of 14 PROCEDURES PR INTERTEST NAME - PRINTERTU PASS 32 767 ‘A SVC NUMBER RETURN STATUSB IT HEY (I I % END PARAMETERS PR INTERNUMBER TEXT - ‘WHAT IS THE NUMBER OF YOUR PRINTER? ' DEFAULT - ' IBM ' RULES 5L RULE TREE 4 BC I CDAL TEXT - ‘ INSTALL A NEW ELEMENT DR R I BBDN. ‘ NAME - 2 CDALI DR NAME - LEVEL2 DR 3 AND NAME - RIBBON 4 EVIDENCE NAME * PRINTERI CLASS ' ( ‘YES’ ) DF PR INTER 4 EV IDENCE NAME - YES 521 5 CLASS - I‘ YES‘ I BE IBMSZI 5 3 EVIDENCE NAME ' SYM PTOM‘I CLASS - I BE SYMPTDM ‘A RULE TREE 2 % I COAL TEXT - lit-MN ' REPORT SERVICE REDUEST NUMBER I51 DIB FOR THE PRINTERNUMRER PRINTER. ‘ AN 0 NOT REFERENCE NAME - RIBBD N DR EXTERNAL PRDC - PRINTERTEST STATU SBI T NE '00‘ NB EV I DE NCE CLASS - (‘YES ‘I (If PR INTER L ITE EVIDENCE CLASS I 2 OF SYM PTDM FIG. 3B 4,763,277 US. Patent Aug. 9, 1988 Sheet 4 of 14 4,763,277 RULE TREE 4 mi com INSTALL ELEMENT on mason NAME‘ LEVELZOR 0R | MN‘ ~ R'BM Hm EVIDENCE: 4T0 snmou ' m5 srmom NAME PRlHTE EVIDENCE‘ ‘YES’ T0 PRINTER EVIDENCE: 'vzs' T0 M5245 Fl G . um TES5245 4 RULE TR£E 2 REPORT SRN 151 048 AND 1 ' uor W 0R EVIDENCE: 2 T0 snmou REFERENCE: EXTERNAL: EVIDENCE: NAHE- PROCEDURE - 'vEs' T0 meow PRINTERTEST PRINTERUTE smusan <>o FIG. 5 US. Patent Aug. 9, 1988 Sheet 5 0f 14 4,763,277 11 _ k_[ \ mx.za@oH3O|mwn?0h5.zxu.Ea1mj:_bh54m<2z _ \ _ \ I]Nx.zmnOHP:MQ‘oaF5m<0z:umatEH2buka4:“m2 _ \ Tu"x=m3.n0w“5Lxozu*3H‘;m:z TAmXNg4O.Qom?HZwz3-ajnmu:2hz m _ w <. IN5.zaQ1H3nH2m05m<oumm»;sz:a‘2Dh54nm2: TmxIFqorm?Aiuz4asJm:hz v M n , |_ 70 Fu 7m mnzm |— Tum US. Patent Aug. 9, 1988 Sheet 7 0f 14 4,763,277 S ZE MFW ARNMTUD VRIBPAENDOT.{LI- TANaln- HEVRO v!I-| A-.VlLRGRI NEPR E!| AVrI.GC FAR AGEYTINVERA I“LIlIuRT 0LAID“RUVE SAU‘RTF|.UN0EUNFA L STuF. T.. ‘Lrum“ FIG. 7 :0 in um 5U P o N T i in ‘RLE 54|20 25- PAR NEXT! WORD RULE PAR‘ 5-7 8 00n0 - :0 4 W'aOoRD OCIoLAS P.'Danoc FIG. \l \ CIlLA‘H.S P.lROiC‘ 6N.EXT Q a NIL O US. Patent Aug. 9, 1988 PTR FROM CLASS- mew TABLE mm Sheet 8 of 14 HASH JRULE "W LE 9_o CLASSREF IHDX E 7 ., more sou gsmscc ASS "‘ S L ms mozx w RULEREF 95 mes :: == - MEMBERSHIP usr roman ‘' L F s2 FIRST m5 RULE uons- ME Fl 4,763,277 ; 91 94 9_5_ - PROPERTY usT POINTER um cuss POINTER 1 FROM _ TABLE - HASH m PROPNAIE 9-6 97 mm mm PROPNAME FILEINDEX PR IOP NEXTPROP v11 . FLAGS ' MEMBERSHIP PROPNAHE ‘ PROPERTY "EXTPROP I ' ' um cu ss POINTER _ l um PROP . l I . e 9B ' mm . 99 402 “P, HEXTHEIBER —/————~ . HASH PTR on / NEXTPRQP 401 F IG . Jig-EL. l RULE NUDE US. Patent Aug. 9, 1988 PTR FR nu Sheet 9 of 14 men E AD 4,763,277 RULE NUDE - FIRST RUL E um TABLE usmc TH IS PRO CEDURE _. FILEINDEX F'Lmw PM F U "C 1L5“7 HASH TABLE 1T_0 PROC TOCALL PR T o R PRUPNAHE wT RULEREF m ms 5 PROPERTYLLG 1- ~- TL MEMBERSHIP m T j f ARBHEAD PROPNAHE mum :} IIEITPROP @ I 1 [H8 mm _. g: NEXTPROC - - - , 424 m PROPERTY :; “ l “720/ NEXTNEHBER NEXTPRDP NEXTPROP I I VARIABLE VALUE CLASSRESP PROPNAME :; i; NEXTPROP rnocuux NEXT ARC ms VALUE NEXTRETURN 1 VAR ‘ABLE mu _ CLASSRESP I mT m . F I s. 10 J US. Patent Aug. 9, 1988 Sheet 10 of 14 4,763,277 F l G . 4 ‘I mums HASH TABLE ENTRY 431 1 2 PAP-“REF w ~ ~ 1 FILEINDEX omuu I um rues PROPERTY NEXT PARA! f 432 € 33 .-/ nonz w r TH rm us I nc nus PARAH == f 4 50 F I L E INDEX ‘ DEFAULT W5 J: PROPE RT r HAGs PROP, NAME n man A mp Em um PROPERTY {as E PROP. NAME um PARAH ’ A EX FARM NEXT PROP. » A 430 I ~ US. Patent Aug. 9, 1988 Sheet 11 of 14 TOPRULE HWQRC) FILEH‘DEX RULEREF “0°57” E 4,763,277 FATHER MEL BROTHER --—-——-o ASSOC cuusxu man IT PTS 7 HI L FLAGS RULE REF PROPKRTL um um FIRST sou "W9 T | RULEREF 1 FATHER FILEINDEX NODETYPE FILEINDEX NODETYPE Assoc ASSOC IT PTS PIS FLAGS NAME NAME I son RULEREF IT FLAGS I 1‘ FIRST- LAST- FATHER “0RD LAST sou F1R5T~ LAsF- FATHER 50*" cous m son so: ‘_i_; nLEnmEx FILE l NDEX I mm PE * REF * I ASSOC I W I FLAGS I um | ' ASSOC PTS L IT PROPS PTS FLAGS um — — T- -—1 El RSTSON F1 "JR LASTSON g __ __|._. ._ q FILE INDEX FILEINDEX MODE TYPE NODETYPE ASSOC ASSOC WT PTS PTS mes mos NAME NAME -F\ as} 50" T NIL 1L As} FIRSTI NIL 50'‘ 5°“ NIL J ._ __ _ _ IT FIGJZ lusr m L so" US. Patent Aug. 9, 1988 Sheet 12 0f 14 4,763,277 mauzwfm 3E . $2 3 .muzmEzH _ m _ 0 y m OHwm:juaknzmErP<Q= msozH US. Patent Aug. 9, 1988 Sheet 13 of 14 4,763,277 A Type Test Printer B PAND _____l L____ AND ¢]__J Liv External Test-Cable E OR AND RC = D J l_“\ Evidence Value I '52‘ of Test-type F G H I External External External External Test-type Test type RC=19 Test type RC=8O Test-type RC=52 SETC type Ir SETC type = RC = 99 SETC TYPE - IBM 5219 5152 FIG léa EPSON 2D External Test 52 7: US. Patent Aug. 9, 1988 4,763,277 Sheet 14 0f 14 A F Tyyp Goal Test Display Display Bad 8 C AND OR C D E H External External External Evidence_ Display 1 Cable-Test Read-Display Hatch I RC = O z 0 SetC Match = 1 FIG. l' 1 4,763,277 2 well. The programs of an expert system are independent of the problem domain (taxes) and serve to process the data structures without regard to the nature of the prob lem area they describe. For example, there are pro grams to acquire the described data values through user METHOD FOR OBTAINING INFORMATION IN AN EXPERT SYSTEM FIELD OF INVENTION interaction, programs to represent and process special organizations of description, and programs to process lar, to an improved method in which answers to ques the declarations that represent semantic relationships tions solicited from the user may be obtained indirectly within the problem domain and an algorithm to control from related information previously collected by the 10 the processing sequence and focus. system. The general architecture of an expert system involves two principal components: a problem dependent set of RELATED APPLICATIONS data declarations called the knowledge base or Rule U.S. application Ser. No. 6/749,076 ?led on June 26, base, and a problem independent (although highly data 1985, in the name of and entitled “Method for Dynami structure dependent) program which is called the infer cally Collecting Current Data for Use in an Expert ence engine. System From Speci?ed External Processes and Proce Individuals Involved with Expert Systems dures," is directed to an expert system in which the rulebase is segmented to permit use in computing sys There are generally three individuals having an inter tems having limited memory capacity. U.S. application 20 action with expert systems. Primary among these is the Ser. No. 6/748,789 entitled “Method for Dynamically end-user; the individual who uses the system for its Collecting Current Data for Use in an Expert System problem solving assistance. In the building and mainte From Speci?ed External Processes and Procedures," nance of the system there are two other roles: the prob ?led on June 26, 1985, and assigned to the assignee of the present invention is directed to a method of collect~ 25 lem domain expert who builds the knowledge base, and a knowledge engineer who assists the experts in deter ing data in which an independent external process or mining the representation of their knowledge and who procedure can be initiated under the control of the de?nes the inference technique required to obtain useful expert system and results speci?ed and generated by the This invention relates in general to methods for ab taining information in an expert system and, in particu problem solving activity. process or procedure are returned to the expert system for use in concluding speci?c Goal nodes. 30 BACKGROUND ART Expert systems is a term applied to a special kind of The End User The end-user usually sees an expert system through an interactive dialog, an example of which follows: problem solving computer program. The general func tion of expert systems is to solve (or assist in the solution 35 Q. Do you know to which restaurant you want to go? of) problems normally addressed by highly trained and A. No experienced human experts. This is not a new goal; in fact, many successful computer programs have Q. Is there any kind of food you would particularly achieved notable success in providing expert levels of like? performance in certain problem areas. What is different 40 A. Unknown about expert system type programs is the approach taken, and the resulting form of the program itself. Q. Do you like spicy food? Expert Systems vs. Problem Solving Systems As explained in the cross-referenced applications, the principal distinction between expert systems and tradi tional problem solving programs is the way in which the problem related expertise is coded. In traditional applications, problem expertise is encoded in both pro gram and data structures. A. No 45 Q. Do you usually drink wine with meals? A. Yes Q. When you drink wine, is it French wine? A. Why In the expert system approach all of the problem As can be seen from this dialog, the system is leading related expertise is encoded in data structures only. the user through a set of questions, the purpose of None is in programs. Several bene?ts immediately fol which is to determine a suitable set of restaurants to low from this organization. An example may help contrast the traditional prob 55 recommend. This dialog begins with the system asking if the user already knows the restaurant choice (a com lem solving program with the expert system approach. mon feature of expert systems) and immediately illus The example is the problem of tax advice. In the tradi trates a characteristic of expert systems; users may tional approach data structures describe the taxpayer choose not to respond to any question. In expert sys tems, dialogs are not pre-planned. There is no fixed control structure. Dialogs are synthesized from the current information and the contents of the knowledge the taxpayer to tax table choices. It is this representation base. Because of this, not being able to supply the an of the tax expert’s knowledge that is difficult for the tax swer to a particular questions does not stop the consul expert to understand or modify. In the expert system approach, the information about 65 tation. and tax tables, and a program in which there are state ments representing an expert tax consultant’s knowl edge, such as statements which relate information about taxpayers and tax computations is again found in data structures, but now the knowledge describing the rela Another major distinction between expert systems and traditional systems is illustrated by the following tionships between them is encoded in data structures as answer given by the system when the user answers a 3 4,763,277 4 question with the question “why," as occurred in the above example. The answer is; Thus, when a conclusion is drawn, it is possible to understand how this conclusion was reached. Further more, because the expert system uses knowledge in a form similar to the expert, it may be easier to retrieve A. I am trying to determine the type of restaurant to suggest. So far Chinese is not a likely choice. It is 5 this information from the expert. possible that French is a likely choice. I know that if Chaining the diner is a wine drinker, and the preferred wine is There are two main methods of reasoning when using French, then there is strong evidence that the restau inference Rules: backward chaining and forward chain: rant choice should include French. mg. Forward chaining starts with the data available and It is very dif?cult to implement a general explanation system (answering questions like Why and How) in uses the inference Rules to conclude more data until a traditional systems. The response of the expert system to the question WHY is an exposure of the underlying desired goal is reached. An inference engine using for ward chaining searches the inference Rules until it ?nds knowledge structure. It is a rule; a set of antecedent 5 one in which the if-clause is known to be true. It then concludes the then-clause and adds this information to conditions which, if true, allow the assertion of a conse its data. It would continue to do this until a goal is quent. The rule references values, and tests them against reached. Because the data available determines which various constraints or asserts constraints onto them. inference Rules are used, this method is also called ‘data This, in fact, is a signi?cant part of the knowledge struc ture. There are values, which may be associated with 20 driven.’ Backward chaining starts with a list of goals and some organizing entity. For example, the individual works backwards to see if there is data which will allow diner is an entity with various attributes (values) includ it to conclude any of these goals. An inference engine using backward chaining would search the inference ing whether they drink wine and the kind of wine. There are also rules, which associate the currently known values of some attributes with assertions that can 25 Rules until it ?nds one which has a then-clause that matches a desired goal. If the if-clause of that inference Rule is not known to be true, then it is added to the list of goals. For example, suppose a Rulebase contains two Rules: (1) If Fritz is green then Fritz is a frog. be made about other attributes. It is the orderly process ing of these rules that dictates the dialog itself. The Knowledge Engineer The knowledge engineer is concerned with the repre sentation chosen for the expert’s knowledge declara (2) If Fritz is a frog then Fritz hops. Suppose a goal is to conclude that Fritz hops. The Rule base would be searched and Rule (2) would be selected because its conclusion (the then clause) matches the goal. It is not known that Fritz is a frog, so this “iF' statement is added to the goal list. The Rulebase is again searched and this time Rule (1) is selected because its then clause matches the new goal just added to the list. This time, the if-clause (Fritz is green) is known to be true and the goal that Fritz hops is concluded. Because the list of goals determines which Rules are selected and used, this method is called ‘goal driven.’ tions and with the inference engine used to process that knowledge. There are several characteristics known to be appropriate to a good inference technique. 1. A good inference technique is independent of the problem domain. In order to realize the bene?ts of explanation, knowl edge transparency, and re-usability of the programs in a new problem domain, the inference engine must contain domain speci?c expertise. 2. Inference techniques may be speci?c to a particular task, such as diagnosis of hardware con?guration. Other techniques may be committed only to a par Con?dences ticular processing technique. Another advantage of expert systems over traditional 3. Inference techniques are always speci?c to the 45 methods of programming is that they allow the use of knowledge structures. Successful examples of Rule processing techniques Con?dences. When a human reasons he does not always include: conclude things with 100% con?dence. He might say, “If Fritz is green, then he is probably a frog” (after all, (a) Forward chaining (b) Backward chaining he might be a chameleon); or, that Fritz’s leg is broken, but not much). This type of reasoning can be imitated The Inference Rule by using numeric values called Con?dences. For exam ple, if it is known that Fritz is green, it might be con An understanding of the “Inference Rule” concept is cluded with 0.85 Con?dence that he is a frog; or, if it is important to understand expert systems. An Inference Rule is a statement that has two parts, an if-clause and a 55 known that he is a frog, it might be concluded with 0.95 Con?dence that he hops. These numbers are similar in then-clause. An example of an Inference Rule is: nature to probabilities, but they are not the same. They If the restaurant choice includes French, and the 50 occasion is romantic, are meant to imitate the Con?dences humans use in reasoning rather than to follow the mathematical de?ni Then the restaurant choice is de?nitely Paul Bocuse. An expert system’s Rulebase is made up of many such 60 tions used in calculating probabilities. inference Rules. They are entered as separate Rules and it is the inference engine that uses them together to draw conclusions. Because each Rule is a unit, Rules may be deleted or added without affecting other Rules (though it should affect which conclusions are reached). 65 One advantage of inference Rules over traditional pro gramming is that inference Rules use reasoning which more closely resemble human reasoning. The following general points about expert systems and their architecture have been illustrated. l. The sequence of steps taken to reach a conclusion is dynamically synthesized with each new case. It is not explicitly programmed when the system is built. 2. Expert systems can process multiple values for any problem parameter. This permits more than one 5 4,763,277 6 line of reasoning to be pursued and the results of processing system, much of the Rulebase is not required incomplete (not fully determined) reasoning to be since many of the components which are optional units of the system will not be present in the system. Never presented. 3. Problem solving is accomplished by applying spe cific knowledge rather than speci?c technique. theless, prior art expert systems require the entire Rule base to be stored since all the Rules were, in effect, This is a key idea in expert systems technology. It chained or linked together by the structure of the Rule re?ects the belief that human experts do not pro base. cess their knowledge differently from others, but The invention described in cross-referenced applica they do possess different knowledge. With this tion Ser. No. 6/749,076 is directed to an expert system philosophy, when one ?nds that their expert sys 0 in which the Rulebase is segmented, preferably into tem does not produce the desired results, work contextual segments or units. When the Rulebase is begins to expand the knowledge base, not to re segmented, it is then possible to eliminate portions of program the procedures. the Rulebase containing data or knowledge that is not The prior art has disclosed various expert systems in needed in a particular application. The segmenting of which a “Rulebase” and an “inference engine” cooper ate to simulate the reasoning process that a human ex the Rulebase also allows the expert system to be run with systems or on systems having much smaller mem pert pursues in analyzing a problem and arriving at a conclusion. In these prior art systems, in order to simu ory capacities than was possible with prior art arrange late the human reasoning process, a vast amount of ments since each segment of the Rulebase can be paged into and out of the system as needed. The segmenting of knowledge needed to be stored in the knowledge base. 20 the Rulebase into contextual segments requires that the Generally, the knowledge base of a prior art expert expert system manage various intersegment relation system consisted of a relatively large number of “if ships as segments are paged into and out of memory then” type of statements that were interrelated in a during execution of the program. Since the system per manner that, in theory at least, resembled the sequence mits a Rulebase segment to be called and executed at of mental steps that were involved in the human reason 25 any time during the processing of the ?rst Rulebase, ing process. Because of the need for large storage capacities and related programs to store the Rulebase, most expert systems have, in the past, been run only on large infor mation handling systems. Recently, the storage capacity of personal computers has increased to a point where it is becoming possible to consider running some types of simple expert systems on personal computers. A num ber of such programs and their applications are dis cussed in PC Magazine, dated Apr. 16, 1985 beginning on page 108. Another article entitled “Arti?cial Intelli gence” appears on page 34 of PC World Magazine, Vol. 2 #1, dated January 1984. Additional publications of interest that describe Ex pert Systems of the type represented by the present invention include; 1. “A User’s Manual for Construct and Consult in the GPSI Environmen ” authored by Paul Nielsen, provision must be made to store the data that has been accumulated up to that point so that at some time later in the process, when the system returns to the ?rst seg ment, it can proceed from the last point or RULE node that was processed. Also, provision must be made so that data that has been collected by the system up to that point can be passed to the second segment of the Rulebase after it has been paged into the system and data collected during the processing of the second seg ment can be passed to the ?rst segment when the system returns to complete processing that segment. The embodiment of the invention described in that application employs a segmented Rulebase that has been established for the primary purpose of diagnosing the faulty hardware operation of a data processing sys tem such as a personal computer. The overall objective of the system is therefore to identify a Field Replaceable Unit (FRU) that is most probably the cause or source of currently available from the University of Illinois the problem. KBPA Project. 45 In the second referenced application, the embodiment 2. Gordon, Robert K., A Rule Editor for an Expert was substantially the same except that the system could System Environment Towards Automating perform a self-diagnosis on its own hardware since it Knowledge Acquisition, M.S. Thesis, University of Illinois, Urbana, Ill. 1984. 3. Harandi, Mehdi T., A General Purpose System for Inferencing, Proceedings of the IBM University Study Conference, Raleigh, NC, October 1983. had the ability to initiate external procedures or test units on speci?c components which, when concluded, would return the results to the expert system. Informa tion was therefore collected by these systems by asking questions of the user or running so-called test units or external processes. Aid in Program Debugging, M.S. Thesis, Univer The User interface and the Procedure interface are 55 two important functions in the information collection sity of Illinois, Urbana, Ill., 1981. In some applications of expert systems, the nature of process of the systems described in the cross-referenced the application and the amount of stored information applications. necessary to simulate the human reasoning process for The User Interface that application is just too vast to store in the active memory of a computer. In other applications of expert 60 The function of the user interface is to present ques systems, the nature of the application is such that not all tions and information to the operator and supply the 4. Laursen, Andrew L., GPSI : An Expert System to of the information is always needed in the reasoning process. An example of this latter type application operator’s responses to the Inference Engine. Any values entered by the user must be received and interpreted by the user interface. Some responses are processing system comprising many separate compo 65 restricted to a set of possible legal answers, others are nents, some of which are optional. When that type of not. The user interface checks all responses to insure expert system employs a single integrated Rulebase to that they are of the correct data type. Any responses would be the use of an expert system to diagnose a data diagnose the minimum system con?guration of the data that are restricted to a legal set of answers are compared 7 4,763,277 8 it. As explained in the cross” referenced application, A leaf that is an EXTERNAL node indicates that data will be used which was obtained from a Procedure Call. A REFERENCE node functions to refer to another communication between the user interface and the In tree or subtree. against these legal answers. Whenever the user enters an illegal answer, the user interface informs the user that his answer was invalid and prompts him to correct ference Engine is performed through the use of a User Interface Control Block (UICB) which is passed be A tree may also contain intermediate or minor nodes Procedure Node Interface between the Goal node and the Leaf node. An interme diate node can represent logical operations like And or Or. The inference logic has two functions. It selects a tree The function of the Procedure node interface is to receive infonnation from the Procedures coordinator and create the appropriate Procedure Call. The ability selected, that tree is traced, depth-?rst, left to right. The word "tracing” refers to the action the system tween the two. to call a Procedure and receive information from that Procedure can be viewed as simply a generalization of input from the external world. While in some prior art expert systems external information has been obtained, that information was obtained only in a predetermined manner so only certain information could actually be acquired. This expert system, disclosed in the cross referenced application, through the knowledge base, is permitted to invoke any Procedure allowed on its host system. This makes the expert system useful in a much wider class of knowledge domains than if it had no external access or only limited external access. In the area of machine diagnostics using expert sys tems, particularly self-diagnostic applications, it is not possible to conclude the current state of “health” of a machine without some information. The best source of information is the machine itself, for it contains much detailed information that could not reasonably be pro vided by the operator. As explained in the prior art, the knowledge that is represented in the system appears in the Rulebase. In the Rulebase described in the cross-referenced applica tions, there are basically four different types of objects, with associated information present. 1. Classes-these are questions asked to the user. 2. Parameters-a Parameter is a place holder for a char acter string which may be a variable that can be in serted into a Class question at the point in the ques tion where the Parameter is positioned. to trace and then it traces that tree. Once a tree has been takes as it traverses the tree. asking Classes (questions), calling Procedures, and calculating Confidences as it proceeds. As explained in the cross-referenced applications, the selection of a tree depends on the ordering of the trees. The original ordering of the trees is the order in which they appear in the Rulebase. This order can be changed, however, by assigning an EVIDENCE node an attri bute “initial” which is described in detail in these appli cations. The ?rst action taken is to obtain values for all EVIDENCE nodes which have been assigned an “ini 25 tial” attribute. Using only the answers to these initial Evidences, the Rules are ordered so that the most likely to succeed is evaluated ?rst. The trees can be further re-ordered since they are constantly being updated as a selected tree is being traced. It has been found that the type of information that is solicited by the system from the user by means of ques tions or classes should be tailored to the level of knowl edge of the user. In many applications, the group of prospective uses is nicely de?ned and the knowledge 35 level can be estimated so that the questions can be pres ented at a level which corresponds generally to the average user. However, in other applications, knowl edge of the speci?c domain of the expert system might vary considerably among the group of prospective us ers. One application where this is particularly true in volves the use of an expert system, operating in a self diagnostic mode on a personal computer to assist the operator of the personal computer to diagnose the cause 3. Procedures-these are de?nitions of calls to external of a fault or error in either the hardware or software. In 45 Procedures. general, asking the operator for information is the most . Rule Nodes-The inferencing in the system is done straightforward way for the expert system to gather by a tree structure which indicates the Rules or logic information assuming, of course, that the information is or should be within the operator’s understanding. For trees are called RULE nodes. There are several dif 50 example, in diagnosing a personal computer, the expert ferent types of RULE nodes. system must know the major functional components of The Rulebase comprises a forest of many trees. The the system. It could ask the operator, for instance, if the top node of the tree is called the Goal node, in that it display is a monochrome or color display. The operator contains the conclusion. Each tree in the forest has a should, in all probability, be able to provide the correct different Goal node. The leaves of the tree are also 55 answer 100% of the time. The expert system could, on which mimics human reasoning. The nodes of these referred to as RULE nodes, or one of the types of RULE nodes. A leaf may be an EVIDENCE node, an EXTERNAL node, or a REFERENCE node. An EVIDENCE node functions to obtain informa the other hand, cause a test unit to be run to determine the type of display. The accuracy of the data collected by either approach in this instance probably would not be that different so the knowledge engineer could em tion from the operator by asking a speci?c question. In responding to a question presented by an EVIDENCE node, the operator is generally instructed to answer “yes” or "no" represented by numeric values 1 and 0 or provide a value of between 0 and 1, represented by a ploy either approach without affecting the accuracy of the diagnosis. However, in many instances, because of handled in a different manner. invention that in many situations the information is the nature of the information being solicited, it is better to obtain the information from the system rather than asking the operator, because the accuracy of the data “maybe.“ 65 supplied by the operator is so low that the system could not effectively process it to a meaningful conclusion. Questions which require a response from the operator other than yes or no or a value between 0 and l are It has been found in accordance with the present 9 4,763,277 already in the system, in a form of which permits the 10 FIG. 3A and FIG. 3B in combination, illustrate the data for a sample Rulebase. FIG. 4 is a Rule tree constructed from the input data shown in FIG. 3A and FIG. 38. FIG. 5 is another tree constructed for the input data shown in in FIG. 3A and FIG. 33. FIG. 6A and FIG. 6B in combination, illustrate the records of the major linked lists. correct answer to a question to be obtained through a process of inductive or deductive reasoning. The data previously collected by the system could be answers provided by the user to less complex questions that were asked for a different reason or results returned from test units that were previously run. For example, in testing diskette drives there are cer tain tests which require that a scratch diskette be pres FIG. 7 illustrates the general format of the variable ent in diskette drive A. These tests may cause data to be 10 ?eld of the records shown in FIG. 6A and FIG. 6B, written to the diskette or the diskette to be reformatted. FIG. 8 illustrates the relationship of the link lists to Data on the diskette may be destroyed, so it is impera the Hashtable structure. tive that the diskette with the diagnostics routines not FIG. 9 illustrates the relation of the Class linked list, be inserted in drive A. Rather than relying on the user the member list, the Hashtable, and RULE nodes that to be sure that a scratch diskette is present, there are 15 are members of the Class. certain things that may indicate to the system that such FIG. 10 illustrates the relation of the Procedure is the case. If drive A is a low capacity diskette drive linked list, the Membership list of a Procedure object, and a diskette is present, then the diskette must be a the Hashtable and the RULE nodes that are members of scratch diskette. If the drive is a high capacity diskette drive, and the procedure, READ__VOLUME_LA~ 20 BEL returns a nonzero return code, then the diagnostic diskette is not in drive A, and a scratch diskette must be. the Procedure object. FIG. 11 illustrates the organization of the Parameter linked list. FIG. 12 illustrates the organization of the Rulenode In the case that the drive is high capacity and linked list READ_VOLUME_LABEL returns a zero return code, then the user must be told to insert a scratch 25 diskette in A. FIG. 13 illustrates the organization of the various programming modules employed in the Expert System FIG. 14a and 14b illustrate examples of Rulenodes in In the Rulebase of the expert system, action attributes which answers to class questions that are obtained from can be associated with any node. One of these actions, the system, and the question is therefore never pres the SET action, indicates that if this node is evaluated to be true, then the answer to a speci?ed question can be 30 ented to the user. set to a speci?ed value. In this way, answers to ques DESCRIPTION OF THE PREFERRED tions can be obtained without directly asking the user EMBODIMENT the question. If the node with the action attribute is The preferred embodiment of the present invention invalidated, then the question speci?ed in the action to be described employs a segmented Rulebase that has attribute will not be affected. 35 been established for the primary purpose of diagnosing These SET actions are equivalent to adding rules to the faulty hardware operation of a data processing sys the rulebase which would resemble the IF . . . THEN tem such as a personal computer. The overall objective rules as follows: of the embodiment is therefore to identify a Field Re~ IF drive A is low capacity placeable Unit (FRU) that is most probably the cause or AND there is a diskette present source of the problem. The application of an expert THEN the answer to “Is there a scratch diskette in A?” system that employs a segmented Rulebase in accor is “yes.” dance with the teachings of the cross referenced and in IF drive A is high capacity which procedures are run to collect data for use by the AND the return code of READ_.VOLUME_LA. BEL is not 0 45 expert system is but one example of an application for THEN the answer to “Is there a scratch diskette in A?” this type of expert system. Other applications employ ing data collected by running external procedures and is “yes." It is therefore an object of the present invention to not using an segmented Rule base may readily be devel oped based on the following description. The ability to provide an improved method of collecting information 50 assign an action attribute to the Rulenode, as described AND there is a diskette present in an expert system. A further object of the present invention is to provide an expert system in which prior to asking a question of the user, other available methods of determining the generally in the cross-referenced application is em ployed in connection with the present invention, in that a speci?c action attribute, “SETC” permits the answer to be set to a class question that would always be pres answer by the system are considered. 55 ented to the user. A still further object of the present invention is to SYSTEM OVERVIEW provide a method in which answers to questions can be The main components of the expert system shown set in accordance with the logical combination of data diagrammatically in FIG. 1 are an Inference Engine IE obtained from other Rule nodes in the system. Objects and advantages other than those mentioned 60 10 and a Rulebase ?le 11. The Inference Engine 10 above will be apparent from the following description when read in connection with the drawing. BRIEF DESCRIPTION OF THE DRAWING includes a supervisor program 12, inference logic 133, and a procedural call coordinator 14. Procedures A-N are interfaced to the coordinator 14 through the Proce dure node interface 15. The operator interfaces with the FIG. 1 illustrates the overall functional relationships 65 supervisor through the operator or user interface block of the components of an expert system in which the 16. The knowledge represented by the compiled Rule present invention is advantageously employed. base is generated by the ?le compiler 17, based on Rule FIG. 2 illustrates schematically, a sample Rule tree. inputs from Rule writers.