夏旭東,于榮歡

(航天工程大學(xué)復(fù)雜電子系統(tǒng)仿真重點實驗室,北京 101416)

實體鏈接是知識圖譜構(gòu)建與應(yīng)用過程中的關(guān)鍵步驟,是指將文本中抽取出的非標(biāo)準(zhǔn)命名實體規(guī)范化,并鏈接到知識圖譜上的過程[1],也可理解為將候選集合中的最佳目標(biāo)實體賦予實體指稱明確的含義[2]。實體鏈接是詞義消歧任務(wù)中的一種類型[3],需要通過建立知識庫中的實體條目與輸入文本中帶歧義的實體之間一一對應(yīng)的關(guān)系來進(jìn)行歧義消除。

文本中存在的實體叫作實體指稱(Mention),一般包括三種類型[4]:名稱性指稱、名詞性指稱和代詞性指稱。例如,在句子“[外交部發(fā)言人][華春瑩]稱,[我國]火星探測任務(wù)受到廣泛關(guān)注”中,[外交部發(fā)言人]是名詞性指稱,[華春瑩]是名稱性指稱,[我國]則是代詞性指稱,自然語言文本中存在歧義且查詢操作頻繁的指稱主要是名稱性指稱,因此,本文將重點關(guān)注名稱性指稱的實體鏈接。

當(dāng)前實體鏈接方法主要分為單實體鏈接和關(guān)聯(lián)實體鏈接[5]。單實體通常出現(xiàn)在包含少量實體的簡潔文本中,實體上下文信息較少,一般來說,不規(guī)范形式有跡可循[6];而關(guān)聯(lián)性實體通常出現(xiàn)在長文本中,大量實體的含義需通過上下文語義進(jìn)行確定,一詞多義或多詞一義等現(xiàn)象比較普遍[7],對不規(guī)范形式很難用簡單規(guī)律進(jìn)行總結(jié)。與醫(yī)藥、影視、電商等其他領(lǐng)域[8]不同的是,為準(zhǔn)確發(fā)號施令,順暢通信聯(lián)絡(luò),進(jìn)而確保“萬無一失”,軍事指揮員在作戰(zhàn)、訓(xùn)練及其他行動和工作中,依據(jù)《中國人民解放軍軍語》,統(tǒng)一使用規(guī)范化軍事用語,因此,其需求語句通常具有命令簡明,無歧義,縮略形式有跡可循等特點。面向指揮員命令語句的實體鏈接屬于典型的單實體鏈接形式。

因此,本文面向指揮員需求命令提出一種基于改進(jìn)編輯距離模型的單實體鏈接方法。該方法在為標(biāo)準(zhǔn)實體建立索引的基礎(chǔ)上,通過融合改進(jìn)編輯距離的BM25模型完成候選實體排序,最后將排序位次最高的實體返回為鏈接目標(biāo)實體,實現(xiàn)了將指揮員自然語言問句中的實體映射到知識圖譜中標(biāo)準(zhǔn)實體的過程。

1 軍事領(lǐng)域指稱分析

為將指揮員提出的實體指稱準(zhǔn)確映射到知識圖譜中的標(biāo)準(zhǔn)實體上,本文提出的實體鏈接方法是根據(jù)指揮員實體指稱中的常見非標(biāo)準(zhǔn)形式,為知識圖譜中存儲的實體標(biāo)準(zhǔn)名稱與指揮員需求語句的實體指稱建立相同格式的索引,通過相似度計算并排序的方式返回排名最高的實體名作為實體指稱對應(yīng)的標(biāo)準(zhǔn)化實體名。完整的工作流程如圖1所示。

經(jīng)過對常見非標(biāo)準(zhǔn)形式實體的總結(jié)可知,指揮員需求語句中實體指稱常見的非標(biāo)準(zhǔn)類型有以下幾類。

1)指稱是標(biāo)準(zhǔn)實體的別稱,二者文本間無縮寫關(guān)系。如“RQ-1”是美軍無人偵察機(jī)“捕食者”的別稱;“RSD-10彈道導(dǎo)彈”又稱為“先鋒”、“軍刀”等。

2)指稱是由標(biāo)準(zhǔn)實體的各部分縮寫合并而來,包括名稱縮寫、拼音縮寫、英文縮寫等,如“STS”是英文“Space Transportation System”的縮寫,其含義是“航天運輸系統(tǒng)”;“TG-1”是拼音“TianGong-1”的縮寫,意為“天宮一號”。

3)雖然實體名稱不存在縮寫與別稱,但是字符間存在位置交換現(xiàn)象。

4)字符塊省略。這是一種特殊的縮寫形式,即用字母與數(shù)字組成的裝備型號直接代替完整的裝備名稱,屬于部分字符塊直接省略的情況。

表1是對上述實體指稱的非標(biāo)準(zhǔn)類型進(jìn)行的歸納,也是后續(xù)為標(biāo)準(zhǔn)實體建立索引的依據(jù)。

2 實體索引建立

本文對T1～T4的四種非標(biāo)準(zhǔn)類型構(gòu)建索引,并通過相似度計算的方式對其排序。而T5～T6兩種非標(biāo)準(zhǔn)類型則直接在編輯距離計算時考慮。

首先,為知識圖譜中的每一項標(biāo)準(zhǔn)實體以及指揮員需求語句中的實體指稱分別建立索引,目的是根據(jù)數(shù)據(jù)分析結(jié)果,按照常見非標(biāo)準(zhǔn)形式對實體進(jìn)行擴(kuò)展,以提升待鏈接實體可能存在的不規(guī)范形式的覆蓋率,進(jìn)而提高后續(xù)相關(guān)度排序的準(zhǔn)確率。

依據(jù)上一節(jié)對常見非標(biāo)準(zhǔn)形式的分析結(jié)果,索引應(yīng)當(dāng)包含四項內(nèi)容:字、詞、英文和拼音,各項索引的名稱及內(nèi)容如表2所示。

表2 索引格式Tab.2 Index format

其中,別稱來自于《中國人民解放軍軍語》《航天科學(xué)技術(shù)敘詞表》等相關(guān)資料文獻(xiàn),擇取其中“別名”“又稱”“又叫”等內(nèi)容,如無別稱,可補充該詞條的外文名。名稱縮寫是將實體名分詞后選取首字進(jìn)行組合而成,如無法分詞或分詞后含義不清,則可不填充此項,用“/”符號表示,英文縮寫以及拼音縮寫按照表中要求進(jìn)行補充。表3是詞條“國防氣象衛(wèi)星計劃”的索引示例。

3 基于改進(jìn)編輯距離的待鏈接實體排序

為解決實體排序問題,本文采用BM25模型結(jié)合改進(jìn)文本相似度算法進(jìn)行待鏈接實體排序。通過對兩種特殊情形的補充,提高了當(dāng)前基于編輯距離的相似度計算能力,使待鏈接實體排序結(jié)果更符合現(xiàn)實情況。最后,將排序首位的標(biāo)準(zhǔn)化實體作為實體指稱的最終鏈接結(jié)果進(jìn)行返回。

表3 索引示例Tab.3 Example indexes

3.1 BM25模型

BM25(Best Match 25)模型[9]是羅伯遜等人提出的一種基于概率檢索模型的算法,常用于檢索的相關(guān)度評分。由于該模型對于評分的排序效果突出,當(dāng)前仍被廣泛用于搜索結(jié)果排序[10]。BM25模型的關(guān)鍵思想可歸納為:首先,對query進(jìn)行特征提取并分解,生成若干特征詞qi,而后,對每個搜索結(jié)果D,計算特征詞qi與D的相關(guān)性得分,最后,將相關(guān)性得分進(jìn)行加權(quán)求和,從而得到query與D的相關(guān)性得分[11]。BM25模型的一般公式為

(1)

式中,Wi表示特征詞qi的權(quán)重,較為常用的權(quán)重計算公式為

(2)

其中,N為索引中的文檔數(shù)量,dfi為包含特征詞qi的文檔個數(shù),根據(jù)IDF的作用,若包含特征詞qi的文檔越多,則表示qi重要性越低。需要注意的是,當(dāng)一個詞在超過半數(shù)的文檔里出現(xiàn)時,為避免IDF值為負(fù),一般將其置為0。

研究發(fā)現(xiàn),詞頻和相關(guān)性之間的關(guān)系為非線性變化的,一般來說不會超某個閾值,因此,式中用R(qi,D)表示單詞和文檔的相關(guān)性。

(3)

(4)

其中,tftd為單詞的詞頻,Ld為文檔的長度,Lave為文檔集合的平均長度。超參數(shù)k1代表詞語頻率飽和度,用于調(diào)節(jié)特征詞文本頻率尺度,當(dāng)k1=0時,模型退化為二元模型,k1越大,則代表特征詞qi的詞頻參與度更高。而b表示字段規(guī)約長度,b越大,表示文檔長度對相關(guān)性得分的影響就越大,b=1代表完全使用文檔長度來衡量相關(guān)性,b=0即不使用文檔長度。

BM25模型的最終公式為

(5)

對于上述兩個超參數(shù),通常取k1∈[1.2,2.0],b=0.75。

3.2 達(dá)梅勞編輯距離

達(dá)梅勞編輯距離(Damerau Levenshtein Distance)是傳統(tǒng)編輯距離(Levenshtein Distance)的一種變體,也是用于衡量兩個字符串之間相似程度的常用方法[12]。傳統(tǒng)編輯距離的基本原理是計算兩個字符串由Q經(jīng)插入、刪除、替換三種操作轉(zhuǎn)化為D所需的最少單字符操作次數(shù)[13],由于替換可分解為先刪除再插入,因此,上述三種操作所需的操作代價cost應(yīng)有所不同,即cost(插入)=cost(刪除)=1,cost(替換)=2,操作代價越少,則表示二者相似度越高[14]。

傳統(tǒng)的編輯距離對于文本中存在字符交換的情形難以得到正確結(jié)果,例如,文本“長征六號改進(jìn)型”與“改進(jìn)型長征六號”從字面來看屬于相同語義的重復(fù)表達(dá),但是通過上述編輯距離計算會得到兩個文本不相同的分詞串,會得到二者不相似的錯誤結(jié)論,因此,達(dá)梅勞編輯距離在傳統(tǒng)編輯距離的基礎(chǔ)上加入“交換”操作,該操作cost=1,其含義是交換兩個相鄰字符的位置。

達(dá)梅勞編輯距離可定義為DlevQ,D(i,j):

DlevQ,D(i,j)=

(6)

其中case1為“if min(i,j)=0”;case2為“ifQi=Di-1andQi-1=Dj”;case3代表“otherwise”。上式表示,當(dāng)兩個字符串之間有一個為空時,Q轉(zhuǎn)化到D只需進(jìn)行j次插入即可。當(dāng)兩個字符串均不為空時,可通過“l(fā)evQ,D(i-1,j)+1”(刪除Qi)、“l(fā)evQ,D(i,j-1)+1”(插入Dj)、“l(fā)evQ,D(i-1,j-1)+1(Qi≠Dj)”(替換Dj)三種情形中的最小值決定。當(dāng)存在可交換的字符時,還須加上“l(fā)evQ,D(i-2,j-2)+1”(交換Qi-1與Di)操作,再取最小值。

3.3 文本包含關(guān)系

僅通過達(dá)梅勞編輯距離計算相似度仍有不足之處,即不能解決含有文本包含的情形:文本“DF31彈道導(dǎo)彈”與“DF41彈道導(dǎo)彈”編輯距離為1,二者僅需通過一次替換操作即可完成轉(zhuǎn)化,但是“DF31彈道導(dǎo)彈”與其簡稱“DF31”之間的編輯距離卻為4,說明僅按照達(dá)梅勞編輯距離計算文本“DF31彈道導(dǎo)彈”與“DF41彈道導(dǎo)彈”的相似性高于與其簡稱“DF31”的相似度,這顯然與實際情形不符。

因此,本文對于存在包含關(guān)系的文本,通過條件判斷函數(shù)結(jié)合權(quán)重賦值,進(jìn)行文本相似度加強(qiáng),即

(7)

其中,α是對于文本包含情形的相似度增強(qiáng)權(quán)重。

3.4 改進(jìn)的編輯距離模型

通過以上分析,本文最終使用BM25模型融合達(dá)梅勞編輯距離并結(jié)合文本包含關(guān)系的組合方式,對知識圖譜中標(biāo)準(zhǔn)化實體構(gòu)建的索引,按照文本相似度進(jìn)行排序,并將排在首位的索引視為最能體現(xiàn)指揮員實體指稱含義的標(biāo)準(zhǔn)化實體,從而完成實體鏈接。改進(jìn)的編輯距離模型具體公式如下所示:

Score(Wa,Wb)=B(Q,D)+DlevQ,D(i,j)+Dcontain(WQ,WD)

(8)

3.5 實體缺失

由于知識庫更新具有一定周期,指揮員輸入錯誤等不可控因素存在,在實體鏈接過程中不可避免地會出現(xiàn)實體缺失的情況,一般采用設(shè)定閾值的方法處理,如在相似度計算得分的基礎(chǔ)上設(shè)定相似度閾值為0.3,即當(dāng)匹配得分小于0.3時視為該實體不存在,返回“null”。

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

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

本文的實驗數(shù)據(jù)以空間態(tài)勢領(lǐng)域知識圖譜中的實體名稱為基礎(chǔ),通過收錄常見實體簡稱、實體別稱,并通過人工刪減字符等方式構(gòu)造了3 870余個實體指稱,每個實體指稱均鏈接對應(yīng)空間態(tài)勢知識圖譜中的某個實體節(jié)點,部分實體指稱與標(biāo)準(zhǔn)實體的對應(yīng)關(guān)系如表4所示。

4.2 評價指標(biāo)

實驗采用三個通用的評測指標(biāo)作為評價標(biāo)準(zhǔn),即準(zhǔn)確率(P)、召回率(R)和F1值(F-score),具體的計算公式如下:

(9)

(10)

(11)

其中,TP為正確鏈接的實體個數(shù),FP表示鏈接錯誤的實體個數(shù),FN表示未鏈接出的實體個數(shù)。

表4 構(gòu)建的實體指稱及對應(yīng)的標(biāo)準(zhǔn)實體名(部分)Tab.4 Constructed entity mention and corresponding standard entity names (partial)

4.3 結(jié)果及分析

為驗證本文提出的單實體鏈接方法對于實體指稱的鏈接效果,實驗選取的對比方法有四種:完全匹配法、基于傳統(tǒng)檢索的方法、基于傳統(tǒng)編輯距離的方法和基于達(dá)梅勞編輯距離。

其中,完全匹配法是直接將待鏈接實體放入空間態(tài)勢知識圖譜中進(jìn)行匹配;基于傳統(tǒng)檢索的方法是對文本分詞后建立索引并使用BM25算法進(jìn)行檢索;而基于傳統(tǒng)編輯距離法不考慮文本位置與包含相似性,僅衡量字符串之間相似度;基于達(dá)梅勞編輯距離是在傳統(tǒng)編輯距離的基礎(chǔ)上考慮了字符位置交換對相似度計算的影響。最終的實驗結(jié)果如表5所示。

表5 對比實驗結(jié)果Tab.5 Comparison of experimental results

由表5可見,本文提出的實體鏈接方法相對于其他方法在軍事領(lǐng)域的實體鏈接領(lǐng)域具有明顯優(yōu)勢,其原因是本文通過對指揮員需求語句中實體指稱常見的非標(biāo)準(zhǔn)形式進(jìn)行了更加細(xì)致的歸納與總結(jié),以此建立索引,并將字符位置交換和包含相似性納入實體鏈接方法,使得鏈接具有更高的準(zhǔn)確度。而其他方法因未充分考慮指揮員實體指稱特點、排序算法的不適應(yīng)性等原因,導(dǎo)致未能對實體指稱進(jìn)行有效的鏈接。

5 結(jié)束語

本文提出了一種基于改進(jìn)編輯距離的軍事領(lǐng)域?qū)嶓w鏈接方法。通過總結(jié)指揮員需求語句中實體指稱的非標(biāo)準(zhǔn)類型,對采用傳統(tǒng)編輯距離的文本相似度算法進(jìn)行了改進(jìn),通過實驗證明了本方法的準(zhǔn)確性。但是該算法在時間復(fù)雜度上耗費成本較高,且在別稱索引部分比較依賴構(gòu)建的別稱詞表,在下一步的研究中,將嘗試采用深度學(xué)習(xí)方法,使模型自主學(xué)習(xí)標(biāo)準(zhǔn)實體別稱形成規(guī)則,同時也能夠提高算法鏈接效率。