arXiv cs.AI· Akshay Vyas, Hailiang Dong, Shivvrat Arya, Brij Malhotra, Tahrima Rahman, Vibhav Gogate, Nicholas Ruozzi·· 4 小时前AI 评分32
Learning to Bound（L2B）：用于 MPE 推理的单调、经校准的神经上界框架
Learning to Bound: Monotonic, Calibrated Neural Upper Bounds for MPE Inference
AI 导读
arXiv 论文提出 Learning to Bound（L2B），一个通过训练神经预测器来摊销上界计算成本的数据驱动框架，用于概率图模型的 MPE 推理。L2B 借助统计校准保证可采纳性，并通过结构性架构约束确保随证据增加的单调收紧。在多个基准上，L2B 以数量级更低的开销给出更紧的单调上界，并在高树宽实例上与 branch-and-bound 结合取得可测量的改进。
正文 · 原文
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