Analysing symbolic regression benchmarks under a meta-learning approach

ABSTRACT

The definition of a concise and effective testbed for Genetic Programming (GP) is a recurrent matter in the research community. This paper takes a new step in this direction, proposing a different approach to measure the quality of the symbolic regression benchmarks quantitatively. The proposed approach is based on meta-learning and uses a set of dataset meta-features---such as the number of examples or output skewness---to describe the datasets. Our idea is to correlate these meta-features with the errors obtained by a GP method. These meta-features define a space of benchmarks that should, ideally have datasets (points) covering different regions of the space. An initial analysis of 63 datasets showed that current benchmarks are concentrated in a small region of this benchmark space. We also found out that number of instances and output skewness are the most relevant meta-features to GP output error. Both conclusions can help define which datasets should compose an effective testbed for symbolic regression methods.

References

1. Ignacio Arnaldo, Krzysztof Krawiec, and Una-May O'Reilly 2014. Multiple regression genetic programming. In GECCO '14: Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, New York, NY, USA, 879--886.
2. Ignacio Arnaldo, Una-May O'Reilly, and Kalyan Veeramachaneni. 2015. Building Predictive Models via Feature Synthesis. In GECCO '15: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 983--990.
3. Pavel Brazdil, Christophe Giraud Carrier, Carlos Soares, and Ricardo Vilalta. 2008. Metalearning: Applications to data mining. Springer Science & Business Media.
4. Armand R. Burks and William F. Punch. 2015. An Efficient Structural Diversity Technique for Genetic Programming. In GECCO '15: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 991--998.
5. Mauro Castelli, Leonardo Trujillo, Leonardo Vanneschi, Sara Silva, Emigdio Z-Flores, and Pierrick Legrand. 2015. Geometric Semantic Genetic Programming with Local Search. In GECCO '15: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 999--1006.
6. Qi Chen, Bing Xue, Lin Shang, and Mengjie Zhang. 2016. Improving Generalisation of Genetic Programming for Symbolic Regression with Structural Risk Minimisation. In GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, New York, NY, USA, 709--716.
7. Vinícius Veloso De Melo. 2014. Kaizen programming. In GECCO '14: Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, New York, NY, USA, 895--902.
8. Grant Dick, Aysha P. Rimoni, and Peter A. Whigham. 2015. A Re-Examination of the Use of Genetic Programming on the Oral Bioavailability Problem. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO '15). ACM, New York, NY, USA, 1015--1022.
9. Ivo Gonçalves, Sara Silva, Carlos M. Fonseca, and Mauro Castelli. 2017. Unsure when to stop?: ask your semantic neighbors. In GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 929--936.
10. Tomohiro Harada and Keiki Takadama. 2014. Asynchronously evolving solutions with excessively different evaluation time by reference-based evaluation. In GECCO '14: Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, New York, NY, USA, 911--918.
11. H. Hotelling. 1933. Analysis of a complex of statistical variables into principal components. J. Educ. Psych. 24 (1933).
12. Krzysztof Krawiec and Una-May O'Reilly. 2014. Behavioral programming: a broader and more detailed take on semantic GP. In GECCO '14: Proceedings of the 2014 conference on Genetic and evolutionary computation. ACM, New York, NY, USA, 935--942.
13. Krzysztof Krawiec and Tomasz Pawlak. 2013. Approximating geometric crossover by semantic backpropagation. In GECCO '13: Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, New York, NY, USA, 941--948.
14. William La Cava, Thomas Helmuth, Lee Spector, and Kourosh Danai. 2015. Genetic Programming with Epigenetic Local Search. In GECCO '15: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 1055--1062.
15. William La Cava, Lee Spector, and Kourosh Danai. 2016. Epsilon-Lexicase Selection for Regression. In GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, New York, NY, USA, 741--748.
16. Pawe lLiskowski and Krzysztof Krawiec. 2017. Discovery of search objectives in continuous domains. In GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 969--976.
17. Rui L. Lopes and Ernesto Costa. 2013. GEARNet: grammatical evolution with artificial regulatory networks. In GECCO '13: Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, New York, NY, USA, 973--980.
18. James McDermott, David R. White, Sean Luke, Luca Manzoni, Mauro Castelli, Leonardo Vanneschi, Wojciech Jaskowski, Krzysztof Krawiec, Robin Harper, Kenneth De Jong, and Una-May O'Reilly. 2012. Genetic programming needs better benchmarks. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. ACM, 791--798.
19. Nicholas Freitag McPhee, M. Kirbie Dramdahl, and David Donatucci. 2015. Impact of Crossover Bias in Genetic Programming. In GECCO '15: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 1079--1086.
20. David Medernach, Jeannie Fitzgerald, R. Muhammad Atif Azad, and Conor Ryan. 2016. A New Wave: A Dynamic Approach to Genetic Programming. In GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, New York, NY, USA, 757--764.
21. Eric Medvet, Fabio Daolio, and Danny Tagliapietra. 2017. Evolvability in grammatical evolution. In GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 977--984.
22. Andreas Meier, Mark Gonter, and Rudolf Kruse. 2013. Accelerating convergence in cartesian genetic programming by using a new genetic operator. In GECCO '13: Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, New York, NY, USA, 981--988.
23. Luis F. Miranda, Luiz Otavio V. B. Oliveira, Joao Francisco B. S. Martins, and Gisele L. Pappa. 2017. How noisy data affects geometric semantic genetic programming. In GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 985--992.
24. Mario A Muñoz and Kate Smith-Miles. 2017. Generating custom classification datasets by targeting the instance space. In Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM, 1582--1588.
25. Mario A Muñoz, Laura Villanova, Davaatseren Baatar, and Kate Smith-Miles. 2018. Instance spaces for machine learning classification. Machine Learning 101, 1 (2018), 109--147.
26. Ji Ni, Russ H Drieberg, and Peter I Rockett. 2013. The use of an analytic quotient operator in genetic programming. IEEE Transactions on Evolutionary Computation 17, 1 (2013), 146--152.
27. Miguel Nicolau, Alexandras Agapitos, Michael O'Neill, and Anthony Brabazon. 2015. Guidelines for defining benchmark problems in genetic programming. In Evolutionary Computation (CEC), 2015 IEEE Congress on. IEEE, 1152--1159.
28. Miguel Nicolau and Michael Fenton. 2016. Managing Repetition in Grammar-Based Genetic Programming. In GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, New York, NY, USA, 765--772.
29. Luiz Otavio V.B. Oliveira, Fernando E.B. Otero, and Gisele L. Pappa. 2016. A Dispersion Operator for Geometric Semantic Genetic Programming. In GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, New York, NY, USA, 773--780.
30. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825--2830.
31. Léo Françoso Dal Piccol Sotto and Vinícius Veloso de Melo. 2017. A probabilistic linear genetic programming with stochastic context-free grammar for solving symbolic regression problems. In GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 1017--1024.
32. Trevor Stephens. 2018. gplearn: Genetic Programming in Python. (2018). https://github.com/trevorstephens/gplearn {Online; accessed 30/03/2018}.
33. Marcin Szubert, Anuradha Kodali, Sangram Ganguly, Kamalika Das, and Josh C. Bongard. 2016. Reducing Antagonism between Behavioral Diversity and Fitness in Semantic Genetic Programming. In GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016. ACM, New York, NY, USA, 797--804.
34. Pham Thi Thuong, Nguyen Xuan Hoai, and Xin Yao. 2017. Combining conformal prediction and genetic programming for symbolic interval regression. In GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 1001--1008.
35. Peter A. Whigham, Grant Dick, James Maclaurin, and Caitlin A. Owen. 2015. Examining the "Best of Both Worlds" of Grammatical Evolution. In GECCO '15: Proceedings of the 2015 on Genetic and Evolutionary Computation Conference. ACM, New York, NY, USA, 1111--1118.
36. David R White, James McDermott, Mauro Castelli, Luca Manzoni, Brian W Goldman, Gabriel Kronberger, Wojciech Jaśkowski, Una-May O'Reilly, and Sean Luke. 2013. Better GP benchmarks: community survey results and proposals. Genetic Programming and Evolvable Machines 14, 1 (March 2013), 3--29.
37. Bartosz Wieloch and Krzysztof Krawiec. 2013. Running programs backwards: instruction inversion for effective search in semantic spaces. In GECCO '13: Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, New York, NY, USA, 1013--1020.
38. Tony Worm and Kenneth Chiu. 2013. Prioritized grammar enumeration: symbolic regression by dynamic programming. In GECCO '13: Proceeding of the fifteenth annual conference on Genetic and evolutionary computation conference. ACM, New York, NY, USA, 1021--1028.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Supervised learning by regression

    • Machine learning approaches

      • Bio-inspired approaches

        • Genetic programming