In this appendix we discuss the optimization problems that we must solve in the case of noisy-OR networks. We consider the upper and lower bounds separately, beginning with the upper bound.

## Upper Bound Transformations

Our goal is to compute a tight upper bound on the likelihood of the observed findings:
P(f+) =
, P(f+|d)P(d). As discussed in Section 4.2, we obtain an upper bound on P(f+[d) by introducing upper bounds for individual node conditional probabilities. We represent this upper bound as P(f+ld, f), which is a product across the individual variational transformations and may contain contributions due to findings that are being treated exactly (i.e., are not transformed). Marginalizing across d we obtain a bound:

$$P(f^{+})\leq\quad\operatorname*{P}_{d}(f^{+}|d,\xi)P(d)\equiv P(f^{+}|\xi).$$
$$(39\,)$$

It is this latter quantity that we wish to minimize with respect to the variational parameters s.

To simplify the notation we assume that the first m positive findings have been transformed (and therefore need to be optimized) while the remaining conditional probabilities will be treated exactly. In this notation P(f+[$) is given by

$$\begin{array}{ccccccccc}P(f^{+}|\xi)&=&&P(f_{i}^{+}|d,\xi_{i})&&P(f_{i}^{+}|d)&&P(d_{j})\\ &&\propto&&E&&P(f_{i}^{+}|d,\xi_{i})&,\\ &&\leq m&&\end{array}$$
$$(40\,)$$
$$\left(41\,\right)$$

well in the expectation is taken with respect to the posterior distribution for the diseases given those positive findings that we plan to treat exactly. Note that the proportionality constant does not depend on the variational parameters (it is the likelihood of the exactly treated positive findings). We now insert the explicit forms of the transformed conditional probabilities (see Eq. (17)) into Eq. (41) and find:

, θ i j d j ) − f * ( ξ i ) E Ei ( θio + P(f+l&) x E i <m i ≤ rn (ξi θio − ſ* (ξi))  E e j, i ≤ m
$$\left(42\right)$$  $$\left(43\right)$$
where we have simply converted the products over i into sums in the exponent and pulled out the terms that are constants with respect to the expectation. On a log-scale, the proportionality becomes an equivalence up to a constant:

$$\log P(f^{+}|\xi)=C+\operatorname*{\operatorname*{lim}}_{i\leq m}(\xi_{i}\theta_{i0}-f^{*}(\xi_{i}))+\log E\quad e\quad_{j,i\leq m}\,\xi_{i}\,\theta_{i j}\,d_{j}$$
$$(44\,)$$

317