隱馬爾可夫總結

1、HMM隱馬爾可夫Hidden Markov Model、馬爾可夫過程Markov Process1、馬爾可夫過程介紹馬爾可夫過程(Markov Process)，它因俄羅斯數(shù)學家安德烈馬爾可夫而得名，代表數(shù)學中具有馬爾可夫性質 的離散隨機過程。該過程中，每個狀態(tài)的轉移只依賴于之前的 n個狀 態(tài)，這個過程被稱為1個n階的模型，其中n是影響轉移狀態(tài)的數(shù)目。 最簡單的馬爾科夫過 程就是一階過程，每一個狀態(tài)的轉移只依賴于其之前的那一個狀態(tài)。馬爾可夫鏈是隨機變量 Xi,，Xn的一個數(shù)列。這些變量的范圍，即他們所有可能取 值的集合，被稱為"狀態(tài)空間，而Xn的值那么是在時間n的狀態(tài)。如果 Xn+1

2、對于過去狀態(tài) 的條件概率分布僅是 X n的一個函數(shù)，那么P(X=XXX = PX = xX |這里x為過程中的某個狀態(tài)。上面這個恒等式可以被看作是馬爾可夫性質。2、馬爾可夫過程舉例以下列圖展示了天氣這個例子中所有可能的一階轉移:注意一個含有N個狀態(tài)的一階過程有 N2個狀態(tài)轉移。每一個轉移的概率叫做狀態(tài)轉移概率(state transition probability)，即從一個狀態(tài)轉移到另一個狀態(tài)的概率。這所有的N2個概率可以用一個狀態(tài)轉移矩陣來表示，其表示形式如下：A a * * *> 口2 ¥«««*. *.*«I *¥ V

3、 #«aNaN2 aNj - - d.W% 二尸(q二j|q- = i) 1 £U j§N對該矩陣有如下約束條件:F面就是海藻例子的狀態(tài)轉移矩陣:Todtresun cloud rainsun'0.50 0.375 0.125Yesierdm cloud0.25 0.125 0.625rain0.25 0375 0375這個矩陣表示，如果昨天是晴天，那么今天有50%的可能是晴天，37.5%的概率是陰天,12.5%的概率會下雨，很明顯，矩陣中每一行的和都是1。為了初始化這樣一個系統(tǒng)，我們需要一個 初始的概率向量Sun10OoudRain0.00.0這個向量表

4、示第一天是晴天。3、一階馬爾可夫過程定義如上述馬爾可夫過程例子可知，我們?yōu)橐浑A馬爾可夫過程定義了以下三個局部: 狀態(tài)：晴天、陰天和下雨；初始向量：定義系統(tǒng)在時間為 0的時候的狀態(tài)的概率； 狀態(tài)轉移矩陣：每種天氣轉換的概率；所有的能被這樣描述的系統(tǒng)都是一個馬爾可夫過程。、隱馬爾可夫過程HMM1、隱馬爾可夫模型介紹隱馬爾可夫模型(HMM)是一個輸出符號序列統(tǒng)計模型，具有T個狀態(tài)Xi,X2.Xt-i,它按一定的周期從一個狀態(tài)轉移到另一個狀態(tài)，每次轉移時，輸出一個符號觀測值。轉移到哪一個狀態(tài)，轉移時輸出什么符號， 分別由狀態(tài)轉移概率和轉移時輸出概率來決定。因為只能觀測到輸出符號的序列，而不能觀測到狀態(tài)

5、轉移序列即模型的觀測序列是通過哪個狀 態(tài)路徑是不知道的所以稱為隱馬爾可夫模型。2、隱馬爾可夫過程舉例下面是一個簡單的例子。 氣象學上，可通過年輪的寬窄了解各年的氣候狀況， 利用年輪 上的信息可推測出幾千年來的氣候變遷情況。 年輪寬表示那年光照充足， 風調雨順；假設年 輪較窄，那么表示那年溫度低、雨量少，氣候惡劣。為了簡單起見，我們只考慮冷(code)，熱hot兩種溫度。根據(jù)現(xiàn)代的氣象知識可以知道，“冷的一年跟著下一年為熱的概率為，為冷的概率為；“熱的一年跟著下一年為熱的概率為，為冷的概率為?？梢院唵蔚臍w納為下 面規(guī)律：HCH'0.7(13C0.40,6我們將樹的年輪簡單分為小 smal

6、l,中middle,大large三種，或者分別寫成 S,M丄。根 據(jù)現(xiàn)代的氣象知識可以知道，熱的一年樹木年輪為“小，“中，“大的概率分別為；冷的一年樹木年輪為“小，“中，“大的概率分別為。因此，冷 C，熱H對年輪的影響可以 簡單歸納為下面規(guī)律：SMLHr0.1040.5'C070.201*在這個系統(tǒng)中，狀態(tài)序列是每年的溫度 H或者C。因為下一年的溫度只與上一年有關，所以從一個狀態(tài)溫度轉移到下一個狀態(tài)溫度可以看成是一個一階Markov process因為無法觀測過去的溫度，狀態(tài)序列也被稱為隱藏狀態(tài)。盡管我們不能觀測過去的狀態(tài)溫度序列，但是可以通過樹的年輪給我們提供的信息預測溫度。我們的目

7、標就是充分利用可觀測的年輪序列，來預測那些年的溫度序列情況Markov過程。從上面規(guī)律可以得到，狀態(tài)轉移矩陣A:0A 0.6混淆矩陣(confusion matrix)B:0.104 0.5B -Hot和Cold天氣的概率0/7 0.2 0,1假設初始狀態(tài)矩陣n ,如本例中是初始狀態(tài)矩陣是最開始產(chǎn)生0.41這樣可以得到天氣與樹年輪的概率圖模型Markov process:Observations:圖中最開始產(chǎn)生 Hot天氣的概率為由初始狀態(tài)矩陣PI決定，Hot天氣產(chǎn)生樹年輪Small的概率為，Hot狀態(tài)產(chǎn)生Hot狀態(tài)的概率為，接著 Hot產(chǎn)生Middle的概率為以此類 推。因此可以得到隱藏天氣

8、序列HHCC產(chǎn)生樹木年輪序列為 SMSL的概率。P(HHCC) = 0.6*0.1*07*0.4*0.3*0.7 *0.6*0.1 = 0.000212使用這種方法我們就可以計算產(chǎn)生 SMSL序列存在的所有天氣序列的概率。stateprobabilityIIHHH.000412HHHC000035HHCH.000706HHCC1)00212HCHH.000050HCHC.000004HCCH.000302HCCC.000091CHHH,001098CHHC.000094CHCH.001882CHCC000564CCHH.00047()CCHC.000040CCCH.002822cccc.000

9、847比擬可得P(CCCH)的概率為，是最大的。結論:假設樹木年輪序列為 SMSL，那么最可能狀態(tài)序列 Markov process是CCCH ；產(chǎn)生樹木年輪序列為 SMSL的概率為0.009629 所有可能相加3、HMM 的三個重要假設我們假設隱藏以下列圖顯示了天氣的例子中隱藏的狀態(tài)和可以觀察到的狀態(tài)之間的關系。 的狀態(tài)是一個簡單的一階馬爾可夫過程，并且他們兩兩之間都可以相互轉換。OBSERVABLE STATESHIDDEN STATES對HMM 來說，有如下三個重要假設，盡管這些假設是不現(xiàn)實的。 假設1:馬爾可夫假設狀態(tài)構成一階馬爾可夫鏈P(不|心.占)十(兀丄假設2：不動性假設狀態(tài)與具

10、體時間無關二 P(兀+J 兀)，Vz； j 假設3：輸出獨立性假設輸出僅與當前狀態(tài)有關P(Q,二屮(°工)4、HMM的根本元素一個HMM 可用一個5元組 N, M, n, A, B 表示，其中：N表示隱藏狀態(tài)的數(shù)量，我們要么知道確切的值，要么猜想該值；M表示可觀測狀態(tài)的數(shù)量，可以通過訓練集獲得；n = n i為初始狀態(tài)概率；A=aj為隱藏狀態(tài)的轉移矩陣Pr(xt(i) | xt-i(j)B=bik表示某個時刻因隱藏狀態(tài)而導致可觀察狀態(tài)的概率，即混淆矩陣，Pr(ot(i) | xt(j)。在狀態(tài)轉移矩陣和混淆矩陣中的每個概率都是時間無關的，即當系統(tǒng)演化時，這些矩陣并不隨時間改變。對于一

11、個N和M固定的HMM來說，用入= n , A, B 表示HMM參數(shù)。三、HMM的三個根本問題1、問題1識別問題1.1問題描述給定模型入= n , A, B 和觀測序列0=0。, 01,Oi，如何快速有效的找到P(O|入)?解釋：假設我們已經(jīng)有一個特定的隱馬爾科夫模型入和一個可觀察狀態(tài)序列集。我們也許想知道在所有可能的隱藏狀態(tài)序列下，給定的可觀察狀態(tài)序列的概率。問題1可以歸納為：兄二4加oOf)吋4 T卜尸0|兄舉例：如小節(jié)的例子中，模型入，觀測序列0=SMSL，求產(chǎn)生SMSL年輪序列的概率。1.2解決方案蠻力算法設X二仗“百x口為一個狀態(tài)序列口通過定義B,可以推出：P0 X, A=bIc0Jb

12、Ii01.bXr_i0IjJ通過定義A和;r可以推出：PX |凡二開屮如盤工円-由by貂定理可推出：P0, X| 兄二P0 X, APX| a.因此可以得到辛尸O|Z=PO,X|Zx= PO|XT 2PX|lx=2Z b電0。0 Jb與-0巧_】X珀f內礙i孔“也s假設用圖表示可以得到如下：血恤 Process: J > Aq " 、A； %： > X2> XT_r紜0)W以(6)f'ffVObeervitons;0&0:O.O口其中：兔旳=表示在i時刻狀態(tài)、轉移到下一個時刻j狀態(tài)&的概率 bj0斗=表示在ti時刻狀態(tài)衍J產(chǎn)生輸出觀測0斗的概

13、率然而，這種直接的計算的方法蠻力算法一般是不可行的，實際情況中，我們不可能知 道每一種可能的路徑，而且這種計算的計算量也是十分驚人的，到達大約數(shù)量級。如，當HMM的狀態(tài)數(shù)為5,觀測序列長度為100時，計算量到達，是完全無法接受的。因此需要 更有效的算法，這就是 Baum等人提出的前向-后向算法。前向算法(a-pass )前向算法即按輸出觀察值序列的時間，從前向后遞推計算輸出概率。 首先說明以下符號的定義：i=L2.?r-i觀測蘆列時刻直i=0JT2.V-l 隱藏狀態(tài)序列下標值 0二斑0心T鐮出的觀測符號宇PO|2) 給定模圭兒 輸出符號宇列O的概率從狀態(tài)XJX；的轉移概率J1J山(0)從狀態(tài)片

14、產(chǎn)生輸出符號q的低率ar(i)輸出局部脣號序列為qo,井且到達狀態(tài)X；的概率，|即甫T向槪率|由上面的符號的定義，那么 at(i)可由下面遞推公式計算得到：I初始化厲二也(0,其中i=0丄2-V 12*遞推公式a.(i)= £ J葉i.(0.)?其中2,T-l;丄V-ly-i3.最后結果：P(01 A) = Va71(i).H)解釋：每一市始狀石進備一不數(shù)垂丟量£1表示輸出局部符號序列為勺，并且到達狀態(tài)Xj的概率，*Q2)根癮時劃的輸出符號入計算af(i)：其H 糾表示舸出苯分苻專芋列為 g“q：并且到達狀態(tài)、的隹率 jCj)表示輸出局部符號序列為盹,巧.“；亠并且到達狀態(tài)

15、x)的董寧 送：寒示i時刻的隱疲狀態(tài)二I =1時刻3) 當2T-咐轅到2),否那么轅到執(zhí)行4) °4) 把這時的所有可能的終了狀態(tài)a_(i)取出.即P(0|2) = f冬應)i=C使用這種前向遞推計算算法的計算量大為減少，復雜度變?yōu)閚2t。同樣的1中例子,N=5,T=100時，只需要大約 2500次乘法。1.2.3 后向算法(3 -pass)與前向算法類似，向后算法即使按輸出觀察序列的時間，從后面向前遞推計算輸出概率的方法。首先說明以下符號的定義：2。丄觀訓宇列時刻值件丄V-1隱黴狀態(tài)序列下標直O(jiān)=°防込戶卜輸出的觀測符號序P(O|z)沿克嘆型兒輯出符號甲列O的嘅率af從狀

16、態(tài)XMX的蛭移祗孚b(q)從狀態(tài)X產(chǎn)生輸出符號q的強率A0)輸出局部符號序列為弘并且到達狀態(tài)爼的麻勒即前向櫃率由遞推公式可得:初始化 爲二=L其中i = 0丄匕.仝-1(2)追強公弍氏=£卯勺(0,)件,)rr其豐t = r-工一30i二0丄丄：X-1V-1最后絶果P(0| A) = 2/?c (i)b/O0)i"0解釋:1)繪每一個初始狀態(tài)總備一個數(shù)組艾量0m(i) = l：表示狀譽到達X廣未輸出死I宇列的嘅率n甲來0一)0“(2)根據(jù)計算幾(i)陽)二養(yǎng)也(0丿3久()表示輸出芋分符虧宇列為q fOq。5并且到達狀態(tài)X.的區(qū)率 0：(i)表示輸出卻分符號宇列為。日:。&

17、#169;：并且到達狀態(tài)兀的蒞率當t豐0時轉到(2),否那么轉到Q) o 把所有可能的狀態(tài)0°(i)取出.即2、問題2解碼問題2.1問題描述給定模型入= n , A, B 和觀測序列0=0o, Oi,Oi，找到最優(yōu)的隱藏狀態(tài)序列？ 解釋：根據(jù)可觀察狀態(tài)的序列找到一個最可能的隱藏狀態(tài)序列。問題2可以歸納為:0 = (Og, ±0.0丁_)舉例：如小節(jié)的例子中，模型入，觀測序列 0=SMSL，求最有可能產(chǎn)生 SMSL 序列的狀態(tài)序列 CCCH。2.2解決方案蠻力算法如中計算每一條可能狀態(tài)序列的概率，然后比擬找出其中概率最大的一條就為我們需要的狀態(tài)序列X。如開始的例1中就是采用這

18、種算法。 這種算法雖然易理解，但是計算開銷太大，一般不可取。2前向后向算法在中我們詳細的討論了前向算法以及后向算法，而前向后向算法就是綜合這兩種算法。 可以用來解決尋找最可能隱藏狀態(tài)序列X的問題。首先我們說明以下符號的定義：乳表示輸出觀測字列QQ且狀態(tài)到達X的櫃率AW表示輪出觀測宇列Jor_:且狀態(tài)到達x的概宰P(O|z)表示給定模型幾 輸出觀測字列Q,。"的砸宦人(i)表示輸出觀測字列且t時刻q是工聲主的砸室J f P(01 A)其中臥河由前向算法求得，夙(i河由后向算法求得,P(0初也可以求得 我們可以每一個狀態(tài)沫肚訃 厲到最大的片(咯妙下標 那么表示在t時刻最可能宙產(chǎn)生的。對每

19、一個時刻都如此求，就可以得到最有可能的隱藏狀態(tài)序列X維特比(Viterbi)算法在給定了一個可觀察序列和HMM的情況下，我們可以考慮遞歸的來尋找最可能的隱藏序列。我們可以先定義一個局部概率3,即到達某個中間狀態(tài)的概率。接下來我們將討論如何計算t=1和t=n (n>1)的局部概率。注意這里的局部概率和前向算法中的局部概率是不一樣的，這里的局部概率表示的是在t時刻最可能到達某個狀態(tài)的一條路徑的概率，而不是所有概率之和。1) 局部概率和局部最優(yōu)路徑考慮下面這個圖以及可觀察序列(dry, damp, soggy)的一階轉移。U1說t*3drydampsoggy對于每一個中間狀態(tài)和終止狀態(tài)t=3都

20、有一個最可能的路徑。比方說，在t=3時刻的三個狀態(tài)都有一個如下的最可能的路徑：我們可以稱這些路徑為局部最優(yōu)路徑。這些局部最優(yōu)路徑都有一個概率， 也就是局部概 率3。和前向算法中的局部概率不一樣， 這里的概率只是一個最可能路徑的概率， 而不是所 有路徑的概率和。我們可以用 3 i, t來表示在t時刻，到狀態(tài)i的所有可能的序列路徑中概率最大 的序列的概率，局部最優(yōu)路徑就是到達這個最大概率的路徑， 對于每一個時刻的每一個狀態(tài) 都有這樣一個概率和局部最優(yōu)路徑。最后，我們通過計算 t=T時刻的每一個狀態(tài)的最大概率和局部最優(yōu)路徑，選擇其中概 率最大的狀態(tài)和它的局部最優(yōu)路徑來得到全局的最優(yōu)路徑。2計算t=1

21、時刻的局部概率當t=1時刻的時候，到達某個狀態(tài)最大可能的路徑還不存在，但是我們可以直接使用 在t=1時刻某個狀態(tài)的概率和這個狀態(tài)到可觀察序列ki的轉移概率：60 =兀叭3計算t>1時刻的局部概率接下來我們可以根據(jù) t-1時刻的局部概率來求t時刻的局部概率。0A00 IB -二* Oc 'o1 % t-1t-it我們可以計算所有到狀態(tài)X的路徑的概率，找到其中最可能的路徑，也就是局部最優(yōu)路徑。注意到這里，到達X的路徑必然會經(jīng)過 t-1時刻的A、B和C,所以我們可以利用 之前的結果。到達X的最可能的路徑就是下面三個之一：狀態(tài)序列，A , X 狀態(tài)序列，B , X 狀態(tài)序列，C, X 我

22、們需要做的就是找到以 AX、BX和CX結尾的路徑中概率最大的那個。根據(jù)一階馬爾科夫的假設，一個狀態(tài)的發(fā)生只和之前的一個狀態(tài)有關系，所以X在某個序列的最后發(fā)生的概率只依賴于其之前的一個狀態(tài)：Pr 到達A的最優(yōu)路徑 Pr X | A Pr 觀察狀態(tài)| X有個了這個公式，我們就可以利用t-1時刻的結果和狀態(tài)轉移矩陣和混淆矩陣的數(shù)據(jù)：PrXf = max BC Pr專PrX | ixTxobservationt X將上面這個表達式推廣一下，就可以得到t時刻可觀察狀態(tài)為 kt的第i個狀態(tài)的最大局部概率的計算公式：力竹怠其中aji表示從狀態(tài)j轉移到狀態(tài)i的概率，bikt表示狀態(tài)i被觀察成kt的概率。4后向

23、指針 考慮以下列圖Mt-2Mdrydam 卩soggy在每一個中間狀態(tài)和結束狀態(tài)都有一個局部最優(yōu)概率S i, t。但是我們的目的是找到最可能的隱藏狀態(tài)序列，所以我們需要一個方法去記住局部最優(yōu)路徑的每一個節(jié)點?？紤]到要計算t時刻的局部概率，我們只需要知道t-1時刻的局部概率，所以我們只需要記錄那個導致了t時刻最大局部概率的的狀態(tài)，也就是說，在任意時刻，系統(tǒng)都必須處在一個能在下一時刻產(chǎn)生最大局部概率的狀態(tài)。如以下列圖所示：我們可以利用一個后向指針 0來記錄導致某個狀態(tài)最大局部概率的前一個狀態(tài)，即0二 arg max W/%這里argmax表示能最大化后面公式的 j值，同樣可以發(fā)現(xiàn)這個公式和 t-1

24、時刻的局部 概率和轉移概率有關，因為后向指針只是為了找到“我從哪里來，這個問題和可觀察狀態(tài)沒有關系，所以這里不需要再乘上混淆矩陣因子。全局的行為如以下列圖所示：5優(yōu)點使用viterbi算法對一個可觀察狀態(tài)進行解碼有兩個重要的優(yōu)點：a通過使用遞歸來減少復雜度，這點和之前的前向算法是一樣的b可以根據(jù)可觀察序列找到最優(yōu)的隱藏序列，這個的計算公式是:i產(chǎn) arg max 丿(X(j)如)這里就是一個從左往右翻譯的過程，通過前面的翻譯結果得到后面的結果，起始點是初始向量n。6補充但在序列某個地方有噪聲干擾的時候，某些方法可能會和正確答案相差的較遠。但是 Viterbi算法會查看整個序列來決定最可能的終止

25、狀態(tài)，然后通過后向指針來找到之前的狀 態(tài)，這對忽略孤立的噪聲非常有用。Viterbi算法提供了一個根據(jù)可觀察序列計算隱藏序列的很高效的方法，它利用遞歸來 降低計算復雜度，并且使用之前全部的序列來做判斷，可以很好的容忍噪聲。在計算的過程中，這個算法計算每一個時刻每一個狀態(tài)的局部概率，并且使用一個后向指針來記錄到達當前狀態(tài)的最大可能的上一個狀態(tài)。最后，最可能的終止狀態(tài)就是隱藏序列的最后一個狀態(tài)，然后通過后向指針來查找整個序列的全部狀態(tài)。3、問題3模型訓練問題3.1問題描述實際上是一個模型參數(shù)估計問題，即對于初始模型和給定用于訓練的觀測序列0=0。,01,O1如何調整模型入= n , A, B 的參數(shù)，使得輸出概率 PO|入最大？解釋：根據(jù)觀察到的序列集來找到一個最有可能的HMM。問題3可以歸納為：求乂二匕3科使得Po久最大己知0 = 0仆0心303.2解決