%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: scribe.dvi %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentPaperSizes: Letter %%EndComments %DVIPSCommandLine: dvips.bin -h/tmp/DVF18223 -Plaser5 -o scribe9.ps %+ scribe %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1997.06.03:1512 %%BeginProcSet: /tmp/DVF18223 %%EndProcSet %%BeginProcSet: texc.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 /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]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 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /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 userdict /eop-hook known{eop-hook}if showpage}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 newpath 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 true 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 (scribe.dvi) @start /Fa 20 117 df<9139FFC03FF0010F9038E3FFFC013F90B5FCD9FF81EBE07E48 4848EB80FE4848481300D807F849487E01F001FC5B160014030201147C94C7FCA3EE07FF B9FCA33B07F001FC007FB3A33C7FFF1FFFC7FFF0A3342A7FA938>14 D<123E127FEAFF80A5EA7F00123E09097B8813>46 D48 D<130E131E137EEA07FE12FF A212F81200B3ABB512FEA317277BA622>II<00181303381F803F90B5FCA25C14F85C14C091C7FC001CC8 FCA6EB7FE0381DFFF8001F13FEEBC0FF391E007F80001C133FC7EA1FC0A215E0A2121C12 7EB4FCA415C048133F007C1480EC7F00383F81FE6CB45A000713F0C613801B277DA622> 53 D65 D<3803FFC0000F13F8487F 383FC1FEEBC0FF80EC3F80A2EA1F80C7FCA2EB07FF90B5FC1207381FF83FEA3FC0EA7F80 EAFF005AA36C137F14FFD87FC313C0393FFFDFFC6C130F3807FC071E1B7E9A21>97 D99 D101 D<9038FF81F80007EBFFFC5A381FC1FC393F80FE7C9038007E 7848EB7F00A66C137EEB80FE381FC1FCEBFFF85C0038138090C8FCA2123C123E383FFFFC ECFF806C14C015E015F05A397F000FF800FE1303481301A36C1303007E14F0387F800F39 3FE03FE06CB512C000071400C613F81E287E9A22>103 DI I108 D<3BFFC0FF803FE001C39038E0FFF8 01C701F17F3A0FCF0FF3C3903ADC07FF01FE9039F803FE00A201F05BA201E05BAF3CFFFE 3FFF8FFFE0A3331B7D9A38>I<38FFC0FF01C313C001C713E0380FCF1F9038DC0FF0EBF8 0713F0A313E0AF39FFFE3FFFA3201B7D9A25>II<38FFE1FF01E713C090B512F0390F FE1FF89038F807FCEBF00301E013FE1401A2EC00FFA9EC01FEA2140301F013FC9038F807 F89038FE1FF090B512E001EF13C09038E1FE0001E0C7FCA9EAFFFEA320277E9A25>I<38 FFC7F0EBCFFCEBDFFE380FDEFF13F8A25BA2147EEBE000AFB5FCA3181B7F9A1B>114 D<13E0A41201A312031207120F121FB512E0A3380FE000AD1470A6EBF0F03807F9E0EBFF C06C1380C6130014267FA51A>116 D E /Fb 4 119 df<123EA2121EA2121CA2EA3CF012 3D123BEA3F70127EEA7F00EA7780EA7398EAF3B813F0EAE1E00D117E9010>107 D112 D117 DI E /Fc 4 97 df<121FEA3F80EA71C01260EAE0E0A8EA60C012 71EA3F80EA1F000B107F8F0F>48 D<120C127C12FC129C121CAAEAFF80A209107E8F0F> I<123FEA7FC0EAE3E012E112E01200A2EA01C01203EA0780EA0E00EA1C601238EA7FC012 FFA20B107F8F0F>I<1260127012E0A212C012F0A3127004097E9009>96 D E /Fd 8 116 df<141C147C14F8EB01F0EB03E0EB07C0EB0F80EB1F00A2133EA35BB3 B3A25BA3485AA2485A485A485A48C7FC123E5A12F0A2127C7E7E6C7E6C7E6C7E6C7EA26C 7EA3137CB3B3A27FA37FA2EB0F80EB07C0EB03E0EB01F0EB00F8147C141C167C7B8121> 40 D80 DI88 DI<1606A2 160E160CA2161C1618A216381630A216701660A216E016C0A215011680A215031600A25D 1506A2150E150CA2151C1518A215381530A215701560A21204000E14E0001E5C123E1401 006F5C12EF004F1303D8078090C7FCA25C3803C006A2140E140CEA01E0141C1418EA00F0 14381430A2EB78701460A2EB3CE05CA2131F5CA36DC8FCA31306A2274B7C812A>113 D<1606A3160E160CA3161C1618A316381630A316701660A316E016C0A315011680A31503 1600A35D1506A3150E150CA3151C1518A315381530A315701560A31204000E14E05D121E 123E1401006F5C12EF12CF000F1303D8078090C7FCA35C1406EA03C0A2140E140CEA01E0 A2141C1418A2EA00F014381430A3EB78701460A3EB3CE05CA3133DEB1F80A46DC8FCA413 0E1306A227647C812A>I<1606A3160E160CA4161C1618A416381630A416701660A516E0 16C0A415011680A415031600A45D1506A4150E150CA4151C1518A415381530A415701560 A31204A2000E14E05D121EA2123E1401006F5CA212CFA2000F130392C7FCEA0780A35C14 06EA03C0A3140E140CA2EA01E0A2141C1418A3EA00F014381430A3137814701460A4133C 14E05CA4131F5CA4130F91C8FCA51306A3277D7C812A>I E /Fe 5 107 df0 D<1207A3EAE738EAFFF8EA7FF0EA1FC0A2EA7FF0EA FFF8EAE738EA0700A30D0E7E8E12>3 D<143014F0EB03E0EB0F80EB3E001378EA01E0EA 07C0001FC7FC127C12F0A2127C121FEA07C0EA01E0EA0078133EEB0F80EB03E0EB00F014 301400A6B512F0A2141E7D951B>20 D<3801FF80120748C7FC121C5A5A1260A212E05AB5 1280A200C0C7FC7E1260A212707E7E120F3807FF80120111167D9218>50 D<12C0B3AF02217C980A>106 D E /Ff 8 107 df0 D<13C07F5BA338E0C1C0EAF8C7387CCF80381FFE00EA07F8EA01E0EA07F8EA1FFE387CCF 8038F8C7C0EAE0C13800C000A37F5B12157D9619>3 D<150C153C15F8EC03E0EC0F80EC 3E0014F8EB03E0EB0F80013EC7FC13F8EA03E0EA0F80003EC8FC12F85A127C121FEA07C0 EA01F0EA007C131FEB07C0EB01F0EB007C141FEC07C0EC01F0EC007C151C1500A8B612FC A21E287C9F27>20 D50 D57 D102 D<12FCB4FCEA1FC012076C7E1201AF7F 6C7E137CEB3FC0130F133FEB7C005B485A5BAF1203485A121FB4C7FC12FC12317DA419> I<12C0B3B3AD02317AA40E>106 D E /Fg 3 106 df48 DI<123C127EA4123CC7FCA312FEA2 123EABEAFF80A209187F970C>105 D E /Fh 21 120 df12 D14 D<143014F0EB03E0EB0F80EB3E001378EA01E0EA07C0001FC7FC127C12F0A2127C121FEA 07C0EA01E0EA0078133EEB0F80EB03E0EB00F0143014167D921B>60 D<14C0130114E01303A21307130DA21319A2133113711361EBC1F013C0EA01FF5A130012 06120E121E38FF07FEA217177F961A>65 D73 D<3807FFF814FC3800F0 1E140F1201A213E0A20003131E141CEBC078EBFFF014C03807C0005BA3120F90C7FCA25A EAFFE0A218177F9616>80 D<383FFFFEA2383C3C1C0070130CEA607C12E0EAC078A23800 F800A25BA21201A25BA21203A25BA21207EA7FFCA217177F9615>84 D100 DI<131E133FA213 7F137E1370A213F013E0EA0FFEA2EA00E0120113C0A412031380A412071300127712F712 FEA21278101D7E9611>I105 D107 D<123FA2120EA2121EA2121CA2123CA21238A21278A21270A212 F0A212E6A212EE12FC127808177F960B>I110 DII115 D<12075AA2120EA2121EEAFFC0A2EA1C00123CA21238A21278A2EA70C01271EA7380EA7F 00123E0A147F930D>I<381E0380123F1277EA670712E7000F1300120E5B121E381C0E60 131E381E3EE0380FFFC03807E780130E808D14>II<381E070E003F130F 127738670F0738E70E06120F120EEB1E0E001E130CEA1C1C381E1E1CEB3E38380FFFF038 07E7E0180E808D19>I E /Fi 12 97 df0 D<1207A2120E121C12181238A21270A3126012E0AC12601270A312 38A21218121C120E1207A208227D980E>40 D<12E0A2127012381218121CA2120EA31206 1207AC1206120EA3121CA212181238127012E0A208227E980E>I<1330ABB512FCA23800 3000AB16187E931B>43 D48 D<1206121E12FE12EE120EAFEAFFE0A20B15 7D9412>III<137013F0A212011203EA07701206120E121C12181230127012E0EA FFFEA2EA0070A4EA03FEA20F157F9412>I54 D61 D<12301270126012E012C0A212F0 A31270040A7D960A>96 D E /Fj 39 122 df<123C123E127EA2123E1206A2120E120C12 1C12181238127012E012C0070F7D840E>44 D<1278A212F8A2127005057C840E>46 D<133FEBFF803801E1C0380380E0EA0700000E1370A2121E121C123CA3003813F01278A5 38F001E0A5EB03C0A21480A2130700701300130EEA781E6C5AEA1FF0EA07C014227CA018 >48 D<1302130E133EEA07FE13DEEA001E133E133CA5137C1378A513F813F0A5120113E0 A51203EA7FFFB5FC10217CA018>I II<146014E01301 1303A21307EB0FC0131F133B1333136313C33801C7801387EA03071206120E121C38180F 001230126012E0B512F8A238001F00131EA4133EA23803FFE0A215217DA018>I<380180 18EBE0783803FFF814F014C0140090C7FCA25A1206A3137E3807FF80380FC7C0EB03E0EA 0E01120C000013F0A5EA780300FC13E0A212F8EB07C012E038600F8038701F00EA3C7EEA 1FF8EA0FE015227DA018>II<1218123C383FFFF0 A34813E0386001C0EB03801400485A130EC65A5B5BA25B485AA212035B1207A248C7FCA2 5AA2121E123EA4127E127CA21238142379A118>I<133FEBFFC0EA03E3380780E0EA0F00 1470121EA25AA314F0127C1278A2130112381303383C07E0EA1E0FEA0FFDEA07F9380083 C013031480130700F813005B131E485A485A6C5AEA7FE0EA3F8014227CA018>57 D<120F121FA3120E1200AB1278A212F8A2127008157C940E>I<1406140EA2141F5CA25C A25CECDF80EB01CF148F1303140F130701067FEB0C07A21318A213306E7E1360EB7FFF90 B5FCEBC003D801807F1401EA0300A25A120E001F803AFFC01FFF80A221237EA225>65 D<0003B512E015FC39003E003E81ED0F80A21507137E017C130FA3ED1F00153E01FC5B49 5B90B55A5D9038F801F8EC007C0001805B151E151FA30003143E5BA25D5D4A5A0007EB07 E0007FB55AB548C7FC21227FA123>I<903803FC0690380FFF0E90383F079E9038FC01DC 3901F000FC4848137C485A4848133C90C7FC481438123EA25AA3481400A65A1560A215E0 6C14C0A200781301007CEB038015006C5B6C130E380F803C3807E0F83803FFE038007F80 1F247AA223>I<0007B6FCA239007C003E151E150E1506A213FC5B1403A3EC0700000113 06EBF01EEBFFFEA2EBF01E140E0003130C13E01506A2EC000CA21207491318A215381570 15F0000F1307B612E0A220227EA121>69 D<903801FE0390380FFF8790383F83CF90387C 00EE4848137ED803E0133E485A4848131EA248C7121C123EA25AA3481400A648EB7FFF15 FEEC01F07E1403A2007814E0127C123C003E13076C130F380FC01F3907F07DC03801FFF0 39007FC00020247AA226>71 D<3A07FFE0FFFCA23A007E000FC0017C1480A3151F13FC49 1400A45D120149133E90B512FEA29038F0003E157E120349137CA415FC1207495BA41401 120F3AFFFC1FFF80A226227EA125>I<3807FFE0A238007E00137CA413FC5BA512015BA5 12035BA512075BA5120FEAFFFCA213227EA112>I<3A07FFE00FFCA23A007E0007E0017C 1480ED0E005D5D01FC13F049485A4A5A4AC7FC140E5C00011378EBF0FC13F113F3EBF77E 13FE48487E13F89038E01F80A26E7EA200076D7E13C06E7EA26E7EA2000F497E3AFFFC0F FF80A226227EA126>75 D<3807FFF0A2D8007EC7FC137CA413FC5BA512015BA512035B15 60A215E015C01207EBC001A2EC03801407140F000F133FB61200A21B227EA11E>I III<0007B5128015F039007C00F815 7C153C153EA213FC5BA4157C000114784913F8EC01F0EC07C090B51280ECFC00D803F0C7 FC5BA512075BA4120FA2EAFFFCA21F227EA121>I<0007B5FC15E039007C01F0EC007C15 3C153EA213FC5BA3153C157C00015C49485AEC07C090B5C7FCA29038F01F800003EB07C0 01E07F1403A40007130701C05BA316C015C1000F158039FFFC03E3913801FF00C85A2223 7EA124>82 D<90381FC180EB7FF3EBF87F3901E01F0048487EA248487EA2120FEB000613 8091C7FCA213E013FC6CB47E14E06C7F6C7FEA003F1307EB00FC147CA312300070137812 6012705CA2387801E0EAFC03B4485AD8C7FFC7FCEAC1FC19247DA21B>I<001FB512FE5A 393E03E03C0038141C0030140C12701260130714C012C0A300001400130F5CA5131F91C7 FCA55B133EA5137E381FFFF8A21F227AA123>I<3AFFFC03FF80A23A0FC0007C00491330 A31570121F90C71260A415E05A003E5CA41401127E007C5CA4140392C7FC5C1406140E00 3C5B003E5B6C5B380FC1E06CB45AC648C8FC212379A125>I<3BFFF81FFE03FF023F5B3B 0FC003F000F801804913F017E06F13C01407D807C0EC0180A2020DEB0300A20219130615 F80230130E01E0140C00030160131C161814C05E13E14A6C5A01E3137C2601F3005BA201 F6EB7D80A201FC017FC7FCA2497F153E6C5A153C5B1538A230237AA132>87 D<3A03FFF03FFC16F83A003F801FC0011FEB0F00150C6D6C5A15386D6C5A156001035BEC F180EB01F302FFC7FC6D5A5C147C147EA214FF14DF9038019F80EB031F496C7E130EEB0C 0701187FEB300301607FEBE001D801C07F00031300000F497E3AFFF007FFC0A226227FA1 25>I<48B512F84814F0EBF8039038E007E0018013C03807000FEC1F800006EB3F00143E 48137E5C495A1200495A495A5C130F495A49C7FC133E017E13C05B485AEBF00100031480 EA07E0380FC003A2391F80070048485A003E5B007E13FFB55AA21D227DA11E>90 D97 D<13FF000313C0EA0F87EA1F07123C007C13800078C7FC12F85AA7EB0180EAF803387C07 00EA3E1EEA1FFCEA07F012157C9416>99 D<13FE3803FF80380F87C0381F01E0123C1300 5AB5FCA200F0C7FCA614C0EA7801387C0380383F0F00EA1FFEEA07F813157D9416>101 D114 D116 D<00071370387F07F0EAFF0FEA1F01EA0F001301121F001E13E0A41303123E003C13C0A2 1307A2130F133F381FFFF8EA0FE715157C941B>I<390FFE1FF015E03901F00F800000EB 0700140E140C141CEB78185CA25C137CEB3CC0A2EB3D80133F91C7FC131EA2131CA21318 A25BA2EA7860EAF8C012F9485A007FC8FC123C1C1F80941A>121 D E /Fk 36 122 df12 D14 D<127012F8A3127005057C840E>58 D<127012F812FCA2127C120CA3121C1218A2123812 7012E01260060F7C840E>I<153815F8EC03E0EC0F80EC3E0014F8EB03E0EB0F80013EC7 FC13F8EA03E0EA0F80003EC8FC12F8A2123EEA0F80EA03E0EA00F8133EEB0F80EB03E0EB 00F8143EEC0F80EC03E0EC00F815381D1C7C9926>I<12E012F8123EEA0F80EA03E0EA00 F8133EEB0F80EB03E0EB00F8143EEC0F80EC03E0EC00F8A2EC03E0EC0F80EC3E0014F8EB 03E0EB0F80013EC7FC13F8EA03E0EA0F80003EC8FC12F812E01D1C7C9926>62 D<90B61280A290380F001F1507491303131E1600A2133E133CEC01831403017C90C7FC13 785C5CEBFFFEA2EBF01E140E0001130C13E0A3000390C8FC5BA312075BA2120FEAFFFCA2 21227DA120>70 D<9039FFF83FFEA290390F0003C015075B011E1480A2150F133E013C14 00A25D137C0178131EA290387FFFFE90B5FC9038F0003CA2157C1201491378A215F81203 495BA21401120701805BA2000F130339FFF83FFEA227227DA128>72 DI76 D<147F903803FFC090380F83E090383E00F80178137849 133C4848133E4848131E485A000F141F90C7FC121E123EA25AA348143EA3157CA25A15F8 A2EC01F06C14E01403EC07C00078EB0F80007CEB1F00003C133E6C1378380F81F03807FF C0C648C7FC20247DA225>79 D<90B512E015F890380F007C49131E151F011E130FA2133E 151F133CA2017C131E153E0178133C157801F813F0EC03E090B51280ECFE00D801F0C7FC A25BA21203A25BA21207A25BA2120FEAFFF8A220227DA11F>I<001FB512FEA2903801E0 3E003C140EEA3803003013C00070140C1260EAE007148012C0A2D8000F130091C7FCA35B 131EA3133E133CA3137C1378A313F85BA21201387FFFC0A21F227EA11D>84 D<3A3FFE03FF80A23A03C000FC0000071470A2491360A2000F14E05D90C7FCA24813015D 121EA2003E130392C7FC123CA2007C5B14061278A2140E00F8130C5A141C00705B143000 7813705C383C03C0381F0F80D80FFEC8FCEA03F821237DA121>I<90397FF807FFA29039 07E001F8D903C013E09138E003800101140015066E5A01005B6E5AEC7860EC7CE0EC7DC0 EC3F8092C7FC141E141FA25CEC6F8014C790380187C0EB030301077F130EEB1C0101387F EB700001607F484813780003147C000F14FC3AFFF003FFC013E028227FA128>88 D97 D<137F3801FFC0EA03E3EA0F871307121E003C138090C7FC5AA312F85AA314C0EA7801EB 0380383C1F00EA1FFEEA07F012157E9415>99 D<141FEB01FF14FEEB003EA3143CA2147C A21478A214F8A2EB7CF0EA01FEEA07C7EA0F03001E13E01301EA3C03127C007813C0A213 0712F800F01380148C130F149C38701F18EA783F387CFFB8383FE7F0380F83E018237EA2 19>I<13FEEA03FF380F8380EA1F01123C127CEA780338F81F00EAFFFE13F000F0C7FCA2 5AA3EB0180EAF00338700700EA7C3EEA3FFCEA0FE011157D9417>I<143FECFF80EB01EF 14CF1303150014C013075CA4130F91C7FC3801FFFCA2D8000FC7FC5B131EA5133E133CA4 137C1378A413F85BA35B120112795B12FB5B007FC8FC123E192D7EA218>II<13F8120F5B1201A35BA312035BA31207EB8FC0EBBFF013F8380F E07813C01380EB00F84813F0121EA21301003E13E0123CEB03E314C7007C13C6EA780714 8EEB039C00F813F8387001F018237EA21C>I<1338137CA21378A21300A8EA07C0EA1FE0 123D12311271126112E3EA03C0A212071380A2120F130CEA1F1CEA1E18A213381370EA1F E0EA07C00E2280A111>I<13F8120F5B1201A35BA312035BA31207EB80F8EB83FCEB879C 380F8E3CEB1C7C13381370381FE078140013F8EA1EFEEA3E3EEA3C1FEB0F0C141C387C1F 18EA781E1438EB0F7000F813E0387007C016237EA219>107 DI<3A0F81F80FC03A1FC7FE3FF03939EF 1E783A31FC0FE078D861F813C001F013803AE1E01F00F800035DEBC01EA2EC3E0100075D EB803C923803E180027C13C3000F16009039007807C7168602F813DE48EC03FC000E9038 7001F0291580942B>I<380F83F0381FCFFC3839FE3C3831F81EEA71F0126138E1E03E00 03133C13C0A2147C000713781380ECF860ECF0E0000F14C0EB01F1ECE18014E7391F00FF 00000E137C1B1580941D>I<3803E0F83807F3FE38067F8F380E7E07D80C7C13801378EA 1CF8120013F0A20001130F150013E0A20003131EA25C5C3807F9F0EBFFE0EB9F800180C7 FC120FA290C8FCA25AA2121EEAFFE0A2191F829418>112 D<380F87C0381FCFE03839FC 703831F8F0EA71F1EA61E112E1000313E0EBC000A312075BA3120F90C7FCA35A120E1415 809416>114 D<137E3801FF80EA03C31387EA0707A2EB030013C013FC7F6C7E6C1380EA 001FEA3807127800F81300A2130EEAF03EEA7FF8EA1FE011157E9417>I<13E01201A312 03A213C0A21207A2EAFFFCA2EA0F80A21300A25AA2121EA2123EA2123C130CEA7C1C1318 EA78381370EA7CE0EA3FC0EA1F800E1F7F9E12>I<3807C01EEA1FE0383CF03E0038133C 1270126138E1E07C00011378120313C014F800075B138015C0EB81F1ECE180A2EB83E390 38CFF7003803FEFE3801F87C1A1580941C>I<3807C038381FE07CEA3CF012380070133C 0061131CEAE1E000011318120313C014380007133013801470146014E0EB81C0EB838013 C73803FF00EA00FC1615809418>I<3907C01E07D81FE0EB0F80383CF03E0038133C0070 14070061140338E1E07C000101781300120313C0ECF80700071406EB80F0150E150C151C 0181131815383903E7F8709038FF7FE03900FE1FC02115809423>I<3807E1F0380FF3F8 381C7F1C38383E3C38703C7C1260EAE07C00001378EB7800A213F85BA20078130C007913 1C00F91318EBE03838F3F07000E713E0387F7FC0383C1F8016157E941C>I<380F801EEA 1FC03839E03E0031133C1271126338E3C07C000313781207138014F8000F13F01300A213 0114E01303A2138F3807FFC0EA01FBEA0003130700081380EA3E0F1400131EEA3C3EEA38 7CEA3FF0EA0FC0171F809418>I E /Fl 40 123 df40 D<130EA27FA2EB0380A2EB01C0AE1303A314801307A31400 5BA3131EA2131C133C13381378137013F05B1201485A5B120748C7FC121E5A123812F05A 123280A414>I<120E121EA41206120E120CA2121C12381230127012E012C0070F7D840F> 44 D<127012F8A212F0A205057A840F>46 D<1480130113031307EB1F005BEA03FF13DF EA001EA2133EA2133CA2137CA21378A213F8A25BA21201A25BA21203A25BA21207EAFFFC A211217AA019>49 DI<1207EA0F80A21300A2C7FCAB127012F8A25AA2 09157A940F>58 D<90B512F015FC90380F003E150F49EB0780131EED03C0A2133E013C14 E0A3137C1378A301F8EB07C05BA30001EC0F805B16005D0003141E495B157C157800075C 90388003E0EC0780000F011FC7FCB512FC14F023227DA125>68 D<9039FFF87FFC02F013 F890390F000780150F5B011E1400A25D133E013C131EA2153E137C0178133CA290387FFF FC90B5FC9038F00078A215F81201495BA21401120301C05BA21403120701805BA2000F13 0739FFF87FFC01F05B26227DA124>72 D76 DI<9039FF801FFC16F8010F EB07E09138C00380131F011B140014E05D1339903831F006A20130130EEB70F80160130C 1478151CEBE07C9038C03C18A2EC3E380001131E01801330141FEC0F70120301005B1407 A25A00066D5A120E121F38FFE00101C05B26227DA124>I<14FE903807FF8090380F03E0 90383C01F090387800F84913784848133C485A485A48C7123E5A121E123EA25AA348147C A3157815F85AEC01F0A2EC03E015C06C1307EC0F8000781400007C131E003C137C6C5B38 0F83E03807FF80D801FCC7FC1F2479A225>I<90B512E015F890380F007C49131E151F01 1E130FA2133E151F133CA2017C131E153E0178133C157801F813F0EC03E090B51280ECFE 00D801F0C7FCA25BA21203A25BA21207A25BA2120FEAFFF8A220227DA121>I<903803F8 6090380FFCE090381E1FC0EB7807EB700313E00001148013C0A21203150091C7FCA27F13 F86CB47E14E06C13F8EB3FFC1307EB007C80141EA30030131CA3143C0070133800785B14 F0387C01E038EF07C0D8E7FFC7FCEAC1FC1B247DA21B>83 D<001FB512F8A2EB03C0003C 1438EA380700301380007014301260EAE00F00C01300A3C6481300131EA3133E133CA313 7C1378A313F85BA312015BA21203B5FCA21D2277A123>I<3BFFE03FF81FF817F03B1F00 07C007C0001E90390F800380EE0700021F13065E14375E14675E14C75EEB01875EEB0307 001FEC81801306D80F0E0183C7FC130C011C138613180130138CA201601398A201C013B0 15F001805B5D13005D120E6EC8FC120C2D2376A131>87 D<39FFF003FF13E0391F8000F8 6CC712E090388001C000071480EC0300EBC0060003130E5CEBE01800015B5CEBF0E05C38 00F18001FBC7FC13FF137E137C1378A45BA4485AA31203EA3FFCA2202276A124>89 D97 DI<137E3801FF80EA07C3EA0F07121EA248C7FCA25AA312F85AA31303EA7007EA780E EA3C3CEA3FF8EA0FE011157B9416>I<143EEB03FE14FCEB007CA31478A214F8A214F0A2 1301A2EBFDE0EA03FFEA07CFEA0F07381E03C0A2EA3C07127C00781380A2130F12F800F0 13001418131F1430133E38707E703878FE60383FCFE0381F87C017237BA219>II<147E14FFEB01EFEB03CF14CE14C0EB0780A4130F 1400A33801FFF8A238001E00A4133E133CA4137C1378A413F85BA4485AA45B1273EAF380 12F7B4C7FC127E182D82A20F>II<13F8120F5B1201A35BA312035BA3 1207EB9F80EBFFE013F1380FC0F01380A21301001F13E0121EA21303003E13C0123CEB07 C6148E007C138CEA780F141CEB073800F813F0387003E017237DA219>I<1378A3137013 00A8EA0F80EA1FC0EA39E0123112711263EAE3C0120312071380120F1300A2EA1F18EA1E 381330123EEA3C70EA1CE0EA1FC0EA0F800D217DA00F>I108 D<391F03F03F3A3F8FFCFFC03933DE3DE33A 73F81F81E0D863F0130113E039E3C03E030007013C13C01380A2EC7C07000F1580EB0078 ED0F8C02F8131C481518001EEBF01FED1E380101EB0E70003EEC0FE03A1C00E007C02615 7D9428>I<381F07E0383F9FF8383BFC783873F03CEA63E0A238E3C07C000713781380A2 14F8000F5B1300903801F18014E3001F1400EA1E035CEB01CE003E13FC381C00F819157D 941B>I<137E3801FF803807C7C0EA0F83381F01E0121E123CA21278A2130300F813C012 F0A2EB0780130F00701300EA781EEA3C7CEA1FF0EA0FC013157B9419>I<3803E1F83807 F3FCEB7F1E380E7E0E380C7C0F1378EA1CF8120013F0A20001131F141E13E0A20003133C A2147814F03807F1E0EBFFC0EB9F001380120FA290C7FCA25AA2121EEAFFE0A2181F8094 19>I<381F07C0383F9FE03833FC70EA73F03863E0F013C000E313E0000713005BA3120F 90C7FCA35A121EA3123E121C14157D9415>114 D<13FE3803FF80EA07831307120EA238 0F030013C013F813FE12076C7EEA003F130F1270EAF00EA2EAE01EEAF07CEA7FF8EA1FC0 11157D9414>I<13E01201A31203A213C0A21207A2EAFFF8A2EA0F80A21300A25AA2121E A2123EA2123C1318EA7C381330EA787013E01279EA3FC0EA1F000D1F7C9E10>I<380F80 3CEA1FC03839E07C003113781271126338E3C0F8000313F0120713801381000F13E01301 14E3EB03E714C6A2EB07CEEB9FCC3807FDFC3803F0F818157D941A>I<380F80E0381FC1 F0EA39E11231EA71E000631370EAE3C0000313601207138014E0000F13C0130013011480 130314005B138EEA07FCEA01F814157D9416>I<390F807838D81FC0137C3839E0F80031 13F00071143C0063141CEAE3C10003EBE0181207138101831338000F1430EB03C0A21570 1560010713E0ECC1C090388FE3803807FDFF3901F87E001E157D9420>I<380F803CEA1F C03839E07C003113781271126338E3C0F8000313F0120713801381000F13E01301A21303 14C0A21307139F3807FF80EA03F7EA0007130F1400123C131E133EEA387C5BEA3FE0EA1F 80161F7D9418>121 D<3801F0303803FC703807FEE0380FFFC0EA0E07380C0380380007 00130E5B5B5B485AEA038038070060000E13E0381C01C0EA1F83383FFF80127B00E01300 EAC07C14157E9414>I E /Fm 38 123 df<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80 EA1F000B0B7B8A16>46 D48 D<14E01303130F133FEA1FFFB5FCA3EAE03F1200B3AF007FB512F0A41C2E7AAD28>IIII<001C1470391FC007F090B5FC15E015C0158015005C14F814E091 C7FC001EC8FCA7EB1FF890B5FC001F14809038F03FE09038801FF0EB000F001E14F8C7EA 07FCA315FEA2121E127FEAFF8013C0A315FCEB800FD87F0013F8007E131F6CEB3FF09038 C0FFE06CB512C0000714006C13FC38007FE01F2E7CAD28>II66 D68 DI< B612C0A4C6EBC000B3B3A5B612C0A41A317EB01E>73 D77 DI80 D82 D<90391FF8038090B51207000314CF4814FF380FF0 0F381FC001393F80007F48C7123F151F127E00FE140FA215077E7F6D90C7FC13F013FE38 7FFFF014FF6C14E015F86C806C806C80000115806C6C14C0010F14E013001407020013F0 153F151F150F12F01507A37E16E06C140F6C15C06C141F01C0EB3F809039FC01FF0090B5 5A00F95CD8F07F13F0D8E007138024317CB02D>I87 D97 DIIII<90393FF80FC09039FFFE3FE000 0390B512F03907F83FF7390FE00FE7001F14F39039C007F1E0003FECF800A7001F5CEBE0 0F000F5C3907F83FC090B55A000E49C7FCEB3FF8001EC9FCA3121F7F90B512C06C14F815 FE816C15804815C05A383F8000007EC7EA1FE000FE140F481407A36C140F007E15C0007F 141FD83FC0EB7F803A1FF803FF000007B512FC000114F0D8001F90C7FC242F7E9F28> 103 DII107 DI<2703 F00FF8EB3FE000FFD93FFEEBFFF891B5008313FE903AF1F07F87C1903BF3C03FCF00FF26 0FF78013DE00079026001FFCEB7F8001FE5C495CA2495CB2B500C3B5380FFFFCA43E207D 9F43>I<3903F00FF800FFEB3FFE91B512809038F1F07F9039F3C03FC0380FF780000790 38001FE013FE5BA25BB2B500C3B5FCA428207D9F2D>II<3901F83FF039FFF9FFFE90B6128002E013C09138803FE03A07FE001F F049EB0FF85BED07FCA3ED03FEAAED07FCA216F8150F6DEB1FF07F6DEB3FE09138E0FFC0 01FBB5120001F913FC9038F83FE091C8FCAAB512C0A4272E7E9F2D>I<3803F07F39FFF1 FFC001F313E014CF9038F71FF0120FEA07FE13FCEC0FE0A2EC010049C7FCB1B512E0A41C 207E9F21>114 D<3801FF8E000F13FE5AEA3F01387C007E0078133E00F8131EA27E6C90 C7FC6C7E13FC387FFFC014F06C7F6C7F6C7F00037FC67E01011380EB007F00F0131FA26C 130FA27EEC1F00B45BEBC0FEEBFFFC00FB13F000E013C019207D9F20>I<133CA5137CA3 13FCA21201A212031207381FFFFEB5FCA3D803FCC7FCAFEC0780A7140FD801FE13006D5A 6C13FEEB3FFCEB0FF0192E7FAD1F>II<3A7FFF80FFFEA43A01FE003F006C6C133E6E5A6D6C5A90383FC1F090381FE3E0EB0F F7ECFFC06D5B6D90C7FC6D5A6D7E81497FA2497F903807CFF090380F8FF890381F87FC90 383F03FEEB3E01496C7E4914804848EB7FC026FFFE01B5FCA428207F9F2B>120 D<003FB512F8A39038C01FF0EB003F003EEB7FE0003C14C0007CEBFF805BD8780313005C 1307495A00005B495A133F495AECC03CEBFF805A4813005B0007147C485A491378484813 F8003F1301387FE003EBC00FB6FCA31E207E9F24>122 D E /Fn 74 123 df0 D<90381FE1F890387FF7FC3901F07F3E3803E0FE3807C0FCEA0F809038007800A8B6 12C0A2390F007800B139FFE3FFC0A21F2380A21C>11 DI< 90380FE07F90397FF9FFC09038F83FC13A01F07F83E0D803E013033807C07EEB807C9138 3C01C092C7FCA6B712E0A23907803C031501B03A7FF1FF8FFEA2272380A229>14 D35 D<127012F812FCA2127C120CA3121C1218A21238127012E01260060F7CA20E>39 D<13E0120113C0EA0380EA0700A2120E121E121CA2123C1238A21278A21270A212F0B012 70A21278A21238A2123C121CA2121E120E7EA2EA0380EA01C013E012000B327CA413>I< 12E07E12707E7EA27E120F7EA213801203A213C0A21201A213E0B013C0A21203A21380A2 12071300A25A120E5AA25A5A12F05A0B327DA413>I<497EB0B612FEA23900018000B01F 227D9C26>43 D<127012F812FCA2127C120CA3121C1218A21238127012E01260060F7C84 0E>II<127012F8A3127005057C840E>I48 D<13C01201120712FF12FB1203B3A8B5FCA210 217CA018>III<1307A25B5BA25BA213 6F13EF13CFEA018FA2EA030F12071206120C121C121812381230126012E0B512F8A23800 0F00A7EBFFF0A215217FA018>I<38300180EA3E07EA3FFF140013FC13F00030C7FCA6EA 31F8EA37FEEA3F1F383C0F80EA380714C0EA000314E0A412F8A414C0EAE0070070138038 780F00EA3C3EEA1FFCEA07F013227EA018>I<137E3801FF80EA07C3380F01C0EA0E0712 1E123C12380078C7FCA3EA7020EAF3FCEAF7FF38FE0F80EAFC0738F803C0A2EB01E012F0 A51270A2127814C0EA3803003C1380EA1E07380F1F00EA07FEEA03F813227EA018>I<12 601270387FFFE0A314C038600180EAE00338C007001306130EC65A131813381330137013 6013E0A21201A25B1203A41207A86C5A13237DA118>III<127012F8A312701200 AB127012F8A3127005157C940E>I61 D<497E497EA3497EA3497E130DA2EB19F81318A2EB307CA3497EA3497EA33901800F8090 B5FCA239030007C0A30006EB03E0A2000E14F01401003FEB03F839FFC01FFFA220237EA2 25>65 DI<90380FF030EB7FFC9038FC1E703803F0073907C003F0380F8001 EA1F001400123E003C1470127CA215305AA21500A71530127CA36C147015606C14E015C0 380F80013907C003803903F007003800FC1EEB7FFCEB0FF01C247DA223>IIII<90380FF018EB3FFC9038FC0F383903F003B83907C001F8380F800090C7FC481478 123E15385AA215185AA21500A6EC3FFFA2007CEB00F8A37EA27E6C7EA23807E0013803F0 033900FE0F3890383FFE1890380FF80020247DA226>I<3AFFFE1FFFC0A23A07C000F800 AD90B5FCA2EBC000AF3AFFFE1FFFC0A222227FA125>II76 DI<3AFFE003FFC0A23A07F0003C006D1318A2EA 06FC137EA27FEB1F80A2EB0FC0EB07E0A2EB03F0EB01F8A2EB00FC147EA2143FEC1F98A2 EC0FD8EC07F8A214031401A214001578120FD8FFF01338151822227FA125>III82 D<3803F860EA0FFE381E1FE0EA3C07EA78031301EAF000A21460A2 7E14007E127EEA7FC013FC6CB4FC6C13806C13C0000113E0EA001F1307EB03F01301A2EA C000A37E14E0EAF00112F838FC03C038FF078038C7FF00EAC1FC14247DA21B>I<007FB5 12F8A2387C07C00070143800601418A200E0141C150C12C0A400001400B3A248B5FCA21E 227EA123>I86 D<3BFFF83FFE07FEA23B1F8007F001F8000F903903 E000E06F136001C015E0000716C0A29038E006F80003ED0180A2EC0C7CD801F0EC0300A2 EC1C7E9039F8183E0700001506A29038FC301F017C5CA29138600F8C013E1498A202E013 D890393FC007F8011F5CA2EC8003010F5CA2EC00016D5CA32F237FA132>I<397FFC0FFF A23907F003F000036D5A00015C6D485A000091C7FCEBFC06EB7E0EEB3E0CEB3F18EB1FB8 EB0FB014E013071303801301497E497EEB067CEB0C7EEB1C3FEB181F01307F9038700FC0 EB600701C07F00011303D803807F6E7ED80FC07F3AFFF00FFFC0A222227FA125>II<12FEA212C0B3B3A912FEA207317BA40E>91 D<12FEA21206B3B3A912FEA20731 7FA40E>93 D<1204120E121FEA3B801231EA60C0EAC060A20B087AA218>I97 D<120FB4FCA2121F7EAAEB1F80EB FFE0EBE1F0EB8078EB003CA2141C141EA7143CA2EB807C14F8EBE1F0380E7FE0380C3F80 17237FA21B>IIII<133FEBFF80 3803E7C0EA07C71387120F90C7FCA8EAFFF8A2000FC7FCB1EAFFF0A2122380A20F>I<14 F03803F3F8380FFFB8381E1F78383C0F3838780780A6383C0F00EA1E1EEA3FFCEA33F000 70C7FCA21278EA3FFF14C06C13E04813F0387801F838F000785A1438A26C1378A2387C01 F0383F07E0380FFF803803FE0015217F9518>I<120FB4FCA2121F7EAAEB1F80EB7FE013 E1EBC1F01380A21300AD38FFF3FFA218237FA21B>I<120E121FA3120EC7FCA8120F127F A2121F7EAFEAFFE0A20B2280A10D>I<1338137CA313381300A8133CEA03FCA2EA007C13 3CB3A312F8137C137813F0EA7FE0EA3F800E2C84A10F>I<120FB4FCA2121F7EAAEB0FFC A2EB07E014C01400130E5B5B137C13FC7F13BF131FEB0F8014C01307EB03E0A214F038FF E7FEA217237FA21A>I<120FB4FCA2121F7EB3ABEAFFF0A20C2380A20D>I<390F1FC0FE3A FF7FF3FF809038F1F78F3A1FC0FE07C0390F807C03A2EB0078AD3AFFF3FF9FFCA226157F 9429>I<380F1F8038FF7FE013E1381FC1F0EA0F80A21300AD38FFF3FFA218157F941B>I< EA01FCEA07FF380F0780381C01C0383800E0007813F00070137000F01378A70070137000 7813F0003813E0381C01C0380F07803807FF00EA01FC15157F9418>I<380F1F80B512E0 EBE1F0380F80F8EB007C143CA2141EA6143E143CA2EB807C14F8EBE3F0EB7FE0EB3F8090 C7FCA8EAFFF0A2171F7F941B>I<3803F860380FFCE0EA1F8EEA3E07EA7C03EA7801A212 F812F0A61278A2EA7C03EA3E07EA1F0FEA0FFDEA03F1EA0001A8EB1FFEA2171F7E941A> III<1206A5120EA3121E123EEAFFFC A2EA1E00AA130CA5EA1F1CEA0F3813F8EA03E00E1F7F9E13>I<000F13F0EAFF0FA2EA1F 01EA0F00AB1301A21303380787F8EBFEFFEA01FC18157F941B>I<38FFC1FEA2381F00F8 6C13701460380780C0A33803C180A213E300011300A2EA00F6A3137CA31338A217157F94 1A>I<39FF8FF8FFA2391F03E07CD81E011338000F14301303ECF070D807831360138790 388678E0D803C613C013CEEBCC3DD801EC138013FCEBF81F00001400A2497EEB700EA220 157F9423>I<387FE3FFA2380FC1F8000313E0EBE1C000015BD800F3C7FC13FF137E133C 133E133F5BEB6780EBC7C0EA01C3380381E000077F001F7F39FFC3FF80A2191580941A> I<38FFC1FEA2381F00F86C13701460380780C0A33803C180A213E300011300A2EA00F6A3 137CA31338A21330A21370136012F85B12F9EAFB80007FC7FC123E171F7F941A>I<383F FFC0A2EA3C0F0038138038301F00EA703EEA607E137C5BEA01F01203EBE0C0EA07C0EA0F 80121F1301003E1380EA7C03EAFC07B5FCA212157F9416>I E /Fo 43 122 df12 D<90390FF81FF890397FFEFF FC3A01FC1FF83ED803F0EBE03F484848485A120F01C01380A2163E021F131C93C7FCA3B8 FCA33A0FC01F803FB03B7FF8FFF1FFE0A32B237FA22F>14 D<123C127F5A1380A3127F12 3D12011203A213005A120EA25A5A123009127C8710>44 D<123C127E12FFA4127E123C08 087C8710>46 D<1438A21478A214F0A214E01301A2EB03C0A214801307A214005BA2131E A2131C133CA25BA2137013F0A2485AA25B1203A2485AA290C7FC5AA2120E121EA25AA212 381278A25AA25AA215317DA41C>I<13FE3807FFC0380FC7E0381F01F0003F13F8EA3E00 007E13FCA312FE14FEAD007E13FCA3003E13F8EA3F01001F13F0380FC7E03807FFC03800 FE0017207E9F1C>I<13181378EA03F812FFA212FD1201B3A5387FFFE0A313207C9F1C>I< EA03FC381FFF804813C0387C3FE038FC1FF0EAFE0FEB07F8A21303127CEA3807120014F0 130F14E0EB1FC01480EB3F00137E13F8485AEBE038EA03C0EA0780EA0F00001C1378383F FFF05AB5FCA415207D9F1C>II54 D<1270127C387FFFFEA414FC14F838F000F038E001E014C01303EB07803800 0F00131EA25B137C137813F8A3485AA41203A76C5A17227DA11C>I<48B4FC000713C000 1F13E0383F87F0387F01F8127E38FE00FCA314FEA51301127EEA3F031307EA1FFEEA07FC EA0020EB00FCA2121E383F01F8A2EB03F01307383E1FE0381FFFC06C1300EA03F817207E 9F1C>57 D<123C127E12FFA4127E123C1200A6123C127E12FFA4127E123C08167C9510> I<147014F8A3497EA2497EA3EB077FA2010F7FEB0E3FA2496C7EA2013C7FEB380FA20170 7F140701F07F90B5FCA24880EBC001A248486C7EA200078090C77E3AFFF007FFF8A32522 7EA12A>65 D<903907FE018090383FFFC390B512EF0003EB81FF3907FC007FD80FF0133F 4848131F49130F003F1407485AA2150348C7FC92C7FCA96C6CEB0380A36C6C1307001F15 006D5B6C6C131ED807FC5B3903FF81F8C6EBFFF0013F13C0010790C7FC21227DA128>67 DIII73 D76 DI80 D<3803FE06380FFFCE4813FE EA3F03387C007E143E48131EA2140E7E6C13007E13F06CB4FC14E06C13F06C13F86C13FC 000313FEEA007FEB03FF1300143FA200E0131FA37E6C133E6C137E38FF80FCEBFFF800E7 13F000C013C018227DA11F>83 D<007FB61280A3397E03F81F007C140712780070140300 F015C0A200E01401A4000091C7FCB248B512F0A322227EA127>I97 D<3801FF80000713E0381FC3F0EA3F8313 03127F387E01E000FEC7FCA8127FA2383F80381478381FE1F03807FFE00001138015167E 9519>99 D<49B4FCA3EB003FAAEA01FE0007B5FCEA1FC1EA3F80EB003F5A127E12FEA812 7EA2007F5B6C5BD81FC313E0380FFFBF3801FE3F1B237EA21F>III<3801FE1F000FB51280EA1F87383F 03F7EA3E01007EEBF800A5003E5BEA3F03381F87E0EBFFC0D839FEC7FC0038C8FCA2123C 383FFFE014FC6C7F805A397C007F8048131F140FA36C131F007EEB3F00383F80FE380FFF F8000113C019217F951C>II<121E123FEA7F80A4EA3F00121EC7FCA6EAFF80A3121F B0EAFFF0A30C247FA30F>I107 DI<3AFF87F80FF090399FFC3F F89039BC7E78FC3A1FF07FE0FE9039E03FC07E01C01380A201801300AC3BFFF1FFE3FFC0 A32A167E952F>I<38FF87F0EB9FFC13F8381FF07E13E013C0A21380AC39FFF1FFC0A31A 167E951F>I<13FE3807FFC0380F83E0381F01F0383E00F8007E13FCA300FE13FEA7007E 13FCA2383F01F8001F13F0380F83E03807FFC03800FE0017167E951C>I<38FF9FE0EBFF FCEBF0FE381FC07F9038803F80A3EC1FC0A8EC3F80A2EC7F0013C0EBF1FEEBFFF8EB9FE0 0180C7FCA7EAFFF0A31A207E951F>I<38FF1FC0EB3FE0EB7BF0EA1F6313E313C3EBC1E0 EB8000ACEAFFF8A314167F9517>114 DII<38FF83FEA3381F807EAD14FEA21381390FC3FFC03807FF 7FEA03FE1A167E951F>I<39FFF03FE0A3390FC00E00EBE01E0007131CA26C6C5AA2EBF8 7800011370EBFCF000005BA2EB7FC0A36D5AA26DC7FCA2130EA25BA2EA783CEAFC381378 5BEA79E0EA7FC0001FC8FC1B207F951E>121 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: Letter %%BeginPaperSize: Letter /setpagedevice where { pop 1 dict dup /PageSize [ 612 792 ] put setpagedevice } { statusdict /lettertray known { statusdict begin lettertray end /letter where { pop letter } if } { /letter where { pop letter } { statusdict /setpage known { statusdict begin 612 792 0 setpage end } if } ifelse } ifelse } ifelse %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop 78 53 1945 2 v 78 322 2 270 v 124 103 a Fo(Mac)n(hine)20 b(Learning:)25 b(F)-5 b(oundations)481 b(Spring)19 b(semester,)e (1996/7)262 216 y Fn(Lecture)f(9)155 b Fm(Decision)25 b(tree)i(pruning)154 b Fn(Ma)o(y)15 b(21,)i(1997)124 300 y Fl(L)n(e)n(ctur)n(er:)k(Yishay)c(Mansour)785 b(Scrib)n(e:)23 b(Mariano)17 b(Schain)p 2021 322 V 78 324 1945 2 v 75 562 a Fm(10.1)82 b(In)n(tro)r(duction)75 671 y Fn(In)15 b(a)g(previous)h(lecture)f(w)o(e)g(examined)g(metho)q(ds)g(to)h(build)g (decision)g(trees)f(based)h(on)f(giv)o(en)g(examples.)75 732 y(While)i(building)h(the)e(trees)f(w)o(e)g(tried)h(to)g(k)o(eep)f (its)i(size)f(as)g(small)h(as)g(p)q(ossible,)g(y)o(et,)e(the)g (resulting)j(tree)75 792 y(classi\014ed)k(correctly)d Fl(al)r(l)j Fn(the)e(examples.)32 b(As)20 b(seen)g(in)h(the)f(previous) h(lecture,)f(this)h(prop)q(ert)o(y)f(migh)o(t)75 852 y(cause)g(an)h(o)o(v)o(er)e(\014tting)i(e\013ect)f(\(the)g(resulting)i (tree)d(adapts)i(itself)g(to)g(the)f Fl(noise)h Fn(in)f(the)g(sample)h (set)75 912 y(rather)12 b(than)h(the)f(true)g(underlying)i(structure,)e (and)h(will)i(probably)e(fail)h(to)f(classify)g(unseen)g(instances\).) 148 972 y(The)22 b(goal)h(of)e(this)h(lecture)f(is)h(to)g(presen)o(t)f (metho)q(ds)h(to)f Fl(prune)h Fn(the)f(unnecessary)g(no)q(des)i(of)e (the)75 1032 y(resulting)15 b(decision)f(tree.)20 b(The)13 b(problem)h(is)g(actually)h(of)e Fl(mo)n(del)i(sele)n(ction)g Fn(-)f(the)f(mo)q(del)h(size)f(parameter)75 1093 y(is)i(the)f(tree)g (size)h(and)f(the)h(trade)f(o\013)h(is)g(with)h(the)e(accuracy)g(of)h (the)f(tree)f(on)i(the)f(giv)o(en)h(sample)g(set.)20 b(W)l(e)75 1153 y(will)e(examine)e(four)h(metho)q(ds,)f(eac)o(h)g (facing)h(the)f(problem)h(in)g(a)f(di\013eren)o(t)h(manner.)75 1319 y Fm(10.2)82 b(Reduce)26 b(Error)i(Pruning)75 1428 y Fn(The)19 b(\014rst)g(metho)q(d)g(splits)i(the)e(sample)g(set)g(in)o (to)g(a)h(training)h(set)e(and)g(a)g(test)g(set.)29 b(The)19 b(training)i(set)75 1488 y(is)e(used)g(to)g(build)h(the)e(decision)i (tree)e Fo(T)p Fn(.)28 b(And)19 b(the)f(test)g(set)h(is)g(used)g(to)g (decide)f(whether)h(a)g(no)q(de)g(of)75 1548 y Fo(T)h Fn(should)i(b)q(e)e(pruaned)g(or)h(not)f(\(The)g(pruning)h(of)g(an)f (in)o(ternal)h(no)q(de)g Fk(v)g Fn(is)g(done)f(b)o(y)g(replacing)h(the) 75 1609 y(subtree)16 b(of)h Fk(v)g Fn(b)o(y)f(a)h(leaf)s(\).)22 b(In)16 b(this)h(section)g(w)o(e)e(describ)q(e)i(ho)o(w)g(the)f (decision)h(is)g(done.)148 1669 y(First,)h(w)o(e)f(determine)f(for)i (ev)o(ery)e(in)o(ternal)i(no)q(de)g Fk(v)h Fn(of)e Fo(T)h Fn(the)f(lab)q(el)i(of)e Fk(v)r Fn(,)g(if)h(pruned.)24 b(W)l(e)17 b(set)g(the)75 1729 y(lab)q(el)i(of)f(the)f(pruned)g Fk(v)i Fn(to)f(b)q(e)g(the)f(ma)s(jorit)o(y)g(class)i(among)f(the)f (examples)h(in)g(the)f(training)i(set)f(that)75 1789 y(reac)o(h)f Fk(v)r Fn(.)23 b(W)l(e)17 b(no)o(w)g(use)g(the)g(test)g (set)g(to)h(compute)e(for)i(eac)o(h)e(no)q(de)i Fk(v)h Fn(the)e(n)o(um)o(b)q(er)f(of)h(examples)h(that)75 1849 y(reac)o(h)c Fk(v)r Fn(,)f(and)i(the)f(n)o(um)o(b)q(er)g(of)g(errors)h (if)g(the)f(classi\014cation)j(in)e Fk(v)g Fn(is)h(done)e(using)i(the)e (lab)q(el)i(of)e(a)h(pruned)75 1910 y Fk(v)r Fn(.)148 1970 y(The)j(algorithm)i(basically)h(c)o(hec)o(ks)16 b(for)j(eac)o(h)f(in)o(ternal)h(no)q(de)f Fk(v)i Fn(if)f(pruning)g(it)g (impro)o(v)o(es)f(the)g(gen-)75 2030 y(eralization)h(abilit)o(y)f(of)f (the)f(tree.)21 b(Sp)q(eci\014cally)l(,)d(w)o(e)e(compare)g(the)g (computed)h(n)o(um)o(b)q(er)e(of)i(errors)g(o)o(v)o(er)75 2090 y(the)d(test)g(set)g(of)g(the)g(tree)f(pruned)h(at)h Fk(v)g Fn(to)g(the)f(n)o(um)o(b)q(er)f(of)h(errors)h(o)o(v)o(er)e(the)h (test)g(set)f(of)i(all)g(the)f(subtree)75 2150 y(ro)q(oted)j(at)g Fk(v)g Fn(\(whic)o(h)g(is)g(the)f(sum)g(of)h(the)f(errors)g(of)h(all)g (the)f(lea)o(v)o(es)g(of)h(the)f(subtree\).)148 2211 y(In)o(tuitiv)o(ely)l(,)24 b(if)f(a)h(subtree)e(represen)o(ts)h(o)o(v)o (er)f(\014tting,)j(then)e(the)f(true)h(error)g(\(appro)o(ximated)h(b)o (y)75 2271 y(using)f(the)f(test)f(set\))h(of)g Fk(v)h Fn(as)f(a)g(pruned)g(leaf)g(will)i(b)q(e)e(signi\014can)o(tly)h (smaller)g(than)f(the)g(true)f(error)75 2331 y(of)e(the)g(subtree)g(ro) q(oted)h(at)g Fk(v)r Fn(.)29 b(W)l(e)19 b(can)h(therefore)e(conclude)i (the)f(pruning)h(rule:)28 b(If)18 b(the)h(n)o(um)o(b)q(er)g(of)75 2391 y(classi\014cation)j(errors)d(o)o(v)o(er)f(the)h(test)f(set)h(of)g Fk(v)i Fn(as)e(a)h(pruned)f(leaf)g(is)h(signi\014can)o(tly)h(smaller)f (than)f(the)75 2451 y(error)f(of)g(the)g(subtree)g(ro)q(oted)h(at)g Fk(v)g Fn(then)f(w)o(e)g(c)o(ho)q(ose)g(to)h(prune)f Fk(v)r Fn(.)26 b(If)18 b(the)f(n)o(um)o(b)q(er)h(of)g(classi\014cation) 1038 2576 y(1)p eop %%Page: 2 2 2 1 bop 0 -31 a Fn(2)1404 b Fj(Lecture)16 b(9:)21 b(Ma)o(y)16 b(21,)g(1997)0 101 y Fn(errors)22 b(o)o(v)o(er)f(the)g(test)h(set)g(of) g Fk(v)h Fn(as)f(a)g(pruned)g(leaf)h(is)f(signi\014can)o(tly)i(larger)f (than)f(the)f(error)h(of)g(the)0 161 y(subtree)16 b(ro)q(oted)i(at)f Fk(v)h Fn(then)f(w)o(e)f(c)o(ho)q(ose)h(not)g(to)g(prune)g Fk(v)r Fn(.)22 b(Otherwise)17 b(\(when)g(there)f(is)h(no)g (signi\014can)o(t)0 222 y(di\013erence)g(in)h(the)f(n)o(um)o(b)q(er)f (of)i(errors\))f(w)o(e)g(can)g(mak)o(e)f(arbitrary)j(c)o(hoice)d(\(It)h (is)h(natural)h(that)e(w)o(e)g(will)0 282 y(prefer)f(smaller)h (trees\).)73 344 y(The)k(order)g(in)h(whic)o(h)g(no)q(des)f(are)h(c)o (hec)o(k)o(ed)c(is)k(from)f(the)g(lea)o(v)o(es)g(up)g(to)o(w)o(ards)g (the)g(ro)q(ot.)37 b(While)0 404 y(c)o(hec)o(king,)15 b(the)h(tree)g(c)o(hanges)g(and)h(the)f(coun)o(ts)g(are)h(up)q(dated)g (accordingly)l(.)73 466 y(T)l(o)g(illustrate)g(the)f(algorithm)i(w)o(e) d(will)j(use)e(as)g(an)h(example)e(the)h(decision)h(tree)e Fo(T)h Fn(in)g(Figure)h(10.1.)0 526 y(As)h(the)g(tree)f(is)i(not)f (pruned)g(y)o(et,)f(the)h(leaf)h(lab)q(el)g(is)g(the)f(class)h(of)f (all)i(the)e(examples)g(in)g(the)g(training)0 586 y(set)e(that)h(reac)o (h)e(the)h(leaf.)22 b(Note)15 b(that)i(w)o(e)f(can)g(not)h(assume)f(an) o(ything)h(lik)o(e)f(that)h(for)f(the)g(examples)g(in)0 646 y(the)g(test)g(set.)73 709 y(W)l(e)g(\014rst)g(examine)g(the)g(b)q (ottom)g(righ)o(t)h(dotted)f(subtree)g(whose)g(ro)q(ot)i(is)e(the)g(no) q(de)h(lab)q(eled)g Fk(X)1850 716 y Fi(4)1870 709 y Fn(.)k(In)0 769 y(the)e(test)g(set)g(there)g(are)g(5)g(examples)h(reac)o(hing)f (the)g(subtree,)g(2)h(of)f(them)g(to)g(the)g(left)h(leaf)f(and)h(3)g (to)0 829 y(the)g(righ)o(t)g(leaf.)34 b(Assume)19 b(that)i(b)q(oth)f (examples)h(that)f(reac)o(h)f(the)h(left)g(leaf)h(ha)o(v)o(e)e(class)i (lab)q(el)h(1)e(and)0 889 y(that)c(among)h(the)f(three)f(examples)h (that)h(reac)o(h)e(the)h(righ)o(t)g(leaf,)h(t)o(w)o(o)e(ha)o(v)o(e)h (class)h(lab)q(el)g(1)g(and)f(one)g(has)0 949 y(class)g(lab)q(el)g(0)f (\(This)h(is)f(indicated)h(in)f(the)g(\014gure)g(b)o(y)f(the)g(n)o(um)o (b)q(ers)g(b)q(elo)o(w)i(the)e(subtree.\))21 b(The)14 b(subtree)0 1009 y(error)i(is)h(therefore)e(2,)i(while)g(the)f(error)g (of)g Fk(X)852 1016 y Fi(4)889 1009 y Fn(as)g(a)h(pruned)f(leaf)h(is)g (1)f(\(The)g(lab)q(el)i(of)e(the)g(pruned)g(leaf)0 1070 y Fk(X)40 1077 y Fi(4)78 1070 y Fn(is)j(1)f(since)g(in)h(the)e (training)j(set)e(3)g(of)h(the)e(examples)h(reac)o(hing)h Fk(X)1333 1077 y Fi(4)1371 1070 y Fn(ha)o(v)o(e)e(class)i(lab)q(el)g(1) g(and)f(only)0 1130 y(one)e(example)g(has)h(class)h(lab)q(el)g(0\).)j (W)l(e)16 b(can)g(therefore)g(prune)g Fo(T)g Fn(at)h Fk(X)1349 1137 y Fi(4)1369 1130 y Fn(.)k(A)16 b(similar)i(analysis)h (is)e(done)0 1190 y(for)k(the)f(subtrees)h(whose)g(ro)q(ots)h(are)e Fk(X)763 1197 y Fi(6)804 1190 y Fn(and)h Fk(X)943 1197 y Fi(3)984 1190 y Fn(\(Note)f(that)h(when)g(considering)h(the)f Fk(X)1755 1197 y Fi(3)1795 1190 y Fn(subtree)0 1250 y(the)16 b(coun)o(ters)f(are)h(c)o(hanged)g(since)g(w)o(e)f(already)i(pruned)e (at)i Fk(X)1172 1257 y Fi(4)1192 1250 y Fn(\).)k(The)16 b(resulting)h(tree)e(is)h(presen)o(ted)f(in)0 1310 y(Figure)i(10.2.)73 1372 y(Another)g(p)q(ossible)i(pruning)g(metho)q(d)e(is)h(illustrated)h (in)f(\014gure)f(10.3)h(Where)f(an)g(in)o(ternal)h(no)q(de)g(is)0 1433 y(replaced)e(b)o(y)g(one)h(of)f(its)h(subtrees.)k(The)c(pruning)g (rule)g(is)g(similar)h(to)e(the)g(one)h(describ)q(ed)g(ab)q(o)o(v)o(e.) 73 1495 y(It)i(can)g(b)q(e)g(sho)o(wn)h(that)g(if)f(the)g(size)h(of)f (the)g(test)g(set)g(is)h(large)g(enough)g(then)f(the)g(error)g(coun)o (t)g(at)0 1555 y(eac)o(h)d(no)q(de)h(is)g(close)g(to)g(the)f(true)g (error.)21 b(Therefore)16 b(b)o(y)g(pruning)i(w)o(e)e(truly)h(reduce)e (\(or)i(not)g(increase\))0 1615 y(the)f(classi\014cation)j(error.)73 1677 y(This)j(metho)q(d)f(\(similar)h(to)f(CV\))f(requires)h(that)g(w)o (e)f(use)g(only)h(part)g(of)g(the)f(giv)o(en)h(examples)g(to)0 1737 y(build)d(the)e(decision)h(tree)f(\(the)g(rest)g(is)h(used)f(as)h (a)g(test)f(set\).)0 1915 y Fm(10.3)82 b(Structural)27 b(Risk)f(Minimization)0 2028 y Fn(W)l(e)c(will)j(use)e(dynamic)g (programming)h(to)f(\014nd)g(for)g(ev)o(ery)e Fk(k)k Fn(the)e(b)q(est)g(\(with)g(minim)o(um)g(n)o(um)o(b)q(er)0 2088 y(of)d(errors\))g(decision)h(tree)e Fl(T)544 2095 y Fh(k)584 2088 y Fn(of)h(size)g Fk(k)i Fn(that)e(is)g(a)g(pruned)g(v)o (ersion)g(of)g(the)f(giv)o(en)h(decision)h(tree)e Fl(T)7 b Fn(.)0 2149 y(Ob)o(viously)l(,)21 b(the)e(n)o(um)o(b)q(er)g(of)h (errors)g(decreases)f(as)h(w)o(e)f(increase)h Fk(k)r Fn(.)31 b(W)l(e)19 b(can)h(apply)h(the)e(metho)q(d)h(of)0 2209 y(Structural)13 b(Risk)f(Minimization)i(to)e(c)o(hose)f(the)h(b)q (est)g Fl(T)1024 2216 y Fh(k)1045 2209 y Fn(.)20 b(W)l(e)11 b(can)h(alternativ)o(ely)h(use)f(Cross)h(V)l(alidation)0 2269 y(to)j(test)e(eac)o(h)h Fl(T)296 2276 y Fh(k)332 2269 y Fn(on)h(an)g(indep)q(enden)o(t)f(test)g(set,)g(and)h(c)o(ho)q (ose)f(among)h(the)f(set)g(of)h('b)q(est')e(trees)h(the)g(tree)0 2329 y(with)i(the)f(least)h(n)o(um)o(b)q(er)f(of)g(errors.)73 2391 y(The)j(main)g(problem)g(is)h(\014nding)g(for)f(ev)o(ery)e Fk(k)k Fn(the)d(b)q(est)h(decision)h(tree)e Fl(T)1478 2398 y Fh(k)1518 2391 y Fn(of)h(size)g Fk(k)r Fn(.)28 b(Note)19 b(that)0 2451 y(this)e(problem)g(is)g(equiv)m(alen)o(t)f(to)h (\014nding)g(for)g(an)o(y)f Fk(e)f Fn(the)h(smallest)i(tree)d(with)i (no)g(more)f(than)g Fk(e)g Fn(errors.)p eop %%Page: 3 3 3 2 bop 75 -31 a Fj(10.3.)38 b(STR)o(UCTURAL)16 b(RISK)g(MINIMIZA)l(TI) o(ON)922 b Fn(3)p 1 setlinewidth np 1453 600 94 0.00 360.00 arc st 1 setlinewidth np 1642 902 94 0.00 360.00 arc st 1 setlinewidth np 1283 1242 94 0.00 360.00 arc st 1 setlinewidth np 1547 1242 94 0.00 360.00 arc st 1 setlinewidth np 698 1582 94 0.00 360.00 arc st 1 setlinewidth np 452 1582 94 0.00 360.00 arc st 1 setlinewidth np 679 902 94 0.00 360.00 arc st 1 setlinewidth np 924 600 94 0.00 360.00 arc st 1 setlinewidth np 1340 902 94 0.00 360.00 arc st 1 setlinewidth np 566 1242 94 0.00 360.00 arc st 1 setlinewidth np 1207 393 94 0.00 360.00 arc st 1 setlinewidth np 868 1242 94 0.00 360.00 arc st 1 setlinewidth np 1056 902 94 0.00 360.00 arc st 1 setlinewidth np 1301 431 a 1414 525 li st 0 setgray 1 setlinewidth np 1386 512 a 1414 525 li 1396 500 li closepath fil 0 setgray np 1386 512 a 1414 525 li 1396 500 li closepath st 1 setlinewidth np 848 657 a 735 808 li st 0 setgray 1 setlinewidth np 747 779 a 735 808 li 759 789 li closepath fil 0 setgray np 747 779 a 735 808 li 759 789 li closepath st 1 setlinewidth np 980 676 a 1037 808 li st 0 setgray 1 setlinewidth np 1018 783 a 1037 808 li 1032 778 li closepath fil 0 setgray np 1018 783 a 1037 808 li 1032 778 li closepath st 1 setlinewidth np 1395 676 a 1358 808 li st 0 setgray 1 setlinewidth np 1359 777 a 1358 808 li 1373 781 li closepath fil 0 setgray np 1359 777 a 1358 808 li 1373 781 li closepath st 1 setlinewidth np 1490 695 a 1603 827 li st 0 setgray 1 setlinewidth np 1578 809 a 1603 827 li 1589 799 li closepath fil 0 setgray np 1578 809 a 1603 827 li 1589 799 li closepath st 1 setlinewidth np 621 978 a 584 1148 li st 0 setgray 1 setlinewidth np 583 1117 a 584 1148 li 597 1120 li closepath fil 0 setgray np 583 1117 a 584 1148 li 597 1120 li closepath st 1 setlinewidth np 1320 997 a 1301 1148 li st 0 setgray 1 setlinewidth np 1297 1117 a 1301 1148 li 1312 1119 li closepath fil 0 setgray np 1297 1117 a 1301 1148 li 1312 1119 li closepath st 1 setlinewidth np 1377 997 a 1490 1167 li st 0 setgray 1 setlinewidth np 1467 1146 a 1490 1167 li 1479 1138 li closepath fil 0 setgray np 1467 1146 a 1490 1167 li 1479 1138 li closepath st 1 setlinewidth np 603 1337 a 659 1488 li st 0 setgray 1 setlinewidth np 642 1462 a 659 1488 li 656 1457 li closepath fil 0 setgray np 642 1462 a 659 1488 li 656 1457 li closepath st 1 setlinewidth np 1112 431 a 980 525 li st 0 setgray 1 setlinewidth np 1000 501 a 980 525 li 1009 514 li closepath fil 0 setgray np 1000 501 a 980 525 li 1009 514 li closepath st 1 setlinewidth np 546 1337 a 470 1488 li st 0 setgray 1 setlinewidth np 477 1457 a 470 1488 li 491 1464 li closepath fil 0 setgray np 477 1457 a 470 1488 li 491 1464 li closepath st 1 setlinewidth np 735 978 a 829 1148 li st 0 setgray 1 setlinewidth np 808 1125 a 829 1148 li 821 1118 li closepath fil 0 setgray np 808 1125 a 829 1148 li 821 1118 li closepath st 1 setlinewidth np 565 1110 a 550 1116 li 537 1122 li 525 1128 li 513 1133 li 503 1138 li 493 1143 li 476 1152 li 462 1161 li 450 1169 li 433 1186 li st 1 setlinewidth np 433 1186 a 422 1200 li 411 1216 li 402 1234 li 396 1243 li 392 1253 li 387 1263 li 382 1274 li 378 1284 li 373 1295 li 369 1307 li 365 1318 li 361 1329 li 357 1340 li 353 1352 li 349 1364 li 346 1375 li 343 1386 li 340 1398 li 337 1409 li 334 1420 li 332 1431 li 329 1442 li 327 1452 li 325 1462 li 324 1472 li 321 1490 li 319 1507 li st 1 setlinewidth np 319 1507 a 319 1516 li 318 1527 li 318 1538 li 318 1550 li 318 1563 li 319 1576 li 320 1589 li 321 1603 li 323 1616 li 326 1629 li 329 1642 li 333 1654 li 338 1666 li 343 1677 li 357 1696 li st 1 setlinewidth np 357 1696 a 367 1705 li 379 1713 li 392 1721 li 405 1727 li 420 1733 li 435 1738 li 451 1742 li 467 1745 li 483 1748 li 499 1750 li 515 1751 li 531 1752 li 545 1753 li 559 1753 li 572 1753 li 584 1752 li st 1 setlinewidth np 584 1752 a 598 1751 li 613 1751 li 630 1749 li 648 1748 li 666 1745 li 685 1742 li 694 1741 li 704 1739 li 713 1737 li 723 1734 li 732 1732 li 742 1729 li 760 1723 li 778 1715 li 795 1706 li 810 1697 li 825 1685 li 837 1672 li 848 1658 li st 1 setlinewidth np 848 1658 a 854 1647 li 858 1636 li 861 1624 li 862 1611 li 862 1598 li 861 1585 li 859 1572 li 857 1559 li 854 1546 li 851 1533 li 847 1521 li 843 1509 li 839 1498 li 835 1487 li 829 1469 li st 1 setlinewidth np 829 1469 a 823 1452 li 816 1433 li 812 1424 li 807 1413 li 802 1403 li 798 1392 li 792 1381 li 787 1370 li 781 1358 li 775 1347 li 769 1335 li 763 1324 li 756 1312 li 750 1301 li 743 1289 li 736 1277 li 729 1266 li 723 1255 li 716 1244 li 709 1234 li 702 1223 li 695 1213 li 688 1203 li 681 1194 li 667 1177 li 653 1161 li 640 1148 li st 1 setlinewidth np 640 1148 a 630 1140 li 615 1132 li 606 1127 li 594 1122 li 580 1117 li 565 1110 li st 1 setlinewidth np 1320 789 a 1310 794 li 1300 798 li 1283 806 li 1268 813 li 1256 819 li 1238 833 li 1226 846 li st 1 setlinewidth np 1226 846 a 1217 861 li 1209 878 li 1202 897 li 1199 907 li 1196 917 li 1194 928 li 1191 938 li 1189 950 li 1187 961 li 1185 972 li 1183 983 li 1182 995 li 1180 1007 li 1179 1018 li 1178 1029 li 1177 1041 li 1176 1052 li 1175 1064 li 1175 1074 li 1174 1085 li 1173 1096 li 1173 1106 li 1172 1116 li 1171 1135 li 1170 1152 li 1169 1167 li st 1 setlinewidth np 1169 1167 a 1166 1185 li 1164 1196 li 1161 1208 li 1159 1220 li 1156 1232 li 1154 1245 li 1152 1258 li 1150 1272 li 1150 1285 li 1150 1298 li 1151 1311 li 1153 1323 li 1157 1335 li 1162 1346 li 1169 1356 li st 1 setlinewidth np 1169 1356 a 1181 1369 li 1194 1379 li 1210 1389 li 1226 1397 li 1243 1403 li 1261 1407 li 1279 1411 li 1298 1414 li 1317 1415 li 1336 1416 li 1354 1416 li 1372 1416 li 1389 1415 li 1405 1415 li 1420 1413 li 1433 1412 li st 1 setlinewidth np 1433 1412 a 1446 1412 li 1461 1410 li 1476 1409 li 1493 1407 li 1510 1405 li 1528 1402 li 1546 1398 li 1563 1394 li 1581 1388 li 1598 1382 li 1615 1375 li 1630 1366 li 1645 1356 li 1658 1345 li 1669 1332 li 1679 1318 li st 1 setlinewidth np 1679 1318 a 1685 1305 li 1689 1292 li 1691 1279 li 1691 1265 li 1690 1250 li 1688 1236 li 1685 1222 li 1681 1207 li 1677 1193 li 1671 1179 li 1666 1166 li 1661 1154 li 1655 1141 li 1650 1130 li 1645 1120 li 1641 1110 li st 1 setlinewidth np 1641 1110 a 1633 1094 li 1624 1076 li 1618 1066 li 1613 1056 li 1607 1046 li 1601 1036 li 1594 1025 li 1587 1015 li 1580 1004 li 1573 993 li 1565 982 li 1557 971 li 1550 960 li 1542 949 li 1534 938 li 1526 928 li 1517 917 li 1509 907 li 1501 897 li 1492 887 li 1484 877 li 1476 868 li 1460 850 li 1444 834 li 1429 820 li 1414 808 li st 1 setlinewidth np 1414 808 a 1406 802 li 1395 794 li 1383 785 li 1369 777 li 1356 771 li 1343 767 li 1331 767 li 1320 770 li st 1 setlinewidth np 1320 770 a 1317 777 li 1320 789 li st 1 setlinewidth np 1452 487 a 1440 492 li 1428 496 li 1418 500 li 1408 504 li 1391 512 li 1377 518 li 1364 525 li 1354 531 li 1339 544 li st 1 setlinewidth np 1339 544 a 1331 553 li 1324 563 li 1316 575 li 1309 587 li 1302 601 li 1296 615 li 1289 630 li 1283 645 li 1277 660 li 1271 675 li 1266 690 li 1261 704 li 1256 718 li 1252 730 li 1248 742 li 1245 752 li st 1 setlinewidth np 1245 752 a 1239 766 li 1233 784 li 1230 794 li 1226 803 li 1223 814 li 1219 825 li 1216 835 li 1214 846 li 1211 857 li 1209 867 li 1208 877 li 1206 886 li 1207 903 li st 1 setlinewidth np 1207 903 a 1209 916 li 1213 931 li 1218 947 li 1224 964 li 1233 980 li 1242 994 li 1252 1006 li 1263 1016 li st 1 setlinewidth np 1263 1016 a 1275 1023 li 1289 1029 li 1304 1033 li 1320 1037 li 1336 1039 li 1353 1040 li 1370 1041 li 1388 1042 li 1405 1041 li 1422 1041 li 1439 1040 li 1455 1039 li 1470 1037 li 1484 1036 li 1497 1035 li 1509 1035 li st 1 setlinewidth np 1509 1035 a 1520 1035 li 1533 1035 li 1548 1036 li 1563 1037 li 1579 1037 li 1596 1038 li 1614 1038 li 1631 1038 li 1649 1037 li 1666 1035 li 1683 1032 li 1699 1028 li 1715 1023 li 1729 1016 li 1743 1007 li 1754 997 li st 1 setlinewidth np 1754 997 a 1766 982 li 1773 963 li 1776 953 li 1778 943 li 1780 933 li 1780 922 li 1781 911 li 1780 901 li 1780 891 li 1779 881 li 1776 862 li 1773 846 li st 1 setlinewidth np 1773 846 a 1771 837 li 1768 827 li 1765 817 li 1761 807 li 1757 796 li 1752 785 li 1747 774 li 1742 763 li 1737 752 li 1731 741 li 1725 729 li 1718 718 li 1712 706 li 1705 695 li 1698 683 li 1690 672 li 1683 661 li 1675 649 li 1667 638 li 1660 628 li 1652 617 li 1644 607 li 1636 597 li 1628 587 li 1612 569 li 1596 552 li 1580 538 li 1566 525 li st 1 setlinewidth np 1566 525 a 1549 515 li 1539 511 li 1527 506 li 1512 502 li 1495 497 li 1486 495 li 1475 492 li 1464 490 li 1452 487 li st 1170 411 a(X1)905 619 y(X2)468 b(X3)547 1261 y(X6)1642 921 y(1)1264 1261 y(1)259 b(0)433 1601 y(1)222 b(0)679 1469 y(3)16 b(,)g(1)-377 b(3)16 b(,)g(1)509 1110 y(6)h(,)e(4)679 751 y(9)h(,)g(7)1056 770 y(3)h(,)f(3)943 468 y(12)h(,)f(10)291 b(8)17 b(,)f(10)1283 770 y(5)h(,)e(4)1585 789 y(3)i(,)e(6)1226 1110 y(2)i(,)f(3)1510 1129 y(3)g(,)g(1)868 1261 y(0)849 1110 y(3)g(,)g(3)698 1790 y(0)g(:)22 b(1)698 1846 y(1)16 b(:)22 b(3)1245 1469 y(0)17 b(:)k(0)1245 1525 y(1)c(:)k(2)1528 1469 y(1)c(:)k(2)1528 1525 y(0)c(:)k(1)1679 1091 y(0)c(:)k(1)1679 1148 y(1)c(:)k(2)396 1790 y(0)16 b(:)22 b(1)396 1846 y(1)16 b(:)22 b(2)1056 921 y(1)241 b(X4)-741 b(X5)75 1957 y(Figure)16 b(10.1:)21 b(An)15 b(initial)i(decision)f(tree)f Fo(T)p Fn(,)g(ab)q(out)h(to)f(b)q(e)g (pruned.)21 b(The)15 b(n)o(um)o(b)q(ers)g(next)f(to)i(eac)o(h)e(edge)75 2017 y(are)j(the)g(n)o(um)o(b)q(er)f(of)h(examples)g(that)h(reac)o(h)e (the)h(edge)g(when)g(classi\014ed)i(using)f Fo(T)p Fn(.)24 b(\(The)17 b(left)g(n)o(um)o(b)q(er)75 2078 y(is)h(the)f(coun)o(t)g(in) h(the)f(training)i(set,)e(and)h(the)f(righ)o(t)h(n)o(um)o(b)q(er)f(is)h (the)f(coun)o(t)g(in)h(the)f(test)g(set.\))24 b(The)17 b Fk(X)2010 2085 y Fh(i)75 2138 y Fn(v)m(ariable)f(in)e(eac)o(h)f(in)o (ternal)i(no)q(de)g(is)g(the)e(attribute)i(examined)e(while)i(making)g (a)f(decision)i(in)e(the)g(no)q(de,)75 2198 y(and)j(the)f(n)o(um)o(b)q (er)f(in)i(eac)o(h)f(leaf)h(is)g(the)f(classi\014cation)j(made)d(for)g (examples)h(reac)o(hing)f(the)g(leaf.)p eop %%Page: 4 4 4 3 bop 0 -31 a Fn(4)1404 b Fj(Lecture)16 b(9:)21 b(Ma)o(y)16 b(21,)g(1997)p 1 setlinewidth np 645 747 94 0.00 360.00 arc st 1 setlinewidth np 890 445 94 0.00 360.00 arc st 1 setlinewidth np 1022 747 94 0.00 360.00 arc st 1 setlinewidth np 531 1087 94 0.00 360.00 arc st 1 setlinewidth np 1173 238 94 0.00 360.00 arc st 1 setlinewidth np 1419 445 94 0.00 360.00 arc st 1 setlinewidth np 833 1087 94 0.00 360.00 arc st 1 setlinewidth np 1267 275 a 1380 370 li st 0 setgray 1 setlinewidth np 1353 356 a 1380 370 li 1362 344 li closepath fil 0 setgray np 1353 356 a 1380 370 li 1362 344 li closepath st 1 setlinewidth np 814 502 a 701 653 li st 0 setgray 1 setlinewidth np 713 624 a 701 653 li 725 633 li closepath fil 0 setgray np 713 624 a 701 653 li 725 633 li closepath st 1 setlinewidth np 946 521 a 1003 653 li st 0 setgray 1 setlinewidth np 984 628 a 1003 653 li 998 622 li closepath fil 0 setgray np 984 628 a 1003 653 li 998 622 li closepath st 1 setlinewidth np 588 823 a 550 993 li st 0 setgray 1 setlinewidth np 549 961 a 550 993 li 564 965 li closepath fil 0 setgray np 549 961 a 550 993 li 564 965 li closepath st 1 setlinewidth np 1078 275 a 946 370 li st 0 setgray 1 setlinewidth np 966 346 a 946 370 li 975 358 li closepath fil 0 setgray np 966 346 a 946 370 li 975 358 li closepath st 1 setlinewidth np 701 823 a 795 993 li st 0 setgray 1 setlinewidth np 774 970 a 795 993 li 787 963 li closepath fil 0 setgray np 774 970 a 795 993 li 787 963 li closepath st 1135 257 a Fn(X1)871 464 y(X2)833 1106 y(0)1419 464 y(1)1022 766 y(1)531 1106 y(1)607 766 y(X5)471 1288 y(Figure)h(10.2:)22 b(The)16 b(resulting)i(pruned)e(decision)i(tree)p 1 setlinewidth np 955 1779 126 277.12 389.74 arc st 0 setgray 1 setlinewidth np 1002 1649 a 971 1653 li 1000 1664 li 992 1655 li closepath fil 0 setgray np 1002 1649 a 971 1653 li 1000 1664 li 992 1655 li closepath st 1 setlinewidth np 914 1691 59 0.00 360.00 arc st 1 setlinewidth np 782 1880 59 0.00 360.00 arc st 1 setlinewidth np 1009 1880 59 0.00 360.00 arc st 1 setlinewidth np 877 1747 a 820 1823 li st 1 setlinewidth np 832 1794 a 820 1823 li 844 1803 li st 1 setlinewidth np 952 1747 a 990 1823 li st 1 setlinewidth np 970 1799 a 990 1823 li 983 1792 li st 1 setlinewidth np 952 1521 a 933 1634 li st 0 setgray 1 setlinewidth np 931 1603 a 933 1634 li 946 1606 li 937 1613 li closepath fil 0 setgray np 931 1603 a 933 1634 li 946 1606 li 937 1613 li closepath st 1 setlinewidth np 782 1785 a 772 1792 li 762 1798 li 745 1810 li 730 1820 li 718 1829 li 700 1846 li 688 1861 li st 1 setlinewidth np 688 1861 a 679 1874 li 670 1889 li 661 1905 li 652 1922 li 643 1941 li 638 1950 li 634 1960 li 630 1970 li 626 1980 li 622 1990 li 618 2000 li 615 2011 li 612 2021 li 609 2032 li 606 2042 li 604 2053 li 603 2063 li 601 2074 li 600 2084 li 600 2094 li 600 2104 li 601 2115 li 602 2125 li 603 2134 li 606 2144 li 612 2163 li st 1 setlinewidth np 612 2163 a 622 2179 li 636 2193 li 653 2205 li 671 2215 li 681 2220 li 691 2224 li 701 2227 li 710 2230 li 728 2235 li 744 2238 li st 1 setlinewidth np 744 2238 a 760 2241 li 779 2244 li 789 2245 li 799 2245 li 810 2245 li 820 2245 li 831 2245 li 842 2243 li 852 2242 li 862 2239 li 880 2231 li 896 2219 li st 1 setlinewidth np 896 2219 a 907 2204 li 914 2185 li 917 2175 li 918 2165 li 919 2154 li 920 2143 li 920 2133 li 919 2122 li 918 2112 li 917 2102 li 916 2083 li 914 2068 li st 1 setlinewidth np 914 2068 a 912 2053 li 909 2034 li 907 2024 li 904 2013 li 902 2002 li 899 1992 li 896 1981 li 893 1970 li 890 1960 li 887 1950 li 881 1932 li 877 1917 li st 1 setlinewidth np 877 1917 a 874 1908 li 870 1896 li 866 1883 li 861 1869 li 856 1855 li 851 1843 li 845 1832 li 839 1823 li st 1 setlinewidth np 839 1823 a 820 1807 li 804 1797 li 794 1792 li 782 1785 li st 1 setlinewidth np 990 1785 a 973 1794 li 959 1802 li 947 1809 li 938 1816 li 923 1828 li 914 1842 li st 1 setlinewidth np 914 1842 a 911 1852 li 909 1864 li 908 1876 li 909 1890 li 910 1903 li 912 1915 li 913 1927 li 914 1936 li st 1 setlinewidth np 914 1936 a 915 1945 li 917 1957 li 920 1970 li 923 1984 li 925 1997 li 928 2010 li 931 2021 li 933 2030 li st 1 setlinewidth np 933 2030 a 937 2048 li 939 2058 li 941 2069 li 943 2080 li 945 2092 li 948 2104 li 951 2117 li 954 2129 li 958 2141 li 962 2153 li 966 2164 li 971 2175 li 977 2184 li 990 2200 li st 1 setlinewidth np 990 2200 a 1004 2211 li 1022 2221 li 1031 2224 li 1041 2228 li 1052 2231 li 1062 2233 li 1073 2236 li 1084 2237 li 1094 2239 li 1104 2239 li 1114 2240 li 1124 2240 li 1141 2238 li st 1 setlinewidth np 1141 2238 a 1154 2236 li 1168 2233 li 1183 2230 li 1198 2226 li 1214 2221 li 1230 2216 li 1246 2210 li 1261 2203 li 1277 2194 li 1291 2185 li 1304 2175 li 1316 2164 li 1327 2151 li 1336 2138 li 1343 2122 li 1349 2106 li st 1 setlinewidth np 1349 2106 a 1351 2091 li 1351 2076 li 1349 2061 li 1344 2047 li 1338 2033 li 1331 2020 li 1322 2007 li 1313 1995 li 1303 1983 li 1292 1972 li 1282 1961 li 1271 1951 li 1261 1942 li 1252 1933 li 1235 1917 li st 1 setlinewidth np 1235 1917 a 1217 1900 li 1206 1891 li 1193 1881 li 1181 1871 li 1167 1861 li 1153 1851 li 1138 1841 li 1123 1832 li 1108 1823 li 1094 1815 li 1079 1807 li 1065 1800 li 1052 1794 li 1039 1789 li 1028 1785 li st 1 setlinewidth np 1028 1785 a 1014 1783 li 1004 1784 li 990 1785 li st 570 2353 a(Figure)f(10.3:)22 b(Another)16 b(pruning)i(metho)q(d)p eop %%Page: 5 5 5 4 bop 75 -31 a Fj(10.3.)38 b(STR)o(UCTURAL)16 b(RISK)g(MINIMIZA)l(TI) o(ON)922 b Fn(5)75 101 y(Once)15 b(w)o(e)f(solv)o(e)i(the)f(latter)h (problem)f(it)h(is)g(only)g(a)g(matter)f(of)g(rev)o(ersing)g(a)h(table) g(to)f(solv)o(e)h(the)f(former.)148 162 y(Giv)o(en)g Fk(e)p Fn(,)f(the)g(n)o(um)o(b)q(er)g(of)h(errors,)g(w)o(e)f(w)o(an)o (t)h(to)g(\014nd)g(the)f(smallest)i(pruned)f(v)o(ersion)g(of)g Fl(T)21 b Fn(that)15 b(has)75 222 y(at)j(most)g Fk(e)g Fn(errors.)26 b(W)l(e)18 b(giv)o(e)g(a)g(recursiv)o(e)f(algorithm)j (with)f(exp)q(onen)o(tial)g(complexit)o(y)l(.)26 b(W)l(e)18 b(use)g Fo(T)p Fn([0])75 283 y(and)e Fo(T)p Fn([1])g(to)g(represen)o(t) f(the)h(left)g(and)g(righ)o(t)h(c)o(hild)f(subtrees)g(of)g Fo(T)g Fn(resp)q(ectiv)o(ely)l(.)21 b(ro)q(ot\()p Fo(T)p Fn(\))c(is)f(the)g(ro)q(ot)75 343 y(no)q(de)j(of)g(the)f(tree)g Fo(T)p Fn(.)28 b(W)l(e)18 b(also)i(de\014ne)e Fo(mak)n(etree)p Fn(\()p Fk(r)o(;)8 b Fo(T)1175 350 y Fg(0)1196 343 y Fk(;)g Fo(T)1257 350 y Fg(1)1279 343 y Fn(\))18 b(to)h(b)q(e)g(the)f (tree)g(formed)g(b)o(y)g(making)75 403 y(the)f(subtrees)g Fo(T)390 410 y Fg(0)430 403 y Fn(and)h Fo(T)565 410 y Fg(1)604 403 y Fn(the)f(left)h(and)f(righ)o(t)h(c)o(hild)g(of)g(the)f (ro)q(ot)h(no)q(de)g Fk(r)q Fn(.)24 b(F)l(or)18 b(ev)o(ery)d(no)q(de)j Fk(v)h Fn(of)e Fo(T)p Fn(,)75 463 y Fo(Errors)p Fn(\()p Fk(v)r Fn(\))e(is)i(the)f(n)o(um)o(b)q(er)g(of)g(classi\014cation)j (errors)e(on)f(the)g(sample)h(set)f(of)h Fk(v)h Fn(as)f(a)f(leaf.)75 584 y Fo(compute)p Fn(\()f(input)34 b(:)21 b Fk(k)r Fn(:n)o(umOfErrs,)p Fo(T)p Fn(:tree,)319 644 y(output)c(:)22 b Fk(s)p Fn(:treeSize,)p Fo(P)p Fn(:prunedT)l(ree\))319 704 y(If)16 b Fo(IsLeaf)p Fn(\()p Fo(T)p Fn(\))368 764 y(If)g Fo(Errors)p Fn(\()p Fo(T)p Fn(\))g Ff(\024)d Fk(k)417 825 y(s)h Fn(=)g(1)368 885 y(Else)417 945 y Fk(s)g Fn(=in\014nit)o(y)368 1005 y Fo(P)g Fn(=)g Fo(T)368 1065 y Fn(return)319 1126 y(If)i Fo(Errors)p Fn(\(ro)q(ot\()p Fo(T)p Fn(\)\))h Ff(\024)d Fk(k)368 1186 y(s)g Fn(=)g(1)368 1246 y Fo(P)g Fn(=)j(ro)q(ot\()p Fo(T)p Fn(\))368 1306 y(return)319 1366 y(F)l(or)g Fk(i)c Fn(=)h(1)8 b Fk(:)g(:)g(:)g(k)368 1427 y Fn(Call)18 b Fo(compute)p Fn(\()p Fk(i)p Fn(,)p Fo(T)p Fn([0],)p Fk(s)859 1409 y Fi(0)859 1439 y Fh(i)876 1427 y Fn(,)p Fo(P)928 1409 y Fi(0)928 1439 y Fh(i)948 1427 y Fn(\))368 1487 y(Call)g Fo(compute)p Fn(\()p Fk(k)13 b Ff(\000)d Fk(i)p Fn(,)p Fo(T)p Fn([1],)p Fk(s)946 1469 y Fi(1)946 1499 y Fh(i)964 1487 y Fn(,)p Fo(P)1016 1469 y Fi(1)1016 1499 y Fh(i)1036 1487 y Fn(\))319 1547 y Fk(I)20 b Fn(=)c(arg)h(min)581 1554 y Fh(i)595 1547 y Ff(f)p Fk(s)643 1529 y Fi(0)643 1559 y Fh(i)673 1547 y Fn(+)11 b Fk(s)745 1529 y Fi(1)745 1559 y Fh(i)765 1547 y Ff(g)319 1607 y Fk(s)j Fn(=)g Fk(s)431 1589 y Fi(0)431 1619 y Fh(I)462 1607 y Fn(+)d Fk(s)534 1589 y Fi(1)534 1619 y Fh(I)565 1607 y Fn(+)g(1)319 1667 y Fo(P)k Fn(=)h Fo(mak)n(etree)p Fn(\(ro)q(ot\()p Fo(T)p Fn(\),)p Fo(P)886 1649 y Fi(0)886 1680 y Fh(I)905 1667 y Fn(,)p Fo(P)957 1649 y Fi(1)957 1680 y Fh(I)977 1667 y Fn(\))148 1848 y(The)h(exp)q(onen)o(tial)h(complexit)o(y)e(of)h (the)g(algorithm)h(can)f(b)q(e)g(reduced)f(b)o(y)g(implemen)o(ting)i (the)e(same)75 1908 y(idea)e(in)h(a)f(di\013eren)o(t)g(w)o(a)o(y)l(.)20 b(Note)13 b(that)h(w)o(e)g(can)g(compute)f(all)i(the)f(v)m(alues)g(for) g(a)g(no)q(de)h(if)f(w)o(e)f(kno)o(w)h(all)h(the)75 1968 y(v)m(alues)h(for)g(its)g(t)o(w)o(o)f(c)o(hild)h(subtrees.)21 b(The)15 b(basic)h(idea)g(is)g(therefore)f(to)h(do)f(the)h(computation) g(from)f(the)75 2028 y(lea)o(v)o(es)f(up)h(to)o(w)o(ards)h(the)e(ro)q (ot)i(of)f(the)g(tree.)20 b(If)14 b(w)o(e)g(ha)o(v)o(e)g(all)j(the)d (computations)i(done)f(for)h(the)e(subtrees)75 2088 y Fo(T)114 2095 y Fg(0)151 2088 y Fn(and)i Fo(T)284 2095 y Fg(1)321 2088 y Fn(\(W)l(e)f(ha)o(v)o(e)f(computed)h Fk(s)781 2095 y Fh(i)810 2088 y Fn(and)g(the)g(suitable)i(tree)d Fo(P)1301 2095 y Fg(i)1329 2088 y Fn(for)i(ev)o(ery)d Fk(i)h Fn(=)f(1)8 b Fk(:)g(:)g(:)h(k)r Fn(\))15 b(then)f(w)o(e)h(can)75 2148 y(compute)h(for)g Fo(T)h Fn(b)o(y)e(scanning)j(the)e(already)h (computed)f(v)m(alues)h Fk(k)i Fn(times)d(\()p Fk(i)d Fn(=)h(1)8 b Fk(:)g(:)g(:)g(k)r Fn(\):)75 2269 y Fk(I)52 b Fn(=)14 b Fk(ar)q(g)c Fn(min)365 2276 y Fh(i)379 2269 y Ff(f)p Fk(s)427 2251 y Fi(0)427 2282 y Fh(i)457 2269 y Fn(+)h Fk(s)529 2251 y Fi(1)529 2282 y Fh(k)q Fe(\000)p Fh(i)590 2269 y Ff(g)16 b Fn(##)g(this)h(tak)o(es)f(O\()p Fk(k)r Fn(\))75 2329 y Fk(s)98 2336 y Fh(i)133 2329 y Fn(=)e Fk(s)208 2311 y Fi(0)208 2342 y Fh(I)239 2329 y Fn(+)d Fk(s)311 2311 y Fi(1)311 2342 y Fh(I)342 2329 y Fn(+)g(1)216 b(##)16 b(this)h(tak)o(es)f(constan)o(t)h(time)75 2390 y Fo(P)113 2397 y Fh(i)133 2390 y Fn(=)f Fo(mak)n(etree)p Fn(\(ro)q(ot\()p Fo(T)p Fn(\),)f Fo(P)662 2372 y Fi(0)662 2402 y Fh(I)682 2390 y Fn(,)p Fo(P)734 2372 y Fi(1)734 2402 y Fh(I)754 2390 y Fn(\))i(##)e(this)i(tak)o(es)f(constan)o(t)h (time)p eop %%Page: 6 6 6 5 bop 0 -31 a Fn(6)1404 b Fj(Lecture)16 b(9:)21 b(Ma)o(y)16 b(21,)g(1997)73 101 y Fn(W)l(e)21 b(also)i(ha)o(v)o(e)d(to)i (initialize)h(all)g(the)e(v)m(alues)h(in)g(the)f(lea)o(v)o(es)g(of)g Fo(T)p Fn(.)36 b(T)l(o)22 b(do)g(that)f(w)o(e)g(m)o(ust)g(\014nd)0 161 y(for)e(ev)o(ery)f(leaf)i(the)e(exact)h(n)o(um)o(b)q(er)f(of)i (errors)f(o)o(v)o(er)f(the)h(sample)h(set)f(\(if)g(w)o(e)g(ha)o(v)o(e)f Fk(l)i Fn(errors)f(in)h(a)f(leaf)0 222 y(then)j(w)o(e)g(set)h Fk(s)301 229 y Fh(l)338 222 y Fn(=)h(1)f(and)g(all)h(other)f Fk(s)779 229 y Fh(i)815 222 y Fn(to)g(in\014nit)o(y\).)41 b(The)22 b(total)i(time)e(complexit)o(y)g(is)i(therefore)0 282 y Fk(O)q Fn(\()p Fk(k)84 264 y Fi(2)117 282 y Ff(\003)13 b Fk(s)p Fn(\))f(+)h Fk(O)q Fn(\()p Fk(m)g Ff(\003)f Fk(depth)p Fn(\()p Fo(T)p Fn(\)\))19 b(where)f Fk(s)h Fn(is)g(the)g(size)f(of)h Fo(T)g Fn(and)g Fk(m)f Fn(is)i(the)e(size)h (of)g(the)f(sample)i(set.)0 342 y(Since)c Fk(k)g Fn(=)e Fk(O)q Fn(\()p Fk(m)p Fn(\))i(w)o(e)g(ha)o(v)o(e)g(total)h(time)f (complexit)o(y)g Fk(O)q Fn(\()p Fk(m)1115 324 y Fi(2)1146 342 y Ff(\003)11 b Fk(s)p Fn(\).)73 404 y(No)o(w)h(that)g(w)o(e)g(ha)o (v)o(e)f(a)i(w)o(a)o(y)e(to)i(compute)e(for)i(ev)o(ery)d Fk(k)k Fn(the)e(b)q(est)g(decision)i(tree)d Fl(T)1560 411 y Fh(k)1593 404 y Fn(of)i(size)f Fk(k)r Fn(,)g(w)o(e)g(ha)o(v)o(e)0 464 y(to)j(c)o(ho)q(ose)h(one)f(of)g(them)g(as)g(the)g(b)q(est)g(h)o (yp)q(othesis.)22 b(It)15 b(is)h(actually)g(a)f(question)h(of)g(Mo)q (del)f(Selection)h(\()p Fk(k)0 524 y Fn(b)q(eing)g(the)f(mo)q(del)h (size\),)e(and)i(w)o(e)f(can)g(use)g(the)f(metho)q(d)i(of)f(Structural) h(Risk)f(Minimization)i(that)f(w)o(as)0 584 y(discussed)h(in)g(the)g (previous)g(lecture.)k(As)c(the)f(V)o(C-dimension)h Fk(d)g Fn(of)g(the)f(class)i(of)e(decision)i(trees)e(with)0 644 y Fk(k)i Fn(no)q(des)f(is)g(at)g(least)g Fk(k)h Fn(\(H.W.)d(3\))i (w)o(e)f(can)g(c)o(ho)q(ose)h(according)h(to)e(the)g(follo)o(wing)j (rule:)656 801 y Fk(T)685 808 y Fe(\003)718 801 y Fn(=)14 b Fk(ar)q(g)c Fn(min)884 831 y Fh(d)934 801 y Ff(f)p Fk(er)q(r)q Fn(\()p Fk(T)1076 808 y Fh(d)1096 801 y Fn(\))h(+)1175 719 y Fd(s)p 1216 719 53 2 v 1229 767 a Fk(k)p 1221 790 43 2 v 1221 835 a(m)1269 801 y Ff(g)73 937 y Fn(As)j(men)o(tioned)f(b)q (efore,)h(w)o(e)f(can)h(also)i(use)d(Cross)i(V)l(alidation)h(to)f(test) e(eac)o(h)g Fl(T)1524 944 y Fh(k)1559 937 y Fn(on)i(an)f(indep)q(enden) o(t)0 997 y(test)20 b(set)g(\(not)g(the)f(one)i(used)f(to)g(build)h (the)f(decision)h(trees\))e(and)i(c)o(ho)q(ose)f(among)h(the)f(set)f (of)i('b)q(est')0 1058 y(trees)16 b(the)g(tree)f(with)i(the)f(least)i (n)o(um)o(b)q(er)d(of)i(errors.)0 1234 y Fm(10.4)82 b(P)n(essimistic)25 b(Pruning)0 1347 y Fn(W)l(e)18 b(no)o(w)h(presen)o(t)f(a)g(pruning)i (metho)q(d)f(that)g(do)q(es)g(not)g(require)f(a)g(separate)h(test)f (set)h(nor)g(high)g(time)0 1407 y(complexit)o(y)l(.)h(The)15 b(idea)g(is)g(to)f(mak)o(e)g(a)h(single)g(pass)h(from)e(the)g(lea)o(v)o (es)g(of)h(the)f(decision)h(tree)f(up)g(to)o(w)o(ards)0 1467 y(the)g(ro)q(ot,)i(and)f(at)g(ev)o(ery)f(in)o(ternal)h(no)q(de)h (mak)o(e)d(a)j(decision)g(w)o(ether)e(to)h(prune)f(or)h(not.)22 b(The)14 b(decision)i(is)0 1528 y(based)g(on)h(a)f(comparison)h(of)f (the)g(error)f(at)h(the)g(no)q(de)g(\(if)h(pruned\))e(to)h(the)g(error) g(of)g(the)f(no)q(de)i(subtree.)0 1588 y(Since)f(the)g(true)g(error)h (can)f(only)h(b)q(e)f(appro)o(ximated)h(w)o(e)f(mak)o(e)f(a)i(p)q (essimistic)h(appro)o(ximation.)73 1650 y(Let)g Fk(H)202 1657 y Fh(k)242 1650 y Fn(b)q(e)g(the)g(set)g(of)h(all)g(decision)h (trees)d(with)i(at)g(most)f Fk(k)i Fn(no)q(des.)28 b(F)l(or)18 b(an)o(y)g(b)q(o)q(olean)i(function)0 1710 y Fk(f)25 b Fn(and)20 b Fk(h)f Ff(2)g Fk(H)286 1717 y Fh(k)327 1710 y Fn(De\014ne)g Fk(e)p Fn(\()p Fk(f)s(;)8 b(h)p Fn(\))19 b(to)g(b)q(e)h(the)f(true)g(classi\014cation)j(error)d(and)j (^)-26 b Fk(e)p Fn(\()p Fk(f)s(;)8 b(h)p Fn(\))19 b(b)q(e)g(the)g (error)g(as)0 1770 y(measured)d(on)h(the)f(giv)o(en)g(sample)h(set.)73 1832 y(W)l(e)f(sho)o(w)g(no)o(w)h(an)f(upp)q(er)g(b)q(ound)h(on)g(the)e (probabilit)o(y)j(that)f(there)e(is)i(some)e Fk(h)f Ff(2)g Fk(H)1664 1839 y Fh(k)1702 1832 y Fn(with)j Fk(e)p Fn(\()p Fk(f)s(;)8 b(h)p Fn(\))0 1892 y(signi\014can)o(tly)18 b(di\013eren)o(t)f(from)h(^)-26 b Fk(e)o Fn(\()p Fk(f)s(;)8 b(h)p Fn(\).)145 2069 y Fk(P)f(r)q Fn([)p Ff(9)p Fk(h)14 b Ff(2)g Fk(H)377 2076 y Fh(k)431 2069 y Fk(s:t:)31 b Ff(j)p Fk(e)p Fn(\()p Fk(f)s(;)8 b(h)p Fn(\))i Ff(\000)j Fn(^)-26 b Fk(e)p Fn(\()p Fk(f)s(;)8 b(h)p Fn(\))p Ff(j)13 b Fk(>)h Fn(\000)990 2076 y Fh(k)1011 2069 y Fn(])41 b Ff(\024)h(j)p Fk(H)1201 2076 y Fh(k)1222 2069 y Ff(j)p Fk(P)7 b(r)q Fn([)p Ff(j)p Fk(e)p Fn(\()p Fk(f)s(;)h(h)p Fn(\))i Ff(\000)j Fn(^)-26 b Fk(e)p Fn(\()p Fk(f)s(;)8 b(h)p Fn(\))p Ff(j)13 b Fk(>)h Fn(\000)1770 2076 y Fh(k)1791 2069 y Fn(])1066 2154 y Ff(\024)42 b Fn(2)p Ff(j)p Fk(H)1225 2161 y Fh(k)1247 2154 y Ff(j)p Fk(e)1284 2134 y Fe(\000)p Fi(2\000)1351 2122 y Fc(2)1351 2146 y Fb(k)1369 2134 y Fh(n)1407 2125 y(def)1415 2154 y Fn(=)23 b Fk(\016)73 2271 y Fn(Where)16 b(the)g(last)h(inequalit)o(y)h(is)f(Cherno\013)g(b)q (ound,)g(and)g Fk(n)f Fn(is)h(the)f(size)g(of)h(the)f(sample)h(set.)73 2333 y(W)l(e)f(ha)o(v)o(e)741 2431 y(\000)771 2438 y Fh(k)807 2431 y Fn(=)858 2345 y Fd(s)p 900 2345 310 2 v 905 2396 a Fn(ln)9 b(2)p Ff(j)p Fk(H)1032 2403 y Fh(k)1054 2396 y Ff(j)i Fn(+)g(ln)1182 2376 y Fi(1)p 1182 2384 18 2 v 1182 2413 a Fh(\016)p 905 2420 300 2 v 1028 2465 a Fn(2)p Fk(n)p eop %%Page: 7 7 7 6 bop 75 -31 a Fj(10.4.)38 b(PESSIMISTIC)16 b(PR)o(UNING)1221 b Fn(7)148 101 y(The)17 b(ab)q(o)o(v)o(e)f(lemma)h(implies)g(that)g (for)g(an)o(y)f(decision)i(tree)e(with)h Fk(k)i Fn(no)q(des,)e(with)g (high)h(probabilit)o(y)75 161 y(the)e(true)g(error)g(is)h(\000)460 168 y Fh(k)482 161 y Fn(-close)g(to)g(the)f(observ)o(ed)g(error.)148 225 y(W)l(e)h(no)o(w)g(pro)q(ceed)g(to)g(b)q(ound)h Ff(j)p Fk(H)781 232 y Fh(k)803 225 y Ff(j)p Fn(,)e(This)i(will)h(let)e(us)h (get)f(a)g(b)q(ound)h(on)f(\000)1559 232 y Fh(k)1581 225 y Fn(.)23 b(Let)18 b Fk(k)f Fn(=)d(2)p Fk(k)1852 207 y Fi(`)1876 225 y Fn(+)e(1)17 b(\()p Fk(k)2013 207 y Fi(`)75 286 y Fn(in)o(ternal)j(no)q(des)h(and)f Fk(k)524 268 y Fi(`)549 286 y Fn(+)13 b(1)20 b(lea)o(v)o(es\).)31 b(Ignoring)21 b(the)e(lab)q(eling)j(of)e(lea)o(v)o(es)f(and)h(in)o (ternal)g(no)q(des,)h(it)f(is)75 346 y(easy)e(to)g(see)f(that)h(there)f (are)g(at)h(most)g(2)846 328 y Fh(k)886 346 y Fn(di\013eren)o(t)f (decision)i(trees.)25 b(\(This)19 b(is)f(b)q(ecause)g(w)o(e)f(can)h (map)75 406 y(an)o(y)i(suc)o(h)f(decision)i(tree)e(to)h(a)h(v)o(ector)e (of)h Fk(k)h Fn(bits)g(in)f(BFS)g(order,)g(represen)o(ting)g(the)f(in)o (ternal)i(no)q(des)75 466 y(b)o(y)16 b(0)h(and)g(lea)o(v)o(es)f(b)o(y)h (1\).)22 b(There)17 b(are)f(at)h(most)g Fk(d)995 448 y Fh(k)1014 436 y Fc(`)1044 466 y Fn(di\013eren)o(t)g(lab)q(elings)i (for)e(in)o(ternal)h(no)q(des)f(\(W)l(e)g(ma)o(y)75 526 y(c)o(ho)q(ose)g(an)o(y)f(of)h(the)f Fk(d)h Fn(attributes)h Fk(x)758 533 y Fi(1)785 526 y Fk(:)8 b(:)g(:)g(x)879 533 y Fh(d)915 526 y Fn(to)17 b(b)q(e)g(tested)f(at)h(an)o(y)f(in)o (ternal)i(no)q(de\),)e(and)h(2)1788 508 y Fh(k)1807 497 y Fc(`)1819 508 y Fi(+1)1883 526 y Fn(for)f(the)75 587 y(lea)o(v)o(es.)21 b(W)l(e)16 b(conclude)g(with)h(the)f(required)g(b)q (ound)873 709 y Ff(j)p Fk(H)927 716 y Fh(k)949 709 y Ff(j)d Fn(=)h Fk(O)q Fn(\(\(4)p Fk(d)p Fn(\))1172 688 y Fh(k)1195 709 y Fn(\))p Fk(:)148 834 y Fn(Let)i Fk(n)264 841 y Fh(v)300 834 y Fn(b)q(e)f(the)g(n)o(um)o(b)q(er)g(of)h(examples)f (that)h(arriv)o(e)f(to)h(no)q(de)g Fk(v)r Fn(.)k(Let)c Fk(s)f Fn(b)q(e)h(the)f(size)g(of)h(the)f(subtree)75 895 y(ro)q(oted)g(at)f Fk(v)r Fn(.)19 b(Let)14 b Fk(e)450 902 y Fi(1)483 895 y Fn(b)q(e)g(the)f(n)o(um)o(b)q(er)g(of)h(errors)g (at)g(the)g(subtree,)f(and)i(let)f Fk(e)1497 902 y Fi(2)1530 895 y Fn(b)q(e)f(the)h(n)o(um)o(b)q(er)f(of)h(errors)75 955 y(if)k Fk(v)i Fn(is)e(replaced)g(b)o(y)g(a)g(leaf.)27 b(By)17 b(the)h(ab)q(o)o(v)o(e)f(b)q(ound,)i(with)g(high)g(probabilit)o (y)l(,)h(the)e(true)f(error)h(of)g(the)75 1015 y(subtree)d(is)h(at)f (most)478 995 y Fh(e)494 1000 y Fc(1)p 475 1003 40 2 v 475 1032 a Fh(n)496 1036 y Fb(v)528 1015 y Fn(+)9 b(\000)605 1022 y Fh(k)627 1015 y Fn(.)21 b(\(This)16 b(is)g(actually)g(a)g(p)q (essimistic)h(estimation)g(of)e(the)g(true)g(error)g(of)g(the)75 1075 y(subtree,)i(hence)f(the)h(algorithm)i(name\).)24 b(W)l(e)17 b(will)i(decide)e(to)g(prune)h(only)g(if)f(the)g(estimated)h (error)f(of)75 1135 y Fk(v)r Fn(,)e(if)i(replaced)f(b)o(y)g(a)h(leaf,)f (is)h(smaller)g(than)g(the)f(p)q(essimistic)i(estimated)f(error)f(of)g (the)g(subtree:)912 1237 y Fk(e)935 1244 y Fi(2)p 908 1259 50 2 v 908 1305 a Fk(n)937 1312 y Fh(v)977 1271 y Fk(<)1037 1237 y(e)1060 1244 y Fi(1)p 1033 1259 V 1033 1305 a Fk(n)1062 1312 y Fh(v)1099 1271 y Fn(+)11 b(\000)1178 1278 y Fh(s)148 1417 y Fn(The)16 b(follo)o(wing)j(claims)f(justify)e (the)g(ab)q(o)o(v)o(e)h(rule.)75 1563 y Fo(Claim)j(10.1)k Fl(When)16 b(we)g(de)n(cide)g(NOT)g(to)g(prune)g(in)g(the)g(internal)g (no)n(de)g Fk(v)r Fl(,)f(with)h(high)g(pr)n(ob)n(ability)e(the)75 1623 y(err)n(or)i(of)h(the)h(subtr)n(e)n(e)g(r)n(o)n(ote)n(d)d(at)j Fk(v)h Fl(is)e(smal)r(ler)i(than)e(the)h(err)n(or)e(at)i Fk(v)h Fl(as)e(a)g(le)n(af.)75 1765 y Fo(Claim)j(10.2)k Fl(When)15 b(we)g(de)n(cide)g(to)f(prune)h(a)f(subtr)n(e)n(e)g(of)g (size)g Fk(k)r Fl(,)h(the)g(total)g(err)n(or)e(of)h(the)g(tr)n(e)n(e)g (incr)n(e)n(ases)75 1826 y(at)k(most)f(by)g Fn(\000)345 1833 y Fh(k)75 1968 y Fn(Note)c(that)h(all)h(suc)o(h)e(errors)h(o)q (ccur)f(at)h(indep)q(enden)o(t)g(no)q(des,)g(therefore)f(the)g(total)i (increase)f(in)g(the)f(error)75 2028 y(of)k(the)f(tree)f(is)i(an)g(a)o (v)o(erage)f(of)g(those)h(increases)g(and)f(is)h(therefore)f(b)q (ounded)h(b)o(y)f(\000)1636 2035 y Fh(k)1674 2028 y Fn(as)h(w)o(ell.) 148 2099 y(Since)k(\000)310 2106 y Fh(k)352 2099 y Fn(is)g(in)g(the)f (order)g(of)745 2049 y Fd(q)p 786 2049 32 2 v 792 2080 a Fh(k)p 791 2088 22 2 v 791 2116 a(n)818 2099 y Fn(,)g(W)l(e)g(can)h (adjust)g(the)f(pruning)i(decision)f(test)f(with)h(another)75 2159 y(parameter)16 b Fk(c)885 2272 y(e)908 2279 y Fi(2)p 882 2294 50 2 v 882 2339 a Fk(n)911 2346 y Fh(v)950 2305 y Fk(<)1011 2272 y(e)1034 2279 y Fi(1)p 1007 2294 V 1007 2339 a Fk(n)1036 2346 y Fh(v)1073 2305 y Fn(+)11 b Fk(c)1143 2242 y Fd(r)p 1184 2242 40 2 v 1192 2272 a Fk(s)p 1189 2294 30 2 v 1189 2339 a(n)148 2451 y Fn(The)16 b(parameter)g Fk(c)h Fn(con)o(trols)g(the)f(tendency)f(of)i(the)f(algorithm)i(to)f (prune.)p eop %%Page: 8 8 8 7 bop 0 -31 a Fn(8)1404 b Fj(Lecture)16 b(9:)21 b(Ma)o(y)16 b(21,)g(1997)0 101 y Fm(10.5)82 b(Pruning)26 b(With)h(Exp)r(erts)0 211 y Fn(In)c(a)h(previous)g(lecture)f(w)o(e)f(sa)o(w)i(an)g(on-line)h (algorithm)g(that)f(com)o(bined)f(exp)q(erts)g(predictions)i(to)0 271 y(predict)20 b(assimptotically)j(as)e(w)o(ell)g(as)g(the)f(b)q(est) g(exp)q(ert.)32 b(Ev)o(ery)20 b(p)q(ossible)i(pruning)f(of)g(the)f (decision)0 331 y(tree)j(represen)o(ts)f(an)i(exp)q(ert,)g(so)g(b)o(y)f (adapting)i(the)f(algorithm)h(to)f(the)f(pruning)h(problem)g(w)o(e)f (are)0 391 y(assured)17 b(to)g(p)q(erform)f(as)h(go)q(o)q(d)i(as)e(the) f(b)q(est)h(pruned)f(subtree.)22 b(The)16 b(algorithm,)i(ho)o(w)o(ev)o (er,)d(cannot)i(b)q(e)0 451 y(directly)i(used)f(since)h(there)f(are)g (to)q(o)i(man)o(y)e(exp)q(erts.)27 b(W)l(e)18 b(sho)o(w)h(here)f(a)h (metho)q(d)g(to)g(o)o(v)o(ercome)e(that)0 512 y(e\016ciency)l(.)0 653 y Fa(10.5.1)65 b(An)23 b(ine\016cien)n(t)h(algorithm)0 745 y Fn(Recall)14 b(from)g(Lecture)f(5.)21 b(The)13 b(algorithm)j(\()p Fl(He)n(dge\()p Fk(\014)s Fl(\))p Fn(\))d(based)h(its)h(prediction)f(\()s(^)-27 b Fk(y)1523 752 y Fh(t)1538 745 y Fn(\))13 b(giv)o(en)h(the)f(instance)0 806 y Fk(x)28 787 y Fh(t)59 806 y Fn(in)k(time)f Fk(t)g Fn(on)g(a)h(w)o(eigh)o(ted)f(a)o(v)o(erage)g(of)h(the)f(exp)q(erts)g (predictions)h Fk(p)p Fn(\()p Fk(x)1378 787 y Fh(t)1393 806 y Fn(\).)775 975 y Fk(r)798 954 y Fh(t)855 975 y Fn(=)939 905 y Fd(P)983 948 y Fh(p)1011 938 y Fk(w)1047 920 y Fh(t)1046 950 y(p)1066 938 y Fk(p)p Fn(\()p Fk(x)1137 920 y Fh(t)1152 938 y Fn(\))p 939 963 232 2 v 991 976 a Fd(P)1035 1019 y Fh(p)1063 1009 y Fk(w)1099 995 y Fh(t)1098 1021 y(p)778 1085 y Fn(^)-28 b Fk(y)798 1092 y Fh(t)855 1085 y Fn(=)41 b Fk(F)966 1092 y Fh(\014)989 1085 y Fn(\()p Fk(r)1031 1065 y Fh(t)1046 1085 y Fn(\))73 1175 y(Where)16 b Fk(\014)h Ff(2)e Fn([0)p Fk(;)8 b Fn(1])17 b(is)g(a)g(parameter)g(of) g(the)f(algorithm,)i Fk(w)1173 1157 y Fh(t)1172 1187 y(p)1209 1175 y Fn(is)f(the)g(w)o(eigh)o(t)g(of)g(exp)q(ert)f Fk(p)h Fn(at)g(time)g Fk(t)p Fn(,)0 1235 y(and)g Fk(F)127 1242 y Fh(\014)166 1235 y Fn(need)f(only)h(satisfy)g(certain)g(prop)q (erties)g(\(See)f(Lecture)g(5\).)73 1295 y(The)d(w)o(eigh)o(ts)h(of)f (the)g(exp)q(erts)g(are)g(up)q(dated)h(at)f(time)g Fk(t)g Fn(after)g(the)g(true)f(classi\014cation)k Fk(y)1703 1277 y Fh(t)1731 1295 y Fn(is)e(rev)o(ealed)712 1394 y Fk(w)748 1374 y Fh(t)p Fi(+1)747 1407 y Fh(p)822 1394 y Fn(=)f Fk(w)909 1374 y Fh(t)908 1407 y(p)928 1394 y Fk(U)5 b Fn(\()p Ff(j)p Fk(p)p Fn(\()p Fk(x)1070 1374 y Fh(t)1085 1394 y Fn(\))11 b Ff(\000)g Fk(y)1191 1374 y Fh(t)1205 1394 y Ff(j)p Fn(\))73 1484 y(The)16 b(total)i(loss)g(of)e (the)g(algorithm)i(is)f Fk(L)826 1491 y Fh(A)793 1608 y Fk(L)826 1615 y Fh(A)868 1608 y Fn(=)937 1554 y Fh(T)920 1566 y Fd(X)921 1657 y Fh(t)p Fi(=1)988 1608 y Ff(j)s Fn(^)-27 b Fk(y)1028 1587 y Fh(t)1053 1608 y Ff(\000)11 b Fk(y)1129 1587 y Fh(t)1144 1608 y Ff(j)73 1729 y Fn(And)16 b(if)h(the)f(loss)i(of)e(the)g(b)q(est)h(exp)q(ert)e(is)i Fk(L)879 1736 y Fh(P)925 1729 y Fn(then)f(w)o(e)g(are)g(assured)h(that) 749 1862 y Fk(L)782 1869 y Fh(A)824 1862 y Ff(\024)882 1813 y Fk(L)915 1820 y Fh(P)953 1813 y Fn(ln)1008 1794 y Fi(1)p 1007 1802 22 2 v 1007 1831 a Fh(\014)1044 1813 y Ff(\000)11 b Fn(ln)1161 1794 y Fi(1)p 1148 1802 44 2 v 1148 1831 a Fh(w)1174 1821 y Fc(1)1173 1839 y Fb(p)p 882 1850 315 2 v 981 1896 a Fn(1)h Ff(\000)f Fk(\014)73 1977 y Fn(Note)23 b(that)h(the)f(running)h(time)f(of)h(the)f(algorithm) i(is)f(linear)g(in)g(the)f(n)o(um)o(b)q(er)f(of)i(exp)q(erts)f(\(i.e.)0 2037 y(prunings\),)17 b(whic)o(h)g(in)g(this)g(case)f(is)h(enormous.)0 2178 y Fa(10.5.2)65 b(An)23 b(e\016cien)n(t)g(implemen)n(tation)0 2271 y Fn(The)e(problem)h(with)h(the)e(ab)q(o)o(v)o(e)g(algorithm)j(is) e(that)g(w)o(e)f(cannot)h(main)o(tain)h(all)f(of)g(the)f(w)o(eigh)o(ts) h Fk(w)1931 2253 y Fh(t)1930 2283 y(p)0 2331 y Fn(explicitly)12 b(since)f(there)f(are)h(far)g(to)q(o)h(man)o(y)f(prunings)h(to)f (consider.)20 b(Note,)11 b(ho)o(w)o(ev)o(er)f(that)h(the)g(prediction)3 2391 y(^)-27 b Fk(y)26 2373 y Fh(t)57 2391 y Fn(is)17 b(based)g(directly)g(on)g Fk(r)511 2373 y Fh(t)526 2391 y Fn(.)22 b(W)l(e)16 b(sho)o(w)h(here)f(a)h(metho)q(d)g(to)g(e\016cien) o(tly)f(compute)g Fk(r)1593 2373 y Fh(t)1608 2391 y Fn(.)22 b(First)17 b(w)o(e)f(pro)o(v)o(e)0 2451 y(a)h(general)g(result,)f(and)h (then)f(consider)h(its)g(application)i(to)d(our)h(problem.)p eop %%Page: 9 9 9 8 bop 75 -31 a Fj(10.5.)38 b(PR)o(UNING)15 b(WITH)g(EXPER)l(TS)1153 b Fn(9)75 101 y Fo(A)19 b(general)g(result)75 217 y(De\014nition)45 b Fn(Let)21 b Fk(T)27 b Fn(b)q(e)21 b(a)g(decision)h(tree.)34 b(The)20 b Fl(size)h Fn(of)g(a)g(pruning)h Fk(P)28 b Fn(of)21 b Fk(T)7 b Fn(,)21 b(written)g Ff(j)p Fk(P)7 b Ff(j)p Fn(,)21 b(is)g(the)75 277 y(n)o(um)o(b)q(er)f(of)h(in)o (ternal)g(no)q(des)g(and)g(lea)o(v)o(es)g(in)g Fk(P)27 b Fl(minus)21 b Fn(the)f(n)o(um)o(b)q(er)g(of)h(lea)o(v)o(es)f(in)h Fk(P)28 b Fn(that)21 b(are)f(also)75 337 y(lea)o(v)o(es)c(of)g Fk(T)7 b Fn(.)148 420 y(Let)17 b Fk(g)r Fn(\()p Fk(s)p Fn(\))g(b)q(e)g(a)g(function)h(on)f(the)g(lea)o(v)o(es)f(of)h(a)h (decision)g(tree.)k(W)l(e)17 b(de\014ne)f(the)h(follo)o(wing)i (function)75 480 y(on)e(the)f(no)q(des)h(of)f Fk(T)23 b Fn(as)17 b(a)g(w)o(eigh)o(ted)f(a)o(v)o(erage)g(of)g(the)g(follo)o (wing)j(form:)75 563 y Fo(De\014nition)p 704 599 26 2 v 704 626 a Fk(g)r Fn(\()p Fk(u)p Fn(\))808 597 y Fh(def)817 626 y Fn(=)916 584 y Fd(X)877 676 y Fh(P)j(of)e(T)996 680 y Fb(u)1024 626 y Fn(2)1048 605 y Fe(\000j)p Fh(P)5 b Fe(j)1191 584 y Fd(Y)1133 688 y Fh(s)p Fe(2)p Fn(leaf)p Fi(\()p Fh(P)g Fi(\))1310 626 y Fk(g)r Fn(\()p Fk(s)p Fn(\))75 769 y(Where)17 b(w)o(e)g(denote)g(b)o(y)g Fk(T)561 776 y Fh(u)600 769 y Fn(the)g(subtree)g(of)h Fk(T)24 b Fn(ro)q(oted)18 b(at)f Fk(u)p Fn(,)g(and)h(the)f(notation)1617 736 y Fd(P)1661 780 y Fh(P)22 b(of)e(T)1780 784 y Fb(u)1819 769 y Fn(is)e(used)g(to)75 830 y(indicate)f(summation)h(o)o(v)o(er)d (all)j(prunings)f(of)g Fk(T)969 837 y Fh(u)991 830 y Fn(.)75 973 y Fo(Lemma)h(10.3)81 b Fl(1.)25 b(if)17 b Fk(u)g Fl(is)g(a)h(le)n(af)f(then)p 905 946 V 19 w Fk(g)r Fn(\()p Fk(u)p Fn(\))c(=)h Fk(g)r Fn(\()p Fk(u)p Fn(\))133 1079 y Fl(2.)24 b(if)17 b Fk(u)g Fl(is)h(an)f(internal)i(no)n(de)f (then)p 818 1053 V 18 w Fk(g)r Fn(\()p Fk(u)p Fn(\))c(=)980 1060 y Fi(1)p 980 1068 18 2 v 980 1096 a(2)1002 1079 y Fk(g)r Fn(\()p Fk(u)p Fn(\))d(+)1158 1060 y Fi(1)p 1158 1068 V 1158 1096 a(2)1189 1046 y Fd(Q)1228 1090 y Fh(v)q Fe(2)p Fh(son)p Fi(\()p Fh(u)p Fi(\))p 1383 1053 26 2 v 1383 1079 a Fk(g)r Fn(\()p Fk(v)r Fn(\))148 1200 y(Note)j(that)g(computing)h(b)q(ottom)g(up,)f(the)g(lemma)g(pro)o (vides)g(a)g(metho)q(ds)h(to)f(compute)p 1771 1173 V 14 w Fk(g)r Fn(\()p Fk(u)p Fn(\))g(in)g(time)75 1260 y(prop)q(ortional)19 b(to)e(the)f(n)o(um)o(b)q(er)g(of)g(no)q(des)h(in) g Fk(T)7 b Fn(.)148 1321 y Fl(Pr)n(o)n(of:)135 1428 y Fn(1.)24 b(The)15 b(size)g(of)g(a)g(pruning)h(of)f(a)g(leaf)h(of)f Fk(T)21 b Fn(is)16 b(0.)21 b(The)14 b(result)i(trivially)h(follo)o(ws)f (from)f(the)f(de\014nition)197 1488 y(of)p 252 1461 V 16 w Fk(g)s Fn(.)135 1594 y(2.)24 b(Note)e(that)h(an)o(y)g(pruning)g Fk(P)30 b Fn(of)23 b(the)f(subtree)h Fk(T)1139 1601 y Fh(u)1183 1594 y Fn(either)g(con)o(tains)g(only)h(no)q(de)f Fk(u)f Fn(or)h(can)g(b)q(e)197 1654 y(decomp)q(osed)h(in)o(to)g(t)o(w)o (o)g(subtrees,)h Fk(P)927 1661 y Fi(0)971 1654 y Fn(and)f Fk(P)1104 1661 y Fi(1)1125 1654 y Fn(,)h(ro)q(oted)f(at)g(the)g(c)o (hildren)g Fk(u)1704 1661 y Fi(0)1747 1654 y Fn(and)g Fk(u)1877 1661 y Fi(1)1921 1654 y Fn(of)g Fk(u)p Fn(.)197 1715 y(Separating)19 b(the)d(ab)q(o)o(v)o(e)h(t)o(w)o(o)g(cases)g(and)h (using)g(the)f(easy)g(to)g(pro)o(v)o(e)f(fact)h Ff(j)p Fk(P)7 b Ff(j)15 b Fn(=)g(1)d(+)f Ff(j)p Fk(P)1851 1722 y Fi(0)1871 1715 y Ff(j)h Fn(+)f Ff(j)p Fk(P)1991 1722 y Fi(1)2011 1715 y Ff(j)197 1775 y Fn(w)o(e)16 b(ha)o(v)o(e)p 347 1954 V 347 1981 a Fk(g)r Fn(\()p Fk(u)p Fn(\))42 b(=)564 1947 y(1)p 564 1969 25 2 v 564 2015 a(2)593 1981 y Fk(g)r Fn(\()p Fk(u)p Fn(\))11 b(+)744 1939 y Fd(X)755 2031 y Fh(P)777 2036 y Fc(0)813 1939 y Fd(X)823 2031 y Fh(P)845 2036 y Fc(1)881 1981 y Fn(2)905 1960 y Fe(\000)p Fi(\(1+)p Fe(j)p Fh(P)1023 1965 y Fc(0)1041 1960 y Fe(j)p Fi(+)p Fe(j)p Fh(P)1110 1965 y Fc(1)1128 1960 y Fe(j)p Fi(\))1248 1939 y Fd(Y)1162 2043 y Fh(w)1187 2048 y Fc(0)1204 2043 y Fe(2)p Fn(leaf)p Fi(\()p Fh(T)1337 2047 y Fb(u)1355 2054 y Fc(0)1374 2043 y Fi(\))1396 1981 y Fk(g)r Fn(\()p Fk(w)1475 1988 y Fi(0)1495 1981 y Fn(\))1609 1939 y Fd(Y)1522 2043 y Fh(w)1547 2048 y Fc(1)1565 2043 y Fe(2)p Fn(leaf)p Fi(\()p Fh(T)1698 2047 y Fb(u)1716 2054 y Fc(1)1735 2043 y Fi(\))1757 1981 y Fk(g)r Fn(\()p Fk(w)1836 1988 y Fi(1)1856 1981 y Fn(\))480 2141 y(=)564 2108 y(1)p 564 2130 V 564 2175 a(2)593 2141 y Fk(g)r Fn(\()p Fk(u)p Fn(\))g(+)749 2108 y(1)p 749 2130 V 749 2175 a(2)779 2141 y(\()798 2100 y Fd(X)808 2192 y Fh(P)830 2197 y Fc(0)866 2141 y Fn(2)890 2121 y Fe(\000j)p Fh(P)949 2126 y Fc(0)967 2121 y Fe(j)987 2100 y Fd(Y)993 2187 y Fh(w)1018 2192 y Fc(0)1049 2141 y Fk(g)r Fn(\()p Fk(w)1128 2148 y Fi(0)1147 2141 y Fn(\)\)\()1204 2100 y Fd(X)1215 2192 y Fh(P)1237 2197 y Fc(1)1273 2141 y Fn(2)1297 2121 y Fe(\000j)p Fh(P)1356 2126 y Fc(1)1374 2121 y Fe(j)1394 2100 y Fd(Y)1399 2187 y Fh(w)1424 2192 y Fc(1)1455 2141 y Fk(g)r Fn(\()p Fk(w)1534 2148 y Fi(1)1554 2141 y Fn(\)\))480 2283 y(=)564 2249 y(1)p 564 2271 V 564 2317 a(2)593 2283 y Fk(g)r Fn(\()p Fk(u)p Fn(\))g(+)749 2249 y(1)p 749 2271 V 749 2317 a(2)833 2241 y Fd(Y)787 2335 y Fh(v)q Fe(2)p Fh(son)p Fi(\()p Fh(u)p Fi(\))p 940 2256 26 2 v 940 2283 a Fk(g)r Fn(\()p Fk(v)r Fn(\))p 2001 2451 24 24 v eop %%Page: 10 10 10 9 bop 0 -31 a Fn(10)1380 b Fj(Lecture)16 b(9:)21 b(Ma)o(y)16 b(21,)g(1997)0 101 y Fo(E\016cien)n(tly)j(computing)g Fk(r)565 83 y Fh(t)0 193 y Fn(W)l(e)h(no)o(w)g(sho)o(w)g(ho)o(w)g (Lemma)g(10.3)h(is)f(used)g(to)g(compute)g Fk(r)1162 175 y Fh(t)1177 193 y Fn(.)32 b(W)l(e)20 b(do)g(so)g(b)o(y)g(writing)h Fk(r)1711 175 y Fh(t)1746 193 y Fn(in)g(a)f(form)0 254 y(equiv)m(alen)o(t)d(to)p 291 227 26 2 v 16 w Fk(g)r Fn(.)73 314 y(F)l(or)h(an)o(y)f(no)q(de)h Fk(u)f Fn(w)o(e)g(de\014ne)g (the)g(w)o(eigh)o(t)h(at)f(time)h Fk(t)f Fn(to)g(b)q(e)h(its)g(past)g (con)o(tribution)h(to)f(the)f(w)o(eigh)o(t)0 374 y(decrease)f(of)g(an)o (y)g(tree)g Fk(P)23 b Fn(that)17 b(con)o(tains)g Fk(u)f Fn(as)h(a)g(leaf:)327 475 y(WEIGHT)538 454 y Fh(t)553 475 y Fn(\()p Fk(u)p Fn(\))632 446 y Fh(def)641 475 y Fn(=)910 434 y Fd(Y)835 545 y Fn(1)d Ff(\024)g Fk(t)944 527 y Fi(`)969 545 y Fk(<)g(t)722 610 y(x)750 592 y Fh(t)763 580 y Fc(`)792 610 y Fn(passes)j(through)g Fk(u)1180 475 y(U)1213 482 y Fh(\014)1237 475 y Fn(\()p Ff(j)p Fk(v)r(al)q(ue)1389 485 y Fh(t)1402 475 y Fc(`)q Fn(\()p Fk(u)p Fn(\))11 b Ff(\000)g Fk(y)1565 455 y Fh(t)1578 443 y Fc(`)1590 475 y Ff(j)p Fn(\))0 709 y(Where)16 b Fk(v)r(al)q(ue)275 718 y Fh(t)288 709 y Fc(`)q Fn(\()p Fk(u)p Fn(\))g(is)h(the)f(predicted)g(v)m(alue)h(at)g(no)q(de)g Fk(u)f Fn(in)h(time)f Fk(t)1261 691 y Fi(`)1272 709 y Fn(.)22 b(F)l(or)16 b(an)o(y)g(pruning)i Fk(p)p Fn(,)e(w)o(e)g(ha)o(v)o (e)412 806 y Fk(w)448 785 y Fh(t)447 818 y(p)508 806 y Fn(=)42 b(2)612 785 y Fe(\000j)p Fh(p)p Fe(j)715 764 y Fd(Y)687 860 y Fi(1)p Fe(\024)p Fh(t)745 851 y Fc(`)756 860 y Fh(