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 belie f networks is given. The simulation is based on a two steps procedure. The first one is a node deletion technique to calculate the 'a poster iori' distribution on a variable, with the particularity that when exa ct computations are too costly, they are carried out in an approximate way. In the second step, the computations done in the first one are u sed to obtain random configurations for the variables of interest. The se configurations are weighted following importance sampling methodolo gy. Different particular algorithms are obtained depending on the appr oximation procedure used in the first step and the way of obtaining th e random configurations. In this last case, a stratified sampling tech nique :is used, which has been adapted for application to very large n etworks without round-off error problems. (C) 1998 Elsevier Science In c.