Next: The Iterative Part
Up: Bound Propagation
Previous: A Simple Example
The Algorithm In Detail
To solve an arbitrary network we first determine the set of all
we will use for the problem. We choose

(10) 
where
is the cluster
and denotes a single node.
This choice limits the state space of
to , which more or
less determines the computation time. If we choose, for example,
for the Ising grid in Figure assuming binary nodes,
only the configuration in Figure a would be included
in . Choosing puts the configurations
in Figure bd and a few others not shown into
, but not Figure a, since that separator is
already embedded in larger ones (e.g. Figure d).
In other words:
is the set of all
for
which
is not larger than
, but if we add a single node it would cross that boundary.
We will compute bounds for all
for which there can be found
a separator in . We reserve memory for
and
and initialize them to one and zero
respectively. Note that if we have a bound over
it is
still worthwhile to compute bounds over subsets of
(e.g. Figure b and d). In contrast to a joint probability
table, the bounds on marginals over subsets cannot be computed simply
by summing over the marginal of
, since we have only bounds
and not the real values.
Subsections
Next: The Iterative Part
Up: Bound Propagation
Previous: A Simple Example
Martijn Leisink
20030818