Neural networks speed up and improve search for best probabilistic solutions
Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference
Machine LearningArtificial Intelligence
Summary
Finding the most likely explanation in complex probabilistic models can take a very long time. The authors created a method that uses neural networks to quickly estimate upper bounds for these best solutions, helping search algorithms work faster. Their approach ensures these bounds get better as more information is known and remain mathematically trustworthy. Tests show this method improves search speed and accuracy on tough problems where traditional methods struggle.
What this means in practice
- •For machine learning engineers: Accelerate inference in complex probabilistic models for faster decision-making in AI systems.
- •For operations research analysts: Improve optimization processes that rely on probabilistic inference under uncertainty with cheaper upper bounds.
Authors
Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman, Vibhav Gogate, Nicholas Ruozzi
Abstract
Probabilistic graphical models (PGMs) compactly encode structured joint distributions, but Most Probable Explanation (MPE), which finds the highest-probability assignment to unobserved variables, remains computationally intractable in large, densely structured models. Anytime systematic search, such as branch-and-bound (B&B), is a popular approach, but its efficiency depends on tight admissible upper bounds that are often prohibitively expensive to compute using classical methods like Mini-Bucket Elimination (MBE). We introduce Learning to Bound (L2B), a data-driven framework that amortizes bound computation cost by training a neural predictor. L2B targets two key properties required for effective search bounds: admissibility, which is achieved via statistical calibration techniques, and progressive tightening as evidence accumulates, which is enforced through structural architectural constraints that ensure monotonicity by construction. Across challenging benchmarks, L2B delivers tighter, monotonic bounds at orders-of-magnitude lower cost on every PGM family, and yields measurable improvements when integrated with branch-and-bound on high-treewidth instances.