

![0_image_0.png](0_image_0.png)

Figure 1:  Examples of separator and marginal nodes in an (infinite) Ising grid.  Light shaded In this article we present a method called 'bound propagation' which has certain similarities to belief propagation in the sense that small clusters of a few nodes try to bound their marginals as tight as possible. The knowledge contained in these bounds is shared with surrounding clusters. Iteration of this procedure improves bounds on all marginals until it is converged. It is important to realize that bounding and approximation techniques are not mutually exclusive. We propose to always run the bound propagation algorithm first.

When the result is not satisfactory, one can always fall back upon approximation techniques as belief propagation paying the price of being uncertain about the solution.

In Section 2 we explain the general method of bound propagation, which is described more algorithmicly in Section 3. In Section 4 we show the behaviour of the algorithm on a toy problem, whereas in Section 5 the results are shown for more realistic networks. Finally, in Section 6, we conclude and discuss possible paths for future research.

## 2. What Bounds Can Learn From Each Other

Consider a Markov network defined by the potentials ψ i ( S i ) each dependent on a set of nodes S i . The probability to find the network in a certain state S is proportional to

$$p\left(S\right)\propto\prod_{i}\psi_{i}\left(S_{i}\right)$$
$$\left(\,1\,\right)$$

Problems arise when one is interested in the marginal probability over a small number of nodes (denoted by S mar ), since in general this requires the summation over all of the exponentially many states.

Let us define the set of separator nodes, S,,, to be the nodes that separate S,,,, from the rest of the network. One can take, for instance, the union of the nodes in all potentials that contain at least one marginal node, while excluding the marginal nodes itself in that union (which is the Markov blanket of S mar ):

$$S_{\mathrm{sep}}\,=\,\bigcup_{S_{i}\cap S_{\mathrm{mar}}\neq\emptyset}S_{i}\,/\,S_{\mathrm{mar}}$$
$$\left(2\right)$$
