arXiv cs.AI· Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman, Vibhav Gogate, Nicholas Ruozzi·· 14 小时前AI 评分22
Learning to Bound（L2B）：用单调、校准的神经网络上界加速 MPE 推理
Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference
AI 导读
研究者提出 Learning to Bound（L2B），用神经网络预测器摊销概率图模型中 MPE 推理的上界计算成本。该方法通过统计校准保证上界可采纳性，并用结构约束在构造上保证随证据累积单调收紧。在多个挑战性基准上，L2B 在各 PGM 家族上以低数个数量级的成本给出更紧的单调上界，与分支定界结合后在高树宽实例上取得可测提升。
正文 · 原文
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.
| Comments: | 37 pages, 4 figures |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.39305 [cs.LG] |
| (or arXiv:2610.39305v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.39305 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Akshay Vyas [view email]
[v1]
Thu, 29 Oct 2026 03:51:39 UTC (565 KB)
来源：arXiv cs.AI · arxiv.org