Learning Production Rules for Consultation Systems

LEARNING PRODUCTION RULES FOR CONSULTATION SYSTEMS

Sholom M. Weiss, Casimir A. Kulikowski, Department of Computer Science Rutgers University New Brunswick, N.J. 08903 and Bernard Nudel

ABSTRACT

Production rules, with associated measures of probability or confidence, play an important role in contemporary consultation systems. Procedures have been developed which learn a set of probabilistic production rules from a training sample. ~e have experimented with these methods, by deriving a set of production rules from a medical data base.

Production rules, with associated measures of probability or -confidence, play an important role in contemporary consultation systems [1,2]. A recent AI learning system has concentrated on extracting production rules from relatively noise-free data (3], whereas more traditional pattern recognition learning methods have to a large extent dealt with statistical approaches [4]. The major advantage of production rules (and a disadvantage of most statistical methods) is the readily understandable format of the production rule for the expert who is the source of knowledge and the user of consultation systems. A theme of the present work is to show that for some applications, probabilistic productions rules can be learned from a training sample. Moreover, the form of these production rules is similar to those used in a current large-scale consultation system [8]. Some of the procedures employed appear to be analogous to those an expert would use to generate rules from experimental data. A similar goal has motivated application of variable valued logic methods [9] to rule induction in pancreatic cancer.

The problem can be stated as: given a set of h binary features and samples for class C and its logical complement C', find a relatively small set of exhaustive and mutually exclusive production rules (of the type found in decision tables) and their associated probabilities. For simplicity, and to reduce dimensionality, binary features, and a single class and its complement are considered. The task of reducing the features to this form and feature extraction, has been considered separately [5].

A somewhat analogous problem has been previously investigated in the context of learning decision trees [6,7]. Our work has some similarities to version spaces [3), but we consider a set of production rules (not a single production rule) and the data may be very noisy, i.e. the same pattern often appears in both C and its complement. In our testing, the sample data was processed so that it appeared in the following form: For six features, there are 64 possible

patterns, of which 39 occurred.

Each pattern has an associated PROB, the Probability of class C given the Pattern, and FREQ, the total frequency of the pattern (among the samples).

The solution consists of finding a smaller set of production rules (with don't care conditions on the variables in addition to yes/no) such that: the set of production rules is much smaller than the number of patterns, the frequency of occurrence for

• .· j
• j
• · -:.
• 1 -2 3
• 1 -2 .)
• -1 · 3

OPTIMAL CLASSIFICATION RATE: 72.727)

CURRENT CLASSIFICATION RATE: 71.261 )

Table 2. ( 1 is a don't care)

In the order of increasing computation t i me , three procedures are described for deriving a set of production rules.

1. The features are ordered from highest to lowest in significance (this can be done in conjunction wi~h the expert). A c loseness threshold is given, for which r ules with probabilities within the t hreshold can be combined (when logically compatible). The program proceeds to combine rules, beginning with the least s ignificant feature (i.e. those patterns which differ only in the rightmost column). The procedure's criteria for combining pat terns are similar to two important reasoning criteria used by experts: sensitivity and specificity. In this case we r equire a minimum frequency and a degree o f c l oseness of probability for any pair of r ules to be combined. However, the essentia l difference with the usual procedures for combining rules and replac ing constants with variables, is that these rul es have probability measures which must be t a ken into account. These measures change our interpretation of which rules may be combinea. 1his is a relatively simple procedure that gives quick ana often good

results. For example, assume that the thresholds were set so that 2 rules could be combined either when they have probability measures within .1 of each other or when the frequency of one of them is less than .10 . In Table 1, patterns 1 and 2 could be combined because each has a small frequency. Patterns 3 and 4 could not be combined because both frequencies are above the threshold and the probability estimates differ by more than .1.

1. ~;ithout ordering the features as in (a), all possible orders (n!, where n is the number of features) are considered. This has in many instances yielded near-optimal results. Table 2 was generated using this procedure.
2. Using a search and branch ana bound technique, an optimal solution can be found for a set of n production rules. AI search techniques have recently been given more attention in pattern recognition theory [7] .

These procedures can result in a set of production rules which are understandable to the expert, include dependencies, and are competitive in performance with other statistical procedures. The requirement that the number of features included in a rule be no larger than eight is consistent with the maximum size that an expert is likely to provide. The number of the samples must increase if rules containing more findings are required. Rules of this form are compatible and can be incorporated in models developed with a new consultation system [ 8]. The examples pre~ented correspond to a form which ·,;as suggested by a physician who felt that it would be readily understandable by other physicians. ~ie are currently ;;orking on another application of much greater complexity in developing a consultation syste~ in rheumatology. ~nile this learning approach is likely to work in only small applications, it should prove interesting to see whether limited sets of ~ules could be learned and used in relatively de-coupled subsections of the consultation system.

ACKNOwLEC�EME~TS

This research ;;as supported in part by grant RR-643 of the ~In ~iotechnology Re sources Program.

RSFI::iii::NCES

1. weiss, S., KulikO'IiSki, c., h.1l3rel, s., Safir, A., A ~ :odel-based ~~t:-tod for Computer-aided ~€dical Cecision-~& ~ing, Artit'icial Intelligence, Vol. 11, p;::. 11l5-172 (1978).
2. Shortliffe, c., Computer-baseJ ~eci~ a l Consultation: MYCIN, El~evicr, 1--.Y. (1S76).

1. Mitchell, T., Version Spaces: A Candidate elimination Approach to Rule Learning, Proceedings 5th Joint Conference on Artificial Intelligence, pp. 305-310 (1977).
2. Shimura, M., Learning Procedures in Pattern Classifiers-Introduction and Survey, Proceedings 4th International Joint Conference On Pattern Recognition, pp. 125-138 (1978).
3. Weiss, S., Kern K., Kulikowski, C., Pincus, W., An Interactive System for the Design of Classifiers in Diagnostic Applications, Proceedings 1978 International Conference on Cybernetics and Society, pp.58-62.
4. Gleser, M., Collen, M., Towards Automated Medical Decisions, Computers and Biomedical Research, Vol. 5, pp. 180-189 (1972). Vol. 11, pp. 145-172 (1978).
5. Kulkarni, A. Kana!, L., Admissible Search Strategies for Parametric and Nonparametric Hierarchical classifiers, Proceedings 4th International Joint Conference on Pattern Recognition, pp. 238-245 (1978).
6. Weiss, S., Kulikowski, C., EXPERT: A System for Developing Consultation Models, Proceedings IJCAI-1979.
7. Michalski, R., AQVAL/1--Computer Implementation of a Variable-valued Logic System VL1 and Examples of its Application to Pattern Recognition, Proceedings 1st International Joint Conference on Pattern Recognition, pp. 3-17 (1973).