Algorithmen

Algorithmen

Beim Data Fitting sollen Parameterwerte gefunden werden, mit denen ein Modell gemessene Daten bestmöglich beschreiben kann. Dazu werden Modelldaten und empirische Daten mittels eines Abweichungsmaßes verglichen. Würde man dieses Abweichungsmaß für alle denkbaren Parameterwerte und -kombinationen berechnen und in einem Koordinatensystem darstellen, könnte man die gesamte Fehleroberfläche betrachten. Unter allen Parameterausprägungen wären nun diejenigen bestimmbar, welche den kleinsten Fehler verursachen. So einfach, wie diese Lösung klingt, ist sie jedoch nicht. Warum?

Parameter können sehr viele (bei kontinuierlichen Parametern auch unendlich viele) Ausprägungen haben. Jede dieser Ausprägungen auf das Modell anzuwenden, verursacht einen sehr hohen Rechenaufwand. Mit jedem zusätzlichen Parameter im Modell steigt außerdem die Anzahl der Kombinationsmöglichkeiten und damit ebenfalls der Rechenaufwand. Eine graphische Darstellung der Fehleroberfläche wäre, nebenbei bemerkt, schon ab drei Parametern nicht mehr gut möglich, da hierfür ein vierdimensionales Koordinatensystem benötigt werden würde. Die Vielzahl der Kombinationsmöglichkeiten und Parameterausprägungen sorgen für eine hohe Komplexität der Fehleroberfläche und Fehlerfunktion. Dies führt dazu, dass sich die Suche nach der optimalen Parameterwertkombination einfachen analytischen Lösungswegen entzieht.

Um das Minimum zu finden, ist somit ein Algorithmus nötig, der die Fehleroberfläche abtastet, ohne dass alle erdenklichen Punkte berechnet werden müssen. Es gibt viele verschiedene Ansätze solcher Optimierungsalgorithmen, dazu gehören gradientenbasierte Verfahren, genetische Algorithmen, Simplex-Verfahren und Simulated Annealing. Der Ablauf ist dabei jeweils ähnlich:

Mit bestimmten Startparameterwerten werden aus dem Modell Daten generiert und den empirischen Ergebnissen gegenübergestellt. Damit wird ein Abweichungsmaß – der Wert auf der Fehleroberfläche – berechnet. Sofern noch kein Abbruchkriterium, zum Beispiel in Form eines sehr geringen Fehlers, erreicht ist, wählt der Algorithmus anschließend einen neuen Punkt auf der Fehleroberfläche aus. Dieser wird so bestimmt, dass der Fehler mutmaßlich kleiner wird. Die Auswahl kann dabei entweder deterministisch nur tiefer liegende Punkte betreffen oder eine Zufallskomponente beinhalten. Die neu gewählten Parameterausprägungen werden, falls kein Abbruchkriterium in Form einer zu geringen Veränderung eingreift, auf das Modell angewandt. An dieser Stelle beginnt der Kreislauf von vorn, bis ein Minimum erreicht ist.