%!PS-Adobe-2.0 %%Creator: dvips 5.497 Copyright 1986, 1992 Radical Eye Software %%Title: q.dvi %%CreationDate: Fri Aug 12 11:55:50 1994 %%Pages: 9 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: /usr/local/tex/bin/dvips q %DVIPSSource: TeX output 1994.08.12:1155 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N} B /TR{translate}N /isls false N /vsize 11 72 mul N /@rigin{isls{[0 -1 1 0 0 0] concat}if 72 Resolution div 72 VResolution div neg scale isls{Resolution hsize -72 div mul 0 TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{ CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N} B /I{cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook} if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255 {IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V{}B /RV statusdict begin /product where{ pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{ gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{ p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{/CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{10 div /rwi X /rwiSeen true N}B /@rhi {10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{ }N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp{pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray}N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale false def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{ SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial{CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{ rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath}N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin}N /@fedspecial{end}B /li{lineto}B /rl{ rlineto}B /rc{rcurveto}B /np{/SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (/nfs/011/people/wcohen/papers/ml-90-axaebl/q.dvi) @start /Fa 6 117 df<70F8F8F0F005057C840C>46 D<03F00FF81E383C1878387878FFF0FF80F000F000F0 00F018F03878F03FE01F800D107C8F12>101 D<00FB8003FF80079F800F0F001E07001E0F003E 0F003C0E003C0E003C1E003C1E00381C003C3C003CFC001FFC000FB800003800007800707800F0 F000F1F000FFE0007F800011177E8F12>103 D<3C7E007EFF00EFC780CF8380CF0380DE07801E 07001C07001C07003C0F003C0E60380E60381EE0781CC0780FC0700F8013107D8F16>110 D<03F00FFC1F3C3C1E780E781EF81EF01EF01EF03EF03CE03CF07879F07FE01F800F107C8F14> I<06000E000E000E000E001E001C00FFC0FFC03C003800380038007800700070007000F180E180 E380E700FE007C000A177C960D>116 D E /Fb 59 123 df<007E3E03FFFF0787EF0F07CF1E07 8F1C03801C03801C03801C03801C0380FFFFF0FFFFF01C03801C03801C03801C03801C03801C03 801C03801C03801C03801C03801C03801C0380FF8FF0FF8FF0181A809916>11 D<007E0003FF000787800F07801E07801C07801C00001C00001C00001C0000FFFF80FFFF801C03 801C03801C03801C03801C03801C03801C03801C03801C03801C03801C03801C0380FF8FF0FF8F F0141A809915>I<007E1F8001FF7FC007C7F1E00707C1E00F07C1E00E0781E00E0380000E0380 000E0380000E038000FFFFFFE0FFFFFFE00E0380E00E0380E00E0380E00E0380E00E0380E00E03 80E00E0380E00E0380E00E0380E00E0380E00E0380E00E0380E07F8FE3FC7F8FE3FC1E1A809920 >14 D<1E0003003F00070073C00E0071F03E00E1FFFC00E0DFF800E0C03800E0C07000E0C06000 E0C0E000E1C1C00071818000738380003F0700001E0E0000000C0F00001C1F80003839C0003038 C0007070E000E0706000C0706001C070600380706003007060070070E00E0038C00C0039C01C00 1F8018000F001B1E7E9B20>37 D<78F8FCFC7C0C0C1C38387060060C7D990B>39 D<0380078007000E001C001C003800380030007000700070006000E000E000E000E000E000E000 E000E000E000E000E000E00060007000700070003000380038001C001C000E0007000780038009 267D9B0F>II<70F8F8F87818183830706060050C7D840B>44 DI<70F8F8F87005057D840B>I<07E01FF83C3C381C700E700E700E F00FF00FF00FF00FF00FF00FF00FF00FF00FF00F700E700E700E381C3C3C1FF807E010187F9713 >48 D<03000700FF00FF0007000700070007000700070007000700070007000700070007000700 07000700070007007FF87FF80D187D9713>I<1FC03FF071F8F078F87CF83CF83C703C003C007C 007800F800F001E003C0078007000E0C1C0C380C7018FFF8FFF8FFF80E187E9713>I<70387FF8 7FF07FE0600060006000600060006FC07FF078F87078003C003C003C703CF03CF03CF03CE07870 F03FE01F800E187E9713>53 D<60007FFF7FFF7FFF600EC01CC018C038007000E000C001C00180 038003800780070007000F000F000F000F000F000F000F0010197E9813>55 D<07E01FF83C3C781E700E700E780E7E1E3F3C3FF81FF00FF81FFC3CFE787EF01FE00FE007E007 F007700E7C3E3FF80FE010187F9713>I<07E01FF83C3C781C701EF00EF00FF00FF00FF00FF01F 701F783F3FFF1FEF030F000E001E781E781C783878F83FE01FC010187F9713>I<70F8F8F87000 000000000070F8F8F8781818383070606005177D8F0B>59 D<000C0000001E0000001E0000001E 0000003F0000003F0000003F000000678000006780000067800000C3C00000C3C00000C3C00001 81E0000181E0000181E0000300F00003FFF00007FFF80006007800060078000E007C000C003C00 1E003C00FF81FFC0FF81FFC01A1A7F991D>65 DI<007F0601FFE607E0FE0F803E 1E001E3C001E3C000E78000E780006F00006F00000F00000F00000F00000F00000F00000F00006 7800067800063C000E3C000C1E001C0F803807E0F001FFE0007F80171A7E991C>I69 DI73 D76 D<007F000001FFC00007C1F0000F0078001E003C003C001E0038000E007800 0F0070000700F0000780F0000780F0000780F0000780F0000780F0000780F0000780F000078078 000F0078000F0038000E003C001E001E003C000F00780007C1F00001FFC000007F0000191A7E99 1E>79 DI82 D<0FC63FF6787E701EE00EE00EE006F006F000FC007F807FF03FFC0FFE01FE003F00 0F000FC007C007E007E00FF00EFC3CDFF8C7F0101A7E9915>I<7FFFFF007FFFFF00781E0F0060 1E0300601E0300E01E0380C01E0180C01E0180C01E0180001E0000001E0000001E0000001E0000 001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E0000001E00 00001E000003FFF00003FFF000191A7F991C>II87 D91 D93 D<3FE0007FF800787800783C00301C00003C000FFC003FFC007E1C 00F81C00F01C00F01D80F03D80F87D807FFF003F8E0011107F8F13>97 DI<07F8 1FFC3E3C783C7818F000F000F000F000F000F00078007C0C3E1C1FF807E00E107F8F11>I<003F 00003F000007000007000007000007000007000007000007000007000FE7001FFF003E1F00780F 00780700F00700F00700F00700F00700F00700F00700780700780F003C3F001FFFE00FE7E0131A 7F9915>I<0FE01FF03C78783C703CFFFCFFFCF000F000F000F0007800780C3E1C1FF807E00E10 7F8F11>I<01F807FC0F3C0E3C1C3C1C001C001C001C001C00FFC0FFC01C001C001C001C001C00 1C001C001C001C001C001C001C00FF80FF800E1A80990C>I<0FCF803FFF80787B80F03C00F03C 00F03C00F03C00F03C007878007FF0006FC0006000007000007FF8007FFC007FFE00F01F00E00F 00E00700E00700F00F007C3E003FFC000FF00011187F8F13>II<387C7C7C3800 00000000FCFC1C1C1C1C1C1C1C1C1C1C1C1CFFFF081A80990A>I107 DIII<07E01FF83C3C781E70 0EF00FF00FF00FF00FF00FF00F700E781E3C3C1FF807E010107F8F13>II<0FE3001FFB003E3F007C0F 00780F00F80700F00700F00700F00700F00700F00700780F007C1F003E3F001FF7000FC7000007 00000700000700000700000700003FE0003FE013177F8F14>II<3FE07FE0F0E0E060E060F800FF 807FC01FE001F0C0F0E070E070F0F0FFE0DF800C107F8F0F>I<18001800180018001800380038 00FFC0FFC0380038003800380038003800380038603860386038603CE01FC00F800B177F960F> IIII<7F1FC07F1FC00E1E00071C0007 980003B00001F00000E00000F00001F00003B800071C000E1C001E0E00FF1FE0FF1FE01310808F 14>I I I E /Fc 6 55 df<0C007C00FC009C001C001C001C001C001C001C001C001C001C001C00FF80FF 8009107E8F0F>49 D<3F007FC0E3E0E1E0E0E000E000E001C003C007800E001C6038607FC0FFC0 FFC00B107F8F0F>I<3F007F8073C071C021C003C01F801F8001C000E000E0E0E0E0E0E1C0FFC0 3F000B107F8F0F>I<0380078007800F801F801B8033807380E380FFE0FFE00380038003801FE0 1FE00B107F8F0F>I<60C07FC07F807E00600060007F007FC071E060E000E0E0E0E0E0E1C0FFC0 3F000B107F8F0F>I<0F801FC039C071C07000E200FF80FFC0F0E0E0E0E0E0E0E060E071C03FC0 1F000B107F8F0F>I E /Fd 6 55 df<06001E00FE00EE000E000E000E000E000E000E000E000E 000E000E000E000E000E00FFE0FFE00B137D9211>49 D<1F807FC0E3E0E0F0E0F0E07000F000F0 00E001E003C007800F001E3038307070FFE0FFE0FFE00C137E9211>I<1FC07FF070F870787078 0078007801F00FE00FE000F8007C003CE03CE03CE07CF0F87FF01FC00E137F9211>I<00E001E0 01E003E007E00EE01CE018E030E070E0E0E0FFFCFFFC00E000E000E000E007FC07FC0E137F9211 >I<60607FE07FC07F806000600060007F807FC071E060F000700070E070E070E0F0F1E07FC03F 000C137E9211>I<03F00FF81E38383870007000E080EFF0FFF8F838F01CE01CE01CE01C701C70 3C38783FF00FC00E137F9211>I E /Fe 7 86 df0 D<07E01FF83FFC7FFE7FFEFFFFFFFFFFFFFFFFFFFFFFFF7FFE7FFE3FFC1FF807E010107E9115> 15 D<000001800000078000001F0000007C000001F0000007C000001F0000007C000001F00000 07C000001F000000FC000000F0000000F80000003E0000000F80000003E0000000F80000003E00 00000F80000003E0000000F80000003E0000000F80000003800000000000000000000000000000 0000000000000000000000000000FFFFFF80FFFFFF8019227D9920>20 D<006000000000E00000 0000C000000000C000000001C00000000380000000038000000007000000000E000000003C0000 0000FFFFFFFFF8FFFFFFFFF83C000000000E0000000007000000000380000000038000000001C0 00000000C000000000C000000000E0000000006000000025167E942A>32 D<000003000000000380000000018000000001C000000000E0000000007000FFFFFFF800FFFFFF FC000000000E00000000078000000003E000000000F800000001F000000007C00000000F000000 001C00FFFFFFF800FFFFFFF000000000E000000000C000000001C0000000018000000003800000 0003000025187E952A>41 D<0000600000600000E00000C00001C0000180000380000300000700 000600000600000E00000C00001C0000180000380000300000700000600000E00000C00000C000 01C0000180000380000300000700000600000E00000C00000C00001C0000180000380000300000 700000600000E00000C00000C0000013287A9D00>54 D<07C000701FC000F07FC001E073C001E0 03C001E003C003C0078003C0078007C0078007800F000F800F000F801E001F001E001F001E003F 003C007E003C007E003C00FE007801FE007803FC007803FC00F007BC00F00F3C00F01E7800F03C 7800F0787800F8F07B80FFC07F80FF807E007E0078001C1D819B1A>85 D E /Ff 4 115 df<03800780030000000000000000003E007E007E00EE00CE001E001C001C003D 8039803B803F001E00091480930C>105 D<1F003F000F000E000E001E001E001C381CFC3DDC3F B83F383F007F807BC071CC71CCF1DCF1F8E0F00E147F9312>107 D<07D81FF83CF83878707070 707070F0F0E0E0E1E073E07FE03FC001C001C003C003800FE01FE00D137F8C0F>113 D<3EF07FF06FB0EF70CE700E001E001E001C001C003C003C0038000C0D808C0F>I E /Fg 15 121 df<0380700380700380700780F00780F00700E00700E00F01E00F01E00E01C00E 01C01E03CE1E03CE1E078C1E0F8C3F1FD83FFBF83BF1F0380000780000780000700000700000F0 0000F00000E00000E00000171B7F9119>22 D<70F8F8F87005057D840C>58 D<70F8F8F8781818183830706060050D7D840C>I<00000C0000001C0000001E0000003E000000 3E0000007E000000FE000000DE0000019E0000019E0000031E0000071E0000061E00000C1E0000 0C1F0000180F0000180F0000300F00007FFF00007FFF0000C00F0000C00F0001800F0003800F00 03000F0007000F001F000F807FC07FF0FFC07FF01C1D7F9C1F>65 D<01FFFF8001FFFFE0003E01 F0003C00F8003C00F8003C0078007C0078007800F8007800F8007801F000F803E000F007C000FF FF8000FFFF0001F01F8001E007C001E003E001E003E003E003E003C003E003C003E003C003E007 C007C007800F8007801F000F803E00FFFFFC00FFFFE0001D1C7F9B1F>I<0003F800000FFE0000 3E0F8000F807C001E003C003C001E0078001E00F8001F01F0001F01E0001F03E0001F03E0001F0 7C0001F07C0001F07C0001F0F80003E0F80003E0F80003E0F80007C0F80007C0F8000F80F8000F 80F8001F0078001E007C003C003C0078003E01F0001F07C00007FF800001FC00001C1E7E9C20> 79 D<01FFFE0003FFFF80003E03E0003C01E0003C01F0003C01F0007C01F0007801F0007801F0 007803E000F803C000F0078000F01F0000FFFC0001FFF80001E07C0001E01E0001E01E0003E01E 0003C01E0003C01E0003C03E0007C03E0007803E0007803E180F803F38FFF83F70FFF01FF00000 07C01D1D7E9B20>82 D<00FC07FE0F8F1E0F3C1F3C0E78007800F800F000F000F000F000F00670 0E783C3FF80FE010127F9112>99 D<0003F00003F00000F00000F00000E00000E00001E00001E0 0001C00001C00003C001FBC007FF800F1F801E0F803C07807C0700780700780F00F80F00F00E00 F00E00F01E70F01E70F03C60F07C6078FEC03FDFC01F8F80141D7F9C16>I<0003F00007F0000E F8000EF8001C70001C00001C00001C00003C0000380000380003FFC003FF800078000070000070 0000700000700000700000F00000E00000E00000E00000E00001E00001C00001C00001C00001C0 00038000038000038000F38000F70000FF0000FE00007C000015257E9C14>102 D<0007000F000F000F00000000000000000000000000F801FC039C071C0E1C0C1C001C003C003C 00380038007800780070007000F000F000E000E001E001E0F1C0F3C0F780FF007C001024809B11 >106 D<0FC0000FC00003C00003C0000380000380000780000780000700000700000F00000F07 800E1F800E39C01E73C01EE7801DC7801F87803F80003FE00039F00038F0007871C07871C07071 80707380F07300F03F00E03E00121D7E9C16>I<1E1F803F3FE07771E067E0E0E7C0E0C780E007 00E00F01E00F01C00E01C00E03C01E038E1E038E1C078C1C071C3C07B83C03F03801E017127F91 19>110 D<1E3E3F7F77F367C7E78FC78F070F0F000F000E000E001E001E001C001C003C003C00 380010127F9113>114 D<0F8F803FDFC038F9C070F1C0E0F3C0C0E3C000E3C001E00001E00001 C00001C00073C0E0F3C0E0F380C0F781C0E7C780FFFF007C7C0013127E9118>120 D E /Fh 1 83 df<0000F80001FC00039E00071E00071E00061E000E1E000E00000E00000E0000 0E00000E00001E00001E00001E00001E00001E00001C00003C00003C00003C00003C00003C0000 3C00003C00003C00003C00003C0000380000780000780000780000780000780000700000700000 7000007000007000F07000F0E000F0E000F1C000F3C0007F80003E0000172E7E7F14>82 D E /Fi 44 123 df<0003F87E0007F8FE000E7DFF001C7DDF001C3BCE001C0380003C03800038 038000380380003807800038070003FFFFF003FFFFF00070070000700F0000700E0000F00E0000 E00E0000E00E0000E01E0000E01C0001E01C0001C01C0001C01C0001C03C0001C0380003C03800 0380380003803800038078000380700007007000F73CE000F73CE000FE3DC000FC3F8000781F00 002025819C19>11 D<0001FE000007FF80000F0380001E0780001C0780001C0780003C00000038 000000380000003800000038000003FFFE0003FFFE0000700E0000701E0000701C0000F01C0000 E01C0000E03C0000E0380000E0380001E0380001C07B8001C0738001C0730001C0730003C07700 03807E0003803C00038000000380000007000000F7000000F7000000FE000000FC000000780000 001925819C17>I45 D<70F8F8F0F005057B840D>I<000018000000 38000000380000007C0000007C000000FC000000FC000001BC000003BC0000033C0000063C0000 063C00000C3C00000C3C0000183C0000183C0000303C0000603C0000603C0000FFFC0000FFFE00 01801E0001801E0003001E0007001E000E001E001F003E00FF81FFC0FF81FFC01A1D7E9C1F>65 D<01FFFF0001FFFFC0003E03C0003C03E0003C01E0003C01E0007C01E0007803E0007803E00078 07C000F8078000F00F0000FFFE0000FFFC0001F03F0001E00F0001E00F8001E00F8003E00F8003 C00F8003C00F8003C00F8007C01F0007801E0007803E000F80FC007FFFF000FFFFC0001B1C7E9B 1D>I<0007F060001FFCE0007E0FE000F807C001F003C007E003C007C003C00F8001801F000180 1F0001803E0003803E0003007C0000007C0000007C000000FC000000F8000000F8000000F80000 00F8000C00F8000C00F8001C00F8001800780038007C0070003C00E0003E01E0001F8780000FFF 000003FC00001B1E7A9C1E>I<01FFFFF001FFFFF0003E01F0003C00F0003C0060003C0060007C 006000781860007818600078386000F8300000F0700000FFF00000FFF00001F0E00001E0600001 E0600001E0E1C003E0C18003C0018003C0038003C0030007C007000780070007800E000F807E00 7FFFFE00FFFFFC001C1C7E9B1C>69 D<01FFE7FF8001FFC7FF00003E00F800003C00F000003C00 F000003C01F000007C01F000007801E000007801E000007803E00000F803E00000F003C00000FF FFC00000FFFFC00001F007C00001E007800001E007800001E00F800003E00F800003C00F000003 C00F000003C01F000007C01F000007801E000007801E00000F803E00007FF1FFC000FFF3FFC000 211C7E9B1F>72 D<03FF8003FF80007C0000780000780000780000F80000F00000F00000F00001 F00001E00001E00001E00003E00003C00003C00003C00007C0000780000780000780000F80000F 00000F00001F0000FFE000FFE000111C7D9B10>I<001FFE001FFE0001F00001E00001E00003E0 0003E00003C00003C00007C00007C0000780000780000F80000F80000F00000F00001F00001F00 001E00001E00783E00F83E00F83C00F87C00F0F800F1F0007FE0003F8000171D7E9B16>I<01FF E001FFE0003E00003C00003C00003C00007C0000780000780000780000F80000F00000F00000F0 0001F00001E00001E00001E00703E00603C00603C00E03C00C07C01C07803C0780780F81F87FFF F8FFFFF0181C7E9B1A>76 D<01FF0003FE01FF0007FC003F0007E0003F000FC0003F001BC0003F 001FC0007F0037C0006780378000678067800067806F8000E780CF8000C7818F0000C7818F0000 C7831F0001C7831F000187861E000187861E0001878C3E000387983E000307983C000307B03C00 0303F07C000703E07C000603E078000603C078001F0380F8007FC387FF00FFC30FFF00271C7E9B 25>I<01FE01FF8001FE01FF00003F007C00003F003000003F803000003F807000007780700000 67C060000067C060000063C0E00000E3E0E00000C3E0C00000C1E0C00000C1F1C00001C1F1C000 0180F180000180F9800001807B800003807B800003007F000003003F000003003F000007003F00 0006001E000006001E00001F001E00007FC00E0000FFC00C0000211C7E9B1F>I<01FFFE0001FF FF80003E07C0003C03E0003C01E0007C01E0007C03E0007803E0007803E000F803C000F807C000 F0078000F00F0001F01E0001FFFC0001FFF00001E0000003E0000003E0000003C0000003C00000 07C0000007C0000007800000078000000F8000007FF00000FFF000001B1C7E9B1C>80 D<001F8C007FFC00F0FC01E07801C03803803803803807803007003007800007800007C00007F8 0003FF0003FF8001FFC0003FC00007C00003C00001C00001C03001C07003C07003807003807007 00F80F00FE1E00FFFC00C7F000161E7D9C17>83 D<7FF87FE07FF07FC00F801F000F000C000F00 0C001F001C001F0018001E0018001E0018003E0038003E0030003C0030003C0030007C0070007C 0060007800600078006000F800E000F800C000F000C000F000C000F001C000F0038000F0030000 F0070000780E00003C3C00003FF000000FE000001B1D789B1F>85 D87 D<01F70007FF000F3F001E1F003C0F 007C0E00780E00781E00F81E00F01C00F01C00F03DC0F03DC0F07980F0F98079FB807FFF001F1E 0012127C9115>97 D<3F003F000F000F000E000E000E001E001C001C001C003DF03FF83F3C3C1C 781C701E701E703EF03CE03CE03CE07CE078E0F0E0F073E07FC03F000F1D7C9C13>I<01F807FC 0F9E1E1E3C3E7C1C78007800F800F000F000F000F000F00CF01C78783FF01FC00F127C9113>I< 0007E00007E00001E00001E00001C00001C00003C00003C000038000038000078001F78007FF00 0F3F001E1F003C0F007C0E00780E00781E00F81E00F01C00F01C00F03DC0F03DC0F07980F0F980 79FB807FFF001F1E00131D7C9C15>I<01F807FC0F1C1E0C3C0C780C783C7FF8FFC0F000F000F0 00F000F00C701C78783FF01FC00E127C9113>I<0003E0000FE0000FF0001DF0001CE0001C0000 3C0000380000380000380000380003FF8003FF8000700000700000700000F00000E00000E00000 E00000E00001E00001C00001C00001C00001C00003C000038000038000038000038000070000F7 0000F70000FE0000FC00007800001425819C0D>I<007DC001FFC003CFC00787C00F03C01F0380 1E03801E07803E07803C07003C07003C0F003C0F003C1E003C3E001E7E001FFE0007DC00001C00 003C00003C00F03800F07800F1F000FFE0007F8000121A7E9113>I<0FC0000FC00003C00003C0 000380000380000780000780000700000700000F00000F7E000EFF800FC7801F83801F03801E03 801C03803C07803C0700380700380700780F70780E70701E60701CE0F01CC0F00FC0E00F80141D 7E9C15>I<01C001E001E001C00000000000000000000000001F003F0073806380E780C7000F00 0E000E001E001C001CE03CE038C039C03B803F801E000B1C7D9B0D>I<0007000F000F000F0000 0000000000000000000000F801FC039C071C0E1C0C1C001C003C003C0038003800780078007000 7000F000F000E000E001E001E0F1C0F3C0FF80FF00FC001024819B0D>I<0FC0000FC00003C000 03C0000380000380000780000780000700000700000F00000F07800E1F800E3DC01E73C01EE780 1DC7801F87803F80003FE00039F00038F0007871C07871C0707180707380F07300F03F00E03E00 121D7E9C13>I<1F801F8007800780070007000F000F000E000E001E001E001C001C003C003C00 380038007800780070007000F380F380E300E700E600FE007C00091D7D9C0B>I<1E1F87E03F7F DFF077F1FC7067C1F070E7C1F070C781E0700701C0700F03C0F00F03C0E00E0380E00E0381E01E 0781C71E0781C71C0703C61C07038E3C0F03DC3C0F01F8380E01F020127D9122>I<3C3F007E7F C06EE3C0EFC1C0CF81C0CF01C00E01C01E03C01E03801C03801C03803C07B83C0738380F30380E 70780E607807E07007C015127D9117>I<01F80007FE000F9F001E0F003C07007C078078078078 0F80F80F00F00F00F00F00F01F00F01E00F03C00F07C0078F8003FE0001F800011127C9115>I< 0787C00FDFE00DFCF01DF07019E07019C07801C07803C0F803C0F00380F00380F00781F00781E0 0783C00783C00FCF800FFF000E7C000E00001E00001E00001C00001C00003C0000FF8000FF8000 151A809115>I<01F107FF0F3F1E1F3C0F7C0E780E780EF81EF01CF01CF01CF03CF078F0F879F8 7FF81F700070007000F000E000E001E00FFC0FFC101A7C9113>I<1E3E3F7F77E767C7E78FC78F 070F0F000F000E000E001E001E001C001C003C003C00380010127D9112>I<03F007F80F3C0E3C 1E7C1E381F001FE00FF007F000F82078F070F070F0F0E1E07FC03F800E127D9111>I<07000700 07000F000F000E000E001E00FFE0FFE01C003C003C00380038007800780070007000F0E0F0E0E1 C0E180E780FF007C000B1A7C990E>I<1E01C03F01C07701C06703C0E703C0CF03800E03800E07 801E07801C07001C07001C0F701C0F701C1E601C1E601E7EE01FFFC007C78014127D9116>I<1E 073F0F770F670FE707CF030E030E071E061C061C061C0E1C0C1C1C1C181E380FF007E010127D91 13>I<1F01C3803F81C7807381C7806383C780E3838380C783838007038180070783800F070300 0E0703000E0703000E0707000E0706000E0F0E000E1F0C000F3F9C0007FFF80003F1F00019127D 911C>I<078F801FFFC03CF9C038F1C070F3C060E3C000E3C001E00001E00001C00001C00073C1 C0F3C1C0F38180F78380E7CF00FFFE007CFC0012127E9113>I<1E01C03F01C07701C06703C0E7 0380CF03800E03800E07801E07001C07001C07001C0F001C0E001C1E001C1E001E7E001FFC0007 DC00001C00003C00703800F07800F0F000E3E000FFC0003F0000121A7D9114>I<03C307F70FFE 0E3E1C1C0038007000E001C0038007000E071C06180E3F1E7FFCE3F8C1F010127E9111>I E /Fj 33 121 df<00180000780003F800FFF800FFF800FDF80001F80001F80001F80001F80001 F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001 F80001F80001F80001F80001F80001F8007FFFE07FFFE07FFFE013207C9F1C>49 D<03FC001FFF803FFFC07C3FE0FC1FF0FE0FF0FE07F8FE07F8FE03F87C03F83807F80007F80007 F0000FF0000FE0001FC0001F80003F00007E0000F80001F00001E03803C0380780380F00381C00 783FFFF07FFFF0FFFFF0FFFFF0FFFFF0FFFFF015207D9F1C>I<01FE0007FFC01FFFE01F0FF03F 07F83F07F83F83F83F03F83F03F80E07F80007F00007F0000FE0001FC001FF0001FF00000FE000 03F80003FC0001FC0001FE0001FE7C01FEFE01FEFE01FEFE01FEFE03FCFE03FC7E0FF83FFFF01F FFC003FF0017207E9F1C>I<0000E00001E00003E00007E0000FE0000FE0001FE0003FE00077E0 00E7E000E7E001C7E00387E00707E00E07E00E07E01C07E03807E07007E0E007E0FFFFFFFFFFFF FFFFFF0007E00007E00007E00007E00007E00007E000FFFF00FFFF00FFFF18207E9F1C>I<3000 603E03E03FFFE03FFFC03FFF803FFF003FFE003FF80038000038000038000038000039FE003FFF 803F0FC03C07E03803F00003F00003F80003F80003F87803F8FC03F8FC03F8FC03F8FC03F0FC07 F07807E07E1FE03FFFC01FFF0007F80015207D9F1C>I<003FC001FFE003FFF007F0F80FC1F81F 81F83F01F83F01F87F00F07E00007E0000FE0800FE7FC0FEFFF0FFC1F8FF81F8FF00FCFF00FEFE 00FEFE00FEFE00FEFE00FEFE00FE7E00FE7E00FE7E00FE3F00FC3F01FC1FC3F80FFFF007FFC000 FF0017207E9F1C>I<00007000000000F800000000F800000000F800000001FC00000001FC0000 0003FE00000003FE00000003FE000000077F000000077F0000000F7F8000000E3F8000000E3F80 00001C1FC000001C1FC000003C1FE00000380FE00000380FE00000700FF000007007F00000F007 F80000FFFFF80000FFFFF80001FFFFFC0001C001FC0001C001FC00038000FE00038000FE000780 00FF000700007F00FFF007FFF8FFF007FFF8FFF007FFF825227EA12A>65 D<0007FE0180003FFFC38000FFFFEF8003FF81FF8007FC007F800FF0003F801FE0001F801FC000 0F803FC00007807F800007807F800007807F80000380FF00000380FF00000000FF00000000FF00 000000FF00000000FF00000000FF00000000FF00000000FF00000000FF000000007F800003807F 800003807F800003803FC00007801FC00007001FE0000F000FF0001E0007FC003C0003FF81F800 00FFFFF000003FFFC0000007FF000021227DA128>67 D69 D73 D82 D<7FFFFFFF807FFFFFFF807FFFFF FF807E03F81F807C03F807807803F807807003F80380F003F803C0F003F803C0E003F801C0E003 F801C0E003F801C0E003F801C00003F800000003F800000003F800000003F800000003F8000000 03F800000003F800000003F800000003F800000003F800000003F800000003F800000003F80000 0003F800000003F800000003F800000003F800000003F8000001FFFFF00001FFFFF00001FFFFF0 0022227EA127>84 D<0FFE003FFFC07E0FE07E03F07E03F87E01F83C01F80001F80001F800FFF8 0FFFF81FF1F87F81F87F01F8FF01F8FE01F8FE01F8FE03F8FF07FC7F0FFF3FFCFF0FF07F18167E 951B>97 DI<01FF8007 FFE01FC3F03F83F03F03F07F03F07E01E0FE0000FE0000FE0000FE0000FE0000FE0000FE0000FE 00007F00007F00003F80383F80781FE1F007FFE001FF8015167E9519>I<0001FF000001FF0000 01FF0000003F0000003F0000003F0000003F0000003F0000003F0000003F0000003F0000003F00 00003F0001FE3F0007FFFF001FC1FF003F80FF003F003F007F003F007E003F00FE003F00FE003F 00FE003F00FE003F00FE003F00FE003F00FE003F00FE003F007E003F007E003F007F007F003F00 FF001FC3FFE00FFFBFE001FE3FE01B237EA21F>I<01FE0007FF801FC7E03F03E03F03F07E01F0 7E01F8FE01F8FE01F8FFFFF8FFFFF8FE0000FE0000FE0000FE00007E00007F00003F00381F8078 0FE1F007FFE000FF8015167E951A>I<003FC000FFE003FBF007E3F007E3F00FC3F00FC1E00FC0 000FC0000FC0000FC0000FC0000FC000FFFE00FFFE00FFFE000FC0000FC0000FC0000FC0000FC0 000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0000FC0007FFC007FFC 007FFC00142380A211>I<01FE1F000FFFFF801F87FF803F03F7803E01F7807E01F8007E01F800 7E01F8007E01F8007E01F8003E01F0003F03F0001F87E0001FFFC00039FE000038000000380000 003C0000003FFFE0003FFFFC001FFFFE001FFFFF003FFFFF007C007F80F8001F80F8000F80F800 0F80F8000F80FC001F807E003F003F80FE000FFFF80001FFC00019217F951C>II<1E003F007F807F807F807F803F001E 00000000000000000000000000FF80FF80FF801F801F801F801F801F801F801F801F801F801F80 1F801F801F801F801F801F80FFF0FFF0FFF00C247FA30F>I107 DII< FF87F000FF9FFC00FFF8FC001FF07E001FE07E001FC07E001FC07E001F807E001F807E001F807E 001F807E001F807E001F807E001F807E001F807E001F807E001F807E001F807E001F807E00FFF1 FFC0FFF1FFC0FFF1FFC01A167E951F>I<00FE0007FFC00F83E01F01F03E00F87E00FC7E00FC7E 00FCFE00FEFE00FEFE00FEFE00FEFE00FEFE00FEFE00FE7E00FC7E00FC3F01F81F01F00F83E007 FFC000FE0017167E951C>II114 D<0FFF003FFF007C1F00F80F00 F00700F00700F80000FF0000FFF8007FFC007FFE001FFF000FFF80007F80E00F80E00F80F00780 F00780F80F00FE1F00FFFE00C7F80011167E9516>I<01C00001C00001C00001C00003C00003C0 0003C00007C00007C0000FC0003FFF00FFFF00FFFF000FC0000FC0000FC0000FC0000FC0000FC0 000FC0000FC0000FC0000FC0000FC3800FC3800FC3800FC3800FC3800FC78007E70003FE0001FC 0011207F9F16>II119 DI E /Fk 85 125 df<003F1F8001FFFFC003C3F3C00783E3C00F03E3C00E01C0000E01 C0000E01C0000E01C0000E01C0000E01C000FFFFFC00FFFFFC000E01C0000E01C0000E01C0000E 01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C000 0E01C0007F87FC007F87FC001A1D809C18>11 D<003F0001FF8003C3C00783C00F03C00E03C00E 00000E00000E00000E00000E0000FFFFC0FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F87F87F8151D809C17>I<003FC0 01FFC003C3C00783C00F03C00E01C00E01C00E01C00E01C00E01C00E01C0FFFFC0FFFFC00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 7FCFF87FCFF8151D809C17>I<003F83F00001FFDFF80003E1FC3C000781F83C000F01F03C000E 01E03C000E00E000000E00E000000E00E000000E00E000000E00E00000FFFFFFFC00FFFFFFFC00 0E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C 000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF807FC7FC FF80211D809C23>I<70F8F8F8F8F8F8F8F87070707070707070707070700000000070F8F8F870 051E7D9D0C>33 D<7070F8F8FCFCFCFC7C7C0C0C0C0C1C1C181838387070707060600E0D7F9C15 >I<0F8000C03FC001C039E0038070F80F80707FFF00E07FFE00E0300E00E0301C00E0301800E0 303800E0303000E07070007060E00070E0C00039E1C0003FC380000F8303E000070FF0000E0E78 000C1C38001C1C180038381C0030380C0070380C0060380C00E0380C01C0380C0180381C03801C 1807001C3806000E780E000FF00C0003E01E217E9E23>37 D<01F0000003F8000007980000071C 00000E0C00000E0C00000E0C00000E0C00000E1C00000E1800000E3800000F70000007E07FE007 E07FE007C01F0007800E000FC01C001FC018003DE0380079E0300078F07000F0786000F078E000 F03DC000F01F8000F00F8060F80F8060781FC0C07C3FF1C03FF0FF800FC03F001B1F7E9D20>I< 70F8FCFC7C0C0C1C1838707060060D7D9C0C>I<01C00380038007000E000C001C001800380038 007000700070007000E000E000E000E000E000E000E000E000E000E000E000E000E000E0007000 7000700070003800380018001C000C000E0007000380038001C00A2A7D9E10>II<70F8F8F8781818183830706060050D7D840C>44 D I<70F8F8F87005057D840C>I<00030003000700060006000E000C001C00180018003800300030 00700060006000E000C000C001C001800380030003000700060006000E000C000C001C00180018 0038003000700060006000E000C000C00010297E9E15>I<03C00FF01C38381C381C700E700E70 0EF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00F700E700E700E381C381C1C38 0FF007E0101D7E9B15>I<030007003F00FF00C700070007000700070007000700070007000700 070007000700070007000700070007000700070007000700FFF8FFF80D1C7C9B15>I<0FE01FF8 38FC703EE03EF01FF81FF81FF80F700F001F001F001E003E007C007800F001E003C0038007000E 031C0338037006FFFEFFFEFFFE101C7E9B15>I<0FE01FF83C7C703E783E7C3E783E783E003E00 3C007C00F807F007E00078003C003E001E001F001F701FF81FF81FF81FF03E703E787C3FF80FE0 101D7E9B15>I<001C00001C00003C00007C00007C0000DC0001DC00019C00039C00071C00061C 000E1C000C1C00181C00381C00301C00601C00E01C00FFFFC0FFFFC0001C00001C00001C00001C 00001C00001C0001FFC001FFC0121C7F9B15>I<301C3FFC3FF83FF03FC0300030003000300030 0037E03FF83E3C381E301E300E000F000F000F000FF00FF00FF00FF01EE01E703C78783FF00FC0 101D7E9B15>I<01F807FC0F8E1E1E1C1E3C1E781E78007000F080F7F0FFF8FC3CF81EF80EF00F F00FF00FF00FF00FF00F700F700F780E381E3C1C1E3C0FF807E0101D7E9B15>I<6000007FFF80 7FFF807FFF80600700C00600C00E00C01C0000180000380000700000600000E00000E00001C000 01C00001C00003C000038000038000038000078000078000078000078000078000078000078000 078000111D7E9B15>I<07E01FF83C7C381C701E700E700E700E780E7C1C3F3C3FF81FF00FF00F F83DFC787E703EF01FE00FE007E007E007F007700E781E3C3C1FF807E0101D7E9B15>I<07E01F F03E78381C781C700EF00EF00EF00FF00FF00FF00FF00FF01F701F781F3C3F1FFF0FEF010F000E 001E781E781C783C787878F03FE01F80101D7E9B15>I<70F8F8F870000000000000000070F8F8 F87005127D910C>I<70F8F8F870000000000000000070F8F8F8781818183830706060051A7D91 0C>I61 D<00060000000F0000000F0000000F0000001F80 00001F8000001F8000003FC0000033C0000033C0000073E0000061E0000061E00000E1F00000C0 F00000C0F00001C0F8000180780001FFF80003FFFC0003003C0003003C0007003E0006001E0006 001E000E001F001E000F00FF807FF0FF807FF01C1D7F9C1F>65 DI<003FC18000FFF18003F0 7B8007C01F800F800F801F0007803E0007803E0003807C0003807C00018078000180F8000180F8 000000F8000000F8000000F8000000F8000000F8000000F8000000780001807C0001807C000180 3E0003803E0003001F0007000F800E0007C01E0003F87C0000FFF000003FC000191E7E9C1E>I< FFFFC000FFFFF0000F00FC000F003E000F001F000F000F000F0007800F0007C00F0003C00F0003 C00F0003E00F0003E00F0003E00F0003E00F0003E00F0003E00F0003E00F0003E00F0003C00F00 03C00F0007C00F0007800F000F800F000F000F003E000F00FC00FFFFF000FFFFC0001B1C7E9B20 >III<003FC18000FFF18003F07B 8007C01F800F800F801F0007803E0007803E0003807C0003807C00018078000180F8000180F800 0000F8000000F8000000F8000000F8000000F800FFF0F800FFF0780007807C0007807C0007803E 0007803E0007801F0007800F800F8007C00F8003F83F8000FFF980003FC0001C1E7E9C21>I II<07FF8007FF80003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00F83C00F83C00F83C00F87C00F0780078F8003FF0001FC000111D7F9B15 >IIIII<003F800000FFE00003E0F80007803C000F001E001E000F003E000F803C 0007807C0007C07C0007C0780003C0F80003E0F80003E0F80003E0F80003E0F80003E0F80003E0 F80003E0F80003E0780003C07C0007C07C0007C03C0007803E000F801E000F000F001E0007803C 0003E0F80000FFE000003F80001B1E7E9C20>II82 D<07F1801FFF803C3F80780F80700780E00380E00380E00180E00180F00000F800007E00007FE0 003FFC001FFE000FFF0000FF80000F800007C00003C00003C0C001C0C001C0C001C0E001C0F003 80F80780FE0F00FFFE00C3F800121E7E9C17>I<7FFFFFC07FFFFFC0780F03C0700F01C0600F00 C0E00F00E0C00F0060C00F0060C00F0060C00F0060000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F000003FFFC0003FFFC001B1C7F9B1E>IIIIII<7FFFF07FFF F07E01F07803E07007C07007C0600F80600F00601F00603E00003E00007C0000F80000F80001F0 0001F00003E03007C03007C0300F80300F00701F00703E00603E00E07C01E0F807E0FFFFE0FFFF E0141C7E9B19>II<18183838383870706060E0E0C0C0C0C0F8F8FCFCFCFC 7C7C38380E0D7B9C15>II<1838387060E0C0C0F8FCFC7C38060D7E9C0C> 96 D<1FE0003FF8003C3C003C1E00180E00000E00001E0007FE003FFE007E0E00F80E00F80E00 F00E60F00E60F81E607C7E607FFFC01FC78013127F9115>II<07FC1FFE3E1E3C1E780C7800F000F000F000F000F000F000780078063C0E3F1C1FF807F00F 127F9112>I<001F80001F80000380000380000380000380000380000380000380000380000380 07F3801FFF803E1F807C0780780380F80380F00380F00380F00380F00380F00380F00380F00380 7807807C0F803E1F801FFBF007E3F0141D7F9C17>I<07E01FF83E7C781C781EF01EFFFEFFFEF0 00F000F000F000780078063C0E3F1C1FF807F00F127F9112>I<00FC03FE079E071E0F1E0E000E 000E000E000E000E00FFE0FFE00E000E000E000E000E000E000E000E000E000E000E000E000E00 0E007FE07FE00F1D809C0D>I<00078007EFC01FFFC03C3DC0781E00781E00781E00781E00781E 00781E003C3C003FF80037E0007000007000007800003FFC003FFF007FFF807807C0F003C0E001 C0E001C0F003C0F807C07C0F801FFE0007F800121C7F9215>II<38007C007C007C003800000000000000000000000000FC00FC001C001C001C001C001C00 1C001C001C001C001C001C001C001C001C00FF80FF80091D7F9C0C>I<01C003E003E003E001C0 00000000000000000000000007E007E000E000E000E000E000E000E000E000E000E000E000E000 E000E000E000E000E000E000E000E0F0E0F1E0F3C0FF807E000B25839C0D>IIIII<03F0 000FFC001E1E00380700780780700380F003C0F003C0F003C0F003C0F003C0F003C07003807807 803807001E1E000FFC0003F00012127F9115>II<07F1801FF9803F1F803C0F80 780780780380F00380F00380F00380F00380F00380F00380F803807807807C0F803E1F801FFB80 07E380000380000380000380000380000380000380001FF0001FF0141A7F9116>II<1F B07FF0F0F0E070E030F030F8007FC03FE01FF001F8C078C038E038F078F8F0FFF0CFC00D127F91 10>I<0C000C000C000C000C001C001C003C00FFE0FFE01C001C001C001C001C001C001C001C00 1C301C301C301C301C301E700FE007C00C1A7F9910>IIII<7F8FF07F8FF00F078007 0700038E0001DC0001D80000F00000700000780000F80001DC00038E00030E000707001F0780FF 0FF8FF0FF81512809116>II<7FFC7FFC783C707860F061E061E063C00780078C 0F0C1E0C1E1C3C187818F078FFF8FFF80E127F9112>III E /Fl 40 121 df<00E001E003C0078007000F001E001E00 3C003C003C007C0078007800F800F800F800F800F800F800F800F800F800F800F800F800F80078 0078007C003C003C003C001E001E000F000700078003C001E000E00B297C9E13>40 DI45 D<7CFEFEFEFEFE7C07077D86 0D>I<00600001E0001FE000FFE000FFE000E3E00003E00003E00003E00003E00003E00003E000 03E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E0007FFF80 7FFF807FFF80111B7D9A18>49 D<0FF8003FFF007FFF80FE7FC0FE1FC0FE0FE0FE0FE0FE07E07C 07E0000FE0000FE0001FC0001F80003F00007E0000FC0001F00003E00007C0E00F00E01E00E03C 01E07FFFC0FFFFC0FFFFC0FFFFC0FFFFC0131B7E9A18>I<000780000780000F80001F80003F80 007F8000EF8001EF8003CF80038F80070F800E0F801C0F80380F80700F80F00F80FFFFF8FFFFF8 FFFFF8000F80000F80000F80000F80000F8000FFF800FFF800FFF8151B7F9A18>52 D<7CFEFEFEFEFE7C000000007CFEFEFEFEFE7C07127D910D>58 D<000380000007C0000007C000 000FE000000FE000000FE000001FF000001FF000003FF8000039F8000039F8000079FC000070FC 0000F0FE0000E07E0000E07E0001E07F0001C03F0001FFFF0003FFFF8003FFFF8007801FC00700 0FC007000FC00E0007E0FFC03FFEFFC03FFEFFC03FFE1F1C7E9B24>65 DI<003FE06001FFFC E003FFFFE00FF81FE01FE007E03FC003E03F8003E07F0001E07F0001E07E0000E0FE0000E0FE00 0000FE000000FE000000FE000000FE000000FE000000FE0000007E0000E07F0000E07F0000E03F 8001E03FC003C01FE007C00FF81F8003FFFF0001FFFC00003FF0001B1C7D9B22>III<00 1FF81800FFFE3803FFFFF807FC0FF80FF003F81FC001F83F8000F87F0000787F0000787F000038 FE000038FE000000FE000000FE000000FE000000FE000000FE007FFFFE007FFF7F007FFF7F0001 F87F0001F83F8001F81FC001F80FF001F807FC03F803FFFFF800FFFF78001FFC18201C7D9B26> 71 D73 D76 D82 D<07F8601FFFE03FFFE07E0FE07C03E0F801E0F800E0F800E0FC0000FE0000FFF0007FFE007FFF 803FFFC01FFFE007FFE0007FF00007F00003F00001F0E001F0E001F0F001F0F803E0FE07E0FFFF C0FFFF80C3FE00141C7D9B1B>I87 D<7FFE1FFE007FFE1FFE007FFE1FFE0003F807800001F807000001FC0F000000FE1E0000007F3C 0000003F380000003FF80000001FF00000000FE00000000FE000000007F000000007F800000007 F80000000FFC0000001EFE0000003C7E000000387F000000783F800000F01FC00000E01FC00001 C00FE00003C007F000FFF01FFF80FFF01FFF80FFF01FFF80211C7F9B24>I<07FC001FFF003F1F 803F0FC03F07C03F07C01E07C003FFC01FFFC07F87C07F07C0FE07C0FC07C0FC07C0FE0FC07E1F F83FFBF80FE1F815127F9117>97 DI<07FC001FFE003F3F 007E3F007C3F00FC3F00FC1E00FC0000FC0000FC0000FC0000FC0000FC00007E03807F07803F8F 001FFE0007F80011127E9115>I<000FF0000FF0000FF00001F00001F00001F00001F00001F000 01F00001F00001F007F9F01FFFF03F0FF07E03F07E01F0FC01F0FC01F0FC01F0FC01F0FC01F0FC 01F0FC01F0FC01F07C01F07E03F03F0FFE1FFFFE07F9FE171D7E9C1B>I<03FC000FFF003F0F80 3E07C07E03C07C03E0FC03E0FFFFE0FFFFE0FC0000FC0000FC00007C00007E00E03F01E01F83C0 0FFF8003FE0013127F9116>I<003F8001FFC003F7E007C7E00FC7E00F87E00F83C00F80000F80 000F80000F8000FFF800FFF800FFF8000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F80000F80007FF0007FF0007FF000131D809C0F>I<07F9F01FFFF83E1FF87C 0FF87C0FF07C0F807C0F807C0F807C0F803E1F003FFE0037F8007000007000007800003FFF803F FFE01FFFF07FFFF0F801F8F000F8F00078F00078F800F87E03F03FFFE007FF00151B7F9118>I< FF0000FF0000FF00001F00001F00001F00001F00001F00001F00001F00001F00001F1FE01F7FF0 1FF1F81FC0F81F80F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F81F00F8 FFE7FFFFE7FFFFE7FF181D7F9C1B>I<3E007F007F007F007F007F003E00000000000000000000 007F007F007F001F001F001F001F001F001F001F001F001F001F001F001F00FFC0FFC0FFC00A1E 7F9D0E>I108 DII<01FC000FFF801F07C03E03E07C01F07C01F0FC01F8FC01F8FC01F8FC01F8FC01F8FC01F8 7C01F07C01F03E03E01F07C00FFF8001FC0015127F9118>II114 D<1FF87FF87078E038E038F800FF80FFF07FF83FF80FFC 007CE03CF01CF01CF878FFF8EFE00E127E9113>I<07000700070007000F000F000F001F003FFC FFFCFFFC1F001F001F001F001F001F001F001F001F1C1F1C1F1C1F1C1FBC0FF807F00E1A7F9913 >III120 D E /Fm 24 122 df<000007C00000000007C0000000000FE0000000000FE0000000000FE00000 00001FF0000000001FF0000000003FF8000000003FF8000000003FF8000000007FFC000000007F FC00000000FFFE00000000F3FE00000000F3FE00000001E1FF00000001E1FF00000003E1FF8000 0003C0FF80000003C0FF8000000780FFC0000007807FC000000F807FE000000F003FE000000F00 3FE000001E003FF000001E001FF000003FFFFFF800003FFFFFF800003FFFFFF8000078000FFC00 00780007FC0000F80007FE0000F00003FE0000F00003FE0001E00003FF0001E00001FF0003E000 01FF80FFFF003FFFFEFFFF003FFFFEFFFF003FFFFE2F297EA834>65 D<00007FF003800007FFFE 0780001FFFFF8F80007FF80FFF8000FFC003FF8003FF0000FF8007FE00007F800FFC00003F800F F800001F801FF000001F803FF000000F803FE000000F807FE0000007807FE0000007807FC00000 0780FFC000000000FFC000000000FFC000000000FFC000000000FFC000000000FFC000000000FF C000000000FFC000000000FFC000000000FFC000000000FFC0000000007FC0000000007FE00000 03807FE0000003803FE0000003803FF0000003801FF0000007800FF8000007000FFC00000F0007 FE00001E0003FF00007C0000FFC000F800007FF807F000001FFFFFC0000007FFFF000000007FF8 000029297CA832>67 D72 D76 D<0000FFE000000007FFFC0000003FFFFF8000007FC07FC00001FF001FF000 03FC0007F80007F80003FC000FF80003FE001FF00001FF001FF00001FF003FE00000FF803FE000 00FF807FE00000FFC07FC000007FC07FC000007FC07FC000007FC0FFC000007FE0FFC000007FE0 FFC000007FE0FFC000007FE0FFC000007FE0FFC000007FE0FFC000007FE0FFC000007FE0FFC000 007FE0FFC000007FE07FC000007FC07FE00000FFC07FE00000FFC03FE00000FF803FE00000FF80 1FF00001FF001FF00001FF000FF80003FE0007FC0007FC0003FE000FF80001FF001FF00000FFC0 7FE000003FFFFF8000000FFFFE00000000FFE000002B297CA834>79 D82 D85 D<03FFC0000FFFF0001F FFFC003FC1FE003FC0FF003FC07F003FC03F803FC03F801F803F8000003F8000003F80003FFF80 03FFFF800FFE3F801FE03F803F803F807F003F80FF003F80FE003F80FE003F80FE003F80FF007F 807F00FF807FC3FFC03FFFDFFC0FFF0FFC03FC07FC1E1B7E9A21>97 D<003FE00001FFFC0007FF FE000FF07F001FC03F803FC01FC03F800FC07F800FC07F0007E0FF0007E0FF0007E0FFFFFFE0FF FFFFE0FFFFFFE0FF000000FF000000FF000000FF0000007F8000007F8000003F8000E03FC001E0 1FF003C00FFC0FC003FFFF8001FFFE00003FF0001B1B7E9A20>101 D<0007FC00003FFE00007F FF0001FF7F8003FC7F8003F87F8007F87F8007F07F8007F03F0007F0000007F0000007F0000007 F0000007F0000007F00000FFFFC000FFFFC000FFFFC00007F0000007F0000007F0000007F00000 07F0000007F0000007F0000007F0000007F0000007F0000007F0000007F0000007F0000007F000 0007F0000007F0000007F0000007F0000007F0000007F0000007F000007FFF80007FFF80007FFF 8000192A7EA915>I<00FF81F007FFF7FC0FFFFFFC1FC1FEFC3F80FE7C3F007E787F007F007F00 7F007F007F007F007F007F007F007F007F003F007E003F80FE001FC1FC000FFFF8001FFFF00038 FF800038000000380000003C0000003E0000003FFFFC003FFFFF001FFFFFC01FFFFFE01FFFFFF0 3FFFFFF07E000FF8FE0003F8FC0001F8FC0001F8FC0001F8FE0003F87E0003F07F0007F03FE03F E01FFFFFC007FFFF0000FFF8001E287E9A22>II<07801FE01FE03FF03FF03FF03FF01FE01FE00780000000000000000000000000FFE0FFE0 FFE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00FE00F E00FE00FE0FFFEFFFEFFFE0F2B7DAA14>I108 DII<003FE00001FFFC0003FFFE00 0FF07F801FC01FC03F800FE03F800FE07F0007F07F0007F07F0007F0FF0007F8FF0007F8FF0007 F8FF0007F8FF0007F8FF0007F8FF0007F8FF0007F87F0007F07F0007F03F800FE03F800FE01FC0 1FC00FF07F8007FFFF0001FFFC00003FE0001D1B7E9A22>II114 D<03FE701FFFF03FFFF07E03F07C00F0F80070F80070FC0070FE0000FFE000FFFF007F FFC03FFFE01FFFF00FFFF801FFFC0007FC0001FCE000FCE0007CF0007CF8007CFC00F8FF03F8FF FFF0FFFFC0E1FF00161B7E9A1B>I<00700000700000700000700000F00000F00001F00001F000 03F00007F0001FF000FFFFF0FFFFF0FFFFF007F00007F00007F00007F00007F00007F00007F000 07F00007F00007F00007F00007F00007F00007F03807F03807F03807F03807F03807F03807F878 03F8F001FFF000FFE0003F8015267FA51B>II120 DI E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 194 34 a Fm(Learning)23 b(Appro)n(ximate)f(Con)n(trol)h(Rules)e(Of)i (High)f(Utilit)n(y)718 185 y Fl(William)13 b(W.)k(Cohen)718 231 y Fk(Computer)c(Science)i(Departmen)o(t)718 277 y(Rutgers)f(Univ)o(ersit) o(y)718 322 y(New)g(Brunswic)o(k,)h(NJ)f(08903)365 559 y Fj(Abstract)68 638 y Fk(One)k(of)f(the)h(di\016cult)f(problems)g(in)g(the)h(area)g(of)68 683 y(explanation)10 b(based)i(learning)e(is)h(the)h Fi(utility)f(pr)n(ob-)68 729 y(lem)p Fk(;)28 b(learning)c(to)q(o)g(man)o(y)e(rules)j(of)f(lo)o(w)f (util-)68 775 y(it)o(y)h(can)g(lead)g(to)h Fi(swamping)p Fk(,)h(or)e (degradation)68 820 y(of)18 b(p)q(erformance.)31 b(This)18 b(pap)q(er)h(in)o(tro)q(duces)g(t)o(w)o(o)68 866 y(new)h(tec)o(hniques)g(for) f(impro)o(ving)d(the)k(utilit)o(y)e(of)68 912 y(learned)e(rules.)22 b(The)15 b(\014rst)h(tec)o(hnique)g(is)e(to)h(com-)68 957 y(bine)c(EBL)h (with)23 b(inductiv)o(e)11 b(learning)g(tec)o(hniques)68 1003 y(to)i(learn)g(a)g(b)q(etter)i(set)g(of)d(con)o(trol)h(rules;)h(the)g(sec-)68 1049 y(ond)g(tec)o(hnique)h(is)f(to)g(use)h(these)h(inductiv)o(e)e(tec)o(h-) 68 1094 y(niques)24 b(to)g(learn)f(appro)o(ximate)f(con)o(trol)i(rules.)68 1140 y(The)14 b(t)o(w)o(o)g(tec)o(hniques)h(are)g(syn)o(thesized)g(in)f(an)g (al-)68 1186 y(gorithm)20 b(called)h Fi(appr)n(oximating)h(ab)n(ductive)h (ex-)68 1231 y(planation)e(b)n(ase)n(d)f(le)n(arning)f Fk(\(AxA-EBL\).)h (AxA-)68 1277 y(EBL)d(is)f(sho)o(wn)h(to)f(impro)o(v)o(e)e(substan)o(tially)i (o)o(v)o(er)68 1323 y(standard)e(EBL)h(in)e(sev)o(eral)i(domains.)-15 1443 y Fj(1)56 b(In)n(tro)r(duction)-15 1519 y Fk(One)11 b(of)f(the)h (di\016cult)f(problems)g(in)g(the)h(area)g(of)f(explanation)-15 1565 y(based)17 b(learning)e(is)h(the)g Fi(utility)g(pr)n(oblem)p Fk(.)24 b(The)16 b Fi(utility)f Fk(of)g(a)-15 1610 y(rule)j(is)f(its)g(con)o (tribution)g(to)g(p)q(erformance)g(impro)o(v)o(emen)o(t;)-15 1656 y(the)h(utilit)o(y)e(is)h(directly)g(prop)q(ortional)f(to)h(the)h Fi(c)n(over)n(age)g Fk(of)-15 1702 y(a)c(rule)h(and)f(in)o(v)o(ersely)g(prop) q(ortional)g(to)g(the)h Fi(match)g(c)n(ost)g Fk(of)-15 1747 y(a)g(rule,)g(where)i Fi(c)n(over)n(age)e Fk(is)g(de\014ned)h(as)g(the)g(p)q (ercen)o(tage)h(of)-15 1793 y(the)d(time)f(that)h(the)g(rule)g(is)g(used)h (in)e(problem)g(solving,)f(and)-15 1839 y Fi(match)i(c)n(ost)e Fk(is)g(simply)f(the)i(time)e(needed)j(to)e(determine)h(if)e(a)-15 1884 y(rule)j(is)g(applicable.)27 1931 y(The)21 b(utilit)o(y)f(problem)f (often)j(arises)f(in)g(learning)f(rules)-15 1977 y(in)o(tended)j(to)f(impro)o (v)o(e)e(the)j(p)q(erformance)f(of)f(a)h(problem)-15 2023 y(solv)o(er.)40 b(Learning)21 b(to)q(o)g(man)o(y)e(rules)j(of)f(lo)o(w)f(utilit)o(y)g(can)-15 2068 y(lead)25 b(to)h Fi(swamping)p Fk(,)i(or)d(degradation)h(of)f(p)q (erformance:)-15 2114 y(in)e(the)g(w)o(orst)h(case,)i(a)d(problem)f(solv)o (er)h(can)g(b)q(e)h(slo)o(w)o(er)-15 2160 y(after)j(learning)f(than)g(b)q (efore)i(learning.)55 b(Previous)27 b(re-)-15 2205 y(searc)o(h)19 b(on)e(the)h(utilit)o(y)f(problem)f(has)i(fo)q(cused)g(on)f(detect-)-15 2251 y(ing)e(and)h(discarding)g(rules)g(of)g(lo)o(w)f(utilit)o(y)694 2247 y([)706 2251 y(Min)o(ton,)g(1988;)-15 2297 y(Mark)o(o)o(vitc)o(h)f(and)g (Scott,)g(1989)490 2293 y(])500 2297 y(,)g(lo)o(w)o(ering)f(the)i(matc)o(h)e (cost)-15 2342 y(of)e(rules)h(using)g(partial)e(ev)n(aluation)h(or)g(other)i (simpli\014cation)-15 2388 y(tec)o(hniques)186 2384 y([)197 2388 y(Prieditis)f(and)f(Mosto)o(w,)h(1987;)e(Min)o(ton,)g(1988;)-15 2434 y(T)m(am)o(b)q(e)15 b(and)h(Rosen)o(blo)q(om,)f(1989)541 2430 y(])552 2434 y(,)i(and)f(constraining)g(the)-15 2479 y(use)f(of)e (learned)h(rules)349 2475 y([)360 2479 y(Mo)q(oney)m(,)f(1989)610 2475 y(])621 2479 y(.)27 2526 y(This)18 b(pap)q(er)h(in)o(tro)q(duces)g(t)o (w)o(o)f(new)h(tec)o(hniques)g(for)f(im-)-15 2572 y(pro)o(ving)10 b(the)h(utilit)o(y)e(of)i(learned)g(rules.)17 b(The)12 b(\014rst)f(tec)o (hnique)-15 2618 y(is)k(to)f(com)o(bine)f(EBL)j(with)e Fi(inductive)i(le)n (arning)f(te)n(chniques)1035 559 y Fk(to)d(learn)h(a)f(b)q(etter)i(set)f(of)f (con)o(trol)h(rules.)18 b(The)13 b(second)g(tec)o(h-)1035 605 y(nique)h(is)f(to)h(use)g(these)h(inductiv)o(e)f(tec)o(hniques)h(to)e(learn)h Fi(ap-)1035 650 y(pr)n(oximate)j(c)n(ontr)n(ol)g(rules)p Fk(:)24 b(that)16 b(is,)h(to)g(learn)g(rules)g(whic)o(h)1035 696 y(are)h(appro)o (ximations)e(of)h(the)i(con)o(trol)e(rules)i(whic)o(h)f(w)o(ould)1035 742 y(b)q(e)12 b(learned)g(b)o(y)f(standard)h(EBL)g(tec)o(hniques.)18 b(Although)11 b(use)1035 787 y(of)k(inductiv)o(e)g(tec)o(hniques)i(alone)d (do)q(es)j(not)e(alw)o(a)o(ys)f(lead)h(to)1035 833 y(rules)i(of)e(higher)h (utilit)o(y)m(,)f(the)i(com)o(bination)c(of)j(these)h(tec)o(h-)1035 879 y(niques)i(is)f(sho)o(wn)g(to)h(substan)o(tially)e(impro)o(v)o(e)g(the)i (p)q(erfor-)1035 924 y(mance)13 b(of)g(EBL)i(across)g(a)e(v)n(ariet)o(y)h(of) f(domains.)1077 974 y Fi(Combining)h(EBL)g(with)f(inductive)h(le)n(arning.)k Fk(Flann)12 b(and)1035 1019 y(Dietteric)o(h)17 b(ha)o(v)o(e)g(noted)g(that)g (in)f(the)h(pro)q(cess)i(of)d(learning)1035 1065 y(con)o(trol)9 b(rules,)i(man)o(y)c(EBL)j(systems)g(mak)o(e)e(inductiv)o(e)h(leaps.)1035 1111 y(An)18 b(example)f(giv)o(en)g(in)1439 1107 y([)1450 1111 y(Flann)h(and)g(Dietteric)o(h,)h(1989)1954 1107 y(])1982 1111 y(is)1035 1156 y(a)g(rule)h(learned)g(b)o(y)f(LEX2)h(in)f(the)h(sym)o(b)q (olic)e(in)o(tegration)1035 1202 y(domain:)1118 1275 y(If)c(the)g(curren)o(t) h(problem)e(matc)o(hes)1160 1288 y Fh(R)1194 1322 y Fg(cx)1236 1307 y Ff(r)1254 1322 y Fg(dx)p Fk(\()p Fg(r)f Fe(6)p Fk(=)g Fe(\000)p Fk(1\))1118 1368 y(Then)i(use)h(the)g(op)q(erator)1160 1381 y Fh(R)1194 1415 y Fg(cf)t Fk(\()p Fg(x)p Fk(\))p Fg(dx)d Fe(\))f Fg(c)1428 1381 y Fh(R)1462 1415 y Fg(f)t Fk(\()p Fg(x)p Fk(\))p Fg(dx)1035 1484 y Fk(F)m(orming)d(this)j(rule)g(is)f(an)h(inductiv)o (e)f(leap;)h(this)g(is)g(witnessed)1035 1530 y(b)o(y)g(the)h(fact)g(that)g (the)g(rule)g(recommends)e(the)i Fi(wr)n(ong)f Fk(action)1035 1575 y(on)18 b(the)g(problem)1338 1542 y Fh(R)1373 1575 y Fk(0)p Fg(x)1418 1560 y Fd(4)1436 1575 y Fg(dx)f Fk(\(m)o(ultip)o(ying)e(out)j(the)g (zero)h(to)1035 1626 y(get)1103 1592 y Fh(R)1137 1626 y Fk(0)p Fg(dx)11 b Fk(leads)i(to)f(a)g(shorter)h(solution\).)k(Another)c(case)g(in) 1035 1671 y(whic)o(h)e(inductiv)o(e)f(decisions)i(are)f(made)f(is)g(when)i (only)e(one)h(of)1035 1717 y(sev)o(eral)17 b(p)q(ossible)g(con)o(trol)g (rules)g(is)f(learned;)i(for)f(example,)1035 1763 y(PR)o(ODIGY)f(migh)o(t)f (learn)i(either)h(a)f(macro-op)q(erator)f(or)h(a)1035 1808 y(set)f(of)e(op)q(erator)h(preference)j(rules)d(from)e(a)i(trace)1855 1804 y([)1867 1808 y(Min)o(ton,)1035 1854 y(1988)1119 1850 y(])1130 1854 y(.)1077 1903 y(Ho)o(w)o(ev)o(er,)30 b(the)e(standard)g (implemen)o(tation)c(of)j(EBL,)1035 1949 y(in)22 b(whic)o(h)g(con)o(trol)g (rules)h(are)f(learned)h(incremen)o(tally)e(as)1035 1995 y(needed,)11 b(is)f(relativ)o(ely)e(slo)o(w)h(as)h(an)f(inductiv)o(e)h(learner.)17 b(Com-)1035 2040 y(bining)23 b(EBL)h(with)f(more)g(p)q(o)o(w)o(erful)g (inductiv)o(e)h(learning)1035 2086 y(tec)o(hniques)12 b(can)f(impro)o(v)o(e)e (the)j(rate)f(at)g(whic)o(h)g(learning)f(con-)1035 2132 y(v)o(erges)18 b(to)f(an)f(adequate)i(set)f(of)g(con)o(trol)f(rules.)28 b(A)17 b(crucial)1035 2177 y(p)q(oin)o(t)12 b(is)h(that)f(on)h(a)o(v)o(erage,)f Fi(impr)n(oving)h(the)h(r)n(ate)f(of)h(c)n(onver-)1035 2223 y(genc)n(e)j(wil)r(l)e(also)h(impr)n(ove)g(the)h(c)n(over)n(age)f(of)g(the)h (individual)1035 2269 y(rules)c(le)n(arne)n(d.)k Fk(This)12 b(is)g(true)h(b)q(ecause)g(in)f(order)h(to)f(impro)o(v)o(e)1035 2314 y(the)i(learning)f(rate,)h(it)f(necessary)j(to)e(\014nd)f Fi(fewer)g Fk(rules)h(with)1035 2360 y Fi(b)n(etter)f Fk(co)o(v)o(erage.)1314 2345 y Fd(1)p 1035 2409 250 2 v 1087 2436 a Fc(1)1104 2451 y Fb(It)f(m)o(ust)g(b)q(e)h(emphasized)h(that)e(w)o(e)g(are)g Fa(not)f Fb(adv)o(o)q(cating)j(use)1035 2493 y(of)e(pure)h(inductiv)o(e)h (learning)h(tec)o(hniques)f(\()p Fa(e.g.)p Fb(,)c(v)o(ersion)k(spaces\))1035 2534 y(to)j(learn)h(con)o(trol)g(rules.)31 b(Explanation-based)21 b(tec)o(hniques)e(are)1035 2576 y(clearly)d(more)e(appropriate)i(in)e (learning)j(con)o(trol)e(rules)g(b)q(ecause)1035 2618 y(there)e(is)h(a)f (strong)g(theory)m(.)p eop %%Page: 2 2 2 1 bop 27 -153 a Fi(Using)14 b(appr)n(oximate)h(rules.)j Fk(The)c(\014rst)g (tec)o(hnique)h(alone,)-15 -108 y(ho)o(w)o(ev)o(er,)e(is)g(not)g(enough)g(to) g(a)o(v)o(oid)f(sw)o(amping.)k(The)d(prob-)-15 -62 y(lem)i(is)i(that)f(in)h (learning)f(con)o(trol)g(rules,)h(one)g(is)g(trying)f(to)-15 -17 y(maxim)o(ize)g(the)i(utilit)o(y)f(of)g(the)i(set)g(of)e(rules.)31 b(T)m(o)18 b(do)f(this,)-15 29 y(one)12 b(m)o(ust)g(sim)o(ultaneously)e Fi(maximize)j(total)g(c)n(over)n(age)p Fk(,)f(and)-15 75 y Fi(minimize)k(total)g(match)g(c)n(ost)p Fk(.)23 b(Standard)16 b(inductiv)o(e)f(learn-)-15 120 y(ing)j(tec)o(hniques,)j(ho)o(w)o(ev)o(er,)f (maxim)o(ize)c(co)o(v)o(erage)j(without)-15 166 y(regard)14 b(to)g(matc)o(h)f(cost.)27 215 y(View)o(ed)h(in)g(this)h(ligh)o(t,)e Fi(le)n(arning)i(useful)h(c)n(ontr)n(ol)e(rules)h(is)-15 260 y(a)e(multiple-r)n(esour)n(c)n(e)e(optimization)i(pr)n(oblem)p Fk(,)e(in)h(whic)o(h)f(the)-15 306 y(t)o(w)o(o)h(an)o(tagonistic)h(resources) i(of)d(co)o(v)o(erage)i(and)f(matc)o(h)e(cost)-15 352 y(m)o(ust)k(b)q(e)i (sim)o(ultaneously)d(optimized.)24 b(A)17 b(standard)f(tec)o(h-)-15 397 y(nique)g(for)h(solving)e(suc)o(h)i(problems)f(is)g(to)g(set)i(an)e (arti\014cial)-15 443 y(constrain)o(t)e(on)f(one)g(resource,)i(and)e (optimize)f(the)i(other)f(re-)-15 489 y(source)k(sub)r(ject)g(to)f(this)g (constrain)o(t.)23 b(This)16 b(tec)o(hnique)h(can)-15 534 y(b)q(e)12 b(applied)e(to)h(the)g(con)o(trol)g(rule)g(learning)g(problem)e(b)o(y)i(con-) -15 580 y(straining)g(the)h(inductiv)o(e)f(learner)h(to)f(only)g(consider)h (con)o(trol)-15 626 y(rules)j(with)e(matc)o(h)g(cost)h(b)q(elo)o(w)g(a)g (certain)g(\014xed)g(cuto\013.)27 674 y(Unfortunately)m(,)19 b(the)h(con)o(trol)f(rules)h(learned)f(b)o(y)g(expla-)-15 720 y(nation)c(based)h(tec)o(hniques)h(are)f(almost)e(alw)o(a)o(ys)g(v)o(ery)i (com-)-15 766 y(plex;)c(hence)h(if)e(a)h(reasonable)g(matc)o(h-cost)g (cuto\013)g(w)o(ere)h(c)o(ho-)-15 811 y(sen,)18 b(v)o(ery)g(few)f(rules)h(w)o (ould)e(b)q(e)i(a)o(v)n(ailable)d(for)h(the)i(induc-)-15 857 y(tiv)o(e)g(learning)f(metho)q(d)g(to)h(consider.)31 b(This)18 b(problem)f(can)-15 903 y(b)q(e)h(remedied)f(b)o(y)h(allo)o(wing)d(the)j (learner)g(to)f(also)g(consider)-15 948 y Fi(appr)n(oximations)d Fk(to)g(exp)q(ensiv)o(e)h(con)o(trol)f(rules.)27 997 y(In)i(the)h(remainder)f (of)g(the)h(pap)q(er,)g(w)o(e)g(\014rst)g(discuss)g(the)-15 1043 y(con)o(trol)c(rule)h(learning)f(problem)f(used)i(to)g(test)g(these)h (ideas,)-15 1088 y(and)j(then)i(the)f(learning)f(algorithm)e(used.)33 b(W)m(e)18 b(then)i(de-)-15 1134 y(scrib)q(e)15 b(the)g(domains)e(used)i(for) e(exp)q(erimen)o(tation.)19 b(Finally)m(,)-15 1180 y(w)o(e)14 b(presen)o(t)g(and)g(in)o(terpret)g(our)f(exp)q(erimen)o(tal)g(results)h(and) -15 1225 y(dra)o(w)g(some)f(conclusions.)-15 1329 y Fj(2)56 b(The)18 b(learning)i(problem)-15 1408 y Fk(T)m(o)c(ev)n(aluate)g(the)h (learning)f(algorithms)e(discussed)19 b(in)d(this)-15 1454 y(pap)q(er,)j(w)o(e)e(used)i(as)e(a)g(testb)q(ed)j(the)e(problem)e(of)h (learning)-15 1499 y Fi(clause)c(sele)n(ction)g(rules)f Fk(for)g(Prolog)f (programs.)16 b(This)c(learn-)-15 1545 y(ing)h(problem)g(has)h(sev)o(eral)g (adv)n(an)o(tages.)27 1613 y Fe(\017)20 b Fk(Commercial)g(Prologs)j(are)g (highly)f(optimized,)h(and)68 1659 y(hence)c(the)f(initial)d(problem)h(solv)o (er)h(has)h(a)f(fairly)f(lo)o(w)68 1705 y(o)o(v)o(erhead.)31 b(This)18 b(encourages)h(careful)g(exp)q(erimen)o(ta-)68 1750 y(tion,)14 b(and)h(also)g(means)f(that)h(comparisons)f(of)h(p)q(erfor-)68 1796 y(mance)f(b)q(efore)i(and)e(after)i(learning)e(are)h(a)g(reasonable)68 1842 y(test)g(of)e(the)i(o)o(v)o(erall)d(e\013ectiv)o(eness)17 b(of)c(learning.)27 1910 y Fe(\017)20 b Fk(Man)o(y)12 b(di\013eren)o(t)h (problem)f(solving)f(strategies)j(\(for)e(ex-)68 1956 y(ample,)22 b(state)h(space)g(searc)o(h,)h(problem)d(decomp)q(osi-)68 2001 y(tion,)26 b(means-end)e(analysis,)i(etc.\))51 b(can)24 b(b)q(e)h(easily)68 2047 y(co)q(ded)f(as)e(Prolog)g(programs)g(in)g(suc)o(h)h(a)g(w)o(a)o(y)f (that)68 2093 y(learning)i(clause)g(selection)h(rules)g(signi\014can)o(tly)e (im-)68 2138 y(pro)o(v)o(es)14 b(p)q(erformance.)27 2207 y(Our)i(learning)f (testb)q(ed)i(consists)g(of)e(t)o(w)o(o)g(routines.)25 b(The)-15 2252 y(\014rst)11 b(is)e(a)h Fi(critic)e Fk(whic)o(h)i(analyzes)g(a)f(set)i (of)e(Prolog)g(traces)i(and)-15 2298 y(extracts)h(examples)e(of)g(correct)j (and)d(incorrect)j(clause)e(selec-)-15 2344 y(tion)g(decisions.)17 b(A)12 b Fi(c)n(orr)n(e)n(ct)e Fk(decision)i(is)f(an)o(y)g(decision)g(whic)o (h)-15 2389 y(leads)f(to)g(a)g(solution;)g(an)g Fi(inc)n(orr)n(e)n(ct)g Fk(decision)g(is)g(an)o(y)g(decision)-15 2435 y(whic)o(h)i(is)g(ev)o(en)o (tually)g(retracted)i(b)o(y)e(Prolog's)f(bac)o(ktrac)o(king)-15 2481 y(strategy)m(.)21 b(Along)14 b(with)g(eac)o(h)i(correct)g(decision,)f(a) f(pro)q(of)h(of)-15 2526 y(its)g(correctness)i(is)e(recorded.)22 b(The)15 b(theory)g(used)h(to)e(deriv)o(e)-15 2572 y(this)d(pro)q(of)f(is)g (v)o(ery)h(simple:)k(it)10 b(merely)f(con)o(tains)i(the)g(clauses)-15 2618 y(of)h(the)i(initial)c(program)i(as)g(axioms,)f(and)i(also)f(an)g(axiom) f(of)1035 -153 y(the)j(form)1285 -108 y(useful\()p Fg(c)1424 -102 y Ff(i)1438 -108 y Fg(;)7 b(A)p Fk(\))k Fe( )g Fg(B)1599 -102 y Fd(1)1618 -108 y Fg(;)c(:)g(:)g(:)e(;)i(B)1742 -102 y Ff(q)1035 -47 y Fk(for)17 b(eac)o(h)i(clause)f Fg(c)1344 -41 y Ff(i)1376 -47 y Fk(=)g(\()p Fg(A)g Fe( )f Fg(B)1581 -41 y Fd(1)1600 -47 y Fg(;)7 b(:)g(:)g(:)e(;)i(B)1724 -41 y Ff(q)1743 -47 y Fk(\))17 b(in)h(the)g(initial)1035 -1 y(program.)24 b(This)16 b(`usefulness)h(theory")g(is)f(an)g(extension)h(to)1035 44 y(the)i(problem)e(of)h(Prolog)g(clause)h(selection)g(of)e(the)i(theory)1035 90 y(used)11 b(in)f(the)h(LEX/2)f(system)1510 86 y([)1522 90 y(Mitc)o(hell,)g(1982)1776 86 y(])1796 90 y(for)g(op)q(erator)1035 136 y(selection.)1077 181 y(The)i(second)i(routine)f(is)f(a)h Fi(c)n(ontr)n(ol)g(rule)g(c)n(ompiler)f Fk(whic)o(h,)1035 227 y(giv)o(en)20 b(a)g(set)h(of)f(con)o(trol)g(rules)h(and)f(an)h(initial)d (program,)1035 273 y(generates)j(a)e(new)h(Prolog)e(program)g(whic)o(h)h (incorp)q(orates)1035 318 y(the)e(learned)f(con)o(trol)g(rules.)24 b(The)17 b(routine)f(tak)o(es)g(as)g(input)1035 364 y(a)e(set)g(of)g(con)o (trol)f(rules)i(of)e(the)i(form)1334 437 y(useful\()p Fg(c)1473 443 y Ff(i)1487 437 y Fg(;)7 b(A)p Fk(\))k Fe( )g(U)t Fk(\()p Fg(A)p Fk(\))1035 509 y(whic)o(h)h(can)h(b)q(e)g(read)g(as)f(sa)o(ying)g (\\if)f Fe(U)t Fk(\()p Fg(A)p Fk(\))i(is)f(true,)h(then)g(it)f(is)1035 555 y(useful)j(to)f(apply)g(clause)h Fg(c)1462 561 y Ff(i)1490 555 y Fk(to)g(the)g(goal)e Fg(A)p Fk(".)20 b Fe(U)t Fk(\()p Fg(A)p Fk(\))15 b(is)f(t)o(yp-)1035 600 y(ically)k(a)g(complex)g(conjunctiv)o (e)h(condition)g(in)o(v)o(olving)d(the)1035 646 y(v)n(ariables)e(of)h(the)h (goal)e Fg(A)p Fk(.)22 b(F)m(or)15 b(eac)o(h)h(suc)o(h)g(rule,)f(the)h(p)q (ost-)1035 692 y(pro)q(cessor)e(constructs)g(a)e(cop)o(y)g(of)g(clause)h Fg(c)1725 698 y Ff(i)1750 692 y Fk(to)f(whic)o(h)g Fe(U)t Fk(\()p Fg(A)p Fk(\))1035 737 y(has)i(b)q(een)h(added)f(as)g(an)g(additional)e (\\\014ltering)h(condition";)1035 783 y(in)d(other)i(w)o(ords,)f(if)f Fg(c)1367 789 y Ff(i)1392 783 y Fk(=)i(\()p Fg(A)f Fe( )g Fg(B)1578 789 y Fd(1)1598 783 y Fg(;)c(:)g(:)g(:)t(;)g(B)1721 789 y Ff(q)1740 783 y Fk(\),)k(then)g(a)f(clause)1035 829 y(of)j(the)i(form)1308 901 y Fg(A)c Fe( )g(U)t Fk(\()p Fg(A)p Fk(\))p Fg(;)c Fk(!)p Fg(;)g(B)1577 907 y Fd(1)1595 901 y Fg(;)g(:)g(:)g(:)e(;)i(B)1719 907 y Ff(q)1035 974 y Fk(is)12 b(constructed.)20 b(Notice)12 b(that)g(the)h(cut)g(\(!\))k(mak)o(es)11 b(selection)1035 1019 y(of)g(this)h(clause)g(a)f Fi(c)n(ommitte)n(d)i(choic)n(e)p Fk(:)k(no)11 b(bac)o(ktrac)o(king)g(will)1035 1065 y(b)q(e)k(done)f(if)f (this)h(c)o(hoice)g(is)g(incorrect.)1077 1111 y(One)f(adv)n(an)o(tage)e(of)h (incorp)q(orating)g(con)o(trol)h(rules)g(in)f(this)1035 1156 y(w)o(a)o(y)17 b(is)g(that)g(matc)o(hing)f(is)h(done)h(b)o(y)f(Prolog's)g (uni\014cation)1035 1202 y(pro)q(cedure;)c(directly)e(using)f(the)h(implemen) o(tatio)o(n)d(language)1035 1248 y(reduces)16 b(the)e(o)o(v)o(erhead)h(of)e (pattern)i(matc)o(hing.)1077 1293 y(If)i(there)j(is)e(more)f(than)h(one)g (con)o(trol)g(rule)g(for)g Fg(c)1885 1299 y Ff(i)1899 1293 y Fk(,)g(then)1035 1339 y(m)o(ultiple)12 b(copies)i(of)g Fg(c)1386 1345 y Ff(i)1413 1339 y Fk(are)h(generated:)k Fi(i.e.)p Fk(,)13 b(m)o(ultiple)f(con-)1035 1385 y(trol)j(rules)g(are)h(in)o(terpreted)h (disjunctiv)o(ely)m(.)k(A)15 b(cop)o(y)g(of)f(the)1035 1430 y(original)h(clause)j(with)f(no)g(\014ltering)g(condition)g(is)g(retained) 1035 1476 y(if)i(and)h(only)f(if)g(some)g(decisions)h(to)g(use)g(that)g (clause)h(are)1035 1522 y(not)14 b(explained)f(b)o(y)h(an)o(y)f(con)o(trol)g (rule.)19 b(Clauses)14 b(in)f(the)i(new)1035 1567 y(program)10 b(are)i(ordered)h(\014rst)g(according)f(to)f(the)i(order)f(of)f(the)1035 1613 y(clauses)g(in)f(the)g(initial)e(program)h(to)h(whic)o(h)g(they)g (corresp)q(ond)1035 1659 y(\(since)18 b(this)g(ordering)f(ma)o(y)f(represen)o (t)k(imp)q(ortan)o(t)15 b(con)o(trol)1035 1704 y(information\),)j(and)h(then) h(according)g(to)f(the)h(ordering)g(of)1035 1750 y(con)o(trol)14 b(rules.)1077 1796 y(No)f(simpli\014cation)e(or)j(compression)g(is)g(done.) 1077 1841 y(Retaining)9 b(the)i(original)d(clauses)k(when)f(some)e(con)o (trol)i(de-)1035 1887 y(cisions)i(are)h(unexplained)g(means)e(that)i(some)e (p)q(erformance)1035 1933 y(impro)o(v)o(emen)o(t)j(can)i(b)q(e)h(gained)f(ev) o(en)h(if)f(con)o(trol)g(rules)h(can)1035 1978 y(only)j(b)q(e)h(learned)f (for)g(some)g(clause)h(selection)g(decisions.)1035 2024 y(This)16 b(mak)o(es)f(the)h(learning)f(system)h(less)h(brittle;)f(ho)o(w)o(ev)o(er,) 1035 2070 y(it)10 b(also)h(means)e(that)i(some)f(bac)o(ktrac)o(king)h(ma)o(y) d(still)i(b)q(e)i(done)1035 2115 y(in)f(the)g(learned)h(program.)j(This)c(is) g(the)h(motiv)o(e)d(for)i(discard-)1035 2161 y(ing)g(the)i(original)d (clauses)j(when)f(all)f(con)o(trol)h(decisions)g(ha)o(v)o(e)1035 2207 y(b)q(een)i(explained,)e(and)h(requiring)f(that)h(learned)g(con)o(trol)g (de-)1035 2252 y(cisions)18 b(are)g(not)f(bac)o(ktrac)o(k)o(ed)h(o)o(v)o(er;) h(otherwise,)g(in)e(bac)o(k-)1035 2298 y(trac)o(king,)11 b(all)g(of)g(the)h (solutions)g(considered)h(b)o(y)e(the)i(original)1035 2344 y(program)d(w)o(ould)h(still)g(ha)o(v)o(e)h(to)g(b)q(e)g(examined)f(and)h (rejected,)1035 2389 y(limiting)h(the)k(degree)h(to)e(whic)o(h)g(p)q (erformance)g(can)h(b)q(e)g(im-)1035 2435 y(pro)o(v)o(ed.)26 b(Ho)o(w)o(ev)o(er,)17 b(discarding)f(clauses)h(also)f(means)g(that)1035 2481 y(the)h(learned)g(program)e(ma)o(y)g(fail)g(on)h(problems)g(whic)o(h)h (are)1035 2526 y(solv)n(able)g(b)o(y)h(the)g(initial)e(program.)29 b(When)18 b(this)g(happ)q(ens)1035 2572 y(the)e(original)d(program)h(is)h(in) o(v)o(ok)o(ed)g(on)g(the)h(top-lev)o(el)f(goal.)1035 2618 y(Th)o(us,)g(in)f (spite)i(of)e(using)h(appro)o(ximate)e(con)o(trol)i(rules)g(and)p eop %%Page: 3 3 3 2 bop -15 -153 a Fk(committed)16 b(c)o(hoice)j(con)o(trol)f(decisions,)i (the)f(learned)g(pro-)-15 -108 y(gram)14 b(alw)o(a)o(ys)h(solv)o(es)i(at)f (least)g(as)g(man)o(y)e(problems)h(as)h(the)-15 -62 y(original)c(program)g (did.)-15 37 y Fj(3)56 b(The)18 b(learning)i(algorithms)-15 114 y Fk(Three)g(learning)e(algorithms)f(w)o(ere)j(exp)q(erimen)o(tally)d (com-)-15 159 y(pared.)25 b(The)17 b(\014rst)g(t)o(w)o(o)f(are)g(stra)o (wmen,)g(corresp)q(onding)h(to)-15 205 y(a)d(con)o(v)o(en)o(tional)g(EBL)h (con)o(trol-rule)g(learning)f(system,)g(and)-15 251 y(to)19 b(an)g(extended)h(EBL)g(learning)e(system)h(whic)o(h)f(uses)j(in-)-15 296 y(ductiv)o(e)c(learning)f(tec)o(hniques)i(to)f(impro)o(v)o(e)d(co)o(v)o (erage,)k(but)-15 342 y(whic)o(h)g(ignores)g(matc)o(h)e(cost.)31 b(The)18 b(third)g(algorithm)d(uses)-15 388 y(inductiv)o(e)e(tec)o(hniques)i (to)e(searc)o(h)i(a)e(space)h(of)f(appro)o(ximate)-15 433 y(rules,)h(and)g (is)f(the)i(main)d(fo)q(cus)i(of)f(this)h(researc)o(h.)27 481 y(One)h(imp)q(ortan)o(t)f(di\013erence)i(b)q(et)o(w)o(een)h(these)f (algorithms)-15 526 y(and)22 b(con)o(v)o(en)o(tional)e(con)o(trol-rule)i (learning)f(algorithms)e(is)-15 572 y(that)h(they)g(are)h Fi(non-incr)n (emental)p Fk(.)36 b(Eac)o(h)20 b(learning)f(algo-)-15 618 y(rithm)14 b(tak)o(es)h(as)h(input)f(a)g(set)h(of)e(examples)h(of)f(correct)j (and)-15 663 y(incorrect)c(con)o(trol)e(decisions,)h(whic)o(h)g(are)g (generated)h(b)o(y)e(ap-)-15 709 y(plying)i(the)h(critic)g(to)g(a)g(large)f (set)i(of)e(traces.)27 757 y Fl(Standard)d(EBL)j(\(EBL\):)e Fk(Standard)h(EBL)g(starts)g(with)-15 802 y(an)i(empt)o(y)f(list)g(of)h(con)o (trol)f(rules,)h(and)g(examines)f(eac)o(h)i(cor-)-15 848 y(rect)j(con)o(trol) e(decision)h(in)f(the)h(order)g(in)g(whic)o(h)f(they)h(w)o(ere)-15 894 y(made.)i(If)c(there)h(are)f(no)f(existing)h(con)o(trol)f(rules)h(whic)o (h)g(ac-)-15 939 y(coun)o(t)21 b(for)f(the)i(decision,)g(then)f(EBG)g(is)g (applied)f(to)g(the)-15 985 y(pro)q(of)e(of)h(the)g(correctness)j(of)c(the)i (con)o(trol)e(decision,)i(and)-15 1031 y(the)g(resulting)g(rule)g(is)f(added) h(to)g(the)g(end)g(of)f(the)h(list)g(of)-15 1076 y(learned)14 b(con)o(trol)g(rules.)367 1061 y Fd(2)27 1124 y Fk(Standard)20 b(EBL)h(is)f(a)g(batc)o(h)h(sim)o(ulation)c(of)j(a)g(SO)o(AR-)-15 1169 y(lik)o(e)14 b(incremen)o(tal)f(learning)h(system)g(whic)o(h)h(uses)g(a) f(learned)-15 1215 y(clause)f(selection)h(rule)f(if)e(one)i(is)g(a)o(v)n (ailable,)d(and)j(whic)o(h)f(oth-)-15 1261 y(erwise)17 b(\014rst)f(uses)h (searc)o(h)g(to)e(determine)h(the)g(righ)o(t)f(clause,)-15 1306 y(then)k(forms)d(a)i(clause)g(selection)h(rule)f(whic)o(h)g(summarizes) -15 1352 y(the)c(results)i(of)d(the)h(searc)o(h)h(pro)q(cess.)27 1399 y Fl(Ab)q(ductiv)o(e)h(EBL)j(\(A-EBL\):)d Fk(Ab)q(ductiv)o(e)h(EBL)h (also)-15 1445 y(starts)e(with)e(an)h(empt)o(y)f(list)g(of)g(con)o(trol)h (rules,)g(but)g(rep)q(eat-)-15 1491 y(edly)21 b(adds)f(to)h(the)g(end)g(of)f (the)h(list)g(the)g(con)o(trol)f(rule)h Fg(R)-15 1536 y Fk(whic)o(h)d(a\))g (is)g Fi(c)n(onsistent)p Fk(,)g Fi(i.e.)p Fk(,)g(do)q(es)h(not)f(explain)f (an)o(y)h(in-)-15 1582 y(correct)g(con)o(trol)f(decisions,)g(and)f(b\))h (maxim)o(izes)d(the)k(ratio)-15 1628 y(of)f(the)g(n)o(um)o(b)q(er)g(of)f (unexplained)i(decisions)f(explained)g(b)o(y)-15 1673 y Fg(R)j Fk(to)f(the)i(size)f(of)f Fg(R)p Fk(.)352 1658 y Fd(3)407 1673 y Fg(R)g Fk(is)h(c)o(hosen)h(from)d(a)h Fi(c)n(andidate)-15 1719 y(p)n(o)n(ol)13 b Fk(of)g(rules)h(whic)o(h)g(consists)g(of)f(all)g (rules)h(whic)o(h)f(could)g(b)q(e)-15 1765 y(generated)20 b(b)o(y)f(applying) f(EBG)h(to)f(some)h(correct)h(con)o(trol)-15 1810 y(decision.)27 1858 y(The)13 b(main)e(lo)q(op)i(in)f(the)i(A-EBL)g(algorithm)c(implemen)o (ts)-15 1903 y(a)19 b(greedy)h(set)g(co)o(v)o(er)f(of)g(the)g(con)o(trol)g (decisions;)j(in)c(other)-15 1949 y(w)o(ords,)f(A-EBL)f(lo)q(oks)g(for)g(a)g (minim)o(al-)o(size)e(set)k(of)d(con)o(trol)-15 1995 y(rules)h(to)g(explain)f (all)f(the)j(con)o(trol)e(decisions.)24 b(The)16 b(greedy)-15 2040 y(set)j(co)o(v)o(er)g(tec)o(hnique)g(has)g(also)f(b)q(een)h(used)g(in)f (Haussler's)-15 2086 y(algorithm)f(for)j(learning)g(disjunctiv)o(e)g(b)q(o)q (olean)g(form)o(ulae.)-15 2132 y(A-EBL)h(has)g(b)q(een)h(used)g(with)e(some)g (success)j(on)e(induc-)-15 2177 y(tiv)o(e)f(learning)f(tasks)348 2173 y([)360 2177 y(Cohen,)i(1989;)d(Cohen,)j(1990)854 2173 y(])865 2177 y(.)35 b(Its)-15 2223 y(main)7 b(adv)n(an)o(tage)i(o)o(v)o(er)g (standard)h(EBL)g(tec)o(hniques)h(for)e(suc)o(h)-15 2269 y(tasks)19 b(is)e(that)h(it)g(can)g(b)q(e)h(used)g(ev)o(en)g(on)e(an)h(\\ab)q(ductiv)o (e")-15 2314 y(domain)10 b(theory)j(|)f(one)h(whic)o(h)g(generates)h(m)o (ultiple)c(incon-)-15 2360 y(sisten)o(t)18 b(explanations.)27 b(A-EBL)17 b(has)h(b)q(een)g(sho)o(wn)f(to)g(sat-)-15 2406 y(isfy)c(V)m(alian)o(t's)e(criterion)j(of)f(pac-learnabilit)o(y)m(,)e(and)i (to)g(ha)o(v)o(e)p -15 2447 250 2 v 37 2474 a Fc(2)54 2490 y Fb(Exp)q(erimen)o(tal)j(studies)422 2487 y([)432 2490 y(Sha)o(vlik,)g(1987) 655 2487 y(])679 2490 y(suggest)e(that)g(this)-15 2532 y(ordering)h(is)e (most)g(b)q(ene\014cial.)37 2560 y Fc(3)54 2576 y Fb(The)f(size)h(of)e(a)h (rule)h(is)f(de\014ned)i(to)d(b)q(e)h(the)h(n)o(um)o(b)q(er)f(of)g(no)q(des) -15 2618 y(in)i(the)f(explanation)j(structure)e(used)f(to)g(form)g(the)g (rule.)1035 -153 y Fk(near-optimal)f(sample)g(complexit)o(y)1629 -157 y([)1641 -153 y(Cohen,)h(1989)1865 -157 y(])1876 -153 y(.)1077 -105 y Fl(Appro)o(ximati)o(ng)18 b(ab)q(ductiv)o(e)h(EBL)i (\(AxA-EBL\):)1035 -60 y Fk(Appro)o(ximating)14 b(ab)q(ductiv)o(e)k(EBL)f(w)o (orks)g(exactly)g(lik)o(e)f(A-)1035 -14 y(EBL,)k(except)i(that)e(the)g (candidate)g(p)q(o)q(ol)g(consists)h(of)e(all)1035 31 y Fg(k)q Fi(-b)n(ounde)n(d)f(appr)n(oximations)f Fk(to)f(a)g(rule)h(generated)g(b)o(y) f(ap-)1035 77 y(plying)i(EBG)i(to)g(some)e(correct)k(con)o(trol)d(decision.) 36 b(A)19 b Fg(k)q Fk(-)1035 123 y(b)q(ounded)14 b(appro)o(ximation)c(is)j (formed)e(b)o(y)i(dropping)g(all)f(but)1035 168 y Fg(j)i Fk(conditions)d (from)f(the)j(b)q(o)q(dy)e(of)g(the)i(rule,)f(for)f(some)g Fg(j)j Fe(\024)e Fg(k)q Fk(.)1077 216 y(A)28 b Fg(k)q Fk(-b)q(ounded)h(appro) o(ximation)c(rule)k(will)e(ha)o(v)o(e)h(lo)o(w)1035 262 y(matc)o(h)15 b(cost,)i(unless)h(the)e(op)q(erational)g(conditions)g(are)h(ex-)1035 308 y(p)q(ensiv)o(e)24 b(to)g(test.)48 b(F)m(or)23 b(example,)h(if)f(the)h (truth)g(of)f(op-)1035 353 y(erational)18 b(conditions)h(is)h(tested)g(b)o(y) f(database)h(lo)q(okup)e(in)1035 399 y(a)i(database)h(of)f Fg(n)h Fk(facts,)h(then)f(the)g(matc)o(h)f(cost)h(of)f(a)g Fg(k)q Fk(-)1035 445 y(b)q(ounded)15 b(appro)o(ximatio)o(n)c(is)j Fg(O)q Fk(\()p Fg(n)1597 430 y Ff(k)1617 445 y Fk(\).)1077 493 y(AxA-EBL)j(is)f(more)g(computationally)e(exp)q(ensiv)o(e)k(than)1035 538 y(EBL;)11 b(it)g(runs)h(in)f(time)f(p)q(olynomial)e(in)j(the)h(total)f (size)h(of)e(the)1035 584 y(pro)q(ofs)17 b(of)f(the)i(con)o(trol)f (decisions,)g(but)g(exp)q(onen)o(tial)g(in)g Fg(k)q Fk(.)1035 630 y(Hence,)d(only)f(small)e(v)n(alues)i(of)g Fg(k)h Fk(can)f(b)q(e)h(used.) 19 b(In)13 b(the)h(cur-)1035 675 y(ren)o(t)e(implem)o(en)o(tation,)c(t)o(w)o (o)j(tec)o(hniques)h(are)f(used)h(to)f(prune)1035 721 y(the)19 b(searc)o(h)g(space)g(of)e(appro)o(ximate)g(rules:)27 b(Prolog)17 b(mo)q(de)1035 767 y(declarations)f(are)g(used)h(to)e(eliminate)f(ill-formed) f(appro)o(xi-)1035 812 y(mations,)e(and)j(an)g(admissible)d(heuristic)k (searc)o(h)g(is)e(used)i(to)1035 858 y(\014nd)g(the)h(optimal)c(rule)k(from)d (the)j(candidate)f(p)q(o)q(ol.)21 b(These)1035 904 y(tric)o(ks)c(substan)o (tially)f(reduce)i(learning)e(time;)g(the)h(curren)o(t)1035 949 y(implemen)o(tatio)o(n)12 b(of)h(AxA-EBL)i(tak)o(es)g(an)e(a)o(v)o(erage) i(of)e(15.5)1035 995 y(CPU)k(min)o(utes)e(on)h(a)h(Sun/4)f(to)g(pro)q(cess)i (120)e(traces)i(from)1035 1041 y(the)d(STRIPS)f(rob)q(ot-w)o(orld)f(domain)f (describ)q(ed)k(b)q(elo)o(w.)i(\(It)1035 1086 y(tak)o(es)11 b(ab)q(out)f(20)f(min)o(utes)g(to)h(solv)o(e)g(the)h(120)e(problems)g(using) 1035 1132 y(the)14 b(original)f(means-ends)g(analysis)g(planner.\))1077 1180 y(A-EBL)h(is)f(also)h(computationally)c(exp)q(ensiv)o(e,)15 b(but)f(for)f(a)1035 1226 y(di\013eren)o(t)h(reason:)k(to)c(\014nd)f(the)h (optimal)c(rule)k(in)e(the)i(candi-)1035 1271 y(date)d(p)q(o)q(ol,)f(eac)o(h) i(candidate)f(m)o(ust)e(b)q(e)j(tested)g(against)e(ev)o(ery)1035 1317 y(con)o(trol)j(decision.)18 b(This)13 b(is)g(v)o(ery)g(exp)q(ensiv)o(e)h (if)f(rules)g(ha)o(v)o(e)g(a)1035 1363 y(high)g(matc)o(h)g(cost.)1077 1411 y(Standard)20 b(EBL,)h(A-EBL,)g(and)g(AxA-EBL)g(share)g(t)o(w)o(o)1035 1456 y(prop)q(erties)f(whic)o(h)e(app)q(ear)g(to)g(b)q(e)h(crucial)f(for)g (success)i(on)1035 1502 y(this)d(learning)f(task.)26 b(First,)18 b(all)d(three)j(algorithms)c(can)j(b)q(e)1035 1548 y(constrained)d(to)f(pro)q (duce)h(rules)g(whic)o(h)f(con)o(tain)g(only)f(op)q(er-)1035 1593 y(ational)i(features.)22 b(Second,)16 b(lik)o(e)e(standard)i(EBL,)f(b)q (oth)g(A-)1035 1639 y(EBL)f(and)f(AxA-EBL)g(usually)g(learn)g Fi(sever)n(al)f Fk(con)o(trol)h(rules)1035 1685 y(whic)o(h)18 b(determine)g(when)h(a)f(particular)g(clause)h(should)f(b)q(e)1035 1730 y(selected:)26 b(in)16 b(other)i(w)o(ords,)f(the)h(concept)g(of)e (\\usefulness")1035 1776 y(for)11 b(eac)o(h)h(clause)g(can)f(b)q(e)h Fi(disjunctively)g Fk(de\014ned.)18 b(The)12 b(latter)1035 1822 y(prop)q(ert)o(y)j(is)e(imp)q(ortan)o(t)g(b)q(ecause)i(man)o(y)d(Prolog) h(programs)1035 1867 y(con)o(tain)20 b(clauses)i(whic)o(h)f(are)g(useful)f (in)h(sev)o(eral)g(di\013eren)o(t)1035 1913 y(situations.)27 b(Usually)m(,)17 b(sev)o(eral)g(con)o(trol)g(rules,)h(in)o(terpreted)1035 1959 y(disjunctiv)o(ely)m(,)e(will)f(b)q(e)i(needed)h(to)e(determine)g(when)h (suc)o(h)1035 2004 y(a)d(clause)g(is)g(useful.)1077 2052 y(A-EBL)h(and)g (AxA-EBL)h(di\013er)g(in)f(these)i(resp)q(ects)h(from)1035 2098 y(other)31 b(inductiv)o(e)g(extensions)h(to)e(EBL,)h(in)f(particular) 1035 2144 y(mEBG)13 b(and)g(IOE)1344 2140 y([)1355 2144 y(Flann)h(and)f (Dietteric)o(h,)h(1989)1845 2140 y(])1856 2144 y(.)1035 2245 y Fj(4)56 b(Exp)r(erimen)n(tal)18 b(results)1035 2323 y Fl(4.1)48 b(Descriptio)o(n)13 b(of)i(the)g(domains)1077 2387 y Fk(Exp)q(erimen)o (tation)21 b(has)h(b)q(een)i(done)f(with)f(these)i(three)1035 2433 y(learning)14 b(algorithms)f(in)i(sev)o(eral)h(domains.)j(The)d(domains) 1035 2478 y(are)e(summarized)e(in)i(T)m(able)f(1.)1077 2526 y Fg(\026)p Fl(LEX:)g Fk(A)g(simpli\014ed)f(v)o(ersion)h(of)f(sym)o(b)q(olic) g(in)o(tegration)1035 2572 y(using)f(state-space)i(searc)o(h)g(with)e (iterativ)o(e)g(deep)q(ening.)19 b(The)1035 2618 y(training)10 b(and)h(test)h(problem)d(sets)k(and)e(the)g(op)q(erator)h(set)g(are)p eop %%Page: 4 4 4 3 bop 535 -125 a Fk(T)m(able)13 b(1:)18 b(Summary)11 b(of)i(domains)f(used) j(in)e(exp)q(erimen)o(ts)p 156 -73 1684 2 v 155 -28 2 46 v 181 -41 a(Domain)p 347 -28 V 356 -28 V 55 w(Description)p 782 -28 V 219 w(Searc)o(h)p 1039 -28 V 140 w(Num)o(b)q(er)g(of)p 1283 -28 V 50 w(T)m(raining)f(Set)p 1640 -28 V 132 w(T)m(est)j(Set)p 1838 -28 V 155 18 V 347 18 V 356 18 V 782 18 V 807 4 a(Strategy)p 1039 18 V 117 w(Op)q(erators)p 1283 18 V 52 w(Sizes)p 1640 18 V 347 w(Size)p 1838 18 V 156 20 1684 2 v 156 30 V 155 75 2 46 v 181 62 a Fg(\026)p Fk(LEX)p 347 75 V 356 75 V 90 w(simpli\014ed)d(LEX) p 782 75 V 154 w(state-space)p 1039 75 V 213 w(36)p 1283 75 V 50 w(4,8,12,16,)o(19)p 1640 75 V 249 w(13)p 1838 75 V 155 121 V 181 107 a(R)-5 b(W)p 347 121 V 356 121 V 131 w(STRIPS)14 b(rob)q(ot)g(w)o(orld)p 782 121 V 49 w(means-ends)p 1039 121 V 202 w(10)p 1283 121 V 50 w(5,15,25,45,)o(80,)o(120)p 1640 121 V 154 w(50)p 1838 121 V 155 167 V 181 153 a(BW)p 347 167 V 356 167 V 128 w(Nilsson)g(blo)q(c)o(ks)g(w)o(orld)p 782 167 V 54 w(means-ends)p 1039 167 V 223 w(4)p 1283 167 V 50 w(5,15,25,45,)o(80,)o (120)p 1640 167 V 133 w(100)p 1838 167 V 155 212 V 181 199 a(GRID)p 347 212 V 356 212 V 89 w(graph)g(searc)o(h)p 782 212 V 197 w(depth-\014rst)p 1039 212 V 243 w(3)p 1283 212 V 50 w(5,10,15,25)p 1640 212 V 260 w(100)p 1838 212 V 156 214 1684 2 v -15 359 a(tak)o(en)g(from)196 355 y([)208 359 y(Keller,)g(1987)426 355 y(])436 359 y(.)27 407 y Fl(R)-5 b(W:)9 b Fk(The)h(STRIPS)f(rob)q(ot)g(w) o(orld)g(of)629 403 y([)640 407 y(Fik)o(es)h Fi(et)h(al.)p Fk(,)e(1972)938 403 y(])948 407 y(,)-15 453 y(with)k(a)g(means-ends)h (analysis)e(planner.)19 b(Problems)12 b(for)h(the)-15 498 y(training)d(and)h (test)i(set)f(are)g(generated)g(b)o(y)f(selecting)h(a)f(\015o)q(or-)-15 544 y(plan)h(randomly)e(from)h(the)i(three)h(giv)o(en)e(in)687 540 y([)698 544 y(Min)o(ton,)g(1988)938 540 y(])948 544 y(,)-15 590 y(randomly)7 b(placing)i(3)g(blo)q(c)o(ks)h(and)f(the)i(rob)q(ot,)f(and)f (then)h(tak-)-15 635 y(ing)j(a)h(random)e(w)o(alk)h(of)g(b)q(ounded)i(length) f(in)f(state)i(space.)27 683 y Fl(BW:)g Fk(The)h(blo)q(c)o(ks)f(w)o(orld)f (of)516 679 y([)527 683 y(Nilsson,)h(1987)769 679 y(])780 683 y(,)g(with)f(the)-15 729 y(iden)o(tical)j(means-ends)g(analysis)g(planner.)29 b(Problems)17 b(are)-15 774 y(generated)c(b)o(y)e(constructing)h(an)g (initial)d(scene)k(with)e(20)g(ran-)-15 820 y(domly)i(placed)i(blo)q(c)o(ks,) g(and)g(then)h(taking)e(a)h(random)e(w)o(alk)-15 866 y(of)g(b)q(ounded)i (length)f(in)f(state)i(space.)27 913 y Fl(GRID:)d Fk(Depth-b)q(ounded)j (depth-\014rst)f(searc)o(h)h(of)e(an)g(ar-)-15 959 y(ti\014cial)20 b(graph.)40 b(The)22 b(graph)f(is)g(a)g(15x15)f(grid,)j(with)d(75)-15 1005 y(randomly)h(placed)i(obstacles,)j(and)c(5)h(randomly)e(placed)-15 1050 y(\\cities",)16 b(whic)o(h)g(are)g(tigh)o(tly)f(connected)i(b)o(y)f(a)f (net)o(w)o(ork)i(of)-15 1096 y(\014v)o(e)h(\\in)o(terstate)h(high)o(w)o(a)o (ys".)30 b(There)19 b(are)g(three)g(kinds)g(of)-15 1142 y(op)q(erationally)c (di\013eren)o(t)j(connections)g(in)e(the)h(graph,)g(cor-)-15 1187 y(resp)q(onding)g(to)f(increasing)h(or)f(decreasing)i(the)f(v)n(alue)e (of)h(a)-15 1233 y(co)q(ordinate)11 b(b)o(y)g(1)g(or)g(follo)o(wing)d(an)j (\\in)o(terstate".)18 b(Problems)-15 1279 y(are)12 b(selected)i(b)o(y)d (randomly)f(pic)o(king)h(start)i(and)e(end)i(p)q(oin)o(ts,)-15 1324 y(and)h(asking)f(for)g(a)h(path)g(b)q(et)o(w)o(een)h(the)g(p)q(oin)o (ts.)27 1372 y(BW)e(and)g(R)-5 b(W)13 b(problems)g(can)h(b)q(e)g(quite)f (di\016cult,)g(so)g(the)-15 1418 y(planner)j(includes)h(t)o(w)o(o)f(resource) i(b)q(ounds:)23 b(\014rst,)17 b(a)f(b)q(ound)-15 1463 y(on)c(the)h(maxim)o (al)c(length)j(of)g(the)h(plan,)f(and)g(second,)h(a)f(time)-15 1509 y(b)q(ound.)17 b(The)11 b(time)d(b)q(ound)j(w)o(as)f(set)h(at)f(60)g (seconds)i(for)e(these)-15 1555 y(exp)q(erimen)o(ts:)21 b(almost)14 b(all)g(of)h(the)h(blo)q(c)o(ks)f(w)o(orld)g(problems)-15 1600 y(and)e(ab)q(out)h(6/7)e(of)h(the)h(rob)q(ot)g(w)o(orld)f(problems)f(w)o(ere) j(solv-)-15 1646 y(able)f(in)f(this)h(time)f(b)q(ound.)27 1693 y(The)d(domains)e(are)j(listed)f(roughly)f(in)h(order)h(of)e(their)i(di\016-) -15 1739 y(cult)o(y)g(for)g(standard)g(EBL)h(tec)o(hniques.)19 b(F)m(or)10 b(instance,)i(sym-)-15 1785 y(b)q(olic)e(in)o(tegration)g(is)h(w) o(ell)f(suited)i(to)f(use)g(of)g(EBL)g(for)g(op)q(era-)-15 1830 y(tor)f(selection;)h(ho)o(w)o(ev)o(er,)f(unconstrained)g(use)h(of)d(EBL) i(in)f(the)-15 1876 y(blo)q(c)o(ks)18 b(w)o(orld)e(domain)g(can)h(lead)h(to)f (sw)o(amping)805 1872 y([)817 1876 y(Min)o(ton,)-15 1922 y(1988;)d(Mo)q(oney) m(,)h(1989)347 1918 y(])357 1922 y(.)22 b(Graph)15 b(searc)o(hing)h(is)f(a)g (v)o(ery)h(di\016-)-15 1967 y(cult)11 b(problem)f(for)h(standard)h(EBL)g(tec) o(hniques)g(b)q(ecause)h(the)-15 2013 y(matc)o(h)h(cost)h(of)g(learned)g (rules)h(is)f(v)o(ery)g(high,)f(and)h(the)g(cost)-15 2059 y(of)j(problem)e (solving)h(without)h(an)o(y)g(learned)h(rules)f(is)g(lo)o(w;)-15 2104 y(matc)o(hing)g(the)i(rules)h(learned)f(b)o(y)f(EBL)i(is)e(equiv)n(alen) o(t)g(to)-15 2150 y(solving)12 b(the)h(NP-complete)g(subgraph)g(isomorphism)d (prob-)-15 2196 y(lem)70 2192 y([)82 2196 y(Min)o(ton,)21 b(1988)331 2192 y(])342 2196 y(,)h(whereas)g(depth-\014rst)g(searc)o(h)g(only)-15 2241 y(requires)15 b(time)e(linear)g(in)h(the)g(size)h(of)e(the)h(graph.)-15 2326 y Fl(4.2)48 b(Comparison)14 b(of)h(EBL)h(and)f(AxA-EBL)27 2389 y Fk(A)f(series)i(of)d(exp)q(erimen)o(ts)i(w)o(ere)g(designed)g(to)f (determine)-15 2435 y(ho)o(w)j(the)g(p)q(erformance)g(of)g(a)f(learned)i (program)d(v)n(aried)i(as)-15 2481 y(a)c(function)g(of)g(the)h(n)o(um)o(b)q (er)f(of)f(training)h(examples)f(used)i(in)-15 2526 y(learning.)30 b(In)18 b(eac)o(h)h(exp)q(erimen)o(t,)f(\014rst)h(a)f Fi(test)g(set)p Fk(,)h(of)e(the)-15 2572 y(size)f(indicated)g(in)g(table)f(1,)h(w)o(as)f (selected.)26 b(In)15 b(the)i(case)g(of)-15 2618 y(BW,)11 b(R)-5 b(W)11 b(and)h(GRID,)d(the)j(test)h(problems)e(w)o(ere)h(randomly)1035 359 y(selected;)19 b(in)d Fg(\026)p Fk(LEX,)h(the)g(test)h(problems)d(w)o (ere)j(the)f(desig-)1035 405 y(nated)12 b(test)h(problems)d(in)1448 401 y([)1460 405 y(Keller,)i(1987)1676 401 y(])1698 405 y(\(problem)e(sets)j (A)m(T)1035 451 y(and)h(BT.\))g(Then)g(a)f Fi(tr)n(aining)i(set)e Fk(w)o(as)h(selected,)h(again)e(ran-)1035 496 y(domly)j(for)h(BW,)h(R)-5 b(W)17 b(and)h(GRID,)e(and)h(from)g(the)h(desig-)1035 542 y(nated)e(training) f(problems)g(\(problems)g(sets)i(A)e(and)h(B\))g(for)1035 588 y Fg(\026)p Fk(LEX.)e(Progressiv)o(ely)g(larger)g(subsets)h(of)f(the)g (training)f(set)1035 633 y(w)o(ere)j(then)g(giv)o(en)f(to)g(eac)o(h)h (learning)f(system,)g(again)f(as)i(in-)1035 679 y(dicated)f(in)g(table)g(1,)f (and)h(the)h(con)o(trol)f(rules)g(learned)h(from)1035 725 y(eac)o(h)h(subset) h(w)o(ere)g(applied)e(to)h(the)g(problems)f(in)h(the)g(test)1035 770 y(set.)i(Tw)o(o)14 b(statistics)g(w)o(ere)h(k)o(ept.)k(First,)14 b(the)g Fi(total)h(time)e Fk(re-)1035 816 y(quired)j(to)f(solv)o(e)g(all)f (of)h(the)h(test)g(problems)e(w)o(as)i(recorded.)1035 862 y(The)c(second)g (statistic)f(k)o(ept)h(w)o(as)f(the)h Fi(c)n(over)n(age)f Fk(of)g(the)g(set)i (of)1035 907 y(con)o(trol)f(rules:)18 b(the)12 b(p)q(ercen)o(tage)i(of)e(the) h(test)g(problems)e(that)1035 953 y(the)16 b(learner)h(program)d(solv)o(ed)i (directly)m(,)g(without)f(recourse)1035 999 y(to)f(the)h(original)e(program.) 1475 984 y Fd(4)1512 999 y Fk(These)i(exp)q(erimen)o(ts)g(w)o(ere)g(re-)1035 1044 y(p)q(eated)k(ten)f(times,)g(and)f(the)i(results)f(w)o(ere)h(a)o(v)o (eraged.)30 b(In)1035 1090 y(BW,)17 b(R)-5 b(W)16 b(and)h(GRID,)f(eac)o(h)h (trial)f(used)i(a)f(di\013eren)o(t)h(ran-)1035 1136 y(domly)13 b(selected)k(training)e(set;)h(in)f Fg(\026)p Fk(LEX,)h(eac)o(h)f(trial)g (used)1035 1181 y(a)f(di\013eren)o(t)g(ordering)g(of)g(the)g(\014xed)h (training)d(set.)1077 1228 y(Appro)o(ximations)h(in)i(the)h(domains)d(w)o (ere)k(c)o(hosen)f(b)o(y)g(in-)1035 1273 y(cremen)o(ting)f Fg(k)h Fk(un)o(til)f(either)h(some)f(p)q(erformance)g(impro)o(v)o(e-)1035 1319 y(men)o(t)e(o)q(ccurred,)i(or)f(un)o(til)f(the)h(cost)h(of)e(running)g (AxA-EBL)1035 1365 y(b)q(ecame)19 b(excessiv)o(e.)34 b(One)20 b(of)e(the)i(surprises)g(of)f(these)h(ex-)1035 1410 y(p)q(erimen)o(ts)12 b(w)o(as)f(the)i(expressiv)o(eness)h(of)d(a)h(language)f(of)g(v)o(ery)1035 1456 y(short)21 b(appro)o(ximations:)29 b(in)20 b(all)g(of)g(the)h(domains)e (except)1035 1502 y(GRID,)9 b(substan)o(tial)g(p)q(erformance)i(impro)o(v)o (em)o(en)o(t)d(o)q(ccurred)1035 1547 y(using)14 b(AxA-EBL)g(with)g Fg(k)e Fe(\024)g Fk(2.)1077 1594 y(The)h(results)i(of)d(these)j(exp)q(erimen) o(ts)e(are)h(summarized)d(in)1035 1639 y(table)j(2.)19 b(The)c(crucial)f (column)f(of)g(table)h(2)g(is)g(the)h(last)f(one,)1035 1685 y(whic)o(h)c(sho)o(ws)g(the)h(ratio)e(of)g(the)i(time)d(sp)q(en)o(t)j(b)o(y)f (the)h(program)1035 1731 y(learned)19 b(b)o(y)f(AxA-EBL)g(in)g(solving)f(the) i(problems)e(of)g(the)1035 1776 y(test)g(set)f(to)g(the)g(time)e(sp)q(en)o(t) j(b)o(y)e(the)h(program)e(learned)i(b)o(y)1035 1822 y(EBL.)c(AxA-EBL)h(is)g (marginall)o(y)d(slo)o(w)o(er)i(than)g(EBL)h(on)f(the)1035 1868 y Fg(\026)p Fk(LEX)g(domain,)d(and)i(substan)o(tially)g(faster)h(on)f (the)i(remain-)1035 1913 y(ing)k(domains;)h(o)o(v)o(erall,)f(the)h(programs)f (learned)h(b)o(y)g(AxA-)1035 1959 y(EBL)e(are)g(ab)q(out)f(t)o(wice)h(as)g (fast)f(as)h(the)g(programs)e(learned)1035 2005 y(b)o(y)g(EBL.)1077 2051 y(The)f(results)i(of)e(the)h(exp)q(erimen)o(t)f(are)h(giv)o(en)f(in)g (more)g(de-)1035 2097 y(tail)k(Figure)h(1)g(and)g(Figure)g(2.)30 b(These)19 b(\014gures)g(graph)f(the)1035 2142 y(a)o(v)o(erage)12 b(time)f(sp)q(en)o(t)i(b)o(y)f(a)f(learned)i(program,)d(and)i(also)f(the)1035 2188 y(a)o(v)o(erage)g(co)o(v)o(erage)h(of)f(the)h(learned)g(program)e(\()p Fi(i)t Fg(:)p Fi(e)s Fg(:)o Fk(,)h(the)h(p)q(er-)1035 2234 y(cen)o(tage)f(of)e(the)i(time)d(that)i(it)g(w)o(as)g Fi(not)g Fk(necessary)i(to)e(go)f(bac)o(k)1035 2279 y(and)14 b(use)g(the)g(original)e (program)g(to)i(solv)o(e)f(a)h(problem\))e(as)i(a)1035 2325 y(function)g(of)f(the)h(n)o(um)o(b)q(er)g(of)f(training)g(examples)g(giv)o (en.)1077 2371 y(The)20 b(three)i(learning)e(tec)o(hniques)i(b)q(eha)o(v)o (ed)f(essen)o(tially)p 1035 2409 250 2 v 1087 2436 a Fc(4)1104 2451 y Fb(Recall)11 b(that)e(the)f(program)i(whic)o(h)g(incorp)q(orates)g (the)f(learned)1035 2493 y(con)o(trol)j(rules)h(ma)o(y)e(fail)h(if)g(not)f (enough)i(con)o(trol)f(rules)g(ha)o(v)o(e)g(b)q(een)1035 2534 y(learned,)h(or)f(if)g(some)h(of)e(the)h(con)o(trol)i(rules)f(are)f (incorrect.)17 b(If)12 b(the)1035 2576 y(program)j(fails,)h(then)g(the)e (original)k(problem)e(solv)o(er)g(is)f(in)o(v)o(ok)o(ed)1035 2618 y(on)e(the)g(problem.)p eop %%Page: 5 5 5 4 bop -15 -172 2025 2 v 326 1115 a Fg(\026)p Fk(LEX)14 b(Time)1318 1123 y Fg(\026)p Fk(LEX)g(Co)o(v)o(erage)326 2437 y(GRID)f(Time)1291 2441 y(GRID)f(Co)o(v)o(erage)398 2586 y(Figure)i(1:)k(P)o(erformance)13 b(and)h(Co)o(v)o(erage)g(Curv)o(es)h(for)e Fg(\026)p Fk(LEX)h(and)g(GRID)p -15 2596 V eop %%Page: 6 6 6 5 bop -15 -163 2025 2 v 346 1119 a Fk(R)-5 b(W)14 b(Time)1339 1115 y(R)-5 b(W)13 b(Co)o(v)o(erage)345 2437 y(BW)h(Time)910 2387 y @beginspecial -10 @hoffset -360 @voffset 0.450000 @hscale 0.450000 @vscale @setspecial %%BeginDocument: bwcvg.ps /X-CENTER-PLOT 1 def /Y-CENTER-PLOT 1 def clippath pathbbox /page-height exch def /page-width exch def pop pop 538.583 page-width gt { % Rotation required 0 page-width neg translate % Handle centering Y-CENTER-PLOT 1 eq { % Center in y page-height 538.583 sub 2 div } { % Don't center in y 0 } ifelse X-CENTER-PLOT 1 eq { % Center in x page-width 538.583 sub 2 div } { % Don't center in x 0 } ifelse translate } { % No rotation - just handle centering X-CENTER-PLOT 1 eq { % Center in x page-width 538.583 sub 2 div } { % Don't center in x 0 } ifelse Y-CENTER-PLOT 1 eq { % Center in y page-height 538.583 sub 2 div } { % Don't center in y 0 } ifelse translate } ifelse 0.06 0.06 scale /choose-font % stack: fontsize fontname => --- { findfont exch scalefont setfont newpath 0 0 moveto (0) true charpath flattenpath pathbbox /top exch def pop /bottom exch def pop bottom top bottom top add 2 div /center-font-val exch def /upper-font-val exch def /lower-font-val exch def } def /center-x-just % stack: (string) x y => (string) newx y { exch 2 index stringwidth pop 2 div sub exch } def /left-x-just % stack: (string) x y => (string) newx y { } def /right-x-just % stack: (string) x y => (string) newx y { exch 2 index stringwidth pop sub exch } def /center-y-just % stack: (string) x y => (string) x newy { center-font-val sub } def /lower-y-just % stack: (string) x y => (string) x newy { lower-font-val sub } def /upper-y-just % stack: (string) x y => (string) x newy { upper-font-val sub } def /just-string % stack: (string) x y just => --- { dup 0 eq { pop center-x-just center-y-just } if dup 1 eq { pop left-x-just center-y-just } if dup 2 eq { pop left-x-just upper-y-just } if dup 3 eq { pop center-x-just upper-y-just } if dup 4 eq { pop right-x-just upper-y-just } if dup 5 eq { pop right-x-just center-y-just } if dup 6 eq { pop right-x-just lower-y-just } if dup 7 eq { pop center-x-just lower-y-just } if dup 8 eq { pop left-x-just lower-y-just } if moveto show } def /mark0 {/size exch def /y exch def /x exch def newpath x size sub y size sub moveto size size add 0 rlineto 0 size size add rlineto 0 size size add sub 0 rlineto closepath fill} def /mark1 {/size exch def /y exch def /x exch def newpath x size sub y size sub moveto size size add 0 rlineto 0 size size add rlineto 0 size size add sub 0 rlineto closepath stroke} def /mark2 {/size exch def /y exch def /x exch def newpath x y moveto x y size 0 360 arc stroke} def /mark3 {/size exch def /y exch def /x exch def newpath x size sub y size sub moveto x size add y size add lineto x size sub y size add moveto x size add y size sub lineto stroke} def /mark4 {/size exch def /y exch def /x exch def newpath x size sub y moveto x y size add lineto x size add y lineto x y size sub lineto closepath stroke} def /mark5 {/size exch def /y exch def /x exch def x y size mark1 newpath x size sub y moveto size size add 0 rlineto stroke} def /mark6 {/size exch def /y exch def /x exch def newpath x y moveto x y size 0 360 arc fill} def /mark7 {/size exch def /y exch def /x exch def newpath x y moveto x size sub y size sub lineto x size add y size sub lineto closepath fill newpath x y moveto x size add y size add lineto x size sub y size add lineto closepath fill} def 300 /Times-Bold choose-font () 4488 8856 3 just-string 200 /Times-Roman choose-font (no learning) 7236 8104 2 just-string (EBL) 7236 7812 2 just-string (A-EBL) 7236 7520 2 just-string (AxA-EBL) 7236 7228 2 just-string 14 setlinewidth [] 0 setdash newpath 7236 8136 moveto 8886 8136 lineto stroke 14 setlinewidth [25] 0 setdash newpath 7236 7844 moveto 8886 7844 lineto stroke 14 setlinewidth [50] 0 setdash newpath 7236 7552 moveto 8886 7552 lineto stroke 14 setlinewidth [75] 0 setdash newpath 7236 7260 moveto 8886 7260 lineto stroke (Accuracy) 90 8496 2 just-string (Training Examples) 8886 380 5 just-string (30.00) 860 514 5 just-string (35.00) 860 1031 5 just-string (40.00) 860 1548 5 just-string (45.00) 860 2066 5 just-string (50.00) 860 2583 5 just-string (55.00) 860 3100 5 just-string (60.00) 860 3617 5 just-string (65.00) 860 4134 5 just-string (70.00) 860 4652 5 just-string (75.00) 860 5169 5 just-string (80.00) 860 5686 5 just-string (85.00) 860 6203 5 just-string (90.00) 860 6720 5 just-string (95.00) 860 7238 5 just-string (100.00) 860 7755 5 just-string (0) 987 90 7 just-string (20) 1966 90 7 just-string (40) 2946 90 7 just-string (60) 3926 90 7 just-string (80) 4905 90 7 just-string (100) 5885 90 7 just-string (120) 6864 90 7 just-string [] 0 setdash 2 setlinewidth newpath 950 514 moveto 1100 514 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 514 moveto 7146 514 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 1031 moveto 1100 1031 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 1031 moveto 7146 1031 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 1548 moveto 1100 1548 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 1548 moveto 7146 1548 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 2066 moveto 1100 2066 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 2066 moveto 7146 2066 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 2583 moveto 1100 2583 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 2583 moveto 7146 2583 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 3100 moveto 1100 3100 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 3100 moveto 7146 3100 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 3617 moveto 1100 3617 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 3617 moveto 7146 3617 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 4134 moveto 1100 4134 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 4134 moveto 7146 4134 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 4652 moveto 1100 4652 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 4652 moveto 7146 4652 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 5169 moveto 1100 5169 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 5169 moveto 7146 5169 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 5686 moveto 1100 5686 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 5686 moveto 7146 5686 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 6203 moveto 1100 6203 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 6203 moveto 7146 6203 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 6720 moveto 1100 6720 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 6720 moveto 7146 6720 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 7238 moveto 1100 7238 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 7238 moveto 7146 7238 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 7755 moveto 1100 7755 lineto stroke [] 0 setdash 2 setlinewidth newpath 6996 7755 moveto 7146 7755 lineto stroke [] 0 setdash 8 setlinewidth newpath 987 8106 moveto 987 7956 lineto stroke [] 0 setdash 8 setlinewidth newpath 987 530 moveto 987 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 1966 8106 moveto 1966 7956 lineto stroke [] 0 setdash 2 setlinewidth newpath 1966 530 moveto 1966 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 2946 8106 moveto 2946 7956 lineto stroke [] 0 setdash 2 setlinewidth newpath 2946 530 moveto 2946 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 3926 8106 moveto 3926 7956 lineto stroke [] 0 setdash 2 setlinewidth newpath 3926 530 moveto 3926 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 4905 8106 moveto 4905 7956 lineto stroke [] 0 setdash 2 setlinewidth newpath 4905 530 moveto 4905 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 5885 8106 moveto 5885 7956 lineto stroke [] 0 setdash 2 setlinewidth newpath 5885 530 moveto 5885 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 6864 8106 moveto 6864 7956 lineto stroke [] 0 setdash 2 setlinewidth newpath 6864 530 moveto 6864 380 lineto stroke [] 0 setdash 2 setlinewidth newpath 950 8106 moveto 950 380 lineto 7146 380 lineto 7146 8106 lineto 950 8106 lineto stroke 14 setlinewidth [] 0 setdash newpath 1232 7755 moveto 6864 7755 lineto stroke 14 setlinewidth [25] 0 setdash newpath 1232 731 moveto 1721 3100 lineto 2211 3317 lineto 3191 3617 lineto 4905 3959 lineto 6864 4021 lineto stroke 14 setlinewidth [50] 0 setdash newpath 1232 4145 moveto 1721 6627 lineto 2211 7672 lineto 3191 7641 lineto 4905 7672 lineto 6864 7610 lineto stroke 14 setlinewidth [75] 0 setdash newpath 1232 4496 moveto 1721 6472 lineto 2211 6845 lineto 3191 7279 lineto 4905 7517 lineto 6864 7579 lineto stroke %%EndDocument @endspecial 1310 2433 a(BW)g(Co)o(v)o(erage)438 2578 y(Figure)g(2:)k(P)o (erformance)13 b(and)h(Co)o(v)o(erage)g(Curv)o(es)g(for)g(R)-5 b(W)13 b(and)h(BW)p -15 2588 V eop %%Page: 7 7 7 6 bop 614 -125 a Fk(T)m(able)13 b(2:)18 b(Summary)11 b(of)j(exp)q(erimen)o (tal)f(results)p 402 -73 1191 2 v 401 -28 2 46 v 427 -41 a(Domain)p 598 -28 V 607 -28 V 114 w(Av)o(erage)i(Time)d(on)i(T)m(est)g(Problems)p 1352 -28 V 1361 -28 V 1360 -28 V 112 w(AxA-EBL)p 1386 -34 182 2 v 1592 -28 2 46 v 401 18 V 598 18 V 607 18 V 632 4 a(Nolearn)p 798 18 V 61 w(EBL)p 942 18 V 50 w(A-EBL)p 1121 18 V 50 w(AxA-EBL)p 1352 18 V 1361 18 V 1360 18 V 108 w(EBL)p 1592 18 V 402 20 1191 2 v 402 30 V 401 75 2 46 v 427 62 a Fg(\026)p Fk(LEX)p 598 75 V 607 75 V 142 w(2.019)p 798 75 V 49 w(0.103)p 942 75 V 82 w(0.103)p 1121 75 V 135 w(0.104)p 1352 75 V 1361 75 V 165 w(1.01)p 1592 75 V 401 121 V 427 107 a(R)-5 b(W)p 598 121 V 607 121 V 183 w(9.956)p 798 121 V 49 w(2.768)p 942 121 V 82 w(0.922)p 1121 121 V 135 w(1.596)p 1352 121 V 1361 121 V 165 w(0.58)p 1592 121 V 401 167 V 427 153 a(BW)p 598 167 V 607 167 V 180 w(3.150)p 798 167 V 49 w(2.553)p 942 167 V 82 w(4.774)p 1121 167 V 135 w(0.987)p 1352 167 V 1361 167 V 165 w(0.39)p 1592 167 V 401 212 V 427 199 a(GRID)p 598 212 V 607 212 V 141 w(0.137)p 798 212 V 49 w(0.361)p 942 212 V 82 w(0.423)p 1121 212 V 135 w(0.268)p 1352 212 V 1361 212 V 165 w(0.74)p 1592 212 V 402 214 1191 2 v 401 260 2 46 v 427 246 a(Av)o(erage)p 598 260 V 607 260 V 106 w(4.320)p 798 260 V 49 w(1.447)p 942 260 V 82 w(1.555)p 1121 260 V 135 w(0.739)p 1352 260 V 1361 260 V 165 w(0.51)p 1592 260 V 402 261 1191 2 v -15 407 a(iden)o(tically)14 b(on)h(the)h Fg(\026)p Fk(LEX)f(domain.)20 b(This)15 b(domain)e(is)i(not)-15 452 y(v)o(ery)23 b(informativ)o(e)e(for)i(the)g(purp)q(ose)i(of)d(comparing)f (the)-15 498 y(tec)o(hniques:)31 b(it)20 b(is)f(included)h(in)g(this)g(pap)q (er)g(as)g(an)g(addi-)-15 544 y(tional)13 b(demonstration)f(of)i(the)g (generalit)o(y)g(of)f(AxA-EBL.)27 590 y(In)k(the)g(GRID)f(domain,)g(AxA-EBL)h (starts)h(out)f(with)g(a)-15 635 y(v)o(ery)11 b(bad)g(set)h(of)e(con)o(trol)g (rules)i(|)e(one)h(whic)o(h)g(usually)f(leads)-15 681 y(the)19 b(problem)e(solv)o(er)h(on)g(a)g(wild)g(go)q(ose)g(c)o(hase)h(across)g(the) -15 727 y(graph)i(|)f(but)h(then)g(quic)o(kly)f(reco)o(v)o(ers.)40 b(In)20 b(all)g(ten)h(tri-)-15 772 y(als,)h(AxA-EBL)g(con)o(v)o(erges)h(to)e (the)h(same)e(program;)j(the)-15 818 y(programs)c(learned)h(b)o(y)g(EBL)h (and)f(A-EBL)g(are)h(still)e(get-)-15 864 y(ting)14 b(progressiv)o(ely)g(slo) o(w)o(er.)19 b(Unfortunately)m(,)13 b(the)i(program)-15 909 y(learned)i(b)o(y)g(AxA-EBL)h(is)e(still)g(slo)o(w)o(er)h(than)g(the)h (original)-15 955 y(program.)25 b(This)17 b(indicates)g(that)g(some)f (additional)f(utilit)o(y)-15 1001 y(analysis)e(ma)o(y)e(b)q(e)k(necessary)m (,)f(ev)o(en)h(when)f(appro)o(ximations)-15 1046 y(are)g(used.)27 1092 y(In)9 b(the)h(R)-5 b(W)9 b(and)h(BW)f(domains,)f(AxA-EBL)i(outp)q (erforms)-15 1138 y(EBL)i(b)o(y)f(wide)h(margins.)j(Suprisingly)m(,)c(A-EBL)h (do)q(es)g(some-)-15 1184 y(what)17 b(b)q(etter)i(than)e(AxA-EBL)g(in)g(the)g (R)-5 b(W)17 b(domain.)25 b(W)m(e)-15 1229 y(in)o(terpret)18 b(this)g(result)g(as)f(follo)o(ws.)26 b(The)18 b(co)o(v)o(erage)g(graphs)-15 1275 y(sho)o(w)d(that)g(although)f(AxA-EBL)h(generates)i(con)o(trol)d(rules) -15 1321 y(whic)o(h)e(ha)o(v)o(e)h(lo)o(w)o(er)f(matc)o(h)f(cost)i(than)f (A-EBL,)747 1305 y Fd(5)778 1321 y Fk(AxA-EBL)-15 1366 y(con)o(v)o(erges)j (somewhat)e(more)g(slo)o(wly;)f(this)i(is)g(probably)f(the)-15 1412 y(price)h(of)e(searc)o(hing)h(through)g(a)g(m)o(uc)o(h)f(larger)h(space) h(of)e(p)q(os-)-15 1458 y(sible)i(con)o(trol)g(rules.)k(In)c(short,)g Fi(AxA-EBL)h(tr)n(ades)g(o\013)h(c)n(on-)-15 1503 y(ver)n(genc)n(e)k(sp)n(e)n (e)n(d)g(for)g(lower)f(match)h(c)n(ost)f Fk(in)g(the)h(planning)-15 1549 y(domains.)26 b(This)17 b(unfortunately)g(leads)g(to)g(a)g(p)q (erformance)-15 1595 y(tradeo\013:)i(if)13 b(matc)o(hing)g(rules)h(is)g(c)o (heap)h(and)f(problem)f(solv-)-15 1640 y(ing)19 b(is)h(exp)q(ensiv)o(e,)i(as) e(in)g(the)g(R)-5 b(W)20 b(domain,)f(then)h(faster)-15 1686 y(con)o(v)o(ergence)15 b(will)e(o\013set)h(the)h(p)q(o)q(orer)f(qualit)o(y)e (of)h(the)i(rules,)-15 1732 y(and)f(A-EBL)g(will)f(pro)q(duce)i(faster)f (programs.)-15 1826 y Fj(5)56 b(Related)18 b(w)n(ork)-15 1900 y Fk(Use)g(of)f(appro)o(ximations)e(in)h(learning)h(con)o(trol)g(kno)o (wledge)-15 1945 y(w)o(as)27 b(in)o(v)o(estigated)g(in)g(the)g(MetaLEX)h(pro) r(ject)828 1941 y([)840 1945 y(Keller,)-15 1991 y(1987)69 1987 y(])80 1991 y(.)39 b(The)22 b(tec)o(hniques)g(used)g(in)f(MetaLEX,)g(ho)o(w)o (ev)o(er,)-15 2037 y(w)o(ere)e(sp)q(eci\014c)i(to)d(state-space)i(searc)o(h,) h(and)d(required)h(p)q(e-)-15 2082 y(rio)q(dic)h(testing)i(of)e(programs)f (including)h(learned)h(con)o(trol)p -15 2118 250 2 v 37 2145 a Fc(5)54 2161 y Fb(This)11 b(is)g(ob)o(vious)h(in)f(the)f(blo)q(c)o(ks)i(w)o (orld)f(domain,)h(since)f(AxA-)-15 2202 y(EBL's)g(con)o(trol)g(rules)h(outp)q (erform)g(A-EBL's)e(con)o(trol)i(rules)f(ev)o(en)-15 2244 y(though)16 b(their)f(co)o(v)o(erage)h(is)f(usually)i(w)o(orse.)22 b(It)14 b(is)i(a)e(little)j(more)-15 2285 y(di\016cult)j(to)f(v)o(erify)g(in)g(the)g (R)l(W)f(domain.)35 b(One)19 b(w)o(a)o(y)f(to)h(con-)-15 2327 y(trol)f(for)f(the)h(e\013ect)f(of)g(co)o(v)o(erage)i(is)f(to)f(compare)h (only)h(sets)e(of)-15 2368 y(con)o(trol)g(rules)h(with)e(equal)i(co)o(v)o (erage;)g(this)f(comparison)i(sho)o(ws)-15 2410 y(that)g(AxA-EBL)g(con)o (trol)i(rules)f(are)f(ab)q(out)i(12\045)e(faster)g(than)-15 2451 y(A-EBL)11 b(con)o(trol)h(rules)g(with)f(equiv)n(alen)o(t)j(co)o(v)o (erage.)j(Another)11 b(in-)-15 2493 y(dication)k(that)e(the)g(AxA-EBL)f(con)o (trol)i(rules)g(are)f(faster)f(is)i(that)-15 2534 y(the)d(b)q(est)g(con)o (trol)h(rules)g(learned)g(b)o(y)g(AxA-EBL)e(outp)q(erform)i(the)-15 2576 y(b)q(est)g(con)o(trol)h(rules)g(learned)g(b)o(y)f(A-EBL,)f(requiring)j (1.5)e(seconds)-15 2618 y(v)o(ersus)f(12.9)g(seconds)g(to)g(solv)o(e)g(the)g (50)g(problems)h(in)f(the)g(test)f(set.)1035 407 y Fk(kno)o(wledge)16 b(against)f(a)h(b)q(enc)o(hmark.)25 b(This)16 b(w)o(ould)f(b)q(e)i(pro-)1035 452 y(hibitiv)o(ely)f(exp)q(ensiv)o(e)k(in)d(a)h(real-w)o(orld)f(domain.)28 b(Ellman)1035 494 y([)1047 498 y(Ellman,)12 b(1988)1287 494 y(])1298 498 y(,)j(T)m(adepalli)1507 494 y([)1518 498 y(T)m(adepalli,)e(1989) 1796 494 y(])1822 498 y(and)i(Chien)1035 540 y([)1047 544 y(Chien,)c(1989) 1260 540 y(])1283 544 y(ha)o(v)o(e)g(also)h(in)o(v)o(estigated)f(explanation) g(based)1035 589 y(learning)20 b(of)h(appro)o(ximate)e(theories.)41 b(The)21 b(searc)o(h)h(tec)o(h-)1035 635 y(niques)14 b(describ)q(ed)h(b)o(y)e (these)i(authors)f(impro)o(v)o(e)d(on)j(Keller's)1035 681 y(b)o(y)e(taking)f (adv)n(an)o(tage)g(of)h(a)f(partial)g(order)i(on)f(appro)o(ximate)1035 726 y(theories;)18 b(ho)o(w)o(ev)o(er,)f(they)h(ha)o(v)o(e)e(not)g(b)q(een)i (applied)e(to)g(the)1035 772 y(problem)d(of)g(learning)g(con)o(trol)h(rules.) 1077 822 y(Appro)o(ximations)8 b(to)i(EBL)g(rules)h(ha)o(v)o(e)f(also)g(b)q (een)h(in)o(v)o(esti-)1035 868 y(gated)i(in)1194 864 y([)1206 868 y(Chase)g Fi(et)g(al.)p Fk(,)f(1989)1526 864 y(])1550 868 y(in)g(the)h(con)o(text)g(of)g(the)g(ULS)1035 914 y(system.)38 b(The)21 b(appro)o(ximations)d(done)j(in)f(ULS)h(are)g(not,)1035 959 y(ho)o(w)o(ev)o(er,)12 b(selected)g(b)o(y)f(an)g(inductiv)o(e)g(learning) g(mec)o(hanism;)1035 1005 y(as)17 b(a)f(consequence,)k(ULS)d(is)g(limited)d (to)j(conserv)n(ativ)o(e)g(ap-)1035 1051 y(pro)o(ximations)f(\()p Fi(e.g.)p Fk(,)i(dropping)g(one)h(or)f(t)o(w)o(o)g(conditions\).)1035 1096 y(ULS)h(nonetheless)i(has)f(made)e(mo)q(dest)g(impro)o(v)o(emen)o(ts)f (in)1035 1142 y(planning)c(time)f(in)i(the)g(R)-5 b(W)14 b(domain.)1077 1192 y(The)20 b(use)g(of)g Fg(k)q Fk(-b)q(ounded)g(appro)o(ximations)d(is)j (one)g(w)o(a)o(y)1035 1238 y(of)15 b(b)q(ounding)g(the)h(cost)h(of)e(learned) h(rules.)23 b(An)16 b(alternativ)o(e)1035 1284 y(approac)o(h)i(is)f(describ)q (ed)j(b)o(y)d(T)m(am)o(b)q(e)f(and)i(Rosen)o(blo)q(om)d(in)1035 1325 y([)1047 1329 y(T)m(am)o(b)q(e)f(and)i(Rosen)o(blo)q(om,)e(1989)1601 1325 y(])1611 1329 y(;)j(they)f(describ)q(e)i(a)e(syn-)1035 1375 y(tactic)22 b(constrain)o(t)f(on)g(SO)o(AR)g(programs)f(whic)o(h)h (ensures)1035 1421 y(that)g(c)o(h)o(unks)g(ha)o(v)o(e)f(matc)o(h)f(cost)i (linear)g(in)f(their)g(length.)1035 1466 y(A)e(corresp)q(onding)i(constrain)o (t)e(can)h(b)q(e)g(imp)q(osed)e(on)h(EBL)1035 1512 y(rules;)13 b(it)g(is)g(easy)g(to)g(see)h(that)f(requiring)f(ev)o(ery)i(op)q(erational) 1035 1558 y(predicate)22 b(to)e(ha)o(v)o(e)g(at)h(most)e(one)i(solution)f (will)f(lead)h(to)1035 1603 y(EBL)d(rules)h(whic)o(h)e(can)h(b)q(e)g(matc)o (hed)f(in)h(linear)f(time.)25 b(An)1035 1649 y(adv)n(an)o(tage)9 b(to)g(linear-time)e(restricted)12 b(EBL)e(is)f(that)h(sp)q(ecial-)1035 1695 y(purp)q(ose)k(inductiv)o(e)e(tec)o(hniques)i(are)g(not)e(needed)i(to)f (searc)o(h)1035 1740 y(for)f(correct)h(rules;)g(the)f(standard)h(incremen)o (tal)e(learning)g(al-)1035 1786 y(gorithm)h(can)i(b)q(e)h(used.)1077 1836 y(In)g(order)h(to)f(satisfy)g(the)h(constrain)o(t)g(that)g(ev)o(ery)g (op)q(era-)1035 1882 y(tional)9 b(predicate)i(has)f(at)h(most)e(one)h (solution,)g(it)f(is)h(t)o(ypically)1035 1928 y(necessary)20 b(to)d(c)o(hange)h(the)h(op)q(erationalit)o(y)d(predicate.)31 b(In)1035 1973 y(the)18 b(planning)d(domains,)h(for)g(instance,)i(it)f(is)g (su\016cien)o(t)g(to)1035 2019 y(mo)q(dify)d(the)i(op)q(erationalit)o(y)e (predicate)j(so)f(that)g(the)h Fi(holds)1035 2065 y Fk(predicate,)j(whic)o(h) e(determines)h(if)e(a)h(condition)f(is)h(true)h(in)1035 2110 y(a)c(state,)g(is)g(mark)o(ed)f(as)h(non-op)q(erational.)21 b(Using)15 b(the)h(new)1035 2156 y(op)q(erationalit)o(y)11 b(predicate,)i(con)o(trol)f(rules)h(learned)g(b)o(y)f(EBL)1035 2202 y(are)19 b(expressed)h(in)e(terms)g(of)g(constrain)o(ts)h(on)f(elemen)o (ts)h(of)1035 2247 y(the)k(list)g(structure)h(used)g(to)e(represen)o(t)j(a)e (state,)i(rather)1035 2293 y(than)c(constrain)o(ts)g(on)g(the)g(conditions)f (that)h(are)g(true)h(or)1035 2339 y(false)14 b(in)g(that)h(state.)21 b(Changing)13 b(the)i(op)q(erationalit)o(y)e(pred-)1035 2384 y(icate)20 b(in)f(this)h(w)o(a)o(y)f(closely)h(corresp)q(onds)h(to)f(T)m(am)o (b)q(e)e(and)1035 2430 y(Rosen)o(blo)q(om's)12 b(suggestion)i(of)f(replacing) h(m)o(ulti-attributes)1035 2476 y(in)f(SO)o(AR)h(programs)f(with)g(list-pro)q (cessing)i(utilities.)1077 2526 y(Figure)k(3)h(sho)o(ws)g(the)g(result)h(of)e (using)h(linear-time)d(re-)1035 2572 y(stricted)g(EBL)f(\(LR-EBL\))g(in)f (the)h(BW)f(and)h(R)-5 b(W)15 b(domain.)1035 2618 y(This)c(exp)q(erimen)o(t)g (p)q(oin)o(ts)g(out)f(a)h(disadv)n(an)o(tage)f(of)h(the)g(tec)o(h-)p eop %%Page: 8 8 8 7 bop -15 -193 2025 2 v 300 978 a Fk(BW/R)-5 b(W)13 b(Time)695 b(BW/R)-5 b(W)13 b(Co)o(v)o(erage)214 1079 y(Figure)h(3:)k(P)o(erformance)c (and)g(Co)o(v)o(erage)f(Curv)o(es)i(for)f(BW)g(and)f(R)-5 b(W)14 b(with)f(Linear-Time)g(Rules)p -15 1089 V -15 1214 a(nique:)j(learned)11 b(rules)g(tend)g(to)f(b)q(e)h(v)o(ery)g(sp)q(eci\014c,)h(and)f(hence)-15 1259 y(do)17 b(not)g(often)g(transfer)h(to)f(new)h(situations.)28 b(As)17 b(a)g(conse-)-15 1305 y(quence,)d(there)h(is)f(little)e(or)i(no)f(p)q (erformance)h(impro)o(v)o(em)o(en)o(t)-15 1351 y(on)9 b(a)g(test)i(set)f(of)f (no)o(v)o(el)g(problems;)h(and)f(so)h(in)f(b)q(oth)g(domains,)-15 1396 y(p)q(erformance)18 b(impro)o(v)o(emen)o(t)e(w)o(as)i(far)g(less)h(than) f(that)g(at-)-15 1442 y(tained)i(b)o(y)g(AxA-EBL.)h(In)f(the)h(R)-5 b(W)20 b(domain,)f(a)h(mo)q(dest)-15 1488 y(15-20\045)8 b(impro)o(v)o(emen)o (t)g(gain)g(w)o(as)i(ac)o(hiev)o(ed,)h(whereas)g(AxA-)-15 1533 y(EBL)17 b(impro)o(v)o(ed)d(p)q(erformance)i(b)o(y)g(o)o(v)o(er)g(80\045;)g (in)f(the)i(BW)-15 1579 y(domain,)g(p)q(erformance)h(w)o(as)g(degraded)h (sligh)o(tly)m(,)e(whereas)-15 1625 y(AxA-EBL)d(impro)o(v)o(ed)f(p)q (erformance)g(b)o(y)h(65\045.)746 1610 y Fd(6)-15 1730 y Fj(6)56 b(Conclusions)-15 1811 y Fk(The)13 b(utilit)o(y)e(of)i(a)f(rule)h(is)g(its)f (con)o(tribution)h(to)f(p)q(erformance)-15 1857 y(impro)o(v)o(emen)o(t;)22 b(utilit)o(y)e(is)i(directly)f(prop)q(ortional)g(to)g(the)-15 1903 y(co)o(v)o(erage)f(of)f(a)g(rule)g(and)g(in)o(v)o(ersely)h(prop)q (ortional)e(to)h(the)-15 1948 y(matc)o(h)10 b(cost.)18 b(This)11 b(pap)q(er)g(in)o(tro)q(duces)i(t)o(w)o(o)d(new)i(tec)o(hniques)-15 1994 y(for)19 b(impro)o(ving)d(the)k(utilit)o(y)e(of)h(learned)h(rules.)34 b(The)20 b(\014rst)-15 2040 y(tec)o(hnique)j(is)f(to)h(com)o(bine)e(EBL)i (with)f Fi(inductive)h(le)n(arn-)-15 2085 y(ing)15 b(te)n(chniques)p Fk(,)e(th)o(us)h(increasing)g(the)g(co)o(v)o(erage)g(of)f(con)o(trol)-15 2131 y(rules;)f(the)g(second)g(tec)o(hnique)h(is)e(to)g(constrain)g(these)i (induc-)-15 2177 y(tiv)o(e)f(tec)o(hniques)h(to)f(learn)g Fi(appr)n(oximate)i (c)n(ontr)n(ol)e(rules)g Fk(that)-15 2222 y(ha)o(v)o(e)i(v)o(ery)g(lo)o(w)g (matc)o(h)e(cost.)20 b(These)15 b(t)o(w)o(o)f(tec)o(hniques)h(ha)o(v)o(e)-15 2268 y(b)q(een)20 b(syn)o(thesized)g(in)f(the)g(AxA-EBL)g(algorithm.)30 b(AxA-)-15 2314 y(EBL)16 b(has)g(b)q(een)h(exp)q(erimen)o(tally)d(sho)o(wn)i (to)g(pro)q(duce)h(con-)-15 2359 y(trol)12 b(rules)h(whic)o(h)f(impro)o(v)o (e)f(substan)o(tially)g(o)o(v)o(er)h(the)h(con)o(trol)p -15 2409 250 2 v 37 2436 a Fc(6)54 2451 y Fb(The)h(training)i(and)f(test)f (problems)h(used)g(for)e(these)i(exp)q(eri-)-15 2493 y(men)o(ts)g(and)h(the)f (exp)q(erimen)o(ts)h(of)f(Figure)h(2)f(are)g(the)g(same;)h(the)-15 2534 y(CPU)h(time)i(needed)g(to)f(solv)o(e)h(the)f(test)g(set)g(without)h (learning)-15 2576 y(di\013ers)i(b)q(ecause)f(with)f(a)g(di\013eren)o(t)i(op) q(erationali)q(t)o(y)h(predicate,)-15 2618 y(di\013eren)o(t)15 b(domain-sp)q(eci\014c)h(predicates)e(can)g(b)q(e)f(compiled.)1035 1214 y Fk(rules)f(learned)h(b)o(y)e(standard)h(EBL)h(in)e(sev)o(eral)h (domains;)e(the)1035 1259 y(a)o(v)o(erage)j(impro)o(v)o(emen)o(t)d(is)j(ab)q (out)f(a)h(factor)g(of)f(t)o(w)o(o)g(o)o(v)o(er)h(the)1035 1305 y(domains)f(that)i(ha)o(v)o(e)g(b)q(een)h(studied.)1077 1353 y(Sev)o(eral)10 b(op)q(en)i(problems)d(remain.)16 b(First,)11 b(the)h(tec)o(hniques)1035 1398 y(used)25 b(are)g(non-incremen)o(tal;)i(it)d (w)o(ould)f(b)q(e)i(desirable)g(if)1035 1444 y(learning)15 b(could)h(tak)o(e)g(place)h(concurren)o(tly)g(with)e(problem-)1035 1489 y(solving,)i(rather)h(than)f(as)g(a)g(separate)i(pass.)29 b(Second,)18 b(the)1035 1535 y(curren)o(t)12 b(implemen)o(tation)7 b(of)j(AxA-EBL)i(m)o(ust,)e(for)g(reasons)1035 1581 y(of)g(computational)d (complexit)o(y)m(,)h(use)k(a)d(v)o(ery)i(small)d(and)i(con-)1035 1626 y(straining)k(set)i(of)e(appro)o(ximations;)e(it)i(w)o(ould)g(b)q(e)i (desirable)1035 1672 y(to)e(use)h(a)e(larger)h(set)h(of)f(appro)o(ximations.) i(Third,)d(one)h(cost)1035 1718 y(of)19 b(learning)f(appro)o(ximate)g(con)o (trol)h(rules)h(seems)f(to)g(b)q(e)h(a)1035 1763 y(slo)o(w)o(er)f(con)o(v)o (ergence)i(rate,)g(relativ)o(e)e(to)h(simpler)e(learning)1035 1809 y(systems.)g(It)11 b(w)o(ould)h(b)q(e)g(desirable)g(if)f(this)h (tradeo\013)h(could)e(b)q(e)1035 1855 y(lessened)16 b(or)d(a)o(v)o(oided.) 1035 1954 y Fj(Ac)n(kno)n(wledgemen)n(ts)1035 2031 y Fk(I)g(am)f(grateful)h (to)h(m)o(y)e(advisor,)h(Alex)g(Borgida,)g(for)g(his)g(ad-)1035 2076 y(vice)d(and)f(encouragemen)o(t;)i(to)e(Ha)o(ym)f(Hirsh,)j(for)e(in)o(v) n(aluable)1035 2122 y(suggestions)23 b(on)e(exp)q(erimen)o(tal)h(metho)q (dology;)h(to)f(Ch)o(un)1035 2168 y(Liew,)11 b(for)g(commen)o(ts)e(on)i(a)f (draft)h(of)f(the)i(pap)q(er)g(and)e(sev)o(eral)1035 2213 y(useful)17 b(insigh)o(ts;)g(and)f(to)h(Susan)f(Cohen)h(for)f(pro)q(ofreading)1035 2259 y(a)d(late)g(draft)h(of)f(this)g(pap)q(er.)19 b(The)14 b(author)f(is)g(supp)q(orted)i(b)o(y)1035 2305 y(an)f(A)m(T&T)f(F)m(ello)o (wship.)1035 2404 y Fj(References)1035 2477 y Fk([)1047 2481 y(Chase)h Fi(et)h(al.)p Fk(,)e(1989)1371 2477 y(])1402 2481 y(Melissa)29 b(Chase,)j(Mon)o(te)d(Zw)o(eb)q(en,)1079 2526 y(Ric)o(hard)23 b(Piazza,)j(John)e(Burger,)k(P)o(aul)23 b(Maglio,)h(and)1079 2572 y(Ha)o(ym)11 b(Hirsh.)18 b(Appro)o(ximating)11 b(learned)j(searc)o(h)g (con)o(trol)1079 2618 y(kno)o(wledge.)f(In)d Fi(Pr)n(o)n(c)n(e)n(e)n(dings)i (of)g(the)g(Sixth)h(International)p eop %%Page: 9 9 9 8 bop 29 -153 a Fi(Workshop)14 b(on)h(Machine)g(L)n(e)n(arning)p Fk(,)d(Ithaca,)h(New)g(Y)m(ork,)29 -108 y(1989.)f(Morgan)i(Kaufmann.)-15 -50 y([)-3 -46 y(Chien,)f(1989)212 -50 y(])243 -46 y(Stev)o(e)22 b(Chien.)37 b(Using)21 b(and)f(re\014ning)h(sim-)29 0 y(pli\014cations:)e (Explanation-based)14 b(learning)g(of)g(plans)g(in)29 46 y(in)o(tractible)g (domains.)k(In)d Fi(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(the)g(Eleventh)29 91 y(International)f(Joint)f(Confer)n(enc)n(e)g(on)i(A)o(rti\014cial)d(Intel) r(li-)29 137 y(genc)n(e)p Fk(,)g(Detroit,)g(Mic)o(higan,)f(1989.)f(Morgan)i (Kaufmann.)-15 195 y([)-3 199 y(Cohen,)g(1989)221 195 y(])253 199 y(William)h(W.)j(Cohen.)31 b(Ab)q(ductiv)o(e)19 b(expla-)29 245 y(nation)f(based)h(learning:)27 b(A)19 b(solution)e(to)i(the)g(m)o (ultiple)29 290 y(explanation)12 b(problem.)17 b(T)m(ec)o(hnical)c(Rep)q(ort) h(ML-TR-26,)29 336 y(Rutgers)g(Univ)o(ersit)o(y)m(,)f(1989.)-15 394 y([)-3 398 y(Cohen,)g(1990)221 394 y(])253 398 y(William)6 b(W.)j(Cohen.)j(Learning)d(from)g(text-)29 444 y(b)q(o)q(ok)18 b(kno)o(wledge:)27 b(A)18 b(case)h(study)m(.)32 b(In)18 b Fi(Pr)n(o)n(c)n(e)n (e)n(dings)h(of)29 489 y(the)e(Eighth)g(National)h(Confer)n(enc)n(e)f(on)g(A) o(rti\014cial)f(Intel-)29 535 y(ligenc)n(e)p Fk(,)d(Boston,)h(Massac)o(h)o (usetts,)h(1990.)e(MIT)h(Press.)-15 593 y([)-3 597 y(Ellman,)d(1988)236 593 y(])267 597 y(T)m(om)f(Ellman.)k(Appro)o(ximate)c(theory)j(for-)29 643 y(mation:)26 b(An)19 b(explanation-based)f(approac)o(h.)33 b(In)18 b Fi(Pr)n(o-)29 689 y(c)n(e)n(e)n(dings)c(of)g(the)g(Seventh)h (National)f(Confer)n(enc)n(e)g(on)h(A)o(r-)29 734 y(ti\014cial)22 b(Intel)r(ligenc)n(e)p Fk(,)i(Sain)o(t)e(P)o(aul,)h(Minnesota,)h(1988.)29 780 y(Morgan)13 b(Kaufmann.)-15 838 y([)-3 842 y(Fik)o(es)h Fi(et)g(al.)p Fk(,)f(1972)306 838 y(])338 842 y(Ric)o(hard)26 b(Fik)o(es,)k(P)o(eter)f(Hart,)h(and)29 888 y(Nils)20 b(Nilsson.)37 b(Learning)20 b(and)g(executing)h(generalized)29 933 y(rob)q(ot)12 b(plans.)i Fi(A)o(rti\014cial)e(Intel)r(ligenc)n(e)p Fk(,)g(3:251{288,)d (1972.)-15 991 y([)-3 995 y(Flann)k(and)h(Dietteric)o(h,)g(1989)487 991 y(])518 995 y(Nic)o(holas)58 b(Flann)g(and)29 1041 y(Thomas)16 b(Dietteric)o(h.)31 b(A)18 b(study)g(of)f(explanation-based)29 1087 y(metho)q(ds)d(for)h(inductiv)o(e)g(learning.)20 b Fi(Machine)c(L)n(e)n (arning)p Fk(,)29 1132 y(4\(2\),)d(1989.)-15 1191 y([)-3 1195 y(Keller,)g(1987)214 1191 y(])246 1195 y(Ric)o(hard)e(Keller.)j(The)e(role)f (of)g(explicit)g(con-)29 1240 y(textual)17 b(kno)o(wledge)f(in)g(learning)h (concepts)h(to)f(impro)o(v)o(e)29 1286 y(p)q(erformance.)24 b(T)m(ec)o(hnical)15 b(Rep)q(ort)i(ML-TR-7,)d(Rutgers)29 1332 y(Univ)o(ersit)o(y)m(,)f(1987.)-15 1390 y([)-3 1394 y(Mark)o(o)o(vitc)o(h)g (and)g(Scott,)h(1989)500 1390 y(])532 1394 y(Shaul)26 b(Mark)o(o)o(vitc)o(h)h (and)29 1439 y(P)o(aul)c(Scott.)47 b(Utilization)23 b(\014ltering:)37 b(A)24 b(metho)q(d)e(for)29 1485 y(reducing)29 b(the)g(inherit)g(harmfulness) f(of)g(deductiv)o(ely)29 1531 y(learned)17 b(kno)o(wledge.)27 b(In)17 b Fi(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(the)g(Eleventh)29 1576 y(International)d(Joint)f(Confer)n(enc)n(e)g(on)i(A)o(rti\014cial)d (Intel)r(li-)29 1622 y(genc)n(e)p Fk(,)g(Detroit,)g(Mic)o(higan,)f(1989.)f (Morgan)i(Kaufmann.)-15 1680 y([)-3 1684 y(Min)o(ton,)f(1988)237 1680 y(])269 1684 y(Stev)o(en)30 b(Min)o(ton.)63 b(Learning)29 b(e\013ectiv)o(e)29 1730 y(searc)o(h)11 b(con)o(trol)f(kno)o(wledge:)16 b(An)10 b(explanation-based)f(ap-)29 1775 y(proac)o(h.)24 b(T)m(ec)o(hnical) 16 b(rep)q(ort,)h(Carnegie-Mellon)e(Univ)o(er-)29 1821 y(sit)o(y)e(Departmen) o(t)h(of)f(Computer)g(Science,)i(1988.)-15 1879 y([)-3 1883 y(Mitc)o(hell,)d(1982)253 1879 y(])285 1883 y(T)m(om)d(Mitc)o(hell.)k(T)m(o)o (w)o(ard)d(com)o(bining)e(em-)29 1929 y(pirical)15 b(and)h(analytical)e (metho)q(ds)h(for)h(inferring)f(heuris-)29 1975 y(tics.)f(In)d Fi(Human)i(and)g(A)o(rti\014cial)e(Intel)r(ligenc)n(e)p Fk(.)g(La)o(wrence)29 2020 y(Erlbaum,)h(1982.)-15 2078 y([)-3 2082 y(Mo)q(oney)m(,)h(1989)247 2078 y(])278 2082 y(R.)c(J.)h(Mo)q(oney)m(.)i(The)e(e\013ect)i(of)e(rule)g (use)h(on)29 2128 y(the)f(utilit)o(y)f(of)h(explanation)f(based)h(learning.)h (In)f Fi(Pr)n(o)n(c)n(e)n(e)n(d-)29 2174 y(ings)k(of)h(the)f(Eleventh)h (International)g(Joint)f(Confer)n(enc)n(e)29 2219 y(on)19 b(A)o(rti\014cial)e (Intel)r(ligenc)n(e)p Fk(,)i(Detroit,)f(Mic)o(higan,)f(1989.)29 2265 y(Morgan)c(Kaufmann.)-15 2323 y([)-3 2327 y(Nilsson,)g(1987)237 2323 y(])268 2327 y(Nils)20 b(Nilsson.)39 b Fi(Principles)21 b(of)g(A)o(rti\014cial)29 2373 y(Intel)r(ligenc)n(e)p Fk(.)d(Morgan)13 b(Kaufmann,)f(1987.)-15 2431 y([)-3 2435 y(Prieditis)h(and)h(Mosto)o(w,)f (1987)494 2431 y(])526 2435 y(Armand)31 b(Prieditis)i(and)29 2481 y(Jac)o(k)11 b(Mosto)o(w.)h(PR)o(OLEARN:)e(T)m(o)o(w)o(ards)g(a)g (prolog)g(in)o(ter-)29 2526 y(preter)17 b(that)f(learns.)24 b(In)16 b Fi(Pr)n(o)n(c)n(e)n(e)n(dings)h(of)f(the)h(Sixth)g(Na-)29 2572 y(tional)d(Confer)n(enc)n(e)g(on)g(A)o(rti\014cial)f(Intel)r(ligenc)n(e) p Fk(,)g(Seattle,)29 2618 y(W)m(ashington,)f(1987.)g(Morgan)i(Kaufmann.)1035 -157 y([)1047 -153 y(Sha)o(vlik,)e(1987)1289 -157 y(])1320 -153 y(Jude)25 b(Sha)o(vlik.)46 b(Generalizing)24 b(n)o(um)o(b)q(er)1079 -108 y(in)d(explanation)g(based)i(learning.)41 b(T)m(ec)o(hnical)22 b(Rep)q(ort)1079 -62 y(UILO-ENG-87-2276,)e(Univ.)g(of)g(Illinois/Cham)o(paig) o(n,)1079 -17 y(1987.)d(\(PhD)d(thesis\).)1035 42 y([)1047 46 y(T)m(adepalli,)d(1989)1323 42 y(])1354 46 y(Prasad)i(T)m(adepalli.)g (Lazy)f(explanation-)1079 91 y(based)20 b(learning:)29 b(A)19 b(solution)g(to)g(the)h(in)o(tractible)g(the-)1079 137 y(ory)15 b(problem.)22 b(In)16 b Fi(Pr)n(o)n(c)n(e)n(e)n(dings)g(of)h(the)g(Eleventh)f (Inter-)1079 183 y(national)e(Joint)f(Confer)n(enc)n(e)h(on)g(A)o (rti\014cial)f(Intel)r(ligenc)n(e)p Fk(,)1079 228 y(Detroit,)g(Mic)o(higan,)g (1989.)f(Morgan)h(Kaufmann.)1035 287 y([)1047 291 y(T)m(am)o(b)q(e)f(and)h (Rosen)o(blo)q(om,)f(1989)1594 287 y(])1625 291 y(Milinde)28 b(T)m(am)o(b)q(e)f(and)1079 336 y(P)o(aul)21 b(Rosen)o(blo)q(om.)40 b(Eliminating)18 b(exp)q(ensiv)o(e)23 b(c)o(h)o(unks)1079 382 y(b)o(y)15 b(restricting)h(expressiv)o(eness.)26 b(In)15 b Fi(Pr)n(o)n(c)n(e)n(e)n(dings)i(of)f(the)1079 428 y(Eleventh)i(International) g(Joint)g(Confer)n(enc)n(e)g(on)h(A)o(rti\014-)1079 473 y(cial)f(Intel)r (ligenc)n(e)p Fk(,)h(Detroit,)g(Mic)o(higan,)f(1989.)f(Morgan)1079 519 y(Kaufmann.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF