基于分布式表示和多特征融合的知識庫三元組分類

安 波，韓先培，孫 樂，吳 健

(中國科學院 軟件研究所 中文信息處理研究室，北京 100190)

基于分布式表示和多特征融合的知識庫三元組分類

安 波，韓先培，孫 樂，吳 健

(中國科學院 軟件研究所 中文信息處理研究室，北京 100190)

三元組分類是知識庫補全及關(guān)系抽取的重要技術(shù)。當前主流的三元組分類方法通?；赥ransE來構(gòu)建知識庫實體和關(guān)系的分布式表示。然而，TransE方法僅僅適用于處理1對1類型的關(guān)系，無法很好的處理1對多、多對1及多對多類型的關(guān)系。針對上述問題，該文在分布式表示的基礎(chǔ)上，提出了一種特征融合的方法—TCSF，通過綜合利用三元組的距離、關(guān)系的先驗概率及實體與關(guān)系上下文的擬合度進行三元組分類。在四種公開的數(shù)據(jù)集(WN11、WN18、FB13、FB15K)上的測試結(jié)果顯示，TCSF在三元組分類上的效果超過現(xiàn)有的state-of-the-art模型。

知識庫；深度學習；三元組分類

1 引言

知識庫是人工智能和自然語言處理的關(guān)鍵資源，在問答系統(tǒng)、智能檢索及情感分析等領(lǐng)域起到重要的作用。目前已經(jīng)有許多知名的大規(guī)模知識庫，如FreeBase、WordNet等。然而，考慮到知識的規(guī)模和更新速度，現(xiàn)有知識庫的覆蓋度仍然無法達到要求。因此，知識庫補全(Knowledge base completion)在近幾年成為了熱門國際評測任務。三元組分類是知識庫補全的關(guān)鍵技術(shù)之一，由Socher[1]等人首先提出。給定三元組(head,relation,tail)，head和tail表示頭部和尾部實體，relation表示實體之間的關(guān)系。三元組分類的目的是計算三元組的置信度，從而判斷該三元組所表示的語義關(guān)系是否為真，如果該三元組為真，則該三元組(head,relation,tail)將被加入到知識庫。

目前大部分三元組分類系統(tǒng)首先將知識庫中的實體和關(guān)系編碼到低維向量空間，并基于這些連續(xù)向量構(gòu)建置信度模型對三元組進行打分。具體地，對于知識庫中的任意實體，使用一個實數(shù)向量進行表示，知識庫中的任意關(guān)系也一個實數(shù)向量(維度可以與實體向量的不同)來表示。對知識庫的分布式表示任務，TransE[2]是目前效果較好的模型，且時間復雜度較低。但是，就像TransM[3]中指出的那樣，TransE并不適于處理1對多(1-to-N)、多對1(M-to-1)及多對多(M-to-N)類型的關(guān)系。與此同時知識庫中的大多數(shù)關(guān)系都不是1對1(1-to-1)類型的。本文針對知識庫補全任務中常用的四個數(shù)據(jù)集中的關(guān)系進行統(tǒng)計分析，分別是WN11[1]、WN18[2]、FB13[1]和FB15K[2]，其中WN11和WN18抽取自WordNet*http://www.princeton.edu/wordnet數(shù)據(jù)集，F(xiàn)B13和FB15K抽取自Freebase*http://www.freebase.com數(shù)據(jù)集,其結(jié)果如表1所示。從表1中可以看出，WN11數(shù)據(jù)集中的所有11種關(guān)系均為多對多(M-to-N)類型的關(guān)系；WN18數(shù)據(jù)集中的所有18中關(guān)系也全都屬于多對多(M-to-N)類型的關(guān)系；FB13數(shù)據(jù)集中包含一種多對1(M-to-1)的關(guān)系和12中多對多(M-to-N)的關(guān)系；FB15K數(shù)據(jù)集中包含1 345種關(guān)系，其中只有247種關(guān)系為1對1(1-to-1)類型的關(guān)系，其余的均為1對多、多對1及多對多類型的關(guān)系。因此，在上述的四種數(shù)據(jù)集中，絕大多數(shù)關(guān)系屬于非簡單的1對1關(guān)系。因此，我們認為，TransE模型由于不能很好的編碼知識庫中的1對多(1-to-N)、多對1(M-to-1)、多對多(M-to-N)類型的關(guān)系，僅僅依賴于三元組距離|h+r-t|來計算三元組的置信度的現(xiàn)有模型，無法很好的建模多種復雜的關(guān)系。

表1 知識庫關(guān)系分類信息

針對上述問題，本論文在知識庫分布式表示的基礎(chǔ)上，提出了一種多特征融合的方法—TCSF，綜合利用三元組的距離、關(guān)系的先驗概率及實體與關(guān)系上下文的擬合度來進行分類。具體地，TCSF通過兩個啟發(fā)式規(guī)則來解決上述問題： 1)先驗規(guī)則： 一個關(guān)系在知識庫中出現(xiàn)的次數(shù)越多，則給定的實體對(h,t)具有該關(guān)系的可能性就越高；2)實體對(h,t)與給定關(guān)系r上下文擬合程度越高，則該三元組(h,r,t)的置信度越高。本文提出的方法是在知識的分布式表示基礎(chǔ)上利用關(guān)系的先驗信息和關(guān)系的上下文特征針對三元組分類任務進行的優(yōu)化，該方法不針對具體的模型，可以對TransE、TransH等基于翻譯的關(guān)系表示模型進行結(jié)果優(yōu)化。

本文在上述四個數(shù)據(jù)集上進行了實驗。實驗結(jié)果表明，相比于TransE[2]及其他state-of-the-art模型，本文提出的方法能夠大幅提升三元組分類的效果。

2 相關(guān)工作

目前大部分三元組分類方法包含兩個模塊： 1)如何將三元組(h,r,t)中的關(guān)系和實體映射為低維向量或矩陣表示；2)如何構(gòu)建損失函數(shù)fr(h,t)對三元組的置信度進行打分。以下分別從上述兩個模塊介紹現(xiàn)有的不同方法。

UnstructuredModel[4]是一個較為樸素的模型，該模型基于頭部實體h和尾部實體t共現(xiàn)的信息來對知識庫中的實體進行編碼，但不對關(guān)系進行編碼，其損失函數(shù)如式(1)所示。

DistanceModel[5]與UM模型類似，但是增加了對關(guān)系的編碼。該模型將知識庫中的每個關(guān)系編碼為兩個矩陣(Wrh,Wrt)，其損失函數(shù)如式(2)所示。

SingleLayerModel[1]通過單層的神經(jīng)網(wǎng)絡(luò)來對DM模型進行改進，該模型的損失函數(shù)如式(3)所示，其中g(shù)為tanh函數(shù)。

BilinearModel[6]通過增強三元組中實體對之間的交互關(guān)系來改善DM模型，該模型將關(guān)系編碼為一個矩陣，實體編碼為向量，其損失函數(shù)如式(4)所示。

NeuralTensorNetwork[1]是當前較為有效的模型，NTN模型結(jié)合SLM和BM模型的優(yōu)點，其損失函數(shù)如式(5)所示。該模型的主要缺點是模型參數(shù)較多，時間復雜度高。結(jié)合式(3)、式(4)、式(5)可以看出，NTN模型是SLM模型及BM模型的組合優(yōu)化。

TransE[2]是近期提出的一種簡單高效的編碼方式，該模型將關(guān)系看作是從頭部實體到尾部實體的轉(zhuǎn)移，將知識庫中的實體和關(guān)系編碼到相同維度的向量空間，并假設(shè)h+r-t≈0。其損失函數(shù)如式(6)所示。TransE以較低的時間復雜度取得了較好的效果，后續(xù)的方法大多數(shù)是基于TransE的改進。

TransM[3]通過為每個關(guān)系增加一個權(quán)重因子wr來改進TransE模型，其中wr的計算方法如式(7)所示。該模型的損失函數(shù)如式(8)所示。其中hrptr表示:對于每個關(guān)系r，其尾部實體t對應的頭部實體的h的個數(shù)。

TransH[7]通過將知識庫中的實體和關(guān)系編碼到不同維度向量來處理非1對1類型的關(guān)系。在該模型中，每個關(guān)系使用一個轉(zhuǎn)移向量和一個映射向量來表示。映射向量用于將實體向量映射為與關(guān)系向量同維度的向量。其映射函數(shù)及損失函數(shù)如式(9)、式(10)所示。

TransR[8]與TransH類似，該模型將知識庫中的關(guān)系用一個轉(zhuǎn)移向量和一個映射矩陣表示。通過映射矩陣與實體向量的運算，完成從實體空間到關(guān)系空間的映射，其損失函數(shù)如式(11)、式(12)所示。

IIKE[9]將三元組看作實體h、關(guān)系r和實體t之間的聯(lián)合概率，該模型的概率計算函數(shù)如式(13)所示。

綜上所述，目前大部分模型通過優(yōu)化TransE[2]的損失函數(shù)來改善知識庫編碼，進而改善三元組分類效果。但是上述模型在三元組分類的時候，只使用了實體和關(guān)系的分布式表示。分布式表示存在缺乏先驗知識和知識庫本身不完整的缺點，導致僅依靠知識庫的分布式表示很難取得很好的效果。針對分布式表示的這種問題，本文提出，綜合三元組的距離、關(guān)系的先驗概率及實體與關(guān)系上下文的擬合度來提高分類準確率。

3 基于分布式表示和多特征融合的三元組分類方法

為解決前文中提到的問題，我們首先對TransE模型進行分析以得出解決方案。首先，根據(jù)TransE的損失函數(shù)式(6)可知，當兩個實體h1和t1之間存在兩種不同關(guān)系r1和r2時，有(h1,r1,t1) ∈△+且 (h1,r2,t1) ∈△+，從而可以得到h1+r1-t1≈0和h1+r2-t1≈0。依次可以推出r1≈r2。此時，當知識庫中存在三元組(h2,r1,t1) ∈△+，則可以推出h2+r1-t1≈0，結(jié)合上面推出的r1≈r2，可以推出h2+r2-t1≈0，推出(h2,r2,t1) ∈△+。但是h2和t1并不一定具有r2關(guān)系。具體的例子如下：

(Obama,born_in,USA) ∈△+、 (Obama,president_of,USA) ∈△+

(Justin_Biber,born_in,USA) ∈△+

本文對四個常用的數(shù)據(jù)集進行統(tǒng)計分析，其結(jié)果如表2所示。從表中可以看出，數(shù)據(jù)集中實體對具有不同關(guān)系的情況普遍存在，且在FB13和FB15K特別明顯。由上述分析可推出，當一個實體對具有多種不同關(guān)系的時候，TransE[2]會將其編碼到相似在進行三元組分類時，通過式(6)計算給定(h,r,t)的距離。但當實體對具有關(guān)系r′，且r′與r的編碼相似時，就會錯誤的將三元組(h,r,t)判定為真。因此，解決上述問題的關(guān)鍵是如何正確的區(qū)分編碼相近的關(guān)系。針對該問題，本文通過啟發(fā)式的方法來對相似空間的不同關(guān)系進行區(qū)分，以提高三元組分類的準確率。本文使用的啟發(fā)式規(guī)則包括關(guān)系的先驗概率和關(guān)系的上下文。在分布式表示模型中，實體或者關(guān)系之間語義的相似度通常使用計算向量之間的相似度表示。具體地，TCSF使用歐幾里得距離式(14)來計算兩個關(guān)系的相似度。

表2 數(shù)據(jù)集統(tǒng)計信息

注： “#”表示數(shù)量；“&”表示“與”關(guān)系；的空間，容易引起錯誤的分類。

3．1 關(guān)系的先驗概率

本文使用的第一個啟發(fā)式規(guī)則是關(guān)系的先驗概率，即一個關(guān)系出現(xiàn)的次數(shù)越多，則實體對(h,t)具有該關(guān)系的概率就越大。給定候選三元組(h,r,t)，本文通過對比給定關(guān)系r最相似的關(guān)系r′來確定關(guān)系r的先驗概率，如式(15)所示。

其中Nr是關(guān)系r在訓練集中出現(xiàn)的次數(shù)，Nr′是與關(guān)系r最相似的關(guān)系。本文只考慮最相似關(guān)系的原因是相似的關(guān)系得到損失值較為類似，容易引起錯誤分類。當關(guān)系的表示相似度差別較大的時候，根據(jù)式(6)不容易產(chǎn)生誤分類。

Algorithm1ThetripleclassificationofTCSFInput:TrainingsetT={(h,r,t)},validsetV={(h,r,t)},testsetS={(h,r,t)},entitiesandrelationssetEandR,marginγ,embeddingdim.d,normL1/L2,stepsizest,epocheep,threshold.RunTransEandgeneratetheembeddingsofentitiesandrelationsforeachr∈R //對于每個關(guān)系,計算出其頭部實體和尾部實體的均值sim(r)=min{dis(r',r)},r'∈Randr'≠ravgHead(r)=1n∑ni=1h,h∈Hrandn=|Hr|avgTail(t)=1n∑ni=1t,t∈Htandn=|Ht|foreach(h,r,t) ∈Sdo //結(jié)合翻譯距離及先驗概率計算三元組的可信性 iffr(h,t)plausible((h,t),r') (h,r,t) ispositive else (h,r,t) ispositive endif endif endifendforeach

3．2 關(guān)系的上下文

TransE[2]進行訓練時，訓練集中的每個三元組(h,r,t)作為正例，負例通過隨機替換實體h或t構(gòu)造。該方法類似于Word Embedding中的訓練方法?；谏鲜鲇懻?，我們認為所有具有關(guān)系r的實體對集合{(h1,t1),(h2,t2), …}就構(gòu)成了關(guān)系r表示的上下文。在計算(h,r, t)三元組打分的時候，我們可以不僅僅使用關(guān)系r的表示，同時也可以計算實體對(h,t)與r的上下文之間的匹配程度。

具體地，本文將關(guān)系r的上下文表示為具有關(guān)系r的三元組的頭部實體編碼向量的均值表示及尾部實體的均值表示。向量的均值反應了該關(guān)系對應的頭部實體和尾部實體的主要特征，如關(guān)系born_in對應的頭部實體通常為人名，尾部實體通常為地名。根據(jù)TransE[2]得到的結(jié)果分析可知，相同類型的實體會編碼到比 較相近的區(qū)域，如人名會較為集中的分布在一個區(qū)域，地名也會被集中的分布式另外一個區(qū)域。因此，給定一個三元組(h,r,t)，實體對(h,t)與關(guān)系r的合理程度可以通過判斷頭部實體h和尾部實體t與關(guān)系r對應的頭部實體和尾部實體的均值(關(guān)系的上下文)的擬合度來判斷。當實體與關(guān)系的上下文擬合度較低的時候，則該三元組的置信度較低。上下文的擬合度可以通過式(16)計算得到。

3．3 算法

TCSF利用關(guān)系的先驗概率和實體對與關(guān)系上下文的擬合度的對相似的關(guān)系進行區(qū)分，計算方法如式(17)所示。Algorithm 1是模型的簡化算法。

4 實驗

4．1 實驗數(shù)據(jù)

本文使用四個常用的數(shù)據(jù)集來測試模型的效果，分別是WN11[1]、WN18[2]、FB13[1]和FB15K[2]，這些數(shù)據(jù)摘自WordNet和FreeBase知識庫。在TransE[2]的實驗設(shè)計中，測試集中的負例是通過隨機的替換三元組的頭部實體或者尾部實體進行構(gòu)造。為了構(gòu)建質(zhì)量更高的測試數(shù)據(jù)，本文采用Socher[1]等人提出的方法。在進行實體替換時，替換的實體應該在相應的位置出現(xiàn)過，且不能是已經(jīng)存在知識庫中的三元組。例如，當替換頭部實體時，該實體在訓練集中作為頭部實體出現(xiàn)過。WN11、FB13及FB15K數(shù)據(jù)集，我們直接使用Fan[3]等人公開的數(shù)據(jù)。本文根據(jù)Fan[3]中的方法構(gòu)建了WN18的驗證集和測試集。四種數(shù)據(jù)集的統(tǒng)計信息如表2所示。

4．2 實驗結(jié)果

本文與主流的幾種方法進行比較，包括TransE[2]、TransM[3]、TransH[7]、TransR[8]。因為實現(xiàn)和參數(shù)調(diào)整的問題，我們沒有得到相應論文中的最好結(jié)果，因此本文直接使用各個模型在相應論文中的最優(yōu)準確率作為對比依據(jù)。為了減少因為參數(shù)隨機初始化對結(jié)果造成的影響，本文對每一組參數(shù)都進行十次實驗，并取其平均值和最優(yōu)值作為最終的結(jié)果。通過多次實驗驗證，得到每種數(shù)據(jù)集的參數(shù)，(d=200, γ=2.0, st=0.02, ep =300 for WN11; d=200, γ=1.0, st=0.003, ep =10 for WN18; d=100, γ=2.0, st=0.03, ep =20 for FB13; d=400, γ=3.0, st=0.002, ep =30 for FB15k)。d代表實體和關(guān)系的維度、γ是margin值、st為初始的學習率、ep是迭代的次數(shù)。

三元組分類任務使用準確率作為評價指標，計算方法如式(18)所示。式中Tp和Tn表示預測正確的正例數(shù)和負例數(shù)，Npos和Nneg代表訓練集中的正例數(shù)和負例數(shù)。ACC越高表示系統(tǒng)預測的準確率越好，其計算方法如式(18)所示。

實驗結(jié)果如表3所示，TCSF在四種數(shù)據(jù)集上的最優(yōu)結(jié)果明顯高于其他系統(tǒng)。但平均值在FB15K上略低于IIKE[9]和TransR[8]。本文提出的方法是在TransE[2]上的改進，實驗結(jié)果顯示(表4中第一行TransE的結(jié)果來來自文獻[8]，TransE-avg和TransE-best的結(jié)果來自于本文的實現(xiàn))，在四種數(shù)據(jù)集上的三元組分類的準確率的均值和最高值能提升十個以上的百分點。

表3 模型在不同數(shù)據(jù)集上的準確率

注： “avg”表示10次實驗的平均值；“best”表示十次實驗的最好值。

為了驗證我們的方法在不同類型上的關(guān)系上的效果，我們在FB15K上針對不同類型的關(guān)系進行了三元組分類任務，因為該數(shù)據(jù)集包含的關(guān)系數(shù)量較多，且如表1所示，包含全部四種類型的關(guān)系。得到的結(jié)果如表4所示，從表4中可以看出，我們的方法相對于TransE在1-N、M-1和M-N類型的關(guān)系上取得了明顯的提升，在1-1類型的關(guān)系上的準確率沒有變化。因此我們的方法可以有效的提高非1-1類型的關(guān)系的分類準確率。

表4 模型在FB15K中不同關(guān)系類型上的結(jié)果

在本文中，我們主要利用了關(guān)系的先驗概率和關(guān)系的上下文兩種特征來增強三元組分類的準確性，為了更好的分析不同的特征在不同類型的關(guān)系類型中的效果，本文通過在TransE訓練的分布式表示上分別增加不同別的特征在三元組分類任務上進行測試，結(jié)果如表5所示。

表5 不同特征在FB15K中不同關(guān)系類型上的結(jié)果

注： TransE+Prop表示在TransE的基礎(chǔ)上增加先驗特征；TransE+Context表示在TransE的基礎(chǔ)上增加關(guān)系上下文特征；

通過表5的結(jié)果可以看出，關(guān)系的先驗特征能夠在1對多(1-to-N)、多對1(M-to-1)、多對多(M-to-N)類型的關(guān)系上改進三元組分類的效果；關(guān)系的上下文特征也可以在1對多(1-to-N)、多對1(M-to-1)、多對多(M-to-N)類型的關(guān)系上改進三元組分類的效果。并且通過結(jié)果的對比可知，關(guān)系的上下文比關(guān)系的先驗概率對結(jié)果的提高更明顯，并且兩種特征的疊加可以取得更號的結(jié)果。

通過表3～表5的結(jié)果可知，本文提出的方法基于TCSF能夠很大程度上提高三元組分類的效果，我們提出方法有三個關(guān)鍵貢獻。

(1) 我們的方法能夠很大程度的提高三元組分類的結(jié)果，產(chǎn)生新的state-of-the-art的結(jié)果。

(2) 我們通過對比不同的特征對不同類型的關(guān)系上的分類效果，更直觀的反映了不同的特征在三元組分類中的作用。

(3) 本文提出的方法是在知識表示的基礎(chǔ)上針對三元組分類任務的擴展，不僅可以在TransE上使用，也可以在TransM、TransH等模型上使用，具有較好的通用性。

5 結(jié)束語

本文在知識庫分布式表示的基礎(chǔ)上提出了一種特征融合的方法，從而有效提高三元組分類的準確率。實驗結(jié)果顯示，TransE[2]等系統(tǒng)無法很好的建模非1對1類型的關(guān)系。本文通過加入關(guān)系的先驗知識和關(guān)系的上下文特征，能夠有效提高三元組分類上準確率，驗證了不同的特征對不同類型關(guān)系的分類效果。

[1] R Socher, D Chen, C D Manning, et al. Reasoning with neural tensor networks for knowledge base completion[C]//Proceedings of the Advances in Neural Information Processing Systems，2013：926-934.

[2] A Bordes, N Usunier, A Garcia-Duran, et al. Translating embeddings for modeling multi-relational data[C]//Proceedings of the Advances in Neural Information Processing Systems，2013：2787-2795.

[3] Miao Fan, Qiang Zhou, Emily Chang, et al. Transition-based Knowledge graph embedding with relation mapping properties[C]//Proceedings of the PACLIC，2014：328-337.

[4] Bordes A,Glorot X, Weston J, et al. A semantic matching energy function for learning with multirelational data[J]. Machine Learning，2014,(2)：1-27.

[5] A Bordes, J Weston, R Collobert, et al. Learning structured embeddings of knowledge bases[C]//Proceedings of the AAAI，2011：201-306.

[6] I Sutskever, R Salakhutdinov, J B Tenenbaum. Modelling relational data using bayesian clustered tensor factorization[C]//Proceedings of the NIPS，2009：1821-1828.

[7] Wang Z, Zhang J, Feng J, et al. Knowledge graph embedding by translating on hyperplanes[C]//Proceedings of AAAI，2014：1112-1119.

[8] Yankai Lin, Zhiyuan Liu, Maosong Sun, et al. Learning entity and relation embeddings for knowledge graph completion[C]//Proceedings of the AAAI，2015：2181-2187.

[9] Miao Fan, Kai Cao, Yifan He. Jointly Embedding Relations and Mentions for Knowledge Population[J]. arXiv preprint，2015：arXiv:1504.01683.

[10] Socher R, Chen D, Manning C D, et al. Reasoning with neural tensor networks for knowledge base completion[C]//Proceedings of NIPS，2013：926-934.

[11] Bengio Y, Ducharme R, Vincent P, et al. A neural probabilistic language model[J]. JMLR，2003, 3:1137-1155.

[12] Jenatton R, Roux N L, Bordes A, et al. A latent factor model for highly multi-relational data[C]//Proceedings of NIPS，2012：3167-3175.

Triple Classification Based on Synthesized Features for Knowledge Base

AN Bo, HAN Xianpei, SUN Le, WU Jian

(Laboratory of Chinese Information Processing, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

Triple classification is crucial for knowledge base completion and relation extraction. However, the state-of-the-art methods for triple classification fail to tackle 1-to-n, m-to-1 and m-to-n relations. In this paper, we propose TCSF (Triple Classification based on Synthesized Features) method, which can joint exploit the triple distance, the prior probability of relation, and the context compatibility between entity pair and relation for triple classification. Experimental results on four datasets (WN11, WN18, FB13, FB15K) show that TCSF can achieve significant improvement over TransE and other state-of-the-art triple classification approaches.

knowledge base； deep learning； triple classification

安波(1986—),博士研究生,主要研究領(lǐng)域為自然語言處理和知識表示。E-mail:anbo@nfs.iscas.ac.cn韓先培(1984—),副研究員,主要研究領(lǐng)域為信息抽取、知識庫構(gòu)建以及自然語言處理。E-mail:hanxianpei@qq.com孫樂(1971—),研究員,博士生導師,主要研究領(lǐng)域為信息檢索和自然語言處理。E-mail:lesunle@163.com

1003-0077(2016)06-0084-06

2016-09-01 定稿日期： 2016-10-16

國家自然科學基金(61540057，61433015，61272324，61572477)；青海省自然科學基金(2016-ZJ-Y04，2016-ZJ-740)

TP391

A