Shwe & Cooper, 1991). Although some researchers suggested that this may be a promising direction for the work on sampling algorithms, we have not seen any results that would follow up on this.

A separate group of stochastic sampling methods is formed by so-called Markov Chain Monte Carlo (MCMC) methods that are divided into Gibbs sampling, Metropolis sampling, and Hybrid Monte Carlo sampling (Geman & Geman, 1984; Gilks, Richardson, & Spiegelhalter, 1996; MacKay, 1998). Roughly speaking, these methods draw random samples from an unknown target distribution f ( X ) by biasing the search for this distribution towards higher probability regions. When applied to Bayesian networks (Pearl, 1987; Chavez & Cooper, 1990) this approach determines the sampling distribution of a variable from its previous sample given its Markov blanket (Pearl, 1988).  This corresponds to updating Prk (X\E) when sampling every node. Prk (X\E) will converge to the optimal importance function for Pr(e) if Pr 0 (X\E) satisfies some ergodic properties (York, 1992).  Since the convergence to the limiting distribution is very slow and calculating updates of the sampling distribution is costly, these algorithms are not used in practice as often as the simple likelihood weighting scheme.

There are also some other simulation algorithms, such as bounded variance algorithm
(Dagum & Luby, 1997) and the AA algorithm (Dagum et al., 1995), which are essentially bbbed on the LW algorithm and the Stopping-Rule Theorem (Dagum et al., 1995).  Cano et al. (1996) proposed another importance sampling algorithm that performed somewhat better than LW in cases with extreme probability distributions, but, as the authors state, in general cases it "produced similar results to the likelihood weighting algorithm."  Hernandez et al. (1998) also applied importance sampling and reported a moderate improvement on likelihood weighting.

## 2.4 Practical Performance Of The Existing Sampling Algorithms

The largest network that has been tested using sampling algorithms is QMR-DT (Quick Medical Reference - Decision Theoretic) (Shwe et al., 1991; Shwe & Cooper, 1991), which contains 534 adult diseases and 4,040 findings, with 40,740 arcs depicting disease-to-finding dependencies. The QMR-DT network belongs to a class of special bipartite networks and its structure is often referred to as BN2O (Henrion, 1991), because of its two-layer composition: disease nodes in the top layer and finding nodes in the bottom layer. Shwe and colleagues used an algorithm combining self-importance and heuristic importance and tested its convergence properties on the QMR-DT network. But since the heuristic method iterative tabular Bayes (ITB) that makes use of a version of Bayes' rule is designed for the BN2O networks, it cannot be generalized to arbitrary networks. Although Shwe and colleagues concluded that Markov blanket scoring and self-importance sampling significantly improve the convergence rate in their model, we cannot extend this conclusion to general nnetworks. The computation of Markov blanket scoring is more complex in a general multiconnected network than in a BN2O network. Also, the experiments conducted lacked a gold-standard posterior probability distribution that could serve to judge the convergence rate.

Pradhan and Dagum (1996) tested an efficient version of the LW algorithm - bounded variance algorithm (Dagum & Luby, 1997) and the AA algorithm (Dagum et al., 1995) on