在稀疏知識圖譜上進行動態預測完備的多跳推理
本篇題目《Dynamic Anticipation and Completion for Multi-Hop Reasoning over Sparse Knowledge Graph》，來自清華大學人工智慧研究院知識智慧研究中心，一作為博士生呂鑫。
Abstract
稀疏知識圖譜缺少必要的資訊與路徑，使得推理尤為艱難。本文提出適用於稀疏知識圖譜的DacKGR模型，該模型創新性提出
動態預測（dynamic anticipation，DA）
與
動態完備（dynamic completion，DC）
策略，可在一定程度上緩解稀疏性帶來的困境。
Introduction
知識圖譜面臨著嚴重的不完備（Incompleteness）問題，基於嵌入（Embedding-based）的方法預測知識缺少可解釋性（Interpretability）。而一些使用強化演算法的多跳推理模型不僅可以推理出預測結果，還提供可解釋的路徑。但這些模型在稀疏的知識圖譜上遭遇滑鐵盧。因此提出DA與DC策略。
DA：嵌入模型與多跳推理模型相比，在稀疏知識圖譜上有更好的魯棒性。因為嵌入模型依賴於知識圖譜中的
三元組
，而非路徑資訊。因此將嵌入模型的
預測資訊
注入到
狀態資訊
中，從而避免智慧體進行無意義的路徑搜尋。
DC：由於稀疏KG中的某些實體對缺乏通路，因此要擴充動作空間使得agent有路可走。
Methodology
強化學習框架
近幾年的研究將知識圖譜上的多跳推理建模成馬爾科夫決策過程（Markov Decision Process、MDP）。MDP包含的元件如下：
State：
狀態不僅與查詢關係
、當前實體
有關，而且與歷史路徑資訊
有關。因此狀態資訊可表示為
其中
是在t跳下，使用LSTM對歷史路徑資訊的編碼結果。
Action：
當前時刻
的狀態空間
表示從當前實體可選擇經由某條路徑到達另一個實體的所有可能路徑。同時增加
路徑，表示允許agent在當前實體上打轉，即“停止”。
Transition：
狀態下，選擇
動作，可到達
，狀態變為
Reward：
對於一個給定查詢
，如果最終到達ground truth節點
，則reward值為1。否則reward值為
，其中
為agent最終停止的節點，
函式為主流的KGE函式對該三元組的打分
。
策略網路
在第t跳，歷史資訊
由上一跳的歷史資訊與動作決定。
策略網路可表示為
動態預測/Dynamic Anticipation/DA
KGE模型不依賴於知識圖譜的連線性，因此可在稀疏的知識圖譜上有超越多跳推理模型的效能。
對於一個特定的查詢
，使用預訓練的KGE模型得到知識圖譜中所有實體成為該查詢目標實體的機率向量
，修改狀態state為：
![\boldsymbol s_{t} = [\boldsymbol e_{p};\boldsymbol r_{q};\boldsymbol e_{t};\boldsymbol h_{t}]](https://img.beesask.com/upload/website_attach/_JS=ItuMMvGofv6vIv=GcsVL+7IBJ5hWRgA=f+4ByoUm+BsDyb4UdlXi6n0BR0flxnOqoZoje3VoTyBDH=F06YZurB_OR0fliJOA++9Cc3EmZiZ4TG1OPt-04KWNvk5Qj7keIEyOZIG97vr+7ZTieXVrV2zRCQP4D7KC+sX-fh5ldua8cfdOPtnorBwPXw5PwBWzdv4NaKzqdarsejLmZSVrkXCNv3AF2NRPj.jpeg)
。
而對於
的選擇策略有三種：1）由機率分佈
取樣；2）從
中選擇機率最大的；3）加權求均。在實驗部分進行策略驗證。
動態完備/Dynamic Completion/DC
稀疏KG中，初始節點到目標節點常無通路，因此要擴充Action Space。
在狀態
下，可擴充行為集合為
。需要從
中選擇機率最高的行為
，機率計算公式：
。由於
的規模常常過大，因此可先進行關係r的選擇，再根據r選擇實體e。
狀態
下選擇關係
，先對關係集
計算attention值：
![\boldsymbol w = Softmax(MLP(s_{t}) · [r_{1}, · · · , r_{|R|}]) \\](https://img.beesask.com/upload/website_attach/Ym7zbBGvMY9NbicQ10X5HgTgG1rDF3WkbkWzZoMjyzR_cw0UXkUY0_U722tD8GLtI12FI+Pw6PNzX=RTLaW_OKzxoEEFAQigVOqij5S-OOQ_9IkF5klkvqfPtPT4foK++R3XLfxhSkUk_bsUIiG_KKats-9h3wJ4IOLwLaXWOYs_9rMFHFs_ZhfQaHBU3-eE+R3xI+XwKJIPIbUgIh+BKrsjZ.jpeg)
計算擴充行為空間的數量：
其中N是當前行為數，M是最大擴充行為數。
從
中選取 top
的關係集：
，對每個關係求目標實體的機率分佈，再從中取top k個目標實體。由此擴充行為空間：
策略最佳化
訓練過程進行最大回報：
![J(θ) = E_{(e_{s},r,e_{o})∈KG}E_{a_{1},...,a_{T−1}∈π_{θ}} [R(s_{T}|e_{s}, r)]\\](https://img.beesask.com/upload/website_attach/yglfuZgUgfWIzd36PaJAhzAoGSaIbQElhMMf4Fy7+Rvqgn_Th=tR-p0msLTc-qifSdA3q8kL1flI51r18bmu-nj02IAblbtmvjTrhDdr1flI5XNqrdnkcJN978TK1WH7Gkuaqm9JqXAjjv4mFBOk0gTNs8j7-q_nYI67Dvl82mVqLatEhD8e-n57s8NLcptdsZOLh19KfblJM8Mr348RcVZ9aQTK=_t7vK5reaore_uWjvMmv48e1z0Ss8jqObtdsZAJpcGQDqgmymrI3M8e=cq4s8Td-qEoRoO8DvG80.jpeg)
Experiments
資料集
baseline
在稀疏KG上的表現提升明顯，在其他KG中也有一定提升。sample策略由於其他兩個策略。
消融實驗
在FB15K-237-20%上進行對DA/DC的消融實驗。
僅有DC比僅有DA的效果更好，說明DA只是使得模型有更優質的選擇，並未根本上緩解KG的稀疏性。
擴充的狀態空間發揮作用了嗎？
第一行曲線會在開始上升，後陡然下降。因為擴充資訊存在噪聲，而剛開始時模型無法區別。隨著訓練次數增加，模型有了區別噪聲的能力。
增大，擴充資訊也增加，模型表現也更好。50%上幾乎沒有變化，因為模型的稀疏性不再嚴峻，對擴充資訊的依賴也更低。
例項分析
top3個推理路徑。下環線實體是目標實體。粗字型實體為擴充資訊。
該工作可在擴充資訊的質量上，繼續提升模型表現。