融合決策蘊(yùn)涵的知識圖譜推理方法

翟巖慧，何 煦，李德玉,2，張 超,2

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

形式概念分析（formal concept analysis，F(xiàn)CA）是進(jìn)行數(shù)據(jù)分析和規(guī)則提取的強(qiáng)有力工具[1-2]。其中，形式概念分析對知識獲取的研究就是對蘊(yùn)涵的研究。由于形式背景中得到的蘊(yùn)涵數(shù)量過于龐大，Qu等[3]提出了決策蘊(yùn)涵。研究者[4-6]從邏輯角度對決策蘊(yùn)涵進(jìn)行描述，給出了決策蘊(yùn)涵的語義結(jié)論和語構(gòu)結(jié)論，比較了決策蘊(yùn)涵相對于概念規(guī)則和粒規(guī)則[7]的優(yōu)勢[8]。

上述研究目前被廣泛應(yīng)用在文本挖掘[9]、沖突分析[10]、推薦系統(tǒng)[11]、屬性約簡[12-17]及基于概念的認(rèn)知學(xué)習(xí)[18-21]等相關(guān)領(lǐng)域中。隨著對形式概念分析研究[22-23]的深入，發(fā)現(xiàn)它在基于知識圖譜的關(guān)系補(bǔ)全推理上也有一定的應(yīng)用價(jià)值。

關(guān)系補(bǔ)全是知識圖譜補(bǔ)全的任務(wù)之一[24]，最先進(jìn)的關(guān)系補(bǔ)全方法[25]主要是基于知識嵌入的模型，包括翻譯模型和基于卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）的模型。

早期的翻譯模型是Bordes等人[26]于2013年提出的TransE模型，文獻(xiàn)[26]將知識圖譜中的實(shí)體與關(guān)系映射到低維向量空間中，得到實(shí)體與關(guān)系的向量表示，并使用向量差來進(jìn)行關(guān)系預(yù)測。由于該模型在處理多對一等關(guān)系上存在一定的局限性，一些研究者相繼提出TransH[27]、TransR[28]、TransD[29]等模型來解決該問題。文獻(xiàn)[27-29]提出的超平面空間向量可以很好地支持復(fù)雜關(guān)系預(yù)測，但模型復(fù)雜，參數(shù)也較多。

基于卷積神經(jīng)網(wǎng)絡(luò)的模型是由Dettmers 等人[30]提出的，文獻(xiàn)[30]將卷積引入知識圖譜嵌入（knowledge graph embedding，KGE）中，但只考慮了頭實(shí)體和關(guān)系的卷積。文獻(xiàn)[31]對文獻(xiàn)[30]進(jìn)行改進(jìn)，提出將三元組的三個元素都進(jìn)行卷積，由于三元組表現(xiàn)為三列，卷積時三列相同維度被一起提取特征。

上述知識嵌入模型都繼承了表示學(xué)習(xí)[32-33]的強(qiáng)大能力，在關(guān)系預(yù)測任務(wù)中表現(xiàn)優(yōu)異。然而，這些知識圖譜嵌入模型都獨(dú)立地處理三元組，無法封裝知識圖譜中給定實(shí)體附近固有或潛在的關(guān)系，較少關(guān)注知識圖譜的網(wǎng)狀結(jié)構(gòu)和三元組之間的邏輯關(guān)系，存在可解釋性弱等問題。

本文從形式概念分析角度解決關(guān)系推理預(yù)測問題。首先，從理論上證明基于形式概念分析的蘊(yùn)涵及決策蘊(yùn)涵可以表示知識推理中相應(yīng)的規(guī)則。其次，為了快速挖掘決策蘊(yùn)涵，對復(fù)雜背景不斷約簡，并證明約簡后的背景可以挖掘到與原背景等價(jià)的決策蘊(yùn)涵。最后，以具體示例和實(shí)驗(yàn)驗(yàn)證了該方法的可行性。

相比知識嵌入模型，基于蘊(yùn)涵及決策蘊(yùn)涵的關(guān)系補(bǔ)全方法不僅可以在構(gòu)建背景的過程中引入先驗(yàn)知識輔助推理，而且注重不同三元組之間的關(guān)聯(lián)關(guān)系，不需要把實(shí)體關(guān)系向量化后進(jìn)行推理，有良好的可解釋性。

1 知識圖譜基本概念

知識圖譜是結(jié)構(gòu)化的語義知識庫，以符號形式描述物理世界的概念及相互聯(lián)系；其基本組成單位是（實(shí)體，關(guān)系，實(shí)體）三元組，也稱為知識或事實(shí)。

定義1[34]知識圖譜為二元組G=(E,R)，其中E為實(shí)體集合，R為E上的關(guān)系集合。對于r∈R，(x,y)∈r稱為事實(shí)，記為(x,r,y)，x和y分別稱為該事實(shí)的頭實(shí)體和尾實(shí)體。

目前存在的知識圖譜都存在一定的不完整性。例如，在Freebase[35]中，三百萬人物實(shí)體中大約75%都遺漏了國籍信息，僅有4%的人物實(shí)體有兄弟姊妹信息，僅32%的人物實(shí)體有職業(yè)信息。在Dbpedia[35]中，有60%的人物實(shí)體沒有出生地信息。

知識推理就是為了補(bǔ)全缺失的實(shí)體和關(guān)系?；诜柕囊?guī)則推理常考慮兩種規(guī)則[34]：一對一關(guān)聯(lián)規(guī)則和N對一關(guān)聯(lián)規(guī)則（目前只考慮N=2）。

定義2[34]令G=(E,R)為知識圖譜，ri,rj∈R，稱ri和rj具有ri→rj關(guān)系，若

本文將G 中的ri→rj關(guān)系稱為1→1型關(guān)系。

定義3[34]令G=(E,R)為知識圖譜，rj,rk∈R，稱rj和rk具有rj?rk關(guān)系，若

本文將G 中的rj?rk關(guān)系稱為1?1型關(guān)系。

例1給定3個關(guān)系capital、belong_to、contains，其中(x,capital,y)表示x是y的首都，(x,belong_to,y)表示x屬于y，(y,contains,x)表示y包含x。因?yàn)?x,y∈E:(x,capital,y)?(x,belong_to,y)，所以capital和belong_to有capital→belong_to關(guān)系。又因?yàn)?x,y∈E:(x,belong_to,y)?(y,contains,x)，所以belong_to和contains有belong_to?contains關(guān)系。

定義4[34]令G=(E,R)為知識圖譜，ri,rj,rk∈R，稱ri和rj與rk具有rirj→rk關(guān)系，若

定義4表明，如果實(shí)體x和y具有關(guān)系ri且y和z具有關(guān)系rj，則x和z具有關(guān)系rk。本文將G 中的rirj→rk關(guān)系稱為2→1型關(guān)系。

例2給定3 個關(guān)系ri、rj和rk，令ri=place_of_birth，rj=belong_to，rk=nationality，其中，(x,ri,y)表示x出生于y，(y,rj,z)表示y屬于z，(x,rk,z)表示x的國籍是z。因?yàn)?x,y,z∈E:(x,ri,y)∧(y,rj,z)?(x,rk,z)，所以belong_to、place_of_birth和nationality具有rirj→rk關(guān)系。

2 FCA基本概念

本章主要介紹FCA和決策蘊(yùn)涵的一些基本概念和性質(zhì)。

2.1 FCA

定義5[5]形式背景是一個三元組K=(G,M,I),其中G是對象集，M是屬性集，I?G×M是對象和屬性之間的二元關(guān)系。對于g∈G,m∈M,(g,m)∈I表示“對象g具有屬性m”。

定義6[5]設(shè)K=(G,M,I)為形式背景，A,B?M。如果每一個具有屬性集A的對象也同時具有屬性集B，則A→B叫作K的一個蘊(yùn)涵。

定義7[5]設(shè)K為形式背景，對于A?G，記：

為對象集A所共有的屬性集。對于B?M，記：

為具有B中所有屬性的對象集。對于g∈G，為了簡單起見，將{g}I記為gI。

2.2 決策背景上的決策蘊(yùn)涵

定義8[5]決策背景是一個三元組K=(G,C∪D,IC∪ID)，其中，G是對象集，C是條件屬性集，D是決策屬性集，IC?G×C是條件關(guān)聯(lián)關(guān)系，ID?G×D是決策關(guān)聯(lián)關(guān)系。對于g∈G,m∈C∪D,(g,m)∈IC或(g,m)∈ID表示對象g具有屬性m。

由此可見，決策背景由兩個子形式背景構(gòu)成，KC=(G,C,IC)和KD=(G,C,ID)，對于A?C和B?D，符號AIC、BID簡記為AC、BD。

定義9[5]設(shè)K=(G,C∪D,IC∪ID) 是一個決策背景。若A?C且B?D，K上成立的蘊(yùn)涵A→B被稱為K的決策蘊(yùn)涵。此時，A為該決策蘊(yùn)涵的前提，B為該決策蘊(yùn)涵的結(jié)論。

定理1[5]設(shè)K=(G,C∪D,IC∪ID) 是一個決策背景，A?C，B?D，則A→B為K的決策蘊(yùn)涵當(dāng)且僅當(dāng)AC?BD，當(dāng)且僅當(dāng)B?ACD。

3 基于形式概念分析的知識圖譜推理研究

基于規(guī)則的知識推理無論依靠人工構(gòu)建規(guī)則還是采用自適應(yīng)規(guī)則挖掘算法，代價(jià)都非常高。本章研究知識圖譜中1→1 型、1?1 型和2→1 型關(guān)系在形式背景中的蘊(yùn)涵表示和知識推理。

3.1 1→1 型關(guān)系對應(yīng)蘊(yùn)涵

定義10知識圖譜G=(E,R)對應(yīng)的(1,1)型關(guān)系形式背景是一個三元組=(G,M,I)，其中G=E×E，M=R，I滿足對于任意的(x,y)∈G，r∈M，

對于(x,y)∈G,r∈M,(x,y)Ir或者((x,y),r)∈I表示(x,y)具有關(guān)系r。

例3由例1 生成的(1,1)型關(guān)系形式背景如表1所示。

表1 (1,1)型關(guān)系形式背景Table 1 Formal context of (1,1) relationship

表1 (1,1)型關(guān)系形式背景Table 1 Formal context of (1,1) relationship

注：表中x表示相應(yīng)的對象具有相應(yīng)的屬性。

表1中的實(shí)體x和y分別為Beijing和China，屬性ri、rj和rk表示關(guān)系“capital”“belong_to”和“contains”。因?yàn)樵谥R圖譜中有(x,y)∈ri，所以在形式背景中有((x,y),ri)∈I，即((Beijing,China),capital)∈I，同理，((Beijing,China),belong_to)∈I，((China,Beijing),contains)∈I。

定理2令G=(E,R)為一知識圖譜，ri,rj∈R，則ri和rj具有1→1 型關(guān)系當(dāng)且僅當(dāng)ri→rj在中成立。

證明由于ri和rj具有1→1 型關(guān)系，有?x,y∈E:(x,ri,y)?(x,rj,y)，由定義10，上式等價(jià)于?x,y∈E:((x,y),ri)∈I?((x,y),rj)∈I，即有?(x,y)∈G:((x,y),ri)∈I?((x,y),rj)∈I，因此ri→rj。

定理2表明，對知識圖譜中ri→rj關(guān)系的研究可等價(jià)轉(zhuǎn)化為對(1,1)型關(guān)系形式背景上特定蘊(yùn)涵的研究。

結(jié)合定理2可知，例3的實(shí)際意義在于，當(dāng)x和y分別為城市和國家實(shí)體類別時，由(1,1)型關(guān)系形式背景可知，對于任意的(x,y)∈G，若((x,y),ri)∈I，則((x,y),rj)∈I，即若x是y的首都，則x隸屬于y。在知識問答系統(tǒng)中，對于(x,y)∈G，當(dāng)查詢某城市x的隸屬情況時，若只有信息((x,y),ri)∈I，則由定理2可得((x,y),rj)∈I，即在已知首都信息的情況下通過蘊(yùn)涵可推理得到隸屬信息，同時也滿足G 中的1→1 型關(guān)系。

3.2 1?1 型關(guān)系對應(yīng)蘊(yùn)涵

3.3 2→1 型關(guān)系對應(yīng)決策蘊(yùn)涵

知識圖譜中的2→1 型關(guān)系rirj→rk可以補(bǔ)全圖譜中缺失的知識。例如，在開源知識庫Freebase 中，有超過70%的人條目中都沒有國籍相關(guān)信息。如果將rk定義為國籍關(guān)系，并可以從具有國籍信息的知識庫中識別出與國籍信息相關(guān)的ri和rj，則可將識別出的2→1 型關(guān)系rirj→rk應(yīng)用于缺失知識補(bǔ)全。為此，本節(jié)由G 構(gòu)建的(2,1)型關(guān)系形式背景，并將2→1型關(guān)系轉(zhuǎn)換為形式背景中的蘊(yùn)涵。

3.3.1 2→1 型關(guān)系的基本概念

定義12令G=(E,R)為一知識圖譜，G 對應(yīng)的(2,1)型關(guān)系形式背景是一個三元組=(G,M,I)，其中G=E×E×E，M=R×{1,2,3}，I為G和M之間的二元關(guān)系，且滿足對于任意的(x,y,z)∈G，(ri,1),(rj,2),(rk,3)∈M，有：

例4一個(2,1)型關(guān)系形式背景可以用一個二維表表示。從知識圖譜G 中任選3 個關(guān)聯(lián)實(shí)體和3 個關(guān)聯(lián)關(guān)系均可以構(gòu)建一個(2,1)型關(guān)系形式背景，如表2所示。

表2 (2,1)型關(guān)系形式背景Table 2 Formal context of (2,1) relationship

表2 (2,1)型關(guān)系形式背景Table 2 Formal context of (2,1) relationship

注：表中x表示相應(yīng)的對象具有相應(yīng)的屬性。

表3 決策背景Table 3 Decision context

表3 決策背景Table 3 Decision context

注：表中x表示相應(yīng)的對象具有相應(yīng)的屬性。

表4 決策背景Table 4 Decision context

注：表中x表示相應(yīng)的對象具有相應(yīng)的屬性。

下面將知識圖譜中的2→1 型關(guān)系轉(zhuǎn)換為形式背景中的蘊(yùn)涵。

定理4令G=(E,R)為一知識圖譜，ri,rj,rk∈R，則ri和rj與rk具有2→1型關(guān)系當(dāng)且僅當(dāng)(ri,1)(rj,2)→(rk,3)在中成立。

證明由于ri和rj與rk具有2→1型關(guān)系，因此有：

由定義12，上式等價(jià)于：

由定理4 可知，2→1 型關(guān)系成立的充要條件是特定的蘊(yùn)涵在(2,1)型關(guān)系形式背景中成立，因此，只需在中找出相應(yīng)的蘊(yùn)涵即可生成知識圖譜中所有的2→1型關(guān)系。

3.3.2 對象約簡

首先，由定理4可以看出，為了挖掘2→1型關(guān)系對應(yīng)的決策蘊(yùn)涵，可將屬性集M分為兩部分，即條件屬性集C=R×{1,2}和決策屬性集D=R×{3}，而相應(yīng)的蘊(yùn)涵必然具有A→B的形式，其中A?C，B?D。具體來說，可將關(guān)系形式背景=(G,M,I)轉(zhuǎn)化為決策背景=(G,C∪D,IC∪ID)，其中C=R×{1,2}，D=R×{3}，IC?G×C，ID?G×D且IC∪ID=I。

定理5令G=(E,R)為一知識圖譜，ri,rj,rk∈R，則ri和rj與rk具有2→1型關(guān)系當(dāng)且僅當(dāng)(ri,1)(rj,2)→(rk,3)在中成立。

定理7令G=(E,R)為一知識圖譜，ri,rj,rk∈R，則ri和rj與rk具有2→1 型關(guān)系當(dāng)且僅當(dāng)(ri,1)(rj,2)→(rk,3)在中成立。

表5 決策背景Table 5 Decision context

表5 決策背景Table 5 Decision context

注：表中x表示相應(yīng)的對象具有相應(yīng)的屬性。

為簡化2→1型關(guān)系對應(yīng)決策蘊(yùn)涵的生成，本小節(jié)對相應(yīng)的決策背景進(jìn)行了對象約簡。與李金海等[36-37]所提的約簡方法相比：一方面，本小節(jié)所提約簡方法是為了保持決策蘊(yùn)涵即知識的不變性，而文獻(xiàn)[36-37]是為了保存代數(shù)結(jié)構(gòu)的不變性；另一方面，本小節(jié)所提方法進(jìn)行了對象約簡，而文獻(xiàn)[36-37]進(jìn)行了屬性約簡。事實(shí)上，本節(jié)所提約簡方法只能保持2→1 型關(guān)系對應(yīng)決策蘊(yùn)涵，并不是一種通用的約簡方法。

4 實(shí)驗(yàn)和分析

本章通過實(shí)驗(yàn)驗(yàn)證基于形式概念分析的知識圖譜推理方法的可行性和有效性。本文在FB15k-237數(shù)據(jù)集上選取某一關(guān)系作為決策屬性，對知識圖譜中缺失的關(guān)系進(jìn)行補(bǔ)全，并與基于翻譯模型的關(guān)系預(yù)測方法進(jìn)行對比分析。

4.1 數(shù)據(jù)集

本例在FB15k-237數(shù)據(jù)集上進(jìn)行驗(yàn)證，該數(shù)據(jù)集是Freebase的子集。如表6所示，本實(shí)驗(yàn)選用了38 001個元組構(gòu)建該知識圖譜對應(yīng)的決策背景（具體構(gòu)建方法見4.2 節(jié)），并進(jìn)行決策蘊(yùn)涵挖掘，隨后在8 130個元組上測試所得決策蘊(yùn)涵在關(guān)系預(yù)測任務(wù)中的準(zhǔn)確性。其中，訓(xùn)練集含有237個關(guān)系和4 421個人物實(shí)體，測試集含有1個待預(yù)測關(guān)系和4 533個人物實(shí)體。

表6 FB15k-237實(shí)驗(yàn)數(shù)據(jù)Table 6 FB15k-237 experimental data

4.2 決策蘊(yùn)涵挖掘及推理

通常情況下，可以根據(jù)定義12 對訓(xùn)練集中相應(yīng)實(shí)體及其N跳范圍內(nèi)的鄰居關(guān)系和實(shí)體構(gòu)建形式背景，并視其復(fù)雜程度決定是否轉(zhuǎn)化為決策背景。為了減少構(gòu)建決策背景的復(fù)雜度，可以根據(jù)具體的應(yīng)用場景對決策背景進(jìn)行簡化。以Freebase為例，首先可以通過問題分析確定決策屬性，如Freebase 中“nationality”的信息缺失高達(dá)一半，為了補(bǔ)全該信息，以“nationality”作為決策屬性(rk,3)；進(jìn)一步，因?yàn)樾枰评砣宋飳?shí)體的國籍信息，所以可確定人物為頭實(shí)體?；诖耍梢酝ㄟ^以下“直接構(gòu)建法”來建立決策背景。

以人物實(shí)體作為頭實(shí)體h出發(fā)尋找中間實(shí)體e，按照每個實(shí)體平均包含3個關(guān)系，理論上可以找到大約1.4萬個中間實(shí)體e，其對應(yīng)的關(guān)系設(shè)為(ri,1)。再以e為出發(fā)點(diǎn)去尋找尾實(shí)體t，此時分兩種情況進(jìn)行討論：若存在t與之相連，連接關(guān)系記為(rj,2)，對應(yīng)(h,e,t)∈G作為決策背景的對象；若中間實(shí)體e無后續(xù)關(guān)系(rj,2)，也找不到對應(yīng)尾實(shí)體t，該情況符合第3.3.2 小節(jié)中對“可約對象”和“冗余對象”的定義，即有且僅有一個條件屬性時，無論其是否具有決策屬性，該對象都應(yīng)該被約簡，因此可以不考慮該情況。

上述直接構(gòu)建法可以在構(gòu)建過程中對滿足對象約簡定義的對象直接約簡，并對條件屬性1和2加以區(qū)分，在實(shí)現(xiàn)行最簡的同時實(shí)現(xiàn)列最簡，使最終的列規(guī)模僅為原有背景的1/2。

表7 為按照上述方法構(gòu)建的決策背景子圖，其中各屬性的含義為：1.acquire，2.executive_produce，3.education_of，4.artist_of，5.award_of，6.place_lived，7.place_of_birth，8.actor_of，9.nominate，10.nominated_for，11.produced_of，12.currency，13.has student，14.child_of，15.has artist，16.award_winner，17.sports_team_location，18.government，19.category，20.actor，21.film_subject，22.belong_to，23.capital，24.nationality。

表7 FB15k-237子集對應(yīng)的決策背景Table 7 Decision context for subset of FB15k-237

對于生成的決策背景，可以使用算法1生成候選決策蘊(yùn)涵，然后使用算法2生成決策蘊(yùn)涵。

算法1候選決策蘊(yùn)涵生成

算法1根據(jù)決策屬性是否為空將所有的對象（步驟2～26）分為兩個類別（步驟3～14 和步驟16～25）。若該對象k擁有決策屬性（步驟3），則該對象擁有的條件屬性和決策屬性可能建立相應(yīng)的決策蘊(yùn)涵聯(lián)系。為此，將該對象擁有的(ri,1) 類屬性添加到attri[k]，擁有的(rj,2)類屬性添加到attrj[k]。顯然，對于任意的i∈attri[k]和j∈attrj[k]，可生成候選決策蘊(yùn)涵(ri,1)(rj,2)→(rk,3)，因?yàn)閷ο髃擁有條件屬性(ri,1)和(rj,2)的同時也擁有決策屬性(r,3)。為了方便，也可以認(rèn)為對象k可生成決策蘊(yùn)涵集attri[k]×attrj[k]→(r,3)。然而，這樣的候選決策蘊(yùn)涵并不一定成立，還需有不擁有決策蘊(yùn)涵的對象進(jìn)行驗(yàn)證。為此，對于所有不擁有決策蘊(yùn)涵的對象（步驟15），算法1將其擁有的條件屬性和決策屬性分別保存到resti[k]和restj[k]中，然后使用算法2 對候選決策蘊(yùn)涵進(jìn)行排除，以生成最終的決策蘊(yùn)涵。

算法2決策蘊(yùn)涵挖掘

為了減少生成決策蘊(yùn)涵的復(fù)雜度，算法2 首先對算法1 生成的attri、attrj和resti、restj去除重復(fù)（步驟1）；在此過程中，只有attri和attrj均重復(fù)的行才能被去除，類似地，只有resti和restj均重復(fù)的行才能被去除。顯然，這種去除方式相當(dāng)于去除原決策背景中的重復(fù)行，并不會對決策蘊(yùn)涵的生成產(chǎn)生任何影響。

算法2 根據(jù)沒有決策屬性的對象對候選決策蘊(yùn)涵進(jìn)行驗(yàn)證，去除不成立的決策蘊(yùn)涵（步驟2～11）。對于沒有決策屬性的對象s，若其所擁有的(ri,1)類屬性resti[k]和(rj,2)類屬性restj[k]與已生成的候選決策蘊(yùn)涵的交集都不為空（步驟4），這表明交集內(nèi)的候選決策蘊(yùn)涵不成立。例如，對于含有決策屬性的對象l，可生成候選決策蘊(yùn)涵集attri[l]×attrj[l]→(r,3)；此時，對于不含有決策屬性的對象s，可以生成條件屬性集resti[s]和restj[s]，對任意的i∈resti[s]和j∈restj[s]，決策蘊(yùn)涵(ri,1)(rj,2)→(r,3)均不成立；換言之，對象s否認(rèn)決策蘊(yùn)涵集resti[s]×resti[s]→(r,3)的成立性。因此，對象s就可以對對象l生成的候選決策蘊(yùn)涵進(jìn)行修正，去除不成立的候選決策蘊(yùn)涵。此時，記inseti=resti[s]∩attri[l]和insetj=restj[s]∩attrj[l]分別為對象l和對象s在(ri,1)和(rj,2)兩類屬性上的交集，若inseti和insetj均不為空（步驟5），即使resti[s]和restj[s]可以否認(rèn)決策蘊(yùn)涵集resti[s]×restj[s]→(r,3)的成立性，但無法否認(rèn)決策蘊(yùn)涵集attri[l]inseti×attrj[l]→(r,3)和attri[l]×attrj[l]insetj→(r,3)的成立性。因此，步驟7 和步驟8 將這些候選決策蘊(yùn)涵加入到attri和attrj，以便于后續(xù)檢驗(yàn)。容易驗(yàn)證，所有經(jīng)過檢驗(yàn)的決策蘊(yùn)涵均為決策背景上成立的決策蘊(yùn)涵，因此，算法2在步驟9～16生成待挖掘的決策蘊(yùn)涵。

對于表7，通過算法1和算法2可得決策蘊(yùn)涵：

（1）place_of_birth∧belong_to→nationality

（2）place_of_birth∧capital→nationality

由G 轉(zhuǎn)化的決策背景中挖掘到的決策蘊(yùn)涵是進(jìn)行知識補(bǔ)全的依據(jù)。以“nationality”為例，可以從知識圖譜G 中擁有決策蘊(yùn)涵條件屬性的實(shí)體對出發(fā)，選擇與決策蘊(yùn)涵前件匹配的部分進(jìn)行推理。例如，若某個對象同時具有條件屬性“contains”（即belong_to）和“place_of_birth”，則可以為該對象補(bǔ)全相應(yīng)的“nationality”關(guān)系。

在預(yù)測過程中，并非所有的決策蘊(yùn)涵均可預(yù)測得出國家實(shí)體。以決策蘊(yùn)涵place_of_birth∧belong_to→nationality為例，具有“belong_to”屬性的實(shí)體對并非全部具有形式“（國家，城市）”，部分實(shí)體對還包含任意非國家和城市實(shí)體的形式“（大地點(diǎn)，小地點(diǎn)）”。因此，為了進(jìn)一步提高預(yù)測的準(zhǔn)確率，本文限制預(yù)測的尾實(shí)體必須為國家實(shí)體。

4.3 實(shí)驗(yàn)比較

為驗(yàn)證上述方法的有效性，本文與TransE[26]和TransH[27]進(jìn)行了比較。

TransE[26]：文獻(xiàn)[26]提出將多元關(guān)系數(shù)據(jù)的實(shí)體和關(guān)系嵌入到低維向量空間，使用頭尾實(shí)體的向量差預(yù)測關(guān)系。然而，TransE在處理一對多和多對一等特性時效果不佳。原因是該模型在訓(xùn)練過程中會將同一實(shí)體對的不同關(guān)系訓(xùn)練為相等的關(guān)系向量。如給定三元組(h1,place_lived,USA)和(h1,nationality,USA)，經(jīng)訓(xùn)練可能會得到rplace_lived≈rnationality，這將導(dǎo)致關(guān)系預(yù)測出現(xiàn)多個關(guān)系混淆的情況，這也是關(guān)系預(yù)測任務(wù)中排名第一為正確預(yù)測關(guān)系概率較低的原因。

TransH[27]：文獻(xiàn)[27]提出的TransH模型是對上述TransE 模型的改進(jìn)，該模型放寬了h+r=t這一嚴(yán)格假設(shè)，利用頭尾實(shí)體在關(guān)系r對應(yīng)的超平面上的投影向量差預(yù)測關(guān)系。該模型復(fù)雜度與TransE 相似，且在一定程度上解決了一對多等關(guān)系特性。

采用文獻(xiàn)[26]和文獻(xiàn)[27]給定的實(shí)驗(yàn)參數(shù)，包括隨機(jī)梯度下降的學(xué)習(xí)率λ、邊緣γ以及維數(shù)k，其中TransE 上的參數(shù)設(shè)置為k=50，λ=0.01，γ=1.0，TransH上的參數(shù)設(shè)置為k=100，λ=0.005，γ=0.25。

4.4 評估指標(biāo)與結(jié)論

為了評價(jià)nationality 關(guān)系預(yù)測的準(zhǔn)確性，本文設(shè)置評價(jià)指標(biāo)補(bǔ)全率（Completion）、補(bǔ)全準(zhǔn)確率（C_precision）及平均準(zhǔn)確率（average precision）來進(jìn)行評估：

對于TransE 和TransH，本文使用如下方式進(jìn)行評估。給定一個待預(yù)測的三元組(h,r,w)，為了使用TransE 和TransH 進(jìn)行預(yù)測，通過訓(xùn)練集得到h對應(yīng)頭實(shí)體向量h和r對應(yīng)的關(guān)系向量r，并計(jì)算h和r之和得到預(yù)測的尾實(shí)體向量w1，通過選擇w1與所有國家向量中距離最接近的向量作為h所對應(yīng)的國籍向量n1，并比較n1對應(yīng)實(shí)體n1是否等于w來進(jìn)行預(yù)測，若相等，則預(yù)測正確。評估結(jié)果如表8所示。

表8 不同推理方法的關(guān)系預(yù)測性能Table 8 Relationship prediction performance of different inference methods

由表8可以看出，本文所提方法只能補(bǔ)全與條件屬性完全匹配的三元組，因此只能補(bǔ)全約一半（44.6%）的缺失國籍信息。比較而言，TransE 和TransH等翻譯模型可以補(bǔ)全所有的缺失信息；然而，這些模型在補(bǔ)全的準(zhǔn)確率方面有較大缺陷，所有補(bǔ)全的信息中只有約1/4 的信息是正確的（TransE 為23.7%，TransH 為27.5%），而本文方法的正確率可以達(dá)到72.5%。即使同時考慮補(bǔ)全率和正確率，本文方法也有0.725×0.446=32.3%的平均正確率，而翻譯模型只有23.7%和27.5%的正確率，這說明本文方法在關(guān)系補(bǔ)全上具有一定的優(yōu)勢。

事實(shí)上，在進(jìn)行補(bǔ)全時，因?yàn)楸疚姆椒ú]有對不符合要求的元組進(jìn)行預(yù)測，所以該方法可明確區(qū)分未補(bǔ)全元組，方便結(jié)合其他方法進(jìn)行后續(xù)補(bǔ)全，而翻譯模型對所有元組均進(jìn)行了預(yù)測，但難以明確預(yù)測正確與否，因此難以與其他補(bǔ)全方法進(jìn)行協(xié)同補(bǔ)全。

5 結(jié)束語

本文提出了一種新的用于知識圖譜關(guān)系預(yù)測的方法，可以高效補(bǔ)全知識圖譜中某些缺失的關(guān)系，實(shí)驗(yàn)說明了該方法具有較好的推理性能。

本文方法也具有一定的局限性：首先，該方法只能對缺失的關(guān)系進(jìn)行推理預(yù)測，不能補(bǔ)全缺失的實(shí)體；其次，由于該方法挖掘出的依賴關(guān)系較為精確，對知識圖譜中的噪聲不具有魯棒性，同時也會忽略一些具有高可信度的依賴關(guān)系，不足以表達(dá)現(xiàn)實(shí)世界所有的語義。因此，本文一方面考慮通過引入模糊性[38-39]和魯棒性度量[40]來提升該方法的魯棒性；另一方面計(jì)劃將該方法提取的依賴關(guān)系進(jìn)行嵌入表示，并結(jié)合神經(jīng)網(wǎng)絡(luò)進(jìn)行關(guān)系預(yù)測。

另外，基于本文方法的特性，可考慮將該方法應(yīng)用于生物醫(yī)學(xué)領(lǐng)域，如在以疾病和基因?yàn)楣?jié)點(diǎn)的圖譜中，常需要推理基因和疾病之間的關(guān)聯(lián)。由于醫(yī)學(xué)研究的嚴(yán)謹(jǐn)性，研究者更加關(guān)注精確度，這恰好可體現(xiàn)本文方法的優(yōu)勢。