一、viterbi算法的用途

在自然语言的工程实践中，viterbi算法常常被用来寻找最可能的隐藏状态序列。如，序列标注任务就需要用到viterbi算法。

二、viterbi求最优路径

李航老师《统计机器学习》有如下例题：

用viterbi算法解决上述例题的推理过程如下：

三、viterbi算法的实现

#!/usr/bin/python3
# -*- coding:utf-8 -*-"""
@Author  : heyw
@Time    : 2020/1/30 16:22
@Software: PyCharm
@File    : viterbi.py
"""
import  numpy as npdef viterbi(invisible, transition_prob, emission_prob, pi, obs_seq):# 转换为numpy形式transition_prob=np.array(transition_prob)emission_prob=np.array(emission_prob)pi=np.array(pi)# 计算路径矩阵的行数和列数row_num = np.array(transition_prob).shape[0]col_num = len(obs_seq)# 定义路径矩path_matrix = np.zeros((row_num,col_num))# 定义回溯矩阵back_matrix = np.zeros((row_num,col_num))# 初始状态path_matrix[:,0]=pi*np.transpose(emission_prob[:,obs_seq[0]])for t in range(1,col_num):list_max=[]for j in range(row_num):list_a = list(np.array(path_matrix[:,t-1]) * np.transpose(transition_prob[:,j]))list_max.append(max(list_a))back_matrix[j,t] = np.argmax(list_a)path_matrix[:,t] = np.array(list_max) * np.transpose(emission_prob[:,obs_seq[t]])def decode():back_path = []# 回溯隐藏序列末尾结点back_path.append(np.argmax(path_matrix[:, t]))# 依次回溯其他结点for idx in range(col_num - 1, 0, -1):back_path.append(int(back_matrix[back_path[-1], idx]))# 隐藏序列逆序back_path.reverse()# 隐藏序列映射back_path = [invisible[id] for id in back_path]return back_pathhidden_seq = decode()return hidden_seqif __name__=='__main__':# 隐藏状态种类invisible = {0:'A1',  # 盒子A11:'A2',  # 盒子A22:'A3'   # 盒子A3}# 初始状态pi = [0.2, 0.4, 0.4]# 转移矩阵transition_prob = [[0.5, 0.2, 0.3],[0.3, 0.5, 0.2],[0.2, 0.3, 0.5]]# 发射矩阵emission_prob = [[0.5, 0.5],[0.4, 0.6],[0.7, 0.3]]# 观察序列obs_seq = [0 ,1, 0]# 计算隐藏序列hidden_seq = viterbi(invisible, transition_prob, emission_prob, pi, obs_seq)print("隐藏序列：", hidden_seq)

隐藏序列： ['A3', 'A3', 'A3']