基于圖的聯(lián)合特征實體鏈接方法

周 金， 朱永華， 張鐵男， 邢毅雪， 張 克

(1. 上海大學(xué)上海電影學(xué)院， 上海200072;2. 上海大學(xué)計算機工程與科學(xué)學(xué)院， 上海200444)

在“信息泛濫-知識匱乏”的網(wǎng)絡(luò)大數(shù)據(jù)情境下， 針對如何排除冗余和噪聲知識以及精準(zhǔn)挖掘目標(biāo)信息， 給人們帶來了極大的挑戰(zhàn). 而伴隨著知識庫的持續(xù)擴(kuò)增和知識圖譜的新興發(fā)展，如何對多源異構(gòu)數(shù)據(jù)進(jìn)行數(shù)據(jù)融合， 豐富碎片化知識關(guān)系， 實現(xiàn)知識圖譜的自動構(gòu)建， 都成為了當(dāng)下亟待解決的難題， 其中不可避免要涉及的問題就是自然語言表達(dá)的多樣性與歧義性， 具體而言即是同一實體可能存在多種不同表達(dá)形式(多詞一義)， 而同一表達(dá)可能指代多個不同的實體(一詞多義). 因此， 實體鏈接便成為了解決這一問題的關(guān)鍵.

實體鏈接(entity linking)是指將從網(wǎng)絡(luò)大數(shù)據(jù)文本中獲取的實體指稱鏈接到知識庫實體的過程. 例如， 給出一段文本“······把蘋果削皮去核， 取果肉 ······”， 實體鏈接的工作是將文本中的實體指稱項“蘋果”與知識庫中的水果“蘋果”相鏈接， 而不是將其鏈接到iPhone“蘋果”、歌曲“蘋果”， 或者電影“蘋果”. 實體鏈接不僅能夠增強閱讀體驗， 幫助人們和計算機更深入地理解目標(biāo)信息的含義， 而且可以形成以實體為中心的精準(zhǔn)信息聚合體系， 推動領(lǐng)域知識庫的發(fā)展. 實體鏈接在搜索引擎檢索[1]、知識圖譜自動構(gòu)建[2]、知識融合[3]等領(lǐng)域都有著重要的應(yīng)用前景和研究意義.

本工作提出了一種基于圖的聯(lián)合特征實體鏈接方法， 利用主題模型對主題相似的文檔進(jìn)行聚類， 以獲取更豐富的上下文信息并實現(xiàn)批量處理實體指稱鏈接; 選取核心的特征(上下文、元數(shù)據(jù)等)計算生成重啟隨機游走的初始邊權(quán)重; 綜合考慮全部實體相互之間的相關(guān)度， 利用一致性模型進(jìn)行聯(lián)合消歧， 以實現(xiàn)實體鏈接的目標(biāo).

1 相關(guān)工作

本工作通過對已有研究的調(diào)研與分析， 從考慮實體特征范圍的角度， 將實體鏈接方法分為小局部鏈接方法、局部鏈接方法和全局鏈接方法.

小局部鏈接方法在屬性信息豐富且沒有干擾項的情況下， 只考慮實體指稱與候選實體之間的名稱屬性相似度計算， 有借助編輯距離(edit distance)、Dice 相似性系數(shù)(Dice coefficient score)、漢明距離(Hamming distance)等的字符串相似度方法[4]和利用詞典的實體語義相似度計算方法[5].

局部鏈接方法則在文本環(huán)境下分析單個實體指稱與候選實體之間的相似度， 忽略實體指稱項之間的內(nèi)在聯(lián)系， 有基于實體知名度的方法[6]、基于上下文相似度的方法[7]和基于概率生成模型的方法[8]， 其中基于實體知名度的方法雖然是一種相對比較可靠的方法， 但是該方法將結(jié)果固定在同一個候選實體上， 對于特殊情況不是很合理; 基于上下文相似度的方法作為最普遍的方法， 在兩個文本中必須出現(xiàn)重疊詞這一嚴(yán)格框架下， 無法保證計算準(zhǔn)確率; 基于概率生成模型的方法則需要大量統(tǒng)計數(shù)據(jù)作為支撐. 與此同時， 這些上下文相關(guān)的方法只是以實體知識庫信息作為特征， 沒有考慮到實體指稱項之間的內(nèi)在聯(lián)系.

全局鏈接方法認(rèn)為， 在同一文本中出現(xiàn)的實體指稱之間是相互關(guān)聯(lián)的. 該方法通過捕捉實體間的語義關(guān)系， 協(xié)同鏈接文本內(nèi)所有提及的實體指稱， 以實現(xiàn)批量實體鏈接效果， 有基于語義相似度的方法[9]、基于圖的方法[10]、基于主題模型的方法[11]和基于深度神經(jīng)網(wǎng)絡(luò)的方法[12]等.

Han 等[13]首先提出圖模型的思想， 在全部實體范圍內(nèi)， 同時計算上下文相似度與語義相似度， 利用隨機游走排序， 從而得到目標(biāo)結(jié)果; Hoffart 等[14]構(gòu)建包括先驗、上下文、聚類在內(nèi)的加權(quán)圖， 選擇出一個候選實體的密集子圖作為目標(biāo); 李茂林[15]則在文獻(xiàn)[13]的基礎(chǔ)上加入了主題信息; 高艷紅等[16]提出對從維基百科抽取的上下文與內(nèi)容兩方面語義特征的語義相似度進(jìn)行計算， 并融合到構(gòu)建的圖模型， 但沒有實現(xiàn)批量處理， 且對于空鏈接的處理不完備; 譚詠梅等[17]在知識庫部分實體的圖結(jié)構(gòu)中重啟隨機游走， 獲得實體和指稱的分布式表示， 甚至融入卷積神經(jīng)網(wǎng)絡(luò)[12]， 聚類知識庫中無對應(yīng)的實體指稱， 然而在指稱擴(kuò)充方面忽略了語義聯(lián)系，但指稱識別部分仍舊不理想， 融合卷積神經(jīng)網(wǎng)絡(luò)的改進(jìn)方案也增加了算法復(fù)雜度.

2 實體鏈接框架與算法

從目標(biāo)實現(xiàn)的角度來看， 實體鏈接是聯(lián)合指稱項和候選實體的多種特征， 通過某種方法識別出目標(biāo)實體; 若對應(yīng)目標(biāo)實體不存在， 則返回空鏈接NIL. 本工作提出的基于圖的聯(lián)合特征實體鏈接方法的整體框架如圖1 所示. 框架接受一個文檔集合作為輸入， 輸出文檔中的指稱和對應(yīng)的實體. 框架被分成了線上和離線兩部分.

圖1 基于圖的聯(lián)合特征實體鏈接方法框架圖Fig.1 Framework of entity linking method based on graph with multi-feature fusion

離線部分是對知識庫Freebase 作預(yù)處理: ①建立實體索引， 加速候選實體的查詢， 其中Lucene 是一款高性能的檢索工具; ②構(gòu)建一義多詞表， 擴(kuò)充分詞器的詞庫. 在自然語言文本中很多實體常常以別名等形式出現(xiàn)， 分詞器很難把這些別名都識別出來， 因此本工作從Freebase提供的實體信息中抽取這些別名信息.

線上部分首先利用LDA 主題模型對文檔集進(jìn)行聚類， 將相似主題分布的文檔歸為一類.①一篇文檔中的指稱對應(yīng)的實體相互之間有較大的關(guān)聯(lián)度; ②兩篇主題分布相似的文檔中的指稱對應(yīng)的實體之間也會有較大的相關(guān)性. 鏈接算法以主題分布形式的文本集作為輸入， 實體鏈接過程分為以下6 個部分: 指稱識別、候選實體生成、圖構(gòu)建、邊權(quán)重計算、重啟隨機游走和聯(lián)合鏈接.

2.1 指稱識別

本工作采用Stanford NER 漢語分詞系統(tǒng)， 依據(jù)詞性標(biāo)注結(jié)果識別出主題分布相似的文本集D 中的實體指稱項. 對于指稱的別名等問題， 將離線部分生成的一義多詞表輸入分詞系統(tǒng)的詞庫中， 提高識別率， 記分詞系統(tǒng)最終識別出的指稱集合為 M ={m1，m2，··· ，mn}.

2.2 候選實體生成

在離線部分， 知識庫的實體已經(jīng)通過Lucene 建立了索引. 本工作直接使用Lucene 來檢索指稱的候選實體. 記指稱集合 M 對應(yīng)的候選實體集合為 Em= {Em1，Em2，··· ，Emn}， 其中Emi是指稱mi的候選實體集合， 由此可以得到m-Em映射表， 如表1 所示.

表 1 m-Em 映射表Table 1 m-Em matching

2.3 指稱-實體圖構(gòu)建

本工作借鑒文獻(xiàn)[15]的思想， 采用重啟隨機游走的方法計算指稱和實體之間的相關(guān)度. 在隨機游走之前， 需要構(gòu)建一個連通圖(指稱-實體圖)， 即圖中的任意兩個節(jié)點之間是可達(dá)的. 第一步， 在指稱和對應(yīng)的候選實體之間加上邊(見圖2 中①線); 第二步， 將知識庫中有連接關(guān)系的候選實體之間加上邊(見圖2 中②線); 第三步， 由于隨機游走必須保證每個實體之間是互通的， 所以選擇知識庫中至少同時連接兩個候選實體的實體添加到指稱-實體圖中(見圖2 中③線)， 新加入的實體稱作“擴(kuò)充實體”. 本工作簡化了知識庫中實體之間的聯(lián)系， 將有向邊視為無向邊.

圖2 指稱-候選實體-擴(kuò)充實體圖結(jié)構(gòu)Fig.2 Mention-candidate entity-augmented entity graph structure

2.4 邊權(quán)重計算

指稱-實體圖構(gòu)建完成后， 需要求出相應(yīng)的轉(zhuǎn)移矩陣. 圖2 中存在兩類節(jié)點: 指稱節(jié)點和實體節(jié)點. 因此， 邊的類型可以分成指稱-實體邊(即圖2 中①線)和實體-實體邊(即圖2 中②， ③線). 本工作使用節(jié)點之間的聯(lián)合關(guān)聯(lián)度來描述兩類邊的權(quán)重， 即指稱-實體關(guān)聯(lián)度S(m，e)和實體-實體關(guān)聯(lián)度S(ei，ej)， 采用的計算方法如表2 所示.

表2 邊權(quán)重計算方法Table 2 Method for calculating edge weights

2.4.1 指稱-實體關(guān)聯(lián)度

指稱-實體關(guān)聯(lián)度表示實體指稱m 與候選實體e 之間的關(guān)聯(lián)程度. 本工作在文獻(xiàn)[16-17]的基礎(chǔ)上， 利用文本的字符串特征、上下文特征來計算字符串文本相似度SED(m，e)和上下文-元數(shù)據(jù)相似度CSM(m，e)， 然后線性聯(lián)合這兩個相似度來衡量m 和e 之間的指稱-實體關(guān)聯(lián)度.

(1) SED(m，e).

使用編輯距離(edit distance， ED)計算字符串文本相似度. 編輯距離指兩個字串由一個轉(zhuǎn)成另一個所需的最少編輯操作(替換、插入、刪除)次數(shù). 一般來說， 編輯距離越短， 兩個字符串的相似度越大. 為了衡量關(guān)聯(lián)度， 要將編輯距離歸一化，

式中: a 和b 是兩個字符串; ED(a，b)是兩個字符串之間的編輯距離. 編輯距離和字符串相似度之間呈負(fù)相關(guān)， 字符串文本相似度

式中: SED(m，e)表示指稱m 和實體e 之間的相似度， 值越大的兩個字符串被認(rèn)為在編輯距離意義上越靠近， 反之則越不相似.

(2) CSM(m，e).

指稱-實體圖中的指稱節(jié)點和實體節(jié)點都有相應(yīng)的上下文文本信息. 為了計算上下文之間的相似度， 首先利用預(yù)訓(xùn)練的Word2Vec 模型來獲取上下文句子中每個詞的向量表示. 該模型是在Google News 數(shù)據(jù)集(含有1 000 億個詞)上訓(xùn)練而來的. 記指稱m 的上下文詞集合為Lm= {wm，1，wm，2，··· ，wm，n}， 其中 wm，i= (xi，1，xi，2，··· ，xi，k)， k 是向量的維度. 同理， 記實體 e 的上下文詞集合為 Le= {we，1，we，2，··· ，we，l}， 其中 we，j= (yj，1，yj，2，··· ，yj，k). 將上下文中的詞向量進(jìn)行求和平均， 得到指稱和實體的上下文向量，

記 Cm=(x1，x2，··· ，xk)， Ce=(y1，y2，··· ，yk). 使用 cosine 相似度計算指稱和實體之間的相似度，

(3) S(m，e).

綜合以上兩種相似度特征， 將式(2)和(5)線性組合得到指稱和實體的關(guān)聯(lián)度，

設(shè)定 α =0.36， β =0.64.

2.4.2 實體-實體關(guān)聯(lián)度

實體-實體關(guān)聯(lián)度是實體(ei，ej)之間的相似度， 采用的方法包括上下文相似度和元數(shù)據(jù)相似度. 同樣地， 線性組合兩個相似度來計算實體-實體關(guān)聯(lián)度S(ei，ej).

(1) CSM(ei，ej).

計算CSM(ei，ej)的方法和2.4.1 節(jié)中的上下文相似度的方法是一致的. 兩個實體ei和ej的上下文相似度為

(2) MSM(ei，ej).

Freebase 知識庫中提供了實體和維基百科頁面的映射關(guān)系. 常見的實體在維基百科頁面中都有一個infobox(見圖3(a))， 稱這部分?jǐn)?shù)據(jù)為實體的元數(shù)據(jù). 本工作使用Kalender 等[18]提出的元數(shù)據(jù)相似度來衡量實體之間的關(guān)聯(lián)度. 首先， 將知識庫中所有實體的infobox 中的信息抽取出來， 用詞袋模型(bag-of-words)構(gòu)成一個詞匯表， 即圖3(b)的第2 張表. 詞匯表的規(guī)模直接決定每個詞向量的維度. 高維的向量不僅需要更大的內(nèi)存開銷， 而且還存在稀疏性的問題.因此， Kalender 等[18]進(jìn)一步引入了hashing 算法處理原有的詞典， 轉(zhuǎn)換成圖3(b)第3 張表所示的詞典. 該方法為每個詞添加起止標(biāo)志(如#harvard#)， 然后將詞分割成2-grams 的字母組合(如#h， ha)， 重新構(gòu)成一個詞匯表. 每個詞可以表示成字母組合的向量. 實體的向量同樣是通過其對應(yīng)infobox 中每個詞的向量的求和平均計算而來. 兩個實體ei和ej的元數(shù)據(jù)相似度依然通過 cosine 相似度來計算， 記為 MSM(ei，ej).

圖3 元數(shù)據(jù)相似度Fig.3 Metadata similarity

(3) S(ei，ej).

綜合以上兩種相似度特征， 線性組合得到實體之間的關(guān)聯(lián)度為

設(shè)定 γ =0.42， δ =0.58.

2.5 重啟隨機游走

重啟隨機游走是從某一個節(jié)點出發(fā)遍歷圖的隨機過程. 該過程收斂后對應(yīng)每個節(jié)點生成一個概率值， 表示起點和該點之間的親和度(無論起點和該點是否直接相連)， 記這些概率值構(gòu)成的向量為P. 重啟隨機游走即是更新P，

式中: c 表示重啟概率; Pi表示經(jīng)過i 輪迭代后的概率分布值; P0表示初始向量， 即經(jīng)過0 次迭代后的概率分布. 因此， P0中只有起點對應(yīng)的位置值為1， 其余元素都為0. 圖中每一個節(jié)點都進(jìn)行重啟隨機游走， 就能得到圖中任意兩個節(jié)點之間的親和度.

2.6 聯(lián)合鏈接

本工作采用Globerson 等[19]提出的一致性模型進(jìn)行聯(lián)合實體鏈接. 該方法考慮指稱與實體之間的相關(guān)度和候選實體之間的相關(guān)度， 相關(guān)定義如下.

(1) rm(yt)表示指稱m 和實體yt之間的相關(guān)度， 即以指稱m 為起點的重啟隨機游走生成的概率分布中實體yt對應(yīng)的值.

(2) s(ya，yb)表示實體ya對實體yb的支持度， 即以實體ya為起點的重啟隨機游走生成的概率分布中實體yb對應(yīng)的值. 一篇文檔中實體的主題分布基本一致， 因此判斷一個實體e 是否對應(yīng)某個指稱m， 不僅可以通過指稱和實體之間的關(guān)聯(lián)度， 還可以通過文檔中其他實體和實體e 的一致性程度(支持度). 通過下式得到指稱mi的鏈接實體， 即

式中: yi表示指稱mi的候選實體; max s(yj，yi)表示指稱mj的候選實體對實體yi的最大支持度.

3 實驗結(jié)果

為驗證基于圖的聯(lián)合特征實體鏈接算法的有效性， 本工作采用TAC 2016 年EDL 任務(wù)的實驗數(shù)據(jù)， 并且使用準(zhǔn)確率(P)、召回率(R)和F 值對鏈接和聚類結(jié)果進(jìn)行評價. 在此基礎(chǔ)上重現(xiàn)文獻(xiàn)[16-17]的測試結(jié)果(見表3)， 可見本工作所提出的基于圖的聯(lián)合特征實體鏈接算法優(yōu)于其他兩種算法， 表明本算法能有效完成實體鏈接任務(wù).

表3 不同實體鏈接算法的性能比較Table 3 Performance comparison of different entity linking methods

高艷紅等[16]將多特征融合到圖模型時只是簡單地把單個指稱和對應(yīng)候選實體放在一張圖中， 沒有協(xié)同考慮主題相似性， 而本工作利用LDA 主題模型對文檔集進(jìn)行聚類. 譚詠梅等[17]則僅使用維基百科頁面中共現(xiàn)的次數(shù)作為衡量初始權(quán)重的標(biāo)準(zhǔn)， 單一地對提取的多種特征逐項排序， 沒有充分考慮特征之間的關(guān)系， 而本工作采用一致性模型實現(xiàn)聯(lián)合特征鏈接. 盡管這些不同方法在處理實體鏈接方面都有一定的改進(jìn)， 但在圖的構(gòu)建、邊權(quán)重計算、特征選擇以及排序選擇方面仍舊存在不足. 本工作采用重啟隨機游走的方式， 將多種特征融合到初始邊權(quán)重計算中， 在選擇特征時， 采取聯(lián)合上下文與元數(shù)據(jù)的方式， 以提高鏈接速率; 同時， 排除知名度特征， 降低干擾度， 對于主題相似度的文本實現(xiàn)協(xié)同指稱鏈接.

4 結(jié)束語

面向?qū)嶓w鏈接， 本工作提出一種基于圖的聯(lián)合特征實體鏈接方法， 有選擇地抽取主題、上下文和元數(shù)據(jù)等重要特征， 并融合到重啟隨機游走的初始權(quán)重計算中， 達(dá)成聯(lián)合實體鏈接的目標(biāo). 實驗結(jié)果表明， 本工作提出的方法更準(zhǔn)確地抓住了聯(lián)合相似度的重點， 并且取得了較好的鏈接效果. 但是， 本工作對NIL 空鏈接沒有作處理， 這將是下一步的工作方向. 目前， 實體鏈接還有很多技術(shù)難點， 如通用領(lǐng)域的中文知識庫實體量巨大且實體界限模糊; 短文本缺乏足夠的上下文信息， 需要挖掘?qū)嶓w與詞語之間關(guān)系; 中文與英文的明顯差異對實體鏈接造成的挑戰(zhàn)等. 所以， 后續(xù)工作不僅要改進(jìn)所提出的算法， 在其他方面也將作出探索.