Exact Structure Learning of Bayesian Networks by Optimal Path Extension
This addresses a computational bottleneck for researchers and practitioners using Bayesian networks in big data analytics, offering significant performance gains.
The paper tackles the NP-hard problem of exact structure learning for Bayesian networks by introducing a new approach that leverages relationships between partial structures and remaining variables to constrain optimal extensions, resulting in up to three times runtime improvement and orders of magnitude reduction in memory consumption over current best algorithms.
Bayesian networks are probabilistic graphical models often used in big data analytics. The problem of exact structure learning is to find a network structure that is optimal under certain scoring criteria. The problem is known to be NP-hard and the existing methods are both computationally and memory intensive. In this paper, we introduce a new approach for exact structure learning. Our strategy is to leverage relationship between a partial network structure and the remaining variables to constraint the number of ways in which the partial network can be optimally extended. Via experimental results, we show that the method provides up to three times improvement in runtime, and orders of magnitude reduction in memory consumption over the current best algorithms.