融合TuckER嵌入和強化學習的知識推理①

于鐵忠, 羅 婧, 王利琴,3,4, 董永峰,3,4

1(河北工業大學 人工智能與數據科學學院, 天津 300401)

2(石家莊學院 計算機科學與工程學院, 石家莊 050035)

3(河北省大數據計算重點實驗室, 天津 300401)

4(河北省數據驅動工業智能工程研究中心, 天津 300401)

1 引言

知識圖譜(knowledge graph, KG)[1]本質上是一種概念網絡, 其基本組成單位是形式為(實體, 關系, 實體)的三元組, 目前已經構建了許多知識圖譜, 如WordNet[2]、NELL[3]、Freebase[4]等, 并成功應用于信息檢索、推薦系統、問答系統等智能服務領域. 因為構建的大規模知識圖譜通常是不完備的, 需要不斷對其進行補充, 而知識推理[5,6]是從現有的數據中推理出新的實體或關系, 從而不斷完善知識圖譜, 因此知識推理近年來成為知識圖譜研究領域的熱點問題之一.

使用張量因子分解或神經網絡學習實體和關系的嵌入是目前較為流行的知識推理方法[7-9], 它們將知識圖譜中的實體和關系表示成低維稠密向量, 然后利用向量的相似性推理出實體之間的關系或者判定給定的三元組是否為真, 從而補全知識圖譜. 這些方法效率較高, 但是依賴于知識圖譜的三元組表示形式, 大多數都沒有捕捉到多跳路徑的關系, 從而限制了其在更復雜的推理任務中的應用. 因此, 結合實體對之間的多跳路徑信息成為知識推理的另一種解決方案. 路徑排序算法(path ranking algorithm, PRA)[10]使用基于重啟推理機制的隨機游走來執行多個有界深度優先搜索, 通過監督學習選擇更合理的路徑, 在一定程度上解決了上述問題. 由于具有可解釋性和良好的性能, 最近的工作將多跳推理表述為馬爾可夫決策過程(Marcov decision process, MDP)[11], 并利用強化學習(reinforcement learning, RL)[12,13]執行有效路徑搜索. 其中DeepPath[14]是第一個將強化學習遷移到知識圖譜中的多跳推理方法, 該方法將實體對應強化學習中的狀態, 關系對應動作, 旨在使用RL對關系進行采樣來擴展路徑, 這類方法的提出為知識圖譜的推理提供了新的研究思路.

然而在實際知識推理任務當中, 使用強化學習來進行路徑搜索的效率并不高, 一方面, 多數強化學習方法在構建知識圖譜環境時沒有對實體和關系進行較好的嵌入, 從而導致智能體的路徑搜索成功率偏低; 另一方面, 知識圖譜中存在大量無效路徑, 比如對于三元組(人物A, 出生于, 北京)、(北京, 位于, 中國)、(人物A,結婚, 人物B)而言, 可以推出(人物B, 出生于, 中國).在推理過程中, 關系“結婚”是實體, “北京”和“中國”的無效動作, 因為實體“北京”和“中國”不能作為“結婚”的主語或者賓語. 當智能體在游走的過程中選擇了某無效動作時, 會停止并退回上一步重新進行選擇, 然而智能體可能會不斷選擇該無效動作; 當選擇有效路徑時,也會存在同一條路徑重復被選擇的情況, 均會造成游走死循環. 上述情況都有可能導致智能體在游走初始階段難以獲得策略網絡給予的獎勵, 使得路徑選擇的準確率降低.

針對以上提出的在進行知識推理時路徑選擇效率和準確率偏低的問題, 本文實現了表示學習和強化學習的融合, 提出一種融合TuckER嵌入和強化學習的知識圖譜推理方法TuckRL (TuckER reinforcement learning, TuckRL), 將路徑選擇問題轉化為序列決策問題. 通過使用TuckER嵌入得到知識圖譜中實體和關系的向量表示, 使智能體在與知識圖譜環境的交互中能夠更精準的搜索路徑, 提高了推理方法的效率; 為了減少無效動作對智能體的干擾, 并鼓勵策略網絡選擇不同的關系, 通過對動作執行隨機丟棄操作, 使智能體得到更全面的訓練, 提高了模型的泛化能力; 使用長短期記憶網絡(long short-term memory, LSTM) 存儲智能體歷史動作, 在關系選擇時強制智能體選擇其他動作來避免在同一實體節點上不斷停頓, 使其在訓練過程中盡可能為推理任務找到成功率較高的路徑.

2 相關工作

目前面向知識圖譜的知識推理方法可分為以下3類: 基于嵌入的方法、基于關系路徑的方法以及基于強化學習的方法, 本節將按照此分類對知識推理方法的國內外研究工作進行概述.

基于嵌入的推理是將實體和關系映射到向量空間中, 通過計算得到的向量相似度完成推理. 其中最經典的模型是Bordes等[8]于2013年提出來的TransE, 該模型將關系視為實體對之間的某種翻譯, 在處理簡單關系時表現良好, 但在面對1-N、N-1、N-N等復雜關系時會存在錯誤; Wang等[15]提出的TransH通過設置一個關系超平面, 使不同關系下的實體有不同的表示,解決了TransE在處理復雜關系時的局限性. Ji等[16]提出的TransD同時考慮實體和關系的多樣性, 通過設置兩個投影矩陣分別將頭尾實體投影到關系空間, 模型更加靈活; 陳文杰等[17]提出的TransGraph模型學習三元組信息的同時, 還考慮到知識圖譜的網絡結構特征和語義信息, 從而增強三元組的表示效果; Trouillon等[18]提出的ComplEx將實體和關系嵌入到復數向量空間中, 以推理對稱和反對稱關系; Bala?evi?等[19]提出的TuckER將知識圖譜表示成三階二元張量, 每個元素對應一個三元組, 具有較強的學習特征能力.

基于關系路徑的推理方法側重于捕捉KG中路徑上的信息, 也就是說, 此類方法不僅可以預測實體之間的直接關系, 還考慮其多跳關系的豐富語義. 早期的研究路徑排序算法PRA通過在KG上隨機游走得到實體對之間的所有路徑, 并利用二分類器推理缺失的關系. Lin等[20]提出的PTransE通過組合每條路徑中的所有關系得到路徑的嵌入, 并設計了路徑約束資源分配算法(path-constraint resource allocation, PCRA)衡量關系路徑的可靠性. Das等[21]提出Path-RNN (pathrecurrent neural network, Path-RNN)神經網絡模型, 將每條路徑分解為關系序列, 通過RNN組合關系路徑的語義信息, 構造出路徑的向量表示. Wang等[22]提出知識感知的路徑循環網絡(knowledge-aware path recurrent network, KPRN)模型, 在嵌入實體和向量之后,LSTM通過組合實體和關系的語義生成路徑表示, 利用路徑中的序列依賴項進行關系補全.

基于強化學習的推理方法將實體之間的路徑游走視為馬爾可夫決策過程, 使用基于策略的智能體搜索推理路徑. Xiong等[14]提出第一個考慮在知識圖譜中學習路徑的強化學習方法DeepPath; Das等[23]提出的MINERVA是使用強化學習訓練用于多跳KG查詢應答的端到端模型; Shen等[24]提出的M-Walk是一個由RNN和蒙特卡洛樹組成的智能體, 用來編碼路徑狀態以及生成有效路徑. Li等[25]提出的DIVINE是一種基于生成對抗學習的框架, 通過學習推理策略和獎勵函數來增強知識圖譜中基于RL的推理. Meilicke等[26]提出基于規則的多跳推理模型, 引入強化學習指導規則采樣過程, 有助于獲取更有價值的規則. Lei等[27]提出的RuleGuider利用基于符號方法生成的高質量規則為智能體提供獎勵監督. 崔員寧等[28]提出的TransPath通過在目標任務之外增加單步游走選擇有效動作的源任務來提高路徑選擇的成功率.

從以上研究可以發現, 很少有將嵌入模型和強化學習相結合的方法, 且在使用強化學習進行推理的過程中, 沒有充分利用智能體的歷史路徑信息. 因此, 本文提出采用TuckRL方法解決此類問題, 首先將實體和關系進行低維嵌入, 完成知識圖譜環境的創建; 然后在強化學習的框架中, 為減少無效動作對推理結果的干擾, 通過隨機丟棄智能體的輸出邊進行動作修剪, 并引入LSTM網絡作為記憶組件存儲歷史路徑, 以提高路徑選擇的效率.

3 融合TuckER嵌入和強化學習的知識推理

知識推理的具體任務是在實體對之間找到可靠的預測路徑, 所以為了提高路徑搜索的效率和質量, 本文提出了一種融合TuckER嵌入和強化學習的知識推理方法TuckRL, 將尋找實體對之間可能存在的關系以及路徑信息轉化為強化學習的序列決策問題. 模型如圖1所示, 分為3部分.

圖1 融合TuckER嵌入和強化學習的知識推理模型框架圖

其中, 第1部分為知識圖譜環境模塊: 使用TuckER嵌入將實體和關系映射成含有三元組語義信息的向量;第2部分為強化學習環境模塊: 將TuckER嵌入得到的實體和關系的連續向量化表示作為基于強化學習的神經網絡的輸入, 使得模型能夠充分利用知識圖譜已經存在的三元組信息, 且RL智能體在游走的過程中進行策略網絡的訓練, 使用動作修剪和LSTM網絡來控制關系選擇和路徑搜索, 幫助智能體選擇有效動作, 以便提高模型的性能; 第3部分為策略引導的路徑推理模塊: 智能體與知識圖譜環境進行交互, 在知識推理階段采用訓練好的策略, 完成推理任務.

3.1 TuckER嵌入

知識圖譜嵌入是KG建模的方法, 通過學習評分函數 f(eH,eT)來定義空間中的三元組, 使得語義相近的實體在嵌入空間中的向量表示距離也相近. TuckER具備完全表達能力, 即通過訓練學習, 能夠將正三元組和負三元組完全區分開, 且性能較優于當前的線性嵌入模型. 圖2為TuckER嵌入模型的可視化表示.

圖2 TuckER嵌入模型圖

在該嵌入模型中, 知識圖譜被表示為一個三階二元張量, 而TuckER分解的核心思想是將該三階張量分解為1個核心張量和3個矩陣, 每一個元素表示一條事實三元組, 值為1表示真實三元組, 為0表示錯誤或缺失事實. 定義一個原始張量X ∈RI×J×K, 通過TuckER可以分解為核心張量Z ∈RP×Q×R和 3個矩陣A∈RI×P、B∈RJ×Q、C∈RK×R, 如式(1)所示:

其中, ×n表示沿第n階模的張量積, 3個矩陣每一行分別為頭實體eH、關系r 和尾實體eT的向量表示, 而核心張量 Z 表征了它們之間的交互級別. 頭實體和尾實體是等價的, 均用實體嵌入矩陣 E 來表示, 即E=A=C∈Rne×de ,且關系矩陣嵌入為R =B∈Rnr×dr, 其中ne和nr表示實體和關系的數量, de和dr表示實體和關系嵌入向量的維數.

綜上, 定義出TuckER的得分函數如式(2)所示:

其中,W∈Rde×dr×de為 核心張量, 即模型參數;wr∈Rdr為R的關系表示.

3.2 強化學習

TuckRL模型是將知識圖譜推理問題轉化為馬爾科夫決策問題, 智能體的狀態轉移和動作選擇都在知識圖譜環境中完成, 故本節介紹將知識圖譜G 建模為強化學習智能體決策環境的過程.

該過程主要由< S, A , γ, P ＞四部分構成, 其中S表示智能體的連續狀態空間, A={a1, a2, …, an}是動作空間, 表示所有可用動作的集合, γ(s, a)為獎勵函數, P是狀態轉移策略.

(1) 狀態空間

知識圖譜中的實體集合E作為智能體的狀態S,將智能體在每個時間步驟的狀態表示成 st∈S , 且et表示第t步訪問的實體. 為了更好地表達其語義內涵, 采用TuckER嵌入將實體表示成低維稠密向量.

(2) 動作空間

動作空間A被定義為KG中的關系集合R, At表示狀態 st所對應的實體et在KG中所有可能的輸出邊, 智能體要選擇一個邊進行路徑搜索, 游走步數T作為路徑搜索的終止條件. 動作集合表示如下:

其中, r′、 e′分別表示下一步有可能選擇的關系和實體.

(3) 狀態轉移

狀態轉移是指智能體根據當前狀態做出動作移動到下一個狀態的過程. 具體來說, 智能體在當前狀態下,通過選擇某動作后, 并基于環境的交互實現從當前狀態到下一狀態的轉移. 狀態轉移P表示如下:

(4) 獎勵函數

當智能體從初始狀態開始搜索, 最終能夠到達目標狀態, 則獲得正向獎勵1, 否則無獎勵. 智能體會根據獎勵及時更新自己的策略, 盡可能實現獎勵最大化, 獎勵函數定義如下:

其中, rq表 示查詢到的關系, eT表示最終的尾實體.

3.3 基于MDP的策略網絡

基于MDP的策略網絡是TuckRL的關鍵部分, 主要用于引導智能體在知識圖譜和強化學習的交互環境中進行游走, 做出高效且準確的決策. 在該策略網絡中,首先使用Dropout動作修剪, 目的是減少無效動作對于智能體游走的干擾, 提高動作的選擇效率, 然后引入長短期記憶網絡LSTM作為記憶組件, 避免智能體在同一實體節點上不斷停滯的同時, 編碼完整的路徑游走歷史軌跡, 并采用策略梯度下降算法更新策略網絡的參數, 以便在推理過程中引導智能體走向更可靠的路徑.

(1) 動作修剪

由于無效路徑通常比正確路徑多, 且更容易被發現, 從而增加了路徑搜索的負擔, 尤其是當KG隨著路徑跳數的增長, 動作空間也會呈指數型增加, 從而加大搜索負擔, 對于出度較大的實體(即與之相連的關系較多), 這種現象會更嚴重. 而枚舉出來實體對之間所有可能的關系路徑在大型知識圖譜上是不可行的, 因此如何進行有效的路徑探索, 找出推理路徑格外重要.

針對這類問題, TuckRL借鑒深度神經網絡中Dropout丟棄神經元來緩解過擬合的思想, 提出了一種新的訓練機制: 將隨機丟棄思想用到強化學習的路徑選擇中, 按照一定的概率屏蔽當前實體的輸出邊, 從而實現動作的修剪. 在智能體采樣路徑的時候, 隨機屏蔽當前狀態的一些輸出邊, 智能體根據修剪后的關系分布來采樣動作. 這樣不僅可以減少智能體的搜索空間,防止GPU內存溢出, 同時還能進一步擴大對于不同路徑集的有效探索, 提高路徑選擇的隨機性.

(2) LSTM編碼路徑

KG中的每一個實體和關系都通過TuckER嵌入分別得到具有語義信息的低維稠密向量e ∈E, r ∈R, 為保存搜索歷史路徑, 利用3層LSTM記憶和編碼智能體的歷史動作. 假設初始狀態為 h0=0 , 搜索歷史ht=(eH,r1,e1,···,rt,eT)由從第1步到第t步所采取的動作序列構成.

其中, r0表 示初始關系, eH為初始實體.

(3) 策略神經網絡優化

在知識推理中, 基于策略網絡的強化學習將輸入狀態 st映射到所有可能被選擇的動作的概率向量中, 本文將組合得到的狀態向量輸入到由兩個隱藏層組成的神經網絡中, 且每個隱藏層后面會有一個ReLU層, 輸出層使用Softmax進行歸一化. 策略網絡π定義如下:

其中, θ為神經網絡參數, 動作空間At為所有動作嵌入的集合, W為隱藏層的權重.

對于上述策略網絡πθ, 模型使用REINFORCE梯度策略方法來優化參數θ, 如式(10)所示:

其中, J (θ) 表示一個批次的獎勵, E 表示訓練集上不同三元組對應的期望值.

REINFORCE梯度策略方法使用當前的策略生成的一系列歷史軌跡(迭代遍歷所有在 G 中的三元組)來估計隨機梯度, 然后用隨機梯度來更新參數, 如式(11)和式(12)所示:

其中, θ為需要更新的參數, eH表示頭實體, rt表示當前關系, πθ(at|st)為 在 st狀 態下策略網絡選擇at的概率. γ為執行該動作所獲得的獎勵值, β為學習率.

3.4 模型訓練

在進行知識推理之前, 對RL智能體進行策略網絡的訓練, 目的是讓智能體在路徑游走的過程中盡可能地直接選擇正確的動作, 從而更高效的完成多步關系推理. 在訓練中, 首先輸入知識圖譜訓練集Train、限制游走長度的最大步數T, 然后是智能體和圖譜環境之間的迭代: 根據策略網絡的輸出結果, 選擇一個關系r作為下一步的執行動作, 此時判斷起始狀態 s0和目前選擇的關系r組成的三元組是否在知識圖譜 G 中, 若是, 給予獎勵并更新策略網絡, 具體訓練過程如算法1.

算法1. 策略網絡訓練算法G輸入: 知識圖譜 , 訓練集Train, 最大步數大小T πθ輸出: 策略網絡 的參數θ 1) for episode 1 to N do 2) initial st = s0, h0 = 0, step = 0 3) while step < T do 5) st=TuckER(et), at=TuckER(rt)πθ(at|st)6) Update ht = LSTM(ht-1, at-1) //根據策略 執行動作a, 得到獎勵Reward和狀態St+1 7) if Reward = 0 8) step++9) if Reward = 1 or step = T 10) break 11) end while g∝?θT∑t=1 Reward(st|es,r)logπθ(at|st)12) //更新策略網絡13) end for

4 實驗分析

4.1 數據集及評價標準

為了評估本文所提方法, 在NELL-995、WN18RR、FB15K-237這3個大規模數據集上進行實驗. 其中NELL-995是基于語義機器學習系統NELL的第995次迭代產生的數據集, 包含7.5k個實體、200個關系以及16.9k個三元組, WN18RR的三元組數據來自大型英文語義知識庫WordNet, 包含4.0k個實體、11個關系和14.6k個三元組; FB15K-237是包含常見信息的世界知識庫FB15K的子集, 通過從驗證集和測試集中移除許多關系的逆關系構建, 包含1.4k個實體、237個關系和29.2k個三元組; 數據集的統計信息如表1所示.

表1 數據集的信息

在關系預測任務中, 通常使用平均倒數排名(mean reciprocal rank, MRR)和推理結果命中率Hits@N作為評估指標. 對于三元組中缺失的關系, 模型會對測試集中的實體對(e1, e2), 依據評分函數預測出帶有順序的關系集合r={r1, r2, …, rn}, 正確的關系r在關系集合中排名越靠前, 則說明模型的預測效果越好.

MRR是指正確結果在所有預測結果中排名的倒數平均值, 計算如式(13)所示:

Hits@N表示正確的結果在所有預測結果中排在前n位所占的比例, 計算如式(14)所示:

其中, N是需預測關系的實體對數量; r anki是對需預測的第i個實體對而言正確的關系在所有預測結果中的排序位置. I 為指示函數, 表示當r anki≤n 時 , I =1, 否則I=0.

4.2 參數設置

到的所有實體和關系向量維度設置為100, 這也是策略網絡Policy Network的輸入大小, 路徑編碼器LSTM的隱藏層維度設置為100. 選擇Adam作為優化器, 學習率 β分別設置為{0.001, 0.002, 0.003}, 對于整個訓練過程, Dropout分別為{0, 0.1, 0.2, 0.3, 0.4}, 迭代次數num_epoches和批大小batch_size分別為20和128.

實驗使用與RuleGuider[27]相同的訓練集、驗證集和測試集. 對于每個實體, 將實體的最大輸出邊數設置為閾值η, 以防止GPU內存溢出, 并保留其具有最高PageRank分數的前n個鄰居. 將TuckER模型嵌入得

4.3 實驗結果與分析

為了驗證所提方法的性能, 與嵌入模型TransE、DistMult、ComplEx和ConVKB[29], 使用強化學習進行推理的模型DeepPath、MINERVA、AnyBURL和RuleGuider進行對比實驗, 得出本模型TuckRL優于大部分模型, 實驗結果如表2所示, 其他模型的實驗結果使用文獻[27]給出的結果. 由表2可知, 基于嵌入的模型雖然比較簡單, 但是在多個數據集上的整體結果是不錯的, 原因可能是基于嵌入的方法可以將KG中的每個三元組映射到嵌入空間, 從而可以編碼整個圖譜的連通性; 而TuckRL也正是利用了嵌入模型的這個優點, 也得到了不錯的實驗結果. 在WN18RR和FB15K-237數據集上比其他方法有較明顯提升, 尤其在FB15K-237數據集上, 主要原因可能是FB15K-237實體之間路徑長度較長, 在其他模型中動作選擇的正確率較低,而TuckRL中使用動作修剪和LSTM編碼路徑有效避免了選擇無效動作. 雖然在大型數據集NELL-995上本文的方法相對于MINERVA沒有得到顯著改善, 但Hits@1、Hits@3和MRR指標略優于最新模型Rule-Guider和多數嵌入模型.

表2 不同推理方法在不同數據集上的命中率實驗結果分析比較 (%)

4.4 Dropout分析

為了考察動作修剪策略對于模型性能的影響, 在FB15K-237引入Dropout={0, 0.1, 0.2, 0.3, 0.4}進行實驗, 命中率Hits@N和平均倒數排名MRR的實驗結果如圖3所示, 可以觀察到, Hits@N和MRR一開始隨著Dropout的增加而得到提升. 在Dropout=0.3達到最高值, 并之后開始有所下降, 尤其在Hits@10評價指標上最為明顯. 分析可知, 一開始Dropout實現了動作修剪,減少了動作空間的大小, 提高了路徑選擇的正確性和效率, 但是隨著Dropout的增加, 有一些有效動作也會伴隨著大量的舍棄, 從而導致結果的降低.

圖3 在FB15K-237數據集上不同Dropout率的實驗結果

4.5 消融實驗

為了研究本文模型TuckRL中各個組件的重要性,在NELL-995、WN18RR和FB15K-237數據集上通過替換TuckER嵌入方法(-TuckER)、移除Dropout(-Dropout)和移除路徑編碼器LSTM (-LSTM)進行消融實驗的研究, 并將最終的Hits@3和MRR結果與整個模型進行了比較, 實驗結果如表3所示. 由表3可知,移除每個組件都會導致模型性能的下降, 每個組件對模型的最終結果都有不同的影響.

表3 消融實驗結果

在該消融實驗中, 首先將TuckER嵌入替換為ComplEx嵌入, 原始結果在NELL-995、FB15K-237和WN18RR數據集上的Hits@3和MRR分別有不同程度的下降, 由此可見, 一個性能較好的嵌入方法對于知識推理的作用也是較為明顯的; 當移除Dropout動作丟棄組件時, 發現對應的結果也均得到了降低, 由此可見, 刪除動作丟棄組件會對策略網絡中路徑的游走有一定的影響; 最后是去掉可以記憶歷史路徑的LSTM組件, 也就是說, 智能體僅根據當前的實體和策略函數來選擇下一步的動作, 并且無法得到歷史路徑ht, 從實驗結果可以觀察到記憶組件LSTM對于模型的性能具有重要影響.

5 結論與展望

本文提出了一種基于強化學習的知識圖譜推理方法TuckRL, 該方法融合了表示學習和強化學習, 設計出一個全新的路徑游走策略, 在強化學習智能體進行關系選擇和路徑游走的過程中, 引入了Dropout動作修剪機制和LSTM神經網絡, 相比之前的強化學習工作, 更有利于智能體在推理過程中更有效的挖掘高質量路徑, 從而完成知識圖譜推理任務. 實驗部分驗證了本文模型的性能, 但是基于RL的方法與基于嵌入的方法在個別指標上的差距仍然存在. 在未來的研究中, 將引入注意力機制來對鄰居節點分配不同的權重, 從而更好地捕獲兩個實體之間每條路徑的語義相關性, 來得到更好的推理效果.