Ising Model Settings Temperature (T) = 1 External Field (h) Random External Field Uniform Positive Uniform Zero Uniform Negative Randomize Coupling Strength (J) = 1 Grid Size = 30

Belief Propagation Settings Initialization Random Uniform Reset Simulation Speed Stop Slow Fast Damping (α) = .92

Description

In the figure above, each box represents a particle placed in a 2D grid. The particles interact only with particles that are adjacent to them in a north, south, east, or west direction. Each particle has an associated spin (+1 or -1). Given an assignment of spins, we compute the energy of the system as: $$E(x) = e^{1/T(\sum_i h_ix_i + \sum_{ij} J_{ij}x_ix_j)}$$ In the above, each element of the vector x has a value of either +1 or -1. When studying the properties of such a system, one quatity of interest is the partition function: $$Z = \sum_{x\in\{-1,1\}^n} E(x)$$ In general, computing Z can be computationally expensive (in fact, it's known to be NP-hard). As a result, we will usually settle for a good approximation. The belief propagation algorithm (BP) is an iterative message passing scheme over a given graphical model. The goal of the algorithm is to perform approximate inference. In this example, we use it to approximate the partition function of the energy function for the 2D Ising model. In addition to the partition function, BP also provides approximate marginals. In the above visualization, squares are colored by the approximate marginal probabilities produced by the BP algorithm: the percentage of red is give by the marginal probability of +1 at that node and the percentage of blue is given by the marginal probability for -1. Here, we employ the standard BP update equations with damping. The message passed from a node i to its neighbor j at the nth step of the algorithm is given by the following equation: where η is a normalization constant to prevent the messages from growing too large.

Things to Try

BP Settings

Many of the characteristics of the belief propagation algorithm can be observed by tweaking the BP settings above. For example, with damping set to 1, the standard BP update often oscillates without converging. Also, try pressing the random initialization button a few times: the algorithm may converge to different fixed points. Even after convergence, the value of the esitmate may oscillate in a small range due to numerical issues.

The Ising Model

Try adjusting the values of J while holding h fixed: positive J encourages neighboring spins to align while negative J has the opposite effect.

If the external magnetic field is uniform and J > 0, then the most likely configuration is either all +1 or all -1.

If the external magnetic field is uniform and J < 0, then the most likely configuration is either all +1 or all -1.

If J = 0, then none of the particles interact and the estimate of the log partition function produced by the BP algorithm is exact.

Other observations are as follows:

As T tends to zero, the belief propagation algorithm provides an estimate of the most likely (or highest energy) configuration.

For the 2D Ising model on a grid with all ferromagnetic (J nonnegative) or all antiferromagentic interactions (J negative), fixed point estimates of BP are known to be a lower bound on the exact partition function.

About This Demo

This demonstration was created for HTML 5 capable browsers (needs canvas support) by Nicholas Ruozzi. While I cannot gurantee that the code is error free, feel free to download the source code for this demonstration and use/modify/improve it!