一个基于超图的词义归纳模型-钱涛.pdf

《一个基于超图的词义归纳模型-钱涛.pdf》由会员分享，可在线阅读，更多相关《一个基于超图的词义归纳模型-钱涛.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第48卷第1期 四川大学学报(工程科学版) v0148 N。12016年1月 JOURNAL OF SICHUAN UNIVERSITY(ENGINEERING SCIENCE EDITION) Jan2016文章编号：1009-3087(2016)01-0152-06 DOI：1015961jjsuese201601023一个基于超图的词义归纳模型钱涛1，一，姬东鸿1，戴文华2(1武汉大学计算机学院，湖北武汉430072；2湖北科技学院计算机科学与技术学院，湖北咸宁437100)摘要：针对词义归纳如何学习多个上下文实例中的高阶语义关系的问题，提出一个基于超图的词义归纳模型。首先，采用基于词汇

2、链的方法发现目标单词的上下文实例间的高阶语义关系；然后，用上下文实例表示结点，用词汇链发现超边来构建超图；最后，使用一个基于最大密度超图谱聚类算法发现词义。实验基于Semeval-2013 WSI任务，与普通图模型进行比较，其在词义检测与词义评级2个指标上分别提升了56和64。关键词：词义归纳；超图；高阶语义关系中图分类号：TP391 文献标志码：AA Hypergraph Model for Word Sense InductionQIAN Ta01”，Jt Donghon91，DAI Wenhua2(1School of Computer，Wuhan Univ，Wuhan 430072，C

3、hina；2College of Computer Sciand Techn01，Hubei Univof Sciand Techn01，Xianning 437100，China)Abstract：In order to learn the higherorder semantic relatedness among multiple instance of target word，a hypergraph_model was pro-posed for word sense inductionFirst，a lexical chain based method was used for d

4、iscovering the higherorder semantic relatednessThena hypergraph Was constructed，in which nodes represent the instances of contexts where a target word occurs，and hyperedges wereformed by lexical chainsFinally，a maximum density based hypergraph clustering method was used for finding word sensesExperi

5、ments based on Semeval-2013 WSI task showed that this model gives an improvement of 56and 64in sense detection and senseranking respectively，compared to the traditional graph modelKey words：word sense induction；hypergraph；higherorder semantic relatedness不同于词义消歧(word sense disambiguation，WSD)任务需给定一个已

6、由人工构建的固定的词义集，词义归纳(word sense induction，WSI)，也称词义学习(word sense learning)任务被定义为从大规模语料中自动发现目标单词的词义。由于词义消歧需要大量标注语料且存在词义缺失等问题，词义归纳受到越来越多的关注，它在词典编撰、信息检索、机器翻译等领域有着非常重要的应用。WSI通常被看作是一个非监督的聚类问题。其算法输入是目标单词的上下文实例；其输出是上下文实例的分组，每一组表示一个词义。传统的求解WSI的方法大多基于向量空间模型，如上下文向量、单词替代向量口。等。此类方法首先将目标单词的上下文实例表示成基于频度统计或概率分布的特征向量，

7、然后使用各种方法，如kmean、meanshift层次聚类等对向量进行聚类，聚类结果表示为归纳的词义。最近，图模型被广泛应用到WSI任务。它通常把单词表示为结点，单词间的共现关系表示边，利用识别出的高密度子图来表示归纳的词义。Widdows和Dorow。31提出从句法树来抽取单词关系。Klapaftis和Manandhar【41通过单词的搭配来识别单词关系。这些方法大都是在局部的上下文中利用频度统计或搭配来计算2个向量或结点间的相似关系，其本质是二元语义关系。为了表达单词间复杂的语义关系，Bordagl51提出采用多词搭配来构建多个单词收稿日期：20150429基金项目：国家自然科学基金重点项

8、目资助(61133012；61373108)；国家社会科学基金重点项目资助(1l&ZDl89)作者简介：钱涛(1975一)，男，博士生，讲师研究方向：自然语学处理E-mail：taoqianwhueducahttp：jsueseSCUeducn万方数据第1期 钱涛，等：一个基于超图的词义归纳模型 153间的高阶语义关系；Klapaftis和ManandharMl提出一个基于超图的词义归纳模型，其超边根据多词频度统计来构造。这些方法仅考虑了局部的语义关系，而忽略了全局视角下的语义相似关系，使得WSI性能受到一定程度的限制。WSI任务中面临的一个关键挑战是如何学习多个上下文实例间的高阶语义关系。作

9、者基于词汇链动机，提出一个全局视角下的词义归纳超图模型，其中目标单词的每个实例表示为一个结点，多实例间的高阶语义关系表示为超边。模型采用基于词汇链的方法来识别超边，词汇链抽取采用基于统计的LDA(1atent Dirichlet allocation)话题模型。提出的一个基于最大密度的超图聚类方法被用于发现词义。针对聚类数较多的情况，采用一种高内聚度和低分离的合并策略来减少聚类数。l提出的超图模型所提超图模型主要分为以下3步：Step 1：采用LDA话题模型自动抽取词汇链；Step 2：利用词汇链构建超图；Step 3：对超图进行聚类，每一类表示一个词义。下面分别详细描述以上3个步骤。11词汇

10、链抽取词汇链是文本语义相关的单词序列集合。它为文本结构和文本话题提供非常重要的线索。它能表示全局的语义相似关系o 7|。例如，给出单词“菜单”的3个上下文实例：1)如何显示电脑上的菜单?2)您可以通过菜单打开设备或储存卡上的所有应用程序。3)Windows 8操作系统取消开始菜单一度被全世界用户吐槽。其中，3个单词“电脑一应用程序一操作系统”构成一个词汇链。根据这个词汇链，可推导出3个实例中的目标单词“菜单“表示同一个词义：“计算机显示屏上可操作选项”。这个词汇链本质上表示了3个实例间一种全局的高阶语义关系。词汇链方法是自然语言处理应用中的一个重要技术。它已经被成功运用于词义消歧、单词错误检测

11、、文本摘要话题跟踪和文本分割等自然语言处理任务。词汇链抽取主要分为2类方法。一类方法使用知识库如WordNet或Thesauri作为背景知识来度量多个单词间的语义关系。此类方法的主要不足是结果依赖于知识库，知识库的大小直接影响了词汇链的好坏。另一类方法是基于统计的方法。作者借鉴了Remus和Biemann旧。提出的采用LDA自动抽取词汇链的方法。LDA话题模型是一个基于文本生成的概率模型，其目标是从大规模文档中揭示文档内部的相关隐藏结构。基本思想是将每一个文档表示为话题概率分布，每个话题表示单词概率分布。采用LDA话题模型来建立词汇的语义关联度，并用它自动构建词汇链。在提出的模型中，目标单词的

12、上下文实例代替话题模型中的文档。词汇链被看作话题，所有共享同一话题的单词构成一条词汇链。词汇链通常从篇章和文本中抽取，它们的话题分布是相同的。然而，实验中的上下文实例从不同的文本中抽取出，它们的话题分布是不同的。因此，不能简单把共享同一话题的单词构成一条词汇链，而是必须同时考虑单词与上下文的话题分布。即当训练完LDA模型后，同时使用了文档话题分布0。=p(z d)，话题单词分布妒。=P(W I石)和单词的抽样话题。下面的算法描述了词汇链抽取过程。在算法中，为了保证词汇链的质量，需过滤掉那些生成概率小于阀值7的单词，可用式(1)表示：P(彬，d z)p(z d)p(W z)y (1)阀值y直接影

13、响了模型的评估结果，在第26节将对其进行详细的分析。需要说明的是，研究的词汇链没有方向性，是无向链。采用无向链把话题相关的单词所在句子连成一条超边能较直观地表示构建超边的过程。算法词汇链抽取算法输入：training set D of target word，hyper-parameters of LDA model；semantic threshold y。输出：lexical chain set S。1 日，9，Z+_LDA(D)2 for each topic z3 lc=” lc is a lexical chain4 for each doc d5 for each word W i

14、n doc d6 if(z。=z and P(W，d I彳)y)7 lcadd(埘)8 Sadd(1c)9 return12超图构建图的边通常只连接2个结点。而超图H=(y，万方数据154 四川大学学报(工程科学版) 第48卷E)是图的一种泛化，其边连接多个结点。它比图能更直观表示各类更复杂的数学和计算科学问题。已被广泛应用到各类实际问题I中，如电路设计，数字线性代数、复杂网络、论文引用等。在构建超图时，每一个上下文实例表示一个结点，同一词汇链中单词所在实例构成一条超边。超边的权重对应于词汇链的权重，权重用式(2)表示：p(z di)p(叫i z)W(e)=!LT丁一 (2)l乙l其中，词汇链

15、c对应于超边e，I cI为词汇链的单词个数，z为词汇链的抽样话题。下面给出一个超图构建的实例，初始给定单词“菜单”的7个上下文实例：1)通常会向餐厅索要菜单和酒水价格表。2)服务员向每位客人发放一份菜单。3)客人在iPad显示的菜单上点的菜同步显示到后堂。4)预先选定的菜单，逐道列举菜名。5)可以通过菜单打开设备或储存卡上的所有应用程序。6)Windows 8操作系统取消开始菜单一度被全世界用户吐槽。7)如何显示电脑显示屏上的菜单?一共抽取出4条词汇链(相同下划线的词构成一条词汇链)。分别表示如下(每个词表示为“词群实例序号”)：链1：餐厅#1一服务员舵一客人群2，3；链2：酒水#l一菜名#4

16、；链3：iPad#3一电脑#7；链4：应用程序#5一操作系统#6一电脑#7。图1为所构建的超图。图1中，秽。为第i个实例，ei为第i个词汇链所构建超边。例如，e。为词汇链1中的3个词所对应的实例结点秽。、秽：、口，所构成的超边。图1超图构造实例Fig1 A case of hypergraph construction13超图聚类构造的超图满足“小世界”图属性，即具有高内聚系数和低平均路径长度性质。从另一方面解释，结点的度与给定度的结点数满足分布：P(k)=cka，其中，k为结点的度，P(k)为度为k的结点的频率。图2为动词“add”超图的结点度一频率图。0001001010 lOO结点度图2

17、动词“add”超图的结点度一频率图(口=1)Fig2 VertexS degree-frequency mapping of verb“add”(d=1)超图聚类算法一般分为2类：一类是基于最小分切技术，另一类是基于最大密度。因为“小世界”图结点通常构成高相关联的组块，采用Schype算法一1作超图聚类。Schype算法是基于最大密度的谱聚类算法。最大密度聚类算法是NP难问题，然而根据泛化的PerronFrobenius理论9，任意的超图都存在唯一且符号为正的主特征向量，在线性时间能检索出最大密度子图。该算法主要优点是把超边看作整体进行处理，且不需要预先设置聚类数。其处理过程描述如下：1)先计

18、算主特征向量，检索最大密度子图；2)从超图中去除该子图的超边及结点；3)重复上述步骤直到没有结点在超图中。由于该算法常常生成许多细粒度的类，使用Tan和Kumaru驯的方法对聚类结果作进一步合并处理。合并时采用以下2个度量方法：内聚度(cohesion)和分离度(separation)。一个类Ci的内聚度定义为：#(e I省，Ye)日(Ci)=型坐生百T一(3)b z其中，#(el z，Ye)为在类ci中包含结点x,y的超边数，I c；I为ci的结点数。2个聚类Ci、Ci的分离度定义为：#(e I石，Ye)s(ci，q)=1一(堕钱万而_)(4)通常把比平均内聚度高的类定义为高内聚类；万方数据

19、第1期 钱涛，等：一个基于超图的词义归纳模型 155如果Ci是q的最低分离度类，则把2个聚类ci和e定义为低分离，反之亦成立。直觉地，具有高内聚、低分离的2个类有非常高的语义相似关系。因此设定如下合并规则：2个高内聚类是低分离，则合并2类，如此循环直到收敛。2实验与评估采用Semeval-2013 WSI【11 o任务来评估及验证提出的模型。21 数据集Semeval-2013 WSI任务的测试数据从美国开放语料库(OANC)抽取，它包含4 806个实例、50个单词，其中，20个名词、20个动词、10个形容词。非监督的训练语料从ukWacH纠语料库中抽取。此外，使用trial数据集作为开发集用

20、于调参。22实现细节训练数据从uKwac中抽取，每个单词抽取1104上下文实例，每个实例包含目标单词的一个句子窗口。此外，实例还选择l104不包含任何目标单词的句子作为辅助语料库。实验采用TreeTagger标注词性，去掉停用词，仅仅考虑名词作为特征；同时，去除与目标单词在整个ukWac语料库中共现频率少于50次的单词。实验时，分别对每个目标单词作LDA训练，训练数据为2104，其中，1104为目标单词实例，1104为辅助实例。具体地，采用JGibbLDA作话题估计与推断，需要调整的参数为：话题数k、文档一话题狄利克雷分布超参仅和话题一单词分布超参口。在实验中分别用如下值测试3个参数：后=1

21、000，1 500，2 000，2 500，Ol=5k，10k，50k和口=0001，001，01。实验结果显示当k=2 000，a=25k，口=0001时能获得最好的实验结果。类似于LDA超参，词汇链抽取算法参数y在区间001，0000 001中进行调参，结果显示当y=0000 1时性能最优。对目标进行词义归纳后，需用归纳词义对每个测试实例中的目标单词进行消歧。消歧处理过程如下：单词的每个词义表示为一个向量，向量元素为训练语料中与目标单词共现的单词，其元素为单词个数。每一个测试实例也表示为一个向量，采用cosin函数计算每个实例与归纳语义间的相似关系，当它大于阀值A时，把该语义作为目标单词的

22、词义。在实验中，A调参为01。23评估度量采用传统的词义消歧(WSD)任务评估，即有监督评估。评估提出3个目标：1)词义检测；2)词义评级；3)与人工标注的一致性度量。每个度量指标如下：1)Jaccard index(JI)：词义检测评估。给定同一实例的2类不同的词义标注集为x和Y，Jaccardy n Vindex度量标注的一致性为号篙。当x和y标注相 A Uj同时，其值最大；当x和y完全不同时，其值最小。2)positionallyweighted KendallS下similarity(WKT)：对词义等级评估。采用Kumar和Vassilvitskii列提出的方法评级打分。3)weig

23、hted normalized discounted cumulative gain(WNDCG)：NDCG140正则化2类评级数据的比较，基于权重的NIK：G则量化2类权重的区别。由于归纳词义集与评测标准词义集在数量和类型是不同的，因此监督评估还包含词义对齐处理。其对齐过程如下：测试实例分成2类且piJil练(映射)集和测试集。首先使用训练集把每个归纳词义对齐到标准词义上，然后用对齐词义来预测测试集，进而给出监督评估结果。在实验中，训练集和测试集按80与20比例划分，评估结果为5次随机划分测试的平均值。24基线研究的第一个基线是表示二元语义关系的普通图(Graph)。其普通图的构建如下：利用

24、LDA的学习结果，把目标单词的每个上下文实例表示为话题向量，利用cosin(z，Y)函数两两计算实例之间的相似度；然后每个实例表示为结点，当相似度大于某一阀值时(在实验中阀值为005)，2结点构造一条边，边的权重为其相似度值。其聚类方法采用陈兴蜀等纠提出的方法。为了同所用的超图聚类算法相比较，实验中也采用了另外2个经典的聚类算法，描述如下：1)normalized hypergraph cut(NHC)NHC算法刚采用基于结点扩充的思想。其目标是获得一个最优划分，使得同一类中的密度是密的而被分割的边权重最小。其主要步骤为：首先，把超图转化为图；然后，采用拉普拉斯算子作谱划分。2)hypergr

25、aph expansion clustering(HEC)HEC【17 3采用基于超边扩充的思想。它采用网络流技术，利用超边和结点的连接信息把超边投影回结点。此外，还比较了Semeval一2013 WSI任务中3个万方数据156 四川大学学报(工程科学版) 第48卷基线和2个评测性能最高的参赛系统。其中，3个基线简要描述如下：1)Baseline MFs最高频率词义基线，把所有测试实例都标注为统计频率最高的词义。2)One sense所有实例都用同一个归纳词义标注。3)One sense per instance(1clinst)为每个实例分配的归纳的唯一主词义。2个参赛系统在Semeval-

26、2013任务评测中都取得了最好的成绩。它们分别是：1)AIKU嵋1：采用基于词汇替代方法。2)UoS心J：利用依存特征，使用Ma】【Ma)【算法进行聚类。25实验结果表1为提出的模型同其他系统在Semeval-2013数据集上的评估结果。同以前的WSD任务一样，MFS基线在Jaccard Index度量即词义检测上超过所有其他系统。然而，大多数系统在词义评级及一致性度量上超过了MFS基线。表1实验结果Tab1 Results of experimentation比较超图与普通图模型，3个超图系统(提出的模型、NHC和HEC)在3项指标都超过了普通图系统Graph。提出的模型与普通图模型相比，其

27、在词义检测与词义评级上有较大提升，分别提升56和64。比较3个超图聚类方法，提出的模型使用的超图聚类方法比较适合小世界图特征。因此在词义检测和词义评级2项指标上都取得了最高分。但在WNDCG指标没有获得较高性能，其主要原因是所提模型所归纳语义粒度更细。在实验中NHC和HEC聚类数设置为10，而提出的模型的平均聚类数达到了318。下一步研究采用更优化的合并策略以减少聚类数目。26分析与讨论用到WSI任务。它们通常把话题看作一个词义。而作者研究的动机是词汇链表示多实例间内在的语义关系，话题被解释为词汇链，话题模型被用来发现词汇链。在实验抽取的训练语料基础上，使用文献18所提的方法来训练LDA模型并

28、进行WSI实验(话题数设置为10)。表2给出该方法与提出的模型的实验结果。表2提出的模型与LDA的评估结果Tab2 Results of experimentation between the proposedmodel and LDA model实验结果显示使用词汇链抓住了高阶语义关系，取得了较好的效果。在模型中，词汇链对性能起着关键的作用。直觉地，当词汇链太长时，高阶关系将混杂着一些噪音；当词汇链太短时，将损失一部分高阶关系。为了检验词汇链的有效性，在实验中对参数y进行了调参，其结果见图3。04000 35003000 2500 200O 150O 1000 0500参数r取值图3词汇链参

29、数y影响Fig3 Impact of lexicon chains parameter y此外，由于话题解释为词汇链，话题数也将影响词汇链的质量。当话题数过多时，词汇链语义粒度太细；当话题数太小，词汇链语义粒度太粗。图4为所提模型在不同话题数下JIF1值的实验结果。0303w 03萎03姐03车0303O 303话题模型，如LDA E-81和HDP E，91，已成功地被应 4衍题数图4所提模型在不同话题数的JI-Fl值JI-F1 of the pr哪髓；ed model in the number of topics万方数据第1期 钱涛，等：一个基于超图的词义归纳模型 1573 结论提出基于词

30、汇链的超图模型求解WSI任务。该模型中，结点表示每个实例，超边表示多实例间的高阶语义关系。同其他基于局部点对关系模型相比较，所提模型从全局的角度抓住了复杂的高阶语义关系。另一方面，采用基于最大密度的超图聚类算法能有效抓住所构建超图满足“小世界”图特性。实验结果显示所提算法的有效性。研究不足之处是虽然使用了词汇链，但没有使用词汇链的方向及位置特征，这将是下一步的主要研究内容。参考文献：1Wang J，Bansal M，Gimpel K，et a1A sense-topic modelfor word sense induction with unsupervised data enrichmen

31、tJTransactions of the Association for Computational Linguistics，2015，3：59712Baskaya O，Sert E，Cirik V，et a1Aiku：Using substitutevectors and co-occurrence modeling for word sense indue-tion and disambiguationCProceedings of the SeventhInternational Workshop on Semantic EvaluationAtlanta：ACL，2013：30030

32、63Widdows D，Dorow BA graph model for unsupervisedlexical acquisitionCProceedings of the 19th Intemational Conference on Computational LinguisticsTaipei：ACL，2002：174Klapaftis I P，Manandhar SWord sense induction usinggraphs of coUoeafionsCProceedings of ECAIGreece：IOS，2008：2983025Bordag SWord sense in

33、duction：Tripletbased clusteringand automatic evaluationCProceedings of the 1 l thConference of the European Chapter of the Association forComputational LinguisticsTrento：ACL，2006：3073116Klapaftis I P，Manandhar SUoy：A hypergraph model forword sense inductiondisambiguationCProceedingsof the 4th Intern

34、ational Workshop on Semantic Evalua-tionsPrague：ACL，2007：4144177Navigli RWord sense disambiguation：A surveyJACMComputing Surveys(CSUR)，2009，41(2)：108Remus S，Biemann CThree knowledge-free methods forautomatic lexical chain extractionCHLTNAACLAtlanta：ACL，2013：9899999Michoel T，Nachtergaele BAlignment a

35、nd integration ofcomplex networks by hypergraphbased spectral clusteringJPhysical Review E，2012，86(5)：05611110Tan P N，Kumar VIntroduction to data miningMNew Jersey：Pearson Education，Limited Ine，20141 1Jurgens D，Klapaftis ISemeval-2013 task 13：Word senseinduction for graded and nongraded sensesCSecon

36、dJoint Conference Oll Lexical and Computational Semantics(SEM)Atlanta：ACL，2013，2：29029912Baroni M，Bernardini S，Ferraresi A，et at-The WaCkywide web：A collection of very large linguistically processed web-crawled corporaJLanguage Resources andEvaluation，2009，43(3)：2092261 3Kumar R，Vassilvitskii SGener

37、alized distances betweenrankingsCProceedings of the 19th International Con-ference on World Wide WebRaleigh：ACM，2010：57 158014Moffat A，Zobel JRankbiased precision for measure-ment of retrieval effectivenessJACM Transactions onInformation Systems(TOIS)，2008，27(1)：215Chen Xingshu，Wu Xiaosong，Wang Wenx

38、ian，et a1Animproved initial cluster centers selection algorithm for K-means based on features correlative degreeJJournal ofSichuan University：Engineering Science Edition，2015，47(1)：1319陈兴蜀，吴小松，王文贤，等基于特征关联度的K-means初始聚类中心优化算法J四川大学学报：工程科学版，2015，47(1)：131916Zhou D，Huang J，SchSlkopf BLearning with hyperg

39、-raphs：Clustering，classification，and embeddingCAd-vances in Neural Information Processing SystemsVaneouver：MIT，2006：1601160817Pu L，Faltings BHypergraph learning with hyperedgeexpansionMMachine Learning and Knowledge Discov-cry in DatabasesBerLin：Springer，2012：41042518Brody s，Lapata MBayesian word se

40、nse inductionElProceedings of the 12th Conference of the EuropeanChapter of the Association for Computational LinguisticsAthens：ACL，2009：10311119Lau J H，Cook P，Baldwin TUnimelb：Topic modellingbased word sense inductionCSecond Joint Conferenceon Lexical and Computational Semantics(+SEM)Atlan，ta：ACL，2013，2：307311(编辑杨蓓)万方数据