bounds on the likelihood, but they are not themselves bounds. That is, they are not guaranteed to lie above or below the true posteriors, as we see in Figure 4. As we discussed in Section 4.1, however, it is also possible to induce upper and lower bounds on the posterior marginals from upper and lower bounds on the likelihood (cf. Eq. 33). In this section we evaluate these interval bounds for the QMR-DT posterior marginals.

Figure 12 displays histogram of the interval bounds for the four tractable CPC cases, the 24 selected CPC cases from the previous section, and all of the CPC cases. These histograms include all of the diseases in the QMR-DT network. In the case of the tractable cases the

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

variational method was run with 12 positive findings treated exactly. For the remaining CPC cases the variational method was run with 16 positive findings treated exactly. The running time of the algorithm was less than 10 seconds of computer time per CPC case.

For the tractable CPC cases, the interval bounds are tight for nearly all of the diseases in the network. However, (1) few of the positive findings are treated variationally in these cases, and (2) there is no need in practice to compute variational bounds for these cases.

We get a somewhat better picture of the viability of the variational interval bounds in Figure 12(b) and Figure 12(c), and the picture is decidedly mixed. For the 24 selected cases, tight bounds are provided for approximately half of the diseases. The bounds are vacuous for approximately a quarter of the diseases, and there are a range of diseases in between. When we consider all of the CPC cases, approximately a third of the bounds are tight and nearly half are vacuous.

Although these results may indicate limitations in our variational approximation, there is another more immediate problem that appears to be responsible for the looseness of the bounds in many cases. In particular, recall that we use the Quickscore algorithm (Heckerman, 1989) to handle the exact calculations within the framework of our variational agorithm. Unfortunately Quickscore suffers from vanishing numencal precision for large nmbers of positive findings, and in general we begin to run into numerical problems, resulting in vacuous bounds, when 16 positive findings are incorporated exactly into the variational approximation. Thus, although it is clearly of interest to run the variational agorithm for longer durations, and thereby improve the bounds, we are unable to do so within our current implementation of the exact subroutine.

(a)