Probabilistic Inference in Multiply Connected Belief Networks Using Loop Cutsets

摘要

The method of conditioning permits probabilistic inference in multiply connectedbelief networks using an algorithm by Pearl. This method uses a select set of nodes, the loop cutset, to render the multiply connected network singly connected. We discuss the function of the nodes of the loop cutset and a condition that must be met by the nodes of the loop cutset. We show that the problem of finding a loop cutset that optimizes probabilistic inference using the method of conditioning is NP-hard. We present a heuristic algorithm for finding a small loop cutset in polynomial time, and we analyze the performance of this heuristic algorithm empirically. Keywords: Artificial intelligence, Bayes theorem, Expert systems, Probabilistic reasoning, Belief networks, Multiply connected, Cutset loops, Reprints, Algorithms. (CP)