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.

Abstract

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.

Keywords

  • probabilistic reasoning;
  • belief networks;
  • artificial intelligence;
  • Bayesian methods;
  • reasoning under uncertainty;
  • expert systemsr
Publication Year: 
1990
Faculty Author: 
AttachmentSize
PDF icon Chavez.pdf1.16 MB
^