Premium
Efficient probabilistic reasoning in BNs with mutual exclusion and context‐specific independence
Author(s) -
Domshlak Carmel,
Shimony Solomon E.
Publication year - 2004
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.20021
Subject(s) - mutual information , computer science , bayesian network , independence (probability theory) , context (archaeology) , mutual exclusion , probabilistic logic , path (computing) , conditional independence , bayes' theorem , selection (genetic algorithm) , network topology , theoretical computer science , random variable , variable (mathematics) , artificial intelligence , machine learning , data mining , mathematics , bayesian probability , statistics , paleontology , biology , mathematical analysis , programming language , operating system
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, directed‐path singly connected and polytree networks that have an additional common selector variable can be updated in linear time (given null and general conjunctive evidence, respectively), where quadratic time would be needed without the mutual exclusion requirement. The above results have direct applications, as such network topologies can be used in predicting the ramifications of user selection in some multimedia data browsing systems. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 703–725, 2004.