Viterbi 算法 Python实现 [NLP学习一]
最近思考了一下未来,结合老师的意见,还是决定挑一个方向开始研究了,虽然个人更喜欢鼓捣。深思熟虑后,结合自己的兴趣点,选择了NLP方向,感觉比纯粹的人工智能、大数据之类的方向有趣多了,个人还是不适合纯粹理论研究 :)。发现图书馆一本语言处理方面的书也没有后,在京东找了一本书--《NLP汉语自然语言处理原理与实践》,到今天看了大约150页,发现还是很模糊,决定找点代码来看。
从最简单的分词开始,发现分词的库已经很多了,选择了比较轻巧的jieba来研究。看了一下GitHub的基本介绍,突然感觉:我次奥,这也不过如此嘛,来来来写一个。jieba对于词典外的词用HMM模型进行解决,用Viterbi算法实现。网上对于HMM的解释很多,我个人也不太能够通过数学公司解释,其实模型比较简单,先了解了马尔可夫模型后就能比较容易地理解隐马尔可夫模型。
这里记录一下对于HMM模型中,解决求隐藏状态链问题的Viterbi算法的学习。
在知乎问题:https://www.zhihu.com/question/20136144 中,我看了高票答案地回答,基本理解了思想,但是这个回答稍微有一点不全面,并没有强调回溯的思想,这里让我对算法产生了一点误解,后面有提到。
大约花了半天时间阅读网上各种资料后,我选了一个Python代码决定仿照写一次 (https://blog.csdn.net/youfefi/article/details/74276546)代码用了numpy数组,由于我对numpy的函数不是太熟悉,决定先用list写一遍。令我惊讶的是,由于我脑袋太笨加上当时对维特比算法不是很清晰,我没有看懂作者的代码(略显尴尬),没办法,决定先按照自己的思路写出来。写的过程中发现算法有点出奇简单,居然简单3层循环就出来了,大概40分钟写完了。不出意外,写完运行发现和网上代码结果不一致。
打断点开始调试,发现自己求出的概率矩阵是正确的,但最后路径不正确,意识到可能自己的理解有问题。再次上网查询资料。参考 https://www.2cto.com/kf/201609/544539.html 的文章,发现自己的理解是有问题的:
我的理解是依次迭代每个时刻,找到概率最大的状态即为该时刻状态,这样理解错误在于求的隐藏状态是一个链,根据马尔可夫假设,下一刻时刻的状态是依赖前一个状态的,我的理解就将状态之间割裂了,无法行成链。
正确的算法是每次迭代过程中,记录每种状态概率最大时其前驱状态,这样到最后一个时刻,选择概率最大的状态,再进行回溯。
代码如下:直接使用List、迭代过程中没有对概率进行判断,还有优化空间。
1 # state 存放隐藏序列,sunny 0 rainy 1
2 # obser 存放观测序列 0 1 2 对应 walk shop clean
3 # start_p 是初始概率,0元素对应sunny的初始概率 1元素对应rainy的概率
4 # transition_p 转移概率矩阵 2*2 行为初始状态 列为新状态
5 # emission_p 发射概率矩阵 2*3 行为隐藏状态 列为可观测状态
6
7 # 迭代过程,每次只需要记录第t个时间点 每个节点的最大概率即可,后续计算时直接使用前序节点的最大概率即可
8 def compute(obser, state, start_p, transition_p, emission_p):
9 # max_p 记录每个时间点每个状态的最大概率,i行j列,(i,j)记录第i个时间点 j隐藏状态的最大概率
10 max_p = [[0 for col in range(len(state))] for row in range(len(obser))]
11 # path 记录max_p 对应概率处的路径 i 行 j列 (i,j)记录第i个时间点 j隐藏状态最大概率的情况下 其前驱状态
12 path = [[0 for col in range(len(state))] for row in range(len(obser))]
13 # 初始状态(1状态)
14 for i in range(len(state)):
15 # max_p[0][i]表示初始状态第i个隐藏状态的最大概率
16 # 概率 = start_p[i] * emission_p [state[i]][obser[0]]
17 max_p[0][i] = start_p[i] * emission_p[state[i]][obser[0]]
18 path[0][i] = i
19 # 后续循环状态(2-t状态)
20 # 此时max_p 中已记录第一个状态的两个隐藏状态概率
21 for i in range(1, len(obser)): # 循环t-1次,初始已计算
22 max_item = [0 for i in range(len(state))]
23 for j in range(len(state)): # 循环隐藏状态数,计算当前状态每个隐藏状态的概率
24 item = [0 for i in state]
25 for k in range(len(state)): # 再次循环隐藏状态数,计算选定隐藏状态的前驱状态为各种状态的概率
26 p = max_p[i - 1][k] * emission_p[state[j]][obser[i]] * transition_p[state[k]][state[j]]
27 # k即代表前驱状态 k或state[k]均为前驱状态
28 item[state[k]] = p
29 # 设置概率记录为最大情况
30 max_item[state[j]] = max(item)
31 # 记录最大情况路径(下面语句的作用:当前时刻下第j个状态概率最大时,记录其前驱节点)
32 # item.index(max(item))寻找item的最大值索引,因item记录各种前驱情况的概率
33 path[i][state[j]] = item.index(max(item))
34 # 将单个状态的结果加入总列表max_p
35 max_p[i] = max_item
36 #newpath记录最后路径
37 newpath = []
38 #判断最后一个时刻哪个状态的概率最大
39 p=max_p[len(obser)-1].index(max(max_p[len(obser)-1]))
40 newpath.append(p)
41 #从最后一个状态开始倒着寻找前驱节点
42 for i in range(len(obser) - 1, 0, -1):
43 newpath.append(path[i][p])
44 p = path[i][p]
45 newpath.reverse()
46 return newpath
47
48
49 if __name__ == '__main__':
50 # 隐状态
51 hidden_state = ['rainy', 'sunny']
52 # 观测序列
53 obsevition = ['walk', 'shop', 'clean']
54 state_s = [0, 1]
55 obser = [0, 1, 2]
56 # 初始状态,测试集中,0.6概率观测序列以sunny开始
57 start_probability = [0.6, 0.4]
58 # 转移概率,0.7:sunny下一天sunny的概率
59 transititon_probability = [[0.7, 0.3], [0.4, 0.6]]
60 # 发射概率,0.4:sunny在0.4概率下为shop
61 emission_probability = [[0.1, 0.4, 0.5], [0.6, 0.3, 0.1]]
62 result = compute(obser, state_s, start_probability, transititon_probability, emission_probability)
63 for k in range(len(result)):
64 print(hidden_state[int(result[k])])
最新文章
- OOP感悟
- logistc regression练习(三)
- StructureMap使用方法(转)
- Android UI开发第四十篇——ScrollTricks介绍
- js模拟类的公有与私有 方法与变量
- 使用httpclient时候,出现“Too many open files”问题
- 16.python中的浅拷贝和深拷贝
- 多控制器之UIWindow
- 1.Maven的安装及配置
- 翻译一篇关于jedis的文章
- mongoDB介绍、安装、搭建简单的mongoDB服务器(一)
- 搞懂Linux下的几种文件类型
- mysql字符函数
- ajax post 传递数组参数
- Apache2.4配置总结(转)
- java的堆,栈,静态代码区 详解
- getServletContext()方法详解
- smarty核心思想 自制模板引擎
- 将HTML元素转换成图片供用户下载(html2canvas + canvas2Image)
- ps钢笔工具路径问题
热门文章
- NOIP 模拟 $16\; \rm Lost My Music$
- 题解 Omeed
- pip的问题 Can't connect to HTTPS URL because the SSL module is not available
- dataTemplate 之 ContentTemplate 的使用
- WPF 中TextBox 增加输入检测,错误提示
- 深入浅出Mybatis系列(四)---配置详解之properties与environments
- SpringBoot快速搭建流程
- 未解决:为什么在struts2下新建ognl的包,会出错?
- Spring之AspectJ
- python json demo