a 146 node, multiply connected medical diagnostic Bayesian network.  One limitation in their tests is that the probability of evidence in the cases selected for testing was rather high. Although over 10% of the cases had the probability of evidence on the order of 10- 8 or smaller, a simple calculation based on the reported mean µ = 34.5 number of evidence nodes, shows that the average probability of an observed state of an evidence node conditional on its direct predecessors was on the order of (10-8) 1/34.5 ≈ 0.59.  Given that their algorithm is essentially based on the LW algorithm, based on our tests we suspect that the performance will deteriorate on cases where the evidence is very unlikely. Both algorithms focus on the marginal probability of one hypothesis node. If there are many queried nodes, the efficiency may deteriorate.

We have tested the algorithms discussed in Section 2.3 on several large networks.  Our experimental results show that in cases with very unlikely evidence, none of these algorithms converges to reasonable estimates of the posterior probabilities within a reasonable amount of time. The convergence becomes worse as the number of evidence nodes increases. Thus, when using these algorithms in very large networks, we simply cannot trust the results. We will present results of tests of the LW and SIS algorithms in more detail in Section 4.

## 3. Ais-Bn: Adaptive Importance Sampling For Bayesian Networks

The main reason why the existing stochastic sampling algorithms converge so slowly is that they fail to learn a good importance function during the sampling process and, effectively, fail to reduce the sampling variance. When the importance function is optimal, such as in probabilistic logic sampling without any evidence, each of the algorithms is capable of converging to fairly good estimates of the posterior probabilities within relatively few samples. For example, assuming that the posterior probabilities are not extreme (i.e., larger than say 0.01), as few as 1,000 samples may be sufficient to obtain good estimates. In this section, we present the adaptive importance sampling algorithm for Bayesian networks
(AIS-BN) that, as we will demonstrate in the next section, performs very well on most tests. We will first describe the details of the algorithm and prove two theorems that are useful in learning the optimal importance sampling function.

## 3.1  Basic  Algorithm -  Ais-Bn

Compared with importance sampling used in normal finite-dimensional integrals, importance sampling used in Bayesian networks has several significant advantages.  First, the nnetwork joint probability distribution Pr(X) is decomposable and can be factored into component parts. Second, the network has a clear structure, which represents many conditional independence relationships. These properties are very helpful in estimating the otimal importance function.

The basic AIS-BN algorithm is presented in Figure 2. The main differences between the AIS-BN algorithm and the basic importance sampling algorithm in Figure 1 is that we introduce a monotonically increasing weight function wk and two effective heuristic initialization methods in Step 2. We also introduce a special learning component in Step 7 to let the updating process run more smoothly, avoiding oscillation of the parameters.  The