Neural Logic Network Learning using Genetic Programming

1 Introduction

There has been a fair amount of interest in training neural networks using genetic programming [Golubski and Feuring, 1999]. Gaudet [1996] applied genetic programming on logic-based neural networks which basically represent standard logic (negation, conjunction and disjunction). Similarly, an adaptive logic network [Armstrong and Thomas, 1996] uses linear threshold units at the leaf node level, while the parent nodes of the network are composed of "AND" and "OR" logic units. However, neural networks can also represent nonstandard logic. A Neural Logic Network or simply Neulonet has been proposed that emulates human decision logic which are often too complex to be expressed neatly using standard logic [Teh, 1995; Tan et al., 1996].

In this paper, we begin by focusing on the integration of neulonets into a genetically programmed environment. First, we introduce the concept of neulonets and show how they can be combined to form complex decisions. We then describe a GP system for evolving neulonets, and discuss how genetic operations of crossover and mutation can be adapted to neulonet evolution. Next, we demonstrate how the system can effectively solve a classification problem and extract rules from the evolved neulonet. Finally we provide experimental results to substantiate the use of neulonets as an improvement over the use of standard logic networks in genetic programming.

2 Neural Logic Network

A Neulonet has an ordered pair of numbers associated with each node and connection (figure 1). Let ✂ be the output node and ✄ ☎ , ✄ ✝ , . . . ✄ ✟ be input nodes. Let values associated with the node ✄ ✡ be denoted by ( ☞ ✡ , ✍ ✡ ), and the weight for the connection from ✄ ✡ to ✂ be ( ✏ ✡ , ✒ ✡ ). The ordered pair for each node takes one of three values, namely, (1,0) for true, (0,1) for false and (0,0) for "don't know". (1,1) is undefined. The following activation function determines the output at ✂ :

where ✶ is the threshold, usually set to 1.

By applying equation (1) on a network in figure 2, the network behaves like an expert system rule with an OR logic operation as shown in the truth table.

We call a network in figure 2 a net rule - a rudimentary network that can be chained with other similar networks just like in a conventional rule-based expert system. The power of a net rule, however, is not limited to standard boolean logic operations. A wide range of different human logic in decision making can be represented with net rules using different sets of weights. Figure 3 shows some examples of net rules that emulate a human decision maker's behavior. Human decision processes are often too complex to be expressed neatly using standard logic. One such complexity is that human reasoning can be biased by giving different degrees of importance to different factors. A simple AND or OR operation will be inadequate in representing varying degrees of bias.

For instance, rule (4) "Priority" in figure 3 exhibits different degrees of influence on the outcome of ✂ with ✄ ☎ being the most important factor, while ✄ a0 will only be considered when all other factors are unknown, i.e. (0,0). Another example can be seen in rule (13) "Silence means consent" where Def represents the default action. If no one among ✄ ☎ , ✄ ✝ , . . . , ✄ a0 has any opinion, or if there is an equal number of persons either for or against a motion, the default action is taken. In all other cases, the majority wins. Net rules can combine to form composite net rules to achieve more complicated decisions. For instance, using the output of rule (7) "Unanimity" as the input ✁ to rule (10) "Veto", both with n set to 2, an XOR operation can be realized as shown in figure 4.

A neulonet combines the strengths of neural networks and expert systems [Tan et al., 1996]. It was proposed that a knowledge engineer could first encode his knowledge into component net rules and later use real examples to do refinement training to adjust the weights in the neulonet. Training in this case is by means of backpropagation [Teh, 1995], which will pervasively modify all weights in the network. It was shown that the neulonet's performance improves after the refinement training. However, one problem with backpropagation is that after training, the logic of the net rules may not be decipherable as the weights of the net rules have been altered. The trained net rules may not be reused easily. In view of this, a novel way of neulonet training by means of a genetic programming paradigm is now introduced.

3 Genetic Programming

Genetic programming [Koza, 1992] is an extension of the conventional genetic algorithm where instead of subjecting bit patterns to genetic evolution, the individuals in the gene population are computer programs. In the context of neulonet evolution, the problem statement may be stated as follows:

"Given a set of input nodes, a library of net rules, an output node, and a set of examples containing instances of input values together with the corresponding output decision, apply genetic programming to construct a neulonet that represents a decision logic induced from the examples".

The solution may be carried out in three steps:

1. Generate an initial population of neulonets comprising of random compositions of net rules according to the available input nodes and the output node.

1. Iteratively perform the following substeps until the termination criterion has been satisfied:
2. (a) Fire each neulonet in the population and assign it a fitness value using the fitness measure.
3. (b) Create a new population of neulonets by applying the following three operations to neulonets chosen with a probability based on fitness.
4. Reproduce an existing neulonet by copying it into the new population.
5. Create two new neulonets from two existing ones by genetically recombining chosen parts using a crossover operation applied at a randomly chosen crossover point within each neulonet.
6. Create a new neulonet from an existing one using a mutation operation at a randomly chosen mutation point.
7. The neulonet that is identified to be the best individual is designated as the solution to the problem.

For efficiency, the neulonet structure that undergoes evolution is a labeled tree implemented using a prefix-ordered, jump-table approach [Keith and Martin, 1994]. The initial population of neulonets are generated in a similar fashion as Koza's [1992] "ramped-half-and-half" generative method. We use a normalized fitness measure a0 ✙ ✁ ✩ ✄ ✆ ✞ ✛ based on the errors produced by the neulonet, ✁ , as well as the size of the neulonet, ✄ . The factor, ✞ ✠ ☛ ✫ ✩ ✧ ✌ , is used toweigh the effects of accuracy over size in the fitness measure. A higher value for ✞ places more emphasis on finding an accurate solution at the expense of the size of the neulonet.

The crossover operation involves swapping the chosen parts of two neulonets with constraints imposed on the swapping process to preserve the syntactic integrity. For instance, swapping should not leave any dangling intermediate output nodes as such nodes will not be able to receive input values during firing. Figures 5 and 6 illustrate a crossover operation on two neulonets before and after the operation.

The mutation operation involves changes to a chosen neulonet. A random mutation point is picked such that the neulonet whose root is the mutation point is replaced by another randomly generated neulonet. Figure 7 shows the effect of the mutation operation on a neulonet with the "Conformity" net rule replaced by a "Priority" net rule.

The probabilities assigned are: (i) reproduction: 15%, (ii) crossover: 80%, and (iii) mutation: 5%.

Note that the "Conformity" net rule appears redundant in the activation of a neulonet and might be deemed not to be doing anything significant in the evolutionary process. This kind of net rule is similar to an intron in biology, which is a chromosome that is never expressed and provides spacing between the genes [Angeline, 1994]. However, Levenick [1991] notes that introns are useful in genetic algorithms.

4 ProposedMethod

In [Tan et al., 1996], it was assumed that the knowledge engineer has some prior knowledge to construct a neulonet, which is later subjected to further refinement training. What if the knowledge engineer has only a set of examples without any other knowledge? One approach is to construct a neulonet with random weights and train it with the examples. The resultant neulonet is no different from an ordinary neural network, as it is difficult to interpret the logic semantics from the seemingly meaningless set of weights. Another approach is to solve a set of inequalities arising from the activation function in equation (1) [Teh, 1995]. The solution is not unique. Moreover, the process becomes more difficult with increasing number of inputs and it may not be always possible to find a set of interpretable weights to satisfy all the inequalities.

The genetic programming paradigm proposed here provides a third alternative for constructing a neulonet from examples. We shall illustrate the process using a simple example from the Space Shuttle Landing Domain [Michie, 1988].

This data set comprises 15 instances and 6 attributes. Table 8 shows each instance being classified as either to auto-land or not. To conform to the input requirements of the neulonet structure, every distinct attribute-value pair has a corresponding boolean attribute in a transformed data set. The valid values for these new attributes can either be yes, no or unknown. In our example, the 6-attribute data set transforms to a 16attribute data set of boolean values.

For a particular neulonet evolution run, a 100% accurate solution was produced in generation 5 which consisted of 8 basic net rules. Further evolution produced another 100% accurate solution in generation 11 as shown in figure 9. This solution consisted of a "Priority" rule rooted at ✄ , a "At-Least2-Yes" rule rooted at a0 , and a "Negation" rule rooted at ✁ .

5 Extracting Rules fromNeulonets

Extracting rules from neural networks has been studied by many researchers [Gallant, 1993; Gaudet, 1996; Setiono and Liu, 1996; Tan, 1997; Towell and Shavlik, 1993]. Existing work, however, basically utilizes standard logic, such as negation, conjunction and disjunction. The rules extracted are generally in the form of a decision tree equivalent to an AND/OR tree based on some classification of the example data. In our present work, the goal is to extract human decision logic from the neulonets. The extraction is in fact a straightforward process because the neulonets constructed are just a composition of net rules which by themselves fully express the human logic in use. As for the case of the Space Shuttle Landing Domain classification problem, the following net rules are easily identified from the solution in figure 9.

• ✁ : Negation(Magnitude Strong)

a0 : At-Least-Two-Yes(✁ , Sign pp, Wind tail)

✄ : Priority( a0 , Error SS, Visibility no)

In layman terms, the decision to auto-land the space shuttle is biased towards any two or more positive factors for a "pp" sign, tail wind and a magnitude that is not strong. Otherwise, the presence (absence) of an "SS" error will result in a decision to auto-land (manual-land) the shuttle. If this error is unknown, then the decision to auto-land (manual-land) depends on a negative (positive) visibility.

6 Empirical Study and Discussion

Our analysis above shows that the proposed approach of using net rules in genetic programming should perform well for data sets which encompass some form of ordered logic reasoning. This analysis will be further confirmed via experiments. In particular, we wish to verify whether using an extended set of net rules as logical units is comparable to, if not better, than merely using a limited set of net rules comprising the standard boolean logic of negation, conjunction and disjunction (rules (1), (5) and (6) of figure 3). We selected data sets commonly used and publicly available from the UC Irvine data repository [Blake and Merz, 1998]. Data sets containing discrete attribute data types were transformed to an equivalent binary data set with one attribute for each attributevalue pair in the original set. Moreover, data sets containing continuous-valued attributes were pre-processed using a Chi2 Discretizer [Liu and Motoda, 1998] prior to the transformation. For the case of data sets having three or more class values, a separate data set that performs a boolean classification for each class value was created. Table 10 summarizes the data sets used in our experiments.

The entire library of net rules given in figure 3 was used for our experiments. Each of the net rules (4) to (13), were represented by their 2- and 3-arity equivalents, while a 4-arity "2-out-of-3 Unless Overridden" rule (14) was used. As a large initial population was required to cater for a wide variety of neulonets that could be evolved, we implemented a distributed parallel GP-system on an AP-3000 Fujitsu distributed memory parallel processing system consisting of 32 nodes using a ring-type connection [Niwa and Iba, 1996].

In our experiments, we used an initial population of 10,000, each having a depth of not more than four component net rules, and allowed to evolve to a depth of not more than 17. The evolutionary process would proceed until the classification accuracy and size of the fittest individual were unchanged for the last 100 generations. The weighting factor ✞ used in the fitness measure was set to 0.99. To further simplify the best evolved neulonet, a set of eight most commonly used simplification rules were applied recursively to identify component net rules for elimination or recombination. Results for evolving the best neulonet solution from an average of 10 runs using the set of net rules versus using standard boolean logic are presented in Table 11.

6.1 Classification Accuracy

In terms of the classification accuracy, neulonet evolution provided a comparable, if not better, result than standard logic evolution in all cases. This was especially true for data sets having an ordered logic reasoning as in the case of the Shuttle Landing Domain problem, or when the classification rules encompassed a "quantification" of standard boolean logic. For example, in the Monk-2 data set, the classification rule is given by [Thrun et al., 1991] as follows:

Clearly, it would be difficult to achieve a high classification accuracy using only a composition of standard boolean logic units. However, in the case of neulonet evolution, the expressive power inherent in the set of net rules allowed for a more accurate solution tree to be evolved.

6.2 Solution Size

Due to the neulonet's ability to handle more complex decisions, net rule evolution provided more compact solutions than their standard boolean counterparts for the same classification accuracy, particularly for data sets having non-trivial classification rules. Using the best evolution runs for both empirical approaches in the Monk-2 data set, the profiles for the number of decision nodes is shown in figure 12 for accuracies between 70% to 100%. Observe that the profiles for both approaches are comparable in the case of classification accuracies of less than 90%, indicating that the classification rule learned thus far was still relatively simple. However, as the required accuracy increased, the apparent power of neulonets in deriving complex decision rules resulted in a significantly smaller solution size.

6.3 Number of Generations Required

A general drawback in net rule evolution was the longer time needed to converge to an ideal solution due to the larger size of the component net rule library. It has to be noted that the experiment conducted actually gave the standard logic an advantage in that the rule set is small (only negation and 2or 3-arity conjunctions and disjunctions), while the population sizes in both neulonet and standard logic evolution approaches were kept the same at 10,000 individuals. As a result, there were more opportunities for the small set of standard logic rules to quickly evolve to ideal individuals within the population. Thus for problems involving simpler decisions, standard logic evolution attained the required accuracy faster. However, there were cases in which neulonet evolution was faster. This was observed from the accuracy profile for the Monk-2 data set in figure 13.

For accuracies of less than 95%, standard logic evolution required slightly less generations. However, as the demand in accuracy increased, it became increasingly difficult to evolve a solution using only standard logic rules. The added advantage in expressing complex rules during neulonet evolution, on the other hand, produced a faster rate of convergence.

7 Conclusion

Genetic programming proves to be an interesting paradigm in constructing neulonets with the prescribed human logic net rules. The paradigm is also amenable to refinement training. A knowledge engineer could start by constructing neulonets based on the human expert's prior knowledge. The constructed neulonets may then be subjected to the genetic programming evolutionary process. Thus step 1 of the genetic programming solution (i.e. generation of an initial random population) may be skipped and instead, the process will start from step 2 onwards.

This new mode of neural logic network learning, whether learning from scratch or learning by refining the existing network, preserves the logic semantics understandable for general human decision making. The size of the net rule library determines the granularity of the decision steps and the processing time. A large library enhances the capability in expressing nuances among different decisions but at the expense of a longer time to converge.

Further experiments will be carried out to investigate this trade-off issue. Variants of crossover and mutation processes, and fitness measures will also be studied. A long term plan in future is to apply genetic programming on fuzzy neural logic networks [Teh, 1995]. For such networks, the values for input and output ordered pairs are real-valued between 0 and 1. Genetic programming will thus be an attempt to evolve the best fuzzy decision rules. We envision an even more exciting horizon of fuzzy neulonet learning with genetic programming.