Basic expert system tool

• US 4,648,044 A
• Filed: 06/06/1984
• Issued: 03/03/1987
• Est. Priority Date: 06/06/1984
• Status: Expired due to Term

• Current Assignee: Teknowledge Corporation
• Original Assignee: Teknowledge Corporation
• Inventors: Joyce, Robert H., Hardy, Steven
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US06/617,791
• Time in Patent Office: 1,000 Days
• Field of Search: 364/130, 364/148, 364/300, 364/400, 364/513, 364/200 MS File, 364/900 MS File, 382/14, 382/15
• US Class Current: 706/60
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

A tool for building a knowledge system and running a consultation on a computer is easily mastered by people with little computer experience yet also provides advanced capabilities for the experienced knowledge engineer. The knowledge system includes a knowledge base in an easily understood English-like language expressing facts, rules, and meta-facts for specifying how the rules are to be applied to solve a specific problem. The tool includes interactive knowledge base debugging, question generation, legal response checking, explanation, certainty factors, and the use of variables. The knowledge base language permits recursion and is extensible. Preferably, control during a consultation is goal directed in depth-first fashion as specified by rule order. The tool is easily embodied in assembly language, or in PROLOG to allow user-defined PROLOG functions.

Claims

1. A knowledge engineering tool comprising a computer having memory for storing a knowledge base,

means for interpreting the knowledge base to run an advisory consultation to determine the value of any selected goal expression requested by the user and the value of any subsidiary goal expression implicitly required to determine the value of said selected goal expression,

wherein said knowledge base includes

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for a selected expression,

meta-facts equivalent in form to facts but prescribing the manner in which facts and rules should be used, and

declarations defining whether certain of said expressions are single-valued or multiple-valued, and

wherein said means for interpreting said knowledqe base includes

means for determining the value of any selected goal expression,

means for searching the knowledge base for occurrences of the selected expression,

means for invoking and chaining said rules concluding a value for the selected goal expression,

means for evaluating said logical operations in the premises of the invoked rules,

means for terminating the searching of the knowledge base for a single-valued expression when a substantially certain value is found, and for a multiple-valued expression when all values for the expression are determined, and

means for conveying to the user said value of said goal expression.

2. A knowledge engineering tool as set forth in claim 1 wherein

said rules in said knowledge base include recursive rules and rules having universally quantified variables, and

said means for interpreting said knowledge base includes means for instantiating and de-instantiating the universally quantified variables in said rules.

3. A knowledge engineering tool as set forth in claim 1 which includes means for augmenting and editing the knowledge base, and means for generating a record of said consultation including an ordered list of the rules invoked during a test consultation.

4. A knowledge engineering tool as set forth in claim 1 wherein

said advisory consultation is interactive, said knowledge base includes declarations defining questions to be asked to determine the values of certain of said expressions, and

said means for interpreting said knowledge base includes

means for asking the user said questions when the values of their corresponding expressions are not known with a predetermined certainty, and

means for receiving from the user values for said expressions.

5. A knowledge engineering tool as set forth in claim 4 wherein said means for interpreting said knowledge base includes means for generating an appropriate question when the value of a certain expression is not known and no explicit question is defined by a declaration in the knowledge base.

6. A knowledge engineering tool as set forth in claim 4 wherein said means, for interpreting said knowledge base includes means for explaining to the user why the user is asked said questions to determine the values of certain of said expressions.

7. A knowledge engineering tool as set forth in claim 4 wherein

said knowledge base includes declarations defining legal values of said expressions whose values are to be determined by asking said questions, and

said means for interpreting said knowledge base includes means for checking said values received from the user against said legal values.

8. A knowledge engineering tool as set forth in claim 1 wherein

said means for interpreting said knowledge base includes means for determining the value of at least one predetermined goal expression, and

certain of said meta-facts specify predetermined goal expressions.

9. A knowledge engineering tool as set forth in claim 1 wherein said rules include recursive rules.

10. A knowledge engineering tool as set forth in claim 1 wherein said knowledge base includes built-in predicates for determining the degree of certainty with which the value of a predetermined expression has been determined.

11. A knowledge engineering tool as set forth in claim 1 wherein said means for interpreting said knowledge base includes

means for determining the certainty factor for the value of any selected goal expression,

means for updating said certainty factor by combining certainty factors from multiple sources, and

means for conveying said certainty factor to the user.

12. A knowledge engineering tool as set forth in claim 11 wherein

said facts and rules in said knowledge base include certainty factors encoding uncertain as well as certain knowledge, and

said means for interpreting said knowledge base includes means for selecting certainty factors for the determined values based on the certainty factors of said rules and the certainty factors of said premises.

13. A knowledge engineering tool as set forth in claim 1 which includes means for explaining to the user how a determined value for a goal expression was determined.

14. A knowledge engineering tool as set forth in claim 1 wherein

said knowledge base includes propositions including arithmetic operations, and

said means for interpreting said knowledge base includes means for evaluating said propositions.

15. A knowledge engineering tool comprising a computer having memory for storing a knowledge base and memory for storing predetermined instructions including

means to augment and edit the knowledge base, and

means for interpreting the knowledge base to run an interactive consultation with the user to determine the value of at least one predetermined goal expression,

wherein said knowledge base includes

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for said goal expression, said rules including recursive rules and rules having universally quantified variables,

propositions including arithmetic operations,

declarations defining whether selected expressions are single valued or multiple-valued,

declarations defining questions to be asked to determine the values of selected expressions, and

declarations defining legal values of selected expressions, and

wherein said means for interpreting the knowledge base includes

means for determining the value of said goal expression including

means for searching the knowledge base for occurrences of the goal expression,

means for invoking and chaining said rules to conclude a value for said goal expression,

means for evaluating the logical operations in the premises of the invoked rules,

means for evaluating said propositions,

means for terminating the searching of the knowledge base for a single-valued expression when a certain value is found and for a multiple-valued expression when all values for the expression are determined,

means for instantiating and de-instantiating the universally quantified variables in said rules,

means for asking the user said questions to determine the values of their corresponding expressions,

means for receiving from the user and checking values of said corresponding expressions against the corresponding declared legal values, and

means for explaining to the user why the user is asked for the values of said corresponding expressions,

means for conveying to the user said value of said goal expression,

means for explaining to the user how said value of said goal expression was determined, and

means for generating a record of said consultation including a list of the rules invoked during a test consultation.

16. A knowledge engineering tool comprising

a computer having memory for storing a knowledge base and memory for storing predetermined instructions including

means to augment and edit the knowledge base, and

means for interpreting the knowledge base to run an interactive consultation with the user to determine the value of at least one predetermined goal expression,

wherein said knowledge base includes

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for said goal expression, said rules including recursive rules and rules having universally quantified variables,

certainty factors associated with said facts and rules for encoding uncertain as well as certain knowledge,

propositions including arithmetic operations,

propositions responsive to whether a value of a predetermined expression has been determined with a predetermined degree of certainty, and

declarations defining whether selected expressions are single-valued or multiple-valued, and

wherein said means for interpreting the knowledge base includes

means for determining the value of said goal expression including

means for searching the knowledge base for occurrences of the goal expression,

means for invoking and chaining said rules to conclude a value for said goal expression,

means for evaluating the logical operations of the premises of the invoked rules and selecting certainty factors for the concluded values based on the certainty factors of the rules and the certainty factors of the premises,

means for updating the certainty factor of a value of an expression by combining certainty factors,

means for evaluating said propositions,

means for terminating the searching of the knowledge base for a single-valued expression when a certain value is found and for a multiple-valued expression when all values for the expression are determined, and

means for instantiating and de-instantiating the universally quantified variables in said rules, and

means for conveying to the user said value of said goal expression and its certainty factor.

17. A knowledge engineering tool comprising

a computer having memory for storing a knowledge base and memory for storing predetermined instructions including

means to augment and edit the knowledge base, and

means for interpreting the knowledge base to run an interactive consultation with the user to determine the value of at least one predetermined goal expression,

wherein said knowledge base includes

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for said goal expression, said rules including recursive rules and rules having universally quantified variables, and

declarations defining whether selected expressions are single-valued or multiple-valued, and

wherein said means for interpreting the knowledge base includes

means for determining the value of said goal expression including

means for searching the knowledge base for occurrences of the goal expression,

means for invoking and chaining said rules to conclude a value for said goal expression,

means for evaluating the logical operations in the premises of the invoked rules,

means for terminating the searching of the knowledge base for a single-valued expression when a certain value is found and for a multiple-valued expression when all values for the expression are determined, and

means for instantiating and de-instantiating the universally quantified variables in said rules, and

means for conveying to the user said value of said goal expression.

18. A knowledge engineering tool comprising

a computer having memory for storing a knowledge base and memory for storing predetermined instructions including

means to augment and edit the knowledge base, and

means for interpreting the knowledge base to run an interactive consultation with the user to determine the value of at least one predetermined goal expression,

wherein said knowledge base includes

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for said goal expression, said rules including recursive rules and rules having universally quantified variables,

certainty factors associated with said facts and rules for encoding uncertain as well as certain knowledge,

propositions including arithmetic operations,

propositions responsive to whether a value of a predetermined expression has been determined with a predetermined degree of certainty,

declarations defining whether selected expressions are single-valued or multiple-valued,

declarations defining questions to be asked to determine the values of selected expressions, and

declarations defining legal values of selected expressions, and

wherein said means for interpreting the knowledge base includes

means for determining the value of said goal expression including

means for searching the knowledge base for occurrences of the goal expression,

means for invoking and chaining said rules to conclude a value for said goal expression,

means for evaluating the logical operations of the premises of the invoked rules and selecting certainty factors for the concluded values based on the certainty factors of the rules and the certainty factors of the premises,

means for updating the certainty factor of a value of an expression by combining certainty factors,

means for evaluating said propositions,

means for terminating the searching of the knowledge base for a single-valued expression when a certain value is found and for a multiple-valued expression when all values for the expression are determined,

means for instantiating and de-instantiating the universally quantified variables in said rules,

means for asking the user said questions when the values of their corresponding expressions are not known with a predetermined certainty,

means for receiving from the user and checking values of said corresponding expressions against the corresponding declared legal values, and

means for explaining to the user why the user is asked for the values of said corresponding expressions,

means for conveying to the user said value of said goal expression and its certainty factor,

means for explaining to the user how said value of said goal expression was determined, and

means for generating a record of said consultation including a list of the rules invoked during a test consultation.

19. The knowledge engineering tool as claimed in claim 18, wherein the sequence in which rules concluding said expressions are invoked is determined by the order in which said rules appear in said knowledge base.

20. The knowledge engineering tool as claimed in claim 19, wherein said rules concluding values of said expressions for which said questions are defined are not invoked, when said rules appear after the respective questions for said expressions, until after said questions are asked when the respective values of said expressions are not known with a predetermined certainty.

21. The knowledge engineering tool as claimed in claim 18, wherein said memory of said computer includes a cache memory for sequentially recording said expressions, their corresponding values and certainty factors, whenever the values for said expressions are determined by said means for determining.

22. The knowledge engineering tool as claimed in claim 21, wherein at least some of said facts and rules include labels identifying particular ones of said facts and rules, and wherein said cache stores the labels of the corresponding facts and rules used in determining the corresponding values of said expressions.

23. The knowledge engineering tool as claimed in claim 18, wherein said propositions include user-defined propositions.

24. The knowledge engineering tool as claimed in claim 23, wherein said user defined propositions include PROLOG subroutines.

25. The knowledge engineering tool as claimed in claim 21, wherein the means for determining the value and said certainty factor of said goal expression include means for sequentially checking whether said expression includes one of said propositions for immediate execution;

thereafter determining whether the expression has already been determined for obtaining its already determined value; and

thereafter checking the knowledge base for the occurrence of said expression.

26. The knowledge engineer tool as claimed in claim 25, wherein the means for determining the value and said certainty factor of said goal expression further includes means for determining a value of unknown when said knowledge base has been checked for the occurrence of said expression and no value for said expression is determinable from said knowledge base so that said knowledge base is not searched twice for the value of said goal expression.

27. The knowledge engineering tool as claimed in claim 18, wherein said means for the user to augment and edit the knowledge base includes a disk memory device including a knowledge base disk file and a standard microcomputer text editor for editing the knowledge base disk file.

28. The knowledge engineering tool as claimed in claim 27, further comprising means for loading said knowledge base from said disk file;

wherein said disk file includes comments and multiple blanks, and said means for loading includes means for deleting comments and multiple blanks.

29. A process of operating a computer having a memory to execute a knowledge base stored in the memory to run an advisory consultation about a predefined goal expression included in the knowledge base, said knowledge base comprising entries including

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for a corresponding expression, said rules including recursive rules and rules having universally quantified variables,

meta-facts equivalent in form to facts but prescribing the manner in which facts and rules should be used, and

declarations defining whether certain of said expressions are single-valued or multiple-valued,

said process comprising the steps of:

searching the knowledge base for occurrences of said goal expression, and

determining the value of said goal expression by invoking said rules concluding a value for said goal expression,

searching the knowledge base for entries concluding values for subsidiary goal expressions found in the premises of said invoked rules,

invoking said rules concluding values for said subsidiary goal expressions including evaluating said logical operations in said premise of said rules and instantiating and de-instantiating said logical variables to said subsidiary goal expressions,

chaining said rules concluding values for said subsidiary goal expressions with said rules concluding a value for said goal expression,

terminating the searching of the knowledge base for a single-valued expression when a substantially certain value is found, and for a multiple-valued expression when all values for the expression are determined, and

transmitting to the user said determined value for said goal expression along with an explanation of how said value was determined for said goal expression.

30. A process as set forth in claim 29 wherein the step of determining the value of said goal expression includes the recording of the rules invoked and concluding a value for said goal expression, and said explanation of how said value was determined for said goal expression includes a listing of the rules concluding said values.

31. A process as set forth in claim 29 wherein,

said knowledge base includes declarations defining questions to be asked to determine the values of certain of said subsidiary goal expressions, and

the step of determining the value of said goal expression includes the steps of

asking the user said questions when the values of their corresponding subsidiary goal expressions are not known with a predetermined certainty when said questions are found in the knowledge base, and

receiving from the user values for said expressions.

32. A process as set forth in claim 31, wherein the step of determining the value of said goal expression further comprises the step of generating and asking the user an appropriate question after the knowledge base is searched for any of said subsidiary goal expressions and respective values for said subsidiary goal expressions are not determined.

33. A process as set forth in claim 29, wherein the step of determining the value of said goal expression further includes the step of determining a value of unknown for any of said subsidiary goal expressions that are not determined after the knowledge base is searched for said subsidiary goal expressions so that said knowledge base is not searched twice for the value of said subsidiary goal expressions.

34. A knowledge system comprising a computer having memory for storing a knowledge base including expressions, and

means for interpreting the knowledge base to determine the value of a selected one of said expressions,

wherein said knowledge base includes a plurality of entries including

facts expressed as expressions equivalenced to corresponding values,

rules including premises having logical operations and corresponding conclusions concluding at least one value for respective expressions, said facts and rules including respective certainty factors for encoding certain as well as uncertain knowledge, and

declarations defining questions to be asked of a user to determine the values of certain of said expressions, and

wherein said means for interpreting said knowledge base to determine the value of selected expression includes

means for sequentially searching the knowledge base to find occurrences of the selected expression,

means for determining whether an occurrence of the selected expression is found in a fact equivalencing a value for the selected expression and thereupon determining the equivalenced value and certainty factor for said expression,

means for determining whether an occurrence of the selected expression is found in a rule concluding a value for the selected expression and thereupon evaluating the premise of the rule by evaluating the logical operations in the premise and recursively searching the knowledge base to determine values for expressions that are arguments of said logical operations, and upon evaluation of the premise of the rule conditionally concluding a value and certainty factor for the selected expression responsive to the respective certainty factor of the rule and the evaluation of the premise, and

means for determining whether an occurrence of the selected expression is found in a declaration defining a question to be asked the user, and thereupon asking the user for a value and certainty factor for the selected expression.

35. The knowledge system as claimed in claim 34 wherein the memory includes a cache portion for storing the determined values and certainty factors for expressions, and wherein the means for determining the value of a selected expression includes means for first checking whether a value for the selected expression is already stored in the cache and when a value is already stored thereupon terminating the determination procedure.

36. The knowledge system as claimed in claim 35 wherein the cache includes a portion for storing the reason for concluding each value stored in the cache, and the means for determining the value of a selected expression includes means for storing a label along with each determined value stored in cache identifying the reason for concluding the value including identification of a respective rule concluding the value, identification of a respective fact equivalencing the value, and identification that the user was asked for the value.

37. The knowledge system as claimed in claim 34 wherein the knowledge base includes means for identifying whether an expression in the knowledge base is single-valued or multiple-valued, and means for determining the value of a selected expression includes means for terminating the searching of the knowledge base for single-valued expression when a substantially certain value is found, and for a multiple-valued expression when the entire knowledge base is searched.

38. The knowledge system as claimed in claim 34, wherein

said rules in said knowledge base include recursive rules and rules having universally quantified variables, and

wherein said means for determining the value of a selected expression includes means for instantiating and de-instantiating the universally quantified variables in said rules.

39. The knowledge system as claimed in claim 38, wherein said expressions in said knowledge base include functions, and said means for instantiating and de-instantiating the universally quantified variables in said rules includes means for instantiating function argument variables to respective function argument values.

40. The knowledge system as claimed in claim 34, wherein said knowledge base includes at least one built-in function responsive to the certainty factor of an argument expression, and said means for determining the value of a selected expression includes means for evaluating said built-in function.