作者归档:itenyh

Itenyh版-用HMM做中文分词五:一个混合的分词器

        在上一节中,我们看到了HMM分词器的优势在于它的灵活性,能够联系上文情况作出是否分词的判断,但是过于灵活又会出现一些低级的分词错误。一种扬长避短的想法是使用词典限定HMM的分词。具体的做法是,用基于词典的分词方法分出N种结果,然后用HMM挑出最有可能的分词结果。

       介绍一下分词使用的词典,在《中文分词入门之资源》有提到:

        Mandarin.dic                             分词词典,约40000条词汇

        对于一段文本,找出所有可能的切分结果叫做全切分,全切分可以保证切分结果集对正确切分结果100%的召回率,换句话说全切分中一定包含正确结果(在不包含未登录词的前提之下)。长度为n的句子,最大全切分数量可以达到2`(n-1)个,因此全切分计算量会随着句子长度增加急剧上升。举例,句子“研究生命起源”的全切分如下:

研/究/生/命

研/究/生命

研究/生/命

研究/生命

研究生/命

共有5个切分方案,其中倒数第二个是正确切分。下面讲一下我对句子进行全切分用的具体算法。

        如上图,考虑构建一颗多叉树,其中每一条从root到叶子节点的路径均为一种分词结果,所有root到叶子节点的路径就是全切分的结果。树的建立方法是使用的递归:

        对句子进行正向词典匹配,结果为:

        研            对剩余句子:究生命    进行词典匹配

        研究        对剩余句子:生命        进行词典匹配

        研究生    对剩余句子:命            进行词典匹配

        全切分结果准备就绪,下面的问题是如何从备选分词中选出最佳分词结果,因为备选结果只有有限的数量,因此可以使用枚举算法求最佳解:

                                                          ArgmaxC,O  P(C|O)

解法在第2集中已经提到,等价于求:

ArgmaxC,O  P(O|C)P(C)

       为了避免计算溢出(小数位数太多计算机无法表示),我们改为求:

                                                          ArgminC,O  -lnP(O|C) – lnP(C)

        对于句子“研究生命”,分词结果如下:

        研/究/生/命:44.24491284128293

        研/究/生命:37.12604972173189

        研究/生/命:33.59480382540995

        研究/生命:26.49050292705271

        研究生/命:32.15705471620734

        其中“研究/生命”拥有最低值,被选为最优解。再举一些有意思的分词结果:

        研究生/研究/生活

        结合/成/分子

        他/说/的/确实/在/理

        可以看出这种混合分词器能够灵活的掌握字符间的分和,消除一些歧义分词。

        下面是我对几种分词方法的实验结果,同时使用了ICTCLAS2011作为一个权威的分词效果比对,其中ICTCLAS2011使用的是它自带的词典,其他分词方法使用的词典是Mandarin.dic

                                      每秒分词     P         R            F

普通最大词匹配          5482401      0.76   0.85      0.80

扩展的最大匹配          1118591      0.79   0.75      0.77

普通的Markov           1590173      0.76   0.72      0.74

混合的Markov           46818        0.73   0.84      0.78

ICTCLAS2011           942973       0.92   0.92     0.92

          可以看出ICTCLAS果然是名不虚传,相对于混合的Markov,ICTCLAS使用的是层叠式的HMM模型,可以很好的识别出未登录词;其次ICTCLAS使用了基于N-最短路径的切分,对计算效率也有很大的提高。

          PS:因为之前没有想过要分享分词的程序,所以写得比较混乱,最近也很忙,我会尽快整理发上来的。

 

 

Itenyh版-用HMM做中文分词四:A Pure-HMM 分词器

先介绍一下使用的资源,分词使用的语料来自于SIGHAN Bakeoff 2005的 icwb2-data.rar,《中文分词入门之资源》里有很详细的介绍:

/icwb2-data.rar/training/msr_training.utf8  用以训练HMM,其中包含已分词汇约2000000个

/icwb2-data.rar/testing/pku_test.utf8           测试集

/icwb2-data.rar/scripts/score                           一个perl脚本,测试分词效果

         我们使用经典的字符标注模型,首先需要确定标注集,在前面的介绍中,我们使用的是{B,E}的二元集合,研究表明基于四类标签的字符标注模型明显优于两类标签,原因是两类标签过于简单而损失了部分信息。四类标签的集合是 {B,E,M,S},其含义如下:

B:一个词的开始

E:一个词的结束

M:一个词的中间

S:单字成词

举例:你S现B在E应B该E去S幼B儿M园E了S

用四类标签为msr_training.utf8做好标记后,就可以开始用统计的方法构建一个HMM。我们打算构建一个2-gram(bigram)语言模型,也即一个1阶HMM,每个字符的标签分类只受前一个字符分类的影响。现在,我们需要求得HMM的状态转移矩阵 A 以及混合矩阵 B。其中:

                                     Aij = P(Cj|Ci)  =  P(Ci,Cj) / P(Ci) = Count(Ci,Cj) / Count(Ci)

                                     Bij = P(Oj|Ci)  =  P(Oj,Ci) / P(Ci) = Count(Oj,Ci) / Count(Ci)

公式中C = {B,E,M,S},O = {字符集合},Count代表频率。在计算Bij时,由于数据的稀疏性,很多字符未出现在训练集中,这导致概率为0的结果出现在B中,为了修补这个问题,我们采用加1的数据平滑技术,即:

                                     Bij = P(Oj|Ci)  =  (Count(Oj,Ci) + 1)/ Count(Ci)

         这并不是一种最好的处理技术,因为这有可能低估或高估真实概率,更加科学的方法是使用复杂一点的Good—Turing技术,这项技术的的原始版本是图灵当年和他的助手Good在破解德国密码机时发明的。求得的矩阵A如下:

        B       M                    E              S

B  0.0 | 0.19922840916814916 | 0.8007715908318509 | 0.0

M  0.0 | 0.47583202978061256 | 0.5241679702193874 | 0.0

E  0.6309567616935934 | 0.0 | 0.0 | 0.36904323830640656

S  0.6343402140354506 | 0.0 | 0.0 | 0.36565844303914763

矩阵中出现的概率为0的元素表明B-B, B-S, M-B, M-S, E-M, E-E, S-M, S-E这8种组合是不可能出现的。这是合乎逻辑的。求得的矩阵B,部分如下:

   o1               o2            o3                o4

B 7.8127868094E-7 1.460991186336E-4 0.007293548529516 6.047041844505E-4……

M ……

E …….

S ……

我们设定初始向量Pi = {0.5, 0.0, 0.0, 0.5}(M和E不可能出现在句子的首位)。至此,HMM模型构建完毕。其实用统计方法构建HMM并不复杂,麻烦的是写程序,特别是需要将分类标签和字符集合进行编码,这是个极其繁琐的过程。

我用的JAVA写程序,因此使用的Jahmm这个开源项目来进行相关的计算,对于一个HMM模型,现在我们可以写入一个观察序列,用Viterbi算法获得一个隐藏序列(分词结果)。具体做法是(举例为虚构):

1 . 对测试集按标点符号,空格,换行符拆分为一条一条的只包含字符的单句:

……

中共中央总书记

国家主席

……

2. 将句子转化为对应的编码,也即观察序列:

……

101 121 101 47 1010 32 1992

332 3241 893 2111

……

3. 输入观察序列,使用Viterbi算法输出隐藏序列(0:B,1:M,2:E,3:S)

……

0112333

0202

……

4. 输出最终分词结果:

……

中共中央/总/书/记

国家/主席

……

现在我们在对测试集pku_test.utf8分词,并用perl脚本进行评测,结果如下=== SUMMARY:
=== TOTAL INSERTIONS:    5627
=== TOTAL DELETIONS:    10639
=== TOTAL SUBSTITUTIONS:    18194
=== TOTAL NCHANGE:    34460
=== TOTAL TRUE WORD COUNT:    104372
=== TOTAL TEST WORD COUNT:    99360:

=== TOTAL TRUE WORDS RECALL:  0.724   正确切分出的词的数目/应切分出的词的总数

=== TOTAL TEST WORDS PRECISION: 0.760  正确切分出的词的数目/切分出的词的总数

=== F MEASURE:      0.742   F1 = 2 * Precision*Recall / (Precision + Recall)

=== OOV Recall Rate:    0.250      未登录词召回率

精度为:76%,召回为:72.4%。一个不太让人满意的结果,我们来看看他都干了些什么:

                                                        改判/被/告人/死/刑立/即/执行

这是一个较典型的例子,可见分词结果中出现了“告人”,“刑立”等字典中不存在的词,这些是由于HMM分词的“自由度”太大造成的,当然这种较大的“自由度”也有好处,比如:

                                                        检察院/鲍绍坤/检察/长

         看!HMM成功的识别出一个人名,这是基于词典的分词方法做不到的。实际上,在ICTCLAS系统中(2004)就是用的HMM来识别人名。下一节将会介绍一个基于词典的混合HMM分词器。

Itenyh版-用HMM做中文分词三:前向算法和Viterbi算法的开销

上文中始终未提到前向算法与Viterbi算法,主要是因为想特意强调一下数学解不等同于算法解。算法解考虑进了计算的性能问题,算法是为计算机设计的。

首先看一下“评估”问题中的时间开销。回顾一下公式:

P(O) = sigmaO P(O|C)P(C)= sigmaO P(C1)P(O1|C1)P(C2|C1)P(O2|C2)…P(Ci|Ci-1)P(Oi|Ci)

如果我们使用枚举的方法来求解,那么对于C来说,设有N种状态,序列长度为T,那么所有可能的隐藏序列组合为N`T(N的T次方)个,对于每一个序列需要的乘法次数为2T次,而加法需要T次,那么总共需要的计算次数为2T*N`T的级数(精确的,需要(2T-1)N`T次乘法,N`T-1词加法)。例如N=5,T=100,那么需要约2*100*5`100约10`72次计算,显然我们需要一个更好的算法。

         考虑上图这个简单的例子,图中描述了两个隐藏序列:abb,cbb。为了求得P(O),使用枚举算法有:

Pia * P(O1|a)*Pab*P(O2|b)*Pbb*P(O3|b) + Pic * P(O1|c)*Pcb*P(O2|b)*Pbb*P(O3|b)

Pi代表初始概率,使用前向算法有:

(Pia* P(O1|a) *Pab + Pic * P(O1|c)*Pcb) *P(O2|b)*Pbb* P(O3|b)

其中前向算法中的第一个大括号中的式子为局部概率a2(b),可以清楚的看到枚举算法用了10次乘法和1次加法,而前向算法把乘法次数减少到了7次,原因就是前向算法使用了大家熟知的“乘法分配律”提取了公因式。看起来好像提升不多,不过当计算量大的话这种提升就很可观了。事实上,前向算法将计算次数减低到了N`2*T的级数,那么对于N=5,T=100只需要约3000次计算即可。

         现在使用上面的例子考虑一下Viterbi算法,使用枚举算法我们需要计算:

Pia * P(O1|a)*Pab*P(O2|b)*Pbb*P(O3|b) 和 Pic * P(O1|c)*Pcb*P(O2|b)*Pbb* P(O3|b)

并比较求得其中较大的一个,而使用Viterbi算法,我们首先比较:

Pia *P(O1|a)*Pab 与 Pic * P(O1|c)*Pcb 的大小,选出较大的一个再乘以 Pbb* P(O3|b)

10次乘法一次比较,减少到5词乘法一次比较。

         总结一下,前向算法和Viterbi算法分别从两种角度向我们展现了降低计算复杂度的方法,一种是提取公因式减少计算次数,例如计算(1+2+3)* 5 和 1*5+2*5+3*5,从数学角度来看只是表达的不同,但对于计算者(无论是人还是计算机)来说,少的计算次数意味着更小的计算时间开销;另一种是,去掉不必要的计算,要找到最大的隐藏序列,如果在子序列上都不能取得最大还有必要去计算全序列吗?

Itenyh版-用HMM做中文分词二:模型准备

本质上看,分词可以看做一个为文本中每个字符分类的过程,例如我们现在定义两个类别:E代表词尾词,B代表非词尾词,于是分词“你/现在/应该/去/幼儿园/了”可以表达为:你E现B在E应B该E去E幼B儿B园E了B,分类完成后只需要对结果进行“解读”就可以得到分词结果了。

那么如何找到这个分类序列EBEBEEBBEB呢?我们可以求得所有可能出现的分类序列的出现概率然后选择其中概率最大的一个,用数学表达为:

                                                 argmax C  P(C1,C2,C3….Ci) (1)

其中C代表一个分类标识,这里,C 属于 {E,B} 进一步的:

P(C1,C2,C3….Ci) = P(C1)P(C2,C3…..Ci|C1)=P(C1)P(C2|C1)P(C3…..Ci|C1,C2)=

P(C1)P(C2|C1)P(C3|C2,C1)P(C4|C3,C2,C1)…P(Ci|Ci-1….C1)

这里,我们假设第i个分类标记只依赖于第i-1个标记,那么我们可以得到分类标记的马尔科夫链了:

                                 P(C1,C2,C3….Ci) =P(C1)P(C2|C1)P(C3|C2)…P(Ci|Ci-1)

我们称P(Cj|Ci)为i到j的状态转移概率,可以通过在大量预料中使用统计的方法求得。如果我们用(1)这个模型为上例找到了EBEBEEBBEB这个序列,看似好像是一个好的解决方案,不难想到的问题是,对于任何一个10个字符组成的文本,我们都会得到这个相同的序列,也即相同的分词结果,这太可怕了!问题在于我们只考虑了分类标记而没有考虑被分词的对象,也即每一个具体的字符,我们称这些字符为观察值,用O表示,现在把它们考虑进来,我们要找的是:

                                argmax C  P(C1,C2,C3….Ci | O1, O2, O3……Oi) = P(C|O)(1)

         给定了O的情况下,最有可能出现的C的序列,也是HMM的“解码问题”,根据贝叶斯公式有:

                                               P(C|O) = P(O|C)P(C) / P(O)

        由于P(O)对于每一种序列来说都是一样的,因此可以去掉,因此,(1)等价于 :

                                                  argmax C P(O|C)P(C) (2)

P(C)的求法上面已经讲过了,对于P(O|C),HMM有两个假设:(a)已知类地序列,观察值在统计上是独立的; (b)某类的概率密度函数不依赖其他类。也就是说依赖性仅仅存在于产生类的序列,而在类内,观察值服从类自己的规则。因此对于:

                              P(O|C) = P(O1, O2, O3……Oi | C1,C2,C3….Ci )

根据假设a,观察序列具有统计意义上的独立性,因此:

                   P(O1, O2, O3……Oi | C1,C2,C3….Ci )=P(O1|C) * P(O2|C)……P(Oi|C)

根据假设b,对于Oi的分类Ci与Cj没有依赖关系,所以有:

                      P(O1|C) * P(O2|C)……P(Oi|C) = P(O1|C1) * P(O2|C2)……P(Oi|Ci)

同样的P(Oi|Ci) 可以通过在大量预料中使用统计的方法求得。至此我们在一个马尔科夫链上加入了观察值数据,构造了一个HMM,这个模型已经可以具备一定的分词能力啦!

尽管没有用到,顺便回顾一下HMM要解决的第一个问题“评估”,也即求一个给定观察序列的概率,即:P(O),用全概率公式展开有:P(O) = sigmaO P(O|C)P(C)(sigmaO代表对O的集合求和),同样需要计算P(O|C),因此计算上和“解码”有相似之处。

PS : 关于模型(1),在论文HMM Tutorial中写的是:

图中O是观察值,q是代表分类序列,λ指HMM模型,可见作者用的是qO的联合概率,而(1)中用的是O作为条件的条件概率。这个模型和模型(2)是相等的,因此所求的的序列也和模型(1)相等。个人认为,从理解来看,既然给定了O,是不是把O作为条件概率更合适呢?

Itenyh版-用HMM做中文分词一:序

前段时间仔细看了52nlp的关于隐马尔科夫模型(HMM)的介绍,深入浅出,真的是非常好的教材,再次感谢一下52nlp的辛勤劳作。这里,本人打算写一下个人运用HMM做分词的过程,目的有两个,一个是对之前工作的一个总结,梳理下自己的思路,另一个是和大家做一个交流。

如果对HMM不熟悉的话,推荐先看一看52nlp的系列文章《HMM学习最佳范例》,本文假设读者已经对HMM有所了解,很多地方会直接提出相关概念。理解前向算法,维特比算法是关键,关于无监督学习HMM的Baum-Welch算法在本文中没有使用,至少了解它的作用即可。

总所周知,在汉语中,词与词之间不存在分隔符(英文中,词与词之间用空格分隔,这是天然的分词标记),词本身也缺乏明显的形态标记,因此,中文信息处理的特有问题就是如何将汉语的字串分割为合理的词语序。例如,英文句子:you should go to kindergarten now 天然的空格已然将词分好,只需要去除其中的介词“to”即可;而“你现在应该去幼儿园了”这句表达同样意思的话没有明显的分隔符,中文分词的目的是,得到“你/现在/应该/去/幼儿园/了”。那么如何进行分词呢?主流的方法有三种:第1类是基于语言学知识的规则方法,如:各种形态的最大匹配、最少切分方法;第2类是基于大规模语料库的机器学习方法,这是目前应用比较广泛、效果较好的解决方案.用到的统计模型有N元语言模型、信道---噪声模型、最大期望、HMM等。第3类也是实际的分词系统中用到的,即规则与统计等多类方法的综合。

我计划在 本系列文章中完成以下工作,首先在52nlp的工作基础上对HMM模型做一些补充,然后制作一个HMM的分词器,之后分析其缺点,最后制作一个混合分词器。如果有任何不足的地方,欢迎大家拍砖!