Duce, An Oracle-based Approach to Constructive Induction

1. Introduction.

It is well recognised (Feigenbaum 1979) that acquiaition of expert knowledge is the major "bottleneck" iii expert ayatem development. However, Michalski and Olilausky (1980) and later Quinlan (1982) have shown that this bottleneck can be considerably eased by generalising low-level data to form high-level rules. Shapiro ( 1983) extended this methodology to deal effectively with extensive bodies of lcnowledge by employing structured program­ ming techniques. Thus the expert llructurea the ltnowledp In a top­ down fashion manually, and then providea examplea which can be used to inductively generate each module in the hierarchy aeparately. Using this technique, Shapiro and Kopec created knowledge atruc­ tures for correctly deciding a forced win for white in any )IOIIition within the chess endgames of King-and-Pawn v. King (KPK) and King-and-Pawn-on-a7 v. King-and-Rook (KPa7KR). Doth solutions were completely verified by exhaustive computation. However, using an information theoretic approach Shapiro showed that around 8~ of the endgame knowledge was provided by the expert in the crea­ tion of the knowledge structure. lbus almost all the work was still being done by the expert rather than by the machine. In an attempt to overcome this structuring bottleneck Patenon (1.983) tried to uae the statistical clustering algorithm CLUSTER (Michalski and Stepp 1982) to automatically restructure the knowledge for the aimpler of the two endgames, KPK. Patenon'a reaulll were not promlaing, with the machine's auggested hierarchy not having any aignificance to domain ex pert a.

In the context d Machine Learning, Michalak! (1986) has called the problem of originating terma coMiriiCiivc illduction. CLUSTER (Michalski and Stepp 1982), pemapa the beat known constructive induction algorithm, uaea a atatistical clustering tech­ nique to group objects into conceptual clusters. Each object Ia ini­ tially described in terms of a vector of primitive attn'bute valuea. Objects are grouped using a heuristic inter-object diatance metric. Rendell (1985), and Fu and Buchanan (1985) deacribe alternative similarity-baaed approaches to creating taxonomic hierarchies which work on much the nme basis as CLUSTER.

· Thlt poper dnc:rtbeo wort wblch - IIIDded Ia port by 1111 Brttbll Oo...,.,.,.·a AI.., l.oalc Dolo- Domcnttna. R- loclldol _, pro­ ·iled bJ he Turtna lnldra~e, Oluaow, Ult. Compotollcnl ftcDIIIII f« 1111 prtporatlon or lhll poper -· proolcled by -ICC RAD Corpondon, Vlct«lo, BC. Canodt.

2. Transformation-baaed Induction.

In Duce the approach to constructive induction differs con­ aiderably from that of Michalski and Stepp (1982), Rendell (1985), and Fu and Buchanan (1985), and can be more easily compared to the deductive transformational programming techniques of Burstall and Darlington (1977). Burstall and Darlington, and later Dershowitz (198!5), suggest that .Uductive program synthesis can be carried out by gradual truth-preserving transformations of a program specification. At firat sight, theae techniques seem not to be applica­ ble to inductive inference, which by definition progresses by per­ forming non-truth-preaerving generalisations of the supplied training set. However, if each Inductive transformation is tested against an oracle which enaures the validity of any transformation, any such inductive transformation is as legal and aafe as its deductive counter­ parta. This uae of an oracle is cloaely related to Sammut and Banerji '· (1986) method of teaming concepts by asking questions Indeed, one of the generalintion operators described in the next aec­ tion is directly due to Sammut and Banerji.

Constructive induction carries out transformations which introduce new terms into the Ieamer's vocabulary. Though such transformations can be truth-preserving, they are not what might be called aemantics-preserving. Thus the primary concern in construe­ live Induction should not be "how can new terms be introduced into the vocabularyT' but rather "how can meaningful new terms be introducedT'. Again by using an oracle to either name or reject machine-auggested concepts, the difficult philosophical problems involved in defining the word meaningful can be sidestepped. Given a meaningful and valid training aet, every transformation of which is both meaningful and valid (by agreement of the oracle), the resultant rule aet will be meaningful ar.1 valid.

3. Operators.

Duce takes as input a set of conjunctive productions, or rules, in a form close to that of disjunctive-normal-form proposi­ tional calculus. Six operators are employed to progressively transform subsets of the rule base. These operators are described below.

1. Inter-construction. This transformation takes a group of rulea, such 11

and replaces them with the rules

Here the rule for the new concept Z7 (1.3) is the most specific generalintion of the rules for X (1.1) and Y (1.2).

{blackbird +- [beak t) II [colour bliCk) II (lep 2) II (tail t] II [winp t)) ea {bloclthcad _the_ blockblrd) (chimp +- [colour brown) II [hairy t) II [lqs 2) II (tail t) II [win&· I]) ea (magaie_the_chimp) (ea&le +- [beak t] II [colour &olden) II [leas 2) II [tail t) II [winp t)) ea (eg_the_eaale) (elephant +- [colour arey) II [lep 4) II [size bleJ II [tail t) II [trunk t) II (wina·l1) ee (adult_ elephant) (elephant +- [colour arey) II [lep 4) II [size small) II [tail t) II [trunk t) II [wines I]) ec (baby_elephant) (falcon +- [beak t] II [colour brown] II [lep 2) II [size bi&] II [tail t] II [wings t)) eg (Oap _the _falcon) (gorilla +- [colour black) II [hairy t) II [lep 2) II [tail 11 II [win&-· f)) eg (ronnie_ the _gorilla) (lemur +- [colour grey] II [legs 2] II [tail t] II (wingsl1) eg (lemur_ alone) (man +- [colour brown) II [hairy 11 II (lees 2] II [size bial II [tail f) II [wingsl1) ea (harry_the_hamite) (man +- [colour pink) II [hairy I] II [lep 2) II [size small) II [tail I] II [wincsl1) ee (clap_the_caucL·ian) (sparrow+- [beak t) II [colour brown] II (lep 2) II [size small) II [tail t) II [wings t)) ee (sparky_the_sparrow)

!-Induce TRUNCATION·· (·12) Is (elephant +- [lees 4)) a valid rule? (y/wi) n TRUNCAl'ION ··(·II) Is (elephant +- [leas 4] II [wines r)) a valid rule? (y/nli) n TRUNCATION·· (·I I) Is (elephant +- (lees 4) II [trunk t)) a valid rule? (y/nli) 1 !· Induce TRUNCATION ·· (·9) Is (man +- [hairy r] II [Ices 2] II [tail f) II (wines f)) !- Induce INTI!R-CONSTRUCJ'ION ··(·I) Rule: (7 +- [lep 2) II [winp I]) a valid rule? (y/nli) 1 What shall I call <7>7 (namelwi) primate !-Induce INTER-CONSTRUCTION·· (·7) Rule: (7 +- (beak t] 11 [leas 2) 11 [tailt] 11 [winp t]) What shall I call <7> 7 (name/wi) bird !-Induce No applicable transformation

(bird +- [hcak t) II [Ices 2) II [tail t] II [wings t]) cg (blockhcad_the_blockbird CJ&_thc_cagle Oap_thc_falcon lparl<y_the_sparrow) (blackbird+- bird II [colour black)) ·& (blockhcad_thc_blackbird) (chimp+- primate II [colour brown) II [hairy t) ll[tailt]) ca (maggie_ the_ chimp) (eagle+- bird II [colour colden]) cc (egg_thc_ca&lc) (elephant<- [legs 4) II [trunk t)) eg (adult __ elephant baby_elephant) (falcon<- bird II [colour brown) II [·i7.e big)) ec (Oap_the_falcon) (gorilla<- primate II [colour black) II [hairy I) II [tail11) cg (ronnie_the_aorilla) (lemur<- primAte II [colour arey) II (tail!)) eg (lemur_alone) (man<- primate II [hairy f) II [tail I]) ea (clap_thc_caucuian harry_tho_hamitc) (primate<- [legs 2) II [wings I]) ec (magcie_the_chimp clap_the_caucasian ronnie_the_&orilla harry_the_hamite lemur_alone) (sparrow<- bird II [colour brown] II [size small]) ca (·parl<y_the_aparrow)

2)

3)

4)

5)

Intra-construction. ·Ibis is simply the distributive law of Boolean equations. lntra~nstruction takes a group of rules all having the same rule head, such as

and replaces them with

Note that while operator I, inlcr-conslruelion, could legiti· matcly be applied to rules 2.1 and 2.2, the result would be less compact.

Absorption. 1bis operator is due to Sammut and 8ancrji (1986), who usc it to generate recursive Prolog clauses. Even though recursion is not meaningrul within propositional cal­ culus, this operdtor can be employed profitably in gencrdlis­ ing rule sets. Given a set of rules, the body or one of which is completely contained within the bodies of the others, such as

one can hypothesise

Note that the preconditions for applying this operator arc stronger than those ror applying inter-construction. Also, ir rule 3.2 were the only rule with rule head Y, then the new rule is necessarily valid. Otherwise it is a generalisation and must be verified by the oracle. In general, asking the oracle unnecessary questions can be avoided by first allcrnpting to answer the question deductively from the rule base.

ldentllkatlun. 1be identification operator is again a poten· tial generalisation, whose preconditions arc stronger than those of intra-construction. A set of rules which all have the same head, the body of at least one or which contains exact­ ly one symbol not found within the other rules, such as

can be replaced by the rules

Dlchntumlsallun. "Ibis operator works on sets or mixed po­ sitive and negative examples. Thus a set or rules which con­ tain positive and negative heads, and which all have some common symbols within the bodies, such as

where the replacement is dependent on the oracle naming Z7. Dichotomisation is a generalisation or the the way that I D3 (Quinlan 1982) creates the internal nodes or decision trees.

(even +- [vi t]l\ [v2 t]l\ (v3 t]l\ [v<4 t]l\ [vS t]l\ [v6 t]l\ [v7 t)l\ [v8 t]) eg (tlltllll) (even +- [vi t]l\ [v2 t]l\ [v3 t) 1\ (v4 t)l\ [vS f] 1\ (v6 f] 1\ [v7 f] 1\ [v8 f]) eg (UllfiTT) (even +- [vi f] 1\ [v2 f] 1\ [v3 t]l\ [v4 t] 1\ [vS f] 1\ [v6 f] 1\ [v7 f] II (v8 f]) eg (ffitfiTl) (even +- [vi f] 1\ [v2 f] 1\ [v3 f) 1\ [v4 f) 1\ [vS f) 1\ [v6 f) 1\ [v7 f) 1\ [v8 f)) cg (fffifiTl) (Ieven +- [vi t) 1\ [v2 t] 1\ [v3 t] 1\ [v4 t] 1\ [vS t] 1\ [v6 t)l\ (v7 t)l\ (v8 f)) eg (tullllf) (Ieven +- [vi t)ll [v2 t)ll [v3 !)II (v4 t] II [vS f) II [v6 f) 1\ [v7 f) II [v8 t)) eg (tutfffi) (Ieven +- [vi t] 1\ [v2 I) 1\ [v3 t] II [v4 t] 1\ [vS f) II [v6 f) II (v7 f) 1\ [v8 f)) eg (UtiTfff) (Ieven +- (vi f) II [v2 t] II [v3 t] 1\ [v4 !)I\ [vS t] 1\ [v6 t) II [v7 t] II [v8 t)) eg (Rtttut)

I· Indore DICIIOTOMISA110N .. (·6) (even +- (v3 t] 1\ (v4 t] II 7) (Ieven +- [v3 t] II [v4 t) 1\ 7) What shall 1 call <7>7 (name/nli) n DICIIOTOMISATION ·· (·S) (even +- [vi t) 1\ [v3 t] II [v4 t] II 7) (Ieven +- [vi t] 1\ (v3 t] II [v4 t) II 7) What shall 1 call <7>7 (nam<>'nli) n DICIIOTOMISATION .. (·S) (even +- [v2 t) 1\ [v3 t) II [v4 t] 1\ 7) (Ieven +- [v2 t) II [v3 t) II (v4 t] II 7) What shall I call <7>7 (nam<!/nli) n DICIIOTOMJSATION ·· (·4) (even +- [vi t] II (v2 t] II [v3 t] II [v4 t) II 7) (Ieven +- [vi t] II [v2 t) II [v3 !)II (v4 t] II 7) What ohall 1 call <7>7 (nam<!ln/i) acv !·Indore ADSORI"JlON .. (·3) Ia (Ieven +- aev 1\ [vi f) 1\ [v2 t]l\ [v3 t]l\ [v4 t]) a valid rule? (y/n/1) y I· Induce ADSORM10N ·· (·9) Is (even +- aev 1\ [vi f) 1\ (v2 f) II (v3 t)ll [v4 t]) a valid rule? (y/n/1) y Ia (even +- aev II (vi f] 1\ (v2 f] 1\ [v3 f) II [v4 f)) a valid rule? (y/nli) y Is (Ieven +- ICY II [vi !]I\ [v2 f) II [v3 !)II [v4 t)) a valid rule? (y/nll) y !· Induce DICIIOTOMJSATION ·· (·2) (even +- sev II (v3 t] II [v4 t] II 7) (Ieven +- sev II [v3 t] II [v4 t] II 7) What shall I call <7>7 (namcJn/i) ffcv !· Induce ADSORP'llON ·· (·I) Is (Ieven +- rrev II (v3 t] 1\ (v4 t] II v) a valid rule? (ylnli) y !·Induce ADSORI"llON .. (·I) Is (even +- rrev II sev 1\ [v3 f) fl [v4 f)) a valid rule? (y/nll) 'f I· Induce TRUNCATION·· (·7) Is (even +- rrev flsev) · valid rule? (y/nli) n No applicable t111nsfonnation

6) Truncation. 'lbe truncation operator, like dichotomisatiop is intended for usc with rule sets containing positive and negative examples of the same concept. However, truncation generalises by dropping conditions. A set of rules which all contain the same head, such as

'Ibis operator generalises in a similar manner to that of the AQ learning algorithms (Michalski and Chilausky, 1980). Its usc is restricted by the precondition that the resultant rule (6.116.2) must not clash (i.e. be inconsistent) with any other rule within the rule base. or all the operators truncation is the only one which reduces the number of rules. All other operators compact the rules by shortening the average rule length.

4. The search algorltlun.

For any state of a rule base, there arc many possible operator applications. Any subset of rules within the rule base R is a candi· date for the application of one of the 6 operators. lbus the search· space for the "best" operator application is of si1.c 21RI, the size of the power set of R. What is meant by a "good" operator applica­ tiori7 Since each of the operators can reduce the number of symbols in the rule base, Duce searches for the application which produces the largest symbol reduction, i.e. Occam's ra7.Qr is applied. If each rule is taken as having a symb.ol size equal to the niunbcr of con· junctive tenns in the rule body plus one (for the rule head), then for each operator there exists an equation which can be used to predict the exact symbol reduction for any operator. Let R' be a subset of the rule base R and /' be a common subset of all the bodies of rules within R'. In the following equations V !'I'""'·' is the symbol rcduc· lion produced when the operator is applied to R'. ll1e total number of symbols within the rule set R' is written as total(ll'). 'll1c symbol reduction equations arc

Note that V 0 P can take a zero or negative value, in which case there is no symbol reduction. Searching for the best operator application is clearly intractable. Moreover, there is no guarantee that such an operator application, once found, would be acceptable to the oracle. In Duce the next operator application is chosen using a best first search through the power set of the symbols in U1e rule baseR. Let a subset of symbols I' be found among the bodies of the rule set /l', where ll' is the largest subset of R containing /'. 1bc operator application apply(Op, I', R'), using operator Op, is only suggested to the oracle when some I' has been found for which V0P is locally maximal. Any rejection of an operator application by the oracle leads to continued search. Transfonnations arc carried out iteratively until no further operations can reduce the rule base size further. At tcnnination, by nature of the operators, almost all sym· bois occur within a restricted number of rules. 'll!Us, although the tcnnination condition requires searching the entire remaining spac~ the search space has shrun:: to manageable proportions. Since only operations which reduce the number of symbols arc applied tcnnina· tion is guaranteed.

5. Animal taxonomy.

ll1is section illustrates the behaviour of Duce when creating a simple animal taxonomy. Figure I shows the set of example animal descriptions given to Ducc. In English the first example s~ys

(even <- ffov fl sev fl [v3 l] fl [v4 l]) eg (fnlffff llllffff llllllll) (even <- ffev fl sev fl [v3 f] fl [v4 f]) eg (fffffffT) (ffcv <- [vi l] fl [v2 t]) eg (llllffff llllllll) (ffcv <- [vi f] fl [v2 f]) eg (ffllfffT) (·ev <- [vS l] fl [v6 t] fl [v7 t] fl [v8 t]) eg (lllltlll) (scv +- [vS f] fl [v6 f) fl [v7 f] fl [v8 f]) eg (llllffff) (Ieven +- sev fljv3 l] fl [v4 l] fl lffev) eg (fllllllt lllfffff) (Ieven +- ffev fl [v3 l] fl [v4 t] fll.<ev) eg (llllffft lllllllf) (lffev +- [vi t] II [v2 f]) eg (lllfffff) (lffev ..... [vi f] fl [v2 t]) eg cnumt) (lsev +- [vS l] fl [v6 t] fl [v7 l] fl [v8 f]) eg (lllllllf) (lsev +- [vS f] fl [v6 f] fl [v7 f] fl [v8 l]) eg (llllffft)

Pa7

bxqsq rim !till otlml Delayed-queening hdehk Mate-threat bkxl>q bkxwp qxmsq rxm~q r2ar8 WK-on-a8 blxwp r2ar8 simp! wkna8 WK-in-check bkxcr mulch rimmx rkxwp thrak wknck Dlack-allacks-quecning-square-soon bknwy bkona bkon8 skrxp wkovl Double-allack-thrcat bkblk bkxl>q cnL·l kalri wkpos Dlack-advantage-from-polenlial-skewer Delayed-skewer bkxl>q d<opp dwipd skewr spcop wtocg bkspr rc.<kd n:skr r2ar8 skach wkcli

A blacl:bird hM a b·ak, is black, has IWO l·gs, a tail and wings. "blockhoad_th·_blackbird' i.r an iNI<ulu ofth· "blackbird' co~~e·pl.

Note the inclusion of the instance set (bloclchead IM blackbird) within the rule. This can be used as a powerful tool for illustrating the meaning of new rules and concepts.

l'igure 2 shows user interaction for this example set. User input is shown in bold type. When asked to induce, Duce searches for an operation and suggests an application of the truncation opera­ tor which will save 12 symbols. The operation is valid if and only if everything having four legs is an elephant. 1lte user can either answer affirmatively ("y"), negatively C'n") or ask for illustrative examples ("i")- If Duce is asked for illustrative examples it lists the instances adult_ elephant and baby_ elephant The suggesliop although consistent with the limited universe of the examples, is too general, and is rejected. l"tce continues its search and finds a slightly less advantageous truncation, which would save II symbols. The new suggestion, that anything with four legs and no wings is an elephant is similarly rejected. There is no particular mechanism for specialising over-generalised hypotheses. This is merely a by­ product of the search mechanism. On the third attempt, Duce ques­ tions whether everything that has four legs and a trunk is an elephant Since this is affirmed, Duce replaces all elephant rules by the new more general rule and returns to the "!-" prompt.

The second generalisation, concerning man is accepted first time around, producing a saving of 9 symbols. In the third interac­ tion Duce finds that using the interconstruction operator, one symbol can. be saved by defining a new concept for all things which have two legs and no wings. 'Inc user can either reject this new concept ("n"), ask for illustrative examples ("i"), or give a name for the con­ cept 'i11e name "primate" is given to the concept Duce goes on to suggest another new concept for all things which have a beak, two legs, a tail and wings. 1ltis concept is named "bird". When asked to search for another operator application Duce comes back with the message, "No applicable transfomtation", meaning that none of the operators reduce the rule base. llte time between each prompt in this example is in the order of one second.

l'igure 3 shows the result of the transfomtations. Not only is the rule base more compact but also the new concepts have made tile rules more conceptually transparent. l'or example, a blackbird is simply defined as a bird which is black. Note that the illustrative examples are propagated to all new rules.

6. Even ·parity.

According to Minsky and Papert (1969) the "parity" function is unlearnable by single-layer perccptrons. llte even-parity problem is that of recognising whether - ~trings of binary digits contain an even number of I' s. Recent techniques using multi-layered percej>­ tron networks (Rumelhart and McClelland 1986) have been shown to be capable of learning parity effectively. Ilowever, in the para­ digm of explicit rule fonnation, algorithms such as 103 (Quinlan 1982) and AQII (Michalski and Otilausky 1980) tum out to be rather inadequate when used fo learn such functions. It has been shown (Muggleton 1986) that whereas single-level concept represen­ tations of parity have a description complexity which is necessarily non-polynomially dependent on the number of attributes, multi-level descriptions can be built whose size is only linearly dependent on the number of primitive attributes. Efficient multi-concept solutions inevitably rely on a divide-and-conquer approach. 1ltus the decision of the tuj>-level concept is based on the combination of values of lower-level predicates. Each lower-level predic.ate has a domain which depends on a restricted subset of the total set of problem attri­ butes.

l'igure 4 depicts examples of 8-variable even-parity. The variables (or primitive attributes) are numbered vl to v8, and each is bound to a value from the set {f t} (rather than {0 1}). In the first example, the variables have even-parily, since all eight have the value 1, i.e. an even number of variables are bound to I. 1lte "eg" part of the example shows a string of this fonn. l'igure 5 shows the session in which Duce transfomts the training set of figure 4 into the partial, hierarchical solution of figure 6. llte responses are based on

bxqsq hdchk rimmx spcop s!lmt Delayed-queening-! bknwy bkon8 dsopp mulch rxmsq skach skrxp wkna8 Dclayed-queening-2 Mate-threat-I bkblk White-king-In-check-delay bkxcr bkxwp cntxtsimpl skewr wknck wtoeg Skewer-threat bkspr rkxwp r2ar8 rkxwp wkcli wkovl wkpoo Double-attack-lhrcat-2 bkona bkxwp bkxbq blxwp dwipd kalri n:skr cntxl wkna8 Mate-and-double-attack bkblk bkxbq bkxcr katri lhrsk Mate-and-double-attack-safc>-from-prornoled-queen Mate-threat-2 dsopp qxmsq r2ar8 rkxwp wkcti wknck bkon8 bklpr bkxcr r2ar8 skrxp thrsk wknck wkovl Mate-lhreat-safc-from-promoled-q Double-attack-! bkblk bkona bkspr bkxcr bkxwp blxwp dwipd skrxp bkxbq blxwp dsopp dwipd rkxwp rxmsq simp! skcwr wtocg Potential -double-attack -uscful-to-blac k bknwy bkxbq cntxl katri r2ar8 wkcti wknck wkovl wkpos

a standard solution in which the variables arc recursively broken into two equal sized sets at each level. The total set of variables have even-parity if and only if both subsets have even-parity, or both have odd-parity. 'll1e first three concept suggestions do not follow this scheme, and arc rejected. lbc fourth is recognised as "the second-half of the variables have even-parity" (scv). lbe user then affinnatively answers questions concerning the application of the absorption operator. 'lbc next suggested concept is named ffcv or "first-half of the first-half of the variables arc even". Given the origi­ nal eight examples, Ducc' s solution is generalised to cover 16 of the

256 possible instances. If presented initially with the complete instance set, Ducc tends towards a solution consisting of an 8-lcvel deep hierarchy in which levels are used to count the number of vari­ ables set to t.

7. Recreation of the Kl'a7KR structure.

!3oth the animal taxonomy and parity problem have highly restricted domains. lbc real test of Ducc's capabilities has been the attempt to restructure Shapiro and Kopec's expert system (Shapiro 1983) for deciding whether positions within the chess endgame of King-and-Pawn-on-a7 v. King-and Rook (KPa7KR) are won-for­ white or not. The domain contains around 200,000 positions Shapiro generated a database of all positions, labelling each with its minimax backup value of forced win-for-white or not. A set of 36 primitive board features were calculated for each position. Since many positions had the same feature vector and won-for-white value, the number of distinct examples was reduced to 3196. With this number of examples Duce's search-space for applying the first operation is 2 3196 (see section 4), or approximately 10 1000 · Nilsson (1982) states that the complete game tree for chess has approxi­ mately 10 120 nodes; even that well-known hard problem has a con­ siderably smaller search space than that attempted here.

For the purposes of the experiment, Shapiro provided a ran­ donlly chosen board position for each example. lbus the initial rule base given to Ducc consisted of examples of the form

Jwonfor-whitt +- [tatur<l II [tatur<2 II .. [taturt36) tg (position)

Two chess experts, Ivan Ilratko and Tim Niblcu, helped in giving oracle answers to questions asked by Ducc. 'll1c rule base started with II 8,252 symbls. 'l11e first suggestion reduced 21,606 of these, a reduction of around 20%. After three questions, around 60% of the rule base had been reduced. After 41 transformations, the rule base had been reduced to 553 rules, and contained a total of 9050 symbols. At this point there were still applicable operations, but symbol reductions had been reduced to the low hundreds.

In questions 3 and 5, in which new concepts were intro­ duced, the size of the common set of symbols, Int was too large for a comprehensible rule description. It is here that the illustraiive board positions were indispensible. For this experiment, a domain­ dependent graphics front-end was built into Duce, which gave the user the ability to peruse a large number of board positions representing the concept and counter-concept Without this graphical device, new concepts could not have been recognised and named As it was, concepts were named with confidence within the presen­ tation of 20 to 40 board positions. It was rarely necessary to reject new concepts and generdlisations suggested by Ducc in the KPa7KR experiment.

Figure 7 shows the structure created manually by Shapiro and Kopec, which took an estimated 6 man months of effort. Figure 8 shows Ducc's solution. Duce carried out the 41 oracle agreed transformations during a single working day. lbe computation time between each question was in the order of a minute. It should be noted that where Shapiro and Kopec have used . nine hierarchically arranged concepts, Ducc has used thirteen. Ducc's solution also con­ tains 553 rules and 9050 symbols where Shapiro and Kopec's manu­ ally created solution contains the equivalent of around 225 produc­ tions and around 1000 symbols. Although Duce's solution could have been made more compact by applying more transformations or by generating decision trees for each concept using ID3, it seems unlikely to the author that 01is would have resulted in a solution which was as compact as O!'!t of Shapiro and Kopec.

Ily virtue of the operators used by Duce, the KPa7KR solu­ tion is guaranteed correct by construction.

8. Discussion.

Duce is a program which, with the aid of a human oracl~ discovers useful new concepts. AM (Lena! 1979), an early concept discovery program, was criticised (Ritchie and IIanna 1984) for the obscurity of the techniques involved. Unlike AM, Duce uses a sim­ ple and explicit set of six operators to create and refine concepts. In addition the meaning-giVIng agent, implicitly present within any Machine Learning system, is explicitly represented 11 tho oracle within Duce.

Extensive search is used to decrease the number of question& asked by Duce of the oracle. However, in what circumstance& Ia tho usc of an oracle either justi!led or feaaible? In thia reapoct it Ia worth noting that on the basia of a meagre number of empirical stu­ dies the ratio of oracle rejections to acceptances seems to be inversely related to the percentage of examples provided from the domain. In the parity problem, where Duco was supplied with a sparse set of examples, a large number of rejections were necouary (figure S). In the more complex KPa7KR chess domain, Duce was given an exhaustive set of examples, and required almoll no rejec­ tions from the oracle. Thus it might be expected that in domains in which a moderate amount of example material is available the oracle would need to reject a moderato number of proposals. Further research is necessary to show the truth of this hypothesis.

Duce works with statements in propoaitional logic. One way of extending the present work would be to attempt using aimilar techniques within O!her representations. Banerji (1986) is presently looking at the problem of constructive induction within first-order calculus. The author believes that techniques akin to those u!icd in Duce could be profitably employed i!l learning hierarchically definable context free grammars.

Acknowledgements.

I would like to thank Donald Michie for auggeating the application of Duce to the KPa7KR problem. Thanks are alao due to Alen Shapiro for supplying the chess example database, Ivan Bratko and Tim Niblett for acting as chess oraclea, Pete Mowforth for sug­ gesting the name "Duce" and Michael Bain, Dave Hauaaler, Claude Sammut and Wray Buntine for helpful discussion.

References.

• Banerji R.B., Changing language while learning recuraive descriptions from examples. MachiM Learning: A Guid. to Curren/ Research. Ed. T. Mitchell, J. Carbonell and R. Michalski. Dordrccht: Kluwer, (1986), pp. 3-9.
• 2 Burstall R.M. and Darlington J., A transformation system for developing recursive programs. Journal of the M.rocia­ tion for CompuJing Machinery, Vol. 24, (1977), pp. 4467.
• 3 Dershowitz N., Synthesis by completion. Procudi11g.r of/he Ninth International Conferel'lce 011 Artifrciol Intelligence. Los Altos, CA: Kaufmann, (198S), pp. 208214.
• 4 Feigenbaum E.A, Themes and case studiea of knowledge engineering. &pert syslem.r ill the Micro-electronic Age, Ed. D. Michie. Edinburgh: Edi::t.o~rgh University Press, (1979), pp. 3-2S.
• S Fu L.M and Buchanan B.G., Learning Intermediate concepta in constructing a hierarchiesl knowledge base. Proceedings of the Ninth International Joint Conference 011 Artificiol llllelligence. Loa Altoa, CA: Kaufmann, (198S), pp. 659-666.
• 6 Lenat D.B., On automated scientific theory formation: a caae study using the AM program. Machine Intelligence 9. lld. J.E.Hayes, D.Michie and L.l. Mikulich. Chichester: llor­ wood, (1979), pp. 2S 1-283.
• 7 Michalski R.S. and Chilausky R.L., Learning by being told and learning from examplea: an experimental comparison of the two methods of knowledge acquisition in the con­ text of developing an expert system for soybean diaeasc diagnosis. International Journal of Policy Analysis and lnfori!'IIJtiol'l System.r. 4(2): (1980), pp. 126-161.
• 8 Michalski R.S. and Stepp R., Revealing conceptual atructurc in data by inductive inference, Machine llllellige/ICI 10. Ed. J.E. Hayes, D. Michie and Y-11 Pao. Chicheater: Horwood. (1982), pp. 173-196.
• 9 Michalski R.S., Understanding the nature of learning: issuea

and research directions. Machine uarning: An Artificial llllelligeiiCI Approach. Vol. 2. Eds Michalski R.S., Car­ bonell J.G. and Mitchell R.M. Los Altos, CA: Kaufrnanp (1986), pp. 3-2S.

• 10 Minsky M. and Papert S., Pcrceptr011.,, Cambridge, MA: MIT Preaa, 1969.
• 11 Muggleton S.H., Inductive Acquisition of Expert Knowl1dge. Edinburgh: Edinburgh Univenity (Ph.D. thesis), 1986.
• 12 Nilaaon N.J., Princip/11 of Artificiol llllelligence. Berlip Springer-Verlag, (1982), p. liS.
• 13 Pateraon A., An al/empt to use CWSTER to sylllhesise humanly intelligible .rubproblem.r for th1 KPK chess el'ldga~M. Uroana, IL: Univ. Illinois, (UIUCDCS-R-831156), 1983.
• 14 Quinlan J.R., Semi-autonomous acquiaition of pattern-ba~ed knowledge. llllroductory readings in upert systems. Ed. D. Michie. New York: Gordon & Breach. (1982), pp 192-207.
• IS Rendell, L., Subllantial constructive induction u~ing layered infom1ation compreaaion: tractable feature formation in acarch. Proceedings of the Ninth lnter11ational Joint C011Jerence 011 Artificial lntelligel'lct. Los Altos, CA: Kaufmann, (1985), pp. 6S0-6S8.
• 16 Ritchie O.D. and Hanna J1.K., AM: a case study in A.t. methodology. ArtiJidal lnlllligencc. 23:3 (1984), pp 249-268.
• 17 Rumclhart D.E. and McClelland J.L. , Learning inteni"al representations by error propagation. Parallel DistribUted Processing. &ploration.r ill the Micro-Structure of Cog­ nition. Vol. 1: Fowu/JJtion.r. Cambridge, MA: MIT Press, (1986), pp. 318-362.
• 18 Sammut C. and Banerji R.B., Learning concepts by asking questiona. MachiM uarning: An Artificiol l"telligence Approach. Vol. 2. Eds. Michalski R.S., Carbonell J.G and Mitchell R.M. Los Altoa, CA: Kaufmann, (1986), pp. 167-192.
• 19 Shapiro A.D., The Rol· of Structured /flduction in &pert System.r. Edinburgh: Edinburgh University (Ph.D. thesis), 1983.