Cavity Method: Message Passing from a Physics perspective
2016 (English)In: Statistical Physics, Optimization, Inference, and Message-Passing Algorithms: Lecture Notes of the Les Houches School of Physics - Special Issue October 2013 / [ed] F. Krzakala et al., Oxford University Press, 2016Chapter in book (Other academic)
In this three-sections lecture cavity method is introduced as heuristic framework from a Physics perspective to solve probabilistic graphical models and it is presented both at the replica symmetric (RS) and 1-step replica symmetry breaking (1RSB) level. This technique has been applied with success on a wide range of models and problems such as spin glasses, random constrain satisfaction problems (rCSP), error correcting codes etc. Firstly, the RS cavity solution for Sherrington-Kirkpatrick model---a fully connected spin glass model---is derived and its equivalence to the RS solution obtained using replicas is discussed. Then, the general cavity method for diluted graphs is illustrated both at RS and 1RSB level. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as example of an actual problem, K-SAT is investigated using belief and survey propagation.
Place, publisher, year, edition, pages
Oxford University Press, 2016.
cavity method, message passing, survey propagation, tree-like graphs
Research subject Physics
IdentifiersURN: urn:nbn:se:kth:diva-192102OAI: oai:DiVA.org:kth-192102DiVA: diva2:958026
QC 201609052016-09-052016-09-052016-09-05Bibliographically approved