STANDARD BAYESIAN NETWORKS

 

We consider a set x of discrete variables; each variable x_i has a finite set of values x_i and a set of variables pa(x_i), the parents of x_i. A Bayesian network defines a unique joint probability distribution [29]:

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

We use the abbreviation p_i for p(x_i|pa(x_i)); expression (1) can be written as p(x) = prod_i p_i. Suppose a set of variables is fixed as evidence e; p^e() is a distribution where variables e are fixed. Our algorithms assume efficient computation of posterior marginals in a Bayesian network [12, 21, 40].