Next: Real World Networks Up: A Toy Problem Previous: A Toy Problem

## 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 () 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 fixed point the following holds for any :

 (12)

under the constraints

and similarly for the lower bound. The conditional probability in Equation  is given by
 (13)

From these equations one can derive the fixed point for and . It turns out, however, that it is easier to determine the fixed point of the upper and lower bound on the mean, hence and . But this has no effect on the principle results as tightness and convergence speed.

In Figure a the difference between the upper and lower bound on the means is shown for various choices of the weight and threshold. As we saw before tight bounds can be obtained for small weights and somewhat larger, but positive weights, whereas negative weights result in rather poor, but still non-trivial bounds. It should be mentioned, however, that these results correspond to the choice of the smallest clusters ( and ) for the bound propagation algorithm. The bounds can easily be improved by enlarging the clusters as we saw in Figure .

Close to the fixed point the bound propagation algorithm converges exponentially. The distance to the asymptotic value can be written as , where is the number of iterations and is a number between zero and one indicating the convergence speed. The closer to one is, the slower the algorithm converges. In Figure b is shown for the same weights and thresholds. It is clear that larger weights induce a slower convergence. That is what we see in general: probabilities that are close to deterministic slow down the convergence.

Next: Real World Networks Up: A Toy Problem Previous: A Toy Problem
Martijn Leisink 2003-08-18