article

Resampling methods for meta-model validation with recommendations for evolutionary computation

Authors:

C. WeihsAuthors Info & Claims

Evolutionary Computation, Volume 20, Issue 2

Pages 249 - 275

https://doi.org/10.1162/EVCO_a_00069

Published: 01 June 2012 Publication History

Abstract

Meta-modeling has become a crucial tool in solving expensive optimization problems. Much of the work in the past has focused on finding a good regression method to model the fitness function. Examples include classical linear regression, splines, neural networks, Kriging and support vector regression. This paper specifically draws attention to the fact that assessing model accuracy is a crucial aspect in the meta-modeling framework. Resampling strategies such as cross-validation, subsampling, bootstrapping, and nested resampling are prominent methods for model validation and are systematically discussed with respect to possible pitfalls, shortcomings, and specific features. A survey of meta-modeling techniques within evolutionary optimization is provided. In addition, practical examples illustrating some of the pitfalls associated with model selection and performance assessment are presented. Finally, recommendations are given for choosing a model validation technique for a particular setting.

References

[1]

Alpaydin, E. (1999). Combined 5×2CV F test for comparing supervised classification learning algorithms. Neural Computation, 11:1885-1892.

[2]

Bartlett, P., Boucheron, S., and Lugosi, G. (2002). Model selection and error estimation. Machine Learning, 48(1-3):85-113.

[3]

Bartz-Beielstein, T. (2006). Experimental research in evolutionary computation; The new experimentalism. Berlin: Springer.

[4]

Bengio, Y., and Grandvalet, Y. (2004). No unbiased estimator of the variance of k-fold cross-validation. Journal of Machine Learning Research, 5:1089-1105.

[5]

Bhattacharya, M. (2008). Meta model based EA for complex optimization. International Journal of Computational Intelligence, 1(4):36-45.

[6]

Binder, H., and Schumacher, M. (2008). Adapting prediction error estimates for biased complexity selection in high-dimensional bootstrap samples. Statistical Applications in Genetics and Molecular Biology, 7(1):12.

[7]

Birattari, M., Stützle, T., Paquete, L., and Varrentrapp, K. (2002). A racing algorithm for configuring metaheuristics. In W. Langdon (Ed.), Genetic and Evolutionary Computation Conference (GECCO), pp. 11-18.

[8]

Bischl, B. (2010). MLR: Machine learning in R. Retrieved from http://mlr.r-forge.r-project.org

[9]

Büche, D., Schraudolph, N. N., and Koumoutsakos, P. (2004). Accelerating evolutionary algorithms with Gaussian process fitness function models. IEEE Transactions on Systems, Man and Cybernetics, 35:183-194.

[10]

Cawley, G., and Talbot, N. (2004). Fast exact leave-one-out cross-validation of sparse least-squares support vector machines. Neural Networks, 17(10):1467-1475.

[11]

Diamantidis, N., Karlis, D., and Giakoumakis, E. (2000). Unsupervised stratification of cross-validation for accuracy estimation. Artificial Intelligence, 116(1-2):1-16.

[12]

Dietterich, T. (1998). Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10(7):1895-1923.

[13]

Efron, B. (1979). Bootstrap methods: Another look at the jackknife. The Annals of Statistics, 7(1):1-26.

[14]

Efron, B. (1983). Estimating the error rate of a prediction rule: Improvement on cross-validation. Journal of the American Statistical Association, 78(382):316-331.

[15]

Efron, B., and Tibshirani, R. (1997). Improvements on cross-validation: The 0.632 + bootstrap method. Journal of the American Statistical Association, 92(438):548-560.

[16]

El-Beltagy, M., Nair, P. B., and Keane, A. J. (1999). Metamodeling techniques for evolutionary optimization of computationally expensive problems: Promises and limitations. In Genetic and Evolutionary Computation Conference (GECCO), pp. 196-203.

[17]

Emmerich, M., Giannakoglou, K., and Naujoks, B. (2006). Single- and multiobjective evolutionary optimization assisted by Gaussian random field metamodels. IEEE Transactions on Evolutionary Computation, 10(4):421-439.

[18]

Fiebrink, R., and Fujinaga, I. (2006). Feature selection pitfalls and music classification. In Proceedings of the Eleventh International Society forMusic Information Retrieval Conference (ISMIR), pp. 340-341.

[19]

Fu, W. J., Carroll, R. J., and Wang, S. (2005). Estimating misclassification error with small samples via bootstrap cross-validation. Bioinformatics, 21(9):1979-1986.

[20]

Giotis, A. P., and Giannakoglou, K. C. (1999). Single- and multi-objective airfoil design using genetic algorithms and artificial intelligence. In EUROGEN 99, Evolutionary Algorithms in Engineering and Computer Science.

[21]

Good, P. (2005). Resampling methods: A practical guide to data analysis. Basel, Switzerland: Birkhauser.

[22]

Hastie, T., Tibshirani, R., and Friedman, J. (2001). The elements of statistical learning. Berlin: Springer.

[23]

Hothorn, T., Leisch, F., Zeileis, A., and Hornik, K. (2005). The design and analysis of benchmark experiments. Journal of Computational and Graphical Statistics, 14:675-699.

[24]

Huang, D., Allen, T., Notz, W., and Zeng, N. (2006). Global optimization of stochastic black-box systems via sequential Kriging meta-models. Journal of Global Optimization, 34(3):441-466.

[25]

Jin, R., Chen, W., and Simpson, T. (2000). Comparative studies of metamodeling techniques under multiple modeling criteria. Structural and Multidisciplinary Optimization, 23:1-13.

[26]

Jin, Y. (2005). A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing, 9(1):3-12.

[27]

Jin, Y., and Brank, J. (2005). Evolutionary optimization in uncertain environments: A survey. IEEE Transactions on Evolutionary Computation, 9(3):303-318.

[28]

Jin, Y., Olhofer, M., and Sendhoff, B. (2000). On evolutionary optimization with approximate fitness functions. In Genetic and Evolutionary Computation Conference (GECCO), pp. 786-793.

[29]

Jin, Y., Olhofer, M., and Sendhoff, B. (2002). A framework for evolutionary optimization with approximate fitness functions. IEEE Transactions on Evolutionary Computation, 6:481-494.

[30]

Jones, D., Schonlau, M., and Welch, W. (1998). Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-492.

[31]

Kampolis, I. C., Zymaris, A. S., Asouti, V. G., and Giannakoglou, K. C. (2007). Multilevel optimization strategies based on metamodel-assisted evolutionary algorithms, for computationally expensive problems. In K. C. Tan and J.-X. Xu (Eds.), IEEE Congress on Evolutionary Computation (CEC), pp. 4116-4123.

[32]

Kern, S., Hansen, N., and Koumoutsakos, P. (2006). Local meta-models for optimization using evolution strategies. In Parallel problem solving from nature, PPSN IX, pp. 939-948.

[33]

Kim, J.-H. (2009). Estimating classification error rate: Repeated cross-validation, repeated holdout and bootstrap. Computational Statistics and Data Analysis, 53(11):3735-3745.

[34]

Knowles, J., and Nakayama, H. (2008). Meta-modeling in multiobjective optimization. In Multi-objective optimization: Interactive and evolutionary approaches (pp. 245-284). Berlin: Springer.

[35]

Kohavi, R. (1995). A study of cross-validation and bootstrap for accuracy estimation and model selection. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 1137-1143.

[36]

Kruisselbrink, J.W., Emmerich, M. T.M., Deutz, A. H., and Bäck, T. (2010). A robust optimization approach using Kriging metamodels for robustness approximation in the CMA-ES. In IEEE Congress on Evolutionary Computation (CEC), pp. 1-8.

[37]

Lim, D., Jin, Y., Ong, Y.-S., and Sendhoff, B. (2010). Generalizing surrogate-assisted evolutionary computation. IEEE Transactions on Evolutionary Computation, 14(3):329-355.

[38]

Loshchilov, I., Schoenauer, M., and Sebag, M. (2010). Comparison-based optimizers need comparison-based surrogates. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (pp. 364-373). Berlin: Springer.

[39]

Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., and Rudolph, G. (2011). Exploratory landscape analysis. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 829-836.

[40]

Mersmann, O., Preuss, M., and Trautmann, H. (2010). Benchmarking evolutionary algorithms: Towards exploratory landscape analysis. In Parallel problem solving from nature (PPSN). Lecture notes in computer science, Vol. 6238 (pp. 73-82). Berlin: Springer.

[41]

Molinaro, A., Simon, R., and Pfeiffer, R. (2005). Prediction error estimation: A comparison of resampling methods. Bioinformatics, 21(15):3301-3307.

[42]

Mukhopadhyay, N., and de Silva, B.M. (2009). Sequential methods and their applications. New York: Chapman & Hall/CRC.

[43]

Myers, R., and Montgomery, D. (1995). Response surface methodology. New York: Wiley.

[44]

Nadeau, C., and Bengio, Y. (2003). Inference for the generalization error. Machine Learning, 52(3):239-281.

[45]

Nakayama, H., Yun, Y., and Yoon, M. (2009). Sequential approximate multiobjective optimization using computational intelligence. Berlin: Springer.

[46]

Ong, Y., Nair, P., and Keane, A. (2003). Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA Journal, 41(4):687-696.

[47]

Ong, Y., Zhou, Z., and Lim, D. (2006). Curse and blessing of uncertainty in evolutionary algorithms using approximation. In IEEE Congress on Evolutionary Computation (CEC), pp. 2928-2935.

[48]

Paenke, I., Branke, J., and Jin, Y. (2006). Efficient search for robust solutions bymeans of evolutionary algorithms and fitness approximation. IEEE Transactions on Evolutionary Computation, 10(4):405-420.

[49]

Salzberg, S. (1997). On comparing classifiers: Pitfalls to avoid and a recommended approach. Data Mining and Knowledge Discovery, 1(3):317-328.

[50]

Sanchez, E., Pintos, S., and Queipo, N. (2008). Toward an optimal ensemble of kernel-based approximations with engineering applications. Structural and Multidisciplinary Optimization, 36(3):247-261.

[51]

Santers, T., Williams, N., and Notz, W. (2003). The design and analysis of computer experiments. Berlin: Springer.

[52]

Shao, J. (1993). Linear model selection by cross-validation. Journal of the American Statistical Association, 88(422):486-494.

[53]

Shi, L., and Rasheed, K. (2010). A survey of fitness approximation methods applied in evolutionary algorithms. Computational intelligence in expensive optimization problems (pp. 3-28). Berlin: Springer.

[54]

Simon, R. (2007). Resampling strategies for model assessment and selection. In Fundamentals of data mining in genomics and proteomics (pp. 173-186). Berlin: Springer.

[55]

Simon, R., Radmacher, M. D., Dobbin, K., and McShane, L. M. (2003). Pitfalls in the use of DNA microarray data for diagnostic and prognostic classification. Journal of the National Cancer Institute, 95(1):14-18.

[56]

Simpson, T., Mauery, T., Korte, J., and Mistree, F. (1998). Comparison of response surface and Kriging models for multidisciplinary design optimization. In Proceedings of the 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, pp. 98-4755.

[57]

Smit, S., and Eiben, A. (2009). Comparing parameter tuningmethods for evolutionary algorithms. In A. Tyrrell (Ed.), IEEE Congress on Evolutionary Computation (CEC), pp. 399-406.

[58]

Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society, Series B, 36(1):111-147.

[59]

Stone, M. (1977). An asymptotic equivalence of choice of model by cross-validation and Akaike's criterion. Journal of the Royal Statistical Society, Series B, 39:44-47.

[60]

Sundararajan, S., and Keerthi, S. (2001). Predictive approaches for choosing hyperparameters in Gaussian processes. Neural Computation, 13(5):1103-1118.

[61]

Tenne, Y., and Armfield, S. (2008). Metamodel accuracy assessment in evolutionary optimization. In IEEE Congress on Evolutionary Computation (CEC), pp. 1505-1512.

[62]

Ulmer, H., Streichert, F., and Zell, A. (2003). Evolution strategies assisted by Gaussian processes with improved pre-selection criterion. In IEEE Congress on Evolutionary Computation (CEC), pp. 692-699.

[63]

Vladislavleva, E., Smits, G., and Kotanchek, M. (2007). Better solutions faster: Soft evolution of robust regression models in Pareto genetic programming. In R. L. Riolo, T. Soule, and B. Worzel (Eds.), Genetic programming theory and practice V, Genetic and evolutionary computation (chap. 2, pp. 13-32). Berlin: Springer.

[64]

Wagner, T., Emmerich, M., Deutz, A., and Ponweiser, W. (2010). On expected-improvement criteria for model-based multi-objective optimization. In R. Schaefer (Ed.), Parallel Problem Solving from Nature (PPSN), pp. 718-727.

[65]

Wahba, G. (1980). Spline bases, regularization, and generalized cross validation for solving approximation problems with large quantities of noisy data. In International Conference on Approximation Theory in Honour of George Lorenz.

[66]

Weihs, C. (1993). Canonical discriminant analysis: Comparison of resampling methods and convex-hull approximation. Information and Classification (pp. 225-238). Berlin: Springer.

[67]

Weiss, S., and Kulikowski, C. (1991). Computer systems that learn: Classification and prediction methods from statistics, neural nets, machine learning, and expert systems. San Mateo, CA: Morgan Kaufmann.

[68]

Wu, C. (1986). Jackknife, bootstrap and other resampling methods in regression analysis. Annals of Statistics, 14:1261-1295.

[69]

Younis, A., and Dong, Z. (2010). Metamodelling using search space exploration and unimodal region elimination for design optimization. Engineering Optimization, 6(42):517-533.

[70]

Yun, Y., Yoon, M., and Nakayama, H. (2009). Multi-objective optimisation based on meta-modelling using support vector regression. Optimization and Engineering, 10(2):167-181.

[71]

Zhou, Z., Ong, Y.-S., Nair, P., Keane, A., and Lum, K. (2007). Combining global and local surrogate models to accelerate evolutionary optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 37(1):66-76.

Cited By

Koch TRomero PStachl C(2022)Age and gender in language, emoji, and emoticon usage in instant messagesComputers in Human Behavior10.1016/j.chb.2021.106990126:COnline publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.chb.2021.106990
Muñoz MKirley MSmith-Miles K(2022)Analyzing randomness effects on the reliability of exploratory landscape analysisNatural Computing: an international journal10.1007/s11047-021-09847-121:2(131-154)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11047-021-09847-1
Morales-Hernández AVan Nieuwenhuyse IRojas Gonzalez S(2022)A survey on multi-objective hyperparameter optimization algorithms for machine learningArtificial Intelligence Review10.1007/s10462-022-10359-256:8(8043-8093)Online publication date: 24-Dec-2022
https://dl.acm.org/doi/10.1007/s10462-022-10359-2
Show More Cited By

Resampling methods for meta-model validation with recommendations for evolutionary computation
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Analysis of evolutionary multi-tasking as an island model
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Recently, an idea of evolutionary multi-tasking has been proposed and applied to various types of optimization problems. The basic idea of evolutionary multi-tasking is to simultaneously solve multiple optimization problems (i.e., tasks) in a ...
Investigating the local-meta-model CMA-ES for large population sizes
EvoApplicatons'10: Proceedings of the 2010 international conference on Applications of Evolutionary Computation - Volume Part I

For many real-life engineering optimization problems, the cost of one objective function evaluation can take several minutes or hours. In this context, a popular approach to reduce the number of function evaluations consists in building a (meta-)model ...
The ($$1+\lambda $$1+ý) Evolutionary Algorithm with Self-Adjusting Mutation Rate

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Evolutionary Computation

Evolutionary Computation Volume 20, Issue 2

Summer 2012

155 pages

ISSN:1063-6560

EISSN:1530-9304

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 June 2012

Published in EVOL Volume 20, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
188
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Koch TRomero PStachl C(2022)Age and gender in language, emoji, and emoticon usage in instant messagesComputers in Human Behavior10.1016/j.chb.2021.106990126:COnline publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1016/j.chb.2021.106990
Muñoz MKirley MSmith-Miles K(2022)Analyzing randomness effects on the reliability of exploratory landscape analysisNatural Computing: an international journal10.1007/s11047-021-09847-121:2(131-154)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11047-021-09847-1
Morales-Hernández AVan Nieuwenhuyse IRojas Gonzalez S(2022)A survey on multi-objective hyperparameter optimization algorithms for machine learningArtificial Intelligence Review10.1007/s10462-022-10359-256:8(8043-8093)Online publication date: 24-Dec-2022
https://dl.acm.org/doi/10.1007/s10462-022-10359-2
Esmaeili AGhorrati ZMatson E(2022)Hierarchical Collaborative Hyper-Parameter TuningAdvances in Practical Applications of Agents, Multi-Agent Systems, and Complex Systems Simulation. The PAAMS Collection10.1007/978-3-031-18192-4_11(127-139)Online publication date: 13-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-18192-4_11
Probst PBoulesteix ABischl B(2021)TunabilityThe Journal of Machine Learning Research10.5555/3322706.336199420:1(1934-1965)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3361994
Talbi E(2021)Automated Design of Deep Neural NetworksACM Computing Surveys10.1145/343973054:2(1-37)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3439730
Farzana WTemtam AShboul ZRahman MSadique MIftekharuddin K(2021)Radiogenomic Prediction of MGMT Using Deep Learning with Bayesian Optimized HyperparametersBrainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries10.1007/978-3-031-09002-8_32(357-366)Online publication date: 27-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-031-09002-8_32
Molnar CKönig GHerbinger JFreiesleben TDandl SScholbeck CCasalicchio GGrosse-Wentrup MBischl B(2020)General Pitfalls of Model-Agnostic Interpretation Methods for Machine Learning ModelsxxAI - Beyond Explainable AI10.1007/978-3-031-04083-2_4(39-68)Online publication date: 18-Jul-2020
https://dl.acm.org/doi/10.1007/978-3-031-04083-2_4
Derbel BLiefooghe AVerel SAguirre HTanaka KFriedrich TDoerr CArnold D(2019)New features for continuous exploratory landscape analysis based on the SOO treeProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340308(72-86)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340308
Lapp LBouamrane MKavanagh KRoper MYoung DSchraag S(2019)Evaluation of Random Forest and Ensemble Methods at Predicting Complications Following Cardiac SurgeryArtificial Intelligence in Medicine10.1007/978-3-030-21642-9_48(376-385)Online publication date: 26-Jun-2019
https://dl.acm.org/doi/10.1007/978-3-030-21642-9_48
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents