We can see that Equation 6 is almost identical to Equation 1 except that integration is replaced by summation and the domain Ω is replaced by X\E. The theoretical results derived for the importance sampling that we reviewed in the previous section can thus be directly applied to computing probabilities in Bayesian networks.

While there has been previous work on importance sampling-based algorithms for Bayesian networks, we will postpone the discussion of this work until the next section. Here we will present a generic stochastic sampling algorithm that will help us in both reviewing the prior work and in presenting our algorithm.

The posterior probability Pr(ale) can be obtained by first computing Pr(a,e) and Pr(e)
and then combining these based on the definition of conditional probability

$$\operatorname*{Pr}(\mathbf{a}|\mathbf{e}\,)={\frac{\operatorname*{Pr}\left(\mathbf{a},\mathbf{e}\right)}{\operatorname*{Pr}(\mathbf{e})}}\ .$$
$$\left(7\right)$$

In order to increase the accuracy of results of importance sampling in computing the posterior probabilities over different network variables given evidence, we should in general use different importance functions for Pr(a, e) and for Pr(e). Doing so increases the computation time only linearly while the gain in accuracy may be significant given that obtaining a desired accuracy is exponential in nature. Very often, it is a common practice to use the same importance function (usually for Pr(e)) to sample both probabilities. If the difference

## 1. Order The Nodes According To Their Topological Order.

2. Initialize importance function Pr 0 (X\E), the desired number of samples m, the updating interval l, and the score arrays for every node.

3. k ← 0, T ← 0
4. for i ← 1 to m do 5.

if (i mod l == 0) then 6.

k ← k + 1 7.

Update importance function Prk (X\E) based on T.

end if 8.

s; ← generate a sample according to Pr (X\E)
9.

T ← T U {s; }
Calculate Score(si, Pr(X\E, e), Prk(X\E)) and add it to the correspond10.

ing entry of every score array according to the instantiated states.

end for 1. Normalize the score arrays for every node.
Figure 1: A generic importance sampling algorithm.