🤖 AI

Neural Decision-Propagation for Answer Set Programming

本文介绍了神经决策传播（NDProp），这是一种可微方法，通过在神经决策与模糊传播之间交替迭代来高效计算稳定模型，从而克服了经典求解器在神经符号答案集编程中的可扩展性瓶颈。

原作者： Thomas Eiter, Katsumi Inoue, Sota Moriyama

发布于 2026-05-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Thomas Eiter, Katsumi Inoue, Sota Moriyama

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试解决一个庞大而复杂的逻辑谜题。你拥有一套规则（例如“如果灯是红色的，汽车必须停下”）以及一堆事实。你的目标是找到一个单一、一致的世界图景，其中每条规则都被满足且没有任何矛盾。在计算机科学领域，这被称为使用一种称为**答案集编程（ASP）**的系统来寻找“稳定模型”。

长期以来，计算机使用一种非常僵化、逐步推进的方法来解决这些谜题。它们会猜测一个事实，检查是否违反了规则；如果违反了，就必须从头开始。这就像试图通过走遍每一条路径来解迷宫，直到撞墙，然后折返并尝试下一条路径。这种方法虽然有效，但速度缓慢，且当迷宫变得巨大时很容易陷入困境。

本文介绍了一种新的解谜方法，称为DProp（决策 - 传播），随后又为其加装了一个“大脑”以使其更快，称为NDProp（神经 DProp）。

以下是其工作原理，借助一些简单的类比：

1. 旧方法与新方法（DProp）

将旧方法想象成一位一次只查看一条线索并容易陷入循环的侦探。

新方法DProp则像两名协同工作的工人：

决策者：这名工人查看尚未放置的拼图块，并说：“我猜这块拼图是假的（它不属于这里）。”他们做出大胆的猜测以推动进展。
传播者：这名工人立即检查规则。“好的，如果那块拼图被移除，那么这块其他拼图必须在这里以保持画面平衡。”他们会瞬间填补该猜测带来的所有明显后果。

他们轮流工作：决策者做出猜测，传播者填补空白。如果他们遇到矛盾（例如一条规则说"A 必须在这里”，而另一条说"A 必须在那里”），他们就知道该特定猜测是错误的。但由于他们在结构化的循环中执行此操作，因此能够比旧的“尝试一切”方法更快地找到正确解。论文证明，如果该过程在不崩溃的情况下完成，其结果就是一个数学上完美的解。

2. 添加一个“大脑”（NDProp）

第一种方法的问题在于，“决策者”仍然必须随机猜测或使用简单规则。如果谜题非常庞大，随机猜测依然缓慢。

随后，作者构建了NDProp。想象一下，给那位决策者配备一个神经网络（一种人工智能大脑），而不是一个随机猜测器。

学习启发式规则：神经网络不再盲目猜测，而是根据以往见过的模式学习哪些拼图块最可能是假的。这就像一位精通谜题的解决者，知道“哦，每当我看到蓝色的角块时，它通常位于左上角”。
模糊逻辑：该系统还允许“模糊”思考。它不再将拼图块严格定义为“真”或“假”，而是可以说“这块拼图有 70% 的可能性为真”。这有助于系统处理混乱的现实世界数据，因为在这些情境中，事物并不总是非黑即白的。
神奇之处：论文表明，尽管该系统使用模糊数学和神经网络进行学习，但如果强制最终答案为严格的“真”或“假”，它就能保证产生与僵化的传统方法完全相同的完美结果。

3. 为何这很重要（结果）

作者在三个方面测试了这种新的“神经谜题求解器”：

学习求解：他们向系统提供了随机生成的逻辑谜题。该系统学习解决这些谜题的能力远超随机猜测器。它自行掌握了求解这些谜题的“经验法则”。
混合测试（神经 - 符号）：他们将求解器与一个用于识别图像（如手写数字）的神经网络相结合。
- 任务：识别两个手写数字，将它们相加，并检查总和是否正确。
- 结果：与依赖缓慢、僵化解题器的旧系统相比，新系统快得多（在某些测试中快达 46 倍），且更准确。它能够同时学习识别数字并进行数学运算，而不是分步、缓慢地进行。
“混乱数据”测试：他们用数字模糊或图像识别器表现不佳（准确率仅为 1%）的数独谜题进行了测试。
- 结果：当输入数据不佳时，旧系统会崩溃或完全失败。新系统则利用其推理大脑表示：“尽管图片看起来像 3，但数独规则表明它必须是 5，所以我选择 5。”它能够利用逻辑来修正图像识别器的错误。

总结

本文提出了一种新工具，用智能的、基于学习的方法取代了解决逻辑谜题时缓慢、僵化的“暴力”方法。通过教导神经网络如何做出正确的猜测，并立即检查其后果，该系统能够比以往任何时候都更快、更准确地解决复杂的逻辑问题，即使输入数据不完美。它将“从数据中学习”（神经）与“遵循严格规则”（符号）之间的鸿沟弥合，融合为一个流畅、快速的过程。

技术摘要：用于答案集编程的神经决策传播

1. 问题陈述

将答案集编程（ASP）与神经网络相结合，已成为神经符号人工智能的一个有前景的方向，使系统能够结合强大的学习能力与符号推理。然而，现有方法（如 NeurASP、SLASH）通常在其推理流程中依赖经典 ASP 求解器。这种依赖性造成了显著的可扩展性瓶颈，因为符号求解器通常计算成本高昂，且难以集成到端到端可微分的训练框架中。此外，尽管某些方法试图利用概率反馈来剪枝搜索空间，但它们从根本上仍依赖于离散的、不可微分的求解机制。

本文旨在解决对可扩展、可微分方法的需求，该方法能够计算稳定模型、学习决策启发式规则，并能无缝集成到神经网络中，而无需依赖外部符号求解器。

2. 方法论

2.1 决策传播（DProp）

作者首先提出决策传播（DProp），这是一种用于计算经典 ASP 中稳定模型的新颖算法。DProp 在原子集合 $A$ 上运行，将其划分为三个不相交的集合：真（ $T$ ）、假（ $F$ ）和未决（ $U$ ）。该算法迭代执行两个交替阶段，直到终止：

决策阶段：算法非确定性地选择一个未决原子 $a \in U$ 并将其承诺为假（将其移至 $F$ ）。
传播阶段：在固定集合 $F$ 的情况下，算法使用前向链式方法推导后果。它从当前的 $T$ 开始，计算直接后果算子 $C_{P, A \setminus F}$ 的最小不动点。被推导为真的原子从 $U$ 移至 $T$ 。

当 $U$ 为空时，过程终止。如果终止时 $U = \emptyset$ 且无矛盾（ $T \cap F = \emptyset$ ），则该计算被视为成功。作者证明，任何成功的 DProp 计算都能捕捉到程序的稳定模型语义。具体而言，集合 $S$ 是稳定模型，当且仅当它是某次成功 DProp 运行的最终真集。

2.2 神经决策传播（NDProp）

为了实现学习并与神经网络集成，作者开发了NDProp，这是 DProp 的可微分扩展。

表示：NDProp 不再维护二元集合，而是为每个原子维护连续的真值度 $\tau \in [0, 1]^n$ 和假值度 $\phi \in [0, 1]^n$ 。隶属度分数 $p_i = \frac{1}{2}(\tau_i + 1 - \phi_i)$ 表示软真值。
可微分决策：“决策”阶段通过循环神经网络（RNN）决策模块实现。RNN 接收当前状态（ $\tau, \phi$ 和未决度 $\mu$ ）并输出决策 logits，这些 logits 通过 Sigmoid 函数转换为分数 $\delta$ 。假值度进行加法更新： $\phi^{t+1} = \phi^t + (\mu^t \odot \delta^t)$ 。这使得网络能够学习哪些原子应被设为假。
可微分传播：“传播”阶段使用模糊逻辑算子（t-范数和 t-余范数）来更新真值度 $\tau$ 。它迭代软直接后果算子 $C_{P, \phi}$ 直到收敛（或达到固定步数）。
清晰恢复：作者证明，当输入和输出被约束为二元值（0 或 1）时，NDProp 与离散的 DProp 算法完全一致。
稳定性强制：本文表明，通过损失函数（例如二元交叉熵）强制输出为二元值，在传播达到不动点的前提下，会内在迫使系统收敛到稳定模型。这允许无监督训练，即模型无需答案集的显式标签即可学习寻找稳定模型。

3. 主要贡献

DProp 算法：提出了一种基于交替假值决策和真值传播来计算稳定模型的新方法，并形式化证明了成功的运行能够捕捉稳定模型语义。
NDProp 框架：开发了一个完全可微分的扩展（NDProp），利用神经网络进行决策，利用模糊逻辑进行传播。已证明其在清晰情况下与 DProp 一致。
学习动态：证明了 NDProp 能够学习决策启发式规则以解决随机 ASP 问题，而无需依赖外部求解器。
神经符号集成：成功将 NDProp 集成到神经符号流程中，表明感知和推理的端到端训练相比基于求解器的基线方法，能产生更高的准确性和可扩展性。

4. 实验结果

作者进行了三类实验：

随机 ASP 求解：使用随机负双文字（N2L）和 3-LP 程序，训练 NDProp 学习决策动态。结果表明，即使在单样本（1-shot）设置下，NDProp 也显著优于随机决策基线（RDProp），并且能很好地泛化到更大的问题规模。
神经符号基准测试：在基于 MNIST 的算术任务（加法、Add2x2、Apply2x2、成员资格）上进行了评估。将 NDProp 与 NeurASP 和 SLASH 进行了比较。
- 准确性：NDProp 在所有任务中均实现了更高的识别和推理准确率。
- 速度：由于 GPU 并行化以及消除了符号求解器调用，NDProp 表现出显著更快的推理速度（平均比 NeurASP 快 46 倍，比 SLASH 快 7.5 倍）。
不完整数据下的推理：在具有不完美数字分类器预测的视觉数独任务中，NDProp 的表现优于纯神经基线和标准 ASP 求解器。当预测存在噪声（1% 数据）时，ASP 求解器严重失败，而 NDProp 通过将噪声预测用作引导搜索兼容解的启发式规则，保持了鲁棒性。

5. 意义与主张

本文声称 NDProp 提供了一种基于新颖不动点语义的完全可微分答案集求解器。其主要意义在于：

可扩展性：通过消除对经典符号求解器的依赖，NDProp 实现了更高的推理速度，并能更好地扩展到更大的问题。
端到端学习：它允许感知（神经网络）和推理（逻辑）的联合优化，从而在神经符号系统中产生更连贯、更一致的输出。
理论可靠性：该方法保持与经典稳定模型语义的清晰联系，确保二元输出对应于有效的稳定模型。

作者总结道，尽管 t-范数的选择以及向模糊变体或复杂构造（约束、聚合）的扩展仍是未来的工作，但 NDProp 代表了在神经架构中使 ASP 推理可扩展且可学习的重要一步。