A Generalization of AIS-BN: The Problem of Estimating Pr($\bf a$|$\bf e$)

A typical focus of systems based on Bayesian networks is the posterior probability of various outcomes of individual variables given evidence, Pr(a|$\bf e$). This can be generalized to the computation of the posterior probability of a particular instantiation of a set of variables given evidence, i.e., Pr($\bf A$ = $\bf a$|$\bf e$). There are two methods that are capable of performing this computation. The first method is very efficient at the expense of precision. The second method is less efficient, but offers in general better convergence rates. Both methods are based on Equation 7.

The first method reuses the samples generated to estimate Pr($\bf e$) in estimating Pr($\bf a$,$\bf e$). Estimation of Pr($\bf a$,$\bf e$) amounts to counting the scored sum under the condition $\bf A$ = $\bf a$. The main advantage of this method is its efficiency -- we can use the same set of samples to estimate the posterior probability of any state of a subset of the network given evidence. Its main disadvantage is that the variance of the estimated Pr($\bf a$,$\bf e$) can be large, especially when the numerical value of Pr($\bf a$|$\bf e$) is extreme. This method is the most widely used approach in the existing stochastic sampling algorithms.

The second method, used much more rarely (e.g., [Cano et al.1996,Pradhan and Dagum1996,Dagum and Luby1997]), calls for estimating Pr($\bf e$) and Pr($\bf a$,$\bf e$) separately. After estimating Pr($\bf e$), an additional call to the algorithm is made for each instantiation $\bf a$ of the set of variables of interest $\bf A$. Pr($\bf a$,$\bf e$) is estimated by sampling the network with the set of observations $\bf e$ extended by $\bf A$ = $\bf a$. The main advantage of this method is that it is much better at reducing variance than the first method. Its main disadvantage is the computational cost associated with sampling for possibly many combinations of states of nodes of interest.

Cano et al. [1996] suggested a modified version of the second method. Suppose that we are interested in the posterior distribution Pr($\bf a_{i}^{}$|$\bf e$) for all possible values $\bf a_i$ of $\bf A$, i = 1, 2, ..., k. We can estimate Pr($\bf a_{i}^{}$,$\bf e$) for each i = 1, ..., k separately, and use the value $\sum_{i=1}^{k}$Pr($\bf a_{i}^{}$,$\bf e$) as an estimate for Pr($\bf e$). The assumption behind this approach is that the estimate of Pr($\bf e$) will be very accurate because of the large sample from which it is drawn. However, even if we can guarantee small variance in every Pr($\bf a_{i}^{}$,$\bf e$), we cannot guarantee that their sum will also have a small variance. So, in the AIS-BN algorithm we only use the pure form of each of the methods. The algorithm listed in Figure 2 is based on the first method when the optional computations in Steps 12 and 13 are performed. An algorithm corresponding to the second method skips the optional steps and calls the basic AIS-BN algorithm twice to estimate Pr($\bf e$) and Pr($\bf a$,$\bf e$) separately.

The first method is very attractive because of its simplicity and possible computational efficiency. However, as we have shown in Section 2.2, the performance of a sampling algorithm that uses just one set of samples (as in the first method above) to estimate Pr($\bf a$|$\bf e$) will deteriorate if the difference between the optimal importance functions for Pr($\bf a$,$\bf e$) and Pr($\bf e$) is large. If the main focus of the computation is high accuracy of the posterior probability distribution of a small number of nodes, we strongly recommend to use the algorithm based on the second method. Also, this algorithm can be easily used to estimate confidence intervals of the solution.