Knowledge Acquisition from Structural Descriptions

KNOWLEDGE ACQUISITION FROM STRUCTURAL DESCRIPTIONS 1

Fredericl1 Hayes- fioth The [(!\NO Cor port ~lion S<>nt a Moni c a, C/\ 901106

1\h r. tr <~cl . The r epre·:enl nlion of concep ts 11nd ;mlr·ccdcnl -con~;cquenl prodt1c lions i ~; di·.cur.sed and a l>i<'l llnd lor indue ing 11110WI!'clf·,e by "b~. trilt ling such · (··prr".enl ;, lions lro1n a ~·<' '11 . t PI1Ce of lr <<ini nf', ·exmnples is dr".<C ribcd. The propo:.ed lc;u·ninr{ method, interference ,,.,,tl c hing, induces illY, I r<ldions hy finding relational properliPs common to two or more ~·x·~ mplar s .

I. I NHWDUCTION

1\ numhPr of di!.linrl p<ll"<tdigmo. for study inp, learning '"'K !tine" il 'lve Pnwrged · dur inr, tile I <1st I wenty years. ·1 hou ~~ ~~ earh differs from I he others in a var iety of ways, lite three differ f'nCPS whi ch most clc :·rly demark each p;~niCii p,m <lr r> (I) ll1r> t ypes of ~. now l cdge which c;m be <·cqui 1 c· rl, (;;>} I he W<lY in whir il I hi ~; ltnowledge is rcp r c~.f' nl c d, ;mel (3) the' l ypc of l c~rnin8 ;,lgorithm u<.:ed. I hr· lr>ar ning m'lchine whit h we· wi ll de<-C I ilw in thi s paper '" q11ir'-"' concept s rPpre<:enlahlc ;,s conjunc tive forms of I he predicate c;,lc ulu!; and lwhJviorr. represent abl e as p1 odtK iionr. (antcr edent -cow.·cqU('nt pairs of such COI1JUncli ve form·:); th~"·C conc e pt ~. ;md beh<~vior rul es are inferred fr om sequenti all y presen ted pai1·s of exLimptes by · 111 a l ~.o rithm thi'lt i ~. prov,.hl y e lf r~c ti ve for a wide var iety of proi.>IPm"-.

I C''lrninp, is v iewed hc>re "s ;, continual process of ~. nowk·dge expi'l ll ~'io n, that i·: , H!· the at qui sition, in adaption to lr nining exper iences, of hi p, her -·OI"der, more complex, i'lnd 1nnre el .1bOri11c ~,now l edgr> ·:tnJc.ture':. One's ~. nowledge at <~ 11 y point in time includes tho,;e concep t ~: 11nd produdions innnlrly prov ided or previously teamed. The concepts are P<·ll r 1n tr rnplatC's; event s which m<1lch a r.oncept 11re rr·r ol~nized 'Is belonging to the ci<l ~·~' delimited by th<~t t lll lCPpl. ·1 he productions are poirs of concep ts; one of the concPpls functions "~ il recogni zer , the other ~. pcc ifics the form or i'l n i15SOCii'll ed ilclion. A production is interpreted "'· <l lw hav ior gener ator in the sen~:e !hilt (in some c o1npuling env ironment with an appropri<1tc control c. tructure) the det c>c.tion of " condition in lhP environment w lti c h n·<~lches the ant ecedc.·nt c au·,e~. the consequent cornpnnen t to be instantiai C'd ;,nrl then evoked. Here both lhc i'lnl ecedr' nt "nd the ron~.equf'n t i\re templol es; the <llll ('(<'dr nt dr i Prminr's whether lltf' production is to I.Je c>-:ec ul cd, and i·f ~, o,. wh<~ l spec ifi c constan ts in the dc~cription of thr event heinr; aiiPndr>d to il re to be bound to v ari;.~hle s in the consequent.

Within thi s f r;,rncwor~ .· lhc m.1c hine learninr, problem w it It which we <~re com enw d um be <.. t a ted in the iollowill f~ way: Gi vf' n a collection of concepts and product ion ~; const ituting what is known at ~: orne time and a WilY of describing event s in t erm~; of their structure, i'lnd John McDermott Carnegie -Mellon Uni vers ity Pitt sburgh, PA 15213

--- ,"l,i ·:·;:·e~,e-~;:-(h·.,:;;;o.-j)erforrncd white both authors were at Cmrwp, ie·Mellon Uni ver sit y. It W il'· support ed in part by the De fense Advanced Re~.earc h Proj ects Agency (14461'0 - /:l ·C-·00711) <>nd monitored by the Air Force Office of Scientific Re ~.e arch . A 1nore detailed version of thi s r esearch report can be ob tained from lhc Computer ScicncP. Depilrtment, Camegie-Mc lton Uni versity, Pittsburgh, PA 15213.

construct a milchinr whi ch is ahtr., to induce "dclitional r.n ll(P pt ~. or productiow: from tr aining datil. To rnake our I rc<~ l men ! of thi s probl em more. conuete, we will usc the ··, irnplr" ;l of the concept fortn<1lion b1<, lt'.. <~ II"Nrlpl ed hy our lllil t hi1w <1~; an example through01 1t thJ> pilper. The t a~; k is to lind wha t the three exemplar s in Figure 1 have in co lllmon. Our program induc e<. the following abs tr ac tion:

There are three object s, including a '-'mall circle and il '.;m<t ll squue. The <..quare is ilbove .the circle . ·1 he thi rd obj<>d is l ilrge.

This p<tper is di v ided into four sect ions. In the nex t <..ec lion Wf' di scuss in gfmer;·l a way of de<.cribing event s whi ch fac ililill es lindinr. what two 01· more event s have in con11non and il m<~l c hinR illp,or ilhm whk.h ci\n be used to find these abstr<>clionr.. l hr n wP locate SPI<OLJTU~, our concept and produ( t ion indue ing progr arn, within the h ro,,der context of our wor~,. The third sect ion descr ibes ~; l ' l ((l lrt Fl('s int erference matching (induction) <> lgorithm in c:orne del ;,i l; we indi ca te hen~ '"ore ~.peci fi c ally how SPROUTER makes use of stn1clural repre'.ent at ions of event s to acquire and store know! P.dge. In the final section we conc lude with a brief considc1·ation of the strengths and we<~knesses of SPROUTER and directions for future research.

II. STRUCTUr~AL REPI(ESENTA TIONS

The problem whi ch Wf' are addres ,; ing is si"mpl y clC' ~:c ribcd: Design a progr~m which C'l l1 infer conccph; 11nd prodttr. lion~ front illttslriltivc in c. l <~nu~s. Tile method we Plnplny is correspondinr, ly s lr <~ i ghtforw <~ nl: Extract co tnlnonalities from the examples and attenuil l e their dilfN( 'nr es. Such iln ilppro;Kh i ~ lil·.e Cillton's very primiti ve "composit e piloln!'.r<~ph theory" of concept lr! Mninp.. [8] and the "po ~ ilive foc u ~; ing str ategy" for ronjuncti vn concept lc<> rninr:, fir ~. t ~ . ludied by f:lruner, et al. I Tl. WI 1ile �alton'~, coni ribu linn W <'~' ~; impl y l o propose th<~l Lm.kn'own patterns could be inferred by ovNiay ing homologous memory rpprcscnt ationr. of relat ed examples (,,., if one were forming a composite of milny photographs o f the same subject), Oruner and his colleilgucc. showed how suc- h a procc r.~. could in f <tel be refl li zed. E<~c h pre,;cnted object (exemplm) is dc(.cribcd "~· a conjunction of ~; ppc ifi c feature values. To find lhe templ ate whi ch is tn il l ched by all of the presented ob.jed s, a feature vector con taining only those features cornmon to all of the t'x<'mplilrs h generntr>d. Thi s fe,.ture vector 'is the comept. Since that scmin~l work, m~ny computer ~. ci f' nti sh h;we produced increasinp.ly practical and ·> oplli ~. ti r iltr)d feo:tture-vil lue < c>nt ept l earner ~. based on r e lat ed techniques [11, 10, 16, 20, 21, 29).

Extending such lc <1 rning motk·lr. so that they can indut e general (relotion'll) clil ,,f- ificillion <md beh<1vior rules i·' the goill of our work. In foCII~ ing on rn<'lhods for ~·. · ·· rwnl! ing re i<Jtionill ill ·' ~' t r <lclion ~' whit h make pos,;ible the r ec ognition of compl t> x event s, we encounter three problc~ ms not encountered in previou ~. worl1. Firc.l we mu5t d<"'clop " formal <,r hemf' for ck·scribing compl ex event s whi ch f;Kilil.,t es the gener il lion of ~bs lr<1clions. Second, g iven dec.criptions of two exilmplcs of the s;unc concep t or p1 od11dion, WP li111St deve lop " mr-· lllod for· compe~rinr, them '·O 11~<11 their· tOmrnone>liti e'' nm bf' identified. Third, it is r!CCP'' ~'il r y to develop "' w <~ y of ~;lor·inr, the discovered il i.l ', tr ,lclions to filcililill e thf' ir <, uh!.equent use in either of two ways : they rnay be u ~; ed as t c>mplate!; for clo:tssifi cat-ion and beh;wior r,cncre>lion, or they may be used as ~.now l cde,c rr>prr~ent<~tion~ who<,e pre c i ~ion m<1y later be irnprovr d by leilrning if now in ,; t~llces of the same concept or production are prov ided. Thc ,.e problemr. are referred to · lwlow "~ the dc><. rriplion problrm, the comp<~ri son pr ohl<' tn, <ll1d the ~;lor <~ co rrobiPm. Ee>rh is considered in mor e de tail in the (, lfbsecplenl p<~rilg r aphs .

·1 hr dt~<. cription probiN r> (HJI<lil·_; prov iding il symbolic n ·rre<.pnt e> lion of e(lch <'xcnlplar saldy in~ two demands. r· ir ~;l , lhoc.o at tribut er, of the exc~ 1r 1 pl ,1r which me s<Jiient <111fl polr·nli <l lly cri l er·i;,l l'rll"d he· rdlr)ct ed in its description to itl '' llre that thr) cl asf,ific ;llion rule inducNI will be suffi ciently di scriminating. Note th<Jt c. incc <1n exemplar rn<1 y hP compo<,P.d of rnany objNt ~., lhe description must di stingui sh ee1ch obj ect <ll1d indic<ll e cl earl y how it relates to the other s. Second, the dcscriplionc. should facilitate tho irlcntifirillion of cotntl'rOllilliti e~ among thP Pxempl;,rs so thnt the e>IJ!dr"lction being ·;ought r<Hl IJp found quickly. Since eac h object may exhibit a v ilric ty of charilcleristi cs and p;,rticipilte iri nunler'our, relationships with other objet ts, finding commondlitie'' between two or more ex <~mplt> s wil l necessite>le se;,rch. 1\ represen tational scheme which helps direct thi s -:;e arch is ;~lmcrs t essential.

The me thod of description we employ is bui lt on three centre>! concepts, the .propert y, the c ;~se fre>me, and thE' par ilrneler. A propf)rt y i!, " featur e or charilct eristic of e> tl ohjPd. For ex'lmple, SQUI\riE <1nd SM/\LL namP two pr·operties of smil ll squar~;"s ; the properties AIJOVE and HFI.OW ilrf> used in our worl1 to cfpsnibe objec ts which are ahovP or below othr>r s in pictoriill di ~ pla ys. To define the r e l<1tionship of one object being above another, a case fr <Hne of the ~. or! {AUOVE, FlFI OW} is 11:.Pcl. In p,P.neral, ca<" ' frilrr'res il re se ts of prope rtic ~; which are ~.ernantic;~lly r c l<~l c> d in some e·xogcnously determined manner. To produce dr~.rriptions of obje ct~;, events, or· behaviors, case fr e>mes are parameterized (instantiilted); that is, " name is r, iven to each obj ect in the event being described and this nilmc is. CJssociilted with e<1ch properly of the object. l'arilmeterized c<l sE' frilmr>s Me call ed c;N~ re lo:ttions. For ex;nnple, if b is the n;~me of a ~.quare above a circle named c, I hi s might be dc<;cribcd by thC" followinr. set of case n ·t,,tions: {{ SQUARE: b}, {CmCIE: c}, {ABOVE:b, BELOW: c}}. :.>ur h <1 set of case relations interprc>led '"' a conjunction of Vdlid propo~. itions is cilllcd a parameterized structural r- e pr e~.entntion or PSR [9, J 2, 13). In this exampiP, {b, c} is tlw petrame ter se t of the PSR.

A struclurill dPscription of the first two exempl<trs in the concept formation tilsk di scussed in the introduction is given below.

l he dcsuiption of E) il s~e rt s th;;,t there is an event r nmposed of threp objPct s, nilmcd a, b, and c; that the object li!beled a has the pr·operli es of a trianr; lc , of a large object, and of contilining the object le>bclcd b; ~nd so on.

PSRs prov ide " ''olulion to the s lor ;~ge problem as well as to the clc ~; cription probl em; that is, they can be " ~C'd in storing di scovered ilb'dr ilclionc. . In the case of dw;criptions, parmnPtc> r ,;yrnbol '' <rre c ho~;e n to nilme each oiJjec I ·;o I hilt if the silmr obj ect i'.- p<~rt of more than one c il',e rc~ liltion, it is n ' fen ·f'd to in " consi,;t ent Wily. If one ;.1\t Pr ', the interpret;,tion so that eil<h di ~. tinct par ameter is conc;itlc rod e>s an unbound vMi ~ ble, the PSR can be < on~ idc· rcd ;, t ernple~le for concept idP.ntification. Such t c rnpl..1te ~; h<1ve been w;pd by ~eve r a l researc.hers [1, 9, 12, 1 ~~. 1~i . 28] to specif y what properli rs an obj ect must hilve in c>rdN to sati ~ fy mcmbP. l <, hip ir1 il patt ern c.lilss. While tiH· p<~nHne t e rs in a de~cription can be llrought of e~s being ex ir. l entiall y quilntified, those in a PSfl used as a template o. hould he thouchl of ilr. IJ<'inp, univc r ~. all y que1ntificd. When ll '.r.!d as e~ templat e for p;,tlern cl w,~;ific.ation, the PSR. is compilrecl with ;~n even t (iln existentiall y quantified PSR). If ;r m<Jpping from the f'Vf'nt to the lcnlplilte Ciln he found whi ch preser ves the> p<rrametPr bindingo. in the event clr!''rription ilnd which ma~.es ee>ch Cil ~;e reliltion of the templ e> tc true, the event is s;,id to rn e> tch the templ <1 le.

In ;~ ddition to their role as cl ass ification rules, PSRs c iln be used ilS r-cncral bch<1v ior rules. In thi s case two lempliltf's ;,re 'l s~.ociiltrd . One of ti1C' rrr, the ilnl ecedent, is U '"~d to r ecogni4e a se t of condition ~; (a cont ex t) which indi ce>lcs that <> particular set of <Ktions is appropriate; when the <lnteccdent templiltr> i<, n1 illched by some event in the 0nv ironment, the rulf' i·; invo~,ed . Tlw second .template, llle consequent, specifi cs wh<1l <1clions arc to be pc rfonned. WhPn the two I P mplilt c ~ ~. harP common p <l r<llne l er !; , e<1ch parilnw t·cr in tlw consequent is bound to the f,;nne ve>lue " " the corrrsponding pilrameler in the ;111tec.edcnt. These beho:tv ior rules rn<>y ilcl, for example, as F'ost productions, trilnsform<Jtion il l r, r«mmo:tr rules, or the problern sol v ing rules of STRIPS [7]. In short, a rule with the ilntecedent A(X) and the consequent C(X) over the variables in the set X is intNprded to mean (X) [A(X) => C(X)]. In actual ilpplicat ions, II defines a precondition which can be true of the content s of some working memory, e~nd C definr>s whilt is to be done if the precondi ti on is .; atisfied. Note thilt ilny such production c e1n be described by a PSR in whi ch ee>c.h case relation in the ilntccedent includes a term of the sort EVENT:a, P.ach c <J ~. e rE'Iation in the consequent includes a term of ·the sort [V[NT:c, e>nd the PSR itself includes ·a ca~e relation {ANI ECEDENf:a, CONSEQUE.NT:c}.

The abstraction of the first and second examples in the '-rllllple concept form;~tion task can be represented in the following w<~y:

EhE2: { {ABOVE: I ,UELOW:2), { SAME!SIZE:2,SAME!SIZE: 1 }, {SMALL:2}, {SQUAf~[:l }, {SMALL: 1 ), {CIRCLE:2}, {TRIANc;LE:3}, {Li\RGE:3 }}

f'xcmpl;u· l i<; in fact <1r1 ir1<; \ance of thi s <'~h!; lraction if the par<rnwter 1 i·; replaced by tlw pilrarneter b, the parameter 2 by c, and the pnrarneter :3 by a. Lil·,cwise, excmplnr 2 can be ~;een to mntch the abstrnction iJ the J)<Jramder l is r epi<Ked by ci, the par<1rneter 2 by f, nnd the parameter 3 by e.

The comparison problem c<rr1 be sCl lved by U(dng a technique called interference rn<rlchinr, or IM [1 J -12, 15]. It i~; a rrocess for identify ing all of lhc common properties of two PSr~s <~nd extr<lc.ting <1 third p~;R which is ;r templnte matched by the two exernpl<lr~'- WhPn two events haveN allribulcs in common, their· dc~,crrplions will cont<1in ;:rt most N C'lse relations which ;m~ identical (r,xcept for alphabetic diff!'rences between the narnes of corresponding pararnelers). Figure 2 schemati zcs IM iiS a process for findinp, the intersection conl<lininp, thr>·:.r) c<>~.P rel'ltions.

The circular area·; lalwllcd 1\ and B correspond to two f'SRs; <1ll of the cilsc relations common to !lie two PSRs are in lhr <'~rea lilhellr>d A*[3 (r·ead "A d<~r fl"). Elecause any sub·;et of this (conjunctive) se t of common relations <~l~o defines an abstraction of 1\ and 0, it is impodant to be able to di stinp,uish betwrcn the set and it s proper subsets . . We c <rll ;111y <~bstr action of A 11nd B wlrich i~; properly contained in no other <'lbstraclion of 1\ and 8 il maximal abdradion. Mor·e forrn~lly, if S (;) A denotes that A is a PSf~ matchr.d by the PSR S, then a maximal ab~.tr<1ction, A, of two PSRs S and T, satisfies S(*)i\ and T(o<)i\ and (B) [B(;)A S(;)B T(;)B ~> A(*)[Jl

It should be pointed out that for any two PSRs, there may be more than one abstraction which is maximal in the above sense. For examrle, given the following two exemplars,

E3: {{CIRCLE:<~). {RED:a }, { LARGE:a l}

E4: { {CIRCLE:b }, {CJRCLF:c }, W!=D:b }, {GREEN:c}. {SMALL:b}, {LARGE:c}}

two milximal abstractions cxd. If the parameters a and b are considered to be identic<~!, the maximal a.bslrilction is

[3;E4: {{CIRCLE: I}, {RED: I})

If on the other hand, the parameters a and c are considered to be identical, the maximal abstrilclion is

E3;EI!: {{CIRCLE:!), {LARGE:!})

To perform interference matching on reasonably complex representations, we need an algorithm which operating within as small a search space as possible, ca~

discover the best mi1ximal iliY,Ir·ilctionc. a~; quickly as pOs(;rhle. Two approaches to intr)rf en,·rKe mat ching are r,nowr1: (1) In llw hind - fir·st appronch, rach pilrameter in one f'Sf~ is ;, s~;ocialed with a par·;11netcr in the ~.c'cond PSR >111d then a rn;~xirn;~l aly.\raction is found by Pxtr;~c\ing the c ";'e rel<1l iow: which are idenl ic al in I he I wo PSI'Is (modulo lhc paramete r bindings). In thi :; Ci1SC, if the lesse r· number of P"r"rnetr·r·s (in PithN PSI~) i~. MP :omd tlw grer~ter nurnl>er i ~; Nr', the nutnbe r· of pO'·'·ible bindin1~ fundions is cornbimrtorii11, (binomial coefficient Clf NP over Ml,) * MP!. (?) 1\llrrnillivr) ly, in thr mi11ch - fir ~;\ ;~pproach, all in~:\;m tialions of case frnnws of onP type in orH' f'SR are cornpi1red with <til instantiillions of the ~.i1rne type of case fr<lmr in the other f'Sil, ;mel po ~;r. ibl c p;~rarn r. lr>r bindings ilr·e identified b)' determining which pilrarnete·rr. have corresponclinp., properlie~; in rornpilrable r e lation ~ .. Her'C if Nl <1r1rl Ml ·are the numbcr·s of rw.r r ·e l;~lion c; in the l"r-r,et <111d smaller PSf~ (<1Ssurning only orw type of ca~'"' frame), \he number· of possible way~; in which the n~lalions can be fore eel into corre!.pOmlrnce is r. imililrl y comb inatorial. While it is true th;~t if one were int r'rc~ t ed in computing nb:.\r;tclions of quite low·-level event desc riplrons (such as undirected graphs) neither method would b0 much prc:fr~rable to the! other, in most reil l problem:; tile number of in ~. \ances of ;my p<1rticular c<~se fr<~me is quite smal l r elative to the number of p<tr·;m1clcrs in the PSR, and so thre sP.cond method i ~; Uf; uitlly rrefernble to the fir st. It is I hi ~ mel hod whi ch is w;ed in our current work.

ThP actual ;~lgorithm we use hils the following form: 1\ r<n1domly selected c<1se rel~lion from one of the C'XC' I11pl ar PSris is pu\ in\0 COrrc·.pondence with a case rrlrttion (which is il p<tr<trn0!Pr·i7;1lior1 of the s;~rne case fr-;111\C) from a ~-econd exc rnr'' '" f '~;tl; p~r<unetcrs havinp., iclcnt ic al proper\ ie ~ arc iclenl ified ;r~ cquivillenl and the. rr c. ultinr, common ca:.e rrliltion bf'cOrnes \he (primitive) <~h:;\r"c linn associ;~ted with 11~>1t set of pi\raw~ t e r bindings. I hen other pairs of primitive Cilsc r cl<~ lions , one fr·om each of the two cxcrnplm PSI'Is, ;,r·e put i11to cor·rcspondence. If <1 compared pair of rel;~tior1'· enbtih parilrroc l er bindings cow: istenl with those already identified, the coi11mon rcl <1 tion is itcldecl to the ;,\y.\r<Kiion bein:; pi'Oduccd. This r1f'W abstr;~dion is the f;P.t urtion of the old abstr<lCtion ;~nd t lw new C<l!.:C r elation, and the r1ew sPt of parameter billding~; is the ~;c t union of those bindi11r,s Pntililed by the prev iow. ah~dr;tction ;111d the forced bindinP·; of the p et r ·.1r1"1Pters in the c·ornpnrPd pair of < ilse r·etal'ions. If a pair of case relations enlails par·ilmcter· bindings incon,, istent with tho,;e alrc<~cly idPntificd, the common c;~se r.eliltion becomes a new (prirnitivP) ab,;trilctior.'.

ClcMiy, thi s <tl p,orithm may find a number of cnntpc'ting maximal ill.)·:\ rill tionr. . Our ;rppro,1ch i'' to huilci <~~; many distinct abstrac.lions as por,sible, one rcl<tlion at a tirnr, until a limitation on the number of distinct 'lbstractions which can be considered at one time is exc.eecied. At that roint, only those abstractions which are most signific.<tnt in terms of thr ntunher and type of case relations they incltrde <ln~ r·etilinrd. These <tbstr;,clions continue to be elllenrled "" other rairs of consistent rcliltion~; arc found; at the ~ . .,rnr~ time, the lcrtst si[<nificant <~bstractions ilre continu;dly pruned frorn further con~dderation in order to kePp the r.e<trch r;pace as small as possible.

The result of the procw.s i ~; a .;e l of best maxirnill <lbs I r iiC t ions, repre~('ntecl <1~ PSRs. 1\ny onr of t hesc ilhc.lrilction·, (interpt·ctcd ;~:, exi',\enti;,lly quilntified) c.an tlw n be input to SPfWLJTF.r~ lop,el her with a third exemplar to produce a set of maximal abstr·actions of three cxernplilrs, or the procrO>c;~. may be repeated on as many additional exemplars ilS desi red. Since a maximal abstraction is compared to an cxemplilr in the same way !hilt an exernpl;~r is compared to another exemplar, we find it d0si rilhlf' to store abs lr <Jc lions "'' PSFis, wi th the in iPI·rrc l il l ion lh<l l their p;u·.>mE>I er c. reprf".ent exis tentiall y qu<1nlificd v<J ri <Jblcs der ived from the co rr r"~. pondcnce of u1·-.c· 1 !'laliom. in the cxempl<1r s from which the PSfl was ind 11cvd.

·1 hR SUUPc,<; ive ~. t rps invO I Vf~ d in producinr, the m<·xin"·l <~i>slnlC ti on of the fir ~;! two exilmples in the concf'r l fonn<1lion l<~ ~.k arc shown below.

• (J) {SM/\LL:l}

(?) ({SM/\LL:J l. {i\110V£':?, DCLOW:I})

(:l) (({SM/\11.: ll. {i\HOVI :?, Ill ! OW: I}), {Si\ME!SI/E:J, SAME!SI/1:2})

(II ) ((({SM/\LL:l}, {/\110VF:2, IJFl.OW:J }}, {SAML 'SIZE: I, ~;AMF ! SJ/[:2}), {~; MALL:?})

• (~i) (((({SI\.~A I L:l}. {Ai lOVE:?, l lUOW:l}l, {Si\ME!SIZE:l, ~i/\MF!S I /1::2}}, {SM/\11.:2}), {SQU/\IIF.:2})

(6 ) (((((U;MALI .: J }, {IIFlUVL:?, lli'LOW: J }), {Si\ME!SIZE: J, SIIME!SIZI .:2}), {SMIILL:2}), {SQUAR[:2)), {CIRCLE: I }) .

., he U1'·e r e i <~ ! ion {SMIILL:c} is selec ted" ' l'ilndom Iron·, El and i ·; then pul int o corrc (.pondcncc with !he c.<1se relation {SMA!. I :f } from f:2. I he pariltnP. I f' r <; c <111d f ilre idcnlifiP.d "'' t:'qui v:. lenl <111d '·O (-:; in· E' c ;md f ilrf' I he fir s! pair of par'11>1cierr, bound) I he pr imit ive <~ 1> ~- lrilclion {{SMIILL:J}} is p, c·ncr;,IC'd. ThP.n lhr pair of f<1'·f' rrlalions {1\ROVE:b, UJ'IOW:c·} ilncl {AElOVE:rl, BFI.UW: f { are put into c orre·;ponclence. Since 1 he idenl ific " 'ion of c wi l h f and of h wi ll1 d i ~. con,. istent with the ~l r t' <~ciy cr. l ;,bldwd binding, 111(' )' rimi ti ve >~b ~; trwtion {{IIE30VE:2, BELOW:!}} i5 added to ·:\Siv1/\LI :I }}. II ~- hould be nnl c> d lh.11 our ba~.ic !M <1lgorilhm ad 11 '11i y finch only ~i x of the eight case re l<~tions <Onc. tituling the 'lbstr act ion. Thi ,; is bc~c au~·e the parliill <·b~; t r;K tion {(TFI !i\NGI.L3}, {L/\11(;[:3}} w<~s pruned from ronsideril lion c.1r ly in the tn>1lch 11nriPI- lhr space limit ation c ow. lr <rint. ., o insure t il <~ t s11c.h cnmp lelne ·rl ilry relations >1r<> not missed, our algorilhm, _.,fter cornplelint~ the process dt'scribed "bovc, searches for <~dditionill relations which r.1n ex tend the <~b!. l rilclions produc ed. Any such re l <~ tions w hich are found <1re conjoined to the abs tr act ion lo rroducc a maximal <>bs tr;,c lion.

Sri<OUTER, the progrilm which indun·s abdradions from c. lruclur i'll destr iptio 1o~·. is only one pilrt of a c ),, ·.r. ificil lion and le<>rninc "Y"I rm wh ich we· ;rre dPvelopinp,. ""'' top - leve l program, c;llled SLIM [11, JO, 16], i ~; a general ~. pa(f~ limit ed interferenc p m;,lching procedure which builds .11.>" t r ,,ct i on~ from ex <11nple·; and then U(,£'S t he"e .. hr;\r ;·r ti ons to cJil<,:;i fy l r~;t ·,;\imuli. Whil e the abs tr ~ction ol feat ure -v il lue repe ~-e nl a! ions UH1 be performed by :.: i1nplr· bit vPr lo1· opNations (which SI.IM it self i~ capable of), ""' .r.c·ner ;llion of 'lb ~- lr >Ktion·; from fJS I ~,, requires the ,-,.,lchitrp, and pilrmneler bincl inf'. dPierminalions di scussed "hove. The prop,r ;,m, SPf<OUH fl, was tr<'alcd for thi s )Hirpo·.c. Once <~ n :.h~-.lrilc ti on is nunpuiPd from some PSr~s. it i!; 1w ;1rly ""complex a p··ol·l"m to use il fo1· ci<Jss ificiltion ···<; il wa"'. to generate it ori r,in~ ll y [1, 11 - 13]. With this in 111 ind, S IJ I~OlJI ER WilS desir.ned to produce two outp11ls: one of IIH} '.'e i:; ;r f'SR, which <~r; we' have indicated can be mill c heel w ith subsequent exempl ars to produce more r e fined ;,bstr ·x tions; the other is a spec ial purpose rc·cognition ne twork .used to exploit on <~bstraction .as a

l emplill e.

1 he tr.mp l <> tes which SPROlll fJ( geliCI'itl es for SLIM Me aulomati cil ll y compi lable reror,nil ion networks or 1\C:Oim~, [1 3, J 8]. An ACORN is a ~. pec i;,l d;,la structure, "quiv<~ l c nt in.· repr esent a tion <~ l power to a PSr<, but ·better ;,d ilp l ecl to serve ils a templa te; il is essentiilll y a F'andcr.ronium pill tern rec.op,nilion sys tem [27], generalized . lo hilndle patte··ns and datil described as general proposi tion <~ ! formul ilC". Once an /\CORN has been produced, SLIM can determine whether a descr iptive PSR m>1 l c h r. ~; it by using !he PSII to UPille an in~. l <'lnCP. l i~- t at l.'>~ch of the lowe!;f-.level nodec. in the ACORN and then :.1 1iowinp, !he r elevant insl <mce!; ol subpil ll er ns of interest l o )'JC' I·rolntc upward in the nel wor l· .. If nny iw.lances of lllf~ hiehes l ··l<'vel nod<! 'Ire fou·rd, II·<' templi11C' is matched l·y the stimulus p;~llern. ·11w lnwesl - level nodes of an ACCH~N correspond lo thr di slincl ca~;c fr;,mes in a 1111i ver !; <'l ll y qu,mtifled PSr~ and arC' lii'.t" lht! fpa ture demons o f a f'ilm.lemonium sy~' l em. A fc;dure demon, however, report s only th0. number of in'.;l.,nrr:'., of its particular ft'rl illr<' to hi r,lwr .. level dcmow., wll t-'re<~c. the node in r~ n /\COliN acl ll all y p<l·;ses it s in"' l <lnres up l o the higher-level nod<'~· whic h il supports. The higher - leve l nodes look for in<; l ilnccc. of !he p;,rlicular conju11< l ion of C<'l';(! relations in which th~·y are inlere ~. t ed, just as higher - lcvel "cogni ti ve drrnons" in Pandemonium look for spec ific combinations of fr;,lurf' ""''"'"'· Thf' i ··i ('. hc~. t · levP I nodr> in an ACORN is in ~; t ant iated if r~nd only if IIIC' ~b·. t r ;~c I ion is matched by the PSR. Thus thi s hi ghcst-leve l node con·c~; ponds to a I ·,·,ndrmoniuln's hi p. ltr·.t - if'Vf'i c np. nil ivr'! demon which · · ( ·c · o1~.nizes when a p<~tlern of intercd is rnr~tc hed. Because 1\COfiNs h;we been deve loped l o p··ovide a means for ·,h;,ring the results of the evalu.1t ion of ~;ubexpressions c.nn·mon to numerous ternpl,1tes, cac II conjunct ion of prpdic<~ l es or suhlernrlales is a<:<soci<J i ed wi th a single bi n;·ry·-br;,nching node who~.c two dc(;cend,lnlc. represent llw con joined propo"i t ionill formul ilP.

Once il set of best r0aximal abs t ractio n ~; i ~; computed for two Or more f'XF'111piai'S, all l r<~itlill [~ exc-,npiili"S (or ·a ~"Hnple of them) m<Jy be ex<lmined to ~-ee if they match the inferred hypotheti ca l concept or rul e. Only lo the extent !hat exPmp l .l r ~ of tile s;,mn cl~c~; rnr~tc h an r1bs lr;,clion and tho·.;e of the other classes do not, do we find ~; uprort for the inference !hat the abs tr ac ti on is 111£' crit er ia! concept lll1fl0.rl yi np, !he tra ininp. d;,t" [9-10). ACORNs great ly f >~c iii I ak I hi ~; ex~1nin<1tion proc t"; ·:;. One (; imply instan ti ates the IPrmi nil l nodes of the IICO!m who~; e highest nodes r c pre"ent the ilbslr ilc lions of int eres t, and then itr-nali ve ly c nrnpull· ~- all in~; lilnce~- of P<lch higher - level node from !hose pilirs o f ins l <'~ nces of it s subordi n;, l c nodes which c .... t·i·;fy cr it e ri <~ l tcsh on their v:~lue~. If " ny in~. t ances of Il l(' ... bslr<~clion ilre produced, the lrilining exemplar millches the abs traction. Withou t IICOiiNs, it would be cx lrcme ly difficult lo determine which positive and ,,..,gidive t ril ining exemplars matched each abstraction.

Ill. THE INTERFERENCE MATCHING ALGORITHM

SPROUTER's function, ils we have said, is to build 1\C(>rlN:; whi ch can he u~-ed by Sl 1M for rPcop,nition. Hefore thi s cons truclion process ran be::in, " set of pr imi ti ve (bot tom- leve l) nodes mu~; t be ~.cnera l cd and then in:; tanti .. trd. To £:CnNate these nodes, SPROUTER reads in the ''"' ' o f ca ~; c fr ames which are r elr>v<~ nt to the las ~. it is f<1C inp,. For eilch of these tilse fr ames, a primitive node is cre,11Pd which is e:;r.cnlially a unive1·sall y quantified case r(: l ~ ti on . SPROUTER then f inch, in lhc· d(,~;c riptive PSRs of two exemplars, the se t of cli~-lincl insl ilnces (ca5e rel ations) which <~rc instilnccs of each of thc:;e nodes. Each node hils two "5sociat ed instilnce li sts; o~ch of these li st s contains the instances of the C.il~e r E' Iil lion for one. of the exemplars. lor exilmp le, given the two cilse frames Nl: {CIRCLE), N2: (AHOVF.:, BElOW) ilnd !he two exetnpiMs

E5: { {C!RCLE:a, C!RCLE:b), {ABOVE:<'~, BF::LOW:b})

E6 : { {CIRCLE:c} }

SPROUTER will create two nodes, Nl and N2, and then rroduce four ins! a nee lidr. . Two of these li sts, ([E5/a], [[5/b]) ond ([E6/c)), ilre <'~ ssocii)tcd wi th noclo"~ NJ. The otll e> r two, ([f '::> / il, E~i /b)) cltld ( ), ;1re <~ssoci:1l ed with node N2.

Whr n the pri1nili vP nodf·' ;> I1<1Ve been inslnnliated, Sr'fl()lJI Efl produces 1118 SPI of IHilXimil l abst1·actionr. Of the I wo PS I~s by construe I ing, bottom- up, a bin;11·y-br;mc hing ACOfl N. F;o~rh highPr ·· l t ~ ve l node of th i~. ndwor k is a conjunction of two nodes, 01w of whi ch is nlways a p rimiti ve node. Before inili ;1 lin!~ the bui lding proce~;s , Sf.'I"IOlJI FR deletes all of I he pr imi tive nodes !hil l do not h;we il l leil-::1 on€' instance from <'ilc h exE'mplar. Then one exemrlilr, the one with ·fewer inslilnc.es over the rcm;~ining noclC'r.·, i ~. lar.r,ed Ei 1 l ro; the other exernplilr ir. t .. r,ged ~c,o ,._ /\nd eilch inslance of [in l ro is milrked ilS unused. . >I 'tJI)t.Jf[fl tlw n bc~ 111 s the ac luil l consl r ucl1on. An unused r·inlrp inslilnce f rom <'I primi li vr. 110de is chn<.r.n 8C. One of lllf' !wo insl <1ncc<. to hr u:; r d in the cowdruction; it i.s ~P I Pc l cd on the b<~ <. i s of tl1c· lil'.clihood of ih being an 1 nc, I ilnc e of il node which i~ '" cow. I ituenl of il hcs I maximal al >sl r;ocl ion. T hi ~; ins! arlCe i<:; I he-·n paired wi th eve r y i n,·;t ilnc e I rom Ei 1 1 ro 0f every node. f ar h of I hese pairs of 111 -:; l<mrrr. is u~; ctlto con~druct i1 Cilnclidate node which w ill ilCC "PI ins! i'lnce pil ir '> onl y if thry ;1re t·qui vil lent to. !he pro toty pic poir. If there is il l lea,. ! one suc h pair of in<; l ;mc. es in [ conlP'. the ondid;1l e node is. added lo the ne l worl\ ilnd " 11 1 ~. 1;\llCf':; of the nOel!' (frorn both e,·x, ,,-,plilr f. ) ilre tompute->.cl . Thu·; , CilC h ~d ep in the <>b·.dr;,c lion building process invol ve:. combining, iterati ve ly, il ll 11nt1sed in ~ Llme from i1 primiti ve nodr> wi th each other ill'd<lllce in the ACOI<N. 1\ ft er Cilt h of tlw resulting ro11jund ive nodes is generil l cd for a pair of instances from F intro· illl insl<1nces of I hill node, lird from Ecornp and then 1_1 0111 f:.i h·o· are comput ed. 11 no 111 ~;! nncec- ilre found 1n Ec 01l·,p· \l1e node reprc:.c nt ~ ;~n ab~dr ;K iion that is not true of t w second exemplar and ~. o th() node is not <1dded to thr> networl\. The proces>< continut·!; until il ll of the case r el<1lions !hilt are common to both exemplurs have been c0njoinecl .

Of cour se, thi s il lf;orilhtH, left unconstr ained, woulci build il node for each subse t of c;,se rc lil lions in E· 1 . 0 for which there Wil<. an equiv<~ l e nl subsd in Ec.om'· 11 ~/car l y , the !.lze of the ~;ea rch ~> p a c e would increil~e ex t~onc nti a ll y. Thu~ .· for even srnall problem~ .· it ir. important to somehow r educe the number of nodt· ~. c0n:. l rur..led. We use two lle·twi ·dics. The fir r. t of thPsr Pn'lblrs '" to keep the se<1rch space to a manageable. size by p1·oviding for the ilul om:'llic pn111ine of tho~.~> ronj11n c. lion ~. l cil~. t likely to be p <i rl of a bes t maximill ab<. l r<1cl ion. To determine which f' il rli <ll <~b~. l ractions ilre lt:'iiSI promi sing, a vil lue is comput ed whic.h we Cilll lh0 utilit y of a no<lc. Flil~irillly, the utility of a nodr> is an increw; ing funtlion of the number of properlier. covered hy the node and il decreasing function o f thr number of dis lind pMamclcr ~. needed to · inst<Jnlial e tlw node. More spccific.illly, our cur r~ · nl utility measur-e i1dd<:; 1.0 for each proper l y of a case rPiillion and subtract s 1.0 for each di stinct pilramctcr in the ilssociatcd PSR. Our justification for thi s rather rough rneasure of utilit y is that it will y ield as the highes t va lued nodes, those with the {l: I"Cil l e::; t scope ilnd connectivi ty. Equi vil lently, the higher the utility of a ·node, the more informative and apparently "better" it is as an abstraction.

During the constr11clion of the ACOrm, a li st of all IV>de ~. currently in the network is rnaintainPcl . Thi s list, which is ordered by the utility of ih clement s, hils a stipulill ed rn<1xirnum lene.th. Whenever the number of total node~; in the ACORN exceeds thi ~~ slipulill ed m;,ximum, a pr imiti ve node which does not support any higher-order nodes is lllilr~.e cl as removed f rom consideration. If all rrmaining primitive nocl t>s support ·;orne higher-level node, then the least valued maximal abstraction (provided there i·; more lhiln one m:->x im ~ l ab··.traclion in the nC' Iwor l\ ) and " II nod"~ ~. uportinr; it (0r s11pporlinr. on·· o f it ·. supports, I' Cc'CUr !.;i vely ) <t nd not suppor lini', .,nnw other hiRher valu".'d max i mill <>bsl rae I ion arc dr·lc iC'd (nr m.1rkccl il S removed from C0 11 '. idc r il lion if lhr.·y ilre pri1..-.iti vc node:;). Th11~ .· !he lltllnbc~ r of node:. in the IWi wor l\ c:-111 c>Xcl·r.·cl the ·dipul ated rH<>x imum only if just one rn :1xim'l l ilhslr<>clion remains. Whil n in !>Ome Cil~>es , it 111i p, ht be d<e'. il"ilhle to require thil l <>I 1! ·<· ~; 1 i', (k> 1) bwd m<txim:-11 »h·. tl·il< tinw; be rn;, int ained, we ll:'IVP not yet found a nP.ed for I hi s opt ion.

A~.; <> r C':;ult of the li rnil <l l ion on norlcs in the ACORN, I he I y pic at behav ior durinr, conr. true t ion is as follow~.: In ~ ! <l iKC'· ili"C in! I'Oduc rd One- ;d -<1 - l imro from f:i nii'O and ill"(> conjoinr rl wi th olhPI" Fi 1 tro node· in·; l ;lncec. In form PSIIs r r prp r.enling subse ts 0 / r il~·e 1·elillio115 of v~ r y ing utility . /\ ~; soon <15 the numher of node:; rnrr c'.ponrlin{', to these node· ~. in I he> ACOFIN exceed'; the rdipul al ed n···x imum, I he lt l ;winl il l node with the lowwd. utilit y l o~;e lhe r with all node·_. whi ch ~. upport onl y it :>rc deleted f1·om the network. I hi ~ conr.t r uclion - ilnd · pruni11~ cyclr is lf!pc·'" ted until the se t of bes t ln flx imal "bstr ac tions h,lr, been found.

The ~r>cond heur ist ic prov ides lhP r.<-> ilrr-h with direc t ion by indi cil ling wll ic h one· of t lt r> um'~' '-'d in~ t anc:es i·:; to l:w used in the next eyrie of tOnsln1tlion. Our search for the best max imnl ilb ·. l rac lion ~. ir, r'c.sPnl iil ll y hill r l in1 l.>i ng, but occur ~; on many hi ll s (; imult aneou<:;ly. Since <JII r pruning heuri sti c enabiP:> us to main tain a gr aduall y dr ~ neil~; ing ntllnber of max im,1l ;obc. l rM i ion~ .· tltr number of hill·.. under con<;icJer;,lion i ~ r t·dtlced il>· the search p r o:~ r esses. Clear ly , if we cou ld sc l<>c l f ir ~ ! il ll of those in:. l »llccs lro1n [i ntro whirh were ill'd ,.nccs of the bes t rr~<> >< in1 >1 l abst r iic l ions (I he hight"· ' hill !. ), th('n our search, '; inrt' it would l ilke plilre in ;_111 r: ~;~. r · nliall y unimodal space, would he ilS effi e icnl <> ~ po ~ ~. i b l r. Of cou1·~c it is impoc.s ibiP to dPi ermine a pri ori whirh instance's flrc ill··l <lnce r. of the bes t rnilxima l abstr act ion!'. However, by u-:; inp. '"variant of the utilit y function dcc.c ribcd above, it is P"'·~. ihl p to c ornput r, I air ly r hn.>ply , II 1P upper bound of the <>< tual utili t y of nny node whi r h rtli p, t.l bl'> con<;trudecl. l h in r~ thi s slrill ep,y , we c.an, ;d rc l <> li ve ly little cost, ~. i ;o. nifir ilnll y increase thr proh,t!Jilil y lhiit the node < n1v:dr uded will be a constiluPnl of a bw> l maximal nbsl rilc lion. The se lec tion procr~ durc we ur;c is ilS ·follows: We ~.c t il s;~ mplinp, f 'lc.tor (t iiiTenll y 1'01) for the proportion o f the tlllUsed in·.;t ances fr om Eint ro whi(h are to be F.'Xilmined. We ~.e l ect at random th is percent of the unused instances (but ill leil:.l three unlit lhNe <~re fewer than three unu~;pd inslame<. ). For eilch of the in~ l<~nce s in thi s ~'illllpl e , we delermi1w an upper bound of the utility of all of the node~; which could br con<. l rucled by conjoining the <; a1Hpled in·; lanc:e w ith the rem<>ining insl ilncc·s of nodes. still umler c on~;ider at ion. The one ins I ance which produce:. the node w ith the hi.ghc·;t potential utilit y i ~. conr,lrut tcct.

ThP- actual conc. l r llclion of il node> i ·; il two step prore:.s. rir " t SPROUTCfl c rea t e~ il c.el of l cds which ilre both · nr> r-Ps<. ilry ;md sllfficicnt to ilrcept just those i11 <:; l ance'; that ilre equi valent to the pair of instances used "'' a model in builrfinp, the hi p, her - lcvc l candidate node. It ic. po·.·; ible to rre<lte such :'1 se t of t c~. t s wor ~. ine. only with tlw ·;;lmc>ness or differenc e of ·;elect ed pitrameter s. For exmnple, .to con~truct ;~n /\CORN node to acct:'pl 1he two inc. ! Amcs {Cif~CI.E:c) ilnd {/\HOVE·.:", f:JFLOW:c}, a same t.><1nllll t· l er (SP) tes t is generAt ed to insure !hill the first p.1r a1ne ler of the fir st ca~.e relation i ~. the S<llne as the second parameter of the second re i<~! ion, and " differen t fl<ll' ilmeter (OP) test is gcnerilled to ins ure~ that no non-Pxplicit SPs are accepted. II one thinks of thi s ACORN node ilS being constructed from a left ilnd a rieht ins tance, where the parameter of the le ft instance is number ed 1, <1 t1d the parameters of the rip,h t instance are numbered 2 and 3, then a minimal complete se t of test s needed to r>:;-~ rll y ITj.1 r r.~.r nt thr ~;a mr> ;111d cliffc,·pnl relation~ are \Sr' :J, Sf':8} <~nd {Of': I, fJf':?}.

Aft r r thr ~. ct of t c~ t ~; h il~· l:>cr· n < rr.,l l cd, ·the < <ll>did <ll <·~ node i<; w;~.oc i akd wi th a l',t' llf'rdlor se t which ~ . pccific <; how tlw p;1r .11nc tr 1 ~; of i t ~. il1'dam e·; <1 re to be r>.ll ;,r l rd from pilir'; of '.uhoulin;ilr in <, l ;mcr·~ whirh s"lisfy II"' nodr·'', Sl' and Dr' lt·· .. l ,:. IJPCilu··' of the implicit l·rquil' f' lnr·n l for Dr' r e lali un~. l o hold Oil all di stinct P" l .. lll)(' l cr~;, llw order of tl1r' 11cw r r l;ilinll i ~; cx"cl ly the nur.oll('r of di e. tinct par8mct <' l ~' in tht· two rel <1 lion instanc es t";cd in buildint~ llw node. In llu' above px"mple, there wo11l d be two f' <J r amclcr:; in r;,ch iw. l ;111rr of the new node .md lhr><.p wot dd rorrr".pond to J.l"' '"''r·l (· l·r. I ;,nd 2 (since .1 <1 nd :J <II e id r· ntir <~ l) . ·1 hr I~'' IWI' il tor li· .t for thi s node would he j iJ'd (I ,2). From I hr n;, tur r of the 0xplic it SP and Ill' tr"d ~ w.rd, it follow··, !hill ""Y two node'' hav ing in<d;li>Cr"; ck·r ived from cqt li v .ol c llt p;~ir '' of i n ~. t ances must be equi valent. Whcncvc1· such a duplic;lle node is ronc.ln1ded, it is removrcl from the 1\COI<N.

It ~. hould he <>ppilrenl tlv d an /\COliN con ~;( rue led in t loc LY.hion drscr ihcd <1hovc will no I "''< ,,~~~ ril y conl·i1ill a lo\,I Xinoil l <1 IYd r<tc t ion. Wlw t lu" nr llOI it wil l is p<~rli<>lly dr' t>endent on what max in1um h .1~; b0en ~:t i p ul nlecl for the 1111mhr r of nodes in the /\COtm . l lut r1.1Cn if the ~. tipul <> l ed tn>W illl l lll'l i ~; lar gr· enough so that the hi ghp·,,t node in the /\CORN is " constituen t o r a milxitnid ;1bslr ilc tion, the /\COf<N lll ilY no t be compl r te; th ;d is, some of thr Citse relation~ in ll1r' ;1hslr;,dion may h;we been ln ~.t . Thi s cil n occu1· if one or n1c>rr. primiti ve node·; who:;e in·; t allce:; <t re a part of the ;1hcd r ;~c li on were r emovrd frono cow.idcrilli on c~rly ill the cow. I ruction proces~. In ~- ti C h a c .1sc, howcvr 1, it is alwilys po'"·iltle to ex l c lld the /\COliN with conjumtions of these ln·d primiti ve node ino: l ;m< cs. Thi r, i:. donr by succec.;sively n·int 1·oducing into the ronr. lruct - il llCJ .. pnlllc eyri e eilch ill ·;\ ;"JCf' in E· , 1 ,. whi r h do"~ not ·;uppod <1 ll of th~ "''' lill > rc·~; of all of the higlte·.t nodcc. in the 1\CCH!N. Each rr· · inlrodllr.cd inc. l <t llf C is ronjo i1wd 1.1,1 ilh c.1rh of the iw.t <>mf"' of !"ach hi t; IIP,; I node to produce candid·:.lc 110des. If in·_d,lnce'' o f oilY of lhf'~' <' new obslr .,< ltons ;11·<~ found in Lc(Jno/:> ' lhc,.e nrw norlr·c. ilrr rr· l ;~ i1ir· d; the 1\COI<f\J is then PX1c· l dc-od fur ther, in the s<H>w Wily, ulltil the bw. t maximill .-dJ'' tr ac t ions have been found.

We h nve <>ile.,dy ''<'rll til e' ;dJs tr adion SPROUTEf< row. tnlcl s given the fir ~ t two exempla1·c. in the fir st <Otl<cpt form;, lio11 t ac. k. The c;c t of case friln1es from which tiJr' p rimi1i 'l<' node~. were crr<Jt ed, <~II thrrc cxc-- mpl<~rs, ilnd llw 1><:";1 tn <~x ilnal ahstrilction fnund by Sf'IIOlllLR ~rc given be low.

CF: Nl :{CIRCLE}, f\J?:{SOtJ/\FWl, N~l :{Tfii/\N�LE}, 1\JIJ:{LAfiGE}, N! .>:{SMALL.}, N6:{1NNEJ<, OUTER}, f·J7:{N 30VE, OELOW}, NR:{LEF T, RIGHT}, N'J:{ SAME !SH/\r'E, SAME!SI IAf 'E }, N 1 O:{S/\ME!SIZE, 5/\ME!SIZE}, Nil :{BFS IIlE, BESIDE}, N1 2:{CONTIGUOlJS, CONTIGUOUS} l [ 1: { {TRIANGLE:,, SQUAfiE:b, CIHCLE:r}, -:J_/\RGE:il , SM/\LL:b, SMALL:c }, . { INNER:b, OUTER:a }, { AllOVF :.11 , AElOVE :h, ElELOW:c }, ( SAME!SIZE:b, SAME!SIZE:c }}

E? ~;()UI\ f iL:d, Tlli/\N(~U :c, CIRCLE.: f}, %Mi ll :d, l.AI/(;1 :r·, SMA I I :f }, I NNIJU, Oil I L.rl: r> }, /\130\/F :d , RllOW:P, flU 0\AI: f}, SAMU:·>IZJ:: rl, SAML!SI/f::f l} E:i:

{S()U/\ RI::g, Cli?Ct F:h, C I I7CI I~ :i }, {'if.~ !II I :r!, I AI ICI :It, SM/\1 I :i j, {I NNI.Ii :i, OUTF.Il:h}, {1\ClOVE:p,, OLLOW:It, Oll OW:i l. { S/\MI 1SII!II-'I- :h. SliM I !Sf i/\Pl· :i },

{S/\MI:!SIZF:g, S/\MI : ! ~; tzE:il}

1·. I ~ I ?,·f· :l : {N 10:{ SAME!SIZE : 1 ,SAMic!Sl7E:?. }, {Nl:{/\130\/E: 1 ,ClEl.OW:2}, {Nl :{CIRCI.F :?}, {1\i~i:{ SM/\IJ:l}, {N!'>:{ SM/\LL :2}, :N? :{SOlJ/\FI[:l }, {Nil: { l All[;[::l}} 1[\J ~; T/\NCF~i I ROM FXlMPL/111 L.h l. 2 <lr: 1 ,, r:2 / f' .r: hr:?. ; t .rc t *r::~"r1J) H,JS I ANCI-.S I ~10M LXEf.~PI All I :l

([ E3/!·. ,l :l /i,E3/h])

SPFIOU I U< tool\ h ·;ccnnrh of < pu t imc nn il PDP-- I 0 (modr-·1 K/\ - 10) to prodtlcc Eht. ?. wh it ll it found <> Iter <on:. truclinr, 111 norkr. (7 mnrc lh;m l lf'CCS~·"I')'). SI'I{()Lf!Lf( l ook :l ~.econds ;md ron,.t, udr·d 6 node~. (I he fewe<:t po·. ··;il.>l t>) to produrr·' ([I ;T?.hL:l. ·1 he <>hs lr a< lion ~; l'llO l . rt [!'( found, however, lhou;: ll it is the best .l hc. l r;,r lion pmducihle tl'.ing out: rn"trh .. fir c. t IYoelhod, is not 1'1\<JXim;:.l. It is mi,_.s inr, two cao:;(> rr·lation ~; . /\ c. we indi ca·ted in the fir ~:l c;cc ti on oi the p<>jWI·, the aiY;lrnclion SPROUTER induces i ~. lhc followinp,:

l here <> re ll11·ee object s, in< luding a small ci1·cle ·and <t c: mall c; quilre. The square is ilbOvr? the circle. ·r lw third object is larg<·' .

Thr best ma.xirn<1l absll·ilctioll incl ud<'s the ·'·P'' < ific at ion lh <1 l tl11· la1 · ~'.P ohi<·rl conl:'>irv; a not her one w hi ch i-:: one of lite two sm<1ll objN i s. SIJROUTER is unilble to find I hi -:: ;, hslr <>cl ion for two r c<t~; c>n~:: (I) The grain <dze o f thr r cpr r>·;r, nt <l tions u·;pd in dcc.crihing lhe l'X<l lnples is lno l.>i r, ; 1110r r· il tOn)ic unifor111 represpnl iltions ilre needed to rn ;ll<.c al.,;traction, which i·> a ~ !1 icily subtr act ive proccc;s, 1n01r> p:<" nrr ,1 ll y ~pplic <tb lc [I t, I!>]. (?) M;u1y · one p<>nHn<' lnr correspondf.'t1Ct'c. tnu ~d be nllowed in order to inc. ur c that rcl cvonl corrcc.pondenc c·: <1 re not los t. These I wo problems, whose r.o lut ion rr.q11irr s mnt hod c. of r,1·eilter t~ '.' tlt'r <> lit y th<m we have> currentl y implernentec.l, are cli s( us~ed in detail in the CMU trc hnical report from which I hi s pilpe r is I a ken.

IV. CONCLUDING REMAI~KS

Sr'ROU1 ER has already solved teaming problems of tl1cor c liral signifi c;, nc e and of con,, idcrnbl c complexity. l lPu>w;r· of the extensive si;:c of thP se ~rc h ~; paces , such l p ;~rninr; could not be done with simple enumerative lil;Jichinp, illgorithms. In cs:.cncc, SflROUTE:R ec:lablishes the fpa<;ihilit y of induction f1·om non-tri vial exempl"r ciE'scripl ion,:. In many rc c. tx·cl ''· however, SPROUTER is quite primitive. It is il purely c;y ntacti c matcher; it r.nows nothinp, at all ilbout the undArlyinp, ~.trudure or significance o f ilny of the pre di c;~ l e de~.cr iptions upon which it operat es. For this reason, it s utilit y function, and thus its heuri stics, i1re VNY weak. One interesting i1proac.h to i11>prov ing the performance of SPROUTER would be to prov ide it wi th dom,·in - spcr ific utilit y function~ . For ,.., .,npl r·, if SPII(llfl Ill i'. ll<'W lh,1t rO!lcorrhlll< e on ,,,,,., '-'"'-' "' nt c ow. r ~ q11· · 11l rr.' i >lt inll ~· ww; 111nrr· itrtporlanl lh;m ror1tOtci.lllCe 011 mo ~;l <.>lhc·r rr · l ;tliotl ~ , il would never :1 llr·n·pl lo rn<tlch lhc ~ lll r· rc:dr· lll p ;, t·l of an PY.nmple with a. r '-"' '·' ·' ' 11 tr ·nt p;,rl. Sitnil<ll"ly, if it I·. new I hill rom ordanr p of hi f, hPr ··OI del grr1mrncdic0l CIHV~ Iru<. l ~ . (E:'.r,., a ~·e nl enc. e) was tno t c ,:.ic. nific <1nl th<111 conrord;II1Cf ' 011 lowe t···ordet· ones, it c ottld qtticldy ;~rro in on lite ronrord.111rcr. of two ~;e ntenc:e ·, I rt rr I urer, ilnd I hen COlli i11uc buildlll [: ~h ·.drnclions in an r -:;·:.r·nliilll y top- down fil:.hio11.

F. vr··n I ho11gh SI'R( ll IT HI'~. pPr fortn i1 1lt e h<~s been q11ilr- irnpre·." ivc on sc vcr<tl L1s l·. ~.. there ;,re three dd fi r ' d I jp -:-, irnprdiDg t hP u ·,f) of ~·, uc h a lf'-·;u·ning rnnc hine in '"." "''~" " I <~ pplic <l liow.. Fit · ~. I. ;i 11 N npiri c al quest ion hns been 1 ;ri ·:;r·d r q~ Mdi11g ·t he· prefer .1bilil y of ;,ppro<tches to tnd t tr I 10n /i;, ·.rd nn I hn 011e CltlP and milny one binding .il lr: t ll <t·li vc"' · If ohjPr I inl ·.' :·,ril y in rc·pr f""·"'l ;-tliotl '' ir. ~ ~r· n c · t · ;, ll y lr·nuow' -- lh<"tt i~ .· if r; ;,ch objcr.l in Oil<' I 1 Sf( ciltl ''" t '"·POnd to tnttlliplr' , di ve r ·,.., ohjN t··. 1n ~11othcr PSr~. <1 <. ''-'"'· tile c;~·.e in lhP <Oilf.l'td fonwlli oll lw.;v, dc· .. cribcd .ii .H>vr· .... allr.lr ilC I ioll proccdttre,:. b;,·.cd on II te tn<~ny · · onc ' 'I 'I ·rn ;"r< h will '"""' to br' clrvc·lopr·d. ~;ccnlld, OtiC' tnuo. t ~<l· · t~lif y whir It rr··al · wnt lei I" ohlr,· n,·; <.<111 lw ,_: olved by i11 \ 0 rf P ff' ll ( (' mil \ching IIH7' fho(h. i3P( Clll~·f' \hr C c] ~; e fr cHne~ w it it h ~; PIIOl rt lY w .c·r, tt l infc·r ri11p. ilh·;\ r itr lio11s me "'·"·' """ d to br> ex !f't fl ,_,lty pt ov idr,cl, II" ' ttl iii I y of our b~·: ic­ ''"'lirnd clepc nd·; upnn the prior idcnlifiu tlion of useful I"" npc·t ti c~ .. Third, wllilr· ~~r' l lillll L l~ w;co wh" t i~. b~·,icnlly a c Otlltiron lleuri ·; tir ~"''" c h " '' .tlq:.Y in /\I (hrr·adlh fir !;! with J>rttnillg of low- v iliUP.d p ;1 lh'.), it i!. ,, fill too expellsive to be w idely ilpplied ill pr <~c ti c ill probl c tr lS.

fiEFlYENCES

1. l ~>~n nw , II. G., 1\tnhlc t·, /\. 1'., '""I [1ur·. l <tll , [(. M. Senne Icc hllique:. for rc·coglli ,' tnt.', ~.truc lurcc. in pic l ures. In Fronlicrc. of P;dltcrn l~eco t; nilion, S. W" t ittlr~he (Ed.), fie ;H ir·ttric r'rr·;··;, f\J·. ~ w Yori·,, .l 'J/ 1'.
2. l'. 11ohrnw, D., and Winor:r<td, T. A knowl edp,e rc·prr .. -.r·nt .. llion \(ln ~,,u;lgr~ . Cor.nitive SciPnc<?, in prc~ c;.
3. ~l. llrll tr r·f", ..1. S. , Condllnw, .l. .1., '" 'd 1\uc. tin, G. A. A Study of ThinKing. Wilr·y, New Yorl1, .l ~.1!:·6.
4. l l ltr ;"!.'\ J, .1tKI Hnyer.- llo th, F. 1\ nove l p .1 tt em leMnillp, :md < lw;c, ifir. ;, I ion pt·ou·dttrc ~pp liC'd to llw lr·arning of vcr wr l ~. . Proc. of the 197(, l.C.C.E. Inll. Coni. Ar ou~ticr., Spooch, and Signal Procn,;!;inr,. l'hilildclphi-'1, l 'l / 6.
5. r). l.' rn·.t, G. W., :1nd 1\IC'well, 1\. GPS: A c~~f' Study in GP.twralily and Problem Solving. /\c adernic Prc ~.r.. New Yml·,, J 969.
6. 1-. v<>nr., T. G. 1\ pror·.ntrn for lh0 solu tion of r.comclric - ;,nalorw tc·d quc". lions. In M. Min,:,ky (Eel.), SPtl1<111tic lnfonn~tion Proces,;inr:. Ml"l .Press, Cambridge, 1 %8.
7. l . f it·,cs, R E., ;md Nil !'"on, N. J. STRIPS: A new approac h to the e1ppliralion n( llw or0rn provin::.. to problem ·;nl v ing. Artificial ln!PIIi ~:r· nce 2, ( 1 ')71 ), 139-208.
8. ;::. (;;:,lion, F. Inquirier. into lluman Faculty and . its Dnvelopmcnt. Dent, London, I '.JO/.
9. 11-. yp ~; -- f~oth, F. 1\ ~. tructtJrii l '''I'Pt"O<Kh to . pattern l r;,n1 in~ ;md the r~cqui~; ilion of rla~;~; ific<llory power. f'roc. Firr.t !nil. Jt . Coni. Patte-rn l~cco;:tiition, .197:1.
10. J 0. ll<~yp ·;- J(o th, F. S<lwm;il ic rl;~s !:' ifi< it t ion problems and llwir ~. olulion . Pallorn R<)cor,nilion 6, 2 (0< I. 1974), I 0!) -- 114 .
11. . 1 J. 1-l .t ye··; -- l~oth, 1-. lttndm"ent ;tl mc·c h;.oni ,·.tn·. of in!P. IIigent l·eh;wior: I he r epreoenl al ion, orgitni z at ion, <~c qui·; i lion, ;mel u~c of s truc lur r~l 1-.nowlnlr.c in pC' rccption r~nd cognition. Ooclor~l lli ·,, ~ert<~tinn, The University of Mic hi ;~it n, Ann Arbor, 19711.
12. H<~yes-Hoth, F. An optim<·l network representation and
13. rdlwr tnerh;,ni·.tw. fnr the rr·rop,nilton of ~. lrttclurcd <' '-" ' ' "' ~'- Proc. Sncond Inti . Jt. Conf . Pat.tern R"cognition, 1 'J/11.
14. l :?.. II" Vf' ~;· Fio lh, 1·. l ~c pt · r · ·.c· nl ;llion of slrttct"tJred event·, ;·11od C' flici (·nl prnu: rltJrr " , lot· llw·ir n·cognition. Pattern R!'cor~ nition, 8, 3 (/\u;7, , I 'l76), JIll .. J:,o.
15. J If. lt;·ry e·;-1/olh, r. l'allcrn·. o f indllclion ;mel <tc.~;ocia l e rl IU H1 \A.' I (·' rl ~~,( ' ~c qt ti ·;i t 10 11 · rd!._·,nr i I htn ~.;. r\(·cor: nition ~nd Artifici al Inl r·lli t;f'nco, C. fie ildc nri c Prc ·.: s, New Yorv,, in pr<;','·'· In Pattern Chr>n ([cl.),
16. .1'>. ltil)' r,··,-Roth, f-. llniform r r: prP '.I' nl;~lion~; of r. lrttclurced p .'dl,..rn·.. ;tt1cl " " >l it·.ot ilhtrl fnt the induction o f <on! in['.(;nc y - rcspow;c) rule·; . Information and Control, :ll', (.l<J/6), in prr ~ · ..
17. J 6. llilYt"' · riot It, F., <1nd I·J1.tt i'-''· J. Chat :tc l·~ r i zing · ,.yllablr~s tF_, scqur::-nc e~ of n1Cl( hinc -p,r~ nP r ulcd ltlbc11cd !;egmcnt r; nf connected ~. pr' Pc h: .., c.ludy in ~.yt rlholic p~ttern lr··i1rnint; '"; inr, " conjtttlt li ve (Paturc leilrning <~nd r l .1ssifi· ;olion sv~; l c m. Proc. Third Inti. Jt. Coni. Pattern RP<:op,nition, l fJ/6. ·
18. I "/. ll.;yp,_, .. l iolh, F., Lt tnan, L. D., l"ox, M., <mel Mo~:low, D. J. ~;)' nl ilC I ir proc r-s·;inp, in 1-l e.lr~; ;, y · II. In Spcrch unde t ' . l anding ~.y ~. l c r" · . : ~. ttn1tr1<1r y of rec.ulls of lhn fi v(' · yP<H rr" .<'<Hcil r:ffnt I. i.lr.·p:< rltHPnl ·of Computer ~;ci(' ncr , CanH~t: i " lvlr·lln11 Uni ver ,; il y, l'itt ~. bt.ttT,h, .l 976.
19. .18. 1·1.1 \'e';- l?o tlt, r.," " '" t Mo ~dow, D. J. An autotn.llic;,lly u or,pil ilhl r> r PCO[·,nilion nC' IWOii', for ~:lrttclurecl piltlcrns. f'roc . Fourth Inti. Jl. Coni. "Arlificial ln\clt il~'mcc, 19/5.
20. llir ·;chtmm, L., (.;r ir. htr1(1tl, II., ilnd S<l t), C' r, N. ( ;, '"""' ic ,, ll y · ba~. ed ntt i.Otr"r;'l l i< wo t·d cl;, ,;s form>l l ion. lnfornwlion Procc·!:,;ing <mel MrttliiJ;onwnt, 11, 1- 1' (Mar. 19 / 5), 3 9-5/.
21. /0. I It tnt, f-. fl . Concnpl Form;i\ion: An lnfonnalion F'roc(> r.~ in r: Probl<wl. Wik·y, Nr ·w Yort1, J 96".
22. ? l. Mi c lt ,l l ~. t·, i, R S. /\()V/\1 ./ 1-- -Cotf·PUi e t· it,lplcrncnl alion of <1 v.1ri;,hk v., lurrl lo [~.ic ·.y,·. t r~ tn VI J ittHl r;x<ltr·rples of it s ;qrplil<llinn to p<~lkt· n t ccCrt.',nilicm. Proc. Firr.t Inti. Jt . Conf. Pattern R£'cor,nition, I <J :n.
23. ??. 1\~ttl ~. l ·,)' , ~A A fr;llnc·wof"i·, for rcpt·c·.rn!illf, l·,nowleclge. Ill ThA p,;ycholc·r,y of Cotnpul"r Vi !;ion, 1"'. H. Windon (Ed .), McGrmv - llill, Nc·w Yo t·i<, I ~/~i .
24. ?:3. Mnor c , .1., iltld f\Jr·wcll, /\ . I low < iln Merlin unde r ~. land? In KnowiPdt;·! and Co,;nition, I . W. Cregg (l:.d.), Erlbaum, f\l,.w Yorl·., I ')711.
25. ?II. l ' lnll, in, (;. 0. A not e 011 inchtdi vr: w· nr· r;,lii' <~ lion. In M,1chinP lnteltir,f.mce, vnl. 1 :>, ll Mr, l t?r·r illld D. Mi chie ( F d ··;.), /\n1r>ric ;tt1 Fl ">~.''-' i "r , Nr·w Yorv,, .I 9/0.
26. Plolllin, G. 0. A further not e on inducti ve ~·.enC' t "i't li7illiotl . ill Mitcltitw lnlnlli r,encc!, vol. 6, Fl. Hr,·lt,-or and D. Mi< hip (Ed·d, /\rnericiln [l~;evier, New Yorl<, 1971.
27. ?G. lir·r·d, S. 1<., Ernst, C. W., '"'d 11<~ner ji, R lhe rol e of "'"1lo ;-~.y in lr ;m~; f p r he lwr·r··n pt·nblc·m ~. t<~t es. Cognitive P"ychotor.Y 6, 3 (Nov. 1 ~) 711), IJ:'l6- IJ"i0.
28. ?l. Sc· lft ict ~·. r · , 0. (~ . f';,ndr~ rnon i tttfr: il p<~r.<di ~·.tn for lc!il rning. ~; y rrrpo :;ium on the' Mr·c ltani ·.:1 lion of l hough! Processes. II. M. S l<~lione r y Office, I <"6'J.
29. ?:-:: . Slt:lW, /\ . C. Pirlure p,rilph~ . i '. r ;t ; .,"""~"''· <1nd p.1rr.ing. In Fronlit->rs of Pattern f~ <'~o 1: nilion, S. W<1 l<111be (Ed.), fi e <tdr~ tnic Press, New Yorl1, I ~1 / ? .
30. ?9. Stoffel, J. C. fl clil:'''ifict d.-:- ~. i ;·. n Icc hniqttc for di !.cretc v;·,ri<lhlr· pilller n rpr o :.~niticltl pt ohlr·rn'·'· IEEE Trans. on Comrutcrr. C-23, II (/lpr . . I ~1711), 11?8 - /f/fJ.
31. ~-J O. Tt t' li ;,lwff, /\. Computer· genc r ;,[cd word clil';sc~: <tnd !·f'lllf'mc> strudtu·Ps. Infortn<Jtion Proce!;!; ing 1974, Proc . !Fir Conr,rer.r. 71!, JfJ711.
32. :3 t. Vc rc, S. fl. Induct ion of concept ~. in the prcdic;,le r;olcu lur.. Proc. Fourth Inti. Jt . Coni. Artificial lnlellir;<!nce, 1975.
33. Winston, P.H. Lc<~rnin p, ·.lruclur al descriptions from C'Xittnple<:. In The Psycholop,y .of. Computer Vision, P. H. Winston (Ed.), Mc-·Gr;,w -Hill, New Yorr,, 1975.