previous section, we know that there must exist a variational upper bound for this function that is linear in x:

$$f(x)\leq\xi x-f^{*}(\xi)$$
$$(14)$$

Using Eq. (9) to evaluate the conjugate function f*(£) for noisy-OR, we obtain:

$$f^{*}(\xi)=-\xi\log\xi+(\xi+1)\log(\xi+1)$$
$$(15)$$

The desired bound is obtained by substituting into Eq. (13) (and recalling the definition x = 0 io +
; θ i j d j ):

, 0 j j d j ) f ( θ io  + P(f,+ld) 0 0 j d j ) - f * ( c i ) P(f,+ld, ξ,). lll
$$(1\,6)$$
$$\left(\,1\,7\,\right)$$ $$\left(\,1\,8\,\right)$$
Note that the "variational evidence" P(f,+ld, ξ,) is the exponential of a term that is linear in the disease vector d. Just as with the negative findings, this implies that the variational evidence can be incorporated into the posterior in time linear in the number of diseases associated with the finding.

There is also a graphical way to understand the effect of the transformation. We rewrite the variational evidence as follows:

, 0; ; d; )- f *( £; ) e £i ( θio + P(f,+ld, f,i) (19) e Ei Bio - I * (Ei) e Ei Bij (20)
Note that the first term is a constant, and note moreover that the product is factorized across the diseases. Each of the latter factors can be multiplied with the pre-existing prior on the corresponding disease (possibly itself modulated by factors from the negative evidence). The constant term can be viewed as associated with a delinked finding node fi Indeed, the effect of the variational transformation is to delink the finding node fi from the graph, altering the priors of the disease nodes that are connected to that finding node. This graphical perspective will be important for the presentation of our vanational algorithm we will be able to view variational transformations as simplifying the graph until a point at which exact methods can be run.

We now turn to the lower bounds on the conditional probabilities P(f,+ld). The exponnt f(0 i 0 + 1 i 0 i d j ) in the exponential representation is of the form to which we applied Jensen's inequality in the previous section. Indeed, since f is concave we need only identify the non-negative variables zj, which in this case are θjjdj, and the constant a, which is now 0 io. Applying the bound in Eq. (12) we have:

e f ( θ io + , bijdj ) P(f,+ld)
$$\begin{array}{r l}{\geq{}}&{{}e^{-i j\,{\bar{\imath}}\,{\bar{\jmath}}\,|i\,f\quad\theta_{i\,o}+{\frac{\theta_{i j}\,d_{j}}{v_{j}\,|i}}}}\end{array}$$
$$(21\,)$$
$$(22\,)$$