Convex max-product algorithms for continuous MRFs with applications to protein folding

Jian Peng, Tamir Hazan, David McAllester, Raquel Urtasun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper investigates convex belief propagation algorithms for Markov random fields (MRFs) with continuous variables. Our first contribution is a theorem generalizing properties of the discrete case to the continuous case. Our second contribution is an algorithm for computing the value of the Lagrangian relaxation of the MRF in the continuous case based on associating the continuous variables with an ever-finer interval grid. A third contribution is a particle method which uses convex max-product in re-sampling particles. This last algorithm is shown to be particularly effective for protein folding where it outperforms particle methods based on standard max-product resampling.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th International Conference on Machine Learning, ICML 2011
Pages729-736
Number of pages8
StatePublished - Oct 7 2011
Externally publishedYes
Event28th International Conference on Machine Learning, ICML 2011 - Bellevue, WA, United States
Duration: Jun 28 2011Jul 2 2011

Publication series

NameProceedings of the 28th International Conference on Machine Learning, ICML 2011

Other

Other28th International Conference on Machine Learning, ICML 2011
Country/TerritoryUnited States
CityBellevue, WA
Period6/28/117/2/11

ASJC Scopus subject areas

  • Computer Science Applications
  • Human-Computer Interaction
  • Education

Fingerprint

Dive into the research topics of 'Convex max-product algorithms for continuous MRFs with applications to protein folding'. Together they form a unique fingerprint.

Cite this