A combination of exact algorithms for inference on Bayesian belief networks
Suermondt HJ, Cooper GF. A combination of exact algorithms for inference on Bayesian belief networks. International Journal of Approximate Reasoning 5 (1991) 521–542.
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 of network nodes, whereas clique-tree propa- gation 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.
KEYWORDS: probabilistic reasoning; belief networks; artificial intelli- gence; Bayesian methods; reasoning under uncertainty; expert systems