概率神经符号推理的可扩展方法

A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference

A-NESI：一种用于概率神经符号推理的可扩展近似方法

https://arxiv.org/pdf/2212.12393

摘要

我们研究了如何将神经网络与符号推理相结合的问题。最近提出的概率神经符号学习（PNL）框架，例如DeepProbLog，执行指数时间复杂度的精确推理，限制了PNL解决方案的可扩展性。我们引入了近似神经符号推理（A-NESI）：一种用于PNL的新框架，它利用神经网络进行可扩展的近似推理。A-NESI 1）在多项式时间内进行近似推理，而不改变概率逻辑的语义；2）使用背景知识生成的数据进行训练；3）能够生成预测的符号解释；4）能够在测试时保证逻辑约束的满足，这对于安全关键应用至关重要。我们的实验表明，A-NESI是首个能够解决具有指数组合复杂度的三个神经符号任务的端到端方法。最后，我们的实验表明，A-NESI在不损失性能的情况下实现了可解释性和安全性。

1 引言

最近的神经符号学习工作将神经感知与符号推理相结合[52, 38]，使用符号知识来约束神经网络，从弱监督信号中学习感知，并提高数据效率[5, 57]。许多神经符号方法使用可微逻辑，例如模糊逻辑[5, 17]或概率逻辑[35, 57, 16]。我们将后者称为概率神经符号学习（PNL）方法。与模糊逻辑不同，PNL方法在离散真值上添加概率，以保持经典逻辑中的所有逻辑等价。然而，执行推理需要解决加权模型计数（WMC）问题，其计算复杂度呈指数增长，显著限制了PNL能够解决的任务类型。

我们研究如何利用深度生成建模将PNL扩展到具有指数复杂度的任务。我们的方法称为近似神经符号推理（A-NESI），引入了两个神经网络，用于对WMC问题进行近似推理。预测模型预测系统的输出，而解释模型计算哪些世界（即哪些逻辑符号的真值分配）最能解释一个预测。我们使用一种新颖的训练算法，使用背景知识生成的数据来拟合这两个模型：A-NESI从先验中采样符号概率，并使用符号背景知识计算给定这些概率的可能输出。我们在这些样本上训练这两个模型。图1提供了概述。

A-NESI结合了神经符号学习的所有优势和可扩展性。我们在多数字MNISTAdd问题上的实验表明，与其他方法不同，A-NESI在数字数量上几乎呈线性扩展，并在保持精确推理的预测性能的同时解决了多达15位数字的MNISTAdd问题。此外，它能够生成预测的解释，并使用一种新颖的符号剪枝器保证逻辑约束的满足。

本文的结构如下。第3节介绍A-NESI。第3.1节介绍用于近似推理的可扩展神经网络。第3.2节概述了使用背景知识生成数据的新颖训练算法。第3.2.4节扩展A-NESI以包含解释模型。第3.3节扩展A-NESI以保证逻辑公式的满足。在第4节中，我们在需要感知和推理的三个神经符号任务上进行实验。我们在多数字MNISTAdd问题上的实验表明，A-NESI学会了预测两个15位手写数字的和，而竞争系统只能处理4位数字。同样，A-NESI能够分类9×9的数独谜题，而其他方法只能处理4×4的谜题，并在30×30的网格中找到最短路径，而其他方法只能处理12×12的网格。

2 问题设置

首先，我们介绍我们的推理问题。我们将使用[35]中的MNISTAdd任务作为示例。在这个问题中，我们需要仅使用两个MNIST数字的和作为训练标签来学习识别它们的和。重要的是，我们不提供单个MNIST数字的标签。

2.1 问题组成部分

我们引入四个集合，分别表示感兴趣变量的空间。

我们假设可以访问某个符号推理函数 c: W → Y，它能够确定性地计算出任何世界 w 的（结构化）输出 y。这个函数捕捉了我们对问题的背景知识，我们对其形式不做任何限制。对于 MNISTAdd 任务，c 接收两个数字（例如 5 和 8），将它们相加，并按位分解和以形成（1, 3）。

2.2 加权模型计数

这些组件共同构成了加权模型计数（WMC）问题：

2.3 精确推理在加权模型计数（WMC）中的问题

在第2.2节中介绍的三个量需要计算或估计公式（1）中的加权模型计数问题。然而，WMC的精确计算是#P难的，这比NP难还要复杂。因此，我们需要在每次训练迭代和测试查询中进行潜在的指数时间计算。现有的概率神经符号学习（PNL）方法使用概率电路（PCs）来加速这一计算[60, 28, 35, 57]。概率电路将逻辑公式编译成一个电路，使得许多推理查询的计算复杂度与电路的大小呈线性关系。当需要精确推理时，概率电路是一个不错的选择，但它并没有克服问题的固有指数复杂性：编译步骤可能在时间和内存上都是指数级的，并且无法保证电路的大小不会呈指数增长。

多数字MNISTAdd任务非常适合研究WMC的扩展性。我们可以通过考虑不仅仅是两个单个数字的和（称为N=1），而是两个多位数的和，从而将MNISTAdd的复杂性呈指数级增加。例如，N=2的情况是=135。使用两个两位数相加得到135的方法有64种。相比之下，两个单个数字相加得到13的方法只有6种。每次N的增加都会使精确推理需要考虑的选项数量增加10倍。我们在第4节中的实验将表明，近似推理可以解决这个问题，直到N=15。如果使用精确推理来解决这个问题，则需要为每个查询枚举大约10¹⁵种选项。

3 A-NESI：近似神经符号推理

我们的目标是降低PNL的推理复杂度，以便在更复杂的问题上训练神经符号模型。为此，我们在以下小节中介绍近似神经符号推理（A-NESI）。A-NESI使用神经网络来近似第2节中提到的三个感兴趣量，即。我们在图1中给出了我们方法的概述。

3.1 推理模型

这种损失的梯度由于近似 的误差而存在偏差，但在从训练数据集中采样之外，它没有方差。

3.2 训练推理模型

3.2.1 训练仅预测变体

3.2.2 输出空间分解

选择正确的分解方式在应用 A-NESI 时至关重要。一种通用的方法是取符号函数的合取范式（CNF），并预测每个子句的真值。然而，这需要对公式进行实例化，这可能是指数级的。另一种选择是预测全量化公式对哪些对象成立，这将与对象的数量成线性关系。

3.2.3 信念先验设计

3.2.4 训练可解释变体

3.3 符号剪枝器

4 实验
我们研究了三个神经符号推理任务，以评估 A-NESI 的性能和可扩展性：多数字 MNISTAdd [37]、视觉数独谜题分类 [4] 和《魔兽争霸》路径规划。代码可在 GitHub - HEmile/a-nesi 上找到。我们全程使用了 ADAM 优化器。

4.1 多数字 MNISTAdd

4.2 视觉数独谜题分类

4.3 《魔兽争霸》视觉路径规划

《魔兽争霸视觉路径规划任务》[43]的目标是预测从一个N×N网格的左上角到右下角的最短路径，给定一张来自《魔兽争霸》游戏的图像（见图5）。感知模型需要学习《魔兽争霸》图像中每个方格的成本。我们使用了一个小型卷积神经网络（CNN），它接收第i行、第j列的方格（一个3×8×8的图像）并输出一个关于5种可能成本的分布。符号函数c(w)是迪杰斯特拉算法，返回一条最短路径y，我们将这条路径编码为从左上角开始的8个（中）间方向的序列。我们使用ResNet18[22]作为预测模型，训练它根据方格成本的信念P和当前位置来预测下一个方向。我们先在固定的先验分布上预训练预测模型，然后在冻结预测模型的情况下训练感知模型。更多细节见附录I.3。

表3展示了预测最短路径的准确率。A-NESI在12×12的网格上具有竞争力，但在30×30的网格上表现不佳。我们推测这是因为预测模型不够准确，导致梯度偏差过大。尽管如此，A-NESI仍然能找到较短的路径，比纯神经网络表现更好，并且能够扩展到30×30的网格。相比之下，SPL[1]使用精确推理，无法扩展到30×30的网格。由于SPL和I-MLE[41]的设置与我们的方法存在显著差异（见附录I.3.2），我们还增加了使用留一法基线的REINFORCE算法（RLOO，[29]）的实验，该算法是通过Storchastic PyTorch库[53]实现的。我们发现RLOO的性能方差很高。由于RLOO是无偏但高方差的，而A-NESI是有偏但无方差的，我们尝试同时运行A-NESI和RLOO。有趣的是，这种方法在12×12的网格上表现最佳，并且在30×30的网格上具有竞争力，尽管方差很高（10次运行中有6次的准确率在93.3%到98.5%之间，而其他运行的准确率则卡在25%左右）。

5 相关工作

A-NESI可以近似多种PNL方法[16]。DeepProbLog[35]通过将w表示为Prolog程序中的事实，执行符号推理。它枚举查询y的所有可能证明，并通过p(w|P)对每个证明进行加权。NeurASP[58]是一种与DeepProbLog密切相关的PNL框架，但它是基于Answer Set Programming[12]的。一些方法考虑了约束结构化输出预测[19]。在附录B中，我们讨论了将A-NESI扩展到这种设置。

Semantic Loss[57]通过损失函数改进学习，但不能保证公式在测试时被满足。与A-NESI类似，Semantic Probabilistic Layers[1]通过一个执行约束预测的层解决了这个问题。这些方法使用概率电路（PCs）[60]进行精确推理。其他方法通过仅考虑PCs中的top-k证明来执行近似推理[36, 23]。然而，找到这些证明是困难的，尤其是当信念具有高熵时，限制为top-k会显著降低性能。其他工作考虑了MCMC近似[31]。使用神经网络进行近似推理可以确保计算时间是固定的，并且与P的熵或长MCMC链无关。

其他神经符号方法使用模糊逻辑[5, 17, 15, 18]，其速度比PNL的精确推理更快。尽管遍历事实公式是线性时间的，但事实化本身通常是级指数的[37]，因此模糊逻辑的可扩展性往往无法实现。A-NESI在事实原子的数量上是多项式的，并且不遍历事实公式。此外，背景知识通常不是模糊的[54, 20]，并且模糊语义不保留经典等性价。

A-NESI执行WMC问题的梯度估计。我们可以将我们的方法扩展到有偏但零方差的梯度估计，通过学习函数输出的分布（见附录C）。许多最近的工作考虑了离散计算的连续松弛，以使其可微分[42, 24]，但这需要许多技巧才能在计算上可行。其他方法通过计算MAP状态来计算梯度[41, 11, 47]，但这些方法仅限于整数线性规划。得分函数（或“REINFORCE”）提供了无偏但高方差的梯度估计[40, 53]。存在一些减少这种方差的技术，例如记忆增强[32]和留一法基线[29]。

6 结论、讨论与局限性

我们介绍了A-NESI，这是一种可扩展的概率神经符号学习的近似方法。我们证明了A-NESI能够在不损失准确性的情况下扩展到组合性挑战性的任务。A-NESI可以扩展以包含解释和硬约束，而不会损失性能。然而，天下没有免费的午餐：何时A-NESI是一个好的近似方法？我们讨论了可能使其难以学习强大且高效推理模型的三个学习任务方面。

变量的依赖性 当世界w中的变量高度依赖时，找到一个信息量丰富的先验是困难的。我们建议在这种情况下使用可以纳入依赖性的先验，例如归一化流[45, 14]或基于狄利克雷分布的深度生成模型[51]。

符号推理函数的结构 我们研究的推理任务具有相对简单的结构。当符号函数c的结构不那么清晰时，学习推理模型将更加困难。研究结构与可学性之间的关系是未来有趣的工作方向。

问题规模 A-NESI在更具挑战性的问题中未能完美训练预测模型，这从表1中15位数字的符号预测与神经预测之间的性能差异中可以看出。我们预计其所需的参数规模和训练时间会随着问题规模的增加而增加。

未来有希望的研究方向包括研究解释模型是否能产生有用的解释[50]，扩展到连续随机变量[21]（见附录C中的示例），以及扩展到非归一化分布（如马尔可夫逻辑网络[46]），以及为神经符号编程语言（如DeepProbLog[35]）开发（半）自动化的A-NESI解决方案。

D.2 晶格GFlowNet表示

我们对生成过程的设置假设我们是按照某种顺序生成世界中的每个变量的。对于某些问题，比如MNISTAdd，我们可以将生成过程看作是“从左到右读取”，这种假设是可以接受的。然而，对于其他问题，例如数独，我们希望生成符号的顺序就不那么明显了。我们会按块生成吗？按行生成？按列生成？或者本身假设需要以某种固定顺序生成就是错误的呢？

通过这种表示方法，我们可以显著减少用于表示加权模型计数（WMC）问题的流网络的大小和计算量。例如，比较图6和图7，它们都表示公式A∨B的WMC。我们不再需要在分支y=0中用两个节点来表示A和B为假的情况，因为初始的空集{}已经隐含了这一点。这将为我们节省两个节点。同样，我们可以在{A}和{B}处立即停止生成，而不再需要将另一个变量生成为假，这也节省了一个计算步骤。

尽管从理论上讲这种方法很有吸引力，但它也有三个主要缺点：1）正向流（PB）不再容易计算；2）我们需要处理不再是一棵树的事实，这意味着不再有唯一的最优正向流（PF）和反向流（PB）；3）并行化变得更加复杂。我们将探索这一方向的实际应用留待未来的研究。

这种差异同样通过平方在其导数中考虑了p和q之间的距离。然而，它比联合匹配损失要不稳定得多，因为p和q都是通过对许多小数的乘积来计算的。在这种情况下计算平方根，比对每个单独概率取对数并求和的数值稳定性要低得多。最后，我们指出，我们通过取导数Eq[∇ϕ,ψ(log p − log q)²]来最小化策略内的联合匹配Eq[(log p − log q)²]。从技术上讲，这并不是最小化联合匹配，因为它忽略了来自从q中采样的梯度。

F 狄利克雷先验

本节描述了我们如何拟合用于训练推理模型的狄利克雷先验p(P)。在训练期间，我们保留了一个包含最近2500个P = fθ(x)观测值的数据集。由于θ在训练过程中会发生变化，这意味着P的经验分布也会随之变化，因此我们需要频繁丢弃观测值。

我们对kW个独立的狄利克雷先验进行最大似然估计（MLE），以获得每个先验的参数α。狄利克雷分布的对数似然无法以闭合形式找到[39]。然而，由于其对数似然是凸的，我们运行ADAM[25]算法50次迭代，学习率为0.01，以最小化负对数似然。关于计算对数似然和替代选项的详细信息，请参考[39]。由于狄利克雷分布接受正参数，我们在训练期间对无约束参数应用softplus函数。我们将所有参数初始化为0.1，并对参数添加了L2正则化。这是必要的，因为在训练初期，所有观测值P = fθ(x)都表示对数字的均匀信念，这些值几乎相等。因此，对数据拟合狄利克雷分布会给出越来越高的参数值，因为高参数值代表低熵的狄利克雷分布，这种分布会产生均匀的信念。当狄利克雷分布是低熵时，推理模型会学会忽略输入信念P，因为它从未改变。L2正则化鼓励低参数值，这对应于高熵的狄利克雷分布。

G 设计符号剪枝器

接下来，我们讨论四种用于设计可选符号剪枝器的高级方法，每种方法在准确性、工程时间和效率方面都有不同的权衡：

1. 数学推导高效求解器 对于简单问题，我们可以数学推导出一个精确求解器。附录H中给出了Multi-digit MNISTAdd的一个高效符号剪枝器及其精确性的证明。这个剪枝器是线性时间的。然而，对于大多数问题，我们预计剪枝器的计算成本会高得多。

2. 使用SAT求解器 将采样的符号y和加入到一个CNF公式中，并询问一个SAT求解器是否存在一个扩展能够满足该CNF公式。SAT求解器是一种通用方法，适用于每一个函数c，但使用它们是有代价的。首先，我们需要对问题的逻辑表示进行事实化（grounding）。此外，为了进行SAT求解，我们必须解决线性数量的NP难问题。然而，由于多年的设计进步，竞争性的SAT求解器能够处理相当复杂的问题[7]，并且线性数量的NP难调用是一个比#P难更低的复杂性类别。在安全性和可验证性至关重要的问题设置中，使用SAT求解器将特别有吸引力。

3. 使用局部约束进行剪枝 在许多结构化预测任务中，我们可以利用符号问题的局部约束来剪枝那些肯定会导致无法创建可能世界的分支的路径。然而，局部约束并不能保证每条未剪枝的路径都包含一个可能世界，但这并不会使推理模型产生偏差，因为神经网络最终会学会何时扩展会导致不可满足的状态。

一个例子是最短路径问题，我们在其中过滤掉会导致超出N×N网格范围或形成环路的方向（见附录I.3）。然而，这只能确保我们找到一条路径，但不能确保它是最短路径。

4. 学习剪枝器。最后，我们可以学习剪枝器，也就是说，我们可以训练一个神经网络来学习可满足性检查。一种可能的方法是重用在信念P上训练的推理模型，该信念P在所有可能世界中均匀分布质量。

通过学习得到的剪枝器将和常规推理模型一样快速，但它们的准确性不如符号剪枝器，并且在测试时不能保证约束条件始终得到满足。我们将学习剪枝器的实验留待未来工作。

I. 实验细节

I.1 Multi-digit MNISTAdd

与文献[36, 37]类似，我们采用MNIST数据集[30]，并确保每个数字恰好使用一次来创建数据。我们遵循文献[36]的方法，随着N的增加，需要更多的唯一数字。因此，训练数据集的大小将为60000/2N，测试数据集的大小为10000/2N。

I.1.1 超参数

我们通过将训练数据划分为50,000和10,000个数字，形成训练集和验证集，并在验证集上进行超参数调整。在调整过程中，我们逐步将N从N=1增加到N=3、N=4，直至N=8，以更好地了解哪些超参数是重要的。除了学习率之外，最重要的参数是狄利克雷先验参数的L2正则化权重，该权重应该非常高。在整个过程中，我们使用了ADAM优化器[25]。我们对每个实验进行了10次运行，以估计平均准确率，每次运行在训练集数据上进行100个周期的训练。我们使用了Nvidia RTX A4000 GPU和24核AMD EPYC-2（Rome）7402P CPU。

我们在表4中给出了最终的超参数。对于所有的N，我们使用了相同的超参数集合。

“样本数量”指的是我们在算法1中用于训练推理模型的样本数量。为了简化，它也是测试时束搜索（beam search）的束宽度。

“隐藏层”和“宽度”指的是用于计算推理模型每个因子的多层感知机（MLP）。这里没有参数共享。感知模型在这个任务中是固定的，以确保性能提升是由于神经符号推理（见文献[35]）。

I.1.2 其他方法

我们将我们的方法与之前解决MNISTAdd任务的多个神经符号框架进行了比较。其中一些是概率神经符号方法：DeepProbLog[35]、DPLA*[37]、NeurASP[58]和NeuPSL[44]。我们还与基于模糊逻辑的方法LTN[5]以及Embed2Sym[3]和DeepStochLog[56]进行了比较。我们从相应的论文中获取结果，除了DeepProbLog和NeurASP的结果来自[37]，LTN的结果来自[44]。我们重新运行了Embed2Sym，平均了10次运行的结果，因为它的论文没有报告标准差。我们没有将DPLA*与预训练进行比较，因为它解决的是一个更简单的问题，其中部分数字是标记过的。

Embed2Sym[3]通过三个步骤解决多数字MNISTAdd问题：首先，它训练一个神经网络将每个数字嵌入，并从这些嵌入中预测总和。然后，它对嵌入进行聚类，并使用符号推理将聚类分配给标签。A-NESI具有类似的神经网络架构，但我们训练预测网络的目标不需要数据。此外，与Embed2Sym不同，我们对A-NESI进行了端到端训练。对于Embed2Sym，我们使用“符号预测”来指代Embed2Sym-NS，使用“神经预测”来指代Embed2Sym-FN，它也使用预测网络，但仅在给定的训练数据上进行训练，并且不使用先验来采样额外的数据。

我们相信与DeepProbLog相比的准确率提升来自于超参数调整和更长的训练时间，因为A-NESI近似了DeepProbLog的语义。

I.2 Visual Sudoku Puzzle Classification

I.2.1 A-NeSI定义

I.2.2 超参数和其他方法

我们使用了来自文献[4]的视觉数独谜题分类数据集。这个数据集提供了许多选项：

我们使用了简单的生成器策略，生成了200个训练谜题（100个正确，100个错误）。我们选择了0.50的损坏概率，并使用了0重叠的数据集（这意味着每个MNIST数字在200个谜题中只能使用一次）。这个数据集有11个独立生成的分割。我们在9×9数据集的第11个分割上进行了超参数调整，并使用其他10个分割来评估结果，对每个分割的结果进行平均。

最终的超参数在表5中报告。对于4×4谜题，5000个训练周期平均需要20分钟，而对于9×9谜题则需要38分钟，运行在一台配备单个NVIDIA RTX A4000的机器上。在最初的50个周期中，我们只训练了预测模型，以确保它提供合理的准确梯度。

虽然文献[4]使用了NeuPSL，但我们不得不重新运行它以获取准确率结果以及9×9网格上的结果。

我们使用了可以最好地描述为语义损失[57]的确切推理方法。我们将本节开头描述的数独规则编码为CNF，并使用PySDD（[https://github.com/wannesm/PySDD](https://github.com/wannesm/PySDD)）将其编译为SDD[28]。对于4×4的CNF，这几乎是瞬间完成的，但我们未能在4小时内编译9×9的CNF，因此我们报告了精确推理的超时。为了实现语义损失，我们修改了一个PyTorch实现，该实现可在[https://github.com/lucadiliello/semantic-loss-pytorch](https://github.com/lucadiliello/semantic-loss-pytorch)找到，以在对数空间中进行计算以实现数值稳定的行为。这个修改后的版本包含在我们自己的代码库中。我们用0.001的学习率运行了这个方法300个周期。我们运行的周期较少，因为即使在4×4的谜题上，它也比A-NESI慢得多（300个周期需要1小时16分钟，因此大约慢63倍）。

对于A-NESI和精确推理，我们在正确谜题上训练感知模型，通过最大化p(y=1|P)的概率。A-NESI通过最大化log qϕ(y=1|P)来实现，而语义损失则使用PSDD精确计算log p(y=1|P)。对于错误的谜题，由于我们不能对y做出任何假设，因此收益不多。然而，对于这两种方法，我们仍然为错误的谜题增加了−log(1−p(y=1|P))的损失。

I.3 Warcraft 视觉路径规划

I.3.1 A-NeSI定义

我们将x视为一个的实数张量：前两个维度表示不同的网格单元，第三个维度表示RGB颜色通道，最后两个维度表示每个网格单元中的像素。世界w是一个(N XN)的整数网格，其中每个整数索引了穿越该单元的五种不同成本。这五种成本是[0.8, 1.2, 5.3, 7.7, 9.2]，对应于《魔兽争霸》游戏中可能的五种成本。符号函数c接收成本网格w，并使用Dijkstra算法返回从左上角(1, 1)到右下角(N, N)的最短路径。我们将最短路径编码为在网格中需要采取的一系列动作，其中每个动作是八个（介于）基本方向之一（向下、右下、向右等）。该序列用“不移动”动作填充，以便于批量处理。

原文链接：https://arxiv.org/pdf/2212.12393