A Monte Carlo algorithm for probabilistic propagation in belief networks based on importance sampling and stratified simulation techniques

A class of Monte Carlo algorithms for probability propagation in belief networks is given. The simulation is based on a two steps procedure. The first one is a node deletion technique to calculate the 'a posteriori' distribution on a variable, with the particularity that when exact computations are too costly, they are carried out in an approximate way. In the second step, the computations done in the first one are used to obtain random configurations for the variables of interest. These configurations are weighted following importance sampling methodology. Different particular algorithms are obtained depending on the approximation procedure used in the first step and the way of obtaining the random configurations. In this last case, a stratified sampling technique :is used, which has been adapted for application to very large networks without round-off error problems. (C) 1998 Elsevier Science Inc.