在这篇文章中,我们暂停查词典方法的介绍,转而介绍字标注的方法。前面已经提到过,字标注是通过给句子中每个字打上标签的思路来进行分词,比如之前提到过的,通过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://kexue.fm/archives/3922

更详细的转载事宜请参考:《科学空间FAQ》

如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。

如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!

如果您需要引用本文,请参考:

苏剑林. (Aug. 19, 2016). 《【中文分词系列】 3. 字标注法与HMM模型 》[Blog post]. Retrieved from https://kexue.fm/archives/3922

@online{kexuefm-3922,
        title={【中文分词系列】 3. 字标注法与HMM模型},
        author={苏剑林},
        year={2016},
        month={Aug},
        url={\url{https://kexue.fm/archives/3922}},
}