Gradientnedstigning
I denne note vil vi forklare hvad gradientnedstigning går ud på, og hvordan gradientnedstigning kan bruges i forbindelse med at bestemme minimum eller maksimum for en funktion.
Vi vil her nøjes med at se på en funktion \(f(x,y)\) af to variable. I noten om funktioner af flere variable har vi skrevet, at gradientvektoren
\[ \nabla f\left( x_{0},y_{0} \right) = \begin{pmatrix} f_x\left( x_{0},y_{0} \right) \\ f_y\left( x_{0},y_{0} \right) \\ \end{pmatrix} \]
angiver den retning, man skal bevæge sig væk fra punktet \((x_{0},y_{0})\), for at funktionsværdierne \(f(x,y)\) vokser mest muligt. Det er denne egenskab, som vi vil bevise her og forklare, hvordan den kan bruges til at bestemme maksimum eller minimum for en funktion. For at gøre det må vi starte med at definere de såkaldte retningsafledede.
Retningsafledede
Når vi står i et punkt \((x_{0},y_{0})\) og gerne vil undersøge i hvilken retning funktionsværdien vokser mest, så kunne vi jo starte med at udregne de to partielle afledede
\[ f_x( x_{0},y_{0}) \quad \textrm{og} \quad f_y( x_{0},y_{0}). \]
Disse to størrelser angiver væksthastigheden i henholdsvis \(x\)- og \(y\)-aksens retning. Men der er ingen, som siger, at det lige præcis er i en af de to retninger, at funktionsværdien vokser mest. Det kunne lige så godt være i en hvilken som helst anden retning.
Vi vil her angive den retning i \(xy\)-planen, som vi nu vil bevæge os i med en enhedsvektor – det vil sige en vektor med længde 1:
\[ \vec{u} = \begin{pmatrix} u_{1} \\ u_{2} \\ \end{pmatrix} \] hvor altså \(\lvert \vec u \rvert = 1\).
Vi definerer nu den retningsafledede af \(f\) i punktet \((x_{0},y_{0})\) i retningen \(\vec{u}\) ved
\[ D_{\vec{u}}f\left( x_{0},y_{0} \right) = \lim_{h \rightarrow 0}\frac{f\left( x_{0} + hu_{1},y_{0} + hu_{2} \right) - f(x_{0},y_{0})}{h} \tag{1}\]
hvis ellers grænsen eksisterer.
Bemærk, at hvis \(\vec{u}\) peger i \(x\)-aksens retning, så bliver den retningsafledede til \(f_x(x_{0},y_{0})\), og hvis den peger i \(y\)-aksens retning, bliver den til \(f_y(x_{0},y_{0})\).
Af definitionen kan man se, at man udregner en sekanthældning ved at tage et skridt \(h\) i \(\vec{u}\)’s retning og dividere den fundne funktionstilvækst med \(h\). Derefter lader man \(h\) gå mod 0. Det giver hældningen af grafen for \(f\) i punktet \((x_{0},y_{0})\) i retningen \(\vec{u}\). Og dermed altså væksthastigheden for \(f\) i retningen \(\vec{u}\).
Idéen med den retningsafledede er illustreret i figuren nedenfor. Til venstre ses en repræsentant for \(\vec u\) i \(xy\)-planen. Man kan ændre på den retning, som \(\vec u\) peger i, ved at trække i skyderen. Til højre ses grafen for en funktion \(f\) af to variable, hvor et punkt \(P(x_0,y_0,f(x_0,y_0))\) på grafen er indtegnet. Samtidig vises den snitkurve som fås, hvis man på grafen i punktet \(P\) bevæger sig langs en linje i retningen \(\vec u\). Denne snitkurve har i punktet \(P\) en tangent, som også er indtegnet, og denne tangents hældning vil netop svarer til størrelsen af den retningsafledede \(D_{\vec{u}}f\left( x_{0},y_{0} \right)\). Hvis man ændrer på den retning, som \(\vec u\) peger i, kan man se, hvordan størrelsen af den retningsafledede ændrer sig.
Det viser sig, at man kan udregne de retningsafledede med et prikprodukt:
\[ D_{\vec{u}}f\left( x_{0},y_{0} \right) = \nabla f(x_{0},y_{0}) \cdot \vec{u}. \]
Vi vil nedenfor argumentere for formlen, men lad os først se på konsekvenserne af den. Vi ved fra almindelig vektorregning, at
\[ \vec{a} \cdot \vec{b} = \lvert \vec{a} \rvert \cdot \lvert \vec{b} \rvert \cdot \cos(v) \]
hvor \(v\) er vinklen mellem de to vektorer. Da \(\lvert \vec{u} \rvert = 1\) betyder det, at
\[ D_{\vec{u}}f\left( x_{0},y_{0} \right) = \lvert \nabla f(x_{0},y_{0}) \rvert \cdot \cos(v) \]
hvor \(v\) er vinklen mellem gradientvektoren \(\nabla f\left( x_{0},y_{0} \right)\) og den valgte retning \(\vec{u}\).
Vi ved, at \(-1 \leq \cos(v) \leq 1\) samt at \(\cos(0^{{^\circ}})=1\) og \(\cos(180^{{^\circ}})=-1\). Det følger derfor, at den retningsafledede er størst (og dermed at \(f\) vokser mest), når \(\vec{u}\) peger i \(\nabla f(x_{0},y_{0})\)’s retning. Og tilsvarende at den retningsafledede er mindst (og dermed at \(f\) aftager mest), når \(\vec{u}\) peger i \(-\nabla f(x_{0},y_{0})\)’s retning. Det vil sige, at den retningsaflededes størsteværdi er
\[ D_{\vec{u}}f\left( x_{0},y_{0} \right) = \ \ \ \lvert \nabla f(x_{0},y_{0}) \rvert \]
når \(v = 0^{{^\circ}}\) og retningsaflededes mindsteværdi er
\[ D_{\vec{u}}f\left( x_{0},y_{0} \right) = - \lvert \nabla f(x_{0},y_{0}) \rvert \]
når \(v = 180^{{^\circ}}\). Det var netop, hvad vi gerne ville vise.
Princippet er illustreret i figuren herunder. Gradientvektoren \(\nabla f(x_{0},y_{0})\) er indtegnet (med blå) og man kan se, at den retningsafledede antager den største værdi, netop når \(\vec u\) peger i gradientens retning (prøv at trække i skyderen). Og omvendt antager den retningsafledede den mindste værdi, når \(\vec u\) peger i minus gradientens retning.
For at vise, at man kan udregne de retningsafledede med et prikprodukt:
\[ D_{\vec{u}}f\left( x_{0},y_{0} \right) = \nabla f(x_{0},y_{0}) \cdot \vec{u} \]
kan du vælge enten at læse et bevis, som baserer sig på geometriske argumenter eller et bevis som er baseret på middelværdisætningen.
Optimering ved hjælp af gradientnedstigning
Vi vil nu se på, hvordan gradienten kan bruges til at bestemme maksimum eller minimum for en funktion.
Betragt en funktion \(f\) givet ved forskriften \[ f\left( x,y \right) = \left( \left( x - 5 \right)^{2} + 3 \right) \cdot \left( 5 + \left( y - 10 \right)^{2} \right) + 30 \]
Hvis man ser lidt på forskriften, kan man måske overbevise sig selv om, at funktionen har et minimum på 45, som fås, når \(\left( x,y \right) = (5,10)\).
Grafen ses herunder.
Man kan lave en iterativ metode til at finde minimumspunktet ved at udnytte egenskaben ved gradientvektoren:
- Vælg et startpunkt \((x_0,y_0)\) som et første gæt på et minimumspunkt.
Vi udnytter nu, at \(- \nabla f(x_0,y_0)\) angiver den retning, hvor funktionsværdien falder mest i punktet \((x_0,y_0,f(x_0,y_0))\).
Gå derfor et lille skridt i retningen \(- \nabla f(x_0,y_0)\). Det giver så det næste punkt \((x_1,y_1)\), som forhåbentlig er et bedre bud på et minimumspunkt.
Processen foregår i definitionsmængden, men på grafen svarer det til at gå et lille stykke den stejleste vej ned ad bakken.
Processen itereres så gentagne gange indtil man forhåbentlig når minimumspunktet.
Vælger vi med den konkrete funktion et startpunkt på
\[ (x_0,y_0) = ( - 3,4) \]
og vælger vi i hvert skridt at lægge -0,001 gange den negative gradientvektor i punktet til, så kan nogle af de følgende \((x,y)\)-punkter ses til venstre i figur 1. Læg her mærke til hvordan vi nærmer os det globale minimumssted i \((5,10)\). Til højre i figur 1 ses det også hvordan vi ved hjælp af gradientnedstigning, nærmer os den globale minimumsværdi på \(f(5,10)=45\).
Vi ser, at den iterative gradientnedstigning faktisk nærmer sig det globale minimumspunkt. Så om ikke andet så virker metoden i hvert fald i dette konkrete tilfælde.
Træning af neurale netværk
At lede efter et globalt minimumspunkt eller i det mindste et brugbart lokalt minimumspunkt for en funktion af rigtig mange variable er et problem, man står overfor, når man skal træne et neuralt netværk og have fastlagt en masse vægte i netværket.
Det kan ikke gøres analytisk, så derfor bruger man netop en iterativ proces baseret på gradientnedstigning som metode til at finde frem til minimumspunktet. Eksemplet ovenfor illustrerer derfor idéen bag en central del af træningen af et neuralt netværk.
Læs mere om hvordan gradientnedstigning konkret bruges her: Perceptroner og Kunstige neurale netværk.