Expert knowledge system development tool

• US 4,970,657 A
• Filed: 10/03/1989
• Issued: 11/13/1990
• Est. Priority Date: 01/06/1989
• Status: Expired due to Fees

• Current Assignee: Advanced Cell Technology Incorporated (Astellas Pharma Incorporated)
• Original Assignee: US Advanced Technologies NV
• Inventors: Wolf, Daniel
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US07/416,702
• Time in Patent Office: 406 Days
• Field of Search: 364/300, 364/513, 364/200, 364/274.5, 364/274.7, 382/14, 382/15, 382/36, 382/37, 382/38
• US Class Current: 706/52
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

An apparatus and method for an expert knowledge system developmental tool 50 comprising a computer 52 with a structure for storing a knowledge base 54 and an inference engine 56 for inferring from the knowledge base 54. The knowledge base 54 defines a plurality of positive and negative rules 402,410, each rule having one or more antecedents 302 and one conclusion 328. The interference engine 56 includes structure 100 for storing a hypothesis list and structure 100 for selecting rules that have a conclusion which match each hypothesis and the negative of each hypothesis. Further, the inference engine 56 includes structure 116-150 for analyzing the selected rules 402, 410 with respect to each other in order to determine a value of each hypothesis, and structure 162-184 for analyzing the antecedent 302 of each rule to determine a value for each rule 402, 410.

Claims

1. An expert knowledge system development tool comprising a computer with means for storing a knowledge base and inference engine means for inferencing with respect to at least one hypothesis variable from said knowledge base storing means comprising:

said knowledge base storing means including;

means for defining a plurality of positive and negative rules wherein said rules defining means includes;

(a) means for defining at least an antecedent variable for each of said rules and means for defining a conclusion variable for each of said rules; and

said inference engine means including;

(a) means for storing a hypothesis variable list containing said at least one hypothesis variable;

(b) means for automatically selecting and ordering said rules stored in said knowledge base storing means to establish the structures of said rules into a rule tree by determining if any conclusion variable is also an antecedent variable;

(c) means for selecting and sorting said rules ordered in said rule tree that have conclusion variables which match each hypothesis variable into one bundle and said rules that have conclusion variables which match the negative of each hypothesis variable into another bundle; and

(d) means for analyzing the selected said rules with respect to one another for each bundle separately in order to determine a value for each hypothesis variable.

2. The expert system development tool of claim 1 wherein said means for automatically selecting and ordering said rules includes:

means for establishing a type designation for each variable;

means for adding a value of one to the type designation for all conclusion variables;

means for adding a value of two to the type designation for all antecedent variables so that conclusion variables which are also antecedent variables have a type designation of three;

means for ordering the rules according to the value of the type designation.

3. The expert knowledge system development tool of claim 1 wherein said means for selecting rules includes means for ordering selected positive rules first and selected negative rules second.

4. The expert knowledge system development tool of claim 1 wherein said means for analyzing the selected rules to determine the value of each hypothesis variable includes:

first means for assigning a value of True to the hypothesis variable if there is one positive rule with a conclusion variable which has a value of True;

second means for assigning a value of False to the hypothesis variable if there is one negative rule with a conclusion variable which has a value of True;

third means for assigning a value of False to the hypothesis variable if all positive rules have a conclusion variable which has a value of False;

fourth means for assigning a value of True to the hypothesis variable if all negative rules are False;

fifth means for assigning a value of Unknown if all positive and negative rules have conclusion variables with Unknown values.

5. The expert knowledge system development tool of claim 4 including:

sixth means for assigning a value of Untested to any rule that does not have a value of one of True, False, and Unknown.

seventh means for selecting and analyzing Untested rules when value of the hypothesis variable is other than one of True, False and Unknown.

6. The expert knowledge system development tool of claim 5 wherein said seventh means for selecting and analyzing Untested rules include:

eighth means for assigning a value of True to an Untested rule which has all antecedent variables with a value of True;

ninth means for assigning a value of False to an Untested rule if one antecedent variable of said rule is False;

tenth means for assigning a value of Unknown to an Untested rule if no antecedent variable of the Untested rule remain Untested;

eleventh means for returning to the means for analyzing selected rules if a value of one of True, False and Unknown is not assigned to the Untested rule.

7. The expert, knowledge system development tool of claim 6 including:

means for returning to the means for storing a hypothesis variable list and for replacing a hypothesis variable of the hypothesis variable list with a first Untested antecedent variable of a Untested rule if the value of the Untested rule is other than one of True, False and Unknown.

8. The expert knowledge system development tool of claim 1 including:

means for analyzing the antecedent variable of each rule to determine a value for each rule.

9. The expert knowledge system development tool of claim 8 wherein said means for analyzing the antecedent variable of each rule to determine a value for each rule includes:

first means for assigning a value of True to the conclusion variable of a rule and to the rule if all antecedent variable of the rule are True;

second means for assigning a value of False to a rule if one antecedent variable of the rule is False; and

third means for assigning a value of Unknown to a rule if no antecedent variable remaisn tested.

10. The expert knowledge system development tool of claim 9 including:

means for analyzing the value of each rule at least once; and

means for reanalyzing the value of each rule should any conclusion variable be assigned a value of True during the previous analysis.

11. The expert knowledge system development tool of claim 8 wherein the means for analyzing the antecedent variable of each rule include means for applying a forward chaining process to each rule.

12. The expert knowledge system development tool of claim 1 wherein said means for analyzing the selected rules with respect to each other includes means for applying a backward chaining process between the selected rules.

13. The expert system development tool of claim 1 including means for initially selecting all conclusion variables that are not similar to any antecedent variable and for selecting all conclusion variables that are similar to any antecedent variables.

14. The tool of claim 1 wherein said knowledge base storing means includes:

means for storing a set of logical variables.

15. An expert knowledge system development tool method for inferencing with respect to at least one hypothesis variable from a knowledge base with an inference engine including the steps of:

defining a plurality of positive and negative rules;

defining at least an antecedent variable for each of said rules and a conclusion variable for each of said rules;

storing a hypothesis variable list containing said at least one hypothesis variable;

automatically selecting and ordering said rules to establish the structure of said rules into a rule tree by determining if any conclusions are also antecedent;

selecting and sorting said rules ordered into said rule tree that have conclusion variables which match each hypothesis variable into one bundle and the negative of each hypothesis variable into another bundle of said list;

inferencing with respect to the selected rules with respect to one another for each bundle separately in order to determine a value for each hypothesis variable.

16. The expert system development tool method of claim 15 wherein said step of automatically selecting and ordering said rules includes:

establishing a type designation for each variable;

adding a value of one to the type designation for all conclusion variables;

adding a value of two to the type designation for all antecedent variables so that conclusion variables which are also antecedent variables have a type designation of three;

ordering the rules according to the value of the type designation.

17. The method of claim 15 wherein said step of selecting rules includes the step of ordering selected positive rules first and selected negative rules second.

18. The method of claim 15 wherein the step of analyzing the selected rules to determine the value of each hypothesis variable includes the sequential steps of:

first, assigning a value of True to the hypothesis variable if there is one positive rule with a conclusion variable which has a value of True;

second, assigning a value of False to the hypothesis variable if there is one negative rule with a conclusion variable which has a value of True, and if a value is not assigned by the first step;

third, assigning a value of False to the hypothesis variable if all positive rules have a conclusion variable which has a value of False, and if a value is not assigned by the second step;

fourth, assigning a value of True to the hypothesis variable if all negative rules are False, and if a value is not assigned by the third step;

fifth, assigning a value of Unknown if all positive and negative rules have conclusion variables with Unknown values, and if a value is not assigned by the fourth step.

19. The method of claim 18 including the sequential steps of:

sixth, assigning a value of Untested to any rule that does not have a value of one of True, False, and Unknown, and if a value is not assigned by the fifth step;

seventh, selecting and analyzing Untested rules when value of the hypothesis variable is other than one of True, False and Unknown.

20. The method of claim 19 wherein said seventh step of selecting and analyzing Untested rules include the sequential steps of:

eighth, assigning a value of True to an Untested rule which has all antecedent variables with a value of True;

ninth, assigning a value of False to an Untested rule if one antecedent variable of said rule is False, and if a value is not assigned by the eighth step;

tenth, assigning a value of Unknown to an Untested rule if no antecedent variable of the Untested rule remain Untested, and if a value is not assigned by the ninth step; and

eleventh, returning to the means for analyzing selected rules if a value of one of True, False and Unknown is not assigned to the Untested rule.

21. The method of claim 20 including the steps of:

returning to the step of storing a hypothesis variable list; and

replacing a hypothesis variable of the hypothesis variable list with a first Untested antecedent variable of a Untested rule if the value of the Untested rule is other than one of True, False and Unknown.

22. The method of claim 15 including the step of:

inferencing with respect to the antecedent variable of each rule to determine a value for each rule.

23. The method of claim 22 wherein said step for analyzing the antecedent variable of each rule to determine a value for each rule includes the sequential steps of:

first, assigning a value of True to the conclusion variable of a rule and to the rule if all antecedent variables of the rule are True;

second, assigning a value of False to a rule if one antecedent variable of the rule is False and if a value is not assigned by the first step; and

third, assigning a value of Unknown to a rule if no antecedent variables remain tested.

24. The method of claim 23 including the steps of:

analyzing the value of each rule at least once; and

reanalyzing the value of each rule should any conclusion variable be assigned a value of True during the previous analysis.

25. The method of claim 22 wherein the step of inferencing with respect to the antecedent variable of each rule to determine a value for each rule occurs before the step of inferencing with respect to the selected rules to determine a value for each hypothesis variable.

26. The method of claim 22 wherein the step of inferencing with respect to the selected rules and the step of inferencing with respect to the antecedent variable of each selected rule occur alternatingly until a value for each hypothesis variable is determined.

27. The method of claim 15 wherein said step of analyzing the selected rules with respect to each other includes the step of applying a backward chaining process between the selected rules.

28. The method of claim 15 wherein the step of analyzing the antecedent variables of each rule includes the step of applying a forward chaining process to each rule.

29. The method of claim 15 including the steps of:

selecting all conclusion variables that are not similar to any antecedent variables; and

selecting all conclusion variables that are similar to any antecedent variables.

30. An expert knowledge system development tool comprising a computer with means for storing a plurality of knowledge bases and inference engine means for inferencing with respect to at least one hypothesis variable from said knowledge bases storing means including:

means for defining a plurality of positive and negative rules wherein said rules defining means includes;

(a) means for defining at least an antecedent variable for each of said rules and means for defining a conclusion variable for each of said rules; and

said inference engine means including;

(a) means for storing a hypothesis variable list containing said at least one hypothesis variable;

(b) means for selecting and sorting rules that have conclusion variables which match each hypothesis variable into one bundle and rules that have conclusion variables which match the negative of each hypothesis variable into another bundle;

(c) means for analyzing the selected rules with respect to one another for each bundle separately in order to determine a value for each hypothesis variable; and

means for automatically sequencing between knowledge bases including;

(a) means for defining a first knowledge base having a first list of numbered variables that can be at least one of conclusion variables and antecedent variables;

(b) means for defining a second knowledge base having a second list of numbered variables, corresponding to the first list of numbered variables, that can be at least one of conclusion variables and antecedent variables; and

(c) means for using the determined value of each variable for said first list to be used for the initial values of the corresponding numbered variable of said second list.

31. An expert knowledge system development tool method for inferencing from a plurality of knowledge bases with an inference engine including the steps of:

defining a plurality of positive and negative rules;

defining at least an antecedent variable for each of said rules and a conclusion variable for each of said rules;

storing a hypothesis variable list containing said at least one hypothesis variable;

selecting and sorting rules that have conclusion variables which match each hypothesis variable into one bundle and the negative of each hypothesis variable into another bundle of said list;

inferencing with respect to the selected rules with respect to one another for each bundle separately in order to determine a value for each hypothesis variable; and

automatically sequencing between knowledge bases including the steps of;

(a) providing a first knowledge base having a first list of numbered variables that can be conclusion variables and antecedent variables;

(b) providing a second knowledge base having a second list of numbered variables, corresponding to the first list of numbered variables, that can be conclusion variables and antecedent variables;

(c) using the determined value of each variable for said first list as the initial values of the corresponding numbered variable of said second list.