HMM入门介绍及程序代码_C语言_算法_其他

<html xmlns="http://www.w3.org/1999/xhtml"><head><meta charset="utf-8"><meta name="generator" content="pdf2htmlEX"><meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/css/base.min.css"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/css/fancy.min.css"><link rel="stylesheet" href="https://csdnimg.cn/release/download_crawler_static/1436597/raw.css"><script src="https://csdnimg.cn/release/download_crawler_static/js/compatibility.min.js"></script><script src="https://csdnimg.cn/release/download_crawler_static/js/pdf2htmlEX.min.js"></script><script>try{pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({});}catch(e){}</script><title></title></head><body><div id="sidebar" style="display: none"><div id="outline"></div></div><div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/1436597/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">Hidden Markov Mo dels</div><div class="t m0 x2 h2 y2 ff2 fs0 fc0 sc0 ls3 ws0">Sam Roweis</div><div class="t m0 x3 h2 y3 ff3 fs0 fc0 sc0 ls0 ws0">1 What Are HMMs ?</div><div class="t m0 x3 h2 y4 ff4 fs0 fc0 sc0 ls0 ws0">Hidden MarkovModels (HMMs) are a clas s of mo dels for mimicing the probability density of a sequence</div><div class="t m0 x3 h2 y5 ff4 fs0 fc0 sc0 ls0 ws0">of obs erved symbols. They are e ss entially stochastic nitestatemachines whichoutputasymboleachtime</div><div class="t m0 x3 h2 y6 ff4 fs0 fc0 sc0 ls0 ws0">they depart f rom a state. By specifying the state transistion probabilities between states and the symbol</div><div class="t m0 x3 h2 y7 ff4 fs0 fc0 sc0 ls1 ws0">generation model for e achstate, we can attempt tocapture theunderlying structureinalargesetofsymbol</div><div class="t m0 x3 h2 y8 ff4 fs0 fc0 sc0 ls0 ws0">strings.</div><div class="t m0 x3 h2 y9 ff4 fs0 fc0 sc0 ls0 ws0">In general, theoperational paradigm i s as follows: s elect a startingstate accordingtosome xe d probability</div><div class="t m0 x3 h2 ya ff4 fs0 fc0 sc0 ls0 ws0">distribution. Ateachtimestep, generatean outputsymbolbyinvokingthe generativemodel of the current</div><div class="t m0 x3 h2 yb ff4 fs0 fc0 sc0 ls1 ws0">state, andthen transition toanew state accordingtoastatic trans istion probabilitymatrix.</div><div class="t m0 x3 h2 yc ff4 fs0 fc0 sc0 ls1 ws0">Let us dene some notation for future convenience. Assume there are</div><div class="t m0 x4 h2 yc ff5 fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x5 h2 yc ff4 fs0 fc0 sc0 ls7 ws0">possible states</div><div class="t m0 x6 h2 yc ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x7 h2 yd ff6 fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 x8 h2 yc ff4 fs0 fc0 sc0 ls0 ws0">in our model,</div><div class="t m0 x3 h2 ye ff4 fs0 fc0 sc0 ls1 ws0">anddenotethe s et of all po ssible states by</div><div class="t m0 x9 h2 ye ff7 fs0 fc0 sc0 ls0 ws0">S</div><div class="t m0 xa h2 ye ff4 fs0 fc0 sc0 ls6 ws0">where</div><div class="t m0 xb h2 ye ff7 fs0 fc0 sc0 ls0 ws0">S</div><div class="t m0 xc h2 ye ff4 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 xd h2 ye ff7 fs0 fc0 sc0 ls0 ws0">f</div><div class="t m0 xe h2 ye ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 xf h2 yf ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x10 h2 ye ff5 fs0 fc0 sc0 ls1e ws0">;s</div><div class="t m0 x11 h2 yf ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x12 h2 ye ff5 fs0 fc0 sc0 ls1e ws0">;:::;s</div><div class="t m0 x13 h2 yf ff6 fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x14 h2 ye ff7 fs0 fc0 sc0 ls0 ws0">g</div><div class="t m0 x15 h2 ye ff4 fs0 fc0 sc0 ls0 ws0">. Tothi s set, we will add a special</div><div class="t m0 x3 h2 y10 ff4 fs0 fc0 sc0 ls1 ws0">state</div><div class="t m0 x16 h2 y10 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x17 h2 y11 ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x18 h2 y10 ff4 fs0 fc0 sc0 ls0 ws0">in whichthemodel always startsasanimplementational convenience { the us e of this state will be</div><div class="t m0 x3 h2 y12 ff4 fs0 fc0 sc0 ls0 ws0">explained later. Wemay choose touseoneofthestate s (usually</div><div class="t m0 x19 h2 y12 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x1a h2 y13 ff6 fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x1b h2 y12 ff4 fs0 fc0 sc0 ls22 ws0">)asan</div><div class="t m0 x1c h2 y12 ff9 fs0 fc0 sc0 ls1 ws0">end state</div><div class="t m0 x1d h2 y12 ff4 fs0 fc0 sc0 ls1a ws0">{in this cas e, whenever</div><div class="t m0 x3 h2 y14 ff4 fs0 fc0 sc0 ls0 ws0">themodel re aches this state, it stops. Let there b e</div><div class="t m0 x1e h2 y14 ff5 fs0 fc0 sc0 ls0 ws0">P</div><div class="t m0 x1f h2 y14 ff4 fs0 fc0 sc0 lsd ws0">possible outputsymbols</div><div class="t m0 x20 h2 y14 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x21 h2 y15 ff6 fs0 fc0 sc0 ls0 ws0">p</div><div class="t m0 x22 h2 y14 ff4 fs0 fc0 sc0 ls3 ws0">which comprise theoutput</div><div class="t m0 x3 h2 y16 ff4 fs0 fc0 sc0 ls1 ws0">alphabet</div><div class="t m0 x23 h2 y16 ff7 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x24 h2 y16 ff4 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 x25 h2 y16 ff7 fs0 fc0 sc0 ls0 ws0">f</div><div class="t m0 x26 h2 y16 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x27 h2 y17 ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x28 h2 y16 ff5 fs0 fc0 sc0 ls27 ws0">;a</div><div class="t m0 x29 h2 y17 ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x2a h2 y16 ff5 fs0 fc0 sc0 ls1e ws0">;:::;a</div><div class="t m0 x2b h2 y17 ff6 fs0 fc0 sc0 ls0 ws0">P</div><div class="t m0 x2c h2 y16 ff7 fs0 fc0 sc0 ls0 ws0">g</div><div class="t m0 x2d h2 y16 ff4 fs0 fc0 sc0 ls0 ws0">. Tothis s et, weaddthe special symbol</div><div class="t m0 x2e h2 y16 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x14 h2 y17 ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x2f h2 y16 ff4 fs0 fc0 sc0 ls3 ws0">which repre sentsthenull output{</div><div class="t m0 x3 h2 y18 ff4 fs0 fc0 sc0 ls1 ws0">in other words if themodel generates thesymbol</div><div class="t m0 x30 h2 y18 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x31 h2 y19 ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x32 h2 y18 ff4 fs0 fc0 sc0 ls0 ws0">it simply doe s not outputanything. Eachstate</div><div class="t m0 x33 h2 y18 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x34 h2 y19 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x35 h2 y18 ff4 fs0 fc0 sc0 ls0 ws0">has</div><div class="t m0 x3 h2 y1a ff4 fs0 fc0 sc0 ls1 ws0">an output distr ibution dened bythevector</div><div class="t m0 x36 h2 y1a ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x2 h2 y1b ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x37 h2 y1a ff4 fs0 fc0 sc0 ls6 ws0">suchthatthe probabilityofemittingsymbol</div><div class="t m0 x38 h2 y1a ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x39 h2 y1a ff4 fs0 fc0 sc0 ls0 ws0">when weare</div><div class="t m0 x3 h2 y1c ff4 fs0 fc0 sc0 ls1 ws0">in state</div><div class="t m0 x3a h2 y1c ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x23 h2 y1d ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x3b h2 y1c ff4 fs0 fc0 sc0 ls0 ws0">is given by</div><div class="t m0 x3c h2 y1c ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x3d h2 y1d ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x3e h2 y1c ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x3f h2 y1c ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x2b h2 y1c ff4 fs0 fc0 sc0 ls0 ws0">). Of course we require that:</div><div class="t m0 x40 h2 y1e ffa fs0 fc0 sc0 ls0 ws0">X</div><div class="t m0 x41 h2 y1f ff6 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x42 h2 y1f ffb fs0 fc0 sc0 ls0 ws0">2A</div><div class="t m0 x36 h2 y20 ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x43 h2 y21 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x44 h2 y20 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x37 h2 y20 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x45 h2 y20 ff4 fs0 fc0 sc0 ls2c ws0">)=1</div><div class="t m0 x46 h2 y20 ff7 fs0 fc0 sc0 ls0 ws0">8</div><div class="t m0 x10 h2 y20 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x47 h2 y21 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x48 h2 y20 ff7 fs0 fc0 sc0 ls2d ws0">2S</div><div class="t m0 x3 h2 y22 ff4 fs0 fc0 sc0 ls1 ws0">There i s also a matrix</div><div class="t m0 x3c h2 y22 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x49 h2 y22 ff4 fs0 fc0 sc0 ls0 ws0">of trans istion probabilities dened so that</div><div class="t m0 x4a h2 y22 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x4b h2 y23 ff6 fs0 fc0 sc0 ls4 ws0">jk</div><div class="t m0 x4c h2 y22 ff4 fs0 fc0 sc0 lsc ws0">is the probabilityofmovingintostate</div><div class="t m0 x3 h2 y24 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x4d h2 y25 ff6 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x4e h2 y24 ff4 fs0 fc0 sc0 ls0 ws0">if themodel is currently in state</div><div class="t m0 x4f h2 y24 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x50 h2 y25 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x51 h2 y24 ff4 fs0 fc0 sc0 ls0 ws0">. Notethatrows of</div><div class="t m0 x52 h2 y24 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x53 h2 y24 ff4 fs0 fc0 sc0 ls0 ws0">must sumtounity(although columns may not)</div><div class="t m0 x3 h2 y26 ff4 fs0 fc0 sc0 ls1 ws0">andalsothatthe diagonal elementsof</div><div class="t m0 x54 h2 y26 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x40 h2 y26 ff4 fs0 fc0 sc0 ls0 ws0">need not be zero { we allow self transitions.</div><div class="t m0 x3 h2 y27 ff4 fs0 fc0 sc0 ls0 ws0">In order to eliminatethenee d tostore the distribution of startingstates separately,wemakeuseofthe special</div><div class="t m0 x3 h2 y28 ff4 fs0 fc0 sc0 ls1 ws0">state</div><div class="t m0 x16 h2 y28 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x17 h2 y29 ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x55 h2 y28 ff4 fs0 fc0 sc0 ls0 ws0">. Themodel always startsinthis state, andnever returns there. Hence theentire rst column of</div><div class="t m0 x56 h2 y28 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x3 h2 y2a ff4 fs0 fc0 sc0 ls3 ws0">is lled with zeros, andthe rst rowof</div><div class="t m0 x57 h2 y2a ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x58 h2 y2a ff4 fs0 fc0 sc0 ls1 ws0">is just the distribution over thestartingstates. Thatis,</div><div class="t m0 x59 h2 y2a ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x5a h2 y2b ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x5b h2 y2b ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x5c h2 y2a ff4 fs0 fc0 sc0 lsc ws0">is the</div><div class="t m0 x3 h2 y2c ff4 fs0 fc0 sc0 ls0 ws0">probabilitythatthemodel will start in the\real"state</div><div class="t m0 x5d h2 y2c ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x5e h2 y2d ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x5f h2 y2c ff4 fs0 fc0 sc0 ls0 ws0">. Also, no symbolisoutputwhen wedepart from</div><div class="t m0 x3 h2 y2e ff4 fs0 fc0 sc0 ls0 ws0">this state; hence</div><div class="t m0 x60 h2 y2e ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x61 h2 y2f ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x29 h2 y2e ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x2a h2 y2e ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x62 h2 y2e ff4 fs0 fc0 sc0 ls0 ws0">) is 1 for</div><div class="t m0 x63 h2 y2e ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x64 h2 y2e ff4 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 x65 h2 y2e ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x51 h2 y2f ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x66 h2 y2e ff4 fs0 fc0 sc0 ls0 ws0">andis0otherwis e. All this just makes it easier to incorp ortae the</div><div class="t m0 x3 h2 y30 ff4 fs0 fc0 sc0 ls1 ws0">startingstateprobabilities directly intotheworkings of themodel withouthavingtostore them separately</div><div class="t m0 x3 h2 y31 ff4 fs0 fc0 sc0 ls1 ws0">and do a sp ecial start-up step when werunthemodel.</div><div class="t m0 x3 h2 y32 ff4 fs0 fc0 sc0 ls0 ws0">Formally,then, weoperatethemodel as follows. Denotethecurrentstateby</div><div class="t m0 x20 h2 y32 ff5 fs0 fc0 sc0 ls0 ws0">x</div><div class="t m0 x21 h2 y32 ff4 fs0 fc0 sc0 ls0 ws0">. Set</div><div class="t m0 x67 h2 y32 ff5 fs0 fc0 sc0 ls0 ws0">x</div><div class="t m0 x68 h2 y32 ff4 fs0 fc0 sc0 ls10 ws0">=0. Loopuntil x is</div><div class="t m0 x3 h2 y33 ff4 fs0 fc0 sc0 ls0 ws0">theendstateoruntil timeruns out:</div><div class="t m0 x69 h2 y33 ff7 fs0 fc0 sc0 ls0 ws0">f</div><div class="t m0 x6a h2 y33 ff4 fs0 fc0 sc0 ls0 ws0">Generate a symbol</div><div class="t m0 xe h2 y33 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x10 h2 y33 ff4 fs0 fc0 sc0 ls1 ws0">accordingto probabilities</div><div class="t m0 x6b h2 y33 ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x6c h2 y34 ff6 fs0 fc0 sc0 ls0 ws0">x</div><div class="t m0 x6d h2 y33 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x6e h2 y33 ff5 fs0 fc0 sc0 ls0 ws0">a</div><div class="t m0 x7 h2 y33 ff4 fs0 fc0 sc0 ls0 ws0">). Pickthenext</div><div class="t m0 x3 h2 y35 ff4 fs0 fc0 sc0 ls1 ws0">state</div><div class="t m0 x16 h2 y35 ff5 fs0 fc0 sc0 ls0 ws0">y</div><div class="t m0 x6f h2 y35 ff4 fs0 fc0 sc0 ls0 ws0">accoringto probabilities</div><div class="t m0 x70 h2 y35 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x71 h2 y36 ff6 fs0 fc0 sc0 ls0 ws0">xy</div><div class="t m0 x4f h2 y35 ff4 fs0 fc0 sc0 ls0 ws0">. Set x=y.</div><div class="t m0 xa h2 y35 ff7 fs0 fc0 sc0 ls0 ws0">g</div><div class="t m0 x72 h2 y35 ff4 fs0 fc0 sc0 ls0 ws0">.</div><div class="t m0 x1f h2 y37 ff4 fs0 fc0 sc0 ls0 ws0">1</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div></body></html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://csdnimg.cn/release/download_crawler_static/1436597/bg2.jpg"><div class="t m0 x3 h2 y38 ff3 fs0 fc0 sc0 ls0 ws0">2 Using many mo dels to do recognition</div><div class="t m0 x3 h2 y39 ff4 fs0 fc0 sc0 ls0 ws0">Nowwe will examinehowtouseseveral HMMs in conjunction to p erform a classication or recognition task.</div><div class="t m0 x3 h2 y3a ff4 fs0 fc0 sc0 ls0 ws0">Consider: given a large number of sequence s each of whichhave b een labelled as b elongingto exactly one</div><div class="t m0 x3 h2 y3b ff4 fs0 fc0 sc0 ls1 ws0">of several clas se s, how can we construct a system that tells us to which class an arbitrary new sequqnce</div><div class="t m0 x3 h2 y3c ff4 fs0 fc0 sc0 ls0 ws0">(previously uns een) b elongs. In other words, how can weusetheexamplesofthevarious class es to extract</div><div class="t m0 x3 h2 y3d ff4 fs0 fc0 sc0 ls0 ws0">salientfeatures of tho se clas se s whichwethen makeuseofduring recognition.</div><div class="t m0 x3 h2 y3e ff4 fs0 fc0 sc0 ls0 ws0">Hidden Markov mo dels can be applied to this problem as follows: Us e all of the s equences labelled as</div><div class="t m0 x3 h2 y3f ff4 fs0 fc0 sc0 lsc ws0">belongingtoclass</div><div class="t m0 x73 h2 y3f ff5 fs0 fc0 sc0 ls0 ws0">C</div><div class="t m0 x74 h2 y3f ff4 fs0 fc0 sc0 ls0 ws0">to train a generativeHMM for class</div><div class="t m0 x75 h2 y3f ff5 fs0 fc0 sc0 ls0 ws0">C</div><div class="t m0 x76 h2 y3f ff4 fs0 fc0 sc0 ls0 ws0">. Do this for each clas s, so thatwenowhaveas</div><div class="t m0 x3 h2 y40 ff4 fs0 fc0 sc0 ls0 ws0">manyHMMsasclasses. Nowgiven an arbitrary sequence, onethingwe could do would b e toletallofthe</div><div class="t m0 x3 h2 y41 ff4 fs0 fc0 sc0 ls0 ws0">HMMs runfreelyforsomelong per iod of time, obs ervingthe sequence s that they produced, and then ask</div><div class="t m0 x3 h2 y42 ff4 fs0 fc0 sc0 ls1 ws0">which one pro duced our arbitrary s equence the greatest number of times. The class for which this HMM</div><div class="t m0 x3 h2 y43 ff4 fs0 fc0 sc0 ls0 ws0">was themodel would b e the class intowhichwe classie d the arbitrary s equence. Conceptually thisisne,</div><div class="t m0 x3 h2 y44 ff4 fs0 fc0 sc0 ls0 ws0">however in practice this i s usually unreali stic because it would take forever to get go od e stimates. Wewould</div><div class="t m0 x3 h2 y45 ff4 fs0 fc0 sc0 ls0 ws0">likesomeway to answer the classication que stion withouthavingtorunallourmodels explicitly and observe</div><div class="t m0 x3 h2 y46 ff4 fs0 fc0 sc0 ls0 ws0">them for long p eriods of time. Theanswer is to computethe</div><div class="t m0 x10 h2 y46 ff9 fs0 fc0 sc0 ls0 ws0">likelihood</div><div class="t m0 x2e h2 y46 ff4 fs0 fc0 sc0 ls0 ws0">thateachmodel has of generatingthe</div><div class="t m0 x3 h2 y47 ff4 fs0 fc0 sc0 ls0 ws0">given s equence. andpicktheclasswhos e model has the largest computed likelihood. Wenowshowhowto</div><div class="t m0 x3 h2 y48 ff4 fs0 fc0 sc0 ls0 ws0">do this computation eciently.</div><div class="t m0 x3 h2 y49 ff4 fs0 fc0 sc0 ls0 ws0">Consider some s equence of symbols</div><div class="t m0 x77 h2 y49 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x78 h2 y49 ff4 fs0 fc0 sc0 ls3 ws0">whichis</div><div class="t m0 x72 h2 y49 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x79 h2 y49 ff4 fs0 fc0 sc0 ls0 ws0">timesteps long:</div><div class="t m0 x7a h2 y4a ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x44 h2 y4a ff4 fs0 fc0 sc0 ls0 ws0">:</div><div class="t m0 x7b h2 y4a ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x7c h2 y4b ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x31 h2 y4a ff5 fs0 fc0 sc0 ls1e ws0">;</div><div class="t m0 x7d h2 y4b ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x7e h2 y4a ff5 fs0 fc0 sc0 ls1e ws0">;:::;</div><div class="t m0 x7f h2 y4b ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x3 h2 y4c ff4 fs0 fc0 sc0 ls1 ws0">There are many p ossible state tra jectories that could havecause d this s equence; wewishtond all of them</div><div class="t m0 x3 h2 y4d ff4 fs0 fc0 sc0 ls1 ws0">and add up all the ir probabilities. Denotethe s et of state tra jectorie s which could po ssibly havecaused</div><div class="t m0 x80 h2 y4d ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x3 h2 y4e ff4 fs0 fc0 sc0 ls0 ws0">by</div><div class="t m0 x4e h2 y4e ff5 fs0 fc0 sc0 ls0 ws0">I</div><div class="t m0 x81 h2 y4e ff4 fs0 fc0 sc0 ls0 ws0">:</div><div class="t m0 x82 h2 y4e ff7 fs0 fc0 sc0 ls0 ws0">f</div><div class="t m0 x6f h2 y4e ff5 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x3a h2 y4f ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x23 h2 y4e ff5 fs0 fc0 sc0 ls27 ws0">;i</div><div class="t m0 x3b h2 y4f ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x83 h2 y4e ff5 fs0 fc0 sc0 ls1e ws0">;:::;i</div><div class="t m0 x84 h2 y4f ff6 fs0 fc0 sc0 ls0 ws0">Q</div><div class="t m0 x85 h2 y4e ff7 fs0 fc0 sc0 ls0 ws0">g</div><div class="t m0 x86 h2 y4e ff4 fs0 fc0 sc0 ls0 ws0">. Here, each element</div><div class="t m0 x42 h2 y4e ff5 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x87 h2 y4e ff4 fs0 fc0 sc0 ls2 ws0">of</div><div class="t m0 x88 h2 y4e ff5 fs0 fc0 sc0 ls0 ws0">I</div><div class="t m0 x89 h2 y4e ff4 fs0 fc0 sc0 lsc ws0">is a state tra jectory</div><div class="t m0 x4b h2 y4e ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x13 h2 y4e ff4 fs0 fc0 sc0 ls6 ws0">states long which repre sentsthestates</div><div class="t m0 x3 h2 y50 ff4 fs0 fc0 sc0 ls0 ws0">the system vi sited (in order) while producingthe symbol s equence</div><div class="t m0 x8a h2 y50 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x8b h2 y50 ff4 fs0 fc0 sc0 ls0 ws0">. Thestatevisited atanytime</div><div class="t m0 x8c h2 y50 ff5 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 x8d h2 y50 ff4 fs0 fc0 sc0 ls0 ws0">in a</div><div class="t m0 x3 h2 y51 ff4 fs0 fc0 sc0 ls0 ws0">tra jectory</div><div class="t m0 x8e h2 y51 ff5 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x8f h2 y51 ff4 fs0 fc0 sc0 lsc ws0">is denoted by</div><div class="t m0 x90 h2 y51 ff5 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x2b h2 y51 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x91 h2 y51 ff5 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 x92 h2 y51 ff4 fs0 fc0 sc0 ls0 ws0">). Nowdenethelikelihood that a particular mo del</div><div class="t m0 x93 h2 y51 ff5 fs0 fc0 sc0 ls0 ws0">M</div><div class="t m0 x94 h2 y51 ff4 fs0 fc0 sc0 ls0 ws0">cause d the sequence</div><div class="t m0 x95 h2 y51 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x96 h2 y51 ff4 fs0 fc0 sc0 ls0 ws0">:</div><div class="t m0 x97 h2 y52 ff5 fs0 fc0 sc0 ls0 ws0">L</div><div class="t m0 x98 h2 y53 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x99 h2 y52 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x69 h2 y52 ff5 fs0 fc0 sc0 ls0 ws0">M</div><div class="t m0 x57 h2 y52 ff4 fs0 fc0 sc0 ls2c ws0">)=</div><div class="t m0 x9 h2 y52 ff5 fs0 fc0 sc0 ls48 ws0">Prob</div><div class="t m0 x37 h2 y52 ff4 fs0 fc0 sc0 ls0 ws0">[</div><div class="t m0 x79 h2 y52 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x9a h2 y54 ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x9b h2 y52 ff5 fs0 fc0 sc0 ls49 ws0">;</div><div class="t m0 x9c h2 y54 ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 xc h2 y52 ff5 fs0 fc0 sc0 ls1e ws0">;:::;</div><div class="t m0 x9d h2 y54 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x48 h2 y52 ff7 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x19 h2 y52 ff5 fs0 fc0 sc0 ls3 ws0">model M</div><div class="t m0 x9e h2 y52 ff4 fs0 fc0 sc0 ls0 ws0">]</div><div class="t m0 x3d h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 x9f h2 y56 ffa fs0 fc0 sc0 ls0 ws0">X</div><div class="t m0 xa0 h2 y57 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 xa1 h2 y57 ffb fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x2c h2 y57 ff6 fs0 fc0 sc0 ls0 ws0">I</div><div class="t m0 xa2 h2 y55 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 xa3 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 xa4 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 xa5 h2 y58 ff8 fs0 fc0 sc0 ls1 ws0">(1)</div><div class="t m0 xa6 h2 y55 ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 xa7 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x51 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">(1)</div><div class="t m0 xa8 h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xa9 h2 y55 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xaa h2 y59 ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x9 h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 xab h2 y55 ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 x88 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x43 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">(1)</div><div class="t m0 x7b h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x45 h2 y58 ff8 fs0 fc0 sc0 ls3 ws0">(2)</div><div class="t m0 xac h2 y55 ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 x9c h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 xad h2 y58 ff8 fs0 fc0 sc0 ls3 ws0">(2)</div><div class="t m0 x5e h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x52 h2 y55 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xae h2 y59 ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x53 h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x9d h2 y55 ff5 fs0 fc0 sc0 ls27 ws0">:::T</div><div class="t m0 xaf h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb0 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x1b h2 y58 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x8a h2 y58 ffb fs0 fc0 sc0 ls0 ws0">,</div><div class="t m0 x8b h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">1)</div><div class="t m0 xb1 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb2 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xb3 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x9e h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 xb4 h2 y55 ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 xb5 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 xb6 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xb7 h2 y58 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xb8 h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x21 h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xb9 h2 y55 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xba h2 y59 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xbb h2 y55 ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x3 h2 y5a ff4 fs0 fc0 sc0 ls0 ws0">This s eems like it i s goingto be an extremely hard f actorial computation, requir ing</div><div class="t m0 xbc h2 y5a ff5 fs0 fc0 sc0 ls0 ws0">O</div><div class="t m0 xbd h2 y5a ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x68 h2 y5a ff5 fs0 fc0 sc0 ls4a ws0">N</div><div class="t m0 x6 h2 y5b ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xbe h2 y5a ff4 fs0 fc0 sc0 ls1d ws0">)multiplies and</div><div class="t m0 x3 h2 y5c ff5 fs0 fc0 sc0 ls0 ws0">O</div><div class="t m0 xbf h2 y5c ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xc0 h2 y5c ff5 fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 xc1 h2 y5d ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xc2 h2 y5c ff4 fs0 fc0 sc0 ls0 ws0">) additions, not includingthe (non-trivial) amountofwork require d to computewhich s equences should</div><div class="t m0 x3 h2 y5e ff4 fs0 fc0 sc0 ls0 ws0">be in theset</div><div class="t m0 xc3 h2 y5e ff5 fs0 fc0 sc0 ls0 ws0">I</div><div class="t m0 xc4 h2 y5e ff4 fs0 fc0 sc0 ls0 ws0">. The exp onential natureofthis co st would make computingmanysuch likelihoods prohibitive,</div><div class="t m0 x3 h2 y5f ff4 fs0 fc0 sc0 ls1 ws0">andthus s everly limit the practicalityof using HMMs as recognizers. Luckily,however, there is an excellent</div><div class="t m0 x3 h2 y60 ff4 fs0 fc0 sc0 ls1 ws0">trick(due or iginally to?) whichgreatly save s on thecostofworkingthi s out:</div><div class="t m0 x3 h2 y61 ff4 fs0 fc0 sc0 ls0 ws0">Dene</div><div class="t m0 xc5 h2 y61 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xc6 h2 y62 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xc7 h2 y61 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xc8 h2 y61 ff5 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 xc9 h2 y61 ff4 fs0 fc0 sc0 ls2b ws0">)astheincremental probabilites of havingreached state</div><div class="t m0 xca h2 y61 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 xcb h2 y62 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x14 h2 y61 ff4 fs0 fc0 sc0 ls0 ws0">attime</div><div class="t m0 xcc h2 y61 ff5 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 x22 h2 y61 ff4 fs0 fc0 sc0 ls0 ws0">having emitted thecorrect</div><div class="t m0 x3 h2 y63 ff4 fs0 fc0 sc0 ls0 ws0">symbols up till then (including</div><div class="t m0 xcd h2 y63 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xa4 h2 y64 ff6 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 x97 h2 y63 ff4 fs0 fc0 sc0 ls3 ws0">):</div><div class="t m0 xce h2 y65 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xcf h2 y66 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xcf h2 y67 ff6 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 xd0 h2 y65 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xd1 h2 y65 ff5 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xa3 h2 y65 ff4 fs0 fc0 sc0 ls2c ws0">)=</div><div class="t m0 xa6 h2 y65 ff5 fs0 fc0 sc0 ls4c ws0">Prob</div><div class="t m0 x41 h2 y65 ff4 fs0 fc0 sc0 ls0 ws0">[</div><div class="t m0 xa9 h2 y65 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xaa h2 y68 ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x9 h2 y65 ff5 fs0 fc0 sc0 ls1e ws0">;</div><div class="t m0 x88 h2 y68 ff8 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 xd2 h2 y65 ff5 fs0 fc0 sc0 ls1e ws0">;:::;</div><div class="t m0 x1f h2 y68 ff6 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 xd3 h2 y65 ff4 fs0 fc0 sc0 ls0 ws0">andstateattime</div><div class="t m0 xd4 h2 y65 ff5 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 xd5 h2 y65 ff4 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 x20 h2 y65 ff5 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 xd6 h2 y68 ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xd7 h2 y65 ff4 fs0 fc0 sc0 ls0 ws0">]</div><div class="t m0 x3 h2 y69 ff4 fs0 fc0 sc0 ls0 ws0">Nowinduction comes to our re scue:</div><div class="t m0 xd8 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xd9 h2 y6b ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xd9 h2 y6c ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 xda h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x90 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xdb h2 y6a ff4 fs0 fc0 sc0 ls34 ws0">)=</div><div class="t m0 xa3 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 xdc h2 y6d ff8 fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x71 h2 y6d ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xdd h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 xde h2 y6d ff6 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xa7 h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x78 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x57 h2 y6d ff8 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x41 h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 xdf h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">; </div><div class="t m0 xe0 h2 y6b ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xe0 h2 y6c ff6 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 xe1 h2 y6c ff8 fs0 fc0 sc0 ls0 ws0">+1</div><div class="t m0 xe2 h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xb h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x9c h2 y6a ff4 fs0 fc0 sc0 ls2c ws0">)=</div><div class="t m0 x52 h2 y6e ffa fs0 fc0 sc0 ls0 ws0">0</div><div class="t m0 x52 h2 y6f ffa fs0 fc0 sc0 ls0 ws0">@</div><div class="t m0 xe3 h2 y70 ffa fs0 fc0 sc0 ls0 ws0">X</div><div class="t m0 x76 h2 y71 ff6 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x10 h2 y72 ffc fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 x47 h2 y71 ffb fs0 fc0 sc0 ls0 ws0">2S</div><div class="t m0 xe4 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xe5 h2 y6b ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xe5 h2 y6c ff6 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 x1b h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x4b h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">j</div><div class="t m0 xe6 h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x13 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">T</div><div class="t m0 xe7 h2 y6d ff6 fs0 fc0 sc0 ls4 ws0">jk</div><div class="t m0 x2f h2 y6e ffa fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x2f h2 y6f ffa fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 xd5 h2 y6a ff5 fs0 fc0 sc0 ls0 ws0">A</div><div class="t m0 xb7 h2 y6d ff6 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 xb8 h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xcc h2 y6a ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xe8 h2 y6d ff6 fs0 fc0 sc0 ls0 ws0">t</div><div class="t m0 x93 h2 y6d ff8 fs0 fc0 sc0 ls2 ws0">+1</div><div class="t m0 xe9 h2 y6a ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x3 h2 y73 ff4 fs0 fc0 sc0 ls1 ws0">Whichenables us to e asily computethedesired likelihood</div><div class="t m0 x5e h2 y73 ff5 fs0 fc0 sc0 ls0 ws0">L</div><div class="t m0 xe h2 y74 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xf h2 y73 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x10 h2 y73 ff5 fs0 fc0 sc0 ls0 ws0">M</div><div class="t m0 x48 h2 y73 ff4 fs0 fc0 sc0 ls3 ws0">) since weknowwemust endinsomepossible</div><div class="t m0 x3 h2 y75 ff4 fs0 fc0 sc0 ls1 ws0">state:</div><div class="t m0 x9 h2 y76 ff5 fs0 fc0 sc0 ls0 ws0">L</div><div class="t m0 xea h2 y77 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xeb h2 y76 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x72 h2 y76 ff5 fs0 fc0 sc0 ls0 ws0">M</div><div class="t m0 x45 h2 y76 ff4 fs0 fc0 sc0 ls2c ws0">)=</div><div class="t m0 xec h2 y78 ffa fs0 fc0 sc0 ls0 ws0">X</div><div class="t m0 x7d h2 y79 ff6 fs0 fc0 sc0 ls0 ws0">s</div><div class="t m0 x7e h2 y7a ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 xed h2 y79 ffb fs0 fc0 sc0 ls0 ws0">2S</div><div class="t m0 xe h2 y76 ff5 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x76 h2 y77 ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x76 h2 y7b ff6 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x7f h2 y76 ff4 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xee h2 y76 ff5 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x48 h2 y76 ff4 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x1f h2 y7c ff4 fs0 fc0 sc0 ls0 ws0">2</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>