An efficient skeleton learning approach-based hybrid algorithm for identifying Bayesian network structure.

Bayesian network (BN) structure learning is the basis of BN applications and plays a pivotal role in many machine learning tasks. Whereas remarkable progress in structure learning has been achieved in the past, making further improvements in the efficiency and accuracy of structure learning is a significant challenge. In this paper, we propose an efficient skeleton learning approach-based hybrid algorithm (ESLH), which consists of two phases. In the constraint-based phase, a dynamic threshold (DTH) strategy and a skeleton learning method based on triangle breaking (SLTB) are proposed to learn the skeleton of a BN structure efficiently. DTH designs a dynamic threshold to remove redundant edges in the initial skeleton with little time overhead. By the result of DTH, SLTB first finds, tests and breaks triangles in the initial skeleton to efficiently remove redundant edges and then removes the remaining redundant edges to discover the final skeleton. In the score-and-search phase, ESLH employs the hill-climbing algorithm to find the highest-scored structure. We propose a novel strategy to divide this phase into three steps, both utilizing the learned skeleton to constrain the search space and preventing the errors of the learned skeleton from reducing the quality of the final learned structure. Extensive experiments on benchmark BNs validate the effectiveness of DTH and SLTB and demonstrate that ESLH is more than five times faster than the state-of-the-art structure learning algorithms while maintaining the highest average accuracy. [ABSTRACT FROM AUTHOR]