Efficient learning of Bayesian networks with bounded tree-width

Siqi Nie, Cassio P. de Campos, Qiang Ji

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)412-427
Number of pages16
JournalInternational Journal of Approximate Reasoning
Volume80
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes

Keywords

  • Bayesian network
  • Structure learning
  • Bounded tree-width
  • Hill climbing

Fingerprint Dive into the research topics of 'Efficient learning of Bayesian networks with bounded tree-width'. Together they form a unique fingerprint.

  • Cite this