|
有效解决MAP估计的凸松弛
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描述的方法类似，这些方法保证收敛。我们在大量合成数据和实际数据上测试我们的算法。我们的实验表明，在TRW框架失效的情况下（即非子模块能量函数的MAP估计），附加约束（即循环不等式和SOC约束）提供了更好的结果。
|
| 课程简介: |
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).
|
| 关 键 词: |
离散随机场; 计算机科学; 拉格朗日对偶
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2019-04-19：lxf
|
| 阅读次数: |
80
|
|
图 书 馆