Total variation class

 

The total variation class is defined as the set of distributions such that:

Gamma^T_k(p(x)) = { r(x) : forall A, {| p(A) - r(A) } <= epsi}.

Almost all the discussion for the constant density bounded class carries to the total variation class since both classes are invariant to marginalization but not to conditionalization. We perform calculation of the upper bound through Lavine's algorithm. 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

p^e(A) - epsi <= r^e(A) <= p(A) + epsi,

where the A are arbitrary elements of x.

For expected value calculations, maximization/minimization of expectation for u(x) = x_q the 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{( 1, p^e(x_q = a) + epsi}

r^e(x_q = a) = max{( 0, p^e(x_q = a) - epsi}.

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():

epsimaxu^e(x) + { Z₀ }/{ N } ,

where

Z₀ = sum_{l = epsiN}^N u_(l).