Learning and Generalization of Characteristic Descriptions: Evaluation Criteria and Comparative Review of Selected Methods

1. INTRODUCTION

1.1 Motivation and Basic Concepts

There are many problem areas where large volumes of data are generated about a class of objectst the behavior of a system, a process, etc. scientists in fields as diverse as agri­ culture, chemistry, and psychology are faced with tne need to analyze such data in order to detect regularities and common patterns. Trad­ itional tools for data analysis include various statistical techniques, curve-fitting tech­ niques, numerical taxonomy, etc. These methods, however, are often not satisfactory because they impose an overly restrictive mathematical framework on the scope of possible solutions. For example, statistical methods describe the data in terms of probability dis­ tribution functions placed on random variables. As a result, the types of patterns which they can discover are limited to those which can be expressed by placing constraints upon the parameters of various probability distribution functions. Because of the mathematical frame­ works upon which they are based, traditional methods cannot detect conceptual patterns sud· as the logical, causal, or functional relation­ ships that are typical of descriptions producer by humans. This is a well-known problem in AI, namely that a system in order to learn some­ thing must first be able to express it. ThP solution requires introducing more powerful representations for hypotheses and developing corresponding techniques of data analysis an~ pattern discovery. Work done in AI and related areas on computer induction and learning struc­ tural descriptions from examples has laid the groundwork for researh in this area. This is not accidental, because, as ~ichie [18) has pointed out, the development of systems which deal with problems in human conceptual terms is a fundamental characteristic of AI research.

In this paper. we examine some of the recent work in AI on the subject of learning and gen­ eralization of structural descriptions. In particular, we will review four recent methods of inductive generalization: Buchanan et. al., Hayes-Roth, Vere, and our own work (Earlier well-known work by Winston was recently re­ viewed by Knapman [11)). We also outline some goals for research in this area. Attention is given primarily to the simplest form of gen­ eralization, namely the maximally specific con­ junctive statements which characterize a single set of input events (called for short, conjunc­ tive generalizations). The reason for this choice is that most work done in this area is addressing this, quite restricted, subject. Many of tfie researchers whose work we review in this paper have done work on other aspects of machine learning including generalization using negative examples (Vere, Michalski) and developing discriminant descriptions of several classes of objects (Michalski). Due to space limitations, we have been unable to include these topics in this paper. Instead, thhese contributions are mentioned in the sections concerning. extensions. We begin the analysis by first discussing several important aspects of the problem of learning conceptual descrip­ tions:

-------------~---------- The authors gratefully acknowledge the support of NSF under grant MCS-76-22940.

• forms of descriptions
• typea of descriptions: characteristic versus discriminant
• types of generalization processes involved in generalizing descriptions (rules of gen­ eralization)
• constructive versus non-constructive in­ duction
• general versus problem-oriented methods of induction.

1.2 ~of Descriptions

We distinguish between characteristic and discriminant descriptions [16). A characteris­ tic descrijtion is a description of a single set of o6 ects (examples, events) which is in­ tended to iscriminate that set of objects from all other possible objects. For example, a characteristic description of the set of all tables would discriminate any table from all things which are non-tables. Psychologists consider this problem under the name of concept formation (e.g. Hunt [10)). Since it is impossible to examine all other possible objects, a characteristic description is usually developed by specifying all characteristics which are true for all known objects of the class (posi­ tive examples). Alternatively, in some p,rob­ lems there are available so-called 'near misses" which can be used to more precisely circumscribe the given class.

A discriminant descrigtion is a description of a single class of o jects in the context of a fixed set of other classes of objects. It states only those properties of objects in the class under consideration which are necessary to distinguish them from the objects in the other classes. A characteristic description can be viewed as a discriminant description in which the given class is discriminated a~ainst infinitely many alternative classes.

In this paper we restrict ourselves to the problem of determining characteristic descrip­ tions. The problem of determining discriminant descriptions has been studied by ~ichalski and his collaborators [13-17)).

1.3 Forms of Descriptions

Descriptions, either characteristic or discrim­ inant, may take several forms. In this paper we concentrate on generalizations in conjunc­ tive form. Other forms include disjunctions, exceptions, production rules of various types, hierarchical and multilevel descriptions, se­ mantic nets, and frames.

1.4 Generalization ~

The process of inducing a general description from examples can be viewed as a process of ap­ plying certain generalization rules to the ini­ tial descriptions to transform them into more general output descriptions. This viewpoint permits one to characterize various methods of induction by specifying the rules of generali­ zation which they use. Below is a brief review of various generalization rules based on the paper [17).

i) Drop¥ins Condition Rule. If a descrip­ tion is v ewed as a conjunction of conditions which must be satisfied, then one way to gen­ eralize it is to drop one or more of these con­ ditions. For example:

red(x) /\ big(x) I< red(x)

(this reads: "the description 'xs which are red and big' can be seneralized to the description 'xs which are red ; i< denotes-the generaliza­ tion operator)

ii) Turninf Constants to Variables Pule. If we have wo or more diicriptions, eacn-of which refers to a specific object (in a set to be characterized) we can generalize these ~Y creating one description which contains a vari­ able in place of· the specific object:

tall (Fred) 1\ man(Fred) I< Vx tall (x) 1\ man(x) tall ( Jim)l\ man (jill) I

assuming that the value set of x is {Fred, Jim, ··· }. 'x' can be interpreted as representin~ 'a person from the group under consideration.'

These first two rules of generalization are the rules most commonly used in the literature on computer induction. Both rules can, however, be viewed as special cases of the following rule.

iii) Generalizing ~ Internal nis~unction Rule. A description ~an be ~enerallze by ex­ ~in~ the set of values that a descriptor (i.e. variable, function, or predicate) is per­ mitted to take on in order that the description is satisfied. This process involves an operatioo called the internal disjunction. For ex­ ample:

shape(x,square) k shape(x,triangle)

shape(x,(square or triangle or rectangle))

where statements on the left of I< describe some single objects in a class, and the state­ ment on tne rignt is a plausible generaliza­ tion.

Using the notation of variable-valued logic system VL 71 [17) this rule can be expressed somewhat more compactly:

f shape(x)·squarel K shape(x)·triang e)

[shape(x)·square, triangle, rectangle)

The ',' in the expression on the right of the I< denotes the internal dis~unction. Although it may seem at first glance hat the internal disjunction is just a notational abbreviation, this operation appears to be one of the funda­ mental operations people use in generalizing descriptions.

In general this rule can be expressed:

where W is some condition and where Rl and R2 are sets of values linked by internal disjunc­ tion, and Pl R2.

There are two important special cases of this rule. First, When the descriptor involved takes on values which are linearly ordered (a linear descriptor) and the second when the descriptor takes on values which represent con­ cepts at various levels of generality (a struc­ tured descriptor).

In the case of a linear descriptor we have:

iv) Closing Interval Pule. For example suppose two objects of the-&8me class have ali the same characteristics except that they have different sizes, a and b. Then, it is plau­ sible to hypothesize that all objects Which share these characteristics but which have sizes between a and b are also in this class.

W fsize(xl)·a) I< W [size(x) · a ·· b) W size(x2)·b)

In the case of structured descriptors we have: v) Climbing Generalization Tree Rule. Sup­ pose the value set of the shape descriptor is the tree of concepts:

With this tree structure, values such as trian­ gle and rectangle can be generalized by climb­ ing the generalization tree:

[shape(x)·rectangle] j< [shape(x)·polygon) [shape(x)·trian~le)

1.5 Constructive Induction

~ost methods of induction produce descriptions which involve the same descriptors which were present in the initial data. These methods operate by selecting descriptors from the input data and puttin~ them into a form which is an appropriate ~eneralization. Such mPthods per­ form non-constructive induction. A method per­ forms--constructive induction if it includes mechanisms Which can ~enerate new descriptors not present in the input data. These new descriptors are ~enerated by applyin~ rules of constructive induction. Such rules may be written as procedures or as production rules and may be based on general knowledge or on problem-oriented knowledge (for examples of constructive generalization rules see [17)). Constructive induction rules can interpret the input data in terms of knowledge about the problem domain. Frequently, the solution to a problem is dependent upon finding the proper description for the problem; as in the mutilat­ ed checkerboard problem. An inductive program should contain facilities for constructive in­ duction including a library of general con­ structive induction rules. The user should be able to suggest new rules for the program to examine. In order to activate those rules which would be most useful, the program must be able to efficiently search the space of possi­ ble constructive induction rules.

Programs which perform constructive induction are more likely to find useful and interesting patterns in complex data since they have the ability to examine the data using many dif­ ferent representations.

1.6 General versus Problem-oriented Methods

It is a common view that general methods of in­ duction although mathematically elegant and theoretically applicable to many problems, are in practice very inefficient and rarely lead to any interesting solutions. This opinion seems to have lead certain workers to abandon (at least temporarily) work on general methods and concentrate on some specific problem (e.g., Buchanan, et. al. [1,2,3] or Lenat [12)). This approach often leads to interesting and practi­ cal solutions. On the other hand, it is often difficult to extract general principles of in­ duction from such problem-specific work. It is also difficult to apply such special-purpose programs to new areas.

An attractive possibility for solving this dilemma is to develop methods which incorporate various general principles of induction (in­ cluding constructive induction) together with mechanisms for using exchangeable packages of problem-specific knowledge. In this way a gen­ eral method of induction, provided with an ap­ propriate package of knowledge, could be both easily ·applicable to different problems and also efficient and practically useful. This idea underlies the development of the INDUCE programs [14,17,4].

2. COMPARATIVE REVIEW OF SELECTED ~TRODS 2.1 Evaluation Criteria

We evaluate the selected methods of induction in terms of several criteria considered espe­ cially important in view of the remarks in sec­ tion 1.

i) Adeguacy of the representation lanfuage. The language used-rD represent input da a and output generalizations determines to a large extent the ·quality and usefulness of the output descriptions. Although it is difficult to as­ sess the adequacy of a representation language out of the context of some specific problem, recent work in AI has shown that languages which treat all phenomena uniformly must sacri­ fice descriptive precision. For example, researchers who are attempting to build natural-language systems prefer the richer knowledge representations such as frames and semantic nets (with their tremendous variety of syntactic forms) to more uniform and less structured representations such as attribute­ value lists and PLANNER-style databases. In our own work on inductive learning, we have chosen to use the representation language VL 21

(see below) which has a wider variety of syn­ tactic forms than our earlier language VL · Although languages with many syntactic forms do provide greater descriptive precision, they also make the induction process more complex. In order to control this complexity, a comprom­ ise must be sought between uniformity and rich­ ness of forms. In the evaluation of each method, a review of the operators and syntactic forms of each description language is provided.

ii) Rules of generalization implemented. The generalization rules implemented in each algorithm are listed.

iii) Computational efficiency. The exact analysis of the computational efficiency of these algorithms is very difficult due both to the inherent complexity of the algorithms and to the lack of precise formulations of the al­ gorithms in available publications. ~owever, it seems useful to have some data comparing the efficiency of these algorithms even if that data is approximate and based on hand­ simulations. To get some indication of the ef­ ficiency we measure the total number of description generations or comparisons required by each method to perform a test example (see Fig. 1). We also measure the ratio of the number of output conjunctive generalizations to the total number of generalizations examined on this example. Since these numbers are derived from only one example, it is not appropriate to draw strong conclusions from them concerning the general performance of the algorithms. Our conclusions are based primarily on the general behavior of the algorithms.

iv) Flexibilitt and extensibilitt. Mere conjunctive charac erTSfic generalizat ons are not particularly useful for conceptual data analysis because of their limited format and their lack of formal mechanisms for handling errors in the input data. It is important in evaluating these algorithms to consider the ease with which each method could be extended to

a) discover descriptions with forms other than conjunctive generalizations (see section 1. 3) '

b) include mechanisms which facilitate the detection of errors in the input data,

c) provide a general facility for incorporat­ ing domain-specific knowledge into the induc­ tion process as an exchangeable package (Ideally, the domain-specific knowledge should be isolated from the general-purpose inductive process.), and

d) perform constructive induction.

It is difficult to assess the flexibility and extensibility of the algorithms presented here. We base our evaluation on the general ap­ proaches of the methods and on extensions which have already been made to them.

In the following sections, we describe each method by presenting the description language used, sketching the underlying algorithm, and evaluating the method in terms of the above criteria. Each method will be illustrated us­ ing the test example shown in Fig. 1.

2. 2 Data-driven Methods: Hayes-Roth and Vere. ~ethods can be divided into bottom-up (data­ driven), top-down (model-driven) and mixed methods. Bottom-up methods generalize the in­ put events pairwise until the final conjunctive generalization is computed:

G2 is the set of conjunctive generalizations of El and E2. Gi is the set of conjunctive gen­ eralizations obtained by taking each element of Gi-l and generalizing it with Ei.

We consider here only the methods described by Hayes-Roth and Vere. Other bottom-up methods include the candidate elimination approach described by Mitchell [19) and the Uhiclass method described by Stepp [21).

2.2.1 Hayes-Roth: Program SPROUTER [6-9)

Hayes-Roth uses the term maximal abstraction or interference match for maximally specific con­ junctive generalization. He uses parameterized structural representations (PSRs) to represent both the input events and their generaliza­ tions. For example, consider the two events described in Fig. 2:

Figure 2

The PSRs for these could be:

E1: {lcircle:a}{square:b}{small:a} small:b}{ontop:a, under:b}} E2: { circle:c}{square:d}{circle:e} small:c}{large:d}{small:e} ontop:c, under:d} inside:e, outside:d}}

The expressions such as {small:a} are case frames made up of case labels (small, circle, etc.) and parameters (a, b, c, d). The PSR can be interpreted as a conjunction of predicates of the form small(a) where the parameters are existentially quantified variables which are assumed to be distinct.

The interference match attempts to find the longest one-to-one match of parameters and case frames (i.e., the longest common subexpres­ sion). This is accomplished in two steps. First the case relations in El and E2 are matched in all possible ways to obtain the set M. Two case relations match if all of their case labels match. F~ch element of ~ is a case relation and a list of parameter correspon­ dences which permit that case relation to match in both events:

~ · {~circle:((a/c)(a/e))}{square:((b/d))} small:((a/c)(b/c)(a/e)(b/e))} ontop,under:((a/c b/d))}}

The second step involves selecting a subset of the parameter correspondences in ~ such that all parameters can be bound consistently. This is conducted by a breadth-first search of the apace of possible bindings with pruning of unpromising nodes. The search can be visual­ ized as a node-building process. Fere is one The nodes are numbered in order of generation. One at a time, a node is examined arid joined with all other consistent nodes which have al­ ready been examined. The nodes 5, ~. and 9 are conjunctive generalizations. Node 9 binds a to c (to give 1} and b to d (to give 2) to produce the conjunction:

{{circle:l}{square:2}{small:l} {ontop:1, under:2}}

The node-building process is guided by comput­ ing a utility value for each candidate node to be built. The nodes are pruned by setting an upper limit on the total number of possible nodes and pruning nodes of low utility when that limit is reached.

Evaluation:

i) Representational adequacy. The algo­ rithm discovers the following conjunctive gen­ eralizations of the example in Fig. 1:

1. {{ontop:l, under:2}{medium:l}{clear:l}} There is a medium clear object ontop of something.
2. {{ontop:1~ under:2}{medium: l}{large:2} {clear:2f} There is a medium object ontop of a large, clear object.
3. {{medium:l}{clear:1}{large:3}{clear:3} {shaded: 2}} · There is a medium sized clear object, a large sized clear object, and a shaded object.

PSRs provide two symbolic forms: parameters and case labels. The case labels can express ordi­ nary predicates and relations easily. Sym­ metric relations may be expresed by using the same label twice as in {samelsize:a, samelsize:b}. The only operator is the con­ junction. The langua~e has no disjunction or Internal disjunction. As a result, the fact that the top element in Fig. 1 is always either a square or a diamond cannot be discovered.

• ii) Rules of generalization. The method uses the dropping condition and turning con­ stants to variables rules.
• iii) Computational efficiency. On our test example, the algorithm requires 22 compar­ isons and generates 20 candidate con.1unct.ive generalizations of which 6 are retainea. This gives a figure of 6/20 or 30% for computational efficiency. Four separate interference matches are required since the first match of El and E2 produces three possible conjunctive gener aliza­ tions.
• iv) Flexibility and extensibility. Rales­ Roth has indicated (personal communicat on) that this method has been extended to produce disjunctive generalizations and to detect er­ rors in data. PAyes-Roth has applied this method to various problems in the design of the speech understanding system Hearsay II. Fowev-

er, no facility has been developed for incor­ porating domain-specific knowledge into the generalization process.

Also, no facility for constructive induction has been incorporated although ~ayes-Roth has developed a technique for converting a PSR to a lower-level finer-grained uniform PSR. This transformation permits the program to develop descriptions which involve a many-to-one bind­ ing of parameters.

2. 2. 2 Vere: Program Thoth [ 22-25]

Vere uses the term maximal conjunctive general­ ization or maximal unifying generalization to denote the maximally specific conjunctive gen­ eralization. Each event is represented as a conjunction of literals. A literal is a parenthesized list of constants called terms. For example, the objects in Fig. 2 would be described :

El: E2: (circle a)(square b)(small a)(small b) (on top a b) (circle c)(square d)(circle e) (small c)(large d)(small e) (ontop c d)(inside e d)

Although these resemble Payes-Poth's PSRs, are quite different. There are no tinguished symbols. All terms are treated formly. they dis­ uni-

The algorithm operates in four steps. First, the literals in each of the two events to be generalized are matched in all possible ways to generate the set of matching pairs ~P. Two literals match if they contain the same number of constants and they share a common term in the same position. For the example of Fig. 2,

~P· { circle a~-~circle c~~· circle a~-~circle e~~· =~!1fe!~~:-~::!f}r~ldl; ' small b - small c , small b - small e , nn~nr A h)-{ontop c d)) }

The secona slelJ utlfo.i.ve::; selecting all possible subsets of ~ duch that no single literal of one event is paired with more than one literal in another event. Fach of these subsets even­ tually forms a new generalization of the origi­ nal events.

In the third step, each subset of matching pairs selected in step 2 is extended by adding to the subset additional pairs of literals which did not previously match. A new pair p i s added to a subset S of ~ if each literal in p is related to some other pair q in S by a common constant in a common position. For ex­ ample, if S contained the pair ((square b)­ (square d)) then we could add to S the pair ((ontop a b)-(inside e d)) because the third element of (ontop a b) is the second element of (square b) and the third element of (inside e d ) is the second element of (square d) ("ere calls this a 3-2 relationship). ~e continue adding new pairs until no more can be added.

In s tep 4 the resulting set of pairs is con­ ver ted into a new conjunction of literals by merging each pair to form a single literal. Constants which do not match are turned into new constants which may be viewed as variables. For example, ((circle a)-(circle c)) would be converted to (circle I).

Evaluation:

i) Pepresentational adequacy. plied to the test example (Fig. 1) rithm produces many generalizations. t he significant ones are listed here: When ap­ this algo­ A few of

1. (ontop 1 2)(medium l)(large 2)(clear 2) (clear 3)(shaded 4)(5 4) There is a medium object on top of a large clear object. Another object is clear. There is a shaded object. (Note also the vacuous relationship 5 derived from unifying circle and triangle).
2. (ontop 1 2)(clear l)(medium 1)(9 1) (5 3 4) (shaded 3) (7 3) (6 3) (clear 4) (large 4)(8 4) There is a medium, clear object on top of some other object and there are two ob­ jects related in some way (5) such that one is shaded and the other is large and clear. (Note the vacuous relationships 6, 7, ll, and 9).
3. (ontop 1 2) (medium 1) (clear 2) (large 2) (5 2) (shaded 3)(7 3)(clear 4)(6 4) There is a medium object on top of a large clear object. There is a shaded object and there is a clear object. (Note the vacuous relationships 5, 6, and 1).

The representation is very general. By conven­ tion the first symbol of a literal can be in­ terpreted as a predicate symbol. The algo­ rithm, however, treats all constants uniformly. This creates difficulties. For instance the algorithm generates vacuous literals in certain situations. Literals can be formed by pairing (red x) with (big y) to produce meaningless generalizations. one advantage of this relaxa­ tion of semantic constraints is that the pro­ gram can discover conjunctive generalizations involving a many-to-one binding of variables.

The language contains only a conjunction opera­ tor. No disjunction or internal disjunction is included.

• ii) Rules of generalization. The algo­ rithm implements the dropping condition rule and the turning constants to variables rule.
• iii) Computational efficiency. From the published articles [22-25] it is not clear how to perform step 2. The space of possibilities is very large ·and an exhaustive search could not possibly give the computation times which Vere has published. It would be interesting to find out what heuristics are being used to guide the search.
• iv) Flexibility and extensibility. Vere has published algorithms which discover descriptions with disjunctions [24] and excep­ tions [25l. He has also developed techniques to genera ize relational production rules [23,24]. The method has been demonstrated us­ ing the traditional AI toy problems of IO anal­ ogy tests and blocks-world sequences. A facili­ ty for using background information to assist the induction process has also been developed. It uses a spreaaing activation technique to ex­ tract relevant relations from a knowledge base and add them to the input examples prior to generalizing them. Since the method has been extended to discover disjunctions and excep­ tions, it would be expected that the method could also operate in noisy environments.

2.3 Model-driven ~ethods: Buchanan £1· al., and "PicnaTs1<r:--

~del-driven methods search a set of pos sible ~eneralizations in an attempt to f i nd a few best" hypotheses which satisfy certain re­ quirements. The two methods discussed here search for a small number of conjunctions which together cover all of the input events. The search proceeds by choosing as the initial working hypothesis some starting point in the partially ordered set of all possible descriptions. If the working hypotheses satisfy cer­ tain termination criteria, then the search halts. Otherwise the current hypotheses are modified by slightly generalizing or specializ­ ing them. These new hypotheses are then checked to see if they satisfy the termination criteria. The process of modifying and check­ ing continues until the criteria are met. Top-down techniques typically have better noise immunity and can easily be extended to discover disjunctions. The principal disadvantage of these techniques is that the working hypotheses must repeatedly be checked to determine whether they subsume all of the input events.

2.3.1 ~uchanan, et. al.: Program ~eta-DENDRAL [ 1-3, 20)

The algorithm which we describe here is taken from the RULEGF.N program (part of the Meta­ DENDRAL system). Meta-nENDRAL was designed to discover cleava~e rules to explain mass spec­ trometry data. The descriptive language is based on the ball-and-stick model of chemical molecules. F~ch input event is a bond environ­ ment which describes some portion of a molecule. The environment is represented by a graph of the atoms in the molecule with four descriptors attached to each atom and forms the left hand side of a cleavage rule. The right hand side of the rule predicts a cleavage based on the existence in a molecule of the left-hand side of the rule (breakbond (**) indicates that the **bond is predicted to be broken). A typ­ ical cleavage rule (with atoms w, x, y, and z) is:

LEFT-HAND SIDE (ROND ENVIRONMENT):

Molecule graph: W **X -- y z -- Atom descriptors:

w

atom tyge

X

z

y

car on

nitrogen

carbon

carbon nhs

2

3

1

2

1

nbrs dots

2

2

2

0

0

0

0

RIGHT-HAND SIDE (CLEAVAGE PREDICTION):

·> Breakbond (**)

The algorithm chooses as its starting point the most general bond enviroment ( x ** y ) with no properties specified for either atom. During the search, this description is grown by suc­ cessively specializin~ a property of one of the atoms in the graph or by adding a new atom to the graph. After each specialization, the new grapll is checked to see if it is "better" than the parent graph from which is was derived. A daughter graph is better than its parent if it still covers at least half of the input rules (it's general enough) and still focusses on only one cleavage process (it's specific enough). The cleavage rules built by this al­ gorithm are further improved by the program PULFMOD.

Evaluation:

1. Representational adequacy. The representation was adequate for 'the specific task of developing cleavage rules. It was not intended to be a general representation for ob­ jects outside of the chemical world. The aescriptions can be viewed as conjunctions. Individual rules developed by the program can be considered to be linked by disjunction.
2. ii) Rules of generalization. The dropping condition and turning constants to variables rules are used "in reverse" during the special­ ization process. RULF.GEN does not seem to have the ability to handle an internal disjunction but RUL~OD apparently does. For example it can indicate that the type of atom is "anyt~ing except hydrogen". In similar work on nuclear

magnetic resonance (NMR)! ~i t che l l present s an example in which the va ue of nhs is listed as "greater than or equal to one" (which indicates an internal disjunction).

• iii) Computational efficiency. Because this is a problem-specific algorithm, we canno t supply comparison figures here for how this al­ gorithm would work on our test example. The current program is considered to be relatively inefficient [2).
• iv) Flexibility and extensibi lity. ~eta­ DENDRAL has been extended to handle ~ spec­ tra. The program works well in an errorful environment. It uses domain-specific knowledFe extensively. However, there is no strict separation between a general-purpose induction component and a special-purpose knowledge com­ ponent. It is not clear whether the methods developed for Meta-DENDRAL could be easily ap­ plied to an~ non-chemical domain. The program does not perform constructive induction in any general way. However, the INTSI~ program does perform sophisticated transformations on t he input spectra in order to develop the bond­ environment descriptions.

2.3.2 Michalski and Dietterich: Program INDUCE 1.2

The algorithm described here is one of three algorithms designed by ~ichalski and his colla­ borators. The others are a data-driven method described by Stepp [21) and a mixed method described by Larson and ~ichalski [13, 14). The language used to describe the input events i s vt 21 , an extension to first-order predicate logic (FOPL) [ 17). F.ach event is represented as a conjunction of selectors. A selector typ­ ically contains a function or predicate descriptor (with variables as arguments) and a list of values that the descriptor may assume. The selector [size(x1)·small 1 medium) asserts that the size of x1 may take the val ues sma l l or medium. The events in Fig. 2 are represent­ ed as:

E1: fsize(x1)·small) [size(x2)·small) shape (x1) ·circle) [shape (x2) ·square ) ontop(xl,x2))

f E2: size(x1)·small] [size(x2)·large] size(x3)·small] [shape(x1)·circle ) [shape (x2) ·square] [shape (x3) ·ci rcle) [ontop(x1,x2))[inside(x3,x2) )

In this method, descriptors are divided i nto two classes: attribute descriptors and structure-specifying descriptors. Attribut e descriptors describe attributes such as size or shape or distance which are applicable to al l variables (representing, e.g., object parts) . Structure-specifying descriptors Include all other descriptors. They typically represent relationships among variables such as ontop or inside. Each input conjunction is broken i nto two conjuncts--one built of selectors contain­ ing only attribute descriptors (the attribute conjunct) and one built of selectors containing only structure-specifying descriptors (the structure conjunct).

The algorithm is based on the observation tha t the structure-specifying descriptors are responsible for the computational complexity of generalizing structural descriptions. If we could determine conjunctions of structure­ specifying selectors which were relevant fo r describing a particular class of obj~cts, then the generalization of the attribute con1uncts could be handled quickly bv an appropriate cov­ ering algorithm. The algorithm seeks to deter­ mine such a set of structure conjuncts which appear likely to be part of a maximall~ specif­ ic conjunctive generalization of all of the input events. It does this by finding conjunc­ tions which are maximally specific generaliza­ tions of the input structure conjuncts con­ sidered alone. Such conjunctive generaliza­ tions of the structure conjuncts must be con­ tained in some maximally specific generaliza­ tions of the entire set of input events. Pow­ ever, there may be maximally specific conjunc­ tive generalizations of the input events Which contain few if any structure-specifying selec­ tors. This algorithm also finds these general­ izations by considering structure conjuncts which are less than maximally specific.

The algorithm operates in two phases. The first phase is the structure-determining phase. A random sample of the input structure con­ juncts is taken. This sample becomes the ini­ tial set of generalizations G 0 · In each step, G 1 is first pruned to a fixed size by removing unpromising generalizations. Then G is checked to see if any of its generaliz~tions covers all of the structure conjuncts. If any do, they are removed from C- and placed in the set C of candidate con1uncti~e generalizations. Lastly, Gi is generalized to form Gi+l by tak­ ing each element of G and generalizing it in all possible ways by aropping single selectors. When the set of candidates C reaches a prespecified size, the search stops.

The second . phase is the attribute-determining phase. In this phase the problem is converted to a multiple-valued logic covering problem us­ ing the VL1 propositional calculus [15,16]. Each candidate cover A in C is matched against all input events and the relevant variables are identified. For each match, the appropriate attribute conjuncts are extracted and used to form a vt 1 event. For example,

~1 ·Afo~tJ~(~~~~~5J1~~~o~(~2 p3)] size(p1)·1] [size(p2)·3f [size(p3)·5] [color (p 1) ·red] [color(p2) ·green] [color(p3)·blue]

then we get two vt 1 events:

V1· (1, 3, red, green) and V2· (3, 5, green, blue).

These are vectors of attributes which correspond here to the descriptors:

(size(p1), size(p2), color(p1), color(p2)) for p1 and p2 in A.

All input events are converted into VL 1 events in this manner. In general more than one VL 1 event is created from each fnput event. The set of VL 1 events can be covered using a cover­ ing algorithm. A cover could be obtained by forming the union of the values taken on by each VL 1 attribute. Such an approach usually leads co overgeneralization since only one VL 1 event derived from each input event need be covered. We use a beam-search technique to select a subset of the vt 1 events to be covered.

This two-phase algorithm provides two computa­ tional advantages. First, the time required to compare expressions in the structure­ determining phase is reduced because the struc­ ture conjuncts are usually much smaller than the full input conjuncts. Second, the manipu­ lation of VL 1 formulas is very easy since they may be represented as bit strings and manipu­ lated using fast bit-parallel operations. The chief disadvantage of this algorithm is that it is difficult to decide when to terminate the structure-determining phase.

• Evaluation:

i) Representational adequacy. The algoithm discovers, among others, the following generalizations of the events in Fig. 1:

• 1.1ontop(pl p2)] [size(pl)-medium] shape(plj·circle,square,rectangle] size(p2)·large] shape(p2)·box 1 rectangle,ellipse] texture(p2)·c ear] There is a medium-sized circle, rectangle or square on top of a large, clear box, rectangle, or ellipse.
• ~ontop(p1 p2)l[size(pl)-medium] shape(pl~-po ygon] ftexture(p1)·clear] size(p2)-medium,large shape(p2)·rectangle circle] There is a clear, medium-sized polygon on top of a medium or large circle or rec­ tangle.
• ~ontop(p1tp2)l[size(pl)-medium] shape(plJ·po ygon] size(p2)-medium,large] shape(p2)·rectangle,ellipse,circle] There is a medium-sized polrgon on top of a large or medium rectang e, ellipse or circle.
• fsize(pl)·small medium] shape(pl)·circle,rectangle] [texture(pl)·shadedl There is a shaded object which is either medium or small in size and has a circu­ lar or rectangular shape.

This algorithm implements the conjunction, dis­ _1unction and internal disjunction operators. lt provides a fairly non-uniform set of representational facilities. Descriptors, variables, and values are all distinguished. nescriptors are further analyzed into structure-specifying descriptors and attribute descriptors. The current method provides for descriptors which have unordered, linearly or­ dered, and tree ordered value sets. This variety of possible representations permits a better "fit" between the description language and any specific problem.

• ii) Pules of generalization. The algo­ rithm uses all rules mentioned in section 1.4 and also a few constructive induction rules (see below). All constants are coded as vari­ ables. The effect of the turning-constants to variables rule is achieved as a special case of the generalization by internal disjunction rule.
• iii) Computational efficiency. The algo­ rithm requires 28 comparisons and builds 13 rules during the search to develop the descrip­ tions listed above. Four rules are retained so this gives an efficiency ratio of 4/13 or 30%.
• iv) Flexibility and extensibility. The al­ gorithm can easily discover disjunctions by altering the termination criteria for the structure-determining phase to accept structure conjuncts which do not necessarily cover all of the input events. The same general two-phase approach can also be applied to problems of determining discriminant generalizations. Lar­ son and Michalski have done work on determining discriminant classification rules [13,14,15].

The algorithm has good noise immunity. Noise events can be. discovered because the algorithm tends to place them in separate terms of a dis­ junction.

Domain-specific knowledge can be incorporated into the program by defining the domains of descriptors, specifying the structures of these domains, specifying certain simple production rules. and by providing constructive induction rules. These forms of knowledge representation are not always convenient, however. Further work shoula provide other facilities for knowledge representation.

A few simple constructive induction rules have been incorporated into the current implementa­ tion as a preprocessor. Other constructive in­ duction rules can be specified by the user. Using the built-in constructive induction rules the program produces the following con­ junctive generalization of the input events in tig. 1:

I # p's with texture clear·2] [top-most(p1)] ontop(p1 p2)l[size(p1)-medium] shape(p1~·po ygon] [texture(p1)·clear] size(p2)-medium,large] [shape(p2)·circle,rectangle] There are exactly two clear objects in each event. The top most object is a medium sized, clear polygon and it is on top of a large or medium sized . circle or rectangle.

We hope to expand this constructive induction facility in the future.

2.4 Summary

The comparison of various methods is summarized in Fig. 3. The table shows the distinct advan­ tages and disadvantages of top-down methods as opposed to bottom-up methods. Bottom-up methods tend to be faster but noise immunity and flexi­ bility suffer as a consequence. Top-down methoas have good noise immunity and are easily modified to discover disjunctive and other forms of generalization. Tfiey do tend to be computationally more expensive. By separating the structure-determining phase from the attribute-determining phase in our method, a considerable speed-up has been achieved.

3.-0 CONCLUSION

One of the problems of current research on in­ duction is that each research group is using a different formal language and terminology. This makes the exchange of information diffi­ cult. This paper was intended to help readers get a better understanding of the state of the art in this area.

Some important problems to be addressed in fu­ ture research include:

1. the development of adequate formal languages and knowledge representations for hy­ pothesis formulation and modification;
2. ii) extension of the scopes of operators and forms which an inductive program can effi­ ciently use during hypothesis formulation;
3. iii) the development of general mechanisms of induction which can be guided by problem­ specific packets of knowledge; and
4. iv) incorporation in the program of exten­ sive facilities for constructive induction and multi-level schemes of description. In partic­ ular, an inductive program should be able to assign names to various subdescriptions and use these names in the formulation of hypotheses (i.e. generate hierarchical forms).

Finally, an important principle which should guide future research is what we call the pii¥­ ~ of comrrehensibility. This princ p e stites -chat he descriptions which an AI pro­ gram uses and the concepts which it generates should be easily comprehensible by people. In the context of work on induction, the comprehensibility principle requires that the descriptions be short and use operators which can be easily interpreted in natural language. Furthermore systems should be desi~ned to pro­ vide flexible interactive facilities. This ap­ proach has been adopted in our work because we expect that the most significant applications of AI inductive programs will be as interactive tools for conceptual data analysis.

4. REFERENCES

[1] Buchanan B. G., E. A. Feigenbaum J. Lederberg, "A Heuristic Programming Study of Theory Formation in Science," in Proc. IJCAI-2, 1971, PP· 40-4!1.

[2] Buchanan, B.G., D. H. Smith, W. C. White, R. J. Gritter, E. A. Feigenbaum, J. Lederberg, c. Djerassi, J. Am. Chern. Soc. 9~ (1976) p. 6lfi~. - - -- --

(3] Buchanan, B. G., E. A. Feigenbaum "Den­ dral and ~eta-Dendral, Their Applications Di­ mension," Artif. Intell. 11 (1978) PP· 5-24.

[4] Dietterich, T., "User's Guide for IN­ DUCE!. 1," internal report, Dept. of Comp. Sci., Univ. of Illnois, Urbana.

[ 5] Diet terich Thomas G., "A Comparison of ~ethod s for l:haracterist ic Generalization," Dept. of Comp. Sci., Univ. of Ill. Rept. UIUC-DCS-7~-950. Dec. 197~.

[6] Hayes-Roth F., "Collected Papers on the Learning and Recognition of Structured Pat­ terns", Dept. of Comp. Sci., Carnegie-~ellon Univ., Jan. 1975.

[7] Payes-Roth, F., "Patterns of Induction and Associated Jl'nowledge Acquisition Algorithms," Dept. of Comp. Sci., Carnegie-Mellon Univ., May 1976.

[R] Payes-Roth, F. J. !ofcDermott, "Knowledge Acquisition from Structure Descriptions", In Proc. IJCAI-5, 1977, PP· 356-362.

[9] Payes-Foth, F., J. McDermott, "An In­ terference Matching Technique for Inducing Abstractions", CACM' 21:5, 197R, PP· 401-410.

[10] Hunt, E.B. 1 Experiments Academic Press, 1 <166. in Induction,

[11] Jl'napman, John, "A Critical Review of Winston's Learning Structural Descriptions from Examples," AISJI Ouarterly Issue 31, September 197R, PP· mzn.

[ 12] Lenat, D., "~: An artificial intelligence approach to discovery in mathematics as heuris­ tic search," Comp. Sci. Dept.! Rept. STAN-CS76-570, Stanford Univ., July 976.

[13] Larson, J., and R.S. ~ichalski, "Inductive Inference of VL Decision Rules," SIGART Newsletter, June 1977, pp. 3R-44. ------

[14] Larson, J., 'Inductive Inference in the Variable Valued Predicate Logic System VL21 : ~ethodology and Computer Implementation't Rept. No. 869, Dept. of Comp. Sci., Univ. or Ill., Urbana, ~ay 1977.

[15] Michalski, R. S., "Variable-valued logic and its application to pattern recognition and machine learning," In Co(JP· Sci. and ~ultiple­ Valued Lo~B1' ed. D. · Rlne, ~orth-Po11and, ~PP· -534.

[16] fo'ichalski, R.S., "Toward Computer-aided Induction: a brief review of Currently Imple­ mented AOVAL programs," In Proc. IJCAI-5, 1977.

[17] fo'ichalski, P.S. "Pattern Recognition as fl'nowledge-r.uided Indue t ion," Pept. 927 1 nept. of Comp. Sci.,· llniv. of Ill. TTrbana, lOtfl.

[ 1 ~] Michie, n., "New Face of AI," Fxperimental Programming Pepts.: 't-lo. 33, M'IRll, ITniv. of Edinburgh, 1977.

[19] Mitch.ell T. M., "Version Spaces: A Candi­ date Elimination Approach to Pule Learning," In Proc. IJCAI-5, MIT, 1977.

h20] Schwenzer, G. M., T. M. Mitchell, Computer-assisted Structure Elucidation Usinj$ Automatiically Acquired Carbon-13 'tJM'R Rules, in ACS Symposium Series No. 54, 'Computer­ assisted Structure Elucidation,' D.H. Smith (ed), 1977.

[21} Stepp, R., "User's guide for UNICLASS pro­ gram", internal report, Dept. of Comp. Sci., Univ. of Ill., Urbana.

[22] Vere .. S.A. 1 "Induction of Concepts in the Predicate Calculus," In Proc. IJCAI-4, 1975.

[23} Vere S. A. "Induction of Relational Pro­ ductions In the Presence of Background Informa­ tion," In Proc. IJCAI-5, 1977.

[24} Vere, s. A., "Inductive Learning of Pela­ tional Productions"}. in Pattern-Directed Infer­ ence Systems, D.A. waterman and F. Payes=RO!n \eQS), ACademic Press, 1978.

[25} Vere, s. A.! "Multilevel Counterfactuals for Generalizat ons of Relational Concepts and Productions," Dept. of Inf. Eng'g, Univ. of Ill., Chicago Circle, 1978.