On the use of local search heuristics to improve GES-based Bayesian network learning

摘要

Bayesian networks learning is computationally expensive even in the case of sacrificing the optimality of the result. Many methods aim at obtaining quality solutions in affordable times. Most of them are based on local search algorithms, as they allow evaluating candidate networks in a very efficient way, and can be further improved by using local search-based metaheuristics to avoid getting stuck in local optima. This approach has been successfully applied in searching for network structures in the space of directed acyclic graphs. Other algorithms search for the networks in the space of equivalence classes. The most important of these is GES (greedy equivalence search). It guarantees obtaining the optimal network under certain conditions. However, it can also get stuck in local optima when learning from datasets with limited size. This article proposes the use of local search-based metaheuristics as a way to improve the behaviour of GES in such circumstances. These methods also guarantee asymptotical optimality, and the experiments show that they improve upon the score of the networks obtained with GES. (C) 2017 Elsevier B.V. All rights reserved.