Tightening bounds for Bayesian network structure learning

A recent breadth-first branch and bound algorithm (BF-BnB) for learning Bayesian network structures (Mal-one et al. 2011) uses two bounds to prune the search space for better efficiency; one is a lower bound cal-culated from pattern database heuristics, and the other is an upper bound obtained by a hill climbing search. Whenever the lower bound of a search path exceeds the upper bound, the path is guaranteed to lead to subop-timal solutions and is discarded immediately. This pa-per introduces methods for tightening the bounds. The lower bound is tightened by using more informed vari-able groupings when creating the pattern databases, and the upper bound is tightened using an anytime learn-ing algorithm. Empirical results show that these bounds improve the efficiency of Bayesian network learning by two to three orders of magnitude