陳欽況，陳 珂,2+，伍 賽,2，壽黎但,2，陳 剛,2

1.浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310027

2.浙江省大數(shù)據(jù)智能計(jì)算重點(diǎn)實(shí)驗(yàn)室（浙江大學(xué)），杭州 310027

1 引言

隨著信息科技的突破，新一代人工智能迎來了史無前例的發(fā)展熱潮。知識圖譜作為人工智能的基礎(chǔ)支撐，例如支撐軌道交通運(yùn)維優(yōu)化、系統(tǒng)設(shè)計(jì)等，目前也得到了許多學(xué)者和研究人員的關(guān)注。

知識圖譜是一種信息網(wǎng)絡(luò)，它包含真實(shí)世界中存在的物品、人物、地點(diǎn)等信息。知識圖譜一般用三元組集合來表示，用RDF（resource description framework）或者圖數(shù)據(jù)庫來存儲三元組。知識圖譜目前已經(jīng)被廣泛應(yīng)用在搜索、推薦、問答領(lǐng)域，知識圖譜逐漸成為人工智能領(lǐng)域不可或缺的一部分。學(xué)術(shù)界對知識圖譜的研究從未間斷過，隨著人工智能的熱潮來臨，研究知識圖譜變得越來越重要。

常見的公開的知識圖譜有Freebase、DBPedia、ConceptNet 等。然而這些知識圖譜都有不同程度的缺失。這些知識圖譜的缺失主要體現(xiàn)在實(shí)體與實(shí)體之間缺失本應(yīng)該有關(guān)系的邊。知識圖譜補(bǔ)全任務(wù)（knowledge graph completion）是致力于通過預(yù)測知識圖譜中潛在的關(guān)系，從而提高知識圖譜的完整性和可靠性。許多學(xué)者對知識圖譜補(bǔ)全任務(wù)進(jìn)行了許多探索和研究，其中包括：（1）路徑排序算法（path ranking algorithm，PRA）[1-5]；（2）詞嵌入技術(shù)[6-12]；（3）神經(jīng)網(wǎng)絡(luò)方法[13-18]。這些方法一般將知識圖譜補(bǔ)全任務(wù)看作是分類問題，比如路徑排序算法（PRA）的改進(jìn)——子圖特征提取算法（sub-graph feature extraction，SFE）[2]通過判斷不在知識圖譜中的三元組是否成立，來實(shí)現(xiàn)知識圖譜缺失補(bǔ)全。

然而這些方法存在以下兩個問題：（1）這些方法都關(guān)注于算法準(zhǔn)確率，使用的測試集一般由人工規(guī)則進(jìn)行構(gòu)建，如果將這些方法應(yīng)用到真實(shí)的知識圖譜上，需要對所有的候選目標(biāo)進(jìn)行分類任務(wù)，導(dǎo)致龐大的時間開銷。（2）這些方法都只著眼于知識圖譜內(nèi)部數(shù)據(jù)的缺失補(bǔ)全，沒有考慮到采用知識圖譜外部數(shù)據(jù)進(jìn)行缺失補(bǔ)全，導(dǎo)致利用的信息不充分。這些方法在缺失補(bǔ)全上有這么兩點(diǎn)局限，因此本文提出一種基于主動學(xué)習(xí)的知識圖譜補(bǔ)全框架，這個框架由三部分構(gòu)成：不斷更新的知識圖譜、鏈接預(yù)測器、關(guān)系驗(yàn)證器。其中鏈接預(yù)測器預(yù)測知識圖譜中最有可能產(chǎn)生鏈接的k對實(shí)體對，關(guān)系驗(yàn)證器推理驗(yàn)證實(shí)體對之間的關(guān)系，形成新的三元組完善知識圖譜。

本文的主要貢獻(xiàn)可以概括如下：

（1）提出了一種采用主動學(xué)習(xí)，使用知識圖譜內(nèi)部和外部關(guān)系驗(yàn)證，從而不斷完善知識圖譜的框架。這個框架結(jié)合了主動學(xué)習(xí)，能夠不斷完善知識圖譜。

（2）在鏈接預(yù)測階段，提出了增強(qiáng)鏈接預(yù)測算法（enhance link prediction，ELP）來預(yù)測知識圖譜中最有可能形成鏈接的實(shí)體對。ELP 算法結(jié)合了Rooted PageRank 算法和實(shí)體聚類算法，能夠有效挖掘知識圖譜中的圖結(jié)構(gòu)信息和語義信息。利用ELP 算法能夠?qū)崿F(xiàn)主動學(xué)習(xí)，從而不斷完善知識圖譜。

（3）在關(guān)系驗(yàn)證階段，提出一種采用基礎(chǔ)驗(yàn)證加增強(qiáng)驗(yàn)證的方法驗(yàn)證關(guān)系。實(shí)驗(yàn)表明，這種方法能夠有效利用知識圖譜內(nèi)部數(shù)據(jù)和互聯(lián)網(wǎng)數(shù)據(jù)進(jìn)行關(guān)系驗(yàn)證。

2 相關(guān)工作

本文的相關(guān)工作主要涉及鏈接預(yù)測任務(wù)、知識圖譜補(bǔ)全任務(wù)、知識庫問答系統(tǒng)、實(shí)體抽取、關(guān)系抽取等領(lǐng)域。

在知識圖譜補(bǔ)全領(lǐng)域已經(jīng)有許多學(xué)者做出了豐富的研究，Lao 等人[1]提出路徑排序算法（PRA），PRA通過計(jì)算知識圖譜中節(jié)點(diǎn)間的特征矩陣來實(shí)現(xiàn)知識圖譜中的鏈接預(yù)測。PRA 算法主要分成兩步：（1）使用統(tǒng)計(jì)模型來尋找兩個節(jié)點(diǎn)間的潛在路徑。（2）計(jì)算任意兩個節(jié)點(diǎn)間的隨機(jī)游走概率。Gardner 等人[2]在PRA 的基礎(chǔ)上提出了子圖特征提取算法（SFE）。SFE 將知識圖譜補(bǔ)全任務(wù)看作是二分類問題，通過判斷三元組是否成立來實(shí)現(xiàn)知識圖譜缺失補(bǔ)全。SFE 算法主要分成兩步：（1）提取兩個節(jié)點(diǎn)的一系列特征。（2）采用二分類分類器對第一步提取的特征做二分類判別。

Bordes 等人[6]提出了詞嵌入模型TransE。TransE模型將實(shí)體和關(guān)系映射到低維空間中的向量，通過計(jì)算向量間距離h′+r′-t′來實(shí)現(xiàn)知識圖譜缺失補(bǔ)全。Wang 等人[7]在TransE 模型的基礎(chǔ)上提出了TransH 模型，TransH 模型將實(shí)體映射到關(guān)系向量的超平面中，增強(qiáng)向量解釋能力。

Neelakantan 等人[14]提出了Path-RNN 模型來推理兩個節(jié)點(diǎn)間的關(guān)系。Path-RNN 將兩個節(jié)點(diǎn)路徑之間的實(shí)體輸入到循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network，RNN）中，來實(shí)現(xiàn)實(shí)體間的關(guān)系推理。Das 等人[15]在Path-RNN 的基礎(chǔ)上提出Single Model，Single Model不僅考慮了節(jié)點(diǎn)間路徑上的實(shí)體，還考慮了路徑上的關(guān)系，增強(qiáng)了神經(jīng)網(wǎng)絡(luò)的表達(dá)能力。

在社交網(wǎng)絡(luò)領(lǐng)域，許多學(xué)者和研究人員對鏈接預(yù)測問題進(jìn)行了許多研究[19-21]。鏈接預(yù)測問題主要是從圖中篩選出最有可能形成鏈接的k對節(jié)點(diǎn)對。解決鏈接預(yù)測問題的方法主要有三類：（1）局部方法；（2）基于路徑的方法；（3）隨機(jī)游走方法。其中局部方法有公共鄰居方法、Jaccard 系數(shù)等，主要的流程是計(jì)算節(jié)點(diǎn)對之間的相鄰的節(jié)點(diǎn)來實(shí)現(xiàn)相似度的計(jì)算?；诼窂降姆椒ㄓ凶疃搪窂健atz 距離等，主要的流程是計(jì)算節(jié)點(diǎn)對之間的路徑信息來實(shí)現(xiàn)相似度的計(jì)算。隨機(jī)游走的方法有Rooted PageRank 等，主要的流程是通過圖中節(jié)點(diǎn)的隨機(jī)游走來實(shí)現(xiàn)相似度計(jì)算。

主動學(xué)習(xí)[22]是一種機(jī)器學(xué)習(xí)技術(shù)，從數(shù)據(jù)中選擇出具有代表性或者能夠有利于學(xué)習(xí)模型快速學(xué)習(xí)的樣本。主動學(xué)習(xí)解決的問題包含已標(biāo)注的數(shù)據(jù)和未標(biāo)注的數(shù)據(jù)，主動學(xué)習(xí)采用算法策略從未標(biāo)注的數(shù)據(jù)中選擇一部分最有利于學(xué)習(xí)模型學(xué)習(xí)的數(shù)據(jù)，交由專家系統(tǒng)進(jìn)行標(biāo)注，標(biāo)注后的數(shù)據(jù)用于學(xué)習(xí)更好的模型。

知識庫問答系統(tǒng)（knowledge base question answering，KBQA）[23-24]是給定自然語言問題，通過對自然語言問題的語義分析，利用知識庫進(jìn)行語義查詢、關(guān)系推理得到答案。KBQA 主要分以下幾個模塊：問題分析、短語映射、消歧、查詢構(gòu)建等。KBQA 主要的應(yīng)用體現(xiàn)在智能問答上，同時也廣泛應(yīng)用于搜索、推薦等領(lǐng)域。

還有許多學(xué)者對開放世界假設(shè)下的知識圖譜補(bǔ)全問題進(jìn)行了深入的研究[25]。開放世界假設(shè)指知識圖譜中的關(guān)系代表現(xiàn)實(shí)世界中正確的關(guān)系，知識圖譜中未知的關(guān)系可能代表現(xiàn)實(shí)世界中錯誤的關(guān)系，也可能代表現(xiàn)實(shí)世界中存在的關(guān)系。開放世界假設(shè)對應(yīng)的是封閉世界假設(shè)，封閉世界假設(shè)是指知識圖譜中未知的關(guān)系代表現(xiàn)實(shí)世界錯誤的關(guān)系。一般知識圖譜比較完善的時候，或者是知識圖譜不完全，但是由于需要通過知識圖譜對現(xiàn)實(shí)世界的問題做出回答時采用封閉世界假設(shè)。

3 知識圖譜補(bǔ)全方法框架

本文對知識圖譜作如下定義：知識圖譜由三元組集合O={(h,r,t)}構(gòu)成。每個三元組都有兩個實(shí)體h,t∈E 和關(guān)系r∈R，其中E 是實(shí)體集合，R 是關(guān)系集合。定義,ei∈E,ej∈E 是知識圖譜中的實(shí)體對。知識圖譜補(bǔ)全框架的主要流程如圖1 所示，知識圖譜補(bǔ)全框架主要分為鏈接預(yù)測和關(guān)系驗(yàn)證兩個模塊。鏈接預(yù)測模塊主要是從知識圖譜中篩選出最有可能形成鏈接的k對實(shí)體對。關(guān)系驗(yàn)證模塊驗(yàn)證鏈接預(yù)測輸出的實(shí)體對之間的關(guān)系，形成正確的三元組。形成正確的三元組會返回知識圖譜進(jìn)行不斷更新迭代。整個知識圖譜補(bǔ)全框架包含了主動學(xué)習(xí)的思想，鏈接預(yù)測模塊從未標(biāo)注數(shù)據(jù)中選擇代表性的數(shù)據(jù)，交由關(guān)系驗(yàn)證模塊進(jìn)行專家驗(yàn)證。

Fig.1 Flowsheet of knowledge graph completion圖1 知識圖譜補(bǔ)全流程圖

鏈接預(yù)測模塊主要實(shí)現(xiàn)篩選知識圖譜中最有可能形成鏈接的k對節(jié)點(diǎn)對。鏈接預(yù)測模塊以知識圖譜的三元組作為輸入，采用ELP 算法，尋找并篩選整個知識圖譜中最有可能形成鏈接的k對實(shí)體對。ELP 算法采用實(shí)體聚類算法來挖掘知識圖譜中的語義信息，采用Rooted PageRank 算法來挖掘知識圖譜中的圖結(jié)構(gòu)信息，經(jīng)過聯(lián)合篩選來挖掘知識圖譜中最有可能形成鏈接的k對實(shí)體對。鏈接預(yù)測模塊輸出實(shí)體對，由關(guān)系驗(yàn)證模塊進(jìn)行進(jìn)一步的關(guān)系確認(rèn)。關(guān)系驗(yàn)證形成的正確的三元組能夠返回鏈接預(yù)測模塊進(jìn)行進(jìn)一步的學(xué)習(xí)，使得鏈接預(yù)測模塊能夠更好地預(yù)測知識圖譜中能夠形成鏈接的實(shí)體對。

關(guān)系驗(yàn)證模塊主要實(shí)現(xiàn)對實(shí)體對之間的關(guān)系的驗(yàn)證。關(guān)系驗(yàn)證模塊由基礎(chǔ)驗(yàn)證和增強(qiáng)驗(yàn)證兩部分構(gòu)成?；A(chǔ)驗(yàn)證采用TransH[7]算法，以知識圖譜內(nèi)部的數(shù)據(jù)作為訓(xùn)練集，對鏈接預(yù)測模塊產(chǎn)生的實(shí)體對進(jìn)行分類任務(wù)確定實(shí)體對間的關(guān)系。增強(qiáng)驗(yàn)證模塊通過爬取、清洗互聯(lián)網(wǎng)結(jié)構(gòu)化數(shù)據(jù)，采用多源數(shù)據(jù)關(guān)系驗(yàn)證和領(lǐng)域?qū)＜业娜藱C(jī)交互方式來實(shí)現(xiàn)對基礎(chǔ)驗(yàn)證輸出的三元組集合的進(jìn)一步驗(yàn)證。關(guān)系驗(yàn)證模塊輸出正確的三元組，輸出的三元組返回知識圖譜補(bǔ)全完善知識圖譜。正確的三元組還會返回鏈接預(yù)測模塊，增強(qiáng)鏈接預(yù)測模塊的鏈接預(yù)測效果。

4 鏈接預(yù)測

鏈接預(yù)測模塊主要的任務(wù)是從知識圖譜中篩選出前k對最有可能形成鏈接的實(shí)體對。本章提出了增強(qiáng)鏈接預(yù)測算法（ELP），ELP 算法結(jié)合了Rooted PageRank 算法和實(shí)體聚類算法進(jìn)行聯(lián)合篩選，使得篩選出的候選實(shí)體對更有可能形成鏈接。Rooted PageRank 算法能夠挖掘知識圖譜中的圖結(jié)構(gòu)信息，篩選可能形成鏈接的實(shí)體對。而實(shí)體聚類算法能夠挖掘知識圖譜中的語義信息，排除不可能形成鏈接的實(shí)體對。ELP 中算法中的Rooted PageRank算法和實(shí)體聚類算法是相對獨(dú)立的兩個子模塊，通過該兩個模塊的聯(lián)合篩選，能夠篩選出知識圖譜中最有可能形成鏈接的實(shí)體對。由于ELP 算法結(jié)合了知識圖譜中的語義信息和圖結(jié)構(gòu)信息，因此ELP 算法信息挖掘能力更強(qiáng)，能夠通過主動學(xué)習(xí)增強(qiáng)鏈接預(yù)測的性能。將在實(shí)驗(yàn)中證明本章提出的ELP 算法效果優(yōu)于Rooted PageRank 算法，并且具有主動學(xué)習(xí)能力。本文分知識圖譜實(shí)體聚類和Rooted PageRank算法兩部分來介紹ELP 算法。

4.1 實(shí)體聚類算法

本節(jié)提出一種知識圖譜實(shí)體聚類算法來挖掘知識圖譜中的語義信息。在知識圖譜中，節(jié)點(diǎn)和邊分別代表實(shí)體和關(guān)系，節(jié)點(diǎn)和邊都是有各自的語義的。本節(jié)提出的實(shí)體聚類方法能夠快速篩選出知識圖譜中的實(shí)體類。篩選出的實(shí)體類可以用于ELP 算法的聯(lián)合篩選。它主要分成兩個階段：（1）實(shí)體類的初始化；（2）實(shí)體類的合并。

定義知識圖譜可以看作是有向圖G，其中實(shí)體類E 是有向圖G 的節(jié)點(diǎn)，三元組o=∈O 可以看成是有向圖G 中從節(jié)點(diǎn)h出發(fā)到節(jié)點(diǎn)t的一條有向邊。定義H={H1,H2,…,H2m}代表頭節(jié)點(diǎn)類集合，T={T1,T2,…,T2m}代表尾節(jié)點(diǎn)類集合。

對于關(guān)系ri∈R，有三元組集合Oi={(hij,ri,tij)}?O，其中hij∈Hi，tij∈Ti。如圖2 所示，頭節(jié)點(diǎn)類Hi中的實(shí)體hij都有一定的相似性，比如關(guān)系-Nationality-對應(yīng)的頭實(shí)體類一般都是人。尾實(shí)體類Ti中的實(shí)體tij也有一定的相似性，比如關(guān)系-Gender-對應(yīng)的尾實(shí)體類一般都是性別。圖2 中的{e1,e2}、{e2,e3}、{e4,e5}、{e6,e7}分別構(gòu)成4 個實(shí)體類{H1,H2,T1,T2}。

Fig.2 Entity class initialization diagram圖2 實(shí)體類初始化示意圖

實(shí)體類的初始化過程需要遍歷關(guān)系集合R，對于每個關(guān)系ri∈R，記錄對應(yīng)的頭實(shí)體類Hi和尾實(shí)體類Ti。最后得到了2m個初始實(shí)體類，該實(shí)體類集合記為S={H1,H2,…,H2m,T1,T2,…,T2m} 。值得注意的是，由于知識圖譜包含一些錯誤數(shù)據(jù)，以及一些關(guān)系的頭實(shí)體類和尾實(shí)體類有一定的重復(fù)，因此對于任意的實(shí)體e∈E，可能屬于一個或者多個實(shí)體類。初始化實(shí)體類的流程如下：

算法1初始化實(shí)體類

實(shí)體聚類算法的第二個階段是合并初始實(shí)體類。經(jīng)過上一步提取的實(shí)體類存在很多錯誤，這些錯誤主要體現(xiàn)在以下幾個方面：（1）知識圖譜中可能有些邊是錯誤的，比如大規(guī)模的多語言百科知識圖譜DBpedia 有大約10%的錯誤率。知識圖譜中錯誤的三元組可能會導(dǎo)致一些實(shí)體類包含少量本不屬于該集合的實(shí)體。（2）一些集合之間可能存在大量重復(fù)的實(shí)體。比如關(guān)系-Gender-和關(guān)系-Nationality-對應(yīng)的頭實(shí)體類高度相似，這兩個實(shí)體類之間存在大量相似的實(shí)體。由于實(shí)體類初始化提取的實(shí)體類存在以上的問題，因此需要對上一步提取的實(shí)體類做進(jìn)一步的處理。實(shí)體類的合并過程如圖3 所示，當(dāng)發(fā)現(xiàn){e1,e2}、{e2,e3}兩個實(shí)體類較為相似，這兩個實(shí)體類需要被合并，合并完后剩余的實(shí)體類有{e1,e2,e3}、{e4,e5}、{e6,e7}三個實(shí)體類，記為{H1,T1,T2}。

對于實(shí)體類si,sj∈S，count(si)、count(sj)分別代表實(shí)體類si和sj中的實(shí)體數(shù)量。定義兩個集合的相似度：

任意兩個相似度超過閾值τ的實(shí)體類需要進(jìn)行合并，不斷迭代直到?jīng)]有兩個實(shí)體類相似度超過閾值τ。

由于實(shí)體類過程中的每次迭代需要計(jì)算兩兩實(shí)體類間的相似度，當(dāng)實(shí)體類較多時候，每次迭代需要較大的時間開銷，因此采用貪心策略來加速實(shí)體類的合并。實(shí)體類的合并算法如下：

（1）隨機(jī)選取一個集合，計(jì)算其他集合與當(dāng)前集合的相似度。

（2）選取一個與當(dāng)前集合相似度最大的集合，如果相似度超過閾值τ，則將這兩個集合進(jìn)行合并，并將新的集合作為當(dāng)前集合；如果沒有超過閾值τ，則將當(dāng)前集合標(biāo)記為終態(tài)，以后不參與集合合并。

（3）重復(fù)前兩步直到所有集合都為終態(tài)。

算法2實(shí)體類的合并

Fig.3 Diagram of entity class consolidation process圖3 實(shí)體類合并過程示意圖

4.2 Rooted PageRank 算法

Rooted PageRank 算法[19-20]將知識圖譜看作是無向圖G，其中實(shí)體E 是無向圖G的節(jié)點(diǎn)，三元組o=∈O 可以看成是無向圖G中從節(jié)點(diǎn)h出發(fā)到節(jié)點(diǎn)t的一條無向邊。介紹Rooted PageRank 算法之前，本節(jié)先介紹隨機(jī)游走算法（Random Walks）。對于任意節(jié)點(diǎn)x∈E，隨機(jī)游走算法以等概率游走到和節(jié)點(diǎn)x相鄰的節(jié)點(diǎn)。定義命中時間Hx,y：從節(jié)點(diǎn)x，隨機(jī)游走到節(jié)點(diǎn)y的期望步長，其中x,y∈E 。那么往返時間Cx,y定義如下：

Rooted PageRank 算法在隨機(jī)游走算法的基礎(chǔ)上引入了重啟機(jī)制，對于圖G中的任意節(jié)點(diǎn)x，每次隨機(jī)游走的時候，以α的概率重新回到節(jié)點(diǎn)x，以1-α的概率游走到與節(jié)點(diǎn)x相鄰的節(jié)點(diǎn)。本文定義score(x,y)代表從節(jié)點(diǎn)x隨機(jī)游走到y(tǒng)的穩(wěn)定概率。選擇score較高的k個實(shí)體對作為知識圖譜中最有可能形成鏈接的實(shí)體對。相應(yīng)的圖計(jì)算核方法是(1-α)(I-αD-1A)-1，其中D代表度矩陣，A代表鄰接矩陣。

4.3 ELP 算法

前文所介紹的Rooted PageRank 算法能夠通過知識圖譜的圖結(jié)構(gòu)，從知識圖譜中發(fā)現(xiàn)最有可能形成鏈接的k對實(shí)體對。而實(shí)體聚類算法則是挖掘知識圖譜中的語義信息對知識圖譜中的實(shí)體進(jìn)行聚類。本節(jié)將提出ELP 算法，聯(lián)合Rooted PageRank算法和實(shí)體聚類算法對實(shí)體對進(jìn)行篩選。

在實(shí)體聚類算法對知識圖譜中的實(shí)體進(jìn)行聚類后，對于任意兩個實(shí)體類Si,Sj∈S，定義三元組集合Oz={(hik,rz,tjk)}?O 并且滿足hik∈Si,tjk∈Sj。定義實(shí)體類之間的置信度如下：

如果兩個實(shí)體類之間的置信度大于閾值β，則任意兩個實(shí)體ei和ej都屬于篩選出的實(shí)體候選對。因此，對于實(shí)體對,ei∈Si,ej∈Sj，有如下關(guān)系：

ELP 算法采用Rooted PageRank 算法和實(shí)體聚類算法聯(lián)合篩選進(jìn)行鏈接預(yù)測。既考慮了知識圖譜中的圖結(jié)構(gòu)信息，又考慮了知識圖譜的語義信息。通過ELP 算法篩選出的最有可能形成鏈接的k對實(shí)體對更具有代表性，可獲得優(yōu)于Rooted PageRank 算法的效果。

另外，ELP 算法具有主動學(xué)習(xí)能力。對于鏈接預(yù)測問題，將整個知識圖譜看作是數(shù)據(jù)集Ud，所有在知識圖譜中有鏈接的數(shù)據(jù)看作是訓(xùn)練集Us，所有不在知識圖譜中的鏈接看作是測試集Ut。ELP 算法每次從測試集Ut選出一定數(shù)量的樣本，通過關(guān)系驗(yàn)證模塊組合成正確的三元組加入訓(xùn)練集Us，組成新的訓(xùn)練集Us′和新的測試集Ut′。在實(shí)驗(yàn)環(huán)節(jié)，驗(yàn)證了對于新的訓(xùn)練集Us′，ELP 算法的鏈接預(yù)測效果比原訓(xùn)練集Us要好。這說明ELP 算法具有主動學(xué)習(xí)能力，對于更完善的數(shù)據(jù)集，ELP 算法有更強(qiáng)的潛在信息挖掘能力。

5 關(guān)系驗(yàn)證

關(guān)系驗(yàn)證模塊驗(yàn)證鏈接預(yù)測輸出的實(shí)體對的關(guān)系。對于鏈接預(yù)測輸出的任一實(shí)體對，關(guān)系驗(yàn)證模塊需要找到對應(yīng)正確的三元組，如果不存在關(guān)系，則有r=NULL。本章采用基礎(chǔ)驗(yàn)證和增強(qiáng)驗(yàn)證兩個模塊解決關(guān)系驗(yàn)證問題。在基礎(chǔ)驗(yàn)證模塊中，將關(guān)系驗(yàn)證問題看作是關(guān)系分類問題，采用TransH 算法對鏈接預(yù)測模塊輸出的實(shí)體對進(jìn)行分類任務(wù)。在增強(qiáng)驗(yàn)證模塊，通過爬蟲技術(shù)爬取互聯(lián)網(wǎng)上結(jié)構(gòu)化數(shù)據(jù)信息，采用多源數(shù)據(jù)關(guān)系驗(yàn)證和領(lǐng)域?qū)＜胰藱C(jī)交互方式來實(shí)現(xiàn)增強(qiáng)驗(yàn)證。

5.1 基礎(chǔ)驗(yàn)證

在基礎(chǔ)驗(yàn)證模塊，本節(jié)只利用知識圖譜內(nèi)部的數(shù)據(jù)，將關(guān)系驗(yàn)證看作是分類問題。對于任一實(shí)體對，需要對所有r∈R 做二分類判別。即是對于所有的r∈R，判斷三元組是否成立。關(guān)系驗(yàn)證也可以看成是多分類任務(wù)，即對于實(shí)體對，分類選擇出正確的關(guān)系r，形成正確的三元組。

Bordes 等人[6]提出詞嵌入模型TransE，TransE 模型將知識圖譜中的實(shí)體和關(guān)系都用數(shù)學(xué)空間的向量來表示。因此，對于三元組，可以通過計(jì)算頭實(shí)體h和尾實(shí)體t的向量距離來實(shí)現(xiàn)關(guān)系驗(yàn)證。圖4展現(xiàn)了三元組在數(shù)學(xué)空間中的關(guān)系。

Fig.4 Math space of TransE圖4 TransE 模型數(shù)學(xué)空間

對于知識圖譜中的三元組O={(h,r,t)}，其中h,t∈E,r∈R，TransE 模型將實(shí)體和關(guān)系映射到數(shù)學(xué)空間Rk中，其中k是模型的超參數(shù)。定義知識圖譜中的正確的三元組集合為S(h,r,t)，錯誤的三元組集合為S′(h′,r,t′)，其中S′(h′,r,t′)可以隨機(jī)替換知識圖譜中正確的三元組的頭實(shí)體和尾實(shí)體來得到。有如下等式:

其中，γ是超參數(shù)。實(shí)體向量和關(guān)系向量可以通過訓(xùn)練目標(biāo)函數(shù)L來得到。

Wang等人[7]在TransE模型的基礎(chǔ)上提出了TransH模型，TransH 模型在TransE 模型的基礎(chǔ)上把實(shí)體向量和關(guān)系向量映射到超平面空間wr。圖5 展現(xiàn)了TransH 模型中的三元組在數(shù)學(xué)空間中的關(guān)系。TransH 模型的距離函數(shù)和目標(biāo)函數(shù)如下定義：

Fig.5 Math space of TransH圖5 TransH 模型數(shù)學(xué)空間

模型訓(xùn)練開始時，一般用隨機(jī)值來初始化實(shí)體向量和關(guān)系向量。在訓(xùn)練過程中，為了節(jié)省計(jì)算資源以及加快訓(xùn)練速度，研究人員往往采用隨機(jī)梯度下降方法SGD（stochastic gradient descent）來實(shí)現(xiàn)模型的訓(xùn)練，采用L2正則化方法來避免模型對訓(xùn)練數(shù)據(jù)的過擬合。

5.2 增強(qiáng)驗(yàn)證

通過基礎(chǔ)驗(yàn)證后的三元組仍存在許多錯誤，造成這些錯誤的原因主要是基礎(chǔ)驗(yàn)證只利用了知識圖譜內(nèi)部的數(shù)據(jù)信息，然而現(xiàn)實(shí)世界中大多數(shù)知識圖譜包含的知識信息較為有限。隨著互聯(lián)網(wǎng)的進(jìn)一步發(fā)展，諸如百度百科、互動百科、維基百科等包含了大量的知識信息。因此，本文提出利用外部數(shù)據(jù)進(jìn)行增強(qiáng)驗(yàn)證，增強(qiáng)驗(yàn)證模塊包括三部分：（1）多源數(shù)據(jù)的采集與清洗；（2）多源數(shù)據(jù)的關(guān)系驗(yàn)證；（3）領(lǐng)域?qū)＜业娜藱C(jī)交互驗(yàn)證。

定義多源數(shù)據(jù)S={S1,S2,…,Sn}表示不同數(shù)據(jù)源的數(shù)據(jù)，數(shù)據(jù)倉庫KB={KB1,KB2,…,KBn}表示多源數(shù)據(jù)S經(jīng)過爬蟲技術(shù)采集、數(shù)據(jù)清洗、數(shù)據(jù)格式規(guī)范化后的數(shù)據(jù)。對于任意數(shù)據(jù)倉庫KBi都符合以下形式：

其中，Ei={ei1,ei2,…,eim}代表數(shù)據(jù)倉庫KBi中的實(shí)體集合，Ri={ri1,ri2,…,rim}代表數(shù)據(jù)倉庫KBi中的關(guān)系集合，Oi代表數(shù)據(jù)倉庫KBi中的三元組集合。增強(qiáng)驗(yàn)證模塊如圖6。

數(shù)據(jù)采集部分采用網(wǎng)絡(luò)爬蟲技術(shù)對互聯(lián)網(wǎng)上的網(wǎng)站進(jìn)行數(shù)據(jù)爬取。許多網(wǎng)站針對開發(fā)者開放了API接口與Dump 文件等?；ヂ?lián)網(wǎng)上的數(shù)據(jù)如圖7 所示，一般由文本數(shù)據(jù)和結(jié)構(gòu)化Infobox 數(shù)據(jù)構(gòu)成。增強(qiáng)驗(yàn)證模塊主要采用互聯(lián)網(wǎng)的結(jié)構(gòu)化數(shù)據(jù)進(jìn)行關(guān)系驗(yàn)證。

Fig.6 Flowsheet of enhanced verification圖6 增強(qiáng)驗(yàn)證流程圖

Fig.7 Diagram of Wiki Web page圖7 Wiki網(wǎng)頁數(shù)據(jù)示意圖

爬取后的數(shù)據(jù)需要進(jìn)行數(shù)據(jù)清洗和格式規(guī)范化，包含以下幾點(diǎn)：（1）剔除無關(guān)字符。（2）關(guān)系統(tǒng)一化。在不同數(shù)據(jù)源中，關(guān)系描述可能不一致，因此需要將同一關(guān)系的不同描述統(tǒng)一化。（3）實(shí)體消歧與統(tǒng)一化。在不同數(shù)據(jù)源中，實(shí)體的描述可能并不一致，可能出現(xiàn)縮寫名等，因此需要對實(shí)體進(jìn)行統(tǒng)一化。經(jīng)過清洗與規(guī)范化后的數(shù)據(jù)會存入數(shù)據(jù)倉庫中，進(jìn)行多源數(shù)據(jù)關(guān)系驗(yàn)證。

多源數(shù)據(jù)關(guān)系驗(yàn)證以基礎(chǔ)驗(yàn)證輸出的三元組集合Op、知識圖譜G和數(shù)據(jù)倉庫KB為輸入，輸出置信度集合Cp。對于任意三元組o=∈Op，與數(shù)據(jù)倉庫KBi進(jìn)行數(shù)據(jù)對齊需要考慮如下兩點(diǎn)：（1）實(shí)體h在知識圖譜G中描述的實(shí)體和在數(shù)據(jù)倉庫KBi中描述的實(shí)體是不是同一個實(shí)體。（2）數(shù)據(jù)倉庫KBi是否存在三元組o=。

式（10）描述了三元組關(guān)系o與數(shù)據(jù)倉庫KBi之間的對應(yīng)關(guān)系。

式（11）描述了三元組o與數(shù)據(jù)倉庫KBi之間置信度。其中VG表示知識圖譜G中包含實(shí)體h的三元組集合，VKBi表示在數(shù)據(jù)倉庫KBi中包含實(shí)體h的三元組集合。因此對于三元組o，總的置信度有如下公式：

多源數(shù)據(jù)關(guān)系驗(yàn)證輸出三元組集合和置信度，經(jīng)過領(lǐng)域?qū)＜胰藱C(jī)交互驗(yàn)證后可以輸出正確的三元組集合。對于置信度較低的三元組，領(lǐng)域?qū)＜乙揽孔陨淼膶I(yè)知識來決定三元組是否正確。領(lǐng)域?qū)＜胰藱C(jī)交互驗(yàn)證的形式化定義如下：

本節(jié)提出的增強(qiáng)驗(yàn)證包含多源數(shù)據(jù)采集與清洗、多源關(guān)系驗(yàn)證、領(lǐng)域?qū)＜胰藱C(jī)交互驗(yàn)證三部分。增強(qiáng)驗(yàn)證模塊能夠有效地驗(yàn)證基礎(chǔ)驗(yàn)證輸出的三元組集合，形成更加正確的三元組集合。

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

本文的實(shí)驗(yàn)環(huán)境是在一臺小型服務(wù)器上運(yùn)行，處理器為Intel?Xeon?Silver 4114 CPU@2.2 GHz，內(nèi)存為100 GB，操作系統(tǒng)為Ubuntu 18.04.1 LTS Server。使用的語言為Java 和Python，Python 主要用于鏈接預(yù)測模塊篩選實(shí)體對，Java 主要用于關(guān)系驗(yàn)證模塊驗(yàn)證實(shí)體對的關(guān)系。

實(shí)驗(yàn)數(shù)據(jù)方面，本文采用公開數(shù)據(jù)集Freebase 和DBpedia。Freebase 數(shù)據(jù)集和DBpedia 是在知識圖譜領(lǐng)域常用的數(shù)據(jù)集，被許多科研學(xué)者采用。由于Freebase 數(shù)據(jù)集和DBpea 數(shù)據(jù)集非常龐大，為了方便起見，本文對Freebase 數(shù)據(jù)pedia 數(shù)據(jù)集進(jìn)行了采樣，選取了一定數(shù)量的實(shí)體、關(guān)系作為實(shí)驗(yàn)的真值數(shù)據(jù)集。真值數(shù)據(jù)集如表1 所示。

Table 1 Truth dataset表1 真值數(shù)據(jù)集

從真值數(shù)據(jù)集隨機(jī)采樣55%、60%、65%、70%、75%、80%、85%、85%、90%、95%的三元組，構(gòu)成本文的缺失知識圖譜。剩余的三元組作為需要補(bǔ)全完善的缺失值。

6.1 鏈接預(yù)測實(shí)驗(yàn)結(jié)果

在鏈接預(yù)測模塊中，測試了Rooted PageRank（RPR）算法和ELP 算法篩選缺失的知識圖譜中最有可能形成鏈接的前1 000 和前2 000 對實(shí)體對，并將篩選出的實(shí)體對和真值數(shù)據(jù)集進(jìn)行比較，計(jì)算出正確預(yù)測的實(shí)體對百分比。篩選前1 000 對實(shí)體對和前2 000 對實(shí)體對的結(jié)果如表2 所示。圖8 和圖9 表現(xiàn)了在DBpedia 數(shù)據(jù)集上和Freebase 數(shù)據(jù)集上的實(shí)驗(yàn)對比。

從圖8 和圖9 中分析發(fā)現(xiàn)在DBpedia 和Freebase兩個數(shù)據(jù)集上，ELP 算法效果均好于RPR 算法。對于前2 000 對實(shí)體對，應(yīng)用了CommonNeighbours、Katz、SimRank 算法[19]進(jìn)行對比測試。實(shí)驗(yàn)結(jié)果如表3 所示。可以看到在DBpedia 和Freebase 數(shù)據(jù)集上，ELP 算法效果均優(yōu)于其他算法。這兩個實(shí)驗(yàn)證明了本文提出的ELP 算法的有效性，說明本文算法相較于其他算法而言，能較為準(zhǔn)確地篩選知識圖譜中最有可能形成鏈接的前k對實(shí)體對。

ELP 算法不僅能夠很好地進(jìn)行鏈接預(yù)測，還具有主動學(xué)習(xí)能力，隨著知識圖譜的不斷完善，ELP 算法能夠更好地預(yù)測知識圖譜中需要進(jìn)行鏈接的實(shí)體對。然而由于知識圖譜越來越完善的同時，需要補(bǔ)全的正確三元組越來越少，用前k對實(shí)體對中正確的實(shí)體對百分比來評價鏈接預(yù)測的主動學(xué)習(xí)能力并不公平。定義了如下函數(shù)來評價在知識圖譜更新過程中算法的鏈接預(yù)測能力。

Table 2 Accuracy comparison of RPR and ELP表2 RPR 與ELP 準(zhǔn)確率對比

Fig.8 Experiment comparison between RPR and ELP in DBpedia圖8 DBpedia 數(shù)據(jù)集RPR 與ELP 實(shí)驗(yàn)對比

Fig.9 Experiment comparison between RPR and ELP in Freebase圖9 Freebase數(shù)據(jù)集RPR 與ELP 實(shí)驗(yàn)對比

Table 3 Accuracy comparison of ELP algorithm and others@2 000表3 ELP 算法與其他算法準(zhǔn)確率對比結(jié)果@2 000

其中，Dt表示當(dāng)前知識圖譜剩余還未補(bǔ)全的正確實(shí)體對總數(shù)，hit代表鏈接預(yù)測器篩選出的前k對實(shí)體對中正確的實(shí)體對個數(shù)。相比較于前k對實(shí)體對中正確實(shí)體對的百分比，Yscore考慮了知識圖譜中剩余還未補(bǔ)全的實(shí)體對總數(shù)，能較好地評價算法的主動學(xué)習(xí)的能力。本文在DBpedia 數(shù)據(jù)集和Freebase 數(shù)據(jù)集上測試了各個算法的實(shí)驗(yàn)結(jié)果，如表4 所示。通過圖10 和圖11 可以看出，隨著知識圖譜的不斷完善，Yscore結(jié)果變得越來越高。這說明了隨著知識圖譜的不斷完善，ELP 算法的鏈接預(yù)測能力越來越強(qiáng)。因此，ELP 算法具有主動學(xué)習(xí)能力。

以上的實(shí)驗(yàn)以及分析驗(yàn)證了如下兩點(diǎn)：（1）本文提出的ELP 算法能夠挖掘知識圖譜中的圖結(jié)構(gòu)信息和語義信息，效果好于Rooted PageRank 算法。（2）本文提出的ELP 算法具有主動學(xué)習(xí)能力，隨著知識圖譜的完善程度越高，ELP 算法的信息挖掘能力越強(qiáng)。

6.2 關(guān)系驗(yàn)證實(shí)驗(yàn)結(jié)果

關(guān)系驗(yàn)證模塊采用TransH 模型對鏈接預(yù)測模塊輸出的候選實(shí)體對進(jìn)行關(guān)系驗(yàn)證。首先對ELP 算法鏈接預(yù)測得到的前k對實(shí)體對進(jìn)行關(guān)系擴(kuò)展，對于鏈接預(yù)測輸出中的正確的實(shí)體對，需要擴(kuò)展正確的關(guān)系；對于鏈接預(yù)測輸出中的錯誤的實(shí)體對，則隨機(jī)擴(kuò)展知識圖譜中的任一關(guān)系。

對于鏈接預(yù)測模塊輸出的前1 000 對實(shí)體對和前2 000 對實(shí)體對，基礎(chǔ)驗(yàn)證模塊采用TransH 模型進(jìn)行二分類?；A(chǔ)驗(yàn)證模塊將預(yù)測的結(jié)果和真值數(shù)據(jù)集進(jìn)行比較，并計(jì)算F1值。F1值的計(jì)算方式如下:

其中，P代表精確率，R代表召回率。F1指標(biāo)能較好地衡量二分類分類器的性能。關(guān)系驗(yàn)證的結(jié)果如表5 所示。

Table 4 Yscore results of active learning in link prediction module表4 鏈接預(yù)測模塊主動學(xué)習(xí)Yscore 結(jié)果

Fig.10 Yscore results of ELP algorithm in DBpedia圖10 DBpedia 數(shù)據(jù)集ELP 算法Yscore 結(jié)果

Fig.11 Yscore results of ELP algorithm in Freebase圖11 Freebase數(shù)據(jù)集ELP 算法Yscore 結(jié)果圖

Table 5 F1 results of relationship verification表5 關(guān)系驗(yàn)證F1 指標(biāo)實(shí)驗(yàn)結(jié)果

表5 證明了基礎(chǔ)驗(yàn)證模塊能夠較好地驗(yàn)證鏈接預(yù)測輸出的實(shí)體對之間的關(guān)系，基礎(chǔ)驗(yàn)證模塊的F1指標(biāo)都集中在0.5～0.8 之間。

爬取Freebase 有關(guān)的實(shí)體75 043 個，以及它們有關(guān)聯(lián)的三元組集合。然后以0.25 的概率采樣其中的三元組集合，構(gòu)建了5 個與Freebase 有關(guān)的多源數(shù)據(jù)倉庫。同樣地，爬取了與DBpedia 有關(guān)的實(shí)體14 656個，以及與它們有關(guān)聯(lián)的三元組集合。然后以0.3 的概率采樣其中的三元組集合，構(gòu)建了5 個與DBpedia有關(guān)的多源數(shù)據(jù)倉庫。基礎(chǔ)驗(yàn)證標(biāo)記為正確的三元組將作為多源數(shù)據(jù)關(guān)系驗(yàn)證的輸入，計(jì)算對應(yīng)的F1指標(biāo)，結(jié)果如表6 所示。從實(shí)驗(yàn)結(jié)果可以看出采用較為正確的數(shù)據(jù)源進(jìn)行多源關(guān)系驗(yàn)證，能得到較好的效果。

對于多源關(guān)系驗(yàn)證中置信度較低的三元組，增強(qiáng)驗(yàn)證模塊采用領(lǐng)域?qū)＜胰藱C(jī)驗(yàn)證進(jìn)一步確定三元組關(guān)系，可以得到正確的三元組。經(jīng)過增強(qiáng)驗(yàn)證后的三元組較為正確，最后采用正確的三元組更新知識圖譜。

6.3 各環(huán)節(jié)時間實(shí)驗(yàn)結(jié)果

本文測試了本文提出的基于主動學(xué)習(xí)的知識圖譜補(bǔ)全框架的各個環(huán)節(jié)的時間消耗?？蚣馨膫€環(huán)節(jié)：（1）實(shí)體聚類算法；（2）RPR 算法；（3）ELP 算法；（4）TransH 模型訓(xùn)練。結(jié)果如表7 所示，從表7 中可以看出主要時間開銷在關(guān)系驗(yàn)證模塊中，鏈接預(yù)測模塊的時間開銷相對不高。而本文提出的對于知識圖譜實(shí)體聚類方法的時間開銷相對于RPR 算法要小很多。總的ELP 算法的時間開銷相對占比不大。

7 結(jié)論

本文提出了一種基于主動學(xué)習(xí)的知識圖譜補(bǔ)全框架來實(shí)現(xiàn)對缺失知識圖譜的不斷更新完善。知識圖譜補(bǔ)全框架由不斷更新的知識圖譜、鏈接預(yù)測模塊、關(guān)系驗(yàn)證模塊構(gòu)成。在鏈接預(yù)測模塊中，提出的ELP 算法充分考慮了知識圖譜中的語義信息和圖結(jié)構(gòu)信息，能準(zhǔn)確實(shí)現(xiàn)對知識圖譜的鏈接預(yù)測，同時ELP 算法具有主動學(xué)習(xí)能力，能隨著知識圖譜的不斷完善，可以更好地進(jìn)行鏈接預(yù)測。在實(shí)驗(yàn)中，通過與前人的RPR、SimRank、CommonNeighbours、Katz 等方法進(jìn)行對比，證明了ELP 算法的有效性。同時，也通過實(shí)驗(yàn)證明了ELP 算法的主動學(xué)習(xí)能力。關(guān)系驗(yàn)證模塊采用基礎(chǔ)驗(yàn)證和增強(qiáng)驗(yàn)證相結(jié)合的方法進(jìn)行關(guān)系驗(yàn)證，這種關(guān)系驗(yàn)證方式能夠結(jié)合知識圖譜內(nèi)部數(shù)據(jù)和互聯(lián)網(wǎng)結(jié)構(gòu)化數(shù)據(jù)，以及領(lǐng)域?qū)＜胰藱C(jī)交互標(biāo)注，能夠驗(yàn)證三元組的正確性。通過實(shí)驗(yàn)驗(yàn)證了關(guān)系驗(yàn)證模塊的有效性。關(guān)系驗(yàn)證模塊能驗(yàn)證鏈接預(yù)測模塊輸出的實(shí)體對之間的關(guān)系，形成正確的三元組，從而更新知識圖譜。

Table 6 F1 results of multi-source data relationship verification表6 多源數(shù)據(jù)關(guān)系驗(yàn)證F1 實(shí)驗(yàn)結(jié)果

Table 7 Time comparison of each step表7 各環(huán)節(jié)時間對比