Bounded recursive decomposition: A search-based method for belief-network inference under limited resources
Monti S, Cooper GF. Bounded recursive decomposition: A search-based method for belief-network inference under limited resources. International Journal of Approximate Reasoning 15 (1996) 49-75.
This 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 probable instantiations of the network 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.
KEYWORDS: Bayesian belief networks, belief updating, incremental bound- ing algorithms, simulation