next up previous
Next: Experimental Evaluation Up: Variational Methods Previous: Variational Upper and Lower

Approximate Inference for QMR


In the previous section we described how variational transformations are derived for individual findings in the QMR model; we now discuss how to utilize these transformations in the context of an overall inference algorithm.

Conceptually the overall approach is straightforward. Each transformation involves replacing an exact conditional probability of a finding with a lower bound and an upper bound:


Given that such transformations can be viewed as delinking the ith finding node from the graph, we see that the transformations not only yield bounds, but also yield a simplified graphical structure. We can imagine introducing transformations sequentially until the graph is sparse enough that exact methods become feasible. At that point we stop introducing transformations and run an exact algorithm.

There is a problem with this approach, however. We need to decide at each step which node to transform, and this requires an assessment of the effect on overall accuracy of transforming the node. We might imagine calculating the change in a probability of interest both before and after a given transformation, and choosing to transform that node that yields the least change to our target probability. Unfortunately we are unable to calculate probabilities in the original untransformed graph, and thus we are unable to assess the effect of transforming any one node. We are unable to get the algorithm started.

Suppose instead that we work backwards. That is, we introduce transformations for all of the findings, reducing the graph to an entirely decoupled set of nodes. We optimize the variational parameters for this fully transformed graph (more on optimization of the variational parameters below). For this graph inference is trivial. Moreover, it is also easy to calculate the effect of reinstating a single exact conditional at one node: we choose to reinstate that node which yields the most change.

Consider in particular the case of the upper bounds (lower bounds are analogous). Each transformation introduces an upper bound on a conditional probability tex2html_wrap_inline1037 . Thus the likelihood of observing the (positive) findings tex2html_wrap_inline1075 is also upper bounded by its variational counterpart tex2html_wrap_inline1077 :


We can assess the accuracy of each variational transformation after introducing and optimizing the variational transformations for all the positive findings. Separately for each positive finding we replace the variationally transformed conditional probability tex2html_wrap_inline1029 with the corresponding exact conditional tex2html_wrap_inline1037 and compute the difference between the resulting bounds on the likelihood of the observations:


where tex2html_wrap_inline1083 is computed without transforming the tex2html_wrap_inline1085 positive finding. The larger the difference tex2html_wrap_inline1087 is, the worse the tex2html_wrap_inline1085 variational transformation is. We should therefore introduce the transformations in the ascending order of tex2html_wrap_inline1087 s. Put another way, we should treat exactly (not transform) those conditional probabilities whose tex2html_wrap_inline1087 measure is large.

In practice, an intelligent method for ordering the transformations is critical. Figure 2 compares the calculation of likelihoods based on the tex2html_wrap_inline1087 measure as opposed to a method that chooses the ordering of transformations at random. The plot corresponds to a representative diagnostic case, and shows the upper bounds on the log-likelihoods of the observed findings as a function of the number of conditional probabilities that were left intact (i.e. not transformed). Note that the upper bound must improve (decrease) with fewer transformations. The results are striking--the choice of ordering has a large effect on accuracy (note that the plot is on a log-scale).

Figure 2: The upper bound on the log-likelihood for the delta method of removing transformations (solid line) and a method that bases the choice on a random ordering (dashed line).

Note also that the curve for the proposed ranking is convex; thus the bound improves less the fewer transformations there are left. This is because we first remove the worst transformations, replacing them with the exact conditionals. The remaining transformations are better as indicated by the delta measure and thus the bound improves less with further replacements.

We make no claims for optimality of the delta method; it is simply a useful heuristic that allows us to choose an ordering for variational transformations in a computationally efficient way. Note also that our implementation of the method optimizes the variational parameters only once at the outset and chooses the ordering of further transformations based on these fixed parameters. These parameters are suboptimal for graphs in which substantial numbers of nodes have been reinstated, but we have found in practice that this simplified algorithm still produces reasonable orderings.

Once we have decided which nodes to reinstate, the approximate inference algorithm can be run. We introduce transformations at those nodes that were left transformed by the ordering algorithm. The product of all of the exact conditional probabilities in the graph with the transformed conditional probabilities yields an upper or lower bound on the overall joint probability associated with the graph (the product of bounds is a bound). Sums of bounds are still bounds, and thus the likelihood (the marginal probability of the findings) is bounded by summing across the bounds on the joint probability. In particular, an upper bound on the likelihood is obtained via:


and the corresponding lower bound on the likelihood is obtained similarly:


In both cases we assume that the graph has been sufficiently simplified by the variational transformations so that the sums can be performed efficiently.

The expressions in Eq. (29) and Eq. (30) yield upper and lower bounds for arbitrary values of the variational parameters tex2html_wrap_inline967 and q. We wish to obtain the tightest possible bounds, thus we optimize these expressions with respect to tex2html_wrap_inline967 and q. We minimize with respect to tex2html_wrap_inline967 and maximize with respect to q. Appendix 6 discusses these optimization problems in detail. It turns out that the upper bound is convex in the tex2html_wrap_inline967 and thus the adjustment of the variational parameters for the upper bound reduces to a convex optimization problem that can be carried out efficiently and reliably (there are no local minima). For the lower bound it turns out that the maximization can be carried out via the EM algorithm.

Finally, although bounds on the likelihood are useful, our ultimate goal is to approximate the marginal posterior probabilities tex2html_wrap_inline933 . There are two basic approaches to utilizing the variational bounds in Eq. (29) and Eq. (30) for this purpose. The first method, which will be our emphasis in the current paper, involves using the transformed probability model (the model based either on upper or lower bounds) as a computationally efficient surrogate for the original probability model. That is, we tune the variational parameters of the transformed model by requiring that the model give the tightest possible bound on the likelihood. We then use the tuned transformed model as an inference engine to provide approximations to other probabilities of interest, in particular the marginal posterior probabilities tex2html_wrap_inline933 . The approximations found in this manner are not bounds, but are computationally efficient approximations. We provide empirical data in the following section that show that this approach indeed yields good approximations to the marginal posteriors for the QMR-DT network.

A more ambitious goal is to obtain interval bounds for the marginal posterior probabilities themselves. To this end, let tex2html_wrap_inline1115 denote the combined event that the QMR-DT model generates the observed findings tex2html_wrap_inline909 and that the tex2html_wrap_inline1119 disease takes the value tex2html_wrap_inline915 . These bounds follow directly from:


where tex2html_wrap_inline1123 is a product of upper-bound transformed conditional probabilities and exact (untransformed) conditionals. Analogously we can compute a lower bound tex2html_wrap_inline1125 by applying the lower bound transformations:


Combining these bounds we can obtain interval bounds on the posterior marginal probabilities for the diseases (cf. Draper & Hanks 1994):


where tex2html_wrap_inline1127 is the binary complement of tex2html_wrap_inline915 .

next up previous
Next: Experimental Evaluation Up: Variational Methods Previous: Variational Upper and Lower

Michael Jordan
Sun May 9 16:22:01 PDT 1999