### Abstract

Dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decomposition has a large integrality gap, due to frustrated cycles. One way to tighten the relaxation is to introduce additional constraints that explicitly enforce cycle consistency. Earlier work showed that cluster-pursuit algorithms, which iteratively introduce cycle and other higherorder consistency constraints, allows one to exactly solve many hard inference problems. However, these algorithms explicitly enumerate a candidate set of clusters, limiting them to triplets or other short cycles. We solve the search problem for cycle constraints, giving a nearly linear time algorithm for finding the most frustrated cycle of arbitrary length. We show how to use this search algorithm together with the dual decomposition framework and clusterpursuit. The new algorithm exactly solves MAP inference problems arising from relational classification and stereo vision.

Original language | English (US) |
---|---|

Title of host publication | Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012 |

Pages | 795-804 |

Number of pages | 10 |

State | Published - 2012 |

Event | 28th Conference on Uncertainty in Artificial Intelligence, UAI 2012 - Catalina Island, CA, United States Duration: Aug 15 2012 → Aug 17 2012 |

### Publication series

Name | Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012 |
---|

### Other

Other | 28th Conference on Uncertainty in Artificial Intelligence, UAI 2012 |
---|---|

Country | United States |

City | Catalina Island, CA |

Period | 8/15/12 → 8/17/12 |

### ASJC Scopus subject areas

- Artificial Intelligence

## Fingerprint Dive into the research topics of 'Efficiently searching for frustrated cycles in MAP inference'. Together they form a unique fingerprint.

## Cite this

*Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012*(pp. 795-804). (Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012).