Apparatus and method for generating a knowledge base

• US 5,546,507 A
• Filed: 08/20/1993
• Issued: 08/13/1996
• Est. Priority Date: 08/20/1993
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Staub, Wendy C.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/111,251
• Time in Patent Office: 1,089 Days
• Field of Search: 395/76, 395/12, 395/51
• US Class Current: 706/60
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

The present invention relates to a method and apparatus for automatically generating a knowledge base for use in an expert system. More specifically, the present invention discloses a method and system for automatically generating a knowledge base using a graphical programming environment to create a logical tree from which such a knowledge base may be generated. This enables a user of the present invention to author a knowledge base without knowledge of artificial intelligence specific languages and constructs. This is accomplished by permitting the user to construct a graphical picture that represents the problem solving knowledge about a given subject known as a decision tree, or logical tree. The arrangement of the graphical objects in the logical tree, along with the logical attachments associated with these objects, is used by the system employing the present invention to generate a knowledge base.

Claims

1. A system including a computer and a display means for constructing a logical tree having at least one non-disjunctive branch and displaying a graphical representation of said logical tree for use in automatically generating a knowledge base in a computer comprising:

a) node generation means for generating a node in said tree wherein a graphical representation of said node is displayed on said display means;

b) type definition means for defining the type of said node wherein permissible node types include a test node type and a solution node type;

c) test definition means for defining a test associated with said test node type node;

d) solution definition means for defining a solution associated with said solution node type node;

e) leg definition means for defining a leg associated with two nodes wherein a graphical representation of said leg may be displayed on said display means; and

f) formula definition means for defining a formula associated with said leg.

2. The system of claim 1 which further comprises:

g) component generation means for generating components for use in creating results and tests.

3. The system of claim 2 wherein said components are defined as a plurality of attributes wherein said plurality of attributes includes an integer type, a truth type, and a list type.

4. A method for automatically generating a knowledge base in a computer from a graphical representation of a logical tree having at least one non-disjunctive branch, comprising the steps of:

a) verifying the organization of said logical tree;

b) verifying the content of said logical tree;

c) generating a plurality of global attributes;

d) creating a plurality of classes; and

e) creating a plurality of rules as defined by said tree using said plurality of global attributes and said plurality of classes, wherein said rules are executable by an inference engine in a backward chaining mode;

wherein said step of verifying the content of said tree comprises the steps of;

b1) verifying that a valid formula is associated with each said leg;

b2) verifying that a valid test is associated with each said test node;

b3) verifying that a valid solution is associated with each solution node; and

b4) verifying that each link node in said logical tree is linked to either a procedure or to a domain.

5. The method of claim 4 further including the step

f) generating links to electronic documents referenced by said knowledge base.

6. The method of claim 4 wherein said step of verifying the organization of said logical tree comprises the steps of:

a1) verifying that each test node in said logical tree has at least one leg leading out of said test node; and

a2) verifying that each leg in said logical tree is connected to two and only two nodes wherein at least one of said two nodes is a test node.

7. The method of claim 4 wherein said step of generating said plurality of global attributes comprises the steps of:

c1) determining the identity of domains referenced by the present domain; and

c2) creating a domain list attribute wherein said domains determined in step c1 are possible values for said domain list attribute.

8. The method of claim 7 wherein said step of generating said plurality of global attributes comprises the steps of:

c3) identifying a plurality of solution nodes in a present domain; and

c4) creating a solution list attribute wherein said solution nodes identified in step c3 are possible values for said solution list attribute.

9. The method of claim 8 wherein said step of generating said plurality of global attributes comprises the steps of:

c5) identifying a plurality of test nodes in a present domain; and

c6) creating a truth attribute for each test node identified in step c5.

10. The method of claim 4 wherein said step of creating said plurality of classes includes the step of:

d1) creating a class for a component in a present domain based upon attributes of said component and possible values associated with said attributes.

11. The method of claim 4 wherein said step of creating a plurality of rules comprises the steps of:

e1) determining the identity of a path beginning with a root test node and ending at a solution node wherein said path comprises a plurality of path legs and a plurality of test nodes;

e2) generating a first boolean evaluation statement for a given knowledge base language employing a formula associated with a first leg of said path;

e3) determining if there is another leg in said path;

e4) generating a second boolean evaluation statement for the given knowledge base language employing a formula associated with a next leg of said path if another leg was determined to exist in step e3;

e5) concatenating said second boolean evaluation statement with said first boolean evaluation statement using a logical connector to form a new first boolean evaluation statement if another leg was determined to exist in step e3;

e6) repeating steps e3, e4, and e5 until it is determine in step e3 that there is not another said test node and said leg in said path;

e7) formatting a solution associated with said solution node as appropriate for the given knowledge base language; and

e8) writing said first boolean evaluation statement and said formatted solution to said knowledge base.

12. The method of claim 11 which further includes the step of:

e9) verifying that said boolean evaluation statement comprises a valid combination of valid components, operators, facts, and attributes.

13. The method of claim 4 wherein said step of creating a plurality of rules comprises the steps of:

e1) starting with a first node of an ordered node list, identifying a left-most path leg leading into said first node;

e2) identifying the node from which the left-most path leg identified in step e1 originates;

e3) if the first node is a solution node, formatting a rule consequent by adding this node to a global solution attribute list;

e4) if the first node is a domain link node, formatting the rule consequent by adding this node to the global solution attribute list;

e5) if the first node is a procedure link node, formatting the rule consequent by asserting a global truth attribute associated with the root node of the linked procedure to true;

e6) if the first node is a test node, formatting the rule consequent by asserting the global truth attribute associated with this node to true;

e7) formatting a Boolean expression in the knowledge base language based on a formula found at the current path leg, wherein this expression is made a part of a rule antecedent;

e8) determining if the node from which this path originates is the root node and, if not, formatting a Boolean expression to test the global truth attribute associated with the originating node, wherein this expression is made a part of the rule antecedent, and concatenating the node and path Boolean expressions with a logical AND;

e9) repeating steps e1 through e8 for each path leading into the first node and, each time a path is processed, concatenating the resulting expression to the rule antecedent with a logical OR; and

e10) generating a knowledge base language rule using the formatted rule antecedent and the rule consequent.

14. The method of claim 13 which further includes the step of:

e11) repeating the steps recited in claim 30 for every node in the ordered node list.

22. The method of claim 15 which further includes the step of:

e11) repeating the steps recited in claim 11 for every node in the ordered node list.

15. A method for automatically generating a knowledge base in a computer from a graphical representation of a logical tree having at least one non-disjunctive branch, comprising the steps of:

a) verifying the organization of said logical tree;

b) verifying the content of said logical tree;

c) generating a plurality of global attributes;

d) creating a plurality of classes; and

e) creating a plurality of rules as defined by said tree using said plurality of global attributes and said plurality of classes, wherein said rules are executable by an inference engine in a backward chaining mode;

wherein said step of creating a plurality of rules comprises the steps of;

e1) starting with a first node of an ordered node list, identifying a left-most path leg leading into said first node;

e2) identifying the node from which the left-most path leg identified in step e1 originates;

e3) if the first node is a solution node, formatting a rule consequent by adding this node to a global solution attribute list;

e4) if the first node is a domain link node, formatting the rule consequent by adding this node to the global solution attribute list;

e5) if the first node is a procedure link node, formatting the rule consequent by asserting a global truth attribute associated with the root node of the linked procedure to true;

e6) if the first node is a test node, formatting the rule consequent by asserting the global truth attribute associated with this node to true;

e7) formatting a Boolean expression in the knowledge base language based on a formula found at the current path leg, wherein this expression is made a part of a rule antecedent;

e8) determining if the node from which this path originates is the root node and, if not, formatting a Boolean expression to test the global truth attribute associated with the originating node, wherein this expression is made a part of the rule antecedent, and concatenating the node and path Boolean expressions with a logical AND;

e9) repeating steps e1 through e8 for each path leading into the first node and, each time a path is processed, concatenating the resulting expression to the rule antecedent with a logical OR; and

e10) generating a knowledge base language rule using the formatted rule antecedent and the rule consequent.

16. The method of claim 15 further including the step of:

f) generating links to electronic documents referenced by said knowledge base.

17. The method of claim 15 wherein said step of verifying the organization of said logical tree comprises the steps of:

a1) verifying that each test node in said logical tree has at least one leg leading out of said test node; and

a2) verifying that each leg in said logical tree is connected to two and only two nodes wherein at least one of said two nodes is a test node.

18. The method of claim 15 wherein said step of generating said plurality of global attributes comprises the steps of:

c1) determining the identity of domains referenced by the present domain; and

c2) creating a domain list attribute wherein said domains determined in step c1 are possible values for said domain list attribute.

19. The method of claim 18 wherein said step of generating said plurality of global attributes comprises the steps of:

c3) identifying a plurality of solution nodes in a present domain; and

c4) creating a solution list attribute wherein said solution nodes identified in step c3 are possible values for said solution list attribute.

20. The method of claim 19 wherein said step of generating said plurality of global attributes comprises the steps of:

c5) identifying a plurality of test nodes in a present domain; and

c6) creating a truth attribute for each test node identified in step c5.

21. The method of claim 15 wherein said step of creating said plurality of classes includes the step of:

d1) creating a class for a component in a present domain based upon attributes of said component and possible values associated with said attributes.

23. The method of claim 15 wherein said step of creating a plurality of rules comprises the steps of:

e11) determining the identity of a path beginning with a root test node and ending at a solution node wherein said path comprises a plurality of path legs and a plurality of test nodes;

e12) generating a first boolean evaluation statement for a given knowledge base language employing a formula associated with a first leg of said path;

e13) determining if there is another leg in said path;

e14) generating a second boolean evaluation statement for the given knowledge base language employing a formula associated with a next leg of said path if another leg was determined to exist in step e3;

e15) concatenating said second boolean evaluation statement with said first boolean evaluation statement using a logical connector to form a new first boolean evaluation statement if another leg was determined to exist in step e3;

e16) repeating steps e3, e4, and e5 until it is determine in step e3 that there is not another said test node and said leg in said path;

e17) formatting a solution associated with said solution node as appropriate for the given knowledge base language; and

e16) writing said first boolean evaluation statement and said formatted solution to said knowledge base.

24. The method of claim 23 which further includes the step of:

e19) verifying that said boolean evaluation statement comprises a valid combination of valid components, operators, facts, and attributes.