统计学习方法|维特比算法的python实现动态规划|统计学习方法

这里写自定义目录标题

隐马尔可夫模型

预测算法

维特比解码算法

【统计学习方法|维特比算法的python实现】
隐马尔可夫模型预测算法维特比解码算法
在隐马尔科夫模型中，我们使用维特比解码算法求得概率的最大路径（最优路径）。
依据的方法为动态规划。
而动态规划又满足最优化原理：给出一个最优的决策序列，每个子序列自身必须是最优的决策序列。下面则为整个过程的符号引入与递推公式：

文章图片

下面为数理统计方法中关于维特比算法的例题：

文章图片

下面则为维特比解码算法的python代码实现:

import numpy as np def vitebi_decode(hmm_paramter, obs_idx_seq): #取出HMM模型的三个参数 A, B , L = hmm_paramter #状态的总个数 N = A.shape[0] #获取观测序列的长度 T = len(obs_idx_seq)#定义[N*T]的矩阵P，用来表示t时刻状态为i的最大概率 P = np.zeros((N, T)) #定义[N*T]的矩阵D，用来表示t时刻状态为i取得最大概率时t-1时刻的状态 D = np.zeros((N, T), dtype=int) #初始化P,D在t=0时刻所对应的概率值和初状态 for i in range(N): P[i][0] = L[i] * (B[i, obs_idx_seq[0]]) D[i][0] = -1#接下来通过一个三层循环对P,D里面的元素进行赋值操作 for i in range(1, T): obs_value = https://www.it610.com/article/obs_idx_seq[i] for j in range(N): pro_list = [] for k in range(N): pro_list.append(P[k, i-1] * A[k, j] * B[j, obs_value]) max_value = max(pro_list) max_idx = pro_list.index(max_value) P[j, i] = max_value D[j, i] = max_idx#获取P最后一个时刻的最大值，即为最大概率 final_max_value = np.max(P, axis=0)[-1] final_max_idx =np.argmax(P, axis=0)[-1]#通过finax_max_idx和D倒推出最大概率值所对应的状态序列 state_list = [] state_list.append(final_max_idx) for i in range(T-1, 0, -1): final_max_idx = D[final_max_idx][i] state_list.append(final_max_idx) final_state_list = [] #由于状态是从1开始的，所以要对每一个状态索引加1 for i in range(len(state_list) - 1, -1, -1): final_state_list.append(state_list[i]+1) #print(P) #print(D) return final_max_value, final_state_list if __name__ =="__main__": A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]]) B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]]) L = [0.2, 0.4, 0.4] O = ['红', '白', '红'] obs_to_idx = {'红':0, '白':1} obs_seq_idx = [obs_to_idx[i] for i in O] max_pro, state_seq = vitebi_decode((A, B, L), obs_seq_idx) print(max_pro) print(state_seq)

运行结果如下：