ssees that the control of the complete of the complete of the complete and the complete of 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:

$P\left({f}^{+}\right)=$  d. 
$$P(f^{+}|d)P(d)\leq\quad\;\;\;P(f^{+}|d,\xi)P(d)\equiv P(f^{+}|\xi)$$
$$(29)$$

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

$$P(f^{+})=\sum_{d}P(f^{+}|d)P(d)\geq\sum_{d}P(f^{+}|d,q)P(d)\equiv P(f^{+}|q)$$
$$\mathrm{d\;\;is\;\;obtained\;\;si\,m i l\,a r l y\,:}$$
$$(30)$$

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 5 and q. We wish to obtain the tightest possible bounds, thus we optimize these expressions with respect to ξ and q. We minimize with respect to ξ 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 ξ 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 P(djlf+). 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 P(djlf+).

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 nt work.

A more ambitious goal is to obtain interval bounds for the marginal posterior probabilities themselves. To this end, let P(f+, dj) denote the combined event that the QMR-DT
model generates the observed findings f+ and that the j th disease takes the value dj. These bounds follow directly from:

$$P(f^{+},\,d_{j})=\sum_{d\setminus d_{j}}P(f^{+}|d)\,P(d)\leq\sum_{d\setminus d_{j}}P(f^{+}|d,\,\xi)\,P(d)\equiv P(f^{+},\,d_{j}|\xi)$$
$$(31\,)$$
