with the diagnosis of lymph-node diseases. There are two versions of this network. We used the larger version, consisting of 135 nodes. In contrast to the CPCS network, PATHFINDER
contains many conditional probabilities that are equal to 1, which reflects deterministic relationships in certain settings. To make the sampling challenging, we randomly selected 20 evidence nodes from among the leaf nodes. Ea of these was an observable node (David Heckerman, personal communication). We verified in each case that the probability of so selected evidence was not equal to zero.

We fixed the execution time of the algorithms to be 60 seconds. The learning overhead for the AIS-BN algorithm in the PATHFINDER network was about 3.5 seconds. In 60 ss and LW generated about 2,700,000 samples. The reason why LW could generate more than 10 times as many samples as SIS within the same amount of time is that the LW algorithm terminates sample generation at a very early stage in many samples, when the weight of a sample becomes zero. This is a result of determinism in the probability tables, mentioned above. We will see that LW benefits greatly from generating more samples. The other parameters used in AIS-BN were the same as those used in the CPCS network.

We tested 20 cases, each with randomly selected 20 evidence nodes. The reported MSE
for each case was averaged over 10 runs. Some of the runs of the SIS and LW algorithms did not manage to generate any effective samples (the weight score sum was equal to zero). SIS had only 75% effective runs and LW had only 89% effective runs, which means that in some runs SIS and LW were unable to yield any information about the posterior distributions.

In all those cases, we discarded the run and only averaged over the effective runs.  All runs in the AIS-BN algorithm were effective. We report our experimental results with the summary statistics in Table 4. From these data, we can see that the AIS-BN algorithm is still significantly better than the SIS and LW algorithms. Since the LW algorithm can generate more than ten times the number of samples than the SIS algorithm, its performance is better than that of the SIS algorithm.

| A IS- BN       | LW      |         |         |
|----------------|---------|---------|---------|
| SIS            |         |         |         |
| 0.00050        | 0.166   | 0.089   |         |
| l              | 0.00037 | 0.107   | 0.0707  |
| a              |         |         |         |
| min            | 0.00025 | 0.00116 | 0.00080 |
| median         | 0.00037 | 0.184   | 0.0866  |
| max            | 0.0017  | 0.467   | 0.294   |
| effective runs | 200     | 150     | 178     |

The second network that we tested was one of the ANDES networks (Conati et al.,
1997). ANDES is an intelligent tutoring system for classical Newtonian physics that is being developed by a team of researchers at the Learning Research and Development Center at the University of Pittsburgh and researchers at the United States Naval Academy. The student model in ANDES uses a Bayesian network to do long–term knowledge assessment,