Bayesian network structure learning using cooperative coevolution

ABSTRACT

We propose a cooperative-coevolution - Parisian trend - algorithm, IMPEA (Independence Model based Parisian EA), to the problem of Bayesian networks structure estimation. It is based on an intermediate stage which consists of evaluating an independence model of the data to be modelled. The Parisian cooperative coevolution is particularly well suited to the structure of this intermediate problem, and allows to represent an independence model with help of a whole population, each individual being an independence statement, i.e. a component of the independence model. Once an independence model is estimated, a Bayesian network can be built. This two level resolution of the complex problem of Bayesian network structure estimation has the major advantage to avoid the difficult problem of direct acyclic graph representation within an evolutionary algorithm, which causes many troubles related to constraints handling and slows down algorithms. Comparative results with a deterministic algorithm, PC, on two test cases (including the Insurance BN benchmark), prove the efficiency of IMPEA, which provides better results than PC in a comparable computation time, and which is able to tackle more complex issues than PC.

REFERENCES

• 1: Cédric Baudrit , Pierre-Henri Wuillemin , Mariette Sicard , Nathalie Perrot, A Dynamic Bayesian Network to Represent a Ripening Process of a Soft Mould Cheese, Proceedings of the 12th international conference on Knowledge-Based Intelligent Information and Engineering Systems, Part II, September 03-05, 2008, Zagreb, Croatia [doi>10.1007/978-3-540-85565-1_33]
• 2: John Binder , Daphne Koller , Stuart Russell , Keiji Kanazawa, Adaptive Probabilistic Networks with Hidden Variables, Machine Learning, v.29 n.2-3, p.213-244, Nov./Dec. 1997 [doi>10.1023/A:1007421730016]
• 3: Jie Cheng , David A. Bell , Weiru Liu, Learning belief networks from data: an information theory based approach, Proceedings of the sixth international conference on Information and knowledge management, p.325-331, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266920]
• 4: D. M. Chickering and C. Boutilier. Learning equivalence classes of Bayesian-network structures. In Journal of Machine Learning Research pages 150--157. Morgan Kaufmann, 1996.
• 5: David Maxwell Chickering , David Heckerman , Christopher Meek, Large-Sample Learning of Bayesian Networks is NP-Hard, The Journal of Machine Learning Research, 5, p.1287-1330, 12/1/2004
• 6: C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory 14(3):462--467, 1968.
• 7: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 8: Kalyanmoy Deb , David E. Goldberg, An Investigation of Niche and Species Formation in Genetic Function Optimization, Proceedings of the 3rd International Conference on Genetic Algorithms, p.42-50, June 01, 1989
• 9: O. Francois and P. Leray. Etude comparative d 'algorithmes d 'apprentissage de structure dans les réseaux Bayésiens. In Rencontres des Jeunes Chercheurs en IA 2003.
• 10: Nir Friedman, Learning Belief Networks in the Presence of Missing Values and Hidden Variables, Proceedings of the Fourteenth International Conference on Machine Learning, p.125-133, July 08-12, 1997
• 11: N. Friedman, M. Linial, I. Nachman, and D. Pe 'er. Using Bayesian Network to Analyze Expression Data. J. Computational Biology 7:601--620, 2000.
• 12: David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, United States
• 13: H. Jia, D. Liu, and P. Yu. Learning dynamic Bayesian network with immune evolutionary algorithm. 2005
• 14: Pedro Larrañaga , Mikel Poza , Yosu Yurramendi , Roberto H. Murga , Cindy M. H. Kuijpers, Structure Learning of Bayesian Networks by Genetic Algorithms: A Performance Analysis of Control Parameters, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.9, p.912-926, September 1996 [doi>10.1109/34.537345]
• 15: Jean Louchet , Maud Guyon , Marie-Jeanne Lesot , Amine Boumaza, Dynamic flies: a new pattern recognition tool applied to stereo sequence processing, Pattern Recognition Letters, v.23 n.1-3, p.335-345, January 2002 [doi>10.1016/S0167-8655(01)00129-5]
• 16: Evelyne Lutton , Patrice Martinez, A Genetic Algorithm with Sharing for the Detection of 2D Geometric Primitives in Images, Selected Papers from the European conference on Artificial Evolution, p.287-303, September 04-06, 1995
• 17: K. Murphy. The Bayes Net Toolbox for Matlab. Computing Science and Statistics 33(2):1024--1034, 2001.
• 18: J. W. Myers, K. B. Laskey, and K. A. DeJong. Learning Bayesian Networks from Incomplete Data using Evolutionary Algorithms. In Genetic and Evolutionary Computation Conference volume1, pages 458--465. Morgan Kaufmann, 1999.
• 19: G. Ochoa, E. Lutton, and E. Burke. The Cooperative Royal Road:Avoiding Hitchhiking. In Artificial Evolution pages 184--195, 2007.
• 20: J. Pearl and T. Verma. A theory of inferred causation. In Second International Conference on the Principles of Knowledge Representation and Reasoning 1991.
• 21: R. W. Robinson. Counting unlabeled acyclic digraphs. Combinatorial mathematics V 622:28--43, 1977.
• 22: Brian J. Ross , Eduardo Zuviria, Evolving dynamic Bayesian networks with Multi-objective genetic algorithms, Applied Intelligence, v.26 n.1, p.13-23, February 2007 [doi>10.1007/s10489-006-0002-6]
• 23: P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction, and Search The MIT Press, second edition, 2001.
• 24: A. Tucker and X. Liu. Extending Evolutionary Programming Methods to the Learning of Dynamic Bayesian Networks. In GECCO '99 1999.
• 25: S. C. Wang and S. P. Li. Learning Bayesian Networks by Lamarckian Genetic Algorithm and Its Application to Yeast Cell-Cycle Gene Network Reconstruction from Time-Series Microarray Data. 3141/2004:49--62.
• 26: M. L. Wong and K. S. Leung. An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach. 8:378--404, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
bayesian network structure learning, cooperative coevolution, independence model, parisian evolution