图 书 馆
完美图的MAP估计MAP Estimation with Perfect Graphs |
|
| 课程网址: | http://videolectures.net/mlss09us_jebara_mapepg/ |
| 主讲教师: | Tony Jebara |
| 开课单位: | 哥伦比亚大学 |
| 开课时间: | 2009-07-30 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Efficiently finding the maximum a posteriori (MAP) configuration of a graphical model is an important problem which is often implemented using message passing algorithms and linear programming. The optimality of such algorithms is only well established for singly-connected graphs such as trees. Recently, along with others, we have shown that matching and b-matching also admit exact MAP estimation under max product belief propagation. This leads us to consider a generalization of trees, matchings and b-matchings: the fascinating family of so-called perfect graphs. While MAP estimation in general loopy graphical models is NP, for perfect graphs of a particular form, the problem is in P. This result leverages recent progress in defining perfect graphs (the strong perfect graph theorem which has been resolved after 4 decades), linear programming relaxations of MAP estimation and recent convergent message passing schemes. In particular, we convert any graphical model into a so-called nand Markov random field. This model is straightforward to relax into a linear program whose integrality can be established in general by testing for graph perfection. This perfection test is performed efficiently using a polynomial time algorithm. Alternatively, known decomposition tools from perfect graph theory may be used to prove perfection for certain graphs. Thus, a general graph framework is provided for determining when MAP estimation in any graphical model is in P, has an integral linear programming relaxation and is exactly recoverable by message passing. |
| 关 键 词: | 最大后验配置; 消息传递算法; 线性编程 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-07-18：cjy |
| 阅读次数: | 65 |