R67  
On the impact of causal independence
Irina Rish (irinar@ics.uci.edu) & Rina Dechter (dechter@ics.uci.edu)

Abstract Reasoning in Bayesian networks is exponential in a graph parameter w* known as induced width (also known as treewidth and maxclique 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 polytrees, 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 bucketelimination 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 CInetworks using arcconsistency, and apply this idea to noisyOR networks. The resulting algorithm generalizes the Quickscore algorithm [9] for BN2O networks. [ps] [pdf] 