** Next:** Modifying the Sampling Distribution
** Up:** AIS-BN: Adaptive Importance Sampling
** Previous:** AIS-BN: Adaptive Importance Sampling

##

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 network
joint probability distribution
Pr() 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
optimal 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 *w*^{k} 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 score processing in Step 10 is

*w*_{iScore} =

*w*^{k} .

Note that in this respect the algorithm in Figure 1
becomes a special case of AIS-BN when *w*^{k} = 1. The reason why we
use *w*^{k} is that we want to give different weights to the
sampling results obtained at different stages of the algorithm. As
each stage updates the importance function, they will all have
different distance from the optimal importance function. We
recommend that
*w*^{k} 1/, where
is the standard deviation estimated in
stage *k* using Equation 3.^{1} In
order to keep *w*^{k} monotonically increasing, if *w*^{k} is smaller
than *w*^{k - 1}, we adjust its value to *w*^{k - 1}. This weighting
scheme may introduce bias into the final result. Since the initial
importance sampling functions are often inefficient and introduce
big variance into the results, we also recommend that *w*^{k} = 0 in
the first few stages of the algorithm. We have designed this
weighting scheme to reflect the fact that in practice estimates
with very small estimated variance are usually good estimates.

** Next:** Modifying the Sampling Distribution
** Up:** AIS-BN: Adaptive Importance Sampling
** Previous:** AIS-BN: Adaptive Importance Sampling
Jian Cheng
2000-10-01