Fusion and propagation with multiple observations in belief networks

摘要

The Polytree Algorithm of Kim and Pearl [16, 19] is a fundamental method for evidential reasoning in belief networks. Not only does it provide exact solutions to singly connected networks using efficient, local computations, but variations of it can be applied to more general networks as well. When a belief network is singly connected, the Polytree Algorithm can compute a posterior marginal distribution for each variable by visiting each node at most once for each piece of evidence. By contrast, the related algorithms based on undirected graphs [1, 14–16, 28] only need to visit each node at most twice no matter how much evidence is observed. In this paper, a Revised Polytree Algorithm is developed with the same complexity as the undirected methods, but within the directed framework of the Polytree Algorithm. When this new algorithm is applied via “cutset conditioning” to general networks it obtains not just the corresponding significant improvement in speed, but also a much simpler form for combination. Furthermore, the revised algorithm requires only minor modifications to existing implementations of the Polytree Algorithm.