Improved EDNA (estimation of dependency networks algorithm) using combining function with bivariate probability distributions

ABSTRACT

One of the key points in Estimation of Distribution Algorithms (EDAs) is the learning of the probabilistic graphical model used to guide the search: the richer the model the more complex the learning task. Dependency networks-based EDAs have been recently introduced. On the contrary of Bayesian networks, dependency networks allow the presence of directed cycles in their structure. In a previous work the authors proposed EDNA, an EDA algorithm in which a multivariate dependency network is used but approximating its structure learning by considering only bivariate statistics. EDNA was compared with other models from the literature with the same computational complexity (e.g., univariate and bivariate models). In this work we propose a modified version of EDNA in which not only the structural learning phase is limited to bivariate statistics, but also the simulation and the parameter learning task. Now, we extend the comparison employing multivariate models based on Bayesian networks (EBNA and hBOA). Our experiments show that the modified EDNA is more accurate than the original one, being its accuracy comparable to EBNA and hBOA, but with the advantage of being faster specially in the more complex cases.

REFERENCES

• 1: S. Baluja and S. Davies. Combining Multiple Optimization Runs with Optimal Dependency Trees. Technical Report CMU-CS-97-157, Carnegie Mellon University, 1997.
• 2: J. S. D. Bonet, C. L. Isbell, and P. Viola. MIMIC: Finding optima by estimating probability densities. In Advances in Neural Information Processing Systems, volume 9, pages 424--430. MIT Press, Cambridge, 1997.
• 3: N. Friedman and M. Goldszmidt. Learning bayesian networks with local structure. In 12th Annual Conference on Uncertainty in Artificial Intelligence (UAI-96), pages 252--262, 1996.
• 4: J. A. Gámez, J. L. Mateo, and J. M. Puerta. Dependency networks based classifiers: learning models by using independence test. In Third European Workshop on Probabilistica Graphical Models (PGM06), pages 115--122, 2006.
• 5: J. A. Gámez, J. L. Mateo, and J. M. Puerta. EDNA: Estimation of Dependency Networks Algorithm. In International Work-Conference on the Interplay between Natural and Artificial Computation (IWINAC'07), volume 1, pages 427--436, 2007.
• 6: S. Geman and D. Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:147--156, 1984.
• 7: D. E. Goldberg, K. Deb, and J. Horn. Massive multimodality, deception, and genetic algorithms. In Parallel Problem Solving from Nature (PPSN), volume 2, 1992.
• 8: G. Harik. Linkage learning in via probabilistic modelling in the EcGA. Technical Report 99010, Illinois Genetic Algorithms Laboratory, 1999.
• 9: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 10: G. Harik, F. G. Lobo, and D. E. Golberg. The compat genetic algorithm. In Proceedings of the 4th International Conference on Evolutionary Computation, pages 1--5, 1997.
• 11: D. Heckerman. A Tutorial on Learning Bayesian Networks. Technical Report MSR-TR-95--06, Microsoft Research, Mar. 1995.
• 12: David Heckerman , David Maxwell Chickering , Christopher Meek , Robert Rounthwaite , Carl Kadie, Dependency networks for inference, collaborative filtering, and data visualization, The Journal of Machine Learning Research, 1, p.49-75, 9/1/2001 [doi>10.1162/153244301753344614]
• 13: D. Heckerman, D. Geiger, and D. M. Chickering. Learning bayesian networks: The combination of knowledge and statistical data. In 10th Conf. Uncertainty in Artificial Intelligence, pages 293--301. Morgan Kaufmann Publishers, 1994.
• 14: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 15: Manfred Jaeger, Complex Probabilistic Modeling with Recursive Relational Bayesian Networks, Annals of Mathematics and Artificial Intelligence, v.32 n.1-4, p.179-220, August 2001 [doi>10.1023/A:1016713501153]
• 16: Pedro Larrañaga , Ramon Etxeberria , Jose Antonio Lozano , Jose Manuel Peña, Combinatonal Optimization by Learning and Simulation of Bayesian Networks, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.343-352, June 30-July 03, 2000
• 17: J. L. Mateo and L. de la Ossa. LiO: an easy and exible library of metaheuristics. Technical Report DIAB-06-04-1, Departamento de Sistemas Informaticos, Escuela Politecnica Superior de Albacete, Universidad de Castilla-La Mancha, 2006.
• 18: Heinz Mühlenbein, The equation for response to selection and its use for prediction, Evolutionary Computation, v.5 n.3, p.303-346, Fall 1997 [doi>10.1162/evco.1997.5.3.303]
• 19: Heinz Mühlenbein , Thilo Mahnig , Alberto Ochoa Rodriguez, Schemata, Distributions and Graphical Models in Evolutionary Optimization, Journal of Heuristics, v.5 n.2, p.215-247, July 1999 [doi>10.1023/A:1009689913453]
• 20: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 21: Jennifer Neville , David Jensen, Relational Dependency Networks, The Journal of Machine Learning Research, 8, p.653-692, 5/1/2007
• 22: A. Onisko, M. J. Druzdzel, and H. Wasyluk. Learning bayesian network parameters from small data sets: Application of noisy-or gates. International Journal of Approximate Reasoning, 27(2):165--182, 2001.
• 23: J Pearl, Fusion, propagation, and structuring in belief networks, Artificial Intelligence, v.29 n.3, p.241-288, Sept. 1986 [doi>10.1016/0004-3702(86)90072-X]
• 24: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 25: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, San Francisco, California, USA, 7--11 2001. Morgan Kaufmann.
• 26: Roberto Santana, Estimation of Distribution Algorithms with Kikuchi Approximations, Evolutionary Computation, v.13 n.1, p.67-97, January 2005 [doi>10.1162/1063656053583496]
• 27: G. Schwarz. Estimating the dimension of a model. Annals of Statistics, 6(2):461--464, 1978.
• 28: Yonghong Tian , Qiang Yang , Tiejun Huang , Charles X. Ling , Wen Gao, Learning Contextual Dependency Network Models for Link-Based Classification, IEEE Transactions on Knowledge and Data Engineering, v.18 n.11, p.1482-1496, November 2006 [doi>10.1109/TKDE.2006.178]
• 29: Richard A. Watson , Greg Hornby , Jordan B. Pollack, Modeling Building-Block Interdependency, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.97-108, September 27-30, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Design

Keywords:
combinatorial optimization, dependency networks, estimation of distribution algorithms, probability combining function, scalability