基于表示學習和語義要素感知的關系推理算法

劉 嶠 韓明皓 楊曉慧 劉 瑤 吳祖峰

(電子科技大學信息與軟件工程學院 成都 610054) (qliu@uestc.edu.cn)

基于表示學習和語義要素感知的關系推理算法

劉 嶠 韓明皓 楊曉慧 劉 瑤 吳祖峰

(電子科技大學信息與軟件工程學院 成都 610054) (qliu@uestc.edu.cn)

基于知識表示的關系推理方法研究是近年來統計關系學習和知識圖譜領域共同關注的熱點.通過對當前流行的基于知識表示的推理模型進行比較，分析了現有模型所普遍采用的基本假設存在的不合理之處，即忽視了實體與關系在語義上的多樣性.據此提出了一種新的關系推理建模假設：實體對之間的每種關系反映的是兩側實體在某些特定方面的語義關聯，通過對實體向量的語義方面要素進行選擇性加權，可以實現對不同關系語義的表示和區分.根據該假設提出了一種新的關系推理建模方法，采用非線性變換的方法來解決表示學習中的語義分辨率問題.在公開數據集上的實驗結果表明：所提出的算法對復雜關系類型和相關實體具有良好的語義區分能力，能有效提高知識圖譜上的關系推理準確率，性能顯著優于目前主流的相關工作.

統計關系學習；關系推理；表示學習；知識圖譜；多元關系數據挖掘

本文研究的是知識圖譜上的關系推理問題.關系推理任務的目標是基于知識圖譜中已有的知識，采用統計機器學習方法自動推理實體對之間可能存在的關系.它既是統計關系學習領域長期關注的基礎理論問題，也是知識圖譜領域的研究熱點[1].

知識圖譜是一個由實體與關系構成的結構化語義知識庫，其中的知識元素以(實體，關系，實體)三元組的形式表達和存儲，實體間通過關系相互聯結，構成網狀知識結構[2].知識圖譜技術在自然語言處理、智能信息檢索和知識工程等領域具有核心基礎地位，近年來受到學術界的廣泛關注[3].然而，制約知識圖譜應用水平的一個關鍵問題是知識的不完備性，雖然近年來谷歌Knowledge Vault、微軟Satori和IBM Watson等知識圖譜項目不斷刷新知識規模記錄，現有的知識圖譜仍然存著大量的信息缺失[4].

關系推理技術可以直接應用于知識圖譜的自動化補全，也可以與開放域信息抽取(open information extraction, OIE)技術相結合，用于對信息抽取結果進行質量評估，提高知識圖譜構建的自動化水平[1].

當前關系推理方法的研究思路主要有2類：基于邏輯規則的關系推理模型和基于表示學習的關系推理模型[5].隨著關系推理算法研究不斷取得新進展，部分成果已經在主流商業產品中取得應用，例如Knowledge Vault項目就采用了邏輯規則模型與表示學習模型相結合的混合模型來進行知識質量評估[6].

與基于邏輯規則的關系推理模型相比，基于表示學習的關系推理模型能夠更有效地利用知識圖譜中已有的知識進行推理建模[7].而且，隨著深度學習技術在知識表示學習領域的應用不斷深入，基于表示學習的關系推理算法研究也取得了快速發展，是近年來關系推理研究領域重點聚焦的熱點問題[5].

然而，通過文獻調研我們發現，現有的基于表示學習的關系推理模型在對實體關系三元組(h,r,t)進行關系推理時均采用了Bordes等人提出的向量表達基本假設：h+r=t，因此存在一個共性缺陷，即模型無法表達關系語義的多樣性，建模方式的僵化導致算法對位于關系同一側的多個實體的分辨率較差.

這種理論缺陷典型的表現是當此類算法在處理“一對多”和“多對一”類型關系(對關系類型的定義詳見2.1)時，如果對于關系兩側實體分別實施替換干擾，得到的推理性能表現不均衡，對于“多”側實體的區分能力明顯較差.本文實驗部分將對此進行詳細討論.另一個典型表現是當實體間存在多種關系時，會出現語義上的悖論.例如，若實體對(h,t)之間既有“父子”關系，又有“校友”關系，由于實體的向量表達是確定的，則根據基本假設h+r=t可以得出“父子=校友”的錯誤結論.

針對上述問題，本文提出一種新的建模思路如下：將通過表示學習得到的實體向量中的元素視為其語義方面要素(aspect factors)，在不同關系代表的語義環境下，關系向量中的每個元素可由關系兩側實體向量中的對應元素線性組合得到.籍此可以修正基于表示學習的關系推理算法的基本假設，提高模型對關系語義多樣性的區分能力.論文的主要貢獻包括：

1) 提出了一種新的關系推理建模假設：實體對(h,t)之間的每種關系反映的是關系兩側實體在某些特定的語義方面要素上的關聯，可以通過對實體的語義方面要素進行選擇性加權來表達和區分.

2) 設計了2種新的關系推理算法，對上述假設進行了實驗驗證，實驗結果表明所提算法的綜合性能表現顯著優于當前主流的相關工作.

1 相關工作

早期的關系推理方法研究主要基于一階謂詞邏輯規則和貝葉斯算法，通過將人工編寫的一階謂詞邏輯規則與不同類型的概率圖模型相結合，依據所生成的邏輯網絡進行推理獲得新的知識[8].代表性工作包括Markov邏輯網絡模型[9]和基于貝葉斯網絡的概率關系模型[10].這類模型能夠在小規模領域知識庫上取得較高的關系推理準確性，缺點在于依賴專家構建邏輯規則，且模型在推理過程中的計算復雜度較高，難以適應大規模知識庫上關系推理任務要求[11].

1.1基于邏輯規則的關系推理模型

為解決大規模知識圖譜中關系推理的效率問題，Lao等人在基于一階Horn子句推理的FOIL(first order inductive learner)算法基礎上提出了一種路徑排序算法(path ranking algorithm, PRA)[12].PRA算法采用抽象的實體間關系路徑取代了具象的Horn子句作為關系推理的依據，并采用隨機采樣的方式替代窮舉搜索以提高計算效率.PRA算法不僅保持了FOIL算法的關系推理準確性，而且提高了模型的計算效率.

隨后，Gardner等人指出PRA算法在計算關系路徑概率時的計算開銷過大，并據此采用特征空間二值化、增加自定義特征模式以及采取廣度優先搜索等方式對PRA算法進行了改進，提出了準確性和計算效率更好的SFE(subgraph feature extraction)算法[13].

然而，SFE算法在推理準確性上仍無法與當前主流的基于表示學習的關系推理算法抗衡.Liu等人指出了PRA和SFE算法所采用的關系單向性假設存在的問題，并采用雙層隨機游走策略提高了算法對關系路徑的采樣覆蓋率，所提出的層次化隨機游走推理模型(hierarchical random walk inference, HiRi)在公開數據集上取得了優于表示學習模型的性能表現[7].

總體說來，邏輯推理模型的發展趨勢是逐漸摒棄對人工規則的依賴，轉而借助模式識別方法進行規則特征發現，并采用機器學習方法進行特征建模.制約邏輯推理算法研究的主要問題是圖算法的計算復雜度較高，導致方法可擴展性差.而且知識圖譜中的節點度的分布服從長尾分布，即只有少量的實體與關系擁有較高的出現頻率，而大部分實體關系的出現頻率較低.由此導致的數據稀疏性問題對邏輯推理算法的性能影響較大[5].因此目前學術界主要關注對數據稀疏性不敏感，且算法可并行的表達推理算法.

1.2基于表示學習的關系推理模型

隨著word2vec和GloVe等“詞向量表達”模型相繼在一系列自然語言處理任務中取得進展[14-15]，表示學習方法近年來受到了廣泛關注.在關系推理領域，以TransE算法為代表的關系推理模型，因其具有推理準確性高和算法可并行等優點而成為近期研究熱點，目前仍在快速發展過程中[16].

TransE模型參考了Nickel等人提出的RESCAL張量分解模型(tensor factorization model)[17].該模型采用三階張量對知識圖譜中的事實(h,r,t)進行建模，參數模型的函數表達為

(1)

其中，h,t∈k為三元組的頭、尾實體在k維空間的向量表達，Wr∈k×k表示關系r的權重矩陣.

受RESCAL模型啟發，Bordes等人提出了基于結構化表達的SE(structured embedding)關系推理算法[18].參數模型的函數表達如下：

(2)

其中，Mrh和Mrt分別表示關系r關于頭和尾實體的線性變換.由于SE和RESCAL算法在大規模真實數據集上的推理準確性較低，Bordes等人受word2vec詞表達算法的啟發提出了TransE建模假設，放棄了RESCAL算法采用關系矩陣變換的實體映射方式，轉而采用h+r=t的方式進行推理[16].參數模型為

(3)

Fig. 1 The example of TransE model圖1 TransE模型示例

TransE算法因其計算效率高(可并行)和算法召回率高而受到學術界的高度關注[1].然而該算法在處理復雜關系類型時存在性能瓶頸，為改進TransE算法性能，學術界近年來付出了大量的努力[5].

例如Wang等人提出的TransH算法允許實體在不同的關系下采用不同的向量表達[19].基本思路是在TransE基本假設基礎上增加實體映射，即首先將實體映射到對應關系r的超平面中：

(4)

其中，wr∈k表示由關系r所確定的超平面的單位法向量.然后根據hr+r=tr基本假設進行建模.

Fan等人提出的TransM模型[20]，通過向優化目標函數中引入與關系類型相關的權重因子，以強化TransE模型對實體的區分能力.參數模型如下：

(5)

受上述工作啟發，Lin等人綜合借鑒TransH,TransM和RESCAL算法的思路，提出了TransR算法和改進的CTransR算法[21].基本思路是將實體與關系視為不同類型的對象，應分別將其投影到不同的向量空間中，TransR所使用的實體映射為

hr=Mrh;tr=Mrt，

(6)

其中，Mr∈d×k表示關系r的線性變換參數矩陣，其作用是將實體的向量表達從k維空間變換到關系r所在的d維空間.由于TransR算法的參數復雜度較高，為了降低模型復雜度，提高算法對大規模知識圖譜推理任務的適用性，Lin等人還進一步提出了改進的CTransR算法，通過將知識圖譜中的實體按從屬的關系類型進行聚類，在提高計算效率的同時也增加了實體在不同關系上下文的區分度，在FB15K等數據集上的實驗性能優于主流相關算法[21].

1.3對相關工作的討論

除了基于邏輯規則和基于表示學習的關系推理方法外，學術界還提出了一些新的解決方案.例如，Socher等人針對SE模型對知識庫結構信息利用不足的缺點提出了單層感知機模型(single layer model, SLM)，SLM模型能夠對實體在特定關系語義下的相關性進行建模，參數模型表達為：

f(h,r,t)=rTg(Mrhh+Mrtt)，

(7)

其中，Mrh和Mrt分別表示關系r關于頭實體和尾實體的映射矩陣.激活函數g(·)為雙曲正切(tanh)函數.針對SLM模型表示學習能力不足的缺點，Socher等人進一步提出了神經張量模型(neural tensor networks, NTN)，通過將SLM中的線性變換層替換為雙線性張量，進一步提高了關系推理準確性[22].然而，NTN算法的張量計算復雜度非常高，且由于模型參數復雜度過高，易導致參數訓練欠擬合，所以需要大量的訓練數據，進一步導致模型訓練困難.

此外，Lin等人嘗試將邏輯推理與表達推理方法相結合，提出了PtransE算法[23].思路是將知識圖譜中的關系路徑與關系的向量表達聯系起來，將邏輯推理規則視為向量加法操作.評分函數為

f(h,r,t)=E(h,r,t)+E(h,P(h,t),t)，

(8)

其中，P(h,t)={p1,p2,…,pN}表示實體間關系路徑集合，pi=(r1,r2,…,rk)為實體間的一條路徑，E(h,r,t)等價于式(3)，E(h,P(h,t),t)計算為

(9)

綜上，基于表示學習的關系推理算法研究是近年來關系推理領域關注的熱點問題.基本思路是將實體與關系對象包含的語義信息表示為低維空間中的實值向量，進而用于關系推理計算.TransE算法是表達推理模型的典型代表，因其計算效率高且推理準確性高而備受關注，學術界對其進行了反復研究改進[5].

然而，通過對比以上算法改進工作可看到，改進后的算法均未能從根本上解決TransE基本假設中存在的矛盾，即忽視實體與關系在語義上的多樣性.例如，TransH和TransR算法，雖然采用了不同的線性變換機制修正實體向量，但最終仍是基于h+r=t基本假設進行模型參數學習.由于該假設無法對實體在不同關系上下文環境下的語義做出區分，因此在得到實體的向量表達后，再試圖通過線性變換來提高對實體間語義差別的分辨能力是非常困難的.

本文受上述相關工作的啟發，提出用非線性變換的方法來解決表示學習的語義分辨率問題.通過將關系表達視為相關實體語義方面要素的加權組合，使算法模型既能夠保留TransE基本假設的合理性，又同時具備對實體和關系在不同語義條件下的區分能力.在對算法性能進行測評時，考慮到PtransE和CTransR算法是目前公開報道的關系推理算法中性能表現最好的算法，但PtransE的關系路徑采樣過程計算復雜度過高，難以適應大規模知識圖譜的推理任務要求，因此本文主要采用CtransR算法作為性能指標比較對象.此外，TransE算法被用作實驗的Baseline，原因是該算法可以視為本文提出的算法的特例，通過比較二者的實驗結果，可以加深對本文算法的理解.由于RESCAL算法目前被應用于一些商業知識庫中，因此也將其作為實驗比較對象，目的是通過對比二者的計算效率和推理準確率，揭示本文提出的算法模型的性能優勢和實用價值.

2 基于表示學習的關系推理算法

符號系統說明：以符號KB表示知識圖譜中已有的三元組集合.E和R分別表示知識圖譜中的實體集合與關系集合.符號(h,r,t)∈KB表示一個已知事實.其中，符號h,t和r分別表示實體和關系的k維向量表達(embeddings)，h稱為頭實體(head)，t稱為尾實體(tail)，r表示實體對(h,t)之間的關系.

2.1算法設計思想

現有基于表示學習的關系推理算法大多基于Bordes等人提出的h+r=t基本假設，采用確定的實向量表達知識庫中已有的實體與關系.本文認為這種確定的表示學習方式忽略了目標對象的語義多樣性，是導致此類算法性能存在瓶頸的問題根源.

表1給出了TransE算法在4種關系類型上的實驗結果，表中的Prediction with Head replacement字段表示對于給定三元組，通過替換頭實體構造干擾列表的推理實驗結果，Prediction with Tail replacement字段表示通過替換尾實體構造干擾列表得到的結果.

Table 1 hits@10 of TransE on FB15k Dataset

從表1可以看出，如果對關系兩側實體分別實施替換干擾，TransE算法在1∶M和M∶1等關系類型上的推理性能表現非常不均衡.表1中4種關系類型的劃分依據為：對于給定關系ri定義一組參數為

(10)

其中，factsi表示知識圖譜中包含關系ri的三元組(事實)集合，#factsi表示factsi中的元素個數，#headsi和#tailsi分別表示factsi中包含的不同頭、尾實體的個數.據此定義4種關系類型為

(11)

閾值η=1.5，以便與相關工作保持一致[7].從表1可以看出，TransE算法在處理一對多(1∶M)類型的關系(即一個頭實體對應于多個尾實體)時，在尾實體一側的性能表現顯著低于頭實體一側.類似的情況也發生在多對一(M∶1)類型的關系推理任務中.這一現象表明，如果采用固定的向量表達來表示實體，在h+r=t假設下無法對相似實體的細微語義差別進行區分，導致推理結果存在語義分辨率問題.

為了進一步從理論角度闡述該假設存在的矛盾，假設實體對(h,t)之間存在多種不同的關系，以符號r1,r2,…,rn分別表示這些關系.則由TransE的基本假設h+r=t可以得出結論：

(12)

即關系r1,r2,…,rn的向量表示趨同，無法做語義上的區分.例如給定3個基本事實：(星球大戰，導演，喬治·盧卡斯)，(星球大戰，制作人，喬治·盧卡斯)以及(星球大戰，編劇，喬治·盧卡斯)，由式(12)可知，TransE模型將對“導演”、“制作人”和“編劇”這3種關系得出相同的向量表達.其他基于TransE的表達推理模型也有類似的問題.

為解決該矛盾，需要修正算法的基本假設，提高模型對關系語義多樣性的區分能力.

考慮到關系的普適性，即多個實體對之間可以共享同一種關系(如IsA關系和Affiliation關系等).本文將關系的向量表達視為不變量，將實體向量中的元素視為實體屬性的方面要素(aspect factors).據此在h+r=t基本假設的基礎上，提出新的假設如下：實體對(h,t)間的每種關系反映了兩側實體在某些特定的方面要素上的關聯，可以通過對實體向量的方面要素進行選擇性加權，以實現關系語義的區分.

該假設的合理性舉例說明如下：以2個三元組為例：(特朗普，國籍，美國)和(特朗普，居住于，美國).若將實體向量視為不變量，則由h+r=t假設可以得出“國籍”=“居住于”的錯誤結論.

而根據本文提出的假設，即每種關系反映的是實體間某些特定方面要素的關聯和差異，則可以有效解決上述問題.例如，“國籍”關系反映的是兩側實體間在法律、出生地等方面的從屬關系，而“居住于”關系反映的是兩側實體間在工作、生活等方面的地理位置聯系.本文認為，在實體的向量表達中，每個維度包含了不同的語義方面信息，通過對其進行適當的加權處理，可以實現對關系的表達和對關系語義的區分.據此提出關系推理算法的設計方案如下.

2.2算法描述

對于知識圖譜中的每種關系ri∈k，定義與之相關的實體方面要素(語義)權重向量βi∈k，即關系ri代表的語義環境下，與實體向量的元素相對應的語義權重值所組成的向量.算法模型為

(13)

式(13)表示在給定的關系語境下，對三元組中的頭尾實體向量采用相同的加權系數進行處理，以突出對應方面要素的影響，同時弱化不相關方面要素的影響.考慮到關系的有向性，關系兩側的實體也可能存在顯著的語義差異，因此其向量表達的組成要素可能存在顯著差異.以(特朗普，國籍，美國)為例，“國籍”關系的頭實體是人物名實體，尾實體是國家名實體.人物的特征要素與國家的特征要素顯然是無法實現一一對應的，因此本文進一步考慮對關系兩側的實體進行分別加權處理.即，對于知識圖譜中的每種關系ri∈k，定義2個與之相關的實體方面要素權重向量k，分別用于對關系兩側實體集合的向量表達進行加權處理，算法模型為

(14)

從式(13)和(14)可以看出，當權重向量βi,βhi和βti的元素取值為1時，式(13)(14)2個算法等價于TransE模型.為便于區分上述模型，本文將式(13)稱為統一加權模型(unified weighted model, UWM)，將式(14)稱為獨立加權模型(independent weighted model, IWM).下面介紹模型的參數估計方法.

2.3模型訓練方法

首先介紹訓練樣本的構造方法.本文遵循封閉世界假設[1]，將知識圖譜中已有的三元組視為正樣本，正樣本集合采用符號Δ表示.對于任意給定正樣本(h,r,t)∈Δ，構造其負樣本集合：

Δ′={(h′,r,t)|h′∈E∧(h′,r,t)?Δ}∪
{(h,r,t′)|t′∈E∧(h,r,t′)?Δ}，

(15)

其中，(h′,r,t)和(h,r,t′)分別表示對樣本(h,r,t)中的頭、尾實體進行替換得到的三元組.得到訓練樣本集合后，采用邊界最大所化(maximum margin)方法對本文提出的UWM算法與IWM算法的參數進行學習[19].設(h,r,t)∈Δ表示已知事實，(h′,r,t′)∈Δ′表示針對該給定事實構造的負樣本.定義正負樣本語義偏差函數為

J(h,r,t)=f(h,r,t)+γ-f(h′,r,t′)，

(16)

其中，符號γ表示邊界參數，用于設置正、負樣本的語義誤差間隔.據此進一步定義模型參數估計的優化目標函數為

(17)

其中，函數max(x,y)返回x和y中較大的值.本文采用隨機梯度下降(stochastic gradient descent, SGD)方法求解優化目標函數(17)的最優值，由此即可同步求得式(13)或式(14)的參數.

2.4算法復雜度分析

表2給出了本文提出的UWM和IWM算法模型以及一些經典相關算法的復雜度分析結果.其中，參數復雜度(parameter complexity)給出了模型中需要估計的參數個數，時間復雜度(time complexity)給出了采用SGD算法求解模型參數時，每輪迭代需要執行的浮點數加法和乘法的基本運算次數.

Table 2 Analysis of the Model Complexity表2 模型復雜度分析

表2中的符號Ne和Nr分別表示知識圖譜中已有的實體數目與關系數目，N表示知識圖譜中已有的三元組總數，k表示實體向量空間的維度，d表示關系向量空間的維度.包括TransE在內的多數表達推理算法將實體和關系投影到相同維度的空間中(即k=d)，但也有部分算法采用不同維度的實體和關系向量表達(如TransR和CtransR算法).

從表2可以看出RESCAL模型和TransR模型的參數復雜度和計算時間復雜度均高出本文所提出的UWM算法和IWM算法約2個數量級(通常k和d的取值為102級別).同時可看出，UWM算法和IWM算法的參數復雜度與TransE相當(因為通常情況下Ne?Nr)，計算時間復雜度則比TransE算法高出約2個數量級.由此可見，本文提出2種關系推理算法的參數復雜度接近TransE算法，因此能夠保持TransE算法對訓練數據需求量較小，不易出現欠擬合問題的優點；計算時間復雜度則介于TransE和另外2種模型之間，但由于UWM算法和IWM算法不涉及張量運算和矩陣計算，因此易于實現并行，經GPU加速后，算法實際性能與TransE相當.因此，本文提出的關系推理算法簡單高效，實用性好.

3 實驗結果與分析

為驗證本文提出的基本假設的有效性，即知識圖譜中的關系可以通過對其相關聯的實體向量的方面要素進行選擇性加權來表達，本文選擇了4種近期在關系推理領域引起廣泛重視的相關工作進行實驗比較，包括基于張量分解的代表性模型RESCAL算法，基于表示學習的代表性模型TransE算法，以及在TransE基礎上改進得到的TransR算法和CTransR算法.并使用相關工作普遍采用的2組公開數據集對所提出的UWM算法和IWM算法進行測試.

① https://everest.hds.utc.fr/doku.php?id=en:transe

3.1實驗數據

本文所使用的實驗數據由法國貢比涅技術大學的Antoine Bordes等人整理并發布，分別稱為WN18和FB15k數據集①.數據統計信息如表3所示.

其中，WN18數據集從WordNet知識庫采樣得到，WordNet是一個基于認知語言學，且覆蓋范圍較廣的大型英文詞匯數據庫.WN18數據集包含18種關系類型、40 943個實體、151 442個三元組.上述三元組被隨機劃分為3組，分別用于模型參數訓練(Train)、模型驗證(Validation)和性能測試(Test).

FB15k數據集從Freebase采樣得到，Freebase早期的知識來源是維基百科，后來被谷歌收購并維護，是當前規模最大的開源通用型知識庫之一，知識范圍覆蓋現實世界中的各個方面.FB15k數據集包含1 345種關系、14 951個實體、592 213個三元組.同樣地，FB15k中的三元組被隨機劃分為3組.

Table 3 Statistics of the Benchmark Datasets表3 基準數據集的統計信息

由于WN18包含的關系種類較少，且FB15k的知識來源更為豐富，因此本文將重點使用FB15k數據集對算法性能進行比較分析.經統計，取η=1.5，FB15k中1∶1類型的三元組數量約占1.51%，1∶M類型的三元組約占15.26%，M∶1類型的三元組數量約占9.49%，M∶M類型的三元組約占73.74%.

3.2實驗方法與評估指標

對算法性能的測試與相關工作中所采用的實驗方法保持一致，即使用干擾列表排序法.對于測試集中的每一個三元組(h,ri,t)，枚舉知識圖譜中所有的實體，替換(h,ri,t)中的頭實體，從中過濾掉已知的事實(即知識圖譜中已有的三元組)，得到第1組干擾事實列表，稱為頭干擾列表為

hlist={(h′,ri,t)|?h′∈E∧(h′,ri,t)?Δ}，

(18)

類似地,構造尾干擾列表如下：

tlist={(h,ri,t′)|?t′∈E∧(h,ri,t′)?Δ}.

(19)

然后采用關系推理算法計算干擾列表中每個三元組的分值，并按照分值分別對頭、尾干擾列表進行排序，取給定事實(h,ri,t)在相應排序結果中所處的位置作為評估關系推理結果的基礎測度，分別記為rank(?,ri,t)和rank(h,ri,?).對二者求均值，得到關系推理算法對給定三元組的綜合預測排名：

(20)

得到綜合排名后，可進一步構造3種統計量對算法性能進行評估：首位命中率指標(hits@1)、前10命中率指標(hits@10)、平均倒數排名指標(mean reciprocal rank,MRR).hits@1定義如下：

(21)

其中，符號T表示測試集，|T|表示測試集中的三元組個數.ind(·)為指示函數，定義：

(22)

hits@1指標值表示排名第一的算法推理結果為正確知識的可能性，可以視為關系推理算法的準確率指標.類似地可以定義hits@10指標如下：

(23)

hits@10指標值表示正確結果出現在推理結果列表前10位(通常可接受的推薦列表長度)的概率，可以視為關系推理算法對知識的召回率指標.

進一步定義MRR指標的計算為

(24)

MRR指標表示對測試集中所有事實在推理結果列表中排名的倒數求平均值.由于給定事實在推理結果中的排名越靠前，其倒數值越大，因此MRR值越高，表明算法的推理性能也越好.但由于倒數取值范圍是(0,1]區間，所以排名靠后的結果對MRR值的影響較大，因此MRR值能夠全面反映算法的綜合表現.

3.3實驗結果與分析

本文所提出的UWM和IWM算法包含3個超參數需要在模型訓練之前加以確定：SGD算法的學習率α、邊界參數γ以及向量表達空間的維度k.

實驗前采用網格搜索法(grid search)對上述參數進行選擇.參考相關工作的實驗參數，設定α的搜索范圍為{0.01,0.005,0.001,0.000 5}，γ的范圍為{0.5,1.0,1.5,2.0}，k的范圍為{50,100,150,200}.在WN18和FB15k的驗證集上分別進行網格搜索，取hits@10指標最優時的參數組合作為本文的實驗參數：在WN18數據集上，參數取值為α=0.000 5，γ=1.0，k=50；在FB15k數據集上，參數取值為α=0.001，γ=1.5，k=150.在本文的所有實驗中，SGD算法迭代次數統一設置為1 000輪.

3.3.1 算法性能綜合評估

表4和表5分別給出了UWM和IWM算法與相關工作在WN18和FB15k這2個數據集上的實驗對比情況.表中每列指標中性能表現最好的一項用粗體標出.由于TransE算法可以看作是UWM和IWM算法中權重向量的元素取值全為1的情況，因此可作為Baseline算法，用于評估本文基本假設的有效性.

Table 4 Experimental Results on WN18 Dataset表4 WN18數據集上的實驗結果

Table 5 Experimental Results on FB15k Dataset表5 FB15k數據集上的實驗結果

由表4和表5可見，UWM算法和IWM算法在2個數據集的MRR和hits@1指標上的表現均一致且顯著優于參與比較的相關算法.在WN18數據集上的hits@10指標表現與TransE,TransR和CTransR算法相當，在FB15k數據集上的hits@10指標則再次表現出顯著優勢.初步表明本文提出的假設和算法有效.

通過對比UWM算法和IWM算法的性能表現可以看出，IWM算法在2組實驗中的所有性能指標上的表現均優于UWM算法，然而優勢并不顯著，除WN18數據集上的hits@1指標外，二者在其他性能指標上的差異小于5%.該結果表明，對同種類型關系兩側的實體向量分別進行加權處理，有助于提高關系推理算法的準確性和召回率.但由此帶來的性能提升并不顯著，意味著通過適當改進共享權重參數的估計方法，有可能達到同樣的效果.

為深入揭示UWM和IWM算法的相對優勢及其產生原因，接下來以IWM算法為代表，將其逐一與相關算法的實驗結果進行比對.由于基于張量分解的RESCAL算法在2組實驗中的表現顯著低于其余相關工作，因此將其排除在討論范圍之外.此外，TransR算法和CtransR算法的設計思路相近，因此本文將其合并進行討論.首先比較TransE和IWM算法.

如2.2節所述，TransE算法可以被視為IWM算法的特例，當IWM權重向量的所有元素均取值為1時，IWM算法退化為TransE算法.從實驗結果來看，在WN18和FB15k數據集上，IWM算法的MRR指標與TransE算法相比分別提高了41.01%和23.06%，說明IWM中引入的權重處理機制顯著地影響了正確結果(已知事實)在干擾列表中的分布，使之向列表的頂部偏移，從而進一步驗證了本文假設的合理性，即知識圖譜中的關系可以通過對其相關聯的實體向量的方面要素進行選擇性加權進行區分，通過合理建模，可以有效提升推理結果的準確率.

進一步對二者的準確率和召回率指標進行比對，可以看到在WN18和FB15k數據集上，IWM算法的hits@1指標與TransE算法相比分別提高了337.17%和38.60%；hits@10指標分別提高了6.05%和10.15%.該結果表明，新引入的假設能夠對推理模型的準確率和召回率同時產生積極影響，但對于算法準確率的影響更為顯著，說明該假設有助于提高表示學習模型對于同類型實體(出現在同種關系一側的實體集合)的分辨率，由此進一步證明本文提出的假設是有效的.

將IWM算法與TransR和CtransR二者中表現較好的結果進行比較，可以看到在WN18和FB15k數據集上，IWM的MRR指標分別提高了15.37%和44.16%；hits@1指標分別提高了47.46%和69.26%.hits@10指標分別提高了1.94%和22.60%.該結果表明，與將實體和關系分別映射到不同語義空間的TransR和CtransR算法相比，IWM算法的魯棒性更好，且對實體和關系語義差異的分辨能力更優.

綜上，與相關工作相比，本文提出的UWM和IWM算法在關系推理準確率指標(hits@1)上的優勢十分明顯，在WN18和FB15k數據集上與性能最接近的算法相比，準確率提高水平也超過了38.60%.此外，IWM算法在上述數據集上的推理準確率分別達到49.4%和41.3%，意味著在一般關系推理任務，用戶能夠以近40%的把握接受算法給出的第一項推理結果，因此具備良好的實際應用前景.

3.3.2 在不同關系類型上的性能分析

為進一步分析UWM和IWM算法性能優勢的成因，本文在FB15k數據集上做了關系分類實驗.首先，將FB15k測試集按照式(11)劃分成4類，然后分別對其進行關系推理實驗，結果如表6和表7所示.為便于分析比較，相關工作選擇了可被視為本文提出的算法特例的TransE算法和相關算法中綜合性能表現最好的CtransR算法作為實驗參考對象.

Table 6 Evaluation Results of hits@1 on FB15k Dataset

Table 7 Evaluation Results of hits@10 on FB15k Dataset

首先比較UWM和IWM算法的性能表現，可以看出在hits@1和hits@10指標上，二者在多數關系類型上的性能表現十分接近(差異小于5%)，僅在處理M∶1類型關系的頭干擾列表時表現出系統性差異，與UWM算法相比，IWM算法在hits@1指標上準確率高出14.15%，在hits@10指標上召回率高出6.30%.然而，考察與之相對應的1∶M類型關系尾干擾列表，可以看出IWM算法在上述2個指標上只分別高于UWM算法5.45%和1.64%.該結果表明，造成上述性能表現差異的原因可能與測試數據分布和訓練數據量不足有關，并不足以證明IWM算法比UWM算法的性能更優，對此將在下一步工作中加以驗證.

接下來考察本文提出的UWM和IWM算法與TransE和CtransR算法的性能對比.從表6可以看出，相對于另外2個參考算法，UWM和IWM算法在所有8個子項上的推理準確率表現都占據了明顯的優勢，尤其是在處理1∶M和M∶1關系類型時，準確率提升更為顯著.該實驗結果進一步表明本文提出的算法能夠有效提升實體與關系的向量表達的準確性，從而提高實體分辨率，同時也間接說明本文提出的基本假設具有合理性，即可以通過對關系兩側的實體向量中包含的方面要素進行加權組合，獲得對關系的向量表達.同樣的情況也出現在表7的實驗結果中，本文提出的2種算法，在4種關系類型的召回率指標上也全面占優，在處理1∶M和M∶1關系類型的優勢更為顯著.進一步驗證了本文假設的有效性.

值得注意的是，盡管實驗數據證明了UWM和IWM算法能夠克服部分TransE基本假設存在的問題，提高算法對實體和關系語義的分辨能力，從而大幅提升關系推理準確率，但是從表6和表7的實驗數據不難看出，UWM和IWM算法在處理1∶M和M∶1關系類型數據時，同樣存在明顯的性能不均衡性.例如，UWM算法在處理1∶M關系類型的頭干擾列表時，hits@1準確率達到70.7%，但在處理M∶1類型的頭干擾列表時，hits@1準確率只有20.5%.類似的情況在表6右側的尾干擾列表，以及表7中均可以觀察到.該結果表明，本文提出的建模假設僅揭示了部分客觀規律，并沒有完全解決TransE基本假設中存在的矛盾問題.然而，從實驗結果所反饋的積極信號來看，本文的工作在一定程度上觸及了問題的本質，為下一步工作提供了一個有希望的參考解決方案.

4 結束語

本文研究了知識圖譜上的關系推理問題，指出了當前基于表示學習的關系推理模型所普遍采用的基本假設存在理論問題，并據此提出了新的建模假設和數學模型.在WN18和FB15k等基準數據集上的仿真實驗表明，本文所提出的算法在所有指標上的性能表現一致且顯著優于本領域的代表性工作，且算法計算效率高，可適用于大規模知識圖譜關系推理任務.

該工作為研究基于表示學習的關系推理算法提供了新的建模思路和解決方案，同時也留下了一些值得繼續研究的問題，比如：IWM所采用的獨立加權方式是否優于UWM所采用的共享參數方式；本文提出的算法為什么在大幅提高1∶M和M∶1關系類型推理準確率的同時，卻未能消除算法對關系兩側實體的推理能力的不均衡問題.在后續工作中，將針對上述問題開展進一步研究，目標是提出更為合理的關系推理建模思路和設計更為高效的推理算法.

[1] Nickel M, Murphy K, Tresp V, et al. A review of relational machine learning for knowledge graphs[J]. Proceedings of the IEEE, 2016, 104(1): 11-33

[2] Liu Qiao, Li Yang, Duan hong, et al. Knowledge graph construction techniques[J]. Journal of Computer Research and Development, 2016, 53(3): 582-600 (in Chinese)(劉嶠, 李楊, 段宏, 等. 知識圖譜構建技術綜述[J]. 計算機研究與發展, 2016, 53(3): 582-600)

[3] Wang Yuanzhuo, Jia Yantao, Liu Dawei, et al. Open web knowledge aided information search and data mining[J]. Journal of Computer Research and Development, 2015, 52(2): 456-474 (in Chinese)(王元卓, 賈巖濤, 劉大偉, 等. 基于開放網絡知識的信息檢索與數據挖掘[J]. 計算機研究與發展, 2015. 52(2): 456-474)

[4] West R, Gabrilovich E, Murphy K, et al. Knowledge base completion via search-based question answering[C] //Proc of the 23rd Int World Wide Web Conf. New York: ACM, 2014: 515-526

[5] Liu zhiyuan, Sun Maosong, Lin Yankai, et al. Knowledge representation learning: A review[J]. Journal of Computer Research and Development, 2016, 53(2): 247-261 (in Chinese)(劉知遠, 孫茂松, 林衍凱, 等. 知識表示學習研究進展[J]. 計算機研究與發展, 2016. 53(2): 247-261)

[6] Dong X, Gabrilovich E, Heitz G, et al. Knowledge vault: A Web-scale approach to probabilistic knowledge fusion[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM. 2014: 601-610

[7] Liu Qiao, Jiang Liuyi, Han Minghao, et al. Hierarchical random walk inference in knowledge graphs[C] //Proc of the 39th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2016: 445-454

[8] Getoor L, Mihalkova L. Learning statistical models from relational data[C] //Proc of the 2011 ACM SIGMOD Int Conf on Management of data. New York: ACM, 2011: 1195-1198

[9] Richardson M, Domingos P. Markov logic networks[J]. Machine Learning, 2006, 62(1): 107-136

[10] Friedman N, Getoor L, Koller D, et al. Learning probabilistic relational models[C] //Proc of IJCAI 1999. San Francisco, CA: Morgan Kaufmann, 1999: 1300-1309

[11] Schoenmackers S, Etzioni O, Weld D S, et al. Learning first-order horn clauses from web text[C] //Proc of the 2010 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2010: 1088-1098

[12] Lao Ni, Mitchell T, Cohen W W. Random walk inference and learning in a large scale knowledge base[C] //Proc of the 2011 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2011: 529-539

[13] Gardner M, Mitchell T. Efficient and expressive knowledge base completion using subgraph feature extraction[C] //Proc of the 2015 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2015: 1488-1498

[14] Pennington J, Socher R, Manning C D. GloVe: Global vectors for word representation[C] //Proc of the 2014 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2014: 1532-1543

[15] Mikolov T, Sutskever I, Chen Kai, et al. Distributed representations of words and phrases and their compositionality[C] //Proc of the 26th Int Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2013: 3111-3119

[16] Bordes A, Usunier N, Garcia-Duran A, et al. Translating embeddings for modeling multi-relational data[C] //Proc of the 27th Annual Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2013: 2787-2795

[17] Nickel M, Tresp V, Kriegel H-P. A three-way model for collective learning on multi-relational data[C] //Proc of the 28th Int Conf on Machine Learning. New York: ACM, 2011: 809-816

[18] Bordes A, Weston J, Collobert R, et al. Learning structured embeddings of knowledge bases[C] //Proc of the 25th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2011

[19] Wang Zhen, Zhang Jianwen, Feng Jianlin, et al. Knowledge graph embedding by translating on hyperplanes[C] //Proc of the 28th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2014: 1112-1119

[20] Fan Miao, Zhou Qiang, Chang Emily, et al. Transition-based knowledge graph embedding with relational mapping properties[C] //Proc of Pacific Asia Conf on Language, Information and Computation. Stroudsburg, PA: ACL, 2014: 328-337

[21] Lin Yankai, Liu Zhiyuan, Sun Maosong, et al. Learning entity and relation embeddings for knowledge graph completion[C] //Proc of the 29th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2015: 2181-2187

[22] Socher R, Chen Danqi, Manning C D, et al. Reasoning with neural tensor networks for knowledge base completion[C] //Proc of the 27th Conf on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2013: 926-934

[23] Lin Yankai, Liu Zhiyuan, Luan Hanbo, et al. Modeling Relation Paths for Representation Learning of Knowledge Bases[C] //Proc of the 2015 Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2015: 705-714

RepresentationLearningBasedRelationalInferenceAlgorithmwithSemanticalAspectAwareness

Liu Qiao, Han Minghao, Yang Xiaohui, Liu Yao, and Wu Zufeng

(SchoolofInformationandSoftwareEngineering,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054)

Knowledge representation based relational inference algorithms is a crucial research issue in the field of statistical relational learning and knowledge graph population in recent years. In this work, we perform a comparative study of the prevalent knowledge representation based reasoning models, with detailed discussion of the general potential problems contained in their basic assumptions. The major problem of these representation based relational inference models is that they often ignore the semantical diversity of entities and relations, which will cause the lack of semantic resolution to distinguish them, especially when there exists more than one type of relation between two given entities. This paper proposes a new assumption for relation reasoning in knowledge graphs, which claims that each of the relations between any entity pairs reflects the semantical connection of some specific attention aspects of the corresponding entities, and could be modeled by selectively weighting on the constituent of the embeddings to help alleviating the semantic resolution problem. A semantical aspect aware relational inference algorithm is proposed to solve the semantic resolution problem, in which a nonlinear transformation mechanism is introduced to capture the effects of the different semantic aspects of the embeddings. Experimental results on public datasets show that the proposed algorithms have superior semantic discrimination capability for complex relation types and their associated entities, which can effectively improve the accuracy of relational inference on knowledge graphs, and the proposed algorithm significantly outperforms the state-of-the-art approaches.

statistical relational learning; relational inference; representation learning; knowledge graphs; multi-relational data mining

Liu Qiao, born in 1974. PhD and associate professor. Member of CCF. His main research interests include machine learning and data mining, natural language processing, and social network analysis.

Han Minghao, born in 1992. Mater. Student member of CCF. His main research interests include natural language processing and machine learning (hanmhao@gmail.com).

Yang Xiaohui, born in 1993. Mater. Her main research interests include machine learning, natural language processing and data mining (yangxhui@std.uestc.edu.cn).

Liu Yao, born in 1978. PhD and Lecturer. Member of CCF. Her main research interests include social network analysis, machine learning, data mining, and network measurement (liuyao@uestc.edu.cn).

Wu Zufeng, born in 1978. PhD and Engineer. Member of CCF. His main research interests include machine learning, data mining, and information security (wuzufeng@uestc.edu.cn).

2017-03-20；

：2017-05-15

國家自然科學基金項目(61133016,U1401257)；四川省高新技術及產業化面上項目(2017GZ0308) This work was supported by the National Natural Science Foundation of China (61133016,U1401257) and the General Program of the Sichuan Province High-Technology Industrialization (2017GZ0308).

TP391