(original) (raw)

%!PS (but not EPSF; comments have been disabled) %DVIPSCommandLine: dvips -o -N npftp %DVIPSSource: TeX output 1994.09.26:1625 /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 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 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 TeXDict begin 40258431 52099146 1000 300 300 (/tmp_mnt/home/u2/zoubin/papers/nips93/npftp.dvi) @start /Fa 1 50 df<18F818181818181818181818FF080D7D8C0E>49 D E /Fb 1 1 df0 D E /Fc 2 106 df<03C000C000C000C00180 1D8033806180C300C300C300C32047403B800B0E7E8D0F>100 D<0808000000007098B0 303060646870060F7D8E0B>105 D E /Fd 28 123 df<60F0F07010101020204080040B 7D830B>44 D<60F0F06004047D830B>46 D<003F020001C0C60003002E000E001E001C00 0E001C00060038000600780002007000020070000200F0000000F0000000F0000000F000 0000F0000000F001FFC070000E0070000E0078000E0038000E001C000E001C000E000E00 0E000300160001C06600003F82001A1A7E991E>71 D<7FFFFF00701C0700401C0100401C 0100C01C0180801C0080801C0080801C0080001C0000001C0000001C0000001C0000001C 0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C 0000001C0000001C0000001C000003FFE000191A7F991C>84 D<3F8070C070E020700070 007007F01C7030707070E070E071E071E0F171FB1E3C10107E8F13>97 DI<07F80C1C381C30087000E000E000E000E000E000E000 7000300438080C1807E00E107F8F11>I<007E00000E00000E00000E00000E00000E0000 0E00000E00000E00000E0003CE000C3E00380E00300E00700E00E00E00E00E00E00E00E0 0E00E00E00E00E00600E00700E00381E001C2E0007CFC0121A7F9915>I<07C01C303018 7018600CE00CFFFCE000E000E000E0006000300438080C1807E00E107F8F11>I<01F003 1807380E100E000E000E000E000E000E00FFC00E000E000E000E000E000E000E000E000E 000E000E000E000E000E007FE00D1A80990C>I<0FCE1873303070387038703870383030 18602FC02000600070003FF03FFC1FFE600FC003C003C003C0036006381C07E010187F8F 13>II<18003C003C001800000000000000000000000000 FC001C001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80091A8099 0A>I108 DI< FCF8001D0C001E0E001E0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E001C0E00 1C0E001C0E001C0E00FF9FC012107F8F15>I<07E01C38300C700E6006E007E007E007E0 07E007E0076006700E381C1C3807E010107F8F13>II<03C2000C2600381E0030 0E00700E00E00E00E00E00E00E00E00E00E00E00E00E00700E00700E00381E001C2E0007 CE00000E00000E00000E00000E00000E00000E00007FC012177F8F14>II<1F2060 E04020C020C020F0007F003FC01FE000F080708030C030C020F0408F800C107F8F0F>I< 0400040004000C000C001C003C00FFC01C001C001C001C001C001C001C001C001C201C20 1C201C201C200E4003800B177F960F>II< FF1F803C06001C04001C04001E0C000E08000E080007100007100007900003A00003A000 01C00001C00001C00000800011107F8F14>IIII<7FF86070407040E041C041C00380070007000E081C081C08381070107030FF F00D107F8F11>I E /Fe 1 50 df<0C003C00CC000C000C000C000C000C000C000C000C 000C000C000C000C00FF8009107E8F0F>49 D E /Ff 1 23 df<03801C0007C03E0007C0 3E0007C03E000F807C000F807C000F807C000F807C001F00F8001F00F8001F00F8001F00 F8803E01F1803E01F1803E01F1803F03F3007F0CF2007FF83C007C0000007C000000F800 0000F8000000F8000000F8000000F0000000E0000000191A7E911D>22 D E /Fg 4 90 df80 DI88 DI E /Fh 14 121 df<40E06020202040408003097D820A>59 D<00200060006000C000C000 C0018001800180030003000300060006000C000C000C0018001800180030003000300060 0060006000C000C000C0000B1D7E9511>61 D<07FFE000E07001C01801C00C01C00C01C0 0E03800E03800E03800E03800E07001C07001C07001C0700380E00300E00700E00E00E01 C01C0700FFFC0017147F931B>68 D<07F000FE00F000F0017001E0017002E0017002E001 7004E0027009C0023809C0023811C0023821C0043823800438438004388380041C838008 1D0700081E0700081E0700081C070018180E00FE187FC01F147F9320>77 D<07E01FC000E0060001700400017004000138040001380400021C0800021C0800020E08 00020E0800040710000407100004039000040390000801E0000801E0000800E0000800E0 0018004000FE0040001A147F931A>I<1FFFF8381C182038182038084038084038108070 1000700000700000700000E00000E00000E00000E00001C00001C00001C00001C0000380 003FF8001514809314>84 D<07800C4010E031C0600060006000C000C000402040402180 1E000B0D7E8C0F>99 D<007C000C0018001800180018003007B00C701070306060606060 6060C0C0C0C8C0C841C862D03C700E147E9311>I<06070600000000384C4C8C98181830 326262643808147F930C>105 D<0060007000600000000000000000038004C0046008C0 08C000C000C0018001800180018003000300030003006600E600CC0078000C1A81930E> I<3E0006000C000C000C000C001800187018B819383230340038003E0063006310631063 10C320C1C00D147E9312>I<7C0C181818183030303060606060C0D0D0D0D06006147E93 0A>I<30F8590C4E0C9C0C980C180C180C30183019303130316032601C100D7F8C15>110 D<0E3C13CE238E430C43000300030006000608C608E610CA2071C00F0D7F8C13>120 D E /Fi 9 112 df<01020408103020606040C0C0C0C0C0C0C0C0C0C040606020301008 040201081E7E950D>40 D<80402010080C0406060203030303030303030303020606040C 0810204080081E7E950D>I<006000006000006000006000006000006000006000006000 006000006000FFFFF0FFFFF0006000006000006000006000006000006000006000006000 00600000600014167E9119>43 D<0C001C00EC000C000C000C000C000C000C000C000C00 0C000C000C000C000C000C000C00FFC00A137D9211>49 D<1F0060C06060F070F0306030 00700070006000C001C00180020004000810101020207FE0FFE00C137E9211>I<7FFFE0 FFFFF0000000000000000000000000000000000000FFFFF07FFFE0140A7E8B19>61 D<2070200000000000F03030303030303030303030FC06157F9409>105 D109 D<0FC0186020106018C00CC00CC00CC00CC00C6018601838 700FC00E0D7F8C11>111 D E /Fj 1 1 df0 D E /Fk 11 107 df0 D<0004000000060000000600 000006000000060000000600000006000000060000000600000006000000060000000600 0000060000FFFFFFE0FFFFFFE00006000000060000000600000006000000060000000600 000006000000060000000600000006000000060000FFFFFFE0FFFFFFE01B1C7E9A20>6 D17 D<07C000201FE000203FF80020783C0060E01F00 E0C00783C08003FF808000FF0080007C001B097E8E20>24 D<007FF801FFF80780000E00 00180000300000300000600000600000C00000C00000C00000FFFFF8FFFFF8C00000C000 00C000006000006000003000003000001800000E000007800001FFF8007FF8151A7D961C >50 D<0003F0000FF80030F80040780180780300700700700E00E00E00E01C01801C0000 380000380000780000780000700000700000F00000F00000F00000F00000F00000F00020 F80060F801C07C01807E03003F04001FF8000FE000151E7F9C16>67 D<001F003C003F807C00EF803C0187803C0007C0380007C0300003C0600003C0800003C1 000003C6000003C8000003F0000003C0000003C0000007C000000BC0000033C0000043C0 000183C0000203C0000403C0001803C0003003E0007003E000F001E180F001F700F801FC 00F000F8001E1C7E9B1E>88 D<0007F810001FFFF000607FE000C000C001C00180038003 000200060000000C0000001800000038000000700000006000001FFC00003FFC00000318 0000060000000C0000001800000030000000400000008000C0030001C0060003800C0003 00180007003FFC0C007FFFF800803FE0001C1C7E9B1E>90 D<003C00E001C00180038003 8003800380038003800380038003800380038003800380030007001C00F0001C00070003 000380038003800380038003800380038003800380038003800380018001C000E0003C0E 297D9E15>102 DI106 D E /Fl 21 123 df<007800CC0186030606060E060C061C07180738063806300E70 0E700E7FFEE01CE01CE01CE018E038C038C070C060C060C0C0C180618062003C00101D7E 9C13>18 D<0180300380700380700380700700E00700E00700E00700E00E01C00E01C00E 01C00E01C01C03881C03881C03881E07883E19903BE0E038000038000070000070000070 0000700000E00000E00000C00000151B7F9119>22 D<0FFFF81FFFF83FFFF06084004084 00808C00010C00010C00030C00030C00020C00061C00061C000E1C000C1C001C0E001C0E 00180C0015127E9118>25 D<08000410000E10000E200006200006400002400802401802 80180480180480300C803008C03018C0F030FFFFF07FBFE07F1FC03E0F00171280911A> 33 D<60F0F06004047C830C>58 D<60F0F0701010101020204080040C7C830C>I<01FFFF 80003C01E000380070003800380038001C0038001C0070001C0070001E0070001E007000 1E00E0001E00E0001E00E0001E00E0001E01C0003C01C0003C01C0003C01C00038038000 7803800070038000F0038000E0070001C0070003800700070007001C000E007800FFFFC0 001F1C7E9B22>68 D<01FFFFF8003C007800380018003800100038001000380010007000 1000700010007010100070100000E0200000E0200000E0600000FFE00001C0400001C040 0001C0400001C04000038080400380004003800080038000800700010007000100070003 00070006000E003E00FFFFFC001D1C7E9B1F>I<01FE0000FF003E0000F0002E0001E000 2E0002E0002E0002E0002E0004E0004E0009C0004E0009C000470011C000470011C00087 002380008700438000870043800087008380010701070001070107000103820700010382 07000203840E000203880E000203880E000203900E000403A01C000403A01C000401C01C 000C01C01C001C01803C00FF8103FF80281C7E9B28>77 D<01FFFF00003C03C0003800E0 003800F00038007000380070007000F0007000F0007000F0007000E000E001E000E003C0 00E0078000E01E0001FFF00001C0000001C0000001C00000038000000380000003800000 03800000070000000700000007000000070000000F000000FFE000001C1C7E9B1B>80 D<0003F800000E0E000038038000E001C001C001C0038000E0070000E00F0000F01E0000 F01C0000F03C0000F03C0000F0780000F0780000F0780000F0F00001E0F00001E0F00001 E0F00003C0F00003C0F0000380F0000780F0000F00703C0E0070421C0038823800388270 001C83C0000787810001FF0100000303000003020000038E000003FC000003F8000001F8 000001E0001C257E9C21>I<0007E00000E00000E00001C00001C00001C00001C0000380 00038000038000038001E7000717000C0F00180F00380E00300E00700E00700E00E01C00 E01C00E01C00E01C00E03880E03880E038806078803199001E0E00131D7E9C16>100 D<0001E0000630000E78000CF0001C60001C00001C00001C00003C0000380000380003FF C000380000380000700000700000700000700000700000E00000E00000E00000E00000E0 0001C00001C00001C00001C00001C000018000038000038000630000F30000F60000E400 0078000015257E9C14>102 D<0FC00001C00001C0000380000380000380000380000700 000700000700000700000E3E000EC3000F03800E03801E03801C03801C03801C03803807 00380700380700380E00700E20700E20701C20701C40E00C80600700131D7E9C18>104 D<01C003C003C001800000000000000000000000001C00270047004700870087000E000E 001C001C001C003800388038807080710032001C000A1C7E9B0E>I<0007000F000F0006 0000000000000000000000000070009C010C020C021C041C001C001C0038003800380038 007000700070007000E000E000E000E001C061C0F180F300E6007C001024809B11>I<0F C00001C00001C0000380000380000380000380000700000700000700000700000E07000E 18800E21C00E23C01C47801C83001D00001E00003F800039C00038E00038E00070E10070 E10070E10070E200E06200603C00121D7E9C16>I<1F800380038007000700070007000E 000E000E000E001C001C001C001C0038003800380038007000700070007000E400E400E4 00E40064003800091D7E9C0C>I<381F004E61804681C04701C08F01C08E01C00E01C00E 01C01C03801C03801C03801C0700380710380710380E10380E2070064030038014127E91 19>110 D<07878008C84010F0C020F1E020E3C040E18000E00000E00001C00001C00001 C00001C000638080F38080F38100E5810084C60078780013127E9118>120 D<038107C10FE6081C10080010002000400080010002000400080410042C1877F843F081 C010127E9113>122 D E /Fm 32 122 df<00180000780001F800FFF800FFF80001F800 01F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F800 01F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F800 7FFFE07FFFE013207C9F1C>49 D<03FC000FFF003C1FC07007E07C07F0FE03F0FE03F8FE 03F8FE01F87C01F83803F80003F80003F00003F00007E00007C0000F80001F00003E0000 380000700000E01801C0180380180700180E00380FFFF01FFFF03FFFF07FFFF0FFFFF0FF FFF015207D9F1C>I<00FE0007FFC00F07E01E03F03F03F03F81F83F81F83F81F81F03F8 1F03F00003F00003E00007C0001F8001FE0001FF000007C00001F00001F80000FC0000FC 3C00FE7E00FEFF00FEFF00FEFF00FEFF00FC7E01FC7801F81E07F00FFFC001FE0017207E 9F1C>I<0000E00001E00003E00003E00007E0000FE0001FE0001FE00037E00077E000E7 E001C7E00187E00307E00707E00E07E00C07E01807E03807E07007E0E007E0FFFFFEFFFF FE0007E00007E00007E00007E00007E00007E00007E000FFFE00FFFE17207E9F1C>I<10 00201E01E01FFFC01FFF801FFF001FFE001FF8001BC00018000018000018000018000019 FC001FFF001E0FC01807E01803E00003F00003F00003F80003F83803F87C03F8FE03F8FE 03F8FC03F0FC03F07007E03007C01C1F800FFF0003F80015207D9F1C>I<000070000000 007000000000F800000000F800000000F800000001FC00000001FC00000003FE00000003 FE00000003FE00000006FF000000067F0000000E7F8000000C3F8000000C3F800000183F C00000181FC00000381FE00000300FE00000300FE00000600FF000006007F00000E007F8 0000FFFFF80000FFFFF800018001FC00018001FC00038001FE00030000FE00030000FE00 0600007F000600007F00FFE00FFFF8FFE00FFFF825227EA12A>65 D68 DI< FFFFE0FFFFE003F80003F80003F80003F80003F80003F80003F80003F80003F80003F800 03F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003F80003F800 03F80003F80003F80003F80003F80003F80003F80003F800FFFFE0FFFFE013227FA115> 73 D76 DI82 D<01FC0407FF8C1F03FC3C007C7C003C78001C78001CF8000CF8000CFC000CFC0000FF00 00FFE0007FFF007FFFC03FFFF01FFFF80FFFFC03FFFE003FFE0003FF00007F00003F0000 3FC0001FC0001FC0001FE0001EE0001EF0003CFC003CFF00F8C7FFE080FF8018227DA11F >I<07FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003FF003FDF01F C1F03F01F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F18167E95 1B>97 DI<00FF8007FFE00F83F01F03F03E03F07E03F07C01E07C0000FC0000FC00 00FC0000FC0000FC0000FC00007C00007E00007E00003E00301F00600FC0E007FF8000FE 0014167E9519>I<0001FE000001FE0000003E0000003E0000003E0000003E0000003E00 00003E0000003E0000003E0000003E0000003E0000003E0001FC3E0007FFBE000F81FE00 1F007E003E003E007E003E007C003E00FC003E00FC003E00FC003E00FC003E00FC003E00 FC003E00FC003E00FC003E007C003E007C003E003E007E001E00FE000F83BE0007FF3FC0 01FC3FC01A237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC00F8FC 00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003 FFC000FF0015167E951A>I<003F8000FFC001E3E003C7E007C7E00F87E00F83C00F8000 0F80000F80000F80000F80000F8000FFFC00FFFC000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80007FF8007FF80013237FA211>I<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03 E07C03E07C03E07C03E03C03C03E07C01F0F801FFF0013FC003000003000003800003FFF 801FFFF00FFFF81FFFFC3800FC70003EF0001EF0001EF0001EF0001E78003C7C007C3F01 F80FFFE001FF0018217E951C>I<1C003F007F007F007F003F001C000000000000000000 000000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F00 1F001F001F001F001F00FFE0FFE00B247EA310>105 D108 DII<00FE0007FFC00F83E01E00F03E00F87C00 7C7C007C7C007CFC007EFC007EFC007EFC007EFC007EFC007EFC007E7C007C7C007C3E00 F81F01F00F83E007FFC000FE0017167E951C>II114 D<0FF3003FFF00781F00600700E00300E00300F00300FC 00007FE0007FF8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC 0E00EFFC00C7F00011167E9516>I<018000018000018000018000038000038000078000 0780000F80003F8000FFFF00FFFF000F80000F80000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F81800F81800F81800F81800F81800F830007C30003FE00 00F80011207F9F16>III121 D E /Fn 17 123 df<70F8F8F8700505788416>46 D<00F80003FC0007FE000F07001C3F80387F8078FF8071C3C071C3C0E381C0E381C0E381 C0E381C0E381C0E381C0E381C071C38071C38078FF00387E001C3C000F03C007FFC003FF 0000FC0012197E9816>64 D<7E0000FE00007E00000E00000E00000E00000E00000E3E00 0EFF000FFF800F83C00F00E00E00E00E00700E00700E00700E00700E00700E00700E00E0 0F01E00F83C00FFF800EFF00063C001419809816>98 D<03F80FFC1FFE3C1E780C7000E0 00E000E000E000E000F000700778073E0E1FFC0FF803F010127D9116>I<003F00007F00 003F0000070000070000070000070003C7000FF7001FFF003C1F00780F00700700E00700 E00700E00700E00700E00700E00700700F00700F003C1F001FFFE00FE7F007C7E014197F 9816>I<03E00FF81FFC3C1E780E7007E007FFFFFFFFFFFFE000E000700778073C0F1FFE 0FFC03F010127D9116>I<7E0000FE00007E00000E00000E00000E00000E00000E3C000E FE000FFF000F87800F03800E03800E03800E03800E03800E03800E03800E03800E03800E 03800E03807FC7F0FFE7F87FC7F01519809816>104 D<018003C003C001800000000000 0000007FC07FC07FC001C001C001C001C001C001C001C001C001C001C001C001C07FFFFF FF7FFF101A7D9916>I109 D<7E3C00FEFE007FFF000F87800F03800E03800E03800E03800E03800E03800E03800E03 800E03800E03800E03807FC7F0FFE7F87FC7F01512809116>I<03E0000FF8001FFC003C 1E00780F00700700E00380E00380E00380E00380E00380F00780700700780F003C1E001F FC000FF80003E00011127E9116>I<7E3E00FEFF007FFF800F83C00F00E00E00E00E0070 0E00700E00700E00700E00700E00700E00E00F01E00F83C00FFF800EFF000E3C000E0000 0E00000E00000E00000E00000E00007FC000FFE0007FC000141B809116>I<0FEC3FFC7F FCF03CE01CE01C70007F801FF007F8003C600EE00EF00EF81EFFFCFFF8C7E00F127D9116 >115 D<0300000700000700000700000700007FFF00FFFF00FFFF000700000700000700 0007000007000007000007000007010007038007038007038007870003FE0001FC0000F8 0011177F9616>I<7E1F80FE3F807E1F800E03800E03800E03800E03800E03800E03800E 03800E03800E03800E03800E03800E0F800FFFF007FBF803E3F01512809116>I<7F1FC0 FF9FE07F1FC01C07000E07000E0E000E0E00070E00071C00071C00039C00039C00039800 01B80001B80000F00000F00000F00000E00000E00000E00001C00079C0007BC0007F8000 3F00003C0000131B7F9116>121 D<3FFFC07FFFC07FFFC0700780700F00701E00003C00 00780001F00003E0000780000F00001E01C03C01C07801C0FFFFC0FFFFC0FFFFC012127F 9116>I E /Fo 47 122 df<0001FC000703000C03001C07001C03001800003800003800 00380000380000700007FFFC00701C00701C00701C00E03800E03800E03800E03800E070 01C07001C07001C07001C0E201C0E201C0E20380E4038064038038038000030000070000 060000C60000E40000CC00007000001825819C17>12 D45 D<3078F06005047C830D>I<00020006000C001C007C039C003800380038003800700070 0070007000E000E000E000E001C001C001C001C003800380038003800780FFF00F1C7C9B 15>49 D<003E0000C1800101800200C00400C00440C00841C00841C00841C00883800703 80000700000E0001F800003800000C00000C00000E00000E00000E00000E00700E00E01C 00801C0080380080300040600021C0001F0000121D7C9B15>51 D<00C06000FFC001FF80 01FE00010000010000020000020000020000020000047800058C00060600040600080600 000700000700000600000E00000E00700E00700C00E01C00801800803800403000406000 21C0001F0000131D7C9B15>53 D<000F0000308000C0800183800383800300000600000E 00000C00001C00001CF0003B18003C0C00380C00780C00700E00700E00700E00601C00E0 1C00E01C00E01C00E03800E03800E0700060600060C0002180001E0000111D7B9B15>I< 003C0000C6000183000303000603000E03000C03801C03801C03001C0300380700380700 380700380F00380E00181E00181E000C6C00079C00001C00001800003800003000006000 E0C000E0C0008180008600007C0000111D7B9B15>57 D<060F0F06000000000000000000 003078F06008127C910D>I<000018000000180000003800000038000000780000007800 0000B8000001B800000138000002380000023C0000041C0000041C0000081C0000181C00 00101C0000201C0000201C00007FFC0000401C0000801C0001801C0001001C0002001C00 02001C0004000E000C000E001C001E00FF00FFC01A1D7E9C1F>65 D<01FFFE00003C0780003803C0003801C0003801C0003801C0007001C0007003C0007003 C00070078000E0070000E00E0000E03C0000FFF80001C01C0001C00E0001C00F0001C00F 0003800F0003800F0003800F0003800F0007001E0007001C0007003C00070078000E01E0 00FFFF80001A1C7D9B1D>I<0003F020001E0C60003002E000E003C001C001C0038001C0 070000C00E0000801E0000801C0000803C0000803C000000780000007800000078000000 F0000000F0000000F0000000F0000000F0000400F0000400F0000400F000080070000800 7000100038002000180040000C0180000706000001F800001B1E7A9C1E>I<01FFFE0000 3C0780003801C0003801C0003800E0003800E0007000F00070007000700070007000F000 E000F000E000F000E000F000E000F001C001E001C001E001C001E001C001C0038003C003 800380038007800380070007000E0007001C0007003800070070000E01C000FFFF00001C 1C7D9B1F>I<01FFFFE0003C00E000380060003800400038004000380040007000400070 0040007020400070200000E0400000E0400000E0C00000FFC00001C0800001C0800001C0 800001C0800003810100038001000380020003800200070004000700040007000C000700 18000E007800FFFFF0001B1C7D9B1C>I<01FFFFC0003C01C0003800C000380080003800 80003800800070008000700080007020800070200000E0400000E0400000E0C00000FFC0 0001C0800001C0800001C0800001C0800003810000038000000380000003800000070000 000700000007000000070000000F000000FFF000001A1C7D9B1B>I<01FFC0003C000038 0000380000380000380000700000700000700000700000E00000E00000E00000E00001C0 0001C00001C00001C0000380000380000380000380000700000700000700000700000F00 00FFE000121C7E9B10>73 D<007FF0000780000700000700000700000700000E00000E00 000E00000E00001C00001C00001C00001C00003800003800003800003800007000007000 00700000700060E000E0E000C0C00081C0008380004700003C0000141D7B9B16>I<01FF E0003C0000380000380000380000380000700000700000700000700000E00000E00000E0 0000E00001C00001C00001C00001C0000380080380080380080380100700100700300700 600700E00E03C0FFFFC0151C7D9B1A>76 D<01FE0007F8003E000780002E000F00002E00 1700002E001700002E002700004E002E00004E004E00004E004E00004E008E00008E011C 00008E011C00008E021C00008E021C000107043800010704380001070838000107103800 0207107000020720700002072070000207407000040740E000040780E000040700E0000C 0700E0001C0601E000FF861FFC00251C7D9B25>I<01FC03FE001C0070003C0060002E00 40002E0040002E0040004700800047008000470080004380800083810000838100008181 000081C1000101C2000101C2000100E2000100E2000200E4000200740002007400020074 000400380004003800040038000C0018001C001000FF8010001F1C7D9B1F>I<01FFFC00 003C070000380380003801C0003801C0003801C0007003C0007003C0007003C000700380 00E0078000E0070000E00E0000E0380001FFE00001C0000001C0000001C0000003800000 038000000380000003800000070000000700000007000000070000000F000000FFE00000 1A1C7D9B1C>80 D<01FFF800003C0E000038070000380380003803800038038000700780 007007800070078000700F0000E00E0000E01C0000E0700000FFC00001C0C00001C06000 01C0700001C07000038070000380700003807000038070000700F0000700F0400700F040 0700F0800F007880FFE0790000001E001A1D7D9B1E>82 D<000F8400304C00403C008018 01001803001803001806001006001006000007000007000003E00003FC0001FF00007F80 0007C00001C00001C00000C00000C02000C02000C0600180600180600300600200F00400 CC180083E000161E7D9C17>I<1FFFFFC01C0701C0300E00C0200E0080600E0080400E00 80401C0080801C0080801C0080001C000000380000003800000038000000380000007000 0000700000007000000070000000E0000000E0000000E0000000E0000001C0000001C000 0001C0000001C0000003C000007FFE00001A1C799B1E>I<03CC063C0C3C181C38383038 70387038E070E070E070E070E0E2C0E2C0E261E462643C380F127B9115>97 D<3F00070007000E000E000E000E001C001C001C001C0039C03E60383038307038703870 387038E070E070E070E060E0E0C0C0C1C0618063003C000D1D7B9C13>I<01F007080C08 181C3838300070007000E000E000E000E000E000E008E010602030C01F000E127B9113> I<001F80000380000380000700000700000700000700000E00000E00000E00000E0003DC 00063C000C3C00181C00383800303800703800703800E07000E07000E07000E07000E0E2 00C0E200C0E20061E4006264003C3800111D7B9C15>I<01E007100C1018083810701070 607F80E000E000E000E000E000E0086010602030C01F000D127B9113>I<0003C0000670 000C70001C60001C00001C0000380000380000380000380000380003FF80007000007000 00700000700000700000E00000E00000E00000E00000E00001C00001C00001C00001C000 01C000038000038000038000030000030000070000C60000E60000CC0000780000142581 9C0D>I<00F3018F030F06070E0E0C0E1C0E1C0E381C381C381C381C3838303830381878 18F00F700070007000E000E0C0C0E1C0C3007E00101A7D9113>I<0FC00001C00001C000 0380000380000380000380000700000700000700000700000E78000E8C000F0E000E0E00 1C0E001C0E001C0E001C0E00381C00381C00381C00383800703880703880707080707100 E03200601C00111D7D9C15>I<01800380010000000000000000000000000000001C0026 00470047008E008E000E001C001C001C0038003800710071007100720072003C00091C7C 9B0D>I<0FC00001C00001C0000380000380000380000380000700000700000700000700 000E0F000E11000E23800E43801C83001C80001D00001E00003F800039C00038E00038E0 0070E20070E20070E20070E400E06400603800111D7D9C13>107 D<1F800380038007000700070007000E000E000E000E001C001C001C001C003800380038 0038007000700070007000E400E400E400E40068003800091D7C9C0B>I<3C1E07802663 18C04683A0E04703C0E08E0380E08E0380E00E0380E00E0380E01C0701C01C0701C01C07 01C01C070380380E0388380E0388380E0708380E0710701C0320300C01C01D127C9122> I<3C3C002646004687004707008E07008E07000E07000E07001C0E001C0E001C0E001C1C 00381C40381C40383840383880701900300E0012127C9117>I<01E007180C0C180C380C 300E700E700EE01CE01CE01CE018E038E030E06060C031801E000F127B9115>I<078700 04D98008E0C008E0C011C0E011C0E001C0E001C0E00381C00381C00381C0038180070380 0703000707000706000E8C000E70000E00000E00001C00001C00001C00001C00003C0000 FF8000131A7F9115>I<3C3C26C2468747078E068E000E000E001C001C001C001C003800 3800380038007000300010127C9112>114 D<01F006080C080C1C18181C001F001FC00F F007F0007800386030E030C030806060C01F000E127D9111>I<00C001C001C001C00380 038003800380FFE00700070007000E000E000E000E001C001C001C001C00384038403840 388019000E000B1A7D990E>I<1E0300270700470700470700870E00870E000E0E000E0E 001C1C001C1C001C1C001C1C003838803838801838801839001C5900078E0011127C9116 >I<1E06270E470E4706870287020E020E021C041C041C041C0818083808181018200C40 07800F127C9113>I<1E01832703874703874703838707018707010E07010E07011C0E02 1C0E021C0E021C0E04180C04181C04181C081C1C100C263007C3C018127C911C>I<070E 0019910010E38020E38041C30041C00001C00001C0000380000380000380000380000702 00670200E70400CB04008B080070F00011127D9113>I<1E03270747074707870E870E0E 0E0E0E1C1C1C1C1C1C1C1C38383838183818381C7007F00070007000E0E0C0E1C0818047 003C00101A7C9114>I E /Fp 84 125 df6 D<007E1F0001C1B1800303E3C00703C3C00E03C1800E01C0000E01C0000E01C0000E01C0 000E01C0000E01C000FFFFFC000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0 000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0000E01C0 000E01C0007F87FC001A1D809C18>11 D<007E0001C1800301800703C00E03C00E01800E 00000E00000E00000E00000E0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8151D809C 17>I<007FC001C1C00303C00703C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C07FCFF8151D809C17>I<003F07E00001C09C180003 80F018000701F03C000E01E03C000E00E018000E00E000000E00E000000E00E000000E00 E000000E00E00000FFFFFFFC000E00E01C000E00E01C000E00E01C000E00E01C000E00E0 1C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C000E00E01C 000E00E01C000E00E01C000E00E01C000E00E01C007FC7FCFF80211D809C23>I<6060F0 F0F8F86868080808080808101010102020404080800D0C7F9C15>34 D<00E0000001900000030800000308000007080000070800000708000007080000071000 0007100000072000000740000003C03FE003800F00038006000380040005C0040009C008 0010E0100030E010006070200060702000E0384000E03C4000E01C8000E00F0020E00700 20700780403009C0401830E18007C03E001B1F7E9D20>38 D<60F0F86808080810102040 80050C7C9C0C>I<004000800100020006000C000C001800180030003000700060006000 6000E000E000E000E000E000E000E000E000E000E000E000E00060006000600070003000 3000180018000C000C00060002000100008000400A2A7D9E10>I<800040002000100018 000C000C000600060003000300038001800180018001C001C001C001C001C001C001C001 C001C001C001C001C0018001800180038003000300060006000C000C0018001000200040 0080000A2A7E9E10>I<0006000000060000000600000006000000060000000600000006 0000000600000006000000060000000600000006000000060000FFFFFFE0FFFFFFE00006 000000060000000600000006000000060000000600000006000000060000000600000006 00000006000000060000000600001B1C7E9720>43 D<60F0F0701010101020204080040C 7C830C>II<60F0F06004047C830C>I<00010003000600060006 000C000C000C0018001800180030003000300060006000C000C000C00180018001800300 03000300060006000C000C000C00180018001800300030003000600060006000C000C000 10297E9E15>I<03C00C301818300C300C700E60066006E007E007E007E007E007E007E0 07E007E007E007E007E007E00760066006700E300C300C18180C3007E0101D7E9B15>I< 030007003F00C70007000700070007000700070007000700070007000700070007000700 070007000700070007000700070007000F80FFF80D1C7C9B15>I<07C01830201C400C40 0EF00FF80FF807F8077007000F000E000E001C001C00380070006000C00180030006010C 01180110023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C781E780E781E381E001C 001C00180030006007E00030001C001C000E000F000F700FF80FF80FF80FF00E401C201C 183007E0101D7E9B15>I<000C00000C00001C00003C00003C00005C0000DC00009C0001 1C00031C00021C00041C000C1C00081C00101C00301C00201C00401C00C01C00FFFFC000 1C00001C00001C00001C00001C00001C00001C0001FFC0121C7F9B15>I<300C3FF83FF0 3FC020002000200020002000200023E024302818301C200E000E000F000F000F600FF00F F00FF00F800E401E401C2038187007C0101D7E9B15>I<00F0030C06040C0E181E301E30 0C700070006000E3E0E430E818F00CF00EE006E007E007E007E007E00760076007700630 0E300C18180C3003E0101D7E9B15>I<4000007FFF807FFF007FFF004002008004008004 0080080000100000100000200000600000400000C00000C00001C0000180000180000380 00038000038000038000078000078000078000078000078000078000030000111D7E9B15 >I<03E00C301008200C20066006600660067006780C3E083FB01FE007F007F818FC307E 601E600FC007C003C003C003C00360026004300C1C1007E0101D7E9B15>I<03C00C3018 18300C700C600EE006E006E007E007E007E007E0076007700F300F18170C2707C7000600 06000E300C780C78187010203030C00F80101D7E9B15>I<60F0F0600000000000000000 000060F0F06004127C910C>I<60F0F0600000000000000000000060F0F0701010101020 204080041A7C910C>I<7FFFFFC0FFFFFFE0000000000000000000000000000000000000 0000000000000000000000000000FFFFFFE07FFFFFC01B0C7E8F20>61 D<000600000006000000060000000F0000000F0000000F00000017800000178000001780 000023C0000023C0000023C0000041E0000041E0000041E0000080F0000080F0000180F8 000100780001FFF80003007C0002003C0002003C0006003E0004001E0004001E000C001F 001E001F00FF80FFF01C1D7F9C1F>65 DI< 001F808000E0618001801980070007800E0003801C0003801C0001803800018078000080 7800008070000080F0000000F0000000F0000000F0000000F0000000F0000000F0000000 F0000000700000807800008078000080380000801C0001001C0001000E00020007000400 0180080000E03000001FC000191E7E9C1E>IIII<001F8080 00E0618001801980070007800E0003801C0003801C000180380001807800008078000080 70000080F0000000F0000000F0000000F0000000F0000000F0000000F000FFF0F0000F80 700007807800078078000780380007801C0007801C0007800E00078007000B8001801180 00E06080001F80001C1E7E9C21>III<1FFF00F8007800780078007800780078007800 78007800780078007800780078007800780078007800787078F878F878F878F0F040E021 C01F00101D7F9B15>IIIII<003F800000E0E0000380380007001C000E00 0E001C0007003C00078038000380780003C0780003C0700001C0F00001E0F00001E0F000 01E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0780003C03800 03803C0007801C0007000E000E0007001C000380380000E0E000003F80001B1E7E9C20> II82 D<07E0801C1980300580700380600180E00180E00080E00080E00080F00000F800007C00 007FC0003FF8001FFE0007FF0000FF80000F800007C00003C00001C08001C08001C08001 C0C00180C00180E00300D00200CC0C0083F800121E7E9C17>I<7FFFFFC0700F01C0600F 00C0400F0040400F0040C00F0020800F0020800F0020800F0020000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000001F800003FFFC001B1C7F9B1E> IIII89 D<7FFFF07C01F07001E06003C06003C0400780400F80 400F00401E00001E00003C00007C0000780000F00000F00001E00003E00003C010078010 0780100F00101F00301E00203C00203C00607800E0F803E0FFFFE0141C7E9B19>II<08081010202040404040808080808080B0B0F8F8787830300D0C 7A9C15>II<0C0012002100408080400A057B9B15>I<1FC000 307000783800781C00301C00001C00001C0001FC000F1C00381C00701C00601C00E01C40 E01C40E01C40603C40304E801F870012127E9115>97 DI<07E00C301878307870306000E000E000E000E000E000E000600070 04300418080C3007C00E127E9112>I<003F000007000007000007000007000007000007 0000070000070000070000070003E7000C1700180F00300700700700600700E00700E007 00E00700E00700E00700E00700600700700700300700180F000C370007C7E0131D7E9C17 >I<03E00C301818300C700E6006E006FFFEE000E000E000E00060007002300218040C18 03E00F127F9112>I<00F8018C071E061E0E0C0E000E000E000E000E000E00FFE00E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E007FE00F1D809C0D >I<00038003C4C00C38C01C3880181800381C00381C00381C00381C001818001C38000C 300013C0001000003000001800001FF8001FFF001FFF803003806001C0C000C0C000C0C0 00C06001803003001C0E0007F800121C7F9215>II<18003C003C0018000000000000000000000000000000FC001C001C001C 001C001C001C001C001C001C001C001C001C001C001C001C001C00FF80091D7F9C0C>I< 00C001E001E000C000000000000000000000000000000FE000E000E000E000E000E000E0 00E000E000E000E000E000E000E000E000E000E000E000E000E000E060E0F0C0F1C06180 3E000B25839C0D>IIIII<03F0000E1C00180600300300700380600180E001C0E001C0E001C0E001C0E001C0E0 01C06001807003803003001806000E1C0003F00012127F9115>II<03C1000C3300180B00300F00700700700700E00700E00700E00700E00700E007 00E00700600700700700300F00180F000C370007C7000007000007000007000007000007 00000700000700003FE0131A7E9116>II<1F9030704030C010C010E010 F8007F803FE00FF000F880388018C018C018E010D0608FC00D127F9110>I<0400040004 0004000C000C001C003C00FFE01C001C001C001C001C001C001C001C001C001C101C101C 101C101C100C100E2003C00C1A7F9910>IIII<7F8FF00F03800F030007020003840001C80001D80000F00000700000780000F800 009C00010E00020E000607000403801E07C0FF0FF81512809116>II<7FFC70386038407040F040E041C003C0038007000F040E041C043C0C380870 087038FFF80E127F9112>III E /Fq 44 123 df<003FC00001F0300003C0380007C07C000F807C000F807C000F803800 0F8000000F8000000F8000000F800000FFFFFC00FFFFFC000F807C000F807C000F807C00 0F807C000F807C000F807C000F807C000F807C000F807C000F807C000F807C000F807C00 0F807C000F807C007FE1FF807FE1FF80191D809C1B>12 D45 D<78FCFCFCFC7806067D850D>I<00600001E0000FE000FFE000F3E00003E00003 E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003 E00003E00003E00003E00003E00003E00003E0007FFF807FFF80111B7D9A18>49 D<07F8001FFE00383F80780FC0FC07C0FC07E0FC03E0FC03E07803E00007E00007C00007 C0000F80001F00001E0000380000700000E0000180600300600600600800E01FFFC03FFF C07FFFC0FFFFC0FFFFC0131B7E9A18>I<03F8001FFE003C1F003C0F807C07C07E07C07C 07C03807C0000F80000F80001E00003C0003F800001E00000F800007C00007C00007E030 07E07807E0FC07E0FC07E0FC07C0780F80781F001FFE0007F800131B7E9A18>I<000180 000380000780000F80001F80003F80006F8000CF80008F80018F80030F80060F800C0F80 180F80300F80600F80C00F80FFFFF8FFFFF8000F80000F80000F80000F80000F80000F80 01FFF801FFF8151B7F9A18>I<78FCFCFCFC7800000000000078FCFCFCFC7806127D910D> 58 D<00038000000380000007C0000007C0000007C000000FE000000FE000001FF00000 1BF000001BF0000031F8000031F8000061FC000060FC0000E0FE0000C07E0000C07E0001 803F0001FFFF0003FFFF8003001F8003001F8006000FC006000FC00E000FE00C0007E0FF C07FFEFFC07FFE1F1C7E9B24>65 DI<001FE02000FFF8E003F8 0FE007C003E00F8001E01F0000E03E0000E03E0000607E0000607C000060FC000000FC00 0000FC000000FC000000FC000000FC000000FC000000FC0000007C0000607E0000603E00 00603E0000C01F0000C00F80018007C0030003F80E0000FFFC00001FE0001B1C7D9B22> II70 D<000FF008007FFE3801FC07F8 07E001F80F8000781F0000783F0000383E0000387E0000187C000018FC000000FC000000 FC000000FC000000FC000000FC000000FC007FFFFC007FFF7C0001F87E0001F83E0001F8 3F0001F81F0001F80F8001F807E001F801FC07F8007FFE78000FF818201C7D9B26>I73 D<07FFF007FFF0001F80 001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80001F80 001F80001F80001F80001F80001F80301F80781F80FC1F80FC1F80FC1F00783E00387C00 0FF000141C7F9B19>I77 D82 D<7FFFFC7FFFFC7E01F87803F87003F0E007E0 E007E0C00FC0C01FC0C01F80003F00007F00007E0000FC0000FC0001F80003F80603F006 07E0060FE0060FC00E1F800E1F801C3F001C7F003C7E00FCFFFFFCFFFFFC171C7D9B1D> 90 D<020007000F801DC078F0E03840100D077B9C18>94 D<0FF8001C1E003E0F803E07 803E07C01C07C00007C0007FC007E7C01F07C03C07C07C07C0F807C0F807C0F807C0780B C03E13F80FE1F815127F9117>97 DI<03FC000E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F800 007800007801803C01801C03000E0E0003F80011127E9115>I<000FF0000FF00001F000 01F00001F00001F00001F00001F00001F00001F00001F001F9F00F07F01C03F03C01F078 01F07801F0F801F0F801F0F801F0F801F0F801F0F801F07801F07801F03C01F01C03F00F 0FFE03F9FE171D7E9C1B>I<01FC000F07001C03803C01C07801C07801E0F801E0F801E0 FFFFE0F80000F80000F800007800007C00603C00601E00C00F038001FC0013127F9116> I<007F0001E38003C7C00787C00F87C00F83800F80000F80000F80000F80000F8000FFF8 00FFF8000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80 000F80000F80000F80007FF8007FF800121D809C0F>I<03F8F00E0F381E0F381C07303C 07803C07803C07803C07801C07001E0F000E0E001BF8001000001800001800001FFF001F FFC00FFFE01FFFF07801F8F00078F00078F000787000707800F01E03C007FF00151B7F91 18>II<1E003F003F003F003F001E 00000000000000000000000000FF00FF001F001F001F001F001F001F001F001F001F001F 001F001F001F001F00FFE0FFE00B1E7F9D0E>I107 DIII<01FC000F07801C01C03C01E07800F07800F0F800F8 F800F8F800F8F800F8F800F8F800F87800F07800F03C01E01E03C00F078001FC0015127F 9118>II114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01C E01CE018F830CFC00E127E9113>I<0300030003000300070007000F000F003FFCFFFC1F 001F001F001F001F001F001F001F001F001F0C1F0C1F0C1F0C0F08079803F00E1A7F9913 >IIIIII<3FFF803C1F00303F00303E 00607C0060FC0060F80001F00003F00007E00007C1800F81801F81801F03803E03007E07 007C0F00FFFF0011127F9115>I E /Fr 21 119 df69 D77 D<001FF0018000FFFF038003FFFFC78007F00FFF800F8001FF801F00007F 803F00001F803E00000F807E00000F807E00000780FE00000780FE00000780FE00000380 FF00000380FF00000380FF80000000FFE00000007FFC0000007FFFE000007FFFFE00003F FFFFC0001FFFFFF0001FFFFFF8000FFFFFFC0003FFFFFE0001FFFFFF00007FFFFF80001F FFFF800000FFFFC0000007FFC0000000FFE00000003FE00000003FE00000001FE0600000 1FE0E000000FE0E000000FE0E000000FE0E000000FC0F000000FC0F000000FC0F800001F 80FC00001F80FF00003F00FFC0007E00FFFC01FC00F1FFFFF800E03FFFE000C007FF0000 23317BB02E>83 D<007FF8000003FFFF000007FFFFC0000FE01FE0001FF007F0001FF003 F8001FF003FC001FF001FE000FE001FE0007C001FE00010001FE00000001FE00000001FE 000001FFFE00003FFFFE0001FFF1FE0007FE01FE000FF001FE001FC001FE003F8001FE00 7F8001FE00FF0001FE00FF0001FE00FF0001FE00FF0001FE00FF0003FE007F8003FE007F C00EFE003FF03CFF000FFFF87FF807FFF03FF800FF800FF825207E9F28>97 D<0007FF00007FFFE000FFFFF003FC03F807F007FC0FE007FC1FE007FC3FC007FC3FC003 F87FC001F07F8000407F800000FF800000FF800000FF800000FF800000FF800000FF8000 00FF800000FF8000007F8000007FC000007FC000003FC0000E3FE0000E1FE0001C0FF000 1C07F8007803FF01F000FFFFE0007FFF800007FC001F207D9F25>99 D<00000007E0000003FFE0000003FFE0000003FFE00000003FE00000001FE00000001FE0 0000001FE00000001FE00000001FE00000001FE00000001FE00000001FE00000001FE000 00001FE00000001FE00000001FE00000001FE0000FF81FE0007FFF1FE001FFFFDFE003FE 03FFE007F800FFE00FE0003FE01FE0001FE03FC0001FE03FC0001FE07F80001FE07F8000 1FE07F80001FE0FF80001FE0FF80001FE0FF80001FE0FF80001FE0FF80001FE0FF80001F E0FF80001FE0FF80001FE07F80001FE07F80001FE07F80001FE03FC0001FE03FC0001FE0 1FC0003FE00FE0007FE007F001FFE003FC07DFF001FFFF9FFF007FFE1FFF000FF01FFF28 327DB12E>I<0007FC0000003FFF800000FFFFE00003FC07F00007F801F8000FE000FC00 1FE0007E003FC0007E003FC0003F007FC0003F007F80003F007F80003F80FF80003F80FF 80003F80FFFFFFFF80FFFFFFFF80FFFFFFFF80FF80000000FF80000000FF800000007F80 0000007F800000003FC00000003FC00003801FC00003801FE00007800FF0000F0007F800 1E0003FE00FC0000FFFFF800003FFFE0000003FF000021207E9F26>I<0000FF000007FF C0001FFFE0003FC7F0007F0FF800FE0FF801FE0FF801FC0FF803FC07F003FC03E003FC01 C003FC000003FC000003FC000003FC000003FC000003FC000003FC0000FFFFF800FFFFF8 00FFFFF80003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC00 0003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC00 0003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC000003FC00 007FFFF0007FFFF0007FFFF0001D327EB119>I<001FF007E000FFFE3FF001FFFF7FF807 F83FF1F80FE00FE1F80FE00FE0F01FC007F0601FC007F0003FC007F8003FC007F8003FC0 07F8003FC007F8003FC007F8001FC007F0001FC007F0000FE00FE0000FE00FE00007F83F C00007FFFF000006FFFE00000E1FF000000E000000001E000000001E000000001F000000 001F800000001FFFFFC0000FFFFFF8000FFFFFFE0007FFFFFF0003FFFFFF8007FFFFFFC0 1FFFFFFFE03F00007FE07E00000FF0FC000007F0FC000003F0FC000003F0FC000003F0FC 000003F07E000007E03F00000FC01FC0003F800FF801FF0007FFFFFE0000FFFFF000001F FF8000252F7E9F29>I<01F800000000FFF800000000FFF800000000FFF8000000000FF8 0000000007F80000000007F80000000007F80000000007F80000000007F80000000007F8 0000000007F80000000007F80000000007F80000000007F80000000007F80000000007F8 0000000007F80000000007F807F8000007F83FFF000007F87FFF800007F8F03FC00007F9 C01FE00007FB000FE00007FE000FF00007FE000FF00007FC000FF00007FC000FF00007F8 000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8 000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8 000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8 000FF000FFFFC1FFFF80FFFFC1FFFF80FFFFC1FFFF8029327DB12E>I<03C0000FF0000F F0001FF8001FF8001FFC001FF8001FF8000FF0000FF00003C00000000000000000000000 000000000000000000000000000001F800FFF800FFF800FFF8000FF80007F80007F80007 F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007 F80007F80007F80007F80007F80007F80007F80007F80007F80007F800FFFF80FFFF80FF FF8011337DB217>I<01F800FFF800FFF800FFF8000FF80007F80007F80007F80007F800 07F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800 07F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800 07F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F800 07F80007F800FFFFC0FFFFC0FFFFC012327DB117>108 D<03F007F8000FF000FFF03FFF 007FFE00FFF07FFF80FFFF00FFF0F03FC1E07F800FF1C01FE3803FC007F3000FE6001FC0 07F6000FFC001FE007FE000FFC001FE007FC000FF8001FE007FC000FF8001FE007F8000F F0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE0 07F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000F F0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE0 07F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000FF0001FE007F8000F F0001FE0FFFFC1FFFF83FFFFFFFFC1FFFF83FFFFFFFFC1FFFF83FFFF40207D9F45>I<03 F007F80000FFF03FFF0000FFF07FFF8000FFF0F03FC0000FF1C01FE00007F3000FE00007 F6000FF00007FE000FF00007FC000FF00007FC000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF000FFFFC1FFFF80FF FFC1FFFF80FFFFC1FFFF8029207D9F2E>I<0007FE0000003FFFC00000FFFFF00003FC03 FC0007F000FE000FE0007F001FC0003F803FC0003FC03FC0003FC07F80001FE07F80001F E07F80001FE0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF0FF80001FF0 FF80001FF0FF80001FF07F80001FE07F80001FE07F80001FE03FC0003FC03FC0003FC01F E0007F800FE0007F0007F801FE0003FE07FC0001FFFFF800003FFFC0000007FE00002420 7E9F29>I<01F80FF000FFF87FFE00FFF9FFFF80FFFFE07FC00FFF001FE007FE000FF007 F80007F807F80007FC07F80003FC07F80003FE07F80003FE07F80001FE07F80001FF07F8 0001FF07F80001FF07F80001FF07F80001FF07F80001FF07F80001FF07F80001FF07F800 01FE07F80003FE07F80003FE07F80003FC07F80007FC07FC0007F807FE000FF007FF001F E007FBE07FC007F9FFFF0007F87FFE0007F81FE00007F800000007F800000007F8000000 07F800000007F800000007F800000007F800000007F800000007F800000007F800000007 F8000000FFFFC00000FFFFC00000FFFFC00000282E7E9F2E>I<03F03F00FFF07FC0FFF1 FFE0FFF3C7F00FF38FF807F70FF807F60FF807FE0FF807FC07F007FC03E007FC008007F8 000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F8 000007F8000007F8000007F8000007F8000007F8000007F8000007F8000007F80000FFFF E000FFFFE000FFFFE0001D207E9F22>114 D<00FF870007FFEF001FFFFF003F007F003C 001F0078000F00F8000700F8000700F8000700FC000700FF000000FFF800007FFFC0003F FFF0003FFFFC000FFFFE0007FFFF0001FFFF80001FFF800000FFC000001FC060000FC0E0 0007C0E00007C0F00007C0F8000780F8000F80FE000F00FF803E00FFFFFC00F3FFF800C0 7FC0001A207D9F21>I<00380000380000380000380000380000780000780000780000F8 0000F80001F80003F80007F8001FF800FFFFFEFFFFFEFFFFFE07F80007F80007F80007F8 0007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F80007F8 0007F80707F80707F80707F80707F80707F80707F80703F80E03FC0E01FE1C00FFF8007F F0000FE0182E7EAD20>I<01F80003F000FFF801FFF000FFF801FFF000FFF801FFF0000F F8001FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007F8000FF00007 F8000FF00007F8000FF00007F8001FF00007F8001FF00003F8003FF00003F8006FF00001 FE03CFF80000FFFF8FFF80007FFF0FFF80000FFC0FFF8029207D9F2E>II E end TeXDict begin 1 0 bop 225 317 1500 17 v 311 441 a Fr(Sup)r(ervised)26 b(learning)h(from)g(incomplete)515 524 y(data)g(via)g(an)h(EM)g (approac)n(h)p 225 605 1500 5 v 530 756 a Fq(Zoubin)13 b(Ghahramani)h Fp(and)h Fq(Mic)o(hael)g(I.)h(Jordan)588 802 y Fp(Departmen)o(t)d(of)g(Brain)h(&)g(Cognitiv)o(e)f(Sciences)628 847 y(Massac)o(h)o(usetts)j(Institute)f(of)e(T)m(ec)o(hnology)770 893 y(Cam)o(bridge,)f(MA)i(02139)225 17 y(In)i(Co)o(w)o(an,)f(J.D.,)g (T)m(esauro,)i(G.,)e(and)h(Alsp)q(ector,)h(J.)f(\(eds.\).)25 b Fo(A)n(dvanc)n(es)17 b(in)g(Neur)n(al)f(Infor-)225 63 y(mation)h(Pr)n(o)n(c)n(essing)g(Systems)h(6)p Fp(.)25 b(Morgan)16 b(Kaufmann)e(Publishers,)k(San)e(F)m(rancisco,)g(CA,)225 109 y(1994.)h(Email)11 b(to:)18 b Fn(zoubin@psyche.mit.e)o(du)p Fp(.)868 1077 y Fm(Abstract)374 1173 y Fp(Real-w)o(orld)d(learning)g (tasks)i(ma)o(y)d(in)o(v)o(olv)o(e)h(high-dimensional)e(data)i(sets)374 1219 y(with)h(arbitrary)f(patterns)h(of)f(missing)f(data.)22 b(In)16 b(this)f(pap)q(er)h(w)o(e)g(presen)o(t)374 1264 y(a)f(framew)o(ork)f(based)i(on)f(maxim)n(um)c(lik)o(eliho)q(o)q(d)i (densit)o(y)i(estimation)f(for)374 1310 y(learning)g(from)f(suc)o(h)i (data)f(sets.)21 b(W)m(e)14 b(use)h(mixture)e(mo)q(dels)g(for)h(the)h (den-)374 1356 y(sit)o(y)h(estimates)g(and)f(mak)o(e)g(t)o(w)o(o)g (distinct)h(app)q(eals)g(to)g(the)g(Exp)q(ectation-)374 1401 y(Maximization)e(\(EM\))k(principle)e(\(Dempster)h(et)h(al.,)e (1977\))g(in)g(deriving)374 1447 y(a)f(learning)f(algorithm|EM)e(is)i (used)i(b)q(oth)f(for)f(the)i(estimation)d(of)h(mix-)374 1493 y(ture)20 b(comp)q(onen)o(ts)f(and)f(for)h(coping)f(with)h (missing)e(data.)33 b(The)19 b(result-)374 1538 y(ing)e(algorithm)e(is) i(applicable)f(to)h(a)g(wide)h(range)f(of)g(sup)q(ervised)i(as)e(w)o (ell)374 1584 y(as)i(unsup)q(ervised)h(learning)d(problems.)31 b(Results)18 b(from)f(a)h(classi\014cation)374 1630 y(b)q(enc)o (hmark|the)c(iris)g(data)f(set|are)i(presen)o(ted.)225 1764 y Fm(1)56 b(In)n(tro)r(duction)225 1860 y Fp(Adaptiv)o(e)16 b(systems)g(generally)f(op)q(erate)i(in)f(en)o(vironmen)o(ts)f(that)h (are)g(fraugh)o(t)g(with)f(imp)q(er-)225 1905 y(fections;)f (nonetheless)i(they)f(m)o(ust)f(cop)q(e)h(with)f(these)h(imp)q (erfections)f(and)g(learn)h(to)f(extract)225 1951 y(as)19 b(m)o(uc)o(h)f(relev)n(an)o(t)h(information)e(as)i(needed)h(for)f (their)h(particular)e(goals.)33 b(One)20 b(form)e(of)225 1997 y(imp)q(erfection)11 b(is)h(incompleteness)h(in)f(sensing)g (information.)j(Incompleteness)e(can)f(arise)h(ex-)225 2042 y(trinsically)k(from)e(the)k(data)e(generation)h(pro)q(cess)h(and) e(in)o(trinsically)f(from)g(failures)h(of)g(the)225 2088 y(system's)d(sensors.)21 b(F)m(or)13 b(example,)g(an)h(ob)r(ject)h (recognition)f(system)g(m)o(ust)f(b)q(e)i(able)f(to)g(learn)225 2134 y(to)d(classify)g(images)f(with)h(o)q(cclusions,)g(and)h(a)f(rob)q (otic)g(con)o(troller)g(m)o(ust)g(b)q(e)g(able)g(to)h(in)o(tegrate)225 2179 y(m)o(ultiple)g(sensors)j(ev)o(en)g(when)f(only)f(a)h(fraction)f (ma)o(y)f(op)q(erate)j(at)f(an)o(y)f(giv)o(en)h(time.)225 2250 y(In)9 b(this)h(pap)q(er)g(w)o(e)g(presen)o(t)h(a)e(framew)o (ork|deriv)o(ed)f(from)g(parametric)h(statistics|for)g(learn-)p eop 2 1 bop 225 42 a Fp(ing)9 b(from)f(data)i(sets)h(with)e(arbitrary)h (patterns)h(of)f(incompleteness.)16 b(Learning)10 b(in)f(this)h(frame-) 225 87 y(w)o(ork)j(is)f(a)h(classical)f(estimation)g(problem)f (requiring)i(an)f(explicit)h(probabilistic)f(mo)q(del)f(and)225 133 y(an)j(algorithm)e(for)i(estimating)f(the)i(parameters)f(of)g(the)h (mo)q(del.)k(A)14 b(p)q(ossible)h(disadv)n(an)o(tage)225 178 y(of)e(parametric)g(metho)q(ds)g(is)g(their)h(lac)o(k)f(of)f (\015exibilit)o(y)g(when)i(compared)f(with)g(nonparamet-)225 224 y(ric)18 b(metho)q(ds.)31 b(This)18 b(problem,)f(ho)o(w)o(ev)o(er,) i(can)g(b)q(e)f(largely)g(circum)o(v)o(en)o(ted)g(b)o(y)g(the)h(use)g (of)225 270 y(mixture)12 b(mo)q(dels)h(\(McLac)o(hlan)g(and)g(Basford,) g(1988\).)k(Mixture)d(mo)q(dels)e(com)o(bine)g(m)o(uc)o(h)h(of)225 315 y(the)h(\015exibilit)o(y)e(of)i(nonparametric)e(metho)q(ds)i(with)f (certain)h(of)f(the)i(analytic)d(adv)n(an)o(tages)i(of)225 361 y(parametric)f(metho)q(ds.)225 432 y(Mixture)h(mo)q(dels)e(ha)o(v)o (e)h(b)q(een)h(utilized)f(recen)o(tly)h(for)f(sup)q(ervised)i(learning) d(problems)h(in)f(the)225 477 y(form)17 b(of)h(the)i(\\mixtures)e(of)g (exp)q(erts")j(arc)o(hitecture)f(\(Jacobs)g(et)g(al.,)e(1991;)i(Jordan) f(and)225 523 y(Jacobs,)d(1994\).)21 b(This)15 b(arc)o(hitecture)i(is)e (a)g(parametric)g(regression)h(mo)q(del)e(with)h(a)g(mo)q(dular)225 569 y(structure)21 b(similar)c(to)i(the)h(nonparametric)e(decision)i (tree)g(and)f(adaptiv)o(e)g(spline)g(mo)q(dels)225 614 y(\(Breiman)14 b(et)i(al.,)d(1984;)h(F)m(riedman,)g(1991\).)20 b(The)c(approac)o(h)f(presen)o(ted)i(here)f(di\013ers)g(from)225 660 y(these)k(regression-based)g(approac)o(hes)f(in)e(that)i(the)f (goal)f(of)h(learning)g(is)g(to)g(estimate)f(the)225 706 y Fo(density)12 b Fp(of)g(the)g(data.)17 b(No)12 b(distinction)f(is)h(made)f(b)q(et)o(w)o(een)i(input)f(and)g(output)g (v)n(ariables;)f(the)225 751 y(join)o(t)k(densit)o(y)h(is)f(estimated)g (and)h(this)g(estimate)f(is)g(then)i(used)f(to)g(form)e(an)h (input/output)225 797 y(map.)27 b(Similar)15 b(approac)o(hes)k(ha)o(v)o (e)e(b)q(een)i(discussed)g(b)o(y)e(Sp)q(ec)o(h)o(t)i(\(1991\))e(and)g (T)m(resp)h(et)g(al.)225 843 y(\(1993\).)c(T)m(o)g(estimate)h(the)g(v)o (ector)h(function)f Fq(y)f Fp(=)g Fl(f)t Fp(\()p Fq(x)p Fp(\))i(the)g(join)o(t)e(densit)o(y)i Fl(P)6 b Fp(\()p Fq(x)p Fl(;)h Fq(y)q Fp(\))14 b(is)h(esti-)225 888 y(mated)h(and,)h (giv)o(en)f(a)g(particular)h(input)f Fq(x)p Fp(,)h(the)h(conditional)d (densit)o(y)i Fl(P)6 b Fp(\()p Fq(y)q Fk(j)p Fq(x)p Fp(\))16 b(is)h(formed.)225 934 y(T)m(o)f(obtain)h(a)f(single)h(estimate)g(of)f Fq(y)i Fp(rather)g(than)f(the)h(full)d(conditional)h(densit)o(y)h(one)h (can)225 980 y(ev)n(aluate)d Fq(^)-25 b(y)12 b Fp(=)g Fl(E)r Fp(\()p Fq(y)q Fk(j)p Fq(x)p Fp(\),)h(the)i(exp)q(ectation)f(of) g Fq(y)g Fp(giv)o(en)g Fq(x)p Fp(.)225 1050 y(The)19 b(densit)o(y-based)g(approac)o(h)f(to)g(learning)f(can)i(b)q(e)f (exploited)g(in)g(sev)o(eral)h(w)o(a)o(ys.)30 b(First,)225 1096 y(ha)o(ving)16 b(an)i(estimate)f(of)f(the)i(join)o(t)f(densit)o(y) h(allo)o(ws)e(for)h(the)h(represen)o(tation)h(of)e(an)o(y)g(rela-)225 1142 y(tion)f(b)q(et)o(w)o(een)h(the)g(v)n(ariables.)24 b(F)m(rom)14 b Fl(P)6 b Fp(\()p Fq(x)p Fl(;)h Fq(y)q Fp(\),)16 b(w)o(e)g(can)h(estimate)f Fq(^)-25 b(y)16 b Fp(=)g Fl(f)t Fp(\()p Fq(x)p Fp(\),)i(the)e(in)o(v)o(erse)226 1187 y Fq(^)-25 b(x)13 b Fp(=)g Fl(f)332 1172 y Fj(\000)p Fi(1)377 1187 y Fp(\()p Fq(y)q Fp(\),)h(or)h(an)o(y)f(other)h(relation) f(b)q(et)o(w)o(een)i(t)o(w)o(o)e(subsets)i(of)e(the)h(elemen)o(ts)g(of) f(the)h(con-)225 1233 y(catenated)g(v)o(ector)g(\()p Fq(x)p Fl(;)7 b Fq(y)q Fp(\).)225 1303 y(Second,)16 b(this)f(densit)o (y-based)h(approac)o(h)f(is)g(applicable)g(b)q(oth)g(to)g(sup)q (ervised)i(learning)d(and)225 1349 y(unsup)q(ervised)k(learning)e(in)g (exactly)g(the)h(same)f(w)o(a)o(y)m(.)24 b(The)17 b(only)e(distinction) h(b)q(et)o(w)o(een)i(su-)225 1395 y(p)q(ervised)g(and)e(unsup)q (ervised)i(learning)e(in)g(this)g(framew)o(ork)f(is)h(whether)i(some)d (p)q(ortion)i(of)225 1440 y(the)d(data)g(v)o(ector)h(is)e(denoted)i(as) f(\\input")f(and)h(another)g(p)q(ortion)g(as)g(\\target".)225 1511 y(Third,)f(as)g(w)o(e)g(discuss)h(in)e(this)i(pap)q(er,)f(the)g (densit)o(y-based)h(approac)o(h)f(deals)g(naturally)f(with)225 1557 y(incomplete)k(data,)g(i.e.)g(missing)e(v)n(alues)j(in)f(the)h (data)f(set.)27 b(This)16 b(is)h(b)q(ecause)h(the)f(problem)225 1602 y(of)c(estimating)e(mixture)h(densities)j(can)e(itself)g(b)q(e)h (view)o(ed)f(as)h(a)f(missing)e(data)i(problem)f(\(the)225 1648 y(\\lab)q(els")d(for)h(the)g(comp)q(onen)o(t)g(densities)g(are)h (missing\))d(and)i(an)g(Exp)q(ectation{Maximization)225 1694 y(\(EM\))15 b(algorithm)d(\(Dempster)j(et)h(al.,)d(1977\))h(can)h (b)q(e)g(dev)o(elop)q(ed)h(to)e(handle)h(b)q(oth)g(kinds)g(of)225 1739 y(missing)d(data.)225 1858 y Fm(2)56 b(Densit)n(y)18 b(estimation)e(using)j(EM)225 1955 y Fp(This)f(section)h(outlines)e (the)i(basic)f(learning)f(algorithm)f(for)h(\014nding)h(the)g(maxim)n (um)c(lik)o(e-)225 2001 y(liho)q(o)q(d)19 b(parameters)h(of)f(a)h (mixture)f(mo)q(del)f(\(Dempster)i(et)h(al.,)e(1977;)j(Duda)d(and)h (Hart,)225 2046 y(1973;)d(No)o(wlan,)f(1991\).)26 b(W)m(e)16 b(assume)g(that)h(the)g(data)g Fk(X)22 b Fp(=)16 b Fk(f)p Fq(x)1272 2052 y Fi(1)1291 2046 y Fl(;)7 b(:)g(:)g(:)e(;)i Fq(x)1409 2052 y Fh(N)1440 2046 y Fk(g)16 b Fp(are)i(generated)225 2092 y(indep)q(enden)o(tly)d(from)d(a)h(mixture)g(densit)o(y)692 2208 y Fl(P)6 b Fp(\()p Fq(x)766 2214 y Fh(i)779 2208 y Fp(\))12 b(=)863 2156 y Fh(M)851 2168 y Fg(X)852 2257 y Fh(j)r Fi(=1)918 2208 y Fl(P)6 b Fp(\()p Fq(x)992 2214 y Fh(i)1005 2208 y Fk(j)p Fl(!)1043 2214 y Fh(j)1060 2208 y Fp(;)h Fl(\022)1098 2214 y Fh(j)1116 2208 y Fp(\))p Fl(P)f Fp(\()p Fl(!)1207 2214 y Fh(j)1224 2208 y Fp(\))p Fl(;)420 b Fp(\(1\))p eop 3 2 bop 225 42 a Fp(where)14 b(eac)o(h)g(comp)q(onen)o(t)f(of)f(the)i (mixture)e(is)h(denoted)h Fl(!)1144 48 y Fh(j)1175 42 y Fp(and)f(parametrized)g(b)o(y)g Fl(\022)1582 48 y Fh(j)1600 42 y Fp(.)18 b(F)m(rom)225 87 y(equation)12 b(\(1\))h(and)f(the)i (indep)q(endence)h(assumption)c(w)o(e)i(see)h(that)e(the)i(log)d(lik)o (eliho)q(o)q(d)g(of)h(the)225 133 y(parameters)i(giv)o(en)f(the)i(data) e(set)i(is)627 229 y Fl(l)q Fp(\()p Fl(\022)q Fk(jX)6 b Fp(\))12 b(=)811 177 y Fh(N)795 190 y Fg(X)799 278 y Fh(i)p Fi(=1)862 229 y Fp(log)935 177 y Fh(M)923 190 y Fg(X)924 278 y Fh(j)r Fi(=1)990 229 y Fl(P)6 b Fp(\()p Fq(x)1064 235 y Fh(i)1077 229 y Fk(j)p Fl(!)1115 235 y Fh(j)1132 229 y Fp(;)h Fl(\022)1170 235 y Fh(j)1188 229 y Fp(\))p Fl(P)f Fp(\()p Fl(!)1279 235 y Fh(j)1296 229 y Fp(\))p Fl(:)348 b Fp(\(2\))225 329 y(By)17 b(the)h(maxim)n(um)13 b(lik)o(eliho)q(o)q(d)i(principle)i(the)g(b)q(est)i(mo)q(del)c(of)h (the)i(data)f(has)g(parameters)225 375 y(that)c(maximi)o(ze)e Fl(l)q Fp(\()p Fl(\022)q Fk(jX)6 b Fp(\).)18 b(This)13 b(function,)f(ho)o(w)o(ev)o(er,)i(is)f(not)g(easily)f(maximi)o(zed)f(n) o(umerically)225 421 y(b)q(ecause)16 b(it)d(in)o(v)o(olv)o(es)g(the)h (log)g(of)f(a)h(sum.)225 491 y(In)o(tuitiv)o(ely)m(,)d(there)i(is)f(a)g (\\credit-assignmen)o(t")g(problem:)k(it)c(is)g(not)g(clear)h(whic)o(h) f(comp)q(onen)o(t)225 537 y(of)j(the)h(mixture)f(generated)h(a)g(giv)o (en)f(data)g(p)q(oin)o(t)g(and)g(th)o(us)h(whic)o(h)g(parameters)g(to)f (adjust)225 583 y(to)d(\014t)g(that)g(data)f(p)q(oin)o(t.)17 b(The)12 b(EM)g(algorithm)e(for)h(mixture)g(mo)q(dels)g(is)g(an)h (iterativ)o(e)g(metho)q(d)225 628 y(for)j(solving)f(this)h (credit-assignmen)o(t)f(problem.)21 b(The)15 b(in)o(tuition)f(is)h (that)g(if)f(one)h(had)g(access)225 674 y(to)j(a)f(\\hidden")h(random)e (v)n(ariable)h Fq(z)h Fp(that)g(indicated)f(whic)o(h)h(data)g(p)q(oin)o (t)f(w)o(as)h(generated)225 720 y(b)o(y)g(whic)o(h)h(comp)q(onen)o(t,)f (then)h(the)g(maximi)o(zation)c(problem)i(w)o(ould)h(decouple)h(in)o (to)f(a)g(set)225 765 y(of)h(simple)e(maximi)o(zations.)32 b(Using)19 b(the)g(indicator)g(v)n(ariable)f Fq(z)p Fp(,)j(a)e (\\complete-data")e(log)225 811 y(lik)o(eliho)q(o)q(d)12 b(function)i(can)g(b)q(e)g(written)562 899 y Fl(l)574 905 y Fh(c)591 899 y Fp(\()p Fl(\022)q Fk(jX)6 b Fl(;)h Fk(Z)s Fp(\))12 b(=)814 847 y Fh(N)799 860 y Fg(X)802 948 y Fh(i)p Fi(=1)878 847 y Fh(M)865 860 y Fg(X)867 948 y Fh(j)r Fi(=1)932 899 y Fl(z)951 905 y Fh(ij)988 899 y Fp(log)6 b Fl(P)g Fp(\()p Fq(x)1122 905 y Fh(i)1136 899 y Fk(j)p Fq(z)1169 905 y Fh(i)1182 899 y Fp(;)h Fl(\022)q Fp(\))p Fl(P)f Fp(\()p Fq(z)1307 905 y Fh(i)1321 899 y Fp(;)h Fl(\022)q Fp(\))p Fl(;)284 b Fp(\(3\))225 999 y(whic)o(h)14 b(do)q(es)g(not)g(in)o(v)o(olv)o(e)f(a)g(log)h(of)f(a)h (summatio)o(n.)225 1070 y(Since)i Fq(z)h Fp(is)e(unkno)o(wn)h Fl(l)608 1076 y Fh(c)641 1070 y Fp(cannot)g(b)q(e)h(utilized)e (directly)m(,)h(so)g(w)o(e)g(instead)h(w)o(ork)e(with)h(its)g(ex-)225 1115 y(p)q(ectation,)d(denoted)g(b)o(y)g Fl(Q)p Fp(\()p Fl(\022)q Fk(j)p Fl(\022)731 1121 y Fh(k)752 1115 y Fp(\).)18 b(As)13 b(sho)o(wn)f(b)o(y)h(\(Dempster)g(et)g(al.,)e(1977\),)h Fl(l)q Fp(\()p Fl(\022)q Fk(jX)6 b Fp(\))12 b(can)h(b)q(e)225 1161 y(maxim)o(ized)f(b)o(y)h(iterating)h(the)g(follo)o(wing)e(t)o(w)o (o)h(steps:)589 1214 y Fo(E)i(step:)50 b Fl(Q)p Fp(\()p Fl(\022)q Fk(j)p Fl(\022)866 1220 y Fh(k)887 1214 y Fp(\))42 b(=)f Fl(E)r Fp([)p Fl(l)1075 1220 y Fh(c)1092 1214 y Fp(\()p Fl(\022)q Fk(jX)6 b Fl(;)h Fk(Z)s Fp(\))p Fk(jX)f Fl(;)h(\022)1330 1220 y Fh(k)1350 1214 y Fp(])589 1259 y Fo(M)15 b(step:)69 b Fl(\022)813 1265 y Fh(k)q Fi(+1)945 1259 y Fp(=)62 b(arg)7 b(max)1100 1305 y Fl(\022)1202 1259 y(Q)p Fp(\()p Fl(\022)q Fk(j)p Fl(\022)1302 1265 y Fh(k)1324 1259 y Fp(\))p Fl(:)1672 1258 y Fp(\(4\))225 1357 y(The)14 b(E)g(\(Exp)q(ectation\))g(step)h(computes)e(the)h(exp)q (ected)i(complete)d(data)g(log)g(lik)o(eliho)q(o)q(d)f(and)225 1403 y(the)21 b(M)f(\(Maximization\))e(step)j(\014nds)g(the)g (parameters)f(that)h(maxim)o(ize)d(this)i(lik)o(eliho)q(o)q(d.)225 1448 y(These)d(t)o(w)o(o)f(steps)h(form)d(the)j(basis)f(of)f(the)i(EM)f (algorithm;)e(in)h(the)i(next)f(t)o(w)o(o)g(sections)h(w)o(e)225 1494 y(will)12 b(outline)i(ho)o(w)f(they)i(can)f(b)q(e)g(used)h(for)f (real)f(and)h(discrete)i(densit)o(y)e(estimation.)225 1593 y Fq(2.1)48 b(Real-v)m(alued)14 b(data:)21 b(mixture)13 b(of)j(Gaussians)225 1678 y Fp(Real-v)n(alued)g(data)g(can)h(b)q(e)h (mo)q(deled)e(as)h(a)g(mixture)f(of)g(Gaussians.)27 b(F)m(or)17 b(this)g(mo)q(del)e(the)225 1724 y(E-step)g(simpli\014es)e(to)h (computing)e Fl(h)816 1730 y Fh(ij)857 1724 y Fk(\021)h Fl(E)r Fp([)p Fl(z)966 1730 y Fh(ij)995 1724 y Fk(j)p Fq(x)1032 1730 y Fh(i)1045 1724 y Fl(;)7 b(\022)1083 1730 y Fh(k)1104 1724 y Fp(],)13 b(the)i(probabilit)o(y)d(that)i (Gaussian)g Fl(j)r Fp(,)225 1769 y(as)g(de\014ned)h(b)o(y)f(the)g (parameters)g(estimated)f(at)h(time)f(step)i Fl(k)q Fp(,)e(generated)i (data)f(p)q(oin)o(t)f Fl(i)p Fp(.)460 1863 y Fl(h)484 1869 y Fh(ij)525 1863 y Fp(=)626 1830 y Fk(j)643 1819 y Fp(^)638 1830 y(\006)668 1815 y Fh(k)668 1841 y(j)688 1830 y Fk(j)700 1815 y Fj(\000)p Fi(1)p Fh(=)p Fi(2)785 1830 y Fp(exp)p Fk(f\000)906 1814 y Fi(1)p 906 1821 17 2 v 906 1844 a(2)928 1830 y Fp(\()p Fq(x)969 1836 y Fh(i)992 1830 y Fk(\000)1038 1829 y Fp(^)1033 1830 y Ff(\026)1063 1811 y Fh(k)1063 1840 y(j)1083 1830 y Fp(\))1099 1815 y Fh(T)1130 1819 y Fp(^)1126 1830 y(\006)1156 1810 y Fj(\000)p Fi(1)p Fh(;k)1156 1841 y(j)1228 1830 y Fp(\()p Fq(x)1269 1836 y Fh(i)1293 1830 y Fk(\000)1339 1829 y Fp(^)1334 1830 y Ff(\026)1364 1811 y Fh(k)1364 1840 y(j)1384 1830 y Fp(\))p Fk(g)p 573 1854 901 2 v 573 1868 a Fg(P)617 1879 y Fh(M)617 1912 y(l)p Fi(=1)679 1899 y Fk(j)696 1889 y Fp(^)691 1899 y(\006)721 1885 y Fh(k)721 1912 y(l)741 1899 y Fk(j)753 1887 y Fj(\000)p Fi(1)p Fh(=)p Fi(2)837 1899 y Fp(exp)q Fk(f\000)959 1883 y Fi(1)p 959 1890 17 2 v 959 1914 a(2)980 1899 y Fp(\()p Fq(x)1021 1905 y Fh(i)1045 1899 y Fk(\000)1091 1898 y Fp(^)1086 1899 y Ff(\026)1116 1880 y Fh(k)1116 1910 y(l)1136 1899 y Fp(\))1152 1887 y Fh(T)1183 1889 y Fp(^)1178 1899 y(\006)1208 1879 y Fj(\000)p Fi(1)p Fh(;k)1208 1912 y(l)1281 1899 y Fp(\()p Fq(x)1322 1905 y Fh(i)1345 1899 y Fk(\000)1391 1898 y Fp(^)1387 1899 y Ff(\026)1416 1880 y Fh(k)1416 1910 y(l)1437 1899 y Fp(\))p Fk(g)1479 1863 y Fl(:)181 b Fp(\(5\))225 1960 y(The)19 b(M-step)g(re-estimates)g(the)g(means)e (and)h(co)o(v)n(ariances)h(of)f(the)h(Gaussians)1518 1945 y Fi(1)1554 1960 y Fp(using)f(the)225 2006 y(data)c(set)g(w)o (eigh)o(ted)g(b)o(y)g(the)g Fl(h)710 2012 y Fh(ij)740 2006 y Fp(:)269 2103 y(a\))331 2102 y(^)327 2103 y Ff(\026)356 2084 y Fh(k)q Fi(+1)356 2113 y Fh(j)430 2103 y Fp(=)479 2043 y Fg(P)523 2053 y Fh(N)523 2087 y(i)p Fi(=1)585 2074 y Fl(h)609 2080 y Fh(ij)639 2074 y Fq(x)664 2080 y Fh(i)p 479 2093 199 2 v 498 2108 a Fg(P)542 2118 y Fh(N)542 2151 y(i)p Fi(=1)605 2139 y Fl(h)629 2145 y Fh(ij)683 2103 y Fl(;)90 b Fp(b\))850 2092 y(^)845 2103 y(\006)875 2085 y Fh(k)q Fi(+1)875 2114 y Fh(j)949 2103 y Fp(=)998 2040 y Fg(P)1042 2050 y Fh(N)1042 2083 y(i)p Fi(=1)1105 2071 y Fl(h)1129 2077 y Fh(ij)1158 2071 y Fp(\()p Fq(x)1199 2077 y Fh(i)1222 2071 y Fk(\000)1268 2070 y Fp(^)1264 2071 y Ff(\026)1293 2052 y Fh(k)q Fi(+1)1293 2081 y Fh(j)1355 2071 y Fp(\)\()p Fq(x)1412 2077 y Fh(i)1436 2071 y Fk(\000)1482 2070 y Fp(^)1478 2071 y Ff(\026)1507 2052 y Fh(k)q Fi(+1)1507 2081 y Fh(j)1569 2071 y Fp(\))1585 2056 y Fh(T)p 998 2093 614 2 v 1225 2108 a Fg(P)1269 2118 y Fh(N)1269 2151 y(i)p Fi(=1)1332 2139 y Fl(h)1356 2145 y Fh(ij)1617 2103 y Fl(:)43 b Fp(\(6\))p 225 2170 598 2 v 277 2197 a Fe(1)294 2212 y Fd(Though)12 b(this)f(deriv)n(ation) i(assumes)f(equal)g(priors)g(for)f(the)f(Gaussians,)j(if)e(the)g (priors)h(are)f(view)o(ed)225 2254 y(as)i(mixing)i(parameters)f(they)f (can)h(also)g(b)q(e)f(learned)h(in)g(the)f(maximization)j(step.)p eop 4 3 bop 225 42 a Fq(2.2)48 b(Discrete-v)m(alued)12 b(data:)21 b(mixture)14 b(of)i(Bernoull)o(is)225 126 y Fp(D-dimensional)11 b(binary)j(data)f Fq(x)f Fp(=)h(\()p Fl(x)846 132 y Fi(1)864 126 y Fl(;)7 b(:)g(:)g(:)e(;)i(x)981 132 y Fh(d)999 126 y Fl(;)g(:)g(:)g(:)e(x)1097 132 y Fh(D)1127 126 y Fp(\),)14 b Fl(x)1193 132 y Fh(d)1223 126 y Fk(2)e(f)p Fp(0)p Fl(;)7 b Fp(1)p Fk(g)p Fp(,)12 b(can)i(b)q(e)h(mo)q(deled)e(as)225 172 y(a)h(mixture)e(of)i Fl(M)k Fp(Bernoulli)c(densities.)19 b(That)13 b(is,)590 289 y Fl(P)6 b Fp(\()p Fq(x)p Fk(j)p Fl(\022)q Fp(\))11 b(=)780 237 y Fh(M)767 249 y Fg(X)768 338 y Fh(j)r Fi(=1)834 289 y Fl(P)6 b Fp(\()p Fl(!)909 295 y Fh(j)926 289 y Fp(\))965 237 y Fh(D)952 249 y Fg(Y)949 339 y Fh(d)p Fi(=1)1015 289 y Fl(\026)1040 270 y Fh(x)1059 274 y Fc(d)1040 301 y Fh(j)r(d)1078 289 y Fp(\(1)k Fk(\000)f Fl(\026)1191 295 y Fh(j)r(d)1226 289 y Fp(\))1242 272 y Fi(\(1)p Fj(\000)p Fh(x)1317 276 y Fc(d)1334 272 y Fi(\))1349 289 y Fl(:)311 b Fp(\(7\))225 409 y(F)m(or)13 b(this)h(mo)q(del)f(the)h(E-step)h(in)o(v)o(olv)o(es)e(computing)628 525 y Fl(h)652 531 y Fh(ij)693 525 y Fp(=)792 459 y Fg(Q)831 470 y Fh(D)831 503 y(d)p Fi(=1)903 491 y Fp(^)-25 b Fl(\026)924 472 y Fh(x)943 476 y Fc(id)924 503 y Fh(j)r(d)974 491 y Fp(\(1)9 b Fk(\000)k Fp(^)-25 b Fl(\026)1086 497 y Fh(j)r(d)1121 491 y Fp(\))1137 475 y Fi(\(1)p Fj(\000)p Fh(x)1212 479 y Fc(id)1240 475 y Fi(\))p 741 515 565 2 v 741 530 a Fg(P)785 540 y Fh(M)785 574 y(l)p Fi(=1)847 530 y Fg(Q)886 540 y Fh(D)886 574 y(d)p Fi(=1)958 561 y Fp(^)g Fl(\026)979 542 y Fh(x)998 546 y Fc(id)979 574 y Fh(ld)1029 561 y Fp(\(1)9 b Fk(\000)k Fp(^)-24 b Fl(\026)1142 567 y Fh(ld)1172 561 y Fp(\))1188 549 y Fi(\(1)p Fj(\000)p Fh(x)1263 553 y Fc(id)1290 549 y Fi(\))1311 525 y Fl(;)349 b Fp(\(8\))225 635 y(and)14 b(the)g(M-step)h(again)e(re-estimates)h (the)g(parameters)g(b)o(y)796 744 y(^)791 745 y Ff(\026)821 726 y Fh(k)q Fi(+1)821 756 y Fh(j)895 745 y Fp(=)943 686 y Fg(P)987 696 y Fh(N)987 729 y(i)p Fi(=1)1050 717 y Fl(h)1074 723 y Fh(ij)1103 717 y Fq(x)1128 723 y Fh(i)p 943 736 199 2 v 963 750 a Fg(P)1007 761 y Fh(N)1007 794 y(i)p Fi(=1)1070 781 y Fl(h)1094 787 y Fh(ij)1147 745 y Fl(:)513 b Fp(\(9\))225 880 y(More)14 b(generally)m(,)e(discrete)i (or)g(categorical)f(data)f(can)i(b)q(e)f(mo)q(deled)g(as)g(generated)h (b)o(y)f(a)g(mix-)225 926 y(ture)h(of)e(m)o(ultinom)o(ial)d(densities) 14 b(and)f(similar)d(deriv)n(ations)j(for)f(the)i(learning)e(algorithm) f(can)225 972 y(b)q(e)k(applied.)k(Finally)m(,)12 b(the)k(extension)f (to)f(data)g(with)g(mixed)f(real,)i(binary)m(,)e(and)h(categorical)225 1017 y(dimensions)f(can)i(b)q(e)g(readily)g(deriv)o(ed)g(b)o(y)f (assuming)f(a)h(join)o(t)g(densit)o(y)h(with)f(mixed)f(comp)q(o-)225 1063 y(nen)o(ts)i(of)e(the)i(three)g(t)o(yp)q(es.)225 1182 y Fm(3)56 b(Learning)18 b(from)f(incomplete)f(data)225 1279 y Fp(In)j(the)h(previous)g(section)g(w)o(e)g(presen)o(ted)h(one)f (asp)q(ect)h(of)e(the)h(EM)f(algorithm:)27 b(learning)225 1325 y(mixture)17 b(mo)q(dels.)30 b(Another)19 b(imp)q(ortan)o(t)e (application)g(of)g(EM)i(is)f(to)g(learning)g(from)e(data)225 1370 y(sets)21 b(with)d(missing)g(v)n(alues)h(\(Little)g(and)g(Rubin,)g (1987;)i(Dempster)e(et)h(al.,)f(1977\).)33 b(This)225 1416 y(application)18 b(has)h(b)q(een)h(pursued)g(in)f(the)g (statistics)h(literature)f(for)g(non-mixture)f(densit)o(y)225 1462 y(estimation)12 b(problems;)g(in)h(this)h(pap)q(er)g(w)o(e)g(com)o (bine)f(this)g(application)g(of)g(EM)h(with)f(that)h(of)225 1507 y(learning)f(mixture)g(parameters.)225 1578 y(W)m(e)j(assume)g (that)g(the)h(data)f(set)h Fk(X)k Fp(=)16 b Fk(f)p Fq(x)920 1584 y Fi(1)939 1578 y Fl(;)7 b(:)g(:)g(:)t(;)g Fq(x)1056 1584 y Fh(N)1087 1578 y Fk(g)16 b Fp(is)h(divided)e(in)o(to)h(an)g (observ)o(ed)h(com-)225 1624 y(p)q(onen)o(t)d Fk(X)399 1608 y Fi(o)431 1624 y Fp(and)g(a)f(missing)f(comp)q(onen)o(t)h Fk(X)942 1608 y Fi(m)971 1624 y Fp(.)18 b(Similarly)m(,)10 b(eac)o(h)k(data)g(v)o(ector)g Fq(x)1523 1630 y Fh(i)1551 1624 y Fp(is)f(divided)225 1669 y(in)o(to)h(\()p Fq(x)351 1654 y Fi(o)351 1680 y Fh(i)370 1669 y Fl(;)7 b Fq(x)414 1654 y Fi(m)414 1680 y Fh(i)443 1669 y Fp(\))16 b(where)g(eac)o(h)g (data)f(v)o(ector)h(can)f(ha)o(v)o(e)g(di\013eren)o(t)h(missing)e(comp) q(onen)o(ts|this)225 1715 y(w)o(ould)d(b)q(e)i(denoted)g(b)o(y)f(sup)q (erscript)i Fq(m)862 1721 y Fh(i)888 1715 y Fp(and)e Fq(o)991 1721 y Fh(i)1004 1715 y Fp(,)g(but)h(w)o(e)f(ha)o(v)o(e)g (simpli\014ed)e(the)j(notation)e(for)225 1761 y(the)j(sak)o(e)h(of)e (clarit)o(y)m(.)225 1831 y(T)m(o)g(handle)h(missing)e(data)h(w)o(e)i (rewrite)g(the)f(EM)g(algorithm)d(as)j(follo)o(ws)527 1904 y(E)h(step:)51 b Fl(Q)p Fp(\()p Fl(\022)q Fk(j)p Fl(\022)806 1910 y Fh(k)827 1904 y Fp(\))42 b(=)g Fl(E)r Fp([)p Fl(l)1016 1910 y Fh(c)1033 1904 y Fp(\()p Fl(\022)q Fk(jX)1117 1889 y Fi(o)1135 1904 y Fl(;)7 b Fk(X)1190 1889 y Fi(m)1219 1904 y Fl(;)g Fk(Z)s Fp(\))p Fk(jX)1335 1889 y Fi(o)1353 1904 y Fl(;)g(\022)1391 1910 y Fh(k)1411 1904 y Fp(])527 1950 y(M)14 b(step:)70 b Fl(\022)753 1956 y Fh(k)q Fi(+1)885 1950 y Fp(=)63 b(arg)7 b(max)1041 1995 y Fl(\022)1143 1950 y(Q)p Fp(\()p Fl(\022)q Fk(j)p Fl(\022)1243 1956 y Fh(k)1264 1950 y Fp(\))p Fl(:)1651 1948 y Fp(\(10\))225 2067 y(Comparing)i(to)j(equation)f(\(4\))h(w)o(e)g (see)h(that)e(aside)h(from)e(the)i(indicator)f(v)n(ariables)g Fk(Z)k Fp(w)o(e)d(ha)o(v)o(e)225 2113 y(added)j(a)g(second)g(form)e(of) h(incomplete)g(data,)g Fk(X)1019 2098 y Fi(m)1048 2113 y Fp(,)h(corresp)q(onding)g(to)g(the)g(missing)e(v)n(alues)225 2159 y(in)g(the)i(data)e(set.)19 b(The)14 b(E-step)h(of)e(the)i (algorithm)c(estimates)i(b)q(oth)h(these)h(forms)e(of)g(missing)225 2204 y(information;)d(in)j(essence)j(it)c(uses)j(the)f(curren)o(t)g (estimate)f(of)f(the)i(data)f(densit)o(y)h(to)f(complete)225 2250 y(the)h(missing)f(v)n(alues.)p eop 5 4 bop 225 42 a Fq(3.1)48 b(Real-v)m(alued)14 b(data:)21 b(mixture)13 b(of)j(Gaussians)225 126 y Fp(W)m(e)d(start)i(b)o(y)f (writing)f(the)h(log)f(lik)o(eliho)q(o)q(d)f(of)i(the)g(complete)f (data,)327 225 y Fl(l)339 231 y Fh(c)357 225 y Fp(\()p Fl(\022)q Fk(jX)441 208 y Fi(o)459 225 y Fl(;)7 b Fk(X)514 208 y Fi(m)543 225 y Fl(;)g Fk(Z)s Fp(\))k(=)681 173 y Fh(N)666 186 y Fg(X)690 274 y Fh(i)745 173 y(M)733 186 y Fg(X)755 274 y Fh(j)800 225 y Fl(z)819 231 y Fh(ij)855 225 y Fp(log)c Fl(P)f Fp(\()p Fq(x)990 231 y Fh(i)1003 225 y Fk(j)p Fq(z)1036 231 y Fh(i)1050 225 y Fl(;)h(\022)q Fp(\))i(+)1171 173 y Fh(N)1156 186 y Fg(X)1180 274 y Fh(i)1235 173 y(M)1223 186 y Fg(X)1245 274 y Fh(j)1290 225 y Fl(z)1309 231 y Fh(ij)1345 225 y Fp(log)e Fl(P)f Fp(\()p Fq(z)1476 231 y Fh(i)1489 225 y Fk(j)p Fl(\022)q Fp(\))p Fl(:)102 b Fp(\(11\))225 327 y(W)m(e)14 b(can)h(ignore)g(the)g (second)h(term)e(since)h(w)o(e)g(will)e(only)h(b)q(e)i(estimating)d (the)i(parameters)g(of)225 373 y(the)i Fl(P)6 b Fp(\()p Fq(x)373 379 y Fh(i)386 373 y Fk(j)p Fq(z)419 379 y Fh(i)433 373 y Fl(;)h(\022)q Fp(\).)25 b(Using)16 b(equation)g(\(11\))g(for)g (the)h(mixture)e(of)g(Gaussians)h(w)o(e)h(note)g(that)f(if)225 419 y(only)c(the)h(indicator)f(v)n(ariables)g Fq(z)751 425 y Fh(i)778 419 y Fp(are)h(missing,)e(the)i(E)g(step)h(can)e(b)q(e)i (reduced)g(to)f(estimating)225 464 y Fl(E)r Fp([)p Fl(z)289 470 y Fh(ij)318 464 y Fk(j)p Fq(x)355 470 y Fh(i)369 464 y Fl(;)7 b(\022)q Fp(].)17 b(F)m(or)11 b(the)i(case)g(w)o(e)f(are)g (in)o(terested)i(in,)d(with)h(t)o(w)o(o)f(t)o(yp)q(es)i(of)e(missing)g (data)g Fq(z)1632 470 y Fh(i)1658 464 y Fp(and)225 510 y Fq(x)250 495 y Fi(m)250 521 y Fh(i)280 510 y Fp(,)h(w)o(e)i(expand)g (equation)f(\(11\))g(using)g Fq(m)g Fp(and)g Fq(o)g Fp(sup)q(erscripts) j(to)d(denote)h(sub)o(v)o(ectors)h(and)225 556 y(submatrices)h(of)g (the)h(parameters)f(matc)o(hing)e(the)j(missing)d(and)i(observ)o(ed)i (comp)q(onen)o(ts)e(of)225 601 y(the)e(data,)237 700 y Fl(l)249 706 y Fh(c)266 700 y Fp(\()p Fl(\022)q Fk(jX)350 683 y Fi(o)369 700 y Fl(;)7 b Fk(X)424 683 y Fi(m)452 700 y Fl(;)g Fk(Z)s Fp(\))12 b(=)591 648 y Fh(N)576 661 y Fg(X)600 749 y Fh(i)655 648 y(M)643 661 y Fg(X)665 749 y Fh(j)710 700 y Fl(z)729 706 y Fh(ij)758 700 y Fp([)775 672 y Fl(n)p 775 691 25 2 v 777 729 a Fp(2)811 700 y(log)7 b(2)p Fl(\031)j Fp(+)974 672 y(1)p 974 691 21 2 v 974 729 a(2)1006 700 y(log)d Fk(j)p Fp(\006)1109 706 y Fh(j)1126 700 y Fk(j)h(\000)1193 672 y Fp(1)p 1193 691 V 1193 729 a(2)1219 700 y(\()p Fq(x)1260 683 y Fi(o)1260 710 y Fh(i)1288 700 y Fk(\000)h Ff(\026)1359 683 y Fi(o)1359 710 y Fh(j)1377 700 y Fp(\))1393 683 y Fh(T)1420 700 y Fp(\006)1450 680 y Fj(\000)p Fi(1)p Fh(;)p Fi(o)q(o)1450 712 y Fh(j)1538 700 y Fp(\()p Fq(x)1579 683 y Fi(o)1579 710 y Fh(i)1607 700 y Fk(\000)h Ff(\026)1678 683 y Fi(o)1678 710 y Fh(j)1697 700 y Fp(\))540 818 y Fk(\000)p Fp(\()p Fq(x)613 801 y Fi(o)613 828 y Fh(i)638 818 y Fk(\000)c Ff(\026)705 801 y Fi(o)705 828 y Fh(j)724 818 y Fp(\))740 801 y Fh(T)766 818 y Fp(\006)796 798 y Fj(\000)p Fi(1)p Fh(;)p Fi(om)796 829 y Fh(j)895 818 y Fp(\()p Fq(x)936 801 y Fi(m)936 828 y Fh(i)971 818 y Fk(\000)g Ff(\026)1038 801 y Fi(m)1038 828 y Fh(j)1068 818 y Fp(\))g Fk(\000)1133 790 y Fp(1)p 1133 808 V 1133 846 a(2)1158 818 y(\()p Fq(x)1199 801 y Fi(m)1199 828 y Fh(i)1235 818 y Fk(\000)g Ff(\026)1302 801 y Fi(m)1302 828 y Fh(j)1331 818 y Fp(\))1347 801 y Fh(T)1374 818 y Fp(\006)1404 798 y Fj(\000)p Fi(1)p Fh(;)p Fi(mm)1404 829 y Fh(j)1513 818 y Fp(\()p Fq(x)1554 801 y Fi(m)1554 828 y Fh(i)1589 818 y Fk(\000)g Ff(\026)1656 801 y Fi(m)1656 828 y Fh(j)1686 818 y Fp(\)])p Fl(:)225 885 y Fp(Note)16 b(that)g(after)g(taking)f(the)h(exp)q(ectation,)h(the) f(su\016cien)o(t)h(statistics)f(for)g(the)g(parameters)225 930 y(in)o(v)o(olv)o(e)e(three)i(unkno)o(wn)f(terms,)g Fl(z)800 936 y Fh(ij)829 930 y Fp(,)g Fl(z)875 936 y Fh(ij)905 930 y Fq(x)930 915 y Fi(m)930 941 y Fh(i)959 930 y Fp(,)g(and)g Fl(z)1087 936 y Fh(ij)1117 930 y Fq(x)1142 915 y Fi(m)1142 941 y Fh(i)1172 930 y Fq(x)1197 915 y Fi(m)1197 941 y Fh(i)1226 913 y(T)1252 930 y Fp(.)22 b(Th)o(us)15 b(w)o(e)h(m)o(ust)e(compute:)225 984 y Fl(E)r Fp([)p Fl(z)289 990 y Fh(ij)318 984 y Fk(j)p Fq(x)355 969 y Fi(o)355 994 y Fh(i)373 984 y Fl(;)7 b(\022)411 990 y Fh(k)432 984 y Fp(],)13 b Fl(E)r Fp([)p Fl(z)533 990 y Fh(ij)562 984 y Fq(x)587 969 y Fi(m)587 994 y Fh(i)616 984 y Fk(j)p Fq(x)653 969 y Fi(o)653 994 y Fh(i)672 984 y Fl(;)7 b(\022)710 990 y Fh(k)730 984 y Fp(],)13 b(and)h Fl(E)r Fp([)p Fl(z)912 990 y Fh(ij)941 984 y Fq(x)966 969 y Fi(m)966 994 y Fh(i)995 984 y Fq(x)1020 969 y Fi(m)1020 994 y Fh(i)1050 966 y(T)1076 984 y Fk(j)p Fq(x)1113 969 y Fi(o)1113 994 y Fh(i)1131 984 y Fl(;)7 b(\022)1169 990 y Fh(k)1190 984 y Fp(])p Fl(:)225 1054 y Fp(One)15 b(in)o(tuitiv)o(e)e(approac)o(h)i(to)f(dealing)f(with)h(missing)f(data) g(is)i(to)f(use)h(the)g(curren)o(t)h(estimate)225 1100 y(of)g(the)h(data)f(densit)o(y)g(to)g(compute)g(the)h(exp)q(ectation)g (of)f(the)h(missing)d(data)i(in)g(an)g(E-step,)225 1145 y(complete)c(the)i(data)e(with)h(these)h(exp)q(ectations,)f(and)g(then) h(use)f(this)g(completed)f(data)h(to)f(re-)225 1191 y(estimate)i (parameters)h(in)f(an)g(M-step.)21 b(Ho)o(w)o(ev)o(er,)14 b(this)h(in)o(tuition)e(fails)h(ev)o(en)h(when)g(dealing)225 1237 y(with)d(a)g(single)g(t)o(w)o(o-dimensional)d(Gaussian;)j(the)h (exp)q(ectation)g(of)f(the)h(missing)d(data)i(alw)o(a)o(ys)225 1282 y(lies)k(along)e(a)i(line,)f(whic)o(h)g(biases)i(the)f(estimate)f (of)g(the)h(co)o(v)n(ariance.)24 b(On)16 b(the)g(other)h(hand,)225 1328 y(the)12 b(approac)o(h)f(arising)g(from)f(application)g(of)g(the)i (EM)g(algorithm)d(sp)q(eci\014es)k(that)f(one)f(should)225 1374 y(use)h(the)f(curren)o(t)i(densit)o(y)e(estimate)f(to)h(compute)g (the)g(exp)q(ectation)h(of)e(whatev)o(er)i(incomplete)225 1419 y(terms)k(app)q(ear)g(in)f(the)i(lik)o(eliho)q(o)q(d)d(maxim)o (ization.)21 b(F)m(or)15 b(the)i(mixture)e(of)g(Gaussians)h(these)225 1465 y(incomplete)h(terms)i(in)o(v)o(olv)o(e)e(in)o(teractions)i(b)q (et)o(w)o(een)h(the)f(indicator)f(v)n(ariable)f Fl(z)1534 1471 y Fh(ij)1582 1465 y Fp(and)h(the)225 1511 y(\014rst)f(and)f (second)i(momen)o(ts)c(of)i Fq(x)787 1496 y Fi(m)787 1522 y Fh(i)817 1511 y Fp(.)25 b(Th)o(us,)17 b(simply)d(computing)h (the)i(exp)q(ectation)h(of)d(the)225 1556 y(missing)f(data)h Fq(z)492 1562 y Fh(i)522 1556 y Fp(and)h Fq(x)630 1541 y Fi(m)630 1567 y Fh(i)675 1556 y Fp(from)e(our)i(mo)q(del)e(and)i (substituting)g(those)g(v)n(alues)g(in)o(to)f(the)h(M)225 1602 y(step)f(is)f Fo(not)g Fp(su\016cien)o(t)g(to)g(guaran)o(tee)g(an) g(increase)h(in)e(the)i(lik)o(eliho)q(o)q(d)d(of)h(the)i(parameters.) 225 1673 y(The)f(ab)q(o)o(v)o(e)g(terms)g(can)g(b)q(e)h(computed)e(as)h (follo)o(ws:)j Fl(E)r Fp([)p Fl(z)1136 1679 y Fh(ij)1165 1673 y Fk(j)p Fq(x)1202 1658 y Fi(o)1202 1683 y Fh(i)1220 1673 y Fl(;)7 b(\022)1258 1679 y Fh(k)1279 1673 y Fp(])13 b(is)h(again)f Fl(h)1481 1679 y Fh(ij)1510 1673 y Fp(,)h(the)g(proba-) 225 1718 y(bilit)o(y)e(as)i(de\014ned)h(in)f(\(5\))g(measured)f(only)h (on)f(the)i(observ)o(ed)g(dimensions)d(of)i Fq(x)1504 1724 y Fh(i)1518 1718 y Fp(,)f(and)255 1787 y Fl(E)r Fp([)p Fl(z)319 1793 y Fh(ij)348 1787 y Fq(x)373 1770 y Fi(m)373 1797 y Fh(i)403 1787 y Fk(j)p Fq(x)440 1770 y Fi(o)440 1797 y Fh(i)458 1787 y Fl(;)7 b(\022)496 1793 y Fh(k)516 1787 y Fp(])k(=)h Fl(h)607 1793 y Fh(ij)636 1787 y Fl(E)r Fp([)p Fq(x)706 1770 y Fi(m)706 1797 y Fh(i)736 1787 y Fk(j)p Fl(z)767 1793 y Fh(ij)807 1787 y Fp(=)g(1)p Fl(;)7 b Fq(x)916 1770 y Fi(o)916 1797 y Fh(i)934 1787 y Fl(;)g(\022)972 1793 y Fh(k)992 1787 y Fp(])k(=)h Fl(h)1083 1793 y Fh(ij)1112 1787 y Fp(\()p Ff(\026)1158 1770 y Fi(m)1158 1797 y Fh(j)1196 1787 y Fp(+)e(\006)1268 1770 y Fi(mo)1268 1797 y Fh(j)1314 1787 y Fp(\006)1344 1770 y Fi(o)q(o)1378 1757 y Fb(\000)p Fa(1)1344 1797 y Fh(j)1419 1787 y Fp(\()p Fq(x)1460 1770 y Fi(o)1460 1797 y Fh(i)1488 1787 y Fk(\000)f Ff(\026)1559 1770 y Fi(o)1559 1797 y Fh(j)1577 1787 y Fp(\)\))p Fl(:)30 b Fp(\(12\))225 1849 y(De\014ning)393 1848 y(^)390 1849 y Fq(x)415 1834 y Fi(m)415 1860 y Fh(ij)457 1849 y Fk(\021)11 b Fl(E)r Fp([)p Fq(x)570 1834 y Fi(m)570 1860 y Fh(i)599 1849 y Fk(j)p Fl(z)630 1855 y Fh(ij)671 1849 y Fp(=)h(1)p Fl(;)7 b Fq(x)780 1834 y Fi(o)780 1860 y Fh(i)798 1849 y Fl(;)g(\022)836 1855 y Fh(k)856 1849 y Fp(],)13 b(the)i(regression)g (of)e Fq(x)1229 1834 y Fi(m)1229 1860 y Fh(i)1272 1849 y Fp(on)h Fq(x)1355 1834 y Fi(o)1355 1860 y Fh(i)1388 1849 y Fp(using)f(Gaussian)h Fl(j)r Fp(,)420 1924 y Fl(E)r Fp([)p Fl(z)484 1930 y Fh(ij)513 1924 y Fq(x)538 1906 y Fi(m)538 1934 y Fh(i)568 1924 y Fq(x)593 1906 y Fi(m)593 1934 y Fh(i)622 1904 y(T)648 1924 y Fk(j)p Fq(x)685 1906 y Fi(o)685 1934 y Fh(i)704 1924 y Fl(;)7 b(\022)742 1930 y Fh(k)762 1924 y Fp(])k(=)h Fl(h)853 1930 y Fh(ij)882 1924 y Fp(\(\006)928 1906 y Fi(mm)928 1934 y Fh(j)994 1924 y Fk(\000)e Fp(\006)1066 1906 y Fi(mo)1066 1934 y Fh(j)1112 1924 y Fp(\006)1142 1906 y Fi(o)q(o)1176 1894 y Fb(\000)p Fa(1)1142 1934 y Fh(j)1216 1924 y Fp(\006)1246 1906 y Fi(mo)1246 1934 y Fh(j)1292 1904 y(T)1328 1924 y Fp(+)1371 1923 y(^)1369 1924 y Fq(x)1394 1906 y Fi(m)1394 1934 y Fh(ij)1426 1923 y Fp(^)1424 1924 y Fq(x)1449 1906 y Fi(m)p Fh(T)1449 1934 y(ij)1502 1924 y Fp(\))p Fl(:)121 b Fp(\(13\))225 2010 y(The)20 b(M-step)g(uses)g(these)h(exp)q (ectations)f(substituted)g(in)o(to)f(equations)g(\(6\)a)g(and)g(\(6\)b) g(to)225 2056 y(re-estimate)f(the)h(means)e(and)i(co)o(v)n(ariances.)31 b(T)m(o)17 b(re-estimate)i(the)f(mean)f(v)o(ector,)j Ff(\026)1629 2066 y Fh(j)1647 2056 y Fp(,)f(w)o(e)225 2107 y(substitute)i(the)g(v)n(alues)f Fl(E)r Fp([)p Fq(x)703 2092 y Fi(m)703 2118 y Fh(i)732 2107 y Fk(j)p Fl(z)763 2113 y Fh(ij)814 2107 y Fp(=)i(1)p Fl(;)7 b Fq(x)933 2092 y Fi(o)933 2118 y Fh(i)951 2107 y Fl(;)g(\022)989 2113 y Fh(k)1010 2107 y Fp(])19 b(for)h(the)h(missing)d(comp)q(onen)o (ts)i(of)f Fq(x)1656 2113 y Fh(i)1690 2107 y Fp(in)225 2153 y(equation)j(\(6\)a.)45 b(T)m(o)22 b(re-estimate)h(the)g(co)o(v)n (ariance)g(matrix)e(w)o(e)i(substitute)h(the)f(v)n(alues)225 2204 y Fl(E)r Fp([)p Fq(x)295 2189 y Fi(m)295 2215 y Fh(i)324 2204 y Fq(x)349 2189 y Fi(m)349 2215 y Fh(i)379 2187 y(T)405 2204 y Fk(j)p Fl(z)436 2210 y Fh(ij)476 2204 y Fp(=)12 b(1)p Fl(;)7 b Fq(x)585 2189 y Fi(o)585 2215 y Fh(i)603 2204 y Fl(;)g(\022)641 2210 y Fh(k)662 2204 y Fp(])12 b(for)g(the)h(outer)g(pro)q(duct)g(matrices)f(in)o(v)o (olving)f(the)i(missing)d(com-)225 2250 y(p)q(onen)o(ts)15 b(of)e Fq(x)452 2256 y Fh(i)480 2250 y Fp(in)g(equation)h(\(6\)b.)p eop 6 5 bop 225 42 a Fq(3.2)48 b(Discrete-v)m(alued)12 b(data:)21 b(mixture)14 b(of)i(Bernoull)o(is)225 128 y Fp(F)m(or)d(the)h (Bernoulli)e(mixture)g(the)i(su\016cien)o(t)g(statistics)g(for)e(the)i (M-step)g(in)o(v)o(olv)o(e)e(the)i(incom-)225 173 y(plete)d(terms)e Fl(E)r Fp([)p Fl(z)498 179 y Fh(ij)527 173 y Fk(j)p Fq(x)564 158 y Fi(o)564 184 y Fh(i)583 173 y Fl(;)e(\022)621 179 y Fh(k)641 173 y Fp(])j(and)f Fl(E)r Fp([)p Fl(z)803 179 y Fh(ij)833 173 y Fq(x)858 158 y Fi(m)858 184 y Fh(i)887 173 y Fk(j)p Fq(x)924 158 y Fi(o)924 184 y Fh(i)942 173 y Fl(;)e(\022)980 179 y Fh(k)1001 173 y Fp(].)16 b(The)11 b(\014rst)f(is)g(equal)g(to)g Fl(h)1419 179 y Fh(ij)1458 173 y Fp(calculated)g(o)o(v)o(er)225 219 y(the)15 b(observ)o(ed)h(sub)o (v)o(ector)f(of)f Fq(x)728 225 y Fh(i)742 219 y Fp(.)20 b(The)15 b(second,)g(since)g(w)o(e)g(assume)f(that)h(within)e(a)h (class)h(the)225 265 y(individual)f(dimensions)h(of)h(the)h(Bernoulli)f (v)n(ariable)f(are)h(indep)q(enden)o(t,)i(is)e(simply)f Fl(h)1626 271 y Fh(ij)1655 265 y Ff(\026)1684 249 y Fi(m)1684 275 y Fh(j)1713 265 y Fp(.)225 316 y(The)f(M-step)h(uses)g(these)g(exp) q(ectations)h(substituted)f(in)o(to)e(equation)g(\(9\).)225 438 y Fm(4)56 b(Sup)r(ervised)17 b(learning)225 537 y Fp(If)g(eac)o(h)h(v)o(ector)g Fq(x)520 543 y Fh(i)551 537 y Fp(in)f(the)h(data)e(set)j(is)e(comp)q(osed)g(of)f(an)h(\\input") g(sub)o(v)o(ector,)i Fq(x)1577 522 y Fi(i)1577 548 y Fh(i)1591 537 y Fp(,)e(and)g(a)225 583 y(\\target")e(or)h(output)f(sub) o(v)o(ector,)i Fq(x)805 568 y Fi(o)805 593 y Fh(i)824 583 y Fp(,)e(then)h(learning)f(the)h(join)o(t)e(densit)o(y)i(of)f(the)h (input)f(and)225 628 y(target)f(is)f(a)g(form)f(of)g(sup)q(ervised)j (learning.)i(In)d(sup)q(ervised)h(learning)d(w)o(e)i(generally)f(wish)g (to)225 674 y(predict)g(the)f(output)g(v)n(ariables)g(from)e(the)i (input)g(v)n(ariables.)k(In)c(this)g(section)h(w)o(e)f(will)e(outline) 225 720 y(ho)o(w)j(this)h(is)g(ac)o(hiev)o(ed)g(using)g(the)g (estimated)g(densit)o(y)m(.)225 825 y Fq(4.1)48 b(F)l(unction)13 b(appro)o(ximation)225 911 y Fp(F)m(or)j(real-v)n(alued)g(function)g (appro)o(ximation)e(w)o(e)i(ha)o(v)o(e)h(assumed)f(that)g(the)h(densit) o(y)g(is)g(esti-)225 957 y(mated)e(using)g(a)h(mixture)f(of)g (Gaussians.)24 b(Giv)o(en)15 b(an)h(input)f(v)o(ector)i Fq(x)1371 942 y Fi(i)1371 968 y Fh(i)1401 957 y Fp(w)o(e)f(extract)h (all)d(the)225 1003 y(relev)n(an)o(t)19 b(information)e(from)g(the)j (densit)o(y)g Fl(P)6 b Fp(\()p Fq(x)1021 988 y Fi(i)1032 1003 y Fl(;)h Fq(x)1076 988 y Fi(o)1094 1003 y Fp(\))20 b(b)o(y)f(conditionalizing)e(to)i Fl(P)6 b Fp(\()p Fq(x)1628 988 y Fi(o)1647 1003 y Fk(j)p Fq(x)1684 988 y Fi(i)1684 1013 y Fh(i)1697 1003 y Fp(\).)225 1048 y(F)m(or)16 b(a)g(single)f (Gaussian)h(this)g(conditional)f(densit)o(y)h(is)g(normal,)e(and,)j (since)g Fl(P)6 b Fp(\()p Fq(x)1555 1033 y Fi(i)1566 1048 y Fl(;)h Fq(x)1610 1033 y Fi(o)1628 1048 y Fp(\))16 b(is)g(a)225 1094 y(mixture)g(of)h(Gaussians)g(so)h(is)f Fl(P)6 b Fp(\()p Fq(x)807 1079 y Fi(o)826 1094 y Fk(j)p Fq(x)863 1079 y Fi(i)874 1094 y Fp(\).)29 b(In)17 b(principle,)h(this)f (conditional)f(densit)o(y)i(is)f(the)225 1140 y(\014nal)g(output)i(of)e (the)i(densit)o(y)f(estimator.)30 b(That)17 b(is,)i(giv)o(en)e(a)h (particular)g(input)g(the)h(net-)225 1185 y(w)o(ork)14 b(returns)h(the)f(complete)g(conditional)e(densit)o(y)i(of)g(the)g (output.)k(Ho)o(w)o(ev)o(er,)c(since)h(man)o(y)225 1231 y(applications)k(require)h(a)g(single)f(estimate)g(of)h(the)g(output,)h (w)o(e)f(note)g(three)h(w)o(a)o(ys)f(to)f(ob-)225 1277 y(tain)g(estimates)i Fq(^)-25 b(x)20 b Fp(of)f Fq(x)628 1262 y Fi(o)669 1277 y Fp(=)j Fl(f)t Fp(\()p Fq(x)788 1262 y Fi(i)788 1287 y Fh(i)803 1277 y Fp(\):)30 b(the)20 b(least)g(squares)h(estimate)f(\(LSE\),)g(whic)o(h)g(tak)o(es)226 1322 y Fq(^)-25 b(x)250 1307 y Fi(o)269 1322 y Fp(\()p Fq(x)310 1307 y Fi(i)310 1333 y Fh(i)324 1322 y Fp(\))23 b(=)h Fl(E)r Fp(\()p Fq(x)493 1307 y Fi(o)512 1322 y Fk(j)p Fq(x)549 1307 y Fi(i)549 1333 y Fh(i)562 1322 y Fp(\);)g(sto)q(c)o(hastic)e(sampling)c(\(STOCH\),)k(whic)o(h)e (samples)g(according)h(to)225 1368 y(the)e(distribution)h Fq(^)-25 b(x)558 1353 y Fi(o)577 1368 y Fp(\()p Fq(x)618 1353 y Fi(i)618 1379 y Fh(i)632 1368 y Fp(\))20 b Fk(\030)g Fl(P)6 b Fp(\()p Fq(x)794 1353 y Fi(o)812 1368 y Fk(j)p Fq(x)849 1353 y Fi(i)849 1379 y Fh(i)863 1368 y Fp(\);)21 b(single)d(comp)q(onen)o(t)h(LSE)g(\(SLSE\),)g(whic)o(h)g(tak)o(es)226 1414 y Fq(^)-25 b(x)250 1399 y Fi(o)269 1414 y Fp(\()p Fq(x)310 1399 y Fi(i)310 1424 y Fh(i)324 1414 y Fp(\))12 b(=)g Fl(E)r Fp(\()p Fq(x)470 1399 y Fi(o)489 1414 y Fk(j)p Fq(x)526 1399 y Fi(i)526 1424 y Fh(i)539 1414 y Fl(;)7 b(!)584 1420 y Fh(j)601 1414 y Fp(\))14 b(where)h Fl(j)f Fp(=)e(arg)7 b(max)968 1420 y Fh(k)996 1414 y Fl(P)f Fp(\()p Fl(z)1064 1420 y Fh(k)1084 1414 y Fk(j)p Fq(x)1121 1399 y Fi(i)1121 1424 y Fh(i)1135 1414 y Fp(\).)18 b(F)m(or)13 b(a)h(giv)o(en)f(input,)h(SLSE)g(pic)o(ks)225 1459 y(the)19 b(Gaussian)f(with)g(highest)h(p)q(osterior)g(and)f(appro) o(ximates)f(the)i(output)g(with)f(the)h(LSE)225 1505 y(estimator)13 b(giv)o(en)g(b)o(y)h(that)g(Gaussian)f(alone.)225 1575 y(The)h(conditional)f(exp)q(ectation)i(or)e(LSE)h(estimator)f(for) h(a)f(Gaussian)h(mixture)f(is)575 1695 y Fq(^)-24 b(x)600 1678 y Fi(o)619 1695 y Fp(\()p Fq(x)660 1678 y Fi(i)660 1705 y Fh(i)674 1695 y Fp(\))11 b(=)750 1630 y Fg(P)794 1640 y Fh(M)794 1673 y(j)r Fi(=1)860 1661 y Fl(h)884 1667 y Fh(ij)914 1661 y Fp([)p Ff(\026)955 1646 y Fi(o)955 1672 y Fh(j)982 1661 y Fp(+)f(\006)1054 1646 y Fi(oi)1054 1672 y Fh(j)1082 1661 y Fp(\006)1112 1646 y Fi(ii)1131 1633 y Fb(\000)p Fa(1)1112 1672 y Fh(j)1171 1661 y Fp(\()p Fq(x)1212 1646 y Fi(i)1212 1672 y Fh(i)1236 1661 y Fk(\000)f Ff(\026)1307 1646 y Fi(i)1307 1672 y Fh(j)1324 1661 y Fp(\)])p 750 1686 602 2 v 969 1700 a Fg(P)1013 1710 y Fh(M)1013 1744 y(j)r Fi(=1)1080 1731 y Fl(h)1104 1737 y Fh(ij)1357 1695 y Fl(;)282 b Fp(\(14\))225 1814 y(whic)o(h)16 b(is)h(a)f(con)o(v)o(ex)g(sum)g(of)g(linear)g(appro)o(ximations,)e (where)j(the)g(w)o(eigh)o(ts)g Fl(h)1504 1820 y Fh(ij)1549 1814 y Fp(v)n(ary)f(non-)225 1860 y(linearly)e(according)h(to)g (equation)g(\(14\))g(o)o(v)o(er)g(the)h(input)f(space.)22 b(The)16 b(LSE)f(estimator)f(on)h(a)225 1905 y(Gaussian)g(mixture)f (has)i(in)o(teresting)g(relations)f(to)g(algorithms)f(suc)o(h)i(as)f (CAR)m(T)g(\(Breiman)225 1951 y(et)d(al.,)f(1984\),)g(MARS)g(\(F)m (riedman,)g(1991\),)f(and)i(mixtures)f(of)g(exp)q(erts)j(\(Jacobs)f(et) f(al.,)e(1991;)225 1997 y(Jordan)18 b(and)f(Jacobs,)i(1994\),)e(in)g (that)h(the)g(mixture)e(of)h(Gaussians)g(comp)q(etitiv)o(ely)f(parti-) 225 2042 y(tions)d(the)g(input)g(space,)h(and)f(learns)g(a)g(linear)g (regression)h(surface)g(on)f(eac)o(h)g(partition.)k(This)225 2088 y(similarit)o(y)11 b(has)j(also)f(b)q(een)i(noted)f(b)o(y)g(T)m (resp)h(et)f(al.)j(\(1993\))c(.)225 2159 y(The)f(sto)q(c)o(hastic)h (estimator)e(\(STOCH\))h(and)g(the)g(single)f(comp)q(onen)o(t)h (estimator)e(\(SLSE\))j(are)225 2204 y(b)q(etter)j(suited)e(than)g(an)o (y)f(least)h(squares)h(metho)q(d)f(for)f(learning)g(non-con)o(v)o(ex)h (in)o(v)o(erse)h(maps,)225 2250 y(where)i(the)f(mean)f(of)g(sev)o(eral) i(solutions)e(to)h(an)f(in)o(v)o(erse)i(migh)o(t)d(not)i(b)q(e)g(a)g (solution.)23 b(These)p eop 7 6 bop 225 87 a Fp(Figure)16 b(1:)22 b(Classi\014cation)16 b(of)f(the)i(iris)e(data)225 133 y(set.)j(100)12 b(data)f(p)q(oin)o(ts) h(w)o(ere)h(used)g(for)e(train-)225 179 y(ing)j(and)g(50)g(for)h (testing.)20 b(Eac)o(h)15 b(data)f(p)q(oin)o(t)225 224 y(consisted)f(of)e(4)h(real-v)n(alued)f(attributes)i(and)225 270 y(one)23 b(of)g(three)h(class)g(lab)q(els.)45 b(The)23 b(\014gure)225 316 y(sho)o(ws)28 b(classi\014cation)f(p)q(erformance)g Fk(\006)g Fp(1)225 361 y(standard)22 b(error)g(\()p Fl(n)j Fp(=)f(5\))d(as)h(a)f(function)225 407 y(of)g(prop)q(ortion)h(missing)e (features)k(for)d(the)225 453 y(EM)k(algorithm)c(and)k(for)f(mean)f (imputa-)225 498 y(tion)9 b(\(MI\),)h(a)g(common)d(heuristic)k(where)g (the)225 544 y(missing)19 b(v)n(alues)i(are)g(replaced)h(with)f(their) 225 590 y(unconditional)13 b(means.)991 0 y 11367059 10230345 2039234 10722426 40455782 45520977 startTexFig 991 0 a /G2PSbegin {newpath 0 0 moveto 12 setlinewidth 0 0 0 setrgbcolor 1 setlinecap 0 setlinejoin 2 setmiterlimit /imtx matrix currentmatrix def /dmtx matrix defaultmatrix def} def /len {dup mul exch dup mul add sqrt} def /dotpat {0 imtx dtransform len 0 idtransform len}def /solid {{}0}def /dotted {[0 dotpat 3 dotpat ] 0}def /fewdotted {[0 dotpat 6 dotpat ] 0} def /longdashed {[10 dotpat 4 dotpat] 0}def /shortdashed {[4 dotpat] 0}def /dashed {[6 dotpat] 0} def /dotdashed {[1 dotpat 6 dotpat 10 dotpat 6 dotpat] 0}def /none {[0 dotpat 10000 dotpat] 0} def /linestyle {solid} def /ratio 1 def /symbsiz 20 def % symbol size/radius /symbw 40 def /symbh 40 def /patternw 20 def /fillcolor {1 1 1} def % setrgbcolor value for symbol insides /linecolor {0 0 0} def % set color value for lines /nofill {} def /colorfill {fillcolor setrgbcolor fill} def /symbfil {colorfill} def /ifpath {pathbbox eq {eq {false} {true} ifelse} {pop pop true} ifelse} def /ifheight {pathbbox exch pop eq {pop false} {pop true} ifelse} def /crossfill { gsave 1.0 1.0 1.0 setrgbcolor fill grestore % wipe the inside clean clip currentpoint 0 patternw symbw {0 patternw symbh {patternw patternw rlineto patternw neg 0 rmoveto patternw patternw neg rlineto patternw neg patternw rmoveto pop} for patternw symbh patternw add patternw idiv patternw mul neg rmoveto pop} for stroke newpath moveto} def /plusfill { gsave 1.0 1.0 1.0 setrgbcolor fill grestore % wipe the inside clean clip currentpoint 0 patternw symbw {0 patternw symbh {patternw 0 rlineto patternw 2 div neg 0 rmoveto 0 patternw rlineto patternw 2 div neg 0 rmoveto pop} for patternw symbh patternw add patternw idiv patternw mul neg rmoveto pop} for stroke newpath moveto} def /txtpath 0 def % direction for strings in degrees /txtpos [0 0] def % positioning of strings relative to % current position /subpos [0 0] def /txtspace 1 def % space between letters in x direction /fontsiz 15 def % size of font /spacesiz 16 def % size for space character /foostr () def /pairup {moveto lineto stroke} def /ifpairup {moveto lineto ifpath {stroke} if} def /dopairs { linecolor setrgbcolor {pairup} repeat} def /doline { linecolor setrgbcolor 3 1 roll moveto 1 sub {lineto} repeat stroke} def /fillarea { linecolor setrgbcolor 3 1 roll moveto 1 sub {lineto} repeat gsave closepath symbfil grestore stroke} def /docircle { newpath linestyle setdash symbsiz 0 360 arc gsave closepath % define cirlce symbw neg symbh 2 div neg rmoveto symbfil % move to corner before filling grestore linecolor setrgbcolor stroke } def /ori 0 def /doellipse { dup neg /movy exch def exch dup neg /movx exch def exch translate ori rotate 1 ratio scale newpath linestyle setdash 0 0 symbsiz 0 360 arc gsave closepath % define cirlce symbw neg symbh 2 div neg rmoveto symbfil % move to corner before filling grestore linecolor setrgbcolor stroke 1 ratio 1 exch div scale ori neg rotate movx movy translate} def /dobar {newpath dup 3 1 roll exch symbsiz sub exch moveto symbsiz 2 mul 0 rlineto sub dup /symbh exch def dup 0 exch rlineto symbsiz 2 mul neg 0 rlineto neg 0 exch rlineto ifheight {gsave closepath symbfil grestore} if ifheight {stroke} if} def /symbary [10 10 -20 0 0 -20 20 0 0 20] def /arydraw { /ard exch def currentpoint % save centre posn ard 0 get ard 1 get rmoveto % go to plotting point 2 2 ard length 1 sub % { dup 1 add ard exch get exch ard exch get rlineto } for gsave closepath moveto % return to centre symbw 2 div neg symbh 2 div neg rmoveto % bottom left corner ifpath {symbfil} if grestore ifpath {linecolor setrgbcolor stroke} if } def /plotsymb {dupxy /movy exch neg def /movx exch neg def moveto ori rotate symbary arydraw ori neg rotate movx movy moveto} def /sprnt {3 1 roll dup neg 4 1 roll exch dup neg 5 1 roll exch translate txtpath rotate puts txtpath neg rotate translate} def /puts {linecolor setrgbcolor dup dup stringwidth pop exch length txtspace mul add txtpos 0 get mul neg fontsiz txtpos 1 get mul neg moveto 0 0 8#040 txtspace 0 6 -1 roll awidthshow} def /showmark {docircle} def /dupxy {dup 3 2 roll dup 4 1 roll exch} def /nlin 0 def /offx 0 def /showkeyline {dupxy dupxy dupxy exch symbw nlin mul add exch ifpath {pairup} if pop pop} def /showkeysymb {dupxy exch offx add exch showmark} def /showkey {showkeyline /offx 0 def showkeysymb pop pop} def /stringmark {4 2 roll dup neg 5 1 roll exch dup neg 6 1 roll exch % make inverse co-ordinates translate txtpath rotate % move to string pos dup stringwidth pop exch length txtspace mul add % lengtt of first string exch dup stringwidth pop exch length txtspace mul add % length of full string txtpos 0 get mul sub % X pos for mark - sub was add before!! fontsiz txtpos 1 get 0.4 exch sub mul showkey txtpath neg rotate translate} def /Times-Roman findfont fontsiz scalefont setfont /mainfont /Times-Roman def /subfont mainfont def /subscale 0.8 def /substr {/cpath txtpath def 4 2 roll dup neg 5 1 roll exch dup neg 6 1 roll exch % make inverse co-ordinates translate txtpath rotate % move to string pos dup stringwidth pop exch length txtspace mul add % lengtt of first string exch dup stringwidth pop exch length txtspace mul add % length of full string txtpos 0 get mul sub subpos 0 get foostr stringwidth pop mul add % X pos for mark fontsiz txtpos 1 get 0.4 exch sub subpos 1 get add mul % Ypos /txtpath 0 def /txtpos [0. 0.4] def subfont findfont fontsiz subscale mul scalefont setfont foostr sprnt /txtpath cpath def txtpath neg rotate translate mainfont findfont fontsiz scalefont setfont} def G2PSbegin 18 36 translate 0.034965 0.034965 scale 0 0 translate 186 3973 translate 16 setlinewidth solid setdash /linestyle {solid} def /linecolor {0.0 0.0 0.0} def 2612 2080 15200 2080 2612 2080 2612 1904 5129 2080 5129 1904 7647 2080 7647 1904 10164 2080 10164 1904 12682 2080 12682 1904 15200 2080 15200 1904 7 dopairs 2186 2540 2186 13365 2186 2540 2010 2540 2186 5246 2010 5246 2186 7952 2010 7952 2186 10658 2010 10658 2186 13365 2010 13365 6 dopairs 20 setlinewidth solid setdash /linestyle {solid} def 32 setlinewidth solid setdash /linestyle {solid} def /symbfil {colorfill} def /fillcolor {0.0 0.0 0.0} def /patternw 103 def /symbsiz 103 def /symbw 206 def /symbh 206 def /ori 0.00 def /showmark {docircle} def 20 setlinewidth solid setdash /linestyle {solid} def 2612 12715 2612 12499 2612 12499 2612 12282 2714 12715 2510 12715 2714 12282 2510 12282 3871 12824 3871 12661 3871 12661 3871 12499 3973 12824 3769 12824 3973 12499 3769 12499 5759 12853 5759 12715 5759 12715 5759 12578 5861 12853 5657 12853 5861 12578 5657 12578 8906 12027 8906 11308 8906 11308 8906 10589 9008 12027 8804 12027 9008 10589 8804 10589 12053 11958 12053 11308 12053 11308 12053 10659 12155 11958 11951 11958 12155 10659 11951 10659 13941 11648 13941 11146 13941 11146 13941 10644 14043 11648 13839 11648 14043 10644 13839 10644 24 dopairs newpath 2612 12499 3871 12661 5759 12715 8906 11308 12053 11308 13941 11146 6 doline 2612 12499 3871 12661 5759 12715 8906 11308 12053 11308 13941 11146 6 {showmark} repeat 20 setlinewidth dotted setdash /linestyle {dotted} def 32 setlinewidth solid setdash /linestyle {solid} def /fillcolor {0.0 0.0 0.0} def /symbfil {nofill} def /patternw 103 def /symbsiz 103 def /symbw 206 def /symbh 206 def /ori 0.00 def /showmark {plotsymb} def /symbary [103 103 -206 0 0 -206 206 0 0 206] def % Square 20 setlinewidth solid setdash /linestyle {solid} def 2612 12715 2612 12499 2612 12499 2612 12282 2714 12715 2510 12715 2714 12282 2510 12282 3871 12529 3871 12391 3871 12391 3871 12253 3973 12529 3769 12529 3973 12253 3769 12253 5759 12628 5759 12445 5759 12445 5759 12261 5861 12628 5657 12628 5861 12261 5657 12261 8906 11906 8906 11579 8906 11579 8906 11252 9008 11906 8804 11906 9008 11252 8804 11252 12053 6776 12053 6004 12053 6004 12053 5232 12155 6776 11951 6776 12155 5232 11951 5232 20 dopairs 20 setlinewidth dotted setdash /linestyle {dotted} def newpath 2612 12499 3871 12391 5759 12445 8906 11579 12053 6004 13941 4434 6 doline 20 setlinewidth solid setdash /linestyle {solid} def 2612 12499 3871 12391 5759 12445 8906 11579 12053 6004 13941 4434 6 {showmark} repeat /fontsiz 768 def /spacesiz 51 def /fontsiz 768 def /spacesiz 51 def /mainfont /Times-Roman def mainfont findfont fontsiz scalefont setfont /txtspace 63 def /txtpos [0.50 1.00] def 8583 15125 (Classification with missing inputs) sprnt /txtpos [0.00 0.00] def /fontsiz 512 def /spacesiz 34 def /fontsiz 512 def /spacesiz 34 def /mainfont /Times-Roman def mainfont findfont fontsiz scalefont setfont /txtspace 42 def /txtpos [0.50 1.00] def 2612 1744 (0) sprnt 5129 1744 (20) sprnt 7647 1744 (40) sprnt 10164 1744 (60) sprnt 12682 1744 (80) sprnt 15200 1744 (100) sprnt /txtpos [1.00 0.35] def 1850 2540 (20) sprnt 1850 5246 (40) sprnt 1850 7952 (60) sprnt 1850 10658 (80) sprnt 1850 13365 (100) sprnt /fontsiz 771 def /spacesiz 51 def /fontsiz 771 def /spacesiz 51 def /mainfont /Times-Roman def mainfont findfont fontsiz scalefont setfont /txtspace 64 def /txtpos [0.50 1.00] def 8729 1061 (\% missing features) sprnt 15024 11604 (EM) sprnt /txtpath 90 def -1 7793 (\% correct classification) sprnt /txtpath 0 def 14924 4957 (MI) sprnt -186 -3973 translate 0 0 translate 28.600028 28.600028 scale -18 -36 translate showpage endTexFig 225 686 a Fp(estimators)e(tak)o(e)g(adv)n(an)o(tage)f(of)h(the)h (explicit)f(represen)o(tation)i(of)e(the)h(input/output)f(densit)o(y) 225 732 y(b)o(y)j(selecting)g(one)g(of)g(the)g(sev)o(eral)h(solutions)e (to)h(the)g(in)o(v)o(erse.)225 832 y Fq(4.2)48 b(Classi\014cation)225 917 y Fp(Classi\014cation)15 b(problems)f(in)o(v)o(olv)o(e)g(learning)g (a)h(mapping)e(from)h(an)h(input)g(space)h(in)o(to)f(a)g(set)225 962 y(of)f(discrete)j(class)f(lab)q(els.)21 b(The)16 b(densit)o(y)f(estimation)f(framew)o(ork)f(presen)o(ted)k(in)e(this)g (pap)q(er)225 1008 y(lends)g(itself)f(to)g(solving)f(classi\014cation)h (problems)f(b)o(y)h(estimating)f(the)i(join)o(t)e(densit)o(y)i(of)e (the)225 1054 y(input)h(and)h(class)g(lab)q(el)f(using)g(a)g(mixture)g (mo)q(del.)k(F)m(or)c(example,)f(if)h(the)h(inputs)g(ha)o(v)o(e)f (real-)225 1099 y(v)n(alued)f(attributes)h(and)f(there)i(are)f Fl(D)g Fp(class)g(lab)q(els,)f(a)g(mixture)f(mo)q(del)g(with)h (Gaussian)g(and)225 1145 y(m)o(ultinom)o(ia)o(l)e(comp)q(onen)o(ts)i (will)g(b)q(e)h(used:)270 1248 y Fl(P)6 b Fp(\()p Fq(x)p Fl(;)h Fk(C)13 b Fp(=)f Fl(d)p Fk(j)p Fl(\022)q Fp(\))f(=)580 1196 y Fh(M)567 1208 y Fg(X)568 1297 y Fh(j)r Fi(=1)634 1248 y Fl(P)6 b Fp(\()p Fl(!)709 1254 y Fh(j)726 1248 y Fp(\))846 1220 y Fl(\026)871 1226 y Fh(j)r(d)p 747 1238 258 2 v 747 1277 a Fp(\(2)p Fl(\031)q Fp(\))825 1265 y Fh(n=)p Fi(2)881 1277 y Fk(j)p Fp(\006)923 1283 y Fh(j)940 1277 y Fk(j)952 1265 y Fi(1)p Fh(=)p Fi(2)1016 1248 y Fp(exp)p Fk(f\000)1137 1220 y Fp(1)p 1137 1238 21 2 v 1137 1276 a(2)1163 1248 y(\()p Fq(x)k Fk(\000)f Ff(\026)1285 1258 y Fh(j)1302 1248 y Fp(\))1318 1230 y Fh(T)1344 1248 y Fp(\006)1374 1230 y Fj(\000)p Fi(1)1374 1259 y Fh(j)1419 1248 y Fp(\()p Fq(x)g Fk(\000)h Ff(\026)1540 1258 y Fh(j)1558 1248 y Fp(\))p Fk(g)p Fl(;)44 b Fp(\(15\))225 1354 y(denoting)20 b(the)h(join)o(t)f(probabilit)o(y)f(that)h(the)h (data)g(p)q(oin)o(t)f(is)g Fq(x)h Fp(and)f(b)q(elongs)h(to)f(class)h Fl(d)p Fp(,)225 1400 y(where)16 b(the)f Fl(\026)443 1406 y Fh(j)r(d)492 1400 y Fp(are)g(the)g(parameters)f(for)g(the)h(m)o (ultinom)o(ia)o(l.)h(Once)g(this)f(densit)o(y)f(has)h(b)q(een)225 1445 y(estimated,)e(the)i(maxim)n(um)10 b(lik)o(eliho)q(o)q(d)i(lab)q (el)h(for)h(a)g(particular)f(input)h Fq(x)g Fp(ma)o(y)f(b)q(e)h (obtained)225 1491 y(b)o(y)c(computing)e Fl(P)e Fp(\()p Fk(C)13 b Fp(=)f Fl(d)p Fk(j)p Fq(x)p Fl(;)7 b(\022)q Fp(\).)17 b(Similarl)o(y)m(,)7 b(the)k(class)f(conditional)f(densities) i(can)f(b)q(e)g(deriv)o(ed)225 1537 y(b)o(y)15 b(ev)n(aluating)f Fl(P)6 b Fp(\()p Fq(x)p Fk(jC)16 b Fp(=)f Fl(d;)7 b(\022)q Fp(\).)22 b(Conditionalizing)13 b(o)o(v)o(er)j(classes)h(in)e(this)g(w) o(a)o(y)g(yields)h(class)225 1582 y(conditional)j(densities)j(whic)o(h) e(are)h(in)f(turn)h(mixtures)f(of)g(Gaussians.)38 b(Figure)20 b(1)h(sho)o(ws)225 1628 y(the)d(p)q(erformance)g(of)e(the)j(EM)e (algorithm)e(on)i(an)h(example)e(classi\014cation)h(problem)f(with)225 1674 y(v)n(arying)e(prop)q(ortions)h(of)g(missing)e(features.)23 b(W)m(e)15 b(ha)o(v)o(e)g(also)g(applied)g(these)h(algorithms)d(to)225 1719 y(the)i(problems)e(of)g(clustering)i(35-dimensional)c(greyscale)k (images)d(and)i(appro)o(ximating)d(the)225 1765 y(kinematics)i(of)g(a)h (three-join)o(t)g(planar)f(arm)f(from)g(incomplete)h(data.)225 1881 y Fm(5)56 b(Discussion)225 1976 y Fp(Densit)o(y)12 b(estimation)e(in)i(high)f(dimensions)g(is)h(generally)f(considered)j (to)e(b)q(e)g(more)f(di\016cult|)225 2022 y(requiring)h(more)g (parameters|than)g(function)g(appro)o(ximation.)j(The)e(densit)o (y-estimation-)225 2067 y(based)e(approac)o(h)g(to)f(learning,)g(ho)o (w)o(ev)o(er,)h(has)g(t)o(w)o(o)f(adv)n(an)o(tages.)16 b(First,)11 b(it)g(p)q(ermits)f(ready)h(in-)225 2113 y(corp)q(oration)h(of)f(results)i(from)e(the)h(statistical)g (literature)g(on)g(missing)e(data)i(to)g(yield)f(\015exible)225 2159 y(sup)q(ervised)k(and)f(unsup)q(ervised)h(learning)e(arc)o (hitectures.)20 b(This)14 b(is)f(ac)o(hiev)o(ed)h(b)o(y)f(com)o(bining) 225 2204 y(t)o(w)o(o)g(branc)o(hes)h(of)e(application)g(of)h(the)g(EM)h (algorithm)c(yielding)i(a)h(set)h(of)e(learning)h(rules)g(for)225 2250 y(mixtures)g(under)i(incomplete)e(sampling.)p eop 8 7 bop 225 42 a Fp(Second,)18 b(estimating)d(the)j(densit)o(y)f (explicitly)f(enables)h(us)h(to)e(represen)o(t)k(an)o(y)c(relation)g(b) q(e-)225 87 y(t)o(w)o(een)10 b(the)h(v)n(ariables.)k(Densit)o(y)10 b(estimation)e(is)h(fundamen)o(tally)e(more)i(general)h(than)f (function)225 133 y(appro)o(ximation)k(and)i(this)h(generalit)o(y)f(is) h(needed)h(for)f(a)f(large)h(class)g(of)f(learning)g(problems)225 178 y(arising)e(from)f(in)o(v)o(erting)g(causal)i(systems)g (\(Ghahramani,)c(1994\).)17 b(These)e(problems)e(cannot)225 224 y(b)q(e)i(solv)o(ed)f(easily)f(b)o(y)h(traditional)f(function)h (appro)o(ximation)d(tec)o(hniques)16 b(since)e(the)h(data)f(is)225 270 y(not)g(generated)h(from)d(noisy)i(samples)f(of)g(a)g(function,)h (but)g(rather)g(of)g(a)f(relation.)225 365 y Fq(Ac)o(kno)o(wledgemen)o (ts)225 444 y Fp(Thanks)g(to)h(D.)e(M.)h(Titterington)g(and)h(Da)o(vid) e(Cohn)h(for)g(helpful)g(commen)o(ts.)j(This)d(pro)r(ject)225 490 y(w)o(as)h(supp)q(orted)h(in)e(part)h(b)o(y)f(gran)o(ts)h(from)e (the)i(McDonnell-P)o(ew)g(F)m(oundation,)e(A)m(TR)g(Audi-)225 536 y(tory)k(and)h(Visual)e(P)o(erception)j(Researc)o(h)g(Lab)q (oratories,)e(Siemens)g(Corp)q(oration,)g(the)h(Na-)225 581 y(tional)c(Science)i(F)m(oundation,)d(and)i(the)h(O\016ce)f(of)g (Na)o(v)n(al)e(Researc)o(h.)20 b(The)14 b(iris)g(data)f(set)i(w)o(as) 225 627 y(obtained)f(from)e(the)i(UCI)g(Rep)q(ository)g(of)f(Mac)o (hine)h(Learning)g(Databases.)225 743 y Fm(References)225 820 y Fp(Breiman,)d(L.,)g(F)m(riedman,)f(J.)i(H.,)g(Olshen,)g(R.)f(A.,) h(and)g(Stone,)g(C.)f(J.)h(\(1984\).)i Fo(Classi\014c)n(ation)308 866 y(and)i(R)n(e)n(gr)n(ession)e(T)m(r)n(e)n(es)p Fp(.)j(W)m(adsw)o (orth)d(In)o(ternational)f(Group,)g(Belmon)o(t,)f(CA.)225 925 y(Dempster,)g(A.)g(P)m(.,)g(Laird,)g(N.)g(M.,)g(and)g(Rubin,)f(D.)h (B.)g(\(1977\).)j(Maxim)o(um)9 b(lik)o(eliho)q(o)q(d)i(from)308 971 y(incomplete)k(data)g(via)g(the)h(EM)g(algorithm.)21 b Fo(J.)16 b(R)n(oyal)h(Statistic)n(al)f(So)n(ciety)h(Series)f(B)p Fp(,)308 1017 y(39:1{38.)225 1076 y(Duda,)i(R.)f(O.)g(and)h(Hart,)g(P)m (.)f(E.)h(\(1973\).)29 b Fo(Pattern)18 b(Classi\014c)n(ation)g(and)h (Sc)n(ene)h(A)o(nalysis)p Fp(.)308 1122 y(Wiley)m(,)12 b(New)i(Y)m(ork.)225 1181 y(F)m(riedman,)i(J.)h(H.)g(\(1991\).)27 b(Multiv)n(ariate)16 b(adaptiv)o(e)h(regression)h(splines.)29 b Fo(The)18 b(A)o(nnals)g(of)308 1227 y(Statistics)p Fp(,)13 b(19:1{141.)225 1286 y(Ghahramani,)d(Z.)i(\(1994\).)j(Solving)c (in)o(v)o(erse)j(problems)d(using)i(an)f(EM)h(approac)o(h)f(to)h (densit)o(y)308 1332 y(estimation.)20 b(In)15 b Fo(Pr)n(o)n(c)n(e)n(e)n (dings)h(of)g(the)g(1993)h(Conne)n(ctionist)g(Mo)n(dels)f(Summer)g (Scho)n(ol)p Fp(.)308 1377 y(Erlbaum,)c(Hillsdale,)g(NJ.)225 1437 y(Jacobs,)17 b(R.,)f(Jordan,)g(M.,)g(No)o(wlan,)g(S.,)f(and)i(Hin) o(ton,)f(G.)f(\(1991\).)24 b(Adaptiv)o(e)16 b(mixture)g(of)308 1483 y(lo)q(cal)d(exp)q(erts.)20 b Fo(Neur)n(al)14 b(Computation)p Fp(,)g(3:79{87.)225 1542 y(Jordan,)j(M.)g(and)g(Jacobs,)g(R.)f (\(1994\).)27 b(Hierarc)o(hical)16 b(mixtures)h(of)f(exp)q(erts)i(and)f (the)h(EM)308 1588 y(algorithm.)d Fo(Neur)n(al)g(Computation)p Fp(,)e(6:181{214.)225 1647 y(Little,)j(R.)g(J.)g(A.)g(and)h(Rubin,)f (D.)f(B.)i(\(1987\).)25 b Fo(Statistic)n(al)16 b(A)o(nalysis)h(with)g (Missing)g(Data)p Fp(.)308 1693 y(Wiley)m(,)12 b(New)i(Y)m(ork.)225 1752 y(McLac)o(hlan,)e(G.)g(and)g(Basford,)h(K.)g(\(1988\).)i Fo(Mixtur)n(e)e(mo)n(dels:)19 b(Infer)n(enc)n(e)13 b(and)i(applic)n (ations)308 1798 y(to)g(clustering.)j Fp(Marcel)c(Dekk)o(er.)225 1857 y(No)o(wlan,)d(S.)h(J.)g(\(1991\).)j Fo(Soft)f(Comp)n(etitive)f(A) n(daptation:)18 b(Neur)n(al)13 b(Network)g(L)n(e)n(arning)g(A)o(lgo-) 308 1903 y(rithms)h(b)n(ase)n(d)h(on)h(Fitting)f(Statistic)n(al)f (Mixtur)n(es)p Fp(.)k(CMU-CS-91-126,)12 b(Sc)o(ho)q(ol)h(of)h(Com-)308 1949 y(puter)h(Science,)g(Carnegie)f(Mellon)f(Univ)o(ersit)o(y)m(,)g (Pittsburgh,)h(P)m(A.)225 2008 y(Sp)q(ec)o(h)o(t,)19 b(D.)d(F.)h(\(1991\).)28 b(A)17 b(general)h(regression)g(neural)f(net)o (w)o(ork.)29 b Fo(IEEE)18 b(T)m(r)n(ans.)g(Neur)n(al)308 2054 y(Networks)p Fp(,)13 b(2\(6\):568{576.)225 2113 y(T)m(resp,)19 b(V.,)f(Hollatz,)f(J.,)h(and)g(Ahmad,)f(S.)g(\(1993\).) 29 b(Net)o(w)o(ork)18 b(structuring)g(and)g(training)308 2159 y(using)c(rule-based)i(kno)o(wledge.)j(In)c(Hanson,)f(S.)g(J.,)g (Co)o(w)o(an,)f(J.)i(D.,)e(and)h(Giles,)g(C.)g(L.,)308 2204 y(editors,)h Fo(A)n(dvanc)n(es)h(in)f(Neur)n(al)g(Information)h (Pr)n(o)n(c)n(essing)f(Systems)h(5)p Fp(.)e(Morgan)g(Kauf-)308 2250 y(man)e(Publishers,)j(San)e(Mateo,)h(CA.)p eop end userdict /end-hook known{end-hook}if