基于半邊原理的知識圖譜補全

程 濤,陳 恒,2,李冠宇

(1.大連海事大學 信息科學技術(shù)學院,遼寧 大連 116026; 2.大連外國語大學 語言智能研究中心,遼寧 大連 116044)

0 概述

在知識圖譜中,知識表示為三元組<頭實體,關(guān)系,尾實體>(即RDF三元組)的形式,使得知識能夠得到結(jié)構(gòu)化處理[1]。人們必須為知識圖譜應(yīng)用設(shè)計各種基于圖形的方法,然而知識圖譜中的知識不能作為完備的知識,尤其是在大規(guī)模知識圖譜上下文中,需要不斷補充其中的實體關(guān)系進行知識圖譜補全[2]。同時,現(xiàn)有的知識圖譜均以三元組的形式表示知識,這限定了知識必須包含頭實體、關(guān)系和尾實體三部分,但實際上三元組并不是適合所有知識的表示方式。例如管理員想查找某學生的導師A的博士論文,但是已有知識庫中并沒有導師A的博士論文,必須得到一個不完全的三元組,要補全這個三元組,必須補充知識庫。按照知識圖譜的規(guī)則,這個不完全三元組無法加入現(xiàn)有的知識圖譜,只能在以后通過擴充知識庫的方式來補全成完整的三元組后加入。因此,研究保存不完全三元組的方法,實現(xiàn)知識圖譜的動態(tài)補全,是一個具有研究意義的問題。

RDF三元組中關(guān)系本身的特性會對頭尾實體進行限制。例如句子“Lennon was murdered by Champan outside the Dakota on Dec.8.1980”中蘊含的三元組為,其中關(guān)系“kill”決定了頭尾實體都屬于“人”這類實體,屬于地理位置這類的實體“Dakota”則可以被排除。

在多數(shù)知識圖譜中,關(guān)于實體有簡明的描述[3],這些豐富的語義信息對實體非常重要。以FreeBase中的三元組(William Shakespare,book/author/works_written,Romeo and Juliet)為例,頭實體“William Shakespare”含有描述“William Shakespare was an English poet,playwright,and actor…”,尾實體“Romeo and Juliet”含有描述“Romeo and Juliet is a tragedy written by William Shakespare early in his career…”,這些描述對三元組的補全具有重要作用。

本文提出一個運用實體描述的知識圖譜補全方法,即基于半邊的多層卷積模型(Half-edged based Multilayer Convolution Model,HMCM)。該模型利用實體描述和關(guān)系自身可以對實體類別進行限制的特性組成半邊，以保存缺失頭實體或尾實體的不完全三元組。在此基礎(chǔ)上,通過將對應(yīng)類別的半邊相結(jié)合，減少輸入三元組的數(shù)量，再把候選的不完全三元組代入卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network,CNN)進行知識圖譜補全。

1 相關(guān)工作

1.1 知識圖譜補全

針對知識圖譜補全問題,研究者提出了較多的方法[4-6],如基于結(jié)構(gòu)與文本聯(lián)合表示的知識圖譜補全方法[4]和基于雙層隨機游走的關(guān)系推理算法[6]等。學習知識嵌入的代表模型有距離模型、單層神經(jīng)網(wǎng)絡(luò)模型、能量模型、雙線性模型、矩陣分解模型和翻譯模型等[7]。張量神經(jīng)網(wǎng)絡(luò)模型[8]和基于文檔特征的向量空間模型[9]在現(xiàn)有模型中加入多層神經(jīng)網(wǎng)絡(luò)來進行知識圖譜的補全。文獻[10-11]通過類比實驗發(fā)現(xiàn),詞向量空間的平移不變現(xiàn)象普遍存在于詞匯的語義關(guān)系和句法關(guān)系中。對此,文獻[12]進一步提出翻譯模型TransE。然而該模型解決一對一關(guān)系的問題效果較好,但無法應(yīng)對一對多、多對一和多對多關(guān)系的問題。文獻[13]提出TransH模型,通過將關(guān)系建模為超平面,并將h和t投影到關(guān)系特定超平面,從而讓實體在不同的關(guān)系中扮演不同的角色,以解決TransE存在的問題。文獻[14]提出的TransR模型在不同的語義空間中模擬實體和關(guān)系,并在學習嵌入時將實體從實體空間映射到關(guān)系空間。文獻[15]則提出一種基于多步關(guān)系路徑的表示學習模型PTransE。文獻[16]提出的DSKG模型利用循環(huán)神經(jīng)網(wǎng)絡(luò)實現(xiàn)了知識圖譜的補全和實體預(yù)測。文獻[17]提出的DKRL模型用CBOW和卷積神經(jīng)網(wǎng)絡(luò)把實體的描述運用到三元組的補全中。文獻[18]提出的ProjE模型關(guān)注實體與關(guān)系之間的聯(lián)系,不需要預(yù)訓練,參數(shù)規(guī)模小,并且預(yù)測能力強。文獻[19]提出的ConMask模型先以計算實體和關(guān)系語義相似度的方法對錯誤的三元組進行屏蔽,再進行補全工作,大幅減少了訓練時間。

1.2 半邊圖

文獻[20]介紹了半邊原理及其在知識圖譜中的應(yīng)用。該文指出半邊是一個基本概念,其將資源視為頂點和資源屬性信息表示為半邊,不同頂點的半邊依據(jù)可結(jié)合性而結(jié)合成為邊,表示資源屬性之間的關(guān)聯(lián)關(guān)系。此后,文獻[21-22]介紹了半邊在本體和因子圖中的應(yīng)用,文獻[23]則證明了半邊圖在大規(guī)模圖形數(shù)據(jù)庫相似性搜索和高性能查詢處理方面的優(yōu)勢。

2 基于半邊的多層卷積模型

本文提出基于半邊的多層卷積模型HMCM。該模型通過使用實體和關(guān)系約束組成兩種半邊,并根據(jù)結(jié)合規(guī)則使之相互結(jié)合,得到候選三元組集。對于需要補全的缺失三元組,在候選三元組集中查找對應(yīng)的候選三元組代入CNN進行補全。本文模型的整體結(jié)構(gòu)如圖1所示,其利用兩個兩層的卷積神經(jīng)網(wǎng)絡(luò),分別對頭實體的描述和尾實體的描述進行訓練。在此基礎(chǔ)上,將訓練得到的實體描述表示與實體結(jié)構(gòu)表示相結(jié)合,使用TransE模型進行實體和關(guān)系的補全。

圖1 HMCM模型結(jié)構(gòu)Fig.1 HMCM model structure

2.1 半邊的定義

以圖的頂點表示實體,以邊表示關(guān)系,是知識表示的常用方法。這種方法將頂點和邊作為不可分割的原子概念。半邊即是針對這一問題提出的概念,其定義[17]如下:

定義1(半邊) 半邊是描述資源屬性的概念,資源有若干屬性,對應(yīng)于一個頂點有若干個半邊。半邊具有以下特點:

1)一個半邊屬于某個頂點,且分為不同的半邊類型。半邊類型由資源特征屬性決定。

2)半邊之間相互獨立,即屬性之間相互獨立,但半邊與其他的半邊可以相互結(jié)合。資源特征屬性之間的關(guān)聯(lián)關(guān)系,表示何種類型的兩個半邊可以結(jié)合,稱為半邊結(jié)合類型。

3)每個半邊有一個數(shù)值性度量值,稱為半邊權(quán)值,一般取大于0的實數(shù),與資源屬性的載荷情況成反比,即半邊權(quán)值越大,資源屬性的載荷越小。

圖2展示了常見半邊的形態(tài)。

圖2 半邊示意圖Fig.2 Schematic diagram of half-edge

參考半邊的定義,結(jié)合知識圖譜中三元組的特性,HMCM所使用的三元組半邊定義如下:

定義2(三元組半邊) 三元組半邊為知識圖譜補全所使用的特殊半邊,分為頭結(jié)點半邊和尾結(jié)點半邊兩種,每個頂點均只有一個半邊與其相連。三元組半邊符號定義如下:

1)頭結(jié)點半邊HE1={Hh,Rh,csm}。其中:Hh={h,Wh}代表頂點,由三元組中的頭實體h和該實體的描述Wh組成;Rh={r,rs}代表與頂點相連的半邊,由三元組中的關(guān)系r和該關(guān)系所連接的頭尾結(jié)點類別rs組成;csm為實體描述與關(guān)系的相似度得分。

2)尾結(jié)點半邊HE2={Tt,Rh,csm}。其中:Tt={t,Wt}代表頂點,由三元組中的尾實體t和該實體的描述Wt組成;Rh與csm定義與頭結(jié)點半邊中相同。

使用上述兩種半邊,即可得到HMCM所使用的半邊集HE={HE1,HE2}。

2.2 半邊的實現(xiàn)與結(jié)合

2.2.1 半邊的實現(xiàn)

定義實體類別S={s1,s2,…,sn},其中每個實體h(或t)都有自己的類別{si,si+1,…,sj},或是人,或是位置等。對關(guān)系r追加候選實體類別rs={sh,st},其中,sh是關(guān)系r所連接的頭實體類別,st是其尾實體類別。例如關(guān)系father的候選實體類rs={s1,s1},s1為生物類的實體集,這可以解釋為生物的父親一定是生物。因此,那些邏輯上錯誤的三元組(比如某人的父親是某個地理位置)就可以被過濾掉。

最后處理實體的描述。先從描述文本中刪除所有停用詞,再標記所有短語并將這些短語視為單詞。這些描述單詞的集合定義為Wh=[w1,w2…,wi],即詞向量wi是實體h的一個描述單詞。

通過以上符號可以定義三元組的兩種半邊HE1和HE2,如式(1)和式(2)所示:

HE1={h,r,rs,Wh,csm}

(1)

HE2={t,r,rs,Wt,csm}

(2)

其中,實體h(或t)和該實體的描述Wh(或Wt)為頂點,關(guān)系r為半邊,候選實體類rs和csm為半邊的權(quán)值。csm是實體的描述與關(guān)系相似度得分,其定義如式(3)所示:

(3)

其中,a是大于1的常數(shù),用于緩和求平均值所造成的相似度差距縮小的現(xiàn)象。

2.2.2 半邊的結(jié)合

設(shè)實體集E中的兩個實體h和t,若h∈HE1,t∈HE2,HE1.r=HE2.r,并滿足式(4):

|HE1.csm-HE2.csm|>c

(4)

其中,c為設(shè)定閾值。三元組是一個補全的候選三元組,由此得到候選三元組的集合HRT,如式(5)所示:

(5)

HRT將被用于進行實體和關(guān)系預(yù)測。

2.2.3 實體預(yù)測與關(guān)系預(yù)測

對于實體預(yù)測,即缺失一個頭實體或尾實體的三元組,首先使用其中的實體和關(guān)系組成半邊,在HRT中選擇滿足該半邊的候選三元組,再將這些候選三元組代入HMCM進行補全。

同理,對于關(guān)系預(yù)測,可在HRT中得到同時含有已知頭尾實體的三元組集合,再使用HMCM進行補全。

2.3 卷積神經(jīng)網(wǎng)絡(luò)

卷積神經(jīng)網(wǎng)絡(luò)(CNN)是一種廣泛應(yīng)用于圖像的高效模型,其對某些自然語言處理任務(wù)和關(guān)系分類任務(wù)非常有效[17]。同時,CNN也可以用于關(guān)系分類任務(wù)[24-25]。鑒于實體描述詞匯量大、信息環(huán)境復(fù)雜、推理規(guī)則不明確等特點,本文模型需要一個具有良好的容錯能力且并行處理能力和自學習能力、運行速度快、自適應(yīng)能力強的模型來進行訓練,而卷積神經(jīng)網(wǎng)絡(luò)正符合此需求。

參考DKRL模型,HMCM使用兩層的卷積神經(jīng)網(wǎng)絡(luò),第1層池化層為max-pooling層,第2層池化層為mean-pooling層,具體描述如下:

在卷積層中,設(shè)Zi為第i個卷積層的輸出,Xi為第i個卷積層的輸入,大小為k的卷積窗滑過Xi中的輸入向量以得到Xi(k)。在第1個卷積層中,X1是實體的描述向量(x0,x1,…,xn)。因此,卷積層的第i層輸出向量如式(6)所示:

Zi=σ(WiXi+bi)

(6)

模型的第1層輸入為頭實體和尾實體對應(yīng)的描述單詞集Wh和Wt,即X1=Wh(或X1=Wt)。

卷積層之后使用池化層來縮小CNN的參數(shù)空間和濾波器噪聲。卷積層的輸出向量被分成多個大小為nL的非重疊窗口。對于第1層池化層,選取每個窗口的最大值以構(gòu)成新的向量。nL-max-pooling得到nL大小的窗口內(nèi)輸入向量中最大的特征值,如式(7)所示:

X2=max(ZnL×i,ZnL×(i+1),…,ZnL×(i+1)-1)

(7)

nL-max-pooling可以縮小nL次特征表示的大小,降低CNN編碼器的復(fù)雜性和參數(shù)學習的成本。然而,一些描述非常復(fù)雜,不同的句子可能表示信息的不同方面,僅使用max-pooling會導致大量的信息丟失。對此,第2個池化層使用mean-pooling以減少信息丟失,使所有包含不同本地信息的輸入向量都能對最終實體嵌入有貢獻,并可以在反向傳播期間進行更新,所得特征值如式(8)所示:

(8)

最終結(jié)果通過一層全連接神經(jīng)網(wǎng)絡(luò)與第2層池化層相連,輸出結(jié)果為與實體結(jié)構(gòu)向量同維的向量,記為實體的描述向量。

使用卷積神經(jīng)網(wǎng)絡(luò)訓練得到的實體描述表示與實體結(jié)構(gòu)表示組合形成最終的實體表示hc、tc。基于描述的實體表示記為hd、td,基于結(jié)構(gòu)的實體記為hs、ts,則hc和tc的計算公式如式(9)和式(10)所示:

(9)

(10)

最后使用TransE模型進行實體和關(guān)系預(yù)測,如式(11)所示:

(11)

由于已經(jīng)使用半邊篩選了實體的類別,此處實體的輸入量僅為某個類中實體的數(shù)量,因此可縮短運行時間。

2.4 損失函數(shù)

選擇TransE的損失函數(shù)作為訓練目標,如式(12)所示:

|h′c+r-t′c|,0}

(12)

在式(12)中,γ是邊際超參數(shù),γ>0,T′是訓練集T的負例的集合,如式(13)所示:

T′={(h′,r,t)|h′∈E∪(h,r′,t)|r′∈

R∪(h,r,t′)|t′∈E}

(13)

T′為三元組中頭實體、尾實體或關(guān)系被另一個實體或關(guān)系隨機替換所組成的錯誤三元組集。如果三元組已經(jīng)在T中,則不會將其視為負樣本。由于h和t有兩種表示(基于結(jié)構(gòu)的表示和基于描述的表示),因此在基于邊距的得分函數(shù)中,實體的表示是基于結(jié)構(gòu)表示和基于描述表示的平均值。

2.5 算法描述

HMCM算法偽代碼如下:

算法1HMCM算法

輸入三元組T={(h,r,t)},每個實體對應(yīng)的描述Wh

for e in E://在實體和關(guān)系之間組合,形成半邊

for r in R:

if (e.s==rs.sh):

csm=a*(Wh*r)/(||Wh||*||r||);HE1.append(h,r,csm)

if (e.s==rs.st):

csm=a*(Wt*r)/(||Wt||*||r||);HE2.append(t,r,csm)

else:continue

for i in HE1://按照結(jié)合規(guī)則進行半邊的結(jié)合,利用c//進行篩選

for j in HE2:

if(|i.csm-j.csm|>c):HRT.append()

for in HRT://實體描述代入CNN得到最終//的實體向量

hd=Wh→CNN;hc=(hs+hd)/2

td=Wt→CNN;tc=(ts+td)/2

(hc,r,tc)→TransE//最終結(jié)果代入TransE模型

3 實驗與結(jié)果分析

本文實驗的數(shù)據(jù)集使用FB15K和WN18,這兩個數(shù)據(jù)集均是從典型的大型知識庫中提取的數(shù)據(jù)集,可用于評估知識圖譜補全模型。為確認每個實體都能進行基于描述表示學習的訓練,從數(shù)據(jù)集中刪除了部分實體和包含這些實體的所有三元組。處理后的FB15K和WN18數(shù)據(jù)集的數(shù)據(jù)分布如表1所示。其中:FB15K訓練集有472 860個三元組、14 904個實體和1 341個關(guān)系,測試集有57 303個三元組;WN18中訓練集有140 229個三元組、39 852個實體和18個關(guān)系,測試集有49 276個三元組。

表1 FB15K和WN18的數(shù)據(jù)分布Table 1 Data distribution of FB15K and WN18

訓練模型采用多次實驗來尋找最佳的參數(shù)設(shè)置,其中,實體和關(guān)系維度n分別為50、80和100,學習率λ分別為0.000 5、0.001 0和0.002 0,邊緣參數(shù)γ分別為0.5、1.0、1.5和2.0。第1個池化層使用4-max-pooling。

使用正確實體的平均等級和排在前10名(實體)或第1名(關(guān)系)的正確率這兩種指標對模型性能進行評價,同時參照文獻[13],遵循Raw和Filter 2個評估標準并對比CBOW模型和CNN模型,得到實體預(yù)測和關(guān)系預(yù)測的比較結(jié)果,如表2和表3所示,表中數(shù)據(jù)均以FB15K/WN18的形式列出。

表2 實體預(yù)測結(jié)果對比Table 2 Comparison of entity prediction results

表3 關(guān)系預(yù)測結(jié)果對比Table 3 Comparison of relation prediction results

可以看出,HMCM與DKRL(CNN)+TransE在平均等級和Hits@10上顯著優(yōu)于TransE和CBOW。在實體預(yù)測方面,HMCM略優(yōu)于DKRL,而在關(guān)系預(yù)測方面,DKRL模型相對占優(yōu)。這表明在基于結(jié)構(gòu)補全方面,HMCM與DKRL都沒有優(yōu)于TransE。這是由于TransE在結(jié)構(gòu)補全方面較為優(yōu)秀,而DKRL和HMCM都是在TransE的基礎(chǔ)上進行優(yōu)化,并沒有對其進行較大改進,因此,相比之下優(yōu)勢并沒有非常大,但相較于DKRL,HMCM對實體和關(guān)系的組合進行了一定限制,提高了精確度,因此,在實體預(yù)測方面HMCM更占優(yōu)。而對于關(guān)系預(yù)測,HMCM對結(jié)構(gòu)與描述做了平均處理,削弱了關(guān)系描述中隱藏的語義對于關(guān)系預(yù)測的作用,導致預(yù)測關(guān)系的能力變?nèi)?。同時由于在半邊的結(jié)合規(guī)則中,關(guān)系是非常重要的一環(huán),缺失關(guān)系對半邊的結(jié)合精確度有所影響,因此HMCM的預(yù)測能力與DKRL相差無幾。為對此進行改進,后續(xù)將從實體的描述中發(fā)掘頭尾實體之間的聯(lián)系來加強關(guān)系預(yù)測的能力,彌補其不足。

從訓練集中選取100 000個數(shù)據(jù)對DKRL和HMCM分別進行測試,記錄模型運行時間,如圖3所示?？梢钥闯?當數(shù)據(jù)量較少時,HMCM的效率略低于DKRL,而隨著數(shù)據(jù)量不斷增長,HMCM的運行效率逐漸比DKRL高。這是因為HMCM將三元組的范圍擴展為半邊,這雖然能發(fā)現(xiàn)潛在語義關(guān)系,但也一定程度上擴大了搜索范圍,因此,當數(shù)據(jù)量較少時,其補全效率比DKRL略低,而隨著數(shù)據(jù)量的增長,HMCM中半邊的作用逐漸體現(xiàn),數(shù)據(jù)過濾效果逐漸增強,因此,運行時間也較DKRL越來越少。

圖3 DKRL模型與HMCM模型的運行時間對比Fig.3 Comparison of running time by DKRL model and HMCM model

此外,HMCM把不完全的三元組以半邊的形式加以暫存,這讓只能通過補充知識庫才能進行補全的三元組在后續(xù)補全工作中可以使用現(xiàn)有的半邊來加快補全進程,避免了不必要且重復(fù)的遍歷工作,從而實現(xiàn)知識圖譜的動態(tài)補全。

4 結(jié)束語

本文提出HMCM模型,通過引入半邊優(yōu)化具有實體描述的知識圖譜學習,使用深度卷積神經(jīng)網(wǎng)絡(luò)提取實體描述的語義,并將描述與結(jié)構(gòu)相結(jié)合進行知識圖譜補全。實驗結(jié)果表明,該模型在實體預(yù)測和關(guān)系預(yù)測中均能達到預(yù)期目標,并且在知識圖譜的動態(tài)補全方面具有優(yōu)勢。但HMCM模型僅考慮表示學習的實體描述,而未將其他類型的文本信息運用到模型中。此外,模型中雖然引入了半邊來提高補全的精度,但是人工標記關(guān)系和實體分類依然耗時耗力。針對以上不足,下一步將對模型進行優(yōu)化,完成實體的自動分類,同時對關(guān)系的約束進行定義,進一步探索時變半邊圖與知識圖譜結(jié)合的方法。