【中文分词系列】 3. 字标注法与HMM模型
By 苏剑林 | 2016-08-19 | 81634位读者 |在这篇文章中,我们暂停查词典方法的介绍,转而介绍字标注的方法。前面已经提到过,字标注是通过给句子中每个字打上标签的思路来进行分词,比如之前提到过的,通过4标签来进行标注(single,单字成词;begin,多字词的开头;middle,三字以上词语的中间部分;end,多字词的结尾。均只取第一个字母。),这样,“为人民服务”就可以标注为“sbebe”了。4标注不是唯一的标注方式,类似地还有6标注,理论上来说,标注越多会越精细,理论上来说效果也越好,但标注太多也可能存在样本不足的问题,一般常用的就是4标注和6标注。
值得一提的是,这种通过给每个字打标签、进而将问题转化为序列到序列的学习,不仅仅是一种分词方法,还是一种解决大量自然语言问题的思路,比如命名实体识别等任务,同样可以用标注的方法来做。回到分词来,通过字标注法来进行分词的模型有隐马尔科夫模型(HMM)、最大熵模型(ME)、条件随机场模型(CRF),它们在精度上都是递增的,据说目前公开评测中分词效果最好的是4标注的CRF。然而,在本文中,我们要讲解的是最不精确的HMM。因为在我看来,它并非一个特定的模型,而是解决一大类问题的通用思想,一种简化问题的学问。
这一切,还得从概率模型谈起。
HMM模型 #
所谓模型,就是指能对我们的输入数据进行处理,并且给出最优的输出。对于字标注的分词方法来说,输入就是$n$个字,输出就是$n$个标签。我们用$\lambda=\lambda_1 \lambda_2 \dots \lambda_n$表示输入的句子,$o=o_1 o_2 \dots o_n$表示输出。那什么是最优的输出呢?从概率的角度来看,我们当然希望下面的条件概率最大
$$\max P(o|\lambda) =\max P(o_1 o_2 \dots o_n|\lambda_1 \lambda_2 \dots \lambda_n)$$
换句话说,$o$有很多可能性,而最优的$o$应该是最大概率的$o$。
要注意,$P(o|\lambda)$是关于$2n$个变量的条件概率,而且$n$还是不定的。这种情况下,我们几乎不可能对$P(o|\lambda)$进行精确的建模。即便如此,我们可以稍微做些简化,比如,如果我们假设每个字的输出仅仅与当前字有关,那么我们就有
$$P(o_1 o_2 \dots o_n|\lambda_1 \lambda_2 \dots \lambda_n) = P(o_1|\lambda_1)P(o_2|\lambda_2)\dots P(o_n|\lambda_n)$$
而估计$P(o_k|\lambda_k)$就容易多了。这时候问题也得到很大简化,因为要使得$P(o|\lambda)$最大,只需要每个$P(o_k|\lambda_k)$最大就行。我们所做的假设,就称为独立性假设。
以上简化是一种方案,但是完全没有考虑到上下文,而且会出现不合理的情况(比如按照我们的4标注,那么b后面只能接m或e,但是按照这种最大的方法,我们可能得到诸如bbb的输出,这是不合理的)。于是我们就反过来,提出了一种隐含的模型(隐马尔可夫模型),就如同数学中的函数与反函数一般,反过来思考。
由贝叶斯公式,我们得到
$$P(o|\lambda)=\frac{P(o,\lambda)}{P(\lambda)}=\frac{P(\lambda|o)P(o)}{P(\lambda)}$$
由于$\lambda$是给定的输入,那么$P(\lambda)$就是常数,可以忽略。那么最大化$P(o|\lambda)$就等价于最大化
$$P(\lambda|o)P(o)$$
现在,我们可以对$P(\lambda|o)$作独立性假设,得到
$$P(\lambda|o)=P(\lambda_1|o_1)P(\lambda_2|o_2)\dots P(\lambda_n|o_n)$$
同时,对$P(o)$有
$$P(o)=P(o_1)P(o_2|o_1)P(o_3|o_1,o_2)\dots P(o_n|o_1,o_2,\dots,o_{n-1})$$
这时候可以作一个马尔可夫假设:每个输出仅仅于上一个输出有关,那么:
$$P(o)=P(o_1)P(o_2|o_1)P(o_3|o_2)\dots P(o_n|o_{n-1})\sim P(o_2|o_1)P(o_3|o_2)\dots P(o_n|o_{n-1})$$
这时候
$$P(\lambda|o)P(o)\sim P(\lambda_1|o_1) P(o_2|o_1) P(\lambda_2|o_2) P(o_3|o_2) \dots P(o_n|o_{n-1}) P(\lambda_n|o_n)$$
我们称$P(\lambda_k|o_k)$为发射概率,$P(o_k|o_{k-1})$为转移概率。这时候,可以通过设置某些$P(o_k|o_{k-1})=0$,来排除诸如bb、bs这些不合理的组合。
Python实现 #
以上就是对HMM的基本介绍,如果读者有一定的概率论基础,那么应该不难看懂的。可以看到,HMM对问题作了大量的简化,简化到不可能十分精确,因此,HMM模型一般都是用来解决“在查词典方法的过程中不能解决的部分”(就好比结巴分词所做的)。当然,你可以把马尔可夫假设加强——比如假设每个状态跟前面两个状态有关,那样肯定会得到更精确的模型,但是模型的参数就更难估计了。
怎么训练一个HMM分词模型?主要就是$P(\lambda_k|o_k)$和$P(o_k|o_{k-1})$这两部分概率的估计了。如果有一批标注语料,那么估计这两个概率应该不难,但是如果没有呢?有一个词典也凑合。我们可以将一个带有频数的词典转化为一个HMM模型,其Python实现如下:
from collections import Counter
from math import log
hmm_model = {i:Counter() for i in 'sbme'}
with open('dict.txt') as f:
for line in f:
lines = line.decode('utf-8').split(' ')
if len(lines[0]) == 1:
hmm_model['s'][lines[0]] += int(lines[1])
else:
hmm_model['b'][lines[0][0]] += int(lines[1])
hmm_model['e'][lines[0][-1]] += int(lines[1])
for m in lines[0][1:-1]:
hmm_model['m'][m] += int(lines[1])
log_total = {i:log(sum(hmm_model[i].values())) for i in 'sbme'}
trans = {'ss':0.3,
'sb':0.7,
'bm':0.3,
'be':0.7,
'mm':0.3,
'me':0.7,
'es':0.3,
'eb':0.7
}
trans = {i:log(j) for i,j in trans.iteritems()}
def viterbi(nodes):
paths = nodes[0]
for l in range(1, len(nodes)):
paths_ = paths
paths = {}
for i in nodes[l]:
nows = {}
for j in paths_:
if j[-1]+i in trans:
nows[j+i]= paths_[j]+nodes[l][i]+trans[j[-1]+i]
k = nows.values().index(max(nows.values()))
paths[nows.keys()[k]] = nows.values()[k]
return paths.keys()[paths.values().index(max(paths.values()))]
def hmm_cut(s):
nodes = [{i:log(j[t]+1)-log_total[i] for i,j in hmm_model.iteritems()} for t in s]
tags = viterbi(nodes)
words = [s[0]]
for i in range(1, len(s)):
if tags[i] in ['b', 's']:
words.append(s[i])
else:
words[-1] += s[i]
return words
代码的第一部分,就是用一个字典来表示$P(\lambda_k|o_k)$,$P(\lambda_k|o_k)$的计算是通过词典来获取的,比如将词典中所有的一字词都计入s标签下,把多字词的首字都计入b标签下,等等。计算过程中还使用了对数概率,防止溢出;
第二部分的转移概率,直接根据直觉估算的;
第三部分就是通过viterbi算法动态规划,求的最大概率路径了。对于概率估算,简单采用了加1平滑法,没出现的单字都算1次。
整个代码都很简单,纯Python实现,当然,效率不一定高,仅供参考。下面是一点测试
>>print ' '.join(hmm_cut(u'今天天气不错'))
今天 天气 不错>>print ' '.join(hmm_cut(u'李想是一个好孩子'))
李想 是 一个 好 孩子>>print ' '.join(hmm_cut(u'小明硕士毕业于中国科学院计算所'))
小明 硕士 毕业 于 中 国科 学院 计算 所
可以看到,HMM倾向于将两字结合在一起,因此效果不尽完美。但是,如果作为查词典方法不能成词部分的补充切分,那应该是相当不错的,比如“李想是一个好孩子”中,自动发现了人名“李想”,这是单靠查词典方法很难解决的。
转载到请包括本文地址:https://www.spaces.ac.cn/archives/3922
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Aug. 19, 2016). 《【中文分词系列】 3. 字标注法与HMM模型 》[Blog post]. Retrieved from https://www.spaces.ac.cn/archives/3922
@online{kexuefm-3922,
title={【中文分词系列】 3. 字标注法与HMM模型},
author={苏剑林},
year={2016},
month={Aug},
url={\url{https://www.spaces.ac.cn/archives/3922}},
}
May 8th, 2017
for m in lines[1:-1]:
hmm_model['m'][m] += int(lines[1])
这里应该改成
for m in lines[0][1:-1]:
hmm_model['m'][m] += int(lines[1]) ???
对的对的,感谢你的认真阅读~
May 16th, 2017
作者现在有没有找到比较好的发现新词的方法?
本博客已经有4种不同的新词发现方法,基本够用了。
June 12th, 2017
1
June 12th, 2017
由于λ是给定的输入,那么P(λ)就是常数。博主你好,这句话说P(λ)是常数,可不可以这样理解:λ为模型的输入句子,所以λ必然出现了,所以P(λ)=1.这样理解是不是哪里错了?还是对的?
June 16th, 2017
搞懂了,是全概率公式-_-.
^_^
全概率公式和这个 P((λ)是常数有数美关系 啊? 望指导
不知道你什么意思。
July 31st, 2017
冒昧问下,log_total = {i:log(sum(hmm_model[i].values())) for i in 'sbme'}是得出的发射概率吗,hmm_model[i].values()不是每个标注的数量吗,最后是怎么计算出概率的呢?
August 6th, 2018
请问字标注后的文件是如何生成的?
February 28th, 2020
苏神,最后一个公式
$P(\lambda|o)P(o)\sim P(\lambda_1|o_1) P(o_2|o_1) P(\lambda_2|o_2) P(o_3|o_2) \dots P(o_n|o_{n-1}) P(\lambda_n|o_n)$
是不是少了一个$P(O_1)$,即
$P(\lambda|o)P(o)\sim P(O_1) \times P(\lambda_1|o_1) P(o_2|o_1) P(\lambda_2|o_2) P(o_3|o_2) \dots P(o_n|o_{n-1}) P(\lambda_n|o_n)$,如果按照这个公式,那么在维特比算法初始化path的时候应该再乘以$P(O_1), O_1 \in bmes$
望指教,谢谢
其实我是刻意去掉$P(o_1)$的(所以用了符号$\sim$而不是$=$),因为这个对结果影响并不大,而且影响了对称性。
October 10th, 2020
python3 的代码,同时修改了一些缩进的bug
应改为:
m的统计放到else更合理一些,虽然对结果没啥影响哈
June 27th, 2021
"假设$\underline{每个字的输出仅仅与当前字有关}$",这个假设好像叫做"独立输出假设",来自《数学之美》P54最后一段。
不过我个人认为,独立输出假设和马尔可夫假设似乎是表达了同一个含义,目的是简化依赖关系,方便对问题求解。
这个假设叫做"独立输出假设",而非"马尔可夫假设"
已经调整描述。感谢反馈。