基于概率推理的知識(shí)圖譜鏈接預(yù)測(cè)方法

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

(1.云南大學(xué) 信息學(xué)院,云南 昆明 650500;2.云南大學(xué) 云南省智能系統(tǒng)與計(jì)算重點(diǎn)實(shí)驗(yàn)室,云南 昆明 650500;3.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,云南 昆明 650504)

1 問(wèn)題的提出

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3.1 相關(guān)定義

KG中實(shí)體間的鏈接關(guān)系表示為L(zhǎng)(u,w),其中u?E表示任意實(shí)體對(duì),且u=(ex,es),w為鏈接的關(guān)聯(lián)度。針對(duì)KG實(shí)體間的鏈接預(yù)測(cè)任務(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é)點(diǎn)的集合,且每一個(gè)節(jié)點(diǎn)vi對(duì)應(yīng)G中的一個(gè)實(shí)體ej。

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

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

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

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

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

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

(1)

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

Γ=α|N|+β。

(2)

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

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

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

(3)

(2)限界函數(shù)

(4)

(3)剪枝策略

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

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

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

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

(5)

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

(6)

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

(7)

(8)

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

(9)

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

(10)

3.3.2 DAG的構(gòu)建

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

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

(1)初始化:

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

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

3.3.3 參數(shù)計(jì)算

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

(1)v無(wú)父親節(jié)點(diǎn)

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

(11)

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

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

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

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

(12)

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

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

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

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

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

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

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

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

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

3.for i←1 to μ do

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

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 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

4.3 邏輯規(guī)則

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

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

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

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

(13)

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

4.5 對(duì)比模型

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

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

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

4.7 實(shí)驗(yàn)結(jié)果

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

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

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

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

為了測(cè)試基于RLBN的關(guān)聯(lián)度計(jì)算方法的有效性,將測(cè)試集中的三元組進(jìn)行實(shí)體替換,并將頭實(shí)體或尾實(shí)體隨機(jī)替換成錯(cuò)誤的三元組放入原測(cè)試集數(shù)據(jù)中形成新的測(cè)試集,將RLBN與TransH[11],RPJE[10],AMIE[14]模型的Precision@K和Recall@K進(jìn)行對(duì)比。圖5所示為在4個(gè)不同數(shù)據(jù)集上不同模型的Precision@K指標(biāo)值隨K增加的變化。可見(jiàn),RLBN模型在4個(gè)數(shù)據(jù)集上的Precision@K指標(biāo)值均優(yōu)于TransH,RPJE,AMIE基準(zhǔn)模型,具體而言,在FB15K數(shù)據(jù)集上,隨著K值的增加,RLBN的Precision@K指標(biāo)值下降趨勢(shì)平緩,高于基準(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的下降趨勢(shì)雖然有所增加,但是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個(gè)不同類型數(shù)據(jù)集上,不同模型的Recall@K指標(biāo)隨K增加的變化?？梢?jiàn),本文模型在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ǎng)率高于各基準(zhǔn)模型;在YAGO3-10數(shù)據(jù)集上,RLBN和TransH的Recall@K指標(biāo)隨K值的增加而上升的趨勢(shì)基本相同,且均高于AMIE。由此可知,在這4個(gè)數(shù)據(jù)集上,與AMIE,TransH,RPJE相比,RLBN獲得了更高的Recall@K值。

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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