Independence Semantics for BKBs

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 semantics, but lack independence semantics, i.e., a graphbased scheme determining what independence statements are sanctioned by the model. Such a semantics is provided through generalized dseparation, 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 independence can be determined from polynomial-time tests on the BKB graph, are presented.