一種分層強化學習的知識推理方法

孫崇 王海榮 荊博祥 馬赫

摘 要：針對知識推理過程中，隨著推理路徑長度的增加，節(jié)點的動作空間急劇增長，使得推理難度不斷提升的問題，提出一種分層強化學習的知識推理方法（knowledge reasoning method of hierarchical reinforcement learning，MutiAg-HRL），降低推理過程中的動作空間大小。MutiAg-HRL調用高級智能體對知識圖譜中的關系進行粗略推理，通過計算下一步關系及給定查詢關系之間的相似度，確定目標實體大致位置，依據(jù)高級智能體給出的關系，指導低級智能體進行細致推理，選擇下一步動作；模型還構造交互獎勵機制，對兩個智能體的關系和動作選擇及時給予獎勵，防止模型出現(xiàn)獎勵稀疏問題。為驗證該方法的有效性，在FB15K-237和NELL-995數(shù)據(jù)集上進行實驗，將實驗結果與TransE、MINERVA、HRL等11種主流方法進行對比分析，MutiAg-HRL方法在鏈接預測任務上的hits@k平均提升了1.85%，MRR平均提升了2%。

關鍵詞：知識推理； 分層強化學習； 交互獎勵； 鏈接預測

中圖分類號：TP391?? 文獻標志碼：A

文章編號：1001-3695（2024）03-023-0805-06

doi：10.19734/j.issn.1001-3695.2023.07.0309

Knowledge reasoning method based on hierarchical reinforcement learning

Sun Chonga， Wang Haironga，b， Jing Boxianga， Ma Hea

（a.College of Computer Science & Engineering， b.The Key Laboratory of Images & Graphics Intelligent Processing of State Ethnic Affairs Commission， North Minzu University， Yinchuan 750021， China）

Abstract：In the process of knowledge inference， with the increase of the length of the inference path， the action space of the node increases sharply， which makes the inference difficulty continue to increase. This paper proposed a knowledge reasoning method of hierarchical reinforcement learning（MutiAg-HRL） to reduce the size of action space in the reasoning process. MutiAg-HRL invoked high-level agents to perform rough reasoning on the relationships in the knowledge graph， and determined the approximate location of the target entity by calculating the similarity between the next step relationship and the given query relationship. According to the relationship given by the high-level agent， the low-level agents were guided to conduct detailed reasoning and select the next action. The model also constructed an interactive reward mechanism to reward the relationship between the two agents and the choice of actions in time to prevent the problem of sparse reward in the model. To verify the effectiveness of the proposed method， it carried out experiments on FB15K-237 and NELL-995 datasets. The experimental results were compared with those of 11 mainstream methods such as TransE， MINERVA and HRL. The average value of the MutiAg-HRL method on the link prediction task hits@k is increased by 1.85%， MRR increases by an average of 2%.

Key words：knowledge reasoning; hierarchical reinforcement learning; interactive reward; link prediction

0 引言

近年來，知識圖譜（KG）已經逐漸成為管理海量知識的有效手段［1］，被廣泛應用于各個領域，產生了一些大規(guī)模知識圖譜，如Freebase、Wikidata等。這些知識圖譜雖然已經頗具規(guī)模，涵蓋了音樂、電影、書籍等領域，但仍存在大量信息缺失問題，如Freebase中71%的人沒有出生地信息，Wikidata中只有2%的人類實體具有父親信息。據(jù)統(tǒng)計，大部分知識圖譜中，69%～99%的實體至少缺失一個屬性信息［2］。知識缺失將直接影響基于知識圖譜的下游任務的效果［3～5］。知識推理作為知識圖譜補全的有效方法，已經成為日益重要的研究課題［6］。

知識推理通過知識圖譜中已知的知識，挖掘尚未被發(fā)現(xiàn)的知識，對殘缺的知識圖譜進行補全［7］。眾多學者從不同的角度出發(fā)，對知識推理進行研究，并取得了一定的研究成果。例如，基于嵌入的推理，通過將知識圖譜中的實體和關系，映射到低維向量空間中得到其向量表示［8］，這些向量包含了實體原有的語義信息，可作為判斷實體間相似度的依據(jù)，以此進行推理。典型的有TransE［9］、TransH［10］，此類方法簡單且易于擴展，但對于復雜關系的建模效果不佳。因此，Trouillon等人［11］構建了ComplEx模型，在對知識圖譜進行嵌入時引入了復數(shù)空間，能更好地對非對稱關系進行建模；Dettmers等人［12］構建了ConvE模型，引入了一種多層卷積網絡，提高了模型的特征表達能力，可以更好地建模三元組。由于基于嵌入的推理方法是將推理過程轉換為單一的向量計算，沒有考慮知識圖譜中路徑上的信息，使得該類方法在多跳推理路徑上的推理能力受到限制。所以，針對多跳問題的推理方法相繼被提出，如SRGCN［13］、MKGN［14］、ConvHiA［15］，該類方法通過多步推理找到目標實體，同時生成從頭實體到尾實體的完整推理路徑，增強了知識推理的可解釋性［16］。在多跳推理中，基于深度強化學習的推理方法成為當前知識推理研究的熱門方向，其方法被應用于諸多知識圖譜下游任務［5］。例如DAPath［17］、SparKGR［18］、MemoryPath［19］、HRRL［20］等方法，使用神經網絡提取特征向量，對知識圖譜中的事實進行建模，在推理的過程中，外部環(huán)境通過給予智能體一定的獎勵來促使智能體做出最優(yōu)動作，以取得最大化的預期效果。

最近，有學者提出了離線強化學習［21］的知識推理方法，該方法不需要智能體頻繁與外部環(huán)境進行交互，相對傳統(tǒng)的基于強化學習的方法而言開銷較小，但卻存在當智能體選擇錯誤動作時無法被及時糾正的問題，最終導致推理任務失敗?；趶娀瘜W習的知識推理方法可以通過智能體與環(huán)境的不斷交互，給予智能體懲罰，來糾正錯誤的動作選擇，從而保證了推理路徑的可靠性，進而有效提高了知識推理的準確度。但在知識推理過程中，隨著路徑長度的增加，推理的難度也會隨之增加?，F(xiàn)存的多跳推理中基于強化學習的單智能體推理方法，對短路徑推理較為有效，而長推理路徑上的推理往往效果不佳，而且會導致獎勵稀疏的問題。為此，本文提出一種分層強化學習的知識推理方法（knowledge reasoning method of hierarchical reinforcement learning，MutiAg-HRL）。首先對知識圖譜進行聚類處理，幫助高級智能體進行粗略推理，選擇出與查詢關系高度相關的關系，在此基礎上指導低級智能體進行細致推理，選擇出下一步動作，通過分層策略降低了模型的動作空間，有效解決了長推理路徑問題，在構建策略網絡時引入dropout策略，防止模型出現(xiàn)過擬合問題。此外，本文方法通過交互獎勵構造，及時對智能體每一步動作的選擇給予及時獎勵，避免獎勵稀疏的問題。

1 MutiAg-HRL方法模型

MutiAg-HRL方法使用分層強化學習，將知識推理過程看作兩個馬爾可夫序列決策過程（Markov sequence decision process，MDP）。該方法主要包含策略網絡構建和交互獎勵構造兩個模塊，通過策略網絡的構建來指導智能體進行關系和動作的選擇，并使用交互獎勵構造模塊對每一時刻智能體的選擇及時給予獎勵。方法模型如圖1所示。

MutiAg-HRL首先使用K-means++算法對實體嵌入進行聚類，根據(jù)與當前節(jié)點et相連接的關系類型，將知識圖譜分為若干個節(jié)點簇，并通過節(jié)點之間的關系將這些節(jié)點簇連接起來，這些關系則作為高級智能體下一步關系選擇的候選關系集合，在此基礎上進行知識推理任務。

本方法通過分層策略，將傳統(tǒng)基于強化學習的知識推理過程分為關系選擇和動作選擇兩部分。首先，將與當前實體相連接的關系作為當前實體的下一步關系選擇的候選關系集合，通過高級策略網絡對候選關系集合進行概率分布計算，指導高級智能體選擇出分數(shù)較高的下一時刻的關系；其次，通過低級策略網絡對與高級智能體所選關系相連接的實體進行概率分布計算，指導低級智能體選擇出下一時刻的動作實體，直至到達目標實體ep則此次推理任務結束。在構建策略網絡時，采用門控循環(huán)神經網絡（gated recurrent unit，GRU）對歷史推理路徑進行編碼，將歷史編碼與當前節(jié)點狀態(tài)作為高級策略網絡輸入進行粗略推理，最終得到與給定查詢關系rq高度相關的關系rt+1。rt+1與當前節(jié)點狀態(tài)作為低級策略網絡的輸入進行細致推理得到下一步的動作選擇。為防止模型出現(xiàn)過擬合問題，本文還引入了dropout策略對高級策略網絡和低級策略網絡進行動作退出處理，暫時性地隨機隱藏部分神經元，降低模型的參數(shù)量。

為了使模型收益最大化，本文通過引入全局獎勵和交互獎勵函數(shù)構造出交互獎勵模塊，智能體到達目標關系和實體時給予其全局獎勵，否則通過交互獎勵函數(shù)對高級智能體和低級智能體作出的每一步選擇進行相似度計算，并將其作為獎勵分數(shù)及時給予智能體相應的獎勵，加強了高級策略網絡和低級策略網絡之間的聯(lián)系，提高了模型推理準確度。

2 策略網絡

首先對預訓練的實體嵌入進行K-means++聚類，將原知識圖譜根據(jù)關系相似度劃分為多個節(jié)點簇，再利用實體之間的關系來加強這些節(jié)點簇之間的聯(lián)系，得到處理后的知識圖譜G′，在此基礎上進行分層強化學習（hierarchical reinforcement learning，HRL）的知識推理。為了保證模型的糾錯能力，本文方法還對知識圖譜中的三元組〈h，r，t〉添加了逆三元組〈t，r-1，h〉，通過這些逆三元組，智能體能夠在推理出現(xiàn)錯誤時實現(xiàn)后退操作。本文將知識推理過程分為高級策略網絡推理和低級策略網絡推理兩部分，通過高級策略網絡獲得的關系，指導低級策略網絡完成具體的動作選擇，找到目標實體后，此次推理任務結束。

2.1 高級策略網絡

將當前節(jié)點et、給定查詢關系rq通過GRU模塊對歷史推理路徑進行編碼，得到的歷史編碼信息ht-1作為高級策略網絡的輸入，在對知識圖譜進行K-means++算法分簇處理后，將與當前時刻所在節(jié)點相連接的關系作為候選關系集合，構建出初步的高級策略網絡πh′θ，再通過dropout策略對中部分神經元進行隨機隱藏，得到最終的高級策略網絡πh′θ。高級智能體在高級策略網絡的指導下，選擇出概率較高的關系作為下一時刻的關系選擇。高級策略網絡如圖2所示。

由表1可以看出，本文方法在NELL-995數(shù)據(jù)集上取得了最好的推理效果。對比數(shù)據(jù)集來看，F(xiàn)B15K-237的數(shù)據(jù)比NELL-995稀疏，而稀疏環(huán)境往往會導致大量的路徑被截斷，不利于RL代理的多跳推理路徑的探索，所以NELL-995上的知識推理效果要普遍優(yōu)于FB15K-237。在FB15K-237數(shù)據(jù)集中，hits@1和hits@3指標均有提高，而hits@10和MRR指標卻下降，導致該現(xiàn)象的原因可能是MultiHop模型是單智能體推理模型，雖然部分指標在長路徑推理中效果不如本文方法，但也因此導致MultiHop模型結構要比本文方法簡單，降低了模型的復雜度，使其hits@10和MRR指標要優(yōu)于本文方法；在NELL-995數(shù)據(jù)集中，各項指標均有明顯提升，分析其原因，即使本文方法由于需要多智能體導致資源消耗較大，可由于NELL-995數(shù)據(jù)集相比較FB15K-237數(shù)據(jù)集而言規(guī)模較小，模型復雜導致的資源消耗問題也不會使模型效果太差。TransE模型作為結構最簡單的基于嵌入的模型，在保證連通性的同時大大降低了計算復雜度，相比較其他模型而言，也能在MRR指標上取得較好的效果，但是該類方法解釋性較低；而基于強化學習的知識推理不僅推理出結果，還可以提供整條推理路徑，大大增加了推理過程的可解釋性。

4.2 消融實驗

為了更好地論證本文模型引入聚類算法、分層策略網絡結構和交互獎勵機制的有效性，使用平均倒數(shù)排名MRR和推理結果命中率hits@k作為評價指標，在FB15K-237和NELL-995數(shù)據(jù)集上對方法中三個模塊進行了消融實驗，結果如表2所示。

通過消融實驗證明了本文方法中三個模塊的有效性。由表2結果可知，三個模塊均對模型推理效果存在一定的影響，在NELL-995數(shù)據(jù)集上的影響尤為明顯。這主要是該數(shù)據(jù)集規(guī)模較小，只有18個關系類型，而高級策略網絡在進行關系選擇時受數(shù)據(jù)集關系數(shù)量的影響較大，所以與FB15K-237數(shù)據(jù)集相比，在NELL-995數(shù)據(jù)集進行知識推理時加入高級策略進行關系選擇，會大大提高推理的準確度。本文方法在進行知識推理任務前，先對知識圖譜進行聚類處理，使相似度高的節(jié)點彼此靠近，提高了智能體所做選擇的準確度；在進行知識推理時，通過交互獎勵機制對智能體的每一步關系選擇和動作選擇及時地給予獎勵，對于常見的基于強化學習的知識推理模型中的路徑多樣性獎勵、路徑長度獎勵和單獨的全局獎勵而言，本文模型的交互獎勵函數(shù)可以對智能體每一時刻的選擇及時地給予獎勵，幫助模型選擇更高獎勵的行為，有效解決了基于強化學習的知識推理模型在推理過程中遇到的稀疏獎勵問題，實現(xiàn)收益最大化，因此刪除模型中的聚類模塊和獎勵模塊對模型的推理效果也存在一定影響。

4.3 案例研究

通過實驗結果與消融實驗結果分析，可以看出本文分層強化學習框架在知識圖譜推理上的優(yōu)越性。首先，通過聚類算法對知識圖譜進行分簇處理，使關系類型較為相似的事實聚集在一起，便于后續(xù)進行知識推理時的關系選擇和動作選擇；其次，通過分層策略將知識推理分為兩部分，高級智能體在高級策略網絡的指導下先選擇出與查詢關系高度相關的關系作為下一時刻的關系選擇，而低級策略網絡只針對與高級策略網絡中選擇的關系相連接的實體進行概率分布計算，低級智能體根據(jù)實體概率分布選擇出下一時刻的動作，大大降低了動作空間的大小，不僅節(jié)約了計算資源，還提高了模型推理準確度。為了更直觀地表示本文模型在推理時尋找推理路徑的過程，本節(jié)對路徑推理進行案例研究，如圖4所示。

圖4中的例（a）（b）說明了本文模型能夠完成不同推理任務的路徑推理，其中，由于知識圖譜中存在對已知事實構建的逆三元組，所以在完成例（a）推理任務時可以通過逆三元組及時找到與目標實體高度相關的實體。逆三元組還可以在智能體作出錯誤決策時及時退回，糾正之前作出的錯誤決定，實現(xiàn)路徑糾錯。

為了評估本文模型的分層策略在進行知識推理過程中路徑搜索的效率，本節(jié)還對分層策略進行消融（-HRL），與本模型的路徑搜索成功率進行對比分析，路徑搜索成功率如表3所示。

由表3的實驗結果可知，引入分層策略，F(xiàn)B15K-237數(shù)據(jù)集中的路徑搜索成功率提升了2.4%，NELL-995數(shù)據(jù)集中的路徑搜索成功率提升了4.2%。其原因可能是在知識推理過程中進行具體的動作選擇時，只將與所選關系相連接的實體作為候選動作空間，大大降低了動作空間的大小，提高了模型的路徑搜索成功率。因此，本文通過分層策略進行知識推理，能夠有效提升知識推理過程中的路徑搜索成功率，從而提升模型的知識推理準確度。

5 結束語

本文提出了一種多智能體的強化學習知識推理方法MutiAg-HRL。模型通過使用分層策略方法，將知識推理過程分解為兩個馬爾可夫序列決策過程，有效解決了模型在進行長路徑推理時動作空間過大的問題；在進行強化學習推理之前采用聚類算法對知識圖譜進行處理，輔助智能體更準確地進行下一步選擇；通過交互獎勵機制及時給予智能體獎勵，防止模型出現(xiàn)獎勵稀疏的問題，提高了模型的推理能力。

在未來的研究中，將考慮在分層強化學習中引入規(guī)則挖掘模塊，在進行知識推理之前對與給定查詢高度相關的規(guī)則進行挖掘，用于指導模型進行知識推理，進而再度提升模型的知識推理效果。此外，還將進一步優(yōu)化模型的獎勵機制，幫助模型更快地找到目標實體。

參考文獻：

［1］劉玉華， 翟如鈺， 張翔， 等. 知識圖譜可視分析研究綜述［J］. 計算機輔助設計與圖形學學報， 2023，35（1）： 23-36. （Liu Yuhua， Zhai Ruyu， Zhang Xiang， et al. Review of knowledge graph visual analysis［J］. Journal of Computer Aided Design & Computer Graphics， 2023，35（1）： 23-36.）

［2］官賽萍， 靳小龍， 賈巖濤， 等. 面向知識圖譜的知識推理研究進展［J］. 軟件學報， 2018， 29（10）： 2966-2994. （Guan Saiping， Jin Xiaolong， Jia Yantao， et al. Knowledge reasoning over knowledge graph： a survey［J］. Journal of Software， 2018，29（10）： 2966-2994.）

［3］Wu Wenqing， Zhou Zhenfang， Qi Jiangtao， et al. A dynamic graph expansion network for multi-hop knowledge base question answering［J］. Neurocomputing， 2023，515： 37-47.

［4］Shahryar S， Han Qi， Bauke D V， et al. Methodology for development of an expert system to derive knowledge from existing nature-based solutions experiences［J］. MethodsX， 2023，10： 101978.

［5］Cui Hai， Peng Tao， Xiao Feng， et al. Incorporating anticipation embedding into reinforcement learning framework for multi-hop know-ledge graph question answering［J］. Information Sciences， 2022， 619： 745-761.

［6］Ji Shaoxiong， Pan Shirui， Cambria E， et al. A survey on knowledge graphs： representation， acquisition， and applications［J］. IEEE Trans on Neural Networks and Learning Systems， 2022，33（2）： 494-514.

［7］Liu Hao， Zhou Shuwang， Chen Changfang， et al. Dynamic know-ledge graph reasoning based on deep reinforcement learning［J］. Knowledge-Based Systems， 2022，241： 108235.

［8］于鐵忠， 羅婧， 王利琴， 等. 融合TuckER嵌入和強化學習的知識推理［J］. 計算機系統(tǒng)應用， 2022，31（9）： 127-135. （Yu Tiezhong， Luo Jing， Wang Liqin， et al. Knowledge reasoning combining tucker embedding and reinforcement learning［J］. Computer Systems & Applications， 2022，31（9）： 127-135.）

［9］Bordes A， Usunier N， Alberto G， et al. Translating embeddings for modeling multi-relational data［C］//Proc of Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2013： 2787-2795.

［10］Wang Zhen， Zhang Jianwen， Feng Jianlin， et al. Knowledge graph embedding by translating on hyperplanes［C］//Proc of the 28th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2014： 1112-1119.

［11］Trouillon T， Welbl J， Riedel S， et al. Complex embeddings for simple link prediction［C］//Proc of the 33rd International Conference on International Conference on Machine Learning.［S.l.］： JMLR.org， 2016： 2071-2080.

［12］Dettmers T， Minervini P， Stenetorp P， et al. Convolutional 2D know-ledge graph embeddings［C］//Proc of the 32nd AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2018： 1811-1818.

［13］Wang Zikang， Li Linjing， Zeng Dajun. SRGCN： graph-based multi-hop reasoning on knowledge graphs［J］. Neurocomputing， 2021， 454： 280-290.

［14］Zhang Ying， Meng Fandong， Zhang Jinchao， et al. MKGN： a multi-dimensional knowledge enhanced graph network for multi-hop question and answering［J］. IEICE Trans on Information and Systems， 2022， E105.D（4）： 807-819.

［15］Li Dengao， Miao Shuyi， Zhao Baofeng， et al. ConvHiA： convolutio-nal network with hierarchical attention for knowledge graph multi-hop reasoning［J］. International Journal of Machine Learning and Cybernetics， 2023，14： 2301-2315.

［16］Du Zhengxiao， Zhou Chang， Yao Jiangchao， et al. CogKR： cognitive graph for multi-hop knowledge reasoning［J］. IEEE Trans on Knowledge and Data Engineering， 2021，35（2）： 1283-1295.

［17］Tiwari P， Zhu Hongyin， Pandey H M. DAPath： distance-aware know-ledge graph reasoning based on deep reinforcement learning［J］. Neural Networks， 2021，135（5-6）： 1-12.

［18］Xiao Yi， Lan Mingjing， Luo Junyong， et al. Iterative rule-guided reasoning over sparse knowledge graphs with deep reinforcement learning［J］. Information Processing and Management， 2022，59（5）： 103040.

［19］Li Shuangyin， Wang Heng， Pan Rong， et al. MemoryPath： a deep reinforcement learning framework for incorporating memory component into knowledge graph reasoning［J］. Neurocomputing， 2021， 419： 273-286.

［20］Saebi M， Krieg S， Zhang Chuxu， et al. Heterogeneous relational reasoning in knowledge graphs with reinforcement learning［J］. Information Fusion， 2022， 88： 12-21.

［21］Paulo H， Jemin G， Mou Shaoshuai. Distributed offline reinforcement learning［C］//Proc of the 61st Conference on Decision and Control. Piscataway， NJ： IEEE Press， 2022： 4621-4626.

［22］Kristina T， Danqi C， Patrick P， et al. Representing text for joint embedding of text and knowledge bases［C］//Proc of Conference on Empirical Methods in Natural Language Processing. Stroudsburg， PA： Association for Computational Linguistics， 2015： 1499-1509.

［23］Li Zixuan， Jin Xiaolong， Guan Saiping， et al. Path reasoning over knowledge graph： a multi-agent and reinforcement learning based method［C］//Proc of IEEE International Conference on Data Mining Workshops. Piscataway， NJ： IEEE Press， 2018： 929-936.

［24］Lin X V， Socher R， Xiong Caiming. Multi-hop knowledge graph reasoning with reward shaping ［EB/OL］. （2018-09-11）. https：//arxiv.org/abs/1808.10568.

［25］Adnan Z， Summaya S， Junde C， et al. Complex graph convolutional network for link prediction in knowledge graphs［J］. Expert Systems with Applications， 2022，200： 116796.

［26］Feng Jianzhou， Wei Qikai， Cui Jinman， et al. Novel translation knowledge graph completion model based on 2D convolution［J］. Applied Intelligence， 2022， 52（3）： 3266-3275.

［27］Zhang Denghui， Yuan Zixuan， Liu Hao， et al. Learning to walk with dual agents for knowledge graph reasoning［C］//Proc of the 36th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2022： 5932-5941.