Stochastic Sampling Algorithms: AIS Sampling

From DSL

The Adaptive Importance Sampling for Bayesian Networks (AIS-BN) algorithm is described in (Cheng & Druzdzel 2000). This is one of the best sampling algorithm available (as of December 2002), surpassed only recently by the APIS-BN algorithm (Yuan & Druzdzel 2003). In really difficult cases, such as reasoning under very unlikely evidence in very large networks, it will produce two orders of magnitude smaller error in posterior probability distributions than other sampling algorithms. Improvement in speed given a desired precision is even more dramatic. The AIS-BN algorithm is based on importance sampling. According to the theory of importance sampling, the closer the sampling distribution is to the (unknown) posterior distribution, the better the results will be. The AIS-BN algorithm successfully approximate its sampling distribution to the posterior distribution by using two cleverly designed heuristic methods in its first stage, which leads to the big improvement in performance stated above.