11.02.2017

Dieses Verfahren braucht man beim Machine Learning Algorithmus Adaline, weshalb ich hier einen mathematischen Einstieg in das Thema geben möchte. Beachten Sie, dass ich kein Mathematiker bin. Falls etwas nicht stimmt, dürfen Sie mich gerne korrigieren.

Das Gradientenabstiegsverfahren ist ein Verfahren, um bei einer Funktion das Minimum oder das Maximum zu finden.

Das kann ich schon mit Analysis!

Wie man das Minimum oder das Maximum findet haben wir in der Analysis gelernt:

Beispielfunktion:

f(x) = x^2 - 2x + 2

Vorgehen:
1. Die erste Ableitung von f herausfinden und = 0 setzen und auflösen

f'(x) = 2x - 2 = 0
x = 1

2. Bonusschritt: Die zweite Ableitung von f herausfinden und den gefundenen x-Wert aus 1 einsetzen

ist f'' < 0 -> Maximum
ist f'' > 0 -> Minimum

f''(x) = 2 -> Also ein Minimum

Warum also das Gradientenverfahren?

Also zuerst einmal schreibe ich extra diesen Blogeintrag, um das Gradientenverfahren zu erläutern, da wünsche ich mir schon ein bisschen Interesse! Und zweitens hat man in der Realität oftmals nicht solche einfache Funktionen wie x^2 – 2x + 2, sondern hochkomplizierte Gleichungen. Und wenn man diese dann noch = 0 setzen und auflösen soll – viel Spass damit!

Was ist denn ein Gradient?

Ah, jetzt also plötzlich doch Interesse. Nun, ein Gradient zeigt den höchsten Punkt einer Funktion. Oder etwa auf den höchsten Punkt beziehungsweise den steilsten Anstieg eines Berges.

Ich denke, so kann man sich das am Besten vorstellen. Stellen Sie sich vor, sie gingen mit einer Klasse von Schülern zum Matterhorn spazieren. Und ein Schüler hat eine ganz besondere Macke: Er zeigt mit seinem Arm immer genau zur Spitze des Berges. Den Schüler dürfen Sie dann spasseshalber Gradient nennen.

Wenn Sie sich ein Vektorfeld vorstellen, also etwa ein Feld mit 10*10 Punkten, dann würde von jedem Punkt aus ein Vektor zum höchsten Ding zeigen – Sei dieses Ding nun der wärmste Ort, der höchste Berg oder der hellste Punkt. Je nachdem, was Sie halt gerade für ein Bild anschauen. Und bei jedem Punkt gibt es einen solchen Gradienten.

Aber wir suchen doch das Minimum nicht den höchsten Berg

Ja genau, darum heisst es auch Gradientenabstiegsverfahren. Aber das kommt nicht so sehr drauf an. Man kann mit dem Gradientenverfahren ein Maximum oder ein Minimum suchen, dabei ändert sich nur ein Plus zu einem Minus.

Genug gequatscht!

Genau, jetzt schauen wir uns das Gradientenabstiegsverfahren an. Wir suchen also das Minimum einer Funktion.

Zuerst einmal das ganz allgemeine Vorgehen: Beim Gradientenabstiegsverfahren fängt man bei irgendeinem x Wert der gegebenen Funktion an. Dazu bildet man an diesem Punkt den Gradienten, also den Vektor, der zum tiefsten Punkt zeigt (und eben nicht zum höchsten, weil wir suchen ja das Minimum – sollte klar sein).

Dann gehen wir auf der Funktion in Richtung des Minimums um eine gewisse Schrittlänge. Nun sind wir dem Minimum also ein wenig nähergekommen.

Und jetzt berechnen wir wieder den aktuellen Gradienten, gehen dann eine Schrittlänge etc. bis wir beim Minimum angekommen sind.

Man merkt, dass man beim Minimum angekommen ist, wenn der y-Wert mit dem gefundenen x-Wert nicht mehr kleiner wird. Dann ist man beim Minimum.

Und wie berechnet man den Gradienten?

Ganz einfach mit der (partiellen) Ableitung!

Beispiel: Wir haben die Funktion: f(x) = x^2 – 2x + 2 und wollen davon das Minimum herausfinden.

1. Wählen Sie eine zufälliges x

Etwa x = 3

2. Leiten Sie die Funktion ab

f'(x) = 2x - 2

3. Setzen Sie das x in die Ableitung

f'(3) = 2*3 - 2 = 4

4. Analysieren Sie das Ergebnis

Sie wissen hoffentlich noch, dass die Ableitung auch die Steigung des Vektors (oder der Tangente) an einem Punkt bedeutet.

Ist die Steigung positiv, geht der Vektor von links unten nach rechts oben. Ist die Steigung negativ, geht sie von links oben nach rechts unten.

Wenn nun die Steigung positiv ist, heisst das, wir sind bereits am Minimum vorbei und müssen zurück auf der Funktion – Wir müssen also unser gewähltes x verkleinern.

Beim Maximum ist es übrigens dasselbe Verfahren einfach „Vorwärts gehen“ und „Rückwärts gehen“ sind vertauscht.

Ist die Steigung negativ, sind wir vor dem Minimum und müssen auf der Funktion vorwärts gehen – Und unser gewähltes x ein wenig vergrössern.

5. Nun können Sie also das neue x mit der gewählten Schrittlänge herausfinden und dann zum Schritt 3 gehen, bis das Minimum gefunden ist.

Was heisst partielle Ableitung schon wieder?

Bei der Funktion oben hatten wir nur eine Variable, nämlich x. Oftmals hat man aber noch ein y und vielleicht noch ein z. Für den Gradienten muss man dann die partielle Ableitung machen. Das bedeutet, man leitet die Funktion nach jeder dieser drei Variablen ab. Leitet man etwa nach x ab, werden y und z wie Konstanten behandelt. Am einfachsten stellt man sich für y und z dann zum Beispiel eine 1 vor und leitet die Variablen so ab, wie man eine 1 ableiten würde.

Beispiel
f(x,y,z) = x^2 * y^2 + z^3

Abgeleitet nach x = 2x * y^2

Abgeleitet nach y = 2y * x^2

Abgeleitet nach z = 3z^2

Diese drei Teile in einem Vektor geschrieben gibt dann den Gradientenvektor. Sucht man dann etwa den Gradienten beim Punkt P(1,1,1) setzt man diese Werte einfach in den Gradientenvektor und erhält den Gradientenvektor beim Punkt 1,1,1 = (2, 2, 3).

Die Länge des Gradientenvektors steht dabei für seine Steilheit/Steigung. Die Länge eines Vektors berechnet man folgendermassen:

|(2, 2, 3)| = WurzelVon( 2^2 + 2^2 + 3^2 ) = 4.12

Die Ableitung einer einfachen Funktion nach x ist wie gesagt die Steigung der Funktion. Und Steigung bedeutet nichts anderes als die Änderung der Funktion beziehungsweise irgendeiner Grösse. Mathematisch gesehen ist die partielle Ableitung einer Funktion die Veränderung dieser Grösse in eine der drei Richtungen x, y oder z.

Nabla

Nachdem mir kein besserer Wortwitz für diesen Nabla Absatz eingefallen ist als „Das Kind muss sich früher oder später von seinen Eltern abnabla“ habe ich es gelassen.

Auf jeden Fall ist der Nabla Operator das Dreieck, dass nach unten zeigt, und steht schlussendlich für einen Vektor, der die partiellen Ableitungen beinhaltet. Dieses komische Ding, das wie eine verkehrte 6 aussieht, steht für die partielle Ableitung.

Warum zeigt der Gradient immer zum höchsten Punkt? Magic?

Das scheint mir eine längere Geschichte zu sein weshalb ich einen eigenen Artikel dazu schreiben werde.

Ich bin verwirrt – Wo waren wir?

Also nochmals kurz zusammengefasst: Das Gradientenverfahren verwenden wir, um das Minimum oder Maximum einer Funktion zu finden. Man fängt dabei bei einem Punkt der Kurve an und berechnet den Gradienten mit der partiellen Ableitung nach jeder Variablen. Der Gradient zeigt immer zum höchsten/tiefsten Punkt. Wenn man diesen berechnet hat, weiss man, ob man auf der Funktion vor oder zurück muss, um zum Minimum/Maximum zu kommen. Dabei verwendet man eine gewisse Schrittlänge, mit der man sich dem Minimum/Maximum nähert.

Scheint eine bombensichere Sache zu sein

Nun, etwas muss man beachten: Die Schrittlänge darf nicht zu gross sein, da man dann Gefahr läuft, über das Minimum hinüberzuspringen und es so zu verpassen. Macht man dann den nächsten Schritt, springt man wieder über das Minimum – Und so kann das dann endlos weitergehen.

Die Schrittlänge muss daher genügend klein gewählt werden. Ist sie aber „zu“ klein, kann es ewig dauern, bis man beim Minimum angekommen ist.

Um diesen beiden Problemen entgegenzuwirken, macht man oftmals eine Standardisierung, welche die Daten den Eigenschaften einer Standardnormalverteilung anpassen. Aber auch dies ist eine Geschichte für ein anderes Mal.