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} | _{i})),

For any function f(), we use the abbreviation f_{i} for
f(x_{i}|_{i})) and f_{i}(a) for f(x_{i} = a | _{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_{1} = a, x_{3} = b, ..., x_{n} = k }.
Write f^{e}() for a function where the values e are fixed. For example,
p^{e}(x) = p(x_{1} = a, x_{2}, x_{3} = b, x_{4}, ..., 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:

_{d} _{x is in d}
( prod_{i} p^{d}_{i} ).

Tue Jan 21 15:59:56 EST 1997