Translation of a neural network into a rule-based expert system

• US 5,438,644 A
• Filed: 09/09/1991
• Issued: 08/01/1995
• Est. Priority Date: 09/09/1991
• Status: Expired due to Fees

• Current Assignee: University of Florida Research Foundation, Incorporated (State University System of Florida)
• Original Assignee: University of Florida (State University System of Florida)
• Inventors: Fu, Li M.
• Primary Examiner(s): Knepper, David D.
• Assistant Examiner(s): Hafiz, Tariq R.
• Application Number:
  US07/757,040
• Time in Patent Office: 1,422 Days
• Field of Search: 395/10-11, 395/13, 395/20-24, 395/27, 395/50, 395/53, 364/400, 382/14
• US Class Current: 706/12
• CPC Class Codes: G06N 3/042 Knowledge-based neural networks; Logical representations of neural networks

Abstract

A rule-based expert system is generated from a neural network. The neural network is trained in such a way as to avoid redundancy and to select input weights to the various processing elements in such a way as to nullify the input weights which have smaller absolute values. The neural network is translated into a set of rules by a heuristic search technique. Additionally, the translation distinguishes between positive and negative attributes for efficiency and can adequately explore rule size exponential with a given parameter. Both explicit and implicit knowledge of adapted neural networks are decoded and represented as if--then rules.

Claims

1. A data processing system comprising:

a neural network having an input layer of input units, and different layers of processing elements including an output layer of output processing elements and at least one hidden layer of hidden processing elements;

a translating means for translating knowledge in said neural network having an input layer of input units, and layers of processing elements including an output layer of output processing elements and at least one hidden layer of hidden processing elements, said translating means operable to translate knowledge in the outer layer and each hidden layer of the neural network into a corresponding layer set of rules, there being a corresponding layer set of rules for each of the outer layer and each hidden layer, and there being undefined hidden concepts embodied in the layer sets of rules;

a rewriting means for rewriting rules from the layer sets of rules by reformulating rules from one layer of said layers of processing elements in terms of rules of another layer of said layers of processing elements to eliminate undefined hidden concepts and thereby generate a rewritten set of rules, the rewritten set of rules comprising rules in IF-THEN form; and

a memory for receiving and storing the rewritten set of rules; and

wherein said translation means and rewriting means are operably connected to said neural network.

2. The data processing system of claim 1 wherein said neural network is a hardware network with said input units, output processing elements, and hidden processing elements all being hardware components.

3. The data processing system of claim 2 further comprising a CPU and a memory, said memory operably connected to said CPU and wherein said translating means and rewriting means are disposed in said memory.

4. The data processing system of claim 1 further comprising a CPU and a memory, said memory operably connected to said CPU and wherein said translating means, rewriting means, and neural network are disposed in said memory, and said input units, output processing elements, and hidden processing elements all being software components.

5. The data processing system of claim 1 wherein said translation means and said rewriting means are part of one or more of said output processing elements and said hidden processing elements.

6. The data processing system of claim 5 wherein said memory is within at least one of said output processing elements and said hidden processing elements.

7. The data processing system of claim 1 further comprising wherein said translating means translate by:

presenting each processing element with positive input combinations up to a limit k corresponding to positive attributes for that processing element to develop a positive attributes set PA of all combinations of at most k positive attributes, each of which confirms one of said concepts if all negative attributes are absent;

determining which of said input combinations in PA confirm one of said concepts when combined with the absense of some or no negative attributes to develop a positive attributes without negative attributes set PAN;

presenting each processing element with negative input combination up to k corresponding to negative attributes for that processing element to develop a negative attributes set NA of all combinations of at most k negative attributes each of which disconfirms one of said concepts if all positive attributes are absent; and

determining which of said input combinations in NA disconfirm one of said concepts when combined with the absence of some or no positive attributes to develop a negative attributes without positive attributes set NAP.

8. The data processing system of claim 1 further comprising means for performing an initial backpropagation to train a neural network having an input layer of input units and different layers of processing elements including an output layer having output processing elements and at least one hidden layer having hidden processing elements;

means for finding hidden processing elements within a common layer having similar patterns of information and replacing the similar pattern hidden processing elements with a single hidden processing element having information from one or more of the similar pattern hidden processing elements; and

means for performing a further backpropagation on the neural network.

9. The data processing system of claim 1 further comprising an inference engine in said memory, said inference engine and stored rules in the memory being part of a rule-based expert system.

10. The data processing system of claim 1 wherein said rewriting means rewrites such that said rewritten set of rules produce conclusions which are the same as conclusions produced by the neural network for at least 95% of a set of random samples, the set of random samples making up a portion of a problem domain corresponding to input conditions.

11. The data processing system of claim 10 wherein said portion is 10% of the problem domain.

12. A method of producing a rule-based expert system by use of a neural network having an input layer of input units and different layers of processing elements including an output layer and at least one hidden layer, the steps comprising:

translating knowledge in the output layer and each hidden layer of the neural network into a corresponding layer set of rules, there being a corresponding layer set of rules for each of the outer layer and each hidden layer, and there being undefined hidden concepts embodied in the layer sets of rules;

rewriting rules from the layer sets of rules by reformulating rules from one layer of said layers of processing elements in terms of rules of another layer of said layers of processing elements to eliminate undefined hidden concepts and thereby generate a rewritten set of rules, the rewritten set of rules comprising rules in IF-THEN form; and

storing said rewritten rule set in a memory.

13. The method of claim 12 wherein, prior to said translation step, the neural network is trained by the following substeps in order:

performing an initial backpropagation to train a neural network having an input layer of input units and different layers of processing elements including an output layer having output processing elements and at least one hidden layer having hidden processing elements;

finding hidden processing elements within a common layer having similar patterns of information and replacing the similar pattern hidden processing elements with a single hidden processing element having information from one or more of the similar pattern hidden processing elements; and

performing a further backpropagation on the neural network.

14. The method of claim 12 wherein said translation step includes the substeps of:

presenting each processing element with positive input combinations corresponding to positive attributes up to k for that processing element to develop a positive attributes set PA of all combinations of at most k positive attributes each of which confirms one of said concepts if all negative attributes are absent;

determining which of said input combinations in PA confirm one of said concepts when combined with the absence of same or no negative attributes to develop a positive attributes without negative attributes set PAN;

presenting each processing element with negative input combinations corresponding to negative attributes up to k for that processing element to develop a negative attributes set NA of all combinations of at most k negative attributes each of which disconfirms one of said concepts if all positive attributes are absent; and

determining which of said input combinations in NA disconfirm one of said concepts when combined with the absence of same or no positive attributes to develop a negative attributes without positive attributes set NAP.

15. The method of claim 14 wherein said presenting of each processing element with positive input combinations corresponding to positive attributes proceeds heuristically in that, upon finding a member of set PA having m positive attributes P₁ to P_m, m being any positive integer less than k, one or more further combinations corresponding to P₁ to P_m combined with other positive attributes are considered members of PA without such further combinations being supplied to the processing element, and wherein said presenting of each processing element with negative input combinations corresponding to negative attributes proceeds heuristically in that, upon finding a member of set NA having m negative attributes N₁ to N_m, m being any positive integer less than k, one or more further combinations corresponding to N₁ to N_m combined with other negative attributes are considered members of NA without such further combinations being supplied to the processing element.

16. The method of claim 12 wherein the rules are translated by searching for rules in each layer of processing elements starting at a hidden layer closest to the input layer and proceeding to the output layer by way of any interviewing hidden layers, and further comprising the steps of detecting implausible combinations of outputs from processing elements in one layer and using the knowledge of implausible combinations to limit the search in the next layer to be searched.

17. The method of claim 12 wherein said rewriting means rewrites such that said rewritten set of rules produce conclusions which are the same as conclusions produced by the neural network for at least 95% of a set of random samples, the set of random samples making up a portion of a problem domain corresponding to input conditions.

18. The method of claim 17 wherein said portion is 10% of the problem domain.