(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvipsk 5.58f Copyright 1986, 1994 Radical Eye Software %%Title: paper.dvi %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%DocumentFonts: Times-Roman Times-Bold Times-Italic Courier %%EndComments %DVIPSCommandLine: dvips paper.dvi %DVIPSParameters: dpi=300, compressed, comments removed %DVIPSSource: TeX output 1998.08.24:1207 %%BeginProcSet: texc.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]/id ch-image N /rw ch-width 7 add 8 idiv string N /rc 0 N /gp 0 N /cp 0 N{rc 0 ne{rc 1 sub /rc X rw}{G}ifelse}imagemask restore}B /G{{id gp get /gp gp 1 add N dup 18 mod S 18 idiv pl S get exec}loop}B /adv{cp add /cp X}B /chg{rw cp id gp 4 index getinterval putinterval dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 2 idiv S 128 and or}ifelse}ifelse put 1 adv}B /clr{rw cp 2 index string putinterval adv}B /set{rw cp fillstr 0 4 index getinterval putinterval adv}B /fillstr 18 string 0 1 17{2 copy 255 put pop}for N /pl[{adv 1 chg} {adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{ adv rsh nd}{1 add adv}{/rc X nd}{1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore userdict /eop-hook known{eop-hook}if showpage}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: texps.pro TeXDict begin /rf{findfont dup length 1 add dict begin{1 index /FID ne 2 index /UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics exch def dict begin Encoding{exch dup type /integertype ne{pop pop 1 sub dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def} ifelse}forall Metrics /Metrics currentdict end def[2 index currentdict end definefont 3 -1 roll makefont /setfont load]cvx def}def /ObliqueSlant{dup sin S cos div neg}B /SlantFont{4 index mul add}def /ExtendFont{3 -1 roll mul exch}def /ReEncodeFont{/Encoding exch def}def end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale true def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (paper.dvi) @start /Fa 1 49 df<1218A31230A31260A312C0A2050B7E8B09>48 D E /Fb 4 108 df<13201370A313B8A3EA011CA2EA031EEA020EA2487EEA07FFEA0407 38080380A2001813C01301123838FC07F815157F9419>97 DII<38FF81F8381C01E0148014001302 5B5B5B1330137013B8EA1D1C121EEA1C0E7F14801303EB01C014E014F038FF83FC16157F 941A>107 D E /Fc 133[25 24[25 25 56[25 39[{}4 41.666668 /Courier rf /Fd 3 90 df80 D88 DI E /Fe 14 121 df<1380EA0100120212065AA25AA25AA35AA412E0AC1260A47EA37EA2 7EA27E12027EEA0080092A7C9E10>40 D<7E12407E12307EA27EA27EA37EA41380AC1300 A41206A35AA25AA25A12205A5A092A7E9E10>I48 D<5A1207123F12C71207B3A5EAFFF80D1C7C9B15>II<130CA2131C133CA2135C13DC139CEA 011C120312021204120C1208121012301220124012C0B512C038001C00A73801FFC0121C 7F9B15>52 D<13F0EA030CEA0404EA0C0EEA181E1230130CEA7000A21260EAE3E0EAE430 EAE818EAF00C130EEAE0061307A51260A2EA7006EA300E130CEA1818EA0C30EA03E0101D 7E9B15>54 D<126012F0A212601200AA126012F0A212701210A41220A212401280041A7C 910C>59 D<007FB512C0B612E0C9FCA8B612E06C14C01B0C7E8F20>61 D97 D103 D<39FC7E07E0391C838838 391D019018001EEBE01C001C13C0AD3AFF8FF8FF8021127F9124>109 D114 D<38FF0FE0381E0700EA1C06EA0E046C5AEA039013B0EA01E012007F12011338EA021C12 04EA0C0E487E003C138038FE1FF014127F9116>120 D E /Ff 9 107 df<126012F0A2126004047C8B0C>1 D<0040132000C01360006013C0383001803818 0300EA0C066C5A6C5AEA01B0EA00E0A2EA01B0EA0318EA060C487E487E38300180386000 C04813600040132013147A9320>I10 D<12C012F0123C120FEA03C0EA00F0133C130FEB03C0EB00F0143C 140FEC0380EC0F00143C14F0EB03C0010FC7FC133C13F0EA03C0000FC8FC123C127012C0 C9FCA7007FB5FCB6128019227D9920>21 D<13C0485AA348C9FCA212065A121C1230B712 F0A20030C9FC121C120C7E7EA26C7EA36C7E24167D942A>32 D50 D<133C13E0EA01C013801203AD13005A121C12F0121C12077E1380 AD120113C0EA00E0133C0E297D9E15>102 D<12F0121C12077E1380AD120113C0EA00E0 133C13E0EA01C013801203AD13005A121C12F00E297D9E15>I<12C0B3B3A502297B9E0C> 106 D E /Fg 81[21 52[18 18 28 18 21 12 16 16 1[21 21 21 30 12 2[12 21 21 12 18 21 18 21 21 10[25 86[{}24 41.666668 /Times-Italic rf /Fh 16 90 df<13201370A313B8A3EA011CA3EA020EA2EA060FEA04 07EA07FF38080380A3381001C0123838FE0FF815157F9419>65 D68 DI73 DI<38FF83F8381C00E01480 EB010013025B5B5B1330137013B8EA1D1C121EEA1C0E7F14801303EB01C014E014F038FF 83FC16157F941A>II<00FE EB0FE0001E140000171317A338138027A23811C047A33810E087A2EB7107A3133AA2131C A2123839FE083FE01B157F941F>I<38FC03F8381E00E0001F13401217EA138013C01211 EA10E01370A21338131C131E130E130714C0130313011300123800FE134015157F9419> II82 DI<38FF83F8381C00E01440AE00 0C13C0000E138038060100EA0386EA00FC15157F9419>85 D<38FF01F8383C0060001C13 40A26C1380A338070100A21383EA0382A2EA01C4A213ECEA00E8A21370A3132015157F94 19>I<38FF8FF0381E0380000E1300EA0F02EA0784120313C8EA01D0EA00F0A213701378 13BCEA011C7FEA020F487EEB0380000813C0121C38FE07F815157F9419>88 D<38FF80FE381E0030000E13206C134013800003138013C100011300EA00E213F2137413 7C1338A848B4FC1715809419>I E /Fi 198[23 23 23 23 23 23 23 23 23 23 48[{}10 45.833332 /Times-Roman rf /Fj 7 62 df<1360AAB512F0A238006000AA14167E9119>43 D<120C121C12EC120CAFEAFFC00A13 7D9211>49 D<121FEA60C01360EAF07013301260EA0070A2136013C012011380EA02005A EA08101210EA2020EA7FE012FF0C137E9211>II<1360 13E0A2EA016012021206120C120812101220126012C0EAFFFCEA0060A5EA03FC0E137F92 11>I56 D<387FFFE0B512F0C8FCA6B512F06C13 E0140A7E8B19>61 D E /Fk 9 117 df22 DI<124012E012601220A31240A2128003097D82 0A>59 D73 D76 D83 D<121E12065AA45A1338135C139CEA3118EA36001238EA3F80EA61C0EA60C8A3EAC0D013 600E147F9312>107 D<3830F87C38590C86384E0D06EA9C0EEA980C1218A248485A1580 1418A23960301900140E190D7F8C1D>109 D<1204120CA35AEAFF80EA1800A25AA45A12 61A212621264123809127F910D>116 D E /Fl 26 122 df<3801803000031370A33807 00E0A4380E01C0A4381C0388A3EA1E07383E1990383BE0E00038C7FCA25AA45AA25A151B 7F9119>22 D<007E1360000E13E0A3381C01C0A2EB03801400485A130E130C5B485A5BEA 71C00073C7FC12FC12F013127E9115>I<5B1302A45BA45BA2137E3801C980380710E000 0C13600018137000381330EA7020A200E01370A2134014E0A2386041C0EB838038308600 EA1C9CEA07E00001C7FCA41202A414257E9C19>30 D<14401480A4EB0100A41302A2001C 13060027130EEA4704140600871302A2EA0E08A2001C1304A2EB1008A214101420EB2040 000C138038072300EA01FCEA0040A45BA417257E9C1B>32 D<126012F0A2126004047C83 0C>58 D<126012F0A212701210A41220A212401280040C7C830C>I<3801FFC038003C00 1338A45BA45BA4485AA4485AA448C7FCA45AEAFFE0121C7E9B12>73 DI<3801FFE038003C001338A45BA45BA4485AA438 038002A31404EA0700140C14181438000E13F0B5FC171C7E9B1C>76 D78 DI<48B5FC39003C03C090383800E015F01570 A24913F0A315E0EBE001EC03C0EC0700141E3801FFF001C0C7FCA3485AA448C8FCA45AEA FFE01C1C7E9B1B>I<001FB512F0391C03807039300700300020142012601240130E1280 A2000014005BA45BA45BA45BA41201EA7FFF1C1C7F9B18>84 D<3A01FFC0FF803A001E00 3C00011C13306D13205D010F5B6D48C7FC1482EB038414CCEB01D814F05C130080EB0170 EB0278EB04381308EB103CEB201CEB401EEB800E3801000F00027F1206001E497E39FF80 3FF0211C7F9B22>88 D<39FFE007F8390F0001E0158015006C13026D5A00035BEBC01814 1000015B6D5A00005B01F1C7FC13F21376137C1338A25BA45BA4485AEA1FFC1D1C7F9B18 >I97 D<123F1207A2120EA45AA4EA39E0EA3A30EA3C1812381270131CA3 EAE038A313301370136013C01261EA2300121E0E1D7E9C12>I105 D<1307130FA213061300A61378139CEA010C1202131C12041200A21338A41370A413 E0A4EA01C01261EAF180EAF30012E6127C1024809B11>II<39381F81F0394E20C618394640E81CEB80F0EA 8F00008E13E0120EA2391C01C038A315703938038071A215E115E23970070064D8300313 3820127E9124>109 DI<13C01201A3EA0380A4 EAFFF0EA0700A3120EA45AA4EA3820A21340A2EA1880EA0F000C1A80990F>116 D<001C13C0EA27011247A238870380A2120EA2381C0700A438180E20A3EA1C1E380C2640 3807C38013127E9118>I<380787803808C8403810F0C03820F1E0EBE3C03840E1803800 E000A2485AA43863808012F3EB810012E5EA84C6EA787813127E9118>120 D<001C13C0EA27011247A238870380A2120EA2381C0700A4EA180EA3EA1C1EEA0C3CEA07 DCEA001C1318EA6038EAF0305B485AEA4180003EC7FC121A7E9114>I E /Fm 47[42 21[18 8[21 1[23 23 3[18 47[18 21 21 30 21 21 12 16 14 21 21 21 21 32 12 21 12 12 21 21 14 18 21 18 21 18 6[25 30 1[39 30 30 25 23 28 1[23 30 30 37 25 30 16 14 30 30 23 25 30 28 28 30 1[18 3[12 12 21 21 21 21 21 21 21 21 21 21 12 10 14 10 2[14 14 14 32 38[{}77 41.666668 /Times-Roman rf /Fn 136[30 21 23 14 16 18 2[21 23 35 12 23 1[12 23 21 14 18 23 18 1[21 14[30 4[39 3[16 32 1[25 1[30 2[30 11[21 21 21 21 21 2[10 46[{}32 41.666668 /Times-Bold rf /Fo 134[17 1[24 2[11 13 15 2[17 5[9 3[15 18 15 18 17 21[26 5[22 2[22 24 6[11 17 17 17 1[17 17 1[17 3[8 46[{}24 33.333332 /Times-Bold rf /Fp 81[17 52[15 1[22 15 17 9 13 13 17 17 17 17 24 9 15 1[9 17 17 9 15 17 15 17 17 10[20 24 18 17 20 1[20 24 22 28 18 1[15 11 24 1[20 20 24 22 20 20 6[11 17 1[17 1[17 17 17 17 17 17 1[8 11 8 5[26 38[{}56 33.333332 /Times-Italic rf /Fq 17 88 df<124012E0124003037E8209>46 D<1360A313F0A2487E1338A2EA021CA3487E A2EA07FEEA0807A200181380EA1003123838FC0FF014147F9318>65 D<3801F080EA060DEA1C03EA18011230EA7000126000E01300A600601380127012303818 0100EA1C02EA060CEA01F011147E9317>67 DII<38FF9FF0381C0380A8EA1FFFEA1C03A938FF9FF014147F9318>72 DII<38FF81F8381C00C01480EB01001302130C5B1320137013F0EA1D38EA 1E3CEA1C1C7F130F7FEB038014C0EB01E038FF87F81514809318>II<00FEEB3F80001EEB3C00A20017135CA23813 809CA33811C11CA3EA10E2A21374A31338A2123839FE10FF8019147F931D>I<38FC07F0 381E01C0EB00801217EA138013C01211EA10E013F013701338131CA2130E1307A2130313 011238EAFE0014147F9318>II< EAFFF8EA1C0E7FEB0380A4EB0700130EEA1FF8EA1C0C130E7FA41408A2EB039838FF81F0 1514809317>82 DI<38FF87F0381C01C0EB0080AE 380E0100EA06026C5AEA00F814147F9318>85 D<39FF1FE3F039380700E01540001CEB80 80A3390E09C100A3380710E2A33803A074A33801C038A4380080101C147F9320>87 D E /Fr 134[33 33 1[33 37 22 26 29 1[37 33 37 55 18 37 1[18 37 33 22 29 37 29 1[33 19[63 18[22 58[{}23 66.666664 /Times-Bold rf /Fs 4 49 df0 D<1204A3EAC460EAF5E0EA3F 80EA0E00EA3F80EAF5E0EAC460EA0400A30B0D7E8D11>3 D13 D<1204120EA2121CA312 38A212301270A21260A212C0A2070F7F8F0A>48 D E /Ft 156[13 99[{}1 29.166668 /Times-Roman rf /Fu 47[33 30[17 2[18 51[15 17 17 24 17 17 9 13 11 17 17 17 17 26 9 17 9 9 17 17 11 15 17 15 17 15 6[20 24 1[31 1[24 20 18 22 1[18 24 24 30 20 24 13 11 24 24 18 20 24 22 22 24 31 15 4[9 17 17 17 17 17 17 17 17 17 17 9 8 11 8 2[11 11 11 39[{}72 33.333332 /Times-Roman rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 1324 70 a Fu(Machine)7 b(Learning,)g(??,)h(1\26111)f(\(1998\)) 711 101 y Ft(c)701 102 y Fs(\015)742 108 y Fu(1998)g(Kluwer)h(Academic) f(Publishers,)h(Boston.)j(Manufactured)6 b(in)i(The)g(Netherlands.)300 384 y Fr(Mixed)17 b(memory)i(Mark)o(o)o(v)f(models:)300 459 y(decomposing)h(complex)f(stochastic)h(pr)o(ocesses)300 534 y(as)e(mixtur)o(es)h(of)f(simpler)h(ones)300 633 y Fq(LA)m(WRENCE)9 b(K.)j(SA)o(UL)857 b Fu(lsaul@research.att.com)300 679 y Fp(A)o(T&T)9 b(Labs,)f(Florham)g(P)m(ark,)g(NJ)h(07932)300 762 y Fq(MICHAEL)g(I.)i(JORD)o(AN)845 b Fu(jordan@cs.berkeley)m(.edu) 300 807 y Fp(University)7 b(of)h(California,)g(Berkele)o(y)n(,)g(CA)h (94720)300 898 y Fo(Editor:)j Fu(Padhraic)7 b(Smyth)300 998 y Fo(Abstract.)30 b Fu(W)m(e)15 b(study)e(Markov)f(models)i(whose)f (state)h(spaces)f(arise)h(from)g(the)g(Cartesian)g(product)f(of)h(two)g (or)g(more)300 1037 y(discrete)d(random)e(v)o(ariables.)20 b(W)m(e)12 b(sho)o(w)f(ho)o(w)f(to)h(parameterize)f(the)h(transition)g (matrices)f(of)h(these)g(models)f(as)h(a)g(con)o(vex)300 1077 y(combination\320or)i(mixture\320of)h(simpler)g(dynamical)f (models.)31 b(The)15 b(parameters)e(in)i(these)f(models)g(admit)g(a)h (simple)300 1116 y(probabilistic)10 b(interpretation)h(and)f(can)g(be)h (\256tted)g(iterati)o(vely)g(by)g(an)f(Expectation-Maximization)f (\(EM\))i(procedure.)19 b(W)m(e)300 1156 y(deri)o(ve)13 b(a)g(set)h(of)g(generalized)e(Baum-W)m(elch)h(updates)g(for)g (factorial)h(hidden)e(Markov)f(models)i(that)h(make)f(use)g(of)g(this) 300 1195 y(parameterization.)d(W)m(e)f(also)e(describe)g(a)h(simple)f (iterati)o(ve)h(procedure)e(for)h(approximately)f(computing)g(the)i (statistics)g(of)g(the)300 1234 y(hidden)h(states.)18 b(Throughout,)9 b(we)h(gi)o(ve)g(examples)e(where)i(mixed)f(memory)g (models)g(provide)f(a)j(useful)e(representation)g(of)300 1274 y(complex)d(stochastic)h(processes.)300 1365 y Fo(K)o(eywords:)k Fu(Markov)5 b(models,)j(mixture)g(models,)f(discrete)h(time)g(series) 300 1487 y Fn(1.)42 b(Intr)o(oduction)300 1590 y Fm(The)8 b(modeling)e(of)h(time)g(series)h(is)f(a)h(fundamental)f(problem)f(in)h (machine)h(learning,)f(with)f(widespread)300 1640 y(applications.)14 b(These)d(include)e(speech)i(recognition)d(\(Rabiner)n(,)j(1989\),)e (natural)g(language)h(process-)300 1690 y(ing)g(\(Nadas,)i(1984\),)e (traf)o(\256c)h(surv)o(eillance)g(\(F)o(orbes)g(et)g(al.,)g(1995\),)f (protein)g(modeling)g(\(Haussler)g(et)300 1740 y(al.,)i(1993\),)e (musical)h(analysis/synthesis)e(\(Dirst)h(&)h(W)m(eigend,)g(1993\),)f (visual)g(gesture)g(recognition)300 1790 y(\(Y)l(amato)g(et)h(al.,)g (1992\),)f(and)g(numerous)g(others.)333 1841 y(Probabilistic)i(models)i (of)g(discrete)g(time)g(series)g(typically)f(start)g(from)h(some)h (form)e(of)h(Marko)o(v)300 1891 y(assumption\320namely)m(,)e(that)f (the)g(future)g(is)g(independent)g(of)g(the)g(past)h(gi)o(v)o(en)f(the) h(present.)19 b(F)o(or)12 b(the)300 1941 y(purpose)f(of)g(statistical)g (estimation,)g(problems)h(arise)g(if)f(either:)17 b(\(i\))11 b(the)g(system)h(possesses)h(a)f(lar)o(ge)300 1991 y(number)d(of)g(de)o (grees)i(of)e(freedom,)i(or)e(\(ii\))f(the)h(windo)o(w)f(of)h(present)h (kno)o(wledge)e(required)h(to)g(predict)300 2041 y(the)14 b(future)g(e)o(xtends)h(o)o(v)o(er)g(se)o(v)o(eral)g(time)g(steps.)28 b(In)14 b(these)h(cases,)j(the)c(number)g(of)g(parameters)i(to)300 2091 y(specify)10 b(the)f(Marko)o(v)g(model)g(can)h(o)o(v)o(erwhelm)h (the)e(amount)g(of)g(a)o(v)o(ailable)h(data.)15 b(In)9 b(particular)n(,)h(for)f(a)300 2140 y(system)j(with)e Fl(n)h Fm(possible)f(states)i(and)f(memory)h(length)e Fl(k)q Fm(,)i(the)f(number)g(of)g(free)h(parameters)g(scales)300 2190 y(e)o(xponentially)d(as)i Fl(n)606 2175 y Fk(k)q Fj(+1)668 2190 y Fm(.)333 2242 y(The)f(dif)o(\256culties)d(are)j (compounded)f(for)f(latent)g(v)o(ariable)h(models)g(in)f(which)h(the)g (Marko)o(v)f(assump-)300 2292 y(tion)j(applies)h(to)g(the)g(hidden)f (state)i(space.)22 b(In)12 b(this)f(case,)k(it)d(may)g(be)h (computationally)d(intractable)300 2342 y(to)j(infer)h(v)o(alues)g(for) f(the)h(hidden)f(states.)26 b(F)o(or)14 b(e)o(xample,)j(in)c (\256rst-order)g(hidden)g(Marko)o(v)g(models)300 2391 y(\(HMMs\),)e(computing)e(the)h(likelihood)e(of)i(a)i(sequence)f(of)g (observ)o(ations)e(scales)j(as)f Fl(n)1579 2376 y Fj(2)1598 2391 y Fm(,)g(where)g Fl(n)g Fm(is)300 2441 y(the)h(number)h(of)f (hidden)g(states)h(\(Rabiner)n(,)g(1989\).)21 b(In)13 b(practice,)h(e)o(xact)f(probabilistic)e(inference)i(is)300 2491 y(therefore)d(limited)f(to)h(HMMs)g(with)f(relati)o(v)o(ely)h (small)g(\(or)g(tightly)e(constrained\))h(state)i(spaces.)p eop %%Page: 2 2 2 1 bop 300 125 a Fi(2)1137 b Fh(SA)o(UL)13 b(AND)f(JORD)o(AN)333 266 y Fm(In)20 b(this)e(technical)i(note,)i(we)e(propose)f(a)h (principled)f(way)g(to)g(in)n(v)o(estigate)g(Marko)o(v)g(models)300 316 y(with)14 b(lar)o(ge)i(state)f(spaces.)32 b(This)15 b(is)g(done)g(by)f(representing)h(the)g(transition)e(matrix)i(as)h(a)f (con)n(v)o(e)o(x)300 366 y(combination\320or)7 b(mixture\320of)g (simpler)i(dynamical)g(models.)15 b(W)m(e)9 b(refer)h(to)e(the)h (resulting)e(models)300 415 y(as)12 b Fg(mixed)f(memory)h Fm(Marko)o(v)f(models.)18 b(While)11 b(the)g(use)g(of)g(mixture)f (distrib)o(utions)e(to)j(parameterize)300 465 y(higher)o(-order)g (Marko)o(v)i(models)f(is)h(well)f(kno)o(wn)f(\(Raftery)m(,)j(1985;)e (Ne)o(y)i(et)e(al,)i(1994;)e(MacDonald)300 515 y(&)f(Zucchini,)g (1997\),)f(here)h(we)g(apply)f(this)g(methodology)f(more)i(generally)f (to)g Fg(factorial)f Fm(models\320)300 565 y(models)15 b(in)e(which)i(lar)o(ge)f(state)h(spaces)h(are)f(represented)g(via)g (the)f(Cartesian)h(product)e(of)h(smaller)300 615 y(ones.)333 681 y(Our)7 b(note)h(b)o(uilds)e(on)h(earlier)h(work)e(describing)h (factorial)f(HMMs)i(\(Ghahramani)f(&)h(Jordan,)h(1997\))300 731 y(and)g(dynamic)h(probabilistic)d(networks)h(\(Binder)g(et)i(al.,)g (1997\).)k(These)d(papers)e(sho)o(w)g(that)g(comple)o(x)300 781 y(stochastic)14 b(processes)h(can)f(be)g(graphically)f(represented) h(by)g(sets)g(of)g(Marko)o(v)f(chains)h(connected)300 831 y(\(via)e(directed)f(links\))g(to)h(a)g(common)h(set)f(of)f(observ) o(able)h(nodes.)21 b(Such)12 b(models)g(arise)g(naturally)f(in)300 880 y(the)e(study)g(of)g(coupled)g(time)h(series,)g(where)h(the)e (observ)o(ations)f(ha)o(v)o(e)j(an)f Fg(a)f(priori)g Fm(decomposition)f(as)300 930 y(the)j(Cartesian)g(product)f(of)h(two)f (or)h(more)h(random)f(v)o(ariables.)18 b(F)o(actorial)11 b(HMMs)g(aim)h(to)e(combine)300 980 y(the)g(po)o(wer)f(of)h(latent,)f (distrib)o(uted)f(representations)h(with)g(the)h(richness)g(of)f (probabilistic)f(semantics)300 1030 y(\(W)n(illiams)g(&)h(Hinton,)f (1990\).)13 b(Capturing)7 b(this)h(type)g(of)g(probabilistic)e (reasoning)i(is)h(a)g(fundamental)300 1080 y(problem)h(in)f (arti\256cial)h(intelligence)f(\(Dean)i(&)g(Kanaza)o(wa,)h(1989\).)333 1146 y(W)m(e)e(belie)o(v)o(e)g(that)f(mix)o(ed)g(memory)h(Marko)o(v)f (models)g(ha)o(v)o(e)i(se)o(v)o(eral)f(adv)o(antages)g(for)f (representing)300 1196 y(comple)o(x)g(stochastic)g(processes)g(and)g (learning)f(from)g(e)o(xamples.)16 b(The)10 b(parameters)f(in)f(these)h (models)300 1246 y(admit)i(a)h(simple)f(probabilistic)e(interpretation) g(and)j(can)g(be)g(\256tted)e(iterati)o(v)o(ely)h(by)g(an)g (Expectation-)300 1295 y(Maximization)j(\(EM\))h(procedure)g (\(Dempster)h(et)f(al.,)i(1977\).)29 b(The)16 b(EM)f(algorithm)f(has)h (se)o(v)o(eral)300 1345 y(desirable)d(properties,)h(including)d (monotone)i(con)n(v)o(er)o(gence)i(in)e(log-likeli)o(hood)o(,)f(lack)h (of)g(step)h(size)300 1395 y(parameters,)k(and)e(naturalness)g(at)f (handling)f(probabilistic)g(constraints.)27 b(In)15 b(man)o(y)g (situations,)f(it)300 1445 y(pro)o(vides)f(a)g(compelling)f(alternati)o (v)o(e)h(to)g(gradient-based)f(learning)h(methods)g(\(Baldi)f(&)h (Chauvin,)300 1495 y(1996;)c(Binder)g(et)i(al.,)g(1997\).)333 1561 y(Mix)o(ed)f(memory)g(models)f(can)i(also)e(e)o(xpress)i(a)f(rich) g(set)f(of)h(probabilistic)d(dependencies,)k(making)300 1611 y(them)f(appropriate)g(for)f(modeling)g(comple)o(x)i(stochastic)f (processes.)16 b(Applied)9 b(to)h(factorial)f(HMMs,)300 1661 y(the)o(y)i(generalize)g(the)f(work)g(by)g(Ghahramani)h(&)g (Jordan)g(\(1997\))e(in)h(two)g(important)f(directions:)14 b(by)300 1711 y(introducing)9 b(coupled)h(dynamics,)i(and)g(by)e (considering)g(non-Gaussian)h(observ)o(ations.)17 b(The)o(y)12 b(also)300 1760 y(gi)o(v)o(e)j(rise)h(to)e(a)i(simple)f(iterati)o(v)o (e)g(procedure)h(for)e(making)h(inferences)h(about)f(the)g(hidden)g (states.)300 1810 y(W)m(e)10 b(describe)h(this)e(procedure)h(not)f (only)g(for)h(its)f(practical)h(v)o(alue,)h(b)o(ut)e(also)h(because)i (it)d(v)o(ery)i(cleanly)300 1860 y(illustrates)c(the)h(idea)g(of)g(e)o (xploiting)e(tractable)i(substructures)f(in)g(intractable)h (probabilistic)e(networks)300 1910 y(\(Saul)k(&)h(Jordan,)f(1997\).)333 1976 y(The)17 b(main)e(signi\256cance)i(of)e(this)g(work)f(lies)i(in)f (its)g(application)f(to)h(factorial)g(HMMs)h(and)g(the)300 2026 y(modeling)9 b(of)g(coupled)h(time)g(series.)15 b(In)10 b(principle,)f(though,)g(mix)o(ed)h(memory)g(Marko)o(v)g (models)g(can)300 2076 y(be)e(applied)g(where)o(v)o(er)h(lar)o(ge)f (state)h(spaces)g(arise)g(as)f(the)g(Cartesian)g(product)f(of)h(two)f (or)h(more)h(random)300 2126 y(v)o(ariables.)16 b(W)m(e)11 b(will)f(take)g(adv)o(antage)h(of)f(this)g(generality)g(to)g(present)g (mix)o(ed)h(memory)g(models)g(in)f(a)300 2175 y(number)g(of)h(dif)o (ferent)e(settings.)15 b(In)10 b(doing)f(this,)h(our)g(goal)g(is)g(to)g (b)o(uild)f(up\320in)g(a)i(gradual)f(way\320the)300 2225 y(some)o(what)h(in)n(v)o(olv)o(ed)e(notation)g(needed)i(to)e(describe)i (factorial)e(HMMs.)333 2292 y(The)f(or)o(ganization)e(of)h(this)f(note) g(is)h(therefore)g(as)h(follo)o(ws.)13 b(In)7 b(order)g(of)f (increasing)h(comple)o(xity)m(,)h(we)300 2342 y(consider:)15 b(\(1\))c(higher)o(-order)f(Marko)o(v)g(models,)i(where)f(lar)o(ge)g (state)g(spaces)i(arise)e(as)h(the)f(Cartesian)300 2391 y(product)g(of)i(se)o(v)o(eral)g(time)g(slices;)g(\(2\))f(factorial)g (Marko)o(v)g(models,)h(where)g(the)g(dynamics)f(are)i(\256rst)300 2441 y(order)d(b)o(ut)g(the)g(observ)o(ations)f(ha)o(v)o(e)j(a)f (componential)e(structure;)h(and)h(\(3\))e(factorial)h(HMMs,)h(where) 300 2491 y(the)h(Marko)o(v)f(dynamics)h(apply)f(to)g(hidden)g(states,)i (as)g(opposed)e(to)g(the)g(observ)o(ations)g(themselv)o(es.)p eop %%Page: 3 3 3 2 bop 300 125 a Fh(MIXED)11 b(MEMOR)m(Y)i(MARK)o(O)o(V)g(MODELS)857 b Fi(3)300 266 y Fm(W)m(e)8 b(conclude)f(that)g(mix)o(ed)h(memory)g (models)g(pro)o(vide)f(a)h(v)o(aluable)f(tool)f(for)h(understanding)f (comple)o(x)300 316 y(dynamical)k(systems.)300 428 y Fn(2.)42 b(Higher)11 b(order)g(Mark)o(ov)f(models)300 528 y Fm(Let)f Fl(i)378 534 y Fk(t)405 528 y Ff(2)i(f)p Fe(1)p Fl(;)c Fe(2)p Fl(;)g(:)g(:)g(:)s(;)g(n)p Ff(g)i Fm(denote)f(a)i(discrete)f(random)f(v)o(ariable)h(that)f(can)i(take)f (on)f Fl(n)h Fm(possible)f(v)o(alues.)300 578 y(A)i Fl(k)q Fm(th)g(order)f(Marko)o(v)h(model)g(is)g(speci\256ed)h(by)f(the)f (transition)g(matrix)g Fl(P)d Fe(\()p Fl(i)1415 584 y Fk(t)1430 578 y Ff(j)p Fl(i)1456 584 y Fk(t)p Fs(\000)p Fj(1)1513 578 y Fl(;)h(i)1546 584 y Fk(t)p Fs(\000)p Fj(2)1602 578 y Fl(;)g(:)g(:)g(:)e(;)i(i)1709 584 y Fk(t)p Fs(\000)p Fk(k)1768 578 y Fe(\))p Fm(.)300 627 y(T)m(o)g(a)o(v)o(oid)g (ha)o(ving)f(to)h(specify)g(the)g Fl(O)q Fe(\()p Fl(n)866 612 y Fk(k)q Fj(+1)928 627 y Fe(\))g Fm(elements)h(of)f(this)f(matrix,) i(we)g(consider)e(parameterizing)300 677 y(the)k(model)g(by)g(the)g (con)n(v)o(e)o(x)i(combination)d(\(Raftery)m(,)h(1985;)f(Ne)o(y)i(et)f (al.,)h(1994\):)400 789 y Fl(P)6 b Fe(\()p Fl(i)463 795 y Fk(t)477 789 y Ff(j)p Fl(i)503 795 y Fk(t)p Fs(\000)p Fj(1)560 789 y Fl(;)h(i)593 795 y Fk(t)p Fs(\000)p Fj(2)650 789 y Fl(;)g(:)g(:)g(:)e(;)i(i)757 795 y Fk(t)p Fs(\000)p Fk(k)815 789 y Fe(\))12 b(=)909 737 y Fk(k)888 750 y Fd(X)887 838 y Fk(\026)p Fj(=1)956 789 y Fl( )q Fe(\()p Fl(\026)p Fe(\))f Fl(a)1074 772 y Fk(\026)1096 789 y Fe(\()p Fl(i)1126 795 y Fk(t)1141 789 y Ff(j)p Fl(i)1167 795 y Fk(t)p Fs(\000)p Fk(\026)1228 789 y Fe(\))p Fl(;)490 b Fm(\(1\))300 905 y(where)12 b Fl( )q Fe(\()p Fl(\026)p Fe(\))i Ff(\025)f Fe(0)p Fm(,)599 874 y Fd(P)643 918 y Fk(\026)672 905 y Fl( )q Fe(\()p Fl(\026)p Fe(\))h(=)f(1)p Fm(,)f(and)f Fl(a)952 890 y Fk(\026)975 905 y Fe(\()p Fl(i)1005 890 y Fs(0)1017 905 y Ff(j)p Fl(i)p Fe(\))g Fm(are)h Fl(k)g Fm(elementary)g Fl(n)e Ff(\002)g Fl(n)h Fm(transition)e(matrices.)300 963 y(The)14 b(model)f(in)f(eq.)i(\(1\))e (is)h(speci\256ed)h(by)f Fl(O)q Fe(\()p Fl(k)q(n)1018 948 y Fj(2)1036 963 y Fe(\))g Fm(parameters,)j(as)d(opposed)g(to)f Fl(O)q Fe(\()p Fl(n)1590 948 y Fk(k)q Fj(+1)1653 963 y Fe(\))h Fm(for)g(the)300 1012 y(full)8 b(memory)h(model.)15 b(Note)9 b(ho)o(w)g Fl( )q Fe(\()p Fl(\026)p Fe(\))h Fm(is)f(used)g(to)f(weight)h(the)g(in\257uence)g(of)g(past)g(observ)o (ations)f(on)300 1062 y(the)j(distrib)o(ution)d(o)o(v)o(er)k Fl(i)662 1068 y Fk(t)677 1062 y Fm(.)18 b(This)12 b(type)f(of)g (weighted)f(sum)i(is)f(the)g(de\256ning)g(characteristic)g(of)g(mix)o (ed)300 1112 y(memory)g(models.)333 1162 y(The)f(mixture)e(model)g(in)g (eq.)i(\(1\))e(is)g(to)g(be)h(distinguished)e(from)h(models)h(that)f (approximate)g(higher)o(-)300 1212 y(order)i(Marko)o(v)g(models)h(by)f (\252)p Fl(n)p Fm(-gram)h(smoothing\272;)e(that)h(is,)h(by)f(employing) f(a)i(linear)f(combination)300 1261 y(of)18 b Fl(n)p Fm(th)f(order)h(transition)e(matrices)i(\(Chen)g(&)g(Goodman,)i (1996\).)38 b(Our)18 b(model)f(is)h(not)f(an)i Fl(n)p Fm(-)300 1311 y(gram)c(smoother;)i(rather)d(it)g(approximates)h(a)g (higher)o(-order)f(Marko)o(v)g(model)h(by)g(taking)e(a)j(linear)300 1361 y(combination)h(of)g(non-adjacent)h(bigram)f(models.)39 b(The)18 b(model)g(in)f(eq.)i(\(1\))e(also)h(dif)o(fers)g(from)300 1411 y(mixture-of-e)o(xperts)e(models)h(as)g(applied)f(to)h(continuous) e(time)i(series)g(\(Zee)o(vi)g(et)g(al,)i(1996\),)f(in)300 1461 y(which)12 b(the)h(predictions)e(of)i(dif)o(ferent)e Fl(n)p Fm(th)h(order)h(re)o(gressors)g(are)h(combined)f(by)f(the)h (weights)f(of)g(a)300 1511 y(softmax)e(gating)f(function.)333 1560 y(F)o(or)g(the)f(purpose)g(of)g(parameter)i(estimation,)e(it)f(is) i(con)n(v)o(enient)f(to)g(interpret)f(the)h(inde)o(x)h Fl(\026)f Fm(in)g(eq.)h(\(1\))300 1610 y(as)h(the)e(v)o(alue)h(of)g(a)g (latent)g(v)o(ariable.)14 b(W)m(e)9 b(denote)g(this)f(latent)g(v)o (ariable)h(\(at)g(each)h(time)f(step\))g(by)f Fl(x)1711 1616 y Fk(t)1734 1610 y Fm(and)300 1660 y(consider)i(the)g(joint)f (probability)e(distrib)o(ution:)400 1732 y Fl(P)f Fe(\()p Fl(i)463 1738 y Fk(t)477 1732 y Fl(;)h(x)520 1738 y Fk(t)545 1732 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(i)640 1738 y Fk(t)p Fs(\000)p Fj(1)697 1732 y Fl(;)7 b(:)g(:)g(:)e(;)i(i)804 1738 y Fk(t)p Fs(\000)p Fk(k)863 1732 y Fe(\))k(=)h Fl( )q Fe(\()p Fl(\026)p Fe(\))f Fl(a)1052 1715 y Fk(\026)1075 1732 y Fe(\()p Fl(i)1105 1738 y Fk(t)1120 1732 y Ff(j)p Fl(i)1146 1738 y Fk(t)p Fs(\000)p Fk(\026)1206 1732 y Fe(\))p Fl(:)512 b Fm(\(2\))300 1804 y(Note)11 b(that)f(mar)o (ginalizing)g(out)g Fl(x)794 1810 y Fk(t)819 1804 y Fm(\(i.e.,)i (summing)f(o)o(v)o(er)h Fl(\026)p Fm(\))e(reco)o(v)o(ers)j(the)e(pre)o (vious)e(model)i(for)g(the)300 1854 y(transition)g(matrix,)j(eq.)g (\(1\).)24 b(Thus)14 b(we)g(ha)o(v)o(e)g(e)o(xpressed)g(the)g(dynamics) f(as)h(a)g(mixture)f(model,)h(in)300 1904 y(which)c(the)g(parameters)i Fl( )q Fe(\()p Fl(\026)p Fe(\))g Fm(are)f(the)f(prior)g(probabilities,) e Fl(P)e Fe(\()p Fl(x)1278 1910 y Fk(t)1304 1904 y Fe(=)12 b Fl(\026)p Fe(\))p Fm(.)17 b(Like)o(wise,)10 b(we)h(can)h(vie)o(w)300 1954 y(the)e(parameters)i Fl(a)576 1939 y Fk(\026)598 1954 y Fe(\()p Fl(i)628 1939 y Fs(0)640 1954 y Ff(j)p Fl(i)p Fe(\))e Fm(as)h(the)f(conditional)e(probabilities,)h Fl(P)d Fe(\()p Fl(i)1287 1960 y Fk(t)1313 1954 y Fe(=)11 b Fl(i)1370 1939 y Fs(0)1382 1954 y Ff(j)p Fl(i)1408 1960 y Fk(t)p Fs(\000)p Fj(1)1465 1954 y Fl(;)c(:)g(:)g(:)e(;)i(i)1572 1960 y Fk(t)p Fs(\000)p Fk(k)1631 1954 y Fl(;)g(x)1674 1960 y Fk(t)1699 1954 y Fe(=)12 b Fl(\026)p Fe(\))p Fm(.)333 2004 y(Let)17 b Fl(I)23 b Fe(=)c Ff(f)p Fl(i)532 2010 y Fj(1)551 2004 y Fl(;)7 b(i)584 2010 y Fj(2)603 2004 y Fl(;)g(:)g(:)g(:)t(;)g(i)709 2010 y Fk(L)734 2004 y Ff(g)16 b Fm(denote)g(an)g(observ)o(ed)g(time)g(series)h(of)f(length)e Fl(L)p Fm(.)33 b(The)17 b(suf)o(\256cient)300 2053 y(statistics)10 b(for)h(a)g(full)f(memory)i(Marko)o(v)e(model)h(are)h(the)f(transition) e(frequencies.)18 b(T)m(o)11 b(\256t)g(the)g(mix)o(ed)300 2103 y(memory)e(Marko)o(v)f(model)g(we)i(a)o(v)o(ail)e(ourselv)o(es)h (of)f(the)g(EM)h(procedure)g(\(Dempster)g(et)f(al.,)i(1977\).)k(In)300 2153 y(general)9 b(terms)g(the)f(EM)h(algorithm)e(calculates)j Fg(e)o(xpected)h Fm(suf)o(\256cient)d(statistics)g(and)h(sets)g(them)f (equal)300 2203 y(to)k(the)h Fg(observed)i Fm(suf)o(\256cient)d (statistics.)22 b(The)14 b(procedure)f(iterates)g(and)f(is)h (guaranteed)g(to)f(increase)300 2253 y(the)e(likelihood)d(at)j(each)i (step.)j(F)o(or)10 b(the)g(model)g(in)f(eq.)i(\(2\),)f(the)g(EM)h (updates)f(are)h(\(Ne)o(y)f(et)g(al,)h(1994\):)442 2344 y Fl( )q Fe(\()p Fl(\026)p Fe(\))26 b Ff( )637 2284 y Fd(P)681 2327 y Fk(t)703 2315 y Fl(P)6 b Fe(\()p Fl(x)776 2321 y Fk(t)801 2315 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(I)s Fe(\))p 624 2334 309 2 v 624 2341 a Fd(P)668 2385 y Fk(t;\027)718 2372 y Fl(P)6 b Fe(\()p Fl(x)791 2378 y Fk(t)816 2372 y Fe(=)12 b Fl(\027)s Ff(j)p Fl(I)s Fe(\))938 2344 y Fl(;)796 b Fm(\(3\))400 2467 y Fl(a)422 2449 y Fk(\026)444 2467 y Fe(\()p Fl(i)474 2449 y Fs(0)486 2467 y Ff(j)p Fl(i)p Fe(\))25 b Ff( )624 2407 y Fd(P)668 2450 y Fk(t)690 2438 y Fl(P)6 b Fe(\()p Fl(x)763 2444 y Fk(t)788 2438 y Fe(=)12 b Fl(\026;)7 b(i)890 2444 y Fk(t)p Fs(\000)p Fk(\026)962 2438 y Fe(=)12 b Fl(i;)7 b(i)1053 2444 y Fk(t)1079 2438 y Fe(=)12 b Fl(i)1137 2423 y Fs(0)1149 2438 y Ff(j)p Fl(I)s Fe(\))p 624 2457 574 2 v 689 2464 a Fd(P)732 2508 y Fk(t)754 2495 y Fl(P)6 b Fe(\()p Fl(x)827 2501 y Fk(t)852 2495 y Fe(=)12 b Fl(\026;)7 b(i)954 2501 y Fk(t)p Fs(\000)p Fk(\026)1026 2495 y Fe(=)12 b Fl(i)p Ff(j)p Fl(I)s Fe(\))1203 2467 y Fl(:)531 b Fm(\(4\))p eop %%Page: 4 4 4 3 bop 300 125 a Fi(4)1137 b Fh(SA)o(UL)13 b(AND)f(JORD)o(AN)296 251 y Fp(T)m(able)c(1.)k Fu(Entropy)7 b(per)g(character)o(,)g(computed) g(from)g(v)o(arious)h(Markov)d(models.)356 319 y(order)p 510 331 2 40 v 203 w(memory)p 825 331 V 219 w(English)p 1161 331 V 234 w(Italian)p 1480 331 V 234 w(Finnish)p 296 345 1495 2 v 369 385 a(0th)p 510 397 2 40 v 241 w(none)p 825 397 V 255 w(0.900)p 1161 397 V 252 w(0.844)p 1480 397 V 250 w(0.840)371 425 y(1st)p 510 436 V 253 w(full)p 825 436 V 265 w(0.776)p 1161 436 V 252 w(0.696)p 1480 436 V 250 w(0.707)366 464 y(2nd)p 510 476 V 227 w(mixed)p 825 476 V 246 w(0.754)p 1161 476 V 252 w(0.678)p 1480 476 V 250 w(0.679)366 503 y(2nd)p 510 515 V 246 w(full)p 825 515 V 265 w(0.689)p 1161 515 V 252 w(0.622)p 1480 515 V 250 w(0.607)300 637 y Fm(In)k(the)g(case)i(where)f(multiple)e (time)i(series)g(are)g(a)o(v)o(ailable)g(as)g(training)e(data,)i(the)f (sums)h(o)o(v)o(er)g Fl(t)g Fm(should)300 687 y(be)15 b(interpreted)f(as)h(sums)g(o)o(v)o(er)g(series)h(as)f(well.)28 b(The)15 b(EM)g(updates)g(for)f(this)g(model)g(are)i(easy)f(to)300 736 y(understand;)g(at)g(each)h(iteration,)e(the)g(model)h(parameters)g (are)h(adjusted)e(so)g(that)g(the)g(statistics)g(of)300 786 y(the)d(joint)f(distrib)o(ution)e(match)k(the)f(statistics)f(of)h (the)h(posterior)e(distrib)o(utio)o(n.)16 b(The)c(e)o(xpectations)f(in) 300 836 y(eqs.)g(\(3\))f(and)g(\(4\))g(may)h(be)f(straightforwardly)e (computed)i(from)g(Bayes)h(rule:)400 941 y Fl(P)6 b Fe(\()p Fl(x)473 947 y Fk(t)498 941 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(I)s Fe(\))g(=)710 913 y Fl( )q Fe(\()p Fl(\026)p Fe(\))f Fl(a)828 898 y Fk(\026)850 913 y Fe(\()p Fl(i)880 919 y Fk(t)895 913 y Ff(j)p Fl(i)921 919 y Fk(t)p Fs(\000)p Fk(\026)982 913 y Fe(\))p 676 931 355 2 v 676 938 a Fd(P)720 982 y Fk(\027)748 969 y Fl( )q Fe(\()p Fl(\027)s Fe(\))f Fl(a)864 957 y Fk(\027)885 969 y Fe(\()p Fl(i)915 975 y Fk(t)930 969 y Ff(j)p Fl(i)956 975 y Fk(t)p Fs(\000)p Fk(\027)1015 969 y Fe(\))1036 941 y Fl(:)698 b Fm(\(5\))300 1046 y(Note)10 b(that)g(this)f(algorithm)g(requires)h(no)g (\256ne-tuning)e(of)i(step)h(sizes,)g(as)g(does)g(gradient)e(descent.) 333 1096 y(In)g(terms)g(of)g(representational)f(po)o(wer)n(,)i(the)f (model)g(of)f(eq.)i(\(1\))f(lies)f(some)o(where)i(in)f(between)g(a)h (\256rst)300 1146 y(order)h(Marko)o(v)g(model)h(and)g(a)g Fl(k)q Fm(th)f(order)g(Marko)o(v)g(model.)19 b(T)m(o)12 b(demonstrate)f(this)g(point,)g(we)h(\256tted)300 1196 y(v)o(arious)e(Marko)o(v)g(models)h(to)f(word)f(spellings)g(in)h (English,)g(Italian,)h(and)f(Finnish.)15 b(The)c(state)g(space)300 1246 y(for)c(these)h(models)g(was)f(the)h(alphabet)f(\(e.g.,)i Fc(`a')f Fm(to)f Fc(`z')g Fm(for)g(English\),)g(and)h(the)f(training)f (data)i(came)300 1295 y(from)f(v)o(ery)g(long)e(lists)h(of)h(words)f (with)g(four)g(or)g(more)h(letters.)14 b(The)8 b(matrices)f Fl(a)1429 1280 y Fk(\027)1450 1295 y Fe(\()p Fl(i)1480 1280 y Fs(0)1492 1295 y Ff(j)p Fl(i)p Fe(\))g Fm(were)g(initialized)300 1345 y(by)j(count-based)g(bigram)g(models)h(predicting)e(each)i(letter) f(by)g(the)h Fl(\026)p Fm(th)f(preceding)g(one.)16 b(\(This)10 b(type)300 1395 y(of)f(initialization,)f(in)h(which)g(the)h(component)f (sub-models)h(are)g(\256rst)g(trained)f(independently)f(of)h(one)300 1445 y(another)n(,)g(is)g(useful)f(to)g(a)o(v)o(oid)g(poor)g(local)g (maxima)h(in)f(the)h(learning)e(procedure.\))15 b(In)8 b(table)g(1,)i(we)f(gi)o(v)o(e)300 1495 y(the)k(results)h(measured)g (in)g(entropy)e(per)h(character)n(.)27 b(The)14 b(results)f(sho)o(w)h (that)f(the)g(mix)o(ed)h(memory)300 1544 y(model)f(does)h(noticeably)e (better)h(than)g(the)g(\256rst-order)f(model.)24 b(Of)13 b(course,)i(it)d(cannot)h(capture)h(all)300 1594 y(the)9 b(structure)g(of)h(the)f(full)f(second-order)i(model,)g(which)f(has)h (o)o(v)o(er)g(ten)g(times)f(as)i(man)o(y)f(parameters.)300 1644 y(The)g(mixture)e(model)h(should)f(accordingly)h(be)g(vie)o(wed)g (as)h(an)g(intermediate)f(step)g(between)h(\256rst)e(and)300 1694 y(higher)o(-order)h(models.)333 1744 y(W)m(e)i(en)n(vision)f(two)g (situations)f(in)h(which)g(the)h(model)g(of)f(eq.)i(\(1\))e(may)h(be)g (gainfully)e(applied.)16 b(The)300 1794 y(\256rst)d(is)h(when)f(the)h (dynamics)g(of)f(the)g(process)i(generating)e(the)g(data)h(are)g (faithfully)d(described)j(by)300 1843 y(a)h(mixture)e(model.)28 b(In)14 b(this)f(case,)k(one)d(would)f(e)o(xpect)i(the)f(mixture)g (model)g(to)g(perform)g(as)h(well)300 1893 y(as)g(the)f(\(full\))f (higher)o(-order)g(model)i(while)e(requiring)g(substantially)f(less)j (data)g(for)f(its)f(parameter)300 1943 y(estimation.)28 b(A)15 b(real-world)f(e)o(xample)i(might)e(be)h(the)g(modeling)f(of)h (web)g(sites)g(visited)f(during)f(a)300 1993 y(session)d(on)f(the)g(W)m (orld)g(W)n(ide)h(W)m(eb)n(.)15 b(The)10 b(modeling)f(of)g(these)h (sequences)h(has)f(applications)e(to)h(web)300 2043 y(page)16 b(prefetching)e(and)i(resource)g(management)g(on)f(the)g(Internet)g (\(Besta)o(vros)g(&)g(Cunha,)i(1995;)300 2092 y(Cunha)8 b(et)h(al.,)h(1995\).)j(T)m(ypically)m(,)c(the)f(choice)h(of)g(the)f (ne)o(xt)h(web)g(page)g(is)f(conditioned)f(on)h(a)h(pre)o(vious)300 2142 y(site,)h(b)o(ut)f(not)g(necessarily)h(the)g(last)g(one)g(that)f (has)h(been)g(visited.)k(\(Recall)c(ho)o(w)f(often)g(it)g(is)h (necessary)300 2192 y(to)h(retrace)i(one')n(s)e(steps,)h(using)f(the)g Fb(ba)o(ck)i Fm(option.\))k(The)12 b(model)g(in)f(eq.)h(\(1\))f (captures)h(this)f(type)g(of)300 2242 y(conditioning)g(e)o(xplicitly)m (.)24 b(Here,)16 b(the)d(states)h(of)f(the)h(Marko)o(v)f(model)h(would) e(correspond)h(to)g(web)300 2292 y(pages;)g(the)f(matrices)h Fl(a)657 2277 y Fk(\027)678 2292 y Fe(\()p Fl(i)708 2277 y Fs(0)720 2292 y Ff(j)p Fl(i)p Fe(\))p Fm(,)g(to)e(links)g(from)h(web) h(page)g Fl(i)f Fm(to)g(web)g(page)h Fl(j)r Fm(;)g(and)f(the)g(inde)o (x)g Fl(\026)p Fm(,)h(to)300 2342 y(the)d(number)g(of)g(backward)h(or)f (retraced)h(steps)f(taken)g(before)g(acti)o(v)o(ating)f(a)i(ne)o(w)g (link.)333 2391 y(The)16 b(second)g(situation)d(in)h(which)h(this)f (model)h(may)h(be)g(appropriate)e(is)h(when)g(the)g(amount)g(of)300 2441 y(training)h(data)i(is)g(e)o(xtremely)g(sparse)h(relati)o(v)o(e)e (to)h(the)f(size)i(of)e(the)h(state)g(space.)39 b(In)18 b(this)f(case,)300 2491 y(the)d(parameterization)g(in)f(eq.)i(\(1\),)g (though)d(a)j(poor)e(approximation)f(to)i(the)g(true)f(model,)j(may)e (be)p eop %%Page: 5 5 5 4 bop 300 125 a Fh(MIXED)11 b(MEMOR)m(Y)i(MARK)o(O)o(V)g(MODELS)857 b Fi(5)300 266 y Fm(desirable)12 b(to)g(a)o(v)o(oid)g(o)o(v)o (er\256tting.)20 b(Ne)o(y)13 b(et)f(al)g(\(1994\))g(ha)o(v)o(e)h(in)n (v)o(estigated)e(models)i(of)f(this)f(form)h(for)300 316 y(lar)o(ge)k(v)o(ocab)o(ulary)g(language)g(modeling.)31 b(The)16 b(ability)e(to)i(discern)f(likely)g(sequences)i(of)e(words)300 366 y(from)10 b(unlikely)e(sequences)k(is)e(an)h(important)e(component) h(of)g(automated)g(speech)i(recognition.)h(F)o(or)300 415 y(lar)o(ge)i(v)o(ocab)o(ularies\320in)f(the)h(tens)f(of)h (thousands)f(of)g(words\320there)g(is)g(ne)o(v)o(er)i(suf)o(\256cient)e (data)h(to)300 465 y(estimate)g(\(rob)o(ustly\))d(the)i(statistics)f (of)h(second)h(or)f(higher)f(order)h(Marko)o(v)g(models.)27 b(In)14 b(practice,)300 515 y(therefore,)i(these)g(models)f(are)h (\252smoothed\272)f(or)g(interpolated)e(\(Chen)i(&)g(Goodman,)i(1996\)) d(with)300 565 y(lo)o(wer)d(order)h(models.)19 b(The)12 b(interpolation)d(with)i(lo)o(wer)g(order)h(models)f(is)h(forced)g(on)f (practitioners)300 615 y(by)g(the)g(enormous)h(size)g(of)f(the)g(state) h(space)h(\(e.g.,)g Fe(10)1105 600 y Fj(4)1134 615 y Fm(words\))e(and)g(the)h(small)f(\(in)g(relati)o(v)o(e)g(terms\))300 664 y(amount)e(of)g(training)f(data)h(\(e.g.,)i Fe(10)831 649 y Fj(8)859 664 y Fm(words\).)i(Recently)m(,)d(one)g(of)f(us)g (applied)g(a)h(more)g(sophisticated)300 714 y(v)o(ersion)g(of)f(eq.)i (\(1\))e(to)g(lar)o(ge)h(v)o(ocab)o(ulary)g(language)g(modeling)f (\(Saul)g(&)i(Pereira,)g(1997\).)j(In)9 b(only)g(a)300 764 y(fe)o(w)f(CPU)f(hours,)h(it)f(was)h(possible)e(to)h(\256t)h(o)o(v) o(er)g(ten)f(million)f(parameters)j(to)d(the)i(statistics)f(of)g(an)h (eighty)300 814 y(million)i(word)g(corpus.)19 b(Moreo)o(v)o(er)n(,)13 b(the)e(smoothed)h(combination)e(of)h(mix)o(ed)h(memory)g(and)f(higher) 300 864 y(order)f(Marko)o(v)g(models)g(led)g(to)g(signi\256cantly)e(lo) o(wer)i(entropies)g(on)g(out-of-sample)f(predictions.)300 979 y Fn(3.)42 b(F)o(actorial)9 b(Mark)o(ov)i(models)300 1079 y Fm(In)17 b(the)g(last)g(section,)i(we)f(sa)o(w)h(ho)o(w)d(lar)o (ge)i(state)g(spaces)g(arose)g(as)g(the)g(result)e(of)h(higher)g(order) 300 1129 y(dynamics.)36 b(In)16 b(this)g(section,)j(we)f(consider)e (another)h(source)g(of)g(lar)o(ge)g(state)h(spaces\320namely)m(,)300 1179 y(factorial)6 b(representations.)14 b(Man)o(y)8 b(time)f(series)h(ha)o(v)o(e)h(a)f(natural)e(componential)h(structure.) 13 b(Consider)300 1228 y(for)h(e)o(xample)h(the)f(four)g(v)o (oices\320soprano)f(\(S\),)i(alto)e(\(A\),)i(tenor)f(\(T\),)g(and)h (bass)f(\(B\)\320of)f(a)i(Bach)300 1278 y(fugue)d(\(Dirst)f(&)i(W)m (eigend,)g(1993\).)21 b(W)m(e)13 b(can)g(model)f(each)i(v)o(oice)f(by)f (a)h(separate)g(Marko)o(v)f(model,)300 1328 y(b)o(ut)g(this)g(will)g (not)g(capture)h(the)g(correlations)f(due)h(to)f(harmon)o(y)m(.)24 b(The)13 b(most)g(straightforward)e(way)300 1378 y(to)f(model)h(the)f (coupling)f(between)i(v)o(oices)g(is)g(to)f(write)g(do)o(wn)g(a)h (Marko)o(v)f(model)h(whose)f(dynamical)300 1428 y(state)k(is)f(the)h (Cartesian)g(product)e(of)i(the)f(four)g(v)o(oices.)26 b(But)13 b(the)h(combinatorial)e(structure)h(of)g(this)300 1477 y(state)e(space)h(leads)g(to)e(an)i(e)o(xplosion)d(in)i(the)g (number)g(of)f(free)i(parameters;)g(thus)e(it)g(is)h(imperati)o(v)o(e)g (to)300 1527 y(pro)o(vide)f(a)g(compact)h(representation)f(of)g(the)g (transition)e(matrix.)333 1577 y(Mix)o(ed)k(memory)h(models)f(are)h (especially)g(geared)g(to)e(these)i(sorts)f(of)f(situations.)20 b(Let)13 b Fl(I)1657 1583 y Fk(t)1684 1577 y Fm(denote)300 1627 y(the)e Fl(t)p Fm(th)f(element)h(of)f(a)i(v)o(ector)f(time)f (series,)i(and)f Fl(i)1036 1607 y Fk(\026)1036 1637 y(t)1069 1627 y Fm(the)g Fl(\026)p Fm(th)f(component)h(of)f Fl(I)1458 1633 y Fk(t)1473 1627 y Fm(.)17 b(If)10 b(each)i(v)o(ector)f(has)300 1677 y Fl(k)h Fm(components,)g(and)f(each)i(component)e(can)h(take)f (on)g Fl(n)g Fm(v)o(alues,)h(then)f(the)g(o)o(v)o(erall)h(state)f (space)i(has)300 1726 y(size)c Fl(n)398 1711 y Fk(k)419 1726 y Fm(.)15 b(T)m(o)8 b(model)h(the)g(coupling)e(between)i(these)g (components)g(in)f(a)i(compact)f(way)m(,)h(we)f(make)h(two)300 1776 y(simplifying)c(assumptions:)13 b(\(i\))7 b(that)h(the)g (components)g Fl(i)1131 1761 y Fk(\027)1131 1787 y(t)1161 1776 y Fm(at)g(time)g Fl(t)h Fm(are)g(conditionally)c(independent)300 1826 y(gi)o(v)o(en)10 b(the)g(v)o(ector)h Fl(I)594 1832 y Fk(t)p Fs(\000)p Fj(1)651 1826 y Fm(,)g(or)400 1954 y Fl(P)6 b Fe(\()p Fl(I)467 1960 y Fk(t)481 1954 y Ff(j)p Fl(I)511 1960 y Fk(t)p Fs(\000)p Fj(1)568 1954 y Fe(\))12 b(=)661 1902 y Fk(k)643 1915 y Fd(Y)639 2003 y Fk(\027)r Fj(=1)707 1954 y Fl(P)6 b Fe(\()p Fl(i)770 1937 y Fk(\027)770 1965 y(t)790 1954 y Ff(j)p Fl(I)820 1960 y Fk(t)p Fs(\000)p Fj(1)877 1954 y Fe(\);)841 b Fm(\(6\))300 2080 y(and)12 b(\(ii\))f(that)g(the)h(conditional)d(probabilities)h Fl(P)c Fe(\()p Fl(i)1053 2065 y Fk(\027)1053 2091 y(t)1073 2080 y Ff(j)p Fl(I)1103 2086 y Fk(t)p Fs(\000)p Fj(1)1160 2080 y Fe(\))12 b Fm(can)h(be)f(e)o(xpressed)h(as)g(a)f(weighted)f(sum) 300 2130 y(of)f(\252cross-transition\272)f(matrices:)400 2249 y Fl(P)d Fe(\()p Fl(i)463 2232 y Fk(\027)463 2260 y(t)483 2249 y Ff(j)p Fl(I)513 2255 y Fk(t)p Fs(\000)p Fj(1)570 2249 y Fe(\))12 b(=)663 2197 y Fk(k)643 2210 y Fd(X)642 2298 y Fk(\026)p Fj(=1)711 2249 y Fl( )739 2232 y Fk(\027)760 2249 y Fe(\()p Fl(\026)p Fe(\))f Fl(a)850 2232 y Fk(\027)r(\026)890 2249 y Fe(\()p Fl(i)920 2232 y Fk(\027)920 2260 y(t)941 2249 y Ff(j)p Fl(i)967 2229 y Fk(\026)967 2260 y(t)p Fs(\000)p Fj(1)1024 2249 y Fe(\))p Fl(:)694 b Fm(\(7\))300 2384 y(Here)14 b(again,)h(the)f(parameters)g Fl(a)791 2369 y Fk(\027)r(\026)832 2384 y Fe(\()p Fl(i)862 2369 y Fs(0)874 2384 y Ff(j)p Fl(i)p Fe(\))g Fm(are)g Fl(k)1017 2369 y Fj(2)1050 2384 y Fm(elementary)g Fl(n)d Ff(\002)g Fl(n)j Fm(transition)e(matrices,)j(while)300 2433 y(the)e(parameters)i Fl( )588 2418 y Fk(\027)609 2433 y Fe(\()p Fl(\026)p Fe(\))f Fm(are)g(positi)o(v)o(e)f(numbers)g (that)g(satisfy)1242 2402 y Fd(P)1286 2446 y Fk(\026)1315 2433 y Fl( )1343 2418 y Fk(\027)1364 2433 y Fe(\()p Fl(\026)p Fe(\))j(=)h(1)p Fm(.)24 b(The)14 b(number)g(of)300 2491 y(free)d(parameters)g(in)e(eq.)i(\(7\))f(is)f(therefore)h Fl(O)q Fe(\()p Fl(k)997 2476 y Fj(2)1016 2491 y Fl(n)1041 2476 y Fj(2)1059 2491 y Fe(\))p Fm(,)h(as)g(opposed)e(to)h Fl(O)q Fe(\()p Fl(n)1406 2476 y Fj(2)p Fk(k)1443 2491 y Fe(\))g Fm(for)f(the)h(full)f(memory)p eop %%Page: 6 6 6 5 bop 300 125 a Fi(6)1137 b Fh(SA)o(UL)13 b(AND)f(JORD)o(AN)326 251 y Fp(T)m(able)c(2.)k Fu(Portion)c(of)g(the)g(four)o(-component)e (time)i(series)g(generated)e(by)i(Bach')n(s)g(last)g(fugue.)p 326 306 1434 2 v 326 346 a(soprano)48 b(61)h(61)g(61)g(66)g(66)g(66)g (66)g(66)g(66)g(66)g(66)g(66)h(66)f(66)g(66)g(66)354 385 y(alto)77 b(54)49 b(54)g(54)g(54)g(54)g(54)g(54)g(54)g(54)g(54)g (54)g(54)h(56)f(56)g(56)g(56)345 425 y(tenor)67 b(49)49 b(49)g(49)g(49)g(49)g(49)g(49)g(51)g(51)g(52)g(52)g(51)h(51)f(51)g(51)g (51)350 464 y(bass)73 b(46)49 b(44)g(44)g(46)g(46)g(46)g(46)g(46)g(46)g (46)g(46)g(48)h(48)f(48)g(48)g(48)p 326 490 V 300 621 a Fm(model.)15 b(\(By)10 b(allo)o(wing)f(non-square)h(transition)e (matrices,)k(this)d(model)h(can)h(also)g(be)f(generalized)h(to)300 671 y(the)f(case)i(where)f(the)f(dif)o(ferent)f(components)h(take)g(on) g(dif)o(ferent)f(numbers)i(of)f(v)o(alues.\))333 721 y(The)i(parameters)g Fl( )630 706 y Fk(\027)651 721 y Fe(\()p Fl(\026)p Fe(\))g Fm(measure)g(the)f(amount)g(of)f(correlation) g(between)i(the)f(dif)o(ferent)f(compo-)300 771 y(nents)h(of)g(the)g (time)g(series.)19 b(In)11 b(particular)n(,)h(if)e(there)i(is)f(no)g (correlation,)g(then)f Fl( )1476 755 y Fk(\027)1498 771 y Fe(\()p Fl(\026)p Fe(\))h Fm(is)g(the)h(identity)300 820 y(matrix,)g(and)f(the)h Fl(\027)s Fm(th)e(component)h(is)h (independent)e(of)h(all)h(the)f(rest.)19 b(On)12 b(the)f(other)g(hand,) h(for)f(non-)300 870 y(zero)h Fl( )411 855 y Fk(\027)432 870 y Fe(\()p Fl(\026)p Fe(\))p Fm(,)h(all)f(the)f(components)h(at)g (one)f(time)h(step)g(in\257uence)g(the)f Fl(\027)s Fm(th)f(component)i (at)g(the)f(ne)o(xt.)300 920 y(The)g(matrices)g Fl(a)548 905 y Fk(\027)r(\026)589 920 y Fe(\()p Fl(i)619 905 y Fs(0)631 920 y Ff(j)p Fl(i)p Fe(\))f Fm(pro)o(vide)g(a)h(compact)g(way) f(to)f(parameterize)j(these)f(in\257uences.)333 970 y(As)16 b(in)e(the)i(pre)o(vious)e(section,)j(it)d(is)h(con)n(v)o(enient)h(to)e (introduce)h(latent)f(v)o(ariables)i Fl(x)1604 955 y Fk(\027)1604 980 y(t)1639 970 y Fm(and)g(vie)o(w)300 1020 y(eq.)11 b(\(7\))f(as)h(a)f(mixture)g(model.)15 b(Thus)c(we)f(may)h(write:)400 1093 y Fl(P)6 b Fe(\()p Fl(i)463 1076 y Fk(\027)463 1103 y(t)483 1093 y Fl(;)h(x)526 1076 y Fk(\027)526 1103 y(t)558 1093 y Fe(=)k Fl(\026)p Ff(j)p Fl(I)656 1099 y Fk(t)p Fs(\000)p Fj(1)713 1093 y Fe(\))25 b(=)g Fl( )839 1076 y Fk(\027)861 1093 y Fe(\()p Fl(\026)p Fe(\))10 b Fl(a)950 1076 y Fk(\027)r(\026)991 1093 y Fe(\()p Fl(i)1021 1076 y Fk(\027)1021 1103 y(t)1042 1093 y Ff(j)p Fl(i)1068 1073 y Fk(\026)1068 1104 y(t)p Fs(\000)p Fj(1)1125 1093 y Fe(\))p Fl(;)593 b Fm(\(8\))477 1167 y Fl(P)6 b Fe(\()p Fl(I)544 1173 y Fk(t)559 1167 y Fl(;)h(X)612 1173 y Fk(t)626 1167 y Ff(j)p Fl(I)656 1173 y Fk(t)p Fs(\000)p Fj(1)713 1167 y Fe(\))25 b(=)811 1128 y Fd(Y)829 1215 y Fk(\027)871 1167 y Fl(P)6 b Fe(\()p Fl(i)934 1150 y Fk(\027)934 1178 y(t)955 1167 y Fl(;)h(x)998 1150 y Fk(\027)998 1178 y(t)1018 1167 y Ff(j)p Fl(I)1048 1173 y Fk(t)p Fs(\000)p Fj(1)1105 1167 y Fe(\))p Fl(:)613 b Fm(\(9\))300 1275 y(Here,)12 b(the)e(role)h(of)f Fl(x)608 1260 y Fk(\027)608 1285 y(t)639 1275 y Fm(is)g(to)g(select)i(which)e (component)g(of)g Fl(I)1196 1281 y Fk(t)p Fs(\000)p Fj(1)1264 1275 y Fm(determines)h(the)f(transition)f(matrix)300 1325 y(for)j Fl(i)375 1310 y Fk(\027)375 1335 y(t)396 1325 y Fm(.)20 b(As)13 b(before,)g(we)f(can)h(deri)o(v)o(e)f(an)h(EM)f (algorithm)f(to)g(\256t)h(the)g(parameters)h(of)f(this)f(model.)21 b(In)300 1375 y(this)9 b(case,)k(the)d(EM)g(updates)g(are:)440 1471 y Fl( )468 1454 y Fk(\027)489 1471 y Fe(\()p Fl(\026)p Fe(\))25 b Ff( )669 1411 y Fd(P)713 1455 y Fk(t)735 1442 y Fl(P)6 b Fe(\()p Fl(x)808 1427 y Fk(\027)808 1452 y(t)839 1442 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(I)s Fe(\))p 643 1461 341 2 v 643 1468 a Fd(P)687 1512 y Fk(t;\026)730 1503 y Fa(0)749 1499 y Fl(P)6 b Fe(\()p Fl(x)822 1485 y Fk(\027)822 1510 y(t)854 1499 y Fe(=)12 b Fl(\026)923 1487 y Fs(0)934 1499 y Ff(j)p Fl(I)s Fe(\))1725 1471 y Fm(\(10\))400 1597 y Fl(a)422 1580 y Fk(\027)r(\026)462 1597 y Fe(\()p Fl(i)492 1580 y Fs(0)504 1597 y Ff(j)p Fl(i)p Fe(\))25 b Ff( )643 1535 y Fd(P)687 1579 y Fk(t)708 1567 y Fl(P)6 b Fe(\()p Fl(x)781 1551 y Fk(\027)781 1577 y(t)813 1567 y Fe(=)11 b Fl(\026;)c(i)914 1547 y Fk(\026)914 1578 y(t)p Fs(\000)p Fj(1)983 1567 y Fe(=)12 b Fl(i;)7 b(i)1074 1551 y Fk(\027)1074 1577 y(t)1106 1567 y Fe(=)12 b Fl(i)1164 1551 y Fs(0)1176 1567 y Ff(j)p Fl(I)s Fe(\))p 643 1588 583 2 v 717 1595 a Fd(P)761 1638 y Fk(t)783 1626 y Fl(P)6 b Fe(\()p Fl(x)856 1611 y Fk(\027)856 1636 y(t)887 1626 y Fe(=)12 b Fl(\026;)7 b(i)989 1614 y Fk(m)1020 1626 y Fl(u)1044 1632 y Fk(t)p Fs(\000)p Fj(1)1101 1626 y Ff(j)p Fl(I)s Fe(\))1725 1597 y Fm(\(11\))300 1694 y(where)14 b Fl(I)k Fm(stands)13 b(for)g(the)h(observ)o(ed)g(time)g (series.)26 b(Naturally)m(,)14 b(the)f(structure)h(of)f(these)h (updates)g(is)300 1744 y(quite)9 b(similar)h(to)g(the)g(model)g(of)g (the)g(pre)o(vious)f(section.)333 1794 y(T)m(o)j(test)f(this)g (algorithm,)g(we)i(learned)f(a)g(model)f(of)h(the)g(four)o(-component)e (time)i(series)g(generated)300 1843 y(by)h(Bach')n(s)g(last)g(fugue.)25 b(This)13 b(fugue)g(has)g(a)h(rich)f(history)f(\(Dirst)g(&)i(W)m (eigend,)g(1993\).)24 b(The)14 b(time)300 1893 y(series)9 b(\(3284)e(beats)i(long\))e(was)i(made)g(public)f(follo)o(wing)e(the)i (Santa)h(Fe)g(competition)e(on)h(time)g(series)300 1943 y(prediction.)24 b(T)m(able)14 b(2)f(sho)o(ws)h(a)g(portion)d(of)j (this)e(time)i(series:)22 b(here,)15 b(each)g(element)f(represents)g(a) 300 1993 y(sixteenth)8 b(note,)h(while)f(the)h(numerical)g(v)o(alue)f (codes)i(the)f(pitch.)k(T)m(o)c(help)g(a)o(v)o(oid)f(poor)g(local)h (maxima)300 2043 y(in)h(the)g(learning)f(procedure,)i(the)f(transition) f(matrices)i Fl(a)1139 2028 y Fk(\027)r(\026)1180 2043 y Fe(\()p Fl(i)1210 2028 y Fs(0)1222 2043 y Ff(j)p Fl(i)p Fe(\))f Fm(were)h(initialized)e(by)h(count-based)300 2092 y(bigram)i(models)h(predicting)d(the)j Fl(\027)s Fm(th)e(v)o(oice)h(at)h(time)f Fl(t)h Fm(from)f(the)g Fl(\026)p Fm(th)g(v)o(oice)g(at)h(the)f(pre)o(vious)g(time)300 2142 y(step.)333 2192 y(By)g(e)o(xamining)g(the)f(parameters)j(of)d (the)h(\256tted)g(model,)g(we)h(can)g(see)g(to)e(what)h(e)o(xtent)g (each)h(v)o(oice)300 2242 y(enables)d(one)g(to)f(make)h(predictions)f (about)g(the)g(others.)15 b(In)9 b(general,)i(we)f(observ)o(ed)g(that)f (the)g(mixture)300 2292 y(coef)o(\256cients)i Fl( )529 2277 y Fk(\027)550 2292 y Fe(\()p Fl(\026)p Fe(\))g Fm(were)g(v)o(ery)f (close)h(to)f(zero)g(or)g(one.)16 b(The)11 b(reason)f(for)g(this)f(is)i (that)e(the)h(v)o(oices)h(do)300 2342 y(not)f(typically)f(change)i (pitch)f(with)f(e)o(v)o(ery)j(sixteenth)d(note.)16 b(Hence,)d(for)d (each)h(v)o(oice)g(the)g(note)f(at)h(the)300 2391 y(pre)o(vious)e(beat) i(is)f(a)h(v)o(ery)f(good)g(predictor)f(of)h(the)g(note)g(at)g(the)g (current)g(one.)333 2441 y(When)15 b(the)g(v)o(oices)g(do)g(make)g(a)g (transition)e(\(i.e.,)k(mo)o(v)o(e)f(up)e(or)h(do)o(wn)f(in)g(pitch\),) i(ho)o(we)o(v)o(er)n(,)h(the)300 2491 y(coupling)f(between)i(v)o(oices) g(becomes)h(e)o(vident.)36 b(T)m(o)17 b(see)i(this,)g(we)f(can)g(look)e (at)i(the)f Fg(posterior)p eop %%Page: 7 7 7 6 bop 300 125 a Fh(MIXED)11 b(MEMOR)m(Y)i(MARK)o(O)o(V)g(MODELS)857 b Fi(7)402 224 y 20366047 3789043 5854576 14537768 35719495 38350766 startTexFig 402 224 a %%BeginDocument: figs/xmm.ps % MathWorks dictionary /MathWorks 150 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rc {rectclip} bdef /rf {rectfill} bdef /rm /rmoveto ldef /rl /rlineto ldef /s /show ldef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS { /FontSize xstore %save size off stack findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont }bdef /reencode { exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop } bdef /isroman { findfont /CharStrings get /Agrave known } bdef /FMSR { 3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS } bdef /csm { 1 dpi2point div -1 dpi2point div scale neg translate landscapeMode eq {90 rotate} if } bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L { lineto stroke } bdef /MP { 3 1 roll moveto 1 sub {rlineto} repeat } bdef /AP { {rlineto} repeat } bdef /PP { closepath fill } bdef /DP { closepath stroke } bdef /MR { 4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath } bdef /FR { MR stroke } bdef /PR { MR fill } bdef /L1i { { currentfile picstr readhexstring pop } image } bdef /tMatrix matrix def /MakeOval { newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix } bdef /FO { MakeOval stroke } bdef /PO { MakeOval fill } bdef /PD { 2 copy moveto lineto stroke } bdef currentdict end def MathWorks begin 0 cap end MathWorks begin bpage bplot /dpi2point 12 def portraitMode 0216 7344 csm 861 341 5443 4342 MR c np 76 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef /Helvetica /ISOLatin1Encoding 144 FMSR 1 j c1 0 0 6913 5187 PR 6 w DO 4 w SO 6 w c0 898 4615 mt 6255 4615 L 898 389 mt 6255 389 L 6255 4615 mt 6255 389 L 898 4615 mt 898 389 L 6255 389 mt 6255 389 L 898 389 mt 898 389 L 898 4615 mt 6255 4615 L 898 4615 mt 898 389 L 898 4615 mt 898 4615 L 898 4615 mt 898 4561 L 898 389 mt 898 443 L 1568 4615 mt 1568 4561 L 1568 389 mt 1568 443 L 2237 4615 mt 2237 4561 L 2237 389 mt 2237 443 L 2907 4615 mt 2907 4561 L 2907 389 mt 2907 443 L 3577 4615 mt 3577 4561 L 3577 389 mt 3577 443 L 4246 4615 mt 4246 4561 L 4246 389 mt 4246 443 L 4916 4615 mt 4916 4561 L 4916 389 mt 4916 443 L 5585 4615 mt 5585 4561 L 5585 389 mt 5585 443 L 6255 4615 mt 6255 4561 L 6255 389 mt 6255 443 L 898 4615 mt 952 4615 L 6255 4615 mt 6201 4615 L 898 4192 mt 952 4192 L 6255 4192 mt 6201 4192 L 898 3770 mt 952 3770 L 6255 3770 mt 6201 3770 L 898 3347 mt 952 3347 L 6255 3347 mt 6201 3347 L 898 2925 mt 952 2925 L 6255 2925 mt 6201 2925 L 898 2502 mt 952 2502 L 6255 2502 mt 6201 2502 L 898 2079 mt 952 2079 L 6255 2079 mt 6201 2079 L 898 1657 mt 952 1657 L 6255 1657 mt 6201 1657 L 898 1234 mt 952 1234 L 6255 1234 mt 6201 1234 L 898 812 mt 952 812 L 6255 812 mt 6201 812 L 898 389 mt 952 389 L 6255 389 mt 6201 389 L 898 389 mt 6255 389 L 898 4615 mt 6255 4615 L 898 4615 mt 898 389 L 6255 4615 mt 6255 389 L 6255 4615 mt 6255 4615 L 898 4615 mt 898 4615 L gs 898 389 5358 4227 MR c np 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 1395 1 -1395 2 0 1 0 1 1775 2 -1775 1 0 1 0 2 0 1 0 1 42 2 -42 1 0 1 0 2 42 1 0 1 423 2 -465 1 0 1 0 2 423 1 -423 1 507 2 -507 1 0 1 42 2 423 1 -465 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 254 1 -254 1 85 2 -85 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 85 2 -85 1 0 1 0 2 127 1 -127 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 5891 4615 100 MP stroke 2 0 1 3085 1 -3085 2 0 1 0 1 0 2 0 1 2071 1 -2071 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -42 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 1944 1 -1944 2 0 1 0 5758 4615 100 MP stroke 1 0 2 592 1 -550 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 3719 1 -3761 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 -42 1 465 1 -465 2 0 1 0 1 0 2 0 1 127 1 -127 2 85 1 -85 1 0 2 42 1 719 2 -761 1 169 1 -169 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 0 2 1733 1 -1775 1 0 5626 4615 100 MP stroke 2 0 1 592 1 -550 2 0 1 0 1 888 2 -930 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 380 1 -380 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 -42 1 0 2 42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 5493 4573 100 MP stroke 1 0 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1226 2 -1226 1 0 1 0 2 0 1 0 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 423 1 -465 2 0 1 0 1 0 2 0 1 0 1 0 2 127 1 -127 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 0 2 0 1 3930 1 -3972 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 5360 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 380 2 -380 1 0 1 0 2 0 1 0 1 0 2 0 1 85 1 -85 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 42 2 -42 1 0 1 0 2 592 1 -550 1 0 2 0 1 -42 1 0 2 0 1 0 1 845 2 -845 1 0 1 0 2 0 1 0 1 0 2 0 1 2578 1 -2578 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 5228 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 1056 1 -1056 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 0 1 0 2 -42 1 0 1 0 2 0 1 42 1 0 2 0 1 0 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 5095 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 1056 1 -1056 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 -42 1 42 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 4963 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1395 2 -1395 1 0 1 0 2 380 1 -380 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 676 1 -676 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 -42 2 0 1 42 1 0 2 -42 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 254 2 -296 1 42 1 0 2 0 1 0 1 0 2 0 1 -42 2 0 1 0 1 0 2 42 1 0 1 -42 2 0 1 85 1 -85 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 4830 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1352 1 -1352 2 0 1 0 1 0 2 0 1 0 1 0 2 85 1 -85 1 42 2 -42 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 254 2 -254 1 0 1 0 2 169 1 -169 1 0 2 0 1 592 1 -592 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 4697 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 211 1 -211 1 0 2 0 1 803 1 -803 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 127 1 -127 2 1310 1 -1310 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 42 2 127 1 -169 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 4565 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 4432 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 0 2 0 1 0 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 0 2 -42 1 0 1 42 2 0 1 -42 1 0 2 0 1 0 1 42 2 0 1 -42 1 0 2 42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 4300 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 2789 1 -2831 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 338 2 -338 1 338 1 -338 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 169 2 -169 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 296 1 -296 2 761 1 -761 1 0 2 0 1 0 1 0 2 0 1 0 4167 4615 100 MP stroke 1 85 2 -85 1 0 1 0 2 42 1 0 1 1860 2 -1902 1 211 1 -211 2 0 1 0 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 634 1 -634 2 0 1 0 1 127 2 -127 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 423 1 -423 1 127 2 -127 1 2409 1 -2409 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1310 1 -1310 1 0 4035 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 718 2 -718 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 85 1 -85 1 0 2 0 1 127 1 -127 2 0 1 0 1 592 2 -592 1 0 1 42 2 43 1 -85 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 1860 1 -1902 1 211 2 -211 1 0 1 0 2 127 1 -127 1 0 2 0 1 0 1 0 2 169 1 -169 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 3902 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 -42 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 42 1 0 2 -42 1 0 1 0 2 0 1 42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -42 2 0 1 0 1 0 2 1395 1 -1395 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 42 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 507 1 -507 2 127 1 -127 2 127 1 -127 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 1099 1 -1099 1 0 2 0 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 0 3769 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 338 2 -338 1 0 1 0 2 85 1 -85 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 85 1 -85 1 0 2 0 1 0 1 0 2 127 1 -127 2 127 1 -127 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 -42 1 127 1 -127 2 127 1 -127 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 338 1 -338 1 85 2 -85 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 338 2 -338 1 0 1 0 3637 4615 100 MP stroke 2 85 1 -85 1 0 2 0 1 127 1 -127 2 127 1 -127 1 0 2 0 1 0 1 0 2 296 1 -296 1 127 2 -127 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 549 2 -549 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 127 1 -127 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 296 1 -296 1 85 2 -85 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 296 2 -296 1 465 1 -465 2 42 1 -42 1 127 2 -127 1 296 1 -296 2 380 1 -380 1 0 2 0 1 0 1 0 2 423 1 -423 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 85 1 -85 2 0 1 0 1 0 2 0 1 0 1 0 2 0 3504 4615 100 MP stroke 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 465 2 -465 1 85 1 -85 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 3372 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 718 2 -718 1 0 2 0 1 0 1 42 2 0 1 0 1 930 2 -972 1 0 1 0 2 0 1 0 1 0 2 0 1 803 1 -803 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 338 1 -338 2 0 1 0 1 0 2 0 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 3239 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 1141 1 -1141 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 930 1 -930 2 0 1 0 1 42 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 3106 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 0 1 423 2 -465 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 169 1 -169 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2974 4615 100 MP stroke 2 0 1 42 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 296 1 -296 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 2841 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 127 1 -127 2 0 1 0 1 169 2 -169 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 85 2 -85 1 169 1 -169 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 507 1 -507 1 0 2 0 1 423 1 -423 2 0 1 0 1 0 2 0 1 0 1 0 2 169 1 -169 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 85 2 -85 1 0 1 0 2 0 1 0 1 0 2 0 1 549 1 -549 2 0 1 0 1 42 2709 4573 100 MP stroke 2 0 1 0 1 0 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 169 1 -169 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2576 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 845 1 -845 2 0 1 0 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 0 1 1564 2 -1606 1 0 1 0 2 0 1 0 2 0 2443 4615 100 MP stroke 1 0 1 0 2 42 1 0 1 0 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 2 0 1 0 1 1648 2 -1690 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 0 2 507 1 -549 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 42 1 0 2 0 1 0 1 0 2 0 1 0 1 4184 2 -4226 1 0 1 0 2 0 1 0 2311 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 211 1 -211 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 2 0 1 0 1 0 2 -42 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1268 2 -1268 1 0 1 0 2 42 1 0 1 0 2 0 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 2178 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1775 1 -1775 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 85 2 -85 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 127 1 -127 1 0 2 0 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2046 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 42 1 -42 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1913 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 0 1 0 2 1353 1 -1395 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 1437 1 -1437 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 634 1 -634 1 0 2 0 1 549 1 -549 2 0 1 0 1 127 2 -127 1 0 1 0 2 127 1 -127 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 1781 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 296 2 -296 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 127 1 -127 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1648 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 42 1 -42 1 0 2 0 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 85 2 -85 1 0 1 0 2 0 1 0 1 0 2 0 1515 4615 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 169 2 -169 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 338 2 -338 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 127 2 -127 1 0 1 0 2 85 1 -85 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 1383 4615 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 338 1 -338 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1395 1 -1395 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 507 1 -507 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 127 1 -127 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1250 4615 100 MP stroke 1 0 1 0 2 127 1 -127 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 42 1118 4573 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -42 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 985 4615 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 85 1 3930 1 -3930 2 -43 899 4573 65 MP stroke gr end eplot epage end showpage %%EndDocument endTexFig 300 579 a Fp(F)o(igur)o(e)9 b(1.)17 b Fu(Plot)11 b(of)f(soprano-tenor) d(correlations)i(versus)g(time,)i(as)e(measured)g(by)g(the)h(posterior) f(probabilities)g(of)h(a)g(mixed)300 618 y(memory)d(Markov)f(model.)300 757 y Fm(probabilities)g(of)g(the)g(latent)g(v)o(ariables,)f Fl(x)901 737 y Fk(\026)901 767 y(t)923 757 y Fm(,)i(which)f(re)o(v)o (eal)g(the)g(e)o(xtent)g(to)g(which)g(the)g(v)o(oices)g(interact)g(at) 300 806 y(speci\256c)g(moments)g(in)g(time.)16 b(Figure)6 b(1)g(sho)o(ws)g(a)g(plot)g(of)g(the)g(posterior)g(probabilit)o(ies,)f Fl(P)h Fe(\()p Fl(x)1626 791 y Fk(S)1626 817 y(t)1661 806 y Fe(=)12 b Fl(T)6 b Ff(j)p Fl(I)s Fe(\))p Fm(,)300 856 y(v)o(ersus)11 b(time)f(calculated)h(from)f(the)h(\256tted)f (model.)15 b(W)n(ithin)10 b(the)g(frame)o(work)g(of)g(the)h(mixture)e (model,)300 906 y(these)14 b(probabilities)d(measure)k(the)e(relati)o (v)o(e)g(de)o(gree)h(to)f(which)g(the)g(soprano')n(s)g(note)g(at)g (time)g Fl(t)h Fm(can)300 956 y(be)f(predicted)f(from)h(the)g(tenor')n (s)f(note)g(at)h(the)f(pre)o(vious)g(time)h(step.)23 b(The)13 b(moments)g(at)g(which)f(this)300 1006 y(probability)7 b(acquires)i(a)h(non-zero)f(v)o(alue)g(indicate)g(times)g(when)g(the)g (tenor)g(and)g(soprano)g(are)h(tightly)300 1056 y(coupled.)17 b(Not)10 b(surprisingly)m(,)g(these)h(pulses)g(of)g(coupling)e(\(when)i (vie)o(wed)g(as)h(a)f(time)g(series\))h(ha)o(v)o(e)g(a)300 1105 y(discernible)e(local)g(rhythm)f(and)h(re)o(gularity)f(of)h(their) g(o)o(wn.)300 1232 y Fn(4.)42 b(F)o(actorial)9 b(HMMs)300 1338 y Fm(Building)g(on)i(the)g(results)g(of)g(the)h(last)f(section,)h (we)g(no)o(w)e(consider)i(the)f(generalization)g(to)f(factorial)300 1388 y(hidden)f(Marko)o(v)g(models)g(\(HMMs\).)15 b(These)10 b(are)h(HMMs)e(whose)h(states)g(and)f(observ)o(ations)g(ha)o(v)o(e)h (an)300 1438 y(internal,)h(combinatorial)f(structure)h(\(Ghahramani)g (&)h(Jordan,)g(1997;)e(Binder)h(et)g(al.,)h(1997\).)18 b(Ho)o(w)300 1488 y(might)10 b(such)h(structure)f(arise?)18 b(Suppose)10 b(we)i(are)f(trying)e(to)i(model)f(the)h(processes)h(that) e(gi)o(v)o(e)h(rise)g(to)300 1538 y(a)h(speech)g(signal.)17 b(A)12 b(number)f(of)g(unobserv)o(ed)g(v)o(ariables)g(interact)f(to)h (generate)h(the)f(signal)f(that)h(we)300 1587 y(ultimately)g(observ)o (e.)23 b(In)12 b(an)h(articulatory)e(model)i(of)f(speech)h(production,) f(these)h(v)o(ariables)g(might)300 1637 y(encode)g(the)f(positions)f (of)h(v)o(arious)f(or)o(gans,)i(such)g(as)g(the)f(lip,)g(tongue,)h(and) f(ja)o(w)m(.)23 b(In)12 b(a)h(recognizer)n(,)300 1687 y(these)d(v)o(ariables)g(might)e(encode)j(the)e(current)g(phonemic)h (conte)o(xt,)g(the)f(speaker)h(accent)h(and)f(gender)n(,)300 1737 y(and)h(the)g(presence)i(of)e(background)f(noise.)18 b(In)11 b(either)g(case,)j(the)d(hidden)f(state)i(for)f(these)g(models) h(is)300 1787 y(naturally)d(decomposed)i(as)g(the)f(Cartesian)g (product)f(of)h(se)o(v)o(eral)h(random)g(v)o(ariables.)333 1840 y(Another)k(moti)o(v)o(ation)f(for)i(factorial)f(representations)g (is)h(that)f(in)h(man)o(y)h(applications,)f(the)g(ob-)300 1890 y(serv)o(ations)h(ha)o(v)o(e)i(an)f(a)g(priori)e(componential)g (structure.)37 b(This)18 b(is)f(the)h(case,)j(for)c(e)o(xample,)k(in) 300 1940 y(audio)o(visual)14 b(speech)h(recognition)e(\(Bre)o(gler)i(&) g(Omohundro,)g(1995\),)g(where)g(information)e(from)300 1989 y(dif)o(ferent)8 b(modalities)f(is)i(being)f(combined)g(and)h (presented)f(to)g(the)h(recognizer)n(.)15 b(It)8 b(is)g(also)h(the)f (case)i(in)300 2039 y(frequenc)o(y)i(subband-based)e(speech)j (recognition)c(\(Bourlard)g(&)j(Dupont,)e(1996\),)h(where)h(dif)o (ferent)300 2089 y(recognizers)i(are)h(trained)e(on)g(sub-bands)h(of)f (the)h(speech)h(signal)e(and)g(then)h(combined)f(to)h(make)g(a)300 2139 y(global)d(decision.)22 b(Simple)12 b(ways)h(to)f(inte)o(grate)g (these)h(dif)o(ferent)f(components)g(are:)20 b(\(a\))13 b(collapsing)300 2189 y(the)g(data)g(into)f(a)h(single)g(time)g(series) g(or)g(\(b\))g(re)o(weighting)e(and)i(combining)f(the)h(likelihood)d (scores)300 2238 y(of)g(independent)f(HMMs.)16 b(One)11 b(might)e(hope)h(for)g(a)h(more)g(sophisticated)e(inte)o(gration,)g(ho) o(we)o(v)o(er)n(,)j(by)300 2288 y(b)o(uilding)5 b(a)j(joint)d(model)i (that)g(looks)f(for)h(correlations)f(on)h(the)g(actual)g(time)g(scale)h (of)f(the)g(observ)o(ations.)333 2342 y(Whate)o(v)o(er)12 b(the)f(manner)g(in)f(which)h(the)o(y)f(arise,)i(factorial)e(HMMs)h (pose)g(two)f(concrete)i(problems.)300 2391 y(The)j(\256rst)g(is)g (representation.)28 b(In)14 b(most)h(applications,)g(there)g(is)f(not)g (suf)o(\256cient)h(data)g(to)f(estimate)300 2441 y(the)f(elements)h(of) f(the)h(full)e(transition)f(and)i(emission)h(matrices)g(formed)f(by)g (taking)f(the)i(Cartesian)300 2491 y(product)f(of)i(the)f(indi)o (vidual)e(factors.)28 b(Ho)o(w)14 b(should)g(one)g(parameterize)i (these)f(matrices)h(without)p eop %%Page: 8 8 8 7 bop 300 125 a Fi(8)1137 b Fh(SA)o(UL)13 b(AND)f(JORD)o(AN)300 266 y Fm(making)g(restricti)o(v)o(e)g(or)g(inele)o(gant)g(assumptions?) 21 b(Ideally)m(,)12 b(the)h(representation)e(should)g(not)h(make)300 316 y(unjusti\256ed)j(assumptions)g(of)i(conditional)d(independence,)k (nor)e(should)f(it)h(force)h(us)f(to)g(gi)o(v)o(e)g(up)300 366 y(desirable)9 b(properties)f(of)g(the)h(EM)g(algorithm,)f(such)h (as)g(monotone)f(con)n(v)o(er)o(gence)j(in)d(log-likelihoo)o(d.)333 415 y(The)i(second)g(problem)g(in)f(factorial)f(HMMs)i(is)f(one)h(of)f (computational)g(comple)o(xity)m(.)14 b(The)c(Baum-)300 465 y(W)m(elch)15 b(algorithm)e(for)i(parameter)h(estimation)e(scales)i (as)f Fl(O)q Fe(\()p Fl(N)1279 450 y Fj(2)1298 465 y Fe(\))p Fm(,)h(where)g Fl(N)k Fm(is)14 b(the)h(number)g(of)300 515 y(hidden)e(states.)28 b(If)13 b(the)h(hidden)g(state)g(is)g(a)h (Cartesian)f(product)f(of)h Fl(k)h Fm(random)f(v)o(ariables,)h(each)h (of)300 565 y(de)o(gree)10 b Fl(n)p Fm(,)g(then)f(the)g(ef)o(fecti)o(v) o(e)g(number)g(of)g(hidden)f(states)i(is)f Fl(N)16 b Fe(=)c Fl(n)1315 550 y Fk(k)1335 565 y Fm(.)j(Ev)o(en)10 b(for)f(small)g Fl(k)q Fm(,)h(this)e(may)300 615 y(be)j(prohibiti)o(v)o (ely)d(lar)o(ge)k(to)e(calculate)i(the)f(statistics)f(in)g(the)h (E-step)g(of)g(the)g(EM)g(algorithm.)16 b(Hence,)300 664 y(one)10 b(is)g(naturally)f(led)h(to)g(consider)g(approximations)f (to)g(these)i(statistics.)333 714 y(Let)16 b(us)g(no)o(w)f(return)g(to) g(our)g(de)o(v)o(elopment)h(of)f(factorial)g(HMMs)g(with)g(these)h (issues)g(in)f(mind.)300 764 y(W)m(e)d(will)f(see)i(that)e(mixture)g (models)h(pro)o(vide)f(a)i(good)e(compromise)h(to)f(the)h(problem)f(of) h(represen-)300 814 y(tation,)g(and)h(that)f(ef)o(\256cient)h (deterministic)f(approximations)f(e)o(xist)h(for)g(the)h(problem)f(of)g (parameter)300 864 y(estimation.)333 914 y(F)o(or)f(concreteness,)i (suppose)e(that)g(we)g(ha)o(v)o(e)h(trained)f Fl(k)h Fm(simple)f(HMMs)g(on)g(separate)h(time)f(series)300 963 y(of)e(length)g Fl(L)p Fm(.)15 b(No)o(w)10 b(we)g(wish)f(to)g (combine)g(these)h(HMMs)g(into)e(a)j(single)d(model)i(in)f(order)g(to)g (capture)300 1013 y(\(what)15 b(may)g(be\))h(useful)e(correlations)h (between)g(the)g(dif)o(ferent)f(time)h(series.)31 b(If)15 b(each)h(indi)o(vidual)300 1063 y(HMM)11 b(had)f Fl(n)h Fm(hidden)f(states)h(and)g Fl(m)g Fm(types)g(of)f(observ)o(ations,)g (then)h(the)f(hidden)g(state)h(space)h(of)f(the)300 1113 y(combined)h(model)g(has)g(size)h Fl(n)761 1098 y Fk(k)781 1113 y Fm(;)g(like)o(wise,)f(the)g(observ)o(ation)e(space)k(of)d(the)h (combined)g(model)g(has)300 1163 y(size)f Fl(m)411 1148 y Fk(k)432 1163 y Fm(.)k(At)10 b(each)h(time)g(step,)f(we)h(denote)f (these)h(spaces)h(by)d(the)i(Cartesian)f(products:)404 1237 y Fl(I)422 1243 y Fk(t)462 1237 y Fe(=)25 b Fl(i)533 1220 y Fj(1)533 1247 y Fk(t)562 1237 y Ff(\012)9 b Fl(i)617 1220 y Fj(2)617 1247 y Fk(t)645 1237 y Ff(\012)h(\001)d(\001)g(\001)g (\012)j Fl(i)800 1220 y Fk(k)800 1247 y(t)933 1237 y Fm(\(hidden\),)640 b(\(12\))400 1299 y Fl(J)423 1305 y Fk(t)462 1299 y Fe(=)25 b Fl(j)538 1282 y Fj(1)536 1310 y Fk(t)567 1299 y Ff(\012)9 b Fl(j)627 1282 y Fj(2)625 1310 y Fk(t)656 1299 y Ff(\012)g(\001)e(\001)g(\001)h(\012)h Fl(j)815 1282 y Fk(k)813 1310 y(t)929 1299 y Fm(\(observ)o(ed\).)609 b(\(13\))300 1374 y(In)13 b(an)h(HMM,)g(it)f(is)g(the)h(hidden)e (states)i(\(as)g(opposed)f(to)g(the)h(observ)o(ations\))e(that)h(ha)o (v)o(e)i(a)f(Marko)o(v)300 1424 y(dynamics.)h(Accordingly)m(,)7 b(in)h(this)f(setting,)h(we)g(use)h(eq.)f(\(6\2617\))f(to)h(model)f (the)h(hidden)f(state)i(transition)300 1474 y(matrix.)15 b(By)10 b(analogy)f(to)h(eqs.)h(\(6\2617\),)f(we)h(parameterize)g(the)f (emission)g(probabilities)e(by:)400 1561 y Fl(P)e Fe(\()p Fl(J)472 1567 y Fk(t)486 1561 y Ff(j)p Fl(I)516 1567 y Fk(t)530 1561 y Fe(\))12 b(=)602 1522 y Fd(Y)619 1609 y Fk(\027)662 1522 y Fd(X)682 1609 y Fk(\026)729 1561 y Fl(\036)754 1544 y Fk(\027)774 1561 y Fe(\()p Fl(\026)p Fe(\))p Fl(b)849 1544 y Fk(\027)r(\026)890 1561 y Fe(\()p Fl(j)925 1544 y Fk(\027)923 1572 y(t)946 1561 y Ff(j)p Fl(i)972 1541 y Fk(\026)972 1572 y(t)994 1561 y Fe(\))p Fl(;)703 b Fm(\(14\))300 1688 y(where)7 b Fl(b)426 1673 y Fk(\027)r(\026)467 1688 y Fe(\()p Fl(j)r Ff(j)p Fl(i)p Fe(\))h Fm(are)f Fl(k)632 1673 y Fj(2)658 1688 y Fm(elementary)g Fl(n)r Ff(\002)r Fl(m)g Fm(emission)g(matrices.)15 b(Note)7 b(that)f(this)g(model)h(can)g(capture)300 1738 y(correlations)i (between)h(the)g(hidden)f(states)h(of)f(the)h Fl(\026)p Fm(th)f(Marko)o(v)g(chain)h(and)g(the)g(observ)o(ations)e(in)i(the)300 1787 y Fl(\027)s Fm(th)f(time)h(series.)333 1837 y(F)o(or)18 b(the)g(purposes)g(of)g(parameter)h(estimation,)h(it)d(is)h(again)g (con)n(v)o(enient)g(to)f(introduce)g(latent)300 1887 y(v)o(ariables)11 b(that)g(encode)h(the)f(mixture)g(components)g(in)g (eq.)h(\(14\).)18 b(By)10 b(analogy)h(to)g(eqs.)h(\(8\))f(and)h(\(9\),) 300 1937 y(we)f(ha)o(v)o(e:)400 2011 y Fl(P)6 b Fe(\()p Fl(j)468 1994 y Fk(\027)466 2022 y(t)488 2011 y Fl(;)h(y)528 1994 y Fk(\027)527 2022 y(t)561 2011 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(I)660 2017 y Fk(t)674 2011 y Fe(\))25 b(=)g Fl(\036)797 1994 y Fk(\027)818 2011 y Fe(\()p Fl(\026)p Fe(\))p Fl(b)893 1994 y Fk(\026\027)934 2011 y Fe(\()p Fl(i)964 1991 y Fk(\026)964 2022 y(t)986 2011 y Fl(;)7 b(j)1024 1994 y Fk(\027)1022 2022 y(t)1045 2011 y Fe(\))p Fl(;)652 b Fm(\(15\))486 2082 y Fl(P)6 b Fe(\()p Fl(J)558 2088 y Fk(t)572 2082 y Fl(;)h(Y)615 2088 y Fk(t)630 2082 y Ff(j)p Fl(I)660 2088 y Fk(t)674 2082 y Fe(\))25 b(=)772 2042 y Fd(Y)789 2130 y Fk(\027)832 2082 y Fl(P)6 b Fe(\()p Fl(j)900 2065 y Fk(\027)898 2092 y(t)921 2082 y Fl(;)h(y)961 2065 y Fk(\027)960 2092 y(t)982 2082 y Ff(j)p Fl(I)1012 2088 y Fk(t)1026 2082 y Fe(\))p Fl(:)671 b Fm(\(16\))300 2191 y(Ha)o(ving)13 b(encoded)h(the)f(mixture)g(components)g(as)h (hidden)f(v)o(ariables,)h(we)g(can)h(no)o(w)e(apply)f(an)i(EM)300 2240 y(algorithm)9 b(to)g(estimate)i(the)f(model)g(parameters.)17 b(In)10 b(this)f(case,)j(the)f(updates)f(ha)o(v)o(e)h(the)f(form:)440 2338 y Fl( )468 2321 y Fk(\027)489 2338 y Fe(\()p Fl(\026)p Fe(\))25 b Ff( )669 2278 y Fd(P)713 2322 y Fk(t)735 2310 y Fl(P)6 b Fe(\()p Fl(x)808 2294 y Fk(\027)808 2320 y(t)839 2310 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(J)t Fe(\))p 643 2329 347 2 v 643 2336 a Fd(P)687 2379 y Fk(t;\026)730 2371 y Fa(0)749 2367 y Fl(P)6 b Fe(\()p Fl(x)822 2352 y Fk(\027)822 2377 y(t)854 2367 y Fe(=)12 b Fl(\026)923 2355 y Fs(0)934 2367 y Ff(j)p Fl(J)t Fe(\))994 2338 y Fl(;)719 b Fm(\(17\))400 2465 y Fl(a)422 2447 y Fk(\027)r(\026)462 2465 y Fe(\()p Fl(i)492 2447 y Fs(0)504 2465 y Ff(j)p Fl(i)p Fe(\))25 b Ff( )643 2403 y Fd(P)687 2446 y Fk(t)708 2434 y Fl(P)6 b Fe(\()p Fl(x)781 2419 y Fk(\027)781 2444 y(t)813 2434 y Fe(=)11 b Fl(\026;)c(i)914 2414 y Fk(\026)914 2445 y(t)p Fs(\000)p Fj(1)983 2434 y Fe(=)12 b Fl(i;)7 b(i)1074 2419 y Fk(\027)1074 2444 y(t)1106 2434 y Fe(=)12 b Fl(i)1164 2419 y Fs(0)1176 2434 y Ff(j)p Fl(J)t Fe(\))p 643 2455 588 2 v 710 2462 a Fd(P)754 2505 y Fk(t)775 2493 y Fl(P)6 b Fe(\()p Fl(x)848 2479 y Fk(\027)848 2503 y(t)880 2493 y Fe(=)12 b Fl(\026;)7 b(i)982 2473 y Fk(\026)982 2504 y(t)p Fs(\000)p Fj(1)1050 2493 y Fe(=)12 b Fl(i)p Ff(j)p Fl(J)t Fe(\))1235 2465 y Fl(;)478 b Fm(\(18\))p eop %%Page: 9 9 9 8 bop 300 125 a Fh(MIXED)11 b(MEMOR)m(Y)i(MARK)o(O)o(V)g(MODELS)857 b Fi(9)444 284 y Fl(\036)469 267 y Fk(\027)489 284 y Fe(\()p Fl(\026)p Fe(\))25 b Ff( )669 224 y Fd(P)713 268 y Fk(t)735 256 y Fl(P)6 b Fe(\()p Fl(y)805 241 y Fk(\027)804 266 y(t)837 256 y Fe(=)12 b Fl(\026)p Ff(j)p Fl(J)t Fe(\))p 643 275 345 2 v 643 282 a Fd(P)687 325 y Fk(t;\026)730 317 y Fa(0)749 313 y Fl(P)6 b Fe(\()p Fl(y)819 298 y Fk(\027)818 323 y(t)852 313 y Fe(=)12 b Fl(\026)921 301 y Fs(0)932 313 y Ff(j)p Fl(J)t Fe(\))992 284 y Fl(;)721 b Fm(\(19\))410 408 y Fl(b)428 391 y Fk(\027)r(\026)469 408 y Fe(\()p Fl(j)r Ff(j)p Fl(i)p Fe(\))25 b Ff( )643 349 y Fd(P)687 392 y Fk(t)708 380 y Fl(P)6 b Fe(\()p Fl(y)778 365 y Fk(\027)777 390 y(t)811 380 y Fe(=)12 b Fl(\026;)7 b(i)913 360 y Fk(\026)913 390 y(t)946 380 y Fe(=)12 b Fl(i;)7 b(j)1042 365 y Fk(\027)1040 390 y(t)1074 380 y Fe(=)12 b Fl(j)r Ff(j)p Fl(J)t Fe(\))p 643 399 550 2 v 709 406 a Fd(P)753 449 y Fk(t)775 437 y Fl(P)6 b Fe(\()p Fl(y)845 423 y Fk(\027)844 447 y(t)877 437 y Fe(=)12 b Fl(\026;)7 b(i)979 417 y Fk(\026)979 447 y(t)1013 437 y Fe(=)12 b Fl(i)p Ff(j)p Fl(J)t Fe(\))1725 408 y Fm(\(20\))300 503 y(where)i Fl(J)k Fm(denotes)13 b(the)g(observ)o(ed)h(time)f(series.)26 b(A)13 b(V)n(iterbi)f (approximation)g(is)h(obtained)g(by)g(con-)300 553 y(ditioning)g(not)j (only)f(on)h Fl(J)t Fm(,)i(b)o(ut)d(also)i(on)f(the)g(most)g(probable)f (sequence)j(of)e(hidden)f(states,)j Fl(I)1764 538 y Fs(\003)1784 553 y Fm(,)300 603 y(where)400 679 y Fl(I)421 662 y Fs(\003)452 679 y Fe(=)12 b(arg)7 b(max)582 706 y Fk(I)645 640 y Fd(Y)665 727 y Fk(t)705 679 y Fl(P)f Fe(\()p Fl(I)772 685 y Fk(t)786 679 y Ff(j)p Fl(I)816 685 y Fk(t)p Fs(\000)p Fj(1)873 679 y Fe(\))p Fl(P)g Fe(\()p Fl(J)961 685 y Fk(t)976 679 y Ff(j)p Fl(I)1006 685 y Fk(t)1020 679 y Fe(\))p Fl(:)677 b Fm(\(21\))300 797 y(Note)11 b(that)g(computing)g (the)g(posterior)f(probabilities)g(in)h(these)h(updates)f(requires)g Fl(O)q Fe(\()p Fl(Ln)1623 782 y Fj(2)p Fk(k)1661 797 y Fe(\))g Fm(opera-)300 847 y(tions;)d(the)i(same)h(is)f(true)f(for)h (computing)e(the)i(V)n(iterbi)e(path.)15 b(T)m(o)10 b(a)o(v)o(oid)f (this)g(computational)g(b)o(urden,)300 897 y(we)f(ha)o(v)o(e)g(used)f (an)h(approximation)d(for)i(estimating)f(the)h(statistics)f(in)h (factorial)f(HMMs,)i(\256rst)f(outlined)300 947 y(in)h(Saul)h(&)g (Jordan)g(\(1996\).)k(The)d(basic)f(idea)g(behind)f(our)g(approach)h (is)g(simple:)k(the)c(structure)f(of)h(the)300 997 y(factorial)j(HMM,)g (though)g(intractable)f(as)j(a)f(whole,)g(gi)o(v)o(es)g(rise)f(to)g(ef) o(\256cient)h(approximations)e(that)300 1046 y(e)o(xploit)h(the)h (tractability)e(of)i(its)g(underlying)e(components.)23 b(In)13 b(this)g(note,)g(we)h(discuss)f(ho)o(w)g(these)300 1096 y(approximations)f(can)h(be)h(used)f(to)g(estimate)g(the)g(V)n (iterbi)f(path.)23 b(In)13 b(general,)h(these)g(ideas)f(may)h(be)300 1146 y(e)o(xtended)f(to)f(approximate)g(the)g(full)g(statistics)f(of)h (the)h(posterior)e(distrib)o(ution,)f(as)j(for)f(e)o(xample)i(in)300 1196 y(Ghahramani)d(&)f(Jordan)g(\(1997\).)333 1246 y(In)k(the)h (factorial)e(HMM,)i(dynamic)f(programming)g(procedures)h(to)e(compute)i (the)f(V)n(iterbi)f(path)300 1295 y(algorithm)j(require)h Fl(O)q Fe(\()p Fl(Ln)716 1280 y Fj(2)p Fk(k)753 1295 y Fe(\))h Fm(steps.)36 b(As)18 b(a)g(practical)f(alternati)o(v)o(e,)i (we)f(consider)f(an)h(iterati)o(v)o(e)300 1345 y(procedure)13 b(that)e(returns)h(a)h(\(possibly)e(sub-optimal\))g(path)h(in)g (polynomial)f(time.)22 b(Our)12 b(iteration)f(is)300 1395 y(based)j(on)f(a)i(subroutine)d(that)h(\256nds)g(the)g(optimal)g (path)g(of)h(hidden)e(states)i(through)e(the)h Fl(\026)p Fm(th)g(chain)300 1445 y Fg(given)g(\256xed)h(values)g(for)f(the)g (hidden)g(states)g(of)g(the)g(others)p Fm(.)24 b(Note)13 b(that)g(when)h(we)f(instantiate)g(the)300 1495 y(hidden)g(v)o (ariables)g(in)g(all)h(b)o(ut)e(one)i(of)f(the)h(chains,)h(the)e(ef)o (fecti)o(v)o(e)i(size)f(of)f(the)h(hidden)e(state)i(space)300 1544 y(collapses)c(from)f Fl(n)577 1529 y Fk(k)607 1544 y Fm(to)g Fl(n)p Fm(,)h(and)g(we)g(can)g(perform)g(the)f(optimization)f (with)g(respect)j(to)e(the)g(remaining)300 1594 y(hidden)g(states)i(in) e Fl(O)q Fe(\()p Fl(Ln)670 1579 y Fj(2)689 1594 y Fe(\))i Fm(steps.)k(A)10 b(factor)g(of)g Fl(k)1039 1579 y Fj(2)1068 1594 y Fm(is)g(picked)f(up)h(when)g(con)n(v)o(erting)g(the)g(right)f (hand)300 1644 y(side)j(of)f(eq.)i(\(21\))e(into)g(a)h(form)g(for)f (which)h(the)g(standard)f(V)n(iterbi)f(algorithm)h(can)h(be)h(applied;) e(thus)300 1694 y(this)e(elementary)i Fg(c)o(hainwise)f(V)m(iterbi)g Fm(operation)f(requires)h Fl(O)q Fe(\()p Fl(Lk)1275 1679 y Fj(2)1294 1694 y Fl(n)1319 1679 y Fj(2)1337 1694 y Fe(\))h Fm(steps.)333 1744 y(The)f(algorithm)e(for)g(approximately)g (computing)g(the)h(full)f(V)n(iterbi)f(path)i(of)g(the)g(factorial)f (HMM)h(is)300 1794 y(obtained)g(by)g(piecing)g(these)h(subroutines)e (together)h(in)g(the)h(ob)o(vious)e(way)m(.)16 b(First,)9 b(an)h(initial)e(guess)i(is)300 1843 y(made)g(for)e(the)g(V)n(iterbi)f (path)h(of)g(each)i(component)e(HMM.)h(\(T)m(ypically)m(,)g(this)e(is)i (done)f(by)g(ignoring)f(the)300 1893 y(intercomponent)i(correlations)h (and)h(computing)f(a)h(separate)h(V)n(iterbi)d(path)h(for)g(each)i (chain.\))17 b(Then,)300 1943 y(the)9 b(chainwise)g(V)n(iterbi)f (algorithm)f(is)i(applied,)g(in)g(turn,)g(to)f(each)i(of)f(the)g (component)g(HMMs.)15 b(After)300 1993 y(the)e(V)n(iterbi)e(algorithm)h (has)h(been)h(applied)e Fl(k)j Fm(times,)f(or)f(once)g(to)g(each)h (chain,)g(the)f(c)o(ycle)h(repeats;)300 2043 y(each)d(iteration)e(of)h (this)f(process)i(therefore)g(in)n(v)o(olv)o(es)e Fl(O)q Fe(\()p Fl(Lk)1193 2028 y Fj(3)1212 2043 y Fl(n)1237 2028 y Fj(2)1256 2043 y Fe(\))h Fm(steps.)333 2092 y(Note)h(that)f (each)h(iteration)e(results)i(in)f(a)h(sequence)h(of)e(hidden)g(states) h(that)f(is)g(more)h(probable)f(than)300 2142 y(the)f(preceding)g(one;) h(hence,)h(this)d(process)i(is)f(guaranteed)h(to)f(con)n(v)o(er)o(ge)h (to)f(a)h(\256nal)f(\(though)f(possibly)300 2192 y(suboptimal\))13 b(path.)28 b(In)15 b(practice,)i(we)e(ha)o(v)o(e)h(found)d(that)h(this) g(process)i(typically)d(con)n(v)o(er)o(ges)j(to)e(a)300 2242 y(stable)c(path)g(in)g(three)g(or)g(four)g(iterations.)333 2292 y(The)i(chainwise)g(V)n(iterbi)e(algorithm)g(is)h(not)g (guaranteed)h(to)f(\256nd)g(the)g(truly)f(optimal)h(sequence)i(of)300 2342 y(hidden)d(states)i(for)f(the)g(factorial)f(HMM.)h(The)h(success)h (of)e(the)g(algorithm)f(depends)h(on)g(the)g(quality)300 2391 y(of)d(the)h(initial)d(guess)j(and,)g(as)g(always,)g(the)g(good)e (judgment)h(of)g(the)g(modeler)n(.)15 b(The)9 b(approximation)e(is)300 2441 y(premised)i(on)g(the)g(assumption)f(that)h(the)g(model)g (describes)h(a)f(set)h(of)f(weakly)g(coupled)f(time)h(series\320)300 2491 y(in)14 b(particular)n(,)h(that)f(the)g(auto-correlations)f (within)g(each)i(time)g(series)g(are)g(as)g(strong)e(or)h(stronger)p eop %%Page: 10 10 10 9 bop 300 125 a Fi(10)1114 b Fh(SA)o(UL)13 b(AND)f(JORD)o(AN)402 224 y 20366047 3789043 5854576 14537768 35719495 38350766 startTexFig 402 224 a %%BeginDocument: figs/xhmm.ps % MathWorks dictionary /MathWorks 150 dict begin % definition operators /bdef {bind def} bind def /ldef {load def} bind def /xdef {exch def} bdef /xstore {exch store} bdef % operator abbreviations /c /clip ldef /cc /concat ldef /cp /closepath ldef /gr /grestore ldef /gs /gsave ldef /mt /moveto ldef /np /newpath ldef /cm /currentmatrix ldef /sm /setmatrix ldef /rc {rectclip} bdef /rf {rectfill} bdef /rm /rmoveto ldef /rl /rlineto ldef /s /show ldef /sc {setcmykcolor} bdef /sr /setrgbcolor ldef /w /setlinewidth ldef /j /setlinejoin ldef /cap /setlinecap ldef % page state control /pgsv () def /bpage {/pgsv save def} bdef /epage {pgsv restore} bdef /bplot /gsave ldef /eplot {stroke grestore} bdef % orientation switch /portraitMode 0 def /landscapeMode 1 def % coordinate system mappings /dpi2point 0 def % font control /FontSize 0 def /FMS { /FontSize xstore %save size off stack findfont [FontSize 0 0 FontSize neg 0 0] makefont setfont }bdef /reencode { exch dup where {pop load} {pop StandardEncoding} ifelse exch dup 3 1 roll findfont dup length dict begin { 1 index /FID ne {def}{pop pop} ifelse } forall /Encoding exch def currentdict end definefont pop } bdef /isroman { findfont /CharStrings get /Agrave known } bdef /FMSR { 3 1 roll 1 index dup isroman {reencode} {pop pop} ifelse exch FMS } bdef /csm { 1 dpi2point div -1 dpi2point div scale neg translate landscapeMode eq {90 rotate} if } bdef % line types: solid, dotted, dashed, dotdash /SO { [] 0 setdash } bdef /DO { [.5 dpi2point mul 4 dpi2point mul] 0 setdash } bdef /DA { [6 dpi2point mul] 0 setdash } bdef /DD { [.5 dpi2point mul 4 dpi2point mul 6 dpi2point mul 4 dpi2point mul] 0 setdash } bdef % macros for lines and objects /L { lineto stroke } bdef /MP { 3 1 roll moveto 1 sub {rlineto} repeat } bdef /AP { {rlineto} repeat } bdef /PP { closepath fill } bdef /DP { closepath stroke } bdef /MR { 4 -2 roll moveto dup 0 exch rlineto exch 0 rlineto neg 0 exch rlineto closepath } bdef /FR { MR stroke } bdef /PR { MR fill } bdef /L1i { { currentfile picstr readhexstring pop } image } bdef /tMatrix matrix def /MakeOval { newpath tMatrix currentmatrix pop translate scale 0 0 1 0 360 arc tMatrix setmatrix } bdef /FO { MakeOval stroke } bdef /PO { MakeOval fill } bdef /PD { 2 copy moveto lineto stroke } bdef currentdict end def MathWorks begin 0 cap end MathWorks begin bpage bplot /dpi2point 12 def portraitMode 0216 7344 csm 861 341 5443 4342 MR c np 76 dict begin %Colortable dictionary /c0 { 0 0 0 sr} bdef /c1 { 1 1 1 sr} bdef /c2 { 1 0 0 sr} bdef /c3 { 0 1 0 sr} bdef /c4 { 0 0 1 sr} bdef /c5 { 1 1 0 sr} bdef /c6 { 1 0 1 sr} bdef /c7 { 0 1 1 sr} bdef /Helvetica /ISOLatin1Encoding 144 FMSR 1 j c1 0 0 6913 5187 PR 6 w DO 4 w SO 6 w c0 898 4615 mt 6255 4615 L 898 389 mt 6255 389 L 6255 4615 mt 6255 389 L 898 4615 mt 898 389 L 6255 389 mt 6255 389 L 898 389 mt 898 389 L 898 4615 mt 6255 4615 L 898 4615 mt 898 389 L 898 4615 mt 898 4615 L 898 4615 mt 898 4561 L 898 389 mt 898 443 L 1568 4615 mt 1568 4561 L 1568 389 mt 1568 443 L 2237 4615 mt 2237 4561 L 2237 389 mt 2237 443 L 2907 4615 mt 2907 4561 L 2907 389 mt 2907 443 L 3577 4615 mt 3577 4561 L 3577 389 mt 3577 443 L 4246 4615 mt 4246 4561 L 4246 389 mt 4246 443 L 4916 4615 mt 4916 4561 L 4916 389 mt 4916 443 L 5585 4615 mt 5585 4561 L 5585 389 mt 5585 443 L 6255 4615 mt 6255 4561 L 6255 389 mt 6255 443 L 898 4615 mt 952 4615 L 6255 4615 mt 6201 4615 L 898 4192 mt 952 4192 L 6255 4192 mt 6201 4192 L 898 3770 mt 952 3770 L 6255 3770 mt 6201 3770 L 898 3347 mt 952 3347 L 6255 3347 mt 6201 3347 L 898 2925 mt 952 2925 L 6255 2925 mt 6201 2925 L 898 2502 mt 952 2502 L 6255 2502 mt 6201 2502 L 898 2079 mt 952 2079 L 6255 2079 mt 6201 2079 L 898 1657 mt 952 1657 L 6255 1657 mt 6201 1657 L 898 1234 mt 952 1234 L 6255 1234 mt 6201 1234 L 898 812 mt 952 812 L 6255 812 mt 6201 812 L 898 389 mt 952 389 L 6255 389 mt 6201 389 L 898 389 mt 6255 389 L 898 4615 mt 6255 4615 L 898 4615 mt 898 389 L 6255 4615 mt 6255 389 L 6255 4615 mt 6255 4615 L 898 4615 mt 898 4615 L gs 898 389 5358 4227 MR c np 1 -36 2 0 1 20 1 0 2 -20 1 0 1 36 2 0 1 0 1 0 2 -36 1 0 1 36 2 0 1 -1 1 0 2 1 1 0 1 0 2 0 1 0 2 0 1 -36 1 36 2 -1 1 0 1 1585 2 -1579 1 0 1 0 2 1876 1 -1881 1 0 2 0 1 1232 1 -1257 2 2297 1 -2272 1 1671 2 -1734 1 210 1 -120 2 820 1 -881 1 0 2 0 1 1256 1 -1222 2 1329 1 -1354 1 1247 2 -1222 1 0 1 0 2 1648 1 -1712 1 18 2 70 1 858 1 -946 2 0 1 0 1 91 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 616 1 -668 2 277 1 -315 1 40 2 -2 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 272 1 -310 1 36 2 2 1 492 1 -461 2 1869 1 -1875 1 0 2 0 1 0 1 0 2 1979 5885 2571 100 MP stroke 1 -1973 1 1869 2 -1875 1 0 1 0 2 0 1 0 1 1561 2 -1597 1 0 1 0 2 9 1 2 1 467 2 -436 1 29 1 1931 2 -2011 1 69 1 533 2 -593 1 433 1 -372 2 -1 1 -58 1 0 2 0 1 347 1 -286 2 2136 1 -2199 1 1503 2 -751 1 -192 2 -519 1 665 1 -695 2 249 1 -287 1 476 2 514 1 -918 1 -25 2 16 1 -36 1 674 2 -672 1 501 1 -461 2 2584 1 -2625 1 19 2 0 1 16 1 0 2 1064 1 651 1 -1077 2 -672 1 59 1 0 2 -50 1 0 1 3076 2 -3087 1 20 1 0 2 -20 1 0 1 19 2 0 1 -19 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -29 1 29 1 20 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1515 2 -1539 1 -25 1 0 5753 4615 100 MP stroke 2 0 1 1466 1 -413 2 -1053 1 311 1 -271 2 533 1 -502 1 -1 2 0 1 0 1 0 2 1177 1 -1221 1 387 2 -382 1 189 1 349 2 -477 1 0 1 0 2 0 1 0 1 0 2 762 1 -846 1 0 2 0 1 413 1 -419 2 90 1 0 1 1 2 0 1 -1 1 0 2 -75 1 1 1 162 2 -154 1 0 1 0 2 -1 1 0 1 547 2 -570 1 18 2 69 1 1199 1 -1258 2 -1 1 0 1 20 2 0 1 1037 1 -994 2 870 1 -931 1 1257 2 -1258 1 35 1 0 2 1344 1 -1369 1 -40 2 0 1 31 1 0 2 58 1 0 1 0 2 0 1 144 1 -204 2 -3 1 0 1 0 2 0 1 0 1 0 2 491 1 -446 1 -70 2 0 1 0 1 0 2 0 1 0 1 932 2 -902 1 0 1 0 2 350 1 -289 1 0 2 0 1 696 1 -780 2 0 5620 4607 100 MP stroke 1 0 1 220 2 -136 1 0 2 0 1 1959 1 -2022 2 0 1 0 1 0 2 0 1 1083 1 -1086 2 198 1 -16 1 222 2 -399 1 9 1 0 2 -9 1 0 1 0 2 0 1 9 1 0 2 0 1 0 1 0 2 0 1 271 1 -309 2 18 1 -18 1 0 2 0 1 0 1 0 2 209 1 -119 1 0 2 0 1 0 1 0 2 0 1 0 1 969 2 -1059 1 0 1 0 2 0 1 0 1 0 2 0 1 515 1 -425 2 0 1 0 1 -22 2 0 1 0 1 0 2 1702 1 -1708 2 0 1 0 1 1562 2 -1597 1 0 1 0 2 186 1 -207 1 10 2 0 1 151 1 -144 2 217 1 -224 1 1033 2 -962 1 0 1 0 2 1 1 0 1 -1 2 0 1 -49 1 0 2 -9 1 0 1 58 2 0 1 -58 1 0 2 0 1 0 1 0 2 0 1 0 1 0 5488 4584 100 MP stroke 2 0 1 0 1 1516 2 -1529 1 879 1 -807 2 155 1 -220 1 0 2 0 1 -23 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 49 1 20 2 663 1 -694 1 277 2 -315 1 52 1 16 2 22 1 -21 1 0 2 0 1 -1 1 0 2 0 1 0 1 2007 2 -2012 1 0 1 0 2 0 1 0 1 0 2 0 1 1751 1 -1745 2 21 1 0 1 819 2 -880 1 0 1 0 2 9 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 50 2 0 1 0 1 0 2 555 1 -616 1 0 2 0 1 370 1 -368 2 0 1 0 1 429 2 -368 1 0 1 0 2 932 1 -1022 2 49 1 20 1 -1 2 0 1 0 1 0 2 1 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 615 2 -683 1 53 1 16 2 682 1 -713 1 0 2 0 1 0 5355 4575 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 242 1 -280 1 0 2 0 1 38 1 0 2 0 1 0 1 276 2 -314 1 0 1 0 2 0 1 0 1 0 2 0 1 52 1 16 2 0 1 0 1 22 2 0 1 0 1 0 2 841 1 -902 2 0 1 0 1 350 2 -289 1 0 1 0 2 696 1 -780 1 0 2 0 1 220 1 -136 2 0 1 0 1 1675 2 -1702 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 996 2 -970 1 0 1 0 2 557 1 -619 1 0 2 0 1 -4 1 0 2 0 1 0 1 216 2 99 1 -301 1 1 2 49 1 0 1 -58 2 0 1 58 1 0 2 -49 1 0 1 -9 2 0 1 0 1 0 2 213 1 -218 2 194 1 -212 1 -6 2 0 1 0 1 0 2 422 1 -423 1 109 2 0 5222 4505 100 MP stroke 1 -18 1 0 2 18 1 0 1 916 2 -1024 1 27 1 0 2 -4 1 0 1 -23 2 0 1 49 1 20 2 21 1 0 1 -91 2 0 1 70 1 0 2 2 1 -24 1 -20 2 0 1 0 1 0 2 0 1 0 1 36 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -16 1 0 2 0 1 0 1 16 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -1 2 0 1 0 1 0 2 -35 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 36 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -1 2 0 1 1 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 5090 4550 100 MP stroke 1 0 2 -36 1 36 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -36 1 0 2 0 1 0 1 0 2 0 1 36 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -16 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -20 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1861 1 -1850 2 0 1 0 1 0 2 0 1 0 1 0 2 50 1 0 2 1457 1 -1529 1 -16 2 0 1 16 1 0 2 189 1 -181 1 403 2 -398 1 9 1 0 2 0 1 0 1 0 2 0 1 533 1 -502 2 992 1 -1061 1 52 2 17 1 0 1 0 2 708 1 -739 1 2551 2 -2543 1 1 1 0 2 -19 1 0 1 35 2 0 1 0 1 0 2 0 1 0 1 -36 2 0 4957 4586 100 MP stroke 1 20 1 0 2 16 1 0 1 0 2 0 1 1477 1 -1502 2 467 1 -436 1 0 2 0 1 0 1 0 2 1448 1 -1519 2 397 1 -366 1 1298 2 -1311 1 37 1 16 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 39 1 0 1 1 2 0 1 2450 1 -2532 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 20 1 0 2 -20 1 0 1 20 2 0 1 -20 1 0 2 0 1 0 1 35 2 0 1 98 1 0 2 1 1 0 1 -1 2 0 1 2 2 0 1 -2 1 0 2 2 1 0 1 -1 2 0 1 0 1 0 2 0 1 0 1 -98 2 0 1 -35 1 0 2 35 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 4825 4550 100 MP stroke 2 0 1 0 1 0 2 713 1 -747 1 0 2 0 1 9 1 0 2 -9 1 0 1 0 2 0 1 59 1 0 2 130 1 -194 1 194 2 -212 1 242 1 -158 2 789 1 -850 1 1707 2 -1674 1 1 1 0 2 -1 1 0 1 0 2 0 1 1 2 0 1 -1 1 0 2 1 1 0 1 -1 2 0 1 0 1 0 2 1 1 0 1 1410 2 -1473 1 58 1 11 2 637 1 -668 1 0 2 0 1 1489 1 -1464 2 0 1 0 1 1467 2 -1461 1 0 1 0 2 992 1 -1061 1 51 2 18 1 0 1 0 2 21 1 0 1 -21 2 0 1 -70 1 0 2 70 1 0 1 -70 2 0 1 911 1 -881 2 9 1 0 1 0 2 0 1 50 1 0 2 143 1 -207 1 0 2 0 1 -1 2 0 1 -23 1 0 2 441 1 -354 1 -58 2 0 1 9 1 0 2 0 1 0 4692 4575 100 MP stroke 1 0 2 0 1 -9 1 0 2 59 1 0 1 -59 2 0 1 280 1 -309 2 0 1 0 1 694 2 -631 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1232 1 -1257 2 437 1 -406 1 596 2 -665 1 58 1 11 2 -70 1 0 1 91 2 0 1 -21 2 0 1 21 1 0 2 1096 1 -1162 1 371 2 -366 1 664 1 -687 2 0 1 0 1 10 2 0 1 -16 1 0 2 6 1 0 1 10 2 0 1 476 1 -493 2 0 1 0 1 1 2 0 1 -1 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 91 2 0 1 -21 1 0 2 21 1 0 1 -21 2 0 1 -70 1 0 2 91 1 0 1 -21 2 0 1 0 1 0 2 990 1 -1059 1 0 4560 4613 100 MP stroke 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 24 2 0 1 3 1 -3 2 -24 1 0 1 51 2 18 1 0 1 0 2 0 1 0 1 -1 2 0 1 22 1 0 2 -91 1 0 1 91 2 0 1 -22 1 0 2 742 1 -804 1 10 2 0 1 -16 1 16 2 -10 1 0 1 2375 2 -2334 1 16 1 0 2 -36 1 0 1 36 2 0 1 -16 1 0 2 -19 1 0 1 35 2 0 1 -16 1 0 2 15 1 0 1 -35 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 36 1 0 2 -16 1 0 1 -19 2 0 1 19 1 0 2 16 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 4427 4550 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 -35 2 0 1 -1 1 0 2 0 1 0 1 36 2 0 1 -1 2 0 1 0 1 0 2 -35 1 0 1 0 2 0 1 133 1 0 2 -133 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1 1 0 1 -1 2 0 1 0 1 0 2 133 1 0 1 -133 2 0 1 36 1 0 2 -35 1 0 1 -1 2 0 1 134 1 0 2 -1 1 0 1 -113 2 0 1 -20 1 0 2 1 1 0 1 -1 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1 2 0 1 -1 1 0 2 35 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 2 2 0 1 -1 1 0 2 -1 1 0 1 1 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1 1 0 2 -1 4294 4550 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -1 2 0 1 -35 1 0 2 1 1 0 1 -1 2 0 1 1 1 0 2 0 1 0 1 1225 2 -1163 1 0 1 0 2 -30 1 -13 1 -1 2 0 1 1944 2 -1991 1 0 1 0 2 752 1 -713 1 437 2 -406 1 682 1 -713 2 0 1 0 1 0 2 0 1 0 1 0 2 492 1 -461 1 0 2 0 1 -1 1 0 2 1 1 0 1 1117 2 -1162 1 0 1 0 2 2299 1 -2296 1 0 2 0 1 1893 1 -1920 2 0 1 0 1 24 2 0 1 -1 1 0 2 -23 1 0 1 0 2 0 1 18 1 -18 2 751 1 -724 1 1617 2 -1628 1 735 1 -724 2 2362 1 -2389 1 18 2 -18 1 226 1 -136 2 -90 1 0 2 960 1 -931 1 540 2 -563 1 1236 1 -1244 2 215 1 -207 1 386 2 -393 1 910 1 -880 4162 4584 100 MP stroke 2 546 1 -506 1 1869 2 -1875 1 0 1 0 2 1769 1 -1764 1 638 2 -668 1 554 1 -524 2 1697 1 -1702 1 0 2 0 1 1241 1 -1266 2 2701 1 -2676 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1344 1 -1369 2 2377 1 -2352 1 1878 2 -1708 1 543 1 -747 2 58 1 0 1 -58 2 0 1 9 1 0 2 0 1 0 2 1271 1 -1246 1 0 2 0 1 -16 1 0 2 808 1 -826 1 2115 2 -2117 1 0 1 0 2 1057 1 960 1 -2017 2 0 1 36 1 0 2 1769 1 -1764 1 903 2 -971 1 52 1 16 2 1870 1 -1875 1 1344 2 -1369 1 537 1 -506 2 1869 1 -1875 1 2231 2 -2225 1 862 1 -902 2 558 1 -560 1 432 2 -372 1 139 1 -203 2 372 1 -366 1 429 2 -368 1 2130 1 -2193 2 20 1 0 1 0 2 0 1 0 1 0 2 0 4029 4566 100 MP stroke 1 0 2 -20 1 0 1 0 2 0 1 0 1 0 2 36 1 0 1 -16 2 0 1 0 1 0 2 1321 1 -1369 1 0 2 0 1 933 1 -903 2 446 1 -406 1 2157 2 -2199 1 36 1 0 2 -16 1 0 1 -20 2 0 1 1984 1 -1942 2 0 1 0 1 1875 2 -1881 1 1232 1 -1257 2 -40 1 0 1 0 2 0 1 577 1 -506 2 1869 1 -1875 1 -36 2 0 1 36 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 -16 2 0 1 962 1 -1003 2 -6 1 0 1 607 2 -544 1 1769 1 -1764 2 638 1 -668 1 554 2 -524 1 1870 1 -1875 2 0 1 0 1 1460 2 -1485 1 1271 1 -1246 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -1 1 0 1 0 2 0 1 0 1 0 3897 4551 100 MP stroke 2 -35 1 0 1 20 2 0 1 -20 1 0 2 35 1 0 1 0 2 0 1 -34 1 0 2 -1 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 36 1 0 2 0 1 0 1 -36 2 0 1 1 1 0 2 -1 1 0 1 0 2 0 1 1 1 0 2 35 1 0 1 0 2 0 1 1948 1 -1942 2 21 1 0 1 577 2 -667 1 69 1 -1 2 22 1 -21 1 0 2 0 1 0 1 0 2 21 1 0 1 1959 2 -2022 1 0 1 0 2 35 1 0 1 -16 2 0 1 1207 1 -1163 2 -21 1 0 2 894 1 -934 1 1010 2 -1039 1 963 1 -934 2 59 1 0 1 -59 2 0 1 58 1 0 2 371 1 -368 1 -21 2 0 1 683 1 -714 2 0 1 0 1 437 2 -406 1 0 1 0 2 2284 1 -2291 1 0 2 0 1 0 3764 4551 100 MP stroke 1 0 2 0 1 0 1 1949 2 -1942 1 0 1 0 2 708 1 -739 1 0 2 0 1 271 1 -309 2 0 1 0 1 38 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 277 1 -315 2 0 1 0 2 38 1 0 1 549 2 -519 1 1702 1 -1708 2 1 1 0 1 1241 2 -1266 1 2377 1 -2352 2 63 1 -128 1 0 2 70 1 0 1 0 2 638 1 -668 1 549 2 -519 1 1697 1 -1702 2 0 1 0 1 1460 2 -1485 1 2297 1 -2272 2 -1 1 0 1 1752 2 -1745 1 683 1 -714 2 249 1 -287 1 0 2 0 1 0 1 0 2 0 1 0 1 52 2 17 1 0 1 0 2 596 1 -665 1 0 2 0 1 45 1 -45 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 55 2 13 1 1 1 0 2 708 1 -739 1 0 2 0 3631 4575 100 MP stroke 1 271 1 -309 2 39 1 -1 1 537 2 -506 1 1869 1 -1875 2 0 1 0 1 1751 2 -1745 1 663 1 -694 2 537 1 -506 1 1668 2 -1674 1 0 1 0 2 1630 1 -1655 1 492 2 -461 1 633 1 -664 2 833 1 -871 1 35 2 -35 1 18 1 -18 2 40 1 29 1 719 2 -750 1 544 1 -514 2 1669 1 -1674 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1979 2 -1973 1 663 1 -694 2 271 1 -271 1 544 2 -514 1 1 1 0 2 0 1 0 1 -1 2 0 1 1 1 0 2 663 1 -694 1 537 2 -506 1 663 1 -694 2 533 1 -502 1 664 2 -695 1 533 1 -502 2 621 1 -632 1 727 2 -747 1 544 1 -513 2 621 1 -690 1 49 2 -49 1 18 1 -18 2 58 1 11 1 955 2 -1024 1 18 1 -18 2 53 1 16 1 580 2 -649 1 45 3499 4568 100 MP stroke 2 -45 1 0 1 0 2 0 1 0 1 165 2 -102 1 3286 1 -3349 2 18 1 -18 1 40 2 29 1 633 1 -664 2 492 1 -461 1 1668 2 -1674 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 3366 4550 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 2168 1 -2216 2 1 1 0 1 565 2 -552 1 0 1 0 2 214 1 -220 1 0 2 0 1 -23 1 0 2 0 1 0 1 459 2 -371 1 0 1 0 2 529 1 -590 1 0 2 0 1 0 1 0 2 0 1 0 1 11 2 0 1 -9 1 0 2 0 1 0 1 0 2 0 1 59 1 0 2 0 1 0 1 -59 2 0 1 0 1 0 2 389 1 -328 1 0 2 0 1 -21 1 0 2 0 1 0 1 2214 2 -2220 1 0 2 0 1 0 1 0 2 1 1 0 1 -18 2 0 1 1 1 0 2 0 1 0 1 0 2 0 1 872 1 -831 2 -1 1 0 1 2017 2 -2057 1 0 1 0 2 1767 1 -1745 1 1875 2 -1881 1 0 1 0 2 0 1 0 1 0 3234 4550 100 MP stroke 2 0 1 0 1 0 2 1241 1 -1266 1 0 2 0 1 434 1 -382 2 -22 1 0 1 903 2 -971 1 52 1 16 2 1 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 21 2 0 1 0 2 0 1 -21 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 683 1 -714 1 0 2 0 1 242 1 -280 2 0 1 0 1 459 2 -372 1 0 1 0 2 559 1 -619 1 0 2 0 1 0 1 0 2 0 1 0 1 433 2 -371 1 0 1 0 2 0 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 -1 2 0 1 0 1 0 2 515 1 -575 1 0 2 0 1 0 1 0 2 0 1 0 1 384 2 -382 1 0 2 0 1 425 1 -364 2 0 1 0 1 2130 2 -2193 1 0 1 0 2 0 1 0 1 0 2 0 1 36 1 0 2 0 1 0 3101 4550 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 -36 2 0 1 20 1 0 2 0 1 0 1 -20 2 0 1 36 1 0 2 -36 1 0 1 0 2 0 1 1110 1 -1050 2 0 1 0 1 -49 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 242 2 -280 1 38 2 0 1 554 1 -524 2 0 1 0 1 0 2 0 1 0 1 0 2 1 1 0 1 0 2 0 1 1701 1 -1708 2 0 1 0 1 0 2 0 1 0 1 0 2 -34 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 1043 2 -980 1 0 1 0 2 820 1 -881 1 0 2 0 1 9 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 549 1 -519 2 0 1 0 1 -69 2 0 1 0 2 0 1 0 1 0 2 0 2968 4614 100 MP stroke 1 0 1 70 2 0 1 904 1 -973 2 51 1 18 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 21 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -21 1 0 2 0 1 0 1 21 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 842 1 -903 2 0 1 0 1 0 2 0 1 0 1 0 2 1227 1 -1229 2 0 1 0 1 20 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1090 1 -1050 1 498 2 -558 1 0 1 0 2 28 1 14 1 0 2 0 1 0 1 0 2 0 1 0 1 683 2 -714 1 1247 1 -1222 2 0 1 0 1 0 2 0 1 -36 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2836 4586 100 MP stroke 1 0 2 0 1 0 1 0 2 0 1 0 1 36 2 0 1 1329 1 -1354 2 437 1 -406 2 0 1 0 1 21 2 0 1 -91 1 0 2 70 1 0 1 21 2 0 1 871 1 -932 2 1227 1 -1229 1 748 2 -746 1 0 1 0 2 2306 1 -2272 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 1232 1 -1257 2 0 1 0 1 416 2 -364 1 0 1 0 2 643 1 -695 1 2297 2 -2272 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 713 1 -747 1 0 2 0 1 3146 1 -3128 2 0 1 0 1 -20 2 0 1 0 1 0 2 1554 1 -1581 1 0 2 0 1 0 1 0 2 0 1 0 1 346 2 -283 1 0 1 0 2 -1 2703 4551 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 1242 2 -1266 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 549 1 -519 2 0 1 0 1 0 2 0 1 0 1 0 2 22 1 0 1 -22 2 0 1 0 1 0 2 0 1 0 1 1870 2 -1875 1 0 1 0 2 0 1 0 1 0 2 0 1 -16 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 897 1 -854 1 0 2 0 1 820 1 -881 2 0 1 0 1 59 2 0 1 -59 1 0 2 9 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 605 1 -616 2 0 1 0 1 -27 2 0 1 0 1 0 2571 4613 100 MP stroke 2 49 1 20 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 664 1 -695 2 549 1 -519 1 0 2 0 1 1 1 0 2 0 1 0 1 -1 2 0 1 0 1 0 2 1 1 0 1 904 2 -973 1 51 1 18 2 0 1 0 1 21 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1195 1 -1261 1 0 2 0 1 31 1 14 2 1110 1 -1179 1 39 2 -1 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1507 2 -1529 1 879 1 -807 2 499 1 -560 1 2996 2 -2976 1 1207 1 -1167 2 863 1 -951 1 0 2 0 1 28 1 0 2 22 1 20 1 0 2 0 1 21 1 0 2 0 1 0 1 738 2 -822 1 0 1 0 2 220 1 -136 2 0 1 0 1 1195 2 -1261 1 0 2438 4589 100 MP stroke 1 0 2 405 1 -400 1 0 2 0 1 612 1 -641 2 74 1 -36 1 1058 2 -1032 1 0 1 0 2 -1 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 2270 2 -2264 1 0 1 0 2 0 1 0 1 0 2 0 1 990 1 -1059 2 0 1 0 1 0 2 0 1 0 1 0 2 52 1 17 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 742 2 -805 1 0 1 0 2 173 1 -155 1 0 2 0 1 31 1 14 2 0 1 0 1 -70 2 0 1 0 1 0 2 932 1 -902 1 0 2 0 1 449 1 -409 2 0 1 0 1 -70 2 0 1 0 1 0 2 28 1 0 1 0 2 0 1 384 1 -382 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2306 4584 100 MP stroke 2 0 1 0 1 59 2 0 1 0 1 0 2 -59 1 0 2 0 1 0 1 563 2 -524 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 21 2 0 1 0 1 0 2 -21 1 0 1 0 2 0 1 -70 1 0 2 0 1 0 1 18 2 70 1 0 1 0 2 -49 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 204 2 -218 1 -24 1 0 2 0 1 0 1 0 2 0 1 2969 2 -2942 1 36 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 2024 1 -2060 1 0 2 0 1 -27 1 0 2 0 1 0 1 52 2 17 1 21 1 0 2 560 1 -650 1 0 2 0 1 0 2173 4613 100 MP stroke 1 0 2 0 1 0 1 58 2 11 1 0 1 0 2 0 1 0 1 0 2 0 1 2013 1 -2019 2 0 1 0 1 0 2 0 1 0 1 0 2 1329 1 -1354 1 0 2 0 1 49 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1027 2 -1115 1 0 1 0 2 911 1 -881 1 213 2 -218 1 387 1 -382 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 556 1 -558 2 0 1 0 1 -27 2 0 1 0 1 0 2 18 1 -18 1 0 2 0 1 0 1 0 2 0 1 0 1 63 2 6 1 0 1 0 2 682 1 -713 1 0 2 0 1 463 2 -432 1 0 1 0 2 1875 1 -1881 1 0 2 0 1 1978 1 -1972 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 2040 4544 100 MP stroke 1 0 1 0 2 0 1 0 1 707 2 -738 1 0 1 0 2 242 1 -280 1 0 2 0 1 16 1 -16 2 0 1 0 1 161 2 -123 1 0 1 0 2 561 1 -599 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 39 1 31 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 662 2 -731 1 0 1 0 2 27 1 -27 1 0 2 0 1 19 1 -19 2 0 1 0 1 48 2 -10 1 0 1 0 2 263 1 -301 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 428 2 -399 1 0 1 0 2 217 1 -222 1 0 1908 4589 100 MP stroke 2 0 1 31 1 14 2 0 1 0 1 -70 2 0 1 0 1 0 2 932 1 -902 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 58 1 0 2 -49 1 0 1 49 2 0 1 0 1 0 2 533 1 -593 1 0 2 0 1 575 1 -602 2 0 1 0 1 69 2 0 1 21 1 0 2 -21 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 682 1 -713 2 0 1 0 1 440 2 -409 1 0 1 0 2 614 1 -683 1 0 2 0 1 53 1 16 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -70 1 0 2 91 1 0 1 -22 2 0 1 0 1 0 2 597 1 -665 1 0 2 0 1 57 1 -57 2 0 1 0 1 55 2 14 1775 4544 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 -70 1 0 2 91 1 0 1 0 2 0 1 616 1 -668 2 0 1 0 1 0 2 0 1 0 1 0 2 49 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 331 2 -328 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -21 2 0 1 0 1 0 2 707 1 -738 1 0 2 0 1 0 1 0 2 0 1 0 1 -9 2 0 1 9 1 0 2 49 1 0 1 0 2 0 1 500 2 -560 1 0 1 0 2 0 1 0 1 0 2 0 1 9 1 2 2 50 1 0 1 -50 2 0 1 0 1 0 2 193 1 -207 1 0 2 0 1 0 1 0 2 0 1 0 1 15 2 -1 1 0 1 0 2 -9 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 1643 4584 100 MP stroke 2 0 1 0 1 0 2 213 1 -218 1 -24 2 0 1 24 1 0 2 0 1 0 1 189 2 -207 1 -8 1 0 2 55 1 16 1 0 2 0 1 -70 2 0 1 0 1 0 2 17 1 73 1 0 2 0 1 515 1 -577 2 0 1 0 1 0 2 0 1 0 1 0 2 370 1 -368 1 429 2 -368 1 819 1 -880 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 617 1 -619 2 -9 1 -18 1 167 2 -144 1 0 1 0 2 26 1 20 1 0 2 0 1 0 1 0 2 0 1 0 1 -40 2 -2 1 543 1 -570 2 69 1 0 1 0 2 0 1 40 1 0 2 -19 1 0 2 19 1 0 1 0 2 0 1 -19 1 0 2 -90 1 0 1 90 2 0 1 0 1 0 2 -90 1 0 1 1343 2 -1319 1 433 1 -370 2 0 1 0 1510 4526 100 MP stroke 1 1 2 0 1 1 1 0 2 0 1 0 1 0 2 0 1 498 1 -560 2 432 1 -372 1 1458 2 -1529 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 207 2 -185 1 0 1 0 2 242 1 -280 1 0 2 0 1 49 1 20 2 0 1 0 2 0 1 0 1 0 2 0 1 741 1 -804 2 0 1 0 1 0 2 0 1 0 1 0 2 161 1 -144 1 190 2 -207 1 189 1 -105 2 0 1 0 1 -21 2 0 1 0 1 0 2 -69 1 0 1 0 2 0 1 15 1 1 2 436 1 -452 1 0 2 0 1 29 1 -2 2 2368 1 -2348 1 0 2 0 1 0 1 0 2 0 1 0 1 1493 2 -1502 1 0 1 0 2 0 1 0 1 0 2 0 1 620 1 -658 2 0 1 0 2 0 1 0 1 0 2 0 1 323 1 -285 2 0 1377 4575 100 MP stroke 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 492 1 -461 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 580 1 -649 2 0 1 0 1 45 2 -45 1 0 1 0 2 27 1 0 1 0 2 0 1 -27 1 0 2 0 1 0 1 52 2 17 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 841 1 -881 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 1085 2 -1115 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 932 1 -902 1 0 2 0 1 0 1 0 2 0 1 0 1 9 2 0 1 -9 1 0 2 60 1 0 1245 4524 100 MP stroke 1 0 2 0 1 515 1 -577 2 0 1 0 2 0 1 0 1 0 2 0 1 2296 1 -2296 2 0 1 0 1 36 2 0 1 0 1 0 2 -1 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -15 2 0 1 0 1 0 2 16 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -36 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 20 1 0 2 0 1 0 2 16 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 1 1 0 1 0 2 0 1 -1 1 0 2 0 1 0 1 1 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 -16 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -19 1112 4585 100 MP stroke 1 0 1 -1 2 0 1 0 1 0 2 0 1 0 1 1 2 0 1 0 1 0 2 -1 1 0 1 0 2 0 1 36 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -1 1 0 1 0 2 0 1 1 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 -16 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 16 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 980 4550 100 MP stroke 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 0 1 0 1 0 2 -65 899 4615 61 MP stroke gr end eplot epage end showpage %%EndDocument endTexFig 300 579 a Fp(F)o(igur)o(e)d(2.)17 b Fu(Plot)11 b(of)f(soprano-tenor)d (correlations)i(versus)g(time,)i(as)e(measured)g(by)g(the)h(posterior)f (probabilities)g(of)h(a)g(mixed)300 618 y(memory)d(HMM.)300 752 y Fm(than)h(the)g(cross-correlations)f(between)h(them.)15 b(W)m(e)8 b(vie)o(w)g(the)g(approximation)e(as)j(a)g(computationally) 300 802 y(cheap)j(way)f(of)g(inte)o(grating)f(HMMs)h(that)g(ha)o(v)o(e) h(been)g(trained)e(on)h(parallel)g(data)g(streams.)20 b(Its)10 b(main)300 852 y(virtue)h(is)i(that)e(it)h(e)o(xploits)f(the)i (modeler')n(s)f(prior)f(kno)o(wledge)h(that)g(these)h(separate)g(HMMs)g (should)300 901 y(be)e(weakly)f(coupled.)15 b(When)10 b(this)f(assumption)h(holds,)g(the)g(approximation)e(is)i(quite)g (accurate.)333 952 y(T)m(o)i(test)f(these)i(ideas,)f(we)h(\256tted)e(a) h(mix)o(ed)g(memory)g(HMM)g(to)f(the)h(Bach)g(fugue)f(from)h(section)f (3.)300 1002 y(One)j(hopes)g(in)f(this)f(model)i(that)f(the)g(hidden)g (states)h(will)f(re\257ect)h(musical)g(structure)f(o)o(v)o(er)h(longer) 300 1052 y(time)g(scales)i(than)e(a)h(single)e(note.)27 b(In)14 b(our)g(e)o(xperiments,)i(each)g(v)o(oice)e(had)h(a)g (component)f(HMM)300 1102 y(with)d(six)h(hidden)f(states;)i(thus,)g(in) e(our)h(pre)o(vious)f(notation,)g Fl(n)j Fe(=)h(6)d Fm(and)g Fl(k)j Fe(=)g(4)p Fm(.)21 b(W)m(e)12 b(employed)g(a)300 1152 y(V)n(iterbi)g(approximation)g(to)h(the)g(full)f(EM)i(algorithm,)g (meaning)f(that)g(the)h(posterior)e(probabilities)300 1201 y(in)f(eqs.)h(\(17\)\261\(20\))d(were)j(conditioned)d(not)h(only)g (on)h(the)g(observ)o(ations)f Fl(J)t Fm(,)i(b)o(ut)e(also)i(on)e(the)h (V)n(iterbi)300 1251 y(path,)i Fl(I)416 1236 y Fs(\003)435 1251 y Fm(.)23 b(The)13 b(most)g(probable)f(sequence)i(of)e(hidden)g (states)h Fl(I)1261 1236 y Fs(\003)1293 1251 y Fm(was)g(estimated)g(by) f(the)h(iterati)o(v)o(e)300 1301 y(procedure)i(described)h(abo)o(v)o (e.)31 b(Again)15 b(it)f(was)i(interesting)d(to)i(see)h(ho)o(w)f(this)g (model)g(disco)o(v)o(ered)300 1351 y(correlations)i(between)h(the)g (dif)o(ferent)f(v)o(oices)h(of)g(the)f(fugue.)38 b(Figure)18 b(2)f(sho)o(ws)h(a)g(plot)f(of)h(the)300 1401 y(posterior)11 b(probabilities)e Fl(P)d Fe(\()p Fl(x)752 1386 y Fk(S)752 1411 y(t)789 1401 y Fe(=)14 b Fl(T)6 b Ff(j)p Fl(I)898 1386 y Fs(\003)917 1401 y Fl(;)h(J)t Fe(\))12 b Fm(v)o(ersus)g(time,)h (calculated)f(from)g(the)g(factorial)f(HMM)300 1450 y(\(after)c (training\).)13 b(The)8 b(frequent)f(pulses)g(indicate)g(\(within)f (the)h(frame)o(work)g(of)g(this)g(model\))g(moments)300 1500 y(of)j(strong)f(coupling)g(between)h(the)h(soprano)e(and)i(tenor)e (themes)i(of)f(the)g(fugue.)300 1620 y Fn(5.)42 b(Discussion)300 1722 y Fm(Man)o(y)12 b(parameterizations)h(ha)o(v)o(e)g(been)f (proposed)g(for)f(probabilistic)f(models)i(of)g(time)g(series.)21 b(The)300 1771 y(mix)o(ed)c(memory)g(models)f(in)g(this)g(note)g(ha)o (v)o(e)h(three)g(distinguishi)o(ng)c(features.)35 b(First,)17 b(the)o(y)g(can)300 1821 y(e)o(xpress)d(a)g(rich)f(set)g(of)g (probabilistic)e(dependencies,)k(including)d(coupled)g(dynamics)i(in)e (factorial)300 1871 y(models.)20 b(Second,)13 b(the)o(y)f(can)g(be)g (\256tted)g(by)f(EM)h(algorithms,)g(thus)f(a)o(v)o(oiding)f(potential)h (dra)o(wbacks)300 1921 y(of)g(gradient)f(descent.)19 b(Third,)11 b(the)o(y)g(are)h(compact)g(and)g(easy)g(to)e(interpret;)g (notably)m(,)h(as)h(in)f(ordinary)300 1971 y(Marko)o(v)6 b(models,)i(e)o(v)o(ery)g(parameter)g(de\256nes)f(a)h(simple)e (conditional)f(probability)m(.)12 b(All)6 b(these)h(features)300 2021 y(should)i(enable)i(researchers)h(to)e(b)o(uild)e(more)j (sophisticated)e(models)i(of)f(dynamical)g(systems.)300 2140 y Fn(Acknowledgments)300 2242 y Fm(W)m(e)g(thank)g(Marne)o(y)g (Smyth)g(for)f(retrie)o(ving)g(the)h(word)f(lists,)g(T)m(ommi)h (Jaakkola)g(for)g(helping)f(us)h(with)300 2292 y(Finnish,)k(and)g (Fernando)g(Pereira)h(for)e(pointing)f(out)h(the)h(application)f(to)g (web)h(page)h(prefetching.)300 2342 y(W)m(e)9 b(also)g(ackno)o(wledge)g (useful)g(discussions)f(with)g(Zoubin)g(Ghahramani)h(and)g(Y)-5 b(oram)10 b(Singer)n(.)k(This)300 2391 y(work)8 b(was)h(initiated)e (while)h(LS)i(was)f(a)g(member)h(of)f(the)g(Center)f(for)h(Biological)e (and)i(Computational)300 2441 y(Learning)f(at)h(MIT)m(.)g(During)e (that)h(time,)h(it)f(was)h(supported)e(by)h(NSF)h(grant)f(CD)n (A-9404932)e(and)j(ONR)300 2491 y(grant)h(N00014-94-1-077)o(7.)p eop %%Page: 11 11 11 10 bop 300 125 a Fh(MIXED)11 b(MEMOR)m(Y)i(MARK)o(O)o(V)g(MODELS)834 b Fi(11)300 266 y Fn(Refer)o(ences)330 355 y Fu(1.)25 b(P)l(.)16 b(Baldi)e(and)g(Y)l(.)g(Chauvin.)f(Hybrid)h(modeling,)f (HMM/NN)h(architectures,)f(and)h(protein)f(applications.)h Fp(Neural)380 395 y(Computation)7 b Fu(8:1541\2611565)e(\(1996\).)330 433 y(2.)25 b(L.)12 b(Baum.)f(An)g(inequality)f(and)g(associated)f (maximization)h(technique)f(in)i(statistical)h(estimation)e(for)h (probabilistic)380 472 y(functions)g(of)h(a)f(Markov)f(process.)h(In)g (O.)i(Shisha)e(\(ed.\),)i Fp(Inequalities)d Fu(3:1\2618.)h(Academic)g (Press,)i(Ne)o(w)e(Y)l(ork,)h(NY)380 512 y(\(1972\).)330 550 y(3.)25 b(A.)6 b(Besta)o(vros)f(and)g(C.)h(Cunha.)f(A)h (prefetching)t(protocol)t(using)f(client)g(speculation)t(for)h(the)f (WWW)m(.)i Fp(Boston)e(University)380 590 y(Department)i(of)h(Computer) f(Science)g(T)m(echnical)g(Report)h(TR-95-011)f Fu(\(1995\).)330 628 y(4.)25 b(J.)10 b(Binder)o(,)e(D.)i(K)o(oller)o(,)f(S.)h(Russell,)f (and)f(K.)i(Kanazawa.)d(Adapti)o(ve)g(probabilistic)i(networks)e(with)i (hidden)f(v)o(ariables.)380 668 y Fp(Machine)e(Learning)h Fo(29)p Fu(:213\261244)e(\(1997\).)330 706 y(5.)25 b(H.)10 b(Bourlard)e(and)g(S.)h(Dupont.)f(A)h(ne)o(w)g(ASR)h(approach)c(based)i (on)g(independent)f(processing)g(and)h(recombination)f(of)380 745 y(partial)f(frequency)s(bands.)t(In)g(H.)g(Bunnell)f(and)t(W)m(.)i (Idsardi)e(\(eds.\),)g Fp(Pr)o(oceedings)s(of)h(the)f(4th)h (International)t(Confer)o(ence)380 785 y(on)i(Speech)e(and)h(Language)e (Pr)o(ocessing)p Fu(,)i(1:426\261429)e(\(1996\).)330 823 y(6.)25 b(C.)11 b(Bregler)e(and)g(S.)h(Omohundro.)e(Nonlinear)h (manifold)g(learning)f(for)i(visual)f(speech)g(recognition.)f(In)i(E.)g (Grimson)380 863 y(\(ed.\),)j Fp(Pr)o(oceedings)e(of)i(the)g(5th)f (International)g(Confer)o(ence)f(on)h(Computer)g(V)n(ision)p Fu(,)h(494\261499.)e(IEEE)j(Computer)380 902 y(Society)8 b(Press,)h(Los)f(Alamitos,)g(CA)h(\(1995\).)330 940 y(7.)25 b(S.)8 b(Chen)f(and)f(J.)i(Goodman.)e(An)h(empirical)g(study)f(of)h (smoothing)f(techniques)f(for)i(language)f(modeling.)g Fp(Pr)o(oceedings)380 980 y(of)i(the)g(34th)g(Annual)f(Meeting)g(of)h (the)g(Association)f(for)h(Computational)f(Linguistics)h Fu(310\261318)e(\(1996\).)330 1018 y(8.)25 b(C.)10 b(Cunha,)d(A.)i (Besta)o(vros,)g(and)f(M.)g(Crovella.)g(Characteristics)g(of)h(WWW)g (client-based)f(traces.)g Fp(Boston)g(University)380 1058 y(Department)f(of)h(Computer)f(Science)g(T)m(echnical)g(Report)h (TR-95-010)f Fu(\(1995\).)330 1096 y(9.)25 b(T)n(.)9 b(Dean)f(and)g(K.)h(Kanazawa.)e(A)i(model)f(for)g(reasoning)f(about)h (persistence)f(and)h(causation.)g Fp(Computational)f(Intelli-)380 1135 y(gence)g Fu(5\(3\):)h(142\261150)d(\(1989\).)314 1174 y(10.)24 b(A.)11 b(Dempster)o(,)e(N.)i(Laird,)f(and)g(D.)g(Rubin.) g(Maximum)f(likelihood)g(from)g(incomplete)g(data)h(via)g(the)g(EM)g (algorithm.)380 1213 y Fp(J)o(ournal)d(of)h(the)g(Royal)g(Statistical)g (Society)f Fu(B39,)h(1\26138)f(\(1977\).)314 1252 y(11.)24 b(M.)13 b(Dirst)g(and)f(A.)h(W)m(eigend.)g(Baroque)e(forecasting:)h(on) g(completing)f(J.)j(S.)f(Bach')n(s)g(last)g(fugue.)e(In)i(A.)g(W)m (eigend)380 1291 y(and)e(N.)h(Gershenfeld)e(\(eds.\),)i Fp(T)n(ime)g(Series)f(Pr)o(ediction:)g(F)m(or)o(ecasting)f(the)h(Futur) o(e)g(and)g(Understanding)d(the)k(P)m(ast)p Fu(.)380 1330 y(Addison-W)m(esley)n(,)7 b(Reading,)g(MA)h(\(1993\).)314 1369 y(12.)24 b(J.)11 b(Forbes,)f(T)n(.)h(Huang,)f(K.)h(Kanazawa,)d (and)i(S.)h(Russell.)g(The)g(B)o(A)l(Tmobile:)f(to)o(wards)g(a)h (Bayesian)e(automated)g(taxi.)380 1408 y Fp(Pr)o(oceedings)c(of)i(the)g (14th)g(International)f(J)o(oint)h(Confer)o(ence)e(on)h(Arti\256cial)i (Intelligence)p Fu(.)e(Montreal,)h(Canada)f(\(1995\).)314 1447 y(13.)24 b(Z.)9 b(Ghahramani)e(and)g(M.)h(Jordan.)f(Factorial)h (hidden)f(Markov)e(models.)j Fp(Machine)e(Learning)h Fo(29)p Fu(:245\261273)e(\(1997\).)314 1485 y(14.)24 b(D.)9 b(Haussler)o(,)e(A.)h(Krogh,)f(I.)i(Mian,)e(and)g(K.)i (Sjolander)n(.)f(Protein)g(modeling)e(using)h(hidden)g(Markov)e (models:)i(analysis)380 1524 y(of)13 b(globins.)g Fp(Pr)o(oceedings)e (of)j(the)f(Hawaii)g(International)f(Confer)o(ence)f(on)i(System)g (Sciences)f Fu(1:792\261802.)e(IEEE)380 1564 y(Computer)d(Society)h (Press,)h(Los)f(Alamitos,)h(CA)f(\(1993\).)314 1602 y(15.)24 b(I.)9 b(MacDonald)d(and)h(W)m(.)i(Zucchini.)e Fp(Hidden)g(Markov)f (and)h(Other)h(Models)f(for)h(Discr)o(ete-V)l(alued)f(T)n(ime)i(Series) p Fu(.)e(Chap-)380 1642 y(man)h(and)f(Hall)h(\(1997\).)314 1680 y(16.)24 b(A.)10 b(Nadas.)e(Estimation)h(of)g(probabilities)g(in)g (the)g(language)e(model)h(of)h(the)g(IBM)g(speech)e(recognition)h (system.)g Fp(IEEE)380 1720 y(T)n(ransactions)f(on)g(ASSP)h Fu(32\(4\):)g(859\261861)d(\(1984\).)314 1758 y(17.)24 b(H.)7 b(Ney)n(,)f(U.)h(Essen,)f(and)g(R.)h(Kneser)n(.)f(On)g (structuring)g(probabilistic)g(dependence)o(s)t(in)g(stochastic)g (language)f(modeling.)380 1797 y Fp(Computer)i(Speech)f(and)h(Language) f Fo(8)p Fu(:1\26138)g(\(1994\).)314 1836 y(18.)24 b(L.)5 b(Rabiner)n(.)g(A)g(tutorial)g(on)g(hidden)g(Markov)g(mode)o(ls)g(and)g (selec)o(ted)g(app)o(lications)g(in)g(spee)o(ch)g(reco)o(gn)o(ition.)g Fp(Pr)o(ocee)o(ding)o(s)380 1875 y(of)j(the)g(IEEE)h Fu(77\(2\):257\261286)c(\(1989\).)314 1914 y(19.)24 b(A.)10 b(Raftery)n(.)g(A)g(model)e(for)i(high-order)e(Markov)f(chains.)i Fp(J)o(ournal)f(of)i(the)f(Royal)g(Statistical)h(Society)f Fo(B47)p Fu(:528\261539)380 1953 y(\(1985\).)314 1991 y(20.)24 b(D.)12 b(Ron,)g(Y)l(.)g(Singer)o(,)f(and)g(N.)h(T)o(ishby)n (.)f(The)h(po)o(wer)f(of)g(amnesia:)g(learning)g(probabilistic)g (automata)f(with)i(v)o(ariable)380 2031 y(memory)7 b(length.)h Fp(Machine)e(Learning)h Fo(25)p Fu(:117\261150)e(\(1996\).)314 2069 y(21.)24 b(L.)14 b(Saul)f(and)f(M.)g(Jordan.)g(Exploiting)g (tractable)h(substructures)e(in)i(intractable)f(networks.)f(In)i(D.)g (T)m(ouretzky)n(,)f(M.)380 2109 y(Mozer)o(,)7 b(and)g(M.)i(Hasselmo)e (\(eds.\),)h Fp(Advances)f(in)h(Neural)f(Information)g(Pr)o(ocessing)f (Systems)i Fu(8:486\261492)d(\(1996\).)314 2147 y(22.)24 b(L.)14 b(Saul)f(and)f(F)m(.)i(Pereira.)f(Aggregate)e(and)g (mixed-order)g(Markov)f(models)i(for)h(statistical)g(language)e (processing.)380 2186 y Fp(Pr)o(oceedings)6 b(of)i(the)g(2nd)f(Confer)o (ence)f(on)h(Empirical)h(Methods)f(in)h(Natural)f(Language)e(Pr)o (ocessing)p Fu(,)h(81\26189)h(\(1997\).)314 2225 y(23.)24 b(C.)12 b(W)o(illiams)g(and)f(G.)h(Hinton.)f(Mean)f(\256eld)i(networks) e(that)i(learn)f(to)g(discriminate)g(temporally)g(distorted)g(strings.) 380 2264 y Fp(Pr)o(oceedings)6 b(of)i(the)g(Connectionist)f(Models)g (Summer)g(School)p Fu(,)g(18\26122)f(\(1990\).)314 2303 y(24.)24 b(J.)7 b(Y)m(amato,)f(J.)h(Ohya,)f(and)g(K.)h(Ishii.)h (Recognizing)t(human)e(action)g(in)g(time-sequential)g(images)g(using)g (hidden)f(Markov)380 2342 y(models.)j Fp(Pr)o(oceedings)e(of)i(the)g (1992)e(International)h(Confer)o(ence)f(on)i(Computer)f(V)n(ision)p Fu(,)h(379\261385)d(\(1992\).)314 2380 y(25.)24 b(A.)8 b(Zee)o(vi,)h(R.)f(Meir)o(,)g(and)e(R.)j(Adler)n(.)f(T)o(ime)g(series)g (prediction)e(using)h(mixtures)g(of)h(experts.)f(In)g(M.)h(Mozer)o(,)f (M.)h(Jordan,)380 2420 y(and)f(T)n(.)i(Petsche)f(\(eds.\),)g Fp(Advances)f(in)h(Neural)f(Information)g(Pr)o(ocessing)f(Systems)i Fu(9:309\261315)d(\(1997\).)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF