A new hybrid method for learning bayesian networks: Separation and reunion

Most existing algorithms for learning Bayesian networks (BNs) can be categorized as constraint-based or score-based methods. Constraint-based algorithms use conditional independence (CI) tests to judge the presence or absence of an edge. Though effective and applicable to (high-dimensional data) large-scale networks, CI tests require a large number of samples to determine the independencies. Thus they can be unreliable especially when the sample size is small. On the other hand, score-based methods employ a score metric to evaluate each candidate network structure, but they are inefficient in learning large-scale networks due to the extremely large search space. In this paper, we propose a new hybrid Bayesian network learning method, SAR (the abbreviation of Separation And Reunion), which maintains the merits of both types of learning techniques while avoiding their drawbacks. Extensive experiments show that our method generally achieves better performance than state-of-the-art methods.