Scallop: A Language for Neurosymbolic Programming
https://arxiv.org/pdf/2304.04812
https://github.com/scallop-lang/scallop
神经符号语言应该满足的五个关键标准：
DQN 50K个训练周期才能达到84.9%的测试成功率，其中单个周期是从头到尾的一次游戏会话。相比之下，使用Scallop的神经符号解决方案只需要50个训练周期就能达到99.4%
Scallop的关键洞见是利用逻辑程序的结构来指导梯度计算
支持不同的推理模式——离散的、概率的和可微的。
18 种内置源数据（4 种用于离散推理，6 种用于概率推理，8 种用于可微推理）
RQ1 Scallop 在解决多样化的神经符号任务方面的表达能力如何？
RQ2 Scallop 的解决方案与最新基准在准确性方面的比较如何？
RQ3 Scallop 的可微推理模块是否运行高效？
RQ4 Scallop 在提高泛化能力、可解释性和数据效率方面是否有效？
RQ5 Scallop 解决方案的失败模式是什么，我们如何减轻它们？
摘要：
我们介绍了Scallop，这是一种结合了深度学习和逻辑推理优势的语言。Scallop使用户能够编写广泛的神经符号应用程序并以数据和计算高效的方式训练它们。它通过
三个关键特性实现这些目标：
1）基于关系数据模型的灵活符号表示；
2）基于Datalog的声明式逻辑编程语言，支持递归、聚合和否定；
3）基于源半环理论的自动和高效可微推理框架。
我们在文献中的八种神经符号应用程序套件上评估了Scallop。我们的评估表明，Scallop能够表达多样化和具有挑战性的AI任务中的算法推理，为机器学习程序员提供了一个简洁的接口来整合逻辑领域知识，并且在准确性方面提供的解决方案可与或优于最先进的模型。此外，Scallop的解决方案在运行时间和数据效率、可解释性以及泛化能力等方面超越了这些模型。
1 引言
经典算法和深度学习是现代编程的两种普遍范式。
经典算法非常适合明确定义的任务，例如对数字列表进行排序或在图中找到最短路径。另一方面，深度学习非常适合使用经典算法无法实现或不可行的任务，例如在图像中检测对象或解析自然语言文本。这些任务通常使用一组输入输出训练数据来指定，解决它们涉及使用基于梯度的方法学习深度神经网络的参数以适应数据。
这两种范式本质上是互补的。例如，图1a所示的经典算法（如逻辑程序𝑃）是可解释的，但只能处理有限的（例如，结构化的）输入𝑟。相比之下，图1b所示的深度神经网络𝑀𝜃可以处理丰富的（例如，非结构化的）输入𝑥，但不可解释。现代应用需求两种范式的能力。例如，问题回答【Rajpurkar等，2016】、代码补全【Chen等，2021b】、数学问题求解【Lewkowycz等，2022】等。
例如，代码补全需要深度学习从代码上下文中理解程序员的意图，同时也需要经典算法确保生成的代码是正确的。因此，一个自然且基础的问题是如何通过结合这两种范式来编程这些应用。神经符号编程是一种新兴的范式，旨在实现这一目标【Chaudhuri等，2021】。它试图通过将符号知识和推理与神经架构相结合，获得比单独的神经或符号方法更好的效率、可解释性和泛化性。
考虑手写公式求解任务【Li等，2020】，该任务以公式图像作为输入，输出相应的计算结果。该任务的一个输入输出示例为。针对此任务的神经符号程序，如图1c所示，可能首先应用卷积神经网络𝑀𝜃到输入图像，得到一个符号序列的结构化中间形式𝑟，如['1', '+', '3', '/', '5']，然后使用经典算法𝑃解析该序列，评估解析的公式，并输出最终结果1.6。
尽管在各个神经符号应用方面取得了显著进展[Chen等人，2020年；Li等人，2020年；Mao等人，2019年；Minervini等人，2020年；Wang等人，2019年；Yi等人，2018年]，但缺乏一种具有编译器支持的语言，以使神经符号范式的好处更加广泛地被人们所接受。我们着手开发这样的神经符号语言，并确定了
神经符号语言应该满足的五个关键标准，以便实用。这些标准由图1c中的神经符号程序的组件注释如下：
(1) 支持多种数据类型的符号数据表示𝑟，例如图像、视频、自然语言文本、表格数据及其组合。
(2) 允许表达递归、否定和聚合等常见推理模式的符号推理语言𝑃。
(3) 在算法监督下自动高效地进行可微推理引擎，即对可观察的输入输出数据（𝑥, 𝑦）但不对𝑟进行监督。
(4) 能够根据个别应用的特点定制学习（𝜕𝑦/𝜕𝑟），因为逻辑程序的非连续损失景观阻碍了使用一刀切方法的学习。
(5) 利用和整合现有训练管道（𝜕𝑟/𝜕𝜃）、神经架构和模型𝑀𝜃的实现以及硬件（例如，GPU）优化的机制。
在本文中，我们介绍了Scallop，一种满足上述标准的编程语言。Scallop背后的主要洞见在于其选择的三个相互依赖的设计决策：关系模型用于符号数据表示，声明式语言用于符号推理，以及用于可微推理的源框架。我们详细阐述了这些决策。
关系可以表示任意图，因此非常适合在Scallop应用程序中表示符号数据。例如，它们可以表示场景图，这是图像的一种规范符号表示[Johnson等人，2015]，或抽象语法树，这是自然语言文本的符号表示。此外，它们可以在关系数据库中组合以表示多模态数据。关系也非常适合概率推理[Dries等人，2015]，这是因为由神经模型𝑀𝜃产生的符号𝑟可能具有相关联的概率。
接下来，Scallop中的符号推理程序𝑃是用声明式逻辑编程语言指定的。该语言扩展了Datalog[Abiteboul等人，1995]，并且足够表达，以便程序员可以指定神经模型𝑀𝜃难以处理的复杂领域知识模式。Datalog实现可以利用关系数据库系统文献中的优化。这反过来又使得推理和学习更加高效，因为手头任务的逻辑领域知识规范有助于减轻𝑀𝜃的负担，其职责现在不那么复杂，更具模块化。最后，Datalog基于规则，这使得程序更容易编写、调试和验证。它还促进了通过利用程序合成[Gulwani等人，2017]和归纳逻辑编程[Cropper等人，2022]的技术来推断它们。
虽然符号推理提供了许多前述的好处，但它对学习参数𝜃提出了一个基本挑战。深度学习依赖于基于梯度的方法，这些方法是由构成𝑀𝜃的低级激活函数的可微性质实现的，以获得𝜕𝑟/𝜕𝜃。关键挑战在于如何支持高级逻辑程序𝑃的自动和高效微分，以获得𝜕𝑦/𝜕𝑟，这可以与𝜕𝑟/𝜕𝜃结合使用来计算𝜕𝑦/𝜕𝜃。Scallop通过利用源半环框架[Green等人，2007]来解决这个问题。该框架为定义元组注释（即标签）并将注释从关系代数（RA）查询的输入传播到输出的应用提出了一种共同的代数结构。我们的主要贡献之一是将框架新颖地适应于包括递归、否定和聚合的RA扩展片段的可微推理。Scallop实现了一个可扩展的源结构库，包括扩展的最大-最小半环和top-𝑘证明半环[Huang等人，2021]。我们进一步证明不同的源结构为梯度计算提供了不同的启发式方法，为定制学习过程提供了有效的机制以适应各个应用的特点。
我们已经用Rust编写了45K LoC的全面和开源工具链来实现Scallop。它包括一个
编译器、一个解释器和PyTorch绑定，以将Scallop程序与现有的机器学习管道集成。我们使用涵盖图像和视频处理、自然语言处理、规划和知识图查询等领域的八个神经符号应用程序套件来评估Scallop，在各种学习设置如监督学习、强化学习、规则学习和对比学习中。我们的评估表明，Scallop具有表现力，并且提供的解决方案在准确性上与最新模型相当，甚至往往更优。我们展示了Scallop解决方案在运行时间和数据效率、可解释性以及泛化能力方面的额外好处。
任何编程语言论述都会遗漏对语言血统的承认。TensorLog[Cohen等人，2017]和DeepProbLog (DPL)[Manhaeve等人，2021]开创了将概率逻辑编程语言（例如，ProbLog[Dries等人，2015]）与可微推理扩展的想法。Scallop最初在[Huang等人，2021]中提出，通过使用Datalog而不是Prolog并放宽其精确的概率语义来提高DPL的可扩展性。我们在[Huang等人，2021]的基础上，通过扩展其表达能力、形式化语义、开发可定制的源框架并提供实用的工具链来构建。
本文的其余部分组织如下。第2节提供了Scallop的说明性概述。第3节描述了Scallop的符号推理语言。第4节介绍了可微推理框架。第5节描述了我们对Scallop的实现。第6节在基准套件上实证评估Scallop。第7节调查相关工作，第8节总结。
2 说明性概览
我们使用一个基于强化学习（RL）的规划应用程序来说明Scallop，我们称之为PacMan-Maze。该应用程序如图2a所示，涉及一个智能代理在简化版的PacMan迷宫游戏中执行一系列动作。迷宫是一个隐式的5×5格子网格。每个单元格要么是空的，要么包含一个实体，可以是行动者（PacMan）、目标（旗帜）或敌人（鬼魂）。在每一步，代理使行动者朝四个方向之一移动：上、下、右或左。当行动者到达目标或碰到敌人时，游戏结束。迷宫作为原始图像在每一步更新，要求代理处理感官输入，提取相关特征，并逻辑规划要走的路径。此外，游戏的每个会话都有随机化的行动者、目标和敌人的初始位置。
具体来说，游戏被建模为代理与环境之间的一系列交互，如图2b所示。游戏状态𝑠𝑖 ∈ 𝑆在步骤𝑖是一个200×200的彩色图像。代理向环境提出一个动作𝑎𝑖 ∈ 𝐴 = {上，下，右，左}，环境生成一个新的图像𝑠𝑖+1作为下一个状态。环境还返回一个奖励𝑟𝑖给代理：达到目标时为1，否则为0。这个过程一直重复，直到游戏结束或达到预定义的步数限制。
实现我们应用程序的一种流行的RL方法是𝑄-学习。它的目标是学习一个函数𝑄 : 𝑆 ×𝐴 → R，该函数返回在状态𝑠𝑖下采取动作𝑎𝑖的预期奖励。
1. 由于游戏状态是图像，我们采用深度𝑄-学习[Mnih等人，2015]，它使用具有学习参数𝜃的卷积神经网络（CNN）模型来近似𝑄函数。对于我们的应用程序，基于端到端深度学习的方法涉及训练模型预测给定游戏状态的每个动作的𝑄值。这种方法需要50K个训练周期才能达到84.9%的测试成功率，其中单个周期是从头到尾的一次游戏会话。
相比之下，使用Scallop的神经符号解决方案只需要50个训练周期就能达到99.4%的测试成功率。Scallop通过将代理的任务分解为独立的神经和符号组件来实现这些神经符号范式的好处，如图2b所示。这些组件执行最适合各自范式的子任务：神经组件在每一步感知图像的单个单元格的像素以识别其中的实体，而符号组件则推理从行动者到目标的无敌人路径，以确定最优的下一个动作。图2c显示了使用流行的PyTorch框架实现这种架构的大纲。
具体来说，神经组件仍然是一个CNN，但现在它一次处理输入图像中的单个单元格的像素，并对该单元格中的实体进行分类。神经组件（EntityExtractor）的实现是标准的，为了简洁起见省略了。它在图2c的第14-15行被调用，输入是游戏状态图像，一个在中的张量，返回三个
)的实体张量。例如，actor是一个
张量，actor_(i,j)是行动者在单元格(i, j)中的概率。然后将实体的表示传递给符号组件，在第16-17行，它推导出每个动作的𝑄值。符号组件在第6-11行配置，包括图3中显示的Scallop程序。接下来，我们将用这个程序来说明第1节中概述的Scallop的三个关键设计决策。
关系模型。在Scallop中，表示符号的主要数据结构是关系。在我们的示例中，游戏状态可以通过在5×5网格的离散单元格中出现的各种实体来符号化描述。因此，我们可以使用二元关系来表示符号组件的输入，这三种实体分别是：行动者、目标和敌人。例如，事实actor(2,3)表示行动者在单元格(2,3)中。同样，由于有四种可能的动作，符号组件的输出由一个一元关系next_action表示。神经网络从非结构化输入中提取的符号具有相关联的概率，例如我们示例中神经组件产生的R^(5×5)张量actor（图2c的第14行）。
因此，Scallop允许将元组与概率相关联，例如0.96 :: actor(2,3)，表示行动者在单元格(2,3)中的概率为0.96。更一般地说，Scallop通过输入输出映射（图2c中的第9-11行），使得神经组件中的张量与符号组件中的关系可以无缝转换，允许两个组件交换信息。
声明式语言。神经符号语言中的另一个关键考虑是为符号推理提供哪些构造。Scallop使用基于Datalog的声明式语言，我们在第3节中介绍，并在这里使用图3中的程序进行说明。该程序使用一组逻辑规则实现了我们示例的符号组件。遵循Datalog语法，它们是“如果-那么”规则，从右到左阅读，逗号表示合取。
回想一下，我们希望确定一个动作𝑎（上、下、右或左）到一个与行动者单元格(𝑥, 𝑦)相邻的单元格(𝑝, 𝑞)，使得从(𝑝, 𝑞)到目标单元格(𝑟, 𝑠)有一条无敌人的路径。九条描述的规则通过构建越来越复杂的关系来简洁地计算这种复杂的推理模式，最后一行的规则（第14行？？）计算所有这样的动作。
最复杂的概念无疑是路径关系，它是递归定义的（第10-11行）。递归允许简洁地定义模式，使得训练后的应用程序能够泛化到比5×5大得多的网格，与纯粹的神经版本不同，并且使模式更容易从输入输出示例中合成。除了递归，Scallop还支持否定和聚合；这些特性共同使得该语言足以在实践中指定常见的高级推理模式。
可微推理。随着神经和符号组件的定义，最后一个主要考虑是如何仅使用端到端的监督来训练神经组件。
在我们的示例中，监督以每个游戏会话的1或0的奖励形式提供，这取决于代理的一系列动作是否成功地带领行动者到达目标而没有碰到任何敌人。这种形式的监督，称为算法性或弱监督，减轻了标记神经和符号组件界面上的中间关系（例如行动者、目标和敌人关系）的需要。然而，这也使得学习这些关系的张量的梯度变得具有挑战性，而这些梯度反过来又需要使用梯度下降技术来训练神经组件。
Scallop的关键洞见是利用逻辑程序的结构来指导梯度计算。这些计算的最佳启发式取决于几个应用特征，如可用数据量、推理模式和学习设置。Scallop为用户提供了方便的接口，可以从内置启发式库中选择。此外，由于所有这些启发式都遵循逻辑程序的结构，Scallop将它们统一实现为一个通用且可扩展的源框架provenance framework的实例，该框架在第4节中描述。对于我们的示例，图2c中的第8行指定了diff-top-k-proofs，k=1作为要使用的启发式，这是Scallop中的默认设置，适用于许多应用程序，我们在第6节中展示了这一点。
3.2 （Horn）规则
由于Scallop的语言基于Datalog，它支持类似“如果-那么”规则的Horn子句。每条规则由一个头部原子和一个主体组成，通过符号:-或=连接。以下代码展示了两条定义祖母关系的规则。在规则主体中使用逗号分隔的原子指定合取，而通过具有相同头部谓词的多个规则指定析取。头部中出现的每个变量也必须在主体中的某个正原子中出现（我们在下面介绍负原子）。
合取和析取也可以使用逻辑连接词如and、or和implies来表达。例如，以下规则等同于上述两条规则结合。
Scallop通过外部函数（FFs）支持值的创建。FFs是多态的，包括算术运算符如+和-，比较运算符如!=和>=，类型转换如[i32] as String，以及内置函数如$hash和$string_concat。它们只对原始值进行操作，而不对关系元组或原子进行操作。以下示例展示了如何使用FF连接字符串，产生结果full_name("Alice Lee")。
请注意，FFs可能会因为运行时错误（如除以零和整数溢出）而失败，在这种情况下，将省略该单个事实的计算。在下面的示例中，当用denominator除以6时，如果denominator为0，则不计算结果，因为这会导致FF失败：
这种语义的目的是支持概率扩展（第3.3节），而不是静默抑制运行时错误。在处理浮点数时，包含NaN（非数字）的元组也会被丢弃。
递归。如果一个原子𝑠出现在头部原子𝑟的规则主体中，那么关系𝑟依赖于𝑠。递归关系是直接或间接依赖于自身的关系。以下规则通过使用组合关系来组合现有的亲缘关系，从而推导出额外的亲缘关系事实。
否定。Scallop在规则主体中使用not运算符支持分层否定。
以下示例展示了一条定义has_no_children关系的规则，即任何既不是父亲也不是母亲的人p。注意，我们需要用一个正原子person来限定p，以使规则格式良好。
如果一个规则的头部原子𝑟的主体中出现了否定原子𝑠，则关系𝑟对𝑠有负依赖。在上面的例子中，has_no_children对father有负依赖。由于Scallop仅支持分层否定，因此关系不能直接或间接对自己有负依赖。以下规则被编译器拒绝，因为否定不是分层的：
聚合。Scallop还支持分层聚合。内置聚合函数包括常见的count（计数）、sum（求和）、max（最大值）以及一阶量词forall（对于所有）和exists（存在）。除了运算符，聚合还指定了绑定变量、用于绑定这些变量的聚合主体，以及分配结果的结果变量。以下示例中的聚合读取为：“变量n被赋予p的计数，使得p是一个人”：
在该规则中，`p` 是绑定变量，`n` 是结果变量。根据聚合器的不同，可能会有多个绑定变量或多个结果变量。此外，Scallop 支持在聚合中使用 `where` 子句进行类似 SQL 的 `group-by` 操作。在以下示例中，我们计算每个人 `p` 的孩子数量，`p` 作为 `group-by` 变量。
最后，量词聚合器如 `forall` 和 `exists` 返回一个布尔变量。例如，在下面的聚合中，变量 `sat` 被赋值为以下语句的真假（`true` 或 `false`）："对于所有的 `a` 和 `b`，如果 `b` 是 `a` 的父亲，那么 `a` 是 `b` 的儿子或女儿"。
对聚合有一些语法检查。首先，与否定类似，聚合也需要分层——一个关系不能通过聚合依赖于自身。其次，绑定变量必须由聚合体中的一个正原子限制。
3.3 概率扩展
虽然 Scallop 主要用于神经符号编程，但其语法也支持概率编程。这在将 Scallop 代码与神经网络集成之前进行调试时特别有用。考虑一个机器学习程序员希望从自然语言句子 “Bob 带着他的女儿 Alice 去海滩” 中提取结构化关系。程序员可以模仿一个神经网络，生成 Alice (A) 和 Bob (B) 之间亲属关系的概率分布，如下所示：
在这里，我们列出了Alice和Bob之间所有可能的亲缘关系。对于每一种关系，我们使用语法[PROB]::[TUPLE]来标记带有概率的亲缘关系元组。分隔它们的分号“;”表示它们是互斥的——Bob不可能同时是Alice的母亲和父亲。Scallop还支持从概率分布中采样的运算符。它们与聚合具有相同的表面语法，允许进行分组采样。以下规则确定性地选择了给定两个人a和b之间最可能的亲缘关系，这两个人在聚合中是隐式的分组变量。最终，将根据上述概率推导出一个事实，即0.95::top_1_kinship(FATHER, A, B)。
Scallop还支持其他类型的采样，包括分类采样（categorical<K>）和均匀采样（uniform<K>），其中静态常数K表示试验次数。最后，规则也可以被标记上概率，这可以反映它们的置信度。以下规则表明，祖母的女儿以90%的置信度是某人的母亲。
概率性规则是语法糖。它们通过在规则的主体中引入一个辅助的0元（即布尔）事实来实现，该事实被认为具有标记的概率为真。
4 推理框架
上一节介绍了程序员用来表达离散推理的Scallop表面语言。然而，该语言还必须支持可微推理以实现端到端训练。在本节中，我们通过一个源框架正式定义了语言的语义。我们展示了Scallop如何通过定义不同的源来统一支持不同的推理模式——离散的、概率的和可微的。
我们首先介绍我们的源框架的基础知识（第4.1节）。然后，我们介绍低级表示SclRam、其操作语义以及它与Scallop应用程序其余部分的接口（第4.2-4.4节）。接下来，我们介绍微分和三种不同的源用于可微推理（第4.5节）。最后，我们讨论实际考虑（第4.6节）。
4.1 源框架Provenance Framework
Scallop的源框架能够在逻辑程序执行中沿着关系元组标记和传播额外的信息。该框架基于源半环理论provenance semirings[Green等人，2007]。图4定义了Scallop的源代数接口。我们称额外信息为来自标签空间𝑇的标签𝑡。有两个特殊的标签，0和1，分别代表绝对假和真标签。标签通过二元析取⊕、二元合取⊗和一元否定⊖的操作传播，类似于逻辑或、和、非。
所有上述组件结合形成一个7元组（𝑇, 0, 1, ⊕, ⊗, ⊖, ⃝=），我们称之为源𝑇。Scallop提供了内置的源库，用户可以通过实现这个接口简单地添加自定义源。
一个源数据（provenance）必须满足一些属性。首先，5元组 (𝑇 , 0, 1, ⊕, ⊗) 应该形成一个半环（semiring）。也就是说，0 是加法恒等元素并且在乘法下具有消去性，1 是乘法恒等元素，⊕ 和 ⊗ 是结合的和交换的，并且 ⊗ 在 ⊕ 上是分配的。为了保证定点的存在（在第4.3节中讨论），它还必须是吸收性的，即，𝑡1 ⊕ (𝑡1 ⊗ 𝑡2) = 𝑡1 [Dannert 等人，2021]。此外，我们需要 ⊖ 0 = 1, ⊖ 1 = 0, 0 ⃝≠ 1, 0 ⃝= 0, 和 1 ⃝= 1。违反个别属性（例如吸收性）的源数据仍然对不使用受影响特性（例如递归）的应用有用，或者如果用户只是想绕过这些限制。
4.2 SclRam 中间语言
Scallop 程序被编译成一种称为 SclRam 的低级表示。图 5 显示了 SclRam 的核心片段的抽象语法。
表达式类似于扩展关系代数中的查询。它们在关系谓词（𝑝）上操作，使用聚合的一元操作（𝛾𝑔 与聚合器 𝑔）、投影（𝜋𝛼 与映射 𝛼）和选择（𝜎𝛽 与条件 𝛽），以及二元操作并集（∪）、乘积（×）和差集（−）。
在 SclRam 中，规则 𝑟 表示为 𝑝 ← 𝑒，其中谓词 𝑝 是规则的头部，表达式 𝑒 是规则的主体。一组无序的规则组合形成一个层次 𝑠，而一系列层次 𝑠1; ... ; 𝑠𝑛 构成了一个 SclRam 程序。同一层次中的规则具有不同的头部谓词。用 𝑃𝑠 表示层次 𝑠 中的头部谓词集合，我们还要求对于程序中的所有 𝑖 ≠ 𝑗，𝑃𝑠𝑖 ∩ 𝑃𝑠𝑗 = ∅。
表面语言中的分层否定和聚合在 SclRam 中作为语法限制强制执行：在层次 𝑠𝑖 中的规则内，如果关系谓词 𝑝 在聚合（𝛾）下使用，或者在差集（−）的右侧使用，那么该谓词 𝑝 不能出现在 𝑃𝑠𝑗 中，如果 𝑗 ≥ 𝑖。
接下来，我们在图 6 中定义了语义域，这些域将用于后续定义 SclRam 的语义。一个元组 𝑢 要么是一个常量，要么是一个元组序列。一个事实 𝑝(𝑢) ∈ F 是一个在关系谓词 𝑝 下命名的元组 𝑢。元组和事实可以被标记，形成标记元组（𝑡 :: 𝑢）和标记事实（𝑡 :: 𝑝(𝑢)）。给定一组标记元组 𝑈𝑇，我们说 𝑈𝑇 ⊨ 𝑢，如果存在一个 𝑡 使得 𝑡 :: 𝑢 ∈ 𝑈𝑇。一组标记事实形成一个数据库 𝐹𝑇。我们使用括号表示法 𝐹𝑇 [𝑝] 来表示在 𝐹𝑇 下的谓词 𝑝 的标记事实集合。
4.3 SclRam 的操作语义
我们现在介绍图 7 中 SclRam 核心片段的操作语义。一个 SclRam 程序 𝑠 以一个扩展数据库（EDB）𝐹𝑇 作为输入，并返回一个意图数据库intentional database（IDB）𝐹′𝑇 = J 𝑠K (𝐹𝑇 )。这个语义依赖于底层的源数据 𝑇。我们称之为标记语义，与传统 Datalog 中的未标记语义相对。
基本关系代数。在 SclRam 中评估一个表达式会根据图 7 顶部定义的规则产生一组标记元组。一个谓词 𝑝 评估为数据库中该谓词下的所有事实。选择操作过滤满足条件 𝛽 的元组，投影操作根据映射 𝛼 转换元组。映射函数 𝛼 是部分的：它可能会失败，因为它可以对值应用外部函数。在并集 𝑒1 ∪ 𝑒2 中的元组可以来自 𝑒1 或 𝑒2。在（笛卡尔）乘积中，每一对传入的元组结合，我们使用 ⊗ 来计算标记的连接。
差集和否定。为了评估差集表达式 𝑒1 −𝑒2，有两种情况，这取决于从 𝑒1 评估出的元组 𝑢 是否出现在 𝑒2 的结果中。如果没有，我们简单地将元组及其标记传递到结果中（Diff-1）；否则，我们从 𝑒1 中得到 𝑡1 :: 𝑢 和从 𝑒2 中得到 𝑡2 :: 𝑢。与未标记语义中从结果中擦除元组 𝑢 不同，我们用 𝑡1 ⊗ (⊖ 𝑡2) 和 𝑢 传递一个标记（Diff-2）。通过这种方式，在否定过程中不会丢失信息。图 8 比较了在不同语义下评估一个示例差集表达式的结果。在未标记语义的结果中，元组 (2, 3) 被移除，但在标记语义中仍然保留。
聚合。SclRam 中的聚合器是对一组（未标记）元组 𝑈 ∈ U 进行操作的离散函数 𝑔。它们返回一组聚合元组，以考虑像 argmax 这样可能产生多个结果的聚合器。例如，我们有 count(𝑈) = {|𝑈 |}。然而，在概率域中，离散符号并不足够。给定 𝑛 个标记元组进行聚合，每个标记元组可以开启或关闭，从而产生个不同的世界。每个世界是输入集 𝑈𝑇 (|𝑈𝑇 | = 𝑛) 的一个划分。将正部分记为 𝑋𝑇，负部分记为 𝑋𝑇 = 𝑈𝑇 − 𝑋𝑇，与这个世界相关联的标记是 𝑋𝑇 中标记的连接和 𝑋𝑇 中标记的否定。然后在这个世界上进行聚合就涉及到在正部分 𝑋𝑇 上应用聚合器 𝑔。如果我们枚举所有世界，这本质上是指数级的。然而，我们可以通过每个聚合器和每个源数据进行优化，以实现更好的性能。例如，对 max-min-prob 标记元组进行计数可以通过一个 O(𝑛 log(𝑛)) 算法实现，比指数级快得多。图 9 展示了一个运行示例和在 max-min-prob 源数据下评估一个计数表达式的结果。得到的计数可以是 0-9，每个都可以通过多个世界推导出来。
规则和固定点迭代。在数据库 𝐹𝑇 上评估规则 𝑝 ← 𝑒 涉及评估表达式 𝑒 并将结果与 𝐹𝑇 中谓词 𝑝 下的现有事实合并。评估 𝑒 的结果可能包含由不同标记标记的重复元组，这是由于像并集、投影或聚合这样的表达式。因此，我们对集合进行规范化，以合并（⊕）不同的标记。从这里开始，有三种情况将新派生的元组（J 𝑒K (𝐹𝑇)）与之前派生的元组（J 𝑝K (𝐹𝑇)）合并。如果一个事实仅出现在旧的或新的中，我们简单地将事实传递到输出。当一个元组 𝑢 同时出现在旧的和新的中时，我们传递旧的和新的标记的析取（𝑡old ⊕ 𝑡new）。结合所有情况，我们获得了谓词 𝑝 下一组新标记的事实。
SclRam 中的递归实现类似于 Datalog 中的最小固定点迭代 [Abiteboul 等人，1995]。迭代是逐层进行的，以强制执行分层否定和聚合。评估单个层次 𝑠 的一步意味着评估 𝑠 中的所有规则并返回更新的数据库。请注意，我们定义了一个专门的最小固定点运算符 lfp◦，一旦整个数据库饱和就停止迭代。图 10 展示了涉及递归和数据库饱和的评估。整个数据库在第 7 次迭代时饱和，并找到了代表 PacMan 到达目标的最优路径的标记。由于像值创建这样的特性的存在，SclRam 中不普遍保证终止。但可以在每个源数据的基础上证明其存在。例如，很容易证明，如果一个程序在未标记语义下终止，那么它在带有 max-min-prob 源数据的标记语义下也会终止。
4.4 外部接口和执行管道
到目前为止，我们只展示了 max-min-prob 源数据，其中标记是近似概率。还有其他具有更复杂标记的概率源数据，例如证明树或布尔公式。因此，我们为每个源数据 𝑇 引入了一个输入标记空间 𝐼，一个输出标记空间 𝑂，一个标记函数 𝜏 : 𝐼 → 𝑇，以及一个恢复函数 𝜌 : 𝑇 → 𝑂。例如，所有概率源数据共享相同的输入和输出标记空间 𝐼 = 𝑂 = [0, 1] 以实现统一的接口，而内部标记空间 𝑇 可能是不同的。我们称 4-元组 (𝐼,𝑂, 𝜏, 𝜌) 为源数据 𝑇 的外部接口。然后，整个执行管道如下所示：
4.5 源数据支持的可微推理
我们现在阐明源数据如何也支持可微推理。假设 EDB 中的所有概率形成一个向量，并且结果 IDB 中的概率形成一个向量
。微分关心的是导出输出概率
以及导数
。
在 Scallop 中，可以使用可微源数据（differentiable provenance (DP)）获得这些。DPs 共享相同的外部接口——让输入标记空间 𝐼 = [0, 1] 和输出标记空间 𝑂 成为双数空间 D（图 12）。现在，每个输入标记 𝑟𝑖 ∈ [0, 1] 是一个概率，每个输出标记封装了输出概率 𝑦𝑗 及其相对于输入的导数 ∇𝑦𝑗。从这里，我们可以通过分别堆叠
来获得我们期望的输出
。
Scallop 提供了 8 种可配置的内置 DP，它们在运行时效率、推理粒度和性能方面具有不同的经验优势。在本节中，我们详细讨论了 3 种简单但多功能的 DP，它们的定义如图 11 所示。在以下讨论中，我们使用 𝑟𝑖 表示 𝑟® 的第 𝑖 个元素，其中 𝑖 被称为变量（ID）。向量是标准基向量，除第 𝑖 个条目外，所有条目都是 0。
4.5.1 diff-max-min-prob (dmmp)。这种源数据是 mmp 的可微版本。当从输入标记获取 𝑟𝑖 时，我们通过附加 ® e𝑖 作为其导数将其转换为双数。注意，在执行过程中，导数最多只有一个非零条目，具体是 1 或 -1。饱和检查仅基于概率部分的相等性，因此导数不影响终止。它的所有操作都可以通过时间复杂度为 O(1) 的算法实现，使其运行时效率极高。
4.5.2 diff-add-mult-prob (damp)。这种源数据具有与 dmmp 相同的内部标记空间、标记函数和恢复函数。正如其名称所建议的，它的析取和合取操作只是双数的 + 和 ·。执行析取时，我们限制执行 + 得到的双数的实部，同时保持导数不变。damp 的饱和函数设计为总是返回 true，以避免非终止。但这个决定使其不太适合复杂的递归程序。damp 中操作的时间复杂度是 O(n)，这比 dmmp 慢，但在实践中仍然非常高效。
4.5.3 diff-top-k-proofs (dtkp)。这种源数据将最初在 [Huang et al. 2021] 中提出的 top-k proofs 半环扩展为额外支持否定和聚合。如图 11 和 13 所示，dtkp 的标记是布尔公式 𝜑 ∈ Φ，以析取范式（DNF）表示。DNF 中的每个合取子句称为一个证明 𝜂。一个公式最多可以包含 k 个证明，其中 k 是一个可调的超参数。在执行过程中，布尔公式通过 ∨k、∧k 和 ¬k 进行传播，这些运算类似于在 DNF 公式上的或、与和非。在这些计算的最后，应用 topk 来仅保留具有最高证明概率的 k 个证明：
在执行 ∧k 合并两个证明时，可能会出现冲突的字面量，例如 pos(𝑖) 和 neg(𝑖)，在这种情况下我们会移除整个证明。对 𝜑 进行否定 ¬k 时，我们首先否定所有字面量以获得与 ¬𝜑 等价的合取范式（CNF）。然后我们执行 cnf2dnf 操作（包括冲突检查）将其转换回 DNF。要从 DNF 公式 𝜑𝑗，第 𝑗 个输出元组的标记，获得输出双数 ˆ𝑦𝑗，我们采用可微加权模型计数（WMC）过程 [Manhaeve et al. 2021]。WMC 计算给定单个变量权重的布尔公式 𝜑𝑗 的权重。具体来说，，其中
是从变量到它们双数的映射。注意，WMC 是 #P-完全的，并且是使用这种源数据时运行时的主要贡献者。可调的 𝑘 使用户能够在运行时和推理粒度之间进行平衡。附录 B 显示了详细的运行时分析。
4.6 实际考虑
我们最后讨论一些关于 SclRam 扩展和源数据选择的实际方面。
附加特性。我们只介绍了 SclRam 核心片段的语法和语义。SclRam 还支持以下有用的特性：1）采样操作，以及支持它们的源数据扩展，2）按组聚合，3）基于标记的早期移除及其在源数据中的扩展，以及 4）dtkp 中的互斥标记。我们在附录 B 中对这些进行了形式化。
源数据选择Provenance Selection.。一个自然的问题是如何为给定的 Scallop 应用程序选择一个可微源数据。根据我们在第 6 节中的实证评估，dtkp 通常是表现最好的，设置 𝑘 = 3 通常是运行时效率和学习性能的不错选择。这表明用户可以将 dtkp 作为默认选择。一般来说，源数据选择过程类似于机器学习中常见的超参数调整过程。
5 实现
我们用 Rust 语言实现了 45K 行代码的核心 Scallop 系统。各个模块的代码行数（LoC）如表 1 所示。在编译器内部，表面语言和 SclRam 语言之间有两个级别的中间表示，即前端 IR 和后端 IR。在前端 IR 中，我们执行诸如类型推断和去糖化之类的分析和转换。在后端 IR 中，我们生成查询计划并应用优化。运行时直接在 SclRam 上操作，并且是基于标记语义的半朴素求值的专业化。有动态和静态运行时来分别处理解释执行和编译执行的 SclRam 程序。
目前，所有计算仅在 CPU 上进行，但可以按批次并行化以用于机器学习。Scallop 可以通过不同的接口使用，如解释器、编译器和交互式终端。它还提供了诸如 scallopy（用于 Python）和 scallop-wasm（用于 WebAssembly 和 JavaScript）的语言绑定。通过 scallopy，Scallop 可以与 PyTorch 等机器学习框架无缝集成，其中 scallopy 模块就像任何其他 PyTorch 模块一样被对待。当在 scallopy 中指定 jit 时，Scallop 程序可以即时（JIT）编译到 Rust，转换成二进制文件，并动态加载到 Python 环境中。
Scallop 提供了 18 种内置源数据（4 种用于离散推理，6 种用于概率推理，8 种用于可微推理）。WMC 算法使用句子决策图（SDD）[Darwiche 2011] 通过朴素的自下而上编译来实现。我们允许每种源数据提供自己的实现，例如聚合和采样等操作。这提供了相当的自由度，并使得可以对复杂操作进行优化。我们的源数据框架也与 scallopy 接口，允许在 Python 中快速创建和测试新的源数据。
6 评估
我们通过包含八个神经符号应用的基准测试套件对 Scallop 语言和框架进行评估。我们的评估旨在回答以下研究问题：
RQ1 Scallop 在解决多样化的神经符号任务方面的表达能力如何？
RQ2 Scallop 的解决方案与最新基准在准确性方面的比较如何？
RQ3 Scallop 的可微推理模块是否运行高效？
RQ4 Scallop 在提高泛化能力、可解释性和数据效率方面是否有效？
RQ5 Scallop 解决方案的失败模式是什么，我们如何减轻它们？
在以下各节中，我们首先介绍基准任务和每个任务选择的基准（第 6.1 节）。然后，我们分别在第 6.2 节至第 6.6 节回答 RQ1 至 RQ5。所有与 Scallop 相关的和运行时相关的实验都是在一台配备有两个 20 核 Intel Xeon CPU、四个 GeForce RTX 2080 Ti GPU 和 768 GB RAM 的机器上进行的。
6.1 基准测试和基线
我们在图 14 中展示了我们的基准测试概览。它们涵盖了涉及感知和推理的广泛任务。输入数据模式从图像和视频到自然语言文本和知识库（KB）不等。图中还展示了训练数据集的大小。接下来，我们详细说明基准测试任务及其相应的基线。
MNIST-R：合成 MNIST 测试套件。这个基准测试旨在测试 Scallop 的各种特性，如否定和聚合。每个任务以 MNIST 数据集中的手写数字图像作为输入 [Lecun et al. 1998]，并执行简单的算术运算（sum2、sum3、sum4）、比较（less-than）、否定（not-3-or-4）或计数（count-3、count-3-or-4）操作。对于 count-3 和 count-3-or-4，我们从 8 张图像中计数数字。对于这个测试套件，我们使用基于 CNN 的模型、DeepProbLog (DPL) [Manhaeve et al. 2021] 和我们之前的工作 [Huang et al. 2021]（Prior）作为基线。
HWF：手写公式解析和评估。HWF 在 [Li et al. 2020] 中提出，涉及解析和评估手写公式。公式以图像序列的形式提供，每个图像代表一个数字（0-9）或一个算术符号（+、−、×、÷）。公式根据语法规则是良构的，并且不会出现除以零的情况。公式的大小从 1 到 7 不等，并作为输入的一部分指示。目标是评估公式以获得一个有理数作为结果。我们从 [Li et al. 2020] 中选择了基线 NGS-𝑚-BS、NGS-RL 和 NGS-MAPO，这些是专门为这项任务设计的神经符号方法。
Pathfinder：具有长距离依赖的图像分类。在这个任务中 [Tay et al. 2020]，输入是包含两个点的图像，这两个点可能通过曲线和虚线连接。目标是判断这两个点是否连接。有两个子任务，Path 和 Path-X，其中 Path 包含 32×32 的图像，Path-X 包含 128×128 的图像。我们选择了标准的 CNN 和基于 Transformer 的模型，以及最新的神经模型 S4 [Gu et al. 2021]、S4* [Gu et al. 2022] 和 SGConv [Li et al. 2022] 作为基线。
PacMan-Maze：玩 PacMan 迷宫游戏。如第 2 节所述，这个任务测试代理在图像中识别实体并为 PacMan 规划到达目标路径的能力。RL 环境提供游戏状态图像作为输入，代理必须在每一步规划最优动作 {up, down, left, right}。没有“训练数据集”，因为每个会话的环境都是随机的。我们选择了基于 CNN 的 Deep-Q-Network (DQN) 作为基线。与其他任务不同，我们使用“成功率”指标进行评估，即在 1000 个游戏会话中，我们测量 PacMan 在一定时间预算内到达目标的次数。
CLUTRR：从自然语言环境中推理亲缘关系。在这个来自 [Sinha et al. 2019] 的任务中，输入包含一段关于一组角色的自然语言（NL）文章。文章中每个句子都暗示了亲缘关系。目标是推断给定角色对之间的关系。目标关系在文章中没有明确说明，必须通过推理链来推断。我们的基线模型包括 RoBERTa [Liu et al. 2019]、BiLSTM [Graves et al. 2013]、GPT-3-FT（微调）、GPT-3-ZS（零样本）和 GPT-3-FS（5样本）[Brown et al. 2020]。在另一种设置中，CLUTRR-G，不是提供 NL 文章，而是提供与 NL 文章对应的结构化亲缘图，使其成为知识图谱推理问题。对于 CLUTRR-G，我们选择 GAT [Veličković et al. 2017] 和 CTP [Minervini et al. 2020] 作为基线。
Mugen：视频-文本对齐和检索。Mugen [Hayes et al. 2022] 基于一个名为 CoinRun [Cobbe et al. 2019] 的游戏。在视频-文本对齐任务中，输入包含一段 3.2 秒长的游戏画面视频和一段描述视频中发生事件的简短 NL 段落。目标是计算一个相似性分数，代表它们“对齐”的程度。有两个后续任务，视频到文本检索（VTR）和文本到视频检索（TVR）。在 TVR 中，输入是一段文本和一组 16 个视频，目标是检索与文本最对齐的视频。在 VTR 中，目标是从视频中检索文本。我们将我们的方法与 SDSC [Hayes et al. 2022] 进行比较。
CLEVR：组合语言和基本视觉推理 [Johnson et al. 2017]。在这个视觉问题回答（VQA）任务中，输入包含一个几何对象的渲染图像和询问对象数量、属性和关系的 NL 问题。目标是根据图像回答问题。我们选择 NS-VQA [Yi et al. 2018] 和 NSCL [Mao et al. 2019] 作为基线，这些是专门为这项任务设计的神经符号方法。
VQAR：带有常识推理的视觉问题回答。这个任务像 CLEVR 一样也涉及 VQA，但有三个显著的不同点：它包含来自 GQA 数据集 [Hudson and Manning 2019] 的真实生活图像；查询以程序化形式提出，要求检索图像中的对象；还有一个额外的输入，以常识知识库（KB）的形式 [Gao et al. 2019]，包含诸如 (giraffe, is-a, animal) 之类的三元组，用于常识推理。这项任务的基线是 NMNs [Andreas et al. 2016] 和 LXMERT [Tan and Bansal 2019]。
6.2 RQ1：我们的解决方案和表达能力
为了回答 RQ1，我们展示了 Scallop 在基准测试任务中的解决方案（表 2）。对于每个任务，我们指定了作为神经和符号组件之间桥梁的接口关系。神经模块处理感知输入，其输出被映射到接口关系中的概率事实。我们的 Scallop 程序随后将这些事实作为输入，并执行描述的推理以产生最终输出。正如特征列所示，我们的解决方案使用了 Scallop 提供的所有核心特性。
每个任务的完整 Scallop 程序都提供在附录 C 中。这些程序很简洁，如表 2 最后一列的 LoC 所示。我们突出了三个任务，HWF、Mugen 和 CLEVR，以展示 Scallop 的表达能力。对于 HWF，Scallop 程序由一个公式解析器组成。它能够根据上下文无关文法解析概率输入符号，用于简单算术表达式。对于 Mugen，Scallop 程序是一个时间规范检查器，规范从 NL 文本中提取以匹配从视频中提取的顺序事件。对于 CLEVR，Scallop 程序是 CLEVR-DSL 的解释器，这是一种在 CLEVR 数据集 [Johnson et al. 2017] 中引入的特定领域函数语言。
我们注意到，我们之前的作品 [Huang et al. 2021] 只支持正面 Datalog，由于需要否定和聚合，无法表达 8 个任务中的 5 个，如 'N' 和 'A' 列所示。此外，HWF 需要浮点支持，这也是我们之前作品中所缺乏的。除了各种类型的感知数据和推理模式外，Scallop 程序还被应用于多种学习设置。如第 2 节所示，PacMan-Maze 的程序用于在线表示学习设置。对于 CLUTRR，我们编写了完整性约束（类似于第 3.2 节中显示的），以推导用于约束语言模型输出的语义损失。对于 CLUTRR-G，可学习权重附加到诸如 composition(FATHER, MOTHER, GRANDMOTHER) 这样的组合事实上，这使得能够从数据中学习这些事实，类似于 ILP 中的规则学习。对于 Mugen，我们的程序在对比学习设置中进行训练，因为它需要最大化对齐的视频-文本对之间的相似性分数，但最小化未对齐对之间的分数。
6.3 RQ2：性能和准确性
为了回答 RQ2，我们从两个方面评估我们方法的性能和准确性：
1）我们解决方案与现有基线相比的最佳性能，以及 2）我们解决方案在不同源数据结构（dmmp、damp、不同 𝑘 的 dtkp）下的性能。
我们首先比较我们在所有基准测试任务上与选定基线的解决方案，如图 15、表 3 和图 17 所示。首先，我们突出显示两个应用，PacMan-Maze 和 CLUTRR，它们从我们的解决方案中受益最多。对于 PacMan-Maze，与 DQN 相比，我们在训练剧集方面获得了 1000 倍的加速，并且成功率接近完美的 99.4%。请注意，我们的解决方案编码了环境动态（即游戏规则），这在 DQN 模型中是不可用的，且难以结合。对于 CLUTRR，我们比基线提高了 25%，包括在 CLUTRR 数据集上微调的最新大语言模型 GPT-3-FT。接下来，对于 HWF 和 CLEVR 等任务，我们的解决方案达到了可比的性能，即使是与为每个任务特别设计的神经符号基线 NGS-𝑚-BS、NSCL 和 NS-VQA 相比。在 Path 和 Path-X 上，我们的解决方案比我们的底层模型 CNN 获得了 4% 的准确率提升，甚至超过了精心设计的基于 Transformer 的模型 S4。
每个任务的 Scallop 解决方案的性能取决于所选择的源数据结构。从表 3 和图 15-17 可以看出，尽管 dtkp 通常是表现最好的，但每种呈现的源数据都是有用的，例如，dtkp 用于 PacMan-Maze 和 VQAR，damp 用于 less-than（MNIST-R）和 Mugen，dmmp 用于 HWF 和 CLEVR。请注意，在正面 Datalog 下，Scallop 的 dtkp 与 [Huang et al. 2021] 相同，这使我们能够实现类似的性能。总之，允许配置源数据有助于将我们的方法定制到不同的应用中。
6.4 RQ3：运行时效率
我们评估了具有不同源数据结构的 Scallop 解决方案的运行时效率，并将其与基线神经符号方法进行比较。如表 4 所示，Scallop 在 MNIST-R 任务上比 DeepProbLog (DPL) 实现了显著的加速。DPL 是一个基于 Prolog 的概率编程系统，使用精确的概率推理。例如，在 sum4 任务上，DPL 需要 40 天才能完成 4K 训练样本，显示出在实践中使用它的速度极慢。相反，Scallop 解决方案可以在几分钟内完成一个训练周期（15K 样本），而不会牺牲测试准确性（根据图 15）。对于 HWF，Scallop 即使与手工精心设计的 NGS-𝑚-BS 方法相比，也实现了可比的运行时效率。在源数据结构之间进行比较时，我们看到在增加 dtkp 的 𝑘 时运行时显著增加。这是预期的，因为增加 𝑘 会导致更大的布尔公式标记，使 WMC 过程呈指数级变慢。在实践中，我们发现 dtkp 的 𝑘 = 3 是运行时效率和推理粒度之间的良好平衡点。实际上，dtkp 泛化了 DPL，因为可以将 𝑘 设置为非常大的值 𝑘 ≥ 2^𝑛（𝑛 是输入事实的总数）以进行精确的概率推理。
6.5 RQ4：泛化能力、可解释性和数据效率
现在我们考虑除了准确性和运行时之外，机器学习模型的其他重要理想方面，例如对未见输入的泛化能力、输出的可解释性以及训练过程的数据效率。为了简洁，我们每个案例只关注一个基准测试任务。
我们评估了 Scallop 在 CLUTRR 任务上的泛化能力。CLUTRR 中的每个数据点都标注了一个参数 𝑘，表示推断目标亲缘关系的推理链长度。为了测试不同解决方案的系统泛化能力，我们在 𝑘 ∈ {2, 3} 的数据点上训练它们，并在 𝑘 ∈ {2, ..., 10} 的数据点上进行测试。如图 18 所示，神经基线在更复杂的未见实例上的准确性急剧下降，而 Scallop 解决方案的准确性下降得更慢，表明它能够更好地泛化。
接下来，我们展示了 Scallop 在 Mugen 任务上的可解释性。尽管任务的目标是看视频-文本对是否对齐，但我们方法中的感知模型提取了可解释的符号，即在特定帧中受控角色的动作。图 19 显示预测的（动作，模态）对与视频中的事件完全匹配。因此，我们的解决方案不仅告诉我们视频-文本对是否对齐，还告诉我们为什么对齐。
最后，我们评估了 Scallop 在 HWF 任务上的数据效率，使用较少的训练数据（表 5）。虽然像 NGS-MAPO 这样的方法在较少数据上训练时会显著受到影响，但 Scallop 的测试准确性缓慢下降，并且与最新神经符号 NGS-𝑚-BS 方法的数据效率相当。PacMan-Maze 任务也展示了 Scallop 的数据效率，因为它所需的训练剧集比 DQN 少得多，同时实现了更高的成功率。
6.6 RQ5：失败模式分析
与纯神经模型相比，Scallop 解决方案提供了更多的透明度，允许程序员有效地调试。通过手动检查接口关系，我们观察到错误的主要来源在于神经组件的不准确预测。例如，CLUTRR 的 RoBERTa 模型正确提取的亲缘关系只有 84.69%。有两个潜在原因——要么神经组件不够强大，要么我们的解决方案没有提供足够的监督来训练它。前者可以通过使用更好的神经架构或更多的数据来解决。后者可以通过不同的方式减轻，例如调整选定的源数据或将完整性约束（第 3.2 节中讨论）纳入训练和/或推理。例如，在 PacMan-Maze 中，“竞技场中不应该有多于一个目标”的约束有助于提高鲁棒性。
7 相关工作
我们调查了四个不同但重叠的领域的相关工作：源数据推理、Datalog 和逻辑编程、概率和可微编程以及神经符号方法。
关系代数和源数据。关系代数在数据库中得到了广泛研究 [Abiteboul et al. 1995]，并在 Datalog 中通过递归进行了扩展 [Jachiet et al. 2020]。源数据半环框架 [Green et al. 2007] 最初是为正关系代数（RA+）提出的，后来扩展了差异 [Amsterdamer et al. 2011] 和固定点 [Dannert et al. 2021]。它在 Datalog 的变体中得到部署 [Khamis et al. 2021]，并支持程序合成等应用 [Si et al. 2019]。Scallop 采用了扩展的源数据半环框架，并展示了其在可配置可微推理中的应用。
Datalog 是一种声明式逻辑编程语言，其中的规则是逻辑公式。尽管它的表达能力不如 Prolog，但它在编程语言和数据库社区中因其语言扩展和优化而得到了广泛研究 [Khamis et al. 2021]。已经构建了各种基于 Datalog 的系统，用于程序分析 [Scholz et al. 2016] 和企业数据库 [Aref et al. 2015]。Scallop 也是一个基于 Datalog 的系统，它扩展了 [Huang et al. 2021]，增加了诸如否定和聚合等多种语言构造。
概率编程是程序员建模分布并执行概率抽样和推理的范式。这类系统包括 ProbLog [Dries et al. 2015]、Pyro [Bingham et al. 2018]、Turing [Ge et al. 2018] 和 PPL [van de Meent et al. 2018]。当与现代机器学习系统集成时，它们非常适合统计建模和构建生成模型。Scallop 也支持 ProbLog 风格的精确概率推理，作为我们源数据框架的一种实例。但高级统计抽样和生成建模尚未支持，留作未来的工作。
可微编程（DP）系统寻求编写可微分的代码。可微编程的常见实践包括符号微分和自动微分（auto-diff）[Baydin et al. 2015]，从而产生了流行的机器学习框架，如 PyTorch [Paszke et al. 2019]、TensorFlow [Abadi et al. 2015] 和 JAX [Bradbury et al. 2018]。然而，这些系统大多数是为实值函数设计的。Scallop 也是一个可微编程系统，但专注于使用离散的、逻辑的和关系符号的编程。
神经符号方法已经出现，将符号推理融入现有的学习系统。它们在许多应用中的成功已经得到证明 [Chen et al. 2020; Li et al. 2020; Mao et al. 2019; Minervini et al. 2020; Wang et al. 2019; Xu et al. 2022; Yi et al. 2018]。与 [Li et al. 2020; Mao et al. 2019; Yi et al. 2018] 类似，我们主要关注涉及感知后跟符号推理的解决方案。融入符号知识的其他方式包括语义损失 [Xu et al. 2018, 2022]、程序合成 [Chen et al. 2021a; Shah et al. 2020] 和调用大型语言模型（LLMs）[Cheng et al. 2022; Zelikman et al. 2023]。上述大多数神经符号方法构建了自己的领域特定语言或专门的推理组件，其中许多可以在 Scallop 中编程，并且是我们源数据框架的实例 [Chen et al. 2020; Mao et al. 2019; Xu et al. 2018, 2022]。TensorLog [Cohen et al. 2017]、DPL DeepProbLog [Manhaeve et al. 2021] 和 [Huang et al. 2021] 可以被视为不同表达能力的统一神经符号框架。Scallop 受到 DPL 的启发，并且额外提供了一个更可扩展、可定制且易于使用的语言和框架。
8 结论
我们介绍了 Scallop，这是一种用于整合深度学习和逻辑推理的神经符号编程语言。我们引入了一种基于源数据计算的声明式语言和推理框架。我们通过将其应用于各种机器学习任务，展示了我们的框架是实用的。特别是，我们的实验表明，Scallop 解决方案与许多现有基线相当，甚至超越了它们。
在未来，我们计划在以下三个方面扩展 Scallop：
1）支持更多的机器学习范式，如生成建模、开放领域推理、上下文学习以及对抗性学习。
2）进一步提高 Scallop 语言和框架的可用性、效率和表达能力。我们打算为其他 ML 框架（如 TensorFlow 和 JAX）提供绑定，利用 GPU 等硬件加速计算，并支持诸如代数数据类型等构造。
3）将 Scallop 应用于现实世界和安全关键领域。例如，我们打算将其与 CARLA 驾驶模拟器 [Dosovitskiy et al. 2017] 集成，以指定自动驾驶系统的软时间约束。
我们还打算将 Scallop 应用于医疗领域，以便从电子健康记录（EHR）数据中进行可解释的疾病诊断。
https://github.com/scallop-lang/scallop
部分附录：
