基于貝葉斯網(wǎng)的開放世界知識圖譜補(bǔ)全

李鑫柏，吳鑫然，岳 昆

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

0 概述

知識圖譜（Knowledge Graph，KG）是海量數(shù)據(jù)領(lǐng)域中重要的知識儲備庫［1-2］，為知識查詢、問答系統(tǒng)和推薦系統(tǒng)［3］等應(yīng)用提供知識服務(wù)［4-5］。KG 用節(jié)點(diǎn)表示實(shí)體，用邊表示實(shí)體間的關(guān)系，一個由關(guān)系、頭實(shí)體和尾實(shí)體構(gòu)成的三元組表示一個事實(shí)。知識圖譜補(bǔ)全（Knowledge Graph Completion，KGC）指通過預(yù)測實(shí)體之間的新關(guān)系來構(gòu)造三元組［6］，從而提升KG 中知識的豐富程度［7］。

將實(shí)體和關(guān)系表示為低維空間中的向量，是一類有效的KGC 方法，通過向量間的計(jì)算來解決KG內(nèi)部的關(guān)系預(yù)測問題。但現(xiàn)實(shí)世界中的知識在不斷增加變化，這要求KG 及時補(bǔ)充現(xiàn)實(shí)世界中的知識，而這類KGC 方法難以滿足從現(xiàn)實(shí)世界中學(xué)習(xí)知識的要求。因此，研究人員將KG 內(nèi)部的補(bǔ)全方法稱為封閉世界下的KGC 方法，將不包含于KG 的數(shù)據(jù)稱為開放世界數(shù)據(jù)，進(jìn)一步提出開放世界KGC 方法，這類方法的基本思想是從數(shù)據(jù)中提取KG 中不存在的新實(shí)體來補(bǔ)全三元組，從而為KG 引入新實(shí)體。

現(xiàn)有的開放世界KGC 方法雖然有效地解決了新實(shí)體的來源問題，但每次只能針對缺失頭實(shí)體或尾實(shí)體的一個三元組進(jìn)行補(bǔ)全，在一定程度上限制了新知識的全面性。KG 中關(guān)系之間存在相互依賴的性質(zhì)，可以用來學(xué)習(xí)新實(shí)體的多種關(guān)系，但KG 不能直接描述這種依賴性。貝葉斯網(wǎng)（Bayesian Network，BN）是表示和推理具有依賴性和不確定性知識的有效工具。本文提出一種基于BN 的開放世界KGC 方法，給出關(guān)系之間依賴性的BN 表示模型，設(shè)計(jì)BN模型構(gòu)建方法，利用KG 來構(gòu)建BN。在此基礎(chǔ)上，提出基于BN 概率推理的三元組構(gòu)造方法，利用現(xiàn)有的命名實(shí)體識別技術(shù)從開放世界數(shù)據(jù)中獲取包含新實(shí)體的三元組，將其作為證據(jù)，基于BN 概率推理構(gòu)造更多包含新實(shí)體的三元組，從而提升知識的全面性并完善KG。

1 相關(guān)工作

基于KG 的表示學(xué)習(xí)進(jìn)行KGC 是一類典型的KGC 方法，其補(bǔ)全效果的好壞依賴于表示模型的性能高低。TransE 模型［8］將關(guān)系視為實(shí)體間的平移向量，其能夠有效計(jì)算“一對一”關(guān)系，但計(jì)算“一對多”“多對一”和“多對多”等復(fù)雜關(guān)系時存在局限性。文獻(xiàn)［9］提出TransH 模型，利用超平面及該超平面上的向量表示關(guān)系，使每個實(shí)體在不同關(guān)系下?lián)碛胁煌南蛄勘硎?，但TransH 仍假設(shè)實(shí)體和關(guān)系處于相同的語義空間，在一定程度上限制了其表示能力［10］。文獻(xiàn)［11］提出TransR 模型，為實(shí)體向量構(gòu)造一個公共的空間，并為每個關(guān)系向量構(gòu)造只屬于該關(guān)系的空間。

上述方法能夠?qū)G 中的實(shí)體和關(guān)系表示為向量空間中的向量，不僅保存了實(shí)體和關(guān)系的語義，還使得實(shí)體和關(guān)系變得可計(jì)算，進(jìn)而為KGC、KG 查詢等任務(wù)提供定量的依據(jù)，對KG 具有重要意義。雖然基于表示學(xué)習(xí)的封閉世界KGC 方法能夠在KG 內(nèi)部有效地預(yù)測三元組，但是開放世界中的新知識也是補(bǔ)全KG 的重要知識來源。封閉世界KGC 方法難以滿足向KG 中引入新實(shí)體的要求，因此，有必要研究開放世界KGC 方法。

近年來，研究人員用開放世界KGC 方法從數(shù)據(jù)中提取新實(shí)體加入KG，從而豐富KG 中的知識。文獻(xiàn)［12］利用全卷積神經(jīng)網(wǎng)絡(luò)從數(shù)據(jù)中提取新實(shí)體，進(jìn)而利用新實(shí)體補(bǔ)全缺失頭實(shí)體或尾實(shí)體的三元組，為KGC 提供了一種新思路。文獻(xiàn)［13］將文本、圖片和數(shù)值等多種類型數(shù)據(jù)作為新實(shí)體來構(gòu)造三元組，豐富了KG 中實(shí)體的類型，但多種類型的數(shù)據(jù)導(dǎo)致計(jì)算復(fù)雜度較高。

開放世界KGC 方法能夠?yàn)镵G 引入開放世界中的新實(shí)體，為KGC 方法提供一種新思路?，F(xiàn)有的開放世界KGC 方法依賴于數(shù)據(jù)中給出的知識，能夠?qū)W習(xí)到數(shù)據(jù)中直接描述出的與新實(shí)體相關(guān)的知識。然而，與一個實(shí)體相關(guān)的知識往往是多方面的，數(shù)據(jù)中給出的知識通常只是其中的一部分。現(xiàn)有的開放世界KGC 方法雖然能夠引入新實(shí)體，但無法提升知識的全面性。若利用開放世界數(shù)據(jù)中給出的知識學(xué)習(xí)到更多知識，同時對新實(shí)體所涉及的多種關(guān)系進(jìn)行補(bǔ)全，將大幅提高新知識的全面性和KGC 的效率。

2 基于KGBN 的知識圖譜補(bǔ)全

KG 中同一類型實(shí)體涉及的關(guān)系之間通常具有相互依賴的性質(zhì)，給定某個類型實(shí)體涉及的一些關(guān)系，通過關(guān)系之間的依賴性可得到該實(shí)體可能涉及的其他關(guān)系，從而利用該實(shí)體及更多關(guān)系來構(gòu)造三元組。若從開放世界數(shù)據(jù)中提取的新實(shí)體與KG 中的實(shí)體為相同類型，則新實(shí)體涉及的關(guān)系往往也符合KG 中關(guān)系之間的相關(guān)性。例如，一部電影的類型為“喜劇”，另一部電影與這部電影具有相同的導(dǎo)演，則其類型很可能也為“喜劇”。在開放世界KGC 任務(wù)中利用這種依賴性，能基于數(shù)據(jù)中新實(shí)體給定的關(guān)系獲取其涉及的更多關(guān)系，從而提升KG 中知識的全面性。因此，如何定量地描述KG 中同類實(shí)體涉及的關(guān)系之間的依賴性，是實(shí)現(xiàn)開放世界KGC 的重要前提。

BN［14］是描述變量間相互依賴關(guān)系和不確定性知識的有效工具［15］?；谧C據(jù)變量的取值，利用BN 的概率推理，可計(jì)算得到查詢變量不同取值的條件概率。鑒于BN對不確定性知識表示與推理的優(yōu)勢，本文將BN作為KG 中關(guān)系之間依賴性表示和推理的框架，構(gòu)建一個基于KG的BN（KG-based Bayesian Network，KGBN），其中包含有向無環(huán)圖（Directed Acyclic Graph，DAG）和條件概率表（Conditional Probability Table，CPT），將KG中的關(guān)系表示為KGBN 中的變量，并將KG 中關(guān)系連接的不同尾實(shí)體表示為KGBN 中變量的不同取值。如圖1 所示，將KG 中的關(guān)系“導(dǎo)演”“演員”和“類型”表示為KGBN 中的變量x1、x2和x3“，演員1”出演的某部電影為“喜劇”的可能性可利用條件概率P（x3=“喜劇”|x2=“演員1”）=0.95 進(jìn)行定量描述。

圖1 KGBN 示例Fig.1 Example of KGBN

KGBN 的構(gòu)建包括DAG 構(gòu)建和CPT 計(jì)算。對于同一類型的實(shí)體而言，它們共同涉及的關(guān)系描述了該類實(shí)體的特性，在KGC 任務(wù)中考慮這些關(guān)系對實(shí)體的描述作用，能夠更準(zhǔn)確地獲取新實(shí)體的特性，從而為構(gòu)造三元組提供可靠的依據(jù)。因此，本文將關(guān)系在實(shí)體描述中的重要程度作為構(gòu)建DAG 的依據(jù)，在DAG 中使得重要關(guān)系的優(yōu)先級高于次要關(guān)系，進(jìn)而獲取關(guān)系之間的依賴性。具體而言，關(guān)系的出現(xiàn)頻率越低，則越能準(zhǔn)確描述實(shí)體的特點(diǎn)［16］。若將關(guān)系看作一種“資源”，關(guān)系連接的尾實(shí)體看作“傳播介質(zhì)”［17］，那么“傳遞資源多”的關(guān)系在實(shí)體描述中發(fā)揮著更重要的作用，如“語言”關(guān)系的尾實(shí)體“普通話”一般不具備其他信息，而“導(dǎo)演”關(guān)系的尾實(shí)體“導(dǎo)演1”具有國籍、作品等信息，根據(jù)“導(dǎo)演1”容易推出電影的“語言”為“普通話”，反之則很難推出一部“普通話”電影的“導(dǎo)演”是“導(dǎo)演1”。

本文提出基于KG 中關(guān)系出現(xiàn)頻率和傳遞資源數(shù)的DAG 構(gòu)建方法，給出關(guān)系在實(shí)體描述中重要程度的定量計(jì)算方法，將一個關(guān)系重要于另一個關(guān)系的狀態(tài)表示為DAG 中一個變量指向另一個變量的有向邊，構(gòu)造出DAG，進(jìn)而提出基于KG 的三元組數(shù)據(jù)集抽取方法，從KG 中抽取關(guān)系與尾實(shí)體的不同組合情況，并獲取每種組合的出現(xiàn)次數(shù)，從而得到包含KGBN 中不同變量取值組合及其個數(shù)的數(shù)據(jù)集。在此基礎(chǔ)上，給出基于最大似然估計(jì)法的CPT 計(jì)算方法，利用DAG 和數(shù)據(jù)集為每個變量計(jì)算CPT，最終構(gòu)建出KGBN。

為了實(shí)現(xiàn)開放世界KGC，本文將從開放世界數(shù)據(jù)中提取的包含新實(shí)體的三元組作為KGBN 推理的證據(jù)，通過概率推理來獲取新實(shí)體涉及的更多關(guān)系，從而構(gòu)造出新的三元組。BN 推理分為精確推理和近似推理，精確推理通過給定證據(jù)變量取值來計(jì)算查詢變量的后驗(yàn)概率分布，近似推理降低了精確推理的復(fù)雜度和對精度的要求，以在較短時間內(nèi)得到一個近似解［18］。

三元組的正確與否決定了KG 所表達(dá)知識的可靠性，考慮到KGC 任務(wù)對結(jié)果的精度要求較高，本文在KGBN 推理中采用精確推理，提出基于KGBN推理的三元組構(gòu)造方法，從數(shù)據(jù)中提取包含新實(shí)體的三元組，將其中的關(guān)系及尾實(shí)體作為KGBN 推理中的證據(jù)變量及其取值，并將KGBN 中其他未知取值的變量作為查詢變量，進(jìn)而基于KGBN 推理得到查詢變量不同取值的條件概率，將條件概率作為構(gòu)造新三元組的依據(jù)，從而構(gòu)造出包含新實(shí)體及更多關(guān)系的三元組。

本文方法也可用于封閉世界KGC 任務(wù)，即針對KG 中已有的實(shí)體進(jìn)行補(bǔ)全。針對KG 中已有的某個實(shí)體，在包含該實(shí)體的三元組中存在已知的關(guān)系和尾實(shí)體，可以作為KGBN 推理的證據(jù)變量及其取值，基于KGBN 推理即可獲取其他變量的取值條件概率，進(jìn)而構(gòu)造出更多三元組。

本文使用DBpedia數(shù)據(jù)集［19］和Freebase數(shù)據(jù)集［20］，分別在開放世界和封閉世界下進(jìn)行鏈路預(yù)測和三元組類型預(yù)測實(shí)驗(yàn)，以測試本文方法的結(jié)構(gòu)構(gòu)建效率。

3 KGBN 構(gòu)建

3.1 相關(guān)定義

定 義1［10］將KG 表示為GK=(E,R,T)，其中，E={e1,e2,…,eε}表示實(shí)體集合，ε為實(shí)體個數(shù)，R={r1,r2,…,rγ}表示關(guān)系集合，γ為關(guān)系的個數(shù)，T={(h,r,t)}(h,t?E,h≠t,r?R)表示三元組集合，h為頭實(shí)體，t為尾實(shí)體。

BN 通過DAG 和CPT 來表示和推理變量間的相互依賴關(guān)系和不確定性知識，其中，DAG 的節(jié)點(diǎn)表示變量，有向邊表示變量間的依賴關(guān)系，每個節(jié)點(diǎn)具有一個CPT，描述了父節(jié)點(diǎn)對該節(jié)點(diǎn)的影響程度。KGBN 由DAG 和CPT 構(gòu)成，其中，變量表示KG 中的關(guān)系，變量的取值表示關(guān)系連接的尾實(shí)體。為方便后續(xù)討論，將KGBN 中的變量個數(shù)設(shè)為n(n<γ)。

定義2將KGBN 表示為φ=(GB,θ)，其中：

1）GB=(X,Y)表示DAG 結(jié)構(gòu)，X={x1,x2,…,xn}表示變量集，xi表示GK中同類實(shí)體所涉及的任意一個關(guān)系，Y表示有向邊集，表示由xi到xj的有向邊，此時，xi稱為xj的父變量，變量xj的父變量集合記為Ppa(xj)。

2）θ表示所有變量 的CPT 集合，其由P(xi)和P(xi|Ppa(xi))構(gòu)成。

3.2 DAG 構(gòu)建

為了構(gòu)建KGBN，本文提出基于關(guān)系出現(xiàn)次數(shù)和傳遞資源數(shù)的DAG 構(gòu)建方法，通過定量計(jì)算關(guān)系在實(shí)體描述中的重要程度來獲取關(guān)系之間的優(yōu)先級別，并將其表示為DAG 中變量之間的有向邊，從而獲取KG中同一類型實(shí)體所涉及的關(guān)系之間的依賴性。

KG 中出現(xiàn)頻率低的關(guān)系能更準(zhǔn)確地描述實(shí)體的特點(diǎn)，例如，某部電影具有2 位“主演”和10 位“工作人員”，“主演”往往比“工作人員”更能說明電影的特點(diǎn)。本文提出逆頻（Inverse Frequency，IF）指標(biāo)來度量關(guān)系在實(shí)體描述中的重要程度。對于GK中的任意關(guān)系r，IF 計(jì)算公式如下：

其中，NT(r)為三元組集合T中包含關(guān)系r的三元組個數(shù)。

KG 中“傳遞資源越多”的關(guān)系對實(shí)體描述的作用越大，本文提出關(guān)系傳遞（Relation Transfer，RT）指標(biāo)，在某些關(guān)系具有相同IF 值時，利用RT 值度量這些關(guān)系對實(shí)體描述的重要程度。對于r，RT 計(jì)算公式如下：

其中，Er表示在集合T中關(guān)系r連接的尾實(shí)體集合，NT(h?Er)表示集合T中以Er中各實(shí)體為頭實(shí)體的三元組個數(shù)，即關(guān)系r連接的尾實(shí)體的出度之和為φ中n個變量所表示的關(guān)系的NT(h?Er)之和。

在構(gòu)建GB時，首先利用式（1）計(jì)算各變量所表示關(guān)系的IF 值，并根據(jù)IF 值對變量進(jìn)行降序排列，得到GB的變量集X和關(guān)系的IF 值數(shù)組；然后統(tǒng)計(jì)關(guān)系在GK中傳遞的資源數(shù)，利用式（2）計(jì)算X中各變量所表示關(guān)系的RT 值，得到關(guān)系的RT 值數(shù)組。

在進(jìn)行DAG 構(gòu)建時，依次從變量集X中取出變量xi(1≤i≤n-1)，放入SameX集合中，并將這個變量所表示關(guān)系的IF 值與X中下一個變量xi+1(1≤i≤n-1)所表示關(guān)系的IF 值進(jìn)行比較，比較結(jié)果分為以下4 種情況：

1）若兩個關(guān)系的IF 值不相等，則在有向邊集Y中添加SameX集中每個變量指向下一個變量xi+1的有向邊。

2）若兩個關(guān)系的IF 值相等，進(jìn)而比較它們的RT值，并在Y中添加所表示關(guān)系的RT 值大的變量指向所表示關(guān)系的RT 值小的變量的有向邊。

3）若兩個關(guān)系的IF 值和RT 值均相等，則判斷這個變量是否為X中的倒數(shù)第二個變量，若不是，則將這個變量保留在SameX集中，并開始下一次循環(huán)，因此，SameX集中的變量所表示的關(guān)系的IF 值和RT 值總是相等的。

4）若兩個關(guān)系的IF 值和RT 值均相等，且這個變量xi是X中的倒數(shù)第二個變量，則將X中的最后一個變量xn放入SameX集，并獲取SameX集中的變量個數(shù)s，找到X中第n?s個變量xn-s，xn-s即為所表示關(guān)系的RT 值大于SameX集中變量所表示關(guān)系的RT 值的最接近的變量，接著在Y中分別添加xn-s指向SameX集中除第一個變量之外的每個變量的有向邊，并清空SameX集，結(jié)束循環(huán)。

DAG 的構(gòu)建過程如算法1 所示：

算法1KGBN 的DAG 構(gòu)建

算法1 的執(zhí)行代價主要取決于KGBN 中變量的個數(shù)，若變量集X中有n個變量，則算法1 的時間復(fù)雜度為O（n）。

如表1 所示，算法1 在第一次、第二次執(zhí)行中分別添加有向邊和，在第三次執(zhí)行時，將x3與x4比較，得到IIF(r3)=IIF(r4)，且RRT(r3)=RRT(r4)，將x3保留在SameX集中，繼續(xù)循環(huán)。接著，將x4放入SameX集中，并與下一個變量x5進(jìn)行比較，得到IIF(r4)=IIF(r5)和RRT(r4)=RRT(r5)，且x4為倒數(shù)第二個變量，將x5放入SameX集。此時，SameX集中有3 個變量，由此找到變量x2，根據(jù)表1 可以看出，x2所表示關(guān)系的RT 值大于SameX集中變量所表示關(guān)系的RT值，且x2是最接近SameX集中變量的變量，因此，分別對SameX集中除第一個變量之外的每個變量添加x2指向該變量的有向邊，即和。

表1 算法1 元素取值示例Table 1 Example of element values of algorithm 1

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

本節(jié)基于KG 三元組抽取數(shù)據(jù)集，利用三元組中的關(guān)系和尾實(shí)體來生成KGBN 中包含n個變量取值的組合，并統(tǒng)計(jì)變量取值組合的個數(shù)，從而利用DAG 和數(shù)據(jù)集計(jì)算得到KGBN 的CPT。

基于KG 三元組抽取數(shù)據(jù)集的過程為：

1）從GK的三元組集合T中抽取滿足以下2 個條件的三元組：

（1）三元組的頭實(shí)體和構(gòu)建φ的實(shí)體為同一類型。

（2）三元組的關(guān)系為φ中變量所表示的關(guān)系。

2）對于這些三元組中的每一個關(guān)系，將其作為φ中的變量xi，同時將這個關(guān)系連接的不同尾實(shí)體作為變量xi的不同取值，得到變量的取值集合，記為，其中，mi為xi的取值個數(shù)。

3）利用φ中的變量及其取值得到所有可能的取值組合{d1,d2,…,dδ}，其 中，δ=表示第l種變量取值組合。

接著，統(tǒng)計(jì)每種取值組合的個數(shù)，過程為：

1）基于前文抽取出的滿足2 個條件的三元組，將其中頭實(shí)體為同一個實(shí)體的多個三元組歸為一條數(shù)據(jù)。

2）利用這條數(shù)據(jù)中的關(guān)系及尾實(shí)體生成φ的變量及變量取值，每條數(shù)據(jù)可生成一個包含n個變量取值的組合，若這個組合與變量取值組合dl相同，則將這個組合作為dl的一個實(shí)例。

3）根據(jù)前文所得的變量取值組合，利用KG 統(tǒng)計(jì)每種變量取值組合的個數(shù)，構(gòu)成數(shù)據(jù)集D={(d1,ND(d1)),(d2,ND(d2)),…,(dδ,ND(dδ))}，其 中，ND(dl)表示dl的實(shí)例數(shù)。

假設(shè)KG 的片段如圖2 所示，其中每個關(guān)系分別連接2 種尾實(shí)體。在圖1 所示的KGBN 中，共有2 個變量，每個變量有2 個取值，計(jì)算可得數(shù)據(jù)集中共有2×2×2=8 種變量取值組合，如圖2 中數(shù)據(jù)集D的片段所示。利用實(shí)體“電影1”構(gòu)成的多個三元組生成變量取值組合，記為d1的1 個實(shí)例，根據(jù)KG 片段統(tǒng)計(jì)得到d1共有2 個實(shí)例。

圖2 數(shù)據(jù)集D 的抽取過程Fig.2 Extraction process of dataset D

在計(jì)算CPT 時，若xi無父變量，其CPT 值為xi的邊緣概率分布P(xi)；若xi有父變量，則其CPT 值為條件概率分布P(xi|Ppa(xi))。基于最大似然估計(jì)法［14］，利用GB和數(shù)據(jù)集D計(jì)算xi的CPT 值θijk，如 式（3）所示：

其中，ND(xi=k)為D中滿足xi取值為k的實(shí)例數(shù)，為D中的實(shí)例數(shù)之和，ND(Ppa(xi)=j)為D中滿足xi的父變量Ppa(xi)取值組合為第j種的實(shí)例數(shù)，ND(xi=k,Ppa(xi)=j)為D中滿足xi取值為k且其父變量Ppa(xi)取值組合為第j種的實(shí)例數(shù)。

4 基于KGBN 推理的三元組構(gòu)造

本節(jié)以開放世界數(shù)據(jù)中提取的包含新實(shí)體的三元組為基礎(chǔ)，利用其中的關(guān)系及尾實(shí)體獲取KGBN 推理中的證據(jù)變量及其取值，進(jìn)而將新實(shí)體涉及的其他關(guān)系作為查詢變量，并將推理得到的查詢變量取值作為關(guān)系連接的尾實(shí)體，從而構(gòu)造出新的三元組。開放世界數(shù)據(jù)中的三元組可以用經(jīng)典的LSTM-CRF［21-22］技術(shù)獲取。BN 精確推理的計(jì)算復(fù)雜度相對于變量個數(shù)成指數(shù)增長，變量消元（Variable Elimination，VE）方法［23］利用變量間的條件獨(dú)立關(guān)系減少推理過程中的變量個數(shù)，降低計(jì)算復(fù)雜度，使得整體計(jì)算復(fù)雜度未必相對于變量個數(shù)成指數(shù)增長［18］，因此，本文采用VE作為KGBN推理算法。

將從數(shù)據(jù)中提取的三元組集合記為W=，其 中，h'為從數(shù)據(jù)中提取的新實(shí)體。將集合W中的關(guān)系作為φ中的證據(jù)變量，記為證據(jù)變量集合Xz，并將關(guān)系連接的尾實(shí)體作為各證據(jù)變量的取值。將集合X中存在而Xz中不存在的變量作為查詢變量，記為查詢變量集合Xq，最大條件概率的閾值記為α。

基于KGBN 推理構(gòu)造三元組的基本思想如下：首先，針對集合Xq中任意一個查詢變量x，計(jì)算得到包含φ中所有概率分布的集合，并將Xz中各個變量的取值代入其中；其次，對除x外所有屬于X但不屬于Xz的變量設(shè)置消元順序，對其中每個變量進(jìn)行求和消元，得到一個新的概率分布集合；然后，將概率分布集合中的所有函數(shù)相乘得到關(guān)于x的函數(shù)，進(jìn)而利用函數(shù)計(jì)算得到x各個取值的條件概率，并找到最大條件概率P（x=k|Xz）；隨后，判斷最大條件概率是否大于等于閾值α，若是，則利用滿足大條件概率的k值構(gòu)造三元組（h',x,k)；最后，將三元組和集合W加入GK的三元組集合T中。重復(fù)上述過程，直到循環(huán)結(jié)束?；贙GBN 推理的三元組構(gòu)造過程如算法2所示。

算法2基于KGBN 推理的三元組構(gòu)造

算法2 的執(zhí)行代價主要取決于集合Xq中的查詢變量個數(shù)和每次推理中消元的變量個數(shù)，算法2 的總執(zhí)行代價為查詢變量的個數(shù)和每次推理中消元執(zhí)行代價之和的乘積。

在封閉世界下執(zhí)行KGC 任務(wù)時，首先，將KG 中包含同一個頭實(shí)體的多個三元組作為一個集合；其次，利用其中的關(guān)系及尾實(shí)體作為證據(jù)變量及證據(jù)變量的取值；然后，將集合X中其他變量作為查詢變量；最后，針對查詢變量進(jìn)行KGBN 推理，利用算法2 得到新的三元組。

以圖1 中的KGBN 為例，假設(shè)從數(shù)據(jù)中提取到三元組集合W=｛（“電影”，“導(dǎo)演”，“導(dǎo) 演1”），（“電影”，“演員”，“演員1”）｝，證據(jù)變量及其取值為｛x1=“導(dǎo)演1”，x2=“演員1”｝，查詢變量為x3。利用算法2計(jì)算P（x3），首先得到KGBN 中的概率分布集合｛P（x1），P（x2|x1），P（x3|x2）｝，設(shè)置變量消元順序?yàn)椋鹸1，x2｝。從概率分布集合中刪去包含x1的函數(shù)，并生成新函數(shù)，得到｛g（x2），P（x3|x2）｝。類似地，消去x2，得到P（x3=“劇情”|x2=“演員1”）=0.05，P（x3=“喜劇”|x2=“演員1”）=0.95，構(gòu)造三元組（“電影”，“類型”，“喜劇”）。

5 實(shí)驗(yàn)驗(yàn)證

將本文知識圖譜補(bǔ)全方法記為BN-KGC，使用DBpedia50k、DBpedia500k［19］和FB15k［20］數(shù)據(jù)集在開放世界下測試BN-KGC 的效率和有效性。BN-KGC也可用于封閉世界KGC 任務(wù)，本文基于OpenKE 平臺［24］實(shí)現(xiàn)TransE［8］、TransH［9］和TransR［11］方 法，在封閉世界下測試BN-KGC 的有效性。

FB15k 數(shù)據(jù)集包含14 951 個實(shí)體和1 345 個關(guān)系，DBpedia50k 和DBpedia500k 數(shù)據(jù)集分別包含49 900 個實(shí)體、654 個關(guān)系和517 475 個實(shí)體、654 個關(guān)系。3 種數(shù)據(jù)集的三元組個數(shù)劃分情況如表2 所示。

表2 3 種數(shù)據(jù)集的三元組個數(shù)統(tǒng)計(jì)Table 2 Statistics of the number of triples in three datasets

本文定義了最大條件概率的閾值α，利用α來決定KGBN 推理所得的取值是否能夠作為構(gòu)造三元組的實(shí)體。若α值過小，則會導(dǎo)致結(jié)果的準(zhǔn)確率降低；若α值過大，則會導(dǎo)致所得結(jié)果的數(shù)量減少。本文利用驗(yàn)證集進(jìn)行閾值設(shè)置，首先對驗(yàn)證集中的三元組進(jìn)行KGBN 推理，得到構(gòu)成這些三元組的正確結(jié)果的條件概率（正確結(jié)果的條件概率不一定為最大條件概率），進(jìn)而利用這些條件概率計(jì)算平均值并作為閾值α，本文通過測試將閾值α設(shè)置為0.95。

5.1 結(jié)構(gòu)構(gòu)建效率測試

為了驗(yàn)證本文KGBN 構(gòu)建方法的有效性，對KGBN 構(gòu)建方法的執(zhí)行時間進(jìn)行測試。首先，針對KGBN 中不同的變量個數(shù)，測試在不同數(shù)據(jù)集下計(jì)算IF 值和RT 值的執(zhí)行時間。計(jì)算IF 值、RT 值的執(zhí)行時間結(jié)果分別如圖3 和圖4 所示，從中可以看出，執(zhí)行時間均隨變量個數(shù)的增多而增加。其中，在FB15k 數(shù)據(jù)集下執(zhí)行時間最長，在DBpedia500k 數(shù)據(jù)集下執(zhí)行時間次之。對從KG 中抽取數(shù)據(jù)集的執(zhí)行時間進(jìn)行測試，結(jié)果如圖5 所示。從圖5 可以看出，抽取數(shù)據(jù)集的執(zhí)行時間隨KGBN 中變量個數(shù)的增多而增加，其中，在DBpedia500k 數(shù)據(jù)集下執(zhí)行時間最長，在FB15k 數(shù)據(jù)集下執(zhí)行時間次之。

圖3 計(jì)算IF 值所需的執(zhí)行時間Fig.3 The execution time required to calculate the IF value

圖4 計(jì)算RT 值所需的執(zhí)行時間Fig.4 The execution time required to calculate the RT value

圖5 抽取數(shù)據(jù)集所需的執(zhí)行時間Fig.5 The execution time required to extract the dataset

將同個數(shù)據(jù)集下的IF 值、RT 值計(jì)算和數(shù)據(jù)集抽取的執(zhí)行時間進(jìn)行對比，在FB15k、DBpedia50k 和DBpedia500k 數(shù)據(jù)集下的執(zhí)行時間情況分別如圖6～圖8 所示。從中可以看出，在同等條件下RT 值計(jì)算的執(zhí)行時間總體大于IF 值計(jì)算的執(zhí)行時間，且數(shù)據(jù)集抽取的執(zhí)行時間略高于IF 值計(jì)算的執(zhí)行時間，但遠(yuǎn)低于RT 值計(jì)算的執(zhí)行時間。

圖6 FB15k 數(shù)據(jù)集下的執(zhí)行時間比較Fig.6 Comparison of execution time in FB15k dataset

圖7 DBpedia50k 數(shù)據(jù)集下的執(zhí)行時間比較Fig.7 Comparison of execution time in DBpedia50k dataset

圖8 DBpedia500k 數(shù)據(jù)集下的執(zhí)行時間比較Fig.8 Comparison of execution time in DBpedia500k dataset

測試含不同變量個數(shù)時KGBN 結(jié)構(gòu)構(gòu)建的執(zhí)行時間，結(jié)果如圖9 所示。從圖9 可以看出，構(gòu)建KGBN 的執(zhí)行時間隨變量個數(shù)的增多而增加，在DBpedia500k 數(shù)據(jù)集下的執(zhí)行時間最長，在FB15k 數(shù)據(jù)集下的執(zhí)行時間次之。這表明在KGBN 構(gòu)建的執(zhí)行時間中IF 值和RT 值計(jì)算的執(zhí)行時間占比很小，同時測試中針對3 個～11 個IF 值的降序排列以及針對3 個～11 個變量的DAG 構(gòu)建花費(fèi)的時間遠(yuǎn)小于IF 值計(jì)算的時間，這說明本文KGBN 構(gòu)建方法的執(zhí)行時間主要取決于CPT 的計(jì)算時間。

圖9 KGBN 構(gòu)建所需的執(zhí)行時間Fig.9 Execution time for KGBN build

5.2 開放世界KGC 方法有效性測試

5.2.1 三元組類型預(yù)測

在三元組類型預(yù)測任務(wù)中，測試集中的三元組被稱為正確三元組，將測試集中的三元組隨機(jī)替換實(shí)體，得到錯誤三元組。其中，正確三元組被預(yù)測為正記作TP，錯誤三元組被預(yù)測為正記作FP，正確三元組被預(yù)測為負(fù)記作FN。三元組類型預(yù)測的評估指標(biāo)分別為準(zhǔn)確率（Precision）、召回率（Recall）及F1 值。

首先，利用訓(xùn)練集和驗(yàn)證集分別構(gòu)建包含5 個、8 個和11 個變量的KGBN，并將閾值α設(shè)置為0.95；然后，利用測試集中的三元組進(jìn)行KGBN 推理，得到三元組中關(guān)系連接尾實(shí)體的條件概率，將條件概率不小于閾值的三元組記為正，否則記為負(fù)，進(jìn)而得到三元組類型預(yù)測結(jié)果。

當(dāng)KGBN 中包含5 個變量時，三元組類型預(yù)測結(jié)果的各項(xiàng)指標(biāo)如圖10 所示。從圖10 可以看出，隨著查詢變量個數(shù)的增多，預(yù)測結(jié)果的準(zhǔn)確率略有下降，而召回率呈上升趨勢，在FB15k 數(shù)據(jù)集下預(yù)測結(jié)果的F1 值保持相對穩(wěn)定的趨勢，在DBpedia 數(shù)據(jù)集下預(yù)測結(jié)果的F1 值呈先上升后下降的趨勢。當(dāng)KGBN 中包含8 個變量時，三元組類型預(yù)測的結(jié)果如圖11 所示。從圖11可以看出，預(yù)測結(jié)果的準(zhǔn)確率、召回率和F1 值均有明顯的提升。其中，在FB15k 數(shù)據(jù)集下預(yù)測結(jié)果的準(zhǔn)確率和F1 值較好，在DBpedia 數(shù)據(jù)集下預(yù)測結(jié)果的召回率較好。當(dāng)KGBN 中包含11 個變量時，三元組類型預(yù)測的結(jié)果如圖12 所示。從圖12 可以看出，預(yù)測結(jié)果的準(zhǔn)確率隨著查詢變量個數(shù)的增多而略有下降，但召回率和F1 值隨著查詢變量個數(shù)的增多而明顯提升。

圖10 KGBN 變量個數(shù)為5 時的三元組類型預(yù)測結(jié)果Fig.10 Prediction results of triple type when the number of KGBN variables is 5

圖11 KGBN 變量個數(shù)為8 時的三元組類型預(yù)測結(jié)果Fig.11 Prediction results of triple type when the number of KGBN variables is 8

圖12 KGBN 變量個數(shù)為11 時的三元組類型預(yù)測結(jié)果Fig.12 Prediction results of triple type when the number of KGBN variables is 11

在實(shí)際中，準(zhǔn)確率和召回率難以同時兼顧，一個較高時另一個總會較低，因此測試中通常采用F1 值來綜合度量方法的有效性。結(jié)合圖10～圖12 的結(jié)果可以看出，隨著查詢變量個數(shù)的增多，針對同一個頭實(shí)體構(gòu)造的三元組個數(shù)增加，因此，預(yù)測結(jié)果的召回率有所提升。雖然證據(jù)變量的減少可能會導(dǎo)致預(yù)測結(jié)果的準(zhǔn)確率下降，但是預(yù)測結(jié)果的F1 值會有一定提升或能保持相對穩(wěn)定的趨勢。

5.2.2 鏈路預(yù)測

本文分別在3 個數(shù)據(jù)集上執(zhí)行鏈路預(yù)測任務(wù)，進(jìn)一步測試BN-KGC 實(shí)現(xiàn)開放世界KGC 的有效性。鏈路預(yù)測能夠預(yù)測三元組缺失的頭實(shí)體或尾實(shí)體，可用于KGC 任務(wù)。將測試集中的三元組稱為正確三元組，對于任意一個正確三元組，本文利用實(shí)體集中所有實(shí)體替換其尾實(shí)體構(gòu)造參考集，打分排序后根據(jù)正確三元組在參考集中的排名計(jì)算MR 和Hits@10 指標(biāo)。MR 用于度量正確三元組排名的平均值，Hits@10 用于衡量排名在前10 的正確三元組個數(shù)占三元組總個數(shù)的比例。利用前文構(gòu)建得到的KGBN，將基于KGBN 推理得到三元組中關(guān)系連接尾實(shí)體的條件概率作為評分函數(shù)，進(jìn)而計(jì)算BN-KGC的MR 和Hits@10。鏈路預(yù)測結(jié)果如表3 所示，從表3 可以看出，在FB15k 數(shù)據(jù)集下，當(dāng)KGBN 中變量和查詢變量個數(shù)分別為8 和3 時預(yù)測的MR 結(jié)果最小，當(dāng)KGBN 中變量和查詢變量個數(shù)分別為8 和5 時預(yù)測的Hits@10 結(jié)果最大。在DBpedia50k 數(shù)據(jù)集下，當(dāng)KGBN 中變量和查詢變量個數(shù)分別為8 和5 時取得的MR 和Hits@10 均為最好。在DBpedia500k數(shù)據(jù)集下，當(dāng)KGBN 中變量和查詢變量個數(shù)分別為11 和6 時預(yù)測 的MR 結(jié)果最小，當(dāng)KGBN 中變量和查詢變量個數(shù)分別為11 和4 時預(yù)測的Hits@10 結(jié)果最大。從總體來看，當(dāng)KGBN 中變量和查詢變量個數(shù)分別為8 和5 時預(yù)測結(jié)果最好，因此，本文采用該組結(jié)果與現(xiàn)有的開放世界KGC 方法進(jìn)行比較。

表3 開放世界下的鏈路預(yù)測結(jié)果Table 3 Link prediction results in open-world

如表4 所示，在DBpedia 數(shù)據(jù)集下將ConMask［12］方法與BN-KGC 方法執(zhí)行的鏈路預(yù)測結(jié)果進(jìn)行比較。在DBpedia50k 數(shù)據(jù)集中，ConMask 的MR 和Hits@10 最佳，這是由于KGBN 的預(yù)測效果受初始KG 影響，當(dāng)初始KG 規(guī)模較小時難以全面地獲取關(guān)系之間的相關(guān)性，從而導(dǎo)致BN-KGC 的預(yù)測效果略差于ConMask。在DBpedia500k 數(shù)據(jù)集下將BN-KGC 方法和ConMask 方法的鏈路預(yù)測結(jié)果進(jìn)行比較，此時BN-KGC 方法預(yù)測結(jié)果的MR 優(yōu)于ConMask 方法。實(shí)驗(yàn)結(jié)果表明，當(dāng)初始KG 規(guī)模較大時BN-KGC 方法可以較全面地獲取關(guān)系之間的相關(guān)性，從而有效完成開放世界KGC 任務(wù)。

表4 開放世界下的鏈路預(yù)測結(jié)果比較Table 4 Comparison of link prediction results in open-world

5.3 封閉世界KGC 方法有效性測試

BN-KGC 方法也可用于封閉世界KGC 任務(wù)，為了測試基于BN-KGC 方法實(shí)現(xiàn)封閉世界KGC 的有效性，分別在3 個數(shù)據(jù)集下基于OpenKE 平臺得到TransE、TransH 及TransR 的三元組類型預(yù)測結(jié)果和鏈路預(yù)測結(jié)果，并將其與BN-KGC 進(jìn)行比較。

封閉世界下的鏈路預(yù)測結(jié)果如表5 所示，從表5可以看出，在FB15k 數(shù)據(jù)集下，基于BN-KGC 方法預(yù)測的MR 結(jié)果達(dá)到77，僅排在TransR 之后。在DBpeida50k 數(shù)據(jù)集下，基于BN-KGC 方法預(yù)測的MR結(jié)果最佳。在DBpedia500k 數(shù)據(jù)集下，基于BN-KGC方法預(yù)測的MR 結(jié)果和Hits@10 均為最佳。三元組類型預(yù)測結(jié)果的準(zhǔn)確率、召回率和F1 值如圖13 所示。從圖13 可以看出，在FB15k 和DBpedia500k 數(shù)據(jù)集下，基于BN-KGC 方法預(yù)測結(jié)果的準(zhǔn)確率和F1 值最佳，在DBpedia50k 數(shù)據(jù)集下，基于BN-KGC 方法預(yù)測結(jié)果的準(zhǔn)確率、召回率和F1 值均為最佳。實(shí)驗(yàn)結(jié)果表明，本文方法同樣適用于封閉世界KGC 任務(wù)，即BN-KGC 方法具有有效性。

圖13 封閉世界下的三元組類型預(yù)測結(jié)果比較Fig.13 Comparison of prediction results of triple type in closed-world

表5 封閉世界下的鏈路預(yù)測結(jié)果比較Table 5 Comparison of link prediction results in closed-world

本節(jié)基于FB15k 和DBpedia 數(shù)據(jù)集，首先，測試KGBN 構(gòu)建方法的時間效率，實(shí)驗(yàn)結(jié)果表明，KGBN的結(jié)構(gòu)構(gòu)建執(zhí)行時間主要取決于變量個數(shù)，且其中用于計(jì)算CPT 的執(zhí)行時間最多；其次，在開放世界下進(jìn)行三元組類型預(yù)測實(shí)驗(yàn)，對比不同變量個數(shù)、不同查詢變量個數(shù)下的KGBN 預(yù)測結(jié)果，結(jié)果表明，本文方法能夠有效提升預(yù)測結(jié)果的召回率，并且在最好情況下預(yù)測結(jié)果的準(zhǔn)確率高達(dá)0.88；然后，在開放世界下進(jìn)行鏈路預(yù)測實(shí)驗(yàn)，并將本文方法的實(shí)驗(yàn)結(jié)果與現(xiàn)有的開放世界方法進(jìn)行比較，結(jié)果表明，當(dāng)初始KG 達(dá)到一定規(guī)模時，基于本文方法預(yù)測的結(jié)果在MR 指標(biāo)上有所提升，達(dá)到159；最后，在封閉世界下分別進(jìn)行三元組類型預(yù)測和鏈路預(yù)測任務(wù)，結(jié)果表明，基于本文方法預(yù)測三元組類型時的準(zhǔn)確率和F1 值明顯高于基于表示學(xué)習(xí)的其他方法，并且在DBpedia500k 數(shù)據(jù)集下進(jìn)行鏈路預(yù)測時，本文方法的MR 和Hits@10 分 別達(dá)到107 和0.66。

6 結(jié)束語

本文使用BN 描述KG 中同類實(shí)體涉及的關(guān)系之間的依賴性，提出KGBN 模型構(gòu)建方法和基于KGBN 推理的三元組構(gòu)造方法。實(shí)驗(yàn)結(jié)果表明，該三元組構(gòu)造方法針對新實(shí)體能夠同時構(gòu)造多個三元組，有效提升KGC 任務(wù)中新知識的全面性。隨著KG 中知識的增加以及變化，關(guān)系間的依賴性也會發(fā)生相應(yīng)變化，導(dǎo)致KGBN 推理的準(zhǔn)確率降低。因此，如何將KG 中的新知識用于KGBN 構(gòu)建，實(shí)時反映關(guān)系間的依賴性，進(jìn)而提升KGC 方法的時效性，將是下一步的研究方向。