A Large Ising Grid

We created a so called two-dimensional Ising model, which is a rectangular grid with connections between all pairs of nodes that are direct neighbours. We used a grid of 40 by 40 binary nodes. The potentials were drawn from a uniform distribution between zero and one. In contrast with Bayesian belief networks neil92a the probability distribution over the unclamped Ising grid is not automatically normalized, but this has no consequences for the algorithm.

For small Ising grids computing the exact marginals is tractable, but as soon as the grid is larger than about 25 by 25 the exact algorithm fails due to the exponential scaling of the computational complexity. The bound propagation algorithm, on the other hand, only depends on the local structure (i.e. the size of the Markov blankets of each node) and thus scales linearly with the number of nodes. We created an 40x40 Ising grid with binary nodes similarly as above and ran the bound propagation algorithm. For this network the exact algorithm would require a storage capacity of at least $2^{41}$ real numbers, whereas bound propagation converged in about 71 minutes in which time it computed bounds on the marginals over all 1600 nodes.

In Figure  we show the 40x40 grid where the blackness of the squares correspond to the band width of the single node marginals. This band width is defined as the difference between the upper and lower bound. Due to the fact that marginal probabilities sum to one, the two band widths for these binary neurons are identical. We can clearly see some regions in the lattice (the blacker area's) for which bound propagation had some difficulties. Most of the marginals, however, are bounded quite well: more than 75% had a band width less than 0.1.