Research map / Probabilistic and scientific modeling / Variational and generative sampling
A Neural Network Approach for Efficiently Answering Most Probable Explanation Queries in Probabilistic Models
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.
Distills any-MPE queries over probabilistic models (PCs, BNs/MNs, NAMs) into a neural network trained with a self-supervised loss, refined at inference by ITSELF and warm-started by a teacher-student GUIDE procedure.
Problem
Answering arbitrary most probable explanation (MPE) queries, where no fixed evidence/query partition is known in advance, in large probabilistic models is NP-hard and existing exact or approximate solvers are slow or inaccurate.
Approach
Encode any MPE query with 2n input nodes (evidence value plus evidence-indicator per variable), train one NN with a differentiable self-supervised loss (multilinear or NN relaxation plus an entropy penalty), refine each test query by gradient steps (ITSELF), and warm-start the NN with a teacher-student scheme (GUIDE) that distills teacher MPE pseudo-labels into a student.
Key results
- On PCs, GUIDE+ITSELF beats MAX in almost two-thirds of 120 test cases (contingency table), and it outperforms MAX on larger query sets across most datasets.
- On NAMs, GUIDE+ITSELF outperforms the hill-climbing baseline by over 50% in most large datasets.
- GUIDE outperforms SSMP in more than 60% of PC scenarios with single-pass inference and in more than 80% of NAM scenarios.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GUIDE teacher-student training instead of SSMP training (ablation) | any-MPE neural solver · PCs | log-likelihood score: 60% | Helped |
| Use GUIDE teacher-student training instead of SSMP training (ablation) | any-MPE neural solver · NAMs | log-likelihood score: more than 80% | Helped |
| Use GUIDE teacher-student training instead of SSMP training (ablation) | any-MPE neural solver · PGMs | log-likelihood score: 75% | Helped |
| Add ITSELF inference-time optimization to GUIDE (ablation) | GUIDE · PCs | log-likelihood score: nearly 90% | Helped |
| Add ITSELF inference-time optimization to GUIDE (ablation) | GUIDE · NAMs | log-likelihood score: 75% | Helped |
| Add ITSELF inference-time optimization to GUIDE (ablation) | GUIDE · PGMs | log-likelihood score: 75% | Helped |
| Initialize ITSELF with GUIDE pre-training rather than random initialization or SSMP pre-training (ablation) | ITSELF · PCs, NAMs, and PGMs | negative log-likelihood | Helped |
Surprising findings
- With single-pass inference, the polynomial-time MAX baseline beats both SSMP and GUIDE on PCs, so the neural approach needs ITSELF to be competitive.
- Methods built on the self-supervised loss can get stuck or oscillate, so the paper finds that a supervised warm start from a teacher is needed for fast convergence.
Limitations
- Only binary variables are handled in the main method; multi-valued and continuous extensions are described only as sketches in the appendix.
- The self-supervised loss is non-convex, so ITSELF may need many iterations or get stuck in local minima.
- Extending to marginal MAP or constrained MPE can be infeasible when evaluating the loss is expensive, as with NAMs and PGMs.
Experimental setup
Datasets: 20 TPM binary datasets (NLTCS to Ad) grid40x40.f2.wrap grid40x40.f5.wrap grid40x40.f10.wrap grid40x40.f15.wrap
Benchmarks: 20 TPM binary datasets (PCs and NAMs) high-treewidth grid MNs from UAI inference competitions
Metrics: log-likelihood of MPE solution inference time
Baselines: MAX approximation maximum likelihood approximation sequential approximation stochastic hill climbing AND/OR branch and bound SSMP
Builds on: Arya et al. SSMP (self-supervised MMAP solver for PCs) test-time training MADE sum-product networks
Closest papers by meaning
- Learning to Condition: A Neural Heuristic for Scalable MPE Inference (NeurIPS 2025 · similarity 0.90)
- Neural Network Approximators for Marginal MAP in Probabilistic Circuits (AAAI 2024 · similarity 0.87)
- Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations (ICML 2025 · similarity 0.87)
- Explainable Neural Networks with Guarantee: A Sparse Estimation Approach (AAAI 2025 · similarity 0.85)
- Towards Modeling Uncertainties of Self-Explaining Neural Networks via Conformal Prediction (AAAI 2024 · similarity 0.85)
- ReX: A Framework for Incorporating Temporal Information in Model-Agnostic Local Explanation Techniques (AAAI 2025 · 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.