Bounded recursive decomposition: a search-based method for belief-network inference under limited resources

AbstractThis paper presents a new inference algorithm for belief networks that combines a search-based algorithm with a simulation-based algorithm. The former is an extension of the recursive decomposition (RD) algorithm proposed by Cooper, which is here modified to compute interval bounds on marginal probabilities. We call the algorithm bounded-RD. The latter is a stochastic simulation method known as Pearl's Markov blanket algorithm. Markov simulation is used to generate highly propable instantiations of thenetwork nodes to be used by bounded-RD in the computation of probability bounds. Bounded-RD has the anytime property, and produces successively narrower interval bounds, which converge in the limit to the exact value