An algorithm directly finding the K most probable configurations in Bayesian networks

AbstractThis article describes an algorithm that solves the problem of finding the K most probable configurations of a Bayesian network, given certain evidence, for any K, and for any type of network, including multiply connected networks. This algorithm is based on the compilation of the initial network into a junction tree. After a description of the preliminary steps needed to get a junction tree, namely, the moralization, the triangulation, and the ordering of cliques, we explain how the incorporation of evidence is processed. The principle of the algorithm is to visit in a bottom-up way each clique of the junction tree, and to store, at each level, the K most probable configurations of the deeper levels. The complexity of the algorithm is computed and shown to be mainly dependent of the maximum clique size, as it is for Bayesian updating algorithms using the junction tree internal representation. The classic example ASIA is used to illustrate the detailed execution of the algorithm with K = 3. Finally, our method is compared with related work