Effective pruning strategies for branch and bound Bayesian networks structure learning from data

In this paper, designing a bayesian network structure to maximize a score function based onlearning from data strategy is studied. the scoring function is considered to be a decomposable one suchas bdeu, bic, bd, bde or aic. optimal design of such a network is known to be an np-hard problem andthe solution becomes rapidly infeasible as the number of variables (i.e., nodes in the network) increases.several methods such as hill-climbing, dynamic programming, and branch and bound techniques areproposed to tackle this problem. however, these techniques either produce sub-optimal solutions or thetime required to produce an optimal solution is unacceptable. the challenge of the latter solutions is toreduce the computation time necessary for large-size problems.in this study, a new branch and bound method called pbb (pruned brand and bound) is proposedwhich is expected to find the globally optimal network structure with respect to a given score function.it is an any-time method, i.e., if it is externally stopped, it gives the best solution found until that time.several pruning strategies are proposed to reduce the number of nodes created in the branch and boundtree. practical experiments show the effectiveness of these pruning strategies. the performance of pbb,on several common datasets, is compared with the latest state-of-the-art methods. the results show itssuperiority in many aspects, especially, in the required running time, and the number of created nodes ofthe branch and bound tree.