基于改進(jìn)編輯距離的軍事領(lǐng)域?qū)嶓w鏈接

夏旭東,于榮歡

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)體索引建立

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

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

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

表2 索引格式Tab.2 Index format

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

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

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

表3 索引示例Tab.3 Example indexes

3.1 BM25模型

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

(1)

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

(2)

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

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

(3)

(4)

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

BM25模型的最終公式為

(5)

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

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

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

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

達(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)兩個(gè)字符串之間有一個(gè)為空時(shí),Q轉(zhuǎn)化到D只需進(jìn)行j次插入即可。當(dāng)兩個(gè)字符串均不為空時(shí),可通過“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)存在可交換的字符時(shí),還須加上“l(fā)evQ,D(i-2,j-2)+1”(交換Qi-1與Di)操作,再取最小值。

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

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

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

(7)

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

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

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

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

(8)

3.5 實(shí)體缺失

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 評(píng)價(jià)指標(biāo)

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

(9)

(10)

(11)

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

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

4.3 結(jié)果及分析

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

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

表5 對(duì)比實(shí)驗(yàn)結(jié)果Tab.5 Comparison of experimental results

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

5 結(jié)束語

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