跳转至

大概率近似正确最大后验推断

文章背景与核心概要

计算概率分布的条件众数（即最大后验（MAP）赋值）是概率推断中的核心且出了名的棘手任务。本文引入了一种新颖的方法，受多臂老虎机（multi-armed bandits）的启发，将 MAP 重新构建为最佳臂识别（best arm identification）问题。通过为 MAP 提出大概率近似正确（PAC）算法，作者为固定置信度（fixed-confidence）和固定预算（fixed-budget）机制提供了可证明的最优解。

这些 PAC-MAP 求解器使用信息论度量，可以通过概率电路和图模型进行高效实现，从而改进了标准的启发式方法并产生了稳健的实验结果。该方法既可以作为独立的 MAP 估计器，也可以用来增强标准启发式方法，为其解提供严格的理论保证。

摘要 (Abstract)

Summary

Computing the conditional mode of a probability distribution (the Maximum A Posteriori, or MAP, assignment) is a central yet notoriously intractable task in probabilistic inference. This paper introduces a novel approach that recasts MAP as a best arm identification problem inspired by multi-armed bandits. By proposing probably approximately correct (PAC) algorithms for MAP, the authors provide provably optimal solutions for both fixed-confidence and fixed-budget regimes. These PAC-MAP solvers use information-theoretic measures and can be efficiently implemented via probabilistic circuits and graphical models, improving standard heuristics and yielding robust empirical results.

计算分布的条件众数（更广为人知的名称是最大后验（MAP）赋值）是概率推断中的一项基本任务。然而，MAP 通常是难以处理的，即使在许多常见的结构约束和近似方案下仍然很困难。

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.

我们采用了一种受多臂老虎机启发的新颖方法，将 MAP 重新定义为最佳臂识别任务。我们引入了针对 MAP 的大概率近似正确 (PAC) 算法，该算法在固定置信度和固定预算机制下均提供了可证明的最优解。我们使用可以从有限样本中估计的信息论度量来表征可处理性条件。我们的 PAC-MAP 求解器利用具有适当架构的概率电路和图模型进行了高效实现。我们开发的算法既可以作为独立的 MAP 估计器，也可以用于改进标准启发式方法，并通过严格的保证来巩固其解。实验证实了我们的方法在了一系列基准测试中的优势。

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.

论文信息 (Paper Information)

  • arXiv ID: arXiv:2601.16083 [cs.LG]
  • 学科分类: 机器学习 (cs.LG); 人工智能 (cs.AI)
  • 作者: Matthew Shorvon, Frederik Mallmann-Trenn, David S. Watson
  • 提交时间: 2026年1月22日
  • 最后修订: 2026年8月11日 (版本 v2)
  • DOI: 10.48550/arXiv.2601.16083

Paper Information

  • arXiv ID: arXiv:2601.16083 [cs.LG]
  • Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
  • Authors: Matthew Shorvon, Frederik Mallmann-Trenn, David S. Watson
  • Submitted On: 22 January 2026
  • Last Revised: 11 August 2026 (Version v2)
  • DOI: 10.48550/arXiv.2601.16083

访问与资源 (Access & Resources)

Access & Resources

提交历史 (Submission History)

  • [v1] 2026年1月22日 星期四 16:28:01 UTC (104 KB)
  • [v2] 2026年8月11日 星期二 20:30:56 UTC (124 KB, 当前版本)

Submission History

  • [v1] Thu, 22 Jan 2026 16:28:01 UTC (104 KB)
  • [v2] Tue, 11 Aug 2026 20:30:56 UTC (124 KB, Current Version)