+(1-dj) f( 0io ) jjjjjj j j j -f( 0ig ) + f( 0ig ) j  = P(fi+|d,qii)
$$(23\,)$$
$$\begin{array}{l}{(24\,)}\\ {(25\,)}\end{array}$$
where we have allowed a different variational distribution q,l; for each finding. Note that once again the bound is linear in the exponent. As in the case of the upper bound, this implies that the variational evidence can be incorporated into the posterior distribution in time linear in the number of diseases. Moreover, we can once again view the variational transformation in terms of delinking the finding node fi from the graph.

## 4.2 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 bo und :

$$P(f_{i}^{+}|\,d,\,q_{\cdot|i})\leq\,P(f_{i}^{+}|\,d)\leq\,P(f_{i}^{+}|\,d,\xi_{i}).$$
$\left(26\right)^2$
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 P(fj+ | d ). Thus the likelihood of observing the (positive) findings P(f+) is also upper bounded by its variational counterpart P(ƒ†|ξ):

$$P(f^{+})=\sum_{d}\;\;\;\;\;P(f^{+}|d)P(d)\leq\sum_{d}\;\;\;\;\;P(f^{+}|d,\xi)P(d)\equiv P(f^{+}|\xi)$$
$$(27)$$
