Table-driven Rules in Expert Systems CUC5-69-83 Alexander Pasik, \larshall Schor A.ugust 17th, 1 983 Departn1ent of Con1puter Science Columbia C niversity .\"ew York City. ~ew York 10027 Department of \lathematical Sciences IB\1 Thomas .J. 'Vatson Research Center Yorkto\vn Heights. ~ew York 10598 Abstract The structure and organization of expert systems can be usefully mod- eled after corresponding human experts. Often this modeling degrades because of insufficient expressive power in production system lan- guages. Relational table techniques provide additional abstraction ca- pabilities and are useful in extending the expressiveness of production system rules; the resulting systems can be easier to build. understand and debug because they can reflect more accurately human methods of reasoning. The number of superfluous rules is reduced by organizing much of the problem domain knowledge in relations in working mem- ory. The relational table methods also provide a tool for the interfacing of knowledge bases and databases. 1. Introduction Production Rule SyJtmu The knowledge base of many expert systems is composed of a set of production rules together with a set of working m~mory ~/ements. The inference engin~ matches the left hand side of each rule against working memory to determine which rules are satisfied. One of the satisfied rules is selected and the actions on its right hand side are performed. These actions in general alter the working memory so that on the next inference cycle, a different set of productions is satisfied. Using table-driven rules can ease the rule writing process in building expert systems. OPSS [Forgy 81 J, a high speed production system in- terpreter, lends itself well to the implementation of the relational table techniques which will be described. Elegance (and lAck of it) in Rule Writing While building an expert system. knowledge engineers attempt to encapsulate discrete pieces of knowledge into single rules. This has se- veral benefits. Human experts in a particular domain often can explain their expertise in small units. each of which is translated into a pro- duction rule. This strengthens the correspondence between human performance and the expert system. making the system easier to un- derstand and debug. Unfortunately, it is often difficult to encode a unit of knowledge into one rule. Sometimes this is inherent in the type of knowledge, but oc- casionally it is the result of the lack of certain structures in production system languages. In many procedural languages. the Case Statement is used to unify a collection of related but conditionally exclusive actions. Intuitively, production rules can be written for each condition in a desired case statement but again this does not reflect the singularity of the unit of knowledge that must be encoded. For example, if the elements of the class person were to be classified into the groups SHORT, MEOIl.JM and TALL. a case statement would express this as demonstrated in Figure 1. case person.he~qh~ of ;< 5.0) person.cateqory SHORT i> 6.0) person.cateqory:a TALL ielsel : person.cateqory :a MEDtUM endcase Figure 1. Case statement to categorize persons by height Since OPS5 does not allow conditional statements in the right hand side of rules, the case statement construct in not available. Instead. three OPS5 rules can be written to encode this prOCess. one corresponding to each clause in the case statement (see Figure 2).1 For all rules shown in this p:lper. English equivalents WIll be supplied. Thus it is not absolutely necesS:lry to understand OPSS synt:lx. .3hor:. -pe rso:,. ~ :r ~ ~ers~n ~as ~~~~n~ < and ~s ~~t ~~:~?~~l=ed, :HE~ modl~Y che ~~=s~n'5 :~~~qcry ~o :e 3H0RT. 'p shor:.-p~rsor. I person .hel~ht < 5.0 .c~t ?) f --> ~Odl:¥ <:~e-~e~sor.> *~at 5HOR"' I :'a:'':'-rers.jn: !F ~ person has ~e~;~: > a ~nd ~s ~o: Cdteqor~=ed, :H::~! ~od::·:, ::1e ~erson' S ':.3cegory ':,= ::'e 7AL.L . ., :a"l-;:erson I ~erson .he!;nc > ~.': .cae ?) <,:~e-;er3cn> I --> ~Odl~Y ·ca: !AL:I I :"'ed!:J~-pe=sor.: •. a ~erso~ hdS he~=n: ~ecween ~nd ~ and ~s noe ~3:eqorlzed, :HE~: ::'loJ~':i· o::'e ~I!rson's =at~qory:o te ~E=:·_·~. '., "'edl'.l",-pe~scn I ,person *hel:;ht I<~ ';.0 >= 3.01 teat ,I <:~e-.,erson> I --> Figure 2. Three OPS5 rules to categorize persons by height 2. Using Relational Tables in Rule Writing The Relational Table Technique Relational tables structure information into relations. Each relation is made up of a collection of tuples each of which represents a group of objects that are related to each other. For example. the relation party-()f can be defined over 2-tuples (i.e. doubles) in which the domain of one element is the set of all presidents and that of the other is the set of all political parties. One tuple in this relation can be expressed as party-()f( president = Kennedy ,party= Democrat). The complete re- lation can be expressed in a table. A small portion of the relation is shown below. President Party Reagan Republican Carter Democrat Ford Republican Nixon Republican Johnson Democrat Kennedy Democrat Eisenhower Republican Truman Democrat Roosevelt Democrat There is a natural analogy between relational table constructs and OPS5 working memory. A relation and its domains can be represented by a class and its attributes respectively, and the values of a tuple by values in a working memory element. The tuple party-()f(president= Truman, party:cDemocrat) could appear in working memory as (party-of t president Truman t party Democrat). Working Memory as Long Tum Memory Production rules are often referred to as long term memory. and work- ing memory elements are considered short term. In other words. knowledge of the problem domain resides in the rule base. whereas the state of the particular problem being solved is described in worldng memory. The relational table technique uses working memory as long term memory by encoding much of the problem domain knowledge in re- lations. Much of the inference process is then table driven according to the relations in working memory. This has the effect of decreasing the number of rules which then can more accurately reflect the proc- essing of the human expert. Rule:J Drivm by Relations Using the example of the categorization of persons by their height. the relational table technique improves the clarity of that portion of the expert system (see Figure 3). The relation beight-at would be com- posed of the the three tuples in worldng memory. The knowledge in- volved in this categorization is expressed in one simple rule. driven by the relation between heights and categories. This structure supports additional levels of abstraction allowing greater expressive power. IhelQht-cat 'low 0.0 .hlqh 5.0 .cat SHGRTI IhelQhr.-cat 'low 5.0 'hlQh 0.0 'cat MECIJMl \he~Qht-car 010· ... 6.0 .hlqh 9.0 'cat TALL) cate~crlze-helqht5: !F a person has he1~ht CH> and 15 nOt ~ateqcrlzed. ';ND 1S w1thln he1qht-c3t . THEN ",od~!~,. :~.e per~on' s ca::eqory ::0 be . lP cateqor~z~-he!;ht5 I Iperson .helqht 'ea:; 71 <:he-person> I Ihel~n:;-cat 'lo~ .hlqh > .cat l --> i",odl~i' <:ne-po:rson> .cat II Figure 3. The HEIGHT-CAT relation improves the system Table-4riVDI Anribuu Selection In OPS5. relations can be used to encode information about attributes also. For example. if one working memory element is to keep track of how many persons of each height exist. the relation and rule shown in Figure 4 could be used for the categorization. The OPS5 function substl' is used to reference the old value of the attribute of the counter. 2 At a given time, the counter element might be (counter +SHORT 27 +MEDIUM 152 +TALL 112). Each time the rule fires, a person gets categorized and one of the counter attributes gets incre- mented. 2 OPSS's substt has the rollo"'ing rorm:1t and runction. (substr WME ATII ATI2) returns the values or working memory element WME rrom the position designated by attribute A TI 1 through the position designated by allribute A TI2. Thus (substr . :'-:l..;:l:-C:lt . ::..: " ... -" ""c:a: ;-oe :..;::: --:.1:' . -- .:.1 :,.:...:~ -0::1: he:'1r.~-c"t :;'0": .J ·n::';:1 'cat ~~=eQorlze-hel~hcs: =, d ?erson has height lnd :'3 no~ c3te~or~=ed, .;NC o;~~ .2;:~F_':"' :1E: :'_'!,\l TML:', CH> 15 ~:.thLn h~!;n:-cat . :~:::!J ~cd!.::· :he person's ::a:~qcry co be <::>. ';:10 :.ncre~e;.~ ~he ~::r!=u:e 0: :he counter oy ~. ~ ~~;eqo~:=e-he~qht~ I I?erso~ .helqn~ cs> ·c~t ;) <:he-~erson> , I Icoun~erJ <:he-co~n=er> t :'el;:-.":.-ca: - ~.::,.; <~ ·h~;;h > ·c:ac <':>1 --> :::Od1:',' <;he-pe:-son> 'c"t I oo:.nc! COJ> ~suostr <:he-count~r> <0 CC>iJ ',"Odl:';- <;he-counter> ' 1 com~u-:e <:1> - 11 1 1 Figure 4. Values in tuples can be attribute names Table-driven State Transitions Another important use of this technique is the management of problem solving stages within the system. Expert systems using the Match problem-solving strategy [Newell 69] are composed of groups of rules. each group designed to solve a sub-problem within the system. When one sub-problem is solved, a transition rule fires which results in making the next set of rules active. This transition may need to be accompanied by the addition or reorganization of relevant information in working memory before the next stage begins. These transition values can be organized in a relation in working memory. An expert system designed to prepare gourmet meals would be built in terms of solving various sub-problems. The stages would include cooking the entree. appetizers and dessert as well as buying the ingre- dients and serving the meal. A relation for the organization of the transition values can reside in working memory as in Figure 5. By using this relation. transition rules between each stage all collapse to the one rule shown. i:.:rans -from s':d.rt .:':) 0'.1,/ ·:1e~d :::oney) t~:r.lns ·from cu,/ ·:0 d;pet!Ze!'s t!'leed .a-l.::grl t:r3ns ·!rom a;pt!t.lzers . ':',:) dessero; ~::eed d-l.nqrl (~~ans '(:-001 dessert ·:'0 en:ree ·:-.eec ~-l.nqr) It=ans +!rom en cree ·:'0 se~'/e -need i'!.acesl It:-ans +from se:-':e -':0 jone ·r..eed :"lone) \:~anqe-st.l<;es :F the ~o~l to solve problem ,5 ~,,~~s::ed. AND there 15 " tr"nS'Clon f:-om :0 <9> 'oIhlCh needs ",,,~e!'"!,,: . ~H::~~ re~ove :.!1e goal :'0 so ~ ve AND create 3 new qoal :0 sO!'le <9> wl:.h d pre~eq~,slte :0 ooc"ln materla1 . 'p ~h"nqe-5c3qe5 I 1;0"1 .~ame 'St3t~5 SATISFIEOI ':rans +!ro~ .co <9> +need (re:nove 1 mai(e ~Od: • na:ne <8> • ~rereq'': loS 1. ':e , ) Figure 5. The transition states in a gourmet expert system 3. Applications of the Technique In the examples presented. the relational tables were of only a few tuples. The relational table technique has a greater impact on the clarity of a system when the relations are large. An expen system to suggest travel routes using the Manhattan subway and bus systems was built at Columbia University as a project for a course in expen systems [Lerner and Cheng 83]. The system used several relational tables in- cluding one of over 500 tuples to determine intersections of the rapid transit system. Use of this techruque dramatically reduced the number of rules and succeeded in separating the true procedural knowledge from the database which described the transit map of the city. Besides the structural benefits of this method. the relational table tech- nique provides a tool that knowledge engineers can use in another emerging application: the connection of expen systems and databases [Walker 83]. As databases grow and require maintenance. analysts are hired whose responsibility it is to examine large quantities of data and make management decisions based on the information gathered and computed daily by the machines. This data analysis is performed by trained human expens. With the current expert system technology, in- telligent systems can be (and have been) built to analyze these large databases [Stolfo and Vesonder 82]. The relational table techniques can provide knowledge engineers with a tool for the manipulation of ponions of the databases in working memory. Information structured in a relational database can be' mapped into working memory elements in a natural way (one tuple results in one working memory element). The working memory elements are then used by the rule base. The relational table technique described can be used in almost any ex- pen system. Knowledge in a panicular domain is characterized by rules that solve problems. Expen systems have been constructed with a multitude of additional rules which. though syntactically separate. en- code the same knowledge as the original group of rules, varying only in the values of cenain parameters [McDermott 1982]. By building rela- tional tables in working memory consisting of related values and attri- butes. the superfluous rules can be eliminated. Benefits of these techniques include increased ease of preparation and improved read- ability. Systems are easier to maintain because the procedural know- ledge will be condensed. An erroneous result due to a portion of the system can be repaired by the inspection of one rule and a uniform table rather than relying on the complete understanding of a large number of rules that are only slightly different from each other. It has already been demonstrated that relational tables can improve expert systems in gen- eral. With the upcoming demand for expert data analysis. the impor- tance of these methods will continue to increase. References Forgy. C. L. "OPS5 User's Manual" Technical Repon. Carnegie-Mellon University, Department of Computer Science, 1981. Lerner, M. and Cheng. J. "Th~ Manhattan Mapper" Expert Systems Course Project, Columbia Uruversity. Department of Computer Sci- ence, 1983. (unpublished) McDermott. 1. "Rl: A Rule Based Configurer of Computer Systems" Artificial Intelligence, Volume 19(1), pp. 39-88, September 1982. ~ewell. A. "Heuristic Programming: Ill-structured Problems" In J. S. Aronofsky (Ed.). Progress in Operations Research. John Wiley and Sons. pp. 361-414. 1969. Stolfo. S. J. and Vesonder. G. "ACE: An Expert System Supporting Analysis and Management Decision Making" Technical Report. Columbia University. Department of Computer Science. 1982. Walker. A. "Data Bases. Expert Systems. and Prolog" Technical Report RJ 3870. IBM Research Laboratory San Jose. 1983.