用割平面法求解贝叶斯因子模型的MAP推断，可保证收敛且支持复杂约束。
Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition
- 基于Benders分解逐次添加约束，从松弛对偶问题逐步逼近最优解。
- 在标准数据集上比吉布斯采样和变分贝叶斯获得更高后验值。
- 适合需精确推断与逻辑约束的聚类任务，如必须/不能同属一类。
许多贝叶斯统计推断问题归结为计算隐变量的最大后验（MAP）赋值。然而，标准的MAP估计方法缺乏有限时间收敛至不动点的保证。先前研究发现，MAP推断可表示为具有非多项式数量约束的对偶线性规划问题。对偶问题的拉格朗日松弛可转化为统计推断算法，但松弛中移除哪些约束常依赖启发式策略。本文提出一种通用贝叶斯因子模型的MAP推断方法，通过Benders分解逐次向完全松弛的对偶问题添加约束。该方法可融入聚类问题中的表达性强整数与逻辑约束，如必须连接、不能连接及每类至少分配样本数等。基于此，我们推导了贝叶斯高斯混合模型与潜在狄利克雷分配（LDA）的MAP估计算法。实验表明，本方法在标准数据集上所得后验值高于吉布斯采样与变分贝叶斯，并提供收敛证明。
原文摘要 · Abstract (English)
Many Bayesian statistical inference problems come down to computing a maximum a-posteriori (MAP) assignment of latent variables. Yet, standard methods for estimating the MAP assignment do not have a finite time guarantee that the algorithm has converged to a fixed point. Previous research has found that MAP inference can be represented in dual form as a linear programming problem with a non-polynomial number of constraints. A Lagrangian relaxation of the dual yields a statistical inference algorithm as a linear programming problem. However, the decision as to which constraints to remove in the relaxation is often heuristic. We present a method for maximum a-posteriori inference in general Bayesian factor models that sequentially adds constraints to the fully relaxed dual problem using Benders' decomposition. Our method enables the incorporation of expressive integer and logical constraints in clustering problems such as must-link, cannot-link, and a minimum number of whole samples allocated to each cluster. Using this approach, we derive MAP estimation algorithms for the Bayesian Gaussian mixture model and latent Dirichlet allocation. Empirical results show that our method produces a higher optimal posterior value compared to Gibbs sampling and variational Bayes methods for standard data sets and provides certificate of convergence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。