论文部分内容阅读
Propagation algorithm is the most efficient algorithm for exact probabilistic in ference of Bayesian network, which can be seen as two stage: the compilation stage in which a suitable structure, that is, a junction tree of a triangulation of Bayesian networks moral graph, is established and the propagation stage.However, the most difficult step in these two stages, that is, to find the optimal triangulation of Bayesian network, is known to be an NP-hard problem.In this paper, we propose an improved propagation (IP) algorithm which optimizes the compilation stage and improves the efficiency of exact inference of Bayesian network.Our algorithm splits the problem of fining optimal triangulation into several smaller problems on the prime blocks of the moral graph, thus the direct union of the optimal triangulations of all the prime blocks is just the optimal triangulation of the Bayesian network.Furthermore, it connects junction trees of the optimal triangulations of all the prime blocks to con struct a junction tree of the optimal triangulation for the propagation stage which improves the efficiency of exact inference.