which follows from Eq. (4) and the fact that P(fj+|d) = 1 - P(f-|d). To perform the summation in Eq. (5) over the diseases, we would have to multiply out the terms 1 - e { } corresponding to the conditional probabilities for each positive finding. The number of such terms is exponential in the number of positive findings. While algonthms exist that attempt to find and exploit factorizations in this expression, based on the particular pattern of observed evidence (cf. Heckerman, 1989; D'Ambrosio, 1994), these algorithms are limited to roughly 20 positive findings on current computers. It seems unlikely that there is sufficient latent factorization in the QMR-DT model to be able to handle the full CPC corpus, which has a median number of 36 positive findings per case and a maximum number of 61 positive findings.

## 4. Variational Methods

Exact inference algorithms perform many millions of arithmetic operations when applied to complex graphical models such as the QMR-DT. While this proliferation of terms expresses the symbolic structure of the model, it does not necessarily express the numeric structure of the model. In particular, many of the sums in the QMR-DT inference problem are sums over large numbers of random variables. Laws of large numbers suggest that these sums may yield predictable numerical results overthe ensemble of their summands, and this fact might enable us to avoid performing the sums explicitly.

To exploit the possibility of numerical regularity in dense graphical models we develop a variational approach to approximate probabilistic inference. Variational methods are a general class of approximation techniques with wide application throughout applied mathematics. Variational methods are particularly useful when applied to highly-coupled systems. By introducing additional parameters, known as "variational parameters" which essentially serve as low-dimensional surrogates for the high-dimensional couplings of the sssem these methods achieve a decoupling of the system. The mathematical machinery of the variational approach provides algorithms for finding values of the variational parameters such that the decoupled system is a good approximation to the original coupled system.

In the case of probabilistic graphical models vanational methods allow us to simplify a complicated joint distribution such as the one in Eq. (7). This is achieved via parameterized transformations of the individual node probabilities. As we will see later, these node transformations can be interpreted graphically as delinking the nodes from the graph.

How do we find appropriate transformations? The variational methods that we consider here come from convex analysis (see Appendix 6). Let us begin by considering methods for obtaining upper bounds on probabilities. A well-known fact from convex analysis is that any concave function can be represented as the solution to a minimization problem:

$$f(x)=\operatorname*{min}_{\xi}\{\ \xi^{T}\,x-\,f^{*}(\xi)\ \}$$
$$\left({\boldsymbol{\delta}}\right)$$

where f*(£) is the conjugate function of f(x). The function f*(£) is itself obtained as the solution to a minimization problem:

$$f^{*}(\xi)\,=\,\operatorname*{min}_{x}\,\big\{\,\xi^{T}\,x\,-\,f\big(x\,\big)\,\big\}\,.$$
$$(\,0\,)$$
