本篇文章我們來(lái)解決，在給定模型和觀測(cè)序列的情況下，求出最可能出現(xiàn)的對(duì)應(yīng)的隱狀態(tài)序列。
HMM模型的解碼問(wèn)題最常用的算法是維特比算法，接下來(lái)我們將利用維特比算法來(lái)解決上述問(wèn)題。
1、維特比算法概述
維特比算法是一個(gè)通用的解碼算法，是基于動(dòng)態(tài)規(guī)劃的求序列最短路徑的方法，既然是動(dòng)態(tài)規(guī)劃算法，那么久需要找到合適的局部狀態(tài)，以及局部狀態(tài)的遞推公式。在HMM中，維特比算法定義了兩個(gè)局部狀態(tài)用于遞推。
第一個(gè)局部狀態(tài)是在時(shí)刻t隱藏狀態(tài)為i所有可能的狀態(tài)轉(zhuǎn)移路徑i1,i2,...it中的概率最大值。記為δt(i):
由δt(i)的定義可以得到δ的遞推表達(dá)式：
第二個(gè)局部狀態(tài)由第一個(gè)局部狀態(tài)遞推得到。我們定義在時(shí)刻t隱藏狀態(tài)為i的所有單個(gè)狀態(tài)轉(zhuǎn)移路徑(i1,i2,...,it?1,i)中概率最大的轉(zhuǎn)移路徑中第t?1個(gè)節(jié)點(diǎn)的隱藏狀態(tài)為Ψt(i)（表示該隱狀態(tài)）,其遞推表達(dá)式可以表示為：
有了這兩個(gè)局部狀態(tài)，我們就可以從時(shí)刻0一直遞推到時(shí)刻T，然后利用Ψt(i)記錄的前一個(gè)最可能的狀態(tài)節(jié)點(diǎn)回溯，直到找到最優(yōu)的隱藏狀態(tài)序列。
2、維特比算法流程總結(jié)
輸入：HMM模型λ=(A,B,Π)，觀測(cè)序列O=(o1,o2,...oT)
輸出：最有可能的隱藏狀態(tài)序列I?={i?1,i?2,...i?T}
-
進(jìn)行動(dòng)態(tài)規(guī)劃遞推時(shí)刻t=2,3,...T時(shí)刻的局部狀態(tài)：
-
計(jì)算時(shí)刻T最大的δT(i),即為最可能隱藏狀態(tài)序列出現(xiàn)的概率。計(jì)算時(shí)刻T最大的Ψt(i),即為時(shí)刻T最可能的隱藏狀態(tài)。
-
利用局部狀態(tài)Ψ(i)開(kāi)始回溯。對(duì)于t=T?1,T?2,...,1：
最終得到最有可能的隱藏狀態(tài)序列I?={i?1,i?2,...i?T}
3、HMM維特比算法求解實(shí)例
我們的觀察集合是:
V={紅，白}，M=2
我們的狀態(tài)集合是：
={盒子1，盒子2，盒子3}，N=3
而觀察序列和狀態(tài)序列的長(zhǎng)度為3.
初始狀態(tài)分布為：
狀態(tài)轉(zhuǎn)移概率分布矩陣為：
球的顏色的觀測(cè)序列:
O={紅，白，紅}
按照我們上一節(jié)的維特比算法，首先需要得到三個(gè)隱藏狀態(tài)在時(shí)刻1時(shí)對(duì)應(yīng)的各自兩個(gè)局部狀態(tài)，此時(shí)觀測(cè)狀態(tài)為1：
t=1時(shí)刻
現(xiàn)在開(kāi)始遞推三個(gè)隱藏狀態(tài)在時(shí)刻2時(shí)對(duì)應(yīng)的各自兩個(gè)局部狀態(tài)，此時(shí)觀測(cè)狀態(tài)為2：
t=2時(shí)刻
繼續(xù)遞推三個(gè)隱藏狀態(tài)在時(shí)刻3時(shí)對(duì)應(yīng)的各自兩個(gè)局部狀態(tài)，此時(shí)觀測(cè)狀態(tài)為1：
t=3時(shí)刻
現(xiàn)在得到最后的時(shí)刻，開(kāi)始準(zhǔn)備回溯。
t=3:
最大概率為δ3(3),從而得到i?3 = 3，
t=2:
最大概率為δ2(3),從而得到i?2 = 3，
t=1:
最大概率為δ1(3),從而得到i?1 = 3，
最終得到的狀態(tài)序列為（3,3,3）
