Statistical physics of loopy interactions: Independent-loop approximation and beyond

A. Ramezanpour and S. Moghimi-Araghi

Phys. Rev. E 92, 032112 – Published 9 September 2015

Abstract

We consider an interacting system of spin variables on a loopy interaction graph, identified by a tree graph and a set of loopy interactions. We start from a high-temperature expansion for loopy interactions represented by a sum of non-negative contributions from all the possible frustration-free loop configurations. We then compute the loop corrections using different approximations for the nonlocal loop interactions induced by the spin correlations in the tree graph. For distant loopy interactions, we can exploit the exponential decay of correlations in the tree interaction graph to compute loop corrections within an independent-loop approximation. Higher orders of the approximation are obtained by considering the correlations between the nearby loopy interactions involving larger number of spin variables. In particular, the sum over the loop configurations can be computed “exactly” by the belief propagation algorithm in the low orders of the approximation as long as the loopy interactions have a tree structure. These results might be useful in developing more accurate and convergent message-passing algorithms exploiting the structure of loopy interactions.

Received 12 June 2015

DOI:https://doi.org/10.1103/PhysRevE.92.032112

Authors & Affiliations

A. Ramezanpour^*

Department of Physics, University of Neyshabur, P.O. Box 91136-899, Neyshabur, Iran

S. Moghimi-Araghi^†

Department of Physics, Sharif University of Technology, P.O. Box 11155-9161, Tehran, Iran

^*aramezanpour@gmail.com
^†samanimi@sharif.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 92, Iss. 3 — September 2015

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
A loopy interaction graph consisting of a spanning tree and two loopy interactions $(i j)$ and $(k l)$ of lengths $l_{i j} = 5$ and $l_{k l} = 3$ , respectively. The two loops have distance $d_{i j, k l} = 2$ defined as the minimum separation of their end points along the tree.
Reuse & Permissions
Figure 2
(a) Length and (b) distance probability distributions $P (l), P (d)$ of the loopy interactions in the two-dimensional (2D) and three-dimensional (3D) square lattices with respect to a random spanning tree. Here, $L$ is the linear size of the lattices with periodic boundary conditions.
Reuse & Permissions
Figure 3
(a) The exact free energy of the ferromagnetic Ising model ( $h_{i} = 0, J_{i j} = 1$ ) on the 2D square lattice is compared with the independent-loop approximation based on a random and regular (chain) spanning tree. (b) The IL approximation compared with a mean-field approximation of loopy interactions (MFL), where a loopy interaction $(i j) \in L$ is replaced with effective fields $h_{i}^{(i j)} = \frac{1}{2} J_{i j} m_{j}$ and $h_{j}^{(i j)} = \frac{1}{2} J_{i j} m_{i}$ determined self-consistently. The arrows show the position of the ferromagnetic phase transition.
Reuse & Permissions
Figure 4
Comparing the loopy BP (LBP) free energy with that of the independent-site (IS) approximation for a random Ising model ( $h_{i} = \pm h, J_{i j} = \pm 1$ ) on the $2D$ square lattice. The positive and negative values for the fields and the couplings are chosen with equal probability. The loopy BP algorithm does not converge for $T < T_{s}$ indicated by the arrows.
Reuse & Permissions
Figure 5
Comparing the RMS error in magnetization obtained by different approximations: independent loop (IL), independent site (IS), and loopy belief propagation (LBP) for a random Ising model with random fields and couplings uniformly distributed in $(- 1, + 1)$ on the $2D$ square lattice. Both the IL and IS approximations are based on a maximum-weight spanning tree, with weight $W = \sum_{(i j) \in T} | J_{i j} |$ . The $m_{i}^{exact}$ are computed by an exact algorithm [for the smaller system in panel(a)] or by the Monte Carlo algorithm [for the larger system in panel (b)]. The error bars are about the size of the symbols. The RMS error is given by $Δ m \equiv \sqrt{\sum_{i = 1}^{N} {(m_{i}^{app} - m_{i}^{exact})}^{2} / N}$ .
Reuse & Permissions
Figure 6
Comparing the RMS errors in loopy correlations and magnetizations $Δ c \equiv \sqrt{\sum_{(i j) \in L} {(c_{i j}^{app} - c_{i j}^{exact})}^{2} / | L |}$ and $Δ m \equiv \sqrt{\sum_{i = 1}^{N} {(m_{i}^{app} - m_{i}^{exact})}^{2} / N}$ , obtained by different approximations: independent loop (IL), correlated loops (CL), loopy belief propagation (LBP), and generalized belief propagation (GBP) for random Ising models with random couplings uniformly distributed in $(- 1, + 1)$ on the $2D$ square lattice. The fields are zero in panels (a) and (b), but they are nonzero and uniformly distributed in $(- 1, + 1)$ in panels (c) and (d). Both the IL and CL approximations are based on a maximum-weight spanning tree, with weight $W = \sum_{(i j) \in T} | J_{i j} |$ . The $c_{i j}^{exact}$ and $m_{i}^{exact}$ are computed by an exact algorithm for the smaller system in panel (a), and by the Monte Carlo algorithm for the larger systems in panels (b)–(d). The error bars are about the size of the symbols.
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics