基于圖方法的命名實體消歧

楊光　劉秉權(quán)　劉銘

摘 要： 名實體歧義是機器對自然語言進行理解時經(jīng)常遇到的問題，為使機器能夠正確地分析自然語言文本，對名實體消除歧義亟待解決。近年來，隨著Wikipedia等語義知識庫的出現(xiàn)，大量基于知識庫的消歧方法被提出。命名實體消歧的任務(wù)是將文本中具有多個含義的實體指稱去除歧義，并將其鏈接到知識庫中的唯一實體。本文采用DBpedia作為知識庫，基于圖的方法進行實體消歧。

關(guān)鍵詞：實體消歧；圖方法；知識庫；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 引 言

命名實體消歧在自然語言處理應(yīng)用中發(fā)揮著重要的作用，可以有效解決語義網(wǎng)絡(luò)，信息檢索，問答等自然語言處理任務(wù)。在信息檢索任務(wù)中，通過命名實體消歧可以區(qū)分具有相同文本表示的不同實體，從而去除不相關(guān)實體的信息，提高準確率。通過識別特定的實體，可以從大量文本中抽取某一特定實體的信息，對知識庫中實體的內(nèi)容進行擴展。

命名實體消歧的任務(wù)是，對于文本中給定的實體指稱，找到知識庫中對應(yīng)的詞條。實體指稱是需要進行消歧的名實體字符串。例如下面這樣一句話：

Michael Jordan plays basketball in Bulls.

該句話中的Jordan和Bulls就是實體指稱，實體指稱的獲得需要命名實體識別步驟來實現(xiàn)，本文專注于實體消歧，命名實體識別部分不再贅述。由于實體的多義性，例如Michael Jordan，在搜索引擎的結(jié)果中即有籃球運動員Michael Jeffrey Jordan，又有伯克利教授Michael I. Jordan。如何從大量的候選實體中識別出正確的實體是實體消歧任務(wù)面臨的挑戰(zhàn)。

實體消歧的基本步驟是：首先，根據(jù)實體指稱字符串，在知識庫中獲取候選實體。然后，對候選進行排序，將實體指稱鏈接到最有可能的候選實體。

實體消歧的方法大致分為兩種類別，一種是單實體消歧方法，一次對文本中的一個實體指稱進行消歧，而不考慮同一文本中其他實體指稱對其的影響。這種方法通常采用實體指稱所在的上下文文本的局部特征和知識庫中候選實體的描述文本進行比較。Bunescu[1]提出了一種根據(jù)實體指稱的上下文文本和候選實體的維基百科類別的相似度進行實體消歧的方法。Zheng[2]采用了learning-to-rank方法將實體指稱鏈接到最有可能的候選實體。

除了單實體消歧方法，另一類為整體消歧方法。由于同一文本中共現(xiàn)的實體往往基于同一個主題，或者具有某種相關(guān)性，所以這種方法假設(shè)在同一篇文本中的不同實體指稱的消歧決策互相之間具有依賴性。由于要對實體之間的依賴性進行建模，在對某個實體進行消歧操作時會考慮到其他實體的影響。Cucerzan[3]最先采用了該方法，在方法中使用了不同實體指稱的候選實體之間的語義相關(guān)度來衡量候選實體的內(nèi)聚性，語義相關(guān)度采用的是候選之間的維基百科類別的重疊程度。Alhelbawy[4]使用隱馬爾科夫模型來建模實體指稱的候選之間的依賴性。整體消歧方法中有一類較為常用的方法是圖方法，Han[5]構(gòu)造了一種稱為指示圖（referent graph）的圖模型，其中圖節(jié)點為所有實體指稱和所有候選實體；圖的邊分為兩類，一類是實體指稱和其對應(yīng)的候選實體之間的邊，權(quán)重為實體指稱和候選實體的局部文本相似度。另一類是候選實體之間的邊，權(quán)重為候選實體之間的語義相關(guān)度。本文所使用的實體消歧方法也是一種圖方法。

本文接下來的內(nèi)容安排如下：提出一種基于知識庫的候選生成方法，在保證候選有較高的覆蓋率的情況下，維持較少的候選數(shù)目?；趫D方法的實體消歧方法，采用pagerank模型，從候選實體中排序選擇出最有可能的實體。

1 知識庫介紹

本文采用2014年的DBpedia歸檔作為實體消歧的知識庫。這是DBpedia[6]社區(qū)通過語義網(wǎng)絡(luò)和鏈接數(shù)據(jù)技術(shù)（Linked Data Technology）抽取自維基百科的多語言知識庫。本文使用的是英文版本，英文版本的DBpedia實體數(shù)目，鏈接信息最為豐富，大概包括5億的事實，和450萬事物。DBpedia由一系列分散的數(shù)據(jù)集構(gòu)成，不同的數(shù)據(jù)集抽取自維基百科頁面的不同部分，在實體消歧任務(wù)中具有不同的作用。

1.1 知識庫數(shù)據(jù)選擇

候選生成步驟要通過實體指稱產(chǎn)生可能的候選實體集合，使用的數(shù)據(jù)集包括labels_en.nt，disambiguations_en.nt，redirects_en.nt，pagelinks_en.nt。實體消歧步驟主要使用圖方法，需要實體之間的鏈接關(guān)系，采用pagelinks_en.nt數(shù)據(jù)集。

labels_.nt內(nèi)容為維基百科標題，也就是實體的名稱字符串，可以用于和實體指稱計算字符串的編輯距離來確定是否被選擇為候選實體。

知識庫中的同一個實體在現(xiàn)實文本中可以有多種不同的字符串表示，比如，實體Micheal Jordan字面形式有Michael Jeffery Jordan，Michael Air Jordan，His Airness等，這些字面形式通常是一些縮寫，別名等。redirect_en.nt即重定向文件，具體作用是將這些別稱轉(zhuǎn)化為較為常用或更規(guī)范的實體字符串。文本中的實體指稱字符串通常會出現(xiàn)實體的多種字面形式，可以利用重定向找到更為規(guī)范的形式。例如，將文本中的His Airness重定向為Michael Jordan就可以獲得更為豐富的鏈接信息，這有利于在接下來的探討中展開基于圖方法的實體消歧過程。

disambiguation_en.nt即消歧文件，可以用于不同的實體具有相同的實體字符串的情況下。例如LDA可以對應(yīng)的實體有Latent_Dirichlet_Allocation ，Linear_Discriminant_Analysisi ，Legal_Drincking_Age。消歧文件可以在實體指稱含義模糊的情況下獲得同一個實體指稱具有不同含義的候選實體。

pagelinks_en.nt即網(wǎng)頁鏈接文件，存儲了維基百科網(wǎng)頁的入鏈出鏈信息。

1.2 知識庫數(shù)據(jù)預(yù)處理

維基百科數(shù)據(jù)集以三元組文件的形式存儲，例如在redirect.nt數(shù)據(jù)集中的某行數(shù)據(jù)如下所示（這里分三行表示）：

.

該三元組包括兩個實體，實體和實體，以及兩者之間存在的關(guān)系。三元組包括主語、謂語、賓語三元素。上例中兩個實體充當(dāng)三元組的主語賓語，而關(guān)系充當(dāng)?shù)氖侵^語。由于同一個數(shù)據(jù)集中的三元組具有相同的謂語，可將謂語部分省略，并將實體的前綴http：//dbpedia.org/resource/去除，減少知識庫占用的空間。上述三元組數(shù)據(jù)行預(yù)處理之后結(jié)果如下：

AfghanistanMilitary Afghan_Armed_Forces

該數(shù)據(jù)行表示AfghanistanMilitary可以重定向為Afghan_Armed_Forces。所有采用的數(shù)據(jù)集均按照以上方法進行預(yù)處理。數(shù)據(jù)集的統(tǒng)計信息如表1所示。

2候選生成

候選生成部分在實體消歧任務(wù)中具有重要的作用。如果在候選生成步驟，實體指稱的候選實體數(shù)目為0，或者候選集合中沒有覆蓋到正確的候選實體，在接下來的消歧階段就不可能得到正確的結(jié)果。所以候選生成步驟要有較高的召回率要求。另一方面，如果候選實體過多，會加重消歧步驟的計算復(fù)雜度，影響效率。候選生成需要在覆蓋率和候選數(shù)目之間進行綜合的考量。

2.1 基于實體名稱字符串編輯距離的方法

首先再用最簡單的候選生成方法，即通過字符串與實體名稱的編輯距離產(chǎn)生候選。兩個字符串的編輯距離是指其中一個字符串通過插入、刪除、替換三種操作轉(zhuǎn)化為另外一個字符串的步驟數(shù)目。對于生成候選，編輯距離的閾值越大，候選集合覆蓋率越高，但是候選數(shù)目也會越大。我們隨機選擇了十個英文人名，所采用的編輯距離和產(chǎn)生總的候選數(shù)目如圖1所示。

僅僅使用知識庫中實體名稱字符串與實體指稱之間的編輯距離的情況下，通過調(diào)整編輯距離的大小，當(dāng)候選實體覆蓋目標實體的召回率達到83%時，平均候選數(shù)目達到了5 016，候選數(shù)目過于龐大，會加重實體消歧的負擔(dān)。下面研究將主要采用知識庫中的消歧、重定向、鏈接數(shù)據(jù)集，編輯距離作為輔助來實現(xiàn)候選生成。

2.2 基于實體消歧重定向信息的方法

對于候選生成的方法，可以受啟發(fā)于搜索維基百科詞條的過程。當(dāng)發(fā)聲搜索的詞條具有歧義的情況下，維基百科則將進一步導(dǎo)航到消歧頁面，然后在消歧頁面查找目標實體?；蛘呷绻斎氲脑~條是目標實體的別稱，維基百科將會直接查詢重定向到目標實體。當(dāng)所輸入的詞條和目標實體一致且沒有歧義的情況下，即可直接查找到目標實體。在此可以通過重定向，消歧數(shù)據(jù)集模仿以上過程。候選生成結(jié)果對比則如表2所示。

由于實體鏈接任務(wù)中有大量的實體指稱的目標實體具有和實體指稱相同的字符串表示，除了消歧和重定向數(shù)據(jù)集以外，通過label_en.nt添加和實體指稱相同的候選實體會增加候選實體的覆蓋率。此外通過分析未被覆蓋的實體，例如實體指稱Good_Doctor和其目標實體Ron_Paul，通過重定向或者消歧不能直接找到目標實體。而Good_Docter可以重定向到The_Good_Docter，對重定向之后的The_Good_Docter進行再次使用消歧數(shù)據(jù)集可以得到目標實體，所以最終加入一些啟發(fā)式的規(guī)則，可以在之前的覆蓋率的基礎(chǔ)上提升1%左右。

3 實體消歧

實體消歧的目標是根據(jù)實體指稱和對應(yīng)的候選實體集合找到一組最有可能的實體組合分配給實體指稱。本節(jié)采用圖方法進行實體消歧，圖方法認為同一文本中的實體具有一定的內(nèi)聚性，在實體消歧的過程中，同一文本中的實體為其他實體互相提供消歧信息。研究中將所有實體指稱的候選實體作為圖的節(jié)點，通過對節(jié)點進行拓展，并將其連接起來，構(gòu)成圖模型，在此基礎(chǔ)上采用消歧算法為實體指稱選擇出一組最有可能的實體組合。

3.1 圖模型的結(jié)構(gòu)

通過候選生成步驟已經(jīng)獲得了所有實體指稱的候選實體，這些候選實體將作為點出現(xiàn)在消歧的圖結(jié)構(gòu)上面。而如何將這些點連成圖，則是本節(jié)即將討論的問題。

對于一篇文檔中的實體指稱集合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為拓展得出的中間實體。為此，通過深度優(yōu)先遍歷pagelinks_en.nt找到從cij到cmn的所有路徑，其中i≠m，且路經(jīng)長度為1或2。最終這些路徑將候選實體連接成圖。

最終產(chǎn)生的圖模型為G=（V，E），其中V是所有候選實體以及拓展之后的中間實體的集合，E是不同實體指稱候選實體之間的邊或?qū)嶓w指稱和中間實體的邊的集合。任何兩個候選實體之間的路徑長度不超過2。之所以限制候選實體之間的距離，一方面是考慮到實體消歧的效率，每個候選實體經(jīng)過一步拓展可能鏈接到上百相鄰的候選實體，每個拓展出的相鄰實體又可以進一步向外拓展，這樣拓展到第三步，最終構(gòu)成的圖節(jié)點會非常多，將會影響接下來消歧步驟的效率；另一方面，是考慮到實體關(guān)系的發(fā)散。候選實體之間的路徑越長，相互之間的關(guān)聯(lián)也就越弱。

圖模型的示意圖如圖2所示，A、B、C表示實體指稱（注意，這里為了表示實體指稱和候選實體的關(guān)系，最終圖模型中并不包括實體指稱節(jié)點），與其直接相連的是各自的候選實體，此外的即為中間實體。由于不同的實體指稱可能具有相同的候選實體，每個候選實體是以（實體指稱，候選實體）的結(jié)構(gòu)進行相應(yīng)表示。

3.2 實體消歧算法

在此，使用上節(jié)的示意圖為例。實體指稱的候選詞典可以表示為：

dic={A：[A1，A2，A3]，B：[B1，B2]，C：[C1，C2，C3，C4]}

算法的目的是找到一組[Ax，Bx，Cx]使得 P（A=Ax，B=Bx，C=Cx）取得最大值。內(nèi)聚性最高的一組候選實體最有可能是實體指稱對應(yīng)的實體分配。而候選實體之間的內(nèi)聚性又表現(xiàn)為實體之間鏈接的豐富程度。我們使用消歧圖中候選實體的Pagerank[7]值作為候選實體鏈接豐富程度的衡量。

算法使用兩種策略為實體指稱選擇實體。一種是對候選實體構(gòu)成的圖進行pagerank，從各個實體指稱的候選實體集合中選擇一個pagerank值最高的候選實體。另一種策略是，每次通過pagerank選擇出得分最高的候選實體，將其選擇為對應(yīng)的實體指稱的實體。并移除相應(yīng)實體指稱的其它候選實體，在剩下的子圖中再次通過pagerank選擇出得分最高的實體，選擇為實體指稱的對應(yīng)實體。直到確認所有實體指稱為止。策略2算法如表3所示。

實驗數(shù)據(jù)集采用KBP2014評測數(shù)據(jù)集，數(shù)據(jù)集中包括465篇文檔，其中共有11 670個待消歧的實體指稱。實驗結(jié)果如下，消歧圖模型采用了不同的候選實體間的路徑長度和排序策略。表4是實驗結(jié)果的準確率信息。

實驗結(jié)果可以看出，路徑長度為2的情況下消歧的準確率較路徑為1時有顯著的提高，路徑長度為2的圖中添加路徑長度為1的邊并沒有使準確率有明顯的提高。原因可能是候選實體之間具有長度為1的路徑的候選實體之間往往也有具有長度為2的路徑。有長度為2的路徑的實體對卻未必有長度為1的路徑。候選實體間路徑長為2的路徑數(shù)目應(yīng)該是遠多于路徑長為1的路徑數(shù)目，從而提供了更多的消歧信息。

對于多次pagerank方法，由于每次會把本次pagerank選擇出的實體進行保留，參與到下一次pagerank當(dāng)中。如果第一次選擇出來的是錯誤的實體，錯誤信息會向后傳遞。在圖中路經(jīng)長度為1的情況下，由于實體間的鏈接信息較少，效果并不好。但隨著邊數(shù)的增多，效果會略好于第一種方法。

4 結(jié)束語

本文針對實體消歧任務(wù)采用了一種基于圖的消歧方法。該方法利用知識庫中的實體之間的鏈接信息構(gòu)成候選實體之間的關(guān)聯(lián)圖，在該圖的基礎(chǔ)上使用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.