【Viterbi算法】HMM前向、后向及维特比算法的Python实现

代码

• • 条件
  • 前向
  • 后向
  • 结果
  • 维特比viterbi算法

在课程里面学到，但是PPT不见了，所有就懒得写那么多文字，代码可供参考.例子大概就是4个盒子，两种球（红和白），观察的结果O={红 红 白 白 红}

条件

import numpy as np
from numpy import *
A=np.array([[0,1,0,0],[0.4,0,0.6,0],[0,0.4,0,0.6],[0,0,0.5,0.5]])
B=np.array([[0.5,0.5],[0.3,0.7],[0.6,0.4],[0.8,0.2]])
pai=np.array([0.25,0.25,0.25,0.25])
Q=['box1','box2','box3','box4']
V=["red","white"]O=[0,0,1,1,0]

前向

代码片.

#前向算法
def HMM_forward():   #抽到的球的颜色序列O=(红，红，白，白, 红)o=np.array([0,0,1,1,0])# 初始化T=len(o)#B的维数，即盒子数量Box_Num=shape(B)[0]#建立alpha矩阵alpha=np.zeros(T*Box_Num).reshape(Box_Num,T)#时刻1是红色，隐藏状态是1、2、3、4的概率for i in range(Box_Num):alpha[i][0]=pai[i]*B[i][o[0]]# 迭代3次，每次填充一个时刻的alpha[i]sigma=0for j in range(T-1):for i in range(Box_Num):for k in range(Box_Num):#时刻j+2到达状态o[j+1]全概率sigma+=alpha[k][j]*A[k][i]#盒子i,时刻j+2（时刻2，3，4）的概率alpha[i][j+1]=sigma*B[i][o[j+1]]sigma=0# 终止#对最外层[]内最大的块做块与块的运算，同时去掉最外层[]Pro=np.sum(alpha,axis=0)print("α矩阵：")print(alpha)#观测为O=(红，红，白，白)的概率print("观测为O=(红，红，白，白，红)的概率是 %.8f "%Pro[T-1])

后向

#后向算法
def HMM_backward():#抽到的球的颜色序列O=(白，白，红，红)o=np.array([0,0,1,1,0])# 初始化T=len(o)Box_Num=shape(B)[0]#建立beta矩阵beta=np.zeros(T*Box_Num).reshape(Box_Num,T)#时刻4各个隐藏状态后向概率都为1for i in range(Box_Num):beta[i][0]=1# 迭代3次，每次填充一个时刻的beta[i]sigma=0t=Tfor j in range(T-1):t -= 1for i in range(Box_Num):for k in range(Box_Num):sigma+=A[i][k]*B[k][o[t]]*beta[k][j]beta[i][(j+1)]=sigmasigma=0print("β矩阵：")print(beta)# 终止sigma=0for i in range(Box_Num):sigma+=pai[i]*B[i][o[0]]*beta[i][T-1]#观测为O=(白，白，红，红)的概率print("观测为O=(红，白，白，红，红)的概率是 %.8f "%sigma)

结果

print("盒子对应状态集合Q={盒子1，盒子2，盒子3，盒子4}")
print("观测集合V={红，白}")
print("状态转移概率分布A:","\n",A)
print("观测概率分布B:","\n",B)
print("初始概率分布Π:","\n",pai)
print("(1)前向算法")
HMM_forward()
print("(2)后向算法")
HMM_backward()

维特比viterbi算法

maxxb=[] #存φ，b-->δ
for i in range(len(O)):if i==0:b=pai*B.T[0]#t=1时刻概率print(b)else:maxxb.append(np.argmax(b*A.T,axis=1)) #返回最大值下标,axis=1每行最大,axis=0每列最大b=np.max(b*A.T,axis=1)*B.T[O[i]]   #迭代取最大值print(b)print(np.argmax(b*A.T,axis=1)+1)#print(list(maxxb))        
path=[]#最优路径it=np.argmax(b,axis=0)#最优路径的“终点”
path.append(it)
print(it)
for i in range(len(maxxb)):#最优路径回溯it=maxxb[len(maxxb)-i-1][it]print(it)path.append(it)path.reverse()#把顺序调整一下，因为存的时候是倒着存储的   
print(path)

Author

007rbq

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！