从Bengio演讲发散开来：探讨逻辑推理与机器学习

机器之心分析师 络

近年来，深度神经 络的应用获得了巨大的成功，也推动了人工智能的飞速发展。然而，深度神经 络仍存在一些局限性。一般来说，深度神经 络如何进行学习、使用何种算法实现的智能、基于哪些理论分析得出的相关结论并不会在 络架构中有任何的显式或符 表示。也就是说，深度神经 络学习的算法隐式地存储在成千上万甚至是数百万的权重中，这些通常是人类智能体无法破译或验证的。

Bengio 在 AAAI 2020 的演讲 告中提出，人的认知系统包含两个子系统：System1（直觉系统），实现的是快速、无意识、非语言的认知，这也是现有的深度神经 络所实现的。他认为，未来的深度神经 络应当能够实现 System2（逻辑分析系统），实现的是有意识的、有逻辑的、有规划的、可推理以及可以语言表达的系统。我们这篇文章中所讨论的 Logical Reasoning（逻辑推理）拟实现的就是 System2 中重点关注的有逻辑的（Logical）和可推理的（Reasoning）特点。

本图选自 Bengio 在 AAAI 2020 的演讲 告

逻辑推理是一个非常宽泛的概念。实际上，我们所熟悉的字符识别、语音识别、图像识别也可以看做是一种逻辑推理，这不过，这些逻辑推理是低层次的，已经能够使用传统的深度神经 络所解决。我们在这篇文章中所讨论的逻辑推理是更高层次的推理过程，即，即使是人来完成这个逻辑推理任务也是要进行一下思考的。

1. 什么是逻辑？

1.1 逻辑的概念

首先，我们来回顾一下什么是逻辑以及什么是 AI/ML 中的逻辑。所谓逻辑，指的是符 化的、基于知识的、推理和其他类似的人工智能方法。基于逻辑的 AI 系统可以被认为是高级编程系统，可以很容易地以紧凑（compact）和可用的（usable）方式编码人类知识。

最简单的逻辑系统是命题逻辑（有时称为零阶逻辑）。在命题逻辑中，使用一些被称为句子或公式的对象来编码信息。这些对象代表着对世界的一些陈述。通常，可以使用一些基本语句作为这样的对象。例如，使用「P，Q，R，S…」来表示基本语句，P 可能代表「正在下雨」，是一个原子（Atom）。

可以继续将原子与逻辑连接词如「and，or，if then」等组合形成更多的句子，称为复合公式（Compound Formula）。

复合公式提供了一种有效的信息表示方法。那么，我们如何利用这些复合公式从已有的信息推断得到新的信息呢？一般可以通过推理（Reasoning）或推论（Inference）来做到这一点。命题逻辑配有一套称为推理方法的方案。推理方法可以被认为是一个小程序，它以一组句子作为输入，并输出一个或多个句子。推论方法也可以被认为是一个小程序，它也以一组句子作为输入，并输出一个或多个句子。下图展示了一种非常直接的推论方法，它接受表示「Q 和 R」的公式，并将公式 R 作为输出。例如，如果输入为「It is sunny, and It is warm」，则输出将为「It is sunny」。

所有的逻辑都配备了一套与上述过程类似的推论方法。逻辑的这些原始内置方法的作用类似于编程语言中的标准库。有了这些方法，就可以将它们组合起来以得到更复杂的方法。

从教学的角度来看，从命题逻辑出发进行介绍是一个很好的起点。但是，对于实际中具有大量对象的领域建模来说，使用命题逻辑是很难处理的。例如，假设我们要写下数独游戏应该满足的约束条件。对于每个数 k，每行 i 和列 j 都对应一个原子 A_ijk，它代表「行 i 和列 k 包含数字 k」。这样，我们就可以在命题逻辑中快速写出数独的约束条件。例如，下图中的句子说明数字 5 应该出现在第一行中。

同样，我们也可以写下其他数字的其他约束条件。在我们的约束条件下，总共有 9^3=729 个原子。每一个原子可以是真或假，即表征总共 2 种可能的状态（远大于宇宙中物理原子的数量）。

一阶逻辑通过引入原子来改进命题逻辑，这些原子可以接受域中对象的参数。在一阶逻辑中将有一个原子来接受这些变量作为参数，而不是用一个原子 A_ijk 来表示 i、j 和 k 的每个组合。例如，A(1,3,5)表示第 1 行和第 3 列中有一个 5。下图表示第 1 行中有一列的数字是 5。

一阶逻辑是许多现代逻辑系统在研究和工业中应用的基础。许多其他逻辑系统建立并扩展了一阶逻辑（例如，二阶逻辑、三阶逻辑、高阶逻辑和模态逻辑）。每一种逻辑都增加了一个新的维度或特性，以便更容易对世界的某些方面进行建模。例如，被称为时态逻辑的逻辑被用来对时间和变化进行建模。

1.2 AI/ML 中的逻辑

1.2.1 科学中的自动发现

逻辑学最成功的应用之一是在科学领域中表示结构化的科学知识。2007 年，威尔士和英格兰的一个小组创建了一个名为 Adam（自动发现和分析机器）的系统 [1]。Adam 可以自动形成科学假设，进行实验来检验假设并记录实验结果。这是第一个自动系统，用来发现各类的科学信息。Adam 成功地应用于确定酵母中的一些基因。在这个系统中，假设、实验结果和结论都以逻辑的形式表达出来。

1.2.2 归纳程序设计

归纳程序设计的目标是学习给定一组输入和输出示例的计算机程序。归纳程序设计处理的是可以从这些例子中学习的生成系统。这种系统通常是用逻辑来表述的。最先进的归纳程序设计系统可以从几个例子中学习复杂的递归程序。目前，归纳程序设计方法已经被用来学习数据清理和转换程序任务[2]。

1.2.3 数学推理自动化

上面的数独例子说明了一阶逻辑比命题逻辑更具表现力。不过，我们能用它来模拟的东西有限制吗？实际上，单是一阶逻辑就相当强大，它强大到可以模拟几乎所有的古典数学。在标准数学的概念下工作，使用一阶逻辑可以陈述你想要证明的任何目标（一个猜想），并能让机器自动检查你的工作（数学证明）。这种方法就是直接使用数学的推理自动化。

1.2.4 计算机系统（包括机器学习系统）的验证

在数学之外，以一阶逻辑和类似系统为基础的逻辑被用于验证计算机系统。这种选择被称为正式验证（Formal Verification）。在正式的验证中，有一个计算机系统 S 和一个属性 P，用户必须用一种相对严格的方式来验证这个属性是有效的。例如，用于验证硬件和软件系统的工业强度系统 ACL2 (http://www.cs.utexas.edu/users/moore/acl2/)。

1.2.5 类似逻辑系统与机器学习模型

随着越来越多的应用程序和领域使用机器学习模型，仍有一些场景需要使用类似逻辑系统和机器学习模型。例如，许多欺诈检测系统使用一个或多个机器学习模型以及大量手工编制的规则，而这些规则是非常必要的。在欺诈检测领域，这些规则可能会捕获新的和不断发展的欺诈模式，而针对这些模式可能并没有足够的数据来训练得到新的模型[3]。

最近的一些研究着眼于将逻辑与深度学习系统进行结合，这也正是我们这篇文章所考虑的问题。我们将在下面的内容中选择三篇关注于逻辑推理与深度神经 络相结合的文章进行深入分析[5][6][7]。

2. 逻辑推理与深度学习（Logic Reasoning & DL）

2.1 Bridging Machine Learning and Logical Reasoning by Abductive Learning [5]

2.1.1 诱因性学习

人类使用诱因问题解决方法来解决问题的一个直观例子是玛雅象形文字的破译，它反映了人类两个显著的智能能力：1）从象形文字中直观地感知单个数字；2）基于数学和日历的背景知识，象征性地进行推理。图 1 显示了从帕伦克十字庙发现的玛雅历法，它从神话中的创世日期开始，接着是以长计数书写的时间段，最后是由 Tzolk’in 和 Haab’日历编码的特定日期。

图 1. 玛雅历法，其中彩色盒子和「？」对应于未知数字

图 2 描绘了查尔斯 P. 鲍迪奇（Charles P. Bowditch）破解图 1 的记录。他首先确认了一些已知的数字，并确认第一和第六个象形文字是相同的。然后，Bowditch 尝试用视觉上相似的数字代替那些未知的象形文字，如图 2 中的「第 1 列」所示。同时，他根据自己的推测和玛雅历法中的背景知识计算出 Tzolk’in 和 Haab’的值，如图 2 的「第 2 列」所示。最后，通过观察其猜想与计算的一致性，得到了正确答案「1.18.5.4.0，1 Ahau 13 Mak」。这整个过程应用的就是诱因问题解决方法。

图 2. 鲍迪奇对图 1 的解读（他把「Mak」写为「Mac」）。垂直框中的数字是他对图 1 中未知象形文字的猜测（第 1 列）。虚线黄色框根据其计算结果（第 2 栏）标记一致结果。

2.1.2 方法简介

诱因性学习的任务可以形式化的表示如下。诱因性学习的输入由一组标记的关于目标概念 C 和领域知识库 B 的训练数据组成 D = {, . . . ,} 。目标概念 C 是在一组原始概念符 P=之间的未知关系下定义的。其中每个 pk 都是 B 中定义的符 。ABL 的目标是输出一个假设模型 H=p∪?C：

p 是从特征空间到原始符 的映射，即它是一个传统机器学习的感知模型；

?C 是一组用 B 定义目标概念 C 的一阶逻辑子句，称为知识模型。

假设模型应满足：

(1)

ABL 试图通过将机器学习与诱因性逻辑推理模块相连接，并通过一致性优化将它们的内部机制融合起来，从而解决这些挑战。ABL 的完整框架见图 3。其中， 机器学习（Machine Learning）用于学习感知模型 p：给定一个输入实例 x，p 可以预测伪标签 p(x)作为 x 中可能的原始概念的真值。当伪标签包含错误时，需要重新训练感知模型，此时，所使用的标签是逻辑诱因返回的修正后的伪标签 r(x)。逻辑诱因（Logical abduction）是诱因推理的逻辑形式化表示。给定以一阶逻辑子句形式表述的观测事实和背景知识，逻辑推理将对观测事实的可能性解释扩展为基本假设。

图 3. ABL 完整框架

逻辑程序（Logic Programming）中的一个声明性框架将上述的过程形式化，称为诱因性逻辑程序（Abductive Logic Programming，ALP）[8]。形式上，诱因性逻辑程序（abductive logic program）可以定义如下：

定义 1：诱因性逻辑程序是一个三元组 (B,A,IC)，其中 B 是背景知识，A 是一组可扩展谓词，IC 是完整性约束。给定一些观测事实 O，程序输出为一组 A 的真值推理结果?，如：

即，诱因性解释 ? 是一种假设：根据背景知识 B 和约束 IC 来解释观察 O 是如何成立的。考虑到公式（1），ABL 将关于最终概念的实例标签作为观测事实，并将假设模型 H=p∪?C 作为推导内容。给定一个固定的?C，ABL 可以根据 B 和 Y 推导出 p(x)；当感知模型 p 确定后，ALP 能够根据 B∪p(x)∪Y 推导出知识模型?C。

ABL 的目标是学习与背景知识和训练实例相一致的假设。更具体地说，ABL 试图在给定背景知识 B 的情况下，最大化外推假设 H 与训练数据 D 之间的一致性：

2.1.3 手写方程解译任务

图 4. 手写方程解译难题：机器应同时学习识别符 并找出未知运算规则（本例中为「xnor」）

图 5. ABL 结构

注：请注意，计算运算的具体规则在 B 中没有定义，即「0+0」、「0+1」和「1+1」的结果可以是「0」、「1」、「00」、「01」甚至「10」。缺失的计算规则形成知识模型 ?C，这一部分是需要从数据中学习得到的。

训练开始后，CNN 将图像解释为伪标签「0」、「1」、「+」和「=」构造的符 方程。因为 CNN 没有经过训练，所以感知到的符 通常是错误的。在这种情况下，ALP 不能根据领域知识导出任何与训练数据一致的 ?C。为了导出一致性的 ?C，ABL 学习了启发式函数δ来标记可能不正确的伪标签。

当 CNN 收敛或算法满足迭代极限后，所有 < x_i , y_i > 被关系特征确定为二元特征向量。对于每个输入方程 x_i，其伪标签将由所有的关系特征来评估以产生二进制向量 u_i= [u_i1,…,u_iT]：

原始数据集 D={}可以转换为新的数据集 D’={}，从中可以学习一个决策模型来处理子抽样带来的噪声问题。

2.1.4 实验分析

图 6. 手写方程解译任务的数据实例

1）ABL，机器学习模型由两层 CNN、一个两层多层感知器（MLP）和一个 softmax 层组成，逻辑诱因将 50 个位操作的计算规则集作为关系特征，决策模型为两层 MLP。实验中尝试了两种不同的设置：使用所有训练数据的 ABL-all 和仅使用长度为 5-8 的训练方程的 ABL-short。

2）可微神经计算机（Differentiable Neural Computer，DNC），这是一个与记忆有关的深层神经 络。

3）Transformer 络，这是一个经过关注增强的深层神经 络，已经被证实在许多自然语言处理任务中是有效的。

4）双向长短期记忆 络（Bidirectional Long Short-Term Memory Network，BiLSTM），这是目前应用最广泛的序列数据学习的神经 络。为了处理图像输入，BiLSTM、DNC 和 Transformer 络也使用与 ABLs 相同结构的 CNN 作为它们的输入层。所有的神经 络都是用一个从训练数据中随机抽取的验证集来调整的。

图 7. DBA（左）和 RBA（右）任务的实验结果

图 7 中的实验结果表明，在这两个任务中，基于 ABL 的方法明显优于其它进行比较的方法，并且 ABL 正确地学习了定义未知操作的符 规则。所有这些方法在 DBA 任务上的性能都比 RBA 好，这是因为 DBA 任务中的符 图像更容易区分。ABL-all 和 ABL-short 的性能没有显著差异。随着测试方程长度的增加，实验中用于比较的其它方法的性能迅速退化到随机猜测的准确度水平，而基于 ABL 的方法对未知数据的推导预测效果更好。一个有趣的结果是，人在这两个任务上的表现非常接近而且都比 ABL 差。根据志愿者的说法，他们并不需要区分不同的符 ，在这种任务中人们非常容易出错，而机器在检查逻辑理论一致性方面是很擅长的。因此，应该更好的利用机器学习系统在逻辑推理方面的优势。

2.1.5 文章小结

作为心理学中一种重要的认知模型，诱因已经引起人工智能领域的关注。现有的工作大多数是在符 域中将诱因性（Abduction）与归纳（Induction）结合起来。也有一些工作使用诱因性学习改进机器学习的效果，这些方法一般需要将逻辑背景知识调整为函数约束，或者在学习和推理过程中使用特别设计的算子来支持梯度下降，从而将逻辑推理简化为不同的连续优化问题。

2.2 SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver [6]

2.2.1 方法介绍

（1）

（2）

这个问题是 MIN-UNSAT 的一个低秩（但非凸）公式，它等价于 MAXSAT。可以将这个公式重写为一个 SDP，并且已经由研究人员证明给定 k>sqrt(2n)的情况下，该式可以恢复最优 SDP 解。尽管它是非凸的，可以通过坐标下降来优化地解决公式（2）。特别是，依赖于 v_i 的客观条件表示为：

其中 s_i 是 S 的第 i 列向量。根据 ||v_i||=1 的约束条件，最小化 v_i 的值以得到坐标下降更新：

这些更新可证明能够收敛到 SDP(2)（即公式（2）对应的 SDP）的全局最优不动点。

通过 SDP(2)从输入 Z_I 生成输出 Z_O，SATNet Layer 的权重对应于 SDP 的低秩系数矩阵 S。完整的前向传递过程如图 1 所示，具体的层初始化和前向传递的步骤描述见算法 1。

图 1. MAXSAT 层的前向传递。该层将已知 MAXSAT 变量的离散或概率赋值作为输入，通过权重 S 的 MAXSAT SDP 松弛输出对未知变量赋值的猜测。

【层初始化】

初始化 SATNet 时，用户必须指定该层可以表示的最大子句数 m。通常希望将 m 的值设置的较低，因为低秩结构可以防止出现过拟合的问题，从而提高泛化能力。考虑到这种低秩结构，用户希望通过辅助变量在一定程度上提高层的表示能力。这里的高级直觉来自于布尔满足问题的合取范式（Conjunctive Normal Form，CNF）表示。向问题中添加额外的变量可以显著减少描述该问题所需的 CNF 子句的数量。

【放松层输入】

首先将其输入 Z_I 松弛成连续向量用于 SDP 公式（2）。也就是说，将每一层输入 z_l，l∈I 松弛到一个相关的随机单位向量 z_l，v_l∈R^k：

（4）

公式（4）满足：

（5）

其中，(v_l)^rand 为随机单位向量。

【通过 SDP 产生连续的输出松弛】

给定连续输入松弛 V_I，使用坐标下降更新公式（3）来计算连续输出松弛 v_o。值得注意的是，坐标下降更新只计算输出变量，也就是说，不计算其赋值作为层输入的变量。

前向传递的坐标下降算法详细说明在算法 2 中。该算法保留了计算 g_o 所需的Ω=VS^T 项，然后在每次内部迭代中通过秩 1 更新对其进行修改。因此，每次迭代的运行时间是 O(nmk)。

【生成离散或概率输出】

给定坐标下降的松弛输出 V_O，层通过阈值或随机取整将这些输出转换为离散或概率变量赋值 Z_O。随机化舍入的主要思想是，对于每一个 v_o，o∈O，可以从单位球面上取一个随机超平面 r 并赋值。

（6）

给定正确的权值，这种随机取整过程保证了某些 NP-hard 问题的最佳期望逼近比。在训练期间，没有明确地执行随机取整。相反，v_o 和 v_T 在给定 r 的同一侧的概率是：

（7）

在测试过程中，既可以以相同的方式输出概率输出，也可以通过阈值分割或随机舍入输出离散赋值。如果使用随机化舍入，则执行多次舍入后将 z_o 设为使公式（1）中 MAXSAT 目标最大化的布尔解。

【从概率输出到连续松弛】

给定 δl/δZ_O，可以通过概率分配机制推导出 δl/δV_O：

（8）

【通过 SDP 的反向传播】

得到 δl/δV_O 后，通过 SDP 推导出解 δl/δS：

（9）

【从松弛结果到原始输入】

最后，使用梯度 δl/δV_I 通过输入松弛过程推导梯度 δl/δZ_x：

（12）

（13）

2.2.2 实验分析

表 1. 9x 9 个数独实验的结果，将 SATNet 模型与一个普通的卷积神经 络（ConvNet）以及一个接收二进制掩码指示需要学习哪些位的 络（ConvNetMask）进行比较。

2.2.3 文章小结

3. 应用数据库介绍

3.1 LogiQA: A Challenge Dataset for Machine Reading Comprehension with Logical Reasoning [7]

机器阅读是测试自然语言理解能力的一项基本任务，它与人类认知有着密切的关系。机器阅读可以广泛应用于开放领域问答与信息检索等后续任务中。随着 NLP 深度学习的最新进展，阅读理解研究也有了长足的发展，从能够用简单事实来回答的问题发展到需