图 书 馆
收紧线性规划松弛用于地图使用消息传递Tightening LP Relaxations for MAP using Message Passing |
|
| 课程网址: | http://videolectures.net/uai08_sontag_tlpr/ |
| 主讲教师: | David Sontag |
| 开课单位: | 纽约大学 |
| 开课时间: | 2007-07-30 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Linear Programming (LP) relaxations have become powerful tools for finding the most probable (MAP) configuration in graphical models. These relaxations can be solved efficiently using message-passing algorithms such as belief propagation and, when the relaxationis tight, provably find the MAP configuration. The standard LP relaxation is not tight enough in many real-world problems, however, and this has lead to the use of higher order cluster-based LP relaxations. The computational cost increases exponentially with the size of the clusters and limits the number and type of clusters we can use. We propose to solve the cluster selection problem monotonically in the dual LP, iteratively selecting clusters with guaranteed improvement, and quickly re-solving with the added clusters by reusing the existing solution. Our dual message-passing algorithm finds the MAP configuration in protein side chain placement, protein design, and stereo problems, in cases where the standard LP relaxation fails. |
| 关 键 词: | 机器学习; 图形模型; 人工智能; 计算机科学 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-11-04：lxf |
| 阅读次数: | 53 |