A randomized approximation algorithm for probabilistic inference on Bayesian belief networks
Chavez RM, Cooper GF. A randomized approximation algorithm for probabilistic inference on Bayesian belief networks. Networks 20 (1990) 661–685.
Cutset conditioning and clique-tree propagation are two popular methods for exact probabilistic inference in Bayesian belief networks. Cutset conditioning is based on decomposition of a subset network nodes, whereas clique-tree propagation depends on aggregation of nodes. We characterize network structures in which the performances of these methods differ. We describe a means to combine cutset conditioning and clique-tree propagation in an approach called aggregation after decomposition (AD), which can perform inference relatively efficiently for certain network structures in which neither cutset conditioning nor clique-tree propagation performs well. We discuss criteria to determine when AD will perform more efficient belief-network inference than will clique-tree propagation.
- probabilistic reasoning;
- belief networks;
- artificial intelligence;
- Bayesian methods;
- reasoning under uncertainty;
- expert systemsr