HASH GAME - Online Skill Game GET 300

　　随着符号推理与神经网络的结合被证明能够增强推理能力（Yi et al., 2018; Trinh et al., 2024）、安全性（Yang et al., 2023）、可控性（Jiao et al., 2024）和可解释性（Koh et al., 2020），对神经符号AI的兴趣持续增长。此外，神经符号方法通常通过允许更丰富和更明确的先验知识来减少数据需求（Diligenti et al., 2017; Manhaeve et al., 2018）。然而，由于许多神经符号模型的计算结构部分密集（在神经网络组件中）且部分稀疏（在符号组件中），高效学习神经符号模型仍然是一个挑战（Wan et al., 2024）。迄今为止，这些神经符号模型的符号组件尚未充分利用现代AI加速器的潜力。

　　我们的工作专注于一种由Xu et al. (2018)和Manhaeve et al. (2018)开创的神经符号AI方法，该方法对神经网络的输出进行概率推理。这是通过使用算术电路编码符号知识来实现的。虽然算术电路是端到端可微分的，但它们也带来了一些挑战。特别是，算术电路由于其高度不规则稀疏性而不适合在AI加速器（如GPU或TPU）上评估。这种稀疏性使得它们无法以密集张量操作的形式表示。在这项工作中，我们解决了优化神经符号架构以高效利用广泛可用硬件的挑战。为此，我们提出了**KLAY**：一种将算术电路表示为知识层的新数据结构，可以利用现代AI加速器中的并行计算能力。

　　神经符号AI中的符号知识通常以布尔逻辑的形式表示。布尔电路是使用有向无环图（DAG）对布尔逻辑的紧凑表示（Darwiche, 2021）。更具体地说，布尔电路中的叶节点对应于布尔变量（或其否定），而内部节点是∧-门（与门）或∨-门（或门）。我们通常假设布尔电路不包含否定，即否定范式（NNF）。图1a展示了一个布尔电路的示例。通过对图进行简单的后序遍历（即子节点在其父节点之前被评估），可以为一组输入评估电路的值。更正式地说，节点(n)的值(v(n))定义为：

　　为了使布尔电路在神经符号AI的背景下有用，我们首先需要执行所谓的知识编译步骤（Darwiche & Marquis, 2002）。这一编译步骤将NNF电路转换为确定性可分解否定范式（d-DNNF）。确定性（Darwiche, 2001b）和可分解性（Darwiche, 2001a）是两个保证某些计算可以高效执行的属性，例如找到满足条件的赋值数量。关于电路上的可处理计算的深入讨论，请参阅Vergari et al. (2021)。图1b展示了通过对图1a中的电路进行知识编译得到的d-DNNF电路。

　　这种“一次编译，多次评估”的范式在神经符号系统中也得到了广泛应用（Manhaeve et al., 2018; Ahmed et al., 2022b; De Smet et al., 2023）。这些方法背后的核心思想是将符号知识一次性编译成算术电路，并让神经网络预测输入到算术电路中的概率。由于算术电路仅由加法和乘法操作组成，生成的计算图（神经网络 + 算术电路）是端到端可微分的，并且可以使用标准的梯度下降方法优化参数。此外，由于梯度下降是一种迭代方法，电路（及其梯度）需要反复评估。这为初始昂贵的知识编译步骤提供了便利的投资回报，因为其成本可以在多次评估中分摊。

　　正如引言中讨论的那样，算术电路目前阻碍了神经符号方法的高效应用，因为这些电路不太适合现代AI加速器。事实上，在神经符号上下文中评估算术电路的标准方法是逐个节点进行朴素评估（Manhaeve et al., 2018; Ahmed et al., 2022a;b），即对算术电路进行朴素遍历。尽管这种朴素遍历允许一定程度的数据并行性，但它未能充分利用现代GPU的能力。因此，许多现有框架在实践中仅在CPU上评估整个计算图（Manhaeve et al., 2018; Ahmed et al., 2022b）。

　　通过Merkle哈希实现的高效去重不仅在合并单根电路的上下文中有用；重复节点也可能出现在单个电路中。例如，当电路是SDD（Sentential Decision Diagram）时，就可能发生这种情况。另一个重复节点的来源是第3.1节中的分层过程。具体来说，如果节点n有多个上层父节点，则通过一元节点链将节点n连接到上层节点会导致等价的链。使用Merkle哈希可以自动合并多个等价的节点链，从而限制添加新节点的开销。

　　最相关的工作是JUICE（Dang et al., 2021）中的算术电路分层。与我们的电路分层方案类似，JUICE将布尔电路映射到一组可以顺序评估的层，尽管不是逐层评估。为此，Dang et al. (2021) 为CPU实现了自定义的SIMD实现，并为GPU实现了自定义的CUDA内核。这与KLAY形成对比，在KLAY中，我们将电路评估简化为一系列索引和散射归约操作，这些操作在现代深度学习框架中已经高效实现。

　　Shah等人（2020；2021）也指出了在GPU上运行算术电路的困难。尽管Shah等人（2020；2021）专注于开发用于算术电路的硬件加速器，但他们也实现了自定义的电路评估，在一定程度上利用了SIMD指令和GPU并行化。他们发现，CPU上的电路评估优于GPU实现。Shah等人（2020）得出结论，认为算术电路过于稀疏，无法在GPU上高效运行。通过将算术电路分层并将乘积层和求和层解释为索引和散射归约操作，我们能够反驳这一观点。我们在第6节中提供了实验证据来支持这一点。

　　算术电路与概率电路（Vergari等人，2021）的模型类别密切相关。主要区别在于后者的求和单元使用混合权重进行参数化，而前者不包含此类权重。为了在GPU上高效运行概率电路，实现通常依赖于将电路评估转换为密集矩阵-向量乘积（Peharz等人，2020b；a；Galindez Olascoaga等人，2019；Mari等人，2023；Sommer等人，2021）。Liu等人（2024）最近推广了这一思想，允许在编码层的矩阵中存在块稀疏性。通过自定义内核利用这种稀疏性，他们扩大了可以在GPU上高效运行的概率电路类别。然而，概率电路通常比从逻辑理论编译的算术电路密集得多。不幸的是，这限制了为概率电路开发的技术在算术电路上下文中的有效性。同样，具有密集参数化求和节点也限制了为算术电路开发的技术（例如KLAY电路评估的索引和分段方案）在概率电路中的相关性。

　　除了算法进展外，还提出了专门的硬件解决方案来处理算术电路计算图的不规则性（Dadu等人，2019；Shah等人，2020；2021）。然而，这些方法的缺点是需要购买非商品化的硬件。虽然通过使用FPGA可以部分缓解这一问题（如Sommer等人，2018；Weber等人，2022；Choi等人，2023），但任何自定义硬件都会保留通信开销。特别是在神经符号AI的背景下，需要将神经网络的输出传递给算术电路。如果神经网络和电路位于两个不同的设备上（例如GPU和FPGA），数据传输的延迟可能会抵消评估速度的提升。

　　我们首先通过随机生成3-CNF逻辑公式来评估KLAY在一组合成电路上的性能。我们使用PySDD库将3-CNF公式编译为d-DNNF电路，更具体地说是SDD电路。通过改变CNF中变量和子句的数量，我们在5个数量级上调整编译电路的大小。图6比较了KLAY与用C实现的PySDD原生后序遍历的性能。我们报告了实数半环和对数半环的结果。由于JUICE不支持对数半环，且Jax不支持散射乘法的反向传播，因此在各自的比较中排除了这些情况。在附录B中，我们使用D4知识编译器（Lagniez & Marquis, 2017）代替PySDD重复了相同的实验。

　　接下来，我们通过测量在多个神经符号任务的电路上计算梯度的运行时间，来评估KLAY在神经符号学习中的应用。作为基线，我们考虑了PyTorch中的朴素评估，这是现有精确概率神经符号方法中常用的标准方法，其中每个节点单独评估。我们从文献中选取了四个不同的神经符号基准测试。数独基准测试是一个分类问题，确定一个4×4的图像网格是否构成有效的数独（Augustine et al., 2022）。网格（Xu et al., 2018）和魔兽争霸（Pogancič et al., 2020）实例需要预测一条有效的低成本路径。最后，分层多级分类（HMLC）涉及层次结构中标签的一致性分类（Giunchiglia & Lukasiewicz, 2020）。表1中的结果表明，与朴素基线相比，KLAY实现了显著的加速，在魔兽争霸实验中甚至提高了四个数量级。

　　作为最后一个实验，我们展示了KLAY在神经符号框架中的集成。具体来说，我们在DeepProbLog中使用KLAY代替传统的SDD电路。我们在表2中测量了MNIST加法任务的训练时间。MNIST加法是一个常见的神经符号任务，输入是两个表示为MNIST图像的数字，模型需要预测它们的和。更多细节请参考Manhaeve等人（2018）。作为参考，我们还包含了Scallop，它旨在通过使用top-k近似来改进DeepProbLog的可扩展性（Li et al., 2023）。虽然DeepProbLog和Scallop无法执行批量推理，但KLAY可以通过使用多根电路实现这一点。这反映在KLAY比现有DeepProbLog实现快两个数量级的加速上，即使在较小的电路上也是如此。尽管KLAY与Scallop不同，仍然保持精确性，但KLAY在此也展示了显著的加速效果。

　　神经网络的成功很大程度上归功于其规模（Kaplan et al., 2020），而这得益于其对硬件加速器的有效利用。为了竞争，新方法必须在现有硬件上高效运行，否则可能会因Hooker（2021）所称的“硬件彩票”而落后。我们通过引入KLAY——一种新的数据结构来表示算术电路，解决了神经符号AI中的这一问题，使其能够在现代AI加速器上高效评估。除了这种表示方法外，我们还贡献了三种用于KLAY的算法。前两种算法将算术电路的传统链接节点表示映射到相应的KLAY表示（算法2和3）。第三种算法利用并行化机会高效评估这种表示（算法1）。