A recurrence local computation approach towards ordering composite beliefs in Bayesian belief networks (Q1209534)

A Bayesian network is a knowledge representation framework for encoding both qualitative and quantitative probabilistic dependencies among a set of propositional (or random) variables. Finding the Most Probable Explanations (MPE) is an important class of query with wide applications. Yet the probabilistic inference involved in finding the most probable explanations is generally expensive. The problem of finding the \(l\) Most Probable Explanations (MPE) of a given evidence, \(S_ e\), in a Bayesian belief network can be mathematically formulated as identifying and ordering in the first \(l\) instantiations of a given set of nonevidence variables, \(H_ is\), according to their posterior probabilities; i.e., given a set of nonevidence variables \(h\) and its possible instantiations \(H_ i\) (for different \(i)\), the first \(l\) MPE are \(H_ i\) such that \(Pr(H_ 1| S_ e)ge Pr(H_ 2| S_ e)\geq\cdots\geq Pr(H_ l| S_ e)\) and these \(Pr(H_ i| S_ e)\) are the \(l\) largest. A Recurrence Local Computational Method (RLCM) is a technique developed for an efficient derivation of the MPE in a singly connected belief network when \(h\) includes all the nonevidence variables. It can be shown that the time complexity of RLCM is bounded by \(O(lkn)\); where \(l\) is the number of the MPE to be identified, \(k\) the length of the longest path in a network, and \(n\) the maximum number of nodes states -- defined as the product of the size of the conditional probability table of a node and the number of incoming messages towards the node. This technique has been further extended to deal with multiply connected networks. When \(h\) does not include all the nonevidence variables, a boundary approach has been developed to identify the MPE. This approach is based on the result of RLCM to perform an incremental updating on the upper and lower limits of the posterior probabilities of the MPE candidates. Although this boundary approach has an exponential complexity in the worst case, it has been proved elsewhere that the complexity of this approach is always no worse than that of a direct computation, and a preliminary experimental study has shown that the actual computations involved in most of the test cases are only a small fraction of that required in the straight forward direct computations.