corresponding to the second method skips the optional steps and calls the basic AIS-BN
algorithm twice to estimate Pr(e) and Pr(a,e) separately.

The first method is very attractive because of its simplicity and possible computational efficiency. However, as we have shown in Section 2.2, the performance of a sampling algorithm that uses just one set of samples (as in the first method above) to estimate Pr(a|e)
will deteriorate if the difference between the optimal importance functions for Pr(a,e) and Pr(e) is large. If the main focus of the computation is high accuracy of the posterior probability distribution of a small number of nodes, we strongly recommend to use the algorithm based on the second method. Also, this algorithm can be easily used to estimate confidence intervals of the solution.

## 4. Experimental Results

In this section, we first describe the experimental method used in our tests.  Our tests focus on the CPCS network, which is one of the largest and most realistic networks available and for which we know precisely which nodes are observable.  We were, therefore, able to generate very realistic test cases. Since the AIS-BN algorithm uses two initialization heuristics, we designed an experiment that studies the contribution of each of these two heuristics to the performance of the algorithm. To probe the extent of AIS- BN algorithm's excellent performance, we test it on several real and large networks.

## 4.1 Experimental Method

We performed empirical tests comparing the AIS- BN algorithm to the likelihood weighting
(LW) and the self-importance sampling (SIS) algorithms. The two algorithms are basically the state of the art general purpose belief updating algorithms. The AA (Dagum et al.,
1995) and the bounded variance (Dagum & Luby, 1997) algorithms, whi were suggested by a reviewer, are essentially enhanced special purpose versions of the basic LW algorithm.

Our implementation of the three algorithms relied on essentially the same code with separate functions only when the algorithms differed. It is fair to assume, therefore, that the observed differences are purely due to the theoretical differences among the algorithms and not due to the efficiency of implementation.  In order to make the comparison of the AIS-BN algorithm to LW and SIS fair, we used the first method of computation (Section 3.5), i.e., one that relies on single sampling rather than calling the basic AIS-BN algorithm twice.

We measured the accuracy of approximation achieved by the simulation in terms of the Mean Square Error ( MSE ), i.e., square root of the sum of square differences between Pr'( x ij )
and Pr( x ij ), the sampled and the exact marginal probabilities of state j (j = 1,2,...,nj) of node i, such that Xi f E. More precisely,

$$M S E=$$

![0_image_0.png](0_image_0.png)

$$\bigcap_{1}(\operatorname{Pr}^{\prime}(x_{i j})-\operatorname{Pr}\left(x_{i j}\right))^{2}$$

where N is the set of all nodes, E is the set of evidence nodes, and n, is the number of outcomes of node i . In all diagrams, the reported MSE is averaged over 10 runs. We used the clustering algorithm (Lauritzen & Spiegelhalter, 1988) to compute the gold standard