Constant density ratio global neighborhoods

 

A density ratio class consists of all probability densities p(A) so that for any event A [DeRobertis & Hartigan1981]:

Gamma^R_l,u(p(A)) = { r(A) : l(A) <= alpha r(A) <= u(A) },

where l(A) and u(A) are arbitrary positive measures such that l() <= u() and alpha is some positive real number.

A global neighborhood can be constructed with a sub-class of the density ratio class. Take a base Bayesian network and a positive constant k>1. Consider the set of all joint distributions such that for some alpha:

Gamma^R_k(p(x)) = {{ r(x) : (1/k) prod_i p_i <= alphar(x) <= k prod_i p_i } .

Call this class a constant density ratio class. This class is invariant to marginalization and application Bayes rule; in fact it is the only class that has these two properties [Wasserman1992a]. Another way to characterize this class is to define it as the set of all distributions r() that obey the inequalities (valid for all events A and B):

{ r(A) }/{ r(B) } <= k² { p(A) }/{ p(B) } .

Since the class is marginalization and conditionalization invariant, the first step is to obtain p(x|e), the marginal posterior for the base distribution of the class. Now we can set up a linear programming problem:

max( sum_{x is in x} u(x) r(x|e) )

subject to

r(x|e) <= k² { p(x|e) }/{ p(y|e) } r(y|e),

where x, y are arbitrary elements of x (if x has n elements, there are n(n-1) inequalities). This procedure produces the upper bound; the lower bound is obtained by minimization.

For expected value calculations, maximization/minimization of expectation for u(x) = x_q can be easily performed. For calculation of posterior marginals, take u(x) = delta_a(x_q), where delta_a(x_q) is one if x_q = a and zero otherwise. In this case E[u] = p(x_q = a | e), the posterior probability for x_q. The linear programming problem can be solved in closed-form [Seidenfeld & Wasserman1993]:

r(x_q = a|e) = { k p(x_q = a|e) }/{ k p(x_q = a|e) + p(x_q = a^c|e) } ,

r(x_q = a|e) = { p(x_q = a|e) }/{ p(x_q = a|e) + k p(x_q = a^c|e) } .

The linear programming problem above can be intractable if x has too many variables. In this case a Gibbs sampling procedure can be applied to the problem. Consider a sample of the posterior distribution p(x|e) with N elements X_j, which can be produced through Gibbs sampling techniques [York1992]. The following expression converges to the upper expectation of a function u() [Wasserman & Kadane1992]:

max_j ( { 1 }/{ 1 + (1-(j/N))(k-1) } {( { (k-1) Z_j }/{ N } + { Z₀ }/{ N } } ).

where

Z₀ = sum_j u(X_j)

Z_j = sum_{l >= j} u_(l)

The value u_(l), used here and in the next sections, is the lth value of u(X_j) as the N values are ordered from smallest to largest.