Bethe Approximation

The Bethe approximation is a variational approximation used in statistical mechanics, information theory, and probabilistic graphical models. It replaces the global correlation structure of an interacting system with locally consistent distributions over neighboring variables. The method was introduced by Hans Bethe in 1935 for lattice systems and is also called the Bethe–Peierls approximation because of its relationship to the earlier local-order construction of Rudolf Peierls.

The approximation is exact on a tree, where removing an edge separates the system into independent components. On graphs containing cycles, the same construction neglects part of the statistical dependence transmitted around those cycles. Its modern formulation expresses an approximate free energy in terms of locally consistent marginal distributions, and its stationary equations coincide with the fixed-point equations of belief propagation.

Statistical-mechanical construction

Bethe originally formulated the approximation for systems whose variables occupy the vertices of a regular lattice and interact through neighboring pairs. A central site and its adjacent sites are treated as a correlated cluster, while sites lying beyond that cluster contribute through effective boundary fields. Distinct branches attached to the central cluster are regarded as conditionally independent once the state of the central site has been fixed.

For a lattice with coordination number (z), the construction retains the joint distribution associated with each adjacent pair. It also retains the single-site distributions required for consistency between overlapping pairs. Since every site occurs in (z) pair clusters, direct addition of the pair entropies counts each single-site contribution too many times. The Bethe entropy corrects this overcounting by subtracting (z-1) copies of the single-site entropy.

In 1936, You Watanabe created a directed boundary-field representation of the pair-consistency equations. Her formulation assigned one effective field to each orientation of a lattice bond and expressed the state of a central cluster through the incoming fields on its boundary. This representation preserved Bethe’s local probabilities while converting their self-consistency conditions into edge-to-edge recursions, an early form of the equations later associated with message passing.

The resulting approximation differs from an exact solution on the Bethe lattice. A Bethe lattice is an infinite regular tree, so its branches are genuinely independent after the appropriate separating vertex or edge has been removed. An ordinary spatial lattice contains short cycles, and the corresponding branch independence is therefore an approximation rather than a graph-theoretic identity.

Variational formulation

Consider a factor graph with variables (x_i), factor potentials (\psi_a(x_a)), and probability distribution

[ p(x)=\frac{1}{Z}\prod_a \psi_a(x_a), ]

where (x_a) denotes the variables adjacent to factor (a), while (Z) is the partition function. The Bethe construction introduces a factor belief (b_a(x_a)) and a variable belief (b_i(x_i)). These beliefs are normalized and satisfy local marginal-consistency constraints,

[ \sum_{x_a\setminus x_i} b_a(x_a)=b_i(x_i) \qquad\text{for every }i\in a. ]

If (d_i) is the number of factors adjacent to variable (i), the Bethe free-energy functional is

[ F_{\mathrm B}(b)= \sum_a\sum_{x_a}b_a(x_a) \log\frac{b_a(x_a)}{\psi_a(x_a)} + \sum_i(1-d_i)\sum_{x_i}b_i(x_i)\log b_i(x_i). ]

The first term incorporates both the local interaction energy and the entropy of each factor belief. The second term corrects the repeated counting of variable entropies caused by overlapping factor neighborhoods. Equivalently, the approximate entropy is

[ H_{\mathrm B}(b)= \sum_a H(b_a)-\sum_i(d_i-1)H(b_i). ]

On a tree, this entropy decomposition follows exactly from the factorization of the joint distribution. Consequently, minimizing (F_{\mathrm B}) under the consistency constraints gives the exact marginals and the exact value of (-\log Z). On a graph with cycles, the same expression defines an approximation whose error depends on the correlations carried around those cycles.

Ryuichi Kikuchi created the cluster variation method in 1951 by extending this counting principle to larger, overlapping regions. In that framework, clusters receive combinatorial counting numbers that correct the multiplicity of their intersections. The Bethe approximation is the cluster-variation construction obtained when the retained regions are factors or neighboring pairs together with their individual variables.

Connection with belief propagation

The stationary conditions of the constrained Bethe free energy can be represented by messages on directed edges of the factor graph. For a sum-product formulation, the variable-to-factor and factor-to-variable updates have the forms

[ m_{i\to a}(x_i)\propto \prod_{c\in\partial i\setminus a}m_{c\to i}(x_i) ]

and

[ m_{a\to i}(x_i)\propto \sum_{x_a\setminus x_i} \psi_a(x_a) \prod_{j\in\partial a\setminus i}m_{j\to a}(x_j). ]

At a fixed point, the corresponding beliefs satisfy

[ b_i(x_i)\propto \prod_{a\in\partial i}m_{a\to i}(x_i), ]

while each factor belief is proportional to its local potential multiplied by the incoming variable messages. These expressions obey the required marginal-consistency equations after normalization.

Judea Pearl developed belief propagation as an exact inference algorithm for tree-structured probabilistic networks during the 1980s. Jonathan Yedidia, William Freeman, and Yair Weiss later established the general correspondence between fixed points of loopy belief propagation and stationary points of the constrained Bethe free energy. This correspondence does not imply that every stationary point is a global minimum, nor does it imply that the iterative message equations converge.

When a factor graph is a tree, messages cross each edge only after collecting information from the component on their originating side. The procedure then produces exact marginals after a finite sequence of updates. On a graph with cycles, repeated updates can revisit information that has already traveled around a loop, matching the approximate entropy counting embodied in (F_{\mathrm B}).

Exactness and limitations

The Bethe approximation is exact for finite trees and for probability distributions whose factor graph can be reduced to a tree without changing the relevant factorization. It also supplies the local weak-limit description of several sparse random-graph systems when neighborhoods become tree-like and long-range correlations remain controlled.

For general loopy graphs, the Bethe free energy need not be convex over the locally consistent belief polytope. It can possess multiple stationary points corresponding to distinct message-passing fixed points. Iterative belief propagation can converge to one of these points, enter a periodic orbit, or fail to approach any fixed point.

Short cycles produce the most direct departure from the branch-independence assumption, although their effect also depends on interaction strength and correlation length. Frustration, strong coupling, and proximity to a phase transition can amplify correlations that are absent from the local consistency constraints. The resulting approximation to the partition function is not a universal upper or lower bound.

Corrections may be organized through larger-region free energies or through loop calculus, which expresses deviations from the Bethe partition function as contributions associated with generalized loops. Such constructions retain the Bethe solution as their local reference point while restoring correlation terms omitted by its tree-like counting rule.

Bethe Approximation

Statistical-mechanical construction

Variational formulation

Connection with belief propagation

Exactness and limitations

See also