** Next:** The Bi-Partite Graph
** Up:** Real World Networks
** Previous:** The Alarm Network

##

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 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.

** Next:** The Bi-Partite Graph
** Up:** Real World Networks
** Previous:** The Alarm Network
Martijn Leisink
2003-08-18