Learning to Condition: A Neural Heuristic for Scalable MPE Inference
This addresses scalability issues in MPE inference for high-treewidth PGMs, offering a novel heuristic that enhances search algorithms, though it is incremental as it builds on existing solvers.
The paper tackles the intractable problem of Most Probable Explanation (MPE) inference in Probabilistic Graphical Models by introducing a data-driven framework called learning to condition (L2C), which trains a neural network to score variable-value assignments for conditioning, resulting in significant reduction of the search space while maintaining or improving solution quality over state-of-the-art methods.
We introduce learning to condition (L2C), a scalable, data-driven framework for accelerating Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs), a fundamentally intractable problem. L2C trains a neural network to score variable-value assignments based on their utility for conditioning, given observed evidence. To facilitate supervised learning, we develop a scalable data generation pipeline that extracts training signals from the search traces of existing MPE solvers. The trained network serves as a heuristic that integrates with search algorithms, acting as a conditioning strategy prior to exact inference or as a branching and node selection policy within branch-and-bound solvers. We evaluate L2C on challenging MPE queries involving high-treewidth PGMs. Experiments show that our learned heuristic significantly reduces the search space while maintaining or improving solution quality over state-of-the-art methods.