

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

## 4. A Toy Problem

To get some intuition about the performance of the algorithm we created a ring (one large loop) of 200 binary nodes. Nodes are connected as in the Boltzmann machine with a weight w and each node has a threshold 0. Weights and thresholds are varying along the ring as is shown at the bottom of Figure 3. For this simple problem we can compute the exact single node marginals. These are plotted as a solid line in Figure 3. We ran the bound propagation algorithmthree times, where we varied the maximum number of nodes included in Smar: [Smar] = 1, [Smar] = 2 and [Smar] = 3. In all cases we chose two separator nodes: the two neighbors of Smar . Thus these three cases correspond to Ω( 2 3 ), Ω( 2 4 ) and Ω( 2 5 ).

As is clear from Figure 3 the simplest choice already find excellent bounds for the majority of the nodes. For large negative weights, however, this choice is not sufficient. Allowing larger separators clearly improves the result. In all cases the computation time was a few seconds 2 .

## 4.1  Fixed Points And Convergence

It is possible to derive the fixed point of the bound propagation algorithm analytically for a Boltzmann ring if we take a single value for all weights ( w ) and one for all thresholds ( θ ).

Due to this symmetry all single node marginals are equal in such a network. Moreover all upper and lower bounds on the single nodes should be identical. This implies that for the 2. We used a computer with a 1 GHz Athlon processor