協(xié)同過濾(3): Neural Logic Reasoning

前言

  • 發(fā)表在CIKM2020上的一篇關(guān)于通用CF推薦的論文，引入了邏輯推理的思想!

  • 源碼鏈接：https://github.com/evison/NLR/

  • 碼字不易，好心人隨手點個贊

  • 本文為自己的論文閱讀筆記，并非完整的論文翻譯，如有錯誤/問題歡迎評論區(qū)指正，僅為參考，建議首先閱讀原文

  • 如需轉(zhuǎn)載引用，請務(wù)必提前聯(lián)系本人并在文中附上原鏈接及相應(yīng)說明，包括作者信息（阿瑟）

  • 關(guān)于該論文，涉及符號系統(tǒng)等一些概念和思想，可以參考https://blog.csdn.net/weixin_43868020/article/details/107191994

摘要

近年來，深層神經(jīng)網(wǎng)絡(luò)在許多領(lǐng)域取得了成功。大多數(shù)神經(jīng)網(wǎng)絡(luò)設(shè)計背后的基本思想是從數(shù)據(jù)中學(xué)習(xí)相似模式進行預(yù)測和推理，這缺乏認知推理能力。然而，具體的推理能力是許多理論和實踐問題的關(guān)鍵。

另一方面，傳統(tǒng)的符號推理方法在進行邏輯推理方面有很好的效果，但它們大多是直接的基于規(guī)則的推理(Hard rule-based reasoning)，這限制了它們對不同任務(wù)的泛化能力，因為不同的任務(wù)需要不同的規(guī)則。

推理和泛化能力對于推薦系統(tǒng)這樣的預(yù)測任務(wù)都很重要，推理提供了用戶歷史和目標物品之間強有力的關(guān)聯(lián)以便精確預(yù)測，泛化能夠幫助模型在噪聲輸入下構(gòu)造健壯的用戶畫像(robust user portrait)。

本文中提出了邏輯集成神經(jīng)網(wǎng)絡(luò)(LINN)來集成深度學(xué)習(xí)和邏輯推理的能力。LINN 是一種動態(tài)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，根據(jù)輸入的邏輯表達式構(gòu)建計算圖。它學(xué)習(xí)基本的邏輯運算，例如OR\AND\NOT作為神經(jīng)模塊，并通過網(wǎng)絡(luò)進行命題邏輯推理。

理論任務(wù)實驗表明，LINN 在求解邏輯方程和變量方面有顯著的性能。此外，我們通過將推薦任務(wù)描述為一個邏輯推理問題，在推薦的實際任務(wù)上對我們的方法進行了驗證。

引言

雖然神經(jīng)網(wǎng)絡(luò)通常對具有相似分布的數(shù)據(jù)具有良好的泛化能力，但這些方法的設(shè)計思想使得神經(jīng)網(wǎng)絡(luò)在許多理論和實際問題上很難進行邏輯推理分析。然而，邏輯推理是一種重要的智能能力，它對許多理論任務(wù)，如解決邏輯方程，以及實際任務(wù)，如醫(yī)療決策支持系統(tǒng)，法律助理，和個性化推薦系統(tǒng)至關(guān)重要。

例如，在推薦任務(wù)中，推理可以幫助建立用戶和項目之間的復(fù)雜關(guān)系模型(例如，用戶喜歡項目 a，但不喜歡項目 b →用戶喜歡項目 c) ，特別是對于那些罕見的模式，這通常是神經(jīng)網(wǎng)絡(luò)難以捕捉的。

進行推理的一種典型方法是通過邏輯推理(logical inference)。事實上，在機器學(xué)習(xí)方法出現(xiàn)之前，基于符號推理(symbolic reasoning)的邏輯推理一直是人工智能的主流方法，它也是傳統(tǒng)人工智能(GOFAI)中許多專家系統(tǒng)的基礎(chǔ)。然而，傳統(tǒng)的邏輯推理的符號推理方法大多是基于規(guī)則的硬推理，由于規(guī)則難以定義，不易適用于現(xiàn)實世界中的許多任務(wù)。

例如，在推薦系統(tǒng)中，如果我們把每個物品都看作一個符號，我們就很難根據(jù)手工設(shè)計的規(guī)則來捕捉物品之間的所有關(guān)系。此外，個性化用戶偏好帶來了各種交互序列，這可能帶來沖突推理規(guī)則，例如，一個用戶可能同時喜歡 a 和 b，而另一個喜歡 a 的用戶可能不喜歡 b。 數(shù)據(jù)中的這種噪聲使得設(shè)計適合于新數(shù)據(jù)的推薦規(guī)則變得非常具有挑戰(zhàn)性。

為了統(tǒng)一利用深度神經(jīng)網(wǎng)絡(luò)的泛化能力和邏輯推理，提出了邏輯集成神經(jīng)網(wǎng)絡(luò)(LINN) ，基于神經(jīng)網(wǎng)絡(luò)進行邏輯推理的神經(jīng)結(jié)構(gòu)。LINN 用向量表示邏輯變量，每個基本邏輯運算(AND/OR/NOT)作為一個基于邏輯正則化的神經(jīng)模塊來學(xué)習(xí)。

由于由同一組變量組成的邏輯表達式可能具有完全不同的邏輯結(jié)構(gòu)，因此捕獲邏輯的結(jié)構(gòu)信息對邏輯推理至關(guān)重要。為了解決這個問題，LINN 根據(jù)輸入的邏輯表達式動態(tài)構(gòu)造其神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，這不同于許多固定計算圖形的神經(jīng)網(wǎng)絡(luò)。通過在神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中編碼邏輯結(jié)構(gòu)信息，LINN 可以靈活處理指數(shù)級的邏輯表達式。

LINN模型

在 LINN，邏輯表達式中的每個邏輯變量都表示為一個向量嵌入，每個基本邏輯運算(例如，AND/OR/NOT)都學(xué)習(xí)為一個神經(jīng)模塊。大多數(shù)神經(jīng)網(wǎng)絡(luò)都是基于獨立于輸入的固定神經(jīng)結(jié)構(gòu)而開發(fā)的，無論是手動設(shè)計的還是通過神經(jīng)結(jié)構(gòu)搜索學(xué)習(xí)的。 不同的是，我們的 LINN 體系結(jié)構(gòu)的計算圖是依賴于輸入的，并根據(jù)輸入邏輯表達式動態(tài)地構(gòu)建。 我們進一步利用邏輯正則化(Logic Regulaizers)對神經(jīng)模塊，以保證每個模塊進行預(yù)期的邏輯操作。

1. 神經(jīng)模塊的邏輯操作

命題邏輯的表達式由邏輯常量(True 或 False，標記為 T/F)、邏輯變量(v)和基本邏輯運算(否定?、合取∧和析取∨)組成。在 LINN 中，邏輯運算被學(xué)習(xí)為三個神經(jīng)模塊。Leshno 等證明了具有非多項式激活函數(shù)的多層前饋網(wǎng)絡(luò)可以逼近任何函數(shù)。這為我們利用神經(jīng)模塊學(xué)習(xí)邏輯操作提供了理論支持。與大多數(shù)將輸入變量作為向量表示學(xué)習(xí)的神經(jīng)模型類似，T、F 和所有邏輯變量都被表示為具有相同維數(shù)的向量。給定邏輯表達式E={e_i}_{i=1}^m及其對應(yīng)的值Y={y_i}_{i=1}^m,(T/F)，一個表達式示例如下：

相關(guān)符號表示可以定義為：\mathbf{v}=AND(\mathbf{v_i},\mathbf{v_j}) = v_i∧v_j下圖展示了LINN的結(jié)構(gòu)示例


圖中下的框顯示了LINN如何構(gòu)造一個邏輯表達式。每個中間向量表示邏輯表達式的一部分，最后得到整個邏輯表達式 e的向量表示。
這樣，雖然嵌入矩陣的大小隨著邏輯變量總數(shù)的線性增長，但算子網(wǎng)絡(luò)中的參數(shù)總數(shù)保持不變。
此外，由于表達式是按樹結(jié)構(gòu)組織的，因此可以從葉子到根遞歸地計算它。
為了計算表達式的 T/F 值，我們計算了表達式向量和 T/F向量之間的相似度，如上面的框所示。這里 Sim (,)也是一個神經(jīng)模塊，用來計算兩個向量之間的相似度，并輸出0到1之間的相似度值。
輸出
p = Sim (\mathbf{e},\mathbf{t})
計算 模型認為表達式為真的可能性。對于不同的任務(wù)，LINN 可以使用不同的任務(wù)特定的損失函數(shù)進行訓(xùn)練。例如，在一組表達式上訓(xùn)練 LINN 和預(yù)測其他表達式的 T/F 值可以看作是一個分類問題，我們可以采用交叉熵損失:

對于Top-n推薦，可以使用BPRLoss

2. 神經(jīng)模塊上的邏輯約束 Logical Regularization

到目前為止只學(xué)習(xí)了邏輯運算作為神經(jīng)模塊，但沒有明確保證這些模塊實現(xiàn)預(yù)期的邏輯運算。例如，任何與 False 連接的變量或表達式都應(yīng)得到F，即 w ∧ F= F，雙重否定應(yīng)該等于本身。
我們使用 w 代替 v，因為 w 既可以是單個變量(例如，vi) ，也可以是計算流程中間的表達式。LINN 應(yīng)該滿足基本的邏輯規(guī)則，盡管神經(jīng)結(jié)構(gòu)可能隱式地從數(shù)據(jù)中學(xué)習(xí)邏輯操作，但是如果我們對其加上具體的邏輯約束會更好指導(dǎo)學(xué)習(xí)邏輯。為了實現(xiàn)這一目標，文中定義了邏輯正則化(Logical Regularization)來規(guī)范模塊的行為，使它們能夠執(zhí)行一定的邏輯操作。完整的定義如下表所示：

這些規(guī)則完備地設(shè)定了三種基本邏輯運算的各種運算性質(zhì)。相應(yīng)的約束也是建立在LINN定義的特征空間中，而非完整的向量空間中。邏輯正則鼓勵LINN 學(xué)習(xí)神經(jīng)模塊參數(shù)，以滿足模型中涉及的變量/表達式的推理性質(zhì)，這比整個向量空間小得多。

在 LINN 中，常量True的向量T在訓(xùn)練和測試過程中是隨機初始化并且固定的，作為定義T向量的邏輯空間中的標準向量(Anchor vector)。因此可以用 NOT (t)來計算False向量 F。
最后的損失函數(shù)可以定義為：

值得注意的是，除了上面列出的邏輯正則化之外，命題邏輯系統(tǒng)還應(yīng)該滿足其他邏輯規(guī)則，如結(jié)合律、交換律和分配律。
為了考慮交換律，在計算正則化時，可以將由合取或析取的順序隨機化。例如，w ∧ t 的網(wǎng)絡(luò)結(jié)構(gòu)可以是 AND (w，t)或 AND (t，w) ，w ∨ w 的網(wǎng)絡(luò)結(jié)構(gòu)可以是 OR (w，NOT (w))或 OR (NOT (w) ，w)。這樣，當(dāng)輸入是同一表達式在交換性方面的不同形式時，可以訓(xùn)練模型構(gòu)建相同的向量表示。

沒有明確的方法約束其他邏輯規(guī)則的模塊，這些規(guī)則對應(yīng)于更復(fù)雜的表達式變量，如分配律和摩根定律（非(P 且 Q) = (非 P) 或 (非 Q)
非(P 或 Q) = (非 P) 且 (非 Q)）。

為了解決這個問題，我們確保輸入表達式具有相同的規(guī)范形式-- 例如，析取范式-- 因為任何命題邏輯表達式都可以轉(zhuǎn)換為析取范式(DNF)或合取范式(CNF) ，而且每個表達式都對應(yīng)于一個計算圖。這樣就避免了對分配律和摩根定律的神經(jīng)模塊進行規(guī)范化的必要性。

3. 長度正則化 Length Regularization over Logic Variables

邏輯變量的向量長度，以及中間或最后的邏輯表達式，在訓(xùn)練過程中可能爆炸，因為簡單地增加向量長度就可以得到一個平凡的方程優(yōu)化解。通過限制矢量長度可以提供更穩(wěn)定的性能，因此在損失函數(shù)中加入了一個常用的L2長度正則化：

W表示所有輸入的變量向量、中間和最后的表達式向量

最后考慮對參數(shù)L2正則化，最后的損失函數(shù)如下：

4. 實現(xiàn)細節(jié)

原型任務(wù)定義如下:** 給定一定數(shù)量的訓(xùn)練邏輯表達式及其 T/F 值，訓(xùn)練一個 LINN，并測試該模型能否求解邏輯變量的 T/F 值，并在訓(xùn)練中預(yù)測由已有邏輯變量構(gòu)造的新表達式的值。**

相關(guān)邏輯操作的實現(xiàn)如下：其中AND與OR操作相似

原型實驗：求解邏輯等式 Solving logical equations

在將 LINN 應(yīng)用于實際任務(wù)之前，我們在一個基于模擬數(shù)據(jù)的理論任務(wù)上進行了實驗，以證明 LINN 框架具有進行邏輯推理的能力，這是傳統(tǒng)神經(jīng)網(wǎng)絡(luò)難以做到的。 給定一定數(shù)量的訓(xùn)練邏輯表達式及其 T/F 值，訓(xùn)練 LINN，檢驗該模型能否求出邏輯變量的 T/F 值，并預(yù)測由觀測邏輯變量構(gòu)造的新表達式的值。

隨機生成 n 個變量 v = { vi } ，每個變量隨機分配一個 t 或 f 的值。然后這些變量被用來隨機創(chuàng)建 m 個布爾表達式以析取范式形式存儲，構(gòu)成數(shù)據(jù)集。 每個表達式由1到5個分句組成，分句之間用析取∨分隔，每個分句由1到5個變量組成。產(chǎn)生的表達式如下所示：


我們基于一組已知的 DNFs 訓(xùn)練模型，并期望該模型能夠預(yù)測新的 DNFs 的 T/F 值，而不需要顯式地求解每個邏輯變量的 T/F 值。它保證有一個答案，因為訓(xùn)練方程是基于相同的參數(shù)集與已知的 T/F 值。對比結(jié)果如下所示：
可以看出在不同的邏輯長度和數(shù)據(jù)級上，LINN都取得了比通用神經(jīng)網(wǎng)絡(luò)顯著優(yōu)秀的效果。其中LINN-Rl表示去除邏輯正則化設(shè)置的模型效果。

此外，文中還可視化了訓(xùn)練過程中表達式中變量嵌入的變化過程：

可以看到兩類變量隨著迭代逐漸區(qū)分開來。

推薦系統(tǒng)實驗

通過模擬數(shù)據(jù)的實驗，驗證了 LINN 能夠求解邏輯變量和對邏輯方程進行推理。同時也揭示了 LINN 在其他實際任務(wù)中的應(yīng)用前景，只要這些任務(wù)可以表達為邏輯表達式。推薦既需要神經(jīng)網(wǎng)絡(luò)的泛化能力，又需要邏輯推理的推理能力。
為了將 LINN 應(yīng)用到推薦任務(wù)中，我們首先將其轉(zhuǎn)換為一個邏輯公式化的問題。推薦的關(guān)鍵問題是根據(jù)歷史交互理解用戶偏好。

邏輯表達式可以很容易地用于建模用戶歷史記錄中的物品關(guān)系。例如，如果一個用戶購買了 iPhone，他/她可能需要一個 iPhone 保護套而不是 Android 數(shù)據(jù)線，例如，iPhone ∧ iPhone 保護套 = T，而 iPhone ∧ Android 數(shù)據(jù)線 = F。

如果用戶 ui 喜歡/不喜歡 物品 vj，則讓 r_{i,j} = 1/0。然后，如果用戶 ui 喜歡物品 vj3，在一系列歷史交互之后，按照時間{ r_{i,j_1} = 1,r_{i,j_2} = 0}排序，邏輯表達式可以表示為:

這意味著用戶喜歡 j3是因為喜歡 j1，或者因為不喜歡 j2(一階關(guān)系)，或者因為喜歡 vj1，同時不喜歡 vj2(二階關(guān)系)。

這種表達式形式具有兩個顯著優(yōu)點：

  1. 模型可以從用戶歷史篩選掉無關(guān)交互。例如，如果 vj1、 vj2、 vj3分別是 iPhone、貓糧和 iPhone 外殼，只要 vj1∧ vj3接近正向量T，不管 vj2∧ vj3的向量是什么樣的。

  2. 訓(xùn)練后的模型，給定用戶歷史和目標物品，該模型不僅預(yù)測了用戶對物品的偏好程度，而且還通過對表達式中的每個關(guān)聯(lián)項進行評估，找出哪些物品是相關(guān)的。這樣可以為構(gòu)建可解釋性推薦提供基礎(chǔ)。

在構(gòu)建表達式時，如果用戶有更多的歷史交互，可能會有更高的階和更多的關(guān)系，上面的表達式中的析取項數(shù)量將呈指數(shù)增長。 一種解決方案是隨機抽樣或使用一些設(shè)計的抽樣策略。

在這項工作中，為了簡化模型，只考慮了一階關(guān)系，這足以超越許多最先進的方法。 此外，文中還提到模型的優(yōu)勢：

值得注意的是，上面的推薦模型是非個性化的，也就是說，沒有學(xué)習(xí)用戶嵌入來進行預(yù)測和推薦，而是僅僅依靠物品關(guān)系來進行推薦。
然而，正如我們將在下面的實驗中展示的那樣，這種簡單的非個性化模型優(yōu)于最先進的個性化神經(jīng)元序列推薦模型，這顯示了推理在推薦任務(wù)中的巨大潛力。

推薦實驗設(shè)置

模型訓(xùn)練按照如下loss：

按照BPR的方式進行設(shè)計，對于一個正樣本，隨機負采樣一個樣本，兩個樣本設(shè)計兩個邏輯表達式，兩個邏輯表達式為：
兩個表達式差異只是在于目標物品不同

具體用的數(shù)據(jù)是這個有評分數(shù)據(jù)的數(shù)據(jù)集(顯式數(shù)據(jù))

評分數(shù)據(jù)被轉(zhuǎn)化為0和1，以構(gòu)成邏輯表達式。等于或高于4的評分定義為1，這意味著積極的態(tài)度(like) ，其他的評分定義為0，表示不喜歡。

采用Leave-One-Out方式劃分數(shù)據(jù)集：訓(xùn)練-驗證-測試集。按照時間對每個用戶的交互進行排序，用戶的每個正向交互按照上述方式轉(zhuǎn)化為一個邏輯表達式。我們確保與用戶最早的5個正面交互相對應(yīng)的表達式都在訓(xùn)練集中。對于那些不超過5個正面交互的用戶，所有的表達式都在訓(xùn)練集中。對于剩余的數(shù)據(jù)，每個用戶的最后兩個正表達式分別分布到驗證集和測試集中(如果只有一個用戶正表達式，則首選測試集)。所有其他表達式都在訓(xùn)練集中。
沒有透露具體怎么測試的，即是從全集物品進行評估，還是采樣一部分進行推薦評估

推薦效果對比如下：使用了HR@1和NDCG@10進行評估

為了更好地理解 LINN 所學(xué)到的內(nèi)容，我們隨機選擇9部 ML-100k 的電影，并使用 LINN 來預(yù)測它們的共現(xiàn)(也就是說，被同一個用戶喜歡)。這些電影根據(jù)它們在訓(xùn)練集中的受歡迎程度(互動次數(shù))進行排名。 超過30個用戶與前3部電影互動，與后3部電影互動的用戶不到5個。

使用 LINN 來計算每個條目對的 Sim (vi ∧ vj，t) ，即用戶喜歡 vi 時喜歡 vj 的概率。結(jié)果如圖所示:

雖然我們沒有為 AND 或 OR 設(shè)計一個對稱的網(wǎng)絡(luò)，但 LINN 成功地發(fā)現(xiàn) vi ∧ vj 接近 vj ∧ vi。熱圖矩陣中的對稱位置具有相似的值，這表明了這一點。

LINN 可以學(xué)習(xí)到受歡迎的物品組合被同一個用戶消費的概率更高。
? LINN 可以發(fā)現(xiàn)物品之間的潛在關(guān)系。例如，第602項是一個流行的歌舞音樂電影，第1144項是一個不受歡迎的戲劇電影，但他們屬于類似類型的電影。我們看到 LINN 能夠了解到他們被同一個用戶喜歡的概率很高(共現(xiàn)概率高)。

總結(jié)

簡單來說，這篇工作提出了一個新的框架，將神經(jīng)網(wǎng)絡(luò)和基本的一階邏輯推理進行融合，能夠進行有效的邏輯推理。將這樣的結(jié)構(gòu)與推薦任務(wù)相結(jié)合，將推薦序列變成一個邏輯表達式，是非常新穎的做法，在實驗上也證明了該設(shè)計的有效性。當(dāng)然還存在一些小問題，主要是在模型實驗上(如：測試規(guī)模/模型對比實驗為何都是考慮序列推薦，相關(guān)工作也是特別新的工作；而且需要有評分信息這類顯式反饋，比較有局限性；對隱式反饋怎么做？)
總體來講，這篇工作還是比較有創(chuàng)新性和啟迪價值，可以為我們做推薦開拓新的思路和方向，考慮將邏輯推理與ML/DL結(jié)合。

湊巧最近聽了周志華教授的反繹學(xué)習(xí)，將機器學(xué)習(xí)與知識結(jié)合起來，提出了一種新的框架，對于未來這應(yīng)該是一個重要的研究趨勢。

END

如果覺得有用，歡迎點贊關(guān)注贊賞，若對推薦感興趣歡迎評論區(qū)/私信交流~~~

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容