姚建軍,李劍宇,岳 昆+,段 亮,付曉東

(1.云南大學(xué) 信息學(xué)院,云南 昆明 650500;2.云南大學(xué) 云南省智能系統(tǒng)與計算重點實驗室,云南 昆明 650500;3.昆明理工大學(xué) 信息工程與自動化學(xué)院,云南 昆明 650504)

1 問題的提出

知識圖譜(Knowledge Graph,KG)在智能問答[1]、信息檢索[2]和推薦系統(tǒng)[3]等領(lǐng)域的應(yīng)用日益廣泛,Freebase和Wikdata等知識庫在學(xué)界和業(yè)界都得到了長足的發(fā)展。然而,KG中的知識并不完善,部分實體之間缺少鏈接,例如,Freebase中約71%的人缺少與“出生地”的鏈接,Wikipedia中超過70%的人缺少與“種族”的鏈接。鏈接預(yù)測算法通過網(wǎng)絡(luò)中已知節(jié)點和網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中無邊相連的兩個節(jié)點之間是否會產(chǎn)生鏈接關(guān)系,從而解決缺失信息的還原問題和錯誤信息的檢測問題[4]。因此,KG中的鏈接預(yù)測致力于尋找實體間缺失的鏈接,并在社交網(wǎng)絡(luò)分析、生物醫(yī)學(xué)、電影推薦等領(lǐng)域取得了極大進(jìn)展。

通常,KG鏈接預(yù)測需要通過量化不同實體間相互關(guān)聯(lián)的可能性來確定實體間是否存在鏈接。例如,在圖1所示的KG中,實體“姜某”與實體“吳某”之間相互關(guān)聯(lián)的可能性是0.3,與實體“陳某”相互關(guān)聯(lián)的可能性是0.8,則相比“吳某”,“姜某”與“陳某”之間存在鏈接的可能性更大,這種可能性反映了真實世界中實體間存在關(guān)聯(lián)關(guān)系的程度(即關(guān)聯(lián)度),兩個實體間的關(guān)聯(lián)度越大,其存在鏈接的可能性越高。為此,給定查詢實體,如何發(fā)現(xiàn)與之相關(guān)的關(guān)聯(lián)實體集并計算實體間的關(guān)聯(lián)度,再根據(jù)關(guān)聯(lián)度得到與查詢實體存在鏈接關(guān)系的實體集,是本文擬研究的KG鏈接預(yù)測問題。

近年來,研究人員提出許多KG鏈接預(yù)測方法,基于嵌入的方法[5]將KG嵌入低維向量,通過相似度計算得到存在鏈接的實體。Trans系列模型[5-7]通過計算所嵌入實體及關(guān)系向量的“距離”判斷實體間是否存在鏈接。然而,這類方法沒有考慮顯式的邏輯語義,難以找到具有最大關(guān)聯(lián)度的實體鏈接。以AMIE模型[8]為代表的基于推理的方法通過挖掘KG中的邏輯規(guī)則來推斷缺失的知識,并基于采樣和計數(shù)來計算規(guī)則的權(quán)重,能夠快速有效地從KG中挖掘新的知識,并補(bǔ)全實體間缺失的鏈接。然而真實世界中不同實體間的關(guān)聯(lián)關(guān)系錯綜復(fù)雜,基于線性規(guī)則推理的方法不能有效捕獲不同實體間潛在的鏈接關(guān)系,難以全面準(zhǔn)確地完成KG鏈接預(yù)測任務(wù)。

實際上,KG中不同實體之間存在隱含的關(guān)聯(lián)關(guān)系。例如,在圖1所示的KG中,實體“陳某”與“姜某”存在〈合作(姜某,葛某),朋友(葛某,陳某)〉和〈朋友(姜某,張某),作品(張某,《乙》,演員(《乙》,陳某)〉兩條間接關(guān)聯(lián)的路徑,則真實世界中“姜某”與“陳某”間有較大可能存在關(guān)聯(lián)[9]。如何描述不同實體間隱含的鏈接,并對其存在的可能性進(jìn)行定量度量,成為準(zhǔn)確預(yù)測KG中可能存在鏈接的重要保證。因此,本文用圖模型描述實體間的鏈接,針對查詢實體,基于采用AMIE模型從KG中挖掘得到的規(guī)則構(gòu)建描述實體相互關(guān)聯(lián)的圖模型,作為推理未知鏈接的基礎(chǔ)。為此,需要解決以下兩個問題:①基于規(guī)則構(gòu)建圖模型;②量化實體間鏈接的關(guān)聯(lián)度。

貝葉斯網(wǎng)(Bayesian Network,BN)通過有向無環(huán)圖(Directed Acyclic Graph,DAG)描述變量之間的關(guān)聯(lián)關(guān)系,每個節(jié)點(隨機(jī)變量)都有一張條件概率表(Conditional Probability Table,CPT)。BN具有堅實的圖論和概率論理論基礎(chǔ),可有效描述隨機(jī)變量之間的概率依賴關(guān)系,利用條件獨立性簡化概率計算,實現(xiàn)條件概率、后驗概率和聯(lián)合概率分布的推理,廣泛應(yīng)用于診斷分析和決策支持等領(lǐng)域。本文基于描述實體間關(guān)聯(lián)關(guān)系的規(guī)則,進(jìn)一步構(gòu)建描述實體間相互關(guān)聯(lián)的規(guī)則鏈接貝葉斯網(wǎng)(Rule-Link Bayesian Network,RLBN),基于RLBN的概率推理推斷實體間的鏈接關(guān)系,從而進(jìn)行KG的鏈接預(yù)測。

具體而言,本文的研究工作和主要貢獻(xiàn)包括:

(1)RLBN的結(jié)構(gòu)構(gòu)建針對查詢實體,利用AMIE算法挖掘KG中描述查詢實體與候選實體集依賴關(guān)系的邏輯規(guī)則,設(shè)計加權(quán)函數(shù)計算規(guī)則的權(quán)值,并提出抽取最優(yōu)規(guī)則關(guān)聯(lián)實體集的分支限界算法,獲取與查詢實體關(guān)聯(lián)的實體集,然后將查詢實體的規(guī)則關(guān)聯(lián)實體集表示為Horn子句并等價轉(zhuǎn)換為DAG。

(2)RLBN的參數(shù)計算根據(jù)KG自身結(jié)構(gòu)提出實體間的概率分配函數(shù),計算無父親節(jié)點的條件概率參數(shù);基于父節(jié)點取值和Horn子句中的邏輯約束,計算存在父親節(jié)點的條件概率參數(shù)。

(3)實體間的鏈接預(yù)測將KG鏈接預(yù)測任務(wù)轉(zhuǎn)換為RLBN的概率推理任務(wù),將后驗概率作為實體間的關(guān)聯(lián)度,提出基于Gibbs采樣的RLBN近似推理算法,高效計算實體間的關(guān)聯(lián)度,預(yù)測實體間缺失的鏈接。

本文在不同類型和不同規(guī)模的KG數(shù)據(jù)集上完成針對鏈接預(yù)測任務(wù)的實驗,并與基準(zhǔn)模型進(jìn)行對比。實驗結(jié)果表明,RLBN在鏈接預(yù)測任務(wù)中表現(xiàn)優(yōu)異,其精確率和召回率均高于對比模型,驗證了本文模型的有效性與高效性。

2 相關(guān)工作

KG鏈接預(yù)測方法主要分為基于嵌入學(xué)習(xí)的方法、基于規(guī)則推理的方法和基于概率推理的方法3類。

基于嵌入學(xué)習(xí)的方法將KG中高維、稀疏的關(guān)系與實體映射成低維、稠密的向量,利用向量間的“距離”計算實體間的關(guān)聯(lián)度,完成鏈接預(yù)測任務(wù)。BORDES等[5]提出TransE模型,是最早提出的基于嵌入學(xué)習(xí)模型的鏈接預(yù)測方法,隨后研究人員相繼提出TransH[6]和TransR[7]等改進(jìn)模型;DETTMERS等[9]提出ConvE模型,利用神經(jīng)網(wǎng)絡(luò)直接對KG中的事實元組進(jìn)行建模,得到實體與關(guān)系的向量表示;NIU等[10]提出RPJE模型,將規(guī)則和路徑相結(jié)合,通過引入KG的路徑或規(guī)則來提升鏈接預(yù)測的準(zhǔn)確性;YANG等[11]將KG中的三元組視為張量/矩陣,通過分解張量/矩陣實現(xiàn)鏈接預(yù)測?；谇度雽W(xué)習(xí)模型的鏈接預(yù)測方法簡便高效,但結(jié)果缺乏可解釋性,基于向量“距離”度量的實體鏈接存在性判斷方法未考慮顯式的邏輯語義,難以有效預(yù)測實體間最可能存在的鏈接。

基于規(guī)則推理的鏈接預(yù)測方法通過挖掘KG中的規(guī)則,利用規(guī)則進(jìn)行匹配,對實體間可能存在的鏈接進(jìn)行推理。歸納邏輯程序(Inductive Logic Programming,ILP)設(shè)計基于一階邏輯的歸納理論,從關(guān)系數(shù)據(jù)中挖掘Horn子句,例如MUGGLETON等[12]從關(guān)系數(shù)據(jù)中學(xué)習(xí)規(guī)則并實現(xiàn)逆蘊涵算法;GALRRAGA等[8]提出AIME模型,將關(guān)聯(lián)規(guī)則學(xué)習(xí)原理擴(kuò)展到Horn子句,用于挖掘傳遞性閉式規(guī)則,之后提出的AMIE+[13]優(yōu)化了AMIE算法,采用剪枝和近似策略挖掘更大的KG,利用類型信息和聯(lián)合推理來提高預(yù)測精度;TANON等[14]采用完全感知評分函數(shù)評估從KG中挖掘的規(guī)則,以提高規(guī)則質(zhì)量。該類方法的結(jié)果可解釋性強(qiáng)、精確率高,但只能預(yù)測一個新的鄰居鏈接,來自更“遠(yuǎn)”實體和鏈接的聚合效應(yīng)[15]仍有待進(jìn)一步探索。

基于概率推理的KG鏈接預(yù)測方法,旨在利用概率圖模型,如馬爾科夫網(wǎng)(Markov Logic Network,MLN)、BN等進(jìn)行實體間鏈接的推理,為鏈接賦予概率值。MLN是將MN與一階邏輯相結(jié)合的一種鏈接預(yù)測模型,其為每個一階邏輯賦予概率權(quán)重,能夠軟化一階邏輯知識的硬約束;概率軟邏輯(Probabilistic Soft Logic,PSL)[16]將一階謂詞邏輯與概率圖模型結(jié)合,與MLN使用0與1二值邏輯不同,其利用概率代替?zhèn)鹘y(tǒng)的硬邏輯推理,并用加權(quán)公式對推理規(guī)則的強(qiáng)度進(jìn)行約束,權(quán)重越大,約束能力越強(qiáng)。YUE等[17]提出CQBN模型,針對KG中實體間的不確定性關(guān)聯(lián)關(guān)系,以BN為知識表示和推理框架,將KG中描述的領(lǐng)域知識與用戶行為記錄中蘊含的知識進(jìn)行有效融合,并基于BN的概率推理算法計算實體間的關(guān)聯(lián)度。LI等[18]提出AEBN模型,將KG領(lǐng)域知識和外部知識有效融合,利用KG中的關(guān)聯(lián)規(guī)則,針對KG關(guān)聯(lián)實體查詢?nèi)蝿?wù),構(gòu)建了實體間依賴關(guān)系的規(guī)則誘導(dǎo)貝葉斯網(wǎng),再通過BN的近似推理計算出實體間的關(guān)聯(lián)度。然而,MLN模型與PSL模型仍基于規(guī)則進(jìn)行實體間鏈接的推理,無法對KG中實體間相互關(guān)聯(lián)的可能性進(jìn)行量化;CQBN模型與AEBN模型雖然能夠?qū)G中實體間的關(guān)聯(lián)關(guān)系進(jìn)行建模,但是均需人為給出大量的領(lǐng)域知識作為確立實體間關(guān)聯(lián)關(guān)系的先決條件。

3 RLBN模型的構(gòu)建及鏈接預(yù)測

3.1 相關(guān)定義

KG中實體間的鏈接關(guān)系表示為L(u,w),其中u?E表示任意實體對,且u=(ex,es),w為鏈接的關(guān)聯(lián)度。針對KG實體間的鏈接預(yù)測任務(wù),設(shè)置關(guān)聯(lián)度閾值ρ,若w≥ρ則該鏈接存在且L(u,w)=1,否則L(u,w)=0。

下面基于定義1給出RLBN的定義:

定義3RLBN表示為二元組g=(G,P),其中:

(1)G=(V,ε)為DAG結(jié)構(gòu),V={v1,v2,…,vn}?E(1≤n≤η)為節(jié)點的集合,且每一個節(jié)點vi對應(yīng)G中的一個實體ej。

(2)ε表示有向邊的集合,有向邊描述KG實體在g中的依賴關(guān)系。

(3)θ={P(v|Pa(v))|v∈V}為各節(jié)點條件概率參數(shù)的集合,每個節(jié)點的條件概率參數(shù)值構(gòu)成其CPT,Pa(v)表示v的父節(jié)點集合。

RLBN描述KG中不同實體依賴關(guān)系的圖結(jié)構(gòu),針對鏈接預(yù)測任務(wù),本文通過RLBN模型計算兩個節(jié)點間的條件概率值P,若概率值高于閾值,則認(rèn)為節(jié)點對應(yīng)的KG實體間存在鏈接。

3.2 抽取關(guān)聯(lián)實體集

為了尋找影響實體間鏈接關(guān)聯(lián)度的關(guān)聯(lián)實體集,首先采用AMIE算法挖掘如下Horn規(guī)則:

r1(e1,e2)∧r2(e2,e3)→r3(e1,e3)。

(1)

Horn規(guī)則的置信度體現(xiàn)了規(guī)則的可靠性,置信度越高,規(guī)則的可靠性越高,實體間存在鏈接的可能性越大;而且,規(guī)則中包含的實體越多,能夠挖掘到的關(guān)聯(lián)實體數(shù)目越多。因此,基于規(guī)則的置信度與實體數(shù)量,從挖掘得到的Horn規(guī)則中抽取規(guī)則集合,給出規(guī)則得分函數(shù)

Γ=α|N|+β。

(2)

式中:N為該規(guī)則所包含的實體集合;α為N的歸一化系數(shù);β為該規(guī)則的置信度。

(1)目標(biāo)函數(shù)

考慮規(guī)則的置信度與規(guī)則所包含實體數(shù)兩個因素,構(gòu)建目標(biāo)函數(shù)

(3)

(2)限界函數(shù)

(4)

(3)剪枝策略

用best表示當(dāng)前節(jié)點的最大目標(biāo)函數(shù)值,若關(guān)聯(lián)實體集與當(dāng)前tempe中的實體存在沖突,則剪去左孩子分枝;若當(dāng)前tempf及孩子節(jié)點得分不小于best,則生成左孩子,并加入最大堆作為待拓展節(jié)點;若up大于左孩子獲得的best,則該分支可能產(chǎn)生一個最優(yōu)解,為其生成右孩子節(jié)點,并加入最大堆作為待拓展節(jié)點。具體算法1如下:

算法1最優(yōu)無沖突規(guī)則實體挖掘。

3.whilei<|И|+1 do

5.if Si∩tempe=? and tempf+Γ(i)>best then

6. best←tempf+Γ(i);tempe←Si∪tempe

7. Insert to heap(Л,i+1,tempf+Γ(i),tempe,1)

8. end if

10. if up>best then

11. Insert to heap(Л,i+1,up,tempe,0)

12.end if

13. node←Delete max(Л)

14. i←node.level

15. tempe←node.tempe

16. tempf←node.tempf

17.end while

18.for i=|И|to l do

19. if node.leftchild=1 then

21. node←node.parent

22. end if

23.end for

3.3 基于規(guī)則的RLBN構(gòu)建

3.3.1 Horn子句轉(zhuǎn)換

KG中的三元組表示從頭實體指向尾實體的一條有向邊,Horn規(guī)則在KG中表示為實體間有向邊構(gòu)成的回路。將關(guān)系抽象為實體間有向的邏輯關(guān)聯(lián),并用蘊含式“→”代替,規(guī)則中的原子r(ei,ej)為KG中的一個三元組,表示為邏輯蘊涵式ei→ej,則Horn規(guī)則可表示為

(e1→e2)∧(e2→e3)→(e1→e3)。

(5)

(e1→e2)∧(e2←e3)→(e1→e3)。

(6)

基于逆處理結(jié)果,利用邏輯蘊涵式的等價轉(zhuǎn)換可以方便地將Horn規(guī)則轉(zhuǎn)換為3個實體的Horn子句

(7)

(8)

邏輯蘊涵式表達(dá)為

(9)

通過逆處理并根據(jù)邏輯表達(dá)式將式(9)轉(zhuǎn)換為描述實體間關(guān)聯(lián)的Horn子句

(10)

3.3.2 DAG的構(gòu)建

將Horn規(guī)則轉(zhuǎn)換為實體間Horn子句后,本文擴(kuò)展文獻(xiàn)[19]中將Horn子句轉(zhuǎn)換為DAG的算法,將一個實體指向另一個實體的邏輯蘊含表達(dá)式作為RLBN中邊對應(yīng)的關(guān)系,構(gòu)建反映KG關(guān)聯(lián)實體間依賴關(guān)系的DAG,并對影響KG鏈接關(guān)聯(lián)度的實體進(jìn)行建模,為關(guān)聯(lián)度的計算提供依據(jù)。

算法2構(gòu)建DAG。

(1)初始化:

1)將Horn規(guī)則轉(zhuǎn)換為邏輯蘊含表達(dá)式。

2)將實體e1所在的謂詞邏輯進(jìn)行逆處理。

3.3.3 參數(shù)計算

根據(jù)DAG中節(jié)點v是否有父親節(jié)點分別計算其概率參數(shù)。

(1)v無父親節(jié)點

KG中的三元組反映了實體間存在直接相連的路徑,不同三元組表示不同的路徑,因此通過KG中實體間的路徑數(shù)計算v的概率值。為了表達(dá)待測實體間的關(guān)聯(lián)性約束,借鑒文獻(xiàn)[20]計算網(wǎng)頁被訪問概率的方法,將待測實體對的頭實體的概率值視為1,即P(ex)=1,該實體出發(fā)至任意尾實體的概率值相同,所有至尾實體路徑的概率值之和表達(dá)了實體間的關(guān)聯(lián)程度。根據(jù)KG中實體間路徑數(shù)與總路徑數(shù)(查詢實體為頭實體的三元組總數(shù))的比值,基于實體間路徑的概率分配函數(shù),給出以下方法計算v的概率值:

(11)

式中:|Child(vj)|為KG中與節(jié)點vj對應(yīng)的實體ej的尾實體數(shù);|Sum(vj,v)|為KG中從ej到e的路徑數(shù);Ha(v)為v對應(yīng)的實體e在KG中的頭實體集合。

(2)v存在父親節(jié)點

v的概率值為其父親節(jié)點取值情形下該節(jié)點取值的條件概率。根據(jù)3.3.2節(jié)給出的方法,DAG根據(jù)節(jié)點間的布爾邏輯表達(dá)而構(gòu)建,節(jié)點v的條件概率參數(shù)應(yīng)描述相應(yīng)布爾表達(dá)式的邏輯約束,體現(xiàn)了父子節(jié)點取值之間的“或(OR)”關(guān)系?；谶@種布爾邏輯約束,下面給出節(jié)點v概率參數(shù)值的計算函數(shù):

P(v=?|Pa(v)=(?1,?2,…,?d))

(12)

式中:Pa(v)為v的父親節(jié)點集;?,?1,?2,…,?d∈{0,1},分別為節(jié)點v的父親節(jié)點取值。

表1 v1,v2∧v3和v4∧v5的CPT

3.4 基于RLBN概率推理的KG鏈接預(yù)測

本文利用RLBN的概率推理計算待測實體對間鏈接的關(guān)聯(lián)度w,設(shè)置閾值ρ,若w高于閾值,則認(rèn)為所預(yù)測的鏈接存在,L(u,w)=1,否則L(u,w)=0。為了快速得到鏈接預(yù)測結(jié)果,本文給出RLBN的近似推理算法來進(jìn)行實體間關(guān)聯(lián)度的概率推理,將后驗概率作為實體間的關(guān)聯(lián)度,據(jù)此判斷實體間是否存在鏈接關(guān)系。

馬爾科夫鏈蒙特卡羅算法[21](Monte Carlo Markov Chain,MCMC)是BN近似推理中廣泛使用的算法,其能夠合理統(tǒng)計網(wǎng)絡(luò)中真實的后驗概率,并能處理規(guī)模較大的BN。Gibbs采樣[22]是一個簡單且廣泛應(yīng)用的MCMC算法,其將含有不完全數(shù)據(jù)樣本的每一缺項作為待估參數(shù),通過一系列隨機(jī)抽樣來近似計算待估參數(shù)的后驗分布。因此,本文基于Gibbs采樣實現(xiàn)RLBN的近似推理,并基于后驗概率計算關(guān)聯(lián)度,從而實現(xiàn)鏈接預(yù)測。

算法3基于RLBN近似推理的鏈接預(yù)測。

輸出:鏈接預(yù)測結(jié)果L(s,w)。

1.θ←0;w←0;γ←0

2.隨機(jī)生成一個與vx狀態(tài)一致的初始樣本Y1

3.for i←1 to μ do

4. 基于當(dāng)前狀態(tài)Yi-1計算被選變量的概率

6. γ←P(vi=0|(MB(vi)))+P(vi=1|(MB(vi)))

7.生成隨機(jī)數(shù)λ∈[0,γ],確定vi的值:

8.使用采樣結(jié)果替代Yi-1中vi的值

9.end for

10.for l←1 to μ do

11. if Yi=1 then

12. θ←θ+1

13. end if

14.end for

15.P(vs=1|vx=1)←θ/μ

16.w←P(vs=1|vx=1)

17.if w≥ρ then

18. L(s,w)←1

19.else

20. L(s,w)←0

21.end if

22.return L(s,w)

4 實驗

4.1 實驗環(huán)境

使用1臺TS860服務(wù)器,配置如下:4個Intel(R) Xeon(R) E7-4830 v2,2.20 GHz CPU,755 GB內(nèi)存,每個CPU有10個物理核。

4.2 數(shù)據(jù)集

本文使用4個不同類型和不同大小的數(shù)據(jù)集:大規(guī)模Freebase的一個子集FB15K[5],抽取于英語詞匯數(shù)據(jù)庫WN18[15]的WordNet,在NELL上第995次迭代而構(gòu)建的NELL-995[15],以及YAGO3的一個子集YAGO3-10[9]。表2所示為以上數(shù)據(jù)集的描述。

表2 數(shù)據(jù)集描述

4.3 邏輯規(guī)則

采用AMIE算法在4個數(shù)據(jù)集上挖掘邏輯規(guī)則,并通過逆處理增加了規(guī)則數(shù)量,表3所示為置信度為0.1時挖掘得到的規(guī)則數(shù)及其逆處理的結(jié)果。

表3 AMIE邏輯規(guī)則挖掘及其逆處理結(jié)果

4.4 評價指標(biāo)

MR反映模型在測試集上正確的三元組實體對的得分排名均值,其值越小,正確的三元組排名越靠前,模型預(yù)測的結(jié)果越好;Hit@K也反映正確的三元組實體對的得分排名情況,表示正確的三元組實體對在前K個結(jié)果所占的比率。特別地,在替換測試集中三元組的實體時,會出現(xiàn)原本存在于KG中的三元組,未將其剔除計算得到的MR和Hit@K結(jié)果稱為“Raw”,剔除后計算得到的MR和Hit@K結(jié)果稱為“Filtered”;Precision@K表示待測實體對間鏈接權(quán)重的排序結(jié)果,兩個實體間的鏈接關(guān)聯(lián)度越大,其值越高,排名越靠前;Recall@K表示排序在前K的實體數(shù)量在所有測試集的比率。Precision@K和Recall@K定義如下:

(13)

式中:ПK為具有最高關(guān)聯(lián)度的前K個實體對集合;Б為測試集。

4.5 對比模型

本文選擇TransE[5],TransH[6],TransR[7],ConvE[9],RotatE[23],AMIE[8],RPJE[10]7個模型作為對比模型。其中:TransE為基于翻譯機(jī)制的嵌入學(xué)習(xí)模型;TransH和TransR是對該模型的改進(jìn);ConvE采用二維卷積神經(jīng)網(wǎng)絡(luò)實現(xiàn)嵌入學(xué)習(xí);RotatE將實體間的關(guān)系定義為在向量空間中從源實體到目標(biāo)實體的旋轉(zhuǎn);AMIE利用所挖掘的閉環(huán)Horn規(guī)則完成鏈接預(yù)測任務(wù),使用規(guī)則的置信度為實體間的鏈接預(yù)測提供依據(jù);RPJE基于規(guī)則和路徑的聯(lián)合嵌入學(xué)習(xí)來實現(xiàn)鏈接預(yù)測。

4.6 參數(shù)設(shè)置

在采用AMIE算法挖掘規(guī)則時,本文以算法默認(rèn)的最低置信度為閾值,設(shè)置Horn規(guī)則挖掘的最小置信度為0.1,同時AMIE算法挖掘規(guī)則的長度不高于4,以避免規(guī)則過長帶來高昂的挖掘時間開銷。本文選擇與規(guī)則長度相同的路徑長度,在計算CPT時設(shè)置實體間的最大路徑長度為4。測試數(shù)據(jù)集中無規(guī)則匹配的實體對及替換后無規(guī)則匹配的實體對的關(guān)聯(lián)度為0。

4.7 實驗結(jié)果

4.7.1 規(guī)則置信度對RLBN模型的影響

首先測試不同置信度值下RLBN模型鏈接預(yù)測結(jié)果的精確率,結(jié)果如表4所示。在各個數(shù)據(jù)集上,隨著置信度的增加,精確率會出現(xiàn)一個峰值。在FB15K數(shù)據(jù)集上,當(dāng)閾值為0.8時,其精確率達(dá)到最高的0.843;當(dāng)WN18和NELL-995數(shù)據(jù)上的閾值為0.4時,其精確率分別達(dá)到0.975和0.865:當(dāng)YAGO數(shù)據(jù)集上的閾值為0.7時,精確率最高為0.874。由此可知,在FB15K數(shù)據(jù)集上,RLBN模型鏈接預(yù)測結(jié)果的精確率在不同規(guī)則置信度下變化較大,峰值與谷值相差0.181,這是因為FB15K數(shù)據(jù)集上的規(guī)則較多,當(dāng)置信度低的規(guī)則數(shù)目較多時,模型的結(jié)果將產(chǎn)生偏差。其他3個數(shù)據(jù)集中的規(guī)則相對較少,隨著置信度閾值的變化,RLBN模型的準(zhǔn)確率變化平緩,尤其在WN18數(shù)據(jù)集各置信度閾值上的精確率均高于其他數(shù)據(jù)集?？傊?RLBN模型在4個數(shù)據(jù)集上均能保持較高的精確率,表明RLBN模型可以有效判斷實體間的鏈接,并完成鏈接預(yù)測任務(wù)。

表4 置信度對鏈接預(yù)測精確率的影響

4.7.2 關(guān)聯(lián)度的有效性測試

為了測試基于RLBN的關(guān)聯(lián)度計算方法的有效性,將測試集中的三元組進(jìn)行實體替換,并將頭實體或尾實體隨機(jī)替換成錯誤的三元組放入原測試集數(shù)據(jù)中形成新的測試集,將RLBN與TransH[11],RPJE[10],AMIE[14]模型的Precision@K和Recall@K進(jìn)行對比。圖5所示為在4個不同數(shù)據(jù)集上不同模型的Precision@K指標(biāo)值隨K增加的變化?？梢?RLBN模型在4個數(shù)據(jù)集上的Precision@K指標(biāo)值均優(yōu)于TransH,RPJE,AMIE基準(zhǔn)模型,具體而言,在FB15K數(shù)據(jù)集上,隨著K值的增加,RLBN的Precision@K指標(biāo)值下降趨勢平緩,高于基準(zhǔn)模型,AMIE模型的Precision@K指標(biāo)下降明顯,穩(wěn)定性隨著K值的增加而變差;在WN18數(shù)據(jù)集上,RLBN的Precision@K值遠(yuǎn)高于基準(zhǔn)模型,各基準(zhǔn)模型的Precision@K值下降明顯,RLBN表現(xiàn)出較高的穩(wěn)定性;在NELL-995數(shù)據(jù)集上,相比其他數(shù)據(jù)集,RLBN的下降趨勢雖然有所增加,但是Precision@K指標(biāo)高于其他基準(zhǔn)模型,AMIE與TransH均出現(xiàn)不穩(wěn)定狀況;在YAGO3-10數(shù)據(jù)集上,RLBN的指標(biāo)值略高于TransH且遠(yuǎn)優(yōu)于AMIE。這些結(jié)果表明,與AMIE,TransH,RPJE相比,RLBN能夠檢索到更多有效的鏈接,將其排在首位。

圖6所示為在4個不同類型數(shù)據(jù)集上,不同模型的Recall@K指標(biāo)隨K增加的變化。可見,本文模型在Recall@K指標(biāo)上也具有優(yōu)異的表現(xiàn),指標(biāo)值均顯著優(yōu)于所選的基準(zhǔn)模型。具體而言,在FB15K數(shù)據(jù)集上,RLBN與RPJE和TransH的Recall@K指標(biāo)基本相同,隨著K值的增加,RLBN模型高于各基準(zhǔn)模型;在WN18數(shù)據(jù)集上,RLBN的效果最佳,其Recall@K指標(biāo)明顯高于各基準(zhǔn)模型,且K值越大效果越明顯;在NELL-995數(shù)據(jù)集上,RLBN的Recall@K指標(biāo)增長率高于各基準(zhǔn)模型;在YAGO3-10數(shù)據(jù)集上,RLBN和TransH的Recall@K指標(biāo)隨K值的增加而上升的趨勢基本相同,且均高于AMIE。由此可知,在這4個數(shù)據(jù)集上,與AMIE,TransH,RPJE相比,RLBN獲得了更高的Recall@K值。

4.7.3 鏈接預(yù)測結(jié)果的有效性

分別在4個數(shù)據(jù)集上隱去頭實體或尾實體(即(h,r,?)或(?,r,t)),用任意實體隨機(jī)替換隱去的實體并通過模型計算所有替換實體后的三元組得分,測試MR和Hit@10指標(biāo),如表5所示?？梢?在FB15K數(shù)據(jù)集上,RLBN在MR指標(biāo)的Raw部分僅次于RPJE,排名第2,其余指標(biāo)值優(yōu)于RPJE;在WN18數(shù)據(jù)集上,RLBN表現(xiàn)優(yōu)異,在兩個指標(biāo)上均排名第1;在NELL-995數(shù)據(jù)集上,RLBN的MR指標(biāo)值僅次于ConvE和TransR,具體在Raw部分低于最好的ConvE,在Filtered部分低于次好的TransR。對于Hit@10指標(biāo),本文模型的Raw部分排名第1,在Filtered部分僅低于ConvE;在YAGO3-10數(shù)據(jù)集上,RLBN在MR指標(biāo)的Raw部分僅低于TransE,Filtered部分低于次好的TransR,排名第3;對于Hit@10指標(biāo),RLBN優(yōu)于所有基準(zhǔn)模型,在Raw與Filtered部分均排名第1。這表明RLBN模型能夠優(yōu)越地完成KG的鏈接預(yù)測任務(wù),基于RLBN近似推理的實體間關(guān)聯(lián)度計算方法可以有效進(jìn)行鏈接預(yù)測。

表5 鏈接預(yù)測性能比較

4.7.4 模型構(gòu)建和鏈接預(yù)測效率

不同規(guī)則實體數(shù)目下RLBN模型的構(gòu)建時間、基于不同數(shù)據(jù)集的TopK鏈接預(yù)測查詢處理時間、基于不同數(shù)據(jù)集的不同鏈接預(yù)測模型構(gòu)建時間,分別如圖7～圖9所示。

(1)不同規(guī)則實體數(shù)目下的RLBN模型構(gòu)建時間

通過改變規(guī)則實體數(shù)目記錄RLBN的構(gòu)造時間,如圖7所示。RLBN模型的構(gòu)造時間主要包括DAG構(gòu)造時間和CPT計算時間兩部分。由算法1和算法2可知,DAG的構(gòu)造時間與規(guī)則實體的數(shù)目相關(guān),而且由3.3.3節(jié)的CPT計算方式可知,其效率與規(guī)則實體數(shù)目和數(shù)據(jù)集的規(guī)模相關(guān)。FB15K數(shù)據(jù)集包含的實體數(shù)目較多,由于匹配的規(guī)則和實體數(shù)較多,模型構(gòu)建的時間開銷最大;YAGO3-10數(shù)據(jù)集的規(guī)模最大,但是因為其含有的規(guī)則數(shù)目較少,進(jìn)行規(guī)則匹配時的時間花銷較少,模型的構(gòu)建時間大大降低,所以所花的時間低于FB15K;NELL-995數(shù)據(jù)集與YAGO3-10相似,但數(shù)據(jù)規(guī)模低于YAGO3-10,因此模型的構(gòu)建效率高于YAGO3-10;WN18數(shù)據(jù)集無論數(shù)據(jù)規(guī)模還是規(guī)則數(shù)目均最低,因此該模型構(gòu)建的時間花銷最少?？梢缘贸鼋Y(jié)論,基于同一數(shù)據(jù)集,RLBN構(gòu)建時間隨著規(guī)則實體數(shù)目的增加而呈線性增加。

(2)不同數(shù)據(jù)集的TopK鏈接預(yù)測查詢處理時間

不同數(shù)據(jù)集的TopK鏈接預(yù)測查詢處理時間如圖8所示?？梢?RLBN模型能夠快速查詢出與給定實體相關(guān)聯(lián)的前K個實體,在YAGO3-10數(shù)據(jù)集上模型查詢的時間最長,這是因為查詢關(guān)聯(lián)實體集時要搜索數(shù)據(jù)集的實體集,YAGO3-10數(shù)據(jù)集的實體數(shù)目最多,因此搜索時所花的時間最長;相反,在WN18數(shù)據(jù)集上,由于其實體數(shù)量較小,在查詢TopK關(guān)聯(lián)實體集時所花的時間也最少。然而,雖然FB15K數(shù)據(jù)集實體數(shù)目較少,但是其規(guī)則數(shù)目較多,一個實體通過不用規(guī)則重復(fù)關(guān)聯(lián)同一實體,RLBN模型需要對這些實體進(jìn)行去重選擇,增加了模型查詢的時間,因此所花的時間大于WN18模型。總之,RLBN模型能夠在不同數(shù)據(jù)集上快速查詢實體相關(guān)聯(lián)的前K個實體,體現(xiàn)了本文模型關(guān)聯(lián)度計算方法的高效性。

(3)不同數(shù)據(jù)集不同鏈接預(yù)測模型的構(gòu)建時間

不同數(shù)據(jù)集不同鏈接預(yù)測模型的構(gòu)建時間如圖9所示。RLBN模型基于4個數(shù)據(jù)集的所有實體構(gòu)建模型的時間開銷僅大于AMIE方法,原因是構(gòu)造本文模型基于AMIE挖掘的規(guī)則;相比基于“嵌入+規(guī)則”的模型RPJE,RLBN模型的構(gòu)建效率在3個數(shù)據(jù)集上分別提升3.1,3.5,4倍,時間開銷遠(yuǎn)低于RPJE。這表明本文所提RLBN模型能夠在不同規(guī)模數(shù)據(jù)集上高效地構(gòu)建,展示了RLBN模型的優(yōu)越性。

5 結(jié)束語

本文提出基于概率推理的鏈接預(yù)測模型RLBN,該模型用BN作為框架,通過挖掘KG中蘊含的Horn規(guī)則提取滿足規(guī)則的關(guān)聯(lián)實體集,給出從Horn規(guī)則等價轉(zhuǎn)換為實體間Horn子句的方法,利用實體間的Horn子句構(gòu)建描述實體間依賴關(guān)系的RLBN,并采用Gibbs采樣算法的近似推理計算出實體間的條件概率值,計算實體間鏈接的關(guān)聯(lián)度。實驗表明,本文模型可以有效描述實體間隱含的關(guān)聯(lián)關(guān)系并度量實體間存在鏈接的可能性,從而高效地完成鏈接預(yù)測任務(wù)。

本文提出的實體間的鏈接關(guān)聯(lián)度計算方法,作為發(fā)現(xiàn)實體間隱含鏈接的一種探索,仍是一種局部的關(guān)聯(lián)實體挖掘算法,Horn規(guī)則的長度決定了挖掘計算的范圍,當(dāng)涉及KG中更“遠(yuǎn)”的實體時,構(gòu)建模型的計算復(fù)雜度較高,且所構(gòu)建的RLBN規(guī)模也較大。對此,如何拓展本文模型對全局的KG實體與關(guān)系進(jìn)行建模,考慮基于表示學(xué)習(xí)和貝葉斯信息標(biāo)準(zhǔn)(Bayes Information Criteria,BIC)建立新的吻合度度量函數(shù),進(jìn)一步發(fā)現(xiàn)更多的隱含實體鏈接,是未來將要開展的工作。