课程
4.3.5 Viterbi函数分析与调试
4.3.5 Viterbi函数分析与调试
源码位置：chapter04/4.3.5/4.3.5.py:7
一、Viterbi函数代码注释
Viterbi(sentence, array_pi, array_a, array_b, STATES) 这个函数的作用，是根据输入句子和已经训练好的 HMM 参数，求出整句话最可能的一组状态标记。这里的状态一共有四种，分别是 B、M、E、S。
B 表示词的开头，M 表示词的中间，E 表示词的结尾，S 表示单字成词。
程序一开始先建立 weight 和 path 两个变量。weight 用来保存动态规划过程中的最大概率，path 用来保存到当前位置时最优的状态路径。
如果句子的第一个字没有在训练数据对应的词首发射概率中出现，程序会做一个简单处理：把这个字更偏向当作单字词，也就是让它更容易取到 S 状态。
接下来程序对第一个字做初始化。也就是把第一个字分别看成 B、M、E、S 四种状态，计算每种状态下的起始概率，并把路径先记录下来。
然后程序从第二个字开始向后遍历。对于当前字的每一种可能状态，都会去看前一个字的四种状态，比较哪一种状态转移过来之后概率最大。找到最大值之后，就把这个最大概率存到 weight[i][state0]，同时把对应的最优路径存到 new_path[state0]。
整句话处理完之后，程序会在最后一个字的四种状态中再比较一次，选出概率最大的那条路径，这条路径就是整个句子的最优标注结果。
这个程序原来还有一个报错问题。原因是文件里写了 from numpy import *，这样会把 Python 自带的 max() 覆盖掉，导致 best = max(items) 这里出错。所以调试的时候应该把它改成普通的 max(items, key=lambda x: x[0])，或者干脆删掉 from numpy import *。我这次是直接删掉了这个导入，所以程序现在可以正常运行。
二、Viterbi 算法详细执行过程分析
Viterbi 算法本质上就是在很多条可能路径里面，一层一层地保留当前概率最大的那一条路径。虽然每个位置都有 4 种状态可选，但是程序不会把所有路径都保留下来，而是只给每个状态留下“到这里为止最优的一条”。这样就把原本很复杂的穷举问题变成了动态规划问题。
- 初始化阶段
当读取句子的第一个字符 sentence[0] 时，程序要先确定它在四种状态下的初始概率。代码里用 weight[0][state] 保存这个结果，用 path[state] 保存对应的起始路径。
这一阶段做的事情很简单：先看第一个字在 B、M、E、S 四种状态下的发射概率，再把它和初始状态概率相加，得到四种起步情况，同时把路径先初始化为 [‘B’]、[‘M’]、[‘E’]、[‘S’]。
程序这里还做了一个容错处理。如果首字没有在训练集中作为词首出现过，就会把它尽量往 S 状态上靠，这样至少能保证程序继续运行，不至于直接出错。
- 动态规划递推阶段
从第二个字开始，程序就进入最核心的递推部分。假设当前处理到第 i 个字，当前字可能处于 state0 状态，那么程序会把前一个字的四种状态 state1 都检查一遍。
每次检查时，都会算这样一个值：上一时刻的最优概率 + 从 state1 转移到 state0 的概率 + 当前字在 state0 下的发射概率。
也就是说，程序会比较前一个字如果是 B、M、E、S，这四种情况分别转到当前状态时，哪一种结果最大。四种情况算完以后，程序会选出其中概率最大的那一个，把它记为当前状态 state0 的最优前驱状态。然后把这个最优结果记到 weight[i][state0] 里，再把原来的最优路径接上当前状态，更新成新的路径。
这样从前往后一层一层推下去，到句子最后一个字时，每种状态都已经对应了一条最优路径。
- 终止与回溯阶段
当整个句子都处理完以后，程序会看最后一个字如果取 B、M、E、S 四种状态时，哪一种状态对应的总概率最大。找到这个最大值以后，就直接把对应的整条路径取出来，这就是 Viterbi 算法求出来的最终状态序列。
因为在递推过程中，每一步都已经把路径保存到 path 里面了，所以这里不需要再额外从后往前手工回溯，直接取出那条最优路径就可以了。
三、个性化测试与分词结果
这次把主程序里的 test 句子改成：
成员A在[高校名称]计算机学院开发了一个小程序
修改后的测试代码如下：
if __name__ == '__main__':
pramater = json.load(open('hmm_states.txt', encoding='utf-8'))
array_A = pramater['states_matrix']
array_B = pramater['observation_matrix']
array_Pi = pramater['init_states']
STATES = ['B', 'M', 'E', 'S']
test = "成员A在[高校名称]计算机学院开发了一个小程序"
tag = Viterbi(test, array_Pi, array_A, array_B, STATES)
print("状态序列:", tag)
seg = tag_seg(test, tag)
print("分词结果:", '/ '.join(seg))实际运行结果如下：
状态序列：[‘B’, ‘E’, ‘S’, ‘S’, ‘B’, ‘E’, ‘S’, ‘B’, ‘E’, ‘B’, ‘E’, ‘S’, ‘B’, ‘E’, ‘B’, ‘E’, ‘B’, ‘E’, ‘B’, ‘E’, ‘S’, ‘S’, ‘S’, ‘S’, ‘B’, ‘E’]
分词结果：王闯/ 闯/ 在/ 河南/ 大/ 学计/ 算机/ 与/ 信息/ 工程/ 学院/ 开发/ 了/ 一/ 个/ 小/ 程序
从这个结果可以看出来，程序把“河南”“信息”“工程”“学院”“开发”“程序”这些部分切出来了，但是对“成员A”和“大学计算机学院”这样的长人名、长机构名切得不太理想。比如“成员A”被切成了“王闯/ 闯”，“大学计算机”这一段被切成了“大/ 学计/ 算机”。
这说明 HMM 分词虽然能完成基本的状态标注和分词任务，但是它比较依赖训练语料中的统计特征。对于没有在训练集中充分出现过的人名、校名和较长专有名词，模型就容易切分不准。
总的来说，这个程序的 Viterbi 函数实现思路是正确的，原来最主要的问题是 max() 被 numpy 相关导入影响，导致程序运行时报错。修正之后，就能够对新的测试句子完成状态标注和分词，只是分词效果还会受到训练语料规模和领域范围的影响。