Kalia Orphanou
ABSTRACT
Bayesian networks (BNs) are probabilistic graphical models which are widely used for knowledge representation and decision making tasks, especially in the presence of uncertainty. Finding or learning the structure of BNs from data is an NP-hard problem. Evolutionary algorithms (EAs) have been extensively used to automate the learning process. In this paper, we consider the use of the Gene-Pool Optimal Mixing Evolutionary Algorithm (GOMEA). GOMEA is a relatively new type of EA that belongs to the class of model-based EAs. The model used in GOMEA is aimed at modeling the dependency structure between problem variables, so as to improve the efficiency and effectiveness of variation. This paper shows that the excellent performance of GOMEA transfers from well-known academic benchmark problems to the specific case of learning BNs from data due to its model-building capacities and the potential to compute partial evaluations when learning BNs. On commonly-used datasets of varying size, we find that GOMEA outperforms standard algorithms such as Order-based search (OBS), as well as other EAs, such as Genetic Algorithms (GAs) and Estimation of Distribution algorithms (EDAs), even when efficient local search techniques are added.
- Hirotugu Akaike. 1974. A New Look at the Statistical Model Identification. IEEE Trans. Automat Control 19, 6 (1974), 716--723.Google Scholar
Cross Ref
- Peter A.N. Bosnian and Dirk Thierens. 2013. More Concise and Robust Linkage Learning by Filtering and Combining Linkage Hierarchies. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO '13). ACM, New York, NY, USA, 359--366. Google ScholarDigital Library
- Remco Bouckaert. 1995. Bayesian Belief Networks: From Construction to Inference. Ph.D. Dissertation. University of Utrecht.Google Scholar
- Wray L. Buntine. 1991. Theory Refinement on Bayesian Networks. In Proceedings of the Seventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 52--60. Google ScholarDigital Library
- Wray L. Buntine. 1994. Operations for Learning with Graphical Models. CoRR abs/cs/9412102 (1994). Google ScholarDigital Library
- Carlo Contaldi, Fatemeh Vafaee, and Peter C. Nelson. 2017. The Role of Crossover Operator in Bayesian Network Structure Learning Performance: A Comprehensive Comparative Study and New Insights. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July 15-19, 2017. 769--776. Google ScholarDigital Library
- A. E Eiben, P-E Raue, and Zs. Ruttkay. 1994. Genetic Algorithms with Multi-parent Recombination. In International Conference on Parallel Problem Solving from Nature. Springer, 78--87. Google ScholarDigital Library
- G. Elidan. 2001. Bayesian Network Repository. http://www.cs.huji.ac.il/site/labs/compbio/Repository Accessed: 2018-01-31.Google Scholar
- Nir Friedman, Iftach Nachman, and Dana Peér. 1999. Learning Bayesian Network Structure from Massive Datasets: The Sparse Candidate Algorithm. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI'99). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 206--215. Google ScholarDigital Library
- Georges R. Harik, Fernando G. Lobo, and Kumara Sastry. 2006. Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA). In Scalable Optimization via Probabilistic Modeling. Springer, 39--61.Google Scholar
- David Heckerman, Dan Geiger, and David M. Chickering. 1995. Learning Bayesian Networks: The Combination of Knowledge and Statistical Data. Machine learning 20, 3 (1995), 197--243. Google ScholarDigital Library
- Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press. Google ScholarDigital Library
- Larrañaga, Mikel Poza, Yosu Yurramendi, Roberto H. Murga, and Cindy M. H. Kuijpers. 1996. Structure Learning of Bayesian Networks by Genetic Algorithms: A Performance Analysis of Control Parameters. IEEE Transaction on Pattern Analysis and Machine Intelligence 18, 9 (1996), 912--926. Google ScholarDigital Library
- Pedro Larrañaga, Cindy M. H. Kuijpers, Mikel Poza, and Roberto H. Murga. 1997. Decomposing Bayesian networks: Triangulation of the Moral Graph with Genetic Algorithms. Statistics and Computing 7, 1 (1997), 19--34. Google ScholarDigital Library
- Pedro Larrañaga, Roberto Murga, Mikel Poza, and Cindy Kuijpers. 1996. Structure Learning of Bayesian Networks by Hybrid Genetic Algorithms. (1996), 165--174.Google Scholar
- Hoang N. Luong, Peter A.N. Bosman, and Han La Poutré. 2017. Exploiting Linkage Information and Problem-Specific Knowledge in Evolutionary Distribution Network Expansion Planning. Evolutionary Computation (2017), 1--35. Google ScholarDigital Library
- Hoang N Luong, Marinus O.W. Grond, Peter A.N. Bosman, and Han La Poutré. 2013. Medium-voltage Distribution Network Expansion Planning with Gene-pool Optimal Mixing Evolutionary Algorithms. In International Conference on Artificial Evolution. Springer, 93--105.Google Scholar
- Judea Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. Google ScholarDigital Library
- José C. Pereira and Fernando G. Lobo. 2015. A Java Implementation of Parameterless Evolutionary Algorithms. CoRR abs/1506.08694 (2015).Google Scholar
- Stjepan Picek, Marin Golub, and Domagoj Jakobovic. 2011. Evaluation of Crossover Operator Performance in Genetic Algorithms with Binary Representation. In International Conference on Intelligent Computing. Springer, 223--230. Google ScholarDigital Library
- J. Rissanen. 1978. Modeling by Shortest Data Description. Automatica 14, 5 (Sept. 1978), 465--471. Google ScholarDigital Library
- Gideon Schwarz. 1978. Estimating the Dimension of a Model. The Annals of Statistics 6, 2 (1978), 461--464.Google ScholarCross Ref
- Peter Spirtes and Clark Glymour. 1991. An Algorithm for Fast Recovery of Sparse Causal Graphs. Social Science Computer Review 9, 1 (1991), 62--72.Google ScholarCross Ref
- Marc Teyssier and Daphne Koller. 2012. Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks. CoRR abs/1207.1429 (2012). Google ScholarDigital Library
- Dirk Thierens and Peter A.N. Bosman. 2011. Optimal Mixing Evolutionary Algorithms. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO '11). ACM, New York, NY, USA, 617--624. Google ScholarDigital Library
- Ioannis Tsamardinos, Laura E. Brown, and Constantin F. Aliferis. 2006. The Max-min Hill-Climbing Bayesian Network Structure Learning Algorithm. Machine Learning 65, 1 (Oct. 2006), 31--78. Google ScholarDigital Library
- Steven Van Dijk, Dirk Thierens, and Linda C Van Der Gaag. 2003. Building a GA from Design Principles for Learning Bayesian Networks. In Genetic and Evolutionary Computation Conference. Springer, 886--897. Google ScholarDigital Library
- Steven van Dijk, Linda C Van Der Gaag, and Dirk Thierens. 2003. A Skeleton-based Approach to Learning Bayesian Networks from Data. In European Conference on Principles of Data Mining and Knowledge Discovery. Springer, 132--143.Google ScholarCross Ref
Index Terms
- Learning bayesian network structures with GOMEA
Recommendations
A cooperative coevolutionary genetic algorithm for learning bayesian network structures
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationWe propose a cooperative coevolutionary genetic algorithm for learning Bayesian network structures from fully observable data sets. Since this problem can be decomposed into two dependent subproblems, that is to find an ordering of the nodes and an ...
A memetic approach to bayesian network structure learning
EvoApplications'13: Proceedings of the 16th European conference on Applications of Evolutionary ComputationBayesian networks are graphical statistical models that represent inference between data. For their effectiveness and versatility, they are widely adopted to represent knowledge in different domains. Several research lines address the NP-hard problem of ...
Structural learning of Bayesian networks by bacterial foraging optimization
Algorithms inspired by swarm intelligence have been used for many optimization problems and their effectiveness has been proven in many fields. We propose a new swarm intelligence algorithm for structural learning of Bayesian networks, BFO-B, based on ...
Comments