协同过滤(3): Neural Logic Reasoning

前言

• 发表在CIKM2020上的一篇关于通用CF推荐的论文，引入了逻辑推理的思想!

• 源码链接：https://github.com/evison/NLR/

• 码字不易，好心人随手点个赞

• 本文为自己的论文阅读笔记，并非完整的论文翻译，如有错误/问题欢迎评论区指正，仅为参考，建议首先阅读原文

• 如需转载引用，请务必提前联系本人并在文中附上原链接及相应说明，包括作者信息（阿瑟）

• 关于该论文，涉及符号系统等一些概念和思想，可以参考https://blog.csdn.net/weixin_43868020/article/details/107191994

摘要

近年来，深层神经网络在许多领域取得了成功。大多数神经网络设计背后的基本思想是从数据中学习相似模式进行预测和推理，这缺乏认知推理能力。然而，具体的推理能力是许多理论和实践问题的关键。

另一方面，传统的符号推理方法在进行逻辑推理方面有很好的效果，但它们大多是直接的基于规则的推理(Hard rule-based reasoning)，这限制了它们对不同任务的泛化能力，因为不同的任务需要不同的规则。

推理和泛化能力对于推荐系统这样的预测任务都很重要，推理提供了用户历史和目标物品之间强有力的关联以便精确预测，泛化能够帮助模型在噪声输入下构造健壮的用户画像(robust user portrait)。

本文中提出了逻辑集成神经网络(LINN)来集成深度学习和逻辑推理的能力。LINN 是一种动态神经网络结构，根据输入的逻辑表达式构建计算图。它学习基本的逻辑运算，例如OR\AND\NOT作为神经模块，并通过网络进行命题逻辑推理。

理论任务实验表明，LINN 在求解逻辑方程和变量方面有显著的性能。此外，我们通过将推荐任务描述为一个逻辑推理问题，在推荐的实际任务上对我们的方法进行了验证。

引言

虽然神经网络通常对具有相似分布的数据具有良好的泛化能力，但这些方法的设计思想使得神经网络在许多理论和实际问题上很难进行逻辑推理分析。然而，逻辑推理是一种重要的智能能力，它对许多理论任务，如解决逻辑方程，以及实际任务，如医疗决策支持系统，法律助理，和个性化推荐系统至关重要。

例如，在推荐任务中，推理可以帮助建立用户和项目之间的复杂关系模型(例如，用户喜欢项目 a，但不喜欢项目 b →用户喜欢项目 c) ，特别是对于那些罕见的模式，这通常是神经网络难以捕捉的。

进行推理的一种典型方法是通过逻辑推理(logical inference)。事实上，在机器学习方法出现之前，基于符号推理(symbolic reasoning)的逻辑推理一直是人工智能的主流方法，它也是传统人工智能(GOFAI)中许多专家系统的基础。然而，传统的逻辑推理的符号推理方法大多是基于规则的硬推理，由于规则难以定义，不易适用于现实世界中的许多任务。

例如，在推荐系统中，如果我们把每个物品都看作一个符号，我们就很难根据手工设计的规则来捕捉物品之间的所有关系。此外，个性化用户偏好带来了各种交互序列，这可能带来冲突推理规则，例如，一个用户可能同时喜欢 a 和 b，而另一个喜欢 a 的用户可能不喜欢 b。 数据中的这种噪声使得设计适合于新数据的推荐规则变得非常具有挑战性。

为了统一利用深度神经网络的泛化能力和逻辑推理，提出了逻辑集成神经网络(LINN) ，基于神经网络进行逻辑推理的神经结构。LINN 用向量表示逻辑变量，每个基本逻辑运算(AND/OR/NOT)作为一个基于逻辑正则化的神经模块来学习。

由于由同一组变量组成的逻辑表达式可能具有完全不同的逻辑结构，因此捕获逻辑的结构信息对逻辑推理至关重要。为了解决这个问题，LINN 根据输入的逻辑表达式动态构造其神经网络结构，这不同于许多固定计算图形的神经网络。通过在神经网络结构中编码逻辑结构信息，LINN 可以灵活处理指数级的逻辑表达式。

LINN模型

在 LINN，逻辑表达式中的每个逻辑变量都表示为一个向量嵌入，每个基本逻辑运算(例如，AND/OR/NOT)都学习为一个神经模块。大多数神经网络都是基于独立于输入的固定神经结构而开发的，无论是手动设计的还是通过神经结构搜索学习的。 不同的是，我们的 LINN 体系结构的计算图是依赖于输入的，并根据输入逻辑表达式动态地构建。 我们进一步利用逻辑正则化(Logic Regulaizers)对神经模块，以保证每个模块进行预期的逻辑操作。

1. 神经模块的逻辑操作

命题逻辑的表达式由逻辑常量(True 或 False，标记为 T/F)、逻辑变量(v)和基本逻辑运算(否定、合取∧和析取∨)组成。在 LINN 中，逻辑运算被学习为三个神经模块。Leshno 等证明了具有非多项式激活函数的多层前馈网络可以逼近任何函数。这为我们利用神经模块学习逻辑操作提供了理论支持。与大多数将输入变量作为向量表示学习的神经模型类似，T、F 和所有逻辑变量都被表示为具有相同维数的向量。给定逻辑表达式及其对应的值，一个表达式示例如下：

相关符号表示可以定义为：下图展示了LINN的结构示例

图中下的框显示了LINN如何构造一个逻辑表达式。每个中间向量表示逻辑表达式的一部分，最后得到整个逻辑表达式 e的向量表示。
这样，虽然嵌入矩阵的大小随着逻辑变量总数的线性增长，但算子网络中的参数总数保持不变。
此外，由于表达式是按树结构组织的，因此可以从叶子到根递归地计算它。
为了计算表达式的 T/F 值，我们计算了表达式向量和 T/F向量之间的相似度，如上面的框所示。这里 Sim (,)也是一个神经模块，用来计算两个向量之间的相似度，并输出0到1之间的相似度值。
输出 对于Top-n推荐，可以使用BPRLoss

2. 神经模块上的逻辑约束 Logical Regularization

到目前为止只学习了逻辑运算作为神经模块，但没有明确保证这些模块实现预期的逻辑运算。例如，任何与 False 连接的变量或表达式都应得到F，即 w ∧ F= F，双重否定应该等于本身。
我们使用 w 代替 v，因为 w 既可以是单个变量(例如，vi) ，也可以是计算流程中间的表达式。LINN 应该满足基本的逻辑规则，尽管神经结构可能隐式地从数据中学习逻辑操作，但是如果我们对其加上具体的逻辑约束会更好指导学习逻辑。为了实现这一目标，文中定义了逻辑正则化(Logical Regularization)来规范模块的行为，使它们能够执行一定的逻辑操作。完整的定义如下表所示：

这些规则完备地设定了三种基本逻辑运算的各种运算性质。相应的约束也是建立在LINN定义的特征空间中，而非完整的向量空间中。逻辑正则鼓励LINN 学习神经模块参数，以满足模型中涉及的变量/表达式的推理性质，这比整个向量空间小得多。

在 LINN 中，常量True的向量T在训练和测试过程中是随机初始化并且固定的，作为定义T向量的逻辑空间中的标准向量(Anchor vector)。因此可以用 NOT (t)来计算False向量 F。
最后的损失函数可以定义为：

值得注意的是，除了上面列出的逻辑正则化之外，命题逻辑系统还应该满足其他逻辑规则，如结合律、交换律和分配律。 为了考虑交换律，在计算正则化时，可以将由合取或析取的顺序随机化。例如，w ∧ t 的网络结构可以是 AND (w，t)或 AND (t，w) ，w ∨ w 的网络结构可以是 OR (w，NOT (w))或 OR (NOT (w) ，w)。这样，当输入是同一表达式在交换性方面的不同形式时，可以训练模型构建相同的向量表示。

没有明确的方法约束其他逻辑规则的模块，这些规则对应于更复杂的表达式变量，如分配律和摩根定律（非(P 且 Q) = (非 P) 或 (非 Q)
非(P 或 Q) = (非 P) 且 (非 Q)）。

为了解决这个问题，我们确保输入表达式具有相同的规范形式-- 例如，析取范式-- 因为任何命题逻辑表达式都可以转换为析取范式(DNF)或合取范式(CNF) ，而且每个表达式都对应于一个计算图。这样就避免了对分配律和摩根定律的神经模块进行规范化的必要性。

3. 长度正则化 Length Regularization over Logic Variables

逻辑变量的向量长度，以及中间或最后的逻辑表达式，在训练过程中可能爆炸，因为简单地增加向量长度就可以得到一个平凡的方程优化解。通过限制矢量长度可以提供更稳定的性能，因此在损失函数中加入了一个常用的L2长度正则化：

W表示所有输入的变量向量、中间和最后的表达式向量

最后考虑对参数L2正则化，最后的损失函数如下：

4. 实现细节

原型任务定义如下:** 给定一定数量的训练逻辑表达式及其 T/F 值，训练一个 LINN，并测试该模型能否求解逻辑变量的 T/F 值，并在训练中预测由已有逻辑变量构造的新表达式的值。**

相关逻辑操作的实现如下：其中AND与OR操作相似

原型实验：求解逻辑等式 Solving logical equations

在将 LINN 应用于实际任务之前，我们在一个基于模拟数据的理论任务上进行了实验，以证明 LINN 框架具有进行逻辑推理的能力，这是传统神经网络难以做到的。 给定一定数量的训练逻辑表达式及其 T/F 值，训练 LINN，检验该模型能否求出逻辑变量的 T/F 值，并预测由观测逻辑变量构造的新表达式的值。

随机生成 n 个变量 v = { vi } ，每个变量随机分配一个 t 或 f 的值。然后这些变量被用来随机创建 m 个布尔表达式以析取范式形式存储，构成数据集。 每个表达式由1到5个分句组成，分句之间用析取∨分隔，每个分句由1到5个变量组成。产生的表达式如下所示：

我们基于一组已知的 DNFs 训练模型，并期望该模型能够预测新的 DNFs 的 T/F 值，而不需要显式地求解每个逻辑变量的 T/F 值。它保证有一个答案，因为训练方程是基于相同的参数集与已知的 T/F 值。对比结果如下所示： 可以看出在不同的逻辑长度和数据级上，LINN都取得了比通用神经网络显著优秀的效果。其中LINN-Rl表示去除逻辑正则化设置的模型效果。 此外，文中还可视化了训练过程中表达式中变量嵌入的变化过程：

可以看到两类变量随着迭代逐渐区分开来。

推荐系统实验

通过模拟数据的实验，验证了 LINN 能够求解逻辑变量和对逻辑方程进行推理。同时也揭示了 LINN 在其他实际任务中的应用前景，只要这些任务可以表达为逻辑表达式。推荐既需要神经网络的泛化能力，又需要逻辑推理的推理能力。
为了将 LINN 应用到推荐任务中，我们首先将其转换为一个逻辑公式化的问题。推荐的关键问题是根据历史交互理解用户偏好。

逻辑表达式可以很容易地用于建模用户历史记录中的物品关系。例如，如果一个用户购买了 iPhone，他/她可能需要一个 iPhone 保护套而不是 Android 数据线，例如，iPhone ∧ iPhone 保护套 = T，而 iPhone ∧ Android 数据线 = F。

如果用户 ui 喜欢/不喜欢 物品 vj，则让 。然后，如果用户 ui 喜欢物品 vj3，在一系列历史交互之后，按照时间排序，逻辑表达式可以表示为:

这意味着用户喜欢 j3是因为喜欢 j1，或者因为不喜欢 j2(一阶关系)，或者因为喜欢 vj1，同时不喜欢 vj2(二阶关系)。

这种表达式形式具有两个显著优点：

1. 模型可以从用户历史筛选掉无关交互。例如，如果 vj1、 vj2、 vj3分别是 iPhone、猫粮和 iPhone 外壳，只要 vj1∧ vj3接近正向量T，不管 vj2∧ vj3的向量是什么样的。

2. 训练后的模型，给定用户历史和目标物品，该模型不仅预测了用户对物品的偏好程度，而且还通过对表达式中的每个关联项进行评估，找出哪些物品是相关的。这样可以为构建可解释性推荐提供基础。

在构建表达式时，如果用户有更多的历史交互，可能会有更高的阶和更多的关系，上面的表达式中的析取项数量将呈指数增长。 一种解决方案是随机抽样或使用一些设计的抽样策略。

在这项工作中，为了简化模型，只考虑了一阶关系，这足以超越许多最先进的方法。 此外，文中还提到模型的优势：

值得注意的是，上面的推荐模型是非个性化的，也就是说，没有学习用户嵌入来进行预测和推荐，而是仅仅依靠物品关系来进行推荐。
然而，正如我们将在下面的实验中展示的那样，这种简单的非个性化模型优于最先进的个性化神经元序列推荐模型，这显示了推理在推荐任务中的巨大潜力。

推荐实验设置

模型训练按照如下loss：

按照BPR的方式进行设计，对于一个正样本，随机负采样一个样本，两个样本设计两个逻辑表达式，两个逻辑表达式为： 两个表达式差异只是在于目标物品不同

具体用的数据是这个有评分数据的数据集(显式数据)

评分数据被转化为0和1，以构成逻辑表达式。等于或高于4的评分定义为1，这意味着积极的态度(like) ，其他的评分定义为0，表示不喜欢。

采用Leave-One-Out方式划分数据集：训练-验证-测试集。按照时间对每个用户的交互进行排序，用户的每个正向交互按照上述方式转化为一个逻辑表达式。我们确保与用户最早的5个正面交互相对应的表达式都在训练集中。对于那些不超过5个正面交互的用户，所有的表达式都在训练集中。对于剩余的数据，每个用户的最后两个正表达式分别分布到验证集和测试集中(如果只有一个用户正表达式，则首选测试集)。所有其他表达式都在训练集中。
没有透露具体怎么测试的，即是从全集物品进行评估，还是采样一部分进行推荐评估

推荐效果对比如下：使用了HR@1和NDCG@10进行评估

为了更好地理解 LINN 所学到的内容，我们随机选择9部 ML-100k 的电影，并使用 LINN 来预测它们的共现(也就是说，被同一个用户喜欢)。这些电影根据它们在训练集中的受欢迎程度(互动次数)进行排名。 超过30个用户与前3部电影互动，与后3部电影互动的用户不到5个。

使用 LINN 来计算每个条目对的 Sim (vi ∧ vj，t) ，即用户喜欢 vi 时喜欢 vj 的概率。结果如图所示:
虽然我们没有为 AND 或 OR 设计一个对称的网络，但 LINN 成功地发现 vi ∧ vj 接近 vj ∧ vi。热图矩阵中的对称位置具有相似的值，这表明了这一点。

LINN 可以学习到受欢迎的物品组合被同一个用户消费的概率更高。
• LINN 可以发现物品之间的潜在关系。例如，第602项是一个流行的歌舞音乐电影，第1144项是一个不受欢迎的戏剧电影，但他们属于类似类型的电影。我们看到 LINN 能够了解到他们被同一个用户喜欢的概率很高(共现概率高)。

总结

简单来说，这篇工作提出了一个新的框架，将神经网络和基本的一阶逻辑推理进行融合，能够进行有效的逻辑推理。将这样的结构与推荐任务相结合，将推荐序列变成一个逻辑表达式，是非常新颖的做法，在实验上也证明了该设计的有效性。当然还存在一些小问题，主要是在模型实验上(如：测试规模/模型对比实验为何都是考虑序列推荐，相关工作也是特别新的工作；而且需要有评分信息这类显式反馈，比较有局限性；对隐式反馈怎么做？)
总体来讲，这篇工作还是比较有创新性和启迪价值，可以为我们做推荐开拓新的思路和方向，考虑将逻辑推理与ML/DL结合。

凑巧最近听了周志华教授的反绎学习，将机器学习与知识结合起来，提出了一种新的框架，对于未来这应该是一个重要的研究趋势。

END

如果觉得有用，欢迎点赞关注赞赏，若对推荐感兴趣欢迎评论区/私信交流~~~