On the Impact of Causal Independence

Interactive and Mixed-Initiative Decision-Theoretic Systems

Volume

Papers from the 1998 AAAI Spring Symposium

Contents

Reasoning in Bayesian networks is exponential in a graph parameter called induced-width (also known as tree-width and max-clique size). In this paper, we investigate how a property called causal independence can improve this performance. We show that the "effective" induced-width of algorithms exploiting this property can be significantly reduced: it can be as small as the induced width of the unmoralized network’s graph, and will never exceed the induced-width of the network’s moral graph. For example, for polytrees, causal independence reduces complexity from exponential to linear in the family size. Our analysis is presented for belief updating first, and is then extended to three other tasks: finding a most probable explanation (MPE), finding the maximum aposteriori hypothesis (MAP) and finding the maximum expected utility (MEU). We show that, while causal independence can considerably reduce the complexity of belief updating, MAP and MEU, it may have no effect on MPE. For the first three tasks, we present variable-elimination algorithm that exploite causal independence.