Cooled and Relaxed Survey Propagation for MRFs (W14) Hai Leong Chieu, Wee Sun Lee and Yee Whye Teh
Constraint Satisfaction Problem Survey Propagation Sum-product S u m -p r o d u c t Interpretation Interpretation Satisfying configuration

We show how survey propagation can be applied to general MRFs MRFs
MRF Relaxed Survey Relaxed Propagation Propagation Alternative MRF Sum-product S u m -p r o d u c t Interpretation Interpretation Approximate marginals marginals over MRF over MAP MAP configuration configuration

Weighted M a x -S A T

Cooled, Relaxed Survey Propagation

re a tu er m p duct te w e r m -p r o Lo s u on

For energy minimization, outperforms max-product, sum-product, For TRW-S and Tree-EP on binary networks with mixed couplings TRW-S