Top

Published in:

2023 | OriginalPaper | Chapter

Faster Convergence with Lexicase Selection in Tree-Based Automated Machine Learning

Authors : Nicholas Matsumoto, Anil Kumar Saini, Pedro Ribeiro, Hyunjun Choi, Alena Orlenko, Leo-Pekka Lyytikäinen, Jari O. Laurikka, Terho Lehtimäki, Sandra Batista, Jason H. Moore

Published in: Genetic Programming

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In many evolutionary computation systems, parent selection methods can affect, among other things, convergence to a solution. In this paper, we present a study comparing the role of two commonly used parent selection methods in evolving machine learning pipelines in an automated machine learning system called Tree-based Pipeline Optimization Tool (TPOT). Specifically, we demonstrate, using experiments on multiple datasets, that lexicase selection leads to significantly faster convergence as compared to NSGA-II in TPOT. We also compare the exploration of parts of the search space by these selection methods using a trie data structure that contains information about the pipelines explored in a particular run.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Adaptive Batch Size CGP: Improving Accuracy and Runtime for CGP Logic Optimization Flow

next chapter Using FPGA Devices to Accelerate Tree-Based Genetic Programming: A Preliminary Exploration with Recent Technologies

Individual \(i_1\) dominates \(i_2\) if \(i_1\) is better than or the same as \(i_2\) on all objectives and strictly better than \(i_2\) on at least one objective.

https://github.com/EpistasisLab/exploration-trie-tpot including code and supplementary material.

Burlacu, B., Affenzeller, M., Kommenda, M., Winkler, S., Kronberger, G.: Visualization of genetic lineages and inheritance information in genetic programming. In: Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, pp. 1351–1358 (2013)

Ciesielski, V., Mawhinney, D.: Prevention of early convergence in genetic programming by replacement of similar programs. In: Proceedings of the 2002 Congress on Evolutionary Computation, CEC 2002 (Cat. No. 02TH8600), vol. 1, pp. 67–72. IEEE (2002)

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)CrossRef

Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multiobjective optimization. In: Abraham, A., Jain, L., Goldberg, R. (eds.) Evolutionary Multiobjective Optimization. Advanced Information and Knowledge Processing, pp. 105–145. Springer, London (2005). https://doi.org/10.1007/1-84628-137-7_6CrossRefMATH

Dietterich, T.: Approximate statistical tests for comparing supervised classification learning algorithms. Neural Comput. 10, 1895–1923 (1998)CrossRef

Fortin, F.A., De Rainville, F.M., Gardner, M.A., Parizeau, M., Gagné, C.: DEAP: evolutionary algorithms made easy. J. Mach. Learn. Res. 13, 2171–2175 (2012)MathSciNet

Helmuth, T., Spector, L., Matheson, J.: Solving uncompromising problems with lexicase selection. IEEE Trans. Evol. Comput. 19(5), 630–643 (2014)CrossRef

La Cava, W., Moore, J.H.: An analysis of \(\epsilon \)-lexicase selection for large-scale many- objective optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 185–186 (2018)

La Cava, W., Spector, L., Danai, K.: Epsilon-lexicase selection for regression. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, pp. 741–748 (2016)

10.

Langdon, W.B.: Genetic programming convergence. Genet. Program Evolvable Mach. 23(1), 71–104 (2022)CrossRef

11.

Latora, V., Marchiori, M.: Efficient behavior of small-world networks. Phys. Rev. Lett. 87, 198701 (2001). https://doi.org/10.1103/PhysRevLett.87.198701, https://link.aps.org/doi/10.1103/PhysRevLett.87.198701

12.

McPhee, N.F., Finzel, M.D., Casale, M.M., Helmuth, T., Spector, L.: A detailed analysis of a PushGP run. In: Riolo, R., Worzel, B., Goldman, B., Tozier, B. (eds.) Genetic Programming Theory and Practice XIV. GEC, pp. 65–83. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-97088-2_5CrossRef

13.

Metevier, B., Saini, A.K., Spector, L.: Lexicase selection beyond genetic programming. In: Banzhaf, W., Spector, L., Sheneman, L. (eds.) Genetic Programming Theory and Practice XVI. GEC, pp. 123–136. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-04735-1_7CrossRef

14.

Moore, J.M., McKinley, P.K.: A comparison of multiobjective algorithms in evolving quadrupedal gaits. In: Tuci, E., Giagkos, A., Wilson, M., Hallam, J. (eds.) SAB 2016. LNCS (LNAI), vol. 9825, pp. 157–169. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43488-9_15CrossRef

15.

Oh, H., et al.: Convergence-aware neural network training. In: 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1–6. IEEE (2020)

16.

Olson, R.S., Urbanowicz, R.J., Andrews, P.C., Lavender, N.A., Kidd, L.C., Moore, J.H.: Automating biomedical data science through tree-based pipeline optimization. In: Squillero, G., Burelli, P. (eds.) EvoApplications 2016. LNCS, vol. 9597, pp. 123–137. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31204-0_9CrossRef

17.

Orlenko, A., et al.: Model selection for metabolomics: predicting diagnosis of coronary artery disease using automated machine learning. Bioinformatics 36(6), 1772–1778 (2020)CrossRef

18.

Orzechowski, P., Moore, J.H.: Generative and reproducible benchmarks for comprehensive evaluation of machine learning classifiers. Sci. Adv. 8(47), eabl4747 (2022). https://doi.org/10.1126/sciadv.abl4747, https://www.science.org/doi/abs/10.1126/sciadv.abl4747

19.

Saini, A.K., Spector, L.: Relationships between parent selection methods, looping constructs, and success rate in genetic programming. Genet. Program Evolvable Mach. 22(4), 495–509 (2021)CrossRef

20.

Snedecor, G.W., Cochran, W.G.: Statistical Methods, 8th edn. Iowa State University Press (1989)

Title: Faster Convergence with Lexicase Selection in Tree-Based Automated Machine Learning
Authors: Nicholas Matsumoto
Anil Kumar Saini
Pedro Ribeiro
Hyunjun Choi
Alena Orlenko
Leo-Pekka Lyytikäinen
Jari O. Laurikka
Terho Lehtimäki
Sandra Batista
Jason H. Moore
Publisher: Springer Nature Switzerland
Book: Genetic Programming
Print ISBN: 978-3-031-29572-0

Electronic ISBN: 978-3-031-29573-7

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-29573-7_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner