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 b-d 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 2003-08-18