Reasoning MPE to Multiply Connected Belief Networks Using Message Passing

Abstract

Finding the l Most Probable Explanations (MPE) of a given evidence, Se, in a Bayesian belief network is a process to identify and order a set of composite hypotheses, HiS, of which the posterior probabilities are the l largest; i.e., Pr(H1|Se) ≥ Pr(H2|Se) ≥ ... ≥ Pr(Hl|Se). A composite hypothesis is defined as an instantiation of all the non-evidence variables in the network. It could be shown that finding all the probable explanations is a NP-hard problem. Previously, only the first two best explanations (i.e., l = 2) in a singly connected Bayesian network could be efficiently derived without restrictions on network topologies and probability distributions. This paper presents an efficient algorithm for finding l (≥ 2) MPE in singly-connected networks and the extension of this algorithm for multiply-connected networks. This algorithm is based on a message passing scheme and has a time complexity O(lkn) for singly-connected networks; where l is the number of MPE to be derived, k the length of the longest path in a network, and n the maximum number of node states - defined as the product of the size of the conditional probability table of a node and the number of the incoming/outgoing arcs of the node.