Eyal Shlomo Shimony

Bayesian Knowledge Bases (BKB) are a rule-based probabilistic model that extend Bayes Networks (BN), by allowing context-sensitive independence and cycles in the directed graph. BKBs have probabilistic seman- tics, but lack independence semantics, i.e., a graph- based scheme determining what independence state- ments are sanctioned by the model. Such a semantics is provided through generalized d- separation, by constructing an equivalent BN. While useful for showing correctness, the construction is not practical for decision algorithms due to exponential size. Some results for special cases, where indepen- dence can be determined from polynomial-time tests on the BKB graph, are presented.