Cavity method

The cavity method is a family of approximation techniques that studies a system by removing one component, then estimating how its absence affects the rest.

Belief propagation: An iterative algorithm that passes local probability messages along a graph to estimate marginal distributions. Cavity calculations often express a removed node’s influence as messages between neighboring variables.
Factor graph: A bipartite graph representing a factorized function with variable nodes and factor nodes. Cavity equations remove variables or factors from this representation to define local environments.
Spin glass: A magnetic system with competing interactions and many frustrated, disordered configurations. Spin glasses are a central setting for developing and testing cavity approximations.
Mézard–Parisi solution: A replica-symmetry-breaking solution for the Sherrington–Kirkpatrick spin glass developed by Marc Mézard and Giorgio Parisi. Its development established the cavity approach as a way to analyze complex spin-glass states.
Exact inference: A procedure that computes the precise requested probabilities or quantities from a probabilistic model. Cavity methods trade exactness for tractability on large, loopy systems.
Bethe approximation: An approximation to a graphical model’s partition function based on local beliefs and graph structure. The cavity method yields Bethe free-energy estimates when local neighborhoods are effectively tree-like.
Partition function: A sum over system configurations that encodes their statistical weights and determines thermodynamic quantities. Cavity approximations estimate this global quantity from local contributions.
Random graph: A graph generated by a probabilistic model rather than specified edge by edge. Sparse random graphs often have locally tree-like neighborhoods suited to cavity analysis.
Sherrington–Kirkpatrick model: A mean-field spin-glass model with random interactions between every pair of spins. The model provided a major test case for cavity analysis of disordered systems.
Junction tree algorithm: An exact inference algorithm that organizes a graphical model into a tree of overlapping clusters. It handles loops exactly at a cost governed by treewidth, unlike approximate cavity updates.

Linked from 2 pages

Mean-field and cluster methodsRelated: The removed-site construction derives effective fields on sparse networks and tree-like systems.