命名实体识别学习-从基础算法开始-维特比算法

Posted on

命名实体识别学习-从基础算法开始（01）-维特比算法

[TOC]

代码地址：https://github.com/SStarLib/NERfromBasic

Day1: 维特比算法

HMM的小例子

从一个小例子开始实现维特比算法：

例子来自知乎一个答案对维特比算法和HMM的讲解：

如何通俗地讲解 viterbi 算法？ - Kiwee的回答 - 知乎
https://www.zhihu.com/question/20136144/answer/239971177

大致介绍下这个例子：

题目背景

从前有个村儿，村里的人的身体情况只有两种可能：健康或者发烧。
假设这个村儿的人没有体温计或者百度这种神奇东西，他唯一判断他身体情况的途径就是到村头我的偶像金正月的小诊所询问。
月儿通过询问村民的感觉，判断她的病情，再假设村民只会回答正常、头晕或冷。
有一天村里奥巴驴就去月儿那去询问了。
第一天她告诉月儿她感觉正常。
第二天她告诉月儿感觉有点冷。
第三天她告诉月儿感觉有点头晕。
那么问题来了，月儿如何根据阿驴的描述的情况，推断出这三天中阿驴的一个身体状态呢?

将问题抽象为一个HMM

从问题中过可以看出，{健康，发烧}对应隐马尔可夫模型中的状态序列，{正常，冷，头晕}，则对应观察序列。（本例子其实不严谨，冷，头晕这两个观察现象是可以同时存在的，不过本例中假设其不同时存在）

问题要求：推断出这三天中阿驴的一个身体状态

问题本质：解码这三天的状态序列。

模型参数：状态转移概率矩阵，状态-观察概率分布矩阵，初始状态

  • 初始状态：月儿预判的阿驴身体状态的概率分布 = { 健康：0.6 , 发烧： 0.4 }

  • 状态转移概率矩阵： {
    健康->健康： 0.7 ,
    健康->发烧： 0.3 ,
    发烧->健康：0.4 ,
    发烧->发烧： 0.6
    }

  • 状态-观察概率分布矩阵：{
    健康，正常：0.5 ，冷 ：0.4 ，头晕： 0.1 ；
    发烧，正常：0.1 ，冷 ：0.3 ，头晕： 0.6
    }

    image-20200622160308608

有了模型参数。就可以构建模型并用维特比算法进行解码了即预测三天的身体状态。

Python实现维特比算法

为了方便后面学习，使用Pytorch框架（其实numpy应该更简单些）

手算维特比过程：

image-20200622155623835

伪代码：

维特比算法的伪代码（来自宗成庆老师的ppt）：

image-20200622161813184

代码前期准备

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def main():
    states = [ "健康", "发烧"]
    observations = ["正常","冷", "头晕"]
    tran_matrix = torch.Tensor([[0.7, 0.3], [0.4, 0.6]]) #A_ij
    emit_matrix = torch.Tensor([[0.5, 0.4, 0.1], [0.1, 0.3, 0.6]])
    init_state = [0.6, 0.4]
    observation_seq = ["正常","冷", "头晕"]
    viterbi = Viterbi(toIdx(states), toIdx(observations), tran_matrix, emit_matrix)
    maxpro, path = viterbi.viterbi(init_state, observation_seq)
    print("最大概率为：{}".format(maxpro))
    print("最大概率下路径为：")
    pt = ""
    for i in path:
        pt += states[i] + "->"
    print(pt)
main()

将模型主要参数：有状态空间，观察空间，状态转移概率矩阵，状态-观察概率分布矩阵（发射矩阵），初始状态

输入：观察序列（代码里也将初始状态作为了输入了）

1
2
3
4
5
6
7
class Viterbi:
    def __init__(self,s_to_idx, v_to_idx, tran_matrix, emit_matrix):
        self.s_to_idx = s_to_idx
        self.v_to_idx = v_to_idx
        self.tran_matrix = torch.Tensor(tran_matrix).transpose(0,1)
        self.emit_matrix = torch.Tensor(emit_matrix).transpose(0,1)
        self.state_size = len(s_to_idx)

维特比算法本质是动态规划算法，具有最优子结构，需要确定初始量，和递推关系。

小数的乘法计算会导致数越来越小，所以代码在对数空间上进行计算

第一步计算初始维特比变量：

1
2
3
4
5
6
7
8
9
10
11
12
# 在对数空间初始化维特比变量
      res = []
      init_state=torch.Tensor(init_state)
      for i, s in enumerate(init_state):
          v = self.v_to_idx[v_seq[0]]
          tmp = torch.log(s)+torch.log(self.emit_matrix[v][i])
          res.append(tmp)

      del init_state
      init_vvars = torch.stack(res)

      forward_var = init_vvars

第二步 迭代计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for v in v_seq[1:]:
    bptrs_t =[]
    viterbivars_t = []
    v_index = self.v_to_idx[v]
    for s in range(self.state_size):
        next_tag_var = forward_var+torch.log(self.tran_matrix[s])
        best_tag_id = argmax(next_tag_var)
        bptrs_t.append(best_tag_id)
        viterbivars_t.append(next_tag_var[best_tag_id])
    forward_var = (torch.Tensor(viterbivars_t)+torch.log(self.emit_matrix[v_index]))
    backpointers.append(bptrs_t)
# 终结
terminal_var = forward_var
best_tag_id = argmax(terminal_var)
path_score = terminal_var[best_tag_id]

回溯解码：

1
2
3
4
5
6
7
8
# 回溯解码
      best_path = [best_tag_id]
      for bptrs_t in reversed(backpointers):
          best_tag_id = bptrs_t[best_tag_id]
          best_path.append(best_tag_id)

      best_path.reverse()
      return torch.exp(path_score), best_path

结果：

1
2
3
最大概率为：0.015120003372430801
最大概率下路径为：
健康->健康->发烧->

结果和手算的一致

总结

维特比算法本质就是动态规划代码。使用pytorch基本都是向量的运算。涉及到分数的连乘除最好转为对数的加减