用强化学习思路解决难算的最优推断问题，能保证结果靠谱且高效。
Probably Approximately Correct Maximum A Posteriori Inference
- 把最大后验估计转为寻宝游戏，用概率保证找到最好解
- 在有限尝试次数内可证明找到接近最优解，精度有理论保障
- 适合需要可靠推理结果的研究者，尤其在模型结构复杂时
计算概率分布的条件众数，即最大后验（MAP）赋值，是概率推断中的基础任务。然而，MAP通常难以计算，即使在常见结构约束和近似方法下仍困难重重。我们受多臂赌博机启发，将MAP重述为最佳臂识别问题。提出概率上近似正确（PAC）的MAP算法，在固定置信度和固定预算两种情形下均提供可证明最优的解决方案。我们利用信息论度量刻画可计算性条件，这些度量可从有限样本中估计。所提出的PAC-MAP求解器通过具备合适结构的概率电路与图模型高效实现。开发的算法既可独立作为MAP估计器，也可用于改进标准启发式方法，为其解提供严格保证。实验在多个基准测试中验证了该方法的优势。
原文摘要 · Abstract (English)
Computing the conditional mode of a distribution, better known as the maximum a posteriori (MAP) assignment, is a fundamental task in probabilistic inference. However, MAP is generally intractable, and remains hard even under many common structural constraints and approximation schemes. We take a novel approach inspired by multi-armed bandits, recasting MAP as a best arm identification task. We introduce probably approximately correct (PAC) algorithms for MAP that provide provably optimal solutions in both the fixed-confidence and fixed-budget regimes. We characterize tractability conditions using information theoretic measures that can be estimated from finite samples. Our PAC-MAP solvers are efficiently implemented using probabilistic circuits and graphical models with appropriate architectures. The algorithms we develop can be used either as standalone MAP estimators or to improve on standard heuristics, fortifying their solutions with rigorous guarantees. Experiments confirm the benefits of our method in a range of benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。