Research map / Optimization / Optimizers
EM-NeSy: Expectation Maximization for Neurosymbolic Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Casts probabilistic neurosymbolic learning as EM: the symbolic component computes posteriors over neural outputs given the label (E-step, any inference engine), and the neural network is updated by cross-entropy to those posteriors (M-step), matching end-to-end gradients under exact inference.
Problem
Standard probabilistic NeSy learning requires the symbolic component to be differentiable and backpropagates through inference, which is costly or impossible for approximate, sampling-based, or iterative inference methods.
Approach
Recast NeSy learning as EM: compute the posterior over neurally predicted latent symbols given the label with any (exact or approximate) inference engine, then train the neural component by cross-entropy against that posterior with gradients only through the neural net; under exact inference the gradients equal those of standard NeSy loss.
Key results
- On MNISTAdd with 100 digits, BP-EM reaches 9.20% accuracy in 8.51 min versus BP-std's 11.60% in 36.26 min, while peak memory drops from 90.61 GB to 35.52 GB; accuracies at 4 digits are nearly identical (92.53 vs 92.16).
- ABC-EM reaches 98.80% on Warcraft 12x12 in 7.26 min, comparable to A-NeSI (98.96%) but far faster (439.10 min).
- On Visual Sudoku 4x4, BP-EM reaches 89.70% accuracy, but BP-EM fails on 9x9 (0.50%) due to loopy graphs; ABC-EM gets 53.30% on 9x9.
Surprising findings
- Hard EM (max-product BP, BP-EM-M) often converges to poor local optima on MNISTAdd (e.g., 0.00% at 100 digits).
- ABC-EM's 30x30 Warcraft and 15-digit MNISTAdd results show very high variance across seeds.
Limitations
- Does not address how to select effective approximate inference methods; results depend on task-specific hyperparameter tuning.
- Performance depends strongly on the quality of the approximate posterior; loopy BP fails on 9x9 Sudoku and high variance for ABC on larger instances.
- Some baseline numbers taken from original papers on different machines.
Experimental setup
Datasets: MNISTAdd MNIST Visual Sudoku Warcraft path-planning
Benchmarks: MNISTAdd Visual Sudoku Warcraft path-planning
Metrics: accuracy training time peak memory
Baselines: A-NeSI I-MLE EXAL Scallop DeepStochLog Semantic Loss SPL BP-std
Builds on: Expectation-Maximization Relational Neural Machines I-MLE Approximate Bayesian Computation DeepStochLog
Closest papers by meaning
- Relational Neurosymbolic Markov Models (AAAI 2025 · similarity 0.88)
- On the Hardness of Probabilistic Neurosymbolic Learning (ICML 2024 · similarity 0.87)
- Neurosymbolic Diffusion Models (NeurIPS 2025 · similarity 0.86)
- On the Independence Assumption in Neurosymbolic Learning (ICML 2024 · similarity 0.86)
- Convex and Bilevel Optimization for Neural-Symbolic Inference and Learning (ICML 2024 · similarity 0.85)
- From Statistical Relational to Neuro-Symbolic Artificial Intelligence (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.