Local Optimization and Complexity Control for Symbolic Regression

Symbolic regression is a data-based machine learning approach that creates interpretable prediction models in the form of mathematical expressions without the necessity to specify the model structure in advance. Due to numerous possible models, symbolic regression problems are commonly solved by metaheuristics 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 programming 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 subproblems: finding the most appropriate structure describing the data and finding optimal parameters for the specified model structure. Genetic programming excels at finding appropriate model structures, whereas the Levenberq-Marquardt algorithm performs least-squares curve fitting and model parameter tuning. The combination of these two methods significantly improves the prediction accuracy of generated models. Another improvement is to turn the standard single-objective formulation of symbolic regression into a multi-objective one, where the prediction accuracy is maximized while the model complexity is simultaneously minimized. 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 developed 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.Symbolische Regression ist ein datenbasiertes, maschinelles Lernverfahren bei dem Vorhersagemodelle in Form mathematischer Ausdrücke ohne vorgegebener Modellstruktur erstellt werden. Wegen der Vielzahl möglicher Modelle, welche die Daten beschreiben, werden symbolische Regressionsprobleme meist mittels genetischer Programmierung gelöst. Ein Nachteil dabei ist, dass wegen der gleichzeitigen Optimierung der Modellstruktur und deren Parameter, der Aufwand zum Lernen der Modelle erhöht ist und deren Genauigkeit verringert sein kann. Zusätzlich wird die Interpretierbarkeit der Modelle durch das Auftreten überflüssiger Ausdrücke (engl. bloat), welche die Modelle 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 Optimierung, welche die numerischen Parameter der Modelle anpasst, erhöht. Dadurch wird das Regressionsproblem in zwei Aufgaben unterteilt. Zuerst wird eine passende Modellstruktur identifiziert und anschließend deren numerischen Parameter adaptiert. Genetische Programmierung wird zur Identifikation der Modellstruktur verwendet, während der Levenberg-Marquardt Algorithmus 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 Problemformulierung von einzelkriterieller zu multikriterieller Optimierung verbessert, wodurch die Genauigkeit der Modelle maximiert während gleichzeitig deren Komplexität minimiert wird. Das Ergebnis ist somit nicht mehr ein einzelnes Modell, sondern eine Pareto-Front, welche den Kompromiss zwischen Genauigkeit und Komplexität widerspiegelt. Zusätzlich wird ein neues Komplexitätsmaß für symbolische Regression vorgestellt, welches syntaktische und semantische Informationen berücksichtigt. Durch den Einsatz dieses neuen Komplexitätsmaßes werden die erzeugten Modelle besser interpretierbar und überflüssige Ausdrücke vermieden.eingereicht von Michael KommendaUniversität Linz, Dissertation, 2018OeBB(VLID)258190