A chain-model genetic algorithm for Bayesian network structure learning

ABSTRACT

Bayesian Networks are today used in various fields and domains due to their inherent ability to deal with uncertainty. Learning Bayesian Networks, however is an NP-Hard task [7]. The super exponential growth of the number of possible networks given the number of factors in the studied problem domain has meant that more often, approximate and heuristic rather than exact methods are used. In this paper, a novel genetic algorithm approach for reducing the complexity of Bayesian network structure discovery is presented. We propose a method that uses chain structures as a model for Bayesian networks that can be constructed from given node orderings. The chain model is used to evolve a small number of orderings which are then injected into a greedy search phase which searches for an optimal structure. We present a series of experiments that show a significant reduction can be made in computational cost although with some penalty in success rate.

REFERENCES

• 1: Bayesia. Bayesialab Bayesian network software. http://www.bayesia.com/.
• 2: I. A. Beinlich, H. J. Suermondt, R. M. Chavez, and G. F. Cooper. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks,. Proceedings of the Second European Conference on Artificial Intelligence in Medical Care, Springer-Verlag, Berlin. pages 247--256, 1989.
• 3: BNJ. Bayesian network tools in Java. http://bnj.sourceforge.net/.
• 4: Remco R. Bouckaert, Probalistic Network Construction Using the Minimum Description Length Principle, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, p.41-48, November 08-10, 1993
• 5: R. R. Bouckaert. Bayesian Belief Networks: From Construction to Inference PhDthesis, University of Utrecht, 1995.
• 6: W. Buntine. Operations for learning with graphical models. Journal of Artificial Intelligence Research 2: 159--225, 1994.
• 7: D. Chickering. Learning Bayesian networks is NP-Complete. In Proceedings of AI and Statistics 1995.
• 8: 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
• 9: C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory 14: 462--467, 1968.
• 10: 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]
• 11: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan , David J. Spiegelhater, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 12: L. de Campos and J. Huete. On the use of independence relationships for learning simplified belief networks. International Journal of Intelligent Systems 12: 495--522, 1997.
• 13: N. Friedman and M. Goldszmidt. Learning Bayesian networks with local structure. Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence pages 252--262, 1996.
• 14: N. Friedman, I. Nachman, and D. Peér. Learning Bayesian network structure from massive datasets: The "sparse candidate" algorithm. In Uncertainty in Artificial Intelligence pages 206--215, 1999.
• 15: J. Habrant. Structure learning of Bayesian networks from databases by genetic algorithms-application to time series prediction in. nance. In ICEIS pages 225--231, 1999.
• 16: D. Heckerman, D. Geiger, and D. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. In KDD Workshop pages 85--96, 1994.
• 17: M. Koivisto and K. Sood. Exact bayesian structure discovery in Bayesian networks, 2004.
• 18: P. Larrañaga, C. Kuijpers, and R. Murga. Learning Bayesian network structures by searching for the best ordering with genetic algorithms. IEEE Transactions on System, Man and Cybernetics 26: 487--493, 1996.
• 19: P. Larrañaga and Y. Yurramendi. Structure learning approaches in causal probabilistic networks, 1998.
• 20: S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society 50(2): 157--224, 1988.
• 21: Netica. Netica Bayesian network software from Norsys. http: //www.norsys.com.
• 22: A. J. Novobilski. The random selection and manipulation of legally encoded Bayesian networks in genetic algorithms. In IC-AI pages 438--443, 2003.
• 23: G. Provan and M. Singh. Learning Bayesian networks using feature selection. 1995.
• 24: R. Robinson. Counting labeled acyclic digraphs. New Directions in the Theory of Graphs, In Frank Harary, editor. Academic Press, New York pages 239--273, 1973.
• 25: P. Spirtes, C. Glymour, and R. Scheines. Causation, Prediction and Search. Lecture Notes in Statistics, New York: Springer Verlag 81, 1993.
• 26: M. Teyssier and D. Koller. Ordering-based search: A simple and effective algorithm for learning Bayesian networks. In Proceedings of the 21th Annual Conference on Uncertainty in Artificial Intelligence pages 584--59, Arlington, Virginia, 2005. AUAI Press.
• 27: S. van Dijk, D. Thierens, and L. C. van der Gaag. Building a GA from design principles for learning Bayesian networks. In GECCO pages 886--897, 2003.
• 28: L. Darrell Whitley, The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best, Proceedings of the 3rd International Conference on Genetic Algorithms, p.116-123, June 01, 1989
• 29: Man Leung Wong , Shing Yan Lee , Kwong-Sak Leung, A Hybrid Data Mining Approach To Discover Bayesian Networks Using Evolutionary Programming, Proceedings of the Genetic and Evolutionary Computation Conference, p.214-222, July 09-13, 2002
• 30: O. Woodberry, A. Nicholson, K. Korb, and C. Pollino. Parameterising Bayesian networks. In Australian Conference on Artificial Intelligence pages 1101--1107, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Bayesian networks, genetic algorithms, greedy search