1緒論I隱馬爾可夫模型的三個(gè)基本問題及其算法的理論框架分析綜述目錄TOC\o"1-3"\h\u12668隱馬爾可夫模型的三個(gè)基本問題及其算法的理論框架分析綜述 112143（一）隱馬爾可夫模型 162731.馬爾可夫模型 143442.隱馬爾可夫模型 114145（二）隱馬爾可夫模型的三個(gè)基本問題及其算法 3218321.隱馬爾可夫模型的三個(gè)基本問題 3186222.隱馬爾可夫模型的基本算法 3隱馬爾可夫模型馬爾可夫模型一個(gè)離散的隨機(jī)過程{St,t∈N}P即預(yù)測(cè)馬爾可夫鏈的下一個(gè)狀態(tài)出現(xiàn)的概率只與上一個(gè)狀態(tài)有關(guān)，而與前面其他所有的狀態(tài)都無關(guān)。例如，本文做股票預(yù)測(cè)所用到的股票數(shù)據(jù)就是一個(gè)馬爾可夫鏈。其中，一個(gè)股票每一天的走勢(shì)都是一個(gè)結(jié)點(diǎn)，而每一天的狀態(tài)可以分為上漲、下跌、持平（或者分的更細(xì)：小漲、小跌）等，每一個(gè)狀態(tài)之間以一定的概率進(jìn)行轉(zhuǎn)換（例如，第一天股票的狀態(tài)為上漲，那么第二天股票的狀態(tài)有70%的可能是上漲，20%的可能會(huì)下跌，還有10%的可能會(huì)持平。預(yù)測(cè)第二天股票走勢(shì)的概率只與第一天有關(guān)。），連續(xù)若干天的該支股票的走勢(shì)情況就形成了一個(gè)馬爾可夫鏈。上漲上漲上漲持平上漲下跌…圖SEQ圖\*ARABIC1股票走勢(shì)馬爾可夫鏈隱馬爾可夫模型一個(gè)雙離散的隨機(jī)過程{St,t∈N}，{P其中{St,t∈N}觀測(cè)序列的結(jié)點(diǎn)狀態(tài)是可以直接獲取的，而隱藏序列的結(jié)點(diǎn)狀態(tài)是無法直接獲取不可見的，需要通過觀測(cè)序列的狀態(tài)來推測(cè)。例如，在預(yù)測(cè)股票的走勢(shì)情況時(shí)，我們所能觀測(cè)到的數(shù)據(jù)有開盤價(jià)、收盤價(jià)、最高價(jià)和最低價(jià)等等，通過所觀測(cè)到的數(shù)據(jù)來預(yù)測(cè)隱藏序列的狀態(tài)（上漲、下跌、持平等等），則實(shí)際的股票走勢(shì)可能如REF_Ref72436542\h圖2所示：上漲上漲持平上漲下跌…開盤價(jià)等等數(shù)據(jù)開盤價(jià)等等數(shù)據(jù)開盤價(jià)等等數(shù)據(jù)開盤價(jià)等等數(shù)據(jù)…觀測(cè)序列隱藏序列圖SEQ圖\*ARABIC2股票走勢(shì)隱馬爾可夫過程其中，在t時(shí)刻通過隱藏序列得到它所對(duì)應(yīng)的觀測(cè)序列狀態(tài)的概率稱之為輸出概率。在t時(shí)刻隱藏狀態(tài)為上漲，t+1時(shí)刻隱藏狀態(tài)為持平，那么隱藏狀態(tài)從t時(shí)刻的上漲轉(zhuǎn)換成t+1時(shí)刻持平的概率稱之為轉(zhuǎn)換概率。本文所用到的符號(hào)變量如REF_Ref72436554\h表1所示：表SEQ表\*ARABIC1隱馬爾可夫模型各變量說明符號(hào)說明符號(hào)描述含義s隱藏狀態(tài)由st構(gòu)成了隱藏狀態(tài)序列o觀測(cè)狀態(tài)由ot構(gòu)成了觀測(cè)狀態(tài)序列α前向概率前向算法求出的概率β后向概率后向算法求出的概率v初始概率表示t=1時(shí)刻下處于初始狀態(tài)的概率，由vi構(gòu)成的矩陣稱為初始概率矩陣a狀態(tài)轉(zhuǎn)移概率表示在t時(shí)刻處于qi的狀態(tài)，在t+1時(shí)刻變成狀態(tài)qj的概率。由ab輸出概率表示在t時(shí)刻處于qi的狀態(tài)，在t+1時(shí)刻變成狀態(tài)gi的概率。由bτ模型參數(shù)由(A,B,V)構(gòu)成Q所有可能的隱含狀態(tài)的集合Q={G所有可能的觀測(cè)序列集合G={N隱含狀態(tài)個(gè)數(shù)M相應(yīng)的可能觀測(cè)數(shù)隱馬爾可夫模型的三個(gè)基本問題及其算法隱馬爾可夫模型的三個(gè)基本問題問題一：概率問題已知模型的所有參數(shù)，求任意一個(gè)觀測(cè)序列發(fā)生的概率。常用算法為前向-后向算法。問題二：學(xué)習(xí)問題求能使觀測(cè)序列發(fā)生概率最大的參數(shù)。常用算法為：EM算法和Baum-Welch算法。問題三：預(yù)測(cè)問題已知所有模型參數(shù)，并且已知某一條觀測(cè)序列，求該觀測(cè)序列狀態(tài)所一一對(duì)應(yīng)的隱藏狀態(tài)序列。常用算法為Viterbi算法。隱馬爾可夫模型的三個(gè)基本問題不僅能各自解決各自的問題，它們還能組合起來解決實(shí)際問題。例如，已知一系列的觀測(cè)序列，求其中一個(gè)觀測(cè)序列發(fā)生的概率。這個(gè)時(shí)候就需要將問題一與問題二結(jié)合一起使用。先通過學(xué)習(xí)問題的算法求出模型參數(shù)，再根據(jù)所得到模型參數(shù)利用概率問題的算法求觀測(cè)序列發(fā)生的概率。隱馬爾可夫模型的基本算法前向算法 αtk=P(o1,o2第一步，計(jì)算t?1時(shí)刻定義的前向概率： α1k=Po1,s1第二步，構(gòu)建遞推公式： αt+1k=j=1Nαt(j)第三步，遞推終止后，計(jì)算觀測(cè)序列的概率： POτ=k=1NPO,s通過上述的公式描述，可以將前向算法的步驟總結(jié)為：首先通過初始概率讀取所有隱藏狀態(tài)中第一列的全部所有可能狀態(tài)的前向概率值，然后根據(jù)上述概率值計(jì)算第二列全部所有可能狀態(tài)的前向概率值，以此類推直至最后一列，最終計(jì)算出這個(gè)過程中產(chǎn)生的所有路徑的概率值，并對(duì)它們進(jìn)行求和就得到了其中一個(gè)觀測(cè)序列所發(fā)生的概率。后向算法 βtk=P(ot+1,ot+2第一步，計(jì)算t=T時(shí)刻的后向概率： βTk=1 (SEQ公式\*ARABIC6)第二步，構(gòu)建遞推公式： βtk=i=1Nβt+1(j)第三步，遞推終止后，計(jì)算觀測(cè)序列概率： P k=1NPOs1=qk通過上述的公式描述，可以將后向算法的步驟總結(jié)為：首先計(jì)算出所有隱藏序列中最后一個(gè)結(jié)點(diǎn)所有可能狀態(tài)的后向概率值（設(shè)該時(shí)刻為t時(shí)刻），然后根據(jù)上述后向概率值計(jì)算t-1時(shí)刻所有隱藏序列中全部可能狀態(tài)的后向概率值，以此類推直至第一列，最終計(jì)算出這個(gè)過程中產(chǎn)生的所有路徑的概率值，并對(duì)它們進(jìn)行求和就得到了其中一個(gè)觀測(cè)序列所發(fā)生的概率。EM算法首先計(jì)算出觀測(cè)數(shù)據(jù)有關(guān)于模型參數(shù)τ的對(duì)數(shù)似然函數(shù)： Lτ=logPOτ=logQPO,S，即L L =logIPO|S,τPOτ?由Jensen不等式 lognanxn≥na可得： L ?logPO|τn=SPI|O,τ令： w IPS|O,τnPOτlog則： Lτ≥wτ,τn (SEQ公式\*ARABIC當(dāng)τ=τ Lτ=wτn,τn 由公式（23）可知當(dāng)wτ,τn增大時(shí)，Lτ也會(huì)隨之增大。所以可以通過使 τarg=arg ?IPS|O,τnPOτ去掉對(duì)于參數(shù)τ而言是常數(shù)的項(xiàng)，可得： τn+1=argmaxτ(SPS|O,定義R函數(shù)為： Rτ,τn=SPS|O,τ即： τn+1=argmaxτRτ,τn求出R函數(shù)后，對(duì)其極大化。EM算法就是通過不斷求解wτn,Baum-Welch算法Baum-Welch算法是本文求模型參數(shù)所使用的算法。Baum-Welch算法的結(jié)構(gòu)總體流程為：首先，最大化觀測(cè)狀態(tài)鏈的前向概率和后向概率，然后隨機(jī)定義一套模型的參數(shù)（V：初始概率矩陣，A：轉(zhuǎn)換概率矩陣，B：觀測(cè)概率矩陣），通過不斷重復(fù)的迭代，迭代過程為：先用隨機(jī)定義一套模型的參數(shù)V,A,B計(jì)算出前向概率α和后向概率β，再用計(jì)算得出的前向概率α和后向概率β不斷對(duì)模型參數(shù)V,A,B進(jìn)行更新。一直重復(fù)以上步驟，直到找到最佳的模型參數(shù)。通過EM算法可得R函數(shù)： Rτ,τ=SPS|O,τn其中τ是隱馬爾可夫模型當(dāng)前參數(shù)的估計(jì)值。聯(lián)合概率為： PO,Sτ=vi1bi代入公式可得： RI I(t=1TlogbiT(Baum-Welch算法就是通過極大化Rτ,τ來求參數(shù)Viterbi算法定義在t時(shí)刻觀測(cè)序列為O=o1,o2,o δtk=maxi1,i由定義可知： δt+1j=(max?[kδtk所以概率最大的序列中第t?1個(gè)狀態(tài)為： φtk=argmax?[1≤j≤Nδt?1j用維特比算法得到最優(yōu)狀態(tài)序列的步驟如下所示：初始值： δ1k=vkbko φ1k=0,k=1,2,…,N (SEQ公式\*ARABIC27)