Cavity Method: Message Passing from a Physics Perspective

Understand

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.