results for our comparisons of the mean square error. We performed all experiments on a Pentium II, 333 MHz Windows computer.

While MSE is not perfect, it is the simplest way of capturing error that lends itself to further theoretical analysis. For example, it is possible to derive analytically the idealized convergence rate in terms of MSE , which, in turn, can be used to judge the quality of the agorithm. MSE has been used in virtually all previous tests of sampling algorithms, which allows interested readers to tie the current results to the past studies. A reviewer offered an interesting suggestion of using cross-entropy or some other technique that weights small changes near zero much more strongly than the equivalent size change in the middle of the [0,1] interval. Such measure would penalize the algorithm for imprecisions of possibly several orders of magnitude in very small probabilities. While this idea is interesting, we are not aware of any theoretical reasons as to why this measure would make a difference in comparisons between AIS-BN, LW and SIS algorithms. The MSE, as we mentioned above, will allow us to compare the empirically determined convergence rate to the theoretically derived ideal convergence rate. Theoretically, the MSE is inversely proportional to the square root of the sample size.

Since there are several tunable parameters used in the AIS-BN algorithm, we list the values of the parameters used in our test: l = 2, 500; wk = 0 for k ≤ 9 and wk = 1 otherwise. We stopped the updating process in Step 7 of Figure 2 after k ≥ 10. In other words, we used only the samples collected in the last step of the algorithm. The learning parameters used in our algorithm are kmax = 10, a = 0.4, and b = 0.14 (see Equation 10).

We used an empirically determined value of the threshold θ = 0.04 (Section 3.3).  We only change the CPT tables of the parents of a special evidence node A to uniform distributions when Pr(A = a) < 1/(2 · nA). Some of the parameters are a matter of design decision (e.g., the number of samples in our tests), others were chosen empirically. Although we have found that these parameters may have different optimal values for different Bayesian networks, we used the above values in all our tests of the AIS-BN algorithm described in this paper. Since the same set of parameters led to spectacular improvement in accuracy in all tested networks, it is fair to say that the superiority of the AIS-BN algorithm to the other algorithms is not too sensitive to the values of the parameters.

For the SIS algorithm, w k = 1 by the design of the algorithm. We used l = 2, 500. The updating function in Step 7 of Figure 1 is that of (Shwe et al., 1991; Cousins, Chen, &
Frisse, 1993):

$$\operatorname{Pr}_{n e w}^{k}(x_{i}|\operatorname{pa}(X_{i}),\mathbf{e})={\frac{\operatorname{Pr}(x_{i}|\operatorname{pa}(X_{i}))+k\cdot{\widehat{\operatorname*{Pr}}}_{c u r r e n t}(x_{i}|\operatorname{pa}(X_{i}),\mathbf{e}))}{1+k}}$$

where Pr(x;|pa(X;)) is the original sampling distribution, Prcurrent(x;|pa(X;),e) is an equivalent of our ICPT tables estimator based on all currently available information, and k is the updating step.

## 4.2 Results For The Cpcs Network

The main network used in our tests is a subset of the CPCS (Computer-based Patient Case Study) model (Pradhan et al., 1994), a large multiply-connected multi-layer network consisting of 422 multi-valued nodes and covering a subset of the domain of internal medicine.