編者按：儘管知識圖譜推理的發展前景廣闊，但在收斂性和可解釋性上仍存在一定的問題。微軟亞洲研究院的研究員利用一個基於元啓發式方法的示例路徑抽取方法來以較低的標記代價提取示例路徑集合，進而提出了一個對抗的 Actor-Critic 模型來進行示例路徑指導下的路徑搜索。實驗結果表明，這一方法在推薦準確性和可解釋性方面均優於最新的基線方法。

知識圖譜推薦推理

知識圖譜如今被廣泛用於提高推薦算法的準確性方面。同時，知識圖譜上用戶-物品的多跳連接關係也賦予了系統進行推薦推理（Recommendation Reasoning）的能力，讓圖譜上的路徑可以用來表示推薦某個物品的具體原因。例如，在向用戶 Bob 推薦“Acalme Sneaker”這雙鞋時，推薦的原因可以從如下連接關係中推理得到：

這條路徑說明推薦“Acalme Sneaker”給 Bob，是因爲 Bob 曾經購買過同品牌（Nike）的鞋 Revolution 5 Running Shoe。

與基於自然語言的解釋相比，這種知識圖譜推理很少得出關於物品的錯誤論斷，例如錯誤地描述物品的品牌或生產商。這是因爲路徑上的邊都是知識圖譜中已經確爲事實的知識。另外，知識圖譜推理能夠忠實地反映出推薦模型的工作機理，這樣就增加了用戶的信任度和滿意度。

知識圖譜推理儘管有很好的發展前景，但是仍然存在着巨大的研究挑戰。傳統的推薦方法側重於根據用戶的偏好，爲給定的候選物品集合進行打分，而知識圖譜推理還需要在複雜的知識圖譜中識別可行的候選路徑（路徑查找）。現有研究主要的重心在前者， 常常使用缺乏有效監督的蠻力算法來進行路徑查找，導致了算法在收斂性和可解釋性方面的問題 。

收斂性 ：現有的方法缺少有效地指導和監督路徑查找的機制。例如，現有的窮舉搜索的方法可以枚舉知識圖譜上所有可能的候選路徑，但這在大規模的知識圖譜上是不可行的。REINFORCE 通過路徑採樣得到稀疏的獎勵信號，來逐漸地改進策略。由於獎勵信號的稀疏性和知識圖譜巨大的動作空間，使得這種反覆試驗的方法收斂性較差。

可解釋性 ：現有的方法僅優化推薦準確度這一個目標，無法保證生成的路徑有較高的解釋性。連接同一用戶-物品組合可能有多條路徑導致相同的推薦準確性，而某些路徑作爲推薦原因時的說服力並不強。爲了實現良好的可解釋性，將用戶真正感興趣的實體和關係類型納入路徑當中十分重要。同時，除了在路徑中納入上述的實體和關係類型，路徑本身的類型對可解釋性也很重要。例如，考慮以下兩種路徑類型：

“看過商品 A 的用戶也看過”這種類型的路徑在說服力上就弱於“買過商品 A 的用戶也買過”的路徑類型。

爲了解決上面的問題，本文嘗試通過引入不完善的示例路徑（Imperfect Demonstration Paths）來解決這些問題。文中介紹瞭如何使用極少標註快速得到示例路徑，還設計了一個基於模仿學習的知識圖譜推理框架，從而使示例路徑這樣的弱監督信號可以和增強學習中的稀疏獎勵信號自然結合。在這個框架的基礎上，我們 提出了對抗的 Actor-Critic（Adversarial Actor-Critic，ADAC）模型來進行示例路徑指導下的路徑搜索 。實驗表明， 該方法比現有的方法收斂得更快，同時能夠獲得更好的推薦準確性和可解釋性。

示例路徑抽取

爲了得到對知識圖譜推理有用的不完善的示例路徑，我們提出了一個基於元啓發式方法的抽取方法。元啓發式方法是“可被用來定義啓發式方法的概念”，常被用來解決組合優化問題。通過指定示例路徑需要的屬性，來定義元啓發方法。這些屬性被進一步用來定義示例路徑抽取的啓發式規則。具體來說，考慮以下三種屬性：

P1：可得性 。示例路徑通過較低的標記代價得到。

P2：可解釋性 。示例路徑比隨機採樣得到的路徑更有解釋性。

P3：準確性 。示例路徑指向準確的推薦結果。例如，該路徑能夠連接用戶和他/她交互過的物品。

只要滿足上述三個屬性，抽取的示例路徑就被認爲是有效的，即使它們是稀疏而且有噪聲的（不完善）。基於這些屬性，我們定義了三種抽取示例路徑的啓發式規則。

最短路徑 。研究表明，精煉的解釋降低了用戶的認知負擔，同時被認爲是更具解釋性的。因此用戶-物品組合之間更短的路徑比隨機採樣的連接更具解釋力（P2）。爲了保證準確性（P3），我們僅考慮連接用戶 u 和他交互過的物品 v_u 的路徑作爲示例路徑。具體而言，給定（u, v_u），首先從知識圖譜上去除 u 和 v_u 之間觀察到的交互。這樣就得到了一個新的知識圖譜。隨後將 G 視爲無權重的圖，並使用 Dijkstra 算法來自動生成 u 和 v_u 之間的最短路徑（P1）。將生成的最短路徑作爲示例路徑。之後對所有用戶和其交互過的物品重複這個過程，來得到一組示例路徑。

元路徑 。元路徑（Meta-Path）是實體類型和關係構成的序列。在知識圖譜推理中，元路徑自然對應着元級別的解釋策略。通過提供元路徑，就可以得到理想的解釋策略。我們的框架是通過極少量（1~3條）人工定義的元路徑來提高模型性能（P1）。只要這些元路徑被認爲比隨機採樣的元路徑更具解釋力，他們就應當是有效的（P2）。與現有的基於元路徑的方法相比，由於不需要上述預定義的元路徑是完備的或是最優的，所以這一方法可以顯著地減少人工標註的成本。之所以能夠使用這些並不完善的元路徑作爲輸入，是因爲我們利用了元路徑來指導路徑搜索，而非限制搜索空間。爲了基於這些預定義的元路徑生成示例路徑，我們在知識圖譜上進行了有限制的隨機遊走，將每個用戶 u 作爲隨機遊走的起點，然後僅採樣那些元路徑屬於預定義集合的路徑。在所有采樣得到的路徑中，只保留那些通向用戶交互過物品的路徑，並將其作爲示例路徑（P3）。

興趣路徑 。一個更具解釋力的推理路徑應當在實體級別符合用戶的興趣，比如路徑中包含用戶感興趣的實體。在一些數據集中，得到實體級別的用戶興趣相對比較容易。例如，在包含用戶評論的數據集中，可以通過查找實體是否出現在用戶的評論中，來自動判斷路徑上的實體是否符合用戶的興趣（P1）。在這種情況下，使用隨機遊走得到一組路徑，並查看每條路徑中的實體是否多數符合用戶興趣，並僅保留那些符合用戶興趣的路徑（P2），同時，去除那些沒有將用戶與其交互過的物品連接起來的路徑，以保證準確性（P3），並將剩餘路徑作爲示例路徑。

推薦推理的模仿學習框架

我們提出了一種能夠同時利用含有用戶交互關係的知識圖譜和提取的示例路徑的方法。模型要解決的主要問題，是如何在一個統一的框架內，對不完善的示例路徑、觀察到的交互關係和知識圖譜上的隱含事實進行高效地建模。爲了實現這一目標，我們設計了對抗 Actor-Critic（ADversarial Actor-Critic，ADAC）模型，綜合應用了基於 Actor-Critic 的強化學習和對抗模仿學習。

圖1：對抗 Actor-Critic 模型進行示例路徑指導下的路徑搜索

如圖1所示的模型框架。其中，知識圖譜是馬爾科夫決策過程環境（MDP  environment）的一部分。Actor 用來學習路徑搜索策略，它與 MDP 環境進行交互，從而得到知識圖譜上的搜索狀態（State）和可能的行爲（Action）。通過環境給出的獎勵（reward）反饋 _ , ，Actor 判斷現在的策略是否是用戶感興趣的。爲了進一步集成示例路徑，我們設計了一個對抗模仿學習模塊（藍色部分），包含有兩個鑑別器（Discriminator）。鑑別器用來區分專家路徑和 Actor 生成的路徑，而 Actor 通過模仿專家示例路徑，來“混淆”鑑別器，使它更難作出區分。當動作路徑與專家示例路徑在元路徑級別（Meta-path Level）相似和路徑級別（Path Level）相似時，模仿學習模塊就會分別給 Actor 以更高的元路徑獎勵 _ , 及路徑獎勵 _ , 。這樣就得到了三種類型的獎勵， _ , 、 _ , 和 _ , 。它們進一步由 Critic 建模，來精確地預測每個動作的價值。通過獎勵梯度的無偏估計，學得的價值信息就用來訓練 Actor。

Actor 網絡構建 。Actor 學習一個路徑搜索策略，它計算的是在狀態和可能的動作空間的條件下，動作的條件概率分佈。我們使用全連接層和 Softmax 函數來建模 Actor 網絡。

對抗模仿學習 。對抗模仿學習模塊包含兩個部分：路徑鑑別器和元路徑鑑別器。路徑鑑別器 _ 判斷在每個時間 時，Actor 是否能夠生成一個與示例路徑相似的路徑段，元路徑鑑別器 _ 通過比較元路徑，來判斷 Actor 所採用的總體解釋策略是否與示例路徑的策略相似。路徑鑑別器與元路徑鑑別器的損失函數和得到的獎勵有相似的形式：

Critic 網絡構建 。Critic 的目標是高效地建模來自強化學習（即 MDP 環境）和模仿學習（即鑑別器）的獎勵信息。給定狀態， Critic 網絡計算每個動作 _ 的價值爲 Q_ϕ (s_t,a_t)，並利用時間差分方法來學習 Critic 網絡。首先根據貝爾曼方程計算學習目標：

其中 _ 是混合獎勵，它一方面激勵路徑搜索策略，使之搜索到與示例路徑更相似的路徑，另一方面讓策略得到更高的推薦準確性。之後，Critic 通過最小化如下 TD 誤差（TD Error）來更新參數：

給定 _ （ _ , _ ），Actor 再通過最小化以下損失函數來學習參數：

性能評測

我們在亞馬遜三種不同的物品類別上驗證了提出的模型： Beauty（美妝產品）、Clothing Shoes and Jewelry（服飾鞋帽）和 Cell Phones and Accessories（手機及配件）。 這裏爲了公平只用了最短路徑得到示例（沒有額外人工標註）。 實驗結果表明，與基線方法相比，Actor-Critic 方法在推薦準確性方面取得了更好的結果。

表1：推薦準確性比較

爲了評估推理路徑的可解釋性，我們使用真實的評論文本設計了兩個評價指標。設計可解釋性評價指標的基本思想是，用戶發表的真實評論文本揭示了用戶-物品之間產生交互的原因。因此，如果一個推理路徑包含很多真實評論中提到的詞語，那它應當有很好的可解釋性。具體而言，對每個推薦正例，過濾掉評論中出現頻率大於5000或者 TF-IDF 得分小於0.1的詞語，將剩下的詞語作爲真實詞語。然後將路徑中的實體集合起來，並按照它們的頻率進行排序，將實體類型是 Word、Brand 或者 Category 的實體，提取其字符串作爲抽取的解釋詞語。我們通過比較推理路徑抽取的解釋詞語和真實詞語的相似程度來評價可解釋性。同時，也基於匹配詞語使用精確率（Precision）和召回率（Recall）來評價可解釋性。

表2：可解釋性比較

比較 ADAC 在 Beauty 和 Clothing 數據集上的收斂性可以看到，ADAC 通過有效利用示例路徑在路徑級別和元路徑級別的信息實現了高效地收斂。

圖2：收斂性比較

我們還對比了使用不同種類的示例路徑對模型準確性和可解釋性的影響。圖3展示了使用不同示例路徑得到的推理路徑，可以看到利用我們的模仿學習框架，模型不僅能夠找到與示例路徑相同類型的推理路徑，還能泛化到其它種類的路徑上來。

圖3：使用不同示例路徑生成的推理路徑

總結

本文設計了一種基於模仿學習的知識圖譜推理框架，來爲用戶進行可解釋推薦，它解決了知識圖譜推理時遇到的收斂性和可解釋性問題。 首先利用一個基於元啓發式方法的示例路徑抽取方法來以較低的標記代價提取示例路徑集合。 然後提出了一個對抗的 Actor-Critic 模型，進行示例路徑指導下的路徑搜索。 實驗結果表明，這一方法在推薦準確性和可解釋性方面均優於最新的基線方法。

瞭解更多技術細節，請點擊閱讀原文查看論文

Leveraging Demonstrations for Reinforcement Recommendation Reasoning over Knowledge Graphs

本文作者：趙康智（清華大學，微軟亞洲研究院實習生）、王希廷、謝幸

你也許還想看 ：