Matrix controlled expert system producible from examples

• US 4,730,259 A
• Filed: 03/01/1985
• Issued: 03/08/1988
• Est. Priority Date: 03/01/1985
• Status: Expired due to Term

• Current Assignee: Stephen I. Gallant
• Original Assignee: Stephen I. Gallant
• Inventors: Gallant, Stephen I.
• Primary Examiner(s): Harkcom, Gary V.
• Application Number:
  US06/707,458
• Time in Patent Office: 1,103 Days
• Field of Search: 364/513, 364/200 MS File, 364/900 MS File, 364/300 MS File, 364/413, 364/415, 340/146.2
• US Class Current: 706/16
• CPC Class Codes: G06N 3/042 Knowledge-based neural networks; Logical representations of neural networks
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G16H 20/10 relating to drugs or medications, e.g. for ensuring correct administration to patients
• CPC Class Codes: G16H 50/20 for computer-aided diagnosis, e.g. based on medical expert systems
• CPC Class Codes: Y10S 706/903 Control
• CPC Class Codes: Y10S 706/924 Medical

Abstract

An expert system in which an inference engine is controlled by a matrix of learning coefficients and a method for generating a matrix controlled expert system from examples. The inference engine determines likely values and final determinations for resultant variables in the matrix, the variables being representative of responses or actions. The inference engine also determines an input variable which will contribute to making a final determination of a resultant variable. The matrix may be generated by training examples and/or rules and it may be modified dynamically by additional examples as the system operates.

Claims

1. An expert system for providing responses, actions or inquires in response to a set of conditions comprising:

a set of goal variables representative of said responses and said actions;

a set of variables representative of said conditions;

a matrix of learning coefficients providing a matrix value for each combination of one from a set of resultant variables and one from a set of primary variables, said set of resultant variables at least including a set of goal variables representative of said responses and said actions and said set of primary variables at least including a set of varaibles representative of said conditions;

an external interface for receiving said conditions to establish known primary variables and outputting said responses, actions or inquiries; and

an inference engine including;

means for computing likely values of said resultant variables from known primary variables in accordance with said matrix of learning coefficients,

means for determining whether said likely value is a final determination, said likely value being a final determination when said likely value would be unchanged regardless of the value of the primary variables whose values are not known;

means for determining a useful condition which will contribute to making a final determination of a resultant variable whose value has not been finally determined; and

means for causing said external interface to output responses or actions in accordance with the finally determine values of said goal variables and to output an inquiry making for said useful condition.

2. The expert system of claim 1 wherein a goal variable may also be a primary variable.

3. The expert system of claim 1 wherein said matrix of learning coefficients can be generated with examples including values for said conditions with the corresponding responses or actions which should be produced in response to said condition values.

4. The expert system of claim 1 further comprising a learning method for generating said matrix of learning coefficients from examples including values for said conditions with the corresponding responses or actions which should be produced in response to said condition values.

5. The expert system of claim 4 wherein said learning method is also used for modifying said matrix of learning coefficients in response to examples including values for said conditions with the corresponding responses or actions which should be produced in response to said condition values.

6. The expert system of claim 4 wherein said learning method generates a matrix of learning coefficients which properly computes the values of resultant variables for as many of the examples provided to it as is possible.

7. The expert system of claim 1 further comprising learning method which uses rules that must be satisfied for the resultant variables to which it applies, for generating said matrix of learning coefficients.

8. The expert system of claim 7 further comprising a rule compiler for translating rules which are input through said external interface into rules having a matrix form for use in said learning method.

9. The expert system of claim 1 wherein said primary variables may take on integer or fractional values without restriction to the interval from -1 to +1 and wherein the value of a resultant variable depends on the sign of its arithmetically computed value.

10. The expert system of claim 1 wherein said matrix of coefficients has exactly one resultant variable.

11. A method for generating and operating an expert system comprising the steps of:

inputting into said expert system a set of training examples each including values for a plurality of conditions with corresponding values for the responses or actions which should be produced in response to said condition values;

generating a matrix of learning coefficients within said expert system corresponding to said set of training examples, said matrix of learning coefficients having a matrix value for each combination of one from a set of resultant variables and one from a set of primary variables, said set of resultant variables at least including a set of variables corresponding to said responses and said actions and said set of primary variables at least including a set of variables representative of said conditions;

inputting known values for a set of conditions into said expert system; and

determining the value of a resultant variable by combining said known values for a set of conditions with the matrix values associated with said resultant variable; and

outputting responses or actions depending on the value of the corresponding resultant variable.

12. The method of claim 11 further comprising determining a useful condition whose value is unknown and requesting the value of said useful condition.

13. The method of claim 11 wherein said step of determining the value of a resultant variable is performed by summing the products formed by multiplying each of said known values by the matrix value in the matrix of learning coefficients associated with both said resultant variable and the condition corresponding to the known value.

14. The method of claim 13 further comprising determining a likelihood for a particular response or action by comparing the sum of the products of the values representative of said known conditions and the matrix values associated with both said known conditions and said particular response or action with the largest possible value of the sum of these same products computed for conditions which are not known.

15. The method of claim 13 further comprising determining a likelihood for a particular response or action by comparing the sum of the products of the likelihoods of the primary variables and the matrix value corresponding to said particular response or action in said matrix of learning coefficients to sum of the absolute values of the matrix values corresponding to said particular response or action.

16. The method of claim 11 further comprising the step of inputting a set of rules and wherein said matrix of learning coefficients is generated so that it satisfies said set of rules.

17. The method of claim 11 wherein said step of generating a matrix of learning coefficients comprises the steps of:

(a) randomly selecting one of said training examples;

(b) testing, for each resultant variable which is provided a value in said training example, matrix values in a temporary matrix of learning coefficients associated with said resultant variable to determine whether the matrix values combine with the variable values of the example to determine the proper response for the resultant variable as provided by the training example;

(c) replacing the matrix values associated with a resultant variable in said matrix of learning coefficients with the matrix values for said resultant variable from said temporary matrix of learning coefficients when said temporary matrix values have determined the correct response for a greater number of training examples than had been determined by the original matrix of learning coefficients;

(d) modifying the matrix values associated with a resultant variable in the temporary matrix of learning coefficients when said matrix values determine an incorrect response for the training example; and

(e) repeating steps a-d at least a predetermined number of times.

18. The method of claim 17 wherein step b is performed by computing the sum of the products of the variable values in said examples and their associated temporary matrix values.

19. The method of claim 17 wherein said learning method further comprises counting the number of consecutive times the temporary matrix values associated with each resultant variable arise at the correct response for the resultant variable as provided by an example.

20. The method of claim 17 wherein said step of modifying the temporary matrix comprises for each matrix value associated with a resultant variable adding to the matrix value the product of the value in the example of the resultant variable and the value in the example of the primary variable associated with the matrix value.

21. The method of claim 17 wherein said learning method further comprises the step of checking to determine whether the modified temporary matrix values associated with a resultant variable satisfy the requirements of each rule corresponding to that resultant variable.

22. The method of claim 21 wherein checking to determine whether the requirements of a rule are satisfied includes comparing the sum of the products of the modified temporary matrix values and their associated values in the rule with the sum of the modified temporary matrix values associated with each of the primary variables which are irrelevant to the rule.

23. The method of claim 21 wherein said learning method further comprises modifying the temporary matrix values associated with the resultant variable if they do not satisfy the requirements of a rule, said modification including reducing the absolute value of the modified temporary matrix values associated with primary variables which are irrelevant to the rule and adding to the remaining temporary matrix values the product of the corresponding value in the rule and the value of the resultant variable as determined by the rule.

24. An inference engine for use in an expert system controlled by a matrix of learning coefficients having a matrix value for each combination of one from a set of resultant variables and one from a set of primary variables, said set of primary variables at least including a set of input variables, said inference engine comprising:

means for calculating a likely value of a resultant variable from known values of primary variables and the matrix values associated with said resultant variable;

means for determining whether said likely value is a final determination, said likely value being a final determination when said likely value would be unchanged regardless of the value of the primary variables whose values are not known; and

means for determinig an input variable which will contribute to making a final determination of a resultant variable whose value has not been finally determined.

25. The matrix controlled inference engine of claim 24 wherein each input variable is assigned a cost number roughly corresponding to how costly it would be to obtain the value of the variable and wherein said cost number is considered by said means for determining an input variable which will contribute to making a final determination of a resultant variable.

26. The matrix controlled inference engine of claim 24 wherein said means for determining whether said likely value is a final determination comprises comparing the sum of the products of the known primary variable values and their associated matrix values with the sum of the absolute values of the matrix values of the primary variables which are not known.

27. The inference engine of claim 24 wherein said means for calculating a likely value of a resultant variable is performed by summing the products formed by multiplying each of said known values of primary variables by the matrix value in the matrix of learning coefficients associated with both said resultant variable and the primary variable corresponding to the known value.

28. A learning process for operating a general purpose computer having a knowledge base including a matrix of learning coefficients, which includes a matrix value for each combination of one of a set of resultant variables and one of a set of primary variables, to enhance said matrix, comprising the steps of:

(a) inputting a set of examples, each example including values for at least one primary variable and values for at least one resultant variable;

(b) randomly selecting one of said examples;

(c) testing, for each resultant variable which is provided a value in said example, matrix values in a temporary matrix of learning coefficients associated with said resultant variable to determine whether the matrix values combine with the primary variable values of the example to determine the proper value of said resultant variable as provided by the example;

(d) replacing the matrix values associated with a resultant variable in said matrix of learning coefficients with the matrix values for said resultant variable from said temporary matrix of learning coefficients when said temporary matrix values have determined the correct value for said resultant variable for a greater number of examples than had been correctly determined by the present matrix of learning coefficients;

(e) modifying the temporary matrix values associated with a resultant variable in the temporary matrix of learning coefficients when said temporary matrix values determine an incorrect response for the examples; and

(f) repeating steps b-e at least a predetermined number of times.

29. The learning process of claim 28 wherein step c is performed by computing the sum of the products of the primary variable values in said example and their associated temporary matrix values.

30. The learning process of claim 28 further comprising the step of counting the number of consecutive times the temporary matrix values associated with each resultant variable determine the correct response for the resultant variable as provided by an example.

31. The learning process of claim 28 wherein said step of modifying the temporary matrix comprises for each temporary matrix value associated with a resultant variable adding to the temporary matrix values the product of the value in the example of the resultant variable and the value in the example of the primary variable associated with the temporary matrix value.

32. The learning process of claim 28 further comprising the steps of inputting a set of rules and checking to determine whether the modified temporary matrix values associated with a resultant variable satisfy the requirements of each rule corresponding to said resultant variable.

33. The learning process of claim 32 wherein checking to determine whether the requirements of a rule are satisfied includes comparing the sum of the products of the modified temporary matrix values and their associated values in the rule with the sum of the modified temporary matrix values associated with each of the primary variables which are irrelevant to the rule.

34. The learning process of claim 32 further comprising the step of modifying the temporary matrix values associated with said resultant variable if they do not satisfy the requirements of a rule, said step of modifying including reducing the absolute value of the modified temporary matrix values associated with primary variables which are irrelevant to the rule and adding to the remaining temporary matrix values the product of the corresponding value in the rule and the value of the resultant variable as determined by the rule.

35. A learning process for operating a general purpose computer having a knowledge base, including a matrix of learning coefficients which includes a matrix value for each combination of one of a set of resultant variables and one of a set of primary variables to enhance said matrix comprising the steps of:

(a) providing an example including values for at least one primary variable and values for at least one resultant variable;

(b) testing, for each resultant variable which is provided a value in said example, matrix values in a temporary matrix of learning coefficients associated with said resultant variable to determine whether the matrix values combine with the primary variable values of the example to determine the proper value of said resultant variable as provided by the example;

(c) replacing the matrix values associated with a resultant variable in said matrix of learning coefficients with the matrix values for said resultant variable from said temporary matrix of learning coefficients when said temporary matrix values have determined the correct value for said resultant variable for a greater number of examples than had been correctly determined by the present matrix of learning coefficients;

(d) modifying the temporary matrix values associated with a resultant variable in the temporary matrix of learning coefficients when said temporary matrix values determine an incorrect response for the example; and

(e) repeating steps b-d at least a predetermined number of times.

36. The learning process of claim 35 wherein step b is performed by computing the sum of the products of the primary variable values in said example and their associated temporary matrix values.