Gradientenabstiegsverfahren

Einführung

Das Gradientenverfahren, auch Verfahren des steilsten Abstiegs genannt, ist ein Verfahren, das in der Numerik eingesetzt wird, um allgemeine Optimierungsprobleme zu lösen. Dabei geht man (am Beispiel eines Minimierungsproblems) von einem Näherungswert aus. Von diesem schreitet man in Richtung des negativen Gradienten (der die Richtung des steilsten Abstiegs von diesem Näherungswert angibt) fort, bis man keine numerische Verbesserung mehr erzielt.

Animation

Datei:Gradient Descent in 2D.webm

Bemerkung - Animation

In der Animation werden Startpunkte in ein rechteckigen Gitter schachbrettmusterartig in dem Definitionsbereich verteilt. Jede Einzelbewegung dieser Punkte stellt einen Gradientenabstieg dar. Wenn der Gradientenabstieg gegen ein lokale Minimum konvergiert, so muss das nicht das absolute Minimum (z.B. von einer Fehlerfunktion/Kostenfunktion) sein. Wenn man die Startpunkte gitterartig im Definitionsbereich verteilt, findet man ggf. mehrere lokale Minima und wählt dann in einem letzten Optimierungsschritte die Stelle aus, die den geringsten Wert der Zielfunktion (Fehlerfunktion oder Kostenfunktion) besitzt.

Wiki2Reveal-Folien

Diese Seite zum Gradientenabstiegsverfahren ist zugleich ein Wik2Reveal-Foliensatz .

CAS4Wiki - Partielle Ableitung

Diese Lernressource enthält CAS4Wiki-Testlinks zur

• Berechnung von partiellen Ableitung mit folgendem CAS4Wiki-Startlink für partielle Ableitungen

Bemerkung Konvergenz

Das Verfahren konvergiert oftmals sehr langsam, da es sich dem Optimum mit einem starken Zickzack-Kurs nähert. Für die Lösung von symmetrisch positiv definiten linearen Gleichungssystemen bietet das Verfahren der konjugierten Gradienten hier eine immense Verbesserung. Der Gradientenabstieg ist mit dem Bergsteigeralgorithmus (hill climbing) verwandt.

Das Optimierungsproblem

Das Gradientenverfahren ist einsetzbar, wenn es um die Minimierung einer reellwertigen, differenzierbaren Funktion $f:{ℝ}^n\to ℝ$ geht; also um das Optimierungsproblem

$\underset{x\in {ℝ}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}f(x).$

Hierbei handelt es sich um ein Problem der Optimierung ohne Nebenbedingungen, auch unrestringiertes Optimierungsproblem genannt.

Wesentliche Schritte

• Gradient zeigt in die Richtung der "stärksten" Steigung.
• der negative Gradient zeigt daher in die Richtung, in der die Funktionswerte von $f$ fallen.
• Es kann passieren, dass man bei einem Iterationsschritt über das lokale Minimum der Funktion $f$ hinwegspringt. Dann würde man die Schrittweite entsprechend verkleinern, um den Funktionswert von $f$ weiter zu minimieren und genauer zu approximieren.

Abbruchbedingung

• Abbruchbedingung für das Gradientabstiegsverfahren wäre, wenn wir mit der Iteration eine Stelle $x^{(k)}\in {ℝ}^n$ gefunden haben an der der Gradient von $f$ 0 ist

$\mathrm{Grad}(f)(x^{(k)})=0\in {ℝ}^n$ .

Allgemein ist der Gradient einer Stelle $x^{(k)}\in {ℝ}^n$ für den $k$-ten Iterationsschritt wie folgt über die partiellen Ableitungen definiert:

$\mathrm{Grad}(f)(x^{(k)}):=(\frac{\partial f}{\partial x_1}(x^{(k)}),\cdots ,\frac{\partial f}{\partial x_n}(x^{(k)}))$

Notation

Es wird die englische Notation für den Dezimalpunkt statt Komma verwendet. Dies wird analog zu Computer-Algebra-Systemen gemacht, damit die Trennung zwischen Komponenten in einem $n$-Tupel auch mit Zahlen möglich ist. $(6,5)\in {ℝ}^2$ ist ein Vektor mit zwei Komponenten. Besitzen die Komponenten des Vektors Nachkommastellen, werden diese mit einem Punkt notiert - z.B.$(6.12,5.898)\in {ℝ}^2$

Beispiel für einen Gradienten

Sei $f(x_1,x_2):=x_1^3\cdot x_2+x_2^2$:

$\begin{array}{ccc}\mathrm{Grad}(f)(x_1,x_2)& =& (\frac{\partial f}{\partial x_1}(x_1,x_2),\frac{\partial f}{\partial x_2}(x_1,x_2))\\ & =& (3x_1^2{x}_2,x_1^3+2x_2)\end{array}$

Damit können wir den Gradienten an einer bestimmten Stelle im Definitionsbereich berechnen:

$\mathrm{Grad}(f)(1,2)=(6,5)$

CAS4Wiki

Mit CAS4Wiki können Sie die obigen Ableitungen berechnen, siehe z.B. partielle Ableitungen

Beispiel - normierter Gradienten

Mit einem vom Nullvektor verschiedenen Gradienten $\mathrm{Grad}(f)(1,2)=(6,5)$ kann man einen normierten "negativen" Gradienten erzeugen:

$d^{(j)}:=-\frac{\mathrm{Grad}(f(1,2))}{\Vert \mathrm{Grad}(f(1,2))\Vert }=\frac{(-6,-5)}{\sqrt{36+25}}=(-\frac{6}{\sqrt{61}},-\frac{5}{\sqrt{61}})$

Das Verfahren

Als Einführung in das Gradientenabstiegsverfahren wird eine vereinfachte Schrittweitenberechnung verwendet.

• Das Verfahren bricht ab, wenn der Gradient der Nullvektor ist.
• Ist der Gradient nicht der Nullvektor, wird der negative Gradient zunächst auf die Länge 1 normiert und mit der Schrittweite ${\alpha }_j$ multipliziert.
• Die Schrittweite wird halbiert, wenn nach dem Iterationsschritt der Funktionswert (z.B. Kosten) nicht abnehmen.
• Eine weitere Abbruchbedingung für die Iteration ist, wenn die Schrittweite eine Genauigkeitsgrenze $\epsilon >0$ unterschreitet (d.h. ${\alpha }_j<\epsilon$).

Start der Optimierung

Als Anfangspunkt wird eine Stelle $x^{(0)}$ aus dem Definitionsbereich der Funktion $f$ ausgewählt, für die man lokale Minima mit dem Gradientenabstiegsverfahren annähern möchte.

Richtung des steilsten Abstiegs

Ausgehend von einem Anfangspunkt $x^{(0)}$ bzw. von der aktuellen Stelle $x^{(j)}$ für den nächsten Iterationsschritt wird die Richtung des steilsten Abstiegs durch $-\mathrm{Grad}(f(x^{(j)}))$ bestimmt, wobei $\mathrm{Grad}(f(x^{(j)}))\in {ℝ}^n$ den Gradienten von $f$ an der Stelle $x^{(j)}\in {ℝ}^n$ bezeichnet. Dieser zeigt in die Richtung des "größten Anstiegs". Das negative Vorzeichen vor dem Gradienten sorgt dafür, dass man sich mit den Iterationsschritten in die Richtung des stärksten Abfalls bewegt (z.B. Minimierung der Kostenfunktion/Fehlerfunktion $f$).

Normierung des Richtungsvektors

Das vereinfachte Interationsverfahren bricht bei der Bedingung ab, wenn $\Vert \mathrm{Grad}(f(x^{(j)}))\Vert <\epsilon$. Ansonsten wird der Richtungsvektor für den folgenden Iterationsschritt normiert (dies ist optional, um die Schrittweite im Lernalgorithmus zu normalisieren) :

$d^{(j)}:=-\frac{\mathrm{Grad}(f(x^{(j)}))}{\Vert \mathrm{Grad}(f(x^{(j)}))\Vert }$ mit Euklidischer Norm $\Vert x\Vert :=\Vert (x_1,\dots ,x_n)\Vert :=\sqrt{\sum _{k=1}^n{x}_k^2}$

Iterationsschritt

Gradient Descent - Trajectory of Points

Formal notiert man diesen Iterationsschritt wie folgt:

$x^{(j+1)}=\{\begin{array}{cc}{x}^{(j)}+{\alpha }^{(j)}{d}^{(j)},& \text{wenn }f(x^{(j)}+{\alpha }^{(j)}{d}^{(j)})<f(x^{(j)})\text{ (Verbesserung) }\\ x^{(j)},& \text{sonst }\end{array}$

Wenn keine Verbesserung vorliegt, wird die Schrittweite verkleinert (z.B. halbiert).

Festlegung der Schrittweite

Die Schrittweite wird so lange für den nächsten Iterationsschritt verwendet, bis sich die Kostenfunktion $f$ mit dem nachfolgenden Schritt erhöht. In diesem einführenden Beispiel wird die Schrittweite ${\alpha }^{(j)}$ halbiert. Formal

${\alpha }^{(j+1)}=\{\begin{array}{cc}{\alpha }^{(j)},& \text{wenn }f(x^{(j)}+{\alpha }^{(j)}{d}^{(j)})<f(x^{(j)})\text{ (Verbesserung) }\\ \frac{{\alpha }^{(j)}}{2},& \text{sonst }\end{array}$

Alternative Schrittweitenverkleinerung

Die Schrittweitenverkleinerung kann allgemein auch durch einen Faktor $\delta$ mit $0<\delta <1$ über

${\alpha }^{(j+1)}:={\alpha }^{(j)}\cdot \delta$

ersetzt werden.

Schrittweitenfestlegung pro Iterationsschritt

Dabei ist ${\alpha }^{(j)}>0$ die Schrittweite im j-ten Iterationsschritt. Diese Schrittweite muss in jedem Schritt des Iterationsverfahrens bestimmt werden. Hierfür gibt es im Allgemeinen unterschiedliche Möglichkeiten, wie die Rückführung der Schrittweitenbestimmung auf ein eindimensionales Optimierungsproblem. Die hier gewählte Schrittweitenoptimierung ist als Einführung in das Thema gewählt worden.

Gradientenabstieg in Tabellenkalkulation

In der folgenden ZIP-Datei von GitHub befindet sich eine LibreOffice-Datei mit einem exemplarischen Gradientenabstieg für die Kostenfunktion:

$f(x_1,x_2):=\sin (x_1)+\cos (x_2)+3$.

Die Kostenfunktion hat auf ihrem Definitionsbereich ${ℝ}^2$ unendlich viele lokale Minima. Das Minimum der Kostenfunktion ist nach Definition -1. In jeder Tabellenzeile wird ein Iterationsschritt durchgeführt und überprüft, ob die Kostenfunktion nach dem Iterationsschritt tatsächlich abnimmt.

• ZIP-Datei von GitHub
• GradientDescent-Repository auf GitHub

Rückführung auf ein eindimensionales Optimierungsproblem

Eine Methode besteht darin, ${\alpha }^{(j)}$ durch die Minimierung der Funktion auf dem (eindimensionalen) "Strahl" $x^{(j)}(\alpha )$ zu bestimmen, der ausgehend von $x^{(j)}$ in Richtung des negativen Gradienten zeigt. Die eindimensionale zu minimierende Funktion $M$ ist wie folgt definiert.

$M:{ℝ}^{+}\to ℝ,\alpha \mapsto M(\alpha ):=f(x^{(j)}(\alpha ))f(x^{(j)}+\alpha d^{(j)})$

mit $x^{(j)}(\alpha )=x^{(j)}+\alpha d^{(j)}.$

Man berechnet in diesem Fall das $x^{(j+1)}:=x^{(j)}({\alpha }_o)$ mit ${\alpha }_o>0$ so, dass $M({\alpha }_o)$ minimal wird. d.h.:

$f\left(x^{(j+1)}\right)=\underset{\alpha >0}{\min }f(x^{(j)}(\alpha )).$

Dies ist ein einfaches, eindimensionales Optimierungsproblem, für das es spezielle Verfahren der Schrittweitenbestimmung gibt.

Schrittweiten und iterierte Schrittweitenverkleinerung

Eine andere Methode besteht darin, ${\alpha }^{(j)}$ von der Minimierung der Funktion $f$ abhängig zu machen, d. h. von der Bedingung $f(x^{(j+1)})<f(x^{(j)})$. Wird mit dem Iterationsschritt der Funktionswert mit einer Startschrittweite ${\alpha }_0>0$ nicht vermindert, verkleinert man die Schrittweite z. B. mit ${\alpha }_{k+1}:={\alpha }_k\cdot s$ mit $0<s<1$ weiter, bis die Schrittweite ausgehend von $x^{(j)}$ in Richtung des negativen Gradienten tatsächlich einen Funktionswert $f(x^{(j)}+{\alpha }_k{d}^{(j)})<f(x^{(j)})$ liefert und setzt $x^{(j+1)}=x^{(j)}+{\alpha }_k{d}^{(j)}$.

Hat man im Iterationsverfahren eine Stelle $x^{(j+1)}\in {ℝ}^n$ mit $\mathrm{Grad}(f(x^{(j+1)}))=\mathrm{𝟎}\in {ℝ}^n$ erreicht, liegt eventuell eine lokale Extremstelle von $f$ vor (Überprüfung bzw. Abbruch des Iterationsverfahrens).

Abbruchbedingung

Ein zentrales Kriterium für eine Abbruchbedingung ist, dass $d^{(j)}=-\mathrm{Grad}(f(x^{(j)}))=\mathrm{𝟎}\in {ℝ}^n$ ist.

Sattelpunkt/Sattelfläche

Wie in der reellen eindimensionalen Analysis muss sich an dieser Stelle $x^{(j)}\in {ℝ}^n$ kein lokales Minimum befinden (eindimensional Sattelpunkt, mehrdimensional z.B. Sattelfläche). Wenn für $f:U\to ℝ$ zweimal stetig differenzierbar ist und die Hesse-Matrix an dieser Stelle positiv definit ist, liegt in $x^{(j)}\in {ℝ}^n$ hinreichendes Kriterium für ein lokales Minimum. Dieses wird ausgegeben und die Iteration abgebrochen.

Schrittweite als Abbruchbedingung

Wird der Algorithmus auf einem Computer ausgeführt, ist ein mögliches weiteres Abbruchkriterium die Schrittweitenlänge, wenn diese kleiner wird als eine untere Grenze $\epsilon >0$ mit der Bedingung ${\alpha }^{(j)}<\epsilon$.

Verbesserungsschritte als Abbruchbedingung

Ferner kann das Gradientenabstiegsverfahren abgebrochen werden, wenn die Verbesserung der Optimierung von $f$ in den Iterationsschritten kleiner als eine untere Grenze wird.

Bedeutung von Abbruchkriterien

Durch solche Abbruchkriterien wird algorithmisch gewährleistet, dass das Gradientenabstiegsverfahren nicht in einer Endlosschleife der Iterationen landet.

Aufgabe

• Erläutern Sie, wie im Kontext von künstlichen neuronalen Netzen das Gradientenabstiegsverfahren für die Fehlerminimierung beim Maschinellen Lernen eingesetzt werden kann (Backpropagation)?
• Überprüfen Sie, ob und wie man mehrdimensionalen linearen Regression das Gradientenabstiegsverfahren einsetzen kann (siehe /Gradient - lineares Funktional/)!

Videos

• Höhenlinien, Gradient, Vektorfeld, Vektoranalysis, ... Youtube-Video (21.07.2015) von Daniel Jung
• Gradient und Totales Differential Youtube-Video (21.07.2015) von Daniel Jung

Siehe auch

• Gradient
• Kurs:Numerik I
• Maschinelles Lernen
• Backpropagation als Anwendungsbeispiel
• mehrdimensionale lineare Regression

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Numerik' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Gradientenabstiegsverfahren
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.