🤖 machine learning

EM-NeSy: Expectation Maximization for Neurosymbolic Learning

This paper introduces EM-NeSy, a novel neurosymbolic learning framework that leverages the Expectation-Maximization algorithm to enable scalable and efficient training without requiring the symbolic component to be differentiable, thereby supporting both exact and approximate reasoning.

Original authors: Annegret Seibt, Luc De Raedt, Giuseppe Marra

Published 2026-06-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Annegret Seibt, Luc De Raedt, Giuseppe Marra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Teaching a Robot to Think and Reason

Imagine you are trying to teach a robot two things at once:

Perception: How to look at a blurry photo and guess what the objects are (like recognizing a handwritten number). This is done by a Neural Network (the "Neural" part).
Reasoning: How to check if those objects make sense together according to a set of rules (like checking if a Sudoku puzzle is valid). This is done by Symbolic Logic (the "Symbolic" part).

Current methods try to teach these two parts simultaneously by connecting them with a "wire" that allows the robot to learn from its mistakes. However, this wire has a problem: if the logic part is too complex or uses a method that doesn't play nice with math (like random sampling), the "wire" breaks. The robot can't learn because it can't calculate the exact direction to fix its mistakes.

EM-NESY is a new way of teaching the robot that removes this "wire" entirely. Instead of forcing the two parts to talk to each other constantly during the learning process, it lets them take turns.

The Analogy: The Art Critic and the Apprentice

To understand how EM-NESY works, imagine an Apprentice Artist (the Neural Network) and a Strict Art Critic (the Symbolic Logic).

The Old Way (End-to-End Learning)

In the old method, the Apprentice paints a picture, and the Critic immediately yells, "That's wrong!" The Critic then tries to explain exactly which brushstroke was wrong and how to fix it.

The Problem: If the Critic's rules are too complicated (like a complex Sudoku puzzle) or if the Critic uses a method that is hard to explain step-by-step (like guessing randomly), the Critic gets stuck. They can't give specific instructions on how to fix the brushstrokes. The Apprentice is left confused and can't improve.

The New Way (EM-NESY)

EM-NESY changes the workflow into two distinct steps, like a rehearsal process:

Step 1: The Critic's Review (The "Expectation" Step)
The Apprentice paints a picture based on their current skill. The Critic looks at the picture and the correct answer (the label).
Instead of trying to explain how to fix the brushstrokes, the Critic simply writes down a list of corrections.

Example: "You thought this digit was a 3, but given the rules of Sudoku, it is actually 70% likely to be a 5 and 30% likely to be a 6."
Key Point: The Critic does this using any method they want. They can use complex math, random guessing, or strict logic. It doesn't matter if they can explain their reasoning step-by-step; they just need to produce the final list of probabilities (the "posterior").

Step 2: The Apprentice's Practice (The "Maximization" Step)
The Critic hands the list of corrections to the Apprentice. The Apprentice looks at their original guess and the Critic's corrections.

The Apprentice thinks: "I guessed 3. The Critic says I should have guessed 5 or 6. I need to adjust my brain to make 5 or 6 more likely next time."
The Apprentice updates their own internal settings (the neural parameters) to match the Critic's list.
Key Point: The Critic is not involved in this step. The Critic's list is treated as a fixed fact. The Apprentice only needs to learn how to change their own painting style.

Why is this a Big Deal?

1. It Unlocks "Unlearnable" Logic
Some logic problems are so hard that you can't calculate the exact answer, or the method to find the answer is "non-differentiable" (mathematically messy).

Analogy: Imagine the Critic uses a method where they roll dice to find the answer. In the old way, you couldn't teach the Apprentice because you couldn't trace the dice roll back to the brushstrokes.
With EM-NESY: The Critic rolls the dice, gets a result, and writes it down. The Apprentice just learns from the result. The messy dice-rolling part is completely hidden from the learning process.

2. It's Faster and Uses Less Memory
The paper shows that when the logic is simple enough to be calculated exactly, this new method is just as accurate as the old method but much faster.

Analogy: It's like realizing you don't need to re-calculate the entire history of the universe every time you make a mistake. You just need the final verdict. This saves a massive amount of computer memory and time, allowing the robot to solve much larger puzzles (like Sudoku grids with 100 digits) that would crash the old systems.

3. It Works with Any "Critic"
Because the Critic doesn't need to be mathematically "smooth" or differentiable, you can plug in any existing logic engine, even the ones that were previously too difficult to use with neural networks.

What the Experiments Showed

The authors tested this on three types of puzzles:

Adding handwritten numbers: They showed EM-NESY could handle huge sums (100 digits) that other methods couldn't even finish, while using less memory.
Visual Sudoku: They showed it could learn from puzzles where the rules were strict, even when using approximate methods (like random sampling) to solve the logic part.
Pathfinding on a map: They showed it could learn to find the shortest path on a grid, a task where other methods struggled because the logic was too complex to differentiate.

The Bottom Line

The paper proposes EM-NESY, a framework that treats Neurosymbolic learning as a game of "Hot and Cold" played in turns.

Turn 1: The Logic engine (Critic) figures out what the correct answers should have been, using whatever tools it has.
Turn 2: The Neural engine (Apprentice) adjusts its brain to match those answers.

This simple switch allows AI to learn from complex, messy, or approximate logic without needing to force the logic to be mathematically perfect or differentiable. It makes building AI that can both "see" and "think" much more flexible and scalable.

Technical Summary: EM-NESY: Expectation Maximization for Neurosymbolic Learning

Problem Statement

Neurosymbolic (NeSy) models aim to integrate the perceptual strengths of neural networks with the reasoning capabilities of symbolic logic. While state-of-the-art NeSy models typically achieve end-to-end training by backpropagating gradients through both neural and symbolic components, this approach faces significant challenges when the symbolic component relies on approximate inference.

Exact probabilistic inference is often #P-hard and computationally intractable for complex tasks. Consequently, many systems resort to approximate inference methods (e.g., sampling, belief propagation, or linear-programming relaxations). However, these methods introduce differentiability issues:

Non-differentiability: Techniques like sampling are inherently non-differentiable, requiring specialized gradient estimators (e.g., REINFORCE) or reparameterization tricks.
Computational Overhead: Even theoretically differentiable iterative methods (e.g., belief propagation) become impractical to differentiate through in practice due to the massive computational graph required to backpropagate through all iterations.

Current solutions often require inference-specific modifications to ensure differentiability, limiting the flexibility and scalability of NeSy systems.

Methodology: EM-NeSy

The authors propose EM-NeSy, a learning framework that casts probabilistic NeSy learning as an instance of the Expectation-Maximization (EM) algorithm. This formulation decouples the symbolic inference process from the gradient computation, allowing the use of any inference engine (exact or approximate, differentiable or not).

The Framework

The NeSy model is treated as a latent variable model where:

$X$ : Subsymbolic input (e.g., images).
$Z$ : Latent symbolic variables (neurally predicted).
$Y$ : Target symbolic output (e.g., validity of a Sudoku grid).
$\theta$ : Neural network parameters.

The learning process alternates between two steps:

E-Step (Expectation):
The symbolic component computes the posterior distribution of the latent variables $Z$ conditioned on the observed label $Y$ and input $X$ :
$p(z|y, x, \theta) = \frac{p_{Ne}(z|x, \theta)p_{Sy}(y|z)}{p(y|x, \theta)}$
Here, $p_{Ne}$ is the neural prior and $p_{Sy}$ is the symbolic likelihood. Crucially, this step acts as a "probabilistic corrector," abducing soft or hard labels for $Z$ based on background knowledge. This step can be performed by any symbolic inference engine (exact, approximate, sampling-based) without requiring differentiability.
M-Step (Maximization):
The neural parameters $\theta$ are updated by minimizing the cross-entropy between the neural prior $p_{Ne}(z|x, \theta)$ and the posterior $\ell(z)$ computed in the E-step:
$L_{EM-NeSy}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{Ne}(z|x, \theta)$
Gradients are backpropagated only through the neural component, treating the posterior $\ell(z)$ as a constant. This eliminates the need to differentiate through the symbolic inference process.

Theoretical Equivalence

The paper proves that under exact inference, the gradients computed by EM-NeSy are mathematically equivalent to those of standard end-to-end differentiable NeSy learning (Theorem 3.1). Thus, EM-NeSy recovers the standard setting when exact inference is feasible but offers a distinct advantage when it is not.

Variants and Extensions

Hard EM: Uses Maximum A Posteriori (MAP) assignments instead of soft posteriors.
Multi-M EM: Performs multiple M-steps (gradient updates) for a single E-step to accelerate convergence without re-computing the expensive posterior.
Approximate Inference: The framework naturally supports sampling-based methods (e.g., Rejection Sampling, ABC Sampling) and iterative algorithms (e.g., Belief Propagation) without modification.

Key Contributions

Reformulation of NeSy Learning: The authors recast NeSy learning within the EM framework, enabling the use of advanced EM variants (Generalized EM, Stochastic EM, Hard EM) for improved flexibility.
Differentiability-Free Integration: A general framework is proposed that integrates any probabilistic inference engine into a NeSy model without requiring the symbolic inference process to be differentiable.
Scalability and Efficiency: The approach demonstrates that NeSy learning can scale to tasks where exact inference is intractable or where differentiating through iterative solvers is computationally prohibitive.

Experimental Results

The authors evaluated EM-NeSy on three benchmarks: MNISTAdd (addition of handwritten digits), Visual Sudoku, and Warcraft path-planning.

Exact Inference (MNISTAdd): EM-NeSy achieved accuracy comparable to standard end-to-end differentiable NeSy (BP-std) and DeepStochLog. However, it significantly outperformed them in scalability and efficiency. While DeepStochLog failed to scale to 15 digits due to knowledge compilation limits, EM-NeSy scaled to 100 digits. It also reduced peak memory usage from ~90 GB to ~35 GB and reduced training time.
Approximate/Non-Differentiable Inference:
- Visual Sudoku: Standard differentiable methods (Scallop, SL) timed out on 9x9 grids. EM-NeSy using Approximate Bayesian Computation (ABC) sampling achieved competitive accuracy (53.3%) with minimal training time (8.24 min), whereas other methods were inapplicable.
- Warcraft Path-Planning: EM-NeSy with ABC sampling achieved state-of-the-art accuracy (98.80% on 12x12, 69.60% on 30x30) with significantly faster training times compared to I-MLE and EXAL.
Limitations Observed: The performance of EM-NeSy depends on the quality of the approximate posterior. Hard EM (MAP) showed bias on MNISTAdd, and loopy belief propagation failed on 9x9 Sudoku due to the factor graph structure. ABC sampling showed high variance on larger instances but remained effective in smaller settings.

Significance and Claims

The paper claims that EM-NeSy provides a unified learning framework that substantially simplifies model design by eliminating the need for inference-specific differentiability modifications. By treating NeSy learning as an EM problem, the approach:

Allows the use of any symbolic inference engine, including specialized, optimized, or non-differentiable solvers.
Recovers standard end-to-end learning under exact inference while offering superior computational efficiency and memory scalability.
Enables NeSy systems to tackle tasks involving complex, combinatorial constraints (like path planning or Sudoku) where exact inference is infeasible and differentiable approximations are difficult to construct.

The authors conclude that while EM-NeSy does not solve the problem of selecting effective approximations (which remains task-dependent), it removes the barrier of differentiability, thereby enabling more scalable and flexible Neurosymbolic systems.