Background

 

We consider a set x of discrete variables. Each variable x_i has a finite set of values x_i. A Bayesian network defines a probability distribution through the expression [Pearl1988]:

  p(x) = prod_i p(x_i | pa(x_i)),

where pa(x_i) is a set of variables, the parents of variable x_i. p() refers to a single probability distribution; q() refers to an arbitrary distribution and r() refers to an arbitrary member of a set of distributions.

For any function f(), we use the abbreviation f_i for f(x_i|pa(x_i)) and f_i(a) for f(x_i = a | pa(x_i)). In this notation, expression (1) can be rewritten as p(x) = prod_i p_i.

Suppose a set of variables is associated with evidence e = { x₁ = a, x₃ = b, ..., x_n = k }. Write f^e() for a function where the values e are fixed. For example, p^e(x) = p(x₁ = a, x₂, x₃ = b, x₄, ..., x_n = k) for the evidence above. Notice p^e(x) is not the conditional p(x|e), but the function p(x) with some variables fixed to e.

Our algorithms assume efficient solutions for two standard problems in usual Bayesian networks: computation of posterior marginals and maximum a posteriori hypothesis. The calculation of posterior marginals for a queried variable can be done by a technique like variable elimination [Zhang & Poole1996] or bucket elimination [Dechter1996], or a more sophisticated clustering method such as peeling [Cannings & Thompson1981] or graph triangulation [Jensen1996].

Another standard problem is the determination of maximum a posteriori hyposthesis (called MAP) [Dechter1996]. Suppose we select a set of variables d as decision variables, and the objective is to find values for the decision variables such that we obtain the maximum value of marginal probability p(d). The notation p^d_i indicates that the function p_i has the decision variables fixed. With this notation, the objective of the MAP algorithm is to obtain:

  max_d sum_{x is in d} ( prod_i p^d_i ).

There are algorithms which attack this problem in the most general form [Dechter1996]. A class of algorithms attack this problem when decision problem can be represented as an influence diagram [Jensen & Jensen1994].