Learning Bayesian networks with bounded tree-width has attracted much attention recently, because low tree-width allows exact inference to be performed efficiently. Some existing methods [24,29] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. Finding the best k-tree, however, is computationally intractable. In this paper, we propose a sampling method to efficiently find representative k-trees by introducing an informative score function to characterize the quality of a k-tree. To further improve the quality of the k-trees, we propose a probabilistic hill climbing approach that locally refines the sampled k-trees. The proposed algorithm can efficiently learn a quality Bayesian network with tree-width at most k. Experimental results demonstrate that our approach is more computationally efficient than the exact methods with comparable accuracy, and outperforms most existing approximate methods.
|Number of pages||17|
|Journal||International Journal of Approximate Reasoning (IJAR)|
|Early online date||11 Jul 2016|
|Publication status||Published - Jan 2017|
Nie, S., de Campos, C. P., & Ji, Q. (2017). Efficient learning of Bayesian networks with bounded tree-width. International Journal of Approximate Reasoning (IJAR), 80, 412-427. https://doi.org/10.1016/j.ijar.2016.07.002