Improved MDL Score for Learning of Bayesian Networks

In this paper, we propose two modifications to the origi-nal Minimum Description Length (MDL) score for learning of Bayesian networks. The first modification is that the de-scription of network structure is proved to be unnecessary and can be omitted in the total MDL score. The second mod-ification consists in reducing the description length of con-ditional probability table (CPT). In particular, if a specific variable is fully deterministic given its parents, i.e., the vari-able will take a certain value with probability one for some configurations of its parents, we show that only the configu-rations with probability one need to be retained in the CPT of the variable in the MDL score during the learning pro-cess of Bayesian networks. We name the MDL score with the above two modifications the Improved MDL score or IMDL score for short. The experimental results of classic Bayesian networks, such as ALARM [2] and ASIA [17], show that the same search algorithm with the IMDL score can identify more reasonable and accurate models than those obtained with the original MDL score. 1