Efficient Probabilistic Reasoning in Bayes Nets with Mutual Exclusion and Context Specific Independence

May 2003

Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2003)

Volume

Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2003)

All Papers

Prior work has shown that context-specific independence (CSI) in Bayes networks can be exploited to speed up belief updating. We examine how networks with variables exhibiting mutual exclusion (e.g. "selector variables"), as well as CSI, can be efficiently updated. In particular, singlyconnected networks, that have an additional common selector variable, can be updated in linear time, where quadratic time would be needed without the mutual exclusion requirement. The above result has direct applications, as such network topologies can be used in predicting the ramifications of user selection in some multimedia systems.