基于實體相似度信息的知識圖譜補全算法

王子涵，邵明光，劉國軍，郭茂祖，畢建東，劉 揚

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

0 引言

在知識圖譜中，知識以三元組〈頭實體，關系，尾實體〉的形式存儲，使得知識能夠得到結構化整理[1], 但是知識圖譜中的知識稱不上完善，尤其是在大規模知識圖譜中，需要不斷補充實體關系進行知識圖譜補全[2], 而由于信息量過大，實體之間的關系多且復雜，傳統的利用鏈接預測的方法已經不能完成大規模知識圖譜的補全[3], 所以對知識圖譜的補全往往采用學習知識表示, 并定義得分函數、采用對三元組進行打分的方法實現關系預測。這樣知識圖譜的補全算法就成了對三元組的得分進行排序的算法[4]。

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

綜上所述，本文的主要貢獻是：

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

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

1 LCPE模型

1.1 相關模型

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

h+r≈t

(1)

因此，TransE的得分函數定義為：

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

(2)

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

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

ProjE模型[4]的基礎模型是共享變量的神經網絡模型, 它利用組合矩陣D對實體和關系進行組合作為關系對頭實體的翻譯，組合運算如式(3)所示：

e⊕r=Dee+Drr+bc

(3)

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

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

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

(4)

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

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

1.2 LCPE算法概述

由于ProjE模型只是簡單地考慮向量t和向量h⊕r之間的相似度，并沒有充分利用實體嵌入向量的語義信息，導致神經網絡可以分析的信息不足，優勢無法完全發揮。

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

綜上，兩個實體是否相似可以作為實體之間是否存在關系的一個判斷條件，并通過判斷兩個實體之間是否存在關系來加強模型的鏈接預測能力。由于相似的實體嵌入向量在向量空間中距離更近，所以相似的實體嵌入向量會集中在向量空間中的一些小區域中，利用兩個實體是否相似作為加強預測能力的輔助信息就意味著側重于在那些實體分布稠密的局部空間判斷實體之間的具體關系類型，因此本文提出了LCPE模型，它將ProjE模型和實體相似度信息相結合，充分發揮了神經網絡模型的優勢，提高了模型的鏈接預測能力。

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

(5)

表1 各模型的參數規模對比

注：ne表示實體數，k表示對應實體向量和關系向量的參數個數，

s表示關系基空間的個數。

如圖1所示，LCPE模型是一個由判斷兩個實體之間相似度的網絡和判斷兩個實體之間是否具有某種關系的網絡共同構成的神經網絡。Wc是由候選實體向量組成的矩陣，WE表示實體向量構成的矩陣，WR表示關系向量構成的矩陣，Ei和Ej分別是從Wc和WE中提取出的一個實體向量，R是從WR中提取出的關系向量，De和Dr分別代表組合矩陣。

圖1 LCPE模型結構

1.3 模型訓練

在本文算法中，候選實體集雖然因為共享實體變量而沒有增加參數的數量，但是如果每次都用全部實體集進行訓練，也會導致巨大的運算量，所以要使用候選抽樣的方法來減小候選實體集Wc的規模[18-20]，并且利用Word2Vec[19]的規則對候選集進行負例抽樣效果最好[4]。具體方法是對于一個給定的實體e，其訓練所使用的候選實體集由全部的正例中的實體集和一部分負例中的實體集構成，為了簡單起見，利用二項分布B(1,Py)來表示某個負例中的實體是否被選中，即Py表示該負例被選中的概率，而1-Py表示未被選中的概率，實驗表明最優的負例抽樣概率為25%[4]。

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

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

(6)

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

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

h(e,r)i=

(7)

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

(8)

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

預測問題歸根結底是一個對得分進行排序的問題，而pairwise的訓練方法并沒有很好地解決實體預測排名的問題，所以利用考慮了整體的得分排名的listwise方法對模型進行訓練效果更好[4]。

2 實驗結果與分析

本章展示了實體相似度作為輔助項的可行性以及LCPE與之前提到的模型的預測結果對比。關系預測實驗在兩個公開數據集FB15k[21]和WN18上進行，FB15k是一個知識圖譜的重要子集，WNID是一個WordNet[22]的子集，ID表示在WordNet中的ID，用于在WordNet中唯一標記一個子集。FB15k和WN18的實體、關系和三元組數如表2所示。

表2 實驗使用的數據集

2.1 參數設置

2.2 實體相似度對比

為了防止嵌入向量的大小的影響，本文將計算實體之間的余弦距離用以衡量實體之間的相似度。隨機提取LCPE中發生關系的實體對，計算它們的嵌入向量的余弦距離，同時對于上述實體，計算它們在ProjE中的余弦距離，最后計算二者的比值。實驗在WN18數據集上進行。

實驗結果如圖2所示，縱坐標代表同一實體對在兩個模型中的余弦距離比值(ProjE中的實體之間的余弦距離/LCPE中的實體之間的余弦距離)。實驗結果顯示距離比值大多大于1，這說明LCPE中具有關系的實體的余弦距離更小，和本文預期相符，也說明了實體相似度的輔助信息可以用作增強預測能力的輔助項。

2.3 鏈接預測結果

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

圖2 WN18中實體之間的余弦距離

數據集方法Raw Mean Rank(頭實體/尾實體) Filtered Mean Rank(頭實體/尾實體)Raw Hits@10(頭實體/尾實體)Filtered Hits@10(頭實體/尾實體)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

神經網絡模型由于其出色的信息感知和分析能力可以利用更少的參數實現更強的關系預測能力。LCPE模型和ProjE模型充分發揮了這一優勢，同時針對知識圖譜補全問題采用listwise方法訓練神經網絡模型，考慮所有三元組的得分，盡可能保證所有正例的得分比負例的得分高，這也是它們的預測能力強的重要原因之一。

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

3 結語

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

以簡單的共享變量神經網絡為基礎的算法在知識圖譜補全方面取得了很好的效果，而如何將更多看似簡單但其實很有效的方法利用到知識圖譜補全算法中，或如何優化現有模型以取得更好的效果仍然有待研究。