李鑫柏，吳鑫然，岳 昆

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

0 概述

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

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

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

1 相關(guān)工作

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

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

近年來(lái)，研究人員用開放世界KGC 方法從數(shù)據(jù)中提取新實(shí)體加入KG，從而豐富KG 中的知識(shí)。文獻(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í)體來(lái)構(gòu)造三元組，豐富了KG 中實(shí)體的類型，但多種類型的數(shù)據(jù)導(dǎo)致計(jì)算復(fù)雜度較高。

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

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

KG 中同一類型實(shí)體涉及的關(guān)系之間通常具有相互依賴的性質(zhì)，給定某個(gè)類型實(shí)體涉及的一些關(guān)系，通過關(guān)系之間的依賴性可得到該實(shí)體可能涉及的其他關(guān)系，從而利用該實(shí)體及更多關(guān)系來(lái)構(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 中知識(shí)的全面性。因此，如何定量地描述KG 中同類實(shí)體涉及的關(guān)系之間的依賴性，是實(shí)現(xiàn)開放世界KGC 的重要前提。

BN［14］是描述變量間相互依賴關(guān)系和不確定性知識(shí)的有效工具［15］?；谧C據(jù)變量的取值，利用BN 的概率推理，可計(jì)算得到查詢變量不同取值的條件概率。鑒于BN對(duì)不確定性知識(shí)表示與推理的優(yōu)勢(shì)，本文將BN作為KG 中關(guān)系之間依賴性表示和推理的框架，構(gòu)建一個(gè)基于KG的BN（KG-based Bayesian Network，KGBN），其中包含有向無(wú)環(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ì)算。對(duì)于同一類型的實(shí)體而言，它們共同涉及的關(guān)系描述了該類實(shí)體的特性，在KGC 任務(wù)中考慮這些關(guān)系對(duì)實(shí)體的描述作用，能夠更準(zhǔn)確地獲取新實(shí)體的特性，從而為構(gòu)造三元組提供可靠的依據(jù)。因此，本文將關(guān)系在實(shí)體描述中的重要程度作為構(gòu)建DAG 的依據(jù)，在DAG 中使得重要關(guān)系的優(yōu)先級(jí)高于次要關(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ā)揮著更重要的作用，如“語(yǔ)言”關(guān)系的尾實(shí)體“普通話”一般不具備其他信息，而“導(dǎo)演”關(guān)系的尾實(shí)體“導(dǎo)演1”具有國(guó)籍、作品等信息，根據(jù)“導(dǎo)演1”容易推出電影的“語(yǔ)言”為“普通話”，反之則很難推出一部“普通話”電影的“導(dǎo)演”是“導(dǎo)演1”。

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

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

三元組的正確與否決定了KG 所表達(dá)知識(shí)的可靠性，考慮到KGC 任務(wù)對(duì)結(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ù)，即針對(duì)KG 中已有的實(shí)體進(jìn)行補(bǔ)全。針對(duì)KG 中已有的某個(gè)實(shí)體，在包含該實(shí)體的三元組中存在已知的關(guān)系和尾實(shí)體，可以作為KGBN 推理的證據(jù)變量及其取值，基于KGBN 推理即可獲取其他變量的取值條件概率，進(jìn)而構(gòu)造出更多三元組。

本文使用DBpedia數(shù)據(jù)集［19］和Freebase數(shù)據(jù)集［20］，分別在開放世界和封閉世界下進(jìn)行鏈路預(yù)測(cè)和三元組類型預(yù)測(cè)實(shí)驗(yàn)，以測(cè)試本文方法的結(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í)體個(gè)數(shù)，R={r1,r2,…,rγ}表示關(guān)系集合，γ為關(guān)系的個(gè)數(shù)，T={(h,r,t)}(h,t?E,h≠t,r?R)表示三元組集合，h為頭實(shí)體，t為尾實(shí)體。

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

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

1）GB=(X,Y)表示DAG 結(jié)構(gòu)，X={x1,x2,…,xn}表示變量集，xi表示GK中同類實(shí)體所涉及的任意一個(gè)關(guān)系，Y表示有向邊集，表示由xi到xj的有向邊，此時(shí)，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í)體描述中的重要程度來(lái)獲取關(guān)系之間的優(yōu)先級(jí)別，并將其表示為DAG 中變量之間的有向邊，從而獲取KG中同一類型實(shí)體所涉及的關(guān)系之間的依賴性。

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

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

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

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

在構(gòu)建GB時(shí)，首先利用式（1）計(jì)算各變量所表示關(guān)系的IF 值，并根據(jù)IF 值對(duì)變量進(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)建時(shí)，依次從變量集X中取出變量xi(1≤i≤n-1)，放入SameX集合中，并將這個(gè)變量所表示關(guān)系的IF 值與X中下一個(gè)變量xi+1(1≤i≤n-1)所表示關(guān)系的IF 值進(jìn)行比較，比較結(jié)果分為以下4 種情況：

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

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

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

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

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

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

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

如表1 所示，算法1 在第一次、第二次執(zhí)行中分別添加有向邊和，在第三次執(zhí)行時(shí)，將x3與x4比較，得到IIF(r3)=IIF(r4)，且RRT(r3)=RRT(r4)，將x3保留在SameX集中，繼續(xù)循環(huán)。接著，將x4放入SameX集中，并與下一個(gè)變量x5進(jìn)行比較，得到IIF(r4)=IIF(r5)和RRT(r4)=RRT(r5)，且x4為倒數(shù)第二個(gè)變量，將x5放入SameX集。此時(shí)，SameX集中有3 個(gè)變量，由此找到變量x2，根據(jù)表1 可以看出，x2所表示關(guān)系的RT 值大于SameX集中變量所表示關(guān)系的RT值，且x2是最接近SameX集中變量的變量，因此，分別對(duì)SameX集中除第一個(gè)變量之外的每個(gè)變量添加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í)體來(lái)生成KGBN 中包含n個(gè)變量取值的組合，并統(tǒng)計(jì)變量取值組合的個(gè)數(shù)，從而利用DAG 和數(shù)據(jù)集計(jì)算得到KGBN 的CPT。

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

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

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

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

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

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

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

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

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

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

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

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

在計(jì)算CPT 時(shí)，若xi無(wú)父變量，其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ù)雜度相對(duì)于變量個(gè)數(shù)成指數(shù)增長(zhǎng)，變量消元（Variable Elimination，VE）方法［23］利用變量間的條件獨(dú)立關(guān)系減少推理過程中的變量個(gè)數(shù)，降低計(jì)算復(fù)雜度，使得整體計(jì)算復(fù)雜度未必相對(duì)于變量個(gè)數(shù)成指數(shù)增長(zhǎng)［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)造三元組的基本思想如下：首先，針對(duì)集合Xq中任意一個(gè)查詢變量x，計(jì)算得到包含φ中所有概率分布的集合，并將Xz中各個(gè)變量的取值代入其中；其次，對(duì)除x外所有屬于X但不屬于Xz的變量設(shè)置消元順序，對(duì)其中每個(gè)變量進(jìn)行求和消元，得到一個(gè)新的概率分布集合；然后，將概率分布集合中的所有函數(shù)相乘得到關(guān)于x的函數(shù)，進(jìn)而利用函數(shù)計(jì)算得到x各個(gè)取值的條件概率，并找到最大條件概率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í)行代價(jià)主要取決于集合Xq中的查詢變量個(gè)數(shù)和每次推理中消元的變量個(gè)數(shù)，算法2 的總執(zhí)行代價(jià)為查詢變量的個(gè)數(shù)和每次推理中消元執(zhí)行代價(jià)之和的乘積。

在封閉世界下執(zhí)行KGC 任務(wù)時(shí)，首先，將KG 中包含同一個(gè)頭實(shí)體的多個(gè)三元組作為一個(gè)集合；其次，利用其中的關(guān)系及尾實(shí)體作為證據(jù)變量及證據(jù)變量的取值；然后，將集合X中其他變量作為查詢變量；最后，針對(duì)查詢變量進(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)證

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 開放世界KGC 方法有效性測(cè)試

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

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

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

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

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

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

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

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

5.2.2 鏈路預(yù)測(cè)

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

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

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

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

5.3 封閉世界KGC 方法有效性測(cè)試

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

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

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

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

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

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

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