基于图方法的命名实体消歧
2015-05-30杨光刘秉权刘铭
杨光 刘秉权 刘铭
摘 要： 名实体歧义是机器对自然语言进行理解时经常遇到的问题，为使机器能够正确地分析自然语言文本，对名实体消除歧义亟待解决。近年来，随着Wikipedia等语义知识库的出现，大量基于知识库的消歧方法被提出。命名实体消歧的任务是将文本中具有多个含义的实体指称去除歧义，并将其链接到知识库中的唯一实体。本文采用DBpedia作为知识库，基于图的方法进行实体消歧。
关键词：实体消歧；图方法；知识库；DBpedia
中图分类号：TP391.41 文献标识号：A 文章编号：2095-2163（2015）04-
Graph-Based Method for Named Entity Disambiguation
YANG Guang， LIU Bingquan， LIU Ming
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）
Abstract： Ambiguity is one of the most common problems in natural language processing. In order to make machine analysis natural language texts correctly， eliminating ambiguity is an urgent problem to be addressed. In recent years， with the emergency of knowledge base such as Wikipedia， there are large amount of method proposed based on knowledge base. The task of named entity disambiguation is to eliminate ambiguity for the mentions which has multiple meanings， and link it to only one entity in knowledge base. This article uses a graph based method， and employs DBpedia as the knowledge base to link.
Keywords： Entity Disambiguation； Graph-Based Method； Knowledge Base； DBpedia
0 引 言
命名实体消歧在自然语言处理应用中发挥着重要的作用，可以有效解决语义网络，信息检索，问答等自然语言处理任务。在信息检索任务中，通过命名实体消歧可以区分具有相同文本表示的不同实体，从而去除不相关实体的信息，提高准确率。通过识别特定的实体，可以从大量文本中抽取某一特定实体的信息，对知识库中实体的内容进行扩展。
命名实体消歧的任务是，对于文本中给定的实体指称，找到知识库中对应的词条。实体指称是需要进行消歧的名实体字符串。例如下面这样一句话：
Michael Jordan plays basketball in Bulls.
该句话中的Jordan和Bulls就是实体指称，实体指称的获得需要命名实体识别步骤来实现，本文专注于实体消歧，命名实体识别部分不再赘述。由于实体的多义性，例如Michael Jordan，在搜索引擎的结果中即有篮球运动员Michael Jeffrey Jordan，又有伯克利教授Michael I. Jordan。如何从大量的候选实体中识别出正确的实体是实体消歧任务面临的挑战。
实体消歧的基本步骤是：首先，根据实体指称字符串，在知识库中获取候选实体。然后，对候选进行排序，将实体指称链接到最有可能的候选实体。
实体消歧的方法大致分为两种类别，一种是单实体消歧方法，一次对文本中的一个实体指称进行消歧，而不考虑同一文本中其他实体指称对其的影响。这种方法通常采用实体指称所在的上下文文本的局部特征和知识库中候选实体的描述文本进行比较。Bunescu[1]提出了一种根据实体指称的上下文文本和候选实体的维基百科类别的相似度进行实体消歧的方法。Zheng[2]采用了learning-to-rank方法将实体指称链接到最有可能的候选实体。
除了单实体消歧方法，另一类为整体消歧方法。由于同一文本中共现的实体往往基于同一个主题，或者具有某种相关性，所以这种方法假设在同一篇文本中的不同实体指称的消歧决策互相之间具有依赖性。由于要对实体之间的依赖性进行建模，在对某个实体进行消歧操作时会考虑到其他实体的影响。Cucerzan[3]最先采用了该方法，在方法中使用了不同实体指称的候选实体之间的语义相关度来衡量候选实体的内聚性，语义相关度采用的是候选之间的维基百科类别的重叠程度。Alhelbawy[4]使用隐马尔科夫模型来建模实体指称的候选之间的依赖性。整体消歧方法中有一类较为常用的方法是图方法，Han[5]构造了一种称为指示图（referent graph）的图模型，其中图节点为所有实体指称和所有候选实体；图的边分为两类，一类是实体指称和其对应的候选实体之间的边，权重为实体指称和候选实体的局部文本相似度。另一类是候选实体之间的边，权重为候选实体之间的语义相关度。本文所使用的实体消歧方法也是一种图方法。
本文接下来的内容安排如下：提出一种基于知识库的候选生成方法，在保证候选有较高的覆盖率的情况下，维持较少的候选数目。基于图方法的实体消歧方法，采用pagerank模型，从候选实体中排序选择出最有可能的实体。
1 知识库介绍
本文采用2014年的DBpedia归档作为实体消歧的知识库。这是DBpedia[6]社区通过语义网络和链接数据技术（Linked Data Technology）抽取自维基百科的多语言知识库。本文使用的是英文版本，英文版本的DBpedia实体数目，链接信息最为丰富，大概包括5亿的事实，和450万事物。DBpedia由一系列分散的数据集构成，不同的数据集抽取自维基百科页面的不同部分，在实体消歧任务中具有不同的作用。
1.1 知识库数据选择
候选生成步骤要通过实体指称产生可能的候选实体集合，使用的数据集包括labels_en.nt，disambiguations_en.nt，redirects_en.nt，pagelinks_en.nt。实体消歧步骤主要使用图方法，需要实体之间的链接关系，采用pagelinks_en.nt数据集。
labels_.nt内容为维基百科标题，也就是实体的名称字符串，可以用于和实体指称计算字符串的编辑距离来确定是否被选择为候选实体。
知识库中的同一个实体在现实文本中可以有多种不同的字符串表示，比如，实体Micheal Jordan字面形式有Michael Jeffery Jordan，Michael Air Jordan，His Airness等，这些字面形式通常是一些缩写，别名等。redirect_en.nt即重定向文件，具体作用是将这些别称转化为较为常用或更规范的实体字符串。文本中的实体指称字符串通常会出现实体的多种字面形式，可以利用重定向找到更为规范的形式。例如，将文本中的His Airness重定向为Michael Jordan就可以获得更为丰富的链接信息，这有利于在接下来的探讨中展开基于图方法的实体消歧过程。
disambiguation_en.nt即消歧文件，可以用于不同的实体具有相同的实体字符串的情况下。例如LDA可以对应的实体有Latent_Dirichlet_Allocation ，Linear_Discriminant_Analysisi ，Legal_Drincking_Age。消歧文件可以在实体指称含义模糊的情况下获得同一个实体指称具有不同含义的候选实体。
pagelinks_en.nt即网页链接文件，存储了维基百科网页的入链出链信息。
1.2 知识库数据预处理
维基百科数据集以三元组文件的形式存储，例如在redirect.nt数据集中的某行数据如下所示（这里分三行表示）：
该三元组包括两个实体，实体
AfghanistanMilitary Afghan_Armed_Forces
该数据行表示AfghanistanMilitary可以重定向为Afghan_Armed_Forces。所有采用的数据集均按照以上方法进行预处理。数据集的统计信息如表1所示。
2候选生成
候选生成部分在实体消歧任务中具有重要的作用。如果在候选生成步骤，实体指称的候选实体数目为0，或者候选集合中没有覆盖到正确的候选实体，在接下来的消歧阶段就不可能得到正确的结果。所以候选生成步骤要有较高的召回率要求。另一方面，如果候选实体过多，会加重消歧步骤的计算复杂度，影响效率。候选生成需要在覆盖率和候选数目之间进行综合的考量。
2.1 基于实体名称字符串编辑距离的方法
首先再用最简单的候选生成方法，即通过字符串与实体名称的编辑距离产生候选。两个字符串的编辑距离是指其中一个字符串通过插入、删除、替换三种操作转化为另外一个字符串的步骤数目。对于生成候选，编辑距离的阈值越大，候选集合覆盖率越高，但是候选数目也会越大。我们随机选择了十个英文人名，所采用的编辑距离和产生总的候选数目如图1所示。
仅仅使用知识库中实体名称字符串与实体指称之间的编辑距离的情况下，通过调整编辑距离的大小，当候选实体覆盖目标实体的召回率达到83%时，平均候选数目达到了5 016，候选数目过于庞大，会加重实体消歧的负担。下面研究将主要采用知识库中的消歧、重定向、链接数据集，编辑距离作为辅助来实现候选生成。
2.2 基于实体消歧重定向信息的方法
对于候选生成的方法，可以受启发于搜索维基百科词条的过程。当发声搜索的词条具有歧义的情况下，维基百科则将进一步导航到消歧页面，然后在消歧页面查找目标实体。或者如果输入的词条是目标实体的别称，维基百科将会直接查询重定向到目标实体。当所输入的词条和目标实体一致且没有歧义的情况下，即可直接查找到目标实体。在此可以通过重定向，消歧数据集模仿以上过程。候选生成结果对比则如表2所示。
由于实体链接任务中有大量的实体指称的目标实体具有和实体指称相同的字符串表示，除了消歧和重定向数据集以外，通过label_en.nt添加和实体指称相同的候选实体会增加候选实体的覆盖率。此外通过分析未被覆盖的实体，例如实体指称Good_Doctor和其目标实体Ron_Paul，通过重定向或者消歧不能直接找到目标实体。而Good_Docter可以重定向到The_Good_Docter，对重定向之后的The_Good_Docter进行再次使用消歧数据集可以得到目标实体，所以最终加入一些启发式的规则，可以在之前的覆盖率的基础上提升1%左右。
3 实体消歧
实体消歧的目标是根据实体指称和对应的候选实体集合找到一组最有可能的实体组合分配给实体指称。本节采用图方法进行实体消歧，图方法认为同一文本中的实体具有一定的内聚性，在实体消歧的过程中，同一文本中的实体为其他实体互相提供消歧信息。研究中将所有实体指称的候选实体作为图的节点，通过对节点进行拓展，并将其连接起来，构成图模型，在此基礎上采用消歧算法为实体指称选择出一组最有可能的实体组合。
3.1 图模型的结构
通过候选生成步骤已经获得了所有实体指称的候选实体，这些候选实体将作为点出现在消歧的图结构上面。而如何将这些点连成图，则是本节即将讨论的问题。
对于一篇文档中的实体指称集合M={m1，m2，m3，m4…mk}中的任意实体指称Mi，存在一个候选实体列表Ci={ci1，ci2，ci3，…cij}，如果在pagelinks中存在直接从实体cij到实体cmn的链接，该链接视为长度为1的路径，表示为cij->cmn。如果存在实体cij到实体X的链接，以及实体X到实体cmn的链接，则意指cij到cmn之间存在长度为2的路径，表示为cij->X->cmn，其中X为拓展得出的中间实体。为此，通过深度优先遍历pagelinks_en.nt找到从cij到cmn的所有路径，其中i≠m，且路经长度为1或2。最终这些路径将候选实体连接成图。
最终产生的图模型为G=（V，E），其中V是所有候选实体以及拓展之后的中间实体的集合，E是不同实体指称候选实体之间的边或实体指称和中间实体的边的集合。任何两个候选实体之间的路径长度不超过2。之所以限制候选实体之间的距离，一方面是考虑到实体消歧的效率，每个候选实体经过一步拓展可能链接到上百相邻的候选实体，每个拓展出的相邻实体又可以进一步向外拓展，这样拓展到第三步，最终构成的图节点会非常多，将会影响接下来消歧步骤的效率；另一方面，是考虑到实体关系的发散。候选实体之间的路径越长，相互之间的关联也就越弱。
图模型的示意图如图2所示，A、B、C表示实体指称（注意，这里为了表示实体指称和候选实体的关系，最终图模型中并不包括实体指称节点），与其直接相连的是各自的候选实体，此外的即为中间实体。由于不同的实体指称可能具有相同的候选实体，每个候选实体是以（实体指称，候选实体）的结构进行相应表示。
3.2 实体消歧算法
在此，使用上节的示意图为例。实体指称的候选词典可以表示为：
dic={A：[A1，A2，A3]，B：[B1，B2]，C：[C1，C2，C3，C4]}
算法的目的是找到一组[Ax，Bx，Cx]使得 P（A=Ax，B=Bx，C=Cx）取得最大值。内聚性最高的一组候选实体最有可能是实体指称对应的实体分配。而候选实体之间的内聚性又表现为实体之间链接的丰富程度。我们使用消歧图中候选实体的Pagerank[7]值作为候选实体链接丰富程度的衡量。
算法使用两种策略为实体指称选择实体。一种是对候选实体构成的图进行pagerank，从各个实体指称的候选实体集合中选择一个pagerank值最高的候选实体。另一种策略是，每次通过pagerank选择出得分最高的候选实体，将其选择为对应的实体指称的实体。并移除相应实体指称的其它候选实体，在剩下的子图中再次通过pagerank选择出得分最高的实体，选择为实体指称的对应实体。直到确认所有实体指称为止。策略2算法如表3所示。
实验数据集采用KBP2014评测数据集，数据集中包括465篇文档，其中共有11 670个待消歧的实体指称。实验结果如下，消歧图模型采用了不同的候选实体间的路径长度和排序策略。表4是实验结果的准确率信息。
实验结果可以看出，路径长度为2的情况下消歧的准确率较路径为1时有显著的提高，路径长度为2的图中添加路径长度为1的边并没有使准确率有明显的提高。原因可能是候选实体之间具有长度为1的路径的候选实体之间往往也有具有长度为2的路径。有长度为2的路径的实体对却未必有长度为1的路径。候选实体间路径长为2的路径数目应该是远多于路径长为1的路径数目，从而提供了更多的消歧信息。
对于多次pagerank方法，由于每次会把本次pagerank选择出的实体进行保留，参与到下一次pagerank当中。如果第一次选择出来的是错误的实体，错误信息会向后传递。在图中路经长度为1的情况下，由于实体间的链接信息较少，效果并不好。但随着边数的增多，效果会略好于第一种方法。
4 结束语
本文针对实体消歧任务采用了一种基于图的消歧方法。该方法利用知识库中的实体之间的链接信息构成候选实体之间的关联图，在该图的基础上使用Pagerank，为实体指称选择最有可能的候选实体。文章提出了两种通过排序选择候选的策略，并分析了路径长度对实体消歧准确率的影响。
参考文献：
[1] BUNESCU R C， PASCA M. Using encyclopedic knowledge for named entity disambiguation[C]//11th Conference of the European Chapter of the Association for Computational Linguistics. Trento， Italy：ACL， 2006， 6： 9-16.
[2] ZHENG Z， LI F， HUANG M， et al. Learning to link entities with knowledge base[C]//Human Language Technologies： The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics， Los Angeles：ACL， 2010： 483-491.
[3] CUCERZAN S. Large-scale named entity disambiguation based on Wikipedia data[C]//Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning， Prague：ACL， 2007：708--716.
[4] ALHELBAWY A， GAIZAUSKAS R. Named entity disambiguation using HMMs[C]// 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence （WI） and Intelligent Agent Technologies （IAT）， Atlanta：IEEE Computer Society， 2013：159-162.
[5] HAN X， SUN L， ZHAO J. Collective entity linking in web text： a graph-based method[C]//Proceedings of the 34th international ACM SIGIR Conference on Research & Development in Information Retrieval， Beijing：ACM， 2011：765-774.
[6] MORSEY M， LEHMANN J， AUER S， et al. Dbpedia and the live extraction of structured data from wikipedia[J]. Program， 2012， 46（2）： 157-181.
[7] AUTHORS U. The pagerank citation ranking： Bringing order to the Web[J]. Lecture Notes in Engineering， 1998， 9（1）：1-14.
