Reducing the computational complexity in learning Bayesian network structures - considering prior knowledge into account

摘要

We consider learning Bayesian network structure from records with attributes values. When based on the minimum description length (MDL) principle, the obtained model almost surely coincide with the true model as the number of recordes goes to infinity. However, the computation grows exponentially with the number of attributes. In this paper, we consider to apply the branch and bound (B&B) technique and to take prior knowledge into account to save the computation. In particular, we restrict the maximum number of nodes on which each node can depend to some constant K. Moreover, we show the connection difference between the B&B based algorithm with K = 1 and Suzuki's forest generating algorithm based on the Kruskal's algorithm.