

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

Figure 8: A bi-partite network of a thousand nodes in each layer was created and evidence was presented on every third child node.  The left histogram shows the band widths found for the single node marginals of all unclamped nodes.  The bound propagation algorithm converged in about 75 minutes and used Ω(2500).

The right histogram shows the relative position of the approximation within the bounding region. All approximations were between the upper and lower bound, although this is not necessarily the case.

some approaches to use approximation techniques for this network (Jaakkola & Jordan, 199; Murphy et al., 1999). Therefore we have chosen to use the bi-partite network as an architecture to test the bound propagation algorithm on.

We created bi-partite networks of an equal number of (binary valued) nodes in both layers. Each child node has exactly three parents and each parent points to exactly three children. The connections were made randomly. The conditional probability tables ( CPT 's)
holding the probability of the ild given its parents was initialized with uniform random nmber between zero and one. The prior probability tables for the parents were initialized similarly.

In Figure 7 we show a bi-partite network with twenty nodes in each layer, which is still small enough to compute the exact marginals.  The arrows show the parent-child relations. To every third child evidence was presented (the shaded nodes). We ran the bound propagation algorithm with Ω(2500) and reached convergence in 37 seconds.  For ery node we show the marginal over its two states.  The thick line is the exact marginal, the top and bottom of the rectangle around it indicate the upper and lower bound respectively.

It is clear that for most of the nodes the computed bounds are so tight that they give almost the exact value. For every node (except two) the gap between upper and lower bound is less than one third of the whole region.

The network shown in Figure 7 is small enough to be treated exactly. This enables us to show the computed bounds together with the exact marginals. The bound propagation algorithm, however, can be used for much larger architectures. Therefore we created a bipartite graph as we did before, but this time with a thousand nodes in each layer. Again we presented evidence to every third node in the bottom layer. The bound propagation