

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

concerned, AIS-BN was significantly better than SIS. SIS was better than LW, but the difference was small. The mean MSE s of SIS and LW algorithms were both greater than 0.1, which suggests that neither of these algorithms is suitable for large Bayesian networks.

The graph in Figure 9 shows the MSE ratio between the AIS-BN and SIS algorithms.

We can see that the percentage of the cases whose ratio was greater than 100 (two orders of magnitude improvement!) is 60%. In other words, we obtained two orders of magnitude improvement in MSE in more than half of the cases. In 80% cases, the ratio was greater than 50. The smallest ratio in our experiments was 2.67, which happened when posterior probabilities were dominated by the prior probabilities. In that case, even though the LW
and SIS algorithms converged very fast, their MSE was still far larger than that of AIS-BN.

Our next experiment aimed at showing how close the AIS- BN algorithm can approach the best possible sampling results. If we know the optimal importance sampling function, the convergence of the AIS-BN algorithm should be the same as that of forward sampling without evidence. In other words, the results of the probabilistic logic sampling algorithm without evidence approach the limit of how well stochastic sampling can perform. We ran the logic sampling algorithm on the CPCS network without evidence mimicking the test runs of the AIS-BN algorithm, i.e., 5 blocks of 15 runs, each repeated 10 times with a different random number seed. The number of samples generated was equal to the average nmber of samples generated by the AIS-BN algorithm for each series of 15 test runs.

We obtained the average MSE µ = 0.00057, with σ = 0.000025, min = 0.00052, and