Name
Abstract | ||
|---|---|---|
Linear Programming (LP) relaxations have become powerful tools for finding the most probable (MAP) configuration in graphical models. These relaxations can be solved eciently using message-passing algorithms such as belief propagation and, when the re- laxation is tight, provably find the MAP con- figuration. The standard LP relaxation is not tight enough in many real-world prob- lems, however, and this has lead to the use of higher order cluster-based LP relaxations. The computational cost increases exponen- tially with the size of the clusters and lim- its the number and type of clusters we can use. We propose to solve the cluster selec- tion problem monotonically in the dual LP, iteratively selecting clusters with guaranteed improvement, and quickly re-solving with the added clusters by reusing the existing solu- tion. 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 re- laxation fails. |
Year | Venue | Keywords |
|---|---|---|
2008 | Uncertainty in Artificial Intelligence | lp relaxation,graphical model,linear program,higher order,message passing,belief propagation,protein design |
DocType | Volume | Citations |
Conference | abs/1206.3288 | 135 |
PageRank | References | Authors |
3.99 | 18 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Sontag | 1 | 1784 | 88.59 |
| Talya Meltzer | 2 | 415 | 22.18 |
| Amir Globerson | 3 | 1515 | 117.72 |
| Jaakkola, Tommi | 4 | 6948 | 968.29 |
| Yair Weiss | 5 | 10240 | 834.60 |