epsi-contaminated global neighborhoods

 

An epsi-contaminated class is characterized by a distribution p() and a real number epsi is in (0,1) [Berger1985]:

  Gamma^C_epsi(p(x)) = {{ r(x) : r(x) = (1-epsi)p(x) + epsiq(x) },

where q() is an arbitrary distribution. We are interested in epsi-contaminated neighborhoods in the space of all Bayesian networks:

Gamma^C_epsi(p(x)) = {{ r(x) : r(x) = (1-epsi) prod_i p_i + epsiq(x) }.

The posterior expected value for u(x) is:

E[u] = { U(e) }/{ p(e) }

where:

U(e) = sum_{x is in e} u^e(x) p^e(x)

p(e) = sum_{x is in e} p^e(x)

An epsi-contaminated class is a finitely generated convex set of distributions [Cozman1996]. The vertices of this set are unitary point masses on each one of the possible configurations of the network. The maximum and minimum expected values for u(x) occur in these vertices, since we are optimizing a linear function over a convex set.

The upper expectation is:

E[u] = max( { U(e) }/{ p(e) } , { (1-epsi) U(e) + epsiu^e }/{ (1-epsi) p(e) + epsi } ),

where u^e = maxu^e(x). The two terms inside parenthesis represent the two possibilities for a maximum. The first possibility is that q(x) places all the mass in a configuration for which the evidence has zero probability. The second possibility is that q(x) places all the mass in a configuration for which the evidence has non-zero probability.

The same reasoning leads to the lower expectation:

E[u] = min ( { U(e) }/{ p(e) } , { (1-epsi) U(e) + epsiu^e }/{ (1-epsi) p(e) + epsi } ),

where u^e = minu^e(x).

Some special cases are important. When u(x) = x_q, then E[u] = E[x_q], the upper expected value of variable x_q. The most important special case is 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 posterior probability bounds are obtained from the previous expressions through simple substitutions:

p(x_q = a | e) = { (1-epsi) p(x_q = a, e) + epsi }/{ (1-epsi) p(e) + epsi } ,

p(x_q = a | e) = { (1-epsi) p(x_q = a, e) }/{ (1-epsi) p(e) + epsi } ,

where

p(x_q = a, e) = sum_x is in {x_q, e} p^{{ x_q = a, e}}(x).

Notice that standard Bayesian network algorithms can be used to produce the elements of p(x_q, e) which are required in this expression [Cannings & Thompson1981, Dechter1996, Zhang & Poole1996].