A Cuckoo Search Algorithm for Bayesian Network Structure Learning

A Bayesian Network (BN) is a graphical model applying probability and Bayesian rule for its inference. BN consists of structure, that is a directed acyclic graph (DAG), and parameters. The structure can be obtained by learning from data. Finding an optimal BN structure is an NP-Hard problem. If an ordering is given, then the problem becomes simpler. Ordering means the order of variables (nodes) for building the structure. One of structure learning algorithms that uses variable ordering as the input is K2 algorithm. The ordering determines the quality of resulted network. In this work, we apply Cuckoo Search (CS) algorithm to find a good node ordering. Each node ordering is evaluated by K2 algorithm. Cuckoo Search is a nature-inspired metaheuristic algorithm that mimics the aggressive breeding behavior of Cuckoo birds with several simplifications. It has outperformed Genetic Algorithms and Particle Swarm Optimization algorithm in finding an optimal solution for continuous problems, e.g., functions of Michalewicz, Rosenbrock, Schwefel, Ackley, Rastrigin, and Griewank. We conducted experiments on 35 datasets to compare the performances of Cuckoo Search to GOBNILP that is a Bayesian network learning algorithm based on integer linear programming and it is well known to be used as benchmark. We compared the quality of obtained structures and the running times. In general, CS can find good networks although all the obtained networks are not the best. However, it sometimes finds only low-scoring networks, and the running times of CS are not always very fast. The results mostly show that GOBNILP is consistently faster and can find networks of better quality than CS. Based on the experiment results, we conclude that the approach is not able to guarantee obtaining an optimal Bayesian network structure. Other heuristic search algorithms are potentially better to be used for learning Bayesian network structures that we have not compared to our works, for example the ordering-search algorithm by Teyssier and Koller [41] that combines greedy local hill-climbing with random restarts, a tabu list, caching computations, and a heuristic pruning procedure