Ising model

Model description

In its simplest form, the Ising Model consists of a NxN lattice of binary variables $x_i \in \{-1,+1\}$ that are locally connected horizontally and vertically with pairwise potentials. There can also be an external field applied to the variables that biases them toward a particular state. The total energy of a simple Ising model we consider here is defined as $$E = - J \sum_{(i,j) \in E} x_i x_j - J_b \sum_{i \in V} b_i x_i$$ Where the first sum is over all edges of the lattice and the second over all nodes. $J, J_b, b_i$ are the strength of pairwise interactions, strength of external field, and per-pixel binary desired values. The corresponding un-normalized probability distribution over states of the lattice is: $$\pi(x) = exp\{ J \sum_{(i,j) \in E} x_i x_j + J_b \sum_{i \in V} b_i x_i \}$$

Sampling from the model

Gibbs Sampling can be used to draw samples from this distribution as follows: given a sample $x$, produce a candidate new sample $x'$ by flipping a single variable ($ x_i' = -x_i$). Next, compute the acceptance probability: $$ \alpha(x'|x) = min(1, \frac{\pi(x')}{\pi(x)}) $$ and let the next sample be $x'$ with probability $\alpha(x'|x)$, or repeat $x$ otherwise. Clearly, if $\pi(x') > \pi(x)$, the state will transition to $x'$ with certainty. However, if $\pi(x') < \pi(x)$, the sample will only be accepted with some probability that is based on how much worse it is.

The Gibbs sampling process is illustrated on the right, where the potential strengths $J, J_b$ can be manipulated. When $J$ is positive, the low energy states are smooth regions, as this minimizes the number of edges that connect nodes of different values. When $J$ is negative, the reverse happens as the model assigns higher probabilities to states with many crossing edges.

Applications

This example is a special case of an Ising Model, which is a special case of a pairwise Markov Random Field, which is a special case of a Markov Random Field (phew). These models are often used to "clean up" some set of raw, noisy measurements in various applications by incorporating more global knowledge, usually in form of soft smoothness constraints between neighboring measurements.

Psuedocode

// naive gibbs sampler for the ising model
x = randomState()
while true:
	// calculate probability of this state and a proposal
	px = pi(x) // pi is the un-normalized probability as defined above
	xnew = flipOneBit(x)
	pnew = pi(xnew)

	// calculate transition probability alpha
	transitionProbability = min(1, pnew/px)
	if uniformRandom(0,1) < transitionProbability:
		x = xnew // transition to x'!