MAP Estimation with Perfect Graphs
Description
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.
| Slides | |
| 0:00 | MAP Estimation with Perfect Graphs |
| 0:37 | Background, Matchings, Perfect Graphs, MAP Estimation |
| 1:53 | Background on Perfect Graphs (1) |
| 4:14 | Background on Perfect Graphs (2) |
| 6:22 | Graphical Models |
| 7:44 | MAP Estimation |
| 10:40 | Max Product Message Passing |
| 12:36 | Bipartite Matching (1) |
| 14:05 | Bipartite Generalized Matching (1) |
| 15:14 | Bipartite Generalized Matching (2) |
| 16:42 | Bipartite Matching (2) |
| 17:41 | Bipartite Generalized Matching (3) |
| 18:02 | Generalized Matching |
| 18:47 | Unipartite Generalized Matching |
| 19:49 | Unipartite Generalized Matching (1) |
| 20:07 | Unipartite Generalized Matching (2) |
| 21:03 | Unipartite Generalized Matching (3) |
| 22:46 | Back to Perfect Graphs (1) |
| 24:01 | Back to Perfect Graphs (2) |
| 24:26 | nand Markov Random Fields (1) |
| 26:03 | nand Markov Random Fields (2) |
| 27:20 | nand Markov Random Fields (3) |
| 29:38 | Packing Linear Programs (1) |
| 30:53 | Packing Linear Programs (2) |
| 32:02 | Packing Linear Programs (3) |
| 32:23 | Packing Linear Programs (4) |
| 32:47 | Perfect Graphs |
| 35:00 | Strong Perfect Graph Theorem |
| 36:39 | Recognition using Perfect Graphs Algorithm (1) |
| 39:07 | Recognition using Perfect Graphs Algorithm (2) |
| 40:34 | Recognition using Perfect Graphs Algorithm (3) |
| 41:35 | Recognition using Perfect Graphs Algorithm (4) |
| 42:11 | Proving Exact MAP for Tree Graphs (1) |
| 43:28 | Proving Exact MAP for Bipartite Matchings |
| 44:16 | Proving Exact MAP for Bipartite Matchings |
| 44:58 | Pruning NMRFs |
| 46:16 | Convergent Message Passing (1) |
| 46:54 | Convergent Message Passing (2) |
| 47:19 | MAP Experiments (1) |
| 48:23 | MAP Experiments (2) |
| 49:27 | Conclusions |
| 50:20 | Further Reading and Thanks |
Lecture rating
| People found this lecture: | ||
| Worth seeing | ||
| because it is: | ||
| Valuable and informative | ||
| Well presented | ||
| Easily understandable | ||
| Acceptably recorded | ||
| You need to login to cast your vote. | ||
Report a problem or upload files
If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Related content
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !




