基于隐马尔可夫模型的切词系统

基于隐马尔可夫模型的切词系统1，概论本系统使用隐马尔可夫模型和序列标记法实现切词1.1，模型参数状态S={B,M,E,S}代表了序列标记法的四个标记B：词首，M：词中，E：词尾，S：单独的字成词观察值集合V为所有可能出现的汉字p(ti|ti-1)标记转移概率p(wi|ti)标记ti生成词wi的概率p(t)标记t出现在句首的概率1.2，模型学习使用90%的语料信息，采用有指导的学习方法，最大似然估计法P(ti|ti-1)=c(ti-1,ti)/c(ti-1)P(wi|ti)=c(ti,wi)/c(ti)2，语料信息预处理2.1思路分析语料库后发现：语料库每一行都是一个汉语语法意义上的句子。但切词不需要参考语法意义上的句子，只要是有标点符号，我们就视标点符号两侧为不同词，因此我们可以以/w为分割符。例如：迈向/v充满/v希望/n的/u新/a世纪/n——/w一九九八年/t新年/t讲话/n（/w附/v图片/n１/m张/q）/w我们把它当作三个句子，“迈向”，“一九九八”和“附”将作为句首词，而“世纪”，“讲话”和“张”将作为据尾词。两个/w之间定义为一个句子。还要切掉”[“，”]”，否则后面的建模过程会出现麻烦例如：[中央/n人民/n广播/vn电台/n]nt2.2过程读取语料库中每个词语，去掉”/”和”/”后的字符，去掉最前面的版面序号，去掉标点符号，为每个词语添加序列标记（/B,/M,/E,/S），然后保存到一个中间文件中，以备后用。中间文件格式形如：１/B２/M月/E３/B１/M日/ES中/B共/M中/M央/E总/B书/M记/ES国/B家/E主/B席/E江/S泽/B民/E发/B表/E１/B９/M９/M８/M年/E新/B年/E讲/B话/ES迈/B向/E充/B满/E希/B望/E的/S新/S世/B纪/ES3，建模3.1，数据结构设计3.1.1计算p(ti|ti-1)的表BMES句首总和BMESti-1行ti列表是c(ti-1,ti)。总和不包括后来句首，句尾。单独出现表示这个字单独作为一句话出现。计算c(ti)方法：c(ti)=ti出现在句首的次数＋ti出现在其他状态后的次数（及ti所在列的和）3.1.2计算p(wi|ti)的数据结构Typedefstruct_word{//表示这个词以B,M,E,S为标记出现的次数即为c(ti,wi)，p开头的表示p(wi|ti)//因为需要平滑，所以次数表示成double类型DoubleBDoubleMDoubleEDoubleSDoublepBDoublepMDoublepEDoublepS}Word4，切词将预料信息剩下的10%还原成句子，让程序进行切词。切词就是求隐马尔可夫环的一个能最好解释观察序列的状态转换序列。用韦特比算法。4.1数据结构：typedefstruct_wtb{doubledeta;//表示δdoublebo;表示bintfi;表示ψ}WTB;doublem_pi[4];表示πiWTB(*m_db)[4];一个二维数组，里面装的是算法所需要的数据doublea[4][4];表示a4.2算法韦特比算法在本程序中的表示初始化M_db[0][].fi全部初始化为0M_db[0][].bo初始化为map中对应的那些项迭代m_db[t][j].fi=k;m_db[t][j].deta=max*m_db[t][j].bo;max为m_db[t-1][i].deta*a[i][j]的最大值k为使m_db[t-1][i].deta*a[i][j]为max的i终止求m_db[t][i].deta最大值和使其为最大值的k＝i求最佳路径迭代表达式k=m_db[t][k].fi;求出所有的k就可得到最佳路径。4.3平滑当出现未登录词Ox时，假设其在不同的状态下都出现ADD_DELTA（大于0小于1）次，然后算出概率。5，自动评价从中间文件中读取后1/10的句子，读取每个句子，把句子的标注去掉，调用切分算法，然后将切分结果与中间结果比较，求出准确率，召回率和F－评价然后与原预料库进行比较，求出准确率，召回率和F值6，分析6.1delta选择对平滑的影响我选了选了4个delta：1，0.5，0.1，0.000001，发现无论delta选择多少，基本上不会对结果产生太大的影响准确率：67%-68%召回率：69%-70%F－评价：68%-69%6.2模型分析BMES句首总和B068518444333091488512851M029766685180098284E247523001532850512851S173840009706553312303662看这个状态转换表，我终于知道了为什么我的切分结果基本上都是二字成词，概率最大的E-S和B-E居然比其他概率至少大一个数量级，这也许是汉语的特点。6.3切词错误分析我得切分：怀/B揣/E这/S如/B泣/E如/B诉/E的/S呵/B护/E语料库：怀/Ng揣/v这/r如泣如诉/i的/u呵护/vn，/w分析：语料库中“怀”与“揣”分开，而我的程序把它们当作一个词，这个结果倒是可以接受，而“如泣如诉”是不是应该分开应该有争议。怀/B97.5/M22.5/E78.5/S13.5/揣/B5.5/M0.5/E0.5/S4.5通过观察看到，“怀”字出现在词首次数很多，而“揣”字根本没有出现在词尾过，由于数据平滑赋予它出现在词尾0.5词，而怀字在词首概率非常大，所以提高了“怀揣”成为一个词的概率如/B944.5/M104.5/E209.5/S366.5/泣/B2.5/M2.5/E7.5/S0.5/诉/B33.5/M64.5/E177.5/S2.5/“如”字出现在词首比出现在词中概率大8倍而且B-E的概率要比B-M的概率大一个数量级，所以无法切出“如”在中间的情况。我得切分：现/B实/E的/S顿/B悟/E却/S被/S描/B出/E形/B来/E语料库：现实/n的/u顿悟/vn却/d被/p描/v出/v形/Ng来/v。/w语料库中最后四个字分别成词，而我得却切成两个词“描出”这个问题倒不是很大，我觉得可以看成一个词，但是“形来”完全是错误的。形/B1222.5/M25.5/E135.5/S23.5/来/B850.5/M265.5/E2628.5/S1446.5/可以看出，形作为词首的概率比作为词尾的概率大两个数量级，而来作为词尾的概率几乎是单独成词的概率的二倍，而且B-E的概率S-S的概率大一个数量级，所以我得程序肯定会把“形来”切成一个词。我得切分：在/S马/B克/B思/B墓/E前/S的/S讲/B话/E语料库：语料库中没有，这是我手动输入的结果可见这个结果错的太大了“马克思”被切开，这个结果可以预料到，因为这个模型没有考虑到专有名词，所以所有的人名与地名我这个程序基本上都会切错。马/B445.5/M215.5/E131.5/S188.5克/B397.5/M387.5/E499.5/S32.5/思/B702.5/M257.5/E128.5/S14.5/可以看出，“马克思”成为一个词的概率还是蛮大的。主要是B-E和E-B这两个状态转换的概率太大了，大出与M相关的状态转换概率一个数量级，还有就是“思”作为词首的概率也很大。所以就和后面的字合在一起了。做了一个实验，发现“马克思”居然很难切成一个词。我得切分：常/S宝/B宝/E老/B师/E的课讲/B得/E非/B常/E好/S语料库：语料库中没有，是自己输入的常老师的名字被切开倒是很正常，能判断出这个是一个词很难，而且也不想“马克思”这个人名那样常用。常/B446.5/M64.5/E536.5/S93.5/宝/B141.5/M7.5/E87.5/S6.5/虽然“常”字单独成词的概率很小，但是“宝”字做词中的概率更小，而且状态转换概率也决定了BMS比SBS难出现。做了几个实验看出，“常宝宝”这三个字很难成一个词方法局限性我感觉隐马尔可夫模型结合序列标注算法不太适合切词。我认为主要原因如下：A，没有利用词表信息，导致专有名词“分家”B，状态太少，导致模型过于简单。由于汉语的单子和双字词数量太大，基本上冲掉了三字以上词的概率C，汉语切词本身的问题，有些多字词其实可以切开，而有些单字词放在一起也行，这跟汉语的发展有关我认为，古汉语大部分都是单字词，后来由于口语化才出现这么多多字词，所以几个字在一起算不算一个词也很模糊。D，没有考虑到语法知识，使一些本来一眼就能看出的人名没有切对。7，实现环境：windowsxp，visualc++6.0，visualAssistx1.3使用了STL的一些容器，感觉起来确实比用标准C方便些。ASSIST工具非常好用，提高了编程效率8，使用说明由于软件学院无法连上助教的Ftp，所以我就把所有debug目录清空，把所有的预料文件和中间结果文件清空，只保留了切词结果result.txt文件。需要编译重新编译（我用的是vc6），然后在dos命令行下进入debug目录输入：segmentation预料文件名.txt。由于读写了几个大文件，所以运行速度比较慢，在我得电脑（p41.6,768m）上运行需要几分钟才会把模型建好，并且得出评价结果。