The formal identity of this pair of minimization problems expresses the "duality" of f and its conjugate f*.

The representation of f in Eq. (8) is known as a variational transformation. The parameter ξ is known as a variational parameter . If we relax the minimization and fix the the variational parameter to an arbitrary value, we obtain an upper bound:

$$f\left(x\right)\leq\xi^{T}\,x-\,f^{*}\left(\xi\right).$$
$$(10)$$

The bound is better for some values of the variational parameter than for others, and for a particular value of ξ the bound is exact.

We also want to obtain lower bounds on conditional probabilities. A straightforward way to obtain lower bounds is to again appeal to conjugate duality and to express functions in terms of a maximization principle. This representation, however, applies to convex functions in the current paper we require lower bounds for concave functions. Our concave functions, however, have aspecial form that allows us to exploit conjugate duality in a different way. In particular, we require bounds for functions of the form f(a+   j zj), where f is a concave function, where z j for i E {1, 2, . . . , n} are non-negative variables, and where a is a constant. The variables z; in this expression are effectively coupled  the impact of changing one variable is contingent on the settings of the remaining variables. We can use Jensen's inequality, however, to obtain a lower bound in which the variables are decoupled. 3 In particular:

f ( α +
$$(\,1\,1\,)$$  $$(\,1\,2\,)$$  . 
where the q j can be viewed as defining a probability distribution over the variables z j . The variational parameter in this case is the probability distribution q. The optimal setting of this parameter is given by qj = zj/ k zk. This is easily verified by substitution into Eq. (12), and demonstrates that the lower bound is tight.

## 4.1  Variational Upper And Lower Bounds For Noisy-Or

Let us now return to the problem of computing the posterior probabilities in the QMR
model. Recall that it is the conditional probabilities corresponding to the positive findings that need to be simplified. To this end, we write

P(fi+ld) = 1 - e - θio - j θijdj = e log(l - c - z ) (13)
w here x = 0 i 0 +   i 0 i j d j . Consider the exponent f(x) = log(1 - e-x). For noisy-OR, as well as for many other conditional models involving compact representations (e.g., logistic regression), the exponent f(x) is a concave function of x. Based on the discussion in the q = 1,