第36卷第1期自动化学报Vol.36,No.1 2010年1月ACTA AUTOMATICA SINICA January,2010一种改进的汉语全文无指导词义消歧方法李旭1刘国华1张东明2摘要针对现存的基于EM(Expectation maximization)迭代的无指导词义消歧方法收敛缓慢、计算量大的问题,利用互信息和Z-测试结合的方法选取特征,并通过一种统计学习算法估算初始参数值.实验结果表明改进方法有效地提高了汉语词义消歧的准确率,具有良好的扩展性和实用性.关键词词义消歧,无指导学习,特征提取,参数估计DOI10.3724/SP.J.1004.2010.00184An Improved Word Sense Disambiguation Method for Chinese Full-words Based onUnsupervised LearningLI Xu1LIU Guo-Hua1ZHANG Dong-Ming2 Abstract The existing word sense disambiguation methods based on expectation maximization(EM)unsupervised learning need a large amount of computation and converge slowly.To address the problems,an improved method is proposed,which makes use of mutual information theory based on Z-test to select features and uses a statistical learning algorithm to estimate initial parameter values.The experimental result shows that the proposed method improves effectively the precision of word sense disambiguation and has good expansibility and practicability. Key words Word sense disambiguation,unsupervised learn-ing,feature extraction,parameter estimation词义消歧是解决如何在给定上下文语境中确定多义词义项的问题,属于自然语言理解的底层研究[1].实用高效的词义消歧方法会对包括机器翻译、文本分类、自动文摘、信息检索、文本挖掘等在内的许多自然语言问题的研究和应用产生很大的帮助.近几年,国内外研究人员将统计学和机器学习引入到词义消歧的处理中,提出基于语料库的统计方法.基于语料库的词义消歧方法根据训练语料事先是否经过人工标注又可分为有指导机器学习和无指导机器学习两类.基于有指导机器学习的词义消歧方法需要对训练语料中的词语进行词义标记,在词义消歧问题中取得了较好的效果,但是该类方法为了克服数据稀疏问题,获得更好的学习和消歧效果,必须建立大规模的标注语料库.而标注语料库的获得需要耗费代价高昂的人工,很难实现基于大规模标注语料的有指导词义消歧工作,客观上也限制了该类方法的推广和应用[2].基于无指导机器学习的词义消歧方法不需要知道训练样本的词义类别,不依赖于人工标注的语料,可以实现大规模真实语料的训练和学习,能够有效地克服数据稀疏问题.收稿日期2008-11-06录用日期2009-05-06Manuscript received November6,2008;accepted May6,2009国家自然科学基金(60773100)资助Supported by National Natural Science Foundation of China (60773100)1.燕山大学信息科学与工程学院秦皇岛0660042.秦皇岛职业技术学院秦皇岛0661001.College of Information Science and Engineering,Yanshan Uni-versity,Qinhuangdao0660042.Qinhuangdao Institute of Technol-ogy,Qinhuangdao066100基于无指导机器学习的词义消歧方法通过一个训练语料利用EM(Expectation maximization)迭代算法对歧义词的上下文进行聚类,利用聚类的结果对歧义词进行词义消歧[3].利用现存的无指导词义消歧方法时,存在两个问题:1)在词义聚类时没有选择特征,它把歧义词所在句子中所有的上下文词语作为特征变量,因此计算量大并且收敛缓慢;2)以任意值初始化概率模型中的参数.如果初始化参数选择不当,将导致一个不佳的估计结果[4].针对以上问题,提出了一种改进的汉语全文无指导词义消歧方法,利用互信息和Z-测试结合的方法选取特征,并通过一种统计学习算法估算EM迭代的初始参数值.1改进的汉语全文无指导词义消歧方法1.1特征提取词义消歧需要从上下文中获得词义知识,但是并不是所有的上下文词语都对歧义词词义变量的取值有约束.词语之间的固定搭配有强弱之分,词义之间的约束力也有大小区别.因此有必要按照约束力的强弱对候选特征词加以区别,选择信息更丰富的词语作为特征词[5].本文方法从上下文词语与歧义词的搭配关系出发,借鉴李涓子提出的互信息和Z-测试结合的思想[6]选取特征.信息论中的互信息可以作为描述搭配强度的物理量,在词义消歧的特征选择中,如果某一上下文词语与歧义词的互信息较大,说明该词语对歧义词有表征意义.互信息的计算公式见式(1),其中w和w j分别表示歧义词和某一上下文词语,p(w)和p(w j)分别表示词w和w j在语料库中出现的概率,p(w,w j)表示词w和w j在语料库中的共现概率.M为语料库的大小,f(w)和f(w j)分别表示词w和w j在语料库中出现的次数,f(w,w j)表示词w和w j在语料库中的共现次数.I(w,w j)=log2p(w,w j)j=log2Mf(w,w j)j(1)当I(w,w j)>>0时,说明w和w j关联强度大,因此w 和w j可作为特征.虽然互信息可以作为描述搭配强度的物理量,但是,如果特征选择直接确定选择互信息大于某一阈值的上下文信息为特征时,则对不同互信息的分布,设定的阈值也不应该相同,这样,算法难以操作.而Z-测试都可以将互信息的分布进行标准变换,将其变换为标准的正态分布,这样,不论互信息如何分布,都可以使用统一的阈值进行求解[6].根据概率论可知,借助于一个线性变换,可以将一般的正态分布转化成标准正态分布,即若X∼N(µ,σ2),则Z=(X−µ)/σ∼N(0,1)[7].对互信息的分布进行标准变换,将其变换为标准的正态分布.对于每个歧义词w,计算w 的互信息均值、均方差和Z值的公式分别见式(2)∼(4).E=1nni=1I(w,w j)(2)D=1nni=1(I(w,w j)−E)2(3)Z=I(w,w j)−E√D(4)如果Z值大于阈值,则w j与w为选出的一个特征.根据概率论中的“3σ法则”可知:正态分布在区间(−3,+3)1期一种改进的汉语全文无指导词义消歧方法185内,其整个概率覆盖度可达99.74%[7].因此,阈值在(−3,+3)内进行取值.阈值越大,选择出的特征对歧义词的表征意义越大.1.2初始参数估计无指导词义消歧方法使用的是没有词语词义标注信息的生语料.一般认为不能从生语料中获取词义知识.其实不然,生语料中仍然包括很多可挖掘的词义信息,歧义词的词义分布可以通过估算近似地获得[8].由于生语料中歧义词的词义分布是未知的,根据信息论中的最大熵原理,对于未确定的分布,应该采取均匀分布[9].因此假定在某一特定上下文环境中,歧义词w的每一个词义出现的机会均等,在统计上它们的频次相等.在具体的机器学习中,这种均匀分布是短暂的、很不稳定的状态,很容易被打破.在统计句子中的某一个词语时,它的词义虽然采取了均匀分布,但是语料中会有很多词语具有某些相同的语义,这些词义以不同的频率重复出现.这将导致最终的统计结果中歧义词的词义分布不再均匀,而这种不均衡正是真实文本的自然表现[10].因此,可以利用该思想,在生语料中估算歧义词的词义分布,并且根据统计学中的大数定理可知,语料的规模越大,估计分布越接近于真实分布.估算初始参数的统计学习算法如下.输入:训练语料.输出:词义分布.步骤1.利用HowNet[11]构造语料中词语的词义向量.步骤2.为参数建立(M+1)×(N+2)二维表,其中行数M等于不同的定义项数,列数N为词语的总个数.第2列记录每个词义出现的次数f(s i),第3列到N+2列记录词义s i同其上下文词语w j共现的次数f(s i,w j),其中0<i≤M,0<j≤N.进行统计学习前,表中的各元素用0进行初始化.构建的二维表如表1所示.表1词频二维表Table1Table of word frequenciesSense f(s i)f(s i,w1)···f(s i,w n)Sense1f(s1)f(s1,w1)···f(s1,w n)Sense2f(s2)f(s2,w1)···f(s2,w n). . .............Sense k f(s k)f(s k,w1)···f(s k,w n). . .............Sense m f(s m)f(s m,w1)···f(s m,w n)步骤3.在训练语料中统计.对于歧义词w,令它的词义为{s1,s2,···,s i},上下文出现的词语为{w1,w2,···,w j},其中0<i≤M,0<j≤N.如果w在句子中出现1次,则词语w在表中对应的i个词义的出现频度都加1/i,表中对应的j个上下文出现的频度都加1/i.步骤4.统计完成后,根据式(5)和(6)估算各个词义分布.p(s i)=f(s i)mi=1f(s i)(5)p(w j|s i)=f(s i,w j)f(s i)(6)步骤5.算法结束.举例说明估算EM迭代初始参数的统计学习算法的执行过程.假设“剽窃”和“抄袭”是训练语料中的两个词语,现在存在3个搭配分别为:“剽窃论文”、“抄袭论文”和“抄袭思想”,其中“论文”和“思想”分别为与“剽窃”和“抄袭”的义项共现的上下文词语.对“剽窃”和“抄袭”的词义分布估计如下所示.步骤1.利用HowNet查询词语的义项.“剽窃”只有一个义项:G−C=V,DEF=steal|偷.“抄袭”有3个义项,分别为:G−C=V,DEF=attack|攻打,military|军;G−C=V, DEF=imitate|模仿;G−C=V,DEF=steal|偷,#copy|抄写.步骤2.由步骤1可知,“剽窃”和“抄袭”具有共同的义项“steal|偷”.构建二维表,其中包括3个义项,2个上下文词语,各元素初始化为0.令表中的义项s1=steal|偷, s2=attack|攻打,s3=imitate|模仿,上下文词语w1=论文, w2=思想.步骤3.对语料进行统计.对于“剽窃论文”来说,因为“剽窃”只有一个义项,因此只需将f(s1)加1,f(s1,w1)加1.对于“抄袭论文”来说,“抄袭”有3个义项,根据最大熵原理f(s1)=f(s2)=f(s3)=1/3.因此将f(s1)、f(s2)和f(s3)加1/3,同时将f(s1,w1)、f(s2,w1)和f(s3,w1)均加1/3.“抄袭思想”的处理过程与“抄袭论文”相同.统计结果如表2所示,其中i=1,2,3.表2对实例的统计结果Table2Statistical result for the exampleSense f(s i)f(s i,w1)f(s i,w2)s1=steal|偷534313s2=attack|攻打231313s3=imitate|模仿231313步骤4.根据式(5)和(6)估算词义分布.计算结果如下: P(s1)=0.555,P(s2)=0.222,P(s3)=0.222.P(w1|s1)= 0.8,P(w2|s1)=0.2,P(w1|s2)=0.5,P(w2|s2)=0.5, P(w3|s1)=0.5,P(w1|s1)=0.5.1.3改进方法的词义标注过程改进方法的词义标注过程如下.步骤1.预处理:去掉语料库中的虚词和停用词,免得造成噪声干扰.步骤2.根据词典定义对单义词直接标注词义.步骤3.对类别歧义词进行消歧:根据词典定义和词语词性的对应关系标出正确的词义标记.例如“被”在词典定义中标注两个定义项,作为名词时表示一种床上用品,作为介词时表示被动语态.如果在给定的句子中,通过分词和词性标注后,“被”标注为介词,则可以排除其作为名词时的词义,确定在该句子中“被”表示为被动语态.步骤4.利用HowNet对歧义词标注所有可能的词义.步骤5.特征提取:计算歧义词与上下文词语的互信息,并利用Z-测试把互信息的的分布变换为标准的正态分布,使用统一的阈值进行特征选择.步骤6.通过统计学习算法估算初始参数.步骤7.利用选择的特征集合和估算出的初始参数进行EM算法的迭代计算,得到词义聚类结果.举例说明.假设给定文本中的一个歧义词w,为了确定该歧义词在给定上下文语境中的义项S,其中S为隐性变量,需要利用EM算法对词义进行聚类.令F1和F2表示二维离散的特征变量,并且每维特征变量有2个可能的取值.假186学报36卷定数据样本(F1,F2,S)的10组观察结果为:(1,2,?),(1,2,?),(2,2,?),(2,2,?),(1,2,?),(1,1,?),(1,1,?),(1,1,?),(1,2,?),(2,2,?).对数据样本进行无指导词义消歧的聚类过程如下.首先利用统计学习算法估算初始参数值,并利用式(7)和(8)计算参数估计,其中f(S)表示样本中隐性变量S出现的频度,N表示数据个数.f(F i,S)表示样本中第i维特征向量与隐性变量S共现的频度.ˆp(S)=f(S)N(7)ˆp(F i|S)=f(F i,S)f(S)(8)第1次迭代的E-step和M-step结果如图1所示.图1第1次迭代E-step和M-stepFig.1E-step and M-step of iteration1利用第1次迭代的M-step结果可以得到ˆp(S|F1,F2)估计,估计结果见图2,每一组观察的最大估计用粗体表示.举例说明,根据上一步的结果可以计算出ˆp(S=1)׈p(F1=1|S=1)׈p(F2=1|S=1)=0.075,ˆp(F1=1,F2=1,S)=0.225,因此有ˆp(S=1|F1=1,F2=1)=0.075÷0.225=0.333.以此类推.图2第2次迭代前ˆp(S|F1,F2)的估计结果Fig.2Estimation forˆp(S|F1,F2)before iteration2EM算法取S值为在给定上下文中能够观察到的歧义词词义概率的最大值,见式(9).S=arg maxSˆp(S|F1,F2,···,F n−1,F n)(9)例如(F1=1,F2=1,S=?)是样本空间中的一个数据,根据图2可知,ˆp(S=3|F1=1,F2=1)=0.444,ˆp(S=2|F1=1,F2=1)=0.222,ˆp(S=1|F1=1,F2=1)=0.333.ˆp(S=3|F1=1,F2=1)值最大,因此取S值为3.用估计后的S值更新样本,并且利用更新后的数据重新计算边缘事件的期望值.第2次迭代的E-step和M-step结果见图3.图3第2次迭代E-step和M-stepFig.3E-step and M-step of iteration2在第2次迭代结束之后,检查参数估计集合Θnew是否收敛于第1次迭代参数集合Θold.根据以上分析可知:Θold={0.4,0.4,0.2,0.75,0.25,0.50,0.50, 1.00,0.00,0.25,0.75,0.25,0.75,0.50,0.50},Θnew={0.4,0.3,0.3,1.00,0.00,0.00,1.00,1.00,0.00,0.00,1.00,0.00,1.00,1.00,0.00}.令 =0.01.此时2个估计集合Θnew和Θold的差值大于 值,因此,需要进行第3次迭代计算.第2次迭代过程与前两次迭代过程相同.通过计算可知,第3次迭代结果与第2次迭代结果相同,参数估计集合的差值为0,说明参数估计收敛,因此最后分配的隐性变量S值如下:(1,2,1),(1,2,1),(2,2,2),(2,2,2),(1,2,1),(1,1,3),(1,1,3),(1,1,3),(1,2,1),(2,2,2).因此可知事件(F1=1,F2=2)属于类1,事件(F1=2,F2=2)属于类2,事件(F1=1,F2=1)属于类3.2实验实验的训练语料来源于经过了词语切分和词性标注的人民日报基本标注语料库.测试集为500条句子,包含4426个中文词,其中多义词1943个,平均每个多义词具有词义3个左右.把对500条句子进行人工词义标注和校对的结果作为标准评价语料.分别采用3种方法进行对比实验.实验1采用现存的无指导词义消歧方法;实验2在现存无指导词义消歧方法中加入特征提取步骤,利用互信息和Z-测试结合的方法选择特征;实验3采用改进的汉语全文无指导词义消歧方法,不仅加入特征提取步骤,还利用统计学习方法估算初始参数值.词义消歧的准确率按照式(10)计算,其中N1表示标注的正确词义数,N2表示实际标注的词义数,P recision表示准确率.P recision(%)=N1N2×100%(10)为了探讨训练语料的规模对测试结果的影响,分别使用规模递增的6组语料作为训练数据.3种方法的词义消歧准1期一种改进的汉语全文无指导词义消歧方法187确率如图4所示.图43种方法的实验结果Fig.4Experimental results of the three methods由实验数据可以看出,方法2在方法1的基础上增加了特征提取步骤,效果十分显著,这证明了特征提取对无指导词义消歧的作用很大.特征提取步骤的执行一方面减少了计算量,降低了方法的时间复杂度,另一方面消除了一些噪声的影响,提高了词义消歧的准确率.方法3又在方法2的基础上增加了初始参数估计的步骤,从实验结果可以看出,方法3的准确率要高于方法2的准确率,说明估计EM 迭代的初始参数,对于提高词义消歧方法的准确率也有效果.从实验数据可以看出,3种词义消歧方法的准确率都随着训练语料的增大而提高,这说明大规模的训练语料对于改善方法的词义消歧性能有利.训练语料的规模越大,蕴涵的语义知识越多,词义消歧可以获得的有效信息的数量也就越大.此外,实验对测试集中每个歧义词的平均特征变量数进行了统计.方法1中每个歧义词的平均特征变量数为9个,通过在方法2和方法3中加入互信息和Z -测试结合方法选择特征的步骤,每个歧义词的平均特征变量数减少到5个.由于EM 算法主要估算隐性变量的概率及隐性变量条件下特征变量的概率,因此方法2和方法3中每一次EM 迭代的计算量可减少约44.4%.通过上述的理论和实验可知,改进的汉语全文无指导词义消歧方法具有以下特点.1)方法通过在词义聚类时选择特征和估算初始化参数值,解决了现存EM 算法计算量大、收敛缓慢的问题,消除了无关信息的噪声影响,有效提高了汉语词义消歧的正确率.2)方法不是以几个有代表性的歧义词作为研究与测试的对象,而是针对真实的应用情况,能够对大规模真实文本进行词义标注.3)方法无需人工标注语料,可以从大规模语料中自动获取词义排歧知识,避免了有指导词义消歧方法要面对的数据稀疏问题的发生.此外,训练语料的来源和规模可以根据标注的需要任意地调整,使得训练出来的语言模型具有良好的扩展性,适合各个应用领域的文本词义标注.3结论本文提出一种改进的汉语全文无指导词义消歧方法,首先利用互信息和Z -测试结合的方法选取特征,然后通过一种统计学习方法估算EM 算法的初始参数值,最后利用EM 算法进行迭代计算.通过与现存的无指导词义消歧方法进行对比实验,验证了本文方法的有效性.这种改进的汉语全文无指导词义消歧方法可以应用于机器翻译、文本分类、自动文摘、信息检索等领域,具有重要的理论和实用价值.References1Ide N,Veronis J.Word sense disambiguation:the state of the putational Linguistics ,1998,24(1):1−412Lin S D,Karin V.A semantics-enhanced language model for unsupervised word sense disambiguation.In:Proceedings of the 9th International Conference on Computational Linguis-tics and Intelligent Text Processing.Haifa,Israel:Springer,2008.287−2983McCarthy D,Koeling R,Weeds J,Carroll J.Unsupervised acquisition of predominant word putational Lin-guistics ,2007,33(4):553−5904Pedersen T,Bruce R.Distinguishing word senses in untagged text.In:Proceedings of the 2nd Conference on Empirical Methods in Natural Language Processing.New York,USA:1997.197−2075Lu Zhi-Mao,Liu Ting,Li Sheng.The research progress of statistical word sense disambiguation.Acta Electronica Sinica ,2006,34(2):333−343(卢志茂,刘挺,李生.统计词义消歧的研究进展.电子学报,2006,34(2):333−343)6Li Juan-Zi,Huang Chang-Ning.An improved maximum en-tropy language model and its application.Journal of Soft-ware ,1999,10(3):257−263(李涓子,黄昌宁.语言模型中一种改进的最大熵方法及其应用.软件学报,1999,10(3):257−263)7Sheng Zhou.Probability and Statistics .Shanghai:Shanghai Jiao Tong University Press,1999.83−84(盛骤.概率论与数理统计.上海:上海交通大学出版社,1999.83−84)8Klein D.Unsupervised learning for natural language pro-cessing.In:Proceedings of the 21st Annual Conference on Learning Theory.Helsinki,Finland:Springer,2008.5−69Cai Ji-Hong,Song Fei.Maximum entropy modeling with fea-ture selection for text categorization.In:Proceedings of the 4th Asia Information Retrieval Symposium.Harbin,China:Springer,2008.549−55410Lu Zhi-Mao,Liu Ting,Li Sheng.Two statistics methodsof Chinese word sense disambiguation.Journal of Harbin Institute of Technology ,2005,37(7):119−122(卢志茂,刘挺,李生.两种基于统计的汉语词义消歧模型.哈尔滨工业大学学报,2005,37(7):119−122)11Dong Zhen-Dong.HowNet.,November 5,2002(董振东.知网.,November 5,2002)李旭燕山大学信息科学与工程学院博士研究生.主要研究方向为自然语言处理和文档复制检测.本文通信作者.E-mail:lixu102@(LI Xu Ph.D.candidate at the College of Information Science and Engineering,Yanshan University.Her research interest cov-ers natural language processing and document copy detection.Corresponding author of this paper.)刘国华燕山大学信息科学与工程学院教授.主要研究方向为数据库理论,数据库安全,Web 数据管理和自然语言处理.E-mail:ghliu@(LIU Guo-Hua Professor at the the College of Information Science and Engineering,Yanshan University.His research in-terest covers database theory,database security,web data man-agement,and natural language processing.)张东明秦皇岛职业技术学院副教授.主要研究方向为信息管理.E-mail:zdmqzf@(ZHANG Dong-Ming Associate professor at Qinhuangdao Institute of Technology.Her main research interest is informa-tion management.)。
