EM-NeSy: Expectation Maximization for Neurosymbolic Learning¶

会议: NeurIPS 2026
arXiv: 2606.14463
领域: 学习理论
关键词: 神经符号学习, 期望最大化, 概率推断, 近似推断, 隐变量模型

一句话总结¶

将概率神经符号学习形式化为期望最大化（EM）算法，E 步利用任意精确或近似符号推断引擎反推神经预测的后验分布，M 步仅在神经网络内进行梯度下降更新，彻底解耦符号推理与端到端微分需求并在精确推断下数学等价于传统梯度反传。

研究背景与动机¶

神经符号（Neurosymbolic, NeSy）学习致力于将神经网络的感知表征优势与符号逻辑的结构化推理能力深度融合。在“神经 + 逻辑 + 概率”的主流范式中，概率语义构成了连接连续感知与离散知识的天然桥梁：神经网络输出对离散隐变量的先验置信度，而符号组件则在此基础上进行概率推断以对齐高阶逻辑约束。现有端到端可微神经符号框架（如 DeepStochLog、Semantic Loss、Scallop 等）通常依赖知识编译将逻辑规则固化为算术电路，或者直接穿透整个推理过程反向传播梯度。

然而，概率推断本质上是 #P 难的组合爆炸问题。当面对稍微复杂的实际问题时，精确推断或知识编译往往因内存或时间超限而不可行，训练时只能转向近似推断。但在近似推断场景下，端到端梯度的求导遇到了巨大阻碍：采样方法天然不可导，必须依赖方差巨大的 REINFORCE 或复杂的重参数化技巧；而置信度传播（BP）或对偶分解等迭代优化算法虽然理论可导，但在数十轮迭代的消息传递图中穿透反传会导致极高的显存开销与梯度检查点（gradient checkpointing）时间损耗。这种“强求符号组件具备可微性”的范式，极大地限制了 NeSy 系统集成业界成熟黑盒推理求解器（如 SAT 求解器、图算法、采样工具）的能力。

本文的切入角度是打破“自顶向下端到端求导”的固有思维，重新审视隐变量生成视角。既然标签是通过离散符号规则从神经感知输出中生成的，那么神经符号系统在数学上就是一个标准的条件隐变量模型（Latent Variable Model）。核心 idea：将概率神经符号学习重构为期望最大化（EM）算法，E 步利用任意黑盒符号推理引擎计算神经隐变量在标签约束下的后验分布，M 步仅对神经感知网络进行交叉熵梯度更新，在免除符号推断求导需求的同时保持与端到端微积分相同的学习信号。

方法详解¶

整体框架¶

EM-NeSy 将神经符号预测任务视作由输入 $X$ 经由潜在符号变量 $Z$ 预测目标标签 $Y$ 的条件概率隐变量模型。在整个学习循环中，符号推理引擎不再充当求导计算图的一部分，而是退居为一个纯粹的“概率纠错器”（probabilistic corrector）和“标签外展器”（abductive labeler）。

整体流程分为交替进行的两个核心阶段：在 E 步（期望步）中，先由神经网络根据感知输入给出隐符号变量的条件先验预测，再由符号推理引擎结合观测标签与先验计算条件后验分布 $\ell(Z) = p(Z \mid Y, X, \theta)$；在 M 步（最大化步）中，将该后验视为监督目标常数，通过最小化神经预测分布与后验分布之间的交叉熵损失，仅在神经网络参数 $\theta$ 上执行标准的反向传播与参数更新。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入样本 (X, Y) 与知识背景"] --> Prior["神经先验预测<br/>网络输出隐变量分布 pNe(Z|X, θ)"]
    Prior --> EStep["符号后验推断 (E 步)<br/>符号引擎反推后验 ℓ(Z) = p(Z|Y, X, θ)"]
    EStep --> Loss["潜在变量级损失构建<br/>交叉熵 L_EM-NeSy = -∑ ℓ(Z) log pNe(Z|X, θ)"]
    Loss --> MStep["纯神经参数更新 (M 步)<br/>仅在神经网络内反传梯度 ∇θ L_EM-NeSy"]
    MStep -->|参数迭代 θ(t+1)| Prior

关键设计¶

1. 符号纠错 E 步与梯度精确等价性：彻底剥离符号推断的微分负担
传统 NeSy 训练通常在目标变量 $Y$ 层面定义负对数似然损失 $\mathcal{L}(\theta) = -\log \sum_{z \in R(Z)} p_{\text{Ne}}(z \mid x, \theta) p_{\text{Sy}}(y \mid z)$，并尝试将梯度直接穿透整个符号推理过程，导致推理必须保留计算图或设计专门的可微松弛。EM-NeSy 将符号推理从损失函数内部抽离出来，定义为 E 步的后验归纳过程： $$p(z \mid y, x, \theta) = \frac{p_{\text{Ne}}(z \mid x, \theta) p_{\text{Sy}}(y \mid z)}{p(y \mid x, \theta)} = \ell(z)$$ 在 M 步中，系统仅需在隐变量层面最小化神经先验与后验之间的交叉熵： $$\mathcal{L}_{\text{EM-NeSy}}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{\text{Ne}}(z \mid x, \theta)$$ 论文从数学上严格证明了 定理 3.1（Theorem 3.1）：在精确推断条件下，EM-NeSy 在神经网络参数 $\theta$ 上诱导的梯度与端到端标准 NeSy 负对数似然损失的梯度完全相等，即 $\nabla_\theta \mathcal{L}(\theta) = \nabla_\theta \mathcal{L}_{\text{EM-NeSy}}(\theta)$。这意味着微分算符在对数链式法则作用下，天然等于后验加权的得分函数期望。EM-NeSy 并非对原目标的启发式近似，而是原生等价重写；但它带来质的突破：E 步推断可以使用任意非可微、离散或优化的外部算法，推理过程中的临时变量与消息传递图用完即丢，无需维持庞大的反向传播图。

2. 任意推断引擎即插即用：覆盖采样、置信度传播与 MAP 硬分配
由于 M 步仅需要后验边际概率数值而不需要导数，EM-NeSy 可以直接容纳各种近似推理方案。对于树状结构因子图，直接运行和积置信度传播（Sum-Product Belief Propagation）即可获得精确边际；对于环状因子图（如数独规则），可直接运行 Loopy BP 并结合阻尼系数更新消息。对于极其庞大且包含硬性约束的采样空间（如确定性约束导致似然极度稀疏、标准拒绝采样和 REINFORCE 极易权重归零崩溃的问题），EM-NeSy 引入了近似贝叶斯计算（ABC 采样）：将约束分解为集合 $M$，通过局部满足度统计量 $s_{Z_i}(z_i) = \frac{k}{|M_i|}$ 与距离度量构造非退化的软差异度权重 $\frac{k}{C |M_i|}$，避免了采样权重完全坍塌为零。此外，在 E 步中若直接取 MAP 赋值 $\ell(z) = \mathbb{I}(z = \arg\max_{z'} p(z' \mid y, x, \theta))$，EM-NeSy 还可以直接无缝退化为 Hard EM 模式。

3. 随机在线更新与 Multi-M 梯度加速策略
在实际训练中，为匹配大规模深度学习训练，EM-NeSy 采用了在线 EM（Online EM）的微批次迭代机制，单个样本或 mini-batch 计算出的后验即刻用于引导局部梯度步长更新。针对符号推理代价显著高于单步反向传播的场景，算法进一步提出了 Multi-M EM 策略：在同一个 E 步计算出后验 $\ell(z)$ 之后，冻结该后验常数，对当前的神经预测与该后验连续执行 $m$ 次小步长的神经网络梯度反传与权重更新。这种策略在不触发重复高耗时符号推断的前提下充分榨取了后验监督信号，相比单纯调大单步学习率，既显著加快了收敛速度，又有效规避了因步长过大导致的优化震荡。

损失函数 / 训练策略¶

在具体的实现中，神经参数 $\theta$ 的更新采用 Adam 优化器，学习率采用 Cosine Annealing 调度策略。以 Multi-Digit MNISTAdd 为例，学习率从 $10^{-3}$ 退火至 $10^{-4}$，批大小随数字长度增加进行动态收缩；而在 Warcraft 路径规划任务中引入了参数为 $0.03$ 的熵正则化项以鼓励神经先验的探索度。整体训练每轮仅反传神经网络（如 LeNet 或 ResNet-18 特征提取层），无需保留符号求解器的任何前向缓存。

实验关键数据¶

主实验¶

论文在三个涵盖视觉感知与不同复杂度组合推理的基准上进行了验证：包含长程进位链的 Multi-Digit MNISTAdd、具有高阶确定性互斥约束的 Visual Sudoku，以及属于组合图搜索问题的 Warcraft 路径规划。

在 MNISTAdd 上，对比了 EM-NeSy（基于和积置信度传播 BP-EM）、端到端可微基线（BP-std、DeepStochLog DSL、A-NeSI、EXAL）：

任务规模 (MNISTAdd)	指标	BP-EM (本文)	BP-std (端到端可微)	DSL (知识编译)	EXAL
4 字符加法	准确率 (%)	92.53 ± 0.62	92.16 ± 0.23	92.70 ± 0.60	90.71 ± 1.01
4 字符加法	训练耗时 (min)	1.33	2.21	–	4.17
15 字符加法	准确率 (%)	74.85 ± 1.83	72.79 ± 1.62	超时 (T/O)	62.62 ± 4.24
15 字符加法	训练耗时 (min)	1.95	7.93	超时 (T/O)	42.44
100 字符加法	准确率 (%)	9.20 ± 9.76	11.60 ± 3.85	超时 (T/O)	6.67 ± 7.83
100 字符加法	训练耗时 (min)	8.51	36.26	超时 (T/O)	372.20

在 Visual Sudoku 与 Warcraft 路径规划基准上的表现如下：

数据集	任务规模	指标	本文方案 (BP-EM / ABC-EM)	最佳竞品 (A-NeSI / I-MLE / Scallop)	表现差异分析
Visual Sudoku	4×4 网格	准确率 (%)	89.70 ± 3.05 (BP-EM)	87.80 ± 2.05 (BP-std) / 87.20 (A-NeSI)	优于可微基线，训练耗时减少 44% (21.23m vs 38.23m)
Visual Sudoku	9×9 网格	准确率 (%)	53.30 ± 3.15 (ABC-EM)	59.20 ± 2.06 (A-NeSI)	DSL/Scallop 超时；ABC-EM 耗时仅 8.24m (A-NeSI 需 73.33m)
Warcraft	12×12 网格	最短路径准确率 (%)	98.80 ± 0.41 (ABC-EM)	98.96 ± 1.33 (A-NeSI) / 95.34 (I-MLE)	耗时仅 7.26m，比 A-NeSI (439m) 快 60 倍，比 I-MLE 快 3.6 倍
Warcraft	30×30 网格	最短路径准确率 (%)	69.60 ± 35.64 (ABC-EM)	93.40 ± 0.64 (I-MLE)	耗时仅 8.37m (I-MLE 需 227.8m)；但采样方差导致均值偏低

消融实验¶

论文在 MNISTAdd 基准上对不同推断变体（精确 E 步 vs MAP 硬分配 E 步）以及显存消耗进行了详尽的对比与消融分析：

推断变体 / 配置	4 位准确率 (%)	15 位准确率 (%)	100 位准确率 (%)	100 位显存占用 (Peak RAM)	说明
BP-EM (软后验 E 步，本文)	92.53 ± 0.62	74.85 ± 1.83	9.20 ± 9.76	35.52 GB	理论等价，免除计算图反传，显存减半且速度提升 4 倍
BP-std (端到端可微反传)	92.16 ± 0.23	72.79 ± 1.62	11.60 ± 3.85	90.61 GB	需在 BP 消息传递迭代中维护前向状态与梯度，显存巨大
BP-EM-M (Hard MAP E 步)	33.44 ± 33.49	30.36 ± 40.09	0.00 ± 0.00	35.52 GB	MAP 离散决策导致高偏差，极易过早收敛至局部极值

关键发现¶

显存与计算开销急剧降低：在 100 位加法实验中，由于避免了穿透循环推断迭代的消息图求导，EM-NeSy 将峰值显存从 90.61 GB 压缩至 35.52 GB，训练时间从 36.26 分钟减少至 8.51 分钟，同时保持了与端到端微分相当的预测准确度。
知识编译扩展性天花板被击穿：基于算术电路编译的经典模型（DeepStochLog、Semantic Loss、Semantic Probabilistic Layers）在 15 位加法与 9×9 数独上全部触发编译超时（T/O），而 EM-NeSy 结合近似求解器可以平滑扩展至极端组合规模。
后验逼近质量决定下限：Hard EM（BP-EM-M）在多字符加法上出现严重性能衰退（从 92% 骤降至 33%），证明在弱监督感知中保留软概率分布以维持不确定性是避免局部最优的关键。此外，Loopy BP 在高度密集的 9×9 数独环状图上失效，而 ABC 采样在小网格上极速且精准，但大尺寸网格上存在较大方差。

亮点与洞察¶

理论统一与优雅等价：从数学本质上揭示了“神经符号端到端求导”与“隐变量后验期望最大化”的内在一致性。求导链式法则中隐变量的梯度天然等价于后验加权的得分函数，彻底打消了研究界对“非微分训练是否会损失学习信号”的疑虑。
推理与优化的彻底解耦：将神经符号学习的工程栈清晰切分为两半——感知端专注于标准 PyTorch 神经网络梯度反传，符号端可以自由调用非可微的 C++ 求解器、Dijkstra 算法或特定启发式采样，极大拓宽了符号推理的选型空间。
Multi-M 解决“符号慢、神经快”的计算失衡：在图推理或复杂逻辑求解远慢于前向反传时，冻结后验并执行多步神经参数小更新，为神经符号系统提供了一种优雅且稳定的算力平衡杠杆。

局限与展望¶

作者承认的局限：框架虽然移除了可微性限制，但将性能瓶颈转移到了“如何为具体任务选取高质量的近似推理算法”上；超参数配置（如阻尼系数、采样数、距离度量）对特定任务较为敏感。
潜在隐患与缺陷：在大规模组合空间（如 30×30 Warcraft 或 9×9 数独）中，当推断引擎噪声较大（如采样覆盖度不足或环状 BP 震荡）时，E 步提供的后验伪标签会出现显著偏差，导致跨随机种子的训练方差增大甚至陷入训练崩溃。
未来方向：探索具备自适应容错能力的鲁棒 E 步推断策略，或者利用强化学习 / 神经引导采样（Neural MCMC）在训练过程中协同提升后验采样的质量。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从严格的期望最大化（EM）视角统一概率神经符号学习，证明了精确推理下与端到端微分的等价性，从根本上解除了可微性束缚。
实验充分度: ⭐⭐⭐⭐☆ 覆盖加法、数独与路径规划三大经典 NeSy 基准，从精确推断、置信度传播到 ABC 采样进行了细致评测；若在大规模图推理或更复杂视觉推理上有更广验证则更佳。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密精炼，定理阐释清晰，问题定位与背景切入极其敏锐。
价值: ⭐⭐⭐⭐⭐ 为解决神经符号系统中“符号推理 #P 难与端到端求导冲突”这一核心难题提供了极具通用性的全新基础范式。