Knowledge engineering tool

• US 4,658,370 A
• Filed: 06/07/1984
• Issued: 04/14/1987
• Est. Priority Date: 06/07/1984
• Status: Expired due to Term

• Current Assignee: Teknowledge Corporation
• Original Assignee: Teknowledge Corporation
• Inventors: Clancey, William J., Bennett, James S., Lark, Jay S., Scott, A. Carlisle, London, Philip E., Erman, Lee D.
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US06/618,038
• Time in Patent Office: 1,041 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/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: Y10S 706/903 Control

Abstract

A tool is used for knowledge engineers for building and interpreting a knowledge base having separate portions encoding control knowledge, factual knowledge, and judgmental rules. The tool has an inference engine applying the judgmental rules according to a built-in control procedure defining discrete states or control steps during a consultation with a user. The control knowledge is encoded in an applicative and imperative language defining control actions to be executed during interruption of the built-in control procedure at specified control steps. Since the control knowledge is explicit and results in the modification of data only in a precisely defined fashion, the tool can be used to build knowledge systems that can always explain their conclusions and reasoning, and that are intelligible and modifiable. To provide transparent representation of control knowledge as well as factual knowledge, the knowledge base is preferably organized into distinct frames which include the rules; control blocks separately encoding the control knowledge; and classes which become instantiated, attributes which take on values describing the class instances, class types, legal value hierarchies, and user-defined functions, which all encode factual knowledge. The knowledge engineer may provide control blocks to be executed at the start of the consultation, after the instantiation of specified classes, when a value for a specified attribute is to be determined, after a specified attribute is determined, and upon explicit invocation by another control block. The tool can also implicitly determine subsumed attributes.

Claims

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

said knowledge base including factual knowledge and judgmental knowledge, said judgmental knowledge including judgmental rules having premises for limiting the conditions in which the rules are applicable and conclusions for indicating the actions to perform when the rules are successfully applied,

said factual knowledge including definitions of attributes that can take on values,

said judgmental rules including rules having premises referring to attributes and rules concluding values for attributes,

means for executing a built-in control procedure including

means for interpreting the knowledge base,

means for invoking and chaining said rules, and

means for terminating the knowledge base search for a value,

said knowledge base also including control knowledge supplied by a knowledge engineer to modify the built-in control procedure, and

a language interpreter for executing the control knowledge to modify the built-in control procedure, whereby the control knowledge can be separated from the factual knowledge and judgmental knowledge and stored as a distinct portion of the knowledge base.

2. A knowledge engineering tool as set forth in claim 1 which includes means for creating, editing and augmenting said knowledge base.

3. A knowledge engineering tool as set forth in claim 1 wherein said knowledge base includes,

certainty factors for said values of attributes and rules,

predicates responsive to the certainty factor of the values of attributes,

declarations defining whether attributes are single-valued or multi-valued,

declarations defining legal values for attributes,

declarations defining that certain values of said attributes are of a prescribed type.

4. A knowledge engineering tool as set forth in claim 1 which includes interface means with predefined commands for a user to load said knowledge base, start said consultation, end said consultation, and save the results of said consultation.

5. A knowledge engineering tool as set forth in claim 1 which includes means for displaying to the user conclusions of the rules applied.

6. A knowledge engineering tool as set forth in claim 1 which includes means for declaring classes of objects, means for declaring a vector of said classes for each of said attributes, and means for creating instances of said classes.

7. A knowledge engineering tool as set forth in claim 6 wherein said means for creating instances of said classes includes means for implicitly creating instances of a class when a rule is applied having a premise including an attribute defined on a vector of classes including said class.

8. A knowledge engineering tool as set forth in claim 6 wherein said knowledge base includes judgmental rules having premises including quantified conditions determining whether a specified condition succeeds for a specified set of instances.

9. A knowledge engineering tool as set forth in claim 6 which includes means for producing information as to why an instance was created.

10. A knowledge engineering tool as set forth in claim 1 wherein said knowledge base includes declarations describing phrases to use when translating into conventional humanly readable language, knowledge base declarations of classes, class types, instances, control blocks, functions, value hierarchies, and attributes.

11. A knowledge engineering tool as set forth in claim 1 wherein said knowledge base includes declarations defining questions to ask a user to determine values.

12. A knowledge engineering tool as set forth in claim 1 which includes means for receiving values from the user for specified attributes.

13. A knowledge engineering tool as set forth in claim 1 which includes means for receiving uncertain values from the user for specified attributes.

14. A knowledge engineering tool as set forth in claim 1 which includes means for checking values for an attribute against predefined legal values for that attribute.

15. A knowledge engineering tool as set forth in claim 1 which includes means for translating said control knowledge into a conventional humanly readable language.

16. A knowledge engineering tool as set forth in claim 1 which includes means for explaining why and how said control knowledge was used at particular points during a particular consultation with a user.

17. A knowledge engineering tool as set forth in claim 1 which includes means defining a precise language having syntax for said control knowledge.

18. A knowledge engineering tool as set forth in claim 1 wherein said control knowledge is encoded in an imperative procedural language defining a sequence of steps.

19. A knowledge engineering tool as set forth in claim 18 wherein the imperative control language is applicative.

20. A knowledge engineering tool as set forth in claim 1 wherein said control knowledge is expressed as a number of discrete control blocks.

21. A knowledge engineering tool as set forth in claim 20 wherein a control block includes statements in a control language.

22. A knowledge engineering tool as set forth in claim 21 wherein said control language is an imperative procedural language.

23. A knowledge engineering tool as set forth in claim 21 wherein some of said statements request that particular attributes be determined.

24. A knowledge engineering tool as set forth in claim 21 wherein some of said statements attempt to reach conclusions about attributes using prescribed means.

25. A knowledge engineering tool as set forth in claim 21 wherein some of said statements attempt to reach conclusions about attributes by applying specified sets of judgmental rules.

26. A knowledge engineering tool as set forth in claim 21 wherein some of said statements display arbitrary text to the user.

27. A knowledge engineering tool as set forth in claim 21 wherein some of said statements execute other specified control blocks.

28. A knowledge engineering tool as set forth in claim 21 wherein said attributes are defined on predetermined vectors of classes of objects, and some of said statements cause explicit instantiation of specified classes.

29. A knowledge engineering tool as set forth in claim 1 which includes means for indicating that the execution of said control knowledge to run a consultation is to commence in a prescribed control block.

30. A knowledge engineering tool as set forth in claim 1 wherein said attributes are defined on predetermined vectors of classes of objects, and further including means for causing instances of a class to be created.

31. A knowledge engineering tool as set forth in claim 30 wherein said control knowledge comprises a plurality of discrete control blocks, and means for associating selected post-instantiation control blocks with selected classes of objects.

32. A knowledge engineering tool as set forth in claim 30 wherein said instances of a class are implicitly caused to be created.

33. A knowledge engineering tool as set forth in claim 32 wherein said control knowledge comprises a plurality of discrete control blocks and said interpreter comprises means for interrupting the execution of said control language to execute the control knowledge statements in selected post-instantiation control blocks associated with a selected class when an instance of said class has been created.

34. A knowledge engineering tool as set forth in claim 1 wherein said control knowledge includes control blocks specifying methods for determining the values of prescribed attributes.

35. A knowledge engineering tool as set forth in claim 34 which includes means for interrupting the application of a rule in order to execute said control block to determine the value of an attribute in the premise of said rule.

36. A knowledge engineering tool as set forth in claim 34 which includes means for interrupting the execution of a control block in response to an explicit request within the control block for determination of one of said prescribed attributes.

37. A knowledge engineering tool as set forth in claim 1 wherein said control knowledge includes a plurality of control blocks, some of which are post-determination control blocks associated with selected attributes.

38. A knowledge engineering tool as set forth in claim 37 which includes post-determination control blocks for accessing and using concluded values of said associated attributes.

39. A knowledge engineering tool as set forth in claim 37 which includes means for executing a post-determination control block after a value has been determined for an attribute associated with said control block.

40. A knowledge engineering tool as set forth in claim 1 wherein said knowledge base includes user-defined functions and said judgmental rules include calls to said user defined functions.

41. A knowledge engineering tool as set forth in claim 1 wherein said attributes are defined on predetermined vectors of classes of objects, and said knowledge base includes attributes declared to be subsumed by a Boolean attribute defined on the same vector of classes and class types.

42. A knowledge engineering tool as set forth in claim 41 wherein each subsumed Boolean attribute is concluded to be definitely false when a subsuming attribute is determined to be definitely false.

43. A knowledge engineering tool as set forth in claim 41 wherein each subsumed attribute that is non-Boolean but that takes on enumerable values is concluded to be definitely not each of those values when its subsuming attribute is determined to be definitely false.

44. A knowledge engineering tool as set forth in claim 41 wherein each subsumed attribute that is non-Boolean but that takes on non-enumerable values is designated as being determined, with no conclusions being made for any of its values, when a subsuming attribute is determined to be definitely false.

45. A knowledge engineering tool as set forth in claim 41 wherein a subsuming attribute is concluded to be definitely true when a definite value is concluded for a subsumed attribute.

46. A knowledge engineering tool as set forth in claim 41 which includes means for attempting to first determine a subsuming attribute whenever an attempt is made to determine a subsumed attribute.

47. A knowledge engineering tool as set forth in claim 1 which includes means for specifying a finite set of legal values of a declared type for any attribute, and means for constraining that attribute to take on values from that set.

48. A knowledge engineering tool as set forth in claim 47 wherein said finite set of legal values is a hierarchy of values.

49. A knowledge engineering tool as set forth in claim 1 which includes means for designating selected system states as points of articulation for interruption of the built-in control procedure for execution of said control knowledge.

50. A knowledge engineering tool comprising a computer system having a stored program and memory for storing a knowledge base,

said knowledge base including control knowledge, factual knowledge and judgmental knowledge, said judgmental knowledge including judgmental rules having premises for limiting the conditions in which the rules are applicable and conclusions for indicating the actions to perform when the rules are successfully applied,

a built-in control procedure providing a base-level of control of the system, points of articulation in said built-in control procedure to allow the execution of specified portions of the control knowledge when said points are reached, and

a control program for producing system activities in accordance with said built-in control procedure and said control knowledge by interpreting and executing said built-in control procedure and said control knowledge, whereby said control knowledge can be separated from said factual knowledge and judgmental knowledge and stored as a distinct portion of the knowledge base.

51. A knowledge engineering tool as set forth in claim 50 further comprising means for permitting a user to define said points of articulation.

52. A knowledge engineering tool as set forth in claim 51 further comprising means for permitting the user to define a prescribed action sequence to be effected in response to prescribed conditions existing when said points of articulation are reached.

53. A knowledge engineering tool as set forth in claim 50 wherein said points of articulation include a point where a consultation has just begun.

54. A knowledge engineering tool as set forth in claim 50 wherein the built-in control procedure includes means for defining prescribed conditions that must exist for specified portions of the control knowledge to be executed when respective points of articulation are reached.

55. A knowledge engineering tool as set forth in claim 50 wherein said factual knowledge includes definitions of classes and said points of articulation include at least one point where an instance of class is created.

56. A knowledge engineering tool as set forth in claim 50 wherein said factual knowledge includes definitions of attributes that can take on particular values and said points of articulation include at least one point where an attribute has been determined.

57. A knowledge engineering tool as set forth in claim 50, wherein said factual knowledge includes definitions of atrributes that can take on particular values and said points of articulation include at least one point where an attribute needs to be determined.

58. A knowledge engineering tool comprising a computer having a stored program and memory for storing a knowledge base,

means for creating, editing and augmenting a knowledge base that includes control knowledge, factual knowledge and judgmental rules about a particular problem domain,

said knowledge base specifically including,

facts and rules having certainty factors,

declarations defining attributes that can take on values and respective certainty factors,

predicates for attributes responsive to their respective certainty factors,

judgmental rules concluding values for attributes,

declarations defining whether attributes are single-valued or multivalued,

declarations defining legal values for attributes,

judgmental rules having premises referring to attributes not yet determined,

means for interpreting the knowledge base to run an interactive advisory consultation with a user to advise the user on a selected aspect of said problem,

interface means with predefined commands for a user to load said knowledge base, start said consultation, end said consultation, and save the results of said consultation,

interface means for a user to ask questions and to receive responsive information, including the contents of the knowledge base, the current values of an attribute, why an attribute was determined, conclusions reached by said interpreting means, how an attribute was determined, and why a query was posed,

means for generating a record of a consultation, including an ordered list of rules applied and blocks of control knowledge invoked during the consultation,

means for determining the value and certainty factor of any atrribute,

means for invoking and chaining said rules,

means for selecting certainty factors for concluded values by combining certainty factors of attributes in the premises of said rules with the certainty factors of said rules,

means for terminating the knowledge base search for determining a single-valued attribute when a value is found with a certainty factor above a prescribed level, and for determining a multivalued attribute when all values are determined,

means for generating a query of the user for values of an attribute and for receiving values from the user in response to such a query,

means for displaying to the user conclusions of the rules applied,

means for declaring classes of objects and implicitly causing instances of a class to be created, and

a language interpreter for executing imperative procedural language and providing a corresponding interpretation for the control knowledge, whereby the control knowledge can be separated from the factual knowledge and judgmental rules and stored as a distinct portion of the knowledge base.

59. A computer operating under control of a stored program for (a) enabling a knowledge engineer to generate a knowledge base in the memory of the computer including control knowledge, factual knowledge, and judgmental rules for encoding knowledge about a particular problem domain, and for (b) interpreting the knowledge base to conduct a consultation with a user regarding a specified problem in said problem domain, said stored program including a user interface for recognizing a predefined set of control commands, a question and answer facility recognizing questions from the user and formatting responsive answers including an explanation of the basis for the answers, and an inference engine for applying said judgmental rules to determine the responsive answers to said questions and for resolving conflicting conclusions of said judgmental rules,

wherein the improvement comprises:

said knowledge base has a separate portion encoding said control knowledge separate from said factual knowledge and said judgmental rules, said control knowledge being encoded in an applicative and imperative procedural language defining a sequence of steps for conduting said consultation with the user, and further comprising language interpreter means for executing said imperative procedural language.

60. The computer as claimed in claim 59, wherein said separate portion of said knowledge base encoding said control knowledge comprises a plurality of discrete control blocks, each control block including statements in said imperative procedural language, said procedural language including separate statements to ask the user a question and obtain a responsive answer, apply a specified set of said judgmental rules, display to the user the conclusions of the rules applied, and to execute another specified control block.

61. The computer as claimed in claim 60, wherein said factual knowledge includes means for declaring at least one class of objects, said knowledge base includes means for causing distinct instances of said class to be created when the knowledge base is interpreted during a consultation, wherein said plurality of discrete control blocks includes at least one post-instantiation control block associated with said class, and wherein said procedural language interpreter comprises means for interrupting the execution of said procedural language to execute the procedural language statements in the post-instantiation control block associated with said class when an instance of said class has been created.

62. The computer as claimed in claim 60 wherein said factual knowledge includes means for defining at least one attribute capable of having a respective value, one of the judgmental rules has a premise conditioned on the value of said attribute so that said inference engine requires the value of said attribute to apply said rule, said plurality of discrete control blocks includes at least one determination control block defining a predetermined method for determining a value for said attribute, and said language interpreter includes means for interrupting execution of said procedural language to execute the procedural langauge statements in the determination control block when said inference engine applies said rule and requires the determination of a value for said attribute.

63. The computer as claimed in claim 60, wherein said factual knowledge includes means for defining at least one attribute capable of having a respective value, one of the judgmental rules concludes a value for said attribute when it is applied by said inference engine, said plurality of discrete control blocks includes a post-determination control block using the concluded value for said attribute, and said language interpreter means includes means for interrupting the execution of said procedural language to execute the procedural language statements in the post-determination control block when said judgmental rule determines a value for said attribute.

64. The computer as claimed in claim 59, wherein said factual knowledge base includes means for defining attributes capable of having respective values, and means for defining designated ones of the attributes as Boolean attributes having values from the set of values including true and false, and means for defining designated ones of the attributes as subsumed by designated respective ones of said Boolean attributes, and wherein said inference engine includes means for determining the value of an attribute by testing whether the attribute is subsumed by one of said Boolean attributes determining the value of any such Boolean attribute, and determining that the value of the subsumed attribute is known to be irrelevant when the value of such Boolean attribute is false.

65. The computer as claimed in claim 64, wherein said inference engine comprises post-determination means, operative when a value for an attribute is determined, for testing whether the attribute is subsumed by one of said Boolean attributes, and determining any such Boolean attribute to be true when the subsumed attribute is known to have a value.

66. A computer having a memory storing a predefined knowledge base including control knowledge, factual knowledge, and judgmental rules for encoding knowledge about a particular problem domain, said factual knowledge including definitions of classes of objects, attributes defining characteristics of said objects, and structures of said classes and attributes, said computer operating under control of a stored program interpreting the knowledge base to conduct a consultation with a user regarding a specified problem in said problem domain, said stored program including means for creating instances of said classes representing particular objects, a question and answer facility for recognizing questions from the user and formatting responsive answers including an explanation of the basis for the answers, and means for determining values for said attributes and said instances of said classes describing said characteristics of said particular objects, an inference engine for applying said judgmental rules to determine the responsive answers to said questions and for resolving conflicting conclusions of said judgmental rules,

wherein the improvement comprises:

said knowledge base has a separate portion encoding said control knowledge separate from said factual knowledge and said judgmental rules, said control knowledge being encoded in an imperative procedural language defining a sequence of steps for conducting said consultation with the user, and further comprising language interpreter means for executing said imperative procedural language, said separate portion of said knowledge base encoding said control knowledge comprises a plurality of discrete control blocks, each control block including statements in said imperative procedural language, said statements including separate statements to ask the user a question and obtain a responsive answer, apply a specific set of said judgmental rules, display to the user the conclusions of the rules applied, and to execute another specified control block, said plurality of control blocks including at least one post-instantiation control block associated with at least one of said classes, at least one determination control block defining a predetermined method for determining a value for at least one of said attributes being undetermined and being included in the premise of one of said judgmental rules, and at least one post-determination control block using a determined value for a determined attribute, and wherein said procedural language interpreter comprises means for interrupting the execution of said procedural language to execute the procedural language statements in the post-instantiation control block when an instance of the associated class is created, means for interrupting execution of said procedural language to execute the procedural language statements in the determination control block when said inference engine applies said judgmental rule including said undetermined attribute, and said language interpreter means includes means for interrupting the execution of said procedural language to execute the procedural language statements in the post-determination control block when said judgmental rule determines the value for said undetermined attribute.

67. The computer as claimed in claim 66, wherein said factual knowledge base includes means for defining designated ones of the attributes as Boolean attributes having values from the set of values including true and false, and means for defining designated ones of the attributes as subsumed by designated respective ones of said Boolean attributes, and wherein said inference engine includes means for determining the value of an attribute by testing whether the attribute is subsumed by one of said Boolean attributes determining the value of any such Boolean attribute, and determining that the value of the subsumed attribute is known to be irrelevant when the value of such Boolean attribute is false.

68. The computer as claimed in claim 67, wherein said inference engine comprises post-determination means, operative when a value for an attribute is determined, for testing whether the attribute is subsumed by one of said Boolean attributes, and determining any such Boolean attribute to be true when a value is known for the subsumed attribute.

69. The computer as claimed in claim 66, wherein said factual knowledge base includes means for defining at least one of said attributes as multivalued, means for defining hierarchies of legal values for said multivalued attribute, and wherein said inference engine comprises means for determining certainty factors for concluded legal values of said attribute, and said knowledge base interpreter includes means for propagating the determined certainty factors through said hierarchy of legal values.