← Back to papers
2007 NIPS NeurIPS 2007

Cooled and Relaxed Survey Propagation for MRFs

Abstract

We describe a new algorithm, Relaxed Survey Propagation (RSP), for finding MAP configurations in Markov random fields. We compare its performance with state-of-the-art algorithms including the max-product belief propagation, its se- quential tree-reweighted variant, residual (sum-product) belief propagation, and tree-structured expectation propagation. We show that it outperforms all ap- proaches for Ising models with mixed couplings, as well as on a web person disambiguation task formulated as a supervised clustering problem.

🧭 Keyword Pioneer — survey propagation
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics
📈 Trend Setter — Graphical Models
🐣 Hot Topic Early Bird — constraint satisfaction

Authors

Hai L. Chieu , Wee S. Lee , Yee W. Teh

Topics

Machine Learning > Core Methods > Representation Learning Machine Learning > Optimization & Theory > Optimization Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Bayesian & Probabilistic > Probabilistic Modeling Machine Learning > Core Methods > Graphical Models Machine Learning > Bayesian & Probabilistic > Graphical Models Machine Learning > Core Methods > Inference

Keywords

belief propagation map inference map estimation survey propagation constraint satisfaction max-product markov random field optimization algorithm relaxed survey propagation map configuration
Download PDF

Related papers

Exponential Family Predictive Representations of State 2007
Privacy-Preserving Belief Propagation and Sampling 2007
Efficient Principled Learning of Thin Junction Trees 2007
How SVMs can estimate quantiles and the median 2007
Rapid Inference on a Novel AND/OR graph for Object Detection, Segmentation and Parsing 2007