Thus far we have utilized the variational approach to produce approximations to the posterior marginals. The approximations that we have discussed originate from upper and lower 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
Figure 12:
Histograms of the size of the interval bounds on all of the
diseases in the QMR-DT network for (a) the four tractable CPC
cases, (b) the 24 selected CPC cases from the previous section,
and (c) all of the CPC cases.
include all of the diseases in the QMR-DT network. In the case of the tractable cases the 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 algorithm. Unfortunately Quickscore suffers from vanishing numerical precision for large numbers 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 algorithm for longer durations, and thereby improve the bounds, we are unable to do so within our current implementation of the exact subroutine.
While it is clearly worth studying methods other than Quickscore for treating the exact findings within the variational algorithm, it is also of interest to consider combining variational methods with other methods, such as search-based or other partial evaluation methods, that are based on intervals. These methods may help in simplifying the posterior and obviating the need for improving the exact calculations.
It is also worth emphasizing the positive aspect of these results and their potential practical utility. The previous section showed that the variational method can provide accurate approximations to the posterior marginals. Combined with the interval bounds in this section--which are calculated efficiently--the user can obtain guarantees on approximately a third of these approximations. Given the relatively benign rate of increase in false positives as a function of true positives (Figure 11), such guarantees may suffice. Finally, for diseases in which the bounds are loose there are also perturbation methods available (Jaakkola, 1997) that can help to validate the approximations for these diseases.