李子茂，聶夢妍，尹帆，陳思敏

(中南民族大學 計算機科學學院,武漢 430074)

實體鏈接是實體消歧的基本過程[1]，目的是將文本中出現(xiàn)的實體指稱鏈接到維基百科等結構化知識庫.實體指稱的歧義性是指同一個實體指稱在不同的上下文語境中可能指代不同的實體對象. 實體消歧的本質是比較實體指稱與候選實體的語義相似性.針對樣例：

“一首《李白》用鄉(xiāng)村搖滾風的率性旋律，寫出李榮浩對隨性生活的向往.”

我們依據“旋律”一詞便能判斷出這里的實體指稱“李白”與候選實體“李白(歌曲)”的相似度比候選實體“李白(唐代詩人)”更高，從而將實體指稱“李白”鏈接到知識庫中的“李白(歌曲)”.

考慮到出現(xiàn)在同一文本的實體具有全局的語義一致性[2]問題，實體指稱與候選實體之間語義相似性可被分為實體指稱與候選實體之間的文本相似性以及候選實體之間的語義關聯(lián)性.

在衡量實體指稱和候選實體之間的文本相似性方面，最先被提出的詞袋模型用一組無序的詞來表達一個文檔，利用上下文語境信息與候選實體的單詞重疊率來表示候選實體的上下文相似度[3].也有研究利用向量空間模型(VSM)將上下文語境信息和候選實體分別表示為高維上下文向量和候選實體向量，利用點積或余弦相似度計算它們之間的相似度[4].最近一些研究結合深度學習的思想提出了Word2Vec模型，將實體指稱、上下文信息和候選實體分別用分布式向量表示[5]，然后利用余弦相似度等距離衡量方法計算上下文相似度.

在考慮候選實體之間的語義關聯(lián)性方面，HOFFART等使用貪心算法在圖模型中尋找最小強連通圖對實體進行消歧[6].HAN等提出一種集體推理算法，利用實體指稱和所有候選實體作為節(jié)點構成的依賴圖捕獲圖中節(jié)點的相互依賴關系，共同推斷出所有指稱的實體[7].ALHELBAWY等使用PageRank算法將候選實體節(jié)點的首次排序結果與初始置信度動態(tài)結合，進行第二次排序以完成實體消歧的任務[8].近期相關研究進一步考慮了知識圖譜中實體之間的最短路徑，HULPUS等基于圖的相關性計算實體之間的最短路徑來對實體進行消歧[9]，取得了較高的準確率.ZHU等使用互信息為最短路徑長度加權來分析知識圖譜中實體間的相似性[10]，取得了良好效果.

上述方法在進行實體消歧時取得了不錯的效果，但是在使用最短路徑評估候選實體之間的一致性時，忽略了實體間的最短路徑的不對稱性問題，即從實體A到實體B的最短路徑長度與從實體B到實體A的最短路徑長度不相等.

本文針對命名實體的歧義消解，在PageRank算法的基礎上提出一種利用雙向表示兩個實體之間的最短路徑，聯(lián)合實體間的語義相似性構建實體相關圖模型，進一步結合上下文信息與候選實體的文本相似性進行鏈接的實體消歧算法，稱為基于雙向語義關聯(lián)的實體消歧算法(BSAED，Bidirectional Semantic Associations for Entity Disambiguation).

1 雙向語義實體消歧算法

1.1 數據預處理

本文只針對人名、地名、組織機構名3種類型的命名實體進行消歧.對任意一個給定的文本D使用Stanford NER工具進行命名實體識別，得到待消歧的實體指稱集合，記為M={m1,m2,m3, …}.上下文語境詞對一個實體指稱起著重要的證據作用.相較于其他詞性，名詞能攜帶更豐富的信息，因此，使用Stanford NER工具從除去實體指稱集合M的文本D中提取出名詞，構成文本D的上下文語境詞集合，記為C={c1,c2,c3, …}.

本文基于英文維基百科(2018-03-11 打包發(fā)布版本，包含500多萬實體和3000多萬條鏈接關系)的語料，使用Word2Vec詞向量工具對候選實體與實體指稱和候選實體之間的語義相似度進行比較.使用圖數據庫Neo4j將英文維基百科的實體詞條和超鏈接關系抽取出來構建知識圖譜.

1.2 候選實體生成

將集合M中的命名實體指稱通過Google 發(fā)布的Google Knowledge Graph所提供的搜索API獲取預備候選實體集，對預備候選實體集進行信息提取及格式化整理，篩選后生成最終候選實體集合N={{m11,m12, …,m1x, …}, {m21,m22, …,m2y, …}, …}，其中實體指稱mi生成候選實體集合為Ni={mi1,mi2,…,mij, …}，Ni∈N.

1.3 實體相關圖模型構建

BSAED算法將同一個文本中候選實體之間的雙向語義關聯(lián)結構化表示成一個實體相關圖模型G= (V,E)，其中V表示頂點集合，E表示邊集合.實體相關圖的構造分為2個步驟：頂點集合構造和邊集合構造.

1.3.1 頂點集合構造

頂點集V：與給定文本D中出現(xiàn)的實體指稱對應的所有候選實體集合N，其中mij表示與實體指稱mi相對應的第j個候選實體.

V={mij|?i,j,mi∈D,mij∈Ni}.

(1)

圖中每個頂點被賦予一個置信度(CM， Confidence Measure)，CM表示在不考慮文本上下文信息的情況下，一個候選實體被鏈接的可能性，使用Google Knowledge Graph的搜索API返回的ResultScore(匹配分數)作為置信度.

與其他實體消歧方法類似，為避免圖模型復雜度，選擇CM排名前5的候選實體參與頂點集構造.若候選實體個數不足5，則全部加入最終的候選實體集合中.為方便計算，使用式(2)對同一實體指稱對應的所有候選實體的置信度進行歸一化處理.

(2)

1.3.2 邊集合構造

本文圖模型的邊由候選實體之間的雙向語義關聯(lián)結構構成.雙向語義關聯(lián)結構由候選實體在知識庫中節(jié)點間的雙向路徑關聯(lián)度和候選實體間文本描述信息的語義相似度決定.雙向路徑關聯(lián)度能更有效地表示實體間的差異性，語義相似度能更好地表現(xiàn)出實體間的共性.

(1)候選實體間的雙向路徑關聯(lián)度

在使用維基百科作為背景知識庫的圖模型方法中，已有的方法是利用維基百科中兩個詞條之間的超鏈接所構成的最短路徑來衡量兩個詞條之間的關聯(lián)度，從而構成圖模型中兩個節(jié)點的邊[9,11].但是這種方法只是將兩個詞條之間的超鏈接網絡視為無向圖，忽略了其方向，在衡量兩個詞條之間超鏈接路徑長度時，隨機地選擇任一詞條作為起點進行探索[12]，然而，在現(xiàn)實世界中，轉換詞條的終起點能得到兩個不同的最短路徑長度.

本文提出一種新的判定兩個詞條之間路徑關聯(lián)度的方法，即雙向最短路徑判定法.視詞條之間的超鏈接結構為有向圖，記從實體A鏈接到實體B路徑為前向最短路徑，從實體B鏈接到實體A的路徑為后向最短路徑.

定義兩個節(jié)點之間的最短路徑如下：

ShortPath(va,vb)=

(3)

其中，F(xiàn)ShortPath表示前向最短路徑長度，BShortPath表示后向最短路徑長度.為了更好地描述兩個節(jié)點之間的路徑關聯(lián)度，將路經長度轉化成路徑關聯(lián)度，公式為：

(4)

由式(4)可見，兩個節(jié)點之間的路徑長度越小，兩個節(jié)點的路徑關聯(lián)度越大.根據“六度分離”理論，在探索兩個節(jié)點最短路徑長度時，把最短路徑長度的上限設置為6，即如果兩個節(jié)點之間的路徑長度超過6，則認為這兩個節(jié)點沒有路徑關聯(lián)度.

(2)候選實體間的語義相似度

相關研究表明，利用語義信息為最短路徑加權能更好地表達兩個節(jié)點之間的關聯(lián)度[10]，本文利用候選實體在知識圖譜中的文本描述信息來計算兩個候選實體的語義相似度.使用SimText(va,vb)表示頂點va與頂點vb分別所代表的候選實體的語義相似度.分別將頂點va與頂點vb所代表的候選實體的文本描述信息通過Word2Vec工具向量化表示為TA(ta1,ta2,ta3,…)，TB(tb1,tb2,tb3,…)，利用余弦相似度計算可表示為：

(5)

進行歸一化處理，得到：

(6)

使用Wightba表示圖G中邊(va,vb)的權重，若Wightba=0，則表示圖G中的兩個節(jié)點之間沒有邊連接.需要注意的是，對于同一實體指稱源對應的多個候選實體(頂點)，不考慮其相互之間的關聯(lián)關系，即實體相關圖中同一實體指稱所對應的候選實體頂點間不存在關系邊，其Wightba=0.Wightba計算方式如下：

Wightba=αRePath(va,vb)+(1-α)SimText(va,vb).

(7)

1.4 雙向語義關聯(lián)實體消歧算法

基于雙向語義關聯(lián)的實體消歧算法根據候選實體的重要度和候選實體與查詢文本的文本相似性，得到候選實體與實體指稱的語義相似性，選擇語義相似性最大的候選實體作為真正的鏈接對象，由此得到實體的消歧結果.

1.4.1 候選實體重要度的計算

根據已得到的實體相關圖，利用候選實體的雙向語義關聯(lián)結構對候選實體的重要度進行計算.本文基于對PageRank算法的改進，提出一種新的候選實體重要度計算方法，稱之為重要度排序(IR,Importance Rank)算法.

表1 IR算法中所有符號定義Tab.1 All symbol definitions in IR algorithm

IR算法的數學公式如下：

(8)

其中，λ為阻尼因子，一般取值為0.85；CM(va)可由公式(2)得到；IR(va)表示頂點va所對應候選實體的重要度；T(b,a)表示實體相關圖G中從頂點va到頂點vb的帶權轉移概率：

(9)

其中，Weightba表示圖G中邊(va,vb)的權重，可由式(7)計算得到；Nh(vb)表示頂點vb的鄰域，即圖G中直接與vb相鄰的頂點集合.所有候選實體的帶權轉移概率構成轉移概率矩陣Mp；根據算法得到N中每個候選實體的IR值. IR算法的偽代碼框架如下.

算法1 候選實體的重要性算法(IR).

輸入：候選實體置信度VCM，轉移概率矩陣Mp，閾值ε=0.000001，λ=0.85.

輸出：候選實體的重要性VIR.

VIR0←VCM；

k= 1；

repeat

VIRk+1=λ·Mp·VIRk+(1-λ)VCM；

k=k+ 1；

until ‖VIRk+1-VIRk‖≤ε；

returnVIRk+1

1.4.2 候選實體與查詢文本的文本相似度

IR算法中，節(jié)點的重要性計算僅僅依賴于節(jié)點之間的關聯(lián)關系(即候選實體間的雙向語義關聯(lián)結構)，無法與待消歧的查詢文本建立鏈接，因此，利用候選實體與查詢文本的上下文信息，通過IR算法得到每個候選實體節(jié)點的重要性的取值之后，結合候選實體與查詢文本的文本相似度對候選實體進行鏈接.

使用上下文語境詞集合C表示文本，詞向量表示為TC(tc1,tc2,tc3, …)，mij的文本描述信息(取名詞)詞向量表示為TM(tm1,tm2,tm3, …).計算mij與查詢文本的上下文信息的余弦相似度如下：

(10)

進行歸一化處理，得到：

(11)

1.4.3 實體鏈接

考慮到候選實體的重要度和候選實體與查詢文本的文本相似度兩個方面，用S(mij)表示候選實體mij與實體指稱mi的語義相似度：

S(mij)=IR(mij)+SimCon(mij).

(12)

對于實體指稱mi，獲取最佳鏈接實體的方法如下：

(13)

其中Link(mij)是指當S(mik)取最大值時，實體指稱mi所代表的候選實體.基于雙向語義關聯(lián)的實體消歧算法的偽代碼框架如下.

算法2 基于雙向語義關聯(lián)的實體消歧算法(BSAED).

輸入：實體相關圖G，實體指稱集合M.

輸出：實體鏈接結果S.

S←?；

for eachvh∈Vdo

IR(vh)←使用IR算法計算每個候選實體的IR值；

S(vh)←IR(vh) +SimCon(vh)；

end

for eachmi∈Mdo

ifisNIL(mi)

S←S∪NIL；

else

S←S∪L；

end

returnS

針對空鏈接(NIL)實體指稱，提出兩種規(guī)則進行判定：1)實體指稱mi沒有對應的候選實體；2)實體指稱mi有候選實體，但是鏈接到的候選實體不是維基概念.

假定文本D中待消歧的實體指稱個數為n，IR算法的迭代次數為t(與PageRank算法類似，t是常量級).BSAED算法的時間復雜度分析如下：第1步，初始化實體鏈接結果的時間復雜度為O(1)；第2-5步，計算每個候選實體的IR值的時間復雜度為O(t·n2)，計算所有候選實體的IR值的時間復雜度為O(t·n3)，所以計算所有候選實體的語義相似度S的時間復雜度為O(t·n3)；第6-12步，篩選最佳鏈接實體的時間復雜度為O(n)；第13步，返回最終鏈接結果的時間復雜度為O(1)；BSAED算法在第3步計算IR值時，使用鄰接矩陣來存儲雙向語義關聯(lián)結構，空間復雜度為O(n2).綜上，BSAED算法的時間復雜度為O(n3)，空間復雜度為O(n2).

2 實驗及結果分析

2.1 實驗數據

本文驗證BSAED算法有效性的測試集使用的是ALHELBAWY等[8]使用的AIDA數據集，它由CONLL 2003數據集構建，主要用來測試實體消歧的效果，包括一個訓練集(TRAIN)和兩個測試集(TESTA，TESTB).用于實驗的是TESTA測試集，包含215篇文本，內含5919條實體指稱，其中可被鏈接的實體有4785條，涉及到各個知識領域.

2.2 實驗評估方法

本文采用準確率P、召回率R和F1值指標對實體鏈接消歧算法的性能進行評估，計算方法如下：

(14)

(15)

(16)

2.3 實驗參數設置

BSAED算法中包含的參數α用于權衡實體相關圖中邊E的權重.通過在測試集上的實驗發(fā)現(xiàn)，為使算法的F1值取最優(yōu)，α=0.4，如圖1所示.

圖1 參數α的取值對實驗結果的影響Fig.1 The influence of parameter α on experimental results

2.4 實驗結果分析

2.4.1 特征有效性分析

BSAED算法進行實體消歧主要采用了候選實體的置信度CM、候選實體的文本相似度SimCon、候選實體文本描述相似度SimText和雙向路徑關聯(lián)度RePath四個特征，為驗證本文選用特征的有效性，在AIDA測試集上進行實驗，驗證方法是以上述最優(yōu)配置為基礎，分別去掉各個特征來比較實驗結果：CM被賦值為1/N，其余各個特征的權重賦值為0，相應的實驗結果如表2所示.

表2 去掉某一特征的實驗結果Tab.2 Experimental results without one of features %

從表2可以看出，去掉RePath特征時，實體消歧方法的效果表現(xiàn)最差，F(xiàn)1值的下降幅度達到了13.79%，由此可見雙向路徑關聯(lián)度對于實體消歧效果的重要性，進一步分析可知，兩個實體之間的最短路徑長度能有效表示實體間的差異性，路徑越長，兩個實體的關聯(lián)性越弱，考慮到同一查詢文本中實體的一致性，關聯(lián)度弱的實體容易被區(qū)分出來.相對而言，CM、SimCon和SimText這3個特征對消歧效果的重要性區(qū)別不大，針對CM這一特征，由IR算法原理可知，算法的隨機游走過程主要依賴于節(jié)點間的相互關聯(lián)關系，而弱化了節(jié)點初始值的效果.至于SimText這一特征，通過數據分析發(fā)現(xiàn)部分實體在知識圖譜中存儲的文本描述的信息比較接近，這種情況下，利用SimText進行實體區(qū)分的效果便不太明顯，SimCon同理.另外，在算法的性能方面，因RePath需要圖數據庫Neo4j的支持，花費時間會比其他3種特征長(其他3種特征所需時間差異不大).

2.4.2 雙向語義關聯(lián)度有效性分析

為了驗證雙向語義關聯(lián)度的有效性，本文在AIDA測試集上，與使用無向最短路徑構造實體相關圖模型的方法進行比較，其中，對于實體消歧過程中候選實體篩選和候選實體排序等部分采用與本文相同的處理方式，實驗結果如表3所示.

表3 是否使用雙向最短路徑的實驗結果Tab.3 Experimental results with bidirectional shortest paths or not %

由表3可知，只使用無向最短路徑(Undi-ShortPath)來作為實體依賴圖模型的邊進行實體消歧時，F(xiàn)1值為81.01%，當使用SimText為邊的權重加上語義信息后，F(xiàn)1值提高了7.86%，可見通過綜合實體的差異性和共性能更好地評估候選實體的重要度.雙向最短路徑(RePath)較無向最短路徑(Undi-ShortPath)的F1值提高了2.86%，可見本文提出的雙向最短路徑能更準確地描述兩個實體的關聯(lián)度.雙向最短路徑與文本相似度結合使用(BSAED)更進一步地將F1值提高了10.2%，表明本文提出雙向語義關聯(lián)度對實體消歧算法的有效性.

2.4.3 BSAED算法有效性分析

為驗證本文提出BSAED算法的有效性，與在同樣數據集上消歧效果表現(xiàn)較好的兩種算法進行比較，相對應的實驗結果如表4所示.

表4 BSAED與相關算法實驗結果Tab.4 Experimental results of BSAED and correlation algorithms %

由表4可得，本文提出的BSAED算法在準確率、召回率和F1值的指標上的表現(xiàn)均優(yōu)于另兩種算法.與基于PageRank的集成實體鏈接算法ALHELBAWY等相比,BSAED算法在AIDA測試集上的F1值提高了3.98%，該結果表明：通過使用知識圖譜中的最短路徑，可以更好地利用實體的一致性，從而提高了實體消歧的效果；與使用超鏈接路徑的直接關聯(lián)和間接關聯(lián)關系來衡量實體之間一致性的CCEL算法相比,BSAED算法在AIDA測試集上的F1值提高了0.7%，該結果表明：通過引入調用Google Knowledge Graph提供的搜索API可以獲取到更全面有效的候選實體，一定程度上解決了有效候選實體未出現(xiàn)在最終的候選實體集合中的問題，從而提高了實體消歧的準確率.

3 結束語

本文提出了一種衡量實體間語義關聯(lián)的方法，充分利用維基百科的超鏈接結構，更準確地表示了兩個實體在知識圖譜中的平均最短路徑，更合理地描述了實體間語義關聯(lián)性；同時提出了一種新的基于雙向語義關聯(lián)的實體消歧算法，實驗結果表明該算法的準確率和召回率有了提高.