Learning Bounded Tree-width Bayesian Networks via Sampling

Abstract. Learning Bayesian networks with bounded tree-width has at-tracted much attention recently, because low tree-width allows exact in-ference to be performed efficiently. Some existing methods [12, 14] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. In this paper, we propose a sampling method to ef-ficiently find representative k-trees by introducing an Informative score function to characterize the quality of a k-tree. The proposed algorithm can efficiently learn a Bayesian network with tree-width at most k. Ex-periment results indicate that our approach is comparable with exact methods, but is much more computationally efficient