分词、隐马尔可夫模型及其训练
0引言
假设我们要统计一篇文章,或者一部小说里出现的关键词的个数,比如国家名称出现的次数。我们当然可以直接用字符串匹配的方式,看看文本里有多少个”中国”。
但是,这样做会有一个问题,有一些情况下,字符串“中国”还真不一定表示一个国家,比如“在这些革命家的心中国家命运就是自己的命运”,”中”和”国”虽然连在一起,但是不是一个词语,更不是一个国家名称。我们的统计肯定会有较大的误差。
1分词
这种误差如何减小呢?我们可以先对文本进行分词(word segment),把字符以词语为单元分组,形成有意义的文本片段,然后统计其中我们关心的词语。
与英语这类表音文字(书写的时候会将单词用空格分隔开)不同,中文的书写的时候,只是用标点符号将文本大致地切分开(表示标点符号两边的内容关系没有那么亲密,但是没有把文字按照词语进行分组。我们在阅读的时候,会下意识地进行一个操作,就是区分一句话中的”中国”到底是一个国家名称,还是别的什么东西;如果字符串“中国”是一个国家名称(也有可能是古代的一个国家),我们就快速的记住,在这句话中这是一个词语,这是一个国家,这是我们的祖国,等等;如果这个字符串不是一个国家名称,那是不是别的什么词语呢;好像这真不是一个词语(我们人在看文本的时候,经常也会搞不清这到底说的什么),那就是两个独立的字。
这只是一个非常粗糙的分词过程,非常的累人。有人就想,能不能让机器来分词呢?这样的话,一部《西游记》也能很快处理完。
研究者们在分词任务的自动化上花了很大的功夫,他们提出了各种各样的模型和方案,后面我们会介绍其中的隐马尔可夫模型。
我们再来切分一句话:
我是一个中国人。
我/是/一/个/中国人/。
我/是/一/个/中国/人/。
注意,通常来说,我们在分词的时候,会考虑标点符号的存在。这样做的目的,是便于对语句进行准确的切分。比如“我在地图上找到一个国家,是刚果(金)”,这句话中”刚果(金)”是一个国家名称的完整、正确地表述,缺了小括号中的部分,就没办法正确理解了。
另外,这里提供了两种切分结果,两种都不能说错吧?那么,哪一种切分方式更合理呢?有没有什么指标可以度量呢?什么是“最好”?不能空口白牙,得有一个肉眼可见的标准。如果想让大家都信服,还得是一个性质良好的指标。我们需要构建类似多元线性回归模型的残差平方那个和一样的指标,来表征对一句话的切分的质量。这个指标取值越大(小),切分的质量越好。
如何得到最好的切分结果呢?我们可以构建一个模型,这个模型会为我们提供若干切分方案,然后计算出每一种方案的切分质量水平,我们选择其中质量最好的就可以——这就是隐马尔可夫模型在分词任务中干的事情。请注意,这个场景是有监督的;隐马尔可夫模型还可以应对无监督的情况,就像聚类算法一样,可以为词语打上标签,这里就不讲了(主要是因为训练算法比较难,笔者还没弄明白)。
那么,隐马尔科夫模型长什么样呢?如何训练呢?
2隐马尔可夫模型
隐马尔可夫模型是概率图模型的一种,我们一般用概率图来描述。通常来说,我们的概率模型是以哈希表或者概率密度函数这样的形式存储的,比如朴素贝叶斯模型的概率就可以存储在key-value pair数据结构中——这样的概率模型如何展示呢?
2.1图是什么
有一种方法可以把概率模型可视化地展示出来,就是使用概率图(probabilistic graph)。概率图模型就指的是用图(graph)表示的概率分布。图是图论里的一个概念,表示由边(edge)连接顶点(vertex)而形成的结构,如图2-1。图可以看作是现实世界中事物以及事物之间关系的抽象表示,事物就是一个个节点,事物之间的关系就是连接它们的边。比如,一个家庭中的成员可以用节点来表示,成员之间的关系可以用边来表示:
实际应用中,图可以使用这样的结构来存储:
表2-1 一个三口子家的关系
成员A 成员B 关系
李雷 韩梅梅 丈夫
李雷 李大丽 父亲
韩梅梅 李雷 丈夫
韩梅梅 李大丽 妈妈
李大丽 李雷 女儿
李大丽 韩梅梅 女儿
表2-1中,关系一栏,表示成员A是成员B的”XX”。
2.2马尔科夫模型
我们换一个场景,用概率图来描述另外一个东西。假设我们要找工作,你下一份工作的岗位和上一份工作之间有没有关系呢?一般来说是有的,比如我现在是一个销售,那么我下一份工作很有可能还是销售,但是也有一定的可能性转行到其他岗位。我们可以想象,岗位之间存在转化的可能——我们可以统计出一个岗位job_k转换到另一个岗位job_k+1的概率。假设人们的职业只有(数据挖掘工程师,数据分析师,教师 )三种,而且三种岗位之间的转换概率关系如表2-2。
表2-2 一个人的岗位转换概率
岗位1 岗位2 转换概率
数据挖掘工程师 数据挖掘工程师 0.7
数据挖掘工程师 数据分析师 0.2
数据挖掘工程师 教师 o.1
数据分析师 数据挖掘工程师 0.3
数据分析师 数据分析师 0.6
数据分析师 教师 0.1
教师 数据挖掘工程师 0.1
教师 教师 0.8
教师 数据分析师 0.1
如果知道一个人选择第一份工作时的概率分布,我们就可以推算出这个人接下来每一次换工作时,选择各种岗位的概率。假设第一份工作的概率分布如表2-3。
表2-3 各个岗位作为第一份工作的概率
岗位名称 作为第一份工作的概率
数据挖掘工程师 0.5
数据分析师 0.3
教师 0.2
基于表2-2和表2-3中的数据,我们可以画出一个概率图模型,如图2-2。岗位名称后面的是这个岗位作为第一份工作的概率(我们后面会叫它初始状态概率);绿色虚线表示,起点岗位会以一定的概率变为终点的岗位;黑色的实现表示一个人可能会继续呆在这个岗位上。
这个图描述的就是各个岗位之间的转移概率。这就是一个我们常说的马尔可夫模型。由于下一份工作干什么,只和现在的岗位有关系,这个概率图模型就是一个马尔可夫链。
对很多人来说,一辈子会换若干份工作,这样就形成了一个序列,比如"数据挖掘工程师-数据分析师-教师-数据挖掘工程师",表示一个人一共在4个岗位上工作过。
2.3隐马尔可夫模型
假设我们比较注重他人隐私,没有问这个人这些年都在什么岗位上工作过;但是我们又给他安了一个监控,知道他这些年做了些什么事情(请忽略剧情的不合理)。假设一个人可能做的事情有:写代码,看论,为数据库添加索引(为了简化问题,就这3种)。在生活和生产中,我们经常会遇到这样的问题:我们对系统所处的状态感兴趣,但是我们无法观测系统的状态;我们能观测到的,是系统的外在特征;而在不同的状态下,系统的外在特征是有区别的。
按照常理,工作岗位更换后,我们每天做的事情内容就会变化——在不同的岗位工作时,我们每天的生活内容是不一样的,所做的事情出现的概率分布是不一样的。
假设各个岗位上,一个人做事情的概率分布如表2-4。
表2-4 各种岗位工作内容的概率分布
数据挖掘工程师 写代码: 0.5
为数据库添加索引: 0.3
看论文: 0.2
数据分析师 写代码: 0.2
为数据库添加索引: 0.2
看论文: 0.2
教师 写代码: 0.3
为数据库添加索引: 0.1
看论文: 0.6
假设一个人先后做了这么几件事: 写代码, 看论文, 看论文, 为数据库添加索引。我们能不能知道,做这4件事的时候,这个人分别是在什么岗位上吗?
我们能观测到的,就是一个行为序列——我们称这个序列为观测序列。而这个人的岗位序列是观测不到的——我们称这个岗位序列为隐藏状态,或者简称状态。隐藏状态之间的转移关系,以及各个状态生成外在特征取值的概率分布,就是我们常说的隐马尔科夫模型。
3隐马尔可夫模型相关的计算
3.1一个隐藏状态序列的概率
在使用隐马尔可夫模型的时候,我们需要基于可观测序列,去找到一个最合适的隐藏状态序列。是不是”最好”,得靠概率说了算。那么一个候选的隐藏状态序列的概率怎么算呢?
我们可以穷尽4个时间点上,这个人的岗位情况:
hiddenStat1 数据挖掘工程师 数据挖掘工程师 数据挖掘工程师 数据挖掘工程师
hiddenStat2 数据挖掘工程师 数据挖掘工程师 数据挖掘工程师 数据分析师
hiddenStat3 数据挖掘工程师 数据挖掘工程师 数据挖掘工程师 教师
...
一共是3^4=81种组合。
我们把4件事情发生时,可能的岗位情况可视化出来,如图3-1。DM是data mining 的简写, DA是data analysis的简写, TC是teacher的简写。图的一列节点,表示一件事情发生时,可能的隐藏状态;有向边表示隐藏状态的跳转关系。第一个状态取值,是使用初始概率分布随机挑选的,后面的就按照概率转移关系跳转。
然后,我们计算初每一个状态序列下,出现观测序列的概率。通常来说,我们假设一个人做的两件之情之间的相互独立的——这样做当然不完全符合真相,但是可以简化问题,而且实践中确实可以解释和解决问题,这种假设是可以接受的。
p(写代码,看论文,看论文,为数据库添加索引) = p(写代码) * p(看论文) * p(看论文) * p(为数据库添加索引)
=[p(数据挖掘工程师)*p(写代码/数据挖掘工程师) ]* [p(数据挖掘工程师->数据挖掘工程师)*p(看论文/数据挖掘工程师) ]* [p(数据挖掘工程师->数据挖掘工程师)*p(看论文/数据挖掘工程师)] * [p(数据挖掘工程师->数据挖掘工程师)*p(为数据库添加索引/数据挖掘工程师)]
式中, p(数据挖掘工程师)表示第一个岗位是数据挖掘工程师的概率;p(数据挖掘工程师->数据挖掘工程师)表示上一个岗位是数据挖掘工程师,这个也是的概率(就是岗位的转移概率);p(写代码/数据挖掘工程师) 表示一个人在数据挖掘工程师岗位上写代码的概率。
p(写代码,看论文,看论文,为数据库添加索引) = [0.5 * 0.5] * [0.7 * 0.2] * [0.7 * 0.2] * [0.7 * 0.2] = 0.000686
类似的,我们可以计算出另外15种隐藏状态序列下,观测序列出现的概率,然后选取其中概率值最大的,作为我们猜测的真实隐藏状态序列,也就是这个人的岗位序列。
3.2使用维特比算法挑选最好的隐藏状态序列
设想一个极端的情况:我们有这个人整个职业生涯的观测序列,也就是成千上万件事情组成的序列,我们还能不能用前面这种方式找出概率最大的隐藏状态序列呢?3^1000,这么多次的计算,实际上是没办法完成的。
有没有办法,可以减少计算量呢?有的。
有位叫维特比的学者,提出了一个算法,可以用来缩小这个任务的搜索空间,进而减小计算量。这个算法叫做维特比算法,是一个经典的动态规划算法。维特比算法认为,step1到step4的最短路径上,任意两个点之间的路径,都是它们之间唯一的最短路径。假设最短路径上有一个节点,那么这个节点把最短路径一分为二——这两条路径也是对应节点之间的最短路径。
假设概率最大路径是(DM, DA, TC, DM),那么,step1到step3之间的概率最大路径唯一,并且一定是(DM, DA, TC); 反过来讲,假如(DM, DA)是step1到step2的概率最大路径,那么,step1到step4的概率最大路径必然包含了(DM, DA),然后加上step2到step4之间的概率最大路径。这个定理是可以用反证法证明的。
我们可以确定的说,概率最大路径的起始节点必然是DM, DA, TC中的一个。我们可以求出从这三个节点出发的3条概率最大路径,然后选出3条路经中概率最大的,就是全局概率最大路径了。从step1.DM出发,有3个候选节点可以跳转: step2.DM, step2.DA, step2.TC。我们可以求出step.1DM 到step2.DM的概率:
p((写代码,看论文), (DM , DM)) = p((写代码,看论文)|(DM, DM) ) * p((DM , DM))
=p(写代码|DM) * p(看论文|DM) * p(DM ) * p(DM->DM)
= 0.5 * 0.2 * 0.5 * 0.7
= 0.035
类似的我们可以求出step1.DM-step2.DA 以及step.DM-step2.TC的概率:
p((写代码,看论文), (DM , DA)) = 0.5 * 0.2 * 0.3 * 0.2 = 0.006
p((写代码,看论文), (DM , TC)) = 0.5 * 0.6 * 0.2 * 0.1 = 0.006
这样,step1.DM到step2的概率最大路径就是step1.DM-step2.DM。这个路径有什么特殊的呢?根据我们前面看到的定理,step1.DM-step2.DM肯定在以step1.DM为出发点的概率最大路径上——这样的话,我们接下来的任务就是找step2.DM到step4的概率最大路径了。
找step2.DM到step4的概率最大路径,套路和刚才一样,先找step1.DM-step2.DM路径出发, 到step的3个路径中的概率最大路径。
重复前面的操作,我们就可以得到从step1.DM出发的概率最大路径S1了。
在这个过程中,我们在step2需要计算3个路径的概率,在step3需要计算3个概率,step4也是,一共9个路径的概率。
使用前面的策略,还可以找到从step1.DA出发的概率最大路径S2和从step1.TC出发的概率最大路径S3。S1, S2, S3中概率最大的就是我们要找的全局概率最大路径。在这个过程中我们一共需要计算3*9=27个概率。
这个算法的特点,就是"已找到的概率最大路径",帮助我们一步一步地找到下一个节点并延长这个路径。在这个过程中,我们每一步的计算,都可以直接使用之前的计算结果,而不需要像暴力方法一样,重复进行大量计算;另外,假如一个节点不在概率最大路径上,我们在后面的计算中,就不考虑从它出发的所有路径,这样可以大幅减小我们的搜索空间。
前面介绍的,是我们在知道隐马尔可夫模型的参数的情况下,如何基于观测序列求出最好的隐藏状态序列。那么,模型的参数如何去求呢?
4隐马尔可夫模型的训练(有监督情况)
我们把前面介绍的马尔可夫模型推广到一般情况,假设一个系统有N种状态(stat_1, stat_2, ..., stat_n, ..., stat_N),这N种状态的转移概率可以用一个矩阵来记录:
transProbMatrix =
[tp_1_1, tp_1_2, ..., tp_1_N;
tp_2_1, tp_2_2, ..., tp_2_N;
...
tp_N_1, tp_N_2, ..., tp_N_N
]
其中,第i行第j列的元素,表示系统从状态stat_i跳转到状态stat_j的概率。
系统的初始状态取值的概率分布是initProb = [ip_1, ip_2, ..., ip_n, ..., ip_N],第n个元素ip_n表示系统刚启动的时候,状态为stat_n的概率。
系统生成客观测现象记为ov,假设系统可能生成的观测值有M种,(ov_1, ov_2, ..., ov_m, ..., ov_M)。状态stat_n下,观测值的取值概率分布为:
ovProb_n = [ovp_n_1, ovp_n_2, ..., ovp_n_m, ..., ovp_n_M],其中ovp_m表示当体系处于stat_n时,生成一个观测值取值为ov_m的概率。
以上是一个完整的隐马尔可夫模型,我们用lambda 来表示整个模型。
假如我们观测到一个序列(o_1, o_2, o_3,...o_k),这个观测值序列出现的概率是多少呢?
p((o_1, o_2, o_3,...o_k)|lambda)
=p((o_1, o_2, o_3,...o_k), stat_path_1|lambda) + p((o_1, o_2, o_3,...o_k), stat_path_2|lambda) + ... +
p((o_1, o_2, o_3,...o_k), stat_path_F|lambda)
式中,stat_path_f表示一个长度为k的一维向量,表示一种隐藏状态组合;F=(N-1) * N * M,是组合的个数。我们求出每一种隐藏状态序列与观测序列共现概率,然后求和,就得到了这个观测序列的概率。
p((o_1, o_2, o_3,...o_k), stat_path_f|lambda)
= p((o_1, o_2, o_3,...o_k),|stat_path_f,lambda) * p( stat_path_f, lambda)
= [p(o_1|s_f_1) * p(o_2|s_f_2)* ... * p(o_k|s_f_k)] * initp(s_f_1) * transp(s_f_1->s_f_2) * transp(s_f_2->s_f_3) *...*transp(s_f_k-1->s_f_k)
式中,p(o_1|s_f_1) 表示状态s_f_1下,生成观测值o_1的概率;initp(s_f_1) 表示初始状态为s_f_1的概率;transp(s_f_1->s_f_2)表示系统有状态s_f_1转移到s_f_2的概率。
这几个概率都在模型参数lambda中,这样就可以计算观测序列的概率了。
HMM的训练有两种情况:有监督和无监督。有监督的意思是,每个观测值对应的隐藏状态被人工标记出来了;无监督指的是,我们人力不够,训练数据只有观测值序列。
有监督情况下,我们只需要用计数统计的方式,估计初始状态概率分布,转移概率矩阵和观测值的概率分布。比如常见的分词任务,我们可以统计出每一句话的第一个字符的词性,进而获得隐藏状态的初始取值的概率分布;我们可以统计每一个词性下,各个字符出现的概率分布;我们可以统计各个词性之间前后转换的概率分布——这样就得到了隐马尔可夫模型的三部分参数,我们就可以用维特比算法去为一句话分词了,效果还是不错的。
至此,我们就介绍完了有监督隐马尔可夫模型的训练。
5结束语
隐马尔可夫模型是非常有价值的一个模型,不光是在分词任务,它还在词性标注、命名实体识别、语音转换等等序列标注任务中得到了广泛的应用。无监督隐马尔可夫模型在金融领域非常有用,想发财的同志可以好好学一学,重点学习EM算法。
有监督隐马尔可夫模型有点像朴素贝叶斯,我们知道了现象与原因的概率关系后,基于观察到的现象把各类原因的概率算出来,然后以概率最大的那一个原因来解释现象。
注意:本文为李鹏宇(知乎个人主页 https://www.zhihu.com/people/py-li-34)原创作品,受到著作权相关法规的保护。如需引用、转载,请注明来源信息:(1)作者名,即“李鹏宇”;(2)原始网页链接,即当前页面地址。如有疑问,可发邮件至我的邮箱: lipengyuer@126.com。