Probabilistic inference in multiply connected belief networks using loop cutsets.
Suermondt HJ, Cooper GF. Probabilistic inference in multiply connected belief networks using loop cutsets. International Journal of Approximate Reasoning 4 (1990) 283–306.
The method of conditioning permits probabilistic inference in multiply connected belief 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 inteiligenoe, Bayesian methods, expert systems, probabiUstie reasoning, belief networks, multiply connected, cutsets, loops