BSAED：一種基于雙向語義關(guān)聯(lián)的實體消歧算法

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

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

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

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

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

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

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

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

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

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

1 雙向語義實體消歧算法

1.1 數(shù)據(jù)預(yù)處理

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

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

1.2 候選實體生成

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

1.3 實體相關(guān)圖模型構(gòu)建

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

1.3.1 頂點集合構(gòu)造

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

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

(1)

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

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

(2)

1.3.2 邊集合構(gòu)造

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

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

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

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

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

ShortPath(va,vb)=

(3)

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

(4)

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

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

相關(guān)研究表明，利用語義信息為最短路徑加權(quán)能更好地表達(dá)兩個節(jié)點之間的關(guān)聯(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)的權(quán)重，若Wightba=0，則表示圖G中的兩個節(jié)點之間沒有邊連接.需要注意的是，對于同一實體指稱源對應(yīng)的多個候選實體(頂點)，不考慮其相互之間的關(guān)聯(lián)關(guān)系，即實體相關(guān)圖中同一實體指稱所對應(yīng)的候選實體頂點間不存在關(guān)系邊，其Wightba=0.Wightba計算方式如下：

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

(7)

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

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

1.4.1 候選實體重要度的計算

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

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

IR算法的數(shù)學(xué)公式如下：

(8)

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

(9)

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

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

輸入：候選實體置信度VCM，轉(zhuǎn)移概率矩陣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é)點之間的關(guān)聯(lián)關(guān)系(即候選實體間的雙向語義關(guān)聯(lián)結(jié)構(gòu))，無法與待消歧的查詢文本建立鏈接，因此，利用候選實體與查詢文本的上下文信息，通過IR算法得到每個候選實體節(jié)點的重要性的取值之后，結(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)是指當(dāng)S(mik)取最大值時，實體指稱mi所代表的候選實體.基于雙向語義關(guān)聯(lián)的實體消歧算法的偽代碼框架如下.

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

輸入：實體相關(guān)圖G，實體指稱集合M.

輸出：實體鏈接結(jié)果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沒有對應(yīng)的候選實體；2)實體指稱mi有候選實體，但是鏈接到的候選實體不是維基概念.

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

2 實驗及結(jié)果分析

2.1 實驗數(shù)據(jù)

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

2.2 實驗評估方法

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

(14)

(15)

(16)

2.3 實驗參數(shù)設(shè)置

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

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

2.4 實驗結(jié)果分析

2.4.1 特征有效性分析

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

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

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

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

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

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

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

2.4.3 BSAED算法有效性分析

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

表4 BSAED與相關(guān)算法實驗結(jié)果Tab.4 Experimental results of BSAED and correlation algorithms %

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

3 結(jié)束語

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