An Efficient Bayesian Network Structure Learning Strategy

作者：Suzuki Joe^*

来源：New Generation Computing, 2017, 35(1): 105-124.

DOI：10.1007/s00354-016-0007-6

• Parent set
• Branch and bound (B& B)
• Upper bound
• Score
• Maximizing the posterior probability
• Bayesian network structure learning

This paper addresses the problem of efficiently finding an optimal Bayesian network structure for maximizing the posterior probability. In particular, we focus on the B& B strategy to save the computational effort associated with finding the largest score. To make the search more efficient, we need a tighter upper bound so that the current score can exceed it more easily. We find two upper bounds and prove that they are tighter than the existing one (Campos and Ji, J Mach Learn Res 12(3):663-689, 2011). Finally, we demonstrate that the proposed two bounds render the search to be much more efficient using the Alarm and Insurance data sets. For example, the search is twice to three times faster for and almost twice faster for . We also experimentally verify that the overhead due to replacing the existing pruning rule by the proposed one is negligible.

• 出版日期2017-1