5. Grundlagen der Optimierung und Gradient Descent¶

Optimierung begegnet uns nahezu überall in modernen Problemen und interessanten Fragestellungen. Wir werden uns in diesem Notebook mit den Grundlagen der Optimierung befassen und dann auch noch einen konkreten Optimierungs-Algorithmus kennen lernen: Gradient Descent.

5.1 Was ist Optimierung¶

Bei einem Optimierungsproblem geht es grundsätzlich darum, eine bestimmte Größe oder Funktion von Input-Variablen entweder zu maximieren oder zu minimieren. Diese Größe heißt je nach Kontext z.B. “Zielfunktion”, “Kostenfunktion”, “Fitnessfunktion”, etc. Gemeint ist damit aber einfach immer jene Funktion, die optimiert werden soll.

Grundsätzlich kann es bei Optimierungsproblemen verschiedene Einschränkungen geben:

• Die erlaubten Wertebereiche der Input-Variablen können eingeschränkt sein
• Die Wertebereiche der Zielfunktion können eingeschränkt sein
• Die Werte der Input-Variablen können durch eine sogenannte Nebenbedingung zusammenhängen
• Der “Anspruch” der Optimierung kann eingeschränkt sein auf entweder lokale oder globale Optima, die man finden möchte.

Sehen wir uns gleich ein einfaches Beispiel an, dass zwei dieser Einschränkungen aufweist:

Finde jene beiden verschiedenen Zahlen aus der Menge der natürlichen Zahlen bis 10, die folgendes leisten:

• Die Summe der beiden Zahlen muss 10 ergeben
• Das Produkt der beiden Zahlen soll maximal sein

Die eine Einschränkung ist die Nebenbedingung der fixen Summe, die andere Einschränkung ist, dass wir es mit natürlichen Zahlen zu tun haben, also einer diskreten (bzw. letztlich auch endlichen) Menge von möglichen Input-Werten.

Um dieses Problem zu lösen müssten wir eigentlich gar nicht programmieren, sondern nur nachdenken. Aber ich werde trotzdem das Notebook nutzen, um das Beispiel zu illustrieren.

5.2 Varianten der Optimierung¶

Hier haben wir also gesehen, wie man, mehr oder weniger mit der Hand und eine nach der anderen, alle Möglichkeiten durchspielt und am Schluss nachsieht, welche Möglichkeit optimal ist. So eine herangehensweise nennt man oft “brute-force” approach, denn mehr als Rechengewalt haben wir nicht verwendet. Insbesondere haben wir folgendes nicht getan:

• Eine Formel verwendet, um die Lösung direkt zu bestimmen
• Einen iterativen Algorithmus verwendet, der von einem Startwert aus Schritt für Schritt immer bessere Lösungsvorschläge liefert
• Die Werte der Input-Variablen eingeschränkt, als wir sie in die Loops geschickt haben
• Aus möglichen Input-Werten per Zufallsprinzip gesampelt, um Rechenzeit zu sparen, aber gleichzeitig trotzdem einen repräsentativen Teil aller Möglichkeiten abzubilden

Diese Dinge sind natürlich grundsätzlich gute Möglichkeiten, um ein Optimierungsproblem zu vereinfachen. Machmal sind sie allerdings sogar unerlässlich, um überhaupt Fortschritte erzielen zu können. Nehmen wir dazu nocheinmal das obige Beispiel zur Hand und stellen wir uns vor, aus 10 würde eine viel größere Zahl.

Aus unserer Zeit-Komplexitäts-Analyse wissen wir noch, dass ein Programm mit zwei Loops bis $N$ zunächst einmal wie $N^2$ skalieren wird. Hier kommt dann noch etwas dazu, nämlich die Suche nach dem Maximum in der entstandenen Liste. Uns geht es hier allerdings nicht so sehr um diese Details, sondern zunächst einmal darum, dass wir (auch von den Primzahlen damals) schon wissen, dass man hier im Prinzip ganz ordentlich einsparen kann, wenn man z.B. die Loops gut einschränken kann.

Wenn wir hier z.B. den inneren Loop nur bis zu 1 unter der aktuellen Zahl im äußeren Loop laufen lassen, dann können wir sogar die Hälfte der if-Abfrage weglassen (nämlich ob die beiden Zahlen gleich sind). Somit ändern wir den Code etwas ab zu:

5.3 Optimierung mit kontinuierlichen Variablen¶

Unsere ersten Optimierungserfahrungen in diesem Notebook haben wir also mit diskreten Variablen gemacht. Oft werden Sie allerdings mit kontinuierlichen Variablen (z.B. Koordinaten) zu tun haben. Daher wenden wir uns nun dieser Situation zu und befassen uns gleich auch noch mit einem konkreten iterativen Lösungsalgorithmus dafür.

Zunächst sehen wir uns einmal so ein Problem konkret an einem Beispiel an. Nehmen wir z.B. folgendes:

Gegeben ist die Funktion $f(x, y) = (x – 1)^2 + (y-2)^2 + 1$. Für welche $(x, y)$ ist $f$ minimal?

Dazu noch ein paar Anmerkungen:

• Üblicherweise kann man für Optimierungsprobleme mit kontinuierlichen Variablen die Wertebereiche der Input-Variablen einfach als $\mathbb{R}$ annehmen (oder $\mathbb{R}$, eingeschränkt auf ein Intervall).
• Man muss aufpassen, dass man zwischen lokalen und globalen Optima unterscheidet. Ein lokales Minimum kann man z.B. mit Methoden aus der Differenzialrechung finden. Das muss jedoch nicht unbedingt auch das globale Minimum sein.
• Insbesondere bei der Einschränkung der Input-Werte auf Intervalle muss man von vornherein wissen, ob man (ggf. eher) nach globalen oder lokalen Optima sucht.

In unserem Beispiel suchen wir nach beidem gleichzeitig, denn die beiden sind identisch. Das können wir allerdings nur sagen, weil wir wissen, wie die Funktion in etwa aussieht. Hier ist sie z.B. einmal geplottet:

So sieht also die Funktion aus. Es gibt auch noch andere Arten, so etwas zu plotten, z.B. diese:

Wie kann man nun von so einer Funktion das Minimum finden? Beim Kapitel über Vektoren und Matrizen hatten wir schon einmal so etwas ähnliches, nämlich über die lineare Regression (Zur besseren Erklärung: Dort war die Zielfunktion die Summe aller quadrierten Abstände der Beschreibung von den Datenpunkten).

Wir haben damals die exakte Lösungsformel für den Least-Squares-Fit aufgeschrieben und auch umgesetzt. Das ginge konkret auch bei dieser Form der Funktion (weil sie auch quadratisch ist), aber das geht nicht immer. Konkret muss man sogar sagen, dass sehr viele Optimierungsprobleme bisher keine Lösung in dem Sinn haben, dass kein Algorithmus bekannt ist, der das echte Optimum findet.

Nichtsdestotrotz sind viele dieser Probleme zumindest näherungsweise lösbar, und das ist meist gut genug. Wir werden uns daher hier einem Algorithmus zuwenden, der allgemein einsetzbar ist, und der zumindest näherungsweise Lösungen finden kann.

5.4 Gradient Descent¶

Beim Gradient-Descent-Algorithmus geht es darum, bei einer Minimierungsaufgabe dem Gradienten der (Hyper-)Fläche der Zielfunktion im Raum der Variablen Schritt für Schritt so zu folgen, dass man “immer bergab” geht. Stellen Sie sich vor, Sie stehen an einer riesigen Grube (z.B. einem Meteoritenkrater) und wollen an den tiefsten Punkt kommen. Dann könnten Sie folgendes tun:

• Suchen Sie rund um Ihre Position herum jene Stelle, wo es am meisten bergab geht
• Gibt es überhaupt eine Richtung, in der es bergab geht?
  • Ja? Machen Sie einen Schritt in diese Richtung
  • Nein? Sie haben ein (lokales) Minimum erreicht

Mathematisch ausgedrückt macht man bei dieser Vorgehensweise folgendes:

• Wählen Sie einen Startpunkt $(x_0, y_0)$
• Wählen Sie eine Schrittweite $a$
• Berechnen Sie dort den Gradienten $\nabla f(x, y)|_{(x=x_0, y=y_0)}$
• Berechnen Sie den nächsten Punkt, einen Schritt vom vorigen Punkt entfert, entlang des negativen Gradienten, also $$(x_1, y_1) = (x_0, y_0) – a \nabla f(x, y)|_{(x=x_0, y=y_0)}$$
• Nutzen Sie jetzt $(x_1, y_1)$ als neuen Startpunkt für den nächsten Schritt und wiederholen Sie das, bis die Abbruchbedingung erfüllt ist
• Abbruchbedingung: Eine vorgegebene maximale Anzahl von Schritten oder irgendwann ist $||(x_n, y_n)-(x_{n-1}, y_{n-1})||<\varepsilon$ für eine vorgegebene Genauigkeit $\varepsilon$.

Wir wollen nun diesen Algorithmus für unser obiges konkretes Beispiel durchgehen.

5.5 Übungsaufgabe: Spielen Sie mit dem Gradient-Descent-Algorithmus und dem Plot¶

Kopieren Sie nun einfach die relevanten Code-Schnipsel von oben und probieren Sie folgende Dinge aus:

• Nehmen Sie eine andere Funktion $f(x, y)$ und probieren Sie aus, was passiert
• Passen Sie auch die Wertebereiche für $x$ und $y$ entsprechend an, sodass Sie im Plot sehen, wo der Algorithmus hinläuft
• Experimentieren Sie auch mit der Schrittgröße:
  • Was passiert, wenn $a$ zu klein gewählt wird?
  • Was passiert, wenn $a$ zu groß gewählt wird?
• Finden Sie eine Funktion $f$, für die dieser Algorithmus nicht konvergiert?