The Alarm Network

Figure: The exact marginals (thick horizontal lines) and the bounds (rectangles) for the alarm network. Some bounds are so tight that the rectangle is not visible. We used $\Omega\left(25,000\right)$.

Figure: The band width (upper minus lower bound) of each node in a 40x40 Ising grid is shown by the blackness of the squares. The exact marginal could not be computed for such a large network. The solid lines show the boundary where the band width was 0.1. We used $\Omega\left(2500\right)$.

The Alarm network³ is a commonly used network which is a representitive of a real life Bayesian network. It was originally described by beinlich as a network for monitoring patients in intensive care. It consists of 37 nodes of two, three or four states and is small enough to do exact computations. In Figure  the graphical model is shown. Our task was to determine the single node marginals in absence of any evidence. For each node the exact marginal probabilities for its states are shown as horizontal lines. The top and bottom of the rectangles around these lines indicate the upper and lower bounds respectively. For this network we used $\Omega\left(25,000\right)$⁴. If we make this choice, we can treat exactly the minimal Markov blanket of all single node marginals. The algorithm converged in about six minutes.

We see that the bounds in the lower left corner are very close to the exact value. We can give some intuition why this happens. Observe that node 7 on its own can play the role of separator for nodes 1 to 6. Thus all correlations between these nodes and the rest of the network are through node 7, which means that their uncertainty only depends on the uncertainty of node 7. The latter happens to be very small (consider that as a given fact) and therefore the marginal bounds for nodes 1 to 6 are very tight.

The bounds in the upper right corner, on the other hand, are quite poor. This is partially due to the density of the connections there and the number of states each of the nodes has. In combination this leads to large state spaces already for small clusters. Therefore, we cannot compute bounds on sets of multiple nodes, which generally leads to weaker bounds. Secondly, the local probability tables are of a form that is difficult for the bound propagation algorithm. That is, a lot of probabilities are close to zero and one.

This picture is what we generally see. There are some parts in the network that are hard to compute (not necessarily impossible) which usually have a more dense structure and a larger (local) state space. Other parts can be bounded very well. Note that this network could easily be embedded in a very large network that is intractable for any exact method. Even in that case, the bound propagation algorithm could be used to find similar results. Since the method is based on local computations, the existance of a large surrounding network has almost no influence.