文章目錄

• 摘要
• 介紹
• 相關(guān)工作
• 方法
• • Mean Selection Rate (MSR) and Mean Replacement Rate (MRR

Incorporating Graph Attention Mechanism into Knowledge Graph Reasoning Based on Deep Reinforcement Learning

摘要

知識(shí)圖(KG)推理的目的是尋找關(guān)系的推理路徑，以解決KG中的不完全性問題。以前的許多基于路徑的方法，如PRA和DeepPath，要么缺乏記憶部件，要么在訓(xùn)練中卡住。因此，他們的表現(xiàn)總是依賴于良好的訓(xùn)練。本文提出了一種基于AttnPath的深度強(qiáng)化學(xué)習(xí)模型，該模型將LSTM和圖注意機(jī)制作為記憶組件。我們定義了平均選擇率(MSR)和平均替換率(MRR)兩個(gè)指標(biāo)來定量衡量查詢關(guān)系的學(xué)習(xí)難度，并利用它們?cè)趶?qiáng)化學(xué)習(xí)框架下對(duì)模型進(jìn)行微調(diào)。同時(shí)，提出了一種新的增強(qiáng)學(xué)習(xí)機(jī)制，使agent每一步都向前走，以避免agent在同一實(shí)體節(jié)點(diǎn)上不斷陷入停滯。在此基礎(chǔ)上，該模型不僅可以擺脫訓(xùn)練前的訓(xùn)練過程，而且與其他模型相比，可以達(dá)到最先進(jìn)的性能。我們使用不同的任務(wù)在FB15K-237和NELL- 995數(shù)據(jù)集上測(cè)試我們的模型。大量的實(shí)驗(yàn)表明，該模型與現(xiàn)有的許多最先進(jìn)的方法相比是有效的和有競(jìng)爭(zhēng)力的，并且在實(shí)踐中表現(xiàn)良好。

介紹

• 推理的方法

  • 基于規(guī)則
  • 基于路徑
  • 基于嵌入
    同時(shí)，它提供了一個(gè)新的視角，將深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning, DRL)引入到預(yù)測(cè)缺失環(huán)節(jié)的任務(wù)中，如DeepPath (Xiong et al.， 2017)，這是一種基于路徑的方法。DeepPath是第一個(gè)將DRL整合到KG推理中的作品。與PRA相比，它取得了顯著的改進(jìn)，但仍然存在一些缺點(diǎn)。首先，它缺少記憶部件，因此需要預(yù)先培訓(xùn)。訓(xùn)練前的操作需要為模型訓(xùn)練提供許多已知(或存在)的路徑。這種蠻力操作可能會(huì)使模型在預(yù)先訓(xùn)練的給定路徑上過度擬合。其次，在訓(xùn)練時(shí)對(duì)KG中不同的關(guān)系設(shè)置相同的超參數(shù)是不合適的，忽略了實(shí)體之間連接的多樣性。最后，當(dāng)代理選擇了一個(gè)無效的路徑時(shí)，它會(huì)停止并重新選擇，這會(huì)導(dǎo)致不斷地選擇這個(gè)無效的路徑，最后卡在一個(gè)節(jié)點(diǎn)上。因此，本文針對(duì)上述不足，提出了一種新的深度強(qiáng)化學(xué)習(xí)模型和算法。該模型也屬于基于路徑的框架。我們的貢獻(xiàn)可以總結(jié)如下

• DRL的缺陷

  • 缺少記憶部件，需要預(yù)先訓(xùn)練
    • 訓(xùn)練前的操作需要為模型訓(xùn)練提供許多已知(或存在)的路徑–》過擬合
  • 不同關(guān)系超參數(shù)不同，忽略了實(shí)體之間連接的多樣性
  • 當(dāng)代理選擇了一個(gè)無效的路徑時(shí)，它會(huì)停止并重新選擇–卡住

• 本文的貢獻(xiàn)

  • LSTM+圖attention作為記憶組件，不用再預(yù)訓(xùn)練了
  • 定義了兩個(gè)度量標(biāo)準(zhǔn)(MSR和MRR)，以定量地度量學(xué)習(xí)關(guān)系的可替換路徑的難度，這些可替換路徑用于對(duì)模型進(jìn)行微調(diào)。
  • 提出了一種新的增強(qiáng)學(xué)習(xí)機(jī)制，通過強(qiáng)制agent每一步都向前走來避免agent在同一實(shí)體節(jié)點(diǎn)上不斷陷入停滯。

相關(guān)工作

到目前為止，已經(jīng)有許多工作被提出來解決KG不完全的問題。

• 基于規(guī)則的方法，如
  • ProPPR (Wang and Cohen, 2016)和Neural LP (Yang et al.， 2017)，通過人工或數(shù)學(xué)邏輯規(guī)則生成推理規(guī)則，然后根據(jù)現(xiàn)有的三元組將其應(yīng)用于填補(bǔ)缺失的環(huán)節(jié)。雖然這類方法有堅(jiān)實(shí)的數(shù)學(xué)背景，但它們很難擴(kuò)展到大型的kg，因?yàn)樗鼈冎苯硬僮鞣?hào)，而可能的推理路徑的數(shù)量與實(shí)體的數(shù)量呈指數(shù)關(guān)系。
• 基于嵌入的方法，如
  • TransE (Bordes et al.， 2013)和TransR (Lin et al.， 2015)，將實(shí)體和關(guān)系映射到低維連續(xù)的向量空間中，獲取實(shí)體和關(guān)系之間的距離特征。然后，通過比較兩個(gè)訓(xùn)練實(shí)體嵌入和查詢關(guān)系嵌入之間的距離來判斷查詢關(guān)系是否存在。這種方法需要KG中的所有三元組都參與訓(xùn)練，只適用于單跳推理。
• 基于路徑的，如
  • PRA (Lao et al.， 2011)和DeepPath (Xiong et al.， 2017)，訓(xùn)練一個(gè)agent在一個(gè)KG上導(dǎo)航，找到某個(gè)關(guān)系的可替換路徑，然后將其作為下游任務(wù)的特征。路徑排序算法(PRA)是第一個(gè)基于路徑的推理方法。
  • Neelakantan等人開發(fā)了一個(gè)基于RNN的組合模型，該模型非原子性地組合了一條路徑的含義和多跳關(guān)系連接的原因(Neelakantan et al.， 2015)。
  • Guu等人提出了一種軟邊遍歷算子，該算子可以遞歸地應(yīng)用于預(yù)測(cè)路徑，減少TransE和TransR等單跳KG完井方法面臨的級(jí)聯(lián)傳播誤差(Guu et al.， 2015)。
  • Toutanova等人提出了一種動(dòng)態(tài)規(guī)劃算法，該算法將所有有界長度的關(guān)系路徑合并到一個(gè)KG中，并對(duì)組合路徑表示中的關(guān)系和中間節(jié)點(diǎn)進(jìn)行建模(Toutanova等人，2016)。這樣的表示可以幫助生成更多高質(zhì)量的推理路徑。
  • Das等人將DeepPath (Xiong等，2017)改進(jìn)為MINERVA (Das等，2018)，后者從QA s的角度看待KG。它去掉了預(yù)訓(xùn)練，引入LSTM來記憶以前走過的路徑，并訓(xùn)練一個(gè)代理在某個(gè)實(shí)體上運(yùn)行，如果它相信這個(gè)實(shí)體是正確的答案。
  • Lin等人通過引入獎(jiǎng)勵(lì)形成和行動(dòng)退出來改進(jìn)這兩種方法(Lin et al.， 2018)。獎(jiǎng)勵(lì)塑造用動(dòng)態(tài)懲罰代替無用選擇的固定懲罰，既可以基于基于邊緣的預(yù)訓(xùn)練嵌入，如TransE，也可以基于基于概率的嵌入，如ConvE (Dettmers et al.， 2018)。而action dropout則隨機(jī)地掩蓋了一定比例的有效action，以減少查詢關(guān)系的不相關(guān)路徑。
  • DIVA (Chen et al.， 2018)將路徑作為潛在變量，將關(guān)系作為觀測(cè)變量，建立變量推理模型，完成KG推理任務(wù)。它還使用波束搜索來擴(kuò)大搜索范圍。
  • M-Walk (Shen et al.， 2018)利用另一種稱為蒙特卡羅樹搜索(Monte Carlo Tree Search, MCTS)的RL算法來解決稀疏獎(jiǎng)勵(lì)問題。注意機(jī)制首次被引入多跳KG推理中(Wang et al.， 2018)。但是，它只計(jì)算查詢嵌入的注意權(quán)重和所有找到的路徑嵌入。它們被用來幫助判斷vanilla模型找到的答案是否正確。

方法

• 由于我們使用強(qiáng)化學(xué)習(xí)(RL)作為序列決策模型的訓(xùn)練算法，我們首先在KG推理中引入RL框架的基本元素，包括環(huán)境、狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)。

• 環(huán)境:在本任務(wù)中，環(huán)境指的是整個(gè)KG，不包括查詢關(guān)系及其逆。整個(gè)培訓(xùn)過程環(huán)境保持一致

• 狀態(tài):agent的狀態(tài)由三個(gè)部分連接:

  • 嵌入部分、
    • deepPath中用了TransE,這里用TransD（映射到關(guān)系所帶的向量空間中
    • $$\begin{gathered} e^{\prime }=(r_p{e}_p^{\prime }+I)e \\ {m}_t=(e_t^{\prime },e_{target}^{\prime }?e_t^{\prime }) \end{gathered}$$
  • LSTM部分
    • $h_t=LSTM(h_{t?1},m_t)$
  • 圖形注意部分

• 動(dòng)作：選哪個(gè)關(guān)系（邊）走

  • 有關(guān)系-有效邊
  • 無關(guān)系-無效邊

• 獎(jiǎng)勵(lì)

  • 一步的無效操作：-1
  • 可以獲得全局解的（一整條路徑）：convE(a series of actions can lead to ground truth)
  • 獎(jiǎng)勵(lì)是全局精度、路徑效率和路徑多樣性的加權(quán)和。根據(jù)約定，全局精度設(shè)置為1，路徑效率為路徑長度的倒數(shù)，因?yàn)槲覀児膭?lì)代理盡可能少的步進(jìn)。(和DeepPath一樣）

• 使用注意力機(jī)制Graph Attention mechanism (GAT)

  • self-attention在實(shí)體層
  • attention權(quán)重用一層前饋神經(jīng)網(wǎng)絡(luò)訓(xùn)練
  • $$\begin{gathered} {\alpha }_{ij}=LeakyReLU(a^T(W_{e{i}^{\prime }},W_{e{j}^{\prime }}） \\ 只計(jì)算它和它的鄰居，j是與i相鄰的節(jié)點(diǎn)，然后normalize \\ {\alpha }_{ij}=\frac{{\alpha }_{ij}}{{\Sigma }_{k\in N_i}{\alpha }_{ik}} \\ {a}_i={\Sigma }_{k\in N_i}{\alpha }_{ik}{W}_{e_k} \\ {s}_{i,t}=[m_{i,t};h_t;a_t] \end{gathered}$$
  • 然后輸入一個(gè)三層前饋神經(jīng)網(wǎng)絡(luò)，其最終輸出是一個(gè)長度等于所有關(guān)系的數(shù)量(以KG為單位)的Softmax概率。代理選擇一個(gè)動(dòng)作并獲得獎(jiǎng)勵(lì)。當(dāng)它成功到達(dá)尾部實(shí)體或在指定次數(shù)內(nèi)沒有到達(dá)時(shí)，整個(gè)事件的獎(jiǎng)勵(lì)將用于更新所有參數(shù)。
    
    

Mean Selection Rate (MSR) and Mean Replacement Rate (MRR

對(duì)于不同的查詢關(guān)系，需要為每個(gè)查詢關(guān)系訓(xùn)練不同的模型。而在實(shí)踐中，每個(gè)關(guān)系的難度值都是不同的。某些關(guān)系可能具有更多的替換關(guān)系，這表明agent可以很容易地選擇從head實(shí)體到tail的替換路徑。因此，我們發(fā)明了兩個(gè)指標(biāo)，平均選擇率(MSR)和平均替代率。在這里，定量地測(cè)量每個(gè)關(guān)系的不同值。

較低的MSR表示學(xué)習(xí)r比較困難，因?yàn)榕c關(guān)系r相關(guān)的實(shí)體可能有更多方面。

較高的MRR表示一個(gè)關(guān)系可能有更多的替換關(guān)系，因此更容易學(xué)習(xí)，因?yàn)榇砜梢灾苯舆x擇一個(gè)替代關(guān)系來到達(dá)目的地。在我們的模型中，我們有三種方法來防止過度擬合:L2正則化、dropout和action dropout。然而，對(duì)于比較容易學(xué)習(xí)的關(guān)系(高M(jìn)SR和MRR)，我們希望實(shí)施更多的正規(guī)化，以鼓勵(lì)代理尋找更多樣化的路徑，而不是過度擬合立即成功。否則，對(duì)于較難學(xué)習(xí)的關(guān)系(MSR和MRR較低)，我們最好關(guān)注路徑找到的成功率，因此我們應(yīng)該減少正規(guī)化。
為簡(jiǎn)單起見，我們使用指數(shù)來計(jì)算關(guān)系r的難度系數(shù)。它被定義為exp(MSR?+MRR?)，并分別乘以三種正則化方法的基本速率。正則化方法的基本速率是基于KG的，在相同KG中的所有關(guān)系之間共享。

在此基礎(chǔ)上，我們提出了一種新的訓(xùn)練算法，如算法1所示。在我們的算法中，我們的貢獻(xiàn)之一是，**當(dāng)代理選擇了一個(gè)無效路徑時(shí)，我們的模型不僅懲罰了它，而且還迫使它選擇一個(gè)有效的關(guān)系來前進(jìn)。**神經(jīng)網(wǎng)絡(luò)的概率在所有有效關(guān)系上被歸一化，這些有效關(guān)系反過來又決定了強(qiáng)制動(dòng)作的概率。初始化之后，第6行根據(jù)網(wǎng)絡(luò)的輸出對(duì)操作進(jìn)行采樣。當(dāng)代理選擇了一個(gè)無效的操作時(shí)，第7行10被執(zhí)行，第9行10強(qiáng)制代理前進(jìn)。當(dāng)代理選擇一個(gè)有效的操作時(shí)，執(zhí)行第12行。22和25行19日更新參數(shù)無效的行為,有效的行動(dòng)成功的事件,和有效的行動(dòng)在一個(gè)不成功的事件,分別與獎(jiǎng)賞-1，Rtotal Rshaping。

總結(jié)

以上是生活随笔為你收集整理的论文学习2-Incorporating Graph Attention Mechanism into Knowledge Graph Reasoning Based on Deep Reinforce的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。