nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Exploratory Landscape Analysis is Strongly Sensitive to the Sampling Strategy

verfasst von : Quentin Renau, Carola Doerr, Johann Dreo, Benjamin Doerr

Erschienen in: Parallel Problem Solving from Nature – PPSN XVI

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Exploratory landscape analysis (ELA) supports supervised learning approaches for automated algorithm selection and configuration by providing sets of features that quantify the most relevant characteristics of the optimization problem at hand. In black-box optimization, where an explicit problem representation is not available, the feature values need to be approximated from a small number of sample points. In practice, uniformly sampled random point sets and Latin hypercube constructions are commonly used sampling strategies.

In this work, we analyze how the sampling method and the sample size influence the quality of the feature value approximations and how this quality impacts the accuracy of a standard classification task. While, not unexpectedly, increasing the number of sample points gives more robust estimates for the feature values, to our surprise we find that the feature value approximations for different sampling strategies do not converge to the same value. This implies that approximated feature values cannot be interpreted independently of the underlying sampling strategy. As our classification experiments show, this also implies that the feature approximations used for training a classifier must stem from the same sampling strategy as those used for the actual classification tasks.

As a side result we show that classifiers trained with feature values approximated by Sobol’ sequences achieve higher accuracy than any of the standard sampling techniques. This may indicate improvement potential for ELA-trained machine learning models.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Global Landscape Structure and the Random MAX-SAT Phase Transition

Nächstes Kapitel One PLOT to Show Them All: Visualization of Efficient Sets in Multi-objective Landscapes

Note here that flacco covers 343 features in total, which are grouped into 17 feature sets [13]. However, following the discussion in [27] we only use 6 of these sets: dispersion (disp), information content (ic), nearest better clustering (nbc), meta model (ela_meta), y-distribution (ela_distr), and principal component analysis (pca).

Beachkofski, B., Grandhi, R.: Improved distributed hypercube sampling. In: 43rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference. American Institute of Aeronautics and Astronautics (2002). https://doi.org/10.2514/6.2002-1274

Belkhir, N., Dréo, J., Savéant, P., Schoenauer, M.: Surrogate assisted feature computation for continuous problems. In: Festa, P., Sellmann, M., Vanschoren, J. (eds.) LION 2016. LNCS, vol. 10079, pp. 17–31. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50349-3_2CrossRef

Belkhir, N., Dréo, J., Savéant, P., Schoenauer, M.: Per instance algorithm configuration of CMA-ES with limited budget. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO), pp. 681–688. ACM (2017). https://doi.org/10.1145/3071178.3071343

Cauwet, M., et al.: Fully parallel hyperparameter search: reshaped space-filling. CoRR abs/1910.08406 (2019). http://arxiv.org/abs/1910.08406

Derbel, B., Liefooghe, A., Vérel, S., Aguirre, H., Tanaka, K.: New features for continuous exploratory landscape analysis based on the SOO tree. In: Proceedings of Foundations of Genetic Algorithms (FOGA), pp. 72–86. ACM (2019). https://doi.org/10.1145/3299904.3340308

Dick, J., Pillichshammer, F.: Digital Nets and Sequences. Cambridge University Press, Cambridge (2010)CrossRef

Doerr, C., Dréo, J., Kerschke, P.: Making a case for (hyper-)parameter tuning as benchmark problems. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO, Companion), pp. 1755–1764. AMC (2019). https://doi.org/10.1145/3319619.3326857

Garden, R.W., Engelbrecht, A.P.: Analysis and classification of optimisation benchmark functions and benchmark suites. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2014), pp. 1641–1649. IEEE (2014). https://doi.org/10.1109/CEC.2014.6900240

Hansen, N., Auger, A., Mersmann, O., Tusar, T., Brockhoff, D.: COCO: a platform for comparing continuous optimizers in a black-box setting. CoRR abs/1603.08785 (2016). http://arxiv.org/abs/1603.08785

10.

Hansen, N., Finck, A.A.S., Ros, R.: Real-Parameter Black-box Optimization Benchmarking: Experimental Setup. RR-7215, INRIA (2010). https://hal.inria.fr/inria-00462481

11.

Hutter, F., Kotthoff, L., Vanschoren, J. (eds.): Automated Machine Learning. TSSCML. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05318-5CrossRef

12.

Jankovic, A., Doerr, C.: Adaptive landscape analysis. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO 2019), pp. 2032–2035. ACM (2019)

13.

Kerschke, P., Hoos, H., Neumann, F., Trautmann, H.: Automated algorithm selection: survey and Perspectives. Evol. Comput. 27(1), 3–45 (2019)CrossRef

14.

Kerschke, P., Preuss, M., Wessing, S., Trautmann, H.: Low-budget exploratory landscape analysis on multiple peaks models. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO), pp. 229–236. ACM (2016). https://doi.org/10.1145/2908812.2908845

15.

Kerschke, P., Trautmann, H.: The R-package FLACCO for exploratory landscape analysis with applications to multi-objective optimization problems. In: Proceedings of CEC, pp. 5262–5269. IEEE (2016). flacco is available at http://kerschke.github.io/flacco/

16.

Kerschke, P., Trautmann, H.: Automated algorithm selection on continuous black-box problems by combining exploratory landscape analysis and machine learning. Evol. Comput. 27(1), 99–127 (2019). https://doi.org/10.1162/evco_a_00236CrossRef

17.

Knuth, D.: The Art of Computer Programming: Seminumerical Algorithms. Addison-Wesley, Boston (1998)MATH

18.

Malan, K., Engelbrecht, A.P.: A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf. Sci. 241, 148–163 (2013). https://doi.org/10.1016/j.ins.2013.04.015CrossRef

19.

Matoušek, J.: Geometric Discrepancy, 2nd edn. Springer, Heidelberg (2009)MATH

20.

Matsumoto, M., Nishimura, T.: Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998). https://doi.org/10.1145/272991.272995CrossRefMATH

21.

McKay, M., Beckman, R., Conover, W.: A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, 239–245 (1979). http://www.jstor.org/stable/1268522MathSciNetMATH

22.

Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., Rudolph, G.: Exploratory landscape analysis. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO), pp. 829–836. ACM (2011). https://doi.org/10.1145/2001576.2001690

23.

Morgan, R., Gallagher, M.: Sampling techniques and distance metrics in high dimensional continuous landscape analysis: limitations and improvements. IEEE Trans. Evol. Comput. 18(3), 456–461 (2014). https://doi.org/10.1109/TEVC.2013.2281521CrossRef

24.

Muñoz, M.A., Sun, Y., Kirley, M., Halgamuge, S.K.: Algorithm selection for black-box continuous optimization problems: a survey on methods and challenges. Inf. Sci. 317, 224–245 (2015). https://doi.org/10.1016/j.ins.2015.05.010CrossRef

25.

Pedregosa, F., et al.: Scikit-learn: machine learning in Python. JMLR 12, 2825–2830 (2011)MathSciNetMATH

26.

Pitzer, E., Affenzeller, M.: A comprehensive survey on fitness landscape analysis. In: Fodor, J., Klempous, R., Suárez Araujo, C.P. (eds.) Recent Advances in Intelligent Engineering Systems. Studies in Computational Intelligence, vol. 378, pp. 161–191. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-23229-9_8CrossRef

27.

Renau, Q., Dreo, J., Doerr, C., Doerr, B.: Expressiveness and robustness of landscape features. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO, Companion), pp. 2048–2051. ACM (2019). https://doi.org/10.1145/3319619.3326913

28.

Renau, Q., Doerr, C., Dreo, J., Doerr, B.: Experimental data set for the study “exploratory landscape analysis is strongly sensitive to the sampling strategy”, June 2020. https://doi.org/10.5281/zenodo.3886816

29.

Saleem, S., Gallagher, M., Wood, I.: Direct feature evaluation in black-box optimization using problem transformations. Evol. Comput. 27(1), 75–98 (2019)CrossRef

30.

Santner, T., Williams, B., Notz, W.: The Design and Analysis of Computer Experiments. Springer Series in Statistics. Springer, New York (2003). https://doi.org/10.1007/978-1-4757-3799-8CrossRefMATH

31.

Smith-Miles, K.A.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1) (2009). https://doi.org/10.1145/1456650.1456656

32.

Sobol’, I.: On the distribution of points in a cube and the approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7(4), 86–112 (1967). https://doi.org/10.1016/0041-5553(67)90144-9MathSciNetCrossRefMATH

33.

Vallati, M., Hutter, F., Chrpa, L., McCluskey, T.: On the effective configuration of planning domain models. In: Proceedings of IJCAI 2015. AAAI (2015)

34.

Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for sat. JAIR 32, 565–606 (2008). http://dl.acm.org/citation.cfm?id=1622673.1622687CrossRef

Titel: Exploratory Landscape Analysis is Strongly Sensitive to the Sampling Strategy
verfasst von: Quentin Renau
Carola Doerr
Johann Dreo
Benjamin Doerr
Verlag: Springer International Publishing
Buch: Parallel Problem Solving from Nature – PPSN XVI
Print ISBN: 978-3-030-58114-5

Electronic ISBN: 978-3-030-58115-2

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-58115-2_10

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner