图 书 馆
映射估计中凸松弛的有效求解Efficiently Solving Convex Relaxations for MAP Estimation |
|
| 课程网址: | http://videolectures.net/icml08_mudigonda_escr/ |
| 主讲教师: | Pawan Kumar Mudigonda |
| 开课单位: | 牛津大学 |
| 开课时间: | 2008-08-29 |
| 课程语种: | 英语 |
| 中文简介: |  获得离散随机场的最大后验 (MAP) 估计值的问题在计算机科学的许多领域都至关重要。在这项工作中，我们建立在 Kolmogorov 和 Wainwright 等人的树重加权消息传递 (TRW) 框架之上。 TRW 迭代优化用于 MAP 估计的线性规划松弛的拉格朗日对偶。我们展示了如何将 TRW 的对偶公式扩展到包括线性循环不等式。然后我们考虑在对偶中包含一些最近提出的二阶锥 (SOC) 约束。我们提出了有效的迭代算法来解决由此产生的对偶。类似于 Kolmogorov 描述的方法，这些方法保证收敛。我们在大量合成数据和真实数据上测试我们的算法。我们的实验表明，附加约束（即循环不等式和 SOC 约束）在 TRW 框架失败的情况下（即非子模能量函数的 MAP 估计）提供更好的结果。 |
| 课程简介: | The problem of obtaining the maximum a posteriori (MAP) estimate of a discrete random field is of fundamental importance in many areas of Computer Science. In this work, we build on the tree reweighted message passing (TRW) framework of Kolmogorov and Wainwright et al. TRW iteratively optimizes the Lagrangian dual of a linear programming relaxation for MAP estimation. We show how the dual formulation of TRW can be extended to include linear cycle inequalities. We then consider the inclusion of some recently proposed second order cone (SOC) constraints in the dual. We propose efficient iterative algorithms for solving the resulting duals. Similar to the method described by Kolmogorov, these methods are guaranteed to converge. We test our algorithms on a large set of synthetic data, as well as real data. Our experiments show that the additional constraints (i.e. cycle inequalities and SOC constraints) provide better results in cases where the TRW framework fails (namely MAP estimation for non-submodular energy functions). |
| 关 键 词: | TRW 迭代优化; 拉格朗日对偶; Kolmogorov |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2021-08-11：nkq |
| 最后编审: | 2021-08-11：nkq |
| 阅读次数: | 35 |