陳 恒,韓雨婷,李冠宇,王京徽

(1.大連海事大學 信息科學技術學院,遼寧 大連 116026; 2.大連外國語大學 軟件學院,遼寧 大連 116044)

0 概述

Freebase[1]、Wordnet[2]、DBpedia[3]、YAGO[4]和NELL[5]等知識圖譜(Knowledge Graph,KG)在解決人工智能(Artificial Intelligence,AI)任務方面起著重要作用。然而,手動和自動構建的KG遠未達到十分完備的狀態(tài)[6-7],例如,在Freebase中75%的人缺失國籍,71%的人缺失出生地[8]。因此,知識推理(圖譜中隱含知識的挖掘)成為知識圖譜研究的熱點問題。

本文基于知識圖譜實體對間路徑信息的分析,提出一種基于多級關系路徑語義組合的關系推理算法,研究利用路徑信息進行關系推理,提高知識圖譜補全質量。

1 相關工作

1.1 知識圖譜補全方法

在經典的知識圖譜補全方法中,文獻[9]提出一種PRA算法,該算法利用知識圖譜的圖結構特征,通過隨機游走的方式計算實體間關系存在的概率進行關系推理,但PRA在實體空間中進行,計算代價高,且擴展性較差。文獻[10]提出一種基于翻譯的TransE模型,該模型將知識圖譜嵌入到低維向量空間,同時認為具有語義相關的實體在空間中的距離也是相近的。因此,通過判斷頭實體與關系的向量之和是否接近于尾實體向量來對實體間的關系進行推理和判斷,進而補全知識圖譜,取得了較好的效果。雖然TransE模型精確性高、擴展性好,但僅限于實體間的直接關系,對多級路徑關系這種隱藏知識的推理表現不足。文獻[11]提出一種基于強化學習的推理方法,利用Agent和環(huán)境間的交互,在獎勵函數機制下,學習獲得兩個實體間的路徑,通過符號邏輯進行關系推理,但該方法并未考慮路徑上的實體和關系的特征。文獻[12]提出一種組合向量空間模型,將路徑上的關系組合進而推理實體對間的關系,忽略了路徑上的實體信息。文獻[13]提出一種基于循環(huán)神經網絡(Recurrent Neural Network,RNN)模型,其通過對關系路徑進行建模,充分利用了路徑上實體和關系的信息。由于該方法在路徑發(fā)現過程中依賴于PRA算法,雖然提高了精確性,但計算代價也相對較高。

1.2 知識圖譜表示學習

知識表示學習[14-15]的目標是通過機器學習將研究對象的語義信息表示為稠密低維實值向量[16-17],以知識圖譜的實體e和關系r為例,將表示學習得到的向量用le和lr來表示,在向量空間中,可以通過歐氏距離或余弦距離等方式,計算任意對象間的語義相似度。表示學習的主要方法有雙線性模型RESCAL[18-19]、多層感知機模型MLPs[20]以及TransE[10]、TransH[21]、TransR[22]等翻譯模型。通過知識表示得到低維稠密向量,可以更好地用于知識圖譜補全工作。

綜上所述,本文利用TransE模型將知識圖譜中富有語義信息的三元組嵌入到向量空間,從而實現知識圖譜的數值化,并受文獻[11]的啟發(fā),利用強化學習抽取路徑關系,以降低計算成本。在文獻[13]的基礎上,將路徑中實體和關系對應的向量作為RNN的輸入,經過迭代學習輸出多級關系路徑語義組合的結果向量。

2 關系推理框架及算法

本文關系推理框架示意圖如圖1所示。在資源層,以實體關系三元組表示知識圖譜;在向量表示層,利用TransE模型將三元組嵌入到低維向量空間;在路徑發(fā)現層,利用強化學習(Agent與環(huán)境交互),發(fā)現實體間路徑;在關系推理層,將路徑中實體和關系對應的向量輸入到RNN,經過迭代學習將路徑上的語義信息進行組合,輸出多級關系路徑語義組合的結果向量,并將結果向量與目標向量進行相似度計算,進而進行關系推理。

圖1 路徑推理框架示意圖

2.1 強化學習路徑發(fā)現算法

本文采用一種新的路徑發(fā)現算法,即基于強化學習的路徑發(fā)現算法。該算法的基本思想是:將知識圖譜作為環(huán)境進行建模,同時設置一個Agent。首先從環(huán)境傳遞給Agent一個初始狀態(tài)(State),通過Agent的決策得到一個動作(Action)再傳遞給環(huán)境。從初始狀態(tài)轉移到下一個狀態(tài),同時獲得一個獎勵(Reward)。依此循環(huán)往復,便可得到一個從初始狀態(tài)到目標狀態(tài)的決策序列。Agent的位置隨著中間狀態(tài)的改變而改變,通過以上過程,當Agent移動到目標狀態(tài),即尾實體時,就可獲得一條從頭節(jié)點到尾節(jié)點的路徑。強化學習過程示意圖如圖2所示。

圖2 強化學習過程示意圖

2.1.1 環(huán)境部分

本文將強化學習的環(huán)境部分建模為馬爾科夫決策過程(MDP),由四元組(S,A,P,R)組成,其中,S表示連續(xù)的狀態(tài)(State)空間,對應于實體,A表示所有可選擇的動作(Action)集合,對應于每個實體所鏈接關系的集合,R(s,a)表示每對(s,a)的獎勵函數,即在某個狀態(tài)s選擇動作a可得到的獎勵,P(St+1=s′|St=s,At=a)表示從當前狀態(tài)St通過動作At轉移到下一個狀態(tài)St+1的概率矩陣,每個狀態(tài)通過Agent位置的移動來捕捉。

在知識圖譜中,可被Agent選擇的動作(Action)數量很多,而與所得到的路徑中正確的動作相比,不正確動作的數量隨著路徑長度的增加而增加。因此 如果每走一步都給出相應獎勵,則浪費大量的計算成本,為降低計算成本,本文對獎勵的設置如式(1)所示:

(1)

當路徑到達目標實體時,給出一個+1的獎勵;否則給出一個-1的獎勵;同時為鼓勵Agent發(fā)現更多路徑,利用余弦函數設置一個多樣性獎勵函數,計算當前發(fā)現的路徑和已得到路徑之間的相似性,函數設置如下:

(2)

2.1.2 Agent部分

由于關系圖的復雜性,使得Action的空間非常大,對于DQN(Deep Q Network)[23]而言,可能導致非常差的收斂性,同時,為了避免Agent陷入一個中間狀態(tài),本文將Agent設置為一個決策網路,如式(3)所示:

πθ(s,a)=p(a|s;θ)

(3)

本文用一個全連接的神經網絡來參數化策略函數πθ(s;a),該函數能夠將狀態(tài)映射到所有可選動作的概率分布上,神經網絡由兩個隱藏層組成,每個隱藏層后面都有一個激活函數ReLU,最后的輸出層由Softmax函數來進行歸一化,采用隨機梯度下降法更新神經網絡參數θ。為了避免傳統(tǒng)強化學習(Reinforcement Learning,RL)算法收斂性較差的問題,本文引入一種監(jiān)督學習機制,采用BFS(Breadth-First Search)進行路徑發(fā)現過程中的監(jiān)督訓練。

在強化學習中,所有的目標都被描述為最大化期望累計獎勵,即Agent從起點到終點的過程中將獎勵累積到最大。Agent的目標是選擇一系列動作去最大化未來總的獎勵。本文通過蒙特卡羅策略梯度[21]來累計最大化獎勵值,如式(4)所示:

(4)

梯度下降法更新參數如下:

(5)

為盡可能找全實體對間路徑,本文采用獎勵函數來訓練受監(jiān)督的策略網絡。一對實體間路徑信息的發(fā)現稱為一個片段,從源節(jié)點開始,Agent根據隨機策略π(a|s)選擇關系,根據選擇的關系,源節(jié)點可能會鏈接到一個新實體,或者什么也沒有。后者稱為失敗的步驟,同時Agent還將得到一個負面的獎勵。由于Agent遵循隨機的策略,它不會因重復錯誤的步驟而陷入困境,因此在一個失敗步驟之后,Agent仍會處在之前同樣的狀態(tài)。為了提高訓練效率,本文用上限max-length來限制一個輪次的長度,max-length設置為10,即每一個輪次進行10次動作選擇操作。10次選擇后不論是否到達目標節(jié)點,都結束這個片段。在每個片段結束后,對策略網絡進行更新,如式(6)所示:

(6)

其中,Rtotal=rGLOBAL+rDIVERSITY。基于獎勵函數訓練的路徑發(fā)現算法如下:

輸入給定的實體對

輸出實體對間路徑

1.對片段1～N做如下循環(huán):

2.初始化向量S0→St

3.初始化片段長度,step→0

4.當num_steps < max_length時,執(zhí)行:

5.從隨機策略π(a|s)中隨機取樣動作a

6.觀察獎勵Rt,以及下一個狀態(tài)St+1

7.如果Rt=-1,則:

8.保存〈St,a〉到Mneg

9.如果到達了目標節(jié)點或者num_steps=max_length

10.跳出循環(huán)

11.增加步數

12.如果失敗則更新參數θ

14.如果成功則:

15.Rtotal←r1rGLOBAL+r2rDIVERSITY

16.更新參數θ

2.2 實體和關系向量組合模型

在利用強化學習獲得兩個實體間路徑信息后,為更好地提高關系推理的精確性,本文將路徑上實體和關系的特征考慮在內,如圖3所示。

圖3 實體對間的路徑信息

在圖3中,假設實體對(Melinda,Seattle)之間有兩條路徑,若判斷它們之間是否存在關系Live in,由路徑信息可以看出通過Bill這條路徑得到結果的可靠性比通過路徑Marry這條路徑的可靠性大,因此考慮路徑上實體和關系的特征是有必要的。本文通過建立一種如圖4所示的RNN模型,將路徑中實體和關系對應的向量作為RNN的輸入,經過迭代學習將輸出一個關系路徑語義組合的結果向量,并將該結果向量與目標關系向量進行相似度計算。相似度值越高,通過該路徑得到目標關系的概率越大,進而提高結果的精確性。

圖4 RNN模型

本文用(esource,etarget)來表示一個實體對,它們之間的關系用r表示,且(e∈E,r∈R),讓π={e0,r0,e1,r1,…,rt-1,et}表示實體對間的路徑。由于實體對間可能存在多條路徑,本文用S表示它們之間路徑集合;len(π)=k,len表示路徑的長度,值為k,即路徑中實體與關系的個數, 讓lei表示第i個實體向量,lri表示第i個關系向量。然后RNN模型對路徑π上的實體和關系進行向量組合,在步驟t時刻的輸出,如式(7)所示:

ht=f(Whhht-1+Wihlrt+Wehlet)

(7)

路徑的最終輸出結果向量用lπ表示,目標關系向量用lr表示,它們之間的相似度計算公式,如式(8)所示:

score(π,r)=lπ·lr

(8)

由于實體對間有多條路徑相連,需通過式(9)所示的函數找到相似度值最高的路徑。

P(r|es,et)=maxσ(score(π,r)),?π∈S

(9)

圖4中每一步需要利用一個實體和關系向量,路徑向量是整個路徑信息的最終表示,它與查詢關系之間的點乘給出置信度得分,即與目標關系向量的相似度得分。

該算法在表示學習已經訓練好樣本的基礎上進行數據處理。在強化學習階段,通過給定的頭結點對圖進行遍歷的時間復雜度是O(n2);在利用RNN進行路徑信息融合階段,對文本信息處理的時間復雜度是O(n),因此該算法的時間復雜度是O(n2+n),即O(n2)。

由于該算法針對文本中n個向量進行線性計算,因此該算法的空間復雜度是O(n)。

3 實驗結果與分析

3.1 實驗平臺及數據

本文實驗平臺運行在Window7系統(tǒng)、Quad-Core處理器、4 GB物理內存。實驗工具為Pycharm,使用Python3.6作為編程語言編寫程序。在知識圖譜數據集選擇方面,本文選用了FB15K-237[25]和NELL-995[26],它們分別是從FB15K和NELL995中選取的子集。

由于原始數據集數量龐大,對路徑發(fā)現而言,在每一步每個實體面對可選擇的action數量,因存在一些不相關性關系而增加,這些不相關的關系會導致大量不必要的計算,進而影響實驗效果。因此,本文選擇特定領域關系的數據子集進行實驗,同時為降低噪聲數據的影響,都在選取時刪除冗余及對推理沒有任何價值的三元組。本文最終在FB15K-237數據集中選取20種關系任務,在NELL-995中選取12種關系任務進行推理工作。這些任務是來自不同領域,如體育、電影、人物等。為得到更加精確的推理關系,選取最高的相似度值作為路徑的推理關系。在進行實驗前,將數據集隨機地分為8∶2,其中80%作為訓練集,剩下的20%作為測試集。實驗數據集如表1所示。

表1 實驗數據集

3.2 參數設置

在實驗中,本文將參數配置如下:學習率λ=0.001,邊際值γ=1,維度設置為k=200,采用L2正則化參數優(yōu)化,并將值設置為0.01,batch大小設置為B∈{64,128,512,1 024}。在RNN模型中,β1=0.9,β2=0.999,實驗進行1 000次迭代,測試結果通過測試集上的平均排名來選取。

3.3 度量方法

本文通過在鏈接預測和事實預測上的MAP(Mean Average Precision)指標來評價實驗結果。鏈接預測指的是對給定查詢實體對應的目標實體進行排名。具體表現為在訓練中,將一個正例樣本,即對一個正確三元組,將其中的尾實體用其他實體替換,從而形成一個負例樣本。為保證實驗效果的精確性,本文盡量讓每個正例樣本都對應10個負例樣本。最后,通過對這些目標實體的排序,進行正確三元組和錯誤三元組的劃分。事實預測的目標是判斷一個三元組(es,r,et)是否成立,即判斷頭實體es和尾實體et之間是否真的存在關系r。

3.4 實驗結果

用RL+RNN表示本文模型,其中在FB15K-237數據集上的鏈接預測結果如表2所示,在NELL-995數據集上的鏈接預測結果如表3所示。

表2 不同模型在FB15K-237數據集上的鏈接預測結果

Table 2 Link prediction results of different models on the FB15K-237 dataset

TasksPRARL+RNNTransETransHteamSp..0.9870.9430.8960.763birthPl..0.4410.5010.4030.405personN0.8470.8410.6410.695filmDir.0.3490.4520.3860.401filmWr..0.6010.4420.5630.567filmLa..0.6630.6680.6420.644tvLang.0.9600.9660.8040.821capital..0.8290.7920.5540.798origani.0.2810.2950.3900.351musici..0.4620.4960.3610.368?????overall0.5410.5930.5320.537

表3 不同模型在NELL-995數據集上的鏈接預測結果

Table 3 Link prediction results of different models on the NELL-995 dataset

TasksPRARL+RNNTransETransHath..P..T0.5470.7320.6720.658ath..P..L0.8410.9610.7730.897ath..H.S0.8590.8870.7180.731ath..P..S0.4740.9310.8760.981team.P.S0.7910.7420.7610.805orgHq.C0.8110.7930.6200.763worksF..0.6810.6890.6770.672bornLo..0.6680.7640.7120.801pers.L.O0.7000.8210.7510.762orgH..P..0.5990.7630.7190.720?????overall0.6750.7910.7370.753

從表2和表3可以看出,本文方法在鏈接預測的實驗結果優(yōu)于PRA、翻譯模型TransE與TransH,這說明本文提出的模型具有良好的推理能力。對于大部分關系,由于翻譯模型并不能考慮到路徑上的信息,預測結果顯著低于本文提出的模型或者PRA,但當沒有足夠的路徑信息時,翻譯模型還是具有良好的表現能力。同時也說明,本文提出的模型能夠較好地利用路徑上的信息,并能有效提升知識圖譜中信息預測的精確性。

在FB15K-237數據集上的事實預測結果如表4所示,在NELL-995數據集上的事實預測結果如表5所示。

表4 不同模型在FB15K-237數據集上的事實預測結果

Table 4 Fact prediction results of different models on the FB15K-237 dataset

模型MAPPRA0.301TransE0.277TransH0.309RL+RNN0.314

表5 不同模型在NELL-995數據集上的事實預測結果

Table 5 Fact prediction results of different models on the NELL-995 dataset

模型MAPPRA0.387TransE0.383TransH0.389RL+RNN0.417

從表4和表5可以看出,本文提出的方法在事實預測中的結果均優(yōu)于其他3個模型,同時也表明路徑上的實體和關系信息對關系推理具有良好的促進作用,在一定程度上提高了關系推理的質量和效率。

4 結束語

本文提出一種基于多級關系路徑語義組合的關系推理算法。該算法利用關系推理,在一定程度上提高了知識圖譜補全質量,并將知識圖譜嵌入到向量空間,減少了計算開銷。下一步研究除考慮知識圖譜中已存在的路徑信息外,對結構相似性的知識圖譜補全問題以及如何處理新引入的知識也將是進一步的研究重點。