基于概率推理的知識(shí)圖譜中實(shí)體間關(guān)聯(lián)度計(jì)算

李寧?kù)o

(云南大學(xué) 信息學(xué)院，云南 昆明 650500)

0 引 言

知識(shí)圖譜(knowledge graph，KG)[1]通過表示學(xué)習(xí)可計(jì)算，被用作知識(shí)查詢、個(gè)性化推薦中重要的知識(shí)儲(chǔ)備庫(kù)，分析和量化KG中的實(shí)體間關(guān)聯(lián)關(guān)系是實(shí)現(xiàn)和提供這些服務(wù)的基礎(chǔ)和關(guān)鍵，而KG中的實(shí)體之間的關(guān)聯(lián)度計(jì)算是提供這些服務(wù)的重要依據(jù)[2-4]。KG中實(shí)體之間的關(guān)聯(lián)關(guān)系存在不確定性，通過KG結(jié)構(gòu)網(wǎng)絡(luò)中已知的實(shí)體以及實(shí)體之間存在的邊關(guān)系，計(jì)算KG中實(shí)體之間的關(guān)聯(lián)度，不僅能驗(yàn)證KG中實(shí)體之間已有關(guān)系的準(zhǔn)確性，還能為預(yù)測(cè)實(shí)體間存在的隱含關(guān)系提供可靠依據(jù)，進(jìn)而為KG的知識(shí)推理提供支撐技術(shù)。

針對(duì)KG中實(shí)體間關(guān)聯(lián)關(guān)系的表示和推理，文獻(xiàn)[5]通過樣例子圖以子圖同構(gòu)的方法衡量KG中的實(shí)體間關(guān)系；文獻(xiàn)[6]基于距離和結(jié)構(gòu)的相關(guān)性，提出了一種面向多源KG的實(shí)體間關(guān)聯(lián)度度量標(biāo)準(zhǔn)；文獻(xiàn)[7]將實(shí)體和關(guān)系嵌入到向量空間，并以向量空間距離判斷實(shí)體間的相似性；文獻(xiàn)[8]利用實(shí)體的語(yǔ)義上下文作為實(shí)體間相似性度量的補(bǔ)充方法，從而評(píng)估三元組存在的可能性。上述方法雖然為KG中實(shí)體間關(guān)聯(lián)度的計(jì)算方法提供了思路，但并沒有明確地對(duì)實(shí)體間的關(guān)聯(lián)關(guān)系進(jìn)行定量描述，且不能有效定量地分析和表示關(guān)聯(lián)關(guān)系存在的不確定性。

基于以上的研究分析，考慮到貝葉斯網(wǎng)(Bayesian network，BN)[9]對(duì)于不確定知識(shí)表示和推理的有效性，本文通過構(gòu)建基于KG的BN(knowledge graph based Bayesian network，KBN)來描述KG中實(shí)體之間的關(guān)聯(lián)關(guān)系，進(jìn)而基于KBN的概率推理定量地表示KG中實(shí)體之間的關(guān)聯(lián)關(guān)系。根據(jù)KG實(shí)體間關(guān)聯(lián)度的計(jì)算，可以獲取更為完整和真實(shí)的KG。

1 問題描述和相關(guān)定義

KG通過三元組描述了現(xiàn)實(shí)世界中的實(shí)體(entity)及其之間的關(guān)系(relation)，在結(jié)構(gòu)網(wǎng)絡(luò)中利用一條有向邊及其鏈接的兩個(gè)實(shí)體[10]表示三元組(實(shí)體1，關(guān)系，實(shí)體2)，KG中每個(gè)三元組表示一個(gè)事實(shí)，如三元組(“電影A”，“主演”，“演員A”)表示“電影A的主演是演員A”。對(duì)于描述特定領(lǐng)域知識(shí)的KG，KG中的實(shí)體分為核心實(shí)體和屬性實(shí)體兩類，其中核心實(shí)體由其鏈接的屬性實(shí)體作知識(shí)描述，根據(jù)鏈接邊的關(guān)系標(biāo)簽，屬性實(shí)體又有具體的劃分。針對(duì)KG中不存在鏈接的核心實(shí)體和屬性實(shí)體，兩者間的不確定性關(guān)聯(lián)關(guān)系是研究的重點(diǎn)，如何計(jì)算它們之間的關(guān)聯(lián)度是本文研究的核心問題。借助已有的關(guān)聯(lián)關(guān)系，通過實(shí)體間關(guān)聯(lián)度的計(jì)算，發(fā)現(xiàn)核心實(shí)體和不存在鏈接的屬性實(shí)體之間的關(guān)系，是本文的主要工作。

BN是一種描述變量間依賴關(guān)系的概率圖模型[11]，網(wǎng)絡(luò)結(jié)構(gòu)為有向無環(huán)圖(directed acyclic graph，DAG)，其中節(jié)點(diǎn)表示隨機(jī)變量，有向邊表示變量之間的依賴關(guān)系，同時(shí)每個(gè)節(jié)點(diǎn)的條件概率表(conditional probability table，CPT)表示該節(jié)點(diǎn)父節(jié)點(diǎn)的狀態(tài)概率[12,13]。若已知BN中給定證據(jù)變量取值時(shí)，通過概率推理可計(jì)算出其它變量不同取值的條件概率。BN被廣泛用于不確定知識(shí)的學(xué)習(xí)和推理[9]，適用于表示和分析不確定性知識(shí)，并能夠?qū)Σ淮_定性知識(shí)作出快速有效的推理。因此通過構(gòu)建KBN，可以利用KBN的DAG中的變量表示KG中的實(shí)體分類，利用CPT定量描述實(shí)體之間的關(guān)聯(lián)性。

具體而言，本文的主要研究工作包括：

(1)考慮到需要計(jì)算關(guān)聯(lián)度的實(shí)體的范圍選擇對(duì)實(shí)體間關(guān)聯(lián)度計(jì)算效率的影響，本文對(duì)KG的圖結(jié)構(gòu)進(jìn)行剪枝處理，提出了以實(shí)體平均權(quán)重值為依據(jù)的分支限界方法，從而確定KG子圖并縮小推理計(jì)算范圍，最終降低實(shí)體間關(guān)聯(lián)度計(jì)算的時(shí)間復(fù)雜度。

(2)考慮KG中實(shí)體關(guān)聯(lián)的不確定性和關(guān)聯(lián)度度量的有效性，本文基于剪枝后的KG構(gòu)建KBN，提出基于KG的KBN構(gòu)建方法，其中KBN的構(gòu)建包括DAG構(gòu)建和CPT計(jì)算；進(jìn)而利用KBN的概率推理作為KG中實(shí)體間關(guān)聯(lián)度的定量依據(jù)，提出基于KBN的KG中實(shí)體之間關(guān)聯(lián)度的計(jì)算方法。

(3)基于FB15k[14]數(shù)據(jù)集，本文實(shí)現(xiàn)并測(cè)試了KBN構(gòu)建和實(shí)體間關(guān)聯(lián)度計(jì)算方法的有效性。

KG定義請(qǐng)參見文獻(xiàn)[15]，其中對(duì)于GK的實(shí)體集合VK，U={U1,U2,…,Um} 表示核心實(shí)體的集合，Oi={o1,o2,…,ok}(1≤i≤m) 表示核心實(shí)體Ui在GK中對(duì)應(yīng)的屬性實(shí)體集合，因此Ui可以由Oi來特定標(biāo)識(shí)。

例如，圖1是根據(jù)現(xiàn)實(shí)世界中的電影數(shù)據(jù)信息，構(gòu)建的一個(gè)有關(guān)電影領(lǐng)域的KG。電影領(lǐng)域KG的核心實(shí)體為電影，其中電影屬性實(shí)體又有具體的分類，主要包括“演員”、“導(dǎo)演”、“電影類型”和“編劇”等類型。針對(duì)圖1中的KG，“電影B”的主演是“演員B”，而另一部“電影A”與“電影B”具有相同的導(dǎo)演和電影類型，則“演員B”很有可能也是“電影A”的主演，即兩者之間的關(guān)聯(lián)關(guān)系存在不確定性。本文通過已有的實(shí)體與實(shí)體間關(guān)系，計(jì)算“電影A”與“演員B”的關(guān)聯(lián)度，為目標(biāo)實(shí)體組(“演員B”，“電影A”)是否存在關(guān)聯(lián)提供定量的依據(jù)(即虛線邊是否真實(shí)存在)。

圖1 簡(jiǎn)化的KG

KG中實(shí)體間關(guān)聯(lián)度的計(jì)算時(shí)間復(fù)雜度，與目標(biāo)實(shí)體組為中心的范圍選擇有關(guān)，為此本文對(duì)KG的規(guī)模與結(jié)構(gòu)進(jìn)行預(yù)處理，具體步驟為：①提取KG的d步子圖，其實(shí)現(xiàn)方法見定義1；②在d步子圖的基礎(chǔ)上引出實(shí)體平均權(quán)重值value(vi)的概念，其計(jì)算方法見定義2；③通過分支限界算法提取以目標(biāo)實(shí)體組為核心的KG核心子圖(central sub-graph，CSG)，并以核心子圖作為構(gòu)建KBN的初始結(jié)構(gòu)，其具體實(shí)現(xiàn)方法見2.1節(jié)。

定義1Gd是GK的d步可達(dá)子圖，其中Gd滿足以下條件：①弱連接；②包含以目標(biāo)實(shí)體組為起點(diǎn)d步內(nèi)可達(dá)的所有實(shí)體及其連接邊(包含目標(biāo)實(shí)體)，d為設(shè)置的路徑長(zhǎng)度。

例如，設(shè)置d=2，圖2則為圖1的d步可達(dá)子圖，并以此作為之后計(jì)算實(shí)體平均權(quán)重值和獲取GK核心子圖的依據(jù)。

圖2 d=2的Gd

KG中出現(xiàn)頻率低的關(guān)系更能度量實(shí)體之間的相似性[5]，同時(shí)實(shí)體節(jié)點(diǎn)度[15]也是衡量實(shí)體重要性的有效指標(biāo)。因此本文引出實(shí)體平均權(quán)重值的概念，實(shí)體的重要程度可由節(jié)點(diǎn)度和其連接邊的逆邊標(biāo)簽頻率[5]綜合反映。實(shí)體平均權(quán)重值越大，說明該實(shí)體在圖結(jié)構(gòu)中的重要程度越高，以此作為之后剪枝工作的依據(jù)，這樣能保證KG的規(guī)?？s減是有效的。

定義2 基于Gd的實(shí)體vi的平均權(quán)重值value(vi)，反映實(shí)體vi在圖結(jié)構(gòu)中的重要程度，其計(jì)算公式如式(1)所示

(1)

ief(e)=log(|E(G)|/#label(e))

(2)

其中，ief(e) 為逆邊標(biāo)簽頻率，其表示邊標(biāo)簽在Gd中出現(xiàn)的頻率越小，則該邊標(biāo)簽越重要；Ei為與實(shí)體vi相連接的邊的集合， ∑ief(e) 表示邊集合Ei中所有邊e的逆邊標(biāo)簽頻率值之和，Ci為實(shí)體vi的節(jié)點(diǎn)度，即與實(shí)體vi相連的邊數(shù)之和；ief(e) 的計(jì)算公式如式(2)， |E(G)| 為Gd中的邊總數(shù)， #label(e) 為Gd中與邊e有著相同標(biāo)簽的邊數(shù)。根據(jù)圖2的各實(shí)體value(vi) 值計(jì)算見表1。

表1 Gd的value(vi) 值計(jì)算結(jié)果

定義3 KBN：KBN用一個(gè)二元組G=(GB,θ) 表示，其中：

(1)GB=(XB,EB) 為KBN的DAG結(jié)構(gòu)，XB={X1,X2,…,Xm} 為變量集合，其中每個(gè)變量分別對(duì)應(yīng)KG中的一種實(shí)體的分類；EB為有向邊集合，其中 表示由Xi到Xj的有向邊，Xi被稱為Xj的一個(gè)父節(jié)點(diǎn)，Xj的父節(jié)點(diǎn)集記為Pa(Xj)。

(2)θ={p(Xi|Pa(Xi))}, (Xi∈XB) 為條件概率分布的集合，由各變量CPT中的概率參數(shù)值構(gòu)成。

針對(duì)目標(biāo)實(shí)體組(核心實(shí)體，屬性實(shí)體)的關(guān)聯(lián)度計(jì)算，核心實(shí)體可以由其鏈接的屬性實(shí)體唯一表示，因此本文構(gòu)建屬性實(shí)體之間依賴關(guān)系的KBN，其中根據(jù)邊標(biāo)簽可以將屬性實(shí)體再作具體的分類，每個(gè)分類對(duì)應(yīng)KBN中的各個(gè)變量。對(duì)于圖1中的電影領(lǐng)域KG而言，針對(duì)目標(biāo)實(shí)體組(“電影A”，“演員B”)，通過構(gòu)建電影屬性類實(shí)體間關(guān)系的KBN，圖1中的實(shí)體“演員B”對(duì)應(yīng)KBN中的“演員”變量的特定取值，核心實(shí)體“電影A”可以由電影屬性實(shí)體“導(dǎo)演A”和“動(dòng)作片”來標(biāo)識(shí)，即KBN中“導(dǎo)演”與“電影類型”這兩個(gè)變量的特定取值。因此，目標(biāo)實(shí)體組的關(guān)聯(lián)度可以定量地表示為條件概率p(“演員”=演員B |“導(dǎo)演”=導(dǎo)演A，“電影類型”=動(dòng)作片)。

2 KBN構(gòu)建

本文提出基于Gd和value(vi)值的KBN構(gòu)建方法，首先基于GK生成Gd并計(jì)算value(vi)值，以此獲取CSG，并基于CSG作為初始結(jié)構(gòu)構(gòu)建KBN的DAG。進(jìn)而利用DAG和抽取得到的數(shù)據(jù)集D計(jì)算得到CPT，從而完成KBN的構(gòu)建。

2.1 獲取CSG

定義4 CSG： 核心子圖(central sub-graph，CSG)，表示為剪枝后最優(yōu)的Gd子圖，即目標(biāo)評(píng)分函數(shù)Scoremax(Gd)為最大且同時(shí)滿足①包含不少于Nmin個(gè)實(shí)體;②Scoremax(Gd)不小于閾值E。

CSG的獲取由分支限界算法[16]實(shí)現(xiàn)，其目的是從Gd中獲取基于目標(biāo)實(shí)體組的最優(yōu)結(jié)構(gòu)，并同時(shí)縮減Gd的規(guī)模。因此，基于各實(shí)體value(vi)值的計(jì)算和CSG的定義4，本文通過分支限界算法對(duì)Gd進(jìn)行實(shí)體范圍的縮減，從而獲取Gd的最優(yōu)子結(jié)構(gòu)(即CSG)，保證GK優(yōu)化的有效性，并以此作為構(gòu)造KBN的初始結(jié)構(gòu)。具體思想與算法1 如下：

其中，W表示Gd中所有實(shí)體的value(vi)值之和；Nmax表示最多要選的實(shí)體總數(shù)(包括目標(biāo)實(shí)體)；Nmin表示最少要選的實(shí)體數(shù)(包括目標(biāo)實(shí)體)；W’表示最少要選的實(shí)體的value(vi)值之和；分支限界算法的目標(biāo)函數(shù)見式(3)，SWi的值取0或1(0表示該實(shí)體沒選，1表示該實(shí)體選上)，在約束條件的前提下，盡可能找到value(vi)值之和最大的子圖

(3)

算法1： 分支限界算法

輸入：Gd：GK的k步子圖

輸出： {SW1,SW2, …,SWn}

(1) 初始化，構(gòu)造一個(gè)空的最大堆H， 初始一個(gè)子集樹T

(2) 計(jì)算每個(gè)實(shí)體的value(vi)值，W值

(3)best←0，i←1，j←1，tempW←0，Wi←0，n←Gd的實(shí)體數(shù)

(4)WHILEi≠n+1DO//子集樹的構(gòu)建過程

(5)IFi≤tTHEN//t為目標(biāo)實(shí)體組中的實(shí)體個(gè)數(shù)

(6)tempW←tempW+value(vi)；Wi←Wi+value(vi)

(7)best←best+value(vi)；SWi←1；i←i+1；j←j+1

(8)ENDIF

(9)IF(j≤Nmax) and (n-i+j≥Nmin) and (tempW+(W-Wi)≥W’)THEN

(10)IFbest

(11)best←tempW+value(vi)；Wi←Wi+value(vi)；j←j+1

(12) InsertToHeap(H,i+1,tempW+value(vi), 1) //構(gòu)建左子樹

(13)ENDIF

(14)upbound←0

(15)FORs←i+1TonDO

(16)upbound←upbound+value(vi)

(17)ENDFOR

(18)IF(upbound≥Wi) and (n-i+j-2≥n′)THEN

(19) InsertToHeap(H,i+1,upbound, 0) //構(gòu)建右子樹

(20)ENDIF

(21)enode←removeMaxFromHeap(H)；i←enode.level

(22)ENDWHILE

(23)FORi←nDOWNTOt+1DO

(24)IFenode.leftchild=1THENSWi←1

(25)ELSESWi←0

(26)ENDIF

(27)enode←enode.parent

(28)ENDFOR

(29)Return{SW1,SW2, …,SWn}

在算法1的步驟(5)-步驟(8)中，本文將目標(biāo)實(shí)體構(gòu)造作為樹的根節(jié)點(diǎn)，因?yàn)樽詈蟮淖訄D結(jié)構(gòu)中目標(biāo)實(shí)體必須保留。步驟(10)-步驟(13)中，考慮選擇第i個(gè)實(shí)體，即當(dāng)前節(jié)點(diǎn)的左孩子。步驟(14)-步驟(20)中，根據(jù)計(jì)算可能的最大上界值upbound來判斷是否產(chǎn)生右孩子。步驟(18)用來判斷右孩子的產(chǎn)生是否會(huì)有最優(yōu)解。步驟(21)中，將最大堆H中的根節(jié)點(diǎn)移除，最大堆中可以得到下一個(gè)待拓展節(jié)點(diǎn)。步驟(23)-步驟(29)中，通過生成的路徑中從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)，由下往上層遍歷，獲取最優(yōu)子集 {SW1,SW2,…,SWn}， 即最終CSG的圖結(jié)構(gòu)。

由圖2的Gd作為算法1的輸入，通過表1計(jì)算得到的實(shí)體value(vi)值，剪枝過程和最終得到的GK對(duì)應(yīng)的CSG，如圖3所示。

圖3 剪枝得到的CSG

2.2 DAG構(gòu)建

KBN的DAG構(gòu)建包括如下3個(gè)方面的問題：①確定變量節(jié)點(diǎn)之間是否存在邊；②確定存在邊的變量節(jié)點(diǎn)之間邊的方向；③構(gòu)建DAG的過程中保證不出現(xiàn)環(huán)。

針對(duì)問題①，基于獲取的CSG得到KG中各實(shí)體間的鏈接關(guān)系，若CSG中不同的屬性類實(shí)體之間存在可達(dá)路徑，則認(rèn)為對(duì)應(yīng)變量節(jié)點(diǎn)之間存在邊。針對(duì)問題①，基于value(vi)值的計(jì)算式(1)，以KBN中變量對(duì)應(yīng)的不同取值實(shí)體平均權(quán)重值value(vi)之和N作為其重要程度依據(jù)，若N(Xi)>N(Xj)， 即表示邊應(yīng)由Xi指向Xj，N值計(jì)算公式如式(4)所示

N(Xi)=∑value(vi)
(vi為變量Xi各取值對(duì)應(yīng)的屬性實(shí)體)

(4)

針對(duì)問題③，通過N值計(jì)算確定各變量節(jié)點(diǎn)間的鏈接關(guān)系，并以鄰接矩陣的方式存儲(chǔ)。之后任選一個(gè)節(jié)點(diǎn)進(jìn)行廣度優(yōu)先搜索，若存在某個(gè)節(jié)點(diǎn)被訪問兩次，則說明該路徑存在回路，因此將最后一個(gè)遍歷的節(jié)點(diǎn)與上一節(jié)點(diǎn)的鄰接值置為0即可。最后得到的鄰接矩陣即為目標(biāo)DAG。算法2描述了上述思想。

算法2： 構(gòu)建KBN的DAG

輸入：Xi： 構(gòu)建DAG的變量節(jié)點(diǎn)

vaule(vi)： 實(shí)體vi的實(shí)體平均權(quán)重值

輸出：GB←(XB，EB)： KBN的DAG結(jié)構(gòu)

(1)EB←{}

(2)FORi←1DOWNTOn-1DO

(3)FORj←i+1DOWNTOnDO

(4)IFXi與Xj對(duì)應(yīng)的取值實(shí)體間存在可達(dá)路徑 THEN

(5)IFN(Xi)>N(Xj)THEN

(6)EB←EB∪{Xi，Xj}

(7)ELSEEB←EB∪{Xj，Xi}

(8) 將Xi和Xj對(duì)應(yīng)的鄰接值置為1

(9)ENDIF

(10)ENDIF

(11)ENDFOR

(12)ENDFOR

(13) 以BFS遍歷鄰接矩陣， 避免環(huán)路產(chǎn)生

(14)ReturnGB←(XB，EB)

例如，假設(shè)KBN的變量X1、X2、X3和X4分別對(duì)應(yīng)GK中的電影屬性的具體分類“演員”、“導(dǎo)演”、“電影類型”、“編劇”，由圖3的CSG圖結(jié)構(gòu)可知存在路徑如(“編劇A”，“電影A”，“演員A”)，則變量X1和變量X4之間存在邊；已知KBN中“演員”變量對(duì)應(yīng)的不同取值對(duì)應(yīng)屬性實(shí)體“演員A”和“演員B”,通過value(vi)值可得到N(“演員”)=value(“演員A”)+value(“演員B”)=2.52，N(“編劇”)=value(“編劇A”)+value(“編劇B”)=5.16，N(“編劇”)>N(“演員”)， 即KBN中變量“編劇”為變量“演員”的父節(jié)點(diǎn)，邊由變量X4指向變量X1。DAG構(gòu)建過程如圖4所示。

圖4 KBN的DAG構(gòu)建

2.3 數(shù)據(jù)集抽取和CPT計(jì)算

本文中目標(biāo)實(shí)體組(核心實(shí)體，屬性實(shí)體)的關(guān)聯(lián)度計(jì)算，是基于GK中已有的實(shí)體及實(shí)體間關(guān)系。因此為了構(gòu)建屬性類實(shí)體的KBN，本節(jié)基于KG的三元組抽取KBN中變量的取值，構(gòu)成數(shù)據(jù)集D，從而計(jì)算KBN的CPT。

表2 數(shù)據(jù)集D

基于已構(gòu)建的DAG和數(shù)據(jù)集D，本文采用似然估計(jì)[13]的方法來計(jì)算KBN中每個(gè)變量節(jié)點(diǎn)的概率參數(shù)表，從而最終得到KBN，最終得到的KBN如圖5所示。

圖5 構(gòu)建后的KBN

3 基于KBN概率推理的KG中實(shí)體間關(guān)聯(lián)度計(jì)算

BN的概率推理是指利用BN的結(jié)構(gòu)及其條件概率表，在給定證據(jù)后進(jìn)行某些節(jié)點(diǎn)取值概率的計(jì)算。然而，BN的精確推理具有指數(shù)時(shí)間，其中推理的時(shí)間復(fù)雜度與節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)的取值個(gè)數(shù)呈正相關(guān)，所以精確推理不適用于大規(guī)模的KG。因此，本文利用BN的近似推理算法，針對(duì)KG中實(shí)體間關(guān)聯(lián)存在的不確定性，基于KBN的近似推理定量地描述實(shí)體之間的關(guān)聯(lián)度。Gibbs采樣是眾多近似推理算法中應(yīng)用最為廣泛的一種，它是一種簡(jiǎn)單的馬爾可夫鏈蒙特卡羅算法[17](Markov chain Monte Carlo，MCMC)。

本文基于Gibbs采樣進(jìn)行概率推理，針對(duì)目標(biāo)實(shí)體組，將能在GK中唯一標(biāo)識(shí)目標(biāo)電影實(shí)體的其它電影屬性實(shí)體作為證據(jù)變量節(jié)點(diǎn)的取值，通過Gibbs采樣可以得到查詢變量節(jié)點(diǎn)在特定取值下的概率值，以此定量地表示目標(biāo)實(shí)體間可能存在的不確定性關(guān)系，并作為KG中目標(biāo)實(shí)體間的關(guān)聯(lián)度。算法3給出了具體描述[15]。

算法3： 基于Gibbs采樣的KBN近似推理

輸入： KBNGB←(XB,EB)

E,證據(jù)變量 //即能唯一標(biāo)識(shí)目標(biāo)實(shí)體組中Ui的屬性實(shí)體分類

e,證據(jù)變量E的取值 //具體的屬性實(shí)體

c,GB的當(dāng)前狀態(tài)

q,查詢變量 //目標(biāo)實(shí)體組中的屬性實(shí)體oi

s,采樣總次數(shù)；m,q值為1的樣本數(shù)量

輸出：p(q=1|e)

(1)m←0

(2)隨機(jī)生成一個(gè)樣本d0， 并與狀態(tài)c一致

(3)FORk←1TOsDO

(4) 計(jì)算當(dāng)前狀態(tài)dk-1下的被選變量的概率值

(5) 隨機(jī)從Z中選擇一個(gè)非證據(jù)變量Xi

(6)B←p(Xi=0|DMB(Xi))+p(Xi=1|DMB(Xi)) //DMB(Xi)為MB(Xi) 中各變量在當(dāng)前狀態(tài)d下的值

(7) 通過p(Xi|DMB(Xi)) 對(duì)Xi采樣

(8) 隨機(jī)產(chǎn)生rk∈[0,B], 用下面公式確定Xi的值

(9) 用抽樣結(jié)果覆蓋dk-1中的Xi值

(10)ENDFOR

(11)FORk←1TOsDO

(13)m←m+1

(14)ENDIF

(15)ENDFOR

(16)Returnp(q=1|e) //最終的條件概率值

利用KBN近似推理算法3，可以得到p(Xj=1|Xi=1,Xs=1) 的值，即給定證據(jù)變量及其取值Xi=1，Xs=1的情況下，可得查詢變量Xj=1的條件概率值。由于核心實(shí)體可以由其它屬性實(shí)體唯一標(biāo)識(shí)，核心實(shí)體與屬性實(shí)體間不確定性關(guān)聯(lián)關(guān)系即可轉(zhuǎn)換成屬性實(shí)體間的關(guān)系表示，因此通過描述屬性實(shí)體間依賴關(guān)系的KBN的概率推理，即可實(shí)現(xiàn)核心實(shí)體與屬性實(shí)體間不確定性關(guān)聯(lián)關(guān)系的定量推理與計(jì)算。本文中KG的目標(biāo)實(shí)體組(核心實(shí)體，屬性實(shí)體)的關(guān)聯(lián)度即為條件概率p值。給定閾值ε(0<ε<1)， 若p值≥ε，則核心實(shí)體存在與該屬性實(shí)體真實(shí)的關(guān)聯(lián)關(guān)系，從而獲取了更加完整真實(shí)的KG。

例如，針對(duì)目標(biāo)實(shí)體組(“電影A”，“演員B”)，選擇圖5中KBN的X2和X3作為證據(jù)變量節(jié)點(diǎn)，然后取X2=“導(dǎo)演A”，X3=“動(dòng)作片”的情況下， 計(jì)算p(X1=“演員B”|X2=“導(dǎo)演A”，X3=“動(dòng)作片”)， 即“電影A”與“演員B”的關(guān)聯(lián)度。假設(shè)當(dāng)前節(jié)點(diǎn)的狀態(tài)是 [X1=“演員B”，X2=“導(dǎo)演A”，X3=“動(dòng)作片”，X4=“編劇A”]， 在當(dāng)前狀態(tài)下，通過X4馬爾可夫覆蓋中變量在當(dāng)前狀態(tài)下的值來對(duì)非證據(jù)變量節(jié)點(diǎn)X4進(jìn)行采樣，經(jīng)過計(jì)算便可以得到p(X4=“編劇A”|X1=“演員B”,X2=“導(dǎo)演A”，X3=“動(dòng)作片”)=1和p(X4=“編劇B”|X1=“演員B”，X2=“導(dǎo)演A”，X3=“動(dòng)作片”)=0。 假設(shè)生成的隨機(jī)數(shù)為0.5，那么采樣結(jié)果為X4=“編劇B”， 同時(shí)生成新的狀態(tài) [X1=“演員B”，X2=“導(dǎo)演A”，X3=“動(dòng)作片”，X4=“編劇B”]。 若采樣次數(shù)為400，其中X1=“演員B” 的次數(shù)為320，則p(X1=“演員B”|X2=“導(dǎo)演A”，X3=“動(dòng)作片”)=0.6， 即“演員B”與“電影A”的關(guān)聯(lián)度為0.6。若ε=0.5，則目標(biāo)實(shí)體間的鏈接真實(shí)存在。

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

本文測(cè)試了KBN構(gòu)建效率。同時(shí)在封閉世界下，實(shí)現(xiàn)互信息[18]方法作為對(duì)比實(shí)驗(yàn)，進(jìn)而直接測(cè)試本文基于KBN的KG實(shí)體間關(guān)聯(lián)度計(jì)算方法的有效性?；贠penKE[19]平臺(tái)實(shí)現(xiàn)基于TransE[20]和TransR[21]的鏈接預(yù)測(cè)方法，進(jìn)而間接測(cè)試本文基于KBN的KG實(shí)體間關(guān)聯(lián)度計(jì)算方法的有效性。實(shí)驗(yàn)環(huán)境如下：Intel?CoreTMi5 3.40 GHz處理器，24 GB內(nèi)存，Windows10操作系統(tǒng)，以PyCharm2019.3.1 x64為開發(fā)平臺(tái)，MySQL存儲(chǔ)KBN的CPT，使用Python語(yǔ)言編寫程序。本文使用FB15k數(shù)據(jù)集，作為測(cè)試數(shù)據(jù)集，其中數(shù)據(jù)集的實(shí)體、關(guān)系及三元組數(shù)據(jù)劃分信息見表3。其中，本文針對(duì)數(shù)據(jù)集中的電影屬性實(shí)體對(duì)應(yīng)的標(biāo)簽關(guān)系(relation)，構(gòu)建了2-relation、3-relation、5-relation的KG，其中不同關(guān)系個(gè)數(shù)的KG統(tǒng)計(jì)信息見表4。

表3 實(shí)驗(yàn)數(shù)據(jù)集的實(shí)體、關(guān)系及三元組個(gè)數(shù)統(tǒng)計(jì)

表4 不同關(guān)系個(gè)數(shù)的KG統(tǒng)計(jì)信息

本文利用訓(xùn)練集和驗(yàn)證集中的三元組構(gòu)建電影領(lǐng)域相關(guān)的KG，之后通過本文所提出的方法構(gòu)建KBN，最后針對(duì)測(cè)試集中的三元組計(jì)算實(shí)體間的關(guān)聯(lián)度。構(gòu)建好的KG中已有邊鏈接的實(shí)體間關(guān)聯(lián)度都大于等于ε，是本文討論的前提。

4.1 KBN的構(gòu)建效率

為了測(cè)試構(gòu)建KBN的效率，從測(cè)試數(shù)據(jù)集中選取了不同的對(duì)應(yīng)電影屬性實(shí)體的標(biāo)簽關(guān)系個(gè)數(shù)(實(shí)體節(jié)點(diǎn)個(gè)數(shù)也不同)的KG，并分別測(cè)試了對(duì)應(yīng)的是否包含數(shù)據(jù)庫(kù)I/O開銷的KBN構(gòu)建時(shí)間，如圖6所示?？梢钥闯觯瑯?gòu)建KBN的時(shí)間隨著實(shí)體數(shù)的增加基本呈線性增長(zhǎng)趨勢(shì)，但增長(zhǎng)趨勢(shì)逐漸減緩。

圖6 構(gòu)建KBN的效率

4.2 實(shí)體間關(guān)聯(lián)度計(jì)算的有效性測(cè)試

互信息被廣泛應(yīng)用于文本信息處理等領(lǐng)域[22]，常用于描述兩個(gè)變量之間的關(guān)聯(lián)程度。本文實(shí)驗(yàn)中，針對(duì)測(cè)試數(shù)據(jù)集抽取出的同一個(gè)KG，基于互信息的KG中實(shí)體間關(guān)聯(lián)關(guān)系的度量方法作為實(shí)驗(yàn)的對(duì)比方法，進(jìn)而直接驗(yàn)證本文KG中實(shí)體間關(guān)聯(lián)度計(jì)算方法的有效性。在本實(shí)驗(yàn)中，測(cè)試集中實(shí)體間的關(guān)聯(lián)關(guān)系是真實(shí)、正確的，并以之作為測(cè)試的基礎(chǔ)。在同一個(gè)閾值ε的前提下，通過兩種方法分別計(jì)算得到對(duì)應(yīng)的關(guān)聯(lián)度，若關(guān)聯(lián)度值大于ε，則說明所計(jì)算的實(shí)體間具有關(guān)聯(lián)關(guān)系，并以此為依據(jù)對(duì)比測(cè)試集中的三元組數(shù)據(jù)，將預(yù)測(cè)正確的三元組個(gè)數(shù)/測(cè)試集中的三元組個(gè)數(shù)，從而得到兩種計(jì)算方法的正確率。

實(shí)驗(yàn)中，在不同比例的訓(xùn)練集下測(cè)試兩種方法的正確率，訓(xùn)練集比例不同，意味著KG的規(guī)模也不同，測(cè)試結(jié)果如圖7所示?？梢钥闯鰞煞N關(guān)聯(lián)度計(jì)算方法的正確率都在0.6以上，同時(shí)隨著訓(xùn)練集比例的增加，兩者的正確率都趨于固定的范圍值，其中基于KBN的實(shí)體間關(guān)聯(lián)度計(jì)算方法的正確率略優(yōu)于基于互信息的實(shí)體間關(guān)聯(lián)度計(jì)算方法，這直接反映了本文提出方法的高效性和有效性。

圖7 不同訓(xùn)練集比例下的關(guān)聯(lián)度計(jì)算正確率

本文實(shí)驗(yàn)中，實(shí)體間關(guān)聯(lián)度的計(jì)算可以作為KG中不確定性關(guān)系存在的依據(jù)。如果本文方法中計(jì)算得到的關(guān)聯(lián)度值大于ε，則目標(biāo)實(shí)體組中存在邊鏈接。通過與KG已有的鏈接預(yù)測(cè)方法的類比，即可間接驗(yàn)證實(shí)體間關(guān)聯(lián)度計(jì)算的有效性。因此，針對(duì)測(cè)試數(shù)據(jù)集抽取出的同一個(gè)KG，本文使用基于OpenKE平臺(tái)得到基于TransE、TransR的鏈接預(yù)測(cè)方法作為對(duì)比方法。設(shè)置閾值ε，若關(guān)聯(lián)度值大于ε，則說明KG中實(shí)體間關(guān)系真實(shí)存在，將關(guān)聯(lián)度值大于ε的三元組記為正，否則記為負(fù)。隨后通過對(duì)測(cè)試集中的數(shù)據(jù)隨機(jī)替換實(shí)體構(gòu)造錯(cuò)誤三元組，正確三元組被預(yù)測(cè)為正記為TP，錯(cuò)誤三元組被預(yù)測(cè)為正記為FP，正確三元組被預(yù)測(cè)為負(fù)記為FN。最后以關(guān)聯(lián)度為鏈接預(yù)測(cè)的依據(jù)在不同比例的訓(xùn)練集下測(cè)試本文方法的有效性。本文選擇準(zhǔn)確率(Precision)、召回率(Recall)和F值作為衡量實(shí)體間關(guān)聯(lián)度計(jì)算方法有效性的實(shí)驗(yàn)指標(biāo)。

實(shí)驗(yàn)中，測(cè)試各方法在不同比例訓(xùn)練集下的3個(gè)指標(biāo)，結(jié)果如圖8、圖9和圖10所示。從圖8和圖9可以看出，隨著訓(xùn)練集比例的增加，根據(jù)KBN推理計(jì)算得到的關(guān)聯(lián)度為依據(jù)的鏈接預(yù)測(cè)方法，Precision和Recall指標(biāo)逐漸接近并略優(yōu)于TransE方法。從圖10可以看出，各方法的F值普遍在0.5以上。實(shí)驗(yàn)結(jié)果在一定程度上說明了本文提出基于KBN概率推理的KG實(shí)體間關(guān)聯(lián)度計(jì)算方法的有效性。

圖8 KG實(shí)體間關(guān)聯(lián)度計(jì)算方法的準(zhǔn)確率

圖9 KG實(shí)體間關(guān)聯(lián)度計(jì)算方法的召回率

圖10 KG實(shí)體間關(guān)聯(lián)度計(jì)算方法的F值

綜上，在真實(shí)數(shù)據(jù)集FB15k下，通過與現(xiàn)有的相關(guān)方法進(jìn)行實(shí)驗(yàn)對(duì)比，本文所提出的基于KBN的實(shí)體間關(guān)聯(lián)度計(jì)算方法在模型構(gòu)建和關(guān)聯(lián)度計(jì)算方面都有較好的表現(xiàn)，從而驗(yàn)證了本文所提方法的可行性。

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

本文針對(duì)KG中實(shí)體間存在的關(guān)聯(lián)性，提出一種基于概率推理的KG中實(shí)體間關(guān)聯(lián)度的計(jì)算方法，從而為KG中實(shí)體間關(guān)聯(lián)強(qiáng)度的量化和推理提供了一種思路，并為KG的知識(shí)補(bǔ)全和鏈接預(yù)測(cè)提供了依據(jù)，但仍是KG中實(shí)體關(guān)系定量計(jì)算的初步探索。實(shí)驗(yàn)結(jié)果在一定程度上驗(yàn)證了所提出思路的可行性，但在鏈接預(yù)測(cè)對(duì)比實(shí)驗(yàn)中的準(zhǔn)確率、召回率和F值仍與TransR方法有一定的差距，各實(shí)驗(yàn)指標(biāo)仍有待提高。本文僅從現(xiàn)有的KG實(shí)體考慮，并未考慮外部新增數(shù)據(jù)的融合，因此未來的工作將考慮融合外部數(shù)據(jù)，從而提高KG知識(shí)表示和學(xué)習(xí)的時(shí)效性和全面性。