Conclusions
This paper presents new non-trivial pruning rules to be used with the Bayesian Information Criterion (BIC) score for learning the structure of Bayesian networks. The derived theoretical bounds extend previous results in the literature and can be promptly integrated into existing solvers with minimal effort and computational costs. They imply faster computations without losing optimality. The very computationally efficient version of the new rules imply gains of around 20% with respect to previous work, according to our experiments, while the most computationally demanding pruning achieves around 50% more pruning than before. Pruning rules for other widely used scores such as the Bayesian Dirichlet equivalent uniform (BDeu) have been devised [13] and some researchers conjecture that they cannot be improved. Similarly, we conjecture that further bounds for the BIC score are unlikely to exist unless for some particular cases and situations. This can be studied in a future work, as well as means to devise smart strategies to tune the theorem parameters and improve their pruning capabilities.
