Some techniques for minimizing and optimizing the rule base of an expert system

ABSTRACT

The construction of an expert system can be divided into two somewhat independent phases, knowledge engineering and software engineering. In the knowledge engineering phase, the heuristics and the data base for the system must be deduced through interviews with a domain expert. In the software engineering phase, a working program must be constructed. In a rule-based system this working program consists of a set of rules that embody the heuristics and data base of the expert. In the course of constructing an expert system that gives academic advice to Mathematics and Computer Science majors1 we have found some methods for structuring the rule base and for structuring the rules within the rule base that have proven to be very useful. We will discuss some of these methods. Conceptually, rules in such a system consist of if-then statements. Each rule has a single consequent and usually several general antecedents and some specific antecedents. When the goal of the system is to make determinations in its knowledge domain (for example, to give advice), it searches the rule base for a rule with an appropriate consequent. A rule fires when it is reached by such a search and all of its antecedents are true. If any antecedent is not true, the rule does not fire and the search continues. A first principle, then, in the construction of a rule base is that every possible problem configuration for the system's knowledge domain should cause some rule in the rule base to fire, i.e. the rule base should be complete. We have developed some pictorial representations, called “k-trees” and “question lattices”, that we describe elsewhere1 that help us to check the completeness of the rule base. At worst, there should be a rule that fires when there is insufficient information to make a determination. It is apparent that the order of the rules in the rule base is very important to the performance of the system. Creating the rule base is a kind of programming. It would seem that with such limited programming constructs available only simple programming techniques would be needed. This, in fact, is not the case. Performance and accuracy of the expert system depend in large part upon the organization of the rule base. Organizing the rule base is an important programming technique. There are a variety of methods for structuring the rule base that minimize the size of the final system and that cause the system to ask questions in the appropriate order. One way to decrease the size of a rule base is to use “mop-up” rules. When rules are grouped by goals there is often one consequent that appears with greater frequency than any other. All of the rules with this particular consequent can be replaced by a single rule with that consequent and set of general antecedents and no specific antecedents. This new “mop-up” rule is then placed after all of the more specific rules in the rule base. A small specific example from our expert academic advising system will illustrate the point. A student at Manhattanville College must complete a senior thesis in his or her first area (major). There are, therefore, essentially four rules involved in giving advice on the senior thesis to a senior Mathematics or Computer Science Major. The rules are: If it is fall of the senior year and a senior thesis has not been completed, the student should be advised that the thesis must be completed some time in the senior year. If it is fall of the senior year and a senior thesis has been completed (this can happen because some zealous students actually write their senior theses in the spring of their junior year), the student should be commented for the completion of the work. If it is spring of the senior year and a senior thesis has not been completed, the student should be advised that his or her senior thesis must be completed this term. If it is spring of the senior year and a senior thesis has been completed, the student should be commended for the completion of the work. Clearly, rules 2 and 4 have identical antecedents. Figure 1 shows the way these rules actually appear in the computer science section of our expert system. Notice that in the system, rules 2 and 4 have been combined in the third rule in the figure. The new rule is a “mop-up” rule for this recommendation. The new rule comes after the other two and has fewer antecedents. This rule will fire if neither of the other two do. This “mop-up” rule has saved one rule, a 25% savings. That number seems rather silly in such a small example but, in our experience, “mop-up” rules generally represent savings of between 20% and 40% in the rules of a specific grouping. Another way to reduce the size of the rule base is to notice that often entire groupings of rules are duplicated with the exception of only one or two specific antecedents. When this occurs it is possible to perform a “contraction” on the grouping of rules. This is done by replacing the property or properties that differ among the rules in the groupings by a new property that summarizes the existing properties. This new property must be added to the taxonomy. This is a simple process, however, and is a natural step in the development of an expert system. The new “summary” property is then evaluated by several rules. Once this property has been evaluated, the groupings of rules that were formerly needed can be replaced by a single grouping of the size of one of the former groupings. A savings is realized whenever fewer rules are required to instantiate the new property than were needed in the groupings that were eliminated. While potential contractions are most easily spotted when the rules are represented pictorially1, we will present an example of rules that evaluate one of these “summary” properties and indicate how this property creates a contraction that saves a large number of rules. We have a sequence of four intermediate level computer science courses that alternate through the fall and spring semesters of consecutive years. The recommendations that the advising system gives that need knowledge about those courses, therefore, would require four groupings of rules; one set for each of the possible courses under consideration. We realized that except for the specific intermediate level course involved as an antecedent, the four groupings were identical. We, therefore, defined a new property called current that represents the currently offered course. The rules that instantiate current are shown in figure 2. Notice, the last rule in figure 2 is another example of a “mop-up” rule. Here, one rule replaces four. When they are written out, each grouping of rules initially contains 21 rules. When the specific courses in the groupings are replaced by current the four groupings “contract” to one. The 5 rules in figure 2 thus replace 63 rules. Another concern is the ordering of antecedents within individual rules. This ordering effects both the efficiency of the rule base and the way in which the expert system asks questions. In general, a rule is most efficient when its most general antecedents precede its more specific antecedents. The reason for this is that there is usually no sense in checking many specific antecedents if a rule will fail to fire because a general antecedent is not satisfied. The system tries to check for the truth of antecedents in the order in which the antecedents appear in the rules. As soon as an antecedent is found to be false, the system determines that the rule will not fire and continues its search of the rule base. In order to test whether a rule fires, considerable amounts of computation may have to be done and many questions may have to be asked. If this work can be avoided simply because a general antecedent that is already instantiated (or that must be instantiated for future use) is false, then that antecedent should precede any others in the rule. If antecedents are evaluated by questions, the order of the antecedents helps to determine the order in which questions will be asked. Frequently, many of the properties in an expert system are, in some way, interrelated. Knowing the value of one of these properties often allows us to compute the values of all or some of the others by auxiliary rules in the rule base. If this is the case, we certainly wish to avoid having the system ask the user redundant questions. Moreover, we may wish to ask different users questions about the related properties in different orders. An example of such inter-related properties from the mathematics portion of our advising system are the properties of whether a student has completed calculus 1, calculus 2, and calculus 3. Since each of the preceding courses is a prerequisite for the following one in the sequence, the inter-relationships among these courses are the obvious ones. The auxiliary rules that embody these relationships are shown in figure 3. We have set up our system so that it tries to instantiate the properties call, cal2, and cal3 first by rules and then by asking questions. Looking at these rules we see that they force questions to be asked by the system in a different order depending upon whether the user is or is not a freshman. If a student is not a freshman the rules force questions to be asked first about calculus 3, then about calculus 2, and then about calculus 1. Otherwise, the questions are asked in the opposite order. These auxiliary rules force questions to be asked in the desired order and insure that redundant questions are not asked. Having said all of this, there remains the question of whether rule-base size should always be minimized. We believe the answer to this question is no. Often entire rules and antecedents in rules are redundant and can be eliminated by the kind of ordering techniques that we have described. Nevertheless, we often choose to leave these rules and/or antecedents in the rule-base as internal self-documentation. This makes the rule base much more readable and understandable. The cost in time of search must be weighed against the value of the internal documentation and seems to be justified unless system performance degrades unacceptably.

REFERENCES

• 1: Gerard Kiernan , Arnold Koltun , George Psihountas , Edward N. Scwhartz, Manhattanville College expert academic advisor—preliminary report (abstract only), Proceedings of the 15th annual conference on Computer Science, p.352, February 1987, St. Louis, Missouri, United States [doi>10.1145/322917.322976]
• 2: Kiernan, G. , Koltun, A. , Schwartz, E. "Constructing Expert Systems - Software Engineering o4 a Di##erent Kindn to appear

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Design, Performance, Theory