Abstract
Reasoning in Bayesian networks is exponential in a graph parameter w* known as induced width (also known as tree-width and max-clique size). In this paper, we investigate the potential of causal independence (CI) for improving this performance. We consider several tasks, such as belief updating, finding a most probable explanation (MPE), finding a maximum aposteriori hypothesis (MAP), and finding the maximum expected utility (MEU). We show that exploiting CI in belief updating can significantly reduce the effective w*, sometimes down to the induced width of the unmoralized network's graph. For example, for poly-trees, CI reduces complexity from exponential to linear in the family size. Similar results hold for the MAP and MEU tasks, while the MPE task is less sensitive to CI. These enhancements are incorporated into bucket-elimination algorithms based on known approaches of network transformations [10, 13] and elimination [18]. We provide an ordering heuristic which guarantees that exploiting CI will never hurt the performance. Finally, we discuss an efficient way of propagating evidence in CI-networks using arc-consistency, and apply this idea to noisy-OR networks. The resulting algorithm generalizes the Quickscore algorithm [9] for BN2O networks.