Lagrangian Relaxation for MAP Estimation in Graphical Models
Lagrangian Relaxation for MAP Estimation in Graphical Models
复制标题
图形模型中 MAP 估计的拉格朗日松弛
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Willsky
中科院分区：
文献类型：
--
作者：
Jason K. Johnson;D. Malioutov;A. Willsky
我们使用拉格朗日放松技术在离散和高斯图形模型中开发了一个通用框架。关键思想是在更易于处理的图上定义一个棘手的估计问题，但要受其他约束。放松这些约束会提供一个可拖动的双重问题，该问题由薄图定义，然后通过迭代过程进行优化。当这种迭代优化导致一致的估计值时，也满足约束的估计值，则对应于原始模型的最佳映射估计。否则会有“二元差距”，我们会在最佳解决方案上获得绑定。因此，我们的方法将凸优化与适用于薄图的动态编程技术结合在一起。流行的树剥离最大产品（TRMP）方法可能被视为解决了特定类别的这种放松类别，其中将棘手的图形放松到一组跨越树木中。我们还考虑放松一组小的诱导子图，薄的子图（例如循环）以及通过“放松”周期获得的连接树。此外，我们提出了一类新的多尺度放松，以引入“摘要”变量。这种概括的潜在优势包括：在严重问题中减少或消除“二元性差距”，减少双重问题中的Lagrange乘数数量，并加速迭代优化过程的收敛性。
We develop a general framework for MAP es- timation in discrete and Gaussian graphical models using Lagrangian relaxation techniques. The key idea is to refor- mulate an intractable estimation problem as one defined on a more tractable graph, but subject to additional constraints. Relaxing these constraints gives a tractable dual problem, one defined by a thin graph, which is then optimized by an iterative procedure. When this iterative optimization leads to a consistent estimate, one which also satisfies the constraints, then it corresponds to an optimal MAP estimate of the original model. Otherwise there is a "duality gap", and we obtain a bound on the optimal solution. Thus, our approach combines convex optimization with dynamic programming techniques applicable for thin graphs. The popular tree-reweighted max- product (TRMP) method may be seen as solving a particular class of such relaxations, where the intractable graph is relaxed to a set of spanning trees. We also consider relaxations to a set of small induced subgraphs, thin subgraphs (e.g. loops), and a connected tree obtained by "unwinding" cycles. In addition, we propose a new class of multiscale relaxations that introduce "summary" variables. The potential benefits of such generalizations include: reducing or eliminating the "duality gap" in hard problems, reducing the number of Lagrange multipliers in the dual problem, and accelerating convergence of the iterative optimization procedure.