针对非凸约束下的概率推断难题，提出高效可靠的精确与近似求解方法。
The Theory and Practice of MAP Inference over Non-Convex Constraints
- 设计可扩展的消息传递算法，实现特定可解非凸约束下的精确推断。
- 通过划分凸可行区域并结合数值优化，构建通用近似求解框架。
- 适用于安全关键场景中的轨迹预测等复杂约束问题，性能超越现有方法。
在诸多安全关键应用中，概率机器学习系统需在代数约束下做出预测，例如生成不穿越障碍物的最可能轨迹。这些实际约束通常非凸，且所考虑的概率密度也非（对数）凹。这使得高效可靠地计算受限最大后验（MAP）预测极具挑战。本文首先研究在何种条件下可对连续变量上的受限MAP推断进行精确且高效的求解，并提出一种可扩展的消息传递算法来处理这一可解片段。随后，设计了一种通用的受限MAP策略，该策略交替执行将定义域划分为凸可行区域，以及进行数值约束优化。我们在合成数据和真实世界基准上评估了两种方法，结果表明我们的方法显著优于无约束基线，并能扩展到现有最优精确求解器无法处理的复杂密度场景。
原文摘要 · Abstract (English)
In many safety-critical settings, probabilistic ML systems have to make predictions subject to algebraic constraints, e.g., predicting the most likely trajectory that does not cross obstacles. These real-world constraints are rarely convex, nor the densities considered are (log-)concave. This makes computing this constrained maximum a posteriori (MAP) prediction efficiently and reliably extremely challenging. In this paper, we first investigate under which conditions we can perform constrained MAP inference over continuous variables exactly and efficiently and devise a scalable message-passing algorithm for this tractable fragment. Then, we devise a general constrained MAP strategy that interleaves partitioning the domain into convex feasible regions with numerical constrained optimization. We evaluate both methods on synthetic and real-world benchmarks, showing our approaches outperform constraint-agnostic baselines, and scale to complex densities intractable for SoTA exact solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。