Learning Bayesian Belief Networks Based on the MDL Principle: An Efficient Algorithm Using the Branch and Bound Technique

In this paper, the problem of learning a Bayesian belief network (BBN) from given examples based on the minimum description length (MDL) principle is addressed. Given examples, the learning algorithm based on the MDL principle computes for each network the total of description length of the network and that of the examples given the network, and finds a network with the minimum value. We provide a search algorithm that reduces the computation time and at the same time is sure to find the network with the MDL. The proposed algorithm, which applies the branch and bound (B & B) technique to the problem assuming the Dirichlet density over the conditional probabilities of a BBN, has lower computational complexity compared to exhaustive searches. Some empirical experiments using the Alarm database show that the proposed algorithm is fairly efficient for various problems of a moderate size. Our proposed algorithm is considered to take an advantage over the Cooper and Herskovits' algorithm, wh..