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

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

關(guān)鍵詞：實(shí)體消歧；圖方法；知識(shí)庫(kù)；DBpedia

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)號(hào)：A 文章編號(hào)：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 引 言

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

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

Michael Jordan plays basketball in Bulls.

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

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

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

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

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

1 知識(shí)庫(kù)介紹

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

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

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

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

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

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

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

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

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

.

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

AfghanistanMilitary Afghan_Armed_Forces

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

2候選生成

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

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

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

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

2.2 基于實(shí)體消歧重定向信息的方法

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

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

3 實(shí)體消歧

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

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

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

對(duì)于一篇文檔中的實(shí)體指稱集合M={m1，m2，m3，m4…mk}中的任意實(shí)體指稱Mi，存在一個(gè)候選實(shí)體列表Ci={ci1，ci2，ci3，…cij}，如果在pagelinks中存在直接從實(shí)體cij到實(shí)體cmn的鏈接，該鏈接視為長(zhǎng)度為1的路徑，表示為cij->cmn。如果存在實(shí)體cij到實(shí)體X的鏈接，以及實(shí)體X到實(shí)體cmn的鏈接，則意指cij到cmn之間存在長(zhǎng)度為2的路徑，表示為cij->X->cmn，其中X為拓展得出的中間實(shí)體。為此，通過(guò)深度優(yōu)先遍歷pagelinks_en.nt找到從cij到cmn的所有路徑，其中i≠m，且路經(jīng)長(zhǎng)度為1或2。最終這些路徑將候選實(shí)體連接成圖。

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

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

3.2 實(shí)體消歧算法

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

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)聚性最高的一組候選實(shí)體最有可能是實(shí)體指稱對(duì)應(yīng)的實(shí)體分配。而候選實(shí)體之間的內(nèi)聚性又表現(xiàn)為實(shí)體之間鏈接的豐富程度。我們使用消歧圖中候選實(shí)體的Pagerank[7]值作為候選實(shí)體鏈接豐富程度的衡量。

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

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

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

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

4 結(jié)束語(yǔ)

本文針對(duì)實(shí)體消歧任務(wù)采用了一種基于圖的消歧方法。該方法利用知識(shí)庫(kù)中的實(shí)體之間的鏈接信息構(gòu)成候選實(shí)體之間的關(guān)聯(lián)圖，在該圖的基礎(chǔ)上使用Pagerank，為實(shí)體指稱選擇最有可能的候選實(shí)體。文章提出了兩種通過(guò)排序選擇候選的策略，并分析了路徑長(zhǎng)度對(duì)實(shí)體消歧準(zhǔn)確率的影響。

參考文獻(xiàn)：

[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.