Local optimization and complexity control for symbolic regression

Eingereicht von Michael Kommenda Angefertigt am Institute for Formal Models and Verification Betreuer und Erstbeurteiler FH-Prof. PD DI Dr. Michael Affenzeller Local Optimization and Zweitbeurteiler a. Josef Küng Complexity Control for April 2018 Symbolic Regression Dissertation zur Erlangung des akademischen Grades Doktor der technischen Wissenschaften im Doktoratsstudium Technische Wissenschaften JOHANNES KEPLER UNIVERSITÄT LINZ Altenbergerstraße 69 4040 Linz, Österreich www.at DVR 0093696 Acknowledgments Several people have been essential for this thesis to become a reality.

First and foremost and I want to thank Michael Affenzeller for encouraging and giving me the possibility to pursue a doctorate within the research group Heuristic and Evolutionary Algorithms Laboratory (HEAL). Furthermore, I am sincerely grateful to Josef Küng for acting as an examiner without whom this endeavor would not be possible. Research in general is rarely an effort by a single person and numerous people shaped the way I think about computer science, data-based modeling, algorithm design, experimentation, and optimization in general. In addition to my advisors, I want to especially thank Gabriel Kronberger, Stefan Wag- ner, Andreas Beham, and Stephan Winkler who challenged me constantly to improve and whose thoughts and discussions influenced the scientific contri- butions of this thesis.

Working within the research group HEAL has always been a great priv- ilege and pleasure for me. Therefore, I want to thank all of my colleagues for making my work life so enjoyable. Finally and most importantly, I would like to thank my soon-to-be wife Romy for always supporting me. Abstract Symbolic regression is a data-based machine learning approach that creates interpretable prediction models in the form of mathematical expressions with- out the necessity to specify the model structure in advance.

Due to numerous possible models, symbolic regression problems are commonly solved by meta- heuristics such as genetic programming. A drawback of this method is that because of the simultaneous optimization of the model structure and model parameters, the effort for learning from the presented data is increased and the obtained prediction accuracy could suffer. Furthermore, genetic pro- gramming in general has to deal with bloat, an increase in model length and complexity without an accompanying increase in prediction accuracy, which hampers the interpretability of the models. The goal of this thesis is to develop and present new methods for symbolic regression, which improve prediction accuracy, interpretability, and simplicity of the models.

The prediction accuracy is improved by integrating local optimization techniques that adapt the numerical model parameters in the algorithm. Thus, the symbolic regression problem is divided into two separate subprob- lems: finding the most appropriate structure describing the data and find- ing optimal parameters for the specified model structure. Genetic program- ming excels at finding appropriate model structures, whereas the Levenberq- Marquardt algorithm performs least-squares curve fitting and model param- eter tuning. The combination of these two methods significantly improves the prediction accuracy of generated models.

Another improvement is to turn the standard single-objective formula- tion of symbolic regression into a multi-objective one, where the prediction accuracy is maximized while the model complexity is simultaneously mini- mized. As a result the algorithm does not produce a single solution, but a Pareto front of models with varying accuracy and complexity. In addition, a novel complexity measure for multi-objective symbolic regression is de- veloped that includes syntactic and semantic information about the models while still being efficiently computed. By using this new complexity measure the generated models get simpler and the occurrence of bloat is reduced.

Kurzfassung Symbolische Regression ist ein datenbasiertes, maschinelles Lernverfahren bei dem Vorhersagemodelle in Form mathematischer Ausdrücke ohne vorge- gebener Modellstruktur erstellt werden. Wegen der Vielzahl möglicher Mo- delle, welche die Daten beschreiben, werden symbolische Regressionsproble- me meist mittels genetischer Programmierung gelöst. Ein Nachteil dabei ist, dass wegen der gleichzeitigen Optimierung der Modellstruktur und deren Pa- rameter, der Aufwand zum Lernen der Modelle erhöht ist und deren Genauig- keit verringert sein kann. Zusätzlich wird die Interpretierbarkeit der Modelle durch das Auftreten überflüssiger Ausdrücke (engl.

bloat), welche die Model- le verkomplizieren ohne deren Genauigkeit zu erhöhen, erschwert. Das Ziel dieser Dissertation ist es neue Methoden zur Verbesserung der Genauigkeit und Interpretierbarkeit symbolischer Regressionsmodelle zu entwickeln. Die Genauigkeit der Modelle wird durch die Integration lokaler Optimie- rung, welche die numerischen Parameter der Modelle anpasst, erhöht. Da- durch wird das Regressionsproblem in zwei Aufgaben unterteilt.

Zuerst wird eine passende Modellstruktur identifiziert und anschließend deren numeri- schen Parameter adaptiert. Genetische Programmierung wird zur Identifika- tion der Modellstruktur verwendet, während der Levenberg-Marquardt Algo- rithmus eine nichtlineare Anpassung der numerischen Parameter vornimmt. Durchgeführte Experimente zeigen, dass die Kombination dieser Methoden in einer deutlichen Verbesserung der Modellgenauigkeit resultiert. Die Interpretierbarkeit der Modelle wird durch eine Änderung der Pro- blemformulierung von einzelkriterieller zu multikriterieller Optimierung ver- bessert, wodurch die Genauigkeit der Modelle maximiert während gleichzei- tig deren Komplexität minimiert wird.

Das Ergebnis ist somit nicht mehr ein einzelnes Modell, sondern eine Pareto-Front, welche den Kompromiss zwi- schen Genauigkeit und Komplexität widerspiegelt. Zusätzlich wird ein neues Komplexitätsmaß für symbolische Regression vorgestellt, welches syntakti- sche und semantische Informationen berücksichtigt. Durch den Einsatz dieses neuen Komplexitätsmaßes werden die erzeugten Modelle besser interpretier- bar und überflüssige Ausdrücke vermieden. Eidesstattliche Erklärung Ich erkläre an Eides statt, dass ich die vorliegende Dissertation selbstständig und ohne fremde Hilfe verfasst, andere als die angegebenen Quellen und Hilfs- mittel nicht benutzt bzw.

die wörtlich oder sinngemäß entnommenen Stellen als solche kenntlich gemacht habe. Die vorliegende Dissertation ist mit dem elektronisch übermittelten Textdo- kument identisch. Michael Kommenda, Linz, 2018 Contents 1 Introduction 1 1.2 Main Research Contributions .2 Tree-based Genetic Programming .3 Symbolic Regression with Genetic Programming .2 Genetic Programming and Symbolic Regression Software .3 Deterministic Symbolic Regression .1 Fast Function Extraction .2 Prioritized Grammar Enumerations .1 Constants in Symbolic Regression .2 Ephemeral Random Constants .3 Constants Optimization by Nonlinear Least Squares .1 Levenberg-Marquardt Algorithm .3 CO-NLS Algorithm .4 Inclusion in Genetic Programming for Symbolic Regression .1 Comparison with Linear Scaling .3 Genetic Programming Results .4 Offspring Selection Results .2 Multi-objective Symbolic Regression .1 NSGA-II Adaptations .2 Results on Benchmark Problems .3 Results on Noisy Problems. 117 5 Conclusion 119 Bibliography 127 List of Figures 142 List of Tables 143 Chapter 1 Introduction 1.1 Motivation The importance of data-based modeling techniques has risen with the vast increase of available data and computing power during the last years.

Sev- eral methods such as linear regression [Draper et al., 1966], random forests [Breiman et al., 1984], support vector machines [Vapnik, 1999], artificial neu- ral networks [Haykin, 1998], Gaussian processes [Rasmussen, 2004] have been developed to extract the most information from the data and build accurate regression models. Symbolic regression is another data-based modeling technique that dis- tinguishes itself from other methods due to the fact that the model structure need not be predefined, but is automatically adapted to the data. Another advantage is that the generated model is represented as mathematical expres- sion that is open for inspection and interpretation [Affenzeller et al. Symbolic regression problems are commonly solved by genetic programming, because the variable-length encoding of solutions in genetic programming is especially suited for representing mathematical expressions and due to the enormous search space heuristic methods are preferred.

Genetic programming is well suited to search for the model structure describing the data, but is not the very good in determining the appropriate numerical constants to fit the model structure to the data. As a result of inappropriate numerical values in the generated model, their prediction accuracy is reduced. This has also been noted by O’Neill et al. [2010], where a quote of John Koza is presented:.

the finding of numerical constants is a skeleton in the GP closet. [and an] area of research that requires more investigation. INTRODUCTION Another issue regarding genetic programming for solving symbolic regres- sion problems is that the algorithm is hard to configure and parameterize to achieve high quality solutions. Furthermore, not only the algorithm con- figuration affects the obtained quality, but also the restrictions imposed to the symbolic regression problem.

These restriction include the mathematical functions occurring in the models; Is it allowed to use trigonometric functions during model creation or are only arithmetic functions usable? In addition, it is common in most genetic programming systems to im- poses a static size limit to the model length, because otherwise the models would grow infinitely and their interpretability would be severely hampered. The major problem with these two restrictions that are enforced during modeling is that they are highly problem specific. They should be set as tight as possible without affecting the accuracy of the generated models. In general simpler models are preferred to complex ones as long as they general- ize equally well.

However, to achieve simple models by genetic programming several different size limits and function configurations have to be tested for the problem at hand, because appropriate values cannot be identified a- priori. These issues further complicate the use of symbolic regression and are primarily addressed in this thesis.2 Main Research Contributions The broad research topic of this thesis is to identify new ways for improv- ing symbolic regression by addressing its weak points. Therefore, constants creation and the complexity of solutions are studied in detail and based on empirical observations improved methods are derived. This research has been performed by using tree-based genetic programming for symbolic regression and also the new methods are derived and tested with this optimization method.

However, these improvements are not specific to tree-based genetic programming, but are applicable to any kind of algorithm solving symbolic regression problems. All of the described experiments, methodological improvements, and anal- yses are implemented in and have been performed with the open-source framework for heuristic optimization HeuristicLab [Wagner et al. INTRODUCTION Local Optimization The main advancements for the creation and identification of constants for symbolic regression is a new local optimization technique termed constants optimization by nonlinear least squares (CO-NLS). CO-NLS is integrated in the genetic programming algorithm by adapting the numeric values in the models before a solution is evaluated.

However, CO-NLS is more generally applicable and can be integrated in any algorithm and can be even utilized as a post-processing step to improve the accuracy of generated models. The detailed research contributions in the field of constants creation and local optimization are the following: − Review of constants creation, constants adaptation, and local optimiza- tion methods in symbolic regression − Comparison of different objective functions and linear scaling on bench- mark problems − Development and implementation of CO-NLS by combining automatic differentiation and gradient-based nonlinear least squares optimization − Performance evaluation of CO-NLS in genetic programming and off- spring selection genetic programming to highlight its advantages and disadvantages as well as the influence of its parameters Complexity Control The second main topic of this thesis is to investigate ways of creating sim- pler models. Therefore, the role of the tree length restriction in genetic pro- gramming is evaluated and its effect on the obtained solutions is presented. Afterwards more advanced complexity metrics for symbolic regression mod- els are discussed and from these observations another complexity metric is derived.

The newly defined recursive complexity is easily implemented and can be calculated with a single tree iterations without evaluating the models on the presented data. In contrast to other complexity metrics that share these benefits, it takes the semantics of the model into account. The recur- sive complexity does not provide the most accurate estimation of the model’s complexity, but gives the algorithm a strong enough search direction so that simple models can be obtained. Furthermore, it becomes unnecessary to specify the mathematical functions that can occur in the models, because the appropriate ones are automatically detected.