Knowledge representation and inference in similarity networks and Bayesian multinets

AbstractWe examine two representation schemes for uncertain knowledge: the similarity network (Heckerman, 1991) and the Bayesian multinet. These schemes are extensions of the Bayesian network model in that they represent asymmetric independence assertions. We explicate the notion of relevance upon which similarity networks are based and present an efficient inference algorithm that works under the assumption that every event has a nonzero probability. Another inference algorithm is developed that works under no restriction albeit less efficiently. We show that similarity networks are not inferentially complete—namely—not every query can be answered. Nonetheless, we show that a similarity network can always answer any query of the form: “What is the posterior probability of an hypothesis given evidence?” We call this property diagnostic completeness. Finally, we describe a generalization of similarity networks that can encode more types of asymmetric conditional independence assertions than can ordinary similarity networks