基于實(shí)體相似度信息的知識(shí)圖譜補(bǔ)全算法

王子涵，邵明光，劉國(guó)軍，郭茂祖，畢建東，劉 揚(yáng)

(1.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001；2. 北京建筑大學(xué) 建筑大數(shù)據(jù)智能處理方法研究北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044)(*通信作者電子郵箱yliu76@hit.edu.cn)

0 引言

在知識(shí)圖譜中，知識(shí)以三元組〈頭實(shí)體，關(guān)系，尾實(shí)體〉的形式存儲(chǔ)，使得知識(shí)能夠得到結(jié)構(gòu)化整理[1], 但是知識(shí)圖譜中的知識(shí)稱不上完善，尤其是在大規(guī)模知識(shí)圖譜中，需要不斷補(bǔ)充實(shí)體關(guān)系進(jìn)行知識(shí)圖譜補(bǔ)全[2], 而由于信息量過大，實(shí)體之間的關(guān)系多且復(fù)雜，傳統(tǒng)的利用鏈接預(yù)測(cè)的方法已經(jīng)不能完成大規(guī)模知識(shí)圖譜的補(bǔ)全[3], 所以對(duì)知識(shí)圖譜的補(bǔ)全往往采用學(xué)習(xí)知識(shí)表示, 并定義得分函數(shù)、采用對(duì)三元組進(jìn)行打分的方法實(shí)現(xiàn)關(guān)系預(yù)測(cè)。這樣知識(shí)圖譜的補(bǔ)全算法就成了對(duì)三元組的得分進(jìn)行排序的算法[4]。

目前，學(xué)習(xí)知識(shí)表示的代表模型有距離模型、單層神經(jīng)網(wǎng)絡(luò)模型、能量模型、雙線性模型、張量神經(jīng)網(wǎng)絡(luò)模型[5]、矩陣分解模型和翻譯模型等[6]。其中效果較好的張量神經(jīng)網(wǎng)絡(luò)模型[5]和基于文檔特征向量空間模型[7]都是在現(xiàn)有模型中加入了多層神經(jīng)網(wǎng)絡(luò)來進(jìn)行知識(shí)圖譜的補(bǔ)全[4]。這些方法雖然提高了鏈接預(yù)測(cè)能力，卻增大了參數(shù)規(guī)模，并且一次僅能考慮一種關(guān)系，導(dǎo)致模型的擴(kuò)展性較差、效率較低，無(wú)法應(yīng)用于大型知識(shí)庫(kù)[8]，所以，翻譯模型因其簡(jiǎn)單和準(zhǔn)確性引起了廣泛的關(guān)注。Mikolov等[9-10]通過類比實(shí)驗(yàn)發(fā)現(xiàn)， 詞向量空間的平移不變現(xiàn)象普遍存在于詞匯的語(yǔ)義關(guān)系和句法關(guān)系中[5]，該現(xiàn)象的發(fā)現(xiàn)使得翻譯模型TransE[11]被提出。該模型的主要思想是將關(guān)系作為對(duì)頭實(shí)體的翻譯(Translation)，并根據(jù)尾實(shí)體和關(guān)系對(duì)頭實(shí)體的翻譯的相似度來定義得分函數(shù)。TransE模型的參數(shù)少、計(jì)算復(fù)雜度低卻能夠直接建立起實(shí)體和關(guān)系之間的復(fù)雜語(yǔ)義聯(lián)系，在大規(guī)模稀疏知識(shí)圖譜上，TransE的性能更是驚人[5]。為了能夠更加精確地描述實(shí)體和關(guān)系之間的語(yǔ)義聯(lián)系，Trans系列模型[3,12-16]都在TransE的基礎(chǔ)上被提出。雖然這些模型的預(yù)測(cè)能力相較TransE有所提升，但是增大了參數(shù)規(guī)模，部分模型[3,14-16]還需要用TransE對(duì)參數(shù)進(jìn)行預(yù)訓(xùn)練，這些都增加了計(jì)算的復(fù)雜度，使得模型擴(kuò)展性變差。文獻(xiàn)[4]提出ProjE (Embedding Projection for Knowledge Graph)模型成功避免了這些問題，該模型不需要預(yù)訓(xùn)練，參數(shù)規(guī)模小且預(yù)測(cè)能力較強(qiáng)。然而，由于ProjE的關(guān)注點(diǎn)在于實(shí)體與關(guān)系之間的聯(lián)系導(dǎo)致它并沒有能夠充分利用神經(jīng)網(wǎng)絡(luò)感知和分析實(shí)體向量所代表的語(yǔ)義信息。通過研究Unstructured Model (UM)[17]，得到具有關(guān)系的實(shí)體可能集中在一些小區(qū)域內(nèi)的結(jié)論。由于向量空間可以看作是實(shí)體的語(yǔ)義空間，也就是說比較相似的實(shí)體之間更可能具有關(guān)系，所以實(shí)體是否相似可作為是否存在關(guān)系的一個(gè)衡量標(biāo)準(zhǔn)。利用這個(gè)標(biāo)準(zhǔn)和ProjE模型，神經(jīng)網(wǎng)絡(luò)可以同時(shí)分析兩個(gè)實(shí)體之間是否存在關(guān)系和具體存在什么關(guān)系，相當(dāng)于側(cè)重分析在實(shí)體分布集中的那些局部空間中的實(shí)體之間的具體關(guān)系，所以本文提出了一種新的算法——LCPE(Local Combination Projection Embedding)，并通過在標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)證明LCPE的預(yù)測(cè)能力優(yōu)于ProjE。

綜上所述，本文的主要貢獻(xiàn)是：

1) 發(fā)現(xiàn)了一種可以用于輔助判斷實(shí)體之間是否存在關(guān)系的輔助信息——實(shí)體之間的語(yǔ)義相似度，而語(yǔ)義相似度可以利用實(shí)體向量在實(shí)體嵌入空間中的距離來判斷；

2) 提出了LCPE算法，將ProjE模型和實(shí)體相似度信息融合，該模型可以同時(shí)判斷兩個(gè)實(shí)體是否存在關(guān)系和具體存在什么關(guān)系，并通過實(shí)驗(yàn)驗(yàn)證了LCPE在與ProjE參數(shù)規(guī)模相同的情況下預(yù)測(cè)能力提升。

1 LCPE模型

1.1 相關(guān)模型

翻譯模型TransE[11]的中心思想是將關(guān)系看作是頭實(shí)體到尾實(shí)體的翻譯，頭實(shí)體h、關(guān)系r和尾實(shí)體t之間的關(guān)系表示如下：

h+r≈t

(1)

因此，TransE的得分函數(shù)定義為：

E(h,r,t)=|h+r-t|L1/L2

(2)

即向量h+r和t之間的L1或L2距離，其本質(zhì)上是衡量h+r和t之間的相似度。

通過以上介紹可知, TransE模型的參數(shù)規(guī)模為nek+nrk，其中ne和nr分別是知識(shí)庫(kù)中實(shí)體和關(guān)系的數(shù)量，k是特征維數(shù)。

ProjE模型[4]的基礎(chǔ)模型是共享變量的神經(jīng)網(wǎng)絡(luò)模型, 它利用組合矩陣D對(duì)實(shí)體和關(guān)系進(jìn)行組合作為關(guān)系對(duì)頭實(shí)體的翻譯，組合運(yùn)算如式(3)所示：

e⊕r=Dee+Drr+bc

(3)

假設(shè)實(shí)體和關(guān)系被嵌入到k維向量空間中，那么e∈Rk表示實(shí)體向量，r∈Rk表示關(guān)系向量，De、Dr∈Rk×k是組合矩陣，由于在這類問題中考慮同一實(shí)體和關(guān)系的不同的特征維度之間的相互作用關(guān)系意義并不大[5]，所以De、Dr被設(shè)為對(duì)角陣，bc表示偏置量。

利用(3)定義的組合規(guī)則，結(jié)合關(guān)系作為頭尾實(shí)體的翻譯的核心思想，ProjE提出得分函數(shù)(4)用于衡量尾實(shí)體與e⊕r之間的相似度：

h(e,r)=g(Wcf(e⊕r)+bp)

(4)

其中:f和g是激活函數(shù)，Wc∈Rs×k是候選實(shí)體集組成的矩陣，其中s表示候選實(shí)體的數(shù)量，bp表示偏置。

ProjE模型與TransE模型相比，參數(shù)量只多了5k+1，其中，得分函數(shù)中的偏移量、組合矩陣和組合運(yùn)算中的偏移向量分別占1、4k和k個(gè)參數(shù)。不僅如此，ProjE模型不需要預(yù)訓(xùn)練，相較需要通過預(yù)訓(xùn)練提高預(yù)測(cè)精確度的模型[3,15-17]，它訓(xùn)練模型所需要的時(shí)間更少，模型的擴(kuò)展性也得以增強(qiáng)。

1.2 LCPE算法概述

由于ProjE模型只是簡(jiǎn)單地考慮向量t和向量h⊕r之間的相似度，并沒有充分利用實(shí)體嵌入向量的語(yǔ)義信息，導(dǎo)致神經(jīng)網(wǎng)絡(luò)可以分析的信息不足，優(yōu)勢(shì)無(wú)法完全發(fā)揮。

Unstructured Model[17]是r=0時(shí)的TransE模型，在UM中，所有實(shí)體之間的關(guān)系都視為單關(guān)系，即不考慮實(shí)體之間的具體關(guān)系類型，只考慮這實(shí)體之間是否存在關(guān)系。由于r=0，結(jié)合TransE的得分函數(shù)式(2)可知，在UM中，當(dāng)兩個(gè)實(shí)體之間具有某種關(guān)系時(shí)，這兩個(gè)實(shí)體嵌入向量之間的距離會(huì)比較小，并且兩個(gè)實(shí)體之間具有的關(guān)系越多，得到的嵌入向量之間的距離就會(huì)越小。直觀來說，實(shí)體是由多個(gè)屬性描述的，實(shí)體在語(yǔ)義空間中的嵌入向量就是用于描述實(shí)體的屬性值集合，實(shí)體嵌入向量之間的距離越小，就代表這兩個(gè)實(shí)體越相似。綜上所述，實(shí)體越相似，實(shí)體之間存在關(guān)系的可能性越大。這個(gè)結(jié)論適用于大多數(shù)事實(shí)，例如父子關(guān)系，這個(gè)關(guān)系產(chǎn)生于同類實(shí)體之間，并且父子之間具有很多相同或相似的屬性，比如所在地、長(zhǎng)相、家庭等，這些屬性值相同或接近都縮小了父子這兩個(gè)實(shí)體的嵌入向量之間的距離。

綜上，兩個(gè)實(shí)體是否相似可以作為實(shí)體之間是否存在關(guān)系的一個(gè)判斷條件，并通過判斷兩個(gè)實(shí)體之間是否存在關(guān)系來加強(qiáng)模型的鏈接預(yù)測(cè)能力。由于相似的實(shí)體嵌入向量在向量空間中距離更近，所以相似的實(shí)體嵌入向量會(huì)集中在向量空間中的一些小區(qū)域中，利用兩個(gè)實(shí)體是否相似作為加強(qiáng)預(yù)測(cè)能力的輔助信息就意味著側(cè)重于在那些實(shí)體分布稠密的局部空間判斷實(shí)體之間的具體關(guān)系類型，因此本文提出了LCPE模型，它將ProjE模型和實(shí)體相似度信息相結(jié)合，充分發(fā)揮了神經(jīng)網(wǎng)絡(luò)模型的優(yōu)勢(shì)，提高了模型的鏈接預(yù)測(cè)能力。

本文將實(shí)體之間的相似度作為輔助信息加入ProjE模型，定義得分函數(shù)：

(5)

表1 各模型的參數(shù)規(guī)模對(duì)比

注：ne表示實(shí)體數(shù)，k表示對(duì)應(yīng)實(shí)體向量和關(guān)系向量的參數(shù)個(gè)數(shù)，

s表示關(guān)系基空間的個(gè)數(shù)。

如圖1所示，LCPE模型是一個(gè)由判斷兩個(gè)實(shí)體之間相似度的網(wǎng)絡(luò)和判斷兩個(gè)實(shí)體之間是否具有某種關(guān)系的網(wǎng)絡(luò)共同構(gòu)成的神經(jīng)網(wǎng)絡(luò)。Wc是由候選實(shí)體向量組成的矩陣，WE表示實(shí)體向量構(gòu)成的矩陣，WR表示關(guān)系向量構(gòu)成的矩陣，Ei和Ej分別是從Wc和WE中提取出的一個(gè)實(shí)體向量，R是從WR中提取出的關(guān)系向量，De和Dr分別代表組合矩陣。

圖1 LCPE模型結(jié)構(gòu)

1.3 模型訓(xùn)練

在本文算法中，候選實(shí)體集雖然因?yàn)楣蚕韺?shí)體變量而沒有增加參數(shù)的數(shù)量，但是如果每次都用全部實(shí)體集進(jìn)行訓(xùn)練，也會(huì)導(dǎo)致巨大的運(yùn)算量，所以要使用候選抽樣的方法來減小候選實(shí)體集Wc的規(guī)模[18-20]，并且利用Word2Vec[19]的規(guī)則對(duì)候選集進(jìn)行負(fù)例抽樣效果最好[4]。具體方法是對(duì)于一個(gè)給定的實(shí)體e，其訓(xùn)練所使用的候選實(shí)體集由全部的正例中的實(shí)體集和一部分負(fù)例中的實(shí)體集構(gòu)成，為了簡(jiǎn)單起見，利用二項(xiàng)分布B(1,Py)來表示某個(gè)負(fù)例中的實(shí)體是否被選中，即Py表示該負(fù)例被選中的概率，而1-Py表示未被選中的概率，實(shí)驗(yàn)表明最優(yōu)的負(fù)例抽樣概率為25%[4]。

Trans系列模型通常都采用了pairwise方法對(duì)模型進(jìn)行訓(xùn)練，損失函數(shù)L定義為如式(6)形式：

E(h′,r′,t′)])

(6)

其中:E表示三元組的得分函數(shù);S表示正例三元組的集合，正例三元組是在原知識(shí)庫(kù)中存在的三元組;S′表示負(fù)例三元組的集合，負(fù)例三元組是通過用知識(shí)庫(kù)中其他的實(shí)體或關(guān)系替換正例三元組中的h、r或t產(chǎn)生的在原知識(shí)庫(kù)中不存在的三元組。

近年來，softmax回歸在多標(biāo)簽圖像注釋任務(wù)中取得了良好的效果，這是因?yàn)槎鄻?biāo)簽圖像注釋以及許多其他分類任務(wù)應(yīng)該綜合考慮其預(yù)測(cè)出的候選集中的所有分?jǐn)?shù)[5],因此，模型采用softmax函數(shù)以便考慮所有候選實(shí)體的分?jǐn)?shù)，用softmax和tanh作為激活函數(shù)，將式(5)中的g和f分別用softmax函數(shù)和tanh函數(shù)替換可以將得分函數(shù)寫成式(7)所示形式：

h(e,r)i=

(7)

并利用listwise方法進(jìn)行訓(xùn)練。LCPE模型的損失函數(shù)定義為式(8)：

(8)

其中:y∈Rs是一個(gè)二元標(biāo)簽向量;s是候選實(shí)體集的個(gè)數(shù);yi=1代表第i個(gè)候選實(shí)體和實(shí)體e,關(guān)系r組成的三元組是一個(gè)正例三元組, 1(·)代表當(dāng)括號(hào)內(nèi)的等式成立時(shí)，1(·)=1,否則1(·)=0;h(e,r)表示三元組的得分函數(shù)(式(5))，而h(e,r)i表示第i個(gè)候選實(shí)體和實(shí)體e，關(guān)系r組成的三元組的得分。

預(yù)測(cè)問題歸根結(jié)底是一個(gè)對(duì)得分進(jìn)行排序的問題，而pairwise的訓(xùn)練方法并沒有很好地解決實(shí)體預(yù)測(cè)排名的問題，所以利用考慮了整體的得分排名的listwise方法對(duì)模型進(jìn)行訓(xùn)練效果更好[4]。

2 實(shí)驗(yàn)結(jié)果與分析

本章展示了實(shí)體相似度作為輔助項(xiàng)的可行性以及LCPE與之前提到的模型的預(yù)測(cè)結(jié)果對(duì)比。關(guān)系預(yù)測(cè)實(shí)驗(yàn)在兩個(gè)公開數(shù)據(jù)集FB15k[21]和WN18上進(jìn)行，F(xiàn)B15k是一個(gè)知識(shí)圖譜的重要子集，WNID是一個(gè)WordNet[22]的子集，ID表示在WordNet中的ID，用于在WordNet中唯一標(biāo)記一個(gè)子集。FB15k和WN18的實(shí)體、關(guān)系和三元組數(shù)如表2所示。

表2 實(shí)驗(yàn)使用的數(shù)據(jù)集

2.1 參數(shù)設(shè)置

2.2 實(shí)體相似度對(duì)比

為了防止嵌入向量的大小的影響，本文將計(jì)算實(shí)體之間的余弦距離用以衡量實(shí)體之間的相似度。隨機(jī)提取LCPE中發(fā)生關(guān)系的實(shí)體對(duì)，計(jì)算它們的嵌入向量的余弦距離，同時(shí)對(duì)于上述實(shí)體，計(jì)算它們?cè)赑rojE中的余弦距離，最后計(jì)算二者的比值。實(shí)驗(yàn)在WN18數(shù)據(jù)集上進(jìn)行。

實(shí)驗(yàn)結(jié)果如圖2所示，縱坐標(biāo)代表同一實(shí)體對(duì)在兩個(gè)模型中的余弦距離比值(ProjE中的實(shí)體之間的余弦距離/LCPE中的實(shí)體之間的余弦距離)。實(shí)驗(yàn)結(jié)果顯示距離比值大多大于1，這說明LCPE中具有關(guān)系的實(shí)體的余弦距離更小，和本文預(yù)期相符，也說明了實(shí)體相似度的輔助信息可以用作增強(qiáng)預(yù)測(cè)能力的輔助項(xiàng)。

2.3 鏈接預(yù)測(cè)結(jié)果

鏈接預(yù)測(cè)是為了預(yù)測(cè)三元組中缺失的頭實(shí)體和尾實(shí)體的任務(wù)，而實(shí)體的預(yù)測(cè)問題歸根結(jié)底是實(shí)體的得分排序問題，所以使用Raw Mean Rank、Filtered Mean Rank和Raw Hits@10、Filtered Hits@k作為對(duì)鏈接預(yù)測(cè)的預(yù)測(cè)效果評(píng)估指標(biāo)。Raw Mean Rank是正確的實(shí)體在得到的得分序列中的平均排名； Raw Hits@k是指正確的實(shí)體在得分為前k的元素中出現(xiàn)的概率，但是，有其他的正確實(shí)體排在待測(cè)的正確實(shí)體之前的情況，所以還有一種衡量標(biāo)準(zhǔn)就是將其他的已知的正確實(shí)體刪去之后再排序得到Filtered Mean Rank和Filtered Hits@k，它們分別代表刪去了其他的正確實(shí)體后目標(biāo)實(shí)體的平均排名和在前k個(gè)元素中出現(xiàn)的概率。由上述介紹可知，Raw Mean Rank和Filtered Mean Rnak越低越好，Raw Hits@k和Filtered Hits@k越高越好。本文將CLPE與Trans系列模型[3,11-17]及ProjE模型[4]進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果如表3所示。

圖2 WN18中實(shí)體之間的余弦距離

數(shù)據(jù)集方法Raw Mean Rank(頭實(shí)體/尾實(shí)體) Filtered Mean Rank(頭實(shí)體/尾實(shí)體)Raw Hits@10(頭實(shí)體/尾實(shí)體)Filtered Hits@10(頭實(shí)體/尾實(shí)體)WN18UM31530435.338.2TransE26325175.489.2TransH318/401303/38875.4/73.086.7/82.3TransR232/238219/22578.3/79.891.7/92.0TranSparse(US)233/223221/21179.6/80.193.4/93.2TranSparse(S)235/224223/22179.0/79.892.3/92.8TransD242/224229/21279.2/79.692.5/92.2TransF—198—95.3ProjE248.9/254.3231.2/238.478.7/80.295.3/95.0LCPE234.2/238.3216.6/222.478.9/80.295.2/95.0FB15kUM1074 9794.56.3TransE24312534.947.1TransH211/21284/8742.5/45.758.5/64.4TransR226/19878/7743.8/48.265.5/68.7TranSparse(US)216/19066/8250.3/53.778.4/79.9TranSparse(S)211/18763/8250.1/53.377.9/79.5TransD211/19467/9149.4/53.474.2/77.3TransF—62—82.3ProjE278.7/181.883.8/58.741.1/48.774.5/79.6LCPE269.2/176.475.5/54.744.4/52.177.2/82.3

神經(jīng)網(wǎng)絡(luò)模型由于其出色的信息感知和分析能力可以利用更少的參數(shù)實(shí)現(xiàn)更強(qiáng)的關(guān)系預(yù)測(cè)能力。LCPE模型和ProjE模型充分發(fā)揮了這一優(yōu)勢(shì)，同時(shí)針對(duì)知識(shí)圖譜補(bǔ)全問題采用listwise方法訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型，考慮所有三元組的得分，盡可能保證所有正例的得分比負(fù)例的得分高，這也是它們的預(yù)測(cè)能力強(qiáng)的重要原因之一。

LCPE比ProjE在WN18數(shù)據(jù)集上Mean Rank平均提前了11，Hits@10提升了0.2個(gè)百分點(diǎn); 在FB15k上Mean Rank提前了7.5，Hits@10平均提升了3.05個(gè)百分點(diǎn)。這也說明了實(shí)體相似度信息可以用于輔助判斷實(shí)體間的具體關(guān)系類型,從而提高預(yù)測(cè)能力。

3 結(jié)語(yǔ)

知識(shí)圖譜補(bǔ)全算法是對(duì)實(shí)體之間關(guān)系的預(yù)測(cè)算法，由于當(dāng)今時(shí)代的信息量過大導(dǎo)致了預(yù)測(cè)模型可能具有巨大的參數(shù)量，所以如何利用盡可能少的參數(shù)量達(dá)到更高的預(yù)測(cè)精度就成了一個(gè)很重要的問題。ProjE算法不僅實(shí)現(xiàn)了小參數(shù)量并且能夠更為出色的預(yù)測(cè)到實(shí)體之間的各種關(guān)系。通過對(duì)ProjE算法和Unstructured Model的研究，本文提出了CLPE模型，它將利用了實(shí)體之間的相似度作為輔助信息優(yōu)化了ProjE模型，并通過實(shí)驗(yàn)證明了實(shí)體之間的相似度作為輔助信息的合理性以及CLPE在沒有增大參數(shù)規(guī)模的基礎(chǔ)上將模型的預(yù)測(cè)能力進(jìn)一步提升。

以簡(jiǎn)單的共享變量神經(jīng)網(wǎng)絡(luò)為基礎(chǔ)的算法在知識(shí)圖譜補(bǔ)全方面取得了很好的效果，而如何將更多看似簡(jiǎn)單但其實(shí)很有效的方法利用到知識(shí)圖譜補(bǔ)全算法中，或如何優(yōu)化現(xiàn)有模型以取得更好的效果仍然有待研究。