GR2: A Hybrid Knowledge-based System Using General Rules

1 Motivation

The knowledge acquisition bottle-neck is a major obstruc­ tion to knowledge engineering. The technology of Artificial Neural Networks (ANNs) provides a helpful approach to get around it. However, the black-box nature of ANNs makes users reluctant to use them. An optimally organised hybrid system, which includes an ANN fulfilling automatic knowl­ edge acquisition and a Rule-based System (RBS) supporting it with a symbolic inference engine and user interface, can overcome those problems and provide richer knowledge representations and reasoning facilities than the ANN.

The central themes of hybrid system methodology in­ clude the following two considerations: (i) the optimal for­ mat of the symbolic knowledge representation and (ii) the rule extraction method which transfers the subsymbolic knowledge acquired by the ANN into the symbolic knowl­ edge format accurately, abstractly and efficiently.

This paper presents a common symbolic knowledge for­ mat- general rules- in Section 2. These are used in our hybrid knowledge-based system GR2. Section 3 introduces a novel and efficient heuristic method to extract the knowl­ edge from a trained Multilayer Perceptron. The system GR2 is outlined in Section 4, which also includes rule validation and multiple inference functions. Experiments in some arti­ ficial and real-world applications are reported in Section 5. The paper ends with a summary in the final section.

2 General Rules- an Abstract Knowledge Representation

2.1 Definitions

We address binary problems in this paper. A binary problem is defined as a triple <{0,1 }N, {0,1 }M, F >,where F is are­ lationship or a function of the N dimensional inputs to the M dimensional outputs. Knowledge of a binary problem can be represented in three formats in GR2: the training pattern set, the trained MLP and a symbolic form- the general rules.

As we are interested in the relationships between the input bits and each individual output bit, a pattern can be parti­ tioned into M sole patterns <(11, 12, .. , IN), 0 0 >, where /i (i=l..N) is the ith instantiated input bit, and the 0 0 is the oth instantiated output bit.

An MLP in this paper has one layer of hidden units. Com­ pletely weighted connections are used for any adjacent unit layers. The input, the hidden and the output layers of units are denoted as {Id, {Hh} and {0 0 } respectively, where the indices i=l..N, h=I..Q, and a=l..M respectively. The two layers of weight connections from the input to the hidden layer and from the hidden to the output layer are W 1 ={wih} and W 2= {who} respectively. An MLP can approximate the function, F, in a binary problem.

A General Rule, or a rule for short, comprises a premise part and a conclusion part, having the form

where 1g_~. <l_jS and y are instantiated boolean varia­ bles, in a form either positive or negative (headed with a-).

An a j· an instantiated input variable, is called a premise, at­ tribute or feature. a js are conjunctively related. They, an in­ stantiated output variable, is a conclusion or consequence. If y is positive, the rule is a positive rule; otherwise, the rule is a negative rule. It is notable that both a j andy are instanti­ ated binary variables, not only binary values. This form of rules is equivalent to the Hom Clause Format.

A general rule is, syntactically, a production rule. As L<N, however, the corresponding absent premises from a general rule are defined as being insignificant and thus can be ignored. A general rule represents a set of sole patterns whose outputs correspond to the conclusion of the general rule, and whose input vectors correspondingly subsume the premise part of the general rule. The set of sole patterns a rule represents is called its coverage. The fewer premises a rule has, the more general it is, and the larger its coverage is.

Comparing the three formats, the sole patterns can appear contradictory, reflecting the noisy property or uncertain ori­ gins of the given problem. The trained MLP encodes the knowledge in an implicit format and unifies contradictory training patterns by some statistical treatment. The general rule is superior to the two previous formats: it is abstract and explanatory. In addition, probability is naturally incorporat­ ed by rules which embody inherent uncertainty or incom­ plete knowledge. The generality of the representation in general rules supports multiple inference facilities to be dis­ cussed in the following subsections.

2.2 Probabilistic Rules

The rule previously mentioned is categorical whose cover­ age is assumed to be uniform. A probabilistic rule is a rule to which the uniform assumption on its coverage is not nec­ essarily held. A Confidence Factor is the additional compo­ nent of a probabilistic rule. It counts those sole patterns correctly classified or misclassified in the rule coverage:

where cr is the number of sole patterns correctly classi­ fied, and e is the number misclassified. The value range is [-1 , 1] . When the confidence factor is 1, the rule is equiva­ lent to a categorical rule. The confidence factor provides a better capability for classification under uncertainty. GR2 classifies sole patterns in two sequential procedures:

Categorical Reasoning

If an input vector is covered by a set of categorical rules which have the same conclusion, the conclusion of the rules is the class the input vector belongs to. Otherwise

Probabilistic Reasoning

If the vector is covered by a set of rules which have different conclusions, its class is decided by the conclusion of those rules whose confidence factors, when summed, are more than those of the opposite rules.

2.3 Exceptional Reasoning

GR2 usually generates both positive and negative rules for every output variable. However, as training patterns occa­ sionally appear with features not sufficiently distinct in every aspect, the rules for an output variable are provided by only either a positive or a negative form. GR2 performs Ex­ ceptional Reasoning to cope with this situation.

If there are only positive or negative rules to an output vari­ able, check the input vector by the existing rules. If it is cov­ ered by any of the rules, the class is decided by the conclusion of the rules. Otherwise, the class is the opposite of the conclusion in the existing rules.

3 Rule Extraction

Rule extraction methods are released in Black-box [Saito and Nakano, 1988] and/or Open-box (White-box) [Fu, 1994; Towell and Shavlik 1991, 1993a, 1993b] approaches. GR2 takes advantage of the synergy of both approaches. In the Open-box approach, the weights of the MLP are ex­ plored and a static linear statistical property of the MLP is obtained. In the Black-box approach, the Input/Output be­ haviour of the MLP is observed for examining the salient in­ dividual features in the context of the training pattern set. Gathering these two sorts of properties, the rule extraction algorithm generates the rules and controls the generality de­ gree of the rule set with a threshold. The details are ex­ plained in the following three subsections respectively. This method is first introduced by us in [Ma et al., 1995], and im­ proved on in this paper. This method does not require any special modification to the MLP and is effective in both in­ formation dense cases, such as most artificial binary prob­ lems, and information sparse, real-world domains.

3.1 Potential Default Set

The contributive relationship from the input units to the out­ put units of the MLP can be partially observed by the matrix L = (W 1 W 2 ) T · An element of L, Loi = twih ·who is the summed link strength, named Static Link, between the ith input unit Ii and the oth output unit 0 0 ·

Observation is isolated only to units Ii and 0 0 · IfL 0 i>O, 0 0 tends to increase its activation as Ii switches from 0 to 1, and to decrease as Ii switches from 1 to 0. However, if 0 0 's ac­ tivation is in the range [1-o, 1] and Ii is 0, where the o is the tolerance used in the MLP test (classification) stage, switch­ ing Ii will possibly not impact the classification result repre­ sented by 0 0 · Ii may be ignorable in this circumstance. Similarly, ifli is 1 and 0 0 is in the range [0, o], switching Ii may not change the 0 0 's status either. Ii may therefore be ig­ norable. The situations are reversed as Loi<O. These are summarised in Table 1.

The Potential Default Set is defined to identify the subset of an input vector which is possibly not influential on the classification result of a particular output value, based on the foregoing analysis.

Given the oth row from the matrix L, Lo={Loi}, we de­ fine two sets (Note: there is an overlap as Loi=O):

A Potential Default Set (PDS) of the input vector I, with respect to the output variable 0 0 , is

The elements of the PDS are the candidates possibly ab­ sent from the rules extracted from a sole pattern <I, 0 0 >.

Analysis of the contributive relationship from the input units to the output units is also based on two foundations: (a) the monontonicity of the sigmoid function the MLP uses for computing the activations of its units; (b) the fact that the ac­ tivations of the output units always fall within the tolerance range, either in [0, 8] or in [1-8, 1], when the input vectors in the training patterns are fed to the MLP. Note: point (a) is true for most well known MLPs; point (b) can be always sat­ isfied too, since 8 can be loosely assigned as long as all pat­ terns for test are uniquely classified by the MLP, rather than being as restricted as ~- the tolerance for MLP training.

The PDS represents a statistical property of the trained MLP. It averages to half the size of the input vectors, from empirical observations. Hence the dimensionality of the test space on the input values is reduced by up to half. However, PDS has the linear limitation.

3.2 Feature Salient Degree

Concerning all sole patterns {P 1 } with respect to an output variable 0 0 , the Feature Salient Uegree (FSD) is a matrix

where max(X) is the value of the maximal element of the matrix X. The fsd is a matrix whose jith element is

where Iii and 11d are the .ith inpu~ values respectively in the sole patterns Pi and Pj; Ob and 0 0 are the output values in­ volved in Pi and Pk. Pi, Pk I is the hamming distance be­ tween the input vectors Pi and Pk. The definition of fs~i tells: for the ith instantiated input variable of pattern Pi, the summation counts for those Pks, whose output variable and the ith input variable instantiated by different values from those in Pi. e -I Pi, P·l indicates that the fewer different input values the pair of patterns Pi and P~c have, the greater effect Pk gives to fsdji·

The FSD is a measure of the amount of information con­ veyed by the input units in the context of the training set. It represents the correlation of the changes on the input varia­ bles and an output variable, estimating the possibility of a change of the output status when the input variables are switched.

The MLP is used as a black-box in computation of the output values replacing those in the sole patterns.

3.3 Rule Extraction with PDS and FSD

There is a parameter, the FSD threshold, t, used to control the generality of the extracted rule set. t is used to decide if a set of input bits is preserved for forming premises in an ex· tracted rule. It should be within the range (0,1]. A default value 0.4 is recommended fort.

General rules are extracted from a sole pattern Pi=<l,00>, where I is an input vector (11,12,.,IN), in the fol· lowing steps. Remember: lis are instantiated variables, not only values.

Step 1. Compute PDS and FSD. (FSD is built up once for all sole patterns regarding the same output variable OJ.

that all the elements ~s are mutually exclusive, where

Step 4. Construct general rules by all pairs ('If u ek, OJ. The former, 'I' u O~c. a set of instantiated input variables, are symbolized into premises. The latter, one instantiated output variable, is symbolized into the consequence of the rule. The word "symbolize" means: if a variable is instantiated by 1, it presents by its corresponding symbol in the rule. If it is by 0, the symbol is headed with a-, the sign for negation.

The algorithm takes computation of O~Mxf>Z), where N is the input vector size, M is the output vector size, and P is the number of the training patterns (not of the sole pat· terns). Details of this are given in [Ma et al., 1995], where a comparison with other relevant work was addressed too. In fact, the computation is mostly consumed in P calls to the MLP for the output values of the sole patterns, and second­ arily most used in step 3, looking for the subsets. The gener· ality of the rule set is decided by the FSD threshold t. The higher the t, the more general the rule set is, and vice versa

4 GR2 System Architecture

The GR2 system is depicted in Figure 1. The ftrst compo­ nent, an MLP has a common architecture defined in Section 2.1. After training, the MLP will not be changed at all. The second component for Rule Extraction executes the algo­ rithm described in Section 3.3. Categorical rules are gener­ ated.

The third component is for Rule Validation. Rule valida­ tion is a process to determine if the rules perform at an ac­ ceptable accuracy rate over the training pattern set. We also include rule-base maintenance here. The Rule Validation process includes several functions:

·Computation of the confidence factors for rules by checking rules in the training pattern set (Section 2.3);

·Elimination of those rules whose confidence fac­ tor<~, the training tolerance;

· Prevention of redundancy by deleting rules more spe­ cial than any other rules;"

·Generalising rules by combination of similar rules if possible.

The fourth component, Inference by Rules, is the infer­ ence engine classifying input vectors by rules. The inference is simple because the rules are directly mapping from the in­ put space to the output space, no intermediate variables be­ ing involved. The inference process is

·. If rule A is more special than rule B, A and B must have the same consequence. The set of premises in A subsumes the set in B.

· Do exceptional reasoning if necessary. Otherwise, do reasoning by direct matching. In both cases, the follow­ ing two steps are executed:

· If the input vector is covered by categorical rules, do categorical reasoning. Otherwise,

·Do probabilistic reasoning.

There are three user interface components being imple­ mented, which are not addressed here owing to the limited space.

5 Examples

The GR2 has been successfully applied to many typical ar­ tificial binary-valued problems, such as the two or more bit AND, OR and parity problems, and to two real-world med­ ical problems. The artificial problems are always informa­ tion dense. Categorical reasoning is sufficient in those situations. Real-world domains are usually information sparse, where probabilistic reasoning and the tradeoff be­ tween generality and accuracy of the rule set are useful.

In Section 5.1, a four bit parity problem with an incom­ plete training set is presented. One of the real-world do­ mains is discussed in Section 5.2. More examples have been demonstrated in [Ma et al. , 1995].

5.1 Incomplete four Bit Parity Problem

Learning capability is assessed by the accuracy of recogni­ tion of the patterns not included in the training set. This sec­ tion shows how GR2 tackles this situation.

Given a training set with four binary inputs, named A B C D, and one binary output, named E, it includes 11 patterns instead of the complete set of 16 patterns. The included pat­ terns in the training set are assigned as a part of a four bit parity problem. All possible patterns are listed in Table 2 and the shaded columns are excluded from the training set.

After training, the MLP (size 4:3: 1), classifies all16 input vectors. The conclusions are rounded into integers, includ­ ing those patterns absent from the training set. All classifi­ cation results are also shown in Table2, where the training patterns are exactly recognised as designed and the un­ trained input vectors are classified too in the shaded col­ umns.

After the rule extraction, the General Rules extracted from this trained MLP are IF (-A, C, D) THEN (E).

The rule validation shows that all the rules are valid and the confidence degree for each rule is 1. Because each rule correctly covered some training patterns and there are no training patterns in conflict with it.

At rule test stage, the rules are applied on the patterns ab­ sent from the training set:

For input <0 1 0 0> in pattern 3, there are 4 rules cover­ ing it, concluding -E:

IF(-A, -C, -D)THEN(-E); IF(B, -C, -D)THEN(-E); IF(-A, B, -D)THEN (-E); IF(-A, B, -C)THEN(-E); For <0 0 1 0> in pattern 5, 1 rule covers it, IF (-B, C) THEN (E); For <1 0 1 0> in pattern 6, 3 rules cover it, IF (A, C, -D) THEN (E); IF (-B, C) THEN (E); IF (A, -B) THEN (E); For <1 0 0 1> in pattern 10, 3 rules cover it, IF (A, - B) THEN (E); IF (-B, D) THEN (E); IF (A, -C, D) THEN (E); IF (-B, C) THEN (E);

• For <0 0 1 1> in pattern 13, 3 rules cover it, IF (-B, D) THEN (E); IF (-A, C, D) THEN (E);

The rules are uniform at each case. All conclusions are the same as given by the MLP as expected.

5.2 Diagnosis of Acute Myocardial Infarction (Heart Attack)

The early identification of patients with acute ischaemic heart disease remains a great challenge in emergency medi­ cine. The ECG only shows diagnostic changes in about half of acute myocardial infarction (AMI) patients at presenta­ tion [Adams et al., 1993b; Stark and Vacek, 1987]. None of the available biochemical tests becomes positive until at least three hours after symptoms begin, making such meas­ urements of limited use for the early triage of patients with suspected AMI [Adams et al., 1993a]. The early diagnosis of AMI , therefore, relies on an analysis of clinical features along with ECG data. An MLP has been shown to be a good method for combining clinical and electrocardiographic data into a decision aid for the early diagnosis of AMI [Kennedy et al., 1994]. The data used in this study were de­ rived from consecutive patients attending the Accident and Emergency Department of the Royal Infirmary, Edinburgh, Scotland, with non-traumatic chest pain as the major symp­ tom. The relevant clinical and ECG data were entered onto a purpose-designed proforma at, or soon after, the patient's presentation. The study included both patients who were ad­ mitted and those who were discharged. 970 patients were re­ cruited during the study period (September to December 1993). The final diagnosis for these patients was assigned independently by a Consultant Physician, a Research Nurse and a Cardiology Registrar. This diagnosis made use of fol­ low-up ECGs, cardiac enzyme studies and other investiga­ tions as well as clinical history obtained from review of the patient's notes.

The input data items for the MLP were all derived from data available at the time of the patient's presentation. In all, 35 items were used, coded as 37 binary inputs. For the purposes of this application, the final diagnoses were collapsed into two classes termed "AMI" (Q wave AMI and non-Q wave AMI) and "not-AMI" (all other diagnoses). AMI cases were assigned as positive diagnoses, not-AMI cases as neg­ ative diagnoses. The MLP was constructed with 37:13:1 as the sizes of the inputhidden:output layers respectively. The error tolerance was Ll=0.15. Because the positive and nega­ tive patterns are unevenly distributed in the data set, 192 and 778 respectively, random divisions of the training set and test set may result in very different outcomes. The 970 pa­ tient records were divided into two data sets, 500 randomly selected as the training set, and the remaining 4 70 as the test set.

There are three performance criteria on the.data set, being used in the medical community. Sensitivity is defined as the ratio of the number of correct positive diagnoses to the number of positive outcomes. This is most important as the disease is life-threatening. Specificity is defined as the ratio of the number of correct negative diagnoses to the number of negative outcomes. This is important as treatment is ex­ pensive and can be risky. Accuracy is defined as the ratio of the number of correct diagnoses to the total number.

as the FSD threshold 't changes in the range [0.1, 1]. It is im­ portant that trading-off the values of sensitivity and specifi­ city for different medical requirements is easy to do by simply changing 't.The extracted rules are not given in this paper because of the space limit. The results on the training set (Diag. a) and the test set (Diag. b) are similar. The spe­ cificity and accuracy curves are closely correlated because the majority cases in both data sets are negative. The accu­ racy and specificity are at relatively high levels as 'tis in the range [0.1, 0.4 ]. They decline for 't in the range [0.45, 0.7] which leads to fewer rules extracted. For 't>O. 7, the specifi­ city and accuracy subsequently increase because the extract­ ed rules appear solely in positive form and exceptional reasoning is in force. The number of the rules (Diag. c) is generally reduced as 't increases. But the average length of the rules (Diag.d) does not change much.

The rule extraction processes took between 6 and 36 sec­ onds on Sun Sparc10; Rule Validation processes took 4 - 11.66 seconds; and Rule Reasoning processes on all the test set took 0.33 to 7.7 seconds.

Table 3 compares part of the experiment results on differ­ ent platforms such as MLP, GR2 and C4.5 [Quinlan, 1993], in which we believe that the poor outcome at the sensitivity by C4.5 extracted rules may be caused by our unfamiliarity with the use of C4.5 at present.

In the first column, Sen denotes Sensitivity, Spe denotes Specificity, Ace denotes Accuracy, Tra denotes Training Set, and Test denotes Test Set.

6 Conclusion and Further Work

The general rule is a format representing only important features, ignoring superfluous ones. This representation of knowledge provides the capabilities of generalisation, sim­ plicity and efficiency in knowledge engineering. It is feasi­ ble for probabilistic representation and multiple inference utilization, providing systematic robustness.

GR2 extracts knowledge from an MLP in the form of gen­ eral rules via an open-box method for obtaining the linear statistical property, and a black-box method for collecting individual feature salient properties. Generality of the ex­ tracted rule set is easily adjustable by varying the threshold of the feature salient degree.

We are expanding GR2 with more functions such as on­ line knowledge acquisition and explanation. The former guides users by giving queries sensitive to dynamic context, achieving time-labour efficiency. The latter provides a quantitative premise-conclusion causal relationship, which will be valuable information to system optimization in applications.

Acknowledgement

This research work has been supported by the Science and Engineering Research Council, UK, Grant Number GR/ J29916.