HMM解码问题
给定一个观察序列O=O1O2...OT,和模型μ=（A,B,π），如何快速有效地选择在一定意义下“最优”的状态序列Q=q1q2...qT，使该状态最好地解释观察序列。
一种想法是求出每个状态的概率rt(i)最大(rt(i)=P(qt=si,O|μ）)，记q't(i)=argQmax(rt(i))，但是这样做，忽略了状态之间的关系，很可能两个状态之间的概率为0，即aq't(i)q't+1(i)=0,这样求得的“最优”状态序列是不合法的。
为防止状态之间转移概率为0（断续问题），换一种思路，不是求单个状态求得最大值，而是求得整个状态序列最大值，即求
Q'= argQmaxP(Q|O,μ）
此时用维特比算法，先定义下维特比变量δt(i):在时间t，HMM沿着一条路径到达状态si，并输出观察序列O=O1O2...Ot的最大概率:
δt(i)=max P(q1q2...qt=si,O1O2...Ot|μ)
t t+1
上图中，对于从t时刻三个到 t+1时刻的状态1，到底取状态1,2还是3，不是看单独状态1,2还是3的概率，而是看在状态1,2,3各自的维特比变量值乘以相应的状态转换概率，从中选出最大值，假设2时最大，那么记下t+1时刻状态1之前的路径是t时刻的状态2，以此类推。
δt(i)的递归关系式: δt+1(i)=maxj δt(j)*aji*bi(Ot+1),为了记忆路径，定义路径变量ψt(i)，记录该路径上的状态si的前一个状态。
维特比算法
step1 初始化：
δt(i) = πi*bi(O1), 1≤i≤N
ψt(i) = 0
step2 归纳计算：
δt(i)=max1≤j≤N δt-1(j)*aji*bi(Ot),2≤t≤T;1≤i≤N
记忆路径 ψt(i) = arg [max1≤j≤Nδt-1(j)*aji*bi(Ot)]
step3 终结:
QT' = arg max1≤i≤N [δT(i)]
P'(QT') = max1≤i≤N [δT(i)]
step4 路径回溯:
qt'=ψt+1(qt+1') , t=T-1,T-2...1
时间复杂度
计算某时刻的某个状态的前向变量需要比较前一时刻的N个状态，此时时间复杂度为O(N),每个时刻有N个状态，此时时间复杂度为N*O(N)=O(N2),又有T个时刻，所以时间复杂度为T*O(N2)=O(N2T)。
程序例证
step1 初始化：δ1(1) = 0.2*0.5=0.1 ，δ1(2) = 0.4*0.4=0.16， δ1(3) = 0.4*0.7=0.21
step2 归纳计算：δ2(1) =max[0.1*0.5,0.16*0.3,0.21*0.2]*0.6
...
step3 终结：最佳路径是δ4(1)δ4(2)δ4(3)最大的一个对应的状态
step4 回溯：从最后一个状态往回返
程序代码
#include#include #include int main(){ float a[3][3] = { {0.5,0.2,0.3},{0.3,0.5,0.2},{0.2,0.3,0.5}}; float b[3][2] = { {0.5,0.5},{0.4,0.6},{0.7,0.3}}; float result[4][3]; int list[4] = {0,1,0,1}; int max[4][3]; float tmp; //step1:Initialization result[0][0] = 0.2*0.5; result[0][1] = 0.4*0.4; result[0][2] = 0.4*0.7; int i,j,k, count = 1, max_node; float max_v; //step2:归纳运算 for (i=1; i<=3; i++) { for(j=0; j<=2; j++) { tmp = result[i-1][0] * a[0][j] * b[j][list[count]]; max[i][j] = 0; for(k=1; k<=2; k++) { if(result[i-1][k] * a[k][j] * b[j][list[count]] > tmp) { tmp = result[i-1][k] * a[k][j]* b[j][list[count]]; max[i][j] = k; } result[i][j] = tmp; } max_v = result[3][0]; max_node = 0; for (k=1; k<=2; k++) { if(result[3][k] > max_v) { max_v = result[3][k]; max_node = k; } } } count += 1; } //step3:终结 for (i=0; i<=3; i++) { for(j=0; j<=2; j++) { printf("%d %d %f\n",i+1,j+1,result[i][j]); } } printf("Pmax=%f\n", max_v); printf("step4:%d \n", max_node+1); //step4:回溯 for(k=3; k>=1; k--) { printf("step%d:%d \n",k, max[k][max_node]+1); max_node = max[k][max_node]; } return 0; }
运行结果
最终的序列是3 2 2 2