
## Acknowledgements

We would like to thank the University of Pittsburgh and Randy Miller for the use of the QMR-DT database. We also want to thank David Heckerman for suggesting that we attack QMR-DT with variational methods, and for providing helpful counsel along the way.

## Appendix A. Duality

The upper and lower bounds for individual conditional probability distributions that form the basis of our variational method are based on the "dual" or "conjugate" representations of convex functions. We present a brief description of convex duality in this appendix, and refer the reader to Rockafellar (1970) for a more extensive treatment.

Let f(x) be a real-valued, convex function defined on a convex set X (for example, X = R n ). For simplicity of exposition, we assume that f is a well-behaved (differentiable)
function. Consider the graph of f, i.e., the points (x, f(x)) in an n +1 dimensional space.

The fact that the function f is convex translates into convexity of the set { ( x, y ) : y ≥ f ( x ) }
called the epigraph of f and denoted by epi(f) (Figure 13). It is an elementary property

![0_image_0.png](0_image_0.png)

Figure 13: Half-spaces containing the convex set epi(f). The conjugate function f*({)
defines the critical half-spaces whose intersection is epi(f), or, equivalently, it defines the tangent planes of f(x).
of convex sets that they can be represented as the intersection of all the half-spaces that contain them (see Figure 13). Through parameterizing these half-spaces we obtain the dual representations of convex functions. To this end, we define a half-space by the condition:

$${\mathrm{all~}}\left(x,\,y\right){\mathrm{such~t\,h\,at~}}x^{T}\xi-y-\mu\leq0$$

(34)
where ξ and μ parameterize all (non-vertical) half-spaces. We are interested in characterizing the half-spaces that contain the epigraph of f. We require therefore that the points in the epigraph must satisfy the half-space condition: for ( x, y ) E epi ( f ), we must have xT ξ − y − μ ≤ 0. This holds whenever xT ξ − f ( x ) − μ ≤ 0 as the points in the epigraph have the property that y ≥ f(x). Since the condition must be satisfied by all x E X, it follows