Combinatorial effects of local structures and scoring metrics in bayesian optimization algorithm

ABSTRACT

Bayesian Optimization Algorithm (BOA) has been used with different local structures to represent more complex models and a variety of scoring metrics to evaluate Bayesian network. But the combinatorial effects of these elements on the performance of BOA have not been investigated yet. In this paper the performance of BOA is studied using two criteria: Number of fitness evaluations and structural accuracy of the model. It is shown that simple exact local structures like CPT in conjunction with complexity penalizing BIC metric outperforms others in terms of model accuracy. But considering number of fitness evaluations (efficiency) of the algorithm, CPT with other complexity penalizing metric K2P performs better.

REFERENCES

• 1: Chickering, D. M. 1996. Learning Bayesian networks is NP-Complete. Learning from Data: Artificial Intelligence and Statistics, vol. V, 121--130.
• 2: Chickering, D. M., Heckerman, D. and Meek, C. 1997. A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSRTR-97-07, Microsoft Research, Redmond, WA.
• 3: Correa, E. S. and Shapiro, J. L. 2006. Model Complexity vs. Performance in the Bayesian Optimization Algorithm. Proceedings of 9th International Conference on Parallel Problem Solving from Nature (PPSN IX), Springer, 998--1007.
• 4: Echegoyen, C., Lozano, J. A., Santana, R. and Larranaga, P. 2007. Exact Bayesian network learning in estimation of distribution algorithms. IEEE Congress on Evolutionary Computation (CEC 2007), 1051--1058.
• 5: Etxeberria, R. and Larranaga, P. 1999. Global optimization using Bayesian networks. Proceedings of the Second Symposium on Artificial Intelligence (CIMAF-99), A. Ochoa, M. R. Soto, and R. Santana, Eds., Habana, Cuba, 151--173.
• 6: Mark Hauschild , Martin Pelikan , Claudio F. Lima , Kumara Sastry, Analyzing probabilistic models in hierarchical BOA on traps and spin glasses, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277070]
• 7: Karshenas, H., Nikanjam, A., Rahmani, A. 2008. On the Effect of Scoring Metrics in the Bayesian Optimization Algorithm, to be appeared in the electronic proceeding of Learning and Intelligence Optimization Conference (LION3), Trento, Italy.
• 8: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 9: Claudio F. Lima , Fernando G. Lobo , Martin Pelikan, From mating pool distributions to model overfitting, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389174]
• 10: Lima, C. F., Pelikan, M., Goldberg, D. E., Lobo, F. G., F. G. Sastry, F. G. and Hauschild, M. 2007. Influence of selection and replacement strategies on linkage learning in BOA. IEEE Congress on Evolutionary Computation (CEC 2007), 1083--1090.
• 11: Heinz Mühlenbein , Thilo Mahnig, Fda -a scalable evolutionary algorithm for the optimization of additively decomposed functions, Evolutionary Computation, v.7 n.4, p.353-376, Winter 1999 [doi>10.1162/evco.1999.7.4.353]
• 12: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 13: Pelikan, M. 2005. Hierarchical Bayesian Optimization Algorithm, Springer-Verlag, Berlin.
• 14: Pelikan, M., Goldberg, D. E. and Cantu-Paz, E. 1999. BOA: The Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), Orlando, FL: Morgan Kaufmann Publishers, San Francisco, CA, vol. I, 525--532.
• 15: Pelikan, M., Goldberg, D. E. and Sastry, K. 2001. Bayesian optimization algorithm, decision graphs, and Occam's razor. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), 519--526.
• 16: Martin Pelikan , Kumara Sastry , David E. Goldberg, Sporadic model building for efficiency enhancement of the hierarchical BOA, Genetic Programming and Evolvable Machines, v.9 n.1, p.53-84, March 2008 [doi>10.1007/s10710-007-9052-8]
• 17: Schwarz, G. 1978. Estimating the dimension of a model. Annals of Statistics, vol. 7, no. 2, 461--464.

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
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bayesian optimization algorithm, estimation of distribution algorithms, local structures, scoring metrics