Constant density bounded global neighborhoods

 

A density bounded class is the set of all distributions such that [Lavine1991]

Gamma^B_l,u(p(x)) = { r(x) : l(x) <= r(x) <= u(x) },

where l() and u() are arbitrary non-negative functions such that sum_x l(x) <= 1 and sum_x u(x) >= 1.

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

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

Call this class a constant density bounded class. We consider calculation of the upper bound; the lower bound can be obtained through similar methods.

The constant density bounded class is invariant to marginalization, but not to conditionalization [Wasserman & Kadane1992]. To obtain posterior bounds, we must resort to Lavine's algorithm [Cozman1996]. The algorithm brackets the value of the posterior upper expectation of u() by successive calculations of a prior upper expectation:

E_k[u] = max[ sum_{x is in e} {( (u(x) - k) prod_i p^e_i } ],

where k is a given real number. The key observation is that the value of E_k[u] is zero only when k is equal to the posterior upper expectation. The algorithm starts at an arbitrary k and increases or decreases it until the expression above is zero.

To obtain E_k[u], we use the marginalization invariant property of the constant density bounded class. First marginalize p(x) to p^e(x) with any standard algorithm for Bayesian networks. Now we can set up a linear programming problem:

max{( sum_{x is in x} (u(x) - k) r^e(x) }

subject to

(1/k) p^e(x) <= r^e(x) <= k p^e(x),

where the x are arbitrary elements of x.

For expected value calculations, maximization/minimization of expectation for u(x) = x_q can be easily performed. For calculation of posterior, 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 [Wasserman1990]:

r^e(x_q = a) = min{( k p^e(x_q = a), 1 - (1/k) sum_{xq != a} p^e(x_q) }

r^e(x_q = a) = max{( (1/k) p^e(x_q = a), 1 - k sum_{xq != a} p^e(x_q) }.

The linear programming problem above can be intractable if x has too many variables. In this case a Monte Carlo sampling procedure can be applied to the problem [Wasserman & Kadane1992]. Consider a sample of p(x) with N elements X_j. The following expression converges to the upper expectation of a function u():

(1/k) { Z₁ }/{ N } + k { Z₂ }/{ N }

where

Z₁ = sum_l=1^(nk/(k+1)) u_(l)

Z₂ = sum_{l=(nk/(k+1))+1}^N u_(l).