--- title: "CHARADE: A Rule System Learning System" authors: - "Jean-Gabriel Ganascia" doi: "" url: "https://ijcai.org/proceedings/1987/71" pdf: "https://ijcai.org/proceedings/1987/0071.pdf" venue: "Proceedings of the Tenth International Joint Conference on Artificial Intelligence" year: 1987 pages: "345-346" track: "Knowledge Acquisition" keywords: --- # CHARADE: A Rule System Learning System Jean-Gabriel Ganascia *Proceedings of the Tenth International Joint Conference on Artificial Intelligence*, pages 345-346. ## Abstract Designed for an operational prospect, the CHARADE system automatically learns consistent rule systems from a description language, a set of axioms reflecting the language semantics and a set of examples. The technique advocated below is based on a "generate and test" mechanism where the description SPace is explored from the more general to the more specific descriptions. Rules and properties to be obtained are translated into exploration procedure constraints thanks to formalization of the learning set with two Boolean lattices.The underlying theoretical framework allows to both justify the heuristics conventionnaly used similarity based-learning and to introduce global properties to be satisfied by a rule system during its construction. ## Full text ## 1. INTRODUCTION In ~ pragmat~c prospect, that of knowledge base construction and mamtenance, the global properties of the rule s1stem play a central part. They will assist the specialists at the ume of transfer of expertise to prevent errors and possibly ~orrect ~~m. Yet there is a major gap between individual rule JUXtaposition and a compl~te and efficient usable rule system. CHARADE proposes to bridge that gap. It has been designed to detect logical or statistical regularities existing in a set of exam~les and gene~~te production rule systems which, reflecnng such regulanues, can operate on commercial inference engines. The method presented is related to the "generate and test" techniques developed by Buchanan (1) and Michalski (3) the descriptio!~- space ~i~g explored from the more general t~ the more speci~c descrl:ptlons . . H?wever, instead of considering only one or~e~ng :elauon, as It ~s usually the case in learning, Vie shall dis~mgU1~h two ordenng relations, the first being hnked to the mclus10ns of subsets of the learning set the other to the logical implications on the description space. In'fact, these are two aspects of the generalisation notion, and even if they are complementary and indissociably.linked together, they cannot be reduced to one another. Each can be fonnalised with a Boolean lattice. Taking simultaneously into account these two aspects allows to translate the properties of rules and rule systems to be constructed into constraints for the exploration procedure, which considerably limits the number of vertices to be ~xplored. ~uch a fonnalisation of learning with two Boolean latnc~s esta~hshes a theoretic~ base for the learning heuristics used m classical systems and still allows the introduction of new properties. Amongst such properties, it is possible to translate the rule system semantic characteristics, as structuration and nature of rules - logical or approximate - as well as the relative re~eyanc~ ofdescriptors. Last, completeness, consistency and rmm~ahty of the rule systems obtained can be proved. After a precise demonstration of all that differenciates a rule system from a conglomerate of individual rules, we shall study the detail of techniques used to generate rule systems and see how the rule system properties can be translated into this fonnalism. ## 2. RULE SYSTEMS Modularity of production rule systems must not be deceptive. It is not enough for the rules, individually to make sense, they must also, as a whole, meet operational criteria as lack of redundancy and cycle, consistency, completeness, etc. To .insure that such criteria are verified knowledge acquisition assistance tools are built and it is to be able to rid from such verifications that we hope to create systems to learn rules from examples. However, in most cases rule learning systems are limited to the acquisition of concept description from examples and ~oun!er~ex~mples. To ~ convinced of it let us study classical similanty based learnmg system procedure: being a set of examples, E(c1)={el,e2, ... ,en} and a set of counter~ex~p~es, CE( c 1 )= { ce 1 ,ce2, ... ,cep} of a concept c1 a generalization IS looked for: gl of el,e2, ... ,en discriminating cel,ce2, ... ,cep. When gl has been found, the rule gl -+ c1 is generated. In spite of the difficulty to introduce a disjunction in the g 1 generalization, the same operation must be done for all the concepts to be learnt. Moreover, once defmed concepts c1 and c2, to define a concept c3 so that c1 &c2 -+ c3 , descriptors c1 and c2 must be introduced in the example descriptions, which means that rule chainings can be learnt only if they are predetermined and fixed. Thus, rules are isolated from one another during acquisition. Reversely, CHARADE does not refer to the notion of example or counter-example for separated concepts; it considers globally the set of examples, each of them being described by a logical formula, and explores the space of the elementary descriptors present in the examples conjunctions. Be d1 &d2& ... &dn one of those, CHARADE looks for descriptors f1, f2, ... , fp, correlated to the set of examples covered by d1&d2& ... &dn, then it generates rule d1&d2& ... &dn-+ fq, .. . , fm, eliminating amongst f1, f2, ... , fp descriptors fi, already derived from d 1 &df& . . ·&dn through the rule system. ## 3. DETECTION OF REGULARITIES It will be considered that from now on, an example is described by a descriptor conjunction. With an example E, we shall call d(E) description of E: d(E) = d 1 &d2& ... & dn Each descriptor ~ will be originally assumed to be either an atomic proposition or the negation of an atomic proposition. The latter restriction may be removed (Cf. (2)) and it may be then possible to process any form of ( <attribute><selector><value>) representation, integrating the semantical properties of attributes and selectors in the learning process. With the restrictive assumptions made above, it is now easy to carry out the elementary operation in the field of learning, that is generalization: E1 and E2 are two examples with d(E1) = a1&a2& ... & an and d(E2) = b1&b2& . . . & bm. Let us call gen(E 1, E2) the least generalization of E 1 and E2. If semantic relations between atomic descriptors present in these descriptions are not known, gen(E 1 , E 2 ) consists of the conjunction of common descriptors of E 1 and E 2 .More formally ``` gen(E1,E2) = &d such that de {~lie [l ,n] 3je [l ,m] ai=bj} Example: let us assume that: d(El) = blue eyes & tall &fair hair, d(E2) =blue eyes & slwrt & red hair It is then easy to calculate gen(E1, E2) =blue eyes ``` If now the learning set is represented by a function TR associating to each descriptor d the set of examples containing d in their description, to say that blue eyes is a generalisation of E1 and E2 is easily translated, it means thats {E 1 ,E2}~(blue eyes). The inclusion relation introduced here translates the subsumption of a set of examples under a concept, this can be expressed by a function SUB : SUB(E) = { d such that E~(d)}. The two functions TR and SUB allow to go from the description space to the learning set and from the learning set to the description space. Now, combining the two functions one can associate to a description D the set of descriptors ``` TR(SUB(D)) = { d1, d2, ... , dnl such as Vie [l,n] D::::x:lj_ and ``` thus, generate directly a production rule. The method that we advocate is based on this principle. As it does not refer to a preferential set of examples, the notion of example and counter-example become void of sense, the category of an example is only one descriptor among others. Moreover, this method generates all the logical correlations and thus allows to detect rule chainings. However, among those correlations, some are useless, others are accidental, the rest of this paper deals with the description of an exploration procedure limited to descriptions D likely to generate an interesting rule. As the following statements might be very abstract, we shall illustrate them with an example drawn from (4) and modified to meet the requirements of this presentation. This example only intends to give an intuitive content to our presentation; it consists of the description of 9 individuals described by 5 attributes each: Size, Hair colour, Eye colour, Complexion and Class: ``` el= (size=short)&(hair=fair)&(eyes=blue)&(complexion=pale)&(class=+) e2o= (si.ze=tall)&(hair=fair)&(eyes=brown)&(complexion=matt)&(class=-) e3= (size=tall)&(hair=red)&( eyes=blue )&( complexion=pale)&( class=+) e4= (size=short)&(hair=brown )&( eyes=blue )&( complexion=matt)&( class=-) e5= (size= tall)&(hair=~yes=bkie)&(complexiOII--pale)&(ciass=-) e6= (size=tall)&(hair=fair)&( eyes=blue )&( complexion=pale )&(class=+) e7= (size=tall)&(hair=brown)&(eyes=brown)&{complexion=matt)&(class=-) e8= (size=short)&(hair=fair)&(eyes=brown)&(complexion=matt)&(class=-) e9= (size=tall)&(hair=fair)&(eyes=brown)&(complexion=pale)&(ciass=-) ``` The learning set can easily be represented by function TR: TR((size=tall))=(e2 e3 e5 e6 e7 e9), TR((size=short))=(el e4 e8), 1R((hair=brown))=(e4 e5 e7), TR((hair=fair))=(el e2 e6 e8 e9), etc. Thanks to this representation the set of training instances covered by a conjunction of descriptors, for instance (size=short)&(hair=fair), is automatically given by the intersection of the set of training instances covered by each term of the conjunction. Also, for disjunction, the union of sets are sufficient. So we obtain TR{(size=short)&(hair=fair))={el e8) and TR((size=short)v(hair=fair))={el e2 e4 e6 e8 e9) Once function TR has been defined, it is very simple to obtain function SUB: SUB(E) = { d such that E~(d)}. In our example it becomes: SUB{{el e4 e8))={(size=short)), SUB((e4 e5 e7))={(hair=brown), (class=-)) etc ... In accordance with what we had announced above, we should generate, among others the following rules: size=short -+ size=short, hair= brown -+ hair= brown & class=-, and hair=brown & eyes=blue-+ hair=brown & eyes=blue & class=-. However such rules comprise many redundancies which must be eliminated. To do so the Boolean lattice structure of the set of subsets of the descriptors set is used and function IMP is created to describe the set of non trivial implications derived from a descriptor : IMP(D) = SUB(TR(D)) - U SUB(TR(D')) D'<D We have then IMP{(hair=brown)&(eyes=blue)) = 0, as SUP(TR({hair=brown))) = {(hair=brown), (class=-)), and, SUP(TR((eyes=blue))) = {(eyes=blue)) . We can also obtain: IMP((hair=brown))={(class=-)) and 1MP((eyes=blue))=0. The mathematical properties of Boolean lattices allow to simplify this formula into : IMP(D) "' SUB(TR(D)) - U IMP(D') ``` D' In other words, this theorem stipulates that if the set of examples covered by the description D&d 1 is included in the set of examples covered by D&~. then it is not necessary to study the descriptions D&d 1 &d 2 & ... as they will not tell anything new. ## 4.2. Rules systems These theorems are fundamental. They insure the technique feasability, but they are not alone. Other theorems are related to the properties of the rule system. Here, as an example, are a few of the characteristic properties of a rule system as they may be introduced in CHARADE to define the exploration procedure parameters: . . . . - Goal of the rule system: disease diagnosis, determmatton of remedy etc. - Structure of the rule system: rules that go from the symptom to the disease, from the disease to the type of problem, the remedy and the potential danger, - Minimum number of examples to be covered by a rule premise. Thanks to this coefficient it is possib~e to contr~l the ill-effects due to noise: a rule that would be venfied by a smgle example could not be generated. Thus, a parameter v is introduced so that any description D covering a number of examples smaller than v, that is such as card(TR(D))::::v, be a-priori nil for RU, and so no rule D~d could be generated. - Maximum number of descriptors present in a rule premise. - Descriptor relevance: this characteristic allows, heuristically, to eliminate a-priori rules which do not make sense. In fact, there are descriptors which, per se, have no meaning but which, in conjunction with symptom descriptors, limit their field. Thus, considering an expert system in agronomy, the optimum temperature or the level of humidity cannot lead by themselves to a conclusion. This would be absurd. Nevertheless, in conjunction with other descriptors, such as the colour of spots on the leaves, they can be favorably introduced in the rules. - Example coverage: this is the generalisation of a heuristic used by Michalski (3). It consists in stopping the exploration as soon as a number N of rules cover the examples and conclude as to the final condition. - Class partition: in the same spirit, it is possible to detennine the minimal proportion of examples in the learning set covered by a class d and a rule D~d. This allows to introduce disjunctions in the rules and at the same time to avoid having too specific rules covering one example only. - etc. All these properties give rise to a set of parameters which characterize the rule system taken as a whole and give a formal base to the various deletions made in the process of exploring the description space. Actually, one should note that all the heuristics are parameterized by the user and that the adjusment of such parameters depends as much on the properties of the system of rules to be generated as on those of the learning set. Thus, if a classification system must be created and that the number of examples is large, a high coefficient v will be introduced whereas if there is only one proptotypical example in each class, we shall necessarily have v=O. ## 5. CONCLUSION CHARADE has been implemented on Macintosh Plus. Programmed in Le\_Lisp, it was tested in several fields, from tomato pathology to first call at bridge, classification of archaeological objects and galaxy recognition. Running time is reasonable (approximately 45 minutes in the interpreted version for 43 examples and 116 Boolean descriptors) and the space explored is sufficiently limited to leave room for expectations. Moreover, as regards classification, the system returns the examples that it has not been able to classify, which allows a feed back on the description language. Also, the rule construction technique allows to take into account noise in data to generate approximate rules using certainty factors (Cf. (2)). ## References 1. Buchanan B. G., Mitchell T., Model-directed learning of production rules, in Pattern-Directed Inference Systems, Waterman D. and Hayes-Roth F. eds., Academic Press, New-York, 1978. 2. Ganascia J.-G., AGAPE et CHARADE : deux techniques d'apprentissage symbolique appliquees a Ia construction de bases de connaissance, These d'~tat, Universite Paris-Sud, May 1987. 3. Michalski R. S., A theory and methodology of inductive learning, in Machine Learning : an artificial intelligence approach , Eds. 4. R. S. Michalski, J. G. Carbonell and T. M. Mitchell, Pub. TIOGA publishing company, Palo Alto, California, 1983, pp.83-134. 5. Quinlan R. J., Learning Efficient Classification Procedure and their Application to Chess End Game, in Machine Learning : an artificial intelligence approach, Eds. R. S. Michalski, J. G. Carbonell and T. M. Mitchell, Pub. TIOGA publishing company, Palo Alto, California, 1983, pp.463-482.