between the optimal importance functions for these two quantities is large, the performance may deteriorate significantly. Although Pr(a,e) and Pr(e) are unbiased estimators according to Property 1 (Section 2.1), Pr(ale) obtained by means of Equation 7 is not an ubiased estimator. However, as the number of samples increases, the bias decreases and can be ignored altogether when the sample size is large enough (Fishman, 1995).

Figure 1 presents a generic stochastic sampling algorithm that captures most of the existing sampling algorithms. Without the loss of generality, we restrict ourselves in our description to so-called forward sampling, i.e., generation of samples in the topological order of the nodes in the network. The forward sampling order is accomplished by the initialization performed in Step 1, where parents of each node are placed before the node itself. In forward sampling, Step 8 of the algorithm, the actual generation of samples, works as follows. ( i ) each evidence node is instantiated to its observed state and is further omitted from sample generation; ( ii ) each root node is randomly instantiated to one of its possible states, according to the importance prior probability of this node, which can be derived from Pr k (X\E); (iii) each node whose parents are instantiated is randomly instantiated to one of its possible states, according to the importance conditional probability distribution of this node given the values of the parents, which can also be derived from Pr k (X\E); (iv)
this procedure is followed until all nodes are instantiated. A complete instantiation s i of the ntwork based on this method is one sample of the joint importance probability distribution Pr k (X\E) over all variables of the network. The scoring of Step 10 amounts to calculating Pr(s,, e)/Pr k (s,), as required by Equation 2. The ratio between the total score sum and the nmber of samples is an unbiased estimator of Pr(e). In Step 10, if we also count the score sum under the condition A = a, i.e., that some unobserved variables A have the values a, the ratio between this score sum and the number of samples is an unbiased estimator of Pr(a, e).

Most existing algorithms focus on the posterior probability distributions of individual nodes. As we mentioned above, for the sake of efficiency they count the score sum corresponding to Pr(A = a,e), A E X\E, and record it in an score array for node A.  Each entry of this array corresponds to a specified state of A . This method introduces additional variance, as opposed to using the importance function derived from Pr h (X\E) to sample Pr(A = a, e), A E X\E, directly.

## 23 Existing Importance Sampling Algorithms For Bayesian Networks

The main difference between various stochastic sampling algorithms is in how they process Steps 2, 7, and 8 in the generic importance sampling algorithm of Figure 1.

Probabilistic logic sampling (Henrion, 1988) is the simplest and the first proposed sampling algorithm for Bayesian networks. The importance function is initialized in Step 2 to Pr(X) and never updated (Step 7 is null). Without evidence, Pr(X) is the optimal importance function for the evidence set, which is empty anyway. It escapes most authors that Pr(X) may be not the optimal importance function for Pr(A = a), A E X, when A
is not a root node. A mismatch between the optimal and the actually used importance function may result in a large variance. The sampling process with evidence is the same as without evidence except that in Step 10 we do not count the scores for those samples that are inconsistent with the observed evidence, which amounts to discarding them. When